Minimum energy paths for reliable communication in multi-hop wireless networks.
Current algorithms for minimum-energy routing in wireless networks typically select minimum-cost multi-hop paths. In scenarios where the transmission power is fixed, each link has the same cost and the minimum-hop path is selected. In situations where the transmission power can be varied with the distance of the link, the link cost is higher for longer hops; the energy-aware routing algorithms select a path with a large number of small-distance hops. In this paper, we argue that such a formulation based solely on the energy spent in a single transmission is misleading --- the proper metric should include the total energy (including that expended for any retransmissions necessary) spent in reliably delivering the packet to its final destination.We first study how link error rates affect this retransmission-aware metric, and how it leads to an efficient choice between a path with a large number of short-distance hops and another with a smaller number of large-distance hops. Such studies motivate the definition of a link cost that is a function of both the energy required for a single transmission attempt across the link and the link error rate. This cost function captures the cumulative energy expended in reliable data transfer, for both reliable and unreliable link layers. Finally, through detailed simulations, we show that our schemes can lead to upto 30-70% energy savings over best known current schemes, under realistic environments.
INTRODUCTION
Multi-hop wireless networks typically possesstwo important characteristics

1. The battery power available on the constituent lightweight mobile
nodes(such as sensornodes or smart-phones) is relatively
limited.
2. Communication costs (in terms of transmission energy required)
are often much higher than computing costs (on individual
devices).
Energy-aware routing protocols (e.g., [14, 13, 1]) for suchnetworks
typically select routes that minimize the total transmission power
over all the nodes in the selected path.
In constant-power scenarios, where the transmission power of a
node is chosenindependent of the distance of the link, conventional
routing [9, 11] will be most energy efficient when the
links are error free. In alternative variable-power scenarios, where
the nodes can dynamically vary their transmitter power levels, the
chosentransmission power dependson the distance betweenthe transmitter
and receiver nodes. For wireless links, a signal transmitted
with power P t over a link with distance D gets attenuated and is
received with power
Pr /
where K is a constant that depends on the propagation medium and
antennacharacteristics 1 . Therefore, the transmission power for these
links are chosen proportional to D K . In these scenarios, proposals
for energy-efficient routing protocols (e.g., [14, 6]) typically aim to
choosea path with a a large number of small-range hops, since they
consumelesspower than an alternative route that hasa smaller number
of hops, but a larger distance for individual hops. In general,
most formulations for computing energy efficient paths employ algorithms
for computing minimum-cost paths, with the link metric
determined by the energy required to transmit a single packet over
that link. Setting this link cost to 1 (and thus computing minimum
hop paths) suffices in constant-power scenarios, since the transmission
energy is the same for all links.
In this paper, we discuss why such a formulation of the link cost
fails to capture the actual energy spent in reliable packet delivery -
a more accurate formulation needs to consider the link error rates
to account for the potential cost of retransmissions needed for reliable
packet delivery. Wireless links typically employ link-layer
1 K is typically around 2 for short distances and omni-directional
antennae, and around 4 for longer distances.
frame recovery mechanisms (e.g. link-layer retransmissions, or forward
error correcting codes) to recover from packet losses. Addi-
tionally, protocols such as TCP or SCTP employ additional source-initiated
retransmission mechanisms to ensure a reliable transport
layer. Therefore, the energy cost associated with a candidate path
should thus reflect not merely the energy spent in just transmitting
a single packet across the link, but rather the "total effective energy"
spent in packet delivery, which includes the energy spent in potential
retransmissions as well 2 .
We first consider how the error rate of individual links affects the
overall number of transmissions needed to ensure reliable packet
delivery. Such an analysis helps to clearly delineate how the energy
associated with the reliable delivery of a packet differs from the energy
associated with simply transmitting the packet. As part of this
analysis, we consider two different operating models:
a) End-to-End Retransmissions (EER): where the individual
links do not provide link-layer retransmissions and error recovery-
reliable packet transfer is achieved only via retransmissions
initiated by the source node.
Retransmissions (HHR): where each individual
link provides reliable forwarding to the next hop using localized
packet retransmissions.
We shall see that, in both cases, it is important to consider the
link's error rate as part of the route selection algorithm, since the
choice of links with relatively high error rates can significantly increase
the effective energy spent in reliably transmitting a single
packet. This is true in both the constant-power and variable-power
scenarios - in either scenario, ignoring the error rate of the link
leads to the selection of paths with high error rates and consequently,
high retransmission overhead. The analysis of the effects of link
error rates on the effective energy consumption is more interesting
for the variable-power case: we shall see that the choice between
a path with many short-range hops and another with fewer long-range
hops is non-trivial, but involves a tradeoff between the reduction
in the transmission energy for a single packet and the potential
increase in the frequency of retransmissions. Our analysis
of the variable-power scenarios shows that schemeswhich consider
the link-error rates would perform significantly better than currently
proposed minimum-energy routing protocols, which do not.
We then study how routing algorithms can be used to minimize
our new objective function: the energy required to reliably transmit
a packet to the destination, the effective transmission energy. Since
most decentralizedad-hoc routing protocols (e.g., AODV [12], DSR [7])
attempt, at least approximately, to select aminimum-cost path (where
the path cost is a sum of the individual link costs), we define a new
link cost as a function of both the link distance and the link error
rate. We shall show that such a link cost can be exactly defined to
obtain optimal solutions only for the HHR scenario; for the EER
framework, we can only devise an approximate cost function. By
using simulation studies, we also demonstrate how the choice of
parameters in the approximate EER cost formulation represents a
tradeoff between energy efficiency and the achieved throughput.
While the link quality has been previously suggested as a routing
metric to reduce queuing delays and loss rates, its implicit effect on
the energy efficiency has not been studied before. By incorporating
the link error rates in the link cost, energy savings of 30% to 70%
can often be achieved under realistic operating conditions.
2 This is especially relevant in multi-hop wireless networks, where
variable channel conditions often cause packet error rates as high as
The rest of the paper is organized as follows. Section 2 provides
an overview of previous related work. Section 3 formulates the effective
transmission energy problem as a function of the number of
hops, and the error rates of each hop, for both the EER and HHR
case and analyses its effect on the optimum number of hops in the
variable-power scenario. It also demonstrates the agreementbetween
our idealized energy computation and real TCP behavior. Section
4 shows how to form link costs that lead to the selection of minimum
effective energy paths. In Section 5 we present the results
of our simulation studies on certain ad-hoc topologies, for both the
fixed-power and the variable-power scenarios. Finally, Section 6
concludes the paper.
2. RELATED WORK
Metrics used by conventional routing protocols for the wired Internet
typically do not need to consider any energy-related parame-
ters. Thus, RIP [9] uses hop count as the sole route quality metric,
thereby selecting minimum-hop paths between the source and des-
tinations. OSPF [11], on the other hand, can support additional link
metrics such as available bandwidth, link propagation delay etc.-
there is, however, no well-defined support for using link-error rates
as a metric in computing the shortest cost path. Clearly, in fixed-
power scenarios, the minimum-hop path would also correspond to
the path that uses the minimum total energy for a single transmission
of a packet.
In contrast, energy-aware routing protocols for variable-power scenarios
aim to directly minimize the total power consumed over the
entire transmission path. PAMAS [14], is one such minimum total
transmission energy protocol, where the link cost was set to the
transmission power and Dijkstra's shortest path algorithm was used
to compute the path that uses the smallest cumulative energy. In the
case where nodes can dynamically adjust their power based on the
link distance, such a formulation often leads to the formation of a
path with a large number of hops. A link cost that includes the receiver
power as well is presented in [13]. By using a modified form
of the Bellman-Ford algorithm, this approach resulted in the selection
of paths with smaller number of hops than PAMAS.
In contrast to the routing protocols for the wired Internet, the routing
protocols for wireless ad-hoc environments (e.g. AODV, DSR)
contain special features to reduce the signaling overheads and con-
vergenceproblems causedbynode mobility and link failures. While
these protocols do not necessarily compute the absolute minimum-cost
path, they do aim to select paths that have lower cost (in terms
of metrics such as hop count or delay). Such protocols, can in principle
be adapted to yield energy-efficientpaths simply by setting the
link metric to be a function of the transmission energy. In contrast,
other ad-hoc routing protocols have been designed specifically to
minimize transmission energy cost. For example, the Power-Aware
Route Optimization (PARO) algorithm [6, 5] is designed for scenarios
where the nodes can dynamically adjust their transmission
power - PARO attempts to generate a path with a larger number
of short-distance hops. According to the PARO protocol, a candidate
intermediary node monitors an ongoing direct communication
between two nodes and evaluates the potential for power savings by
inserting itself in the forwarding path- in effect, replacing the direct
hop between the two nodes by two smaller hops through itself. For
any frequency-hopping wireless link, Gass et. al. [4] have proposed
a transmission power adaptation scheme to control the link quality.
Researchers in energy-aware routing have also considered other
objective functions, besides the one of minimum total energy. One
alternative approachconsidersthe battery capacity of individual nodes;
such battery-aware routing algorithms typically aim to extend the
lifetime of the networkby distributing the transmission paths among
nodes that currently possess greater battery resources. Such algorithms
are basedon the observationthat minimum-energy routes can
often unfairly penalize a subset of the nodes, e.g., if several minimum
energy routes have a common node in the path, the battery of
that node will be exhausted quickly. Among such battery-aware al-
gorithms, [15] formulated a node metric, where the capacity of each
node was a decreasing function of the residual battery capacity. A
minimum cost path selection algorithm then helps to steer routes
aways from paths where many of the intermediate nodes are facing
battery exhaustion. Since this mechanism could still lead to the
choice of a path having a node that was nearing exhaustion (espe-
cially if the other nodes on the path had high residual capacity), the
basic MMBCR algorithm and its CMMBCR variant [16] formulates
path selection as a min-max problem. In this approach, the capacity
of a route is defined as the battery level of the critical (most drained)
node; the algorithm then selects the path with the highest capacity.
All these protocols and algorithms, do not, however, consider the
effect of the link error rates on the overall number of retransmis-
sions, and thus the energy needed for reliable packet delivery. Our
problem formulation and routing solution implicitly assumes that
each node in the ad-hoc network is aware of the packet error link on
its outgoing links. Sensing the channelnoise conditions can be done
either at the link layer, a capability that is built into most commercial
wireless 802.11 interfaces available today, or through higher layer
mechanismssuch as periodic packet probes or aggregatedpacket reception
reports from the receiver 3 .
3. ENERGY COST ANALYSIS
In this section, we demonstrate how the error rate associated with
a link affects a) the overall probability of reliable delivery, and con-
sequently, b) the energy associated with the reliable transmission of
a single packet. For any particular link (i; j) between a transmitting
node i and a receiving node j, let T i;j denote the transmission
power andp i;j represent the packeterror probability. Assumingthat
all packets are of a constant size, the energy involved in a packet
simply a fixed multiple of T i;j .
Any signal transmitted over a wireless medium experiences two
different effects: attenuation due to the medium, and interference
with ambient noise at the receiver. Due to the characteristics of the
wireless medium, the transmitted signal suffers an attenuation proportional
to D K , where D is the distance between the receiver and
the transmitter. The ambient noise at the receiver is independent of
the distance between the source and distance, and depends purely
on the operating conditions at the receiver. The bit error rate associated
with a particular link is essentially a function of the ratio of this
received signal power to the ambient noise. In the constant-power
scenario, T i;j is independent of the characteristics of the link (i;
and is essentially a constant. In this case, a receiver located farther
away from a transmitter will suffer greater signal attenuation (pro-
portional to D K ) and will, accordingly, be subject to a larger bit-error
rate. In the variable-power scenario, a transmitter node essentially
adjusts T i;j to ensure that the strength of the (attenuated) signal
received by the receiver is independent of D and is above a certain
threshold level Th. According, the optimal transmission power
associated with a link of distance D in the variable-power scenario
is given by:
where fl is a proportionality constant and K is the coefficient of attenuation
(K - 2). Since Th is typically a technology-specific
3 Similar ideas were proposed for link sensing in the Internet
MANET Encapsulation Protocol [2].
constant, we can see that the optimal transmission energy over such
a link varies as:
It is now easy to understand, at least qualitatively, the impact of
neglecting the link error rates while determining a specific path between
the source and destination nodes. For the fixed-power case,
the minimum-hop path may not be the most energy-efficient, since
an alternative path with more hops may prove to be better if its over-all
error rate is sufficiently low. Similarly, for the variable-power
case, a path with a greater number of smaller hops may not always
be better; the savings achieved in the individual transmission energies
(given by Equation may be nullified by a larger increase in
link errors and consequently retransmissions.
We now analyze the interesting consequencesof this behavior for
the variable-power scenario (for both the EER and HHR cases); we
omit the analysis for the fixed-power scenario which is simpler, and
a special case of our ensuing analysis.
3.1 Optimal Routes in EER Case
In the EER case, a transmission error on any link leads to an end-
to-end retransmission over the path. Given the variable-power formulation
of Eopt in Equation (3), it is easy to see why placing an intermediate
node along the straight line between two adjacent nodes
(breaking up a link of distance D into two shorter links of distance
and D2 such that D1 reduces the total Eopt .
In fact, PARO works using precisely such an estimation. From a reliable
transmission energy perspective, such a comparison is, how-
ever, inadequate since it does not include the effect on the overall
probability of error-free reception.
To understand the energy-tradeoff involved in choosing a path
with multiple short hops over one with a single long hop, consider
communication between a sender (S) and a receiver (R) located at
a distance D. Let N represent the total number of hops between S
and R, so that N \Gamma 1 represents the number of forwarding nodes between
the end-points. For notational ease, let the nodes be indexed
referring to the (i \Gamma 1) th intermediate
hop in the forwarding path; also, node 1 refers to S and
refers to R. In this case, the total optimal energy spent
in simply transmitting a packet once (without considering whether
or not the packet was reliably received) from the sender to the receiver
over the forwarding nodes is:
or, on using Equation (3),
ffD K
where D i;j refers to the distance between nodes i and j and ff is
a proportionality constant. To understand the transmission energy
characteristics associated with the choice of
nodes, we compute the lowest possible value of E total for anygiven
layout of N \Gamma 1. Using very simple optimality arguments, it is easy
to see that the minimum transmission energy case occurs when each
of the hops are of equal length D
N . In that case, E total is given by:
ff
ffD K
For computing the energy spent in reliable delivery, we now consider
how the choice of N affects the the probability of transmission
errors and the consequent need for retransmissions. Clearly,
increasing the number of intermediate hops the likelihood of transmission
errors over the entire path.
Assuming that each of the N links has an independent packet error
rate of plink , the probability of a transmission error over the entire
path, denoted by p, is given by
The number of transmissions (including retransmissions) necessary
to ensure the successfultransfer of a packet betweenS andD is then
a geometrically distributed random variable X , such that
The mean number of individual packet transmissions for the successful
transfer of a single packet is thus 1
. Since eachsuch transmission
uses total energy E total given by Equation (6), the total expected
energy required in the reliable transmission of a single packet
is given by:
total
ffD K
The equation clearly demonstrates the effect of increasing N on
the total energy necessary; while the term N K \Gamma1 in the denominator
increaseswith N , the error-related term (1\Gammap link ) N decreaseswith
N . By treating N as a continuous variable and taking derivatives, it
is easy to see that the optimal value of the number of hops, Nopt is
given by:
Thus a larger value of plink corresponds to a smaller value for the
optimal number of intermediate forwarding nodes. Also, the optimal
value for N increases linearly with the attenuation coefficient
K . There is thus clearly an optimal value of N ; while lower values
of N do not exploit the potential reduction in the transmission en-
ergy, higher values of N cause the overhead of retransmissions to
dominate the total energy budget.
To study these tradeoffs graphically, we plot E EER
total rel against
varying N (for different values of plink ) in Figure 1. For this graph,
ff and D (which are really arbitrary scaling constants) in the analysis
are kept at 1 and 10 respectively and 2. The graph shows
that for low values of the link error rates, the probability of transmission
errors is relatively insignificant; accordingly, the presence
of multiple short-range hops nodes leads to a significant reduction
in the total energy consumption. However, when the error rates are
higher than around 10%, the optimal value of N is fairly small; in
such scenarios, any potential power savings due to the introduction
of an intermediate node are negated by a sharp increase in the number
of transmissions necessary due to a larger effective path error
rate. In contrast to earlier analyses, a path with multiple shorter
hops is thus not always beneficial than one with a smaller number
of long-distance hops.
3.1.1 Energy Costs for TCP Flows
Our formulation (Equation (8)) provides the total energyconsumed
per packet using an ideal retransmission mechanism. TCP's flow
control and error recovery algorithms could potentially lead to different
values for the energy consumption, since TCP behavior during
loss-related transients can lead to unnecessary retransmissions.
While the effective TCP throughput (or goodput) as a function of1234
(Energy
per
Number of Intermediate (Relay) Nodes
Total Effective Trx Energy per Pkt (with Retransmissions)
K=2.0, EER

Figure

1: Total Energy Costs vs. Number of Forwarding
Nodes
(Energy
per
Number of Intermediate (Relay) Nodes
vs. TCP Effective Trx Energy/ Pkt

Figure

2: Idealized / TCP Energy Costs vs. Number of Forwarding
Nodes (EER)
the end-to-end loss probability has been derived in several analyses
(see [8, 3]), there exists no model to predict the total number
of packet transmissions (including retransmissions) for a TCP flow
subject to a variable packet loss rate. We thus use simulation studies
using the ns-2 simulator 4 , to measure the energy requirements
for reliable TCP transmissions. Figure 2 plots the energy consumed
by a persistent TCP flow, as well as the ideal values computed using
Equation (8), for varying N and for 0:05g. The
remarkably close agreement between our analytical predictions and
TCP-driven simulation results verifies the practical utility of our analytical
model.
3.2 Optimal Routes in HHR Case
In the case of the HHR model, a transmission error on a specific
link implies the need for retransmissions on that link alone. This
is a better model for multi-hop wireless networking environments,
which typically always employ link-layer retransmissions. In this
case, the link layer retransmissions on a specific link essentially ensure
that the transmission energy spent on the other links in the path
is independent of the error rate of that link. For our analysis, we
do not bound the maximum number of permitted retransmissions: a
transmitter continues to retransmit a packet until the receiving node
acknowledgeserror-free reception. (Clearly, practical systemswould
typically employ a maximum number of retransmission attempts to
4 Available at http://www.isi.edu/nsnam/ns
(Energy
per
Number of Intermediate (Relay) Nodes
Total Effective Trx Energy per Pkt (with Retransmissions)
K=2.0, HHR

Figure

3: Total Energy Costs vs. Number of Forwarding
Nodes (HHR)
bound the forwarding latency.) Since our primary focus is on energy-efficient
routing, we also do not explicitly consider the effect of such
retransmissions on the overall forwarding latency of the path in this
paper.
Since the number of transmissions on each link is now independent
of the other links and is geometrically distributed, the total energy
cost for the HHR case is
total
ff
In the case of N intermediate nodes, with eachhop being of distance
N and having a link packet error rate of plink , this reduces to:
total

Figure

3 plots the total energy for the HHR case, for
different values of N and plink . In this case, it is easy to see that the
total energy required always decreases with increasing N , following
the 1
course, the logarithmic scale for the
energy cost compresses the differences in the value of P HHR
total rel for
different plink . By itself, this result is not very interesting: if all
links have the same error rate, it is beneficial to substitute a single
hop with multiple shorter hops.
A more interesting study is to observe the total energy consump-
tion, for a fixed N , for different values of plink . Clearly, for moderately
large values of plink , the number of total transmissions (and
hence, the energy consumption) increases super-linearly with an increase
in the link error rate. The graph thus shows the importance
of choosing links with appropriate link error rates, even in the HHR
case. (In the EER case, Figure 1 clearly demonstrates that the effect
of larger link error rates is much more drastic - when
example, increasing the loss probability from 0:1 to 0:2 can increase
the energy consumption ten-fold.) An energy-aware algorithm that
does not consider the error rates of associatedlinks would not distinguish
between two paths, each of 10 nodes having the same D values
but different packet error rates. However, our analysis clearly
shows that the effective energy consumed by a path consisting of
links with higher packet error rates would be much larger than a path
with smaller error rates.
We obtain another meaningful observation by comparing the values
rel for the EER and HHR cases (Figures 1 and 3), for
identical values of N and K . It is easy to see that, for moderate to
high values of plink , the EER framework results in at least an order
of magnitude higher energy consumption than the HHR case.
By avoiding the end-to-end retransmissions, the HHR approachcan
significantly lower the total energy consumption. These analyses
reinforce the requirements of link-layer retransmissions in any radio
technology used in multi-hop, ad-hoc wireless networks.
4. ASSIGNING LINK COSTS
In contrast to traditional Internet routing protocols, energy-aware
routing protocols typically compute the shortest-cost path, where
the cost associated with each link is some function of the transmission
(and/or reception) energy associatedwith the correspondingnodes.
To adapt such minimum cost route determination algorithms (such
as Dijkstra's or the Bellman-Ford algorithm) for energy-efficient reliable
routing, the link cost must now be a function of not just the
associated transmission energy, but the link error rates as well. Using
such a metric would allow the routing algorithm to select links
that present the optimal tradeoff between low transmission energies
and low link error rates. As we shall shortly see, defining sucha link
cost is possible only in the HHR case; approximations are needed to
define suitable cost metrics in the EER scenario.
Before presenting the appropriate link costs, it is necessary to define
the graphused for computing the shortest cost paths. Consider a
graph, with the set of vertices representing the communicationnodes
and a link l i;j representing the direct hop betweennodes i and j. For
generality, assume an asymmetric case where l i;j is not the same as
l j;i ; moreover, l i;j refers to the link used by node i to transmit to
node j. A link is assumed to exist between node pair (i; j) as long
as node j lies within the transmission range of node i. This transmission
range is uniquely defined for the constant-power case; for
the variable-power case, this range is really the maximum permissible
range corresponding to the maximum transmission power of a
sender. Let E i;j be the energy associated with the transmission of
a packet over link l i;j , and p i;j be the link packet error probability
associated with that link. (In the fixed-power scenario, E i;j is independent
of the link characteristics; in the variable-power scenario,
E i;j is a function of the distance between nodes i and j.) Now, the
routing algorithm's job is to compute the shortest path from a source
to the destination that minimizes the sum of the transmission energy
costs over each constituent link.
4.1 Hop-by-Hop Retransmissions (HHR)
Consider a path P from a source node S (indexed as node 1) to
nodeD that consists of N \Gamma1 intermediate
Then, choosing path P for communication between S and D implies
that the total energy cost is given by:
Choosing a minimum-cost path from node 1 to node N + 1 is thus
equivalent to choosing the path P that minimizes Equation (11). It
is thus easy to see that the corresponding link cost for link L i;j , denoted
by C i;j , is given by:
Some ad-hoc routing protocols, such as DSR or AODV, can then
use this link cost to compute the appropriate energy-efficient routes.
Other ad-hoc routing protocols, such as PARO, can also be easily
adapted to use this new link cost formulation to compute minimum-energy
routes. Thus, in the modified version of the PARO algo-
rithm, an intermediate nodeC would offer to interject itself between
two nodes A and B if the sum of the link costs CA;C
less than the 'direct' link cost CA;B .
4.2 End-to-End Retransmissions (EER)
In the absence of hop-by-hop retransmissions, the expression for
the total energy cost along a path contains a multiplicative term involving
the packet error probabilities of the individual constituent
links. In fact, assuming that transmission errors on a link do not stop
downstream nodes from relaying the packet, the total transmission
energy can be expressed as :
Given this form, the total cost of the path cannot be expressed as a
linear sum of individual link costs 5 , thereby making the exact formulation
inappropriate for traditional minimum-cost path computation
algorithms. We therefore concentrate on alternative formulations
of the link cost, which allow us to use conventional distributed
shortest-cost algorithms to compute "approximate" minimum energy
routes.
A study of Equation (13) shows that using a link with a high p can
be very detrimental in the EER case: an error-prone link effectively
drives up the energy cost for all the nodes in the path. Therefore,
a useful heuristic function for link cost should have a super-linear
increase with increase in link error rate; by making the link cost for
error-prone links prohibitively high, we can ensure that such links
are usually excluded during shortest-cost path computations.
In particular, for a path consisting of k identical links (i.e. have
the same link error rate and link transmission cost), Equation13 will
reduce to
where, p is the link error rate and E is the transmission cost across
each of these links. This leads us to proposea heuristic cost function
for a link, as follows:
is chosen to be identical for all links 6 .
Clearly, if the exact path length is known and all nodes on the path
have the identical link error rates and transmission costs, L should
be chosen equal to that path length. However, we require that a link
should advertise a single cost for that link for distributed route com-
putation, in accordance with current routing schemes. Therefore,
we need to fix the value of L, independent of the different paths
that cross a given link. If better knowledge of the network paths are
available, then L should be chosen to be the average path length of
this network. Higher values of L impose progressively stiffer penalties
on links with non-zero error probabilities.
Given this formulation of the link cost, the minimum-cost path
computation effectively computes the path with the minimum "ap-
5 We do not consider solutions that require eachnode or link to separately
advertise two different metrics. If such advertisements were
allowed, we can indeed compute the optimal path accurately. For
example, if we considered two separate metrics- a) E i;j and b)
then a node can accurately compute the next hop
neighbor (using a distance-vector approach) to a destination D by
using the cumulative values
advertised
by its neighbor set.
6 There should be an L factor in the numerator too (as in Equation
14, but since this is identical for all links, it can effectively be
ignored.
proximate" energy cost given by:
As before, regular ad-hoc routing protocols, or newer ones such as
PARO, can use this new link cost function C approx to evaluate their
routing decisions.
As with our theoretical studies in Section 3, the analysis here does
not directly apply to TCP-based reliable transport, since TCP's loss
recovery mechanism can lead to additional transients. In the next
section, we shall use simulation-based studies to study the performance
of our suggested modifications to the link cost metric in typical
ad-hoc topologies.
5. PERFORMANCE EVALUATION
The analysis of the previous section provides a foundation for devising
energy-conscious protocols for reliable data transfer. In this
section, we report on extensive simulation-based studies on the performance
impacts of our proposed modifications in the ns-2 simu-
lator. The traffic for our simulation studies consists of two types:
1. For studies using the EER framework, we usedTCP flows implementing
the NewReno version of congestion control.
2. For studies using the HHR framework, we used both UDP
and TCP flows. In UDP flows, packets are inserted by the
source at regular intervals.
To study the performance of our suggested schemes, we implemented
and observed three separate routing algorithms:
1. The minimum-hop routing algorithm, where the cost of all
links is identical andindependent of both the transmission energy
and the error rate.
2. The Energy-Aware (EA) routing algorithm, where the cost
associated with each link is the energy required to transmit a
single packet (without retransmission considerations) across
that link.
3. Our Retransmission-EnergyAware (RA) algorithm, where the
link cost includes the packet error rates, and thus considers
the (theoretical) impact of retransmissions necessary for reliable
packet transfer. For the HHR scenario, we use the link
cost of Equation (12); for the EER model, we use the 'ap-
proximate' link cost of Equation (15) with 2. In Section
5.4.2, we also study the effect of varying the L-parameter.
In the fixed-powerscenario, the minimum-hop andEA algorithms
exhibit identical behavior; accordingly, it suffices to compare our
RA algorithm with minimum-hop routing alone. For our experi-
ments, weused different topologies havingupto 100nodesrandomly
distributed on a squareregion, to study the effects of various schemes
on energy requirements and throughputs achieved. In this section,
we discuss in detail results from one representative topology, where
nodes were distributed over a 70X70 unit grid, equi-spaced 10
units apart (Figure 4). The maximum transmission radius of a node
is 45 units, which implies that each node has between 14 and 48
neighbors on this topology,
Each of the routing algorithms (two for the fixed-power scenario,
three for the variable-power scenario) were then run on these static
topologies to derive the least-cost paths to each destination node.
To simulate the offered traffic load typically of suchad-hoc wireless
topologies, each of the corner node on the grid had 3 active flows,
A

Figure

4: The 49-node topology. The shaded region marks the
maximum transmissionrange for the cornernode, A. Thereare
three flows from each of the 4 corner nodes, for a total of 12
flows.
providing a total of 12 flows. Since our objective was to study the
transmission energies alone, we did not consider other factors such
as link congestion, buffer overflow etc. Thus, each link had an infinitely
larger transmit buffer; the link bandwidths for all links (point
to point) was set to 11 Mbps. Each of the simulations was run for a
fixed duration.
5.1 Modeling Link Errors
The relation between the bit-error-rate (pb ) over a wireless channel
and the received power level Pr is a function of the modulation
scheme. However, in general, several modulation schemes exhibit
the following generic relationship between pb and Pr :
pb / erfc(
r
constant   P r
where N is the noise spectral density (noise power per Hz) and erfc(x )
is defined as the complementary function of erf (x ) and is given by
Z xe \Gammat 2
dt
As specific examples, the bit error rate is given by
r
for BPSK (binary phase-shift keying), where f is transmission bit-rate

Since we are not interested in the details of a specific modulation
schemebut merely want to study the general dependenceof the error
rate on the received power, we make the following assumptions:
i) The packet error rate p, equals S:pb , where pb is the bit error
rate and S is the packet size. This is an accurate approximation
for small error rates pb ; thus, we assume that the packet
error rate increases/decreases in direct proportion to pb .
ii) The received signal power is inversely proportional to D K ,
where D is the link distance, and K is the same constant as
usedin Equation 2. ThusPr canbe replaced by T=D K where
T is the transmitter power. We chooseBPSK as our representative
candidate and hence, use Equation 17 to derive the bit-
error-rate.
We study both the fixed and variable power scenarios in our simulations

Fixed transmission power: In this case all the nodes in the
network use a fixed power for all transmissions, which is independent
of the link distance. While such an approach is
clearly inefficient for wireless environments, it is representative
of several commercial radio interfaces that do not provide
the capability for dynamic power adjustment. From Equation
17, it is clear that links with larger distances have higher
packet error rates.
For our experiments in this case, we first chose a maximum
error rate (pmax ) for an unit hop along the axes for the grid
topology given in Figure 4. Using Equation 2 and 17, it is
then possible to calculate the corresponding maximum error
rates on the other links.
To add the effect of random ambient noise in the channel, we
chose the actual packet error rate on each link uniformly at
random from the interval (0; pmax ), where pmax is the maximum
packet error rate computed for that link. For different
experiments, we varied the pmax for the unit hop links (and
correspondingly the maximum error rates for the other links).
ffl Variable transmission power: In this case, we assume that
all the nodes in the network are dynamically able to adjust
transmission power across the links. Each node chooses the
transmission power level for a link so that the signal reaches
the destination node with the same constant received power.
Since we assumethat the attenuation of signal strength is given
by Equation 1, the energy requirements for transmitting across
links of different lengths is given by Equation 3.
Since all nodes now receive signals with the same power, the
bit error rate, given by Equation 17, is the same for all links
(by using the flexibility of adjusting the transmission power
basedon link distances). Therefore, for this scenario, we only
need to model the additional link error rate due to ambient
noise at the receiver. We chose the maximum error rate for
a link due to ambient noise (p ambient ), for the different experiments
in this case, andchose the actual error rate for a link
uniformly at random from the interval (0; p ambient ).
5.2 Metrics
To study the energy efficiency of the routing protocols, we observed
two different metrics:
1. Normalized energy: We first compute the average energy
per data packet by dividing the total energy expenditure (over
all the nodes in the network) by the total number of unique
packets received at any destination (sequencenumber for TCP
and packets for UDP). We defined the normalized energy of a
scheme, as the ratio of the averageenergyper data packet for
that schemeto the averageenergyperdata packet requiredby
the minimum-hop routing scheme. Since, the minimum-hop
routing schemeclearly consumesthe maximal energy, the normalized
energy parameter provides an easy representation of
the percentage energy savings achieved by the other (EA and
routing algorithms.
2. Effective Reliable Throughput: This metric counts the number
of packets that was reliably transmitted from the source
Normalized
energy
required
Max error rate on the unit links
UDP flows on the 49-node topology (Fixed transmission power)
Retransmission Aware

Figure

5: UDP flows with link layer re-transmissions (HHR)
for fixed transmission power scenario.
to the destination, over the simulated duration. Since all the
plots show results of runs of different schemes over the same
time duration, we do not actually divide this packet count by
the simulation duration. Different routing schemes will differ
in the total number of packets that the underlying flows
are able to transfer over an identical time interval.
5.3 Fixed Transmission Power Scenario
We first present results for the case where each node uses a fixed
and constant transmission power for all links. In this case, it is obvious
that the EA routing scheme degenerates to the minimum-hop
routing scheme.
5.3.1 HHR Model
We first present the results for the case where each link implements
its own localized retransmission algorithm to ensure reliable
delivery to the next node on the path.
HHR with UDP: Figure 5 shows the the total energy consumption
for the routing schemesunder link-layer retransmissions (HHR
case). We experimented with a range of link error rates to obtain
these results. Ascanbe seen, the RA schemeshowsa significant improvement
over the minimum-hop (identical in this environment to
the EA) scheme, as expected. The normalized energy requirements
of the minimum-hop and the EA schemes is unity in this case. With
increasing link error rates, the benefits of using our re-transmission
aware scheme become more significant. For example, at a maximum
link error rate for the unit hop links (pmax ) of 0.25, the RA
schemeconsumesabout24% lower energy than the other two schemes.
Note, that in this case, 0.25 is only the maximum link error rate for
the unit links; typical unit links will have actual error rates varying
between 0.0 and 0.25.
It is perhaps important to emphasize that it is only the normalized
energy for the RA scheme which decreases with increasing link error
rate. The absolute energy expenditure will obviously increase
with an increasing value of pmax for all routing algorithms.
HHR with TCP: In Figure 6, we observe the same metric for
flows. As can be seen, the trends for both UDP and TCP flows,
in terms of energy requirements are similar, when link-layer retransmissions
are present. However, it is more interesting to observe the
consequences of using these different schemes on the number of
data packetstransmitted reliably to the destinations of the flows. This
is shown in Figure 7. The RA scheme consistently delivers a larger
volume of data packets to the destination within the same simulated0.750.850.951.05
Normalized
energy
required
Max error rate on the unit links
flows on the 49-node topology (Fixed transmission power)
Retransmission Aware

Figure

Energy required for TCP flows with link layer re-transmissions
(HHR) for fixed transmission power scenario.2000060000100000140000
Sequence
numbers
transmitted
reliably
Max error rate on the unit links
flows on the 49-node topology (Fixed transmission power)
Energy Aware
Retransmission Aware

Figure

7: Reliable packet transmissions for TCP flows with
link layer re-transmissions (HHR) for fixed transmission
power scenario.
duration, even while it is consuming less energy per sequencenum-
ber transmitted. This is becauseof two reasons. First, the RA scheme
at many times chooses path with lower error rates. Thus the number
of link-layer retransmissions seen for TCP flows using the RA
scheme is lower, andhence the round trip time delays are lower. The
throughput, T , of a TCP flow, with round trip delay, - and loss rate,
varies as [10]:
\Theta 1
The RA scheme has smaller values of both p and - and so has a
higher throughput.
5.3.2 EER Model
We now provide the results of our experiments under the EER
scheme.
EER with TCP: We looked at the energy requirements whenend-
to-end TCP re-transmissions are the sole means of ensuring reliable
data transfer. The minimum-hop algorithm always chooses a small
number of larger distance links. However, in this fixed transmission
power case, the received signal strength over larger distance links is
lower, and consequently, by Equation 17, has a higher bit error rate.
Since there are no link layer retransmissions, the loss probability for
Normalized
energy
required
Max error rate on the links
UDP flows on the 49-node topology
Energy Aware
Retransmission Aware

Figure

8: UDP flows with link layer re-transmissions (HHR)
for variable transmission power scenario.
each data segment is fairly high. Therefore this scheme achieves a
very low TCP throughput (less than 1% of that achieved by the RA
scheme) and still used 10-20% more energy. Hence it was difficult
to do meaningful simulation comparisons of the RA scheme with
this minimum-hop algorithm.
5.4 Variable Transmission Power Scenario
In this case, the nodes are capable to adapting the transmission
power, so that the received signal strength is identical across all links.
To achieve this, clearly, links with larger distances require a higher
transmission power than links with smaller distances. In this situa-
tion, we varied the link error rate due to ambient noise at the receiver
of the links to compare the different schemes.
Unlike the fixed transmission power case, the EA routing algorithm
in this case chooses paths with a large number of small hops,
and has lower energy consumption than the minimum hop routing
algorithm. Therefore, in these results, we compare our RA scheme
with both EA and minimum-hop routing.
5.4.1 HHR Model
We first present the results for the case where each link implements
its own localized retransmission algorithm to ensure reliable
delivery to the next node on the path.
HHR with UDP: Figure 8 shows the the total energy consumption
for the routing schemesunder link-layer retransmissions (HHR
case). We experimented with a range of channel error rates to obtain
these results. Both EA and RA schemes are a significant improvement
over the minimum-hop routing scheme, as expected. How-
ever, with increasing channel error rates, the difference between the
normalized energy required per reliable packet transmission for the
RA and the EA schemesdiverges. At some of the high channel error
rates (pambient = 0:5), the energy requirements of the RA scheme
is about 25% lower than the EA scheme. It is again useful to note,
that this error rate is only the maximum error rate for the link. The
actual link error rate is typically much smaller.
Once again, it is only the normalized energy for the RA scheme
which decreases. The absolute energy required obviously increases
with an increasing value of pmax .
HHR with TCP: In Figure 9, we observe the same metric for
flows. As before, the energy requirements of for the RA scheme
is much lower than the EA scheme. Additionally, we can again observe

Figure

10) that the number of data packets transmitted reliably
for the RA scheme is much higher than that of the EA scheme.0.2050.2150.2250.2350.2450.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6
Normalized
energy
required
Max error rate on the links
flows on the 49-node topology
Energy Aware
Retransmission Aware

Figure

9: Energy required for TCP flows with link layer re-transmissions
(HHR) for variable transmission power scenario
Sequence
numbers
transmitted
reliably
Max error rate on the links
flows on the 49-node topology
Energy Aware
Retransmission Aware

Figure

10: Reliable packet transmissions for TCP flows with
link layer re-transmissions (HHR) for variable transmission
power scenario.
5.4.2 EER Model
Finally, we provide the results of our experiments under the EER
framework.
EER with TCP: For the EER case, like before, it was often difficult
to simulate links with high error rates- even with a small number
of hops, each TCP packet is lost with a high probability and no
data ever gets to the destinations.
The energy savings achieved by the RA algorithm is more pro-
nouncedwhenno link-layer retransmission mechanismsare present.
For some of the higher link error rates simulated in this environment
(e.g., 0:22), the energy savings of the RA scheme
was nearly 65% of the EA scheme, as can be seen in Figure 11.
Again, it is interesting to observe the data packets transmitted reliably
by the EA and the RA schemes, simulated over the same duration
12). For lower error rates (pmax between 0.1 to 0.14)
the RA scheme transmits nearly an order of magnitude more TCP
sequence numbers than the EA scheme. While the total TCP goodput
approacheszero for bothschemes, as the link error rates increase,
the rate of decrease in the TCP goodput is much higher for the EA
scheme than the RA scheme.
Varying L: In Figure 13, we varied the L-parameter of Equation
for a specific error rate on the links (i.e., 0:175). The
Normalized
energy
required
Max error rate on the links
flows on the 49-node topology
Energy Aware
Retransmission Aware (L=2)

Figure

11: TCP flows with no link layer re-transmissions
Sequence
numbers
transmitted
reliably
Max error rate on the links
flows on the 49-node topology
Energy Aware
Retransmission Aware (L=2)

Figure

12: TCP flows with no link layer re-transmissions
(EER) for variable transmission power scenario.
number of reliably transmitted packetsincreasedmonotonically with
the value of L. However, the curve in the figure has a minimum "en-
ergy per reliably transmitted packet", corresponding to
this example 7 . Varying the L-value from this optimal value leads
to poorer energy-efficiency (higher energy/packet). There is thus
clearly a trade-off between the achieved throughput, and the effective
energy expended. To achieve a higher throughput, it is necessary
to prefer fewer hops, as well as links with low error rates
(higher error rate links will causehigher delaysdue to re-transmissions).
This plot illustrates the following important point: it is possible to
tune the L-parameter to choosean appropriateoperating point that
captures the tradeoff between a) the achieved TCP throughput, and
b) the effective energy expended per sequence number received reliably

6. CONCLUSION
In this paper, we have shown why the effective total transmission
energy, which includes the energy spent in potential retrans-
missions, is the proper metric for reliable, energy-efficient commu-
nications. The energy-efficiency of a candidate route is thus critically
dependent on the packet error rate of the underlying links,
7 Finer measurementswith many more L-values would yield the exact
L that minimizes this curve.0.320.360.4
5k 10k 15k 20k 25k 30k 35k 40k 45k 50k
Normalized
energy
required
Sequence numbers transmitted reliably
flows on the 49-node topology

Figure

13: Varying the L parameter to tradeoff normalized energy
and number of reliably transmitted sequence numbers.
since they directly affect the energy wasted in retransmissions. Our
analysis of the interplay between error rates, number of hops and
transmission power levels reveals several key results:
1. Even if all links have identical error rates, it is not always
true that splitting a large-distance (high-power) hop into multiple
small-distance (low-power) hops results in overall energy
savings. Our analysis shows that if the number of hops
exceeds an optimal value (which can be as small as
in realistic scenarios), the rise in the overall error probability
negates any apparent reduction in the transmission power.
2. Any routing algorithm must evaluate a candidatelink (and the
path) on the basis of both its power requirements and its error
rate. Even in the HHR framework, where retransmissions
are typically localized to a specific hop, the choice of an error-prone
link can lead to significantly higher effective energy expended
per packet.
3. Link-layer retransmission support (HHR) is almost mandatory
for a wireless, ad-hoc network, since it can reduce the
effective energy consumption by at least an order of magnitude

4. The advantages of using our proposed re-transmission aware
routing scheme is significant irrespective of whether fixed or
variable transmission power is used by the nodes to transmit
across links.
We also studied modifications to the link cost that would enable
conventional minimum-cost path algorithms to select optimal "ef-
fective energy" routes. While the appropriate cost for link (i;
turned out to be E i;j
for the HHR framework, it was not possible
to define an exact link cost for the EER case. For the EER scenario,
we studied the performance of approximate link costs of the form
various values of L. Our simulation studies show that
the incorporation of the error rate in the link cost leads to significant
energy savings (potentially as high as 70%) compared to existing
minimum-energy algorithms. It also turns out that, in the HHR
model, the L parameter in the link cost provides a knob to trade off
energy efficiency with network throughput (capacity). While larger
values of L always lead to the selection of shorter-hop routes and
larger session throughput, the energy-efficiency typically increases
and then decreases with increasing L.
As part of future research, we intend to extendour analyses(which
assumed each link to be operating independently of other links) to
scenarios, such as IEEE 802.11-based networks, where the logical
links share the same physical channel and hence, interfere with one
another. Indeed, since an energy-aware routing protocol defines the
next-hop node (and hence, implicitly defines the associated transmission
power), the choice of the routing algorithm is expected to
affect both the overall network capacity and individual sessionthrough-
puts in such scenarios.
7.



--R

Energy conserving routing in wireless ad-hoc networks
An Internet MANET encapsulation protocol (IMEP) specification
Connections with multiple congested gateways in packet-switched networks part 1: One-way traffic


PARO: A power-aware routing optimization scheme for mobile ad hoc networks
Dynamic source routing in ad hoc wireless networks.

The macroscopic behavior of the TCP congestion avoidance algorithm.

Routing and channel assignment for low power transmission in PCS.


Performance evaluation of battery-life-aware routing schemes for wireless ad hoc networks
--TR
Connections with multiple congested gateways in packet-switched networks part 1
The macroscopic behavior of the TCP congestion avoidance algorithm
Power-aware routing in mobile ad hoc networks
PAMASMYAMPERSANDmdash;power aware multi-access protocol with signalling for ad hoc networks
An adaptive-transmission protocol for frequency-hop wireless communication networks
Ad-hoc On-Demand Distance Vector Routing
Window-Based Error Recovery and Flow Control with a Slow Acknowledgement Channel

--CTR
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
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
Bansal , Rajeev Shorey , Rajeev Gupta , Archan Misra, Energy efficiency and capacity for TCP traffic in multi-hop wireless networks, Wireless Networks, v.12 n.1, p.5-21, February 2006
Wook Choi , Sajal K. Das , Jiannong Cao , Ajoy K. Datta, Randomized dynamic route maintenance for adaptive routing in multihop mobile ad hoc networks, Journal of Parallel and Distributed Computing, v.65 n.2, p.107-123, February 2005
Qunfeng Dong , Suman Banerjee , Micah Adler , Archan Misra, Minimum energy reliable paths using unreliable wireless links, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
Anand Srinivas , Eytan Modiano, Finding minimum energy disjoint paths in wireless ad-hoc networks, Wireless Networks, v.11 n.4, p.401-417, July 2005
Liran Ma , Qian Zhang , Xiuzhen Cheng, A power controlled interference aware routing protocol for dense multi-hop wireless networks, Wireless Networks, v.14 n.2, p.247-257, March 2008
Constandinos X. Mavromoustakis , Helen D. Karatza, Adaptive Energy Conservation Model using Dynamic Caching for Wireless Devices, Proceedings of the 37th annual symposium on Simulation, p.257, April 18-22, 2004
Budhaditya Deb , Badri Nath, On the node-scheduling approach to topology control in ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
Constandinos X. Mavromoustakis , Helen D. Karatza, Handling Delay Sensitive Contents Using Adaptive Traffic-Based Control Method for Minimizing Energy Consumption in Wireless Devices, Proceedings of the 38th annual Symposium on Simulation, p.295-302, April 04-06, 2005
Constandinos X. Mavromoustakis , Helen D. Karatza, Quality of Service Measures of Mobile Ad-hoc Wireless Network using Energy Consumption Mitigation with Asynchronous Inactivity Periods, Simulation, v.83 n.1, p.107-122, January   2007
Budhaditya Deb , Sudeept Bhatnagar , Badri Nath, Information assurance in sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA
Anand Srinivas , Eytan Modiano, Minimum energy disjoint path routing in wireless ad-hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, 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
Pierpaolo Bergamo , Alessandra Giovanardi , Andrea Travasoni , Daniela Maniezzo , Gianluca Mazzini , Michele Zorzi, Distributed power control for energy efficient routing in ad hoc networks, Wireless Networks, v.10 n.1, p.29-42, January 2004
Jian Li , Prasant Mohapatra, PANDA: a novel mechanism for flooding based route discovery in ad hoc networks, Wireless Networks, v.12 n.6, p.771-787, November 2006
routing;energy efficiency;ad-hoc networks