Neighbor Discovery in Wireless Networks: A Graph-based Analysis and Optimization

Abstract

The neighbor discovery (ND) procedure is typically performed during the network setup and allows nodes to learn about the existence of neighbors, exploiting the transmission of broadcast messages. Battery powered nodes impose many constraints on the ND protocol, such as low latency and energy efficiency. This calls for the deployment of dedicated and efficient ND protocols allowing nodes to be idle and save energy. We propose and analyze a new ND protocol, named collision resolution birthday protocol (CRBP), that drastically improves the performance of the birthday protocol (BP) making the use of multiple transmitted packets per node and successive interference cancellation (SIC). Via a bipartite graph analysis, we optimize the number of transmitted packets per node in order to maximize the discovery rate, under the asymptotically large frame assumption. Numerical simulations are performed for evaluating the goodness of the optimization also for finite frame durations.