18-04-2012, 03:26 PM
Algorithms For Wireless Sensor Networks
wirelesssensor.pdf (Size: 220.06 KB / Downloads: 72)
Introduction
A wireless sensor network may comprise thousands of sensor nodes. Each sensor node has a sensing
capability as well as limited energy supply, compute power, memory and communication ability. Besides
military applications, wireless sensor networks may be used to monitor microclimates and wildlife habitats
[56], the structural integrity of bridges and buildings, building security, location of valuable assets (via
sensors placed on these valuable assets), traffic, and so on. However, realizing the full potential of wireless
sensor networks poses myriad research challenges ranging from hardware and architectural issues, to
programming languages and operating systems for sensor networks, to security concerns, to algorithms
for sensor network deployment, operation and management. Iyengar and Brooks [26, 27] and Culler
and Hong [12] provide good overviews of the breadth of sensor network research topics as well as of
applications for sensor networks.
Sensor Deployment and Coverage
In a typical sensor network application, sensors are to be placed (or deployed) so as to monitor a region or
a set of points. In some applications we may be able to select the sites where sensors are placed while in
others (e.g., in hostile environments) we may simply scatter (e.g., air drop) a sufficiently large number of
sensors over the monitoring region with the expectation that the sensors that survive the air drop will be
able to adequately monitor the target region. When site selection is possible, we use deterministic sensor
deployment and when site selection isn’t possible, the deployment is nondeterministic. In both cases, it
often is desirable that the deployed collection of sensors be able to communicate with one another, either
directly or indirectly via multihop communication.
Point Coverage
Figure 2 gives the greedy algorithm of Kar and Banerjee [32] to deploy a connected sensor network so
as to cover a set of points in Euclidean space. This algorithm, which assumes that r = c, uses at most
7.256 times the minimum number of sensors needed to cover the given point set [32]. It is easy to see
that the constructed deployment covers all of the given points and is a connected network.
Maximizing Coverage Lifetime
When sensors are deployed in difficult-to-access environments, as is the case in many military applications,
a large number of sensors may be air-dropped into the region that is to be sensed. Assume that the sensors
that survive the air drop cover all targets that are to be sensed. Since the power supply of a sensor cannot
be replenished, a sensor becomes inoperable once it runs out of energy. Define the life of a sensor network
to be the earliest time at which the network ceases to cover all targets. The life of a network can be
increased if it is possible to put redundant sensors (i.e., sensors not needed to provide coverage of all
targets) to sleep and awaken these sleeping sensors when they are needed to restore target coverage.
Sleeping sensors are inactive while sensors that are awake are active. Inactive sensors consume far less
energy than active ones.