Power-Aware Routing in Mobile Ad Hoc Networks

Suesh Singh and Mke Woo C. S. Mghavendra

Department of ECE Aerospace Corporation
Oregon State University El SeWndo, CA 90245
CorvaUs, OR 97331 em ail: raghu@aero. org
woo,singh@ece. orst. edu

Abstract stance, low-power displays (see [13]), algorithms to reduce

power consumption of disk &Ives (see [9, 19, 34]), low-power
b this paper we present a case for using new power-aware 1/0 devicw such = cameras (see [5]), etc. dl contribute
metn.cs for determining routes in wireless ad hoc networks. to overall energy savings. Other related work includes the
We present five ~erent metriw based on battery power development of low-power CPUS (such as those used in lap
consumption at nodw. We show that using th=e metrics tops) and high-capacity batteriw.
in a shortest-cost routing algorithm reduces the cost/packet Our focus, in the past year, has been on developing
of routing packets by 5-30% over shortwt-hop routing (this strategia for reducing the energy consumption of the com-
cost reduction is on top of a 40-70% reduction in energy con- munication subsystem and increasing the life of the nodes.
sumption obtained by using PAMAS, our MAC layer pr- Recent studies have strwsed the need for designing prot~
tocol). Furthermore, using these new metrics ensures that cok to ensure longer battery Me. Thus, [21] observes that
the mean time to node failure is increased si~cantly. An the average He of batteries in an idle ceUtiar phone is one
interesting property of using shortest-cost routing is that day. [32] studi= power consumption of several cornrnercid
packet delays do not increase. Fintiy, we note that our new radios (WaveLAN, Metricom and ~) and observw that even
metrim can be used in most tradition routing protocols for in Sleep mode the power consumption ranged between 150-
ad hoc networks. 170 mW whale in Ide state the power consumption went
up by one order of magnitude. k transmit mode the power
1 Introduction consumption typically doubled. The DEC Roarnabout radio
[1] consumes approximately 5.76 watts during transtilon,
Ad Hoc networks are multi-hop wireless networks where dl 2.8S watts during reception and 0.35 watts when ide.
nodes cooperatively maintain network connectivity. These H we examine the existing MAC protocok and routing
types of networks are useftd in any situation where tem- protocok in th= context we see a clear need for improve
porary network connectivity is needed, such as in disaster ment: in all of the current protowk, nodes are powered on
retief. An ad hoc network here wodd enable medim in the most of the time even when they are doing no useful work.
field to retrieve patient history horn hospital databasm (as- At the MAC layer, nodes expend scarce energy when they
suming that one or more of the nodes of the ad hoc network overhear transmissions. b Figure 1, node A’s trans-lon
are connected to the kternet) or Wow insurance companies to node B is overheard by node C because C is a neighbor of
to tie claims horn the field. A. Node C thus expends energy in receiving a packet that
Building such ad hoc networks poses a significant tech- was not sent to it. b this case, clearly, node C needs to be
nical chdenge because of the many constraints imposed by powered off for the duration of the transmission in order to
the environment. Thus, the devicw used in the field must conserve its energy. Our MAC layer protocol (summarized
be lightweight. Furthermore, since they are battery oper- in section 4) does precisely this and saves large amounts of
ated, they need to be energy conserving so that battery fife energy. Routing protocok designed for ad hoc networks are
is maximized. Several technologies are being developed to dso guilty of expending energy needessly. k most of three
achieve these go~ by tmgeting specific components of the protocols the paths are computed based on m~lzing hop
computer and optimizing their energy consumption. For in- count or delay. Thus, some nodes, become responsible for
routing packets from many sourc-dmtination pairs. Over
time, the energy reserv= of th=e nod= wi~ get depleted
Pemtissionto makedi~tal or hard copies of all or part oftbis \vork for rwulting in node failure. A better &oice of routes is one
pemorralor classroom use is @nted without fee provided that copies where packets get routed through paths that may be longer
are nt)t made or distributed for protit or commercial advantage and that
but that pass through nodes that have plenty of ener~ r~
copies bear this notice and the fill citation on the first page. To copy
serves.
othen~ise, to republish, to post on sen’ers or to redistribute to lists,
Our research has focussed on designing protocok that
requires prior specific permission and~ora fee.
increase the Efe of nodes and the network. k order to pr-
MOBICOki 9S Dallas Texas USA
duce a complete solution, we have attacked each layer (MAC,
CopyrightACM 19981-581 13435-f198/10...$00OO

181

~y . - . —. ..—
 A transtits A’s transmission of these protocok, however, can just ~ easily use shortest
toB , is overheard by C delay as the metric. Link quality is a metric that is used by
SSA (Signal Stabifity based Adaptive Routing [8]) and by
I I the DARPA protocol. Here, link qutity information is used
B A c
#--------+ . ... .. .. ... . ... .. ... to select one among many ~erent routes (in some cases
a a short-t-hop route may not be used because of poor link
qudty). k addition to link quality, SSA *O us= iocation
Figure 1: Unnecessary power consumption, stability as a metric. This metric biasw route selection tm
ward routes with relatively stationary nods. A benefit of
these type of rout= is that there ~ be httle need to modify
network and transport) individudly. b our bottom-up ap- them frequently. Finally, the SRA protocol (Spine Routing
proach, we optimize the energy consumption of the MAC Algorithm [7]) attempts to mitilze the m~age and time
layer fist fo~owed by the network layer and fmdly the trans- overhead of computing routes. h this protocol, nodes me
port layer. h [24] we present a MAC layer protocol for ad assigned to clusters (one or tw~hops in diameter) and clus-
hoc networks that reduca energy consumption by 40% to ters are joined together by a virtual backbone. Packets des-
70% for different load and network conditions. An overview tined for other clusters get routed via this backbone. The
of this work is provided in section 4. In this paper, we god here is to reduce the complexity of maintaining routes
e~lore the issue of increasing node and network fife in the face of node mobfity. Of course, the routes are not
by using power-aware metrics for routing. htuitively, necessarily the shortest.
it is best to route packets through nodw that have sufficient The stilent features of these protocols is summarized in
remaining power (rather than through a node whose bat- Table 1. h th= table, we have classfied the protocols ac-
tery is on its last legs). Sim~aly, routing packets through cording to the metrics used for route optimization, the mw-
Eghtly-loaded nod= is *O ener~-conserving because the sage overhead in determiningg routes, the type of protocol
energy ~ended in contention is miniied. We show that used and its convergence go~ (active refers to a protocol
power-aware routing (built on top of a power-aware MAC that runs untfl dl routing tables are consistent while passive
protocol) can save overall energy consumption in the net- refers to an algorithm that determinw rout= based on a
work and, sirmdtaneously, increase battery Me at dl nodes. *needed basis).
Our work on optimtilng transport layer protocok W be
pr=ented in an upcoming paper. 2.1 Discussion of the power-awareness of current metrics
The remainder of this paper is organized as follows. k
Some of thwe metrics, unfortunately, have a negative impact
the n- section we discuss the problem of routing in mdti-
on node and network We by inadvertently overusing the en-
hop wireless networks and provide a survey of metri~ used
ergy resourcm of a smd set of nodes in favor of others. For
by current routing protocok. b section 3 we discuss dif-
instance in the network illustrated in Figure 2, shortest-hop
ferent mettics that restit in power-aware routing. Section
routing wi~ route packets between &3, 14 and 2-5 via node
4 outlines our energy conserving MAC layer protocol for
6, causing node 6 to die relatively early. Stillarly, hierarchi-
multi-hop wirel=s networks. We dso present related re
cal and spine routing algorithms d (by their very design)
suits on reducing energy consumption in ce~tiar and wire
~loit nodes that he on the spine in order to reduce mes-
less LAN environments by caretily daigning the MAC pr~
sage overhead in routing table maintenance. b fact, it is
tocol. Section 5 praents the resdts of our simulations where
important to observe that the metric of reducing message
we demonstrate the use of new power-aware metrim. Fi-
overhead may be mis@ded in the long-term. If we assume
nally, section 6 summarizes the main results and outlinw
that 5-10% of network bandwidth is consumed by routing
our future research.
protocol overhead then reducing this number further will
have Ettle overall benefit if the data packets (that account
2 Metrics used in current Routing Protocols for 90-95% of the bandwidth) either use suboptimd routes
or over~end the energy resourc~ of a small set of nodw (on
The problem of routing in mobfie ad hoc networks is dif- the spine, for instance). h fact, we can probably rephrase
ficult because of node mobifity. Thus, we encounter two a version of Amdti’s Law (see pp. 29, [14]) for routing:
coticting go~ on the one hand, in order to optimize
routes, frequent topology updates are required, w~e on the Mintize the cost for the frequent case (data
other hand, frequent topology updates result in higher mes- packets) over the infrequent case (control packets).
sage overhead. Several authors have presented routing dg~
rithms for these networks that attempt to optimize routes Finrdly, we note that in most cases, fink quality and location
while attempting to keep masage overhead smd. k th~ stability are orthogonal to the god of power-awareness and
section we breMy discuss the ~erent metn.cs used for rout- therefore can be used in conjunction with the new metrics
ing and then =arnine their effect on node and network life. we dehe in the neti section.
DMerent routing protocols use one or more of a small
set of metrics to determine optimal paths. The most com- 3 Metrics for Power-Aware Routing
mon metric used is shortest-hop routing ~ in DSR (Dy-
namic Source Routing [15]), DSDV (D=tination Sequenced Our key intuition in this paper is that conserving power and
Distance Vector [26]), TORA (Temporally-Ordered Routing carefully sharing the cost of routing packets will ensure that
Algorithm [25]), WRP (Wireless Routing Protocol [22]) and node and network fife =e increased. However, we saw in
in the DARPA packet radio protocol (see [16, 18]). Some the previous section that none of the metrics currently used

