Advanced Wireless Networks - 4G Technologies

798 NETWORK INFORMATION THEORY

[37]A. Sendonaris, E. Erkip and B. Aazhang, Increasing uplink capacity via user cooperation diversity, Proc. IEEE Int. Symp. Inform. Theory, 2001, p. 156.

[38]J. Laneman and G. Wornell, Energy-efficient antenna sharing and relaying for wireless networks, Proc. IEEE Wireless Commun. Networking Conf., 2000, p. 294.

[39]J. Laneman, G.Wornell and D. Tse, An efficient protocol for realizing cooperative diversity in wireless networks, Proc. IEEE Int. Symp. Inform. Theory, 2001,

p.294.

[40]A. Scaglione and Y.W. Hong, Opportunistic large arrays: cooperative transmission in wireless multihop ad hoc networks to reach far distances, IEEE Trans. on Signal Process., vol. 51, no. 8, 2003, pp. 2082–2093.

[41]E.M. Royer and C.K. Toh, A review of current routing protocols for ad hoc mobile wireless networks, IEEE Person. Commun. Mag., vol. 6, 1999, pp. 46–55.

[42]Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen and J.-P. Sheu, The broadcast storm problem in a mobile ad hoc network, ACM Wireless Networks, vol. 8, 2002, pp. 153–167.

[43]W. Peng and X.-C. Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, in Proc. IEEE/ACM Mobile Ad Hoc Networking Computing, November 2000, pp. 129–130.

[44]B. Williams and T. Camp, Comparison of broadcasting techniques for mobile ad hoc networks, in Proc. ACM Int. Symp. Mobile Ad Hoc Networking Computing, June 2002.

[45]ANSI/IEEE Std 802.11, 1999 ed., Available at: http://standards.ieee.org/getieee802 /download /802.11–1999.pdf, 1999.

[46]Network Simulator – ns2. Available at: www.isi.edu/nsnam/ns/

[47]S.-Y. R. Li, R.W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inform. Theory, vol. 49, no. 2, February 2003, pp. 371–381.

[48]J.-H Chang, L. Tassiulas and F Rashid-Farrokhi, Joint transmitter receiver diversity for efficient space division multiaccess, IEEE Trans. Wireless Commun., vol. 1, 2002,

pp.16–27.

[49]F. Rashid-Fwrokhi, K.J.R. Liu, and L. Tassiulas, Transmit beamforming and power control for cellulw wireless systems, IEEE J. Select. Areas Commun., vol. 16, 1988,

pp.1437–1450.

[50]F. Rashid-Farrokhi, L. Tassiulas and K.J.R. Liu, Joint optimal power control and beamforming in wireless networks using antenna wrays, IEEE Trans. Commun., vol. 46, 1998, pp. 1313–1324.

[51]A. Cwleial, A case where interference does not reduce capacity, IEEE Trans. Inform. Theory, vol. IT-21, 1975, pp. 569–570.

[52]T. Cover and J. Thomas, Elements of Information Theory. Wiley: New York, 1991.

[53]G.G. Raleigh and V K. Jones, Multivariate modulation and coding for wireless communication, IEEE J. Select. Areas Commun., vol. 17, no. 5, 1999, pp. 851–866.

[54]M.C. Bromberg, Optimizing MIMO multipoint wireless networks assuming Gaussian other-user interference, IEEE Trans. Inform. Theory, vol. 49, no. 10, 2003, pp. 2352– 2362.

[55]M.C. Bromberg and B.G.Agee, Optimization of spatially adaptive reciprocal multipoint communication networks, IEEE Trans. Commun., vol. 51, no. 8, 2003, pp. 1254– 1257.

[56]J.-H Chang, L. Tassiulas and F Rashid-Farrokhi, Joint transmitter receiver diversity for efficient space division multiaccess, IEEE Trans. Wireless Commun., vol. 1, 2002,

pp.16–27.

REFERENCES 799

[57]F. Rashid-Farrokhi, L. Tassiulas and K.J.R. Liu, Joint optimal power control and beamforming in wireless networks using antenna wrays, IEEE Trans. Commun., vol. 46, 1998, pp. 1313–1324.

[58]H.E. Gamal, On the transport capacity of the many-to-one dense wireless network, IEEE Vehicular Technol. Conf., VTC 2003, vol. 5, 6–9 October 2003, pp. 2881–2885.

