984 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 7, NO.

3, MARCH 2008

A Distributed Algorithm for Maximum Lifetime

Routing in Sensor Networks with Mobile Sink
Marios Gatzianas and Leonidas Georgiadis, Senior Member, IEEE

Abstract— We consider a noise-limited wireless sensor network Although the individual facets of the energy-efficient rout-
that consists of battery-operated nodes which can route infor- ing problem, i.e. optimal routing and resource allocation, have
mation to a mobile sink in a multi-hop fashion. The problem of been extensively studied in isolation (see [1], [2] and the
maximizing the network’s lifetime, defined as the period of time
during which the network can route a feasible flow to each sink references in [3]), recently the focus has shifted towards cross-
location subject to power/energy constraints, is cast into a linear layer optimization. Reference [3], with which this work shares
program, reduced into a simpler equivalent form and solved via many traits (though our model does not fit in its framework),
dual decomposition. The unknowns are the sink sojourn times provides a general methodology for optimizing various per-
and the routing flow vector for each sink location. The presence of formance metrics through the formulation of convex problems
a mobile sink presents new challenges but the problem structure
can still be exploited to find the optimal solution. A distributed with the flows and allocated resources as unknowns. Similarly,
algorithm based on the subgradient method and using the sink [4] derives a schedule and power allocation policy that, for
as leader is proposed and its performance is evaluated through given minimum rate requirements, minimizes the average total
simulation for random networks. The algorithm’s requirements power expended by the network. Finally, in the limiting case
in memory are also provided. where the number of nodes grows denumerably to infinity
Index Terms— Sensor networks, network lifetime, duality, (i.e. the nodes are so closely placed that macroscopic quan-
subgradient method, primal recovery. tities can be defined as aggregate averages) the problem of
minimizing the average total power can be cast into a partial
I. I NTRODUCTION differential equation (pde) similar to the ones encountered in
electrostatics [5], [6].
W IRELESS sensor networks (WSNs) typically consist of
a large number of nodes used for gathering information
from a geographical area and sending it in a multi-hop fashion
All of the aforementioned literature considers the total
expended power (usually in its long-term average form) as
to designated sink nodes for further processing. They are often the sole metric of power efficiency which, as observed in [7],
employed in environmental monitoring applications, which can be misleading in the case of sensor networks, since the
requires their topology to be either fixed or slowly varying network lifetime is not directly related to the total expended
in a controllable manner, and their operational lifetime is of power. Hence, a min-max formulation is more appropriate
the order of weeks or months. In addition to the usual ad-hoc than the standard min-sum previously used. This is performed
nature of their formation, they possess the unique characteris- in [8], where an interference-free sensor network in the low-
tics of even more stringent energy/power requirements, due to SNR regime with a single stationary sink is considered and
their long-term operation, as well as high correlation between the lifetime problem is solved through subgradient projection.
the data generated in proximal nodes. Hence, issues such as Reference [9] considers a general interference-limited network
source coding, resource allocation (power, bandwidth etc.) and and formulates the combined scheduling/routing/resource al-
routing policies become very important. This paper deals with location as a non-convex problem which is then approximated
the last two issues by jointly optimizing resource allocation by a convex one in the high-SNR regime. Again, a single
and routing in order to maximize a suitably defined notion of stationary sink is considered.
network lifetime for a sensor network where the sink is mobile. The case of a mobile sink has received less attention
Furthermore, due to the ad-hoc nature of these networks, we than the stationary sink, although it has been demonstrated
specifically direct our attention towards algorithms that are in [10]–[12] that a mobile sink can potentially increase the
amenable to a distributed implementation. network’s lifetime by causing lower saturation on the nodes
Manuscript received September 20, 2006; revised January 27, 2007 and close to the sink due to its changing positions. Such a sink
May 11, 2007; accepted June 24, 2007. The associate editor coordinating the may be a small vehicle, possibly unmanned, equipped with
review of this paper and approving it for publication was V. Leung. This wireless transceiver. The vehicle may stop at specified loca-
research was supported by the GSRT project #05NON-EU-160, “Resource
Allocation Techniques for Efficient Control and Management in Wireless tions (i.e. terminals), where it can dock and collect available
Networks.” Part of this work was presented at the 2006 European Wireless network data without obstructing other vehicles (e.g. consider
conference, April 2-5, Athens, Greece. a WSN employed over cultivated farmland for the purpose
M. Gatzianas is with the Department of Electrical and Computer Engineer-
ing, Division of Telecommunications, Aristotle University of Thessaloniki, of measuring air humidity. Since an arbitrary sink movement
Thessaloniki 54 124, Greece (e-mail: mgkatzia@[Link]). could damage the crops, it is more likely that the sink moves
L. Georgiadis is with the Department of Electrical and Computer Engineer- among predetermined locations). Recently, [13] examined
ing, Division of Telecommunications, Aristotle University of Thessaloniki,
and with CERTH-ITI (e-mail: leonid@[Link]). multiple mobile sinks on sensor networks and developed
Digital Object Identifier 10.1109/TWC.2008.060727. approximation algorithms for special cases of NP-complete
1536-1276/08$25.00 
c 2008 IEEE

Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
GATZIANAS and GEORGIADIS: A DISTRIBUTED ALGORITHM FOR MAXIMUM LIFETIME ROUTING IN SENSOR NETWORKS WITH MOBILE SINK 985

problems. However, the proposed algorithm is not easily nodes i ∈ N except for the sink are equipped with a non-
adapted to a distributed environment. The main contribution of renewable amount of energy Ei > 0, which is gradually
this paper is the development of an efficient distributed (and depleted as the nodes participate in routing, and operate under
parallel) algorithm for a single mobile sink sensor network, a peak transmission power constraint Pi > 0. Once a node’s
offering an alternative to the centralized solution of [12]. As energy is drained, the node can no longer transmit. The
such, considerable emphasis will be placed on issues related lifetime of the network has been traditionally defined as the
to distributed implementation. period of time until the first node runs out of energy. We
The rest of the paper is organized as follows. Section II start from a definition that captures the notion that a network
contains the model description and statement of the problem. is alive as long as it can transfer all generated traffic to the
The dual formulation, along with supporting analysis, is pre- sink while satisfying the energy/power and flow conservation
sented in Section III with Section IV describing in detail the constraints.
distributed version of the proposed method. Numerical results Specifically, we say that the network is survivable up to
and heuristics are presented in Section V while Section VI time T if for each sink location l ∈ L a) there exists a
concludes the paper and offers directions for future work. sequence of time intervals τkl , k = 1, . . . , Kl (representing
the time intervals  duringwhich the sink resides at location
Kl
l) such that T = l∈L k=1 τkl and b) there exist feasible
II. S YSTEM MODEL AND STATEMENT OF THE PROBLEM k,l k,l
flow/power allocations fij , pij for each time interval τkl .
Consider a set N of battery-operated wireless sensors, Here fij k,l
and pk,l
ij denote the traffic rate and transmission
which are randomly deployed over a given area and remain power, respectively, on link (i, j) during l
 the interval τk .