182

-—- .—
--- ,(------ .,- . . . . . . ——— . ---
 Protocol Metrics Message Convergence Protocol me Summary
Overhead
DSR Shortwt Path High Passive Source Routing Route discovery, Snooping
DSDV Shortest Path High Active Distance Vector Routing table exchange
DARPA Shortest Path, High Active Distance Vector Routing table exchange,
Link Quality Snooping
WRP Shortest Path High Active Distance Vector Routing table exchanges
SSA Location Stability, Moderate P=ive Source Routing Route Discovery
Link Qufilty
TORA Shortwt Path Moderate Passive Link Reversal Route update packets
SRA Message and Time Moderate Active Hierartilcd, Spine Route discovery within
overhead cluster, Spine routing

Table 1: Comparison of several routing protocok for ad hoc networks.

for routing achieve this god (in section 5 we support this does not re~y meet our god of increasing node and
claim via simtiations). h this section, therefore, we praent network ~ie.
several power-aware metriw that do r~dt in energy-efficient
routes. o 1

1. Minimize Energy wnsumed/packet: This is one of the

most obvious metriw that reflects our intuition about
conserving energy. Assume that some packet j tra-
6
vers= nodes nl, . . . , nk where nl is the source and nk 5 2
the dwtination. Let T(a, b) denote the energy con- m
sumed in transmitting (and receiving) one packet over
one hop from u to b. Then the energy consumed for
packet j is,
k-1
—
4 3
ej = ~T(ni,ni+l)
i= 1 Figure 2: A network Hlustrating the problem with En-
ergy/packet as a metric.
Thus, the god of this metric is to,

Minimize ej, V packets j (1) 2. Mazimize Time to Network Patiition: This metric is
very important in Wlon critical applications such
Discwsion: It is easy to see that thw metric will mini- as battlwite networks. Unfortunately, optimizing this
mize the average energy consumed per packet. k fact metric is very difficult if we need to sirntitaneously
it is interwting to observe that, under fight loads, the maintain low delay and high throughput.
routes selected when using this metric will be identi-
Discussion: Given a network topology, using the max-
cd to routes selected by shortmt-hop routing! This is
flow-min-cut theorem, we can fid a minimal set of
not a surprising observation because, if we assume that
nodes (the cut-set) the remod of which wi~ cause
T(a, b) = T (a constant) , V(a, b) c E, where E is the
the network to partition. The routes between these
set of dl edgw, then the power consumed is (k – l)T.
two partitions must go through one of thtie critical
To minimize this due, we simply need to minimize k
nodes. A routing procedure therefore must divide the
which is equitient to &ding the shortest-hop path.
work among three nodw to maximize the Me of the
k some c=es, however, the route selected when us- network. ThB problem is similar to the ‘load bakmc-
ing th~ metric may ~er from the route selected by in# problem where t~ks need to be sent to one of
shortest-hop routing. Thus, if one or more nodes on the many servers available so that the response time
the shortmt-hop path are heavfly loaded, the amount is minimized - this is known to be an ~-complete
of energy expended in transmitting one packet over problem. If we don’t ensure that three nodes drain
one hop til not be a constant since we may expend their power at equal rate, we wi~ see delays increase
variable amounts of energy (per hop) on contention. as soon as one of thwe nod= die. Achieving equal
Thus, th~ metric will tend to route packets around power drain rate among these nodes require careful
congested are= (possibly increasing hop-count). routing and is similw to the load balancing problem
One serious drawback of th~ metric is that nod= will d=cribed above. In our case, since nodes in Merent
tend to have widely Mering energy consumption pr~ partitions independently determine rout= we cannot
fles resulting in early death for some nodw. Consider achieve the global brdance required to maximize the
the network illustrated in Figure 2. Here, node 6 will network partition time while minirniiing the average
be selected as the route for packets going from O-3, 1- delay. We can ~so see that because the power con-
4 and 2-5. As a rmult node 6 will expend its battery sumption is dependent on the length of the packet we
resources at a faster rate than the other nodes in the cannot decide optimal routes without the knowledge
network and will be the tist to die. Thus, th~ metric of future arrids (similar to the knowledge of execut-

183
 ing times of t~ks in distributed systems). If W the paths selected when using these metriw shotid be such
packets are of same length, then we can ensure equal that nod= with depleted energy rwerves do not lie on
power drain rate among the critical nodes by selecting many paths. Let ji (zi) be a function that denotes the
these nod= in a round-robin fashion in routing packets node wst or weight of node i. xi represents the totrd
horn one side to the other. energy expended by node i thus far. We dehe the
total cost of sending a packet along some path as the
3. Minimize Vatiance in node power levels: The intuition sum of the node weights of dl nodes that he along that
behind th~ metric is that dl nodes in the network are path. The cost of sending a pa&et j from nl to nk via
equ~y important and no one node must be penfllzed intermediate nod= n2, ..., n~-1 is,
more than any of the others. This metric ensures that
k-1
d the nod= in the network remain up and running
together for as long as possible. .j = ~ fi($i)

i=l
Discussion: This problem is stillar to “load sharin~
in distributed systems where the objective is to min- The god of this metric is to,
imize response time w~e keeping the amount of un-
tihed work in A nod= the same. Atileving th~ Minimize Cj, V packets j (2)
optimrdly is known to be intractable due to unknown
execution times of fiture arri-. Even if we are given Discussion: ktuitively, fi denotes a node‘S reluctance
a set of N tasks with variable Ien@hs to be allocated to foward packets and we can see that with au ap-
to 3 or more machines, thu problem is NP-complete as propriately chosen fi, we can tileve ditferent go*.
it is equident to the bin packing problem. A scheme Thus, if fi is a monotone increasing function, then
that can be used to achieve the stated god reasonably nodes (such as node 6 in Figure 2) d not be overused
well is a poficy cded Join the Shortwt Queue (JSQ). thus increasing their fife. However, it is fikely that the
We can adopt such an idea by using a routing proc~ delay and the energy consumed/packet may be greater
dure where each node sends trtic through a neighbor for some packets, such as those from &3, 14 and 2-5
with the least amount of data waiting to be trans- that use 3-hop routes. This is not necessarily a draw-
mitted. We can improve this further by doing some back since the fife of node 6 (in Figure 2) is incre~ed
Iookups of waiting trfic few hops away to decide the and the variation in the fifetirne of different nodes is
next best hop. An approxirnat e routing procedure can reduced.
be developed which us= the next hop b~ed on total fi can dso be tailored to accurately reflect a battery’s
waiting trtic among its immediate neighbors when it remtilng hfetime. Many batteries display a discharge
has a choice. H dl packets are of same length, how- curve ~ie the one tiustrated in Figure 3 (see [12]).
ever, then we can achieve th~ equal power drain rate Here, we plot the normalized consumed capacity on
by choosing next hop in a round-robin fashion so that the x-axis and the measured voltage on the y-axis. So,
on the average dl nodes process equal number of pack- if the voltage is 2.8V, the battery is dead since dl of its
ets. capacity (1 in normtized units) has been consumed.
When the voltage is 3.6V, for example, 80% of the
capacity has been consumed. One intermting choice
for fi is,
.
fi(Zi) = ‘
1 – g(Zi)
where zi denotes the measured voltage (that gives a
good indication of the energy used thus far) and O <
g(zi) < 1.0 is the normtilzed remaining ~ietime (or
capacity) of the battery ((g(zi), zi) represents a point
on the discharge curve). Using this type of a function
ensures that the cost of forwarding packets is tied in
closely with the power resources deployed in the net-
work. Note that it is trivial to determine fi (Zi) since
zi can be read directly from the battery and the dis-
3 -
&arge curve is available for the batteryl.
\ An alternative form of fi for this =arnple (see Figure
Ot 02 03 04 05 00 07 08 09 1 11
3), however, is,
*-*W (mdQ@

fi(zi) = +
Figure 3: Example of a battery discharge function (Lithium-
Ion). lWe must add a word of caution though – in the case of older
batteries, there is a significant error in determining the remaining
lifetime from the voltage. This happens because of chemical degra-
4. Minimize Cost/Packet: H our god is to maximize the dation in the battery. One solution, for our purposes, would be to
~ie of dl nodes in the network, then metrics other recompute the discharge curve as the battery ages or make amilable
the discharge curves in some databxe that can be accessed by users
than ener~ consumed/packet need to be used. The
bxed on their battery type, model and age.

184
 th~ function has a reasonable node cost for about 80% used. However, after some time when energy resourcw have
of the battery’s Metime (the voltage drops from 4V fden below a thrwhold, nodes can begin using one of the
to 3.6V) but after that point the cost grows rapidly. above routing metri~. Another related point is that routing
btuitively, this form of ~i ensures that shortwt-hop protocok might use these metrics for routing most packets
routing W be used when the network is new but M but switch to shortest-hop (or delay) routing for a fraction
the network nod= near the end of their Metimes, we of the ptiets that have a high priority.
carefully route packets so that no one node (or set of
nodes) di= before the others (which can resdt in a 4 OveNiew of PAMAS (Power-Aware Multiple Access pro-
partition). towl with Signaling)
Findy, we note that the discharge curve for some d-
Hie batteries is ahnost linear and we can =ociate h thissection we provide an overview of our MAC layer
a hear node cost bction, such X, protocol for ad hoc networks. We use this protocol m the
MAC protocol in our simtiator as we~. Thus, the en-
~;(Z~) = cZi (3) ergy savings reported in section 5 are savings that
are obtained on top of the considerable savings due
with each node. to PAMAS. The PAMAS protocol sava 4070% of battery
We can summarize some of the benefits of this metric power by inte~gently turning off radios when they cannot
transmit or cannot receive packets. Thus, in the scenario
~ustrated in Figure 1, node C powers itsek off for the dura-
It is possible to incorporate the battery charac- tion of the transtilon horn A to B. Node C @l thus con-
teristi~ directly into the routing protocol, serve its battery power because it ~ not ~end energy in
As a side&ect, we increase time to network par- ~itening to A’s transmission. The specific conditions under
tition and reduce variation in node costs (though with nodes power off in PAMAS are:
we do not optimize thse metriw), and
● A node powers off if it is overhe~ing a transtilon
Effects of network congestion =e incorporated into and do= not have a packet to transmit,
this metric (as au in;rease in node ;ost due to
contention). ● If at least one neighbor is trmmitting and at least one
neighbor is receiving a transtilon, anode may power
5. Minimize M&mum Node Cost: Let Ci(t) denote the off. ThK is because, even if the node has a packet to
cost of routing a packet through node i a~ time t.De transmit, it cannot do so for fear of interfering with its
fine d(t)denote the mtium of the Ci (t)s. Then, neighbor’s reception,

Minimize ~(t), Vt >0 (4) ● If dl of a node’s neighbors neighbors are transmitting

(and the node is not a receiver), it powers itself off.
metric minimizes mtimum node cost. An alternative
definition is to rni~lze the maximum node cost aj- A fundamental problem that arism when nod= power
ter routing N packets to their destinations or afler T themselves off is, for how long an a node remain powered
sewnds. Afl of these variations ensure that node fail- OH k the optimal case, a node powers itse~ off exactly
ure is delayed and a side effect is that the variance in when one of the conditions above holds true. However, in
node power Ievek is *O reduced. Unfortunately, we actual implementation, a node needs to estimate th~ len~h
see no way of implementing this metric directly in a of time (keep in mind that a node cannot sense carrier when
routing protocol but minimizing cost/node does sig- it is powered off so it has no way of knowing when a tr--
nificantly reduce the m~um node cost (and hence mission in its neighborhood h= completed). k our prot-
time to fist node failure). COI,= in dl other MAC layer protocols for ad hoc networks,
nodes attempt to grab the channel by mchanging RTS/CTS
The five metrics discussed above do, in Merent ways, ex- (ready to send and clear to send) mwsages. Thus, the sender
press our intuition about conserving energy in the network transmits a RTS mwsage. The receiver rwponds with a CTS
by selecting routes caretily. However, what protocols best message if it received the RTS message uncorrupted. The
implement thwe metrim? It is easy to see that any protocol sender begins transmission upon receiving the CTS. b PA-
that fids shortest paths can be used to determine optimal MAS, this exchange of RTS/CTS mwsagw takes place over
routes b~ed on the fist and fourth metrics discussed above a separate signdhng channe12. Thus, this exchange does
(equations 1, 2). To implement the fist metric, we sim- not tiect any ongoing data transmi~ions. The RTS/CTS
ply wsociate an edge weight with each edge in the network. m~sages cent tin the length of the packet the sender wi~
This weight reflects the Aue T(a, b). For the second met- send. Thus, any other node in the neighborhood can deter-
ric (cost/packet), we associate node weights fi with each mine the length of the transmission and power off if one of
node and compute the shortest path as usual. We have not the above conditions is met. A problem =ises in the case
yet implemented the other three metriw but we have de when a node that has powered itself off wakens to hear a
termined that they are optimized somewhat by the metric new ongoing transmission. In this case, it needs to be able
(cost/packet) if we select ji’s carefully. to =timate the length of the remainiig transmission and
Finally, it is important to point out that our metrics
21n PAMAS the receiver transmits a busy tone once it begins hear-
do not necessarily need to be used for routing dl the time.
ing the packet. This is done to combat a specific hidden-terminal
Rather, when the network is new (when dl nodes are r~ problem.
plet e with energy resources), short=t-hop routing can be

185

~--- ‘. >,. . . . . ..-. . a.~ --- .,, - ,,- s ., -,.......

—.- . .——
power itseK off (if one of the conditions above is met) again. inter~ and the base station transmits a TIM (~tic b-
We have a protocol that runs over the signdhng chanel dication Map) that includes the transmission schedule for
that allows nodes to query transmitters about the length of the nodes. All nodes not participating in transmission or
the remaining transmission. Co~iions during this enquiry reception of packets go into doze mode untfl the next rwer-
(which are ~iely in high-degree networks since several nodes vation period. The standard dso indudw an extension of
may power off as a consequence of a transmission and may this idea to ad hoc singlehop networks. Here, nod= com-
waken simdtaneously) are handed with a modified binary pete to be elected the leader to play the role of the b~e
backoff algorithm. This dgorithrn can be tuned so that over- station. [30] presents a comparison of the power consump-
head of the algorithm is traded off against accuracy in the tion behavior of three protocok - EEE 802.11, DQRUMA
estimate of the length of the remaining transmission. (see [20]) and DSA++ (see [27]) -in a singl~hop environ-
Figure 4 Ulustrat= the power savings obtained (as a per- ment. Their main conclusions are that contention results in
centage) when using PAMAS. The network used is a 20-node higher energy consumption while reservation and schedd-
random network. The x-axis denotes the edge probability. ing results in lower energy consumption. [6] &o discusses
Different curves indicate power savings for Werent network the energy consumption of protocok and shows that persis-
loads. Note that at high loads the power savings are smaller tence is not always a good choice and adaptive strategies
because a large amount of power is consumed in contention. that avoid packet retransmission during bad dannel p~
The savings, however, increase with increasing node con- riods is a good energy conserving strategy. Furthermore,
nectivity since a node has more opportuiniti~ to power-off. [6] presents a access protocol for ce~tiar networks based on
The PAkfAS protocol is non-trivial and we cannot explain ALOHA and reservation (the protocol is similar to EEE
its operation in any detti here. However we would We to 802.11) and analyze its performance (energy consumed and
point out that in PAMAS the delay and throughput are not throughput). [31] *O presents a reservation-based power
changed even when nodes power off. This is because the conserving accws protocol for mobile ATM networks.
conditions under which nodes power off are such that the
node powering off cannot transmit or receive packets any- 5 Validation of the Power-Aware Metrim
way. A detailed discussion of PAMAS is provided in [23].
We have derived bounds on the maximum achievable power We conducted extensive simdations to better understand
savings in [24]. the properties of the new metri~ and the tiect of using these
metrim on end-t~end packet delay. Specifictiy, we com-
pared the performance of shortest-hop routing with shotiest-
cost routing (equation 2) and quantified the Merence be
tween three two approachw using three measur~3:

1. End-t~end packet delays (measured as the difference

between tbe when a packet enters the system and
time when it fidly dep~s),

2. Average cost/packet (measured for each packet), and

3. Average mtium node cost (computed after 300 sec-

onds of simulation time)
For the shortest-cost routing approach, we used several dif-
ferent ~i functions. In this paper, however, we only present
two of these models for ~i. The fist model was a linear
model where ~(z) = m for some constant c < 1 and the
of 1 second model was a quadratic model where ~(z) = az. The
0 Ot 02 03 06 07 08 0.9 hnem model is based on the discharge curve of dtiine bat-
:; AS*
teries while the quadratic model represents the precipitous
Figure 4 Power saved in random networks with 20 nod=. discharge in battery life for fithium-ion batteries (Figure 3).
For the simulation, we used a 16-node mesh topolog and
10 and 20-node random graphs. The random graphs were
generated as follows. For each pair of possible edges, we toss
4.1 Related Work on Power-Consewing MAC Protocols a coin that has a probability p of coming up heads. If it does
Recently, some researchers have begun studying the problem come up heads, we put that edge in otherwise we leave it
of reducing power consumption by the wireless interface in out. We varied the due of p from 0.1 to 0.5. ktuitively,
singl~hop wireless networks. Most approaches are based P = 0.1 produces a sparse graph w~e p = 0.5 producw a
on the paging protocols POCSAG and FLEX where a base dense graph. We only considered connected networks in this
station periodically transmits a beacon followed by a min- study and we did not include node mobihty. The reason we
islot containing the ~ of nodes that have a page waiting did not account for mobility is because we were not actudy
for them. Th~e nod= remain awake in order to receive simulating a routing protocol (whose perfowance would d-
their mwsagw while dl the others power thernselv~ off. A penal on the mobility model) but only eduating Merent
similar idea (based on r=ervation) is included in the IEEE power-aware metrics.
802.11 standard as well (see [29]). Here, nodes transmit 3}Ve did not consider hierarchical spine routing because of our
their requ=ts to the base station during specific reservation criticism in section 2

186
 Packets arrive at each node according to a poisson pr~ The reason for th~ is that dl nodes have a Ml btier and
cess. The packet arriti rate A varies between 0.05 and 0.5 expend huge amounts of energy in contention which r=dts
packets/see/node. Each node maintains a FIFO btier of in reducing the node cost ~erentid. Fmdy, we observe
packets that need to be forwarded to the next hop. Every that the savings in cost incrwses with dge probability p.
packet is timestamped when it fist enters the system and The reason for this is that at sm~ p, the network is sparse
then again when it arrives at its datination allowing us to restiting in few alternative routing paths w~e at higher p,
compute delays. Further, node costs are updated constantly more paths become atiable. The cost function ~ *O af-
and when a packet is transmitted over one hop, we add the fects the savings in cost. As the graphs show, savings are
current node cost to the total cost of the packet. The packet greater for the quadratic cost function than for the hear.
costs are averaged out at the end of the simulation as are This is because the cost Werentid between nod= increases
the node costs. sharply with a quadratic function.
We ran each simulation 20 tbes and computed the mean We plot the reduction in maximum node costs for 10-
and the standard deviation for each of the three metriw node and 20-node random networks in F)gurw 7 and 8. h
mentioned e=her (delay, cost/packet and average m= node the 10-node network, there is a 5-10% reduction in maximum
cost) for shortest-hop routing and shortest-cost routing. b node cost for the hear case and 5-50% for the quadratic
the graphs we plot the percentage improvement in thse met- case. Three numbers become 5-45% for the Enear case and
riw when we use shortwt-cost routing. We have not plotted 15-120% for the quadratic case when we have a 20-node net-
the curvw for delay because there was no difference in the work. The reasons for this dramatic increase in savings in
average packet delay (computed separately for packets trav- Imger networks is because of the a@abfity of more routw.
efing over one hop, two hops, etc.) between shortest-hop L&ewise, the savings increwe in denser networks and they
routing and short=t-cost routing. ThB resdt was surpris- increase (tiltidly) with A. Ml for the sme reasons as dis-
ing because we had expected a sfight worsening in delay cussed previously.
for packets (in the shortest-cost case) as they get routed Figure 9 illnstratw the cost savings per pdet and the r~
around nodw with high cost (or low remainiig Metime). duction in maximum node cost for a l~node mwh. We used
On closer examination of the sirntiation trace we found that the mesh because it providw with a we~-connected topolo~
some packets did indeed take longer routes and of thae some and tiows us to verify our conclusions from the random net-
did have higher delay (measured in time steps). However, work topologies. As we can see, as the load increasm (along
the number of three packets was not large and as a r=dt the x-*), the savings in cost per packet increue at fist
did not contribute to a statisticdy si@cant resdt. What and then decreasm as load continues to increase. The rea-
was more significant, under high loads, was the fact that son for the initial increase is that at very low loads, node
shortest-hop routing resulted in stightly longer packet delays costs are almost the same. As load increases, there is an in-
(because of congestion) while short=t-cost routing (which creasing difference in node costs between shortwt-hop and
is a function of energy consumed and is hence affected by shortest-cost routing. FinMy, at very high loads, the cost
contention costs) restited in shorter delays since congested of dl nodes is almost the same and thus there are no sav-
routes were not chosen! So, overall, we conclude that packet ings. The same behavior is illustrated in the plot on the
delay is untiected when using shortest-cost routing. right where we show the reduction in maximum node cost.
Let us now consider the relative improvement in the
wst/packet and mu node wst metrim when using short=t- 5.1 Summav of Results
cost routing. We need to mention that both the shortest-hop
and shortest-cost simtiations were run on top of PAMAS. Based on the simulations, we can conclude that using power-
Thus, the improvement we see is in addition to the improve aware metrics to find routes is very beneficial because the
ment gained by PAMAS (which is si~cant). Let us fist tierence in battery consumption between wious nod= is
look at a 10-node random network. Figure 5 tilustrates the reduced. ThB typically means longer network fife and longer
percentage improvement in the cost/packet/hop for differ- time to node failure. The spectic conclusions from the W-
ent tiues of p. Each curve represents a ditferent vrdue of periments are
A. The plot on the left shows the improvement when we use
1. Larger networks have higher cost savings,
a Knew cost function for ~ and the plot on the right shows
the improvement when the cost function is quadratic. We 2. Cost savings are bmt at moderate network loads ad
can see that the improvement is in the 5-15% range. Fig- negligible at very low or at very high loads,
ure 6 fllustratw the same set of plots for 20-node random
networks. 3. Denser networks tilbit more cost savings in general,
It is inter=ting to observe that the savings are greater and
in larger networks. This is not surprising because larger 4. The cost function used dramatic~y tiects the amount
networks have more routes to choose horn. A second obser- of cost savings.
vation we can make is that savings increase with load. This
is because at very low loads, the cost ~erentid between It is worth pointing out that our results will hold true in
nodes is too small to matter. However as load increases, networks where nodes are mobile. ThM is because nod= in
th~ cost Merentid increases and is reflected in cost sav- red networks do not move randomly independently. fither,
ings per padet. kterestingly however, at heavy loads (be clusters of nodes move in correlated ways (image a platoon
yond 0.2 or 0.3 in th-e studies), the improvement remains of soldiers). If, however, nod= do move randody ind~
constant and, in fact, becomw negligible at very high loads pendently, then we believe that there will be small, if any,
(overloaded conditions). ThB last graph (with A = 1.5 pack- cost savings obtainable by using power-aware metri~ (note,
ets/node/see) was not plotted because the savings were zero. however, that PAMAS will still defiver huge savings).

