14-11-2012, 01:12 PM
Continuous Neighbor Discovery in Asynchronous Sensor Networks
continous neighbour discovery in asynchronous sensor network.pdf (Size: 207.26 KB / Downloads: 46)
INTRODUCTION
A sensor network may contain a huge number of simple
sensor nodes that are deployed at some inspected site. In
large areas, such a network usually has a mesh structure. In
this case, some of the sensor nodes act as routers, forwarding
messages from one of their neighbors to another. The nodes are
congured to turn their communication hardware on and off
to minimize energy consumption. Therefore, in order for two
neighboring sensors to communicate, both must be in active
mode.
In the sensor network model considered in this paper, the
nodes are placed randomly over the area of interest and their
rst step is to detect their immediate neighbors the nodes
with which they have a direct wireless communication and to
establish routes to the gateway. In networks with continuously
heavy trafc, the sensors need not invoke any special neighbor
discovery protocol during normal operation. This is because
any new node, or a node that has lost connectivity to its
neighbors, can hear its neighbors simply by listening to the
channel for a short time. However, for sensor networks with
low and irregular trafc, a special neighbor discovery scheme
should be used. This paper presents and analyzes such a
scheme.
RELATED WORK
In a WiFi network operating in centralized mode, a special
node, called an access point, coordinates access to the shared
medium. Messages are transmitted only to or from the access
point. Therefore, neighbor discovery is the process of having
a new node detected by the base station. Since energy consumption
is not a concern for the base station, discovering new
nodes is rather easy. The base station periodically broadcasts a
special HELLO message1. A regular node that hears this message
can initiate a registration process. The regular node can
switch frequencies/channels in order to nd the best HELLO
message for its needs. Which message is the best might depend
on the identity of the broadcasting base station, on security
considerations, or on PHY layer quality (signal-to-noise ratio).
Problems related to possible collisions of registration messages
in such a network are addressed in [4]. Other works try to
minimize neighbor discovery time by optimizing the broadcast
rate of the HELLO messages [1], [5], [6], [7], [8]. The main
differences between neighbor discovery in WiFi and in mesh
sensor networks are that neighbor discovery in the former
is performed only by the central node, for which energy
consumption is not a concern. In addition, the hidden nodes
are assumed to be able to hear the HELLO messages broadcast
by the central node. In contrast, neighbor discovery in sensor
networks is performed by every node, and hidden nodes cannot
hear the HELLO messages when they sleep.
A BASIC SCHEME AND PROBLEM DEFINITION
In the following discussion, two nodes are said to be
neighboring nodes if they have direct wireless connectivity.
We assume that all nodes have the same transmission range,
which means that connectivity is always bidirectional. During
some parts of our analysis, we also assume that the network
is a unit disk graph; namely, any pair of nodes that are within
transmission range are neighboring nodes. Two nodes are said
to be directly connected if they have discovered each other
and are aware of each other's wake-up times. Two nodes are
said to be connected if there is a path of directly connected
nodes between them. A set of connected nodes is referred
to as a segment. Consider a pair of neighboring nodes that
belong to the same segment but are not aware that they have
direct wireless connectivity. See, for example, nodes a and c
in Figure 4(a). These two nodes can learn about their hidden
wireless link using the following simple scheme, which uses
two message types: (a) SYNC messages for synchronization
between all segment nodes, transmitted over known wireless
links; (b) HELLO messages for detecting new neighbors.
Scheme 1 (detecting all hidden links inside a segment):
This scheme is invoked when a new node is discovered by
one of the segment nodes. The discovering node issues a
special SYNC message to all segment members, asking them
to wake up and periodically broadcast a bunch of HELLO
messages. This SYNC message is distributed over the already
known wireless links of the segment. Thus, it is guaranteed
to be received by every segment node. By having all the
nodes wake up almost at the same time for a short period,
we can ensure that every wireless link between the segment's
members will be detected.
SIMULATION STUDY
In this section we present a simulation study for the schemes
presented in the paper. We simulate a large sensor network,
with nodes distributed randomly and uniformly over the area of
interest. We assume that the nodes have an equal and constant
transmission range. Communication is always bi-directional.
We also assume that most of the nodes discover each other
and enter the continuous neighbor discovery state before the
simulation begins.
Our simulation model consists of 2,000 sensor nodes, randomly
placed over a 10,000 x 10,000 grid. The transmission
range is set to r units. Any two nodes whose Euclidean
distance is not greater than r are considered to have wireless
connectivity. A portion of the nodes are randomly selected
to be hidden. These nodes are uniformly distributed in the
considered area. We set the algorithm parameters such that
every hidden node will be detected with probability P within
a predetermined period of time T. For the study reported in
this section, r is chosen to be 300 (0.03 of the graph), the
detection probability ranges between 0.3 and 0.7, and the target
detection time is 100 time units.
CONCLUSIONS
We exposed a new problem in wireless sensor networks,
referred to as ongoing continuous neighbor discovery. We
argue that continuous neighbor discovery is crucial even if the
sensor nodes are static. If the nodes in a connected segment
work together on this task, hidden nodes are guaranteed to
be detected within a certain probability P and a certain time
period T, with reduced expended on the detection.
We showed that our scheme works well if every node
connected to a segment estimates the in-segment degree of
its possible hidden neighbors. To this end, we proposed three
estimation algorithms and analyzed their mean square errors.
We then presented a continuous neighbor discovery algorithm
that determines the frequency with which every node enters
the HELLO period. We simulated a sensor network to analyze
our algorithms and showed that when the hidden nodes are
uniformly distributed in the area, the simplest estimation algorithm
is good enough. When the hidden nodes are concentrated
around some dead areas, the third algorithm, which requires
every node to take into account not only its own degree, but
also the average degree of all the nodes in the segment, was
shown to be the best.