stationary once placed. In the following, we model the system Denoting with Si = n ∈ N : (i, n) ∈ E the set of outgoing
l l

at the network flow level, i.e. packet scheduling is not taken neighbors of node i for sink location l, the term feasible means
into account. Each sensor (a.k.a. node) i ∈ N produces that the following conditions are true2
information, at a fixed deterministic rate Qi ≥ 0, which
must eventually be routed in a multi-hop fashion (i.e. using 
Kl 
pk,l
ij τk ≤ Ei , ∀ i ∈ N ,
l
(1)
other stationary nodes), to a distinct sink node s, moving
l∈L k=1 j∈Sil
between different locations l ∈ L. Such routing is possible 
only if there exists a directed path from each node to at pk,l
ij ≤ Pi , ∀ i ∈ N , ∀ k ∈ {1, . . . , Kl }, ∀ l ∈ L, (2)
least one sink location l, which is hereafter taken for granted. j∈Sil
Node a communicates directly with node b, i.e. a directed 
k,l
fij ≤ h pk,l , ∀ k ∈ {1, . . . , Kl }, ∀ (i, j) ∈ E l , ∀ l ∈ L,
link (a, b) exists, if the received power at b due to a’s ij

transmission is above a certain threshold, when a transmits (3)

 k,l
 k,l
at maximum power. To make the distributed implementation fij = Qi + fji , ∀ i ∈ N ∪ {s}, ∀ l ∈ L,
(to be presented later) more tractable, all links are assumed to j∈Sil j:i∈Sjl ∀ k ∈ {1, . . . , Kl }.
be bi-directional, i.e. if a can communicate with b but not vice (4)
versa, none of the edges (a, b), (b, a) is considered to exist.
This restriction is imposed for convenience purposes and is Equation (1) ensures that the total expended energy by node
not required per se for the validity of the ensuing analysis. i during the network’s operation will not exceed the initial
The system is considered to operate in the low-SNR regime energy reserve Ei , while (2) places a peak transmission power
such that transmissions incur a power expenditure directly constraint Pi (say, due to FCC regulations) to node i for
proportional to the amount of transmitted information rate. all time intervals and sink locations.
 Equation
(3) provides
k,l
This assumption is justified in the context of, say, ultra-wide a capacity-related upper bound h pij , where h is a non-
band (UWB) networks (see [14] for a detailed description of k,l
decreasing concave function, on the achievable link rate fij
the underlying physical model) which have lately attracted sig- k,l
on link (i, j) using power pij . Finally, (4) ensures long-
nificant attention for sensing applications. We further assume, term network stability under a fluid model, which is most
following a convention established in previous works, that suitable for the macroscopic (flow) level at which we examine
receptions incur no cost (a similar model has been proposed
 For consistency reasons, we also define Qs 
l
the problem.
in [8] for a stationary sink). Adding a reception cost to the Qs = − i∈N Qi , ∀ l ∈ L. Notice that flow conservation is
destination node of each transmission does not change the imposed for each individual sink location.
main principles of our analysis or the structure of the algorithm
In this paper we are interested in maximizing the surviv-
to be presented1 and is neglected in order to simplify the
ability time of the network, i.e. the problem
discussion.
The sink’s movement over different  locations effectively 
Kl

creates a new digraph G l N ∪ {s}, E l for each sink location maximize T = τkl ,
l∈L k=1
(5)
l (where the sink is allowed to stay for an arbitrary amount
of time) and, hopefully, distributes the routing and associated s.t. constraints of (1)–(4).
power costs more evenly compared to a stationary sink. All
k,l k,l

2 the specification of the vector τkl , fij , pij for all i, j, k, l can be
1 as a foresight, only the edge costs dl of the minimum cost flow problem regarded as a policy specification. Hence, a policy achieves survivability up
ij  Kl l k,l k,l
developed in (17) of Section III-B are modified. to time T if T = l∈L k=1 τk and fij , pij is a feasible allocation.

Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
986 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 7, NO. 3, MARCH 2008

TABLE I
L IST OF NOTATIONS

Notation Definition
N set of static sensor nodes
L set of locations where sink may stay
El set of edges (i.e. links) between the static nodes and the sink when the latter is at location l ∈ L
tl sink sojourn time at location l ∈ L, also an unknown in the formulated linear program
T̂ l upper bound on sink sojourn time for location l ∈ L.
Qi exogenous traffic rate for static node i ∈ N
Sil set of outgoing neighbors of node i when the sink is at location l ∈ L
elij amount of power needed to transmit 1 bps from node i to node j when the sink is at location l ∈ L
l
fij time-invariant rate of flow (in bps) from node i to node j when the sink is at location l ∈ L
l
pij amount of power needed to transmit with rate fij l from node i to node j when sink is at location l ∈ L

blij l tl : an unknown in the formulated linear program

fij

The maximum value of T in (5) is defined as the network (8), (9) by tl converts the above problem into a linear program
“lifetime” (equivalently, the network “dies” at time T ). This with respect to tl , blij . Since the original problem has been
definition justifies the imposition of (4) as a problem constraint reduced to a simpler form, we summarize the simplified
since, under the optimal solution, the network lifetime will notation in Table I for the reader’s convenience. Although in
usually be sufficiently large for buffer overflow to occur in any principle any LP solution technique can be applied (as was the
location of non-zero sojourn time (even though the latter may case in [12] where a centralized simplex algorithm was used),
be a small portion of the total lifetime) where (4) is violated. we will focus instead on a distributed algorithm derived via
This is especially true considering the hardware capabilities duality.
of typical sensors. The power constraint of (2), (8) models a broadcast trans-
Using a standard convex combination argument (see Ap- mission, where each node operates in a frame fashion and
pendix I), it is easy to show that we can restrict our attention allocates individual slots in its frame to each of its neighbors.
to time-invariant flows for each sink location (i.e. a single In that sense, Pi is understood as the maximum power
flow allocation for each location suffices), thereby removing expenditure per frame. Another meaningful constraint could be
the k summation from all previous relations. The following applied on a slot basis and it would be expressed by dropping
observations are also useful. First, it is clear that (3) holds with the j summation from (2), (8), so that an additional constraint
strict equality at optimality,
 since if there was an allocation of the form fij eij ≤ P̃ij would appear for each edge and
l l

such that fij < h pk,l

k,l
ij for a specific interval τkl and link sink location. As will be seen in Section III, this additional
constraint is trivial to incorporate in our model, since the
(i, j) we could reduce pk,l ij until equality is achieved with
problem remains convex and only the upper bounds of the flow
no reduction in network lifetime. For an interference-free
in (13) (to appear soon) are affected, while the dual minimum
environment, the low-SNR regime assumption allows us to
cost flow problem remains unaffected.
use the following
  approximation
 to the Shannon
 rate formula