[59]A.D. Murugan, P.K. Gopala and H.E.Gamal, Correlated sources over wireless channels: cooperative source-channel coding, IEEE J. Select. Areas Commun., vol. 22, no. 6, 2004, pp. 988–998.

[60]T. J. Kwon, M.Gerla, V.K. Varma, M. Barton and T.R. Hsing. Efficient flooding with passive clustering-an overhead-free selective forward mechanism for ad hoc/sensor networks Proc. IEEE, vol. 91, no. 8, 2003, pp. 1210–1220.

[61]A. Sabharwal, On capacity of relay-assisted communication, in IEEE GLOBECOM’02, vol. 2, 17–21 November 2002, pp. 1244–1248.

[62]H.E. Gamal, On the scaling laws of dense wireless sensor networks: the data gathering channel, IEEE Trans. Inform. Theory, vol. 51, no. 3, 2005, pp. 1229–1234.

[63]D. Marco, E.J. Duarte-Melo, M. Liu and D.L. Neuhoff, On the many-to-one transport capacity of a dense wireless sensor network and the compressibility of its data, in Int. Workshop on Information Processing in Sensor Networks, Berkeley, CA, April 2003, pp.104–109.

[64]L. Tomba, Computation of the outage probability in rice fading radio channels, Eur. Trans. Telecommun., vol. 8, no. 2, 1997, pp. 127–134.

[65]I. Howitt and Y.M. Hawwar, Evaluation of outage probability due to cochannel interference in fading for a TDMA system with a beamformer, Proc. IEEE Vehicular Technology Conf., 1998, pp. 520–524.

20

Energy-efficient

Wireless Networks

20.1 ENERGY COST FUNCTION

In Chapter 5 we discussed the impact of MAC layer protocols on energy efficiency, including TCP controlled retransmissions. In this chapter, we extend this analysis to the network layer and focus on routing algorithms. We discuss how the error rate associated with a link affects the overall probability of reliable delivery, and consequently 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 Ti, j denote the transmission power and pi, j represent the packet error probability. Assuming that all packets are of a constant size, the energy involved in a packet transmission, Ei, j , is simply a fixed multiple of Ti, j .

Any signal transmitted is affected by two different factors: attenuation due to the medium, and interference with ambient noise at the receiver. The attenuation is proportional to DK , where D is the distance between the receiver and the transmitter. The bit error rate associated with a particular link is essentially a function of the ratio of the received signal power to the ambient noise. In the constant-power scenario, Ti, j is independent of the characteristics of

the link i, j and is a constant. In this case, a receiver located further away from a transmitter will suffer greater signal attenuation (proportional to DK ) and will, accordingly, be subject to a larger bit-error rate. In the variable-power scenario, a transmitter node adjusts Ti, 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. The minimum transmission power associated with a link of distance D in the variable-power scenario is Tm = Th × γ × DK , where γ is a constant and K is the coefficient of channel attenuation (K ≥ 2). Since Th is typically a technology-specific constant, we can see that the minimum transmission energy over such a link varies as Em (D) DK .

Advanced Wireless Networks: 4G Technologies Savo G. Glisic

C 2006 John Wiley & Sons, Ltd.

802 ENERGY-EFFICIENT WIRELESS NETWORKS

If links are considered error-free, then minimum hop paths are the most energy-efficient for the fixed-power case. Similarly, in the absence of transmission errors, paths with a large number of small hops are typically more energy efficient in the variable power case. However in the presence of link errors, none of the above choices may give optimal energy efficient paths. We now analyze the consequences of this behavior for the variable-power scenario and end-to-end (EER) and hop-by-hop (HHR) packet retransmission techniques. The analysis for the fixed-power scenario is simpler, and is a special case of the variable-power scenario. Energy consumption for additional signal processing in the transmitter/receiver (modulation/demodulation) will be neglected. Modification of the models to include these losses is straightforward.

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 Em , it is easy to see why breaking up a link of distance D into two shorter links of distance D1 and D2 such that D1 + D2 = D always reduces the total Em . To elaborate on this, let us consider communication between a sender (S) and a receiver (R) separated by a distance D. Let N represent the total number of hops between S and R, so that N − 1 represents the number of forwarding nodes i: i = {2, . . . , N }, with node i referring to the (i − 1)th intermediate hop in the forwarding path. Node 1 refers to S and node N + 1 refers to R. In this case, the total 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 N − 1 forwarding nodes is:

