25-05-2012, 03:11 PM
Continuous Neighbor Discovery in Asynchronous Sensor Networks
[attachment=23022]
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.
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.
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.
ESTIMATING THE IN-SEGMENT DEGREE OF A HIDDEN NEIGHBOR
As already explained, we consider the discovery of hidden
neighbors as a joint task to be performed by all segment
nodes. To determine the discovery load to be imposed on every
segment node, namely, how often such a node should become
active and send HELLO messages, we need to estimate the
number of in-segment neighbors of every hidden node u,
denoted by degS(u). In this section we present methods that
can be used by node v in the Normal (continuous neighbor
discovery) state to estimate this value.
THE UNIFORM DISTRIBUTION SPECIAL CASE
We now examine a special case where the network nodes are
uniformly distributed. The node degree has a binomial distribution,
where the probability of success p is the probability
that a node v is in the transmission range of another node u.
This probability is equal to the ratio between the area covered
by v and the area covered by the whole network. For this kind
of distribution, the variance is known to be np(1
[attachment=23022]
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.
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.
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.
ESTIMATING THE IN-SEGMENT DEGREE OF A HIDDEN NEIGHBOR
As already explained, we consider the discovery of hidden
neighbors as a joint task to be performed by all segment
nodes. To determine the discovery load to be imposed on every
segment node, namely, how often such a node should become
active and send HELLO messages, we need to estimate the
number of in-segment neighbors of every hidden node u,
denoted by degS(u). In this section we present methods that
can be used by node v in the Normal (continuous neighbor
discovery) state to estimate this value.
THE UNIFORM DISTRIBUTION SPECIAL CASE
We now examine a special case where the network nodes are
uniformly distributed. The node degree has a binomial distribution,
where the probability of success p is the probability
that a node v is in the transmission range of another node u.
This probability is equal to the ratio between the area covered
by v and the area covered by the whole network. For this kind
of distribution, the variance is known to be np(1