l
fij = h plij = r ln 1 + alij plij /N0 ≈ ralij plij /N0 = Finally, it is interesting to consider the relationship between
the network’s lifetime and the first time at least one node
plij /elij , where r, alij are link specific quantities that depend
dies under the optimal policy of time-invariant flows for each
on path quality, employed transmission scheme etc. Hence, elij
sink location. For an immobile sink, the previous definition of
represents the power required to sustain a rate of 1 bps from
lifetime implies that, when the problem has a feasible solution,
node i to node j when the sink is at location l. Clearly, if both
the death of the first node occurs at the time the network dies
i, j are static nodes, the l superscript is redundant since the
under the optimal time-invariant policy3 . However, this is not
same channel exists for all sink locations (i.e. elij = eij ∀ l).
the case for a mobile sink, as the trivial counterexample of
It is only when j becomes equal to the sink index s that
Fig. 1 demonstrates. In Fig. 1, the sink is allowed to move
the l superscript becomes meaningful and in fact necessary
between two locations (marked as squares) while information
to avoid ambiguity. The above results in the original problem
is injected into the black node with rate Q = 1 (the white
being reduced to the equivalent form
 nodes act as relays only). All nodes have a power constraint
maximize tl , (6) of P = 1 and energy constraint of E = 1 for the white nodes
l∈L and E = 2 for the black node. The link labels represent the
 edge costs elij of (7)–(8). Clearly, an optimal policy consists of
s.t fij eij t ≤ Ei ,
l l l
∀i ∈ N, (7)
the source always transmitting with rate 1 to each relay node,
l∈L j∈Sil
 which then forwards this rate to the sink. Regardless of the
l l
fij eij ≤ Pi , ∀ i ∈ N , ∀ l ∈ L, (8) order in which the locations are visited, each relay can transmit
j∈Sil for at most one unit of time, leading to a network lifetime of
 
l
fij = Qi + l
fji , ∀ i ∈ N ∪ {s}, ∀ l ∈ L. (9) 3 this does not exclude the existence of optimal time-varying policies where
j∈Sil j:i∈Sjl the network survives the first node’s death. However, Appendix I guarantees
that these policies can be replaced by time-invariant policies, of optimal
Introducing the auxiliary variable blij = fij
l l
t and multiplying lifetime, where the network dies exactly when the first node dies.

Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
GATZIANAS and GEORGIADIS: A DISTRIBUTED ALGORITHM FOR MAXIMUM LIFETIME ROUTING IN SENSOR NETWORKS WITH MOBILE SINK 987

source
Since the last bound applies to all nodes, we extract the
1 1 following global upper bound for each sink location


Ei
t ≤ min
l
 T̂ l , ∀ l ∈ L, (12)
i∈N Qi minj∈Sil elij
1 1
  
T̂il

the important property being that these bounds are independent

sink location 1 sink location 2
of the flow. Their utility will become apparent later.
Fig. 1. Trivial network demonstrating the relationship between network The constraint set, when non-empty, is compact so that
lifetime and time of first node’s death. a solution always exists, although it may not be unique (a
common nuisance in linear programming). When only energy
constraints are present (i.e. (8) is removed) the set is always
2. Furthermore, there exists no time-invariant policy which
non-empty and the problem is feasible. This is justified as fol-
can force both relay nodes to die at time 2. It is clear though
lows. If there exists one sink location for which a directed path
(applying the argument of Appendix I verbatim) that if, for a
exists from each node to the sink, then Theorem 6.12 of [15]
mobile sink, the problem has a feasible solution, then there
asserts that a valid flow can be constructed for this location.
exists an optimal policy such that for each location of non-
Accordingly, selecting a sufficient small sojourn time allows
zero sojourn, a node dies exactly at the end of the respective
us to satisfy (7) for all nodes, leading to a feasible solution. On
sojourn. At that point, the sink must move to the next location.
the other hand, it is easy to construct trivial networks where
the addition of (8) results in infeasible problems. Since there
III. D UAL FORMULATION is no way of a priori knowing whether the problem is feasible,
In [8] a distributed algorithm was presented for the solution the proposed algorithm must systematically detect (preferably
of the sensor lifetime problem when the sink location is fixed. as soon as possible) infeasible problems and halt properly.
As explained next, this algorithm cannot be applied to the This will be addressed in a later section.
problem at hand. Since [8] considers a stationary sink, we
must temporarily remove the l summation to be on common B. Minimum cost flow via duality
ground. The LP in [8] is derived from (6)–(9) (without the Contrary to previous work that treats (7)–(9) as constraints
l summation) by performing the substitution q = 1/t, thus for the dual formulation and introduces Lagrange multipliers
converting “maximize t” into “minimize q” and (7) into for each of them, we only regard (7), (8) as constraints. We
 therefore define for each sink location l the set
fij eij ≤ qEi ∀ i ∈ N . (10)   
j∈Si Xl = f l , tl : l
fji + Qi = l
fij ,
j:i∈Sjl j∈Sil (13)
Equations (8), (9) don’t contain t and are therefore unaffected. 
The problem is now reduced into LP form with respect to 0≤ l
fij ≤ ulij , 0 ≤ t ≤ T̂
l l
,
q, fij . In order for the same artifice tobe applicable to our
mobile sink case, we should set q = 1/ l∈L tl and transform which is essentially the set of all flow conserving vectors when
(7) into a form containing q only. However, the latter is the sink is at location l. The primal problem then becomes

impossible since the l summation now includes a product of minimize tl ,
∩l X l
three terms, which cannot be expressed as a function of q. l∈L (14)
Hence, a different approach is required. We present a method s.t. constraints of (7)–(8).
in the following after discussing some preliminary results.
Removing the flow conservation from the constraint set im-
poses additional structure to the dual problem, which makes
A. Solution bounds and feasibility it more amenable to a distributed solution. Furthermore, it
To justify later analysis, we provide finite upper bounds on forces all intermediate numerical solutions obtained during the
both fijl
and tl , the lower bounds being obviously zero. Total subgradient projection iterations to be flow-conserving. Hence,
flow conservation requires fij l
≤ i∈N Qi , ∀ l ∈ L, (i, j) ∈ exploiting the fact that both sides of (8) can be multiplied by
E l . Additionally, if the alternative slot-based power constraint tl , the Lagrangian is written as
⎡ ⎤
is applied, it also holds fij l
≤ P̃ij /elij . In both cases, we   
can define an upper bound ulij such that fij l
≤ ulij ∀ l ∈ L(f , t, ν, μ) = − tl + νi ⎣ eij t − Ei ⎦
l l l
fij
L, (i, j) ∈ E . For the sojourn time, we have
l l∈L i∈N l∈L j∈Sil
    l ⎡ ⎤
Ei ≥ elij fij
l l
t ≥ tl min elij fij   
l∈L j∈Sil l∈L j∈Sil
j∈Sil + μli ⎣ fij eij t − Pi tl ⎦ = −
l l l
ν i Ei
l∈L i∈N j∈Sil i∈N
    l (9)  l   ⎧ ⎫
≥ tl min elij fij ≥ t min elij Qi (11)  ⎨    ⎬
j∈Sil j∈Sil + tl −1 − μli Pi + νi + μli fij
l l
eij ,
l∈L j∈Sil l∈L
  ⎩ l
⎭
l∈L i∈N i∈N j∈Si
≥ t min
l
elij Qi , ∀ i ∈ N , ∀ l ∈ L.
j∈Sil (15)
Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
988 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 7, NO. 3, MARCH 2008