187
 Figure 5: Percentage reduction in average cost in 10-node radom networh.

5
t i
01 I
0.$ 0.15 02 025 03 0s 0.4 06 05
E@e ~q

Figure 6: Percentage reduction in average cost in 20-node random networh.

6 Conclusions products-guide/romvir2 .htti, Jan 14, 1998.

[2] D. Beyer, “Accomplishments of the DARPA SURAN Pr&
h this paper we discussed the need to m&e routing prot~ gram”, Proc. IEEE MILCOM’90, Monterey, CA, Oct. 1990.
cob power-aware. Thus, rather than using tradition met-
[3] v. Bharghavan, A. Demers, s.
rics such as hop-count or delay for fiding rout=, we befieve Shenb and L. Zhang,’’MACAW: A Media Access Prot&
that is more important to use cost/pAet and mtimum CO1for Wireless LANs”, Prodings ACM SIGCCMM’9~,
node cost (which are functions of remaining battery power) pp. 212-225, 1994.
as metriw. Our simulations demonstrated that signticmt [4] B61a BollobA, hdom Graphs, Academic Press, 1985.
reductions in cost can be obtained by using shortest-cost
routing as opposed to shortwt-hop routing. A feature of [5] A. Chandrakasan, T. Simon, J. Goodman and W. Ra-
our metrics is that they can be easfly incorporated for use biner,’’SignN Processing for an ultra low power Wirel~
Video Camera”, 3rd International Workshop on Mobile Mul-
in @ting routing protocok for ad hoc network.
tim~ia Communications, Princeton, NJ, September 2%27,
1996.
Acknowledgements [6] A. Chocbfingam and M. Zoni, “Energy Consumption Per-
formance of a class of Access Protocols for Mobile Data Net-
Tti research was supported by NSF ~ant NCR-9706080. worh”, Proc. IEEE VTC’98, Ottawa, Canada, May 1S21,
1998.
References [7] B. Das, R. Si~umar and V. Bharghavan,’’Routing in
Ad Hoc Network using a Spine”, Pmt. IEEE ICCCN’97,
[1] http: //m.netuorks .digitti. con/npb/h~/ (1997).

