Efficient
Algorithms for Neighbor Discovery in Wireless Networks
ABSTRACT:
Neighbor
discovery is an important first step in the initialization of a wireless ad hoc
network. In this paper, we design and analyze several algorithms for neighbor
discovery in wireless networks. Starting with a single-hop wireless network of
nodes, we propose a ALOHA-like neighbor discovery algorithm when nodes cannot
detect collisions, and an order-optimal receiver feedback-based algorithm when
nodes can detect collisions. Our algorithms neither require nodes to have a
priori 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. We finally
show that receiver feedback can be used to achieve a running time, even when
nodes cannot detect collisions. We then analyze neighbor discovery in a general
multihop setting. We establish an upper bound of on the running time of the
ALOHA-like algorithm, where denotes the maximum node degree in the network and the
total number of nodes. We also establish a lower bound of on the running time
of any randomized neighbor discovery algorithm. Our result thus implies that
the ALOHA-like algorithm is at most a factor worse than optimal.
EXISTING SYSTEM:
1) Neighbor discovery needs to cope with
collisions. Ideally, a neighbor discovery algorithm needs to minimize the probability
of collisions and, therefore, the time to discover neighbors.
2) In many practical settings, nodes
have no knowledge of the number of neighbors, which makes coping with
collisions even harder.
3) When nodes do not have access to a
global clock, they need to operate asynchronously and still be able to discover
their neighbors efficiently.
4) In asynchronous systems, nodes can
potentially start neighbor discovery at different times and, consequently, may
miss each other’s transmissions.
5) Furthermore, when the number of
neighbors is unknown, nodes do not know when or how to terminate the neighbor discovery
process.
PROPOSED SYSTEM:
In this paper, we present neighbor
discovery algorithms that comprehensively address each of these practical
challenges under the standard collision channel model. Unlike existing approaches
that assume a priori knowledge of the number of neighbors or clock
synchronization among nodes, we propose neighbor discovery algorithms that:
P1 do not require nodes to have a
priori knowledge of the number of neighbors;
P2 do not require synchronization among
nodes;
P3 allow nodes to begin execution at
different time instants;
P4 enable each node to detect when to
terminate the neighbor discovery process.
To the best of our knowledge, our work
provides the first solution to the neighbor discovery problem that satisfies
all of the properties P1–P4. Our approach is to start with a single-hop wireless
network in which nodes are synchronized and know exactly how many neighbors
they have. As we will see, the analysis in such a simplistic setting yields
several valuable insights about the neighbor discovery problem. These insights allow
us to progressively relax each of the assumptions leading to a complete and
practical solution to the neighbor discovery problem in a multihop network setting.
ALGORITHMS USED:
SYSTEM CONFIGURATION:-
HARDWARE REQUIREMENTS:-
ü Processor - Pentium –IV
ü Speed - 1.1
Ghz
ü RAM - 256
MB
ü Hard
Disk - 20
GB
ü Key
Board - Standard
Windows Keyboard
ü Mouse - Two or Three Button Mouse
ü Monitor - SVGA
SOFTWARE
REQUIREMENTS:
•
Operating system : - Windows XP.
•
Coding Language : C#.Net.
REFERENCE:
Sudarshan Vasudevan, Micah Adler, Dennis
Goeckel, and Don Towsley, “Efficient
Algorithms for Neighbor Discovery in Wireless Networks”, IEEE/ACM
TRANSACTIONS ON NETWORKING, VOL. 21, NO. 1, FEBRUARY 2013.