which results in a dual function of i.e. an update procedure of the form

⎡ ⎛ ⎞⎤
 
  ν k+1 = PF ⎣ν k + sk ⎝ f˜ij t̃ eij − Ei ⎠⎦
l l l
q (ν, μ) = inf L(f , t, ν, μ) = − ν i Ei + inf tl
∩l X l Xl l∈L j∈Sil
⎡ ⎫
⎤l∈L
i∈N
⎡ ⎛ ⎞⎤+
   ⎬ 
⎣−1 − μli Pi + l l ⎦
νi + μli fij eij , = ⎣ν k + sk ⎝ f˜ij t̃ eij − Ei ⎠⎦ ,
l l l

l
⎭ l∈L j∈Sil
i∈N i∈N j∈Si
⎡ ⎛ ⎞ ⎤ (21)
(16) 
μ k+1
= PF ⎣μ + s ⎝k k
f˜ij
l l
eij − Pi ⎠ t̃ l⎦
=
where we exploited the separability of the Lagrangian with j∈Sil
⎡ ⎛ ⎞ ⎤+
respect to l to pass the min through the summation (in the

case where only slot-based power constraints are applied and = ⎣μk + sk ⎝ f˜ij
l l
eij − Pi ⎠ t̃l ⎦ ,
(8) is not imposed, it trivially follows that μli ≡ 0 ∀ i, l in j∈Sil
all subsequent expressions).
where the PF operator denotes a projection (in the metric
Since the two product terms inside the infimum are bounded
space context) of the enclosed argument onto space F, which
and independent of each other, the infimum can be further
is then reduced to the simple [ ]+ = max([ ], 0) operator, sk
decomposed as follows: for a given (ν, μ) pair, we compute
is a suitably chosen scalar step-size for subgradient iteration
  k and the quantities between parentheses in (21) represent the
f˜l = arg inf νi + μli elij fij
l
, (17) subgradients for the energy/power constraints, respectively.
Xl
i∈N j∈Si l
   On a more technical note, the subgradient method is condi-
dlij
tionally convergent upon a suitable choice for sk . According
to Proposition 8.2.6 of [17], choosing sk = 1/k ensures
which corresponds to a minimum cost flow problem [16], since convergence to the dual optimal (ν ∗ , μ∗ ) solution as k →
the set X l contains all flow-conserving vectors4 . Denoting as ∞. This choice for sk also facilitates the primal recovery
F̃ l the corresponding minimum cost, the minimizer of the scheme to be explained later. Additionally, since the problem
separable Lagrangian becomes is effectively an LP, through the substitution blij = fij
l l
t , the
Slater conditions hold [18] and there is no duality gap so that
  a primal solution can be obtained through the minimization of
0 if F̃ l ≥ 1 + μli Pi
t̃ =
l i∈N , (18) L (f , t, ν ∗ , μ∗ ).
T̂ l otherwise

C. Some fine points

so that the dual function can be written as
This section provides information on certain important
  details of the proposed method as well as additional issues
  
q (ν, μ) = − ν i Ei + T̂ l I F̃ l < 1 + μli Pi , alluded to in the previous analysis. It is clear that the heart of
i∈N l∈L i∈N
the problem is the efficient solution of a minimum (linear)
(19) cost flow problem for each Lagrange multiplier pair. This
where I[ ] denotes the indicator function of the enclosed logic problem has been extensively studied and various techniques
statement. Hence, minimization of the Lagrangian in (15) is have been proposed. We choose the synchronous scaled -
equivalent to the solution of |L| minimum cost flow problems, relaxation (SER) [16] algorithm due to its ease of distributed
which can be performed in a distributed manner [16]. implementation and use it exclusively in this paper.
The dual problem now becomes The SER algorithm, as most flow algorithms, implicitly
assumes integer edge costs, which translates in our case to
dlij being integer in (17). This cannot be satisfied a priori
max q(ν, μ), since dlij encapsulate the Lagrange multipliers νi , μli , which
(20)
s.t. ν, μ ∈ F, are most likely floating point numbers. Thankfully, this can
be circumvented by exploiting the scale invariance of a linear
where F = {(ν, μ) : ν, μ ≥ 0, q (ν, μ) > −∞} is the set problem with respect to its (linear) objective. Specifically, all
of Lagrange multipliers leading to a bounded (from below) edge costs dlij are up-scaled by an appropriate power of 10,
Lagrangian. It is clear from (19) that the last predicate in so that the minimum modified edge cost becomes of the order
F is redundant so that F = {(ν, μ) : ν, μ ≥ 0}. The dual of 1000, and all fractional parts are then truncated. Since all
problem is solved via standard subgradient projection [17], costs are larger than 1000, the truncation effect is expected
to be minimal. Notice that this does not affect the optimal
flow allocation since the constraint set remains unaffected (the
4 for the case where link (i, j) incurs a power reception cost on the receiver scaling is essentially performed on the νi +μli part of the cost).
 of the previous procedure results
j equal to aj fij , a straightforward repetition
  The SER algorithm is of pseudo-polynomial time complexity
in dlij = νi + μli elij + aj νj + μlj . so that the scaling affects the execution time; however the time
Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
GATZIANAS and GEORGIADIS: A DISTRIBUTED ALGORITHM FOR MAXIMUM LIFETIME ROUTING IN SENSOR NETWORKS WITH MOBILE SINK 989

dependence on the maximum cost exists only in the form of a guard against a very slow (numerical) convergence due to a
log function, which imposes a minimal computational burden. poor initial guess. The term “slow” refers to the fact that the
Once the solution is obtained, the costs are down-scaled to recovered primal solution at the end of maxiter iterations may
their original values so that (18) can be correctly computed. be of poor “quality”, i.e. the energy and power constraints may
Furthermore, the Lagrange minimizer in (18) is essentially be violated by a significant amount. In practice, the network
a binary decision process, i.e. the sink stays either for the designer may construct quality metrics such as the maximum
maximum allowable time T̃ l or leaves immediately. Since normalized energy and power violations, maxi∈N |e̊i −Ei |/Ei
the original bounds may be too loose, we seek to refine and maxi∈N |p̊i − Pi |/Pi , respectively (where e̊i , p̊i is the en-
them during the algorithm’s execution. This can be performed ergy/power expended by node i under the recovered solution.
through the weak duality theorem [17], which implies These two definitions are in accordance with [8]) and deem
  a recovered solution as acceptable only when these metrics
q(ν k , μk ) ≤ q ∗ ≤ − t∗ l ≤ − tl satisfy given thresholds
  (say below 10%). Obviously, a way