188

-. — .-
 1

Pigure 7 Percentage reduction in mtium node cost in 10-node random networks.

01 015 02 025 025 04 06 05

EW %*

Figure 8: Percentage reduction in mtimum node cost in 20-node random networks.

[8] R. Dube, C. D. Ms, K-Y Wang and S. K. Wlpathi, “Signal Multimtiia Communications, Princeton, NJ, September 2$
Stahiti~-bssed Adaptive Routing (SSA) for Ad Hoc Mobile 27, 1996.
Networks”, Technical Report CS-TR-3646, UMIACS-TR-96- [14] J. L. Hennessy and D. A.
34, August 28, 1996. Patterson,Computer Architecture A Quantitative Approach,
[9] F. Doughs, F. Kaashoek, B. Marsh, R. Caceres, K. Lai and J. 2nd edition, Morgan Kaufmann, San Francisco, CA, (1996).
Tauber, “Storage Altemativ~ for Mobile Computers”, Proc.
[15] David B. Johnson and David A. Mdtz. “Dynamic source
1994 Symposium on Operating Systems Design and Imple-
routing in ad hoc wirelw networks”, In Tom=z Imielinski
mentation, OSDI, November 1994.
and Henry F. Korth, editors, Mobile Computing, pages 153-
[10] Chane L. Fullmer and J.J. Garcia-Luna-Aceves,’’Solutions 181. Kluwer Academic Publishing, 1996.
to Hidden Terrnind Problems in Wireless Networks”, Pro-
tiings ACM SZGCOMM’97, Cannes, France, Sept. 1418, [16] John Jubin and Janet D. Tornow, “The DARPA packet radio
1997. network protocols”, Prodings of the IEEE, 75(1):21-32,
January 1987.
[11] Mario Geria and J.T.-C. Tsai,’’Multicluster, Mobile, Multi-
media Radio Network”, ACM-Baltzer Journal of Wireless [17] P. Karn,l’MACA - a New Channel Access Method for Packet
Networks, Irol. 1, No. 3, pp. 255-265, 1995. Mo”, in ARRL/CRRL Amateur Radio 9th Computer Net-
working Con~erence, pp. 134-140, 1990.
[12] S. Gold,”A PSPICE Macrornodel for Lithium-Ion Batteriw”,
The 12th Annual Battery Conference on Applications and [18] Grezorv S. Lauer. “Packet-radio routind’. In Martha Steen-
Advances, CW1fomia State Univ., Long Beach, CA, Jan 14- stru~, ;ditor, Routing in Communicati;n& Networks, Chap
17, 1997. (see Fig. 4) ter 11, pages 351-396. Prentic&Hdl, 1995.
[13] E.P. Harris and K.W. Warren,’’Low Power Technologies: A [19] K. L], R. Kumpf, P. Horton and T. Anderson,”A Quantita-
System Perspective”, 3ti International Workshop on Mobile tive Analysis of Disk Drive Power Management in Portable