where Di, j refers to the distance between nodes i and j and α is a proportionality constant. To understand the tradeoffs associated with the choice of N − 1, we compute the lowest possible value of Et for any given layout of N − 1. Using very simple symmetry 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, Et is given by

N

Et = α DK /N K = α DK /N K −1

i=1

We now consider how the choice of N affects the probability of transmission errors and the consequent need for retransmissions. Clearly, increasing the number of intermediate hops increases 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 p = 1 − (1 − plink)N .

The number of transmissions (including retransmissions) necessary to ensure the successful transfer of a packet between S and D is then a geometrically distributed random variable X, such that Pr{X = k} = pk−1 × (1 − p), k. The mean number of individual packet transmissions for the successful transfer of a single packet is thus 1/(1 − p). Since each such transmission uses total energy Et given above, the total expected energy required in the reliable transmission of a single packet is given by:

By treating N as a continuous variable and differentiating, it follows that the optimal value of the number of hops, Nopt is given by:

The existence of the optimum value is demonstrated in Figure 20.1.

In the case of the HHR model, the number of transmissions on each link is independent of the other links and is geometrically distributed. The total energy cost for the HHR case with N intermediate nodes, with each hop being of distance D/N and having a link packet error rate of plink, is

In this case, it is easy to see that the total energy required always decreases with increasing N. One should be aware that in a practical system at some point when N is sufficiently large, the signal processing energy will become comparable with the energy spent for transmissions.

20.2 MINIMUM ENERGY ROUTING

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 associated with the corresponding nodes. 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. 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

804 ENERGY-EFFICIENT WIRELESS NETWORKS

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 Ei, j be the energy associated with the transmission of a packet over link li, j , and pi, j be the link packet error probability associated with that link. In the fixed-power scenario, Ei, j is independent of the link characteristics; in the variable-power scenario, Ei, 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 energy costs over each constituent link.

Choosing path P for communication between S and D implies that the total energy cost for HHR is

Choosing a minimum-cost path from node 1 to node N + 1 is thus equivalent to choosing the path P that minimizes Equation (20.5). It is thus easy to see that the corresponding link cost for link Li, j , denoted Ci, j , is given by Ci, j = Ei, j /(1 − pi, j ). Ad-hoc routing protocols, discussed in Chapter 13, such as AODV, DSR and TORA, can use this link cost to compute the appropriate energy-efficient routes. Some of the existing energy-efficient routing techniques, e.g. PARO, can also be easily adapted to use this new link cost formulation to compute minimum-energy routes. Thus, in such a modified version of the PARO algorithm, an intermediate node C would offer to interject itself between two nodes A and B if the sum of the link cost CA,C + CC,B was less than the ‘direct’ link cost CA,B .

In end-to-end retransmissions, 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 energy cost can be now expressed as:

Given this form, the total cost of the path cannot be expressed as a linear sum of individual link costs, thereby making the exact formulation inappropriate for traditional minimum-cost path computation algorithms. In [1] a heuristic cost function for a link, was suggested as

where L = 2, 3, . . . , and is chosen to be identical for all links. Clearly, if the exact path length is known and all nodes on the path have identical link error rates and transmission costs, L should be chosen equal to that path length. However, in accordance with current routing schemes, we require that a link should associate only a single link cost with itself, irrespective of the lengths of specific routing paths that pass through it. 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 is 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 “approximate” energy cost given by:

As before, protocols like AODV, DSR, TORA and PARO can use this new link cost function to make their routing decisions.

20.3 MAXIMIZING NETWORK LIFETIME

We now discuss how we can include the retransmission-aware formulation of the link cost in an algorithm, that attempts to increase the operational lifetime of multihop wireless networks. Unlike previous protocols, maximum reliable packet carrying capacity (MRPC) considers both the node characteristics (residual battery energy at the transmitting node) and the link characteristics (link distance and link error rates), while evaluating the suitability of alternative paths. Given the current battery power levels at the different nodes, MRPC selects a route that has the maximum reliable packet carrying capacity among all possible paths, assuming no other cross-traffic passes through the nodes on that path.