l∈L l∈L
(22) of modifying ν 0 , μ0 must be provided for the contingency
⇒t ≤ l
t ≤ −q(ν , μ ),
l k k
where a solution is considered unacceptable. To this end,
l∈L three heuristics were proposed in [20] and compared via
∗ ∗l simulations. It was concluded that one of them significantly
where q , t are the exact dual/primal optimal values, re-
outperforms the others and hence results will be presented for
spectively. Therefore, for every iteration where it holds T̂ l >
this heuristic, only, in a later section. The reader is referred to
−q(ν k , μk ), T̂ l can be set to the right hand side of the last
[20] for further details on the rationale behind each heuristic.
inequality (we hereafter use the notation T̂ l,k to refer to the
upper sojourn bound for location l at the end of iteration
k). Experience has shown this procedure to lead to increased IV. D ISTRIBUTED IMPLEMENTATION
execution speed. The above property can also be used to derive
an infeasibility detection criterion according to the following The previous analysis already suggests the distributed im-
fact (see Appendix II for the proof) plementation of the above solution. Specifically, we assume
that each node locally stores its Lagrange multipliers νi and μli
Corollary 1: If during the execution of the subgradient
(for a total of |L|+1 values), properly initialized. Furthermore,
projection algorithm there exists an iteration k ∗ such that
∗ for each sink location, every node can determine its outgoing
T̂ l,k = 0 for all l ∈ M ⊆ L, then for all l ∈ M there
l neighbors and estimate the associated link costs. For each
exist no flows fij satisfying the power constraints of (8). If,
location, a spanning tree5 , rooted at the sink, is constructed in
additionally, it holds M = L, then the original problem is
a distributed manner and used for message exchange between
infeasible.
the nodes and the sink. Its utility stems from the fact that
Regarding the primal recovery procedure, we adopt the
summations and min/max operations over nodes (which, as
methodology in [19], from which we have the following
will be seen, are the only operations needed by the sink
Proposition 1: Assume that for a step size sk = 1/k, the
in order to perform its task) can be easily performed in a
subgradient projection method converges to a pair (ν ∗ , μ∗ ).
distributed manner [21] through the spanning tree with only
For each iteration k, denote μkj = 1/k, ∀ j = 1 . . . k and x̃k =
O (|N |) messages (rather than having each node transmit its
(b̃, t̃)k the minimizer of the Lagrangian for the k iteration.
individual variable to the sink with the latter carrying out
Construct the sequence xk as follows
the entire computation). Also, the sink can broadcast control
x0 = x̃0 , instructions to all nodes through the spanning tree using
k 1 (23) O (|N |) messages.
xk+1 = xk + x̃k . The algorithm now proceeds as follows: the sink starts at
k+1 k+1
the first location (say l = 0) and performs some standard
Then, the sequence xk converges to a vector x̄ which is primal initializations (among which is the determination of T̂ l ). It
optimal. then instructs the network to solve, in the distributed manner of
This leads to a scheme that allows “on-the-fly” update of [16], the minimum cost flow problem of (17) using the current
the primal feasible candidate solution with no backstorage Lagrange multipliers. Once the minimum cost flow solution
required. has been attained, the total minimum cost objective F̃ l is
Application
 of the subgradient method requires an initial computed in a distributed manner and is transmitted to the sink
 
guess ν 0 , μ0 for the Lagrange multipliers, as well as two along with the quantities i∈N μli Pi , − i∈N νi Ei , which
scalar parameters maxiter and winrec denoting, respectively, are also computed in a distributed way. These values travel
a maximum number of subgradient iterations and the number towards the sink through the spanning tree and once they reach
of iterations during which the primal recovery scheme is ap- the sink, the quantity t̃l in (18) is evaluated and transmitted
plied (i.e. the subgradient method is run for at most maxiter back to the entire network through the spanning tree. Each
iterations, barring earlier convergence, and the primal recovery node then updates its current power Lagrange multiplier μli
scheme is switched “on” during the last winrec < maxiter according to (21), since the outgoing flowsare locally stored.
iterations). It is well known that choosing an initial guess Additionally, each node adds the quantity j∈S l f˜ij l l l
t̃ eij to a
i
sufficiently close to the dual solution (ν ∗, μ∗ ) is crucial in
obtaining fast convergence. Unfortunately, ν 0 , μ0 is usually 5 since all links are assumed bi-directional, the same property applies to the
chosen at random so that the parameter maxiter is used to tree as well.

Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
990 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 7, NO. 3, MARCH 2008

locally stored variable called sumR and performs the primal Algorithm 1: solve maxlife.
recovery scheme of (23), if applicable. Objective: solve problem defined in (6)–(9).
At this point, the sink moves to the next location (l = 1) and Input: the digraphs G l for all l, vectors E, P , Q, an
performs exactly the same steps as in the previous paragraph, initial guess vector (ν, μ)0 , a starting iteration
 index k0 and a maximum number of iterations
with the minor difference that the quantity − i∈N νi Ei need
not be computed again for the duration of the current round- maxi.
∗l
trip (i.e. until the sink returns to the original location). A Output: the optimal flows fij ∀ (l, i, j) ∈ L × E l and
∗l
spanning tree rooted at the new sink location must also be sojourn times t ∀ l ∈ L.
constructed and used for the exchange of control messages. 1 initialization phase ;
Again, once the new minimum cost flow problem is solved, 2 k ← k0 ;
each node updates its μli and increments its sumR variable. 3 select subgradient step-size sk = 1/k ;
This continues as the sink visits all locations in sequence. The 4 while number of iterations < maxi do
sink will eventually return to its initial location l = 0, where 5 for l ← 0 to |L| − 1 do
it will detect that a round-trip has been completed (we assume 6 if l = 0 then
that the sink is equipped with such a capability). At this point, 7 perform round-trip initialization ;
and before starting a second round-trip, the sink transmits 8 endif
a special message through the spanning tree instructing the 9 solve minimum cost flow problem for digraph G l
nodes to update their νi according to (21). If desired, the sink with respect to (ν, μ)k ;
can also transmit back the value of q (ν, μ), which has been 10 determine t̃l according to (18) ;
computed during the previous round-trip, so that the nodes 11 update blij , tl for all (i, j) ∈ E l according to (23)
can refine their T̂ l bounds from (22), if applicable. Once this if applicable ;
is performed, the sink starts a second round-trip applying the 12 update μli from k to k + 1 for all nodes if power
previous procedure verbatim. The algorithm continues in that constraints are enforced ;
manner until it is terminated by a convergence criterion being 13 endfor
satisfied. Once the complete solution has been recovered, 14 update ν from k to k + 1 for all nodes ;
the sink moves to each location and stays there for the 15 refine all lifetime upper bounds T̂ l,k according to
specified optimal sojourn time. In this sense, the round-trips (22) if applicable ;
performed until convergence is achieved can be considered as 16 test termination criterion for (ν, μ)k and (ν, μ)k+1 ;
part of the network’s initialization period (i.e. the network is 17 if termination criterion is true then
truly operational only after the algorithm has converged to a 18 return;
solution). 19 else
A pseudo-code representation of the above algorithm is 20 k ←k+1 ;
given in Fig. 2. It is clear that the core of the algorithm is the 21 endif
distributed solution of the minimum cost flow problem. The 22 endw
number and type of messages that must be exchanged for this
operation is described in detail in [20], and omitted from here
Fig. 2: Pseudocode for the maximum lifetime algorithm.
due to space restrictions. However, it should be mentioned that
a second variant of the above algorithm exists, in which the
sink performs a single round-trip, allows the nodes to discover
their neighbors for each location, and then returns to the initial communication with the sink and with another static
location and stays there for the remainder of the algorithm. node (i.e. any node other than the sink) .
Obviously, “virtual” sink movement must be emulated by the 2) the maximum energy and instantaneous power con-
sink generating appropriate messages. This variant requires the straints Ei , Pi , the Lagrange multipliers νi , μli and the
construction of a single spanning tree only, which is performed exogenous rate of information Qi (static nodes only).
when the sink returns to the initial location after the round- 3) a group of variables representing the flow surplus gi
trip. It offers the advantage of decreased initialization time and flow conservation cost pi . These are used by the
(convergence is achieved in less “actual time”6 ) but implicitly minimum cost flow algorithm [16].
assumes that the network topology is time-invariant. If this is 4) the outgoing and incoming edges in suitable doubly-
not the case, the sink must move to each location and monitor linked lists. The acquisition of this information is de-
the network topology anew. scribed in [20]. The incoming edges also require some
It follows from the previous discussion that each node memory to be reserved for the primal recovery scheme.
(including the sink, unless otherwise stated) must locally store 5) an array of maximum length (outdeg(i) + 2) necessary
the following information. for storing the children and parent of the node for the
spanning tree.
1) a node tag, possibly hardware-coded, serving as a unique 6) a number of bookkeeping variables that is independent
identifier. The sink identifier is globally recognized by of network size, i.e. O(1).
all nodes, i.e. a node can always distinguish between
A simple inspection of the previous list reveals that the
6 “actual time”, measured in seconds, is used here in contrast to “algorithmic memory required by the algorithm is O (outdeg(i) + |L|
time”, measured in subgradient iterations. +|L| · outdeg(i)) = O (|L| · outdeg(i)) per node, where the
Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
GATZIANAS and GEORGIADIS: A DISTRIBUTED ALGORITHM FOR MAXIMUM LIFETIME ROUTING IN SENSOR NETWORKS WITH MOBILE SINK 991

