Abstract—
An important performance consideration for wireless
sensor networks is the amount of information collected by
all the nodes in the network over the course of network lifetime.
Since the objective of maximizing the sum of rates of all the
nodes in the network can lead to a severe bias in rate allocation
among the nodes, we advocate the use of lexicographical maxmin
(LMM) rate allocation. To calculate the LMM rate allocation
vector, we develop a polynomial-time algorithm by exploiting the
parametric analysis (PA) technique from linear program (LP),
which we call serial LP with Parametric Analysis (SLP-PA). We
show that the SLP-PA can be also employed to address the LMM
node lifetime problem much more efficiently than a state-of-theart
algorithm proposed in the literature. More important, we
show that there exists an elegant duality relationship between
the LMM rate allocation problem and the LMM node lifetime
problem. Therefore, it is sufficient to solve only one of the two
problems. Important insights can be obtained by inferring duality
results for the other problem.
Index Terms—Theory, sensor networks, energy constraint,
network capacity, rate allocation, lexicographic max-min, node
lifetime, linear programming, parametric analysis, flow routing.
I. INTRODUCTION
WIRELESS sensor networks consist of battery-powered
nodes that are endowed with a multitude of sensing
modalities including multi-media (e.g., video, audio) and
scalar data (e.g., temperature, pressure, light, magnetometer,
infrared). Although there have been significant improvements
in processor design and computing, advances in battery technology
still lag behind, making energy resource considerations
the fundamental challenge in wireless sensor networks. Consequently,
there have been active research efforts on performance
limits of wireless sensor networks. These performance limits
include, among others, network capacity (see e.g., [13]) and
network lifetime (see e.g., [7], [8]). Network capacity typically
refers to the maximum amount of bit volume that can be
successfully delivered to the base station (“sink node”) by all
the nodes in the network, while network lifetime refers to the
maximum time limit that nodes in the network remain alive
until one or more nodes drain up their energy.
In this paper, we consider an overarching problem that
encompasses both performance metrics. In particular, we study the network capacity problem under a given network lifetime
requirement. Specifically, for a wireless sensor network where
each node is provisioned with an initial energy, if all nodes
are required to live up to a certain lifetime criterion, what
is the maximum amount of bit volume that can be generated
by the entire network? At first glance, it appears desirable
to maximize the sum of rates from all the nodes in the
network, subject to the condition that each node can meet the
network lifetime requirement. Mathematically, this problem
can be formulated as a linear programming (LP) problem (see
Section II-B) within which the objective function is defined
as the sum of rates over all the nodes in the network and the
constraints are: (1) flow balance is preserved at each node,
and (2) the energy constraint at each node is met for the
given network lifetime requirement. However, the solution
to this problem shows (see Section VI) that although the
network capacity (i.e., the sum of bit rates over all nodes) is
maximized, there exists a severe bias in rate allocation among
the nodes. In particular, those nodes that consume the least
amount of power on their data path toward the base station
are allocated with much more bit rates than other nodes in
the network. Consequently, the data collection behavior for
the entire network only favors certain nodes that have this
property, while other nodes will be unfavorably penalized with
much smaller bit rates.
The fairness issue associated with the network capacity
maximization objective calls for a careful consideration in
rate allocation among the nodes. In this paper, we investigate
the rate allocation problem in an energy-constrained sensor
network for a given network lifetime requirement. Our objective
is to achieve a certain measure of optimality in the rate
allocation that takes into account both fairness and bit rate
maximization. We advocate to use the so-called Lexicographic
Max-Min (LMM) criterion [14], which maximizes the bit
rates for all the nodes for the given energy constraint and
network lifetime requirement. At first level, the smallest rate
among all the nodes is maximized. Then, we continue to
maximize the second level of smallest rate and so forth. The
LMM rate allocation criterion is appealing since it addresses
both fairness and efficiency (i.e., bit rate maximization) in an
energy-constrained network.
A naive approach to the LMM rate allocation problem
would be to apply a max-min-like iterative procedure. Under
this approach, successive LPs are employed to calculate the
maximum rate at each level based on the available energy for
the remaining nodes, until all nodes use up their energy. We
call this approach “serial LP with energy reservation” (SLPER).
We show that, although SLP appears intuitive, unfortunately
it usually gives an incorrect solution. To understand
how this could happen, we must understand a fundamental difference between the LMM rate allocation problem described
here and the classical max-min rate allocation in [3]. Under
the LMM rate allocation problem, the rate allocation problem
is implicitly coupled with a flow routing problem, while under
the classical max-min rate allocation, there is no routing
problem involved since the routes for all flows are given. As it
turns out, for the LMM rate allocation problem, any iterative
rate allocation approach that requires energy reservation at
each iteration is incorrect. This is because, unlike max-min,
which addresses only the rate allocation problem with fixed
routes and yields a unique solution at each iteration, for
the LMM rate allocation problem, there usually exist nonunique
flow routing solutions corresponding to the same rate
allocation at each level. Consequently, each of these flow
routing solutions will yield different available energy levels on
the remaining nodes for future iterations and so forth, leading
to a different rate allocation vector, which usually does not
coincide with the optimal LMM rate allocation vector.
In this paper, we develop an efficient polynomial-time
algorithm to solve the LMM rate allocation problem. We
exploit the so-called parametric analysis (PA) technique [2]
at each rate level to determine the minimum set of nodes that
must deplete their energy. We call this approach serial LP
with PA (SLP-PA). In most cases when the problem is nondegenerate,
the SLP-PA algorithm is extremely efficient and
only requires O(N) time complexity to determine whether or
not a node is in the minimum node set for each rate level.
Even for the rare case when the problem is degenerate, the
SLP-PA algorithm is still much more efficient than the stateof-
the-art slack variable (SV)-based approach proposed in [6],
due to fewer number of LPs involved at each rate level.
We also extend the PA technique for the LMM rate allocation
problem to address the so-called maximum node lifetime
curve problem in [6], which we call LMM node lifetime
problem. We show that the SLP-PA approach is much more
efficient than the slack variable (SV)-based approach (SLPSV)
described in [6]. More importantly, we show that there
exists a simple and elegant duality relationship between the
LMM rate allocation problem and the LMM node lifetime
problem. As a result, it is sufficient to solve only one of these
two problems. Important insights can be obtained by inferring
duality results for the other problem.
The remainder of this paper is organized as follows. In
Section II, we describe the network and energy model, and formulate
the LMM rate allocation problem. Section III presents
our SLP-PA algorithm to the LMM rate allocation problem.
In Section IV, we introduce the LMM node lifetime problem
and apply the SLP-PA algorithm to solve it. Section V shows
an interesting duality relationship between the LMM rate
allocation problem and the LMM node lifetime problem. In
Section VI, we present numerical results. Section VII reviews
related work and Section VIII concludes this paper.

Download full report
http://filebox.vt.edu/users/yshi/papers/TNet08.pdf