Power-Aware Localized Routing in Wireless Networks.
AbstractRecently, a cost aware metric for wireless networks based on remaining battery power at nodes was proposed for shortest-cost routing algorithms, assuming constant transmission power. Power-aware metrics, where transmission power depends on distance between nodes and corresponding shortest power algorithms were also recently proposed. We define a new power-cost metric based on the combination of both node's lifetime and distance-based power metrics. We investigate some properties of power adjusted transmissions and show that, if additional nodes can be placed at desired locations between two nodes at distance d, the transmission power can be made linear in d as opposed to d^\alpha dependence for \alpha\geq 2. This provides basis for power, cost, and power-cost localized routing algorithms where nodes make routing decisions solely on the basis of location of their neighbors and destination. The power-aware routing algorithm attempts to minimize the total power needed to route a message between a source and a destination. The cost-aware routing algorithm is aimed at extending the battery's worst-case lifetime at each node. The combined power-cost localized routing algorithm attempts to minimize the total power needed and to avoid nodes with a short battery's remaining lifetime. We prove that the proposed localized (where each node makes routing decisions based solely on the location of itself, its neighbors, and destination) power, cost, and power-cost efficient routing algorithms are loop-free and show their efficiency by experiments.
Introduction
In this paper we consider the routing task, in which a message is to be sent from a source node
to a destination node (in a sensor or ad hoc wireless network). Due to propagation path loss, the
transmission radii are limited. Thus, routes between two hosts in the network may consist of hops
through other hosts in the network. The nodes in the network may be static (e.g. thrown from an
aircraft to a remote terrain or a toxic environment), static most of the time (e.g. books, projectors,
furniture) or moving (vehicles, people, small robotic devices). Wireless networks of sensors are
likely to be widely deployed in the near future because they greatly extend our ability to monitor
and control the physical environment from remote locations and improve our accuracy of
information obtained via collaboration among sensor nodes and online information processing at
those nodes. Networking these sensors (empowering them with the ability to coordinate amongst
themselves on a larger sensing task) will revolutionize information gathering and processing in
many situations. Sensor networks have been recently studied in [EGHK, HCB, HKB, KKP]. A
similar wireless network that received significant attention in recent years is ad hoc network [IETF,
MC]. Mobile ad hoc networks consist of wireless hosts that communicate with each other in the
absence of a fixed infrastructure. Some examples of the possible uses of ad hoc networking include
soldiers on the battlefield, emergency disaster relief personnel, and networks of laptops.
Macker and Corson [MC] listed qualitative and quantitative independent metrics for judging the
performance of routing protocols. Desirable qualitative properties [MC] include: distributed
operation, loop-freedom, demand-based operation and 'sleep' period operation, while hop count and
delivery rates are among quantitative metrics. We shall further elaborate on these properties and
metrics, in order to address the issue of routing in wireless networks while trying to minimize the
energy consumption and/or reduce the demands on nodes that have significantly depleted batteries.
This is an important problem since battery power at each node is limited. Our final goal is to design
routing protocols with the following properties.
a) Minimize energy required per routing task. Hop count was traditionally used to measure
energy requirement of a routing task, thus using constant metric per hop. However, if nodes can
adjust their transmission power (knowing the location of their neighbors) then the constant metric
can be replaced by a power metric that depends on distance between nodes [E, RM, HCB]. The
distance between neighboring nodes can be estimated on the basis of incoming signal strengths (if
some control messages are sent using fixed power). Relative coordinates of neighboring nodes can
be obtained by exchanging such information between neighbors [CHH]. Alternatively, the location
of nodes may be available directly by communicating with a satellite, using GPS (Global
Positioning System), if nodes are equipped with a small low power GPS receiver. We will use
location information in making routing decisions as well, to minimize energy per routing task.
b) Loop-freedom. The proposed routing protocols should be inherently loop-free, to avoid
timeout or memorizing past traffic as cumbersome exit strategies.
c) Maximize the number of routing tasks that network can perform. Some nodes participate in
routing packets for many source-destination pairs, and the increased energy consumption may
result in their failure. Thus pure power consumption metric may be misguided in the long term
[SWR]. A longer path that passes through nodes that have plenty of energy may be a better solution
[SWR]. Alternatively, some nodes in the sensor or ad hoc network may be temporarily inactive,
and power consumption metric may be applied on active nodes.
d) Minimize communication overhead. Due to limited battery power, the communication
overhead must be minimized if number of routing tasks is to be maximized. Proactive methods that
maintain routing tables with up-to date routing information or global network information at each
node are certainly unsatisfactory solution, especially when node mobility is high with respect to
data traffic. For instance, shortest path based solutions are too sensitive to small changes in local
topology and activity status (the later even does not involve node movement).
memorizing past traffic or route. Solutions that require nodes to memorize route or
past traffic are sensitive to node queue size, changes in node activity and node mobility while
routing is ongoing (e.g. monitoring environment). Flexibility in selecting routes is thus preferred.
f) Localized algorithms. Localized algorithms [EGHK] are distributed algorithms that resemble
greedy algorithms, where simple local behavior achieves a desired global objective. In a localized
routing algorithm, each node makes decision to which neighbor to forward the message based
solely on the location of itself, its neighboring nodes, and destination. While neighboring nodes
may update each other location whenever an edge is broken or created, the accuracy of destination
location is a serious problem. In some cases, such as monitoring environment by sensor networks,
the destination is a fixed node known to all nodes (i.e. monitoring center). Our proposed algorithms
are directly applicable in such environments. All non-localized routing algorithms proposed in
literature are variations of shortest weighted path algorithm (e.g. [CN, LL, RM, SWR]).
g) Single-path routing algorithms. The task of finding and maintaining routes in mobile
networks is nontrivial since host mobility causes frequent unpredictable topological changes. Most
previously proposed position based routing algorithms (e.g. [BCSW, KV]) for wireless ad hoc
networks were based on forwarding the actual message along multiple paths toward an area where
destination is hopefully located, hoping to achieve robustness. However, we have shown in our
previous work that single-path strategies may be even more robust (for instance, they can guarantee
delivery [BMSU]) and with less communication overhead. The significant communication
overhead can be avoided if a variant of source-initiated on-demand routing strategy [BMJHJ, RT]
is applied. In the strategy, the source node issues several search 'tickets' (each ticket is a 'short'
message containing sender's id and location, destination's id and best known location and time
when that location was reported, and constant amount of additional information) that will look for
the exact position of destination node. When the first ticket arrives at the destination node D, D will
report back to the source with brief message containing its exact location, and possibly creating a
route for the source. The source node then sends full data message ('long' message) toward exact
location of destination. The efficiency of destination search depends on the corresponding location
update scheme. A quorum based location update scheme is being developed in [S2]. Other schemes
may be used, with various trade-offs between the success and flooding rates (including an
occasional flooding). If the routing problem is divided as described, the mobility issue is
algorithmically separated from the routing issue, which allows us to consider (in this paper) only
the case of static networks with known destination in our algorithms and experiments. The choice is
justified whenever the destination does not move significantly between its detection and message
delivery, and information about neighboring nodes is regularly maintained. Yet another routing
method may forward message toward imprecise destination location, hoping that closer nodes will
locate destination more accurately.
Maximize delivery rate. Our localized algorithms achieve a very high delivery rates for dense
networks, while further improvements are needed for sparse networks. We have designed power,
cost, and power-cost routing algorithms that guarantee delivery, which is an extension to be
reported elsewhere [SD].
The final important goal of a routing algorithm is to handle node mobility with proper location
update schemes. This issue seems to be the most complex of all discussed here, as argued in an
upcoming report [S].
Ad hoc and sensor networks are best modeled by minpower graphs constructed in the
following way. Each node A has its transmission range t(A). Two nodes A and B in the network are
neighbors (and thus joined by an edge) if the Euclidean distance between their coordinates in the
network is less than the minimum between their transmission radii (i.e. d(A,B) < min {t(A), t(B)}).
If all transmission ranges are equal, the corresponding graph is known as the unit graph. The
minpower and unit graphs are valid models when there are no obstacles in the signal path. Ad hoc
and sensor networks with obstacles can be modeled by subgraphs of minpower or unit graphs. The
properties of power metrics, the proposed algorithms and their loop free properties in this paper are
valid for arbitrary graphs. We have used, however, only unit graphs in our experiments.
A number of protocols for achieving efficient routing have been recently proposed. They differ
in the approach used for searching a new route and/or modifying a known route, when hosts move.
The surveys of these protocols, that do not use geographic location in the routing decisions, are
given in [BMJHJ, IETF, RS, RT]. The power awareness in these protocols is limited to the amount
of control messages sent and degree of message flooding. While the computational power of the
devices used in the network is rapidly increasing, the lifetime of batteries is not expected to
improve much in the future. We see a clear need for improvement in power consumption in
existing MAC protocols and routing algorithms [SWR].
In the next section, we shall review known power aware metrics and routing algorithms. In
section 3, existing routing protocols that use geographic location or consider power in their route
decisions are reviewed. Section 4 discusses the effect of power awareness on the routing decisions
in GPS based algorithms. Section 5 proposes three distributed (localized) algorithms aimed at
extending node and/or network life. In section 6, we prove that these algorithms are loop-free.
Their performance evaluation is given in sections 7 and 8.
2. Existing power aware metrics and routing algorithms
In most of routing protocols the paths are computed based on minimizing hop count or delay.
When transmission power of nodes is adjustable, hop count may be replaced by power
consumption metric. Some nodes participate in routing packets for many source-destination pairs,
and the increased energy consumption may result in their failure. A longer path that passes through
nodes that have plenty of energy may be a better solution [SWR].
The algorithm [SWR] proposed to use a function f(A) to denote node A's reluctance to forward
packets, and to choose a path that minimizes the sum of f(A) for nodes on the path. This routing
protocol [SWR] addresses the issue of energy critical nodes. As a particular choice for f, [SWR]
proposes f(A)=1/g(A) where g(A) denotes the remaining lifetime (g(A) is normalized to be in the
interval [0,1]). Thus reluctance grows significantly when lifetime approaches 0. The other metric
used in [SWR] is aimed at minimizing the total energy consumed per packet. However, [SWR]
merely observes that the routes selected when using this metric will be identical to routes selected
by shortest hop count routing, since the energy consumed in transmitting (and receiving) one
packet over one hop is considered constant. For each of the two proposed power consumption
metrics (cost and hop count), [SWR] assigns weights to nodes or edges, and then refers to non-localized
Dijkstra's algorithm for computing shortest weighted path between source and
destination. We also observed that the validation of power aware metrics in [SWR] was done on
random graphs where each pair of nodes is joined by an edge with a fixed probability p.
Rodoplu and Meng [RM] proposed a general model in which the power consumption between
two nodes at distance d is u(d)=d a +c for some constants a and c, and describe several properties of
power transmission that are used to find neighbors for which direct transmission is the best choice
in terms of power consumption. In their experiments, they adopted the model with u(d)= d 4 +2*10 8 ,
which will be referred to as RM-model. They discuss that large-scale variations (modeled by
lognormal shadowing model) can be incorporated into the path loss formula, and that small-scale
variations (modeled by a Rayleigh distribution) may be handled by diversity techniques and
combiners at the physical layer. Rodoplu and Meng [RM] described a power aware routing
algorithm which runs in two phases. In the first phase, each node searches for its neighbors and
selects these neighbors for which direct transmission requires less power than if an intermediate
node is used to retransmit the message. This defines so called enclosure graph. In the second phase,
each possible destination runs distributed loop-free variant of non-localized Bellman-Ford shortest
path algorithm and computes shortest path for each possible source. The same algorithm is run
from each possible destination. The algorithm is thus proactive, resulting in significant overhead
for low data traffic volumes. We observe that, since the energy required to transmit from node A to
node B is the same as energy needed to transmit from node B to node A, the same algorithm may be
applied from each possible source, and used to discover the best possible route to each destination
node. Alternatively, it may be used to find the location of destination and the best route to it. Such
on-demand variant is a competitive routing protocol but requires path memorization, and may not
be energy efficient since a single transmission at larger radius may reach more nodes at once.
Ettus [E] showed that minimum consumed energy routing reduces latency and power
consumption for wireless networks utilizing CDMA, compared to minimum transmitted energy
algorithm (shortest path algorithm was used in experiments). Heizelman, Chandrakasan and
Balakrishnan [HCB] used signal attenuation to design an energy efficient routing protocol for
wireless microsensor networks, where destination is fixed and known to all nodes. They propose to
utilize a 2-level hierarchy of forwarding nodes, where sensors form clusters and elect a random
clusterhead. The clusterhead forwards transmissions from each sensor within its own cluster. This
scheme is shown to save energy under some conditions. However, clustering requires significant
communication overhead, routing algorithm is not localized, and the destination is not necessarily
fixed. Nevertheless, their simple radio model and metric is adopted in our paper, as follows.
In the simple radio model [HCB], radio dissipates E elec =50 nJ/bit to run the transceiver
circuitry. Both sender and receiver node consume E elec to transmit one bit between them. Assuming
loss, where d is the distance between nodes, transmit amplifier at the sender node
consumes further E ampd
. Thus, to transmit one bit message at distance
d, the radio expends and to receive the message, the radio expends E elec . In order to
normalize the constants, divide both expressions by E amp , so that radio expands T=E
transmission and P=E for reception, where E= E elec /E amp=500 m 2 . Note that T/P= 1+ d 2 /E and
Therefore, in this model, referred to as HCB-model, the power needed for
transmission and reception at distance d is u(d)= 2E+ d 2 .
Chang and Tassiulas [CT1, CT2] independently proposed combining power and cost into a
single metric. Preliminary versions of this paper were published as technical report [SL-tr] and
presented at a conference [SL2]. In [CT1] they experimented with
is energy for transmission on link ij with length d, l and c are small constants, and
remaining battery power at node i. In [CT2] they proposed a general
c ,
initial energy at node i, and a , b and c are constants. They consider routing tasks with
fixed source-destination pairs, one-to-one [CT1] and one-to-many [CT2] cases. The power needed
for reception is not considered. Distributed non-localized Bellman-Ford shortest weighted path
algorithm is used. Their experiments indicate (a,b,c)=(1,50,50) as values that are close to optimal
one. Network lifetime is maximized when traffic is balanced among the nodes in proportion to their
energy reserves, instead of routing to minimize the absolute consumed power [CT1, CT2].
3. Existing GPS based routing methods
Most existing routing algorithms do not consider the power consumption in their routing
decisions. They are reviewed here in order to compare experimentally their power savings
performance with newly proposed algorithms. All described routing algorithms are localized,
demand-based and adapt well to 'sleep' period operation. Several GPS based methods were
proposed in 1984-86 by using the notion of progress. Define progress as the distance between the
transmitting node and receiving node projected onto a line drawn from transmitter toward the final
destination. A neighbor is in forward direction if the progress is positive; otherwise it is said to be
in backward direction. In the random progress method [NK], packets destined toward D are routed
with equal probability towards one neighboring node that has positive progress. In the NFP method
[HL], packet is sent to the nearest neighboring node with forward progress. Takagi and Kleinrock
proposed MFR (most forward within radius) routing algorithm, where packet is sent to the
neighbor with the greatest progress. The method is modified in [HL] by proposing to adjust the
transmission power to the distance between the two nodes. Finn [F] proposed a variant of random
progress method, called Cartesian routing, which 'allows choosing any successor node which makes
progress toward the packet's destination' [F]. The best choice depends on the complete topological
knowledge. Finn [F] adopted the greedy principle in his simulation: choose the successor node that
makes the best progress toward the destination. When no node is closer to the destination than
current node C, the algorithm performs a sophisticated procedure that does not guaranty delivery.
Recently, three articles [BCSW, KV, KSU] independently reported variations of fully
distributed routing protocols based on direction of destination. In the compass routing (or DIR)
method proposed by Kranakis, Singh and Urrutia [KSU], the source or intermediate node A uses
the location information for the destination D to calculate its direction. The location of one hop
neighbors of A is used to determine for which of them, say C, is the direction AC closest to the
direction of AD. The message m is forwarded to C. The process repeats until the destination is,
hopefully, reached. A counterexample showing that undetected loops can be created in directional
based methods is given in [SL]. The method is therefore not loop-free.
GEDIR routing algorithm [SL] is a variant of greedy routing algorithm [F] with a 'delayed'
failure criterion. GEDIR, MFR, and compass routing algorithms fail to deliver message if the best
choice for a node currently holding message is to return it to the previous node [SL]. Such criterion
reduced failure rate and provided fair comparison in our experiments. GEDIR and MFR algorithms
are inherently loop-free [SL]. The proofs are based on the observation that distances (dot products,
respectively) of nodes toward destination are decreasing. A routing algorithm that guarantees
delivery by finding a simple path between source and destination is described in [BMSU].
The 2-hop variants of three basic routing algorithms were proposed in [SL]. The delivery rate of
GEDIR, compass routing (or DIR) or MFR algorithms can be improved if each node is aware of its
2-hop neighbors (neighbors of its neighbors). The node A currently holding the message may then
choose the node closest to the destination among all 1-hop and 2-hop neighbors, and forward the
message to its neighbor that is connected to the choice. In case of ties (that is, more than one
neighbor connected to the closest 2-hop neighbor), choose the one that is closest to destination.
This review did not include various flooding based or multiple paths routing algorithms or
methods for sending control messages to update positions [BCSW, KV, S2]. Our primary interest
in this paper is to examine power consumption under assumption that nodes have accurate
information about the location of their neighbors and destination node (e.g. static networks, source-initiated
on-demand routing, or networks with superb location update scheme).
4. Some properties of power adjusted transmissions
In this section we shall study the optimality of power adjusted transmissions, using a simple and
general radio model. We shall further generalize the model of [RM] (by adding a linear factor) and
assume that the power needed for the transmission and reception of a signal is u(d)=ad a
Constant factor c in this expression for total energy consumption may also include the energy
consumed in computer processing and encoding/decoding at each station. Next, the leading
coefficient a can be adjusted to the physical environment, unit of length considered, unit size of a
signal (a bit, byte, or frame, for example) etc. In the RM-model a=4, a=1, b=0, c=2*10 8 , while in
the HCB-model a=2, a=1, b=0, c=2E. These two models were used in our experiments.
Suppose that the sender S is able to transmit the packet directly to the destination D. Let us
examine whether energy can be saved by sending the packet to an intermediate node A between the
nodes and forwarding the packet from A to D. Let |SD|=d, |SA|=x, |AD|=d-x.
Lemma 1. If d>(c/(a(1-2 1-a ))) 1/a then there exists intermediate node A between source S and
destination D so that the retransmission will save the energy. The greatest power saving is obtained
when A is in the middle of SD.
Proof. The power needed to send message directly from S to D is u(d)=ad a while the
power needed to send via A is (ax a
bd +c is satisfied for g(x)=a(x a
minimum for g(x) is obtained for g'(x)=0, i.e. a(ax a-1 - a(d-x) a-1 )=0. Thus x
or x=d/2. The minimum is <0 if g(d/2)<0, i.e. a((d/2) a or ad a (2 1-a -1)+c <0,
which is satisfied for c< ad a (1-2 1-a ), or d a > c/(a(1-2 1-a )), and lemma follows. Note that this
inequality has a solution in d if and only if a>1.
Lemma 2. If d>(c/(a(1-2 1-a ))) 1/a then the greatest power savings are obtained when the interval
SD is divided into n>1 equal subintervals, where n is the nearest integer to d(a(a-1)/c) 1/a . The
minimal power is then bd
Proof. Let SD be divided into intervals of lengths x 1 , x 2 , ., x n such that d=x 1 . The
energy needed for transmissions using these intervals is (ax 1
a
a +bx n
a
a ). For fixed x i +x j , the expression x i
a
a is minimal when x
1). Therefore the energy is minimal when x and is equal to f(n)=cn
a +bd. This expression has the minimum when f'(n)=0, or c+ a(1-a)n -a d a =0,
i.e. c=a(a-1)n -a d a , n a =a(a-1)d a /c, n=d(a(a-1)/c) 1/a (n is rounded to nearest integer).
Assuming that we can set additional nodes in arbitrary positions between the source and
destination, the following theorem gives power optimal packet transmissions.
Theorem 1. Let d be the distance between the source and the destination. The power needed for
direct transmission is u(d)=ad a bd +c which is optimal if d  (c/(a(1-2 1-a ))) 1/a . Otherwise (that is,
when d > (c/(a(1-2 1-a ))) 1/a ), n-1 equally spaced nodes can be selected for retransmissions, where
(rounded to nearest integer), producing minimal power consumption of about
Corollary 1. Let a=2. The power needed for direct transmission is u(d)=ad bd +c which is
optimal if d  (2c/a) 1/2 . Otherwise (that is, when d > (2c/a) 1/2 ), n-1 equally spaced nodes can be
selected for retransmissions, where n= d(a/c) 1/2 (rounded to nearest integer), producing minimal
power consumption of about v(d)=2d(ac) 1/2
Theorem 1 announces the possibility of converting polynomial function in d (with exponent a)
for power consumption (in case of direct transmission from sender to destination) to linear function
in d by retransmitting the packet via some intermediate nodes that might be available.
5. Power saving routing algorithms
If nodes have information about position and activity of all other nodes then optimal power
saving algorithm, that will minimize the total energy per packet, can be obtained by applying
Dijkstra's single source shortest weighted path algorithm, where each edge has weight u(d)=ad a
bd +c, where d is the length of the edge. This will be referred as the SP-power algorithm.
We shall now describe a corresponding localized routing algorithm. The source (or an
should select one of its neighbors to forward packet toward destination, with
the goal of reducing the total power needed for the packet transmission. Let A be a neighbor of B,
and let r=|AB|, d=|BD|, s=|AD|. The power needed for transmission from B to A is u(r)=ar a
+c, while the power needed for the rest of routing algorithm is not known. Assuming uniformly
distributed network, we shall make a fair assumption that the power consumption for the rest of
routing algorithm is equal to the optimal one (see Theorem 1). That is, the power needed for
transmitting message from A to D is estimated to be v(s)= bs
For a=2, v(s)=2s(ac) 1/2 bs. This is, of course, an unrealistic assumption. However, it is fair to all
nodes. A more realistic assumption might be to multiply the optimal power consumption by a factor
t, which is a constant that depends on the network.
The localized power efficient routing algorithm can be described as follows. Each node B
(source or intermediate node) will select one of its neighbors A which will minimize
p(B,A)=u(r)+v(s)= ar a . For a=2 it becomes
bs. If destination D is a neighbor of B then compare the
expression with the corresponding one, u(d)=ad a needed for direct transmission (s=0 for
D, and D can be treated as any other neighbor). The algorithm proceeds until the destination is
reached, if possible. A generalized power efficient routing algorithm may attempt to minimize
p(B,A)=u(r)+tv(s), where t is a network parameter.
In the basic (experimental) version of the algorithms, the transmission stops if message is to be
returned to a neighbor it came from (otherwise, a detectable loop is created). The power-efficient
routing algorithm may be formalized as follows.
Repeat
Let A be neighbor of B that minimizes p(B,A)=u(r)+ tv(s);
Send message to A
until A=D (* destination reached *) or A=B (* delivery failed *)
Let us now consider the second metric proposed in [SWR], measuring the nodes lifetime.
Recall that the cost of each node is equal to f(A)=1/g(A) where g(A) denotes the remaining lifetime
is normalized to be in the interval [0,1]). [SWR] proposed shortest weighted path algorithm
based on this node cost. It is referred to as the SP-cost algorithm in experimental data in Table 2.
The algorithm uses the cost to select the path, but the actual power is charged to nodes.
The localized version of this algorithm, assuming constant power for each transmission, can be
designed as follows. The cost c(A) of a route from B to D via neighboring node A is the sum of the
cost f(A) =1/g(A) of node A and the estimated cost of route from A to D. The cost f(A) of each
neighbor A of node B currently holding the packet is known to B. What is the cost of other nodes on
the remaining path? We assume that this cost is proportional to the number of hops between A and
D. The number of hops, in turn, is proportional to the distance s=|AD|, and inversely proportional
to radius R. Thus the cost is ts/R, where factor t is to be investigated separately. Its best choice
might even be determined by experiments. We have considered the following choices for factor t:
i) t is a constant number, which may depend on network conditions,
ii) t= f(A) (that is, assuming that remaining nodes have equal cost as A itself),
iii) t= f'(A), where f'(A) is the average value of f(X) for A and all neighbors X of A,
iv) t=1/g'(A), where g'(A) is the average value of g(X) for A and all neighbors X of A.
Note that t=t(A) depends on A. The cost c(A) of a route from S to D via neighboring node A is
estimated to be c(A)=f(A)+ts/R, for the appropriate choice of t. We also suggest to investigate the
product of two contributing elements instead of their sum, that is the cost definition c(A)= f(A)ts/R.
The localized cost efficient routing algorithm can be described as follows. If destination is one
of neighbors of node B currently holding the packet then the packet will be delivered to D.
Otherwise, B will select one of its neighbors A which will minimize c(A). The algorithm proceeds
until the destination is reached, if possible, or until a node selects the neighbor the message came
from as its best option to forward the message. The algorithm can be coded as follows.
Repeat
Let A be neighbor of B that minimizes c(A);
If D is neighbor of B
then send to D else send to A
until D is reached or A=B;
The versions of this cost routing algorithm that use choices ii) and iii) for t (t=f(A) and t=f'(A),
respectively), will be referred to as cost-ii and cost-iii algorithms in our experiments.
We may incorporate both power and cost considerations into a single routing algorithm. A new
power-cost metrics is first introduced here. What is the power-cost of sending a message from node
B the neighboring node A? We propose two different ways to combine power and cost metrics into
a single power-cost metric, based on the product and sum of two metrics, respectively. If the
product is used, then the power-cost of sending message from B to a neighbor A is equal to power-
cost(B,A)=f(A)u(r) (where |AB|=r). The sum, on the other hand, leads to a new metrics power-
suitably selected values of a and b. For example, sender node S may
fix a=f'(S) and b=u(r'), where r' is the average length of all edges going out of S. The values a and
b are (in this version) determined by S and used, without change, by other nodes B on the same
route. The corresponding shortest path algorithms can find the optimal power-cost by applying
single source shortest weighted path Dijkstra's algorithm (the node cost is transferred to the edge
leading to the node). The algorithm will be referred to as the SP-Power*Cost and SP-Power+Cost
algorithms, respectively, in Table 2.
The power-cost efficient routing algorithm may be described as follows. Let A be the neighbor
of B (node currently holding the message) that minimizes pc(B,A)=
(where s=0 for D, if D is a neighbor of B). The algorithm is named power-cost0 in Table 2 when
power-cost(B,A)=f(A)u(r), and power-cost1 when power-cost(B,A)= f'(S)u(r)+u(r')f(A). The packet
is delivered to A. Thus the packet is not necessarily delivered to D, when D is a neighbor of B. The
algorithm proceeds until the destination is reached, if possible, and may be coded as follows.
Repeat
Let A be neighbor of B that minimizes pc(B,A)=
Send message to A
until A=D (* destination reached *) or A=B (* delivery failed *);
The algorithm may be modified in several ways. The second term may be multiplied by a factor
that depends on network conditions. We tested also the version, called power-cost2, that minimizes
pc(B,A)=f(A)(u(r)+v(s)), and an algorithm, called power-costP, that switches selection criteria from
power-cost to power metric only whenever destination D is a neighbor of current node A.
6. Loop-free property
Theorem 2. The localized power efficient routing algorithm is loop-free.
Proof. Suppose that, on the contrary, there exists a loop in the algorithm. Let A 1 , A 2 , . A n
be the nodes in the loop, so that A 1 send the message to A 2 , A 2 sends the message to A 3 , ., A n-1
sends the message to A n and A n sends the message to A 1 (see Fig. 1). Let s 1 , s 2 , ., s n be the
distances of A 1 , A 2 , . A n from D, respectively, and let |A n A 1 |=r 1 , |A 1 A 2 |=r 2 , |A 2 A 3 |=r 3 , .,
|A n-1 A n |=r n . Let u(r)= ar a
bs). According to the choice of neighbors, it follows that u(r 1 )+v(s 1 )<u(r n )+v(s n-1 )
since the node A n selects A 1 , not A n-1 , to forward the message. Similarly u(r 2
since A 1 selects A 2 rather than A n . Next, u(r 3 )+v(s 3
By summing left and right sides we obtain u(r
which is a contradiction since both sides contain
the same elements. Thus the algorithm is loop-free.
A n-1
r n-1 D r 3
A 3

Figure

1. Power efficient routing algorithm is loop-free
In order to provide for loop-free method, we assume that (for this and other mentioned
methods below), in case of ties for the choice of neighbors, if one of choices is the previous node,
the algorithm will select that node (that is, it will stop or flood the mes sage). Note that the above
proof may be applied (by replacing '+' with '*') to an algorithm that will minimize p(A)=u(r)tv(s).
Theorem 3. Localized cost efficient algorithms are loop-free.
Proof. Note that the cost c(A) of sending message from B to A is only the function of A (that
is, t=t(A)), and is independent on B. In the previous proof, assume u(r i )=0 for all nodes, and let
each i. The proof then becomes the same as in the previous theorem. The proof is
valid for both formulas c(A)=f(A)+ts/R and c(A)=f(A)ts/R. Note that the proof assumes that the cost
of each node is not updated (that is, communicated to the neighbors) while the routing algorithm is
in progress. It is possible to show that, on the other hand, if nodes inform their neighbors about new
cost after every transmitted message, a loop (e.g. triangle) can be formed.
Theorem 4. Localized power-cost efficient algorithms are loop-free for the metrics power-
(where a and b are arbitrary constants), and pc(B,A)=
(where t(A) is determined by one of formulas i-iv).
Proof. The proof is again by contradiction, similar to the proof of previous theorems.
Suppose that there exists a loop A 1 , A 2 , . A n in the algorithm (see Fig. 4). Let
be the power-costs of sending message to nodes A 1 , A 2 , . A n , respectively,
from the previous node in the loop. According to the choice of neighbors in Fig. 1 it follows that
since the node A n selects A 1 , not A n-1 , to forward the message. Similarly
summing left
and right sides we obtain
This inequality is equivalent to [au(r
which is a
contradiction since both sides contain the same elements. Thus the algorithm is loop-free. Note that
the proof also assumes that the cost of each node is not updated (that is, communicated to the
neighbors) while the routing algorithm is in progress. Note that this proof does not work for the
formula power-cost(B,A)=f(A)u(r), which does not mean that the corresponding power-cost routing
algorithm is not loop-free.
7. Performance evaluation of power efficient routing algorithm
The experiments are carried using (static) random unit graphs. Each of n nodes is chosen by
selecting its x and y coordinates at random in the interval [0,m). In order to control the average node
degree k (that is, the average number of neighbors), we sort all n(n-1)/2 (potential) edges in the
network by their length, in increasing order. The radius R that corresponds to chosen value of k is
equal to the length of nk/2-th edge in the sorted order. Generated graphs which were disconnected
are ignored. We have fixed the number of nodes to n=100, and average node degree k to 10. We
have selected higher connectivity for our experiments in order to provide for better delivery rates
and hop counts and concentrate our study on power conserving effects.
The choice of route for DIR (compass routing), MFR and GEDIR methods in [SL], and their
mutual comparison, did not depend on the size m of square containing all the points. However, in
case of power consumption, the actual distances greatly impact the behavior of algorithms. More
precisely, the path selection (and the energy for routing) in our power saving algorithm depends on
the actual size of the square. We compared all methods for squares of sizes m=10, 100, 200, 500,
1000, 2000, 5000 for both HCB- and RM-models. The results are averages over 20 graphs with 100
routing pairs in each chosen at random.
In our comparisons, the power consumption (cost, power-cost, respectively) in all compared
methods was measured by assigning the appropriate weights to each edge. Our comparison for the
category of power (only) consumption involved the following GPS based distributed algorithms:
NFP, random progress, MFR, DIR, GEDIR, NC, the proposed localized power efficient routing
algorithm (with t=1), and the benchmark shortest (weighted) path algorithm (SP).
We have introduced a new routing method, called NC (nearest closer), in which node A,
currently holding the message, forwards it to its nearest node among neighboring nodes which are
closer to destination D than A. This method is an alternative to the NFP method which was
experimentally observed to have very low success rate (under 15% in our case). The reason for low
success rate seems to be the existence of many acute triangles ABD (see Fig. 2) so that A and B are
closest to each other, and therefore selected by NFP method which then fails at such nodes.
The proposed power efficient method, which will be referred as power1 method, was also
experimentally shown to have very low success rate for large m. The power efficient algorithm is
therefore modified to increase its success rate. Only neighbors that are closer to destination than the
current node are considered, and this variant will be called the power method. The success rates of
power and power1 methods are almost the same for m200. While the success rate of power
method remains at 95% level, the success rate for power1 drops to 59%, 11%, 4% and 2% only for
remaining sizes of m (numbers refer to HCB-model, and are similar for the other model). Consider
a scenario in which power1 fails (see Fig. 3, where |AD| < |BD| < |CD|). Node A sends message to
closest neighbor B. Since A is very close to B but C is not, power formula applied at B selects A to
send message back, and a loop is created.
A
A

Figure

2. NFP method fails

Figure

3. Power1 frequently fails
We included 2-hop GEDIR, DIR, MFR and NC methods in our experiments. 2-hop NC method
is defined as follows. Each current node C finds the neighboring node A whose 1-hop nearest
(closer to destination D) neighbor B has the shortest distance (between A and B). If no such node
exist (i.e. none of neighboring nodes of C has forward neighbor) then take the neighbor node E
whose backward nearest neighbor F has smallest distance (between E and F).
The delivery rates for 1-GEDIR, 1-DIR, and 1-MFR methods in our experiments were about
97%, 1-NC had 95% success, 2-GEDIR (that is, 2-hop GEDIR) and 2-MFR about 99%, 2-DIR
about 91%, 2-NC and random methods about 98%, and power method 95% success rate (for both
HCB- and RM-models). While all other methods choose the same path independently on m and
power formula applied, power method does not, and almost constant and good delivery rate for it is
a very encouraging result. The hop counts for non-power based methods were 3.8, 4.2, 3.9, 8.0, 3.8,
3.9, 4.1, 5.2, and 6.4, respectively (in above order). Hop counts for power method were 3.8, 3.8,
3.8, 3.8, 6.3, 9.0 and 9.7 for RM-model, and 3.8, 3.8, 4.0, 6.6, 8.3, 9.1, 9.6 for HCB-model, in
respective order of m. Clearly, with increased energy consumption per distance, power method
reacted by choosing closer neighbors, resulting in higher hop counts.
A

Figure

4. GEDIR consumes less power than MFR
Let us show the average case superiority of GEDIR method over MFR method and superiority
of DIR routing over random progress method. Let A and B be the nodes selected by the GEDIR and
MFR methods, respectively, when packet is to be forwarded from node S (see Fig. 4). Suppose that
B is different from A (otherwise the energy consumption at that step is the same). Therefore
|AD|<|BD|. Node B cannot be selected within triangle SAA' where A' is the projection of node A on
direction SD, since B has more progress than A (here we assume, for simplicity, that A and B are on
the same side of line SD). However, the angle SAB is then obtuse, and |SB|>|SA|. From |SB| > |SA|
and |BD| > |AD|, it follows that the packet requires more energy if forwarded to B instead of A.
Suppose now that A and B are selected neighbors in case of DIR and random progress routing
algorithms (we shall use the same Fig. 4). Since the lengths |SA| or |SB| are not considered when
selecting the neighbors, on the average we may assume that |SA|=|SB|. However, the direction of A
is closer to the direction of destination (that is, the angle ASD is smaller than the angle BAD) and
thus A is closer to D than B.
method/size
SP-Power 3577 4356 6772 20256 62972 229455 1404710
Power 3619 4457 6951 21331 69187 261832 1647964
GEDIR 3619 4460 7076 24823 89120 344792 2152891
Random 5962 7099 10626 34382 121002 465574 2896988

Table

1. Power consumption of routing algorithms

Table

shows average power assumption (rounded to nearest integers) per routing tasks that
were successful by all methods, which occurs in about 85% of cases. It is calculated as the ratio of
total power consumption (for each method) for these tasks over the total number of such deliveries.
The quadratic HCB-model formula is used (the results for the RM-model were similar).
The power consumption for GEDIR algorithm is smaller than the one for DIR routing method
for small values of square size m. The reason is that the smaller hop count is decisive when no
retransmission is desirable. However, for larger m, DIR routing performs better, since the greatest
advance is not necessarily best choice, and the closer direction, possibly with smaller advance, is
advantageous. The NC method is inferior to GEDIR or DIR for smaller values of m, because the
greatest possible advance is the better choice for neighbor than the nearest node closer to
destination. However, for larger values of m, NC outperforms significantly both, since it simulates
retransmissions in the best possible way. 2-hop methods failed to produce power savings over
corresponding 1-hop methods, and were eliminated in our further investigations.
As expected, the proposed distributed power efficient routing algorithm outperforms all known
GPS based algorithms for all ranges of m. For small m, it is minor improvement over GEDIR or
DIR algorithms. However, for large m, the difference becomes very significant, since nearest rather
than furthest progress neighbors are preferred. For large m, the only competitor is NC algorithm.
The overhead (percentage of additional energy per routing task) of power efficient algorithm
with respect to optimal SP-power one is 1.2%, 2.3%, 2.6%, 5.3%, 9.9%, 14.1% and 17.3% for the
considered values of m, respectively. Therefore, localized power efficient routing algorithm, when
successful, closely matches the performance of non-localized shortest-power path algorithm. We
have experimented also with different values of parameter t, a trade-off between success rates and
power savings is obtained. Thus the best choice of t remains an issue for further investigation.
8. Performance evaluation of cost and power-cost efficient routing algorithms
The experiments that evaluate cost and power-cost routing algorithms are designed as follows.
Random unit connected graphs are generated as in the previous section. An iteration is a routing
task specified by the random choice of source and destination nodes. A power failure occurs if a
node has insufficient remaining power to send a message according to given method. Iterations are
run until the first power failure at a node occurs (at which point the corresponding method 'dies').
Each node is initially assigned an energy level at random in the interval [minpow, maxpow], where
parameters depend on m. After sending a message from node A to node B, the energy that remained
at A (B) is reduced by the power needed to transmit (receive) the message, respectively. The
experiment is performed on 20 graphs for each method, for each of HCB- and RM-model formulas.
The success rates for unrestricted versions of cost and power-cost algorithms (where all
neighbors were considered) was again low in our experiments. For example, the success rate of
cost-iii method drops from 64% to 55% with increasing m, while power*cost method drops from
77% to 14% (data for other variants are similar; HCB-model is again used, while the other model
had very similar data). Consequently, these methods were deemed not viable. The success rate for
restricted versions (only closer neighbors considered) was in the range 92%-95% for all cost and
power-cost methods discussed here, both models, and all sizes m. The number of iterations before
each method dies, for HCB-model, is given in Table 2 (data refer to restricted versions). RM-
method gave similar results. The cost and power-cost methods are defined in section 5.
method/trial count 10 100 200 500 1000 2000 5000
SP-Power 342 865 1710 983 1114 796 482
SP-Cost 674 1703 3540 1686 1590 1066 646
SP-Power*Cost 674 1697
SPPower+Cost 647 1668 3495 1725 1688 1124 682
Power 379 954 1843 1009 1162 789 469
Power*Cost 662 1609 3118 1513 1528 1056 617
Power+Cost 660 1611 3180 1664 1757 1179 712
Random 201 481 889 546 512 312 202

Table

2. Number of iterations before one of node in each method dies
The intervals [minpow, maxpow] were set as follows: [80K, 90K], [200K, 300K], [500K,
1M], [750K, 1.5M], [3M, 4M], [8M, 10M], [30M, 40M], for given respective sizes of m, where
K=1000 and M=1000000. Our experiments confirmed the expectations on producing power savings
in the network and/or extending nodes lifetime. Both cost methods and all four power-cost methods
gave very close trial numbers, and thus it is not possible to choose the best method based on trial
number alone. However, all proposed localized cost and power-cost methods performed equally
well as the corresponding non-localized shortest path cost and power-cost algorithms (the number
of trials is sometimes even higher, due to occasional delivery failures which save power). It is also
clear that cost and power-cost routing algorithms last longer than the power algorithm.
method/power
SP-Cost 44381 133245 395592 618640 1857188 4819903 19238265
SP-Power*Cost 44437 133591 396031 642748 2067025 5686092 23187052
SPPower+Cost 46338 136490 406887 646583 1972185 5252813 21081420
Power*Cost 27434 126066 416889 712033 2286840 6030614 24419832
Power+Cost 27520 126201 409208 666907 2091211 5658144 22622947

Table

3. Average remaining power level at each node

Table

3 shows the average remaining power at each node after the network dies, for the most
competitive methods. Cost methods have more remaining power only for the smallest size m=10,
when the power formula reduces to the constant function. For larger sizes of m, two better power-
cost formulas leave about 15% more power at nodes than the cost method.
SP-cost, cost-iii and cost-ii methods have hop counts approximately 4.0, 4.5, and 4.9 for HCB-
model and all values of m. Four power-cost methods have similar hop counts, 5.8, 4.7, 5.0, 6.7, 8.4,
9.1 and 9.6, respectively, for sizes of m. Two SP-power-cost methods do not have similar hop
counts. SP-Power*Cost method has hop counts 4.0, 4.1, 4.3, 6.3, 7.8, 8.3, 8.7, while SP-
Power+Cost method has hop counts between 4.0 and 4.6.
Conclusion
This paper described several localized routing algorithms that try to minimize the total energy
per packet and/or lifetime of each node. The proposed routing algorithms are all demand-based and
can be augmented with some of the proactive or reactive methods reported in literature, to produce
the actual protocol. These methods use control messages to update positions of all nodes to
maintain efficiency of routing algorithms. However, these control messages also consume power,
and the best trade-off for moving nodes is to be established. Therefore further research is needed to
select the best protocols. Our primary interest in this paper was to examine power consumption in
case of static networks and provide basis for further study. Our method was tested only on
networks with high connectivity, and their performance on lower degree networks remains to be
investigated. Based on experience with basic methods like GEDIR [SL], improvements in the
power routing scheme to increase delivery rates, or even to guaranty delivery [BMSU, SD] are
necessary before experiments with moving nodes are justified. Power efficient methods tend to
select well positioned neighboring nodes in forwarding the message, while cost efficient method
favor nodes with more remaining power. The node movement, in this respect, will certainly assist
power aspect of the formula since the movement will cause the change in relative node positioning.
This will further emphasize the advantage of power-cost over power only or cost only methods.
The formulas for power, cost, and power-cost methods may also need some improvements. Our
experiments do not give an ultimate answer on even the selection of approach that would give the
most prolonged life to each node in the network. We will investigate this question further in our
future work [SD] which will consider a number of metrics including generalized one f(A) a u(r) b ,
which is similar to one proposed in [CT2].



--R

A distance routing effect algorithm for mobility (DREAM)
A performance comparison of multi-hop wireless ad hoc network routing protocols
Routing with guaranteed delivery in ad hoc wireless networks

Distributed quality-of-service routing in ad hoc networks
Routing for maximum system lifetime in wireless ad-hoc networks
Energy conserving routing in wireless ad-hoc networks
System capacity
Scalable coordination in sensor networks
Routing and addressing problems in large metropolitan-scale internetworks

Adaptive protocols for information dissemination in wireless sensor networks
Transmission range control in multihop packet radio networks
http://www.
Mobile networking for 'smart dust'
Compass routing on geometric networks

QoS routing in ad hoc wireless networks
Mobile ad hoc networking and the IETF
Tha spatial capacity of a slotted ALOHA multihop packet radio network with capture
Minimum energy mobile wireless networks
A survey of routing techniques for mobile communication networks
A review of current routing protocols for ad hoc mobile wireless networks


Location updates for efficient routing in wireless networks
Power aware routing algorithms with guaranteed delivery in wireless networks.
GEDIR: Loop-free location based routing in wireless networks

Power aware distributed routing in ad hoc wireless networks
A routing strategy and quorum based location update scheme for ad hoc wireless networks
Optimal transmission ranges for randomly distributed packet radio terminals
--TR

--CTR
Hseyin zgr Tan , Ibrahim Krpeolu, Power efficient data gathering and aggregation in wireless sensor networks, ACM SIGMOD Record, v.32 n.4, December
Rabi N. Mahapatra , Wei Zhao, An Energy-Efficient Slack Distribution Technique for Multimode Distributed Real-Time Embedded Systems, IEEE Transactions on Parallel and Distributed Systems, v.16 n.7, p.650-662, July 2005
S. Jayashree , B. S. Manoj , C. Siva Ram Murthy, On using battery state for medium access control in ad hoc wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA
Seungjoon Lee , Bobby Bhattacharjee , Suman Banerjee, Efficient geographic routing in multihop wireless networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
Israat Tanzeena Haque , Chadi Assi , J. William Atwood, Randomized energy aware routing algorithms in mobile ad hoc networks, Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 10-13, 2005, Montral, Quebec, Canada
Long Gan , Jiming Liu , Xiaolong Jin, Agent-Based, Energy Efficient Routing in Sensor Networks, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.472-479, July 19-23, 2004, New York, New York
Xiang-Yang Li , Kousha Moaveninejad , Ophir Frieder, Regional gossip routing for wireless ad hoc networks, Mobile Networks and Applications, v.10 n.1-2, p.61-77, February 2005
Susanta Datta , Ivan Stojmenovic , Jie Wu, Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks, Cluster Computing, v.5 n.2, p.169-178, April 2002
Yu-Chee Tseng , Ting-Yu Lin, Power-conservative designs in ad hoc wireless networks, The handbook of ad hoc wireless networks, CRC Press, Inc., Boca Raton, FL,
Qun Li , Daniela Rus, Communication in disconnected ad hoc networks using message relay, Journal of Parallel and Distributed Computing, v.63 n.1, p.75-86, January
Himanshu Raj , Karsten Schwan , Ripal Nathuji, M-ECho: a middleware for morphable data-streaming in pervasive systems, Proceedings of the 2005 workshop on End-to-end, sense-and-respond systems, applications and services, June 05-05, 2005, Seattle, Washington
Johnson Kuruvila , Amiya Nayak , Ivan Stojmenovic, Greedy localized routing for maximizing probability of delivery in wireless ad hoc networks with a realistic physical layer, Journal of Parallel and Distributed Computing, v.66 n.4, p.499-506, April 2006
David Kiyoshi Goldenberg , Jie Lin , A. Stephen Morse , Brad E. Rosen , Y. Richard Yang, Towards mobility as a network control primitive, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
Chao Gui , Prasant Mohapatra, SHORT: self-healing and optimizing routing techniques for mobile ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA
Hannes Frey , Ivan Stojmenovic, On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA
Joongseok Park , Sartaj Sahni, Maximum Lifetime Broadcasting in Wireless Networks, IEEE Transactions on Computers, v.54 n.9, p.1081-1090, September 2005
Silvia Giordano , Ivan Stojmenovic, Position-based ad hoc routes in ad hoc networks, The handbook of ad hoc wireless networks, CRC Press, Inc., Boca Raton, FL,
Yuan Xue , Yi Cui , Klara Nahrstedt, Maximizing lifetime for data aggregation in wireless sensor networks, Mobile Networks and Applications, v.10 n.6, p.853-864, December 2005
Xu Lin , Ivan Stojmenovic, Location-based localized alternate, disjoint and multi-path routing algorithms for wireless networks, Journal of Parallel and Distributed Computing, v.63 n.1, p.22-32, January
Hee Yong Youn , Chansu Yu , Ben Lee, Routing algorithms for balanced energy consumption in ad hoc networks, The handbook of ad hoc wireless networks, CRC Press, Inc., Boca Raton, FL,
Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002
Y. Thomas Hou , Yi Shi , Hanif D. Sherali, On node lifetime problem for energy-constrained wireless sensor networks, Mobile Networks and Applications, v.10 n.6, p.865-878, December 2005
Chao Gui , Prasant Mohapatra, A framework for self-healing and optimizing routing techniques for mobile ad hoc networks, Wireless Networks, v.14 n.1, p.29-46, January 2008
Jae-Hwan Chang , Leandros Tassiulas, Maximum lifetime routing in wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.609-619, August 2004
Marcel Busse , Thomas Haenselmann , Wolfgang Effelsberg, A comparison of lifetime-efficient forwarding strategies for wireless sensor networks, Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks, October 06-06, 2006, Terromolinos, Spain
I. Kadayif , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, An integer linear programming-based tool for wireless sensor networks, Journal of Parallel and Distributed Computing, v.65 n.3, p.247-260, March 2005
Shibo Wu , K. Seluk Candan, Power-aware single- and multipath geographic routing in sensor networks, Ad Hoc Networks, v.5 n.7, p.974-997, September, 2007
routing;power management;wireless networks;distributed algorithms