2 0.4
last term comes from the primal recovery scheme. This
compares very favorably to the memory requirements of a
centralized solution method such as simplex. Specifically, a
full tableau [18] simplex requires O (|N | · |L| · (|L| + |E|))

maximum ormalized energy violation

1.5 0.3

normalized maximum lifetime

memory while a revised simplex requires O |L|2 · |N |2 . The
proposed distributed algorithm clearly has superior memory
scalability than either simplex method. Furthermore, the sink 1 0.2

needs no special knowledge of the network, other than the abil-

ity to communicate with its direct neighbors (essentially, the
sink’s neighbors carry the necessary topology information to
0.5 0.1
the sink through the spanning tree) and requires minimal CPU
resources since the sum/max/min operations are performed by
the nodes themselves in a distributed manner. We consider
these properties as significant assets of the proposed algorithm. 200 220 240 260 280 300 320 340 360 380
0
400
number of iterations

V. N UMERICAL RESULTS Fig. 3. Lifetime and violation evolution for a sample network under energy
A large number of simulations was performed in order to constraints.
evaluate the proposed algorithm. Specifically three sets of 0.15 normalized maximum lifetime 0.02
network topologies with 20, 40 and 80 nodes, respectively, 1.2

were constructed as explained in [12], each set containing 100

1.1
random network instances. The sink was allowed to move over maximum normalized energy violation

maximum normalized power violation

4 locations, which were the same for all networks. In all cases, 1

each node had an exogenous rate of Qi = 1. The flow cost

of edge (i, j) was assumed proportional to d2ij , with dij the 0.9
1280 1330 1380

physical distance between the two nodes. Two scenarios were 0.1 0.01

studied: in the first one, only a power constraint of Ei = 1000

was applied while in the second one a power constraint of
Pi = 100 was also imposed (the values were chosen for
demonstration purposes only and don’t correspond to any
actual specs. Additionally, we use dimensionless quantities
since the paper’s focus is on the algorithm’s convergence
0.05 0
properties and not on actual values). The case of energy 1280 1290 1300 1310 1320 1330 1340 1350 1360 1370 1380
number of iterations
constraints only may arise when the exogenous rates are so
low that the power constraints are inactive for all nodes. Two Fig. 4. Lifetime and violation evolution for a sample network under
different (maxiter, winrec) pairs were used, (400, 200) and energy/power constraints.
(200, 100), respectively, to study the algorithm’s sensitivity to
these parameters. All these combinations resulted in a huge
data set, so that only the most representative results will left axis with the circle marker and the right axis with the
be given. The following results were obtained using the H3 solid line, respectively. The convergence of the normalized
heuristic of [20] since it provided the best performance relative computed lifetime is also shown in the subplot of Fig. 4.
to the other heuristics. Since the solution’s evolution will generally vary among
A typical evolution of the lifetime solution as well as the different random graphs, further insight may only be gained by
constraint violation is shown in Fig. 3 for the pair (400, 200) cumulative results which capture the “average” performance of
and an energy-constrained 20-node network. The normalized the algorithm. Specifically, we define the following quantities
maximum lifetime, measured by the left axis in Fig. 3 using as performance metrics for the proposed distributed algorithm
the circle markers, is defined as the ratio of the lifetime combined with the H3 heuristic.
predicted by the distributed algorithm over the lifetime com- • number of network instances (out of the original 100
puted by a standard LP solver while the normalized maximum instances) for which the algorithm produces an accept-
energy violation, previously defined in Section III, is measured able solution, i.e. a solution that minimally violates the
by the right axis in Fig. 3. A casual inspection of Fig. 3 energy/power constraints (according to criteria imposed
reveals that convergence is practically achieved even after 300 by the network designer). Denote this number as I.
iterations, assuming a 10% violation threshold in order to • the average (with respect to the I instances ) relative error
consider a solution acceptable. Hence, no additional runs are between the optimal lifetime predicted by the proposed
[Link], this is not the case for the second scenario algorithm and the optimal lifetime obtained through a
where, using the pair (200, 100) for a 40-node network, 7 centralized solution (say, simplex method).
individual runs were required for a total of 1380 iterations. • the average (with respect to the I instances) number of
This is depicted in Fig. 4, which shows the energy/power iterations required to achieve an acceptable solution.
violations for the last 100 iterations of the last run, during Under the previous definitions, for the 20-node networks
which the primal recovery scheme was applied, using the with energy constraints only and using the pair (200, 100)
Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
992 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 7, NO. 3, MARCH 2008

TABLE II
N UMBER OF ITERATIONS FOR VARIOUS SETS OF SINK LOCATIONS

20 nodes 40 nodes 80 nodes

sinks 200/100 400/200 200/100 400/200 200/100 400/200
2 859 1539 851 1644 1004 1567
4 819 1519 1141 1681 1498 1875
8 879 1538 1178 1751 1646 1942

TABLE III
E XAMPLE OF ALGORITHM ’ S ADAPTABILITY TO PARAMETER CHANGES

