Neighbor node discovery is an important first
step in the initialization of a wireless ad hoc network. In this
paper, we design and analyse several types of algorithms for
neighbor node discovery in wireless ad-hoc networks.
Starting with a single-hop wireless network of nodes, we
propose a O (n ln n) ALOHA-like neighbor discovery
algorithm when nodes cannot detect collisions, and an orderoptimal
O(n) receiver feedback-based algorithm when nodes
can detect collisions. Our algorithms neither require nodes
to have a priori knowledge or estimates of the number of
neighbors nor synchronization between nodes. Our
algorithms allow nodes to begin execution at different time
instants and to terminate neighbor discovery upon
discovering all their neighbors.
Snehal V. Ambatkar : Department C.S.E.( M.Tech.), R.C.E.R.T. Gondwana University.
Chandrapur, Maharashtra 442401, India.
Pravin Kulkarni : Department C.S.E.( M.Tech.), R.C.E.R.T. Gondwana University.
Chandrapur, Maharashtra 442401, India.
Ad hoc Networks, Initialization, Neighbor
Discovery, Randomized Algorithms, Wireless Networks
In this paper, we have presented efficient neighbor
discovery algorithms for wireless networks that is
comprehensively address various practical limitations of
the earlier approaches. Our neighbor discovery algorithms
do not require estimates of node density and allow
asynchronous operation. Furthermore, as the algorithms
allow nodes to begin execution at different times and also
allow nodes to detect termination. Our analysis shows a
gap between the lower and upper bounds on the running
time for neighbor discovery in the network case. Clearly,
the quest for an order-optimal neighbor discovery
algorithm remains an intriguing prospect. Of particular
interest is the question of whether the feedback-based
algorithms, which are order-optimal in the single-hop
case, can be extended to the multihop network setting
while outperforming the ALOHA-like algorithm. Another
direction of interest is the extension of the various
algorithms and the analysis presented in this paper to
wireless channel models that incorporate phenomena such
as fading and shadowing.
[1] C. E. Perkins and E. M. Belding-Royer, “Ad-hoc ondemand
distance vector routing,” in Proc. IEEE
WMCSA, 1999, pp. 90–100.
[2] J. Capetanakis, “Generalized TDMA: The multiaccessing
tree protocol,” IEEE Trans.
[3] Commun., vol. COM-27, no. 10, pp. 1479–1484, Oct.
1979.
[4] A. Keshavarzian and E. Uysal-Biyikoglu, “Energyefficient
link assessment wireless sensor networks,” in
Proc. IEEE INFOCOM, 2004, vol. 3, pp. 1751–1761.
[5] D. Angelosante, E. Biglieri, and M. Lops, “Neighbor
discovery wireless networks: A multiuserdetection
approach,” in Proc. Inf. Theory Appl. Workshop,
2007, pp. 46–53.
[6] G. Jakllari,W. Luo, and S. V. Krishnamurthy, “An
integrated neighbor discovery and MAC protocol for
ad hoc networks using directional antennas,” IEEE
Trans. Wireless Commun., vol. 6, no. 3, pp. 1114–
1024, Mar. 2007.
[7] H. David and H. Nagaraja, Order Statistics. Hoboken,
NJ: Wiley, 2003. [8] A. G. Greenberg and S. Winograd, “A lower bound on
the time needed worst case to resolve conflicts
deterministically multi-access channels,” J. ACM, vol.
32, no. 3, pp. 589–596, 1985.
[9] J. Hayes, “An adaptive technique for local
distribution,” IEEE Trans. Commun., vol. COM-26,
no. 8, pp. 1178–1186, Aug. 1978.
[10] D. Hush and C. Wood, “Analysis of tree algorithms
for RFID arbitration,” in Proc. IEEE Int. Symp. Inf.
Theory, 1998, p. 107.
[11] D. B. Johnson and D. A. Maltz, “Dynamic source
routing ad hoc wireless networks,” in Mobile
Computing. Norwell, MA: Kluwer, 1996, pp. 153–
181.
[12] R. Kalinowski,M. Latteux, and D. Simplot, “An
adaptive anti-collision protocol for smart labels,”
LIFL, University Lille, Lille, France, 2001.
[13] B. Karp and H. T. Kung, “Greedy perimeter stateless
routing for wireless networks,” in Proc. ACM
Mobicom, 2000, pp. 243–254
[14] M. J. McGlynn and S. A. Borbash, “Birthday
protocols for low energy deployment and flexible
neighbor discovery ad hoc wireless networks,” in
Proc. ACM Mobihoc, 2001, pp. 137– 145.
[15] L. Bao and J. J. Garcia-Luna-Aceves, “A new
approach to channel access scheduling for ad hoc
networks,” in Proc. ACM Mobicom, 2001, pp. 210–
221.
[16] M. J. McGlynn and S. A. Borbash, “Birthday
protocols for low energy deployment and flexible
neighbor discovery ad hoc wireless networks,” in
Proc. ACM Mobihoc, 2001, pp. 137– 145.