To formalize the algorithm, let us assume that the residual battery power at a certain instance of time at node i is Bi . As before, let the transmission energy required by node i to transmit a packet over link i, j to node j be Ei, j . Let the source and destination nodes for a specific session (route) be S and D respectively. If the route-selection algorithm then selects a path P from S to D that includes the link i, j , then the maximum number of packets that node i can forward over this link is clearly Bi /Ei, j . Accordingly, we can define a node-link metric, Mi, j for the link i, j as:

The key point in this formulation is that the cost metric includes both a node-specific parameter (the battery power) and a link-specific parameter (the packet transmission energy for reliable communication across the link). Clearly, the ‘lifetime’ of the chosen path P, defined by the maximum number of packets that may be potentially forwarded between S and D using path P, is determined by the weakest intermediate node – one with the smallest

The MRPC algorithm then selects the candidate route Pc that maximizes the ‘lifetime’ of communication between S and D. Formally, the chosen route is such that:

Given the cost and lifetime formulations for MRPC it is then easy to use a modified version of Dijkstra’s minimum cost algorithm for decentralized route computation.

To apply Dijkstra’s algorithm for determining the minimum-cost path, the distance metric from any node to the given destination should be defined as the value of P over the optimal path from that node to D. Now consider a node A that sees advertisements from its neighbors,

806 ENERGY-EFFICIENT WIRELESS NETWORKS

{X, Y, Z , . . .}, with corresponding distance metrics X , Y , Z , . . . for a given destination D. Node A can then compute the best path to D (using its optimal neighbor) by using the following simple algorithm:

(1)For each of the neighboring nodes ( j {X, Y, Z , . . .}), compute the link cost MA, j using Equation (20.8).

(2)For each of the neighboring nodes ( j {X, Y, Z , . . .}) compute the potential new

value of pot using pot(A, j) = min{MA, j , j }.

(3) Select as the next-hop neighbor towards D the node which results in the maximum

Using this recursive formulation allows all nodes in the ad hoc network to iteratively build their optimal route towards a specific destination D. The distance-vector formulation presented here can easily be incorporated in protocols, such as AODV, DSR and TORA, that are specifically designed for ad hoc mobile environments.

The basic MRPC formulation for power-aware routing does not need to specify the value of the transmission energy cost associated with a specific link. Note that Equation (20.8) is expressed as a function of a generic link cost Mi, j . Accordingly, by specifying different forms of Mi, j it is possible to tailor the MRPC mechanism for specific technologies and/or scenarios.

For the fixed-power scenario, the energy involved in a single packet transmission attempt, Ei, j , is a constant for all i, j and is independent of the distance between neighboring nodes i and j. For the variable-power scenario, Ei, j will typically be DiK, j , where Di, j is the distance between nodes i and j. A routing algorithm for reliable packet transfer should include the link’s packet error probability in formulating the transmission energy cost. By ignoring the packet error probability, the link cost concentrates (wrongly) only on the energy spent in transmitting a single packet. The correct metric is the effective packet transmission energy for reliable transmission, which includes the energy spent in one or more re-transmissions that might be necessary in the face of link errors. A transmission energy metric of the form Ci, j = Ei, j /(1 − pi, j )L was suggested, where pi, j is the link’s packet error probability, L ≥ 1. For hop-by-hop re-transmissions L should be chosen to be 1. In the absence of hop-by-hop re-transmissions (i.e. re-transmissions are only performed end- to-end), the transmission cost is well approximated by L [3, 5]. Power-aware routing has been studied in a number of papers [1–42].

The conditional MRPC (CMRPC) algorithm is the MRPC equivalent of the conditional min–max minimum battery cost routing (CMMBCR) algorithm presented in Toh et al. [2]. The CMMBCR algorithm is based on the observation that using residual battery energy as the sole metric throughout the lifetime of the ad hoc network can actually lower the overall lifetime, since it never attempts to minimize the total energy consumption. Accordingly, the CMMBCR algorithm uses regular minimum-energy routing as long as there is even one candidate path, where the remaining battery power level in all the constituent nodes lies above a specified threshold γ . When no such path exists, CMMBCR switches to MMBCR, i.e. it picks the path with the maximum residual capacity on the ‘critical node’.

The CMRPC algorithm differs from CMMBCR in that the cost-functions at all times include the link-specific parameters (e.g. error rates) as defined earlier in this chapter. The algorithm can thus be specified as follows. Let be the set of all possible paths between