27-07-2012, 11:53 AM
Maximizing the Lifetime of a Barrier of Wireless Sensors
[attachment=29197]
Abstract
To make a network last beyond the lifetime of an individual sensor node, redundant nodes must be deployed. What sleepwake-
up schedule can then be used for individual nodes so that the redundancy is appropriately exploited to maximize the network
lifetime? We develop optimal solutions to both problems for the case when wireless sensor nodes are deployed to form an
impenetrable barrier for detecting movements. In addition to being provably optimal, our algorithms work for nondisk sensing regions
and heterogeneous sensing regions. Further, we provide an optimal solution for the more difficult case when the lifetimes of individual
nodes are not equal. Developing optimal algorithms for both homogeneous and heterogeneous lifetimes allows us to obtain, by
simulation, several interesting results. We show that even when an optimal number of sensor nodes has been deployed randomly,
statistical redundancy can be exploited to extend the network lifetime by up to seven times.
INTRODUCTION
WIRELESS sensors are meant for outdoor deployments
where they may remain unattended for long periods
of time. Security applications such as intrusion detection,
fire detection, and chemical leak detection require sufficient
number of sensor nodes to be active at any time instant.
Given that the sensor nodes operate with small batteries,
individual nodes may not last a long time if continuously
active. To make a network last beyond the lifetime of an
individual node, redundant nodes must be deployed. What
sleep-wake-up schedule can then be used for individual
nodes so that redundancy is appropriately exploited to
maximize the network lifetime?1.
HOMOGENEOUS LIFETIME
In this section, we begin by deriving an upper bound on the
network lifetime when the sensor lifetimes are homogeneous.
Then, we present algorithm Stint that determines an
optimal sleep-wake-up schedule for individual sensors.
Finally, we prove that Stint minimizes the number of path
switches in addition to maximizing the network lifetime.
Upper Bound on the Network Lifetime
Consider the sensor network shown in Fig. 1. If the
maximum number of node-disjoint paths between s and t,
m, is less than k, then the sensor network cannot provide
k-barrier coverage even if all sensors are turned on.
Therefore, the maximum lifetime of the network is 0. In
the following, we only consider the case when m k.
Achieving the Upper Bound
In Section 3.1, an upper bound on network lifetime for
k-barrier coverage in the homogeneous lifetime case is
derived. The Stint algorithm achieves this upper bound.
While we now provide an informal description of this
algorithm, the details appear in Fig. 4.
The Stint algorithm first computes m, the maximum
number of node-disjoint paths between s and t. The
maximum number of node-disjoint paths can be found
using a max-flow algorithm as discussed in [1]. The Stint
algorithm then determines whether m is divisible by k. If it
is, then m disjoint paths are partitioned into ‘ ¼ m=k groups
of k paths each. Then, ‘ groups of k disjoint paths are
activated in sequence. The first group provides k-barrier
coverage until it runs out of energy. Then, the second group
is activated. The process continues for ‘ iterations.
Minimizing Path Switches
In this section, we consider a lexicographic two objective
optimization problem where the first objective is to
maximize the network lifetime, and the second objective
is to minimize the number of path switches. We first
illustrate why minimizing the number of path switches is
nontrivial. We then derive a lower bound on the total
number of path switches that are required if network lifetime
is to be maximized for k-barrier coverage. Finally, we prove
that the Stint algorithm achieves this lower bound.
SIMULATIONS
In this section, we use our optimal algorithms to study three
interesting issues that may have implication in real-life
deployments highlighted in Section 1: 1) On average, how
much statistical redundancy exists in optimal random
deployments? 2) On average, how much loss in potential
network lifetime is incurred if homogeneous sensor lifetime
is assumed when they are not? 3) What is the impact of
imbalance in the lifetimes of individual sensors?
We use the following parameters in the simulations.
Sensors are deployed in a rectangular region of dimension
1 km 200 m, and each sensor has a sensing range of 50 m.
These parameters are in same ratio, as shown in [7, Fig. 9].
As a result, the density needed in a random deployment can
be readily determined from this figure.
Statistical Redundancy in Random
Deployments
Random deployment is often used in simulations. In reallife
deployments also, random deployment can provide a
reliable estimate of the density of sensors needed to achieve
a desired quality of monitoring. This is true even if sensors
are deployed deterministically, because randomness is
introduced due to unanticipated failures after deployment
and due to errors in placement [25]. To compensate for
these sources of randomness, several additional sensors
need to be deployed as compared to an optimal deterministic
deployment. The sensor density in such deterministic
deployments is close to that needed in a pure random
deployment model (see [25] for details).
CONCLUSIONS
In this paper, we propose optimal solutions to the sleepwake-
up problems for the model of barrier coverage for both
the homogeneous and heterogeneous lifetime cases.Weshow
that these algorithms generate solutions where the network
lasts up to seven times longer even if a minimal number of
sensors have been deployed in a random deployment. We
also show that the loss in potential network lifetime is severe
(reduced by two-thirds) if sensor lifetimes are assumed to
be homogeneous when they are not. Finally, we show that
imbalance in load in a network does not cause loss in network
lifetime, as previously assumed, provided that the imbalance
is sufficiently random.
[attachment=29197]
Abstract
To make a network last beyond the lifetime of an individual sensor node, redundant nodes must be deployed. What sleepwake-
up schedule can then be used for individual nodes so that the redundancy is appropriately exploited to maximize the network
lifetime? We develop optimal solutions to both problems for the case when wireless sensor nodes are deployed to form an
impenetrable barrier for detecting movements. In addition to being provably optimal, our algorithms work for nondisk sensing regions
and heterogeneous sensing regions. Further, we provide an optimal solution for the more difficult case when the lifetimes of individual
nodes are not equal. Developing optimal algorithms for both homogeneous and heterogeneous lifetimes allows us to obtain, by
simulation, several interesting results. We show that even when an optimal number of sensor nodes has been deployed randomly,
statistical redundancy can be exploited to extend the network lifetime by up to seven times.
INTRODUCTION
WIRELESS sensors are meant for outdoor deployments
where they may remain unattended for long periods
of time. Security applications such as intrusion detection,
fire detection, and chemical leak detection require sufficient
number of sensor nodes to be active at any time instant.
Given that the sensor nodes operate with small batteries,
individual nodes may not last a long time if continuously
active. To make a network last beyond the lifetime of an
individual node, redundant nodes must be deployed. What
sleep-wake-up schedule can then be used for individual
nodes so that redundancy is appropriately exploited to
maximize the network lifetime?1.
HOMOGENEOUS LIFETIME
In this section, we begin by deriving an upper bound on the
network lifetime when the sensor lifetimes are homogeneous.
Then, we present algorithm Stint that determines an
optimal sleep-wake-up schedule for individual sensors.
Finally, we prove that Stint minimizes the number of path
switches in addition to maximizing the network lifetime.
Upper Bound on the Network Lifetime
Consider the sensor network shown in Fig. 1. If the
maximum number of node-disjoint paths between s and t,
m, is less than k, then the sensor network cannot provide
k-barrier coverage even if all sensors are turned on.
Therefore, the maximum lifetime of the network is 0. In
the following, we only consider the case when m k.
Achieving the Upper Bound
In Section 3.1, an upper bound on network lifetime for
k-barrier coverage in the homogeneous lifetime case is
derived. The Stint algorithm achieves this upper bound.
While we now provide an informal description of this
algorithm, the details appear in Fig. 4.
The Stint algorithm first computes m, the maximum
number of node-disjoint paths between s and t. The
maximum number of node-disjoint paths can be found
using a max-flow algorithm as discussed in [1]. The Stint
algorithm then determines whether m is divisible by k. If it
is, then m disjoint paths are partitioned into ‘ ¼ m=k groups
of k paths each. Then, ‘ groups of k disjoint paths are
activated in sequence. The first group provides k-barrier
coverage until it runs out of energy. Then, the second group
is activated. The process continues for ‘ iterations.
Minimizing Path Switches
In this section, we consider a lexicographic two objective
optimization problem where the first objective is to
maximize the network lifetime, and the second objective
is to minimize the number of path switches. We first
illustrate why minimizing the number of path switches is
nontrivial. We then derive a lower bound on the total
number of path switches that are required if network lifetime
is to be maximized for k-barrier coverage. Finally, we prove
that the Stint algorithm achieves this lower bound.
SIMULATIONS
In this section, we use our optimal algorithms to study three
interesting issues that may have implication in real-life
deployments highlighted in Section 1: 1) On average, how
much statistical redundancy exists in optimal random
deployments? 2) On average, how much loss in potential
network lifetime is incurred if homogeneous sensor lifetime
is assumed when they are not? 3) What is the impact of
imbalance in the lifetimes of individual sensors?
We use the following parameters in the simulations.
Sensors are deployed in a rectangular region of dimension
1 km 200 m, and each sensor has a sensing range of 50 m.
These parameters are in same ratio, as shown in [7, Fig. 9].
As a result, the density needed in a random deployment can
be readily determined from this figure.
Statistical Redundancy in Random
Deployments
Random deployment is often used in simulations. In reallife
deployments also, random deployment can provide a
reliable estimate of the density of sensors needed to achieve
a desired quality of monitoring. This is true even if sensors
are deployed deterministically, because randomness is
introduced due to unanticipated failures after deployment
and due to errors in placement [25]. To compensate for
these sources of randomness, several additional sensors
need to be deployed as compared to an optimal deterministic
deployment. The sensor density in such deterministic
deployments is close to that needed in a pure random
deployment model (see [25] for details).
CONCLUSIONS
In this paper, we propose optimal solutions to the sleepwake-
up problems for the model of barrier coverage for both
the homogeneous and heterogeneous lifetime cases.Weshow
that these algorithms generate solutions where the network
lasts up to seven times longer even if a minimal number of
sensors have been deployed in a random deployment. We
also show that the loss in potential network lifetime is severe
(reduced by two-thirds) if sensor lifetimes are assumed to
be homogeneous when they are not. Finally, we show that
imbalance in load in a network does not cause loss in network
lifetime, as previously assumed, provided that the imbalance
is sufficiently random.