Neighbor discovery in wireless networks and the coupon collector's problem

ABSTRACT

Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical {\em Coupon Collector's Problem}. Consequently, we show that each node discovers all its $n$ neighbors in an expected time equal to $ne (\ln n + c)$, for some constant $c$. When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a $\ln n$ improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing $n$ results in no more than a factor of two slowdown in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase.

References

1. D. Angelosante, E. Biglieri, and M. Lops. Neighbor discovery in wireless networks:a multiuser-detection approach. In Information Theory and Applications Workshop, pages 46--53, 2007.
2. L. Bao and J. J. Garcia-Luna-Aceves. A new approach to channel access scheduling for ad hoc networks. In ACM MOBICOM, pages 210--221, 2001.
3. S. A. Borbash, A. Ephremides, and M. J. McGlynn. An asynchronous neighbor discovery algorithm for wireless sensor networks. Ad Hoc Networks, 5(7):998--1016, 2007.
4. P. Dutta and D. E. Culler. Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications. In ACM SenSys, pages 71--84, 2008.
5. P. Jacquet, P. Minet, P. Muhlethaler, and N. Rivierre. Priority and collision detection with active signaling - the channel access mechanism of hiperlan. Wireless Personal Communications, 4(1):11--25, 1997.
6. P. Jacquet and P. Muhlethaler. Data transmission device and method for random access network having advanced collision resolution, December 1996. http://www.freepatentsonline.com/EP0635184B1.html.
7. G. Jakllari, W. Luo, and S. V. Krishnamurthy. An integrated neighbor discovery and mac protocol for ad hoc networks using directional antennas. IEEE Transactions on Wireless Communications, 6(3):1114--1024, 2007.
8. D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, pages 153--181. Kluwer Academic Publishers, 1996.
9. A. Keshavarzian and E. Uysal-Biyikoglu. Energy-efficient link assessment in wireless sensor networks. In IEEE INFOCOM, 2004.
10. L. Li, J. Y. Halpern, P. Bahl, Y.-M. Wang, and R. Wattenhofer. A cone-based distributed topology-control algorithm for wireless multi-hop networks. IEEE/ACM Transactions on Networking, 13(1):147--159, 2005.
11. J. Luo and D. Guo. Neighbor discovery in wireless ad hoc networks based on group testing. In Annual Allerton Conference, 2008.
12. Maxim. 32.768khz temperature-compensated crystal oscillator. DS32kHz Data Sheet.
13. M. J. McGlynn and S. A. Borbash. Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks. In ACM MOBIHOC, pages 137--145, 2001.
14. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
15. R. Nelson. Probability, Stochastic Processes and Queueing Theory. Springer-Verlag, 1995.
16. K. Pister and L. Doherty. Tsmp: Time synchronized mesh protocol. In IASTED Distributed Sensor Networks, pages 391--398, 2008.
17. R. Ramanathan, J. Redi, C. Santivanez, D. Wiggins, and S. Polit. Ad hoc networking with directional antennas: a complete system solution. IEEE Journal on Selected Areas in Communications, 23:496--506, 2005.
18. L. Roberts. Aloha packet system with and without slots and capture. Computer Communications Review, 1972.
19. S. Vasudevan, J. F. Kurose, and D. F. Towsley. On neighbor discovery in wireless networks with directional antennas. In IEEE INFOCOM, pages 2502--2512, 2005.
20. S. Vasudevan, D. Towsley, D. Goeckel, and R. Khalili. Neighbor discovery in wireless networks and the coupon collector's problem. Technical Report UM-CS-2009-032, UMass Computer Science, 2009.

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks

• Theory of computation

  • Design and analysis of algorithms