On Expected Neighbor Discovery Time With Prior Information: Modeling, Bounds and Optimization

Neighbor discovery (ND) is an essential prerequisite for any peer-to-peer communication. In general, minimizing the discovery time is the goal for ND schemes. In this paper, we study the average discovery time for directional random ND when nodes have prior information about their set of possible neighbors, which also helps identify the performance limits of random ND schemes. Typically, discovery time analysis is done for assumptions that simplify the network structure, such as uniform neighbor relations for all nodes. However, with prior information the directional transmission probabilities depend on the node and the direction. This complicates the analysis of the expected discovery time. We first provide a closed-form expression for the expected discovery time based on the non-uniform coupon collector problem. Next, we identify directional transmission probabilities of each node that achieve a small discovery time. Due to the mathematical complexity, we provide a lower and an upper bound on the expected discovery time, which allows us to write the problem as a convex optimization problem. Through simulations, we demonstrate the performance gain due to prior knowledge with the proposed methods as compared with when no prior information is available, as well as the impact of uncertainty in the prior knowledge.