approach A approach B
20 nodes
problem centralized sol. lifetime lifetime violation (%) iterations lifetime violation (%) iterations
original 3.3557 3.66161 9.11 800 N/A N/A N/A
disturb 2.91661 2.91358 1.74 600 2.9306 6.19 80
disturb 0.865215 0.874121 6.44 800 0.689 7.73 160
disturb 0.382747 0.384058 0.345 800 0.40288 5.26 80
disturb 0.261876 0.275827 5.33 800 0.221995 0.0 80
80 nodes
original 1.89755 1.91398 2.01 1200 N/A N/A N/A
disturb 1.69949 1.70545 4.81 1200 1.69068 9.48 200
disturb 1.5178 1.58869 5.73 1200 1.53319 2.51 200
disturb 1.36093 1.4077 4.25 1200 1.31622 0.00 400
disturb 1.22384 1.27272 8.59 1200 1.22355 4.47 200

the algorithm produced 98 acceptable solutions with an av- trend. This is another indication of the algorithm’s robustness.
erage relative error of 3.04% and 379 iterations on average. Although the algorithm’s execution time (as measured by
This performance can be further improved by using the pair the number of iterations above) may seem too large in absolute
(400, 200), which results in 98 acceptable solutions with an terms, we note that it should be viewed relative to the expected
average error of 1.93%. This is, obviously, achieved at the cost lifetime of the WSN. WSNs are often designed to operate
of more iterations, which now rise to an average of 514. The unattended for weeks or months; hence, the allocation of
corresponding results for the 40-node networks with energy some initial time interval (in the order of seconds or minutes,
constraints only are a) 89 instances with 5.37% error and which is the algorithm’s typical execution time) in order to
647 iterations for the (200, 100) pair and b) 100 instances determine the policy that maximizes the network lifetime may
with 4.2% error and 800 iterations for the (400, 200) pair. be worthwhile.
Imposing power constraints naturally leads to an increase in Another practical issue is the algorithm’s adaptability to
iterations (since there exist more dual variables). Specifically, changing network conditions, since our method implicitly
for the 20-node networks, the pair (200, 100) produced 89 assumes that the problem parameters elij , Qi do not change
acceptable solutions with a 3.42% average error and 819 during the algorithm’s execution. Since the nodes remain
iterations, while the pair (400, 200) provided 92 solutions with stationary, the most common source of variation is a change
2.9% error and 1519 iterations. For each pair, five infeasible in Qi . Obviously, our algorithm should be applied anew to the
problems were also detected. For the 40-node networks, the modified problem; however we claim that if the variations are
(200, 100) pair provided 86 solutions with 2.67% error and slight,7 the new problem can be solved relatively fast using the
1141 iterations while the (400, 200) pair produced 93 solutions last known Lagrange multipliers of the last problem as initial
with 2.77% error and 1681 iterations. Finally, for the 80- guesses for the new one. The number of iterations cannot
node networks under power constraints, the (200, 100) pair become too small, as there is always the need for the primal
produced only 71 acceptable solutions with 3.99% average recovery, but it can still be smaller than solving the problem
error and 1498 iterations. Using the (400, 200) resulted in a anew.
huge improvement: 96 acceptable solutions with 5.11% error To examine this claim, the following experiment was per-
and 1875 iterations. Finally, in order to examine the effect of formed. Consider a power-constrained network whose nodes
the number of sink locations on the algorithm’s performance, have a time-varying Qi in the interval [7 13] with a mean
the power-constrained simulations were repeated using 8 and value of 10. Initially, all nodes have Qi = 10 and Ei =
2 sink locations, respectively The results are summarized in Pi = 1000. However, during the network’s lifetime four
Table II, which reveals that the effect of the number of sink “disturbances” occur at random epochs. In each disturbance
locations on the total number of iterations is more significant epoch, a random node changes its Qi randomly in the allowed
as the network size increases. Even in these cases, however, 7 meaning that each Q , viewed as a random variable, has a small standard
i
the increase appears to be sublinear and exhibits a diminishing deviation

Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
GATZIANAS and GEORGIADIS: A DISTRIBUTED ALGORITHM FOR MAXIMUM LIFETIME ROUTING IN SENSOR NETWORKS WITH MOBILE SINK 993

interval. Hence, in addition to the original problem, four new A PPENDIX I

LP problems need to be solved (note that apart from Qi , the S UFFICIENCY OF TIME - INVARIANT FLOWS
residual energy Ei of each node also changes between the up to time T . By definition,
Let the network be survivable 
disturbances since the network is already operational). The two there exist values T l such that l∈L T = T as well as a
l
options are either solving the problem anew without exploiting k,l k,l
sequence of valid fij , pij values, meaning that (1)–(4) are
any past information (approach A) or using the last known
satisfied. We construct the convex combinations
Lagrange multipliers as initial guess for the new “disturbed”
problem (approach B). The results of each approach are 
Kl
τkl k,l
summarized in Table III, which contains the lifetime obtained fˆij
l
 f ,
T l ij
from both approaches (with a centralized solution lifetime k=1
(24)
used as benchmark), as well as the maximum constraint Kl
τkl k,l
p̂lij  p ,
violation and the number of required iterations. The results T l ij
k=1
were obtained for a typical 20 and 80-node network. In some
K l l
cases, the distributed algorithm produced a lifetime solution for each sink location l ∈ L, where T l = k=1 τk . We only
larger than the centralized one. This was due to the fact that the need to show that this flow is feasible for the special case
recovered primal solution of the distributed algorithm violated of (1)–(4) with Kl = 1, ∀ l ∈ L. We verify each constraint
the energy/power constraints, as evidenced in Table III. If the separately
constraints are hard (i.e. they must be satisfied), they can be
met by reducing them by an amount equal to the maximum  (24)    τ k,l k,l l (1)
Kl
p̂lij T l = p T ≤ Ei , (25)
allowable violation (10% in our case) required for a recovered
l l
T l ij
l∈L j∈Si l∈L j∈Si k=1
solution to be considered acceptable. Hence, an acceptable
solution to the reduced-constraint problem is guaranteed to be  (24)   τkl k,l (2)  τkl
Kl Kl

feasible for the original problem, and hence it will not exceed =
p̂lij p ≤ Pi ≤ Pi , (26)
T l ij Tl
the centralized solution. j∈Sil j∈Sil k=1 k=1

K 
 τkl k,l (3)  τkl  k,l conc 
Kl Kl l
Clearly, approach B can obtain very good solutions with
ˆ τkl k,l
acceptable constraint violations and, most importantly, using fij =
l
f ≤ h pij ≤ h p ,
T l ij Tl T l ij
k=1 k=1 k=1
at most 400 or 160 iterations for the 80 and 20 node network,
(27)
respectively. Solving the problem from scratch (approach A)
allows us to obtain superior accuracy compared to approach B where the last inequality is due to the concavity of h. Finally,
in some cases (i.e. for the 20-node network) but at the cost of the flow conservation for fˆij l
is obtained by multiplying both
far more iterations. Although the decision of which approach l l
sides of (4) with τk /T , summing over k for each location l
to use lies with the network designer, we believe the above and interchanging the summations. This results in
example illustrates the algorithm’s ability to adapt to small  
network perturbations. fˆij
l
= Qi + fˆji
l
, ∀ i ∈ N ∪ {s}, ∀ l ∈ L. (28)
j∈Sil i∈Sjl

