Neighbor discovery in multi-hop wireless networks: evaluation and dimensioning with interference considerations

In this paper, we study the impact of collisions and interference on a neighbor discovery process in the context of multi-hop wireless networks. We consider three models in which interference and collisions are handled in very different ways. From an ideal channel where simultaneous transmissions do not interfere, we derive an alternate channel where simultaneous transmissions are considered two-by-two under the form of collisions, to finally reach a more realistic channel where simultaneous transmissions are handled under the form of shot-noise interference. In these models, we analytically compute the link probability success between two neighbors as well as the expected number of nodes that correctly receive a Hello packet. Using this analysis, we show that if the neighbor discovery process is asymptotically equivalent in the three models, it offers very different behaviors locally in time. In particular, the scalability of the process is not the same depending on the way interference is handled. Finally, we apply our results to the dimensioning of a Hello protocol parameters. We propose a method to adapt the protocol parameters to meet application constraints on the neighbor discovery process and to minimize the protocol energy consumption.