Analytical Models for Randomized Neighbor Discovery Protocols based on Collision Detection in Wireless Ad Hoc Networks

Abstract

[EN] Neighbor discovery is a crucial first step after the deployment of wireless ad hoc networks, which do not have a communications infrastructure. In this paper we present analytical models of randomized neighbor discovery protocols for static one-hop environments: CDPRR (Collision Detection Probabilistic Round Robin) and CDH (Collision Detection Hello). For CDPRR we assumed a geometric distribution and a uniform distribution for CDH. For comparison purposes, we chose two protocols from the literature, i.e., Hello and PRR, to be used as reference. To assess the performance of the proposals we carried out a mathematical study regarding six metrics, i.e., neighbor discovery time, energy consumption, overhead (number of packets sent), packet delivery ratio, the CDF of discoveries, and percentage of idle slots, and presented graphical results obtained from the equations. According to the analytical results, CDH protocol outperforms the other solutions regarding the neighbor discovery time, energy consumption, number of packets sent, packet delivery ratio and CDF of discoveries, while CDPRR achieves good results and it is better than Hello and PRR in terms of neighbor discovery time, energy consumption, CDF of discoveries and the overhead (number of packets sent). Moreover, we found that CDPRR presents more percentage of idle slots than PRR, which is a clear advantage in terms of energy consumed and number of packets sent. In addition, as novelty compared to the reference protocols, we found that both CDH and CDPRR protocols manage to discover all the neighbors, know when to terminate the discovery process, and achieve to operate under more realistic assumptions. We also focused the study on the CDH protocol varying the slot width, and demonstrated that the number of nodes in the network can be unknown, still providing reasonable results.