189

- . . .
 m -

15

to - ,

5 -

:s 0.1 015 02 0s 0.3 0.s 0.4

Figure 9: Percentage reduction in cost/pkt/hop and mtium node cost in a l&node mwh.

Computers”, Pm&ings 1994 USENZX, San fiancisco, CA, [31] Krishna M. Sidngam, M. B. Srivastava, P. Agrawd and
pp. 279-291, 1994. J-C. Chen, “Low-Power Access Protocok Based on Schedul-
in~ for Wireless and Mobile ATM Networks”. Manuscript..,
[20] M. J. Karol, Z.Liu and K. Y. Eng, “Distributed-queuing r~
ht~p://www.eecs.wsu.edu/~krishna. ‘
quest update multiple accw (DQRUMA) for wireless packet
(AThi) networks, Proc. ZEEE ZCC’95, June 1995, pp. 1224 [32] M. Stemm and P. Gauthier and D. Harada,’’Reducing power
1231. consumption of network interfaces in hand-held devices” .3rd
[21] W. Maugion+Smith and P.S. Ghaug, “A low power medium Zntema~ional Workshop on Mobile Multimtiia Commun;ca-
access control protocol for portable multi-media systems”, tions,September 25-27, 1996.
3rd Zntemational Workshop on Mobile Multimdia Commu- [33] GK Toh,’’The Cambridge Ad Hoc Mobile Routing Prot&
nimtions, September 25-271996. COI°, in Wireless ATM and Ad Hoc Networks, Kluwer Aca-
[22] S. Nfurthy and J.J. Garcia-Luna-Aceves, ”An Efficient Rout- demic Publishers, Boston, Chapter 9, (1997).
ing Protocol for }Vlreless Networks”, ACM Mobile Networks [34] S. Zdonik, M. FranMin, R. Alonso and S. Acharya,’’Are
and Applimtions Journal, Special Issue on Routing in MO “disks in the aif’ just pie in the sky?”, ZEEE Workshop on
bile Communications Networks, 1996. Mobile Computing Systems and Applications, Santa Cruz,
[23] S. Singh and C. S. fighavendra,’’Power efficient MAC pr~ CA, pp. 12-19, December 1994.
tocol for multihop radio networks”, Proc. ZEEE PZMRC’98, [35] Michele Zorzi and R. R. Rae, “energy Management in wire
Sept, 1998. less Communications”, Proc. 6th WZNLAB Workshop on
[24] S. Singh and C. S. &ghavendra,’’PAMAS - Power Aware Third Generation Wireless Information Networks, March
hlulti-Accws protocol with Signaling for Ad Hoc Networks”, 1997.
A Cbf Computer Communication Review, July 1998.
[25] \r. D. Park and kL S. Corson,”A Highly Adaptive Dis-
tributed Routing Algorithm for Mobile Wireless Networks”,
Proc. ZEEE ZNFOCOM’97, Kobe, Japan, (1997).
[26] Charles E. Perkins and Pravin Bhagwat, “Routing over
multi-hop wireless network of mobile computers”, In Tomasz
Imielinski and Henry F. Korth, editors, Mobile Computing,
pages 183-205. Kluwer Academic Publishing, 1996.
[27] D. Petras and A. Kr5mling, “MAC protocol with polling
and fast collision resolution for an ATM air interface”, Proc.
ZEEE ATflf’96 workshop, San Francisco, CA, Aug. 1996.
[28] Chunhung Richard Lin and Mario Gerla,’’Asynchronous
Llultime&a Multihop \Vlrelws Networks;’, Procdings
ZEEE ZNFOCOhf’97, (1997).
[29] Christian R6hl, H. Woesner and A. Wolisz, “A Short Look
on Power Saving Mechanisms in the Wireless LAN Standard
Draft EEE 802.11”, Proc. of the 6th WZNLAB Workshop
on Third Generation Wireless Systems, Llarch 1997.
[30] Krishna L1. Sitingam, M. B. Sriwtava and P.
Agrawd, “Low Power Link and Access Protocols for Wire
less Nlult imedia NetworW’, Proc. ZEEE Vehicular Technol-
ogy conference VTC’97, Phoenix, AZ, May 4-7, lgg7.

190

——.
-. - --- —