Maximum Data Gathering in Networked Sensor Systems
ems where data are locally stored at the sensors before the data gathering starts, and
continuous sensing and gathering problems that model time critical applications. We show that these
problems reduce to maximization of network ow under vertex capacity constraint. This ow problem
in turn reduces to a standard network ow problem. We develop a distributed and adaptive algorithm to
optimize data gathering. This algorithm leads to a simple protocol that coordinates the sensor nodes in
the system. Our approach provides a unied framework to study a variety of data gathering problems in
networked sensor systems. The performance of the proposed method is illustrated through simulations.
Supported by the National Science Foundation under award No. IIS-0330445 and in part by DARPA under contract
F33615-02-2-4005.
1
1
Introduction
State-of-the-art sensors (e.g. Smart Dust [20]) are powered by batteries. Replenishing energy by
replacing the batteries is infeasible since the sensors are typically deployed in harsh terrains. Also, the
cost of replacing batteries can be prohibitively high. These sensors, which are usually unattended, need
to operate over a long period of time after deployment. Energy efciency is thus critical. Techniques
ranging from low power hardware design [2, 15] and energy aware routing [8, 19] to application level
optimizations [18, 21] have been proposed to improve energy efciency of networked sensor systems.
An important application of networked sensor systems is to monitor the environment. Examples of
such applications include vehicle tracking and classication in the battle eld, patient health monitoring,
pollution detection, etc. In these applications, a fundamental operation is to sense the environment and
transmit the sensed data to the base station for further processing. In this paper, we study energy efcient
data gathering in networked sensor systems from an algorithmic perspective.
Compared with sensing and computation, communication is the most expensive operation (in terms
of energy consumption) in the context of data gathering [1]. Generally, data transfers are performed
via multi-hop communications where each hop is a short-range communication. This is due to the well
known fact that long-distance wireless communication is expensive in terms of both implementation
complexity and energy dissipation, especially when using the low-lying antennae and near-ground chan-
nels typically found in networked sensor systems. Short-range communication also enables efcient
spatial frequency re-use. A challenging problem with multi-hop communications is the efcient transfer
of data through the system when the sensors have energy constraints.
Some variations of the problem have been studied recently. In [11], data gathering is assumed to be
performed in rounds and each sensor can communicate (in a single hop) with the base station and all
2
other sensors. The total number of rounds is then maximized under a given energy constraint on the sen-
sors. In [14], a non-linear programing formulation is proposed to explore the trade-offs between energy
consumed and the transmission rate. It models the radio transmission energy according to Shannons
theorem. In [16], the data gathering problem is formulated as a linear programing problem and a
牏·
approximation algorithm is proposed. This algorithm further leads to a distributed heuristic.
Our study departs from the above with respect to the problem denition as well as the solution tech-
nique. For short-range communications, the difference in the energy consumption between sending and
receiving a data packet is almost negligible. We adopt the reasonable approximation that sending a data
packet consumes the same amount of energy as receiving a data packet [1]. The study in [14] and [16]
differentiate the energy dissipated for sending and receiving data. Although the resulting problem for-
mulations are indeed more accurate than ours, the improvement in accuracy is marginal for short-range
communications.
In [11], each sensor generates exactly one data packet per round (a round corresponds to the occur-
rence of an event in the environment) to be transmitted to the base station. The system is assumed to
be fully connected. The study in [11] also considers a very simple model of data aggregation where
any sensor can aggregate all the received data packets into a single output data packet. In our system
model, each sensor communicates with a limited number of neighbors due to the short range of the com-
munications, resulting in a general graph topology for the system. We study store-and-gather problems
where data are locally stored on the sensors before the data gathering starts, and continuous sensing and
gathering problems that models time critical applications. A unied ow optimization formulation is
developed for the two classes of problems.
Our focus in this paper is to maximize the throughput or volume of data received by the base station.
3
Such an optimization objective is abstracted from a wide range of applications in which the base station
needs to gather as much information as possible. Some applications proposed for the networked sensor
systems may have different optimization objectives. For example, the balanced data transfer problem [6]
is formulated as a linear programming problem where a minimum achieved sense rate is set for every
individual node. In [5], data gathering is considered in the context of energy balance. A distributed
protocol is designed to ensure that the average energy dissipation per node is the same throughout the
execution of the protocol. However, these issues are not the focus of this paper.
By modeling the energy consumption associated with each send and receive operation, we formulate
the data gathering problem as a constrained network ow optimization problem where each each node
is associated with a capacity constraint
。
, so that the total amount of ow going through
(incoming
plus outgoing ow) does not exceed
。
. We show that such a formulation models a variety of data
gathering problems (with energy constraint on the sensor nodes).
The constrained ow problem reduces to the standard network ow problem, which is a classical ow
optimization problem. Many efcient algorithms have been developed ([3]) for the standard network
ow problem. However, in terms of decentralization and adaptation, these well known algorithms are
not suitable for data gathering in networked sensor systems. In this paper, we develop a decentralized
and adaptive algorithm for the maximum network ow problem. This algorithm is a modied version
of the Push-Relabel algorithm [7]. In contrast to the Push-Relabel algorithm, it is adaptive to changes in
the system. It nds the maximum ow in
うエ
!
time, where
is the number of adaptation
operations,
"
is the number of nodes, and
"
is the number of links.
The above algorithm can be used to solve both store-and-gather problems and continuous sensing and
gathering problems. For the continuous sensing and gathering problems, we develop a simple distributed
4
protocol based on the algorithm. The performance of this protocol is studied through simulations. Be-
cause the store-and-gather problems are by nature off-line problems, we do not develop a distributed
protocol for this class of problems.
The rest of the paper is organized as follows. The data gathering problems are discussed in Section 2.
We show that these problems reduce to network ow problem with constraint on the vertices. In Sec-
tion 3, we develop a mathematical formulation of the constrained network ow problem and show that
it reduces to a standard network ow problem. In Section 4, we derive a relaxed form for the network
ow problem. A distributed and adaptive algorithm is then developed for this relaxed problem. A sim-
ple protocol based on this algorithm is presented in Section 4.3. Experimental results are presented in
Section 5. Section 6 concludes this paper.
2
Data Gathering with Energy Constraint
2.1
System Model
Suppose a network of sensors is deployed over a region. The location of the sensors are xed and
known a priori. The system is represented by a graph
ⅰ
!
, where
is the set of sensor nodes.
·
!
Ε
if
,
＇
and
is within the communication range of
. The set of successors
of
is denoted as
"
·
!
. Similarly, the set of predecessors of
is denoted as
!
!
"
. The event is sensed by a subset of sensors
$#&%
.
'
is the base station to
which the sensed data are transmitted. Sensors
)(
$#!(
0'
in the network does not sense the event but
can relay the data sensed by
1#
.
Among the three categories (sensing, communication, and data processing) of power consumption,
a sensor node typically spends most of its energy in data communication. This includes both data
5
transmission and reception. Our energy model for the sensors is based on the rst order radio model
described in [9]. The energy consumed by sensor
to transmit a
(
bit data packet to sensor
is
＂
イЕ┄
#
ぇ
＂
, where
!"#
#
is the energy required for transceiver circuitry to process
one bit of data,
!
is the energy required per bit of data for transmitter amplier, and
＂
is the distance
between
and
. Transmitter amplier is not needed by
to receive data and the energy consumed by
to receive a
(
bit data packet is
$
%ぇΙ
#
&
. Typically,
!"#
#
('0)
21430576"8
and
!9@
A)CB
D1E30576"8F3!G
.
This effectively translates to
!
＂IH
!"#
#
, especially when short transmission r