Hence, under the convex combination of (24), the network is

VI. C ONCLUSIONS AND FUTURE WORK still survivable up to time T . This concludes the proof.

This paper presented a distributed algorithm for computing A PPENDIX II

the maximum lifetime of a sensor network which routes P ROOF OF C OROLLARY 1
data to a mobile sink. By imposing flow conservation to all
Proof is by contradiction. Specifically, assume that there
sink locations and removing some constraints from the dual l
exists a flow vector fij satisfying power and flow conservation
problem, the number of Lagrange multipliers was reduced and
constraints for some l ∈ M. Then, for this l we could pick
the dual problem acquired special structure that allowed for
a sufficiently small, but still positive tl , such that the energy
an efficient solution using the standard subgradient method
constraint is satisfied for all i ∈ N and arrive at a feasible
and the minimum cost flow -relaxation algorithm. The effi-
solution with positive sojourn. However, this is a contradiction
ciency of the proposed algorithm was studied by numerical ∗
since the assumption T̂ l,k = 0 implies, according to (22), that
simulation.
the sojourn time at location l is zero for any feasible solution.
The case of a mobile sink has not received as much attention If M = L, then, from the above, no power-satisfying feasible
as the single immobile sink. Hence, most open problems re- solutions exist for any l ∈ L and the problem is therefore
garding the latter case, such as various convexifications of the infeasible.
general non-convex interference-based model or incorporation
of stochastic components into the model, carry over to the
former. We consider the stochastic aspects of the problem R EFERENCES
(including fading effects) to be of more interest, especially [1] A. Michail and A. Ephremides, “Energy-efficient routing for connection-
since previous work, such as [22], has been restricted to a oriented traffic in wireless ad-hoc networks,” Mobile Networks and
Applications, no. 8, pp. 517–533, 2003.
semi-deterministic setting and we plan to investigate these in [2] V. Rodoplu and T. Meng, “Minimum energy mobile wireless networks,”
the future. in Proc. IEEE ICC, vol. 3, June 1998, pp. 1633–1639.

Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.
994 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 7, NO. 3, MARCH 2008

[3] L. Xiao, M. Johansson, and S. Boyd, “Simultaneous routing and resource [18] D. Bertsimas and J. Tsitsiklis, Introduction to linear optimization.
allocation via dual decomposition,” IEEE Trans. Commun., vol. 52, Athena Scientific, 1997.
no. 7, pp. 1136–1144, July 2004. [19] H. Sherali and G. Choi, “Recovery of primal solutions when using
[4] R. Cruz and A. Santhaman, “Optimal routing, link scheduling and power subgradient optimization methods to solve Lagrangian duals of linear
control in multi-hop wireless networks,” in Proc. IEEE INFOCOM, Mar. programs,” Operations Research Lett., vol. 19, pp. 105–113, 1996.
2003, pp. 702–711. [20] M. Gatzianas and L. Georgiadis, “Application of a distributed minimum
[5] M. Kalantari and M. Shayman, “Energy efficient routing in wireless cost flow algorithm to the maximum network lifetime problem.”
sensor networks,” in Proc. Conference on Information Sciences and [Online]. Available: [Link] [Link]
Systems, Mar. 2004. [21] N. Lynch, Distributed Algorithms. Morgan Kaufmann, 1996.
[6] S. Toumpis and L. Tassiulas, “Optimal deployment of wireless sensor [22] J. Li and S. Dey, “Lifetime optimization for wireless sensor networks
networks,” IEEE Trans. Inf. Theory, vol. 52, no. 7, pp. 2935–2953, July with outage probability constraints,” in Proc. 12th European Wireless,
2006. Apr. 2006, available in electronic form only.
[7] J. Chang and L. Tassiulas, “Energy conserving routing in wireless ad-
hoc networks,” in Proc. IEEE INFOCOM, 2000, pp. 22–31. Marios Gatzianas received the Diploma degree in
[8] R. Madan and S. Lall, “Distributed algorithms for maximum lifetime Electrical and Computer Engineering from Aristotle
routing in wireless sensor networks,” IEEE Trans. Wireless Commun., University, Thessaloniki, Greece and the M.S. de-
vol. 5, no. 8, pp. 2185–2193, Aug. 2006. gree in EE from Arizona State University in 2000
[9] R. Madan, S. Cui, S. Lall, and A. Goldsmith, “Cross-layer design for and 2003, respectively. He is currently pursuing a
lifetime maximization in interference-limited wireless sensor networks,” Ph.D. degree in the former institute. His research
in Proc. IEEE INFOCOM, vol. 3, Mar. 2005, pp. 1964–1975. interests include optimization and control of wireless
[10] S. Gandham, M. Dawande, R. Prakash, and S. Venkatesan, “Energy ad-hoc networks, asymptotic analysis, and distrib-
efficient schemes for wireless sensor networks with multiple mobile uted algorithms.
base stations,” in Proc. IEEE GLOBECOM, vol. 1, 2003, pp. 377–381.
[11] Z. Wang, S. Basagni, E. Melachrinoudis, and C. Petrioli, “Exploiting Leonidas Georgiadis (S’76-M’78-SM’96) received
sink mobility for maximizing sensor networks lifetime,” in Proc. 38th the Diploma degree in Electrical Engineering from
HICSS, 2005. Aristotle University, Thessaloniki, Greece, in 1979,
[12] I. Papadimitriou and L. Georgiadis, “Maximum lifetime routing to and his M.S. and Ph.D. degrees both in electrical
mobile sink in wireless sensor networks,” in Proc. SoftCOM, Sept. 2005. engineering from the University of Connecticut, in
[13] J. Luo, “Mobility in wireless networks: friend or foe, network design 1981 and 1986 respectively. From 1981 to 1983 he
and control in the age of mobile computing,” Ph.D. dissertation, EPFL, was with the Greek army. From 1986 to 1987 he
2006. was Research Assistant Professor at the University
[14] B. Radunovic and J. L. Boudec, “Optimal power control, scheduling and of Virginia, Charlottesville. In 1987 he joined IBM
routing in UWB networks,” IEEE J. Select. Areas Commun., vol. 22, T. J. Watson Research Center, Yorktown Heights as
no. 7, pp. 1252–1270, 2004. a Research Staff Member. Since October 1995, he
[15] R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, has been with the Telecommunications Department of Aristotle University,
and Applications. Prentice Hall, 1993. Thessaloniki, Greece. His interests are in the area of wireless networks, high
[16] D. Bertsekas and J. Tsitsiklis, Parallel and Distributed Computation: speed networks, distributed systems, routing, scheduling, congestion control,
Numerical Methods. Prentice Hall, 1989. modeling and performance analysis. In 1992 he received the IBM Outstanding
[17] D. Bertsekas, A. Nedić, and A. Ozdaglar, Convex Analysis and Opti- Innovation Award for his work on Goal-Oriented Workload Management for
mization. Athena Scientific, 2003. Multi-class systems.

Authorized licensed use limited to: C.V. Raman College of Engineering. Downloaded on August 19, 2009 at 21:35 from IEEE Xplore. Restrictions apply.