SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION Power Aware Computing
This page intentionally left blank
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION Power Aware Computing
edited by
Ramesh Karri David Goodman Polytechnic University
KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
eBook ISBN: Print ISBN:
0-306-47720-3 1-4020-7204-X
©2002 Kluwer Academic Publishers New York, Boston, Dordrecht, London, Moscow Print ©2002 Kluwer Academic Publishers Dordrecht All rights reserved No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America Visit Kluwer Online at: and Kluwer's eBookstore at:
http://kluweronline.com http://ebooks.kluweronline.com
Contents
List of Figures
vii
List of Tables
xiii
Preface
xvii
1 TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION Elza Erkip, Xiaoan Lu, Yao Wang and David Goodman
1
2 ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS Khaled Arisha, Moustafa Youssef and Mohamed Younis
21
3 POWER AWARE PACKET ROUTING CONTROL IN AD-HOC WIRELESS NETWORKS Qilian Liang and Nancy Neigus
41
4 OPTIMAL NODE SCHEDULING FOR EFFECTIVE ENERGY 53 USAGE IN SENSOR NETWORKS Ankur Srivastava, Justin Sobaje, Miodrag Potkonjak and Majid Sarrafzadeh
vi
Contents
5 ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS Jennifer L. Wong, Giacamino Veltri and Miodrag Potkonjak
69
6 LOW-ENERGY SOFTWARE OPTIMIZATION FOR THE ARM7 PROCESSOR: THE SOFTWARE SCHEDULING APPROACH Giannis Sinevriotis and Thanos Stouraitis
87
7 POWER-AWARE EMBEDDED SYSTEM DESIGN USING THE MILAN FRAMEWORK Amol Bakshi, Jingzhao Ou and Viktor K. Prasanna
97
8 SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE 113 COMPUTATION IN WIRELESS NETWORKS Mitali Singh and Viktor K. Prasanna
9 OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS Ramesh Karri and Piyush Mishra
133
10 NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS Debashis Panigrahi, Sujit Dey, and Anand Raghunathan
153
11 INDIRECT HTTP: AN ENERGY EFFICIENT EXTENSION OF HYPERTEXT TRANSFER PROTOCOL FOR WEB BROWSING Jen-yi Pan, Wei-Tsong Lee and Nen-Fu Huang
173
References
187
Index
205
List of Figures
Figure 1-1. Minimizing total power for fixed end-to-end distortion.
3
Figure 1-2. Total power minimization for transform coding and AWGN channel at fixed distances. The powers are normalized to Numbers along curves (a) and (b) represent optimal compression rates R for a given N.
7
Figure 1-3. Total power minimization for transform coding and AWGN channel. The powers are normalized to Numbers along the curve represent power minimizing pairs (N,R) for a given distance.
8
Figure 1-4. Wireless video transmission system.
9
Figure 1-5. Power consumption for coding “foreman.qcif”, with a software implementation of the H.263 coder running on an IBM ThinkPad with a 360 MHz Pentium II processor. Scaling factor is taken to be 1.
13
Figure 1-6. Total power minimization for wireless video transmission for (a) when the mobile is close to the base station, (b) when the mobile is further away from the base station.
16
Figure 1-7. Total power minimization for wireless video transmission for hardware implementations. We show optimum power versus distance between the mobile and the base station. Channel burst length is 32.
17
Figure 1-8. Total power minimization for wireless video transmission for hardware implementations. We show optimum power versus
viii
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
distance between the mobile and the base station. Channel burst length is 8.
18
Figure 1-9. Total power minimization for wireless video transmission for software implementation. We show optimum power versus distance between the mobile and the base station. Channel burst length is 8.
18
Figure 2-1. Multi-gateway clustered sensor network.
23
Figure 2-2. MAC protocol time-based phases.
27
Figure 2-3. An example of slot assignment techniques.
31
Figure 2-4. Effect of buffer size on packet drop count.
34
Figure 2-5. Effect of buffer size on transmitter state change count.
34
Figure 2-6. Effect of buffer size on receiver state change count.
34
Figure 2-7. Effect of buffer size on node lifetime.
35
Figure 2-8. Effect of buffer size on end-to-end delay.
35
Figure 2-9. Effect of buffer size on throughput.
35
Figure 2-10. Effect of buffer size on energy per packet.
36
Figure 2-11. Effect on network lifetime.
38
Figure 2-12. Effect on power metrics.
38
Figure 2-13. Effect on throughput and delay metrics.
39
Figure 2-14. Time to network partition for routing algorithms.
39
Figure 2-15. Time for Last node to die under routing algorithms.
40
Figure 2-16. Comparing energy metrics among routing algorithms.
40
Figure 2-17. Throughput and delay for routing algorithms.
40
Figure 3-1. Structure of a fuzzy logic system.
43
Figure 3-2. MFs used to represent the linguistic labels: (a) MFs for antecedents, and (b) MFs for consequent.
48
Figure 3-3. The willingness of the node to forward this packet , versus (distance to the gateway or next node) and (size of incoming packet) when (a) and (b) and (c) and (d) and
49
List of Figures
ix
Figure 3-4. The decision boundary generated by the FLS based on (a) and (b) and (c) and (d) and
50
Figure 4-1. Abstraction of a sensor network.
57
Figure 4-2. Network transformation.
60
Figure 4-3. Probability of path existence.
64
Figure 4-4. Average number of nodes per path.
65
Figure 4-5. Maximizing path lifetime.
65
Figure 4-6. Maximizing temporal coverage.
66
Figure 4-7. Normal distribution.
67
Figure 4-8. A comparative study.
67
Figure 5-1. (a) Original Network. (b) Steiner Tree. (c) Path with Multicast considered.
72
Figure 5-2. Map of Minimum Cover Problem to Data Multicast in multi-hop networks.
78
Figure 5-3. (a) Example of the line-distance algorithm. (b) Example of first iteration. (c) Final solution found by the line-distance algorithm.
81
Figure 5-4. A multi-hop wireless network of 300 sensors with communication radius of 0.1 and 10 consumers.
84
Figure 5-5. A multi-hop wireless network of 300 sensors with communication radius of 0.1 and 10 consumers.
84
Figure 6-1. The scheduling process.
90
Figure 7-1. System design Y-Chart
100
Figure 7-2. Automatic Target Recognition application: Task graph.
103
Figure 7-3. The combined meta-model.
105
Figure 7-4. Resource model for the seven-node sensor network.
107
Figure 7-5. Multi-granularity simulation and automatic model refinement.
109
Figure 8-1. System-level energy model.
116
Figure 8-2. Design flow in MILAN.
121
Figure 8-3. Automatic Target Recognition (ATR).
122
x
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Figure 8-4. Energy analysis using data compression.
125
Figure 8-5. Rate 1/2 convolutional coding with Viterbi decoding on an AWGN channel with various convolutional code constraint lengths [TC].
126
Figure 8-6. Energy tradeoffs for FEC.
127
Figure 8-7. Energy dissipation in the system with
128
Figure 8-8. Energy dissipation in the system with
129
Figure 9-1. Energy consumed by a secure wireless session while transmitting 64 KB data over an 802.11 wireless channel using IPSec.
134
Figure 9-2. Messages exchanged by IPSec session negotiation during first SA negotiation.
137
Figure 9-3. Messages exchanged by IPSec session negotiation during IPSec SA negotiation.
138
Figure 9-4. Mobile test bed measurements.
139
for performance
and energy
Figure 9-5. Energy consumed by SHA-256 MAC.
140
Figure 10-1. Palm.Net wireless environment and experimental set-up for energy measurements.
156
Figure 10-2. An example current waveform.
157
Figure 10-3. Effect of signal strength on energy consumption.
159
Figure 10-4. Symbolic current consumption waveform for PalmVII handheld
160
Figure 10-5. Energy model for wireless web access using the PalmVII handheld.
161
Figure 10-6. Comparison between energy measured and estimated.
163
Figure 10-7. An example Web Flow Graph (WFG).
165
Figure 10-8. Design methodology for energy efficient content transformation
166
Figure 10-9. Transformed Web Flow Graphs from the example of Figure 6 under different channel conditions.
170
Figure 11-1. The scenario of a persistent HTTP connection.
176
List of Figures
xi
Figure 11-2. The scenario of pipelining in one connection.
177
Figure 11-3. The scenario of HTTP operation when a web proxy is between the web client and the web server.
178
Figure 11-4. The scenario of proposed extension of HTTP.
179
Figure 11-5. Factor of power reduction PR as a function of the nonvaried fraction of power consumption and the ratio of the mean transmission time of WAN to the mean transmission time on the air.
184
This page intentionally left blank
List of Tables
Table 1-1. Parameters for the source encoder power consumption
13
Table 2-1. Description of MAC protocol phases.
28
Table 2-2. Description of various packet types.
29
Table 3-1. Rules for power aware packet routing control: Antecedent 1 is the remaining battery capacity, Antecedent 2 is the packet loss requirement, and Consequent is the willingness of the node to forward this packet.
46
Table 3-2. Rules for power aware packet routing control: Antecedent 3 is distance to the gateway or next node, Antecedent 4 is the size of incoming packet, and Consequent is the willingness of the node to forward this packet.
46
Table 5-1. Line-directed node selection heuristic.
79
Table 5-2. Selected experimental results for the line-directed algorithm.
83
Table 6-1. Example of code dependence analysis.
91
Table 6-2. Iterations of the list scheduling algorithm.
93
Table 6-3. Example of the application of the list scheduling algorithm.
93
Table 6-4. Impact of register renaming on estimated percent energy savings.
94
Table 6-5. Estimated versus actual percent energy savings on the 802.11 protocol.
94
xiv
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Table 7-1. Configurable model attributes.
107
Table 8-1. SA1100 power measurements [JT].
117
Table 8-2. Power dissipation in memory.
118
Table 8-3. Power dissipation by WaveLAN cards.
119
Table 8-4. Sample model parameters.
120
Table 8-5. Parameter refinement using JouleTrack [JT] simulations.
124
Table 9-1. Power consumed by 11 Mbps Spectrum24® LA-4121 WLAN card.
139
Table 9-2. Energy consumed by AES key-schedule and data encryption.
141
Table 9-3. Energy consumed by IPSec mutual authentication and parameter negotiation.
141
Table 9-4. Energy consumed by IPSec key exchange.
142
Table 9-5. Energy consumed by IPSec SA establishment.
142
Table 9-6. Energy consumed by IPSec session negotiation protocols.
143
Table 9-7. Energy consumed by secure wireless data transmission.
144
Table 9-8. Energy consumed by DEFLATE compression.
145
Table 9-9. Energy saved by compressing the session negotiation protocol messages.
146
Table 9-10. Energy consumed during a secure wireless data communication.
146
Table 9-11. Energy consumed by variants of IPSec secure session negotiation protocol.
147
Table 9-12. Energy saved by the choice of key exchange and management protocols.
149
Table 9-13. Energy saved by choice of data encryption mechanism.
149
Table 9-14. Performance characteristics of optimized software implementations of AES encryption as a function of the user key size.
149
Table 9-15. Improving the secure session energy consumption at various security levels.
151
List of Tables
xv
Table 9-16. Energy savings for the client due to secure session optimization.
151
Table 10-1. Validation of the proposed energy model.
162
Table 10-2. Effect of the merging transformation on energy consumption.
168
Table 10-3. Effect of the deletion transformation on energy and quality of content.
169
Table 10-4. Effect of the migration technique on energy consumption.
169
This page intentionally left blank
Preface
Hundreds of millions of owners of digital cameras, camcorders, personal digital assistants, notebook computers, and cell phones are acutely aware that conservation of battery energy is a major challenge in portable information devices. Under the heading of wireless Internet, almost every day brings news of a new item on the market that merges two or more of these devices. With this convergence, energy management is becoming critical and complex particularly when integrating video signal processing with mobile communications and networking. This book will focus on emerging issues in integrated energy management in portable multimedia communications devices beyond lowpower electronic design by identifying some hooks and controls that are required at various levels. Specifically, the book is a compilation of system level power management approaches including theoretical and simulation studies, field measurements, algorithm development and experimental test beds related to low power computing, mobile communication and networking. Finally, the book addresses integrative power optimization studies that jointly consider computing, communications and networking. Each chapter is the work of two or more experts in one of the diverse set of subject areas that are relevant to power aware computing and communications. The chapters reflect four clusters of work: theoretical studies, work related to networks of sensors, techniques for optimizing hardware and software design, and application-level issues. Chapter 1 describes power optimization problem for wireless multimedia communication by considering power consumption of a mobile transmitter due to compression, channel coding and transmission subject to a fixed endto-end source distortion. The power optimization approaches described in
xviii
this chapter are then validated both on an abstract class of sources and channels and on a realistic H.263 video transmission system through a wireless channel. Networking isolated and disposable sensors is expected to have a significant impact on the efficiency of many emerging military and commercial applications. The next four chapters address a variety of important issues in networks of such energy constrained, disposable sensors. Firstly, chapter 2 presents an approach that maximizes the lifetime of the sensors while maintaining a minimum level of desired quality of service by the sensor nodes while delivering the collected data. The approach dynamically sets routes and arbitrates medium access to minimize energy consumption and maximize sensor life. Then in Chapter 3 the effectiveness of controlling packet routing in ad hoc wireless sensor networks is demonstrated by explicitly considering the remaining battery capacity in conjunction with packet loss requirement, distance to the gateway or next node, and size of incoming packet. Chapter 4 addresses the impact of node scheduling for a minimum degree of coverage towards the overall energy consumption. Finally, Chapter 5 considers energy-efficient data multicast in multi-hop wireless sensor networks. In a multi-hop wireless sensor network each sensor communicates only with a few closely positioned neighbour sensors using low power communication schemes. In this chapter, the problem of minimizing the energy consumed during multicasting of data to all consuming nodes that requested it is formulated, solved and verified via extensive simulation studies. The next three chapters focus on software, hardware and embedded system design optimization techniques. Chapter 6 presents list-scheduling based instruction scheduling technique for optimizing the energy consumed by software executing on an ARM7 Processor. The technique explicitly considers inter-instruction energy costs caused by the switching activity in the processor circuit. Chapter 7 describes an integrated embedded system design and simulation framework MILAN targeting low-power, highperformance embedded systems. This chapter describes the use of the multiaspect modeling and simulation capabilities of MILAN for power-aware design of a class of distributed sensor networks. Finally, Chapter 8 discusses a system-level model for estimating the energy dissipation in collaborative and distributed wireless networks and studies the effect of various energy reduction techniques on the Automatic Target Recognition problem in a wireless environment. Finally, Chapters 9-11 focus on energy management at the application level. Chapter 9 studies the energy vs. security vs. performance trade-offs at the high-level by explicitly considering the IPSec security protocol using techniques based on information compression, session negotiation protocol
xix
optimization and choice of cryptographic primitives. Chapter 10 describes techniques to shape the content delivered to mobile clients by modifying and organizing the content depending on current wireless channel conditions and access patterns of users. Towards this end an energy model for wireless web access in terms of various application level parameters, such as bytes transferred, compression, encryption, received signal strength, network load, and error control techniques etc is developed and used. Finally, chapter 11 describes an energy efficient extension of hypertext transfer protocol for web browsing. This book evolved out of a workshop on Power Aware Computing, Communications and Networking (IMPACCT 2002) organized at the International Conference on Communications (ICC 2002). We thank Dr. Mark Karol, the General Chair, Dr. Malathi Veeraraghavan, and the ICC 2002 organizing committee and Mr. Robert Graybill, DARPA for their support of this project. We acknowledge the active contribution of Dr. Petteri Alinikula, Nokia and Prof. Sujit Dey, University of California, San Diego and all the referees that provided valuable feedback to the authors. We would like to thank Mr. Piyush Mishra, Graduate Research Fellow in the Department of ECE, Polytechnic University, for his help in putting together this final document. Finally, and most importantly, we thank Alex Greene and his editorial team at Kluwer for their support during all stages of this project. We acknowledge the support of New York State Wireless Internet Center for Advanced Technology (WICAT). Ramesh Karri David J. Goodman
This page intentionally left blank
Chapter 1 TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Elza Erkip, Xiaoan Lu, Yao Wang and David Goodman Department of Electrical and Computer Engineering Polytechnic University, Brooklyn, New York
Abstract:
In this work we provide tools for optimizing total power consumption of a mobile transmitter due to compression, channel coding and transmission subject to a fixed end-to-end source distortion. We show that the best coding and transmission strategy depends on the channel quality and that optimizing can prolong the battery considerably. We illustrate our approach both on an abstract class of sources and channels and on a realistic H.263 video transmission system through a wireless channel.
Key words:
Power optimization, H.263, Wireless multimedia communications.
1.
INTRODUCTION
Efficient use of the limited battery energy is one of the major challenges in portable information devices. Management of energy becomes even more critical with devices integrating complex video signal processing techniques with communications. Some of the key technologies that affect the battery life in this respect are source signal compression, channel error control coding and radio transmission. Classically, source and channel coding literature and in particular joint source and channel coding techniques mainly focus on designing codes that minimize the overall distortion of the source as it travels through the channel. However, for mobile units that have limited battery capacities, overall energy consumption is also an important design factor. On the other hand, the work on improving the battery life has focused on separate
2
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
components such as algorithms and hardware design for specific video and channel coders and low power transmitter design. Joint optimization of source compression, channel coding and transmission to balance the quality of service and energy requirements of the mobile has only recently attracted interest. In [LT98], the authors found that, by judiciously selecting operating modes of the H.263 video coder in response to mobile environment, low power consumption can be achieved while maintaining a good video quality level. The work by Appadwedula et. al. considers the minimization of the total energy of a wireless image transmission system by dynamically reconfiguring the architecture. Our previous work recognized that the optimum operating points of source coding and transmit energy depend on the mobile unit’s location. We considered transform coding on first order Markov sources and we modelled the channel error by the additive white Gaussian noise. In this work we incorporate the power consumption due to transmission and due to signal processing, which includes source and channel coding, and provide tools to calculate efficient operating points. Our goal is to allocate power between source compression, channel coding and transmission tasks to minimize the total power dissipation while keeping the end-to-end distortion of the source constant. We only concentrate on total transmitter power, envisioning a situation such as uplink cellular communications where the base station receiver does not have power limitations. Similarly, for the downlink scenario the goal would be to minimize the receiver power consumption. For peer-to-peer communication situations such as ad-hoc networks or cellular networks when the base station does not do transcoding, one would optimize over both the transmitter and receiver energy levels. We consider two scenarios: In the first one, we have an abstract class of sources and channels and we uncover some of the basic principles of power optimization. As an example we consider a first order Gauss-Markov source transmitted over an additive white Gaussian noise channel. There is no channel coding and the source compression is done via transform coding. We illustrate how the minimum total power varies with channel quality of the mobile, or its distance from the base station, and how this power is allocated among signal processing and transmission. We argue that when the channel quality is bad, high compression efficiency or low compressed data rate is preferred. These results are presented in Section 2. The second scenario considers a practical wireless video communication system that uses the standard H.263 video codec [IT] and the Reed-Solomon (RS) channel codec. The channel is characterized by the widely used twostate Markov model [GI60]. We develop a simple model for the power consumption of the H.263 source encoder and validate our model through
TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
3
measurements. We then use this model to study how power can optimally be distributed among the video coder, RS coder and the transmitter for fixed total distortion and how the optimization is affected by channel conditions. Our results are presented in Section 3.
2.
POWER OPTIMIZATION FOR ABSTRACT SOURCES AND CHANNELS
In this section we consider a simple case in which we ignore the power consumption due to channel coding and we send compressed bits through an additive white Gaussian noise (AWGN) channel. We assume we have access to a number of source compression techniques which provide the same source distortion with varying complexity and rate. Hence if we consider the source distortion due to compression versus the compressed bit rate, we move along the horizontal line shown in Figure 1-1(a). We have also plotted the operational rate-distortion curve as a reference.
4
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
The total power consumed by the mobile at the link layer and at the physical layer consists of the energy dissipated by the source compressor and the energy used to transmit the compressed bits though the channel resulting in total power watts. Our goal is to solve the problem
where refers to the total distortion due to source compression and channel errors. Total allowed distortion will be determined by the particular source and application at hand and will be different for telephone calls and video conferencing. To gain insight into the solution, let us first consider a special case where we fix source distortion and channel error rate individually. Generally algorithms that compress more, resulting in a lower compressed rate for identical “quality” have higher complexity and require more processing power. Hence for fixed source distortion in Figure 1-1 (a), the processing power is a decreasing function of the compressed bit rate R shown in Figure 1-1(b). On the other hand, as the number of bits representing a source letter increases to keep the bit error rate of the channel constant, we need higher transmission power as in Figure l-l(c). Combining in Figure l-l(d), we find that the total power as a function of the bit rate has a minimum and the optimal operating point R* that minimizes for fixed end-to-end source distortion can be calculated. As an example of this optimization we consider a class of transform coders of varying dimension N and squared error distortion function. In such a coder, using a longer block length N can increase the coding efficiency, at the expense of more computational power. Also, the compressed bit stream becomes more error prone as N increases, thus requiring a higher transmit energy per bit to maintain the same distortion due to transmission errors. Therefore, an intermediate value of N is likely to be best, depending on the actual channel condition. We consider a first order Gauss-Markov source with variance and autocorrelation function We assume the source is sampled at a rate of samples/second. The operational distortion-rate function of a transform coder using the optimal transform of dimension N is
TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
5
where depends on the quantizer used for the transform coefficients [GG92]. Note that R is the number of bits/sample and D(R) is the distortion per source sample. We assume these compressed bits are transmitted through an AWGN channel of noise spectral density joules using differential phase shift keying (DPSK). The probability of bit error is given by [PR01a]
, where is the received power in watts. Considering only path loss, the radiated power at the transmitter is where d is the distance between the mobile and the receiver and the exponent depends on the propagation medium. We will assume the total power consumption at the mobile due to transmission is where is a scaling factor that is device and implementation specific and includes the power used for modulation and amplification. Since our source is compressed using transform coding of dimension N, we will assume that N source samples (which we call a “symbol”) are received correctly only when all the NR bits describing the vector are correct at the receiver. This results in the probability of symbol error
From (4), we see that when the bit error rate is the same, the symbol error rate increases with N, which means that the compressed bit stream is more sensitive to transmission errors. Combining the effects of the source compression and channel errors, the total end-to-end distortion per source vector of length N can be expressed as which results in per source sample distortion
Let us now turn to the calculation of total power Transforming a source vector of dimension N requires operations. Typically the number of operations necessary for the quantizer and the entropy coder following the transform is negligible with respect to Assuming the energy dissipated is proportional to complexity, with proportionality
6
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
constant the power requirement of the source coder is Using equations (2), (3), (4) and (5), the received power required to keep the total distortion at level is given by with and
Combining, the total power due to signal processing and transmission is
and the optimization in equation (1) can be carried out with respect to transform coder dimension N and compression rate R. In our formulation, the value of the constants and are device and implementation specific and can be determined experimentally. We illustrate the results for and total distortion in Figure 1-2. Note that corresponds to a SNR value of 10 dB for the source. We have plotted both the total power and transmit power as a function of the transform coding dimension N. For each N, the rate R is chosen so that The block size N that minimizes total power is denoted by a star. All the powers are in watts and normalized with respect to the constant Experiments [OH00] suggest that and are comparable, so we have chosen in the range 10-0.1. In Figure l-2(a), we consider modelling a scenario in which the mobile is close to the base station, or equivalently channel attenuation is low. We observe that as the transform coding dimension N increases the total power and signal processing power, which is the difference between total power and transmit power, increases. The optimal N in this case is equal to 1 and results in source coding rate R = 2 bits/sample. Hence for good channel conditions, one does not need to spend a lot of power compressing the source; low attenuation enables more source bits to be transmitted through the channel. Figure l-2(b) shows total power and transmit power for where now the mobile is far away from the base station. The optimum source coding dimension N is 5 and the corresponding rate R is 0.8. Since the channel attenuation is high, we need to compress the source symbols
TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
7
more to send them reliably through the channel, as it is relatively expensive to send each bit. The level of compression to minimize total power consumption is therefore location dependent.
8
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Figure 1-3 summarizes minimum total power consumption as a function of the distance of the mobile from the base station. This optimization requires that the compression and transmission strategies be adapted to the distance. On the same plot we also show two scenarios in which not only the overall distortion is kept constant at but the compression algorithm is also fixed. Then in order to keep the channel error rate constant transmit power increases with distance. As expected, fixed high compression rate (R = 2) performs well for small distances, but requires considerably more total power, a factor of 2, than the optimized case for large distances. Conversely, a low compression rate algorithm (R = 0.7 ) is better suited for large distances, and the total power dissipation is almost 10 times larger than the optimized scenario for small distances from the base station.
3.
POWER OPTIMIZATION FOR WIRELESS VIDEO TRANSMISSION
In this section we extend our results to a practical scenario and consider a video signal compressed by H.263 encoder, channel coded using an RS code and transmitted over a wireless channel. We use a two-state Markov channel to model the wireless medium and assume DPSK is the modulation scheme. A block diagram of the system is illustrated in Figure 1-4.
TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
9
The distortion and power consumption of the H.263 encoder are described by which depend on the INTRA rate and the encoding rate The channel has two states, good (State G) and bad (State B), and is described by (the probability that a symbol is at state B), (transition probability from State B to G), and (noise powers at State B and G respectively). The power consumed by the RS(n,k) channel coder is given by where r = k/n is the channel code rate. The transmission power is where is the radiated energy per transmitted bit. The distortion at the video decoder caused by transmission errors is described by where is the residual symbol error rate after channel decoding. The overall distortion and power consumption are denoted by and respectively. Similar to Section 2, our goal is to minimize subject to an upper bound on We first discuss the parameters that lead to the overall distortion. Power consumption models will be discussed in the next subsection.
3.1
Distortion models
3.1.1
Rate-distortion performance of the source encoder
Stuhlmüller et al. derived a rate distortion model for an H.263 compliant coder based on simulation data. The INTRA update scheme forces a macroblock to be coded in the INTRA-mode after every T –1 macroblocks. The distortion model derived in is:
10
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
where is the INTRA rate, is the encoding bit rate in kbits/second and is the distortion in terms of the mean square error (MSE) per source sample. The parameters and depend on the video sequences as well as the INTRA rate and are given by
, where specific video sequences.
3.1.2
are model parameters depending on
Two-state Markov channel
In order to describe the wireless channel, we use the well-known twostate Markov model. The two states are denoted as good (G) and bad (B) states. We assume that the channel stays at a state for one symbol, which consists of m bits. The transition probability at the symbol level from State B to G is The probability that one symbol is at State B is We use binary DPSK modulation. Hence, the probability of bit error is as in (3), where is the received energy per bit and is the noise power spectral density. Similar to Section 2, the received energy is related to the radiated energy as where d denotes the distance between the mobile and the receiver. Assuming the noise power spectral densities at State G and State B are and respectively, we get bit error rates for the good and the bad states in terms of the radiated energy/bit
TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION 3.1.3
11
Error rate of the channel code
The RS(n, k) channel code converts every k information symbols into an n-symbol block by appending n – k parity symbols. We assume each symbol consists of m bits. Any error pattern with less than symbol errors can be corrected. The influence of transmission errors using the RS code is described by the residual symbol error rate which is the probability that a block cannot be corrected after the channel decoder. It can be calculated as:
where the block error density denotes the probability of k symbol errors within a block of n symbols and depends on the parameters of the Markov channel the distance d between mobile and receiver and the radiated energy per bit The derivation of can be found in [BF92]. 3.1.4
Distortion at the video decoder
While motion compensation yields significant gains in coding efficiency, any residual transmission error will cause interframe error propagation. Hence increasing intra frame rate also increases the error resilience of the video coder. Stuhlmüller et al. proposed a model for distortion introduced by transmission errors as
where leakage describes the efficiency of loop filtering to remove the introduced error, and describes the sensitivity of the video decoder to an increase in error rate. These parameters are sequence specific and are derived in The overall distortion at the video decoder is then given by
12
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
3.2
Power consumption models and measurements
3.2.1
Power consumption of the source encoder
One of our main contributions is the derivation and validation of the H.263 video coder power consumption. We derive the power consumption model of the H.263 encoder based on several assumptions. For an INTRA macroblock, we model the energy consumption by where denotes the expense for computing DCT, and for quantization and variable length coding (VLC). For a macroblock coded in INTER mode, the energy expense is modelled by where denotes the energy used for motion estimation. We assume are constants. While the number of computations, and hence energy for quantization is independent of the bit rate, with small quantization step size, we need more computation for VLC due to the increased number of nonzero coefficients. Hence we assume is proportional to and can be written as Then, the average power consumption is:
, where is a scaling factor which depends on the actual implementation of the coder, is the frame rate and is the number of macroblocks in one frame. The source encoder power consumption in (12) can also be written as
, where and As expected, when increases, i.e., less motion compensation is conducted, less power is necessary; when increases, more power is consumed in VLC. In order to validate the above model and find constants and we carried out some power measurement experiments of a software implementation of H.263 video coder running on an IBM ThinkPad with a 360 MHz Pentium II microprocessor. We used an oscilloscope for our measurements.
TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
13
Figure 1-5 shows the results of these measurements for the sequence “foreman. qcif”. Note that different implementations will affect the scaling factor and hence the scale of the vertical axis.
Assuming we derived constants and as shown in Table 1-1. We observe that the power consumption models fit the data reasonably well. Also is small compared to and thus limiting the effect of on the source power consumption.
3.2.2
Power consumption of the channel encoder
Based on the number of computations, the power consumption of an (n, k) Reed-Solomon encoder is modelled in and is given as
14
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
, where is a scaling factor that depends on the actual implementation. Thus, the power consumption of the RS encoder acting on a compressed stream with bit rate bits/second is
3.2.3
Power consumption of the transmitter
Let represent the radiated energy per bit at the transmitter antenna. The total transmission power is then given by
where is the total bit rate, and is a scaling factor that translates the radiated energy into the actual power consumption for transmission (including modulation and signal amplifiers) in a wireless device.
3.3
Power optimization and allocation
Combining the effects of source quantization and transmission error, the total end-to-end distortion can be expressed as
The total power consumed by the transmitting mobile device consists of power dissipated by the source encoder, the channel encoder and transmitter. Therefore
For a given channel environment, the power allocation problem is now to find the best set of parameters (r, ) so that is minimized subject to
TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION 3.3.1
15
Choice of parameters
We set the total allowed distortion to be for a video source. This corresponds to PSNR=30.38 dB, which indicates good but not excellent video quality. The probability of channel being in the bad state is 1 %, each symbol in the RS coder is represented by m = 8 bits and the block length for the RS code is n = 222 symbols. Noise power spectral density in the bad state is assumed to be thus the SNR in the bad state is 10 dB less than the SNR in the good state. We would like to investigate the effect of different noise levels on the level of compression and channel coding. Similar to Section 2, we can interpret varying noise levels in terms of the distance of the mobile from the receiver. We have taken the propagation constant as 4. We will also investigate the effect of the burst length on the optimization problem. We choose to model a fast varying environment and for a slowly varying channel. Our optimization is over the channel code rate r, H.263 INTRA rate source compression rate and energy per bit at the transmitter. The channel code rate r can take values r =(0.18, 0.27, 0.36, 0.45, 0.55, 0.64, 0.73, 0.82, 0.91), which corresponds to k = rn = (40, 60, 80, 100, 122, 142, 162, 182, 202) information symbols for the RS code with block length n = 222 . We refresh I-mode of the video coder every T macroblocks with T = (33, 25, 16, 12, 9, 5, 3, 2) resulting in The remaining parameters and are chosen to satisfy the distortion constraint. The scaling factors and can affect the optimization results significantly. It is known that in today’s wireless devices, the power consumptions by base-band signal processing and by transmission are roughly the same [OH00] and the power consumption by the channel coder is negligible compared to source coding. Therefore, we choose so that and are on the same order of magnitude, and we choose so that is much smaller than and While the above assumption holds for a hardware implementation, to model a software implemented source and channel code which consumes significantly more power, we also consider larger values of and in our simulations. 3.3.2
Results
We illustrate some of our numerical simulation results for optimal power allocation in Figure 1-6. We assume a hardware implementation. In Figure l-6(a), we consider a small distance between the mobile and the receiver, modelling a scenario in which the channel quality is good. The burst length
16
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
is 32. Figure l-6(b) shows the total power and transmit power for a larger distance, hence larger noise power. Each point in the solid curve is obtained by fixing (equivalently fixing the transmit signal to noise ratio in State G), and finding the parameters r , that minimize the total power consumption while reaching the desired Comparing Figures 16(a) and l-6(b), we see that when the distance increases, the optimal strategy uses higher SNR to guarantee the same total distortion, resulting in higher total power consumption. Also, similar to the abstract scenario of Section 2, transmission uses significantly more power than signal processing (source and channel coding) for large distances.
TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
17
Figure 1-7 summarizes the minimum total power consumption as a function of distance. Each point in the solid curve represents the combination of ( r , that yields the lowest for the given distance. We observe that at large distances, the trend is the same as the abstract scenario of Section 2. Since transmission power is dominant, we would like to send fewer bits and have more error correction. This forces the video coder to decrease and and the channel coder to add more redundancy by decreasing r. However, this trend is reversed for small distances. Now source coding is more costly in terms of power. Since is the dominant factor in the compression power, the optimization keeps it at the largest value of 0.5. This in return forces to slightly increase with distance to ensure the distortion constraint. Figure 1-7 also illustrates the power consumption of two scenarios in which ( r , are fixed and only is allowed to vary to keep the total distortion constant at As expected, fixed high performs well when the mobile is close to the base station. The reverse is true for small Optimization indeed can reduce the total power consumption considerably.
Figure 1-8 shows minimum power consumption versus distance for a smaller burst length of Same observations as above can be made about the effect of compression and channel coding on the total power consumption. Comparison of Figure 1-7 with Figure 1-8 suggests that for larger burst lengths, one needs to operate at a larger to gain more error
18
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
resilience from the source coder. As expected, total power consumption increases with burst length since the channel stays in the bad state longer.
We have also carried out simulations for larger constants and to model software based coding and compression system. Our results are shown in Figure 1 -9 for about We have
TOTAL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
19
Comparing Figure 1-9 with Figure 1-8 we observe that since compression is more costly, we now need more INTRA macroblocks to reduce compression power, resulting in higher This results in higher error resilience in the source coder and enables the channel code rate r to increase. The total power consumption is higher than the hardware implementation and is more pronounced for small distances where signal processing power dominates.
4.
CONCLUSION AND FUTURE WORK
This research provides a framework for optimizing the total power consumption of a mobile transmitter subject to a given end-to-end distortion. The total power incorporates the source compressor, channel coder and transmitter power. We investigate two scenarios: An abstract class of sources and channels (Gauss-Markov source transmitted over an AWGN channel) and a practical H.263 wireless video transmission. For both system models, we observe that optimum distortion-power operating points are dependent on the distance of the mobile from the base station. For large distances since transmission of each bit is costly, one needs a highly compressed bit stream. These highly compressed bits are more error prone, so stronger channel codes are needed for proper error control. Through simulations, we have illustrated the effect of implementation platform and channel burst length on the level of compression and channel coding. Although this chapter mainly focused on transmit power, other scenarios include optimizing the receiver power consumption (for cellular downlink) or optimizing transmit and receive energies jointly (for peer-to-peer communications, or for no base station transcoding). At the transmitter the source coder dissipates most of the signal processing power, whereas at the receiver channel decoder is the bottleneck. Another possible extension is to multiuser scenarios, where interference from nearby users affects the channel error rate of the mobile and one needs to jointly optimize the total powers of all the users.
ACKNOWLEDGMENT The authors would like to thank Ramesh Karri and Piyush Mishra for their help in measuring the power consumption of the source encoder.
This page intentionally left blank
Chapter 2 ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
Khaled Arisha, Moustafa Youssef* and Mohamed Younis** 1 Honeywell International Inc. Advanced Systems Technology Group 7000 Columbia Gateway Drive, Columbia, MD 21046 *Department of Computer Science University of Maryland at College Park College Park, MD 20742 **Department of Computer Science and Electrical Engineering University of Maryland at Baltimore County 1000 Hilltop Circle, Baltimore, MD 21250
Abstract:
Networking unattended sensors is expected to have a significant impact on the efficiency of many military and civil applications. Sensors in such systems are typically disposable and expected to last until their energy drains. Therefore, energy is a very scarce resource for such sensor systems and has to be managed wisely in order to extend the life of the sensors for the duration of a particular mission. In this chapter, we present a novel approach for energyaware management of sensor networks that maximizes the lifetime of the sensors while maintaining desired quality of service attributes related to sensed data delivery. The approach is to dynamically set routes and arbitrate medium access to minimize energy consumption and maximize sensor life. We give a brief overview of the energy-aware routing and a description of a TimeDivision-Multiple-Access (TDMA) -based Medium Access Control (MAC) protocol. We discuss algorithms for assigning time slots for the communicating sensor nodes. The approach is evaluated through simulation. Simulation results have confirmed the effectiveness of our new approach.
Key words:
Medium Access Control (MAC) protocols, Sensor networks, Energy-aware routing, Time Division Multiple Access (TDMA).
1
Work has been partially done while the authors were at Honeywell International Inc.
22
1.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
INTRODUCTION
Sensor networks have recently attracted significant attention for many military and civil applications, such as target tracking, surveillance and security management. Sensors monitor events in a surveillance area and observed data are collected and analyzed. Examples of sensor deployment organization for a target-tracking oriented mission can be found in B198]. Sensors have limited energy resources and their functionality continues until their energy drains. Therefore, energy resources for sensor networks should be managed wisely to extend the lifetime of sensors. The sensing element of a sensor probes the surrounding environment. After performing signal processing of the observed data, sensors communicate this data, typically using a radio-based short-haul links, to a command center usually through a relay or a data concentrator called the gateway. Gateways fuse collected data and send it to the command node for further analysis. Sensors cannot be active all the time, since signal processing and communication circuits can consume most of its energy, thus shortening the lifetime of the sensor network. Energy-aware network management is highly critical to maintain a longer lifetime while still performing its task within an acceptable level of quality. Due to scalability requirements and to avoid overloading the gateways, network clustering is recommended through the involvement of multiple gateways, as shown in Figure 2-1. Clusters are formed such that its gateway is located within the communication range of all of its cluster sensors. Gateways use long-haul communication to send reports fused from its cluster sensor data to other gateways, and eventually to the command node. Clustering, Inter-gateway communication, data fusion and task allocation are beyond the scope of this chapter. Sensors are assumed to be capable of operating in an active mode or a low-power standby mode. The sensing circuits as well as radio transmitters and receivers can be turned on and off independently. Transmission power can be adjusted based on the required range. Sensors can act as store-andforward relay nodes. We assume the on-board clocks of both the sensors and gateways are synchronized. Clock synchronization can be achieved via the use of GPS or through the exchange of synchronization messages [ST87]. This assumption is justified since such capabilities are typically implemented in advanced sensors, e.g. the Acoustic Ballistic Module from SenTech Inc. [AB]. Gateways are responsible of the dynamic configuration of the sensor network within its cluster.
ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
1.1
23
Related Work
In wired and inherently wireless networks, the emphasis has traditionally been on the optimization of throughput and end-to-end delay. Only recently energy efficiency has received attention due to advances in wireless networks. Generally energy efficiency can be achieved at various layers of the communication protocol stack. The bulk of energy-related research has focused on the hardware level, for example [HS00a]. Due to fundamental physical limitations, the focus has recently shifted to architectural and software levels. Given the scope of this chapter we will limit the discussion to data link layer and network layer protocols. Energy-aware routing has started to receive attention in the recent few years, motivated by advances in wireless mobile devices. A comparison between direct routing and minimum energy routing has been conducted in Other comparison between different energy-aware routing protocols is given by Toh in [TO01]. The trade-off between extending lifetime and fair usage of sensors is analyzed in [CT00]. A position-based minimum energy network is proposed in [RM99]. A signalling channel is used in [SR98a] to intelligently turn off nodes that are not active; however nodes use a complex probe mechanism. Store-and-forward schemes of wireless networks, such as IEEE 802.11, have a sleep mode in which nodes are turned off XS01]. A power-aware Time Division Multiple Access (TDMA) Medium Access Control (MAC) protocol that coordinates the delivery of data to receivers based on the base station control is given in [HS00b]. There are three phases in this TDMA: up-link phase in which nodes transmit data to the base station, down-link phase in which the base station transmits data to the nodes, and reservation phase in which nodes request new connections.
24
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
The base station dictates a frame structure within its range. A frame consists of a number of data cells and a traffic control cell. Nodes with scheduled traffic are indicated in a list, which allows nodes without traffic to rapidly reduce power. The traffic control is transmitted by the base station and contains information about the subsequent data-cells, including when the next traffic control cell will be transmitted. Nodes explicitly request transmission from the base station, in a distributed manner, during the reservation phase. In our approach, the gateway performs the slot assignment based on its routing decisions. Our approach, as explained later, has four phases some of them have different functionality than their approach. Their approach requires the three phases to be present in every frame while in our approach the data send phase (up-link phase in their approach) is more frequent than the other phases leading to less control overhead and thus higher bandwidth efficiency. The gateway informs each node of its state so that a node can turn itself off. They did not discuss the effect of transmission errors on collision and network performance. In this chapter, we focus on the network management by the gateway of its cluster sensors, mainly the MAC mechanism. The MAC-layer protocol uses centralized reservation made by the gateway and has a less control overhead. The next section briefly describes our approach for the energyaware routing and explains the details of the MAC layer protocol. Section 3 discusses the validation environment for our approach and analyzes the results of the simulation experiments. Finally, conclusion and potential extensions are presented.
2.
ENERGY-AWARE NETWORK MANAGEMENT
The main objective of our approach is to extend the lifetime of the sensors through topology adjustment, energy aware routing and MAC. Messages are routed through multi-hop paths to preserve the sensor transmission energy. Message traffic between sensors is arbitrated in time to avoid collision and to allow turning off the unneeded sensors. Gateway nodes assume responsibility in its cluster for sensor organization and routing/MAC management. Since the gateway organizes the sensors in the cluster, it can account for energy commitment to data processing, remaining sensor energy, sensor locations and acceptable quality of service such as message latency. It can as well enhance the robustness and effectiveness of the MAC because the decision to turn a node receiver off can be more accurate and deterministic than a decision based on local MAC protocol [SR98a]. Sensors can be in one of four states: sensing, relaying, sensing-
ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
25
relaying and inactive. The gateway uses model-based energy consumption for the data processor, radio transmitter and receiver to track the sensor’s energy level. Periodically, the gateway adjusts the energy model by querying the actual levels of the sensor energy.
2.1
Energy-aware Routing
Our routing approach is centralized in the gateway node for each cluster. We set routes for sensor data from the active sensor node to the gateway in order to optimize an objective function. The problem can be viewed as the transpose of a single-source routing algorithm, i.e. single destination routing. The objective function describes a path optimization problem, which is proved to be of polynomial time complexity [CH99]. Our algorithm is based on the one-to-some shortest path problem, which is performed the best by Dijkstra algorithm [DI59]. The objective function extends the definition of the cost function of Dijkstra algorithm to consider the nature of the sensor network. The new cost factors are classified as energy, routing, and delay related factors. The energy related factors consider communication cost, remaining sensor energy, energy consumption rate, relaying enabling cost and sensing enabling cost. Routing factors consider connection per relaying sensor. Delay factors are concerned with transmission delay and queuing cost. The sensor energy model in the gateway is maintained through received packet updates. Each packet received changes the capacity of the nodes along the path from the initiator sensor down to the gateway. The gateway uses its routing table to keep track the nodes along the path. A refresh phase is scheduled periodically to correct deviations in the energy model due to model inaccuracy, packet drop due to communication error, or packet drop due to buffer overflow. During the periodic refresh phase, each node sends a state-refresh packet. Then, during the routing phase each node turns its receiver on at a pre-specified time to hear the gateway routing decision. In case of lost refresh packets, the node maintains its previous state. Routing set-up can be dynamically adjusted to optimally respond to changes in the sensor organization. Rerouting decision is based on three criteria: sensor reorganization such as an event that requires reselection of active sensors, node battery energy level if it drops to a certain level and energy model adjustment after refresh updates. Details of our routing approach can be found in
26
2.2
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
MAC Layer Protocol
Although the new routing protocol is independent of the MAC layer protocol, choosing a certain MAC layer protocol may enhance the performance. Recent research results pointed out that the wireless network interface consumes a significant fraction of the total power. Measurements show that on a typical application like web-browser or email, the energy consumed when the interface is on and idle is more than the cost of receiving packets. This is because the interface is generally longer idle than actually receiving packets. Furthermore, switching between states (i.e. off, idle, receiving, transmitting) consumes time and energy Therefore, in a wireless system the medium access protocols can be adapted and tuned to enhance energy efficiency. We choose to implement a time division multiple access (TDMA) based MAC layer whose slot assignment is managed by the gateway. The gateway informs each node about slots in which it should listen to other nodes’ transmission and about the slots, which the node can use for its own transmission. The advantages of using a TDMA MAC layer are: Clock synchronization is built in the TDMA protocol. Recall that we need synchronization for the energy model refresh and sending rerouting decision from the gateway to the nodes. Collision among the nodes can be avoided since each node has its own assigned time slots. Problems can occur with the existence of communication errors: a packet containing the slot assignment can be dropped. If a node that does not hear the gateway decision turns itself off, then no collision can occur. However, we choose to implement the other alternative that a node retains its previous state if it does not receive a routing packet from the gateway in the pre-specified time slot, which leads to potential collisions. However, this collision probability is limited due to the following reasons: A node’s new state and forwarding table is highly probable to remain the same during consecutive rerouting phases. The wrong state of the node will be corrected during the next rerouting cycle, which means that the collision period is limited. If the node’s previous state was inactive, no collision will happen. If the node’s new state is inactive, no packets will be destined to it reducing the collision probability (recall that a node can overhear other nodes’ transmissions.) If the node receives a packet that is not in its forwarding table, this packet is dropped.
ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
27
Collision can only occur if the node happens to use the same time slot for transmission as a neighbouring node since during transmission, we use the minimum transmission power required for reaching the destination. The same thing happens during receiving. In the following subsections, we present the details of the MAC layer protocol. 2.2.1
Protocol Phases and Packet Format
The protocol consists of four main phases: data transfer, refresh, eventtriggered rerouting, and refresh-based rerouting phase. In the data transfer phase, sensors send their data in the time slots allocated to them. Relays use their forwarding tables to forward this data to the gateway. Inactive sensor nodes remain off until the time for sending a status update or to receive route broadcast messages. The refresh phase is designated for updating the sensor model at the gateway. This phase is periodic and occurs after multiple data transfer phases, thus minimizing the routing overhead compared to the payload data. Periodic adjustments to sensor status enhance the quality of the routing decisions and correct any inaccuracy in the assumed sensor models. During the refresh phase, each node in the network uses its pre-assigned time slot to inform the gateway of its state (energy level, state, position, etc). Any node that does not send information during this phase is assumed to be nonfunctioning. If the node is still functioning and a communication error caused its packet to be lost, its state may be corrected in the next refresh phase. The slot size in this phase is less than the slot size in the data transfer phase as will be explained later. Figure 2-2 shows an example of a typical sequence of phases.
As previously discussed in subsection 2.1, rerouting is performed when the sensor energy drops below a certain threshold, after receiving a status update from the sensors and when there is a change in the sensor organization. Since the media access in our approach is time-based, rerouting has to be kept as a synchronous event that can be prescheduled. To
28
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
accommodate variations in the rate of causes of rerouting, two phases are designated for rerouting and scheduled at different frequencies. The first phase is called event-based rerouting and allows the gateway to react to changes in the sensor organization and to drops in the available energy of one of the relay sensors below a preset acceptance level. The second rerouting phase occurs immediately after the refresh phase terminates. During both phases, the gateway runs the routing algorithm and sends new routes to each node in its pre-assigned slot number and informs each sensor about its new state and slot numbers as shown in Table 2-1. Given that events might happen at any time and should be handled within acceptable latency, the event-based rerouting phase is scheduled more frequently than the refresh-based rerouting. If there has not been any events requiring messages rerouting, the event-triggered rerouting phase becomes an idle time.
The length of refresh and reroute phases is fixed since each node in the sensor network is assigned a slot to use in transmission during the refresh phase and to receive in it during the reroute phases. Similarly, the length of the data transfer phase is fixed. Although the number of active nodes changes from a rerouting phase to another, the length of the data transfer phase should be related to the data sending rate and not to the number of active nodes. If the length of the data transfer phase is dependent on the number of active nodes, then a node may consume power while it has nothing to do. It should be noted that during system design the size of the data transfer phase should be determined to accommodate the largest number of sensors that could be active in a cluster. Since the length of all phases is fixed, the period of the refresh and rerouting phases can be agreed upon from the beginning and does not have to be included in the routing packets. The description for the packets of the corresponding phases is shown in the Table 2-2. In the data packet used in the data transfer phase includes the originating sensor ID so that the gateway can adjust the energy model for the
ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
29
sender and relay sensors. In addition the sensor ID identifies the location and context of the sensed data for application-specific processing. The refresh packet includes the most recent measurement of the available energy. The optional location coordinates can be used to support sensor mobility.
The content of a routing packet depends on the new state of the recipient sensor node. If the sensor is to be in an Inactive, the packet simply includes the ID of the destination node. In case of a node that is set to sense the environment, the packet includes the data sending rate and the time slots during which these data to be sent. In addition, these sensing nodes will be told the transmission range, which the node has to cover. Basically the transmission power should be enough to reach the next relay on the path from this node to the gateway, as specified in the routing algorithm. Relay sensors will receive the forwarding table that identifies where data packet to be forwarded to and what transmission to be covered. The forwarding table consists of ordered triples of the form: (time slot, data-originating node, transmission range). The “time slot” entry specifies when to turn the receiver on in order to listen for an incoming packet. The “source node” is the sensor node that originated this data packet, and “transmission power” is the transmission power to use to send the data. This transmission power should be enough to reach the next relay on the path from the originating node to the gateway. It should be noted that the intermediate nodes on the data routes are not specified. Thus it is sufficient for the relaying nodes to know only about the data-originating node. The transmission range ensures that the next relay node, which is also told to forward that data packet, can clearly receive the data packet and so on. Such approach significantly simplifies the implementation since the routing table size will be very small to maintain and the changes to the routes will be quicker to communicate among the sensors. Such simplicity is highly desirable to fit the limited computational resources that sensors would have.
30
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
We rely on the sensor organization and smart data fusion to tolerate lost data packets by allocating redundant sensors and applying analytical techniques. 2.2.2
Slot Size and Assignment
The slot sizes for the refresh and reroute phases are equal since they cover all sensor nodes in the cluster. Both slots are smaller than the slot for the data transfer phase. This is due to two reasons. First, the routing packet is typically less than the data packet. Second, during the data transfer phase many nodes are off which allows for larger slot sizes. In the other phases, all nodes must be on and communicating with the gateway. To avoid collision while packets are in transient, the slot size in the refresh and reroute phases should be equal to the time required to send a routing packet with maximum length plus the maximum propagation time in the network, as calculated by the gateway. The slot size of the data-transfer phase equals the time required to send a data packet with maximum length plus the maximum propagation time in the network. Slot assignment is performed by the gateway and communicated with the nodes during the rerouting phases. Different algorithms can be used for slot assignment. We assign each node a number of slots for transmission based on its current load. This leads us to two approaches for handling the TDMAbased MAC slot assignment problem, namely breadth and depth techniques. In the breadth slot assignment technique we follow a breadth-first-search (BFS), commonly used for graph parsing, to assign time slot numbers starting from the outmost active sensors. These outermost sensors are all sensing enabled since they are the source nodes of our data, and thus the initiator nodes in the routes towards the gateway. Such assignment is supposed to provide contiguous time slot numbers assigned for each relaying node to receive at, and thus saving the energy consumed in switching between on and off states. The other technique, namely depth assignment is based upon a depth-firstsearch (DFS) like. It tends to assign time slots contiguously over each route from the sensing node towards the gateway. Although this approach does not save the energy of switching between on and off states as the breadth technique, it still avoids the buffer overflow problem. In most cases each received packet will not wait in the buffer of the relay node and will be forwarded in the next time slot.
ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
31
Figure 2-3 shows an example of the two slot assignment techniques. Nodes A, B, and D acts as sensor so they are assigned one slot for transmitting their data. Node C serves as a relay for nodes A and D, so it is assigned two slots. Node E acts as a sensor and a relay. It is assigned one slot for transmitting its own sensor data and 3 slots to relay other nodes’ packets. In this example, the gateway informs each node of the slots it is going to receive packets from other nodes and the slots it can use to transmit the packets. Now for the breadth technique, the gateway informs nodes A, B and D to transmit their packets at time slots 1, 2 and 5 respectively. For node C, it is informed to listen to packets at time slots 1 and 2, and to forward them at time slots 3 and 4 respectively. Node E is assigned to turn its receiver on at time slots 3-5 (corresponding to the transmission slots of nodes C and D) to receive packets. And that it can use time slot 6 to transmit its own packet, as well as time slots 7-9 to forward packets. It should be noted here that this slot assignment algorithm provides contiguous slot numbers for each node, thus reducing the energy needed to switch between on and off states. However, it might lead to instantaneous buffer overflow. For example, if node E in Figure 2-3 has only a buffer for 2 packets, then it can happen that it receives, in slots 3-5 3 packets from nodes C and D. This may lead to packet drop due to buffer overflow. However, if transmission and receiving slots were interleaved, this overflow cannot happen, as in the depth technique. For the same example we apply the depth technique, as shown in the right side Figure 2-3. For the packet generated by node A, it is assigned time slots 1 to send by node A, 2 to forward by node C, and 3 to forward by node E to the Gateway. Similarly, packets generated by node B are assigned time slots 4, 5 and 6 to be sent by nodes B, C and E respectively. Similarly, node D’s packets are sent at time slots 7 and 8 by nodes D and E respectively. For
32
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
node E’s own packets, they are assigned time slot 9. It is obvious that this technique avoids packet drops due to buffer overflow. However, nodes switch more frequently between on and off states. The performance of both the depth and breadth techniques is compared via simulation, as reported in the next section. It is worth noting that our previous study has demonstrated an improvement of an order of magnitude in the lifetime of the sensor network when combining our energy aware routing with the initial version of our new MAC protocol. Summary of the results of our study is given in appendix A.
3.
PERFORMANCE EVALUATION
In this section, we use simulation to study the performance of the new MAC layer protocol. We further compare the performance of the two proposed techniques, the breadth and depth slot assignment. We use the following performance metrics: Packet drop count: the number of dropped data packets due to buffer overflow. Number of on/off state changes per sensor. Node lifetime: until the sensor energy level drops to zero. End-to-End Delay: the time it takes a data packet from the sensing node to the gateway. Throughput: the rate of data packets arrived to the gateway. Average energy consumed per packet: the average energy consumed in transmitting and receiving a data packet. It should be noted that we considered a number of other energy-related performance metrics related to the network lifetime, time-to-network partitions, etc. In this chapter we only report the results of the above metrics. The reader is referred to for the results for the other metrics. The following subsection describes the simulation environment followed by a summary and analysis of the simulation results.
3.1
Environment Set-up
A cluster is set of 100 nodes placed randomly in a 1000x1000 meter square area. The gateway position is determined randomly within the cluster boundaries. A free space propagation channel model [DI59] is assumed with data rate set to 2Mb/s. Packet lengths are 10 kbit for data packets and 2 kbit for routing and refresh packets. The buffer size at each node is 15 packets.
ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
33
Each node has an initial energy of 2 joules. A node is considered nonfunctional if its energy level reaches zero. For a node in the sensing state, packets are generated at a constant rate of one packet/second. This value is consistent with the specifications of the Acoustic Ballistic Module from SenTech Inc. [AB], Each data packet is time-stamped when it is generated to allow the calculation of average delay per packet. In addition, each packet has an energy field that is updated during the packet transmission to calculate the average energy per packet. A packet drop probability is taken equal to 0.01. This is used to make the simulator more realistic and to simulate the deviation of the gateway energy model. We assume that the cluster is tasked with a target-tracking mission. The initial set of sensing nodes is chosen to be the nodes on the convex hull of the sensors of the cluster. The selected sensing nodes change as the target moves. Since targets are assumed to come from outside the cluster, the sensing circuitry of all boundary nodes is always turned on. The sensing circuitry of other nodes are usually turned off but can be turned on according to targets movement. As mentioned before, rerouting occurs when a node’s energy level falls below a percentage of its initial energy. This percentage is taken equal to 80%. Each time this threshold is reached, it is reset to 0.8 of its previous value. For energy-consumption, we used the communication energy consumption model used in HS00d], the computation energy consumption model used in [HS00d, SC00], and the sensing energyconsumption model used in Targets are assumed to start at a random position outside the convex hull. These targets are characterized by having a constant speed chosen uniformly from the range four meters per second to six meters/second and a constant direction chosen uniformly depending on the initial target position in order for the target to cross the convex hull region. For the purpose of this experiment we assume that only one target will be active at any time. Each target remains active until it leaves the deployment region area. In this case, a new target is generated.
3.2
Performance Results
Now we describe the results of our experiments based on the performance metric. All the performance metrics are plotted against increasing buffer sizes at the sensor nodes.
34
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
In Figure 2-4, we can see the expected advantage of the depth technique over the breadth. The number of packets dropped due to buffer overflow in the case of the depth slot assignment is not zero. This is because either we don’t know when a node will generate its data, if it is a sensing node, or a node retains its buffer when the slot assignment changes.
ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
35
Figures 2-5 and 2-6 show that for the breadth method the number of changes in state is zero. Thus the breadth technique saves energy. The number of state changes for the transmitter is higher than for the receiver. This is expected as each node at least transmits what it receives (if it doesn’t generate new packets.) So the number of transmission slots is larger than the number of receiving slots. Thus it is more probable to change state while you are transmitting than when you are receiving. As the buffer size increases, the number of packets that reaches the gateway increases slightly leading to a more accurate model at the gateway. This also explains the decrease of the average energy consumed per packet shown in Figure 2-10.
36
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
As expected in Figure 2-8, when the buffer size increases, the average delay per packet increases due to the increased queuing delay. However in Figure 2-9, the throughput does not decrease as less number of packets is dropped due to more available buffer size. Average delay per packet is lower in case of depth technique as a packet never waits for a slot if there are no cells in buffer; e.g. a packet goes in slot 3-4-5-6 to reach the gateway. In case of breadth technique, a cell may wait for a slot in the next cycle if a packet arrives after the contiguous transmission period has ended. Throughput is lower in case of breadth technique as the number of packets dropped is higher. Lifetime in case of breadth technique is higher as more packets are dropped and not forwarded saving the energy of the nodes, but with lower throughput. However, it decreases in case of breadth technique as more packets arrive leading to consuming the energy of the nodes (note that the other effect which is more packets means more accurate model is not as effective as the other effect). In summary, the above results show that the breadth technique is better when the energy required for changing the sensor’s state between on and off is critical. However, the depth technique is more reliable regarding packet delivery since it avoids packet drops due to buffer overflow. The depth technique is also superior with respect to end-to-end delay as well as throughput.
4.
CONCLUSION AND POTENTIAL TRENDS
In this chapter, we have presented a novel approach for an energy-aware management of sensor networks. A gateway node acts as a cluster-based
ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
37
centralized network manager that sets routes for sensor data, monitors latency throughout the cluster, and arbitrates medium access among sensors. The gateway tracks energy usage at every sensor node and changes in the mission and the environment. The gateway configures the sensors and the network to operate efficiently in order to extend the life of the network. We have also presented in details a new MAC layer protocol. We have proposed two major techniques for slot assignment. Simulation results demonstrate a comparative evaluation of the breadth and depth slot assignment techniques with increasing buffer sizes. The simulation results demonstrated that the breadth technique is recommended in case the energy consumed for changing the sensor’s state is high. On the other hand, the depth technique offers more reliable data packet delivery since it is more tolerant to packet drops caused by buffer overflow. The depth technique also gives better results regarding end-to-end delay as well as throughput. Our future plan includes extending the routing model to allow for node mobility. We would like also to study approaches for clustering the sensor network and inter-cluster communication, i.e. scaling our approach. We are interested in studying dynamic and reservation-based TDMA slot assignment techniques in the MAC layer. Another potential issue is to allow event driven/on-demand sensing scenario instead of the continuous periodic sensed data flow. Finally, the approach can be extended to be applicable to other sensor-based networks, e.g. automobile, airplane control, and industrial control.
APPENDIX A A.1. Effect of Interaction between Routing Protocol and MAC Layer We run an experiment to determine the effect of using the interaction of the routing algorithm decision and turning on and off the receiver at the MAC layer. Figures 2-11 through 2-13 show the results for different performance metrics. It is clear that turning the receiver circuitry on and off based on the interaction between the routing algorithm and the MAC layer has significant effect on saving power and hence the lifetime of the network. Moreover, the interaction between the routing algorithm and the MAC layer has a positive effect on the average delay per packet. With the receiver always turned on, nodes die quickly leading to selection of longer paths which increases the average delay per packet. The results show one order of
38
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
magnitude enhancement in the network lifetime, 78% enhancement in the average energy consumed per packet, and 23% enhancement in the average delay per packet.
ENERGY-AWARE TDMA-BASED MAC FOR SENSOR NETWORKS
A.2.
39
Comparison between Routing Algorithms
We ran a set of experiments to compare the performance of our approach with other routing algorithms. The results are shown in figures 2-14 through 2-17. The figures show that the new algorithm gives a relatively good performance for all the metrics. Other algorithms may slightly outperform our algorithm in some metrics. However, the same algorithms perform poorly on other metrics. For example, the minimum distance routing algorithm gives a 1.57 improvement factor over the new algorithm in terms of average delay per packet. However, our algorithm outperforms this algorithm by a factor of 13.91 in terms of time to network partitioning, as indicated in Fig. 1-14.
40
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Chapter 3 POWER AWARE PACKET ROUTING CONTROL IN AD-HOC WIRELESS NETWORKS
Qilian Liang and Nancy Neigus Hughes Network Systems 10450 Pacific Center Court San Diego, CA 92121 USA
Abstract:
Most existing works on power aware packet routing are based on the remaining battery capacity. In this chapter, we make power aware routing control based on four descriptors: remaining battery capacity, packet loss requirement, distance to the gateway or next node, and size of incoming packet. We applied a fuzzy logic system to packet forward/discard decision making. Linguistic knowledge is represented using fuzzy rules, and linguistic labels are represented using membership functions. Soft decision surface is obtained for packet forwarding/discarding, and hard decision boundary is generated for the node. Comparing to the minimum battery cost routing and min-max battery cost routing methods, our method incorporates three more descriptors as well as remaining battery capacity, which makes the packet forwarding/discard decision more effective.
Key words:
Power aware, Ad hoc networks, Routing control, Fuzzy logic systems.
1.
INTRODUCTION
Ad hoc networks (AHN) are self-organizing entities that are deployed on demand in support of various activities including collaborative computing, multimedia classroom, disaster relief, search and rescue, and interactive mission planning. Much research has been published that defines methods to minimize power utilization in battery constrained ad hoc networks. This research considers only one or two factors in the methods, such as battery capacity, topology or location.
42
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Rodoplu and Meng [RM99] developed a general mathematical theory for designing a minimum power topology within one cluster for a stationary Ad Hoc network. Their approach only considers the immediate locality of a node, and assumes the mobile devices have similar antenna heights. In Wu et al combined the concept of power control with busy-tonebased protocols to further increase channel utilization. Similar to a power control loop was proposed to control the transmitting and receiving power level in ad hoc wireless network. In [XL01], a locationaided power aware routing protocol was proposed. In [LR02], a powerefficient gathering in sensor information systems (PEGASIS) method is proposed, but no mobility of sensor nodes is assumed. Singh et al proposed power-aware routing and discussed different metrics in poweraware routing; Li et al extended their work and proposed an online power aware routing in wireless ad-hoc networks. In a power aware virtual base station (PA-VBS) protocol was proposed, which elects a mobile node from a set of nominees to act as a base station. In [TO01], a new power aware routing protocol was proposed to both evenly distribute the power consumption rate of each node and minimize the overall transmission power for each connection request. In this chapter, we propose a power control and management scheme for ad hoc wireless networks that will account for multiple factors relevant to battery power conservation. There is a wide range of system characteristics related to power management such as power consuming states (e.g., transmitting data, receiving data, idle mode, and sleep mode), variable data rate, diverse node characteristics, different channel conditions, available bandwidth, and QoS requirements. Nodes in the ad hoc network will evaluate the relevant factors and, based on the results, manage power by controlling packet transmission. The number and range of factors make the use of traditional control methods very difficult, and it is a daunting task for any mathematical model. A more practical and effective mechanism is needed. Several special issues on intelligent techniques in high speed networks have been published by IEEE Journal on Selected Areas in Communications (e.g. ), which shows that intelligent techniques have been extensively applied to high speed networks. According to “The advantages of intelligent techniques are numerous, most notably are learning from experience,” Fuzzy logic systems are known for representing and numerically manipulating linguistic rules in a natural way and for their ability to handle problems that conventional control theory cannot approach successfully, because the latter relies on a valid and accurate model which does not always exist. For example, recently, a fuzzy logic system was
POWER AWARE PACKET ROUTING CONTROL IN AD-HOC WIRELESS NETWORKS
43
applied to connection admission control of ATM networks In this chapter, we apply fuzzy logic system to power aware packet routing control in ad hoc wireless networks. In the following sections, an overview of fuzzy logic systems is given in Section 2; power aware packet routing control based on fuzzy logic systems is presented in Section 3; knowledge processing and packet forwarding/discarding are presented in Section 4; finally, the conclusions are given in Section 5.
2.
OVERVIEW OF FUZZY LOGIC SYSTEMS
A fuzzy logic system (FLS) includes fuzzifier, rules, inference engine, and defuzzifier [ME95], Figure 3-1.
When an input is applied to a FLS, the inference engine computes the output set corresponding to each rule. The defuzzifier then computes a crisp output from these rule output sets. Consider a p-input 1-output FLS, using singleton fuzzification, center-of-sets defuzzification [ME01] and ``IFTHEN" rules of the form: Rule
IF
is
and
is
and... and
is
, THEN y
is
Assuming singleton fuzzification, when input applied, the degree of firing corresponding to the l th rule is computed as
is
44
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
, where T denotes t-norm (we use product operation in this chapter). There are many kinds of defuzzifiers. In this chapter, we focus, for illustrative purposes, on the center-of-sets defuzzifier [ME01]. It computes a crisp output for the FLS by first computing the centroid, of every consequent set and, then computing a weighted average of these centroids. The weight corresponding to the l th rule consequent centroid is the degree of firing associated with the l th rule, so that
, where M is the number of rules in the FLS. In the next section, we define a FLS for power control and management of ad hoc wireless networks.
3.
POWER AWARE PACKET ROUTING CONTROL
Packet routing control is valuable in battery-constrained ad hoc networks as a means to reduce the power costs of transmission and reception. The power cost of a broadcast message includes the sending terminal, the target receiving terminal and neighbouring terminals that overhear it. If four or more neighbours receive a broadcast message, then the total cost of receiving the message is more than the cost to send it Since discarding a packet consumes much less energy than processing it, an energy-saving routing control mechanism would allow the terminal to decide whether to forward route or discard a packet based on certain criteria. An ideal packet routing control mechanism would optimize battery utilization, minimize packet loss ratio, and use the shortest distance and fewest hops to the gateway or next node. But all these goals can't be achieved at the same time. To devise a compromise solution that can save more power, and meet the QoS, we apply fuzzy logic system to power aware
POWER AWARE PACKET ROUTING CONTROL IN AD-HOC WIRELESS NETWORKS
45
packet routing, which enables a node to discard a packet subject to some conditions. We selected the following descriptors as antecedents for fuzzy logic rules: 1. remaining battery capacity of this node, which is a more accurate metric to describe the lifetime of this node [ TO01 ]; 2 . packet loss requirement, which is an important QoS metric; 3 . distance from this node to gateway (or next node), which is important to comprise the shortest routing path and power saving; and, 4 . the size of incoming packet, which is related to power consumption should this packet be forwarded. Based on the fact that discarding a packet consumes much less energy than receiving it, we design a fuzzy logic system using rules such as: IF the remaining battery capacity requirement is
is
of the node to forward this packet
Moderate, High;
and the packet loss
and distance to the gateway or next node
and the size of incoming packet
, where
is
is
THEN the willingness
is
are linguistic labels. We assign from Loose, Moderate, Strict;
from Low,
from Near, Moderate,
Far, from Short, Moderate, Long; and from Very Strong, Strong, Medium, Weak, Very Weak. These rules are based on the intersection rule configuration (IRC) structure, and most FLSs are based on this structure. This requires setting up rules (because every antecedent has 3 fuzzy sub-sets, and there are 4 antecedents) for this FLS. This is a large number of rules to manage, and, in addition, it's very difficult for an expert to complete a rule with 4 antecedents, such as, IF the remaining battery capacity is Low, and the packet loss requirement is Strict, and distance to the gateway or next node is Far, and the size of incoming packet is Long, THEN the willingness of the node to forward this packet is . So we split one rule to two rules, e.g., for the above rule, we split it to IF the remaining battery capacity is Low, and the packet loss requirement is Strict, THEN the willingness of the node to forward this packet is .
46
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Or IF distance to the gateway or next node is Far, and the size of incoming packet is Long, THEN the willingness of the node to forward this packet is . This kind of rule structure is called union rule configuration (URC) based rule structure, which was recently proposed by Combs and Andrews [CA98]. The URC-based structure can tremendously reduce the required number of rules compared to the IRC-based structure. By this means, we only need rules. In addition, the new rules are much easier to be filled with appropriate linguistic labels for the consequence. In total, we have 18 rules, 9 of them with antecedents the remaining battery capacity and the packet loss requirement, and 9 of them with antecedent distance to the gateway or next node and the size of incoming packet. We summarize all the rules in Tables 3-1 and 3-2.
POWER AWARE PACKET ROUTING CONTROL IN AD-HOC WIRELESS NETWORKS
4.
47
KNOWLEDGE PROCESSING AND PACKET ACCEPTING/ FORWARDING
We used trapezoidal membership functions (MFs) to represent Low, High, Loose, Strict, Near, Far, Short, Long, Very Weak, and Very Strong, and triangle MFs to represent Moderate, Weak, Medium, and Strong. We plot these MFs in Figure 3-2. For every input
By
repeating
hypersurface plotted visually.
these
the output is computed using
calculations
for
we
obtain
a
Since it's a 4-D surface, it's impossible to be
If we have (the remaining battery capacity), (the packet loss requirement), and two other antecedents, distance to the gateway or next node input
and size of incoming packet , the output is computed using
are variables, for every
48
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
By repeating these calculations for
and
we
obtain a hypersurface as plotted in Figure 3-3 (a). Packet acceptance/rejection is a binary decision problem — accept or reject — which can be made based on the hypersurface. If we choose as our decision boundary, i.e., accept when and reject when
we obtain decision
areas with respect to distance to the gateway or next node
and size of
POWER AWARE PACKET ROUTING CONTROL IN AD-HOC WIRELESS NETWORKS
incoming packet
for fixed
and
(a). Similarly, we plot hypersurfaces
49
as plotted in Figure 3-4 and
in Figure 3-3 (b) (c) (d) and their decision areas in Figure 3-4 (b) (c) (d). If the node makes forward/reject decision based solely on the remaining battery capacity (e.g., minimum battery cost routing (MBCR) or min-max battery cost routing ), the node will definitely reject the packet when but our method will reject it conditionally (see Figure 3-4 (c)). Similarly, the node will definitely accept and forward the packet when but our method will accept it conditionally (see Figure 3-4 (d)).
50
5.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
CONCLUSIONS
Most existing works on power aware packet routing are based on the remaining battery capacity. In this chapter, we make power aware routing control based on four descriptors: remaining battery capacity, packet loss requirement, distance to the gateway or next node, and size of incoming packet. We applied fuzzy logic system to packet forward/discard decision making. Linguistic knowledge is represented using fuzzy rules, and linguistic labels are represented using membership functions. A soft decision surface is obtained for packet forwarding/discarding, and a hard decision boundary is generated for the node. Compared to the minimum battery cost routing and min-max battery cost routing methods, our method incorporates three more descriptors as well as remaining battery capacity, which makes the packet forwarding/discard decision more reasonable.
POWER AWARE PACKET ROUTING CONTROL IN AD-HOC WIRELESS NETWORKS
51
ACKNOWLEDGMENT The authors would like to thank Dr. Bill Whitmarsh and Mr. Matt Read at Hughes Network Systems for their very helpful comments, many of which we incorporated into this chapter.
This page intentionally left blank
Chapter 4 OPTIMAL NODE SCHEDULING FOR EFFECTIVE ENERGY USAGE IN SENSOR NETWORKS
Ankur Srivastava, Justin Sobaje, Miodrag Potkonjak and Majid Sarrafzadeh Computer Science Department University of California Los Angeles BoelterHall, UCLA, Los Angeles, CA 90095
Abstract:
Up until now, low power system approaches have been restricted to single physical systems. The recent emergence of distributed embedded systems has created a need for power optimization across individual system boundaries. In particular, a great deal of excitement has been generated by wireless ad-hoc sensor networks, which integrate communication, computation, and sensing elements into self-organizing, adaptive, and multi-functional systems. We address power management in these types of systems. We focus our attention on the problem of node scheduling for a minimum degree of coverage. We have developed provably optimal polynomial time algorithms. Furthermore, we analyze the scaling properties of the problem as the number of sensors in the network increase. Extensive simulations provide a number of interesting and important insights into power consumption trade-offs in sensor networks.
Key words:
Sensor networks, Energy optimization, Intruder detection, Node scheduling.
1.
INTRODUCTION
Wireless ad-hoc sensor networks are a prime example of a second generation distributed system. On one end, they provide an interface to the widely used Internet. On the other end they provide an interface to the real world. It has been firmly established that, at least now and in the near future, the limiting factor for effective use of ad-hoc sensor networks is power consumption [RA00b]. A power managed design methodology for systems
54
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
based on sensor networks is hence imperative. It would enable the design of network systems with high longevity and stable quality of service. In this chapter, we address the problem of scheduling the nodes to be turned on such that the overall power dissipation is controlled and minimized while achieving a minimum degree of region coverage (defined later). We solve this problem optimally using min-cost flow formulation. There are many tasks that sensor networks could perform, some of which are fundamental to many applications. One such task is the problem of finding a path of nodes from one side to the other. This path of nodes that are “turned on” could have many applications. Establishing a minimum level communication between one side to the other, detecting objects trying to cross the region are a few to name. Other applications like military, traffic monitoring etc will also extensively use this path of nodes. Hence a methodology, which controls the power dissipation while picking up the nodes that form this path, will greatly affect the power dissipation of the application. In this chapter we optimally solve the problem of scheduling the nodes to be switched on such that there exists at-least one path from one side to the other at every time instance and the overall power dissipation is minimized. Since the problem is solved optimally, at first glance it may seem that there is no need for experimental evaluation. However, the key question in wireless ad-hoc sensor networks is how well the algorithms scale. In order to address such concerns, we studied the behaviour of algorithms as the size of the network in terms of used sensors increases. The remainder of the chapter is organized as follows. Section 2 describes the related work in sensor networks, power optimization, and relevant statistical and combinatorial techniques. Preliminary technical information along with formal problem definition is discussed in Section 3. Section 4 contains the technical core of the chapter: optimal polynomial time algorithms for power minimization during object detection procedures. Finally, before conclusion, we present experimental results related to our statistical studies on algorithms scalability.
2. 2.1
RELATED WORK Ad-hoc Sensor Networks
Due to rapid development in technology, wireless networks have become feasible and cost effective. Wireless networks can have many attractive
OPTIMAL NODE SCHEDULING FOR EFFECTIVE ENERGY USAGE IN SENSOR NETWORKS
55
flavours. On one end of the spectrum, there are multimedia and gigabit wireless LANs, where the dominant issue is high bandwidth. On the other end of the spectrum are the last ten meters (wireless connection between computers and peripherals), last one meter (sensor networks) and last inch (personal and implantable networks). It is projected that the Bluetooth (a protocol for communication in wireless networks) [BS] devices will form a $5 billion annual market in less than three years. A number of applications are envisioned for these types of networks that can dramatically alter the human life [TE00, A number of challenging technical problems are associated with wireless adhoc networks in general and sensor networks in particular. They include a need for new types of signal processing PK00], operating systems features self-organization and deployment low power design [RA00a], integration [Bul96], and issues related to embedded systems [BW00].
2.2
Power Modelling, Minimization and Management
Power is an important optimization metric both while designing the sensor nodes and while developing algorithms to solve specific problems on these networks. A lot of research has gone into the development of design methodologies and systems for low power applications. [AS96] contains a survey of low power techniques for digital circuits. [PW99] considers the problem of maximizing battery life in CMOS circuits. For wireless systems, power issues at circuit level are addressed in and at architectural level in [RA00b]. On the algorithmic side, discusses new power aware metrics for determining routes in traditional wireless ad-hoc networks. Variation of transmitter power level of a mobile node in a wireless network for fixed quality of service in varying channel interference is discussed in [RB97]. In this chapter we discuss provably optimal algorithms for energy conservation while doing node scheduling.
2.3
Statistical and Probabilistic Optimization Techniques
Statistical techniques can be broadly divided into two groups: parametric and nonparametric [Thi88]. Parametric techniques assume that knowledge about the underlying statistical distribution is available (often normal distribution is assumed) and that the task is to validate the assumption regarding the distribution, calculate the corresponding parameters, and
56
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
establish intervals of confidence [DS86]. Nonparametric techniques do not make any assumptions about the statistical distribution. They aim to figure conceptually and quantitatively the simplest (and therefore best) model which fits the recorded data [CA99]. Therefore, nonparametric techniques are significantly more computationally intensive. In situations where the underlying statistical distribution is known, parametric techniques are attractive options. However, for object detection kind of applications, it is very difficult to make any assumptions about the underlying statistical distribution. Therefore, we decided to use non-parametric statistical techniques.
3. 3.1
PRELIMINARIES Sensor Networks: Architecture and Models
Sensor Networks are networks of low power sensing devices (nodes), which are computationally rich. Networking these sensors empowers them with the ability to coordinate among themselves for solving large sensing and computational tasks. These networks would be large scale, very dynamic, and their deployment in inhospitable environments would enable easy acquisition and processing of data. There are many architectural challenges in designing such distributed systems. These sensors would be expected to coordinate among themselves and set-up a network. They would have to divide tasks amongst themselves in an energy efficient fashion. Upon sensor node failure and sensor node addition, they would have to reorganize themselves. Another major constraint that these systems would have is power. Since the nodes will be battery powered, the system lifetime will be heavily dependent upon the way these systems use their available power. In this chapter we discuss algorithms for efficient power management of sensor nodes.
3.2
Problem Formulation
Figure 4-1 shows the abstraction of a sensor network used in this work. Each node has an associated placement coordinate and an associated radius (which could be different for different sensors), which is the radius of the circular region that the node can sense. This circle is called the region of view. We abstract this distribution of nodes to nodes in a graph G = (V, E),
OPTIMAL NODE SCHEDULING FOR EFFECTIVE ENERGY USAGE IN SENSOR NETWORKS
57
where each graph node represents the physical sensor node. The edges in the graph can have different meanings depending on the task we are trying to achieve. For example if we want to establish a communication link between one side to the other, an edge would indicate the feasibility of having a communication between the source and destination of the edge if both are kept “turned on ”. If we are monitoring traffic, an edge would indicate the capability of the system to detect any movement between the source and destination nodes.
In this chapter, we try to find a path from left to right edge of the region. These nodes will be “turned on” and hence will dissipate expensive system energy. Keeping the same path activated all the time is not a very good idea from the overall system energy and lifetime point of view. The problem at hand is to schedule the nodes to be turned on such that there exists exactly one path at any instance of time and overall energy dissipation is also balanced out. More formally the problem can be described as follows: Given a graph G = (V, E) with a source S and a destination T. Let us assume that each time step comprises of some pre-specified number of time units (say Ds) that does not change. We want to find a path from S to T for K. such time steps. Nodes S and T indicate the external base-stations on the sides of the region between which the path needs to be established. Each node has an associated energy Ei and power dissipated per unit time step Pi. Hence the quantity Ei/Pi indicates the number of time steps for which this node can be “turned on” without exhausting its energy reserves. This
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
58
quantity will be called node capacity in the subsequent paragraphs. Each node also has an associated cost which signifies the power dissipated per unit time step to keep it on. The objective is to schedule the nodes to be turned on in such a way that in every time step there is exactly one path from S to T and the overall system lifetime is maximized. This needs to be for K time steps. We believe that the following metric is a good indicator of the overall system lifetime. In order to maximize the Lifetime, we would like to pick nodes with lesser cost. After K time-steps, the system lifetime will be given by where Pi is the energy dissipated per time step and ni is the number of times a node is kept on (assuming the overhead of turning on and off is negligible). Maximizing the system lifetime is equivalent to minimizing the sum of the node costs that take part in the path formation. Problem Statement: Given a graph G = (V, E) with nodes and edges and two distinct nodes S and T. Given node capacities (Ei/Pi) and costs Pi, schedule the nodes in K time slots such that In each time slot there exists exactly one path of nodes that make a connected path from S to T The sum of the costs of the nodes that take part in this process is minimized. Each node that is scheduled in a time slot must have enough energy to remain working for the entire time slot.
We solve this problem optimally using the min-cost K-flow algorithm.
3.3
Combinatorial Optimization Techniques
In this chapter we use the following combinatorial optimization techniques: shortest path and mincost flow. 3.3.1
Shortest Path Problem
The shortest path problem is the problem of finding a path from a node in a graph to another node. This path should have the shortest length, or weight if edge weights are defined. This problem has been extensively studied We use the breath first search algorithm [MO59] to find the shortest path. This algorithm proceeds by expanding the frontier between
OPTIMAL NODE SCHEDULING FOR EFFECTIVE ENERGY USAGE IN SENSOR NETWORKS
59
discovered and undiscovered vertices uniformly across the breath of the frontier. It takes D+ 1 step to discover all vertices at distance D. 3.3.2
The Flow Problem
Given a network with edge capacities, maximum flow problems try to answer the following question: What is the greatest rate at which material can be shipped from source to sink without violating the capacity constraints? There are efficient algorithms to solve this problem, which are discussed extensively in [CL90]. Basically these algorithms try to find a residual path from source to destination along which more flow can be pushed. In this chapter we use a modification of the conventional max-flow algorithm. The reason is that among all solutions which have the flow “f”, we want to pick the solution that has the minimum cost. As we show later, we model flow as time units, and cost as energy dissipation. We intend to maximize the flow, i.e. time, but at the same time we want a minimum cost solution. Such problems come under the category of min-cost flow problems. These are discussed extensively in [FF62, EK72].
4.
COMBINATORIAL OPTIMIZATION FOR ENERGY MINIMIZATION
In this chapter, we are trying to schedule nodes in K time slots such that in each time slot there exists at-least one connected path from S to T. It can be seen that this amounts to finding K units of flow from S to T such that the node capacity constraints are met and the overall flow-cost is also minimum. It can be re-called that node capacity corresponds to the number of time slots it can be kept on without draining its energy reserve. Node cost corresponds to amount of system energy spent for keeping it on for one time slot. Each unit of flow from S to T will correspond to a path of connected nodes.
4.1
Maximum Temporal Coverage with Minimum Power Consumption
In the previous sections we explained the construction of a network from a spatial distribution of sensor nodes. Each node (except S and T) has an associated and We will try to solve this problem using the theory of mincost flows [FF62, EK72]. The first requirement of any network problem is to have a network with edge capacities. The Mincost flow problem also
60
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
needs non-negative cost per unit flow for each edge. The network also needs to be directed. Our abstraction of the sensor nodes generates an undirected graph having a set of nodes with positive capacities and costs The first step is to make the network directed. According to [FF62], this can be achieved by simply replacing each undirected edge in the parent graph by two edges pointing in opposite directions. For the sake of simplicity, let us assume that the edges coming from S and going into T were directed from the very beginning. All the edges connected to S point away from it and all edges connected to T point into it. Note that our algorithms and theory will still be valid even if these links were assumed to be undirected. After this modification we get a directed network with node capacities and node costs. Node cost and capacity needs to be converted to edge cost and capacity. To achieve this, we transform the network as follows [FF62]: Replicate each node n with nodes n and n’. Have a directed edge from n to n’ with capacity equal to the original node capacity. The cost of the new edge is same as the cost of the original node n. All edges that point into the original node n, will point into the new node n. All edges that point out of the original node n will point out of n’. All other edge capacities are infinity and edge costs are zero.
These transformations are illustrated in Figure 4-2. At this stage, we have a directed network with edge capacities and costs. We also have a number K that corresponds to the time units for which the path is needed. We solve this
OPTIMAL NODE SCHEDULING FOR EFFECTIVE ENERGY USAGE IN SENSOR NETWORKS
61
problem by augmenting K units of flow. Each unit of flow corresponds to a unit of time. Among all possible flows with value K, we want the flow which has the minimum total cost. Total flow cost is defined as: Here, f (u, v): flow through the edge, P (u, v): Cost of the edge Note that this number corresponds to the total power dissipated by having a path for K units of time. As observed in [EK72], this problem can be solved by the theory of min-cost flows. We briefly outline the algorithm below. 4.1.1
Min Cost Flow Algorithm
While solving flow problems, a residual network is formed along which flow is augmented. Let us call this residual network where f is the amount of flow that is currently in the network. Associate with each edge (u, v) in the residual network a weight or cost
It is well known that flow algorithms proceed by augmenting flows in residual networks. Let us call this augmenting sequence by In [EK72] it is suggested that in order to solve this problem, each node i must have a value associated with it. The overall algorithm is enumerated below. Algorithm 1. Maximum Coverage with Minimum Power 1. 2.
3. 4. 5. 6.
i=0 Given and determine by augmenting along a minimum weight path from S to T in with respect to non negative weights
indicate the weight of the shortest path from S to u w.r.t weights then set Halt when there is no augmenting path.
Theorem 1: This algorithm gives the minimum value of total flow cost for the max flow solution. Proof: Please refer to [EK72] Since our original objective was to solve the problem for K units of flow, in the above algorithm we can simply stop whenever K units of flow are
62
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
achieved. The algorithm will still give the minimum value of total flow cost for K flows [EK72]. Now that we have the flows, the next problem is to assign paths (nodes) to time slots. This could be done arbitrarily, as the overall cost does not get affected. We propose the following algorithm to solve the problem: Algorithm 2: Path Construction 1. 2.
3. 4.
Remove all edges from the network that have non- positive flow. Find a path from S to T in this network. Any path will work. Assign this path to a time slot. Reduce the flow along the edges of this path by one. Repeat steps 1, 2 and 3 until we have K paths.
Theorem 2: The algorithm outlined above always produces K paths from S to T, if there are K units of flow originally in the network. Proof: It can be seen that in every step we reduce the incoming flow of a node (which lies on the path) by one and also reduce the outgoing flow by one. So in every step we maintain the flow property, which states that the sum of incoming flow is same as outgoing flow. Hence this algorithm produces K paths.
4.2
Interesting Simplifications
Last section dealt with the general problem of scheduling nodes in K time slots. If K=l, then the same problem can be solved by much simpler and faster algorithms. In this case the objective is to find one path from S to T with minimum cost. If all sensor nodes start with the same initial energy and require the same operating power, then the sensing path that optimizes energy consumption is simply the shortest path. The shortest path minimizes the number of nodes that must be switched on, thus minimizing the consumed energy. The existence of a path and the average length of the shortest path depend on the distribution of the sensor nodes, the number of nodes in the network, and the sensing radius of the nodes. Even if the nodes have different power dissipation levels (or different available energy), the min-cost solution can still be obtained using weighted shortest path algorithms [CL90]. Hence the problem can be optimally solved asymptotically faster than the general case.
OPTIMAL NODE SCHEDULING FOR EFFECTIVE ENERGY USAGE IN SENSOR NETWORKS 4.2.1
63
A Different Cost Function: Maximizing the Path Lifetime
In the previous section we used the sum of the cost of all nodes on the path as the cost of a path. A more accurate way of modelling the lifetime of a path could be to consider the minimum available energy of the nodes and picking a path which has the maximum. Hence the cost of a path p is The quantity denotes the number of time units that this node can be switched on (also referred to as capacity). The objective is to find a path with maximum value of In order to find the path that has the maximum the sensor nodes n in the network are sorted from highest to lowest A binary search is performed to obtain the solution. A subgraph is formed using only those nodes with capacity greater than the median, and the subgraph is checked to see if a sensing path exists. If a sensing path exists, the number of nodes in the subgraph is again cut in half and the process is repeated. If no sensing path exists, the number of nodes in the subgraph is expanded to include nodes with lower capacity. The minimum capacity is reported when the search is complete. The solution gives a path from S to T which has the maximum value of minimum capacity node.
5.
EXPERIMENTAL RESULTS
The previous sections described optimal algorithms to solve the single path (K=l) and multi-path problems. These gave a minimum cost solution where the cost metric corresponded to the total power dissipated. In order to evaluate the working of these algorithms, we made a test bed which instantiated a spatial distribution of nodes to a network problem. We assumed a 1x1 rectangle region in which we distributed the sensor nodes using uniform random and normal distributions. From this distribution a connected graph was initialized with nodes corresponding to the sensor nodes and edges between nodes whose region of view (section 3.2) overlap.
5.1
Path with Minimum Power Consumption
We first report the experimental observations for the simplified case in which K = 1. For experimental purposes the probability of existence of a path is obtained. A breadth first search is used to determine if a path from S to T exists. For a given number of sensor nodes and a given sensing radius, a large number of trials are performed in order to obtain an accurate probability. If a sensing path exists, then the breadth first search from node S
64
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
to node T returns the length of the shortest path from S to T. The average length of the shortest path is an important metric, since the amount of energy consumed by the network depends on the number of nodes that must be switched on. Figure 4-3 shows the probability distribution of having a path from the left side of the region to the right side if the nodes are randomly distributed. The result is plotted for a uniform random distribution. The variation was shown w.r.t. number of nodes and radius. The sensing radius was kept the same for all the nodes. For each value of number of nodes and radius, we got 10,000 different node distributions and computed the probability of having a path. The curve shows that if we increase the sensing radius we need lesser number of nodes to achieve the same probability. Another observation we made was that as we cut the radius in half we need approximately four times the number of nodes to achieve the same probability (although this may not be directly evident from this curve).
Figure 4-4 shows the average number of nodes on the shortest path from S to T for various numbers of nodes and for various radii. In this experiment we set the power dissipation and radius of all nodes to the same value. Hence, the shortest path is also the shortest weighted path. We see that for the same radius, the average path length saturates to a value, beyond which
OPTIMAL NODE SCHEDULING FOR EFFECTIVE ENERGY USAGE IN SENSOR NETWORKS
65
addition of more nodes in the network does not help the path length. Increasing the radius does reduce this saturation point. In section 4.2.1 we described an algorithm that finds a path which maximizes the minimum node capacity (Cp = En/Pn, note that this is also the path lifetime) on the path.
Figure 4-5 shows the outcome of that algorithm. For this experiment we randomly distributed the available energy. The power and radius were kept the same for each node. We see that as we increase the number of nodes and radius, the path lifetime also increases. (The values are normalized.)
66
5.2
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Scheduling Nodes for Minimum Power Consumption
In this section we demonstrate the results obtained by using the flow formulations described in section 4.1. The objective is to maximize the number of time units for which we can have a path (i.e. maximize K). We study the variation of this value with different parameters. Figure 4-6 shows the distribution of the maximum flow with radius and nodes. Maximum Flow corresponds to the maximum number of time units that we can have a path until no path is possible. The node distribution is uniform random. The radius and power dissipation for all nodes were kept the same. The capacity (number of time units for which a node can be switched on, En/Pn) was varied randomly between 0 and a number M which was provided by the user. For this graph M was set to 10. It can be seen that the variation is somewhat linear with radius. If we increase the number of nodes the slope of this curve increases.
Figure 4-7 shows the distribution of maxflow with radius for a normal distribution of sensor nodes. We see that the variation is somewhat exponential initially and then it saturates. The value, at which saturation occurs, increases as the nodes count increase. Again, the radius and power were kept the same for all nodes. The capacity was varied between 0 and M randomly. We also compared the variation of maxflow for different M. For
OPTIMAL NODE SCHEDULING FOR EFFECTIVE ENERGY USAGE IN SENSOR NETWORKS
67
the same number of nodes, the saturation point occurred at a smaller value of maxflow for a smaller value of M.
Finally, in Figure 4-8, we compare uniform random distribution and normal distribution. Since the variation for random distribution is somewhat linear and for normal is exponential, there is a point where normal distribution begins to perform better than random. This point is clearly shown in the graph.
68
6.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
CONCLUSION
In this chapter, we have addressed architectural issues regarding sensor networks. We have provided optimal algorithms to solve the node scheduling problem on a framework of sensor nodes forming a sensor network. The sensor nodes will be implemented using low power and low cost embedded systems. Power will be a primary concern in these systems as the overall system stability and lifetime depend on the power. Through our experimental results, we have shown the behaviour of the problem as the nodes scale. We found that for a particular radius there is a value for the number of nodes beyond which the path-probability is constant. So, adding any further nodes will be wasteful. Experimental results also suggest that for a particular radius, the shortest path saturates to a value beyond which increasing the number of nodes does not help. We observed that for a uniform random distribution the maxflow keeps increasing almost linearly (with radius for a particular node count). Moreover, there is a distinct point beyond which the normal distribution starts performing better than the uniform random distribution. This happens when the value of radius is around half the linear dimension of the region. We can conclude that sensor networks form an interesting topic for further low power research. A lot more needs to be done in terms of power optimization for such systems to be commercially viable.
Chapter 5 ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS
Jennifer L. Wong, Giacamino Veltri and Miodrag Potkonjak Department of Computer Science University of California, Los Angeles Los Angeles, CA, US 90095
Abstract:
Multi-hop wireless networks (MHWNs) are an emerging paradigm for bandwidth and energy-efficient wireless systems where each terminal communicates only with a few closely positioned neighbour nodes using low power communication schemes. High-rate (multimedia) data networks, sensor networks, and voice communications are seen as three main application domains of MHWNs. While MHWNs open many new research and economic opportunities, they simultaneously pose a number of new challenging technical problems. Among them, the fundamental role is reserved for energy- efficient data delivery. We address the problem of Data Multicast in Multi-Hop Wireless Networks that effectively captures requirements of all three of the scenarios. The problem focuses on how to minimize energy consumption while delivering data to all consumers that requested it. Since in the current and pending technologies communication dominates energy consumption, we aim to minimize the number of nodes that transmit data for the request data delivery problem instance. First, we formulate the problem and establish its computation complexity. Next, we develop an efficient heuristic which utilizes information about the geographical position of the nodes in the network to find the most energy-efficient communication path. Finally, we establish the effectiveness of the proposed approach by conducting comprehensive testing of our heuristic on typical ad-hoc networks and instances.
Key words:
Wireless ad-hoc networks, Multi-hop networks, Sensor networks, Data dissemination.
70
1.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
INTRODUCTION
In the last decade, the continuous high pace of technological advances has enabled the exponential growth of the Internet. We can trace the development of two implementation technologies as prime enablers of this growth. The first is the dramatic reduction in the cost of disks, or massive permanent storage. The second is the huge reduction in the cost of optical communication and simultaneous capacity increase. For example, the capacity of a hundred dollar disk increased by factor of 1,200 times in the last eleven years. At the same time, the bandwidth of optical cable has been doubling every nine months. The Internet is a great educational, entertainment and economic resource which enables information to be available at the touch of a mouse. There is a wide consensus that the Internet will grow rapidly both in quantitative and qualitative terms. At the same time, it appears that we are on the brink of the next technological revolution that may have even higher impact. This revolution that will enable communication anytime, anywhere and a connection between physical and communication worlds is due to the advancement of wireless communication technology and sensors. For example, while in early 90's, wireless technology was mainly stagnant in the last six years before it started its exponential growth. With this advancement, there is currently a need for methodologies and technologies that will enable efficient and effective use of wireless network applications. The motivational factors pushing for these applications include the mobility of computational devices (e.g. cell phones and PDAs) and the ability to embed these devices into the physical world. These applications will make information easier to obtain and available at lower cost. While the traditional wireless network architecture has been based on systems of static base stations, it appears that multi-hop network, where each node communicates with a few close nodes, is the most efficient in terms of energy saving and bandwidth reuse. In multi-hop networks each node communicates with other nodes that are geographically distant using intermediate nodes to build communication paths. The key constraint in this situation is energy. Battery capacity and size limits the advancement and applications of these networks. In the last eleven years battery capacity has increased only by a factor of 2.7. Communication is the dominating energy consumption component in MHWN. As a result, the most effective way of energy saving is to power down all parts of then multi-hop network except those required for currently requested sensing and communication. Our goal in this work is
ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS
71
to study how one can minimize energy consumption in multi-hop networks while satisfying the needs of all requested data transfers.
1.1
Motivation and Motivational Example
We illustrate the targeted problem using the following example in multihop networks. Recall that the network is multi-hop in the sense that every node cannot communicate with all other nodes in a single hop. As mentioned earlier, communication is the dominant cost, and therefore for each communication by a node in the network we assume a charge of ten units of energy. When a node is not communicating we assume a charge of one unit of energy. In the network, we have some number of data consumers and some number of producers. The consumers are programs, agents, humans or the Internet gateways which would like information from the network. Producers are nodes in the network which detect events or have the stored information required to send to the consumers. An example of a producer could be a person in multimedia delivery who wants to broadcast the video to other users in the network. The goal is to transfer this information from the producers to the consumers in such a way that minimum energy is consumed in the network. Therefore, the goal is to find an energy-efficient way to use the minimum number of nodes when communicating. There are at least two conceptually different and natural ways to abstract and specify the targeted problem: graph theoretic and geometrical. In graph theory problems, each of the nodes in the network corresponds to a node in the graph and is connected by an edge if communication is possible between the nodes. In many senses the graph theoretic approach is a proper and very efficient way to model MHWNs. However, there is at least one serious drawback. This approach allows for the construction of graphs which are not feasible in the geometrical or real life, sense. In the geometrical specification of the problem, each node is placed in 2 or 3-D space and communication between nodes is configured the same way as done in graph theory. The main complication with geometrical representation is that unit distances between nodes in the network have, in general, no correlation with the number of hops required for the nodes to communicate. Two nodes can be positioned in close vicinity of each other, but the only way to communicate between the nodes is to travel some very long multi-hop path. For example this could be due to an obstacle, such as a building of mountain, obstructing their communication path. Because of the limitations of both graph theoretic and geometrical representation, we believe it is advantageous and necessary to consider both of them when approaching the problem.
72
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
We now state the targeted problem of Data Multicast in Multi-Hop Wireless Networks. Informally, the goal is to transmit information from a node to a set of specific nodes in such a way that the minimal number of nodes have to communicate. Consider the following example shown in Figure 5-1.
In this example, the producers are denoted by black bowties. The consumers are denoted by squares and the circles indicate all other nodes in the network. In Figure 5-1(a), we see the given network. The goal is to connect the bowtie with the squares with the path with the minimal amount of communication. One interesting observation is that the problem is similar, but not identical, to finding a Steiner tree. It is important to realize that a Steiner tree-based solution is not necessarily optimal. The Steiner tree problem consists of finding a minimum-weight tree connecting a designated set of vertices, called terminals, in a weighted graph or points in a space. The tree may include non-terminals, which are called Steiner vertices or Steiner points. In this case, we can assume that every edge in the network is of equal cost and those Steiner vertices and points are not allowed. If this is the case, then a possible Steiner tree is shown in Figure 5-l(b). However in MHWNs the problem is slightly different. The key difference is the ability to utilize the benefits of multicasting in MHWNs. Broadcasting allows the communication of data to multiple nodes without additional cost. Therefore, the cost of a single node sending information to one of its neighbours is exactly the same as if it sent the information to multiple or all of its neighbours. Figure 5-l(c) shows a minimal path which makes use of multicasting. In the Steiner tree, 10 communications are
ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS
73
necessary to send the information from the source to the destinations. However, when multicasting is efficiently utilized, only 8 nodes are needed to communicate. Each of the grey nodes in Figure 5-l(c) denote nodes which communicate only once, but to multiple nodes, therefore their outgoing edges are only counted as a single edge. While one can easily solve the motivational problem by implicit enumeration, we will prove that the targeted problem is NP-complete. Note that the Steiner tree problem is also NP-complete. Therefore, the algorithmic goal of this work is to introduce a heuristic approach to the problem of Data Multicast in Multi-Hop Wireless Networks which makes use of multicasting and short path communications to minimize the communications in the network, and therefore save energy.
1.2
Objectives
This work was driven by a number of objectives. To find and formulate an interesting, important and frequently occurring problem in MHWN. We have formulated the problem of Data Multicast in Multi-Hop Wireless Networks. This problem has an interesting interpretation in a number of different types of Multi-Hop Wireless Networks. For example, the problem is a key component for applications such as event tracking and multimedia data delivery. Establish the complexity of the problem. We prove the complexity of the Data Multicast in Multi-Hop Wireless Networks problem to be NP-Complete by component design. Develop an efficient heuristic for the problem. We developed a heuristic technique which leverages on the geographical position of the nodes in the network to determine the most energy-efficient multicast path. Develop efficient testing techniques and instances for the problem. Since the problem is NP-complete and there are no established benchmarks, it is difficult to directly evaluate the quality of obtained solutions.
1.3
Organization
We organize the remainder of the work in the following way. In the next section, we survey the related work. After introducing the related preliminary material in Section 3, we formally define the problem, establish
74
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
its complexity and present the new heuristic algorithm. Finally, before concluding, we present comprehensive experimental results.
2.
RELATED WORK
The related work can be traced along three lines of research: ad-hoc wireless networks, data dissemination in multi-hop wireless networks, and the design and use of low power distributed systems.
2.1
Multi-Hop Wireless Networks
Cellular local area networks have emerged to become a dominating architecture entity in wireless communication. Recent technology has lead to the development of wireless ad-hoc networks, a viable alternative with the potential to reduce deployment costs and increase energy and bandwidth use efficiency. Varieties of high impact applications have been envisioned for this type of network which has the potential to impact our daily lives [ LI60, WE93]. Multi-hop sensor networks pose a need for new solutions to a number of design and efficient usage problems [ SP01, WP02]. For example, there is a need to address problems such as new signal processing techniques [TB96, PK00, ], operating systems with features such as low power design robotics [SM00], coverage and quality of service
2.2
Data Dissemination in Multi-Hop Wireless Networks
Broadcasting information from a producer to a set of consumers is a problem that has received a great deal of attention in a number of computer science fields. For example, describes how Broadcast Disks methodology can be efficiently used to provide data to a set of consumers using satellite broadcast in such a way that each consumer waits least for his data. Therefore, the main goal is to organize broadcast in such a way that data in higher demand is more often broadcast. Dan et al. and many other research addressed questions related to efficient multimedia data delivery from disks. By far the most popular and widely used scheme for broadcasting data is Internet multicast [DC90, ]. There is very little similarity between that and our problem, due to very different set of constraints and objective function. Recently, data delivery and aggregation
ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS
75
attracted the attention of theoretical computer science, and in particular the approximation algorithms community [ PP91]. The work presented by Intanagonwiwat et. al in shares some similarities with our work. For example, the goal of like ours, is to reduce the amount of energy it takes for producers to communicate with consumers, and even more specifically, it attempts to minimize the number of communications required by using a Greedy Incremental Tree. However, the difference mainly lies in the formulation of the problem. In the work, the idea is to send data from multiple producers (referred to as sources) to a particular consumer (referred to as a sink). Along the way, messages from the producers can be combined (aggregated) to form a more compact message to send along to the consumer. Thus, the work deals with minimizing the size of the message received by the consumer. In our work, messages are generated by one producer and distributed to many consumers. Thus, the message sent by nodes will be the same, and therefore our goal is not to minimize the size of the message, but to minimize the amount of communications needed to reach all consumers.
2.3
Low Power and Distributed Systems
Energy consumption is one of the main concerns in wireless ad-hoc networks. Low power techniques are one of the key issues which need to be addressed at all levels of development. A number of different works have focused on minimizing power consumption at the routing level CT99], and also for signal processing of mobile nodes Distributed systems have developed over the last two decades, beginning with techniques such as interprocess communications and remote invocation, distributed file systems, and data replications [ TA95]. In the future, distributed systems will expand to support mobility of users over wireless and ad-hoc networks. Special types of innovative distributed systems are the World Wide Web and the emerging field of wireless ad-hoc networks. The design of distributed systems is also often addressed from the synthesis point of view in the design automation community [PP91, YW95].
3.
PRELIMINARIES
In order to make the chapter self-contained, in this section we summarize all the main assumptions. We assume the following MHWN architecture throughout the rest of the chapter. For each node in the network, we assume a finite, standard
76
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
communication transmitting and listening range. We say that two nodes are neighbours if they reside within their communication range. Communication in the network is assumed to be triggered by sensing or a request by one or more nodes in the network. These requests are much smaller than actual sent data and therefore are not considered during the optimization process. Communication in current technologies is the dominant cost in terms of energy consumption in wireless networks. In today’s technology, listening is often as expensive as communication. However, in the future this may not be the case. For the sake of this work, we assume listening for communication from other nodes is equally as costly as communicating information. According to these assumptions, we define two modes for each of the nodes, on and off. Other models which do not assume equality between listening and communicating may include a third mode which is standby, or a listening state. We define the on mode to include when a node is communicating information and when it is listening or receiving information from another node. In this mode, the node is consuming a dominant amount of energy. The off mode is considered to be the minimum state in which the node consumes an absolute minimum amount of energy possible. We recognize the importance of localized algorithms in MHWNs, and the development of a localized approach is a future goal. However in this case, we assume a centralized system. We see this work as an important and natural starting point for the development of a localized approach. Currently, we see two planes of communication in MHWNs: control and data. The control plane is the operating system of the network, where the data plane is the information and data being passed to various places in the network. The control plane is orders of magnitude smaller than the data plane, and therefore will require negligible communication costs. As a result of this, a centralized approach for communicating on and off states to each node in the network is a reasonable approach. Our model of MHWNs is expanded to include two special types of nodes, producers and consumers. Producers are nodes in the network which have relevant information which needs to be passed on. Consumers are nodes which need the information which the producers have. Applications such as information dissemination, information aggregation, and event/object tracking, to name a few, all contain the notion of producers and consumers. An additional assumption in our model is that the geographical position of each node is known according to a defined origin. A number of location discovery techniques have been developed
ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS
4.
77
DESIGN APPROACH
In this section we first informally and formally define the addressed problem. Next, we establish the computational complexity of the problem. Finally, we propose a new heuristic algorithm that leverages on both graph theoretic and geometric information to find an energy-efficient solution to the data multicast problem.
4.1
Data Multicast in Multi-Hop Networks
Informally, the problem of Data Multicast in Multi-Hop Networks can be defined as follows. The goal is to select the minimum number of nodes in the network to be on, such that there is a path of communication between the producer and each of the consumers. Intuitively, by selecting the minimum number of nodes we are maximizing the number of nodes which can be in the off mode, and therefore save the maximum amount of energy. We define the Data Multicast in Multi-Hop Networks Problem formally using the Garey-Johnson format [GJ79], Problem: Data Multicast in Multi-Hop Networks Instance: Graph G =3D (V,E), subset positive integer Question: Is there a subset with where one and there exists an S, a sequence and for every C to at least one P?
4.2
subset at least where
Complexity
To justify our heuristical approach to the Data Multicast in Multi-Hop Networks problem, we prove using Karp's polynomial transform component design techniques that the problem is NP-complete. Specifically, we map the Minimum Cover problem to the Data Multicast in Multi-Hop Networks. For the sake of completeness, the formal definition of the Minimum Cover Problem is as follows: Problem: Minimum Cover Instance: Collection T of subsets of a finite set S, positive integer
78
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Question: Does T contain a cover for S of size or less, i.e. a subset with s.t. every element of S belongs to at least one member of T? Proof: We show that one can transform, in polynomial time, an arbitrary instance of Minimum Cover Problem to the Data Multicast in Multi-Hop Networks problem. Given an instance of Minimum Cover consisting of j subsets we construct a graph G = (V, E) such that C = S, |P| = 1, and |V|= x + |S| + 1. Consider, for example, the following Minimum Cover instance:
We map the instance to the problem of Data Multicast in Multi-Hop Networks in the following way. We create a single vertex, which corresponds to the collection T. For every element in S, we create a vertex, and include each vertex in the subset C. Each subset in T represents a single vertex, The graph G, for the example given above is shown in Figure 5-2. We place at the top of the graph and create edges from to each of the/ subsets of T, or vertices In the final row, each element of S is shown, represented by Each of the subset nodes, connects to the corresponding elements in which it contains vertices). If a solution to the Data Multicast in Multi-Hop Networks problem can be found where is equal to some K, then a solution to the Minimum Cover problem can be found with
ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS
79
Consequently, we have shown that the Minimum Cover problem polynomially transforms to the problem of Data Multicast in Multi-Hop Networks. It is easy to see that the Data Multicast problem is NP, because one can easily check using breadth-first search and enumerate to see if the proposed solution is correct. Therefore, the Data Multicast in Multi-Hop Networks is a NP-complete problem.
4.3
Line-directed Node Selection Heuristic
Our heuristic approach to the Data Multicast in Multi-Hop Networks problem considers a network with one producer and n consumers. It can be easily generalized by applying the same procedure to each producer in the general case.
The algorithm consists of three main ideas. The first is to use linedirected information to select nodes which will communicate between the
80
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
producer and consumers. The second is to construct the minimal spanning tree, from all the selected nodes, with the largest number of leaves. The leaves represent selected nodes which are not necessary in order for the consumers and the producer to communicate. The last idea is to prune from the tree all the leaves which are not consumers or the producer. The line-directed algorithm calculates what we call a sphere of influence. For a given node, n, all of its neighbours are included in the nodes sphere of influence. If n communicates to any node, all of the other neighbours can detect this communication, assuming the nodes are on or in the sensing mode. We then consider the neighbours of a node which we know to be on, to be influenced by that node, because communication to them is obtained at no additional cost. For each consumer in the graph, we introduce a line between it and the producer, which we will call guidelines. These guidelines never change, and are used to determine the path from the producer to the consumers. We begin the line-directed algorithm by placing all the nodes in the network in the off mode except for the producer. We continually turn nodes on which are selected to be on the path to the consumers, until all the consumers are on and each have a path to the producer. In order for a node to be turned on, and form a path to the consumer, we determine the sphere of influence of the current nodes which are in the on mode. For each of the nodes in the sphere of influence, we sum In order for a node to be turned on, and form a path to the consumer, we determine the sphere of influence of the current nodes which are in the on mode. For each of the nodes in the sphere of influence, we sum up the perpendicular distance from the node to each of the guidelines and the distance from the node to the consumer. Note that once a consumer is on and connected to the producer, we remove its guideline from future consideration. Also, if the perpendicular intersection point of the node and the guideline is not on the line segment between the producer and the consumer, we disregard it. We normalize the calculated sum of each of the nodes in the sphere of influence and select the node with the minimum value. The selected node is turned on and each of the node's neighbors is included in the sphere of influence. If any of the consumers are neighbors of the node, they are also placed in the on mode. It is often the case, that the best node at a single iteration of the algorithm is not the best node to use when constructing communication paths with the minimum number of nodes. As a result, some nodes maybe unnecessarily on in the network. Therefore, we find a minimal spanning tree on the final state to help eliminate these nodes. Once the algorithm has found some path(s) from the producer to all the consumers, we build the minimal spanning tree with the maximal number of
ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS
81
leaf nodes (MST-MaxLeaf) from all the nodes which are on. Each node which is a leaf node can later be pruned under the assumption that it is not needed on the minimal path between the producer and consumers. We use a greedy algorithm which begins with the producer and builds outwards. At each step, the MST-MaxLeaf algorithm examines all the neighbours of all the leaf nodes in the tree and selects the neighbour which has the greatest number of neighbours not in the tree. Once we have constructed the minimal spanning tree with the maximum number of leaf nodes, we then iteratively prune or turn off all nodes which are leaves in the tree at the current iteration. For example, consider the MHWN shown in Figure 5-3. We represent the network as a grid, where each intersection represents a node, and each edge corresponds to a communication edge. A grid design of the network is only used for simplification and example purposes. The line-directed algorithm can be applied to an arbitrary MHWN.
In this example, we have 5 consumers (squares) and 1 producer (bow tie). In Figure 5-3(a) the network is shown along with the guidelines for each of the consumers in the network. According to the line-distance algorithm, the producer is on and the four nodes, A, B, C, and D, which can communicate with the producer are in the sphere of influence (shown in Figure 5-3(b)). For A, B, C, and D, we determine perpendicular distance for each of the nodes to the guidelines and their distance to each of the consumers. Recall, that if the perpendicular distance to the guideline does not fall on the line segment between the consumer and the producer, then the measurements are not taken into account. For example, for nodes A and B, we calculate the perpendicular distance and physical distance to consumers 1, 2, and 3. When calculating the sum for nodes C and D, we only consider consumers 4 and 5.
82
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
The node with the minimal normalized sum will be turned on and its neighbours will be added to the sphere of influence, in this case, node B is turned on. In the next iteration, calculations will be made for each of B's neighbours. Once paths to each of the consumers have been established, the MST-MaxLeaf is established and then iteratively pruned. In this case, no additional nodes were on therefore there was no need to find the MSTMaxLeaf or to prune. The minimal communication path to all consumers is shown in Figure 5-3(c).
5.
EXPERIMENTAL RESULTS
The proper evaluation of the effectiveness of the developed heuristic for the Data Multicast problem poses some technical and logistic problems. Technical, because the problem is NP-complete and therefore, in general we do not know how to find the optimal solution. Logistic, because the problem is not previously studied and therefore, we cannot compare the new algorithm against the previous on standard benchmarks. In this situation there are two sound, but conceptually different, ways to evaluate an algorithm. The first involves creating instances of the problem which the optimal solution is known, yet the solution is not obvious and does not favour any one particular algorithm (especially the algorithm in question). Applying this technique to ours problem means that before we can determine the effectiveness of our algorithm, we first have to create instances of our problem in which the optimal solution is known. Creating these instances leads to several difficulties in particular when one tries to generate a structurally diverse set of examples. Therefore, we have taken a different approach to evaluate the new algorithm - the minimum sharp bound. The idea is to calculate bounds in such a way that the optimal solution cannot be better and yet the bounds are as close as possible to the optimal solution. To accomplish this goal, we evaluate two separate statistics. Our problem is to determine the minimum number of communications such that all consumers can receive the information from the producer. So, the first statistic used to evaluate our algorithm is calculated by determining a lower bound on the number of communications it would take for the producer to talk to each consumer separately. Then, we determine the number of communications it would take our solution to talk to each consumer separately. We determine the excess number of communications used by our algorithm and express it as a percentage greater than the minimum calculated previously, and finally, we take the average over all the paths. To calculate the minimum number of
ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS
83
communications required for a producer to communicate with a consumer, we simply calculate the breadth-first-search shortest path from the producer to the consumer. To determine how many communications are required for the producer to communicate with the consumer in our solution, we calculate a breadth-first-search shortest path using only the nodes that we calculated to be on. Thus, the closer our solution is to the breadth-first-search shortest path, the closer our solution is to optimal. However, it is important to note that in many cases, due to the branching of communications, the breadthfirst-search shortest path from the producer to a consumer is not the optimal solution, and so, having more communications than the breadth-first-search shortest path requires does not indicate that our solution is poor. The second statistic presented is the percentage of sensors that need to be on and are not consumers; obviously, consumers must be on if they are to hear the message communicated by the producer. To calculate this second metric, we simply determine the number of sensors turned on by our algorithm and divide by the total number of sensors. Once again, it is important to note that turning on the minimum number of sensors does not necessarily guarantee the minimum number of communications, and again, this is due to the branching of communications.
We ran several test cases using our algorithm with the number of sensors and consumers, and sensor communication radius as the parameters. The number of sensors varied from 200 to 1000 in increments of 200, the percentage of consumers varied from 10 to 250, and the sensor communication radius varied from 0.05 to 0.3 (assuming that all sensors were located in a 1x1 square). Table 5-2 displays a subset of the results. It is apparent that while the quality of the solution varies relative to the lower bounds, it is consistently competitive. In Figure 5-4 and 5-5 we show two examples of networks with ten consumers and 300 nodes randomly placed, with uniform communication radius of 0.10.
84
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
ENERGY-EFFICIENT DATA MULTICAST IN MULTI-HOP WIRELESS NETWORKS
6.
85
CONCLUSION
We addressed the problem of efficient Data Multicast in Multi-Hop Wireless Networks. The goal is to minimize the energy consumption while delivering data to all consumers in a multi-hop wireless network that requested it. We formulate the problem and proved that the problem is NPcomplete. The technical highlight of the chapter is an efficient heuristic that utilizes information about the geographical position of the nodes in the network to find the energy-efficient communication path. The experimental results indicate that the new algorithm produces solutions that are close to sharp lower bounds.
ACKNOWLEDGEMENT This material is based upon work supported by the National Science Foundation under Grant No. ANI-0085773. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).
This page intentionally left blank
Chapter 6 LOW-ENERGY SOFTWARE OPTIMIZATION FOR THE ARM7 PROCESSOR: THE SOFTWARE SCHEDULING APPROACH
Giannis Sinevriotis and Thanos Stouraitis Department of Electrical and Computer Engineering University of Patras, Greece E-mail: {synevrio,thanos}@ee. upatras.gr
Abstract:
This chapter presents a novel list-scheduling algorithm for low-energy software execution. The aim of the instruction scheduling is the minimization of the inter-instruction energy costs that are due to the switching activity of the processor circuit. The input of the scheduling algorithm is the original code sequence. Its output is a re-arranged sequence of the same instructions that minimizes the total inter-instruction effect cost and that has no impact on the program functionality. The inter-instruction effect cost is determined by means of physical measurements. The target architecture has been the ARM7TDMI processor core. The results of the optimization algorithm have been validated upon the implementation of the IEEE 802.11 protocol microcode for wireless local area networks.
Key words:
ARM, Software optimization, List scheduling, Power optimization.
1.
INTRODUCTION
Low-Power design has been established as one of the most important design tasks in the microelectronics industry. In the recent years the need for power-optimal design has been amplified by the explosive growth of mobile applications, especially consumer electronics. The splitting of functionality between hardware and software components characterizes mobile embedded applications. Transferring functionality from
88
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
hardware to software has the advantages of decreasing substantially the product development cycles, as well as allowing the easier adaptation of existing hardware to new requirements. However, transferring functionality from hardware to software domain causes significant performance degradation as well as a substantial increase in power dissipation. Extending the power optimization strategies to include the software component of embedded systems has, thus, become a necessity. This can be done by optimizing the partitioning of functionality between hardware and software, by optimizing the algorithms used, and, finally, by optimizing the software itself. This third option has received very little attention; mainly due to its limited operational potential that stems from the fact that embedded system architectures exhibit uncommon instruction-level power dissipation characteristics. It has been shown that the total energy cost of a program cannot be calculated by the summation of the energy costs of the individual instructions. In real programs, running on real processors, there are other effects that have an impact on the total energy cost, such as the effect of changing the circuit state and pipeline stalls. These effects have also to be taken into account in order to establish accurate instruction-level power models. The components of these power models are: 1. Basic Costs. These are the costs that are associated with the basic processing required to execute the instruction. 2. Inter-Instruction Effects. The switching activity in a circuit, and therefore the associated power consumption, results from the change in two consecutive sets of inputs. For sequential circuits, the effect of circuit state can expand to many instructions; it has been shown however that is suffices to examine pairs of instructions TL98]. 3. Other Costs. These cover all the other processor-specific effects that may affect the energy dissipation, such as the cost of cache misses and pipeline stalls. Taking these costs into account, the overall energy cost P is given by Equation 1
of a program
, where Bi the base cost of the instruction i, Ni the number of the occurrences of the instruction i, Oij the energy overhead associated with the circuit state when the pair of instructions i, j, is executed, and Ek the energy
LOW-ENERGY SOFTWARE OPTIMIZATION FOR THE ARM7 PROCESSOR: THE SOFTWARE SCHEDULING APPROACH
89
costs of other effects. The aforementioned formula provides quite accurate results in practice TL98].
2.
INSTRUCTION COST MEASUREMENTS
To obtain the required instruction costs, the process originally proposed by Tiwari et.al. has been followed. In the same fashion, a laboratory setup was constructed to measure the current drawn during the execution of specially formulated instruction sequences that isolate the effect of instruction costs. All the basic costs were measured; a scaled-up approach was taken to measure the impact of inter-instruction effects. To cope with the overwhelming amount of instruction combinations that need to be taken into account to cover all possible instruction pairs, the instructions were grouped according to their power-dissipation characteristics. More on the physical measurement process, as well as the complete set of instruction costs, can be found in [SS99, ES].
3.
THE PROPOSED ALGORITHM
The aim of the instruction scheduling is the minimization of the interinstruction energy costs that happen due to the switching activity of the processor circuit. The input of the scheduling algorithm is the original code sequence; its output is the rearranged sequence of the same instructions that minimizes the total inter-instruction effects cost and that has no impact on the program functionality. The application of the scheduling algorithm is done on a basic block-by-basic block basis. A basic code block is a solid portion of code; i.e. a code block that is always executed sequentially, thus eliminating control dependences in the code. The localization of the input of the scheduling algorithm is necessary in order to ensure that the code functionality is not violated. The generic scheduling process is of NP-Complete computational complexity; its complexity increases exponentially with the complexity of the input. Thus, a number of heuristic scheduling algorithms have been proposed, that produce near optimum results in most cases. The list scheduling algorithm JA96] has been adapted for application in our work. It provides good results in practice and has a linear complexity factor O (n).
90
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
The framework for the optimization process is shown in Figure 6-1. The steps shown in Figure 6-1 are described in more detail in the following sections.
3.1
Partitioning of the input code in basic blocks
The algorithm for the partitioning of the input code into basic blocks has the following steps 1.
2.
3.2
The set of leaders that constitute the first statements of every basic block is determined. The rules are: a. The first statement of the code is a leader. b. Any statement that is target of a branch is a leader. c. Any statement that follows a goto or jump statement is a leader For every leader a basic block is formed. This consists of all the statements until the next leader.
Finding code dependences and derivation of the dependence table
Code dependences determine the available amount of code parallelism. There are 3 possible types of code dependences in a code block Data dependences: We say that an instruction l is data-dependent on 1. the instruction k, if either one of the following holds: a. Instruction k produces a result that is used by instruction l.
LOW-ENERGY SOFTWARE OPTIMIZATION FOR THE ARM7 PROCESSOR: THE SOFTWARE SCHEDULING APPROACH
91
b. Instruction l is data-dependent on instruction m, which is datadependent on instruction k. 2. Name dependences. a. Anti-dependences: We say that there is anti-dependence between instruction k and instruction l, when instruction l writes a register or memory location that instruction k reads. b. Output dependences: Output dependence occurs when instruction k and instruction l write the same register or memory location. An example of code dependence analysis is given in Table 6-1.
When the input code block has been analyzed, the next step is the derivation of the dependence table. The dependence table for a basic block consisting of n instructions is an n x n table, its values being: if instruction k is dependent on instruction l. 1. if instruction k is not dependent on instruction l. 2.
3.3
Register renaming
It is possible to reduce the code output dependences, by using the technique called register renaming. By this technique, if the instruction is name-dependent on the instruction (k
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
92
instruction k is not name-dependent on any other instruction in its basic block. The register renaming algorithm has the following steps: 1. 2.
Make a list of the registers L that are not in use. For each basic block: a. Find all the name dependences. b. While L is not empty, for each instruction i starting from the bottom of the code, find the set K of all the name-dependent instructions. c. For each name-dependent instruction k in K, i. Change the instruction 's destination operand with in L. ii. Update the list of the available registers d. Restore the original L set.
It should be noted that the application of the register renaming algorithm, assumes that we can perform global input code analysis to find the list of the globally available registers. This should include global lifetime register analysis
3.4
Implementation of the list scheduling algorithm
The dependence table serves as input for the list scheduling algorithm. The main steps of the algorithm are the following: 1. Find the starting ready set R. The ready set is the set of instructions that can be scheduled, i.e. instructions independent of any following instructions. 2. Schedule the first instruction. 3. For each instruction i in the ready set, find the set of all the dependent instructions. a. b. c.
4.
3.5
Select the instruction j in
that minimizes the inter-instruction cost
Schedule instruction i. Update the ready set R= R -{i} + {j} While the ready set R is not empty: a. For each instruction j in the ready set L. i. Calculate the inter-instruction cost of the scheduled instruction and j. ii. Find the instruction k that minimizes the cost. iii. Schedule instruction k. iv. Update the ready set. where the set of instructions dependent on instruction k.
Example
For the code segment shown in Table 6-1, the scheduling process is as follows: 1. The starting set R is {5}.
LOW-ENERGY SOFTWARE OPTIMIZATION FOR THE ARM7 PROCESSOR: THE SOFTWARE SCHEDULING APPROACH
93
2. Since the starting set R has only one instruction, instruction 5 is
scheduled. The updated ready set becomes R = {7, 9, 10, 11, 14, 16}. 3. The iterations of the list scheduling algorithm are shown in Table 6-2. 4. The resulting optimized code is shown in Table 6-3.
Note that the scheduler has grouped the load/store and ALU instructions to the widest possible extend. In fact, the circuit state overhead is increased when two subsequent instructions utilize different processor resources.
94
4.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
RESULTS
The scheduling algorithm proposed in this chapter has been adapted and integrated in our energy-conscious software tool. It has been applied upon a commercial implementation of the IEEE 802.11 standard protocol, for wireless local area networks, running on the ARM7TDMI processor. The input consisted of 1427 lines of code, in 16 input files. Register renaming was not applied, since the input was divided into many files making it difficult to perform global register lifetime analysis. The code was divided into 433 basic blocks corresponding to an average of 3.3 instructions per basic block. The fact that the average block size is small has reduced the potential for extensive code scheduling. The results have shown a 4.54% decrease in the total energy dissipation of the running protocol. To quantify the impact of the application of register renaming, we applied the proposed scheduling algorithm on a solid portion of code, consisting of 151 lines. The results are shown in Table 6-4.
Coupled with other optimization strategies that were implemented, such as operand replacements, total energy savings accounted for 9.28%. The results were validated in practice by measuring the actual current drawn during the execution of the optimized and non-optimized versions of the code. Results are given in Table 6-5.
From the results in Table 6-5, it is evident that our estimation framework has been quite accurate in practice. Detailed analysis of the obtained results and of the other optimization strategies can be found in [ES].
5.
CONCLUSIONS AND FUTURE WORK
The results obtained may not seem very significant. Part of this can be accounted to the nature of our demonstrator application. Being an event-
LOW-ENERGY SOFTWARE OPTIMIZATION FOR THE ARM7 PROCESSOR: THE SOFTWARE SCHEDULING APPROACH
95
driven application, the protocol consists of many conditional branches that result in small average block size. This has effectively reduced the scheduling potential. However, one has to take into account that the achieved software optimization is completely independent from any hardware optimizations. Moreover, it does not lead into any performance degradation, as programs that take fewer cycles to execute are typically more energy-efficient. Another point is that the whole process can be automated (actually we have implemented an optimizing tool for the ARM7TDMI core), and it has to be applied only once for a given software. The potential of the method may appear to be limited, as accurate cost measurements have to be taken for the application of the method on any alternative architecture. However, we believe that it is possible, at the cost of slightly reduced estimation accuracy, to simplify the whole process and make its application viable to other architectures. Taking advantage of the strong correlation of the inter-instruction effects costs, depending on the processing units they utilize, we think it will be enough to measure only a reduced set of inter-instruction effects costs and assign typical cost values to all possible combinations. This will be part of our future work
ACKNOWLEDGEMENTS This work was funded by the European Union BSD Project 25403 “SOFLOPO”.
This page intentionally left blank
Chapter 7 POWER-AWARE EMBEDDED SYSTEM DESIGN USING THE MILAN FRAMEWORK1
Amol Bakshi, Jingzhao Ou and Viktor K. Prasanna Department of Electrical Engineering – Systems University of Southern California 3740Mc Clintock Ave., Los Angeles, CA, US 90089
Abstract:
MILAN is an integrated simulation framework for designing low-power, highperformance computing systems. The framework is modular and extensible, allowing for plug-and-play integration of simulators, visualization tools, and even user interfaces. This chapter describes the use of the multi-aspect modelling and simulation capabilities of MILAN for power-aware design of a class of distributed sensor networks.
Key words:
Energy efficiency, Design environment, Networked embedded system, Hierarchical simulation.
1.
INTRODUCTION
The proliferation of portable devices such as personal digital assistants, notebook computers, camcorders, etc., reflects a new era of computing system design. New system architectures are required to meet stringent performance requirements, while simultaneously satisfying constraints on factors such as power consumption, hardware area, time-to-market, and cost of the device. By judiciously implementing some parts of the system in software (i.e., on general-purpose processors, DSPs, or AS IPs) and others in 1
This work is supported by DARPA Power Aware Computing and Communication Program under contract no. F33615-C-00-1633 monitored by Wright Patterson Air Force Base
98
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
hardware (i.e., on ASICs or FPGAs), system-wide performance requirements can be met. Also, advances in semiconductor technology have made it possible to implement the entire system functionality on a single chip, enabling savings in area and power consumption. Design tools and methodologies traditionally focused on latency and throughput as the metrics to be optimized. Simulation suites were typically targeted towards a very specific class of architectures, and the underlying analytical performance models did not include power estimation. For a growing fraction of embedded architectures, reducing the overall power consumption has become an overriding priority, even if the power/performance tradeoffs necessitate a compromise on other features of the system/device. Analytical modelling of power dissipation in hardware and the design of power-aware algorithms [BM97, SC00] are areas of active research. New simulators for estimating energy consumption are being developed NS, SC01, based on different analytical models. A new class of integrated system design frameworks is required to address the challenges in the design of single-node and distributed embedded systems. Such frameworks should facilitate modelling of hardware features (such as dynamic voltage scaling for processor cores, and power states for memories) that support application-level power management. The designer should be able to use simulation tools and analytical models of his/her choice. Finally, with the large number of alternate designs that are possible for complex, mixed hardware-software systems, a methodology for automatic design space exploration is required, that traverses the design space and identifies a small set of design alternatives based on user-specified requirements and constraints. Specifically for power-aware design of networked systems such as the distributed sensor network (the case study in this chapter), the design framework should allow for evaluation of tradeoffs between communication and computation energy in different system components. In this chapter, we describe how MILAN2 (Model-based Integrated simuLAtioN framework) can be used for power-aware design of distributed embedded systems. Details of the general MILAN architecture can be found in The specific contributions of this work are: (i) a modelling and simulation environment for power-aware design of multi-node sensor networks (specifically, a seven-node remote netted acoustic detection system [SR95]), (ii) multi-granularity system simulation using a high-level analytical model [SP02] to obtain rapid performance estimates, and ns-2 2
milan (Hindi): unification. http://milan.usc.edu/
POWER-AWARE EMBEDDED SYSTEM DESIGN USING THE MILAN FRAMEWORK
99
[NS] and Wattch as the low-level simulators to obtain detailed performance statistics, (iii) horizontal simulator integration, i.e. results from node-level simulation are used to automatically configure the scenario for network simulation, (iv) vertical simulator integration, i.e., results from lowlevel simulation are used to automatically update parameters of the highlevel analytical model, and (v) all the above functionality provided to the user through a single graphical interface that performs the simulation, result integration, and model refinement in a transparent manner. In this chapter, we do not propose any specific node-level or networklevel power modelling and optimization techniques for wireless sensor networks. However, if simulation or optimization tools based on existing techniques are available with the designer, MILAN provides a well-defined method for integrating them into the framework when possible. MILAN also includes an easy-to-use graphical interface, formal mechanisms to model applications, resources, and performance constraints, and a set of integrated simulators for various system components. The user is not required to have a detailed knowledge of the input/output interfaces of the integrated simulators, which are automatically configured and executed by the framework. The rest of the chapter is organized as follows. Section 2 is a brief discussion of the design philosophy of MILAN. Section 3 defines the scenario and design objectives for the illustrative case study. Sections 4 and 5 describe how MILAN was used to model and simulate a distributed sensor network with a focus on evaluating energy consumption. Section 6 is a brief note on automatic design space exploration in MILAN. Design space exploration and optimization is not part of the case study implementation. Section 7 mentions related research, and we conclude in Section 8.
1.1
The MILAN Approach
MILAN is a modular and extensible design and simulation framework for complex computing systems, specifically targeted for power-aware embedded architectures. In this section, we outline the key elements of the design methodology supported by MILAN. More information about the design of MILAN can be found in The design of a programmable embedded system involves performance evaluation of alternate task implementations and task-to-resource mappings, and using the performance numbers to suitably refine the application, resource, and mapping models. The Y-chart design methodology (Figure 7-1) is an attractive approach because “it fosters reuse, is
100
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
invariant to a specific design level, permits a systematic exploration of the system design space, and considers the application-to-architecture mapping as an independent constituent of the system representation.” [KI00]
MILAN is a model-based integrated simulation framework for embedded system design and optimization that supports the flow illustrated by the Ychart. System design refers primarily to determining the optimal mapping of individual tasks that comprise the target application onto the suitable hardware components of the target embedded system architecture. There are two core ideas that are reflected in MILAN: (a) separating the storage of model information from its usage, and (b) using formal techniques to define the system abstractions themselves. Separating storage of model information from its usage: The Y-chart approach advocates distinct representations for applications, architectures, and mapping. The benefit of this approach is that the designer has a choice of evaluating alternate task implementations, or use different hardware resources, or change the mapping, or a combination of the above. In addition to supporting this methodology (from a designer's perspective), MILAN implements an even basic separation: between storage of information that represents the target system model and its use by other system components. These include the user interface, component-specific simulators, system-wide simulators, etc. A model database acts as the central repository for all model information, which is stored in a canonical form. All components of the framework that need to manipulate this information have to use the same well-defined
POWER-AWARE EMBEDDED SYSTEM DESIGN USING THE MILAN FRAMEWORK
101
programming interface. This enables plug-and-play integration of all framework components, including the user interface3. For example, integrating a new simulator translates into writing a piece of software (called model interpreter) that uses the database's interface to extract the relevant model parameters and writes the simulation output back into the database. Writing a model interpreter requires detailed knowledge of the particular simulator but once integrated, the designer is shielded from the workings of the simulator. He/she can instead focus on system-level design decisions based on the simulation results. Storing simulation results as just another model parameter also enables a form of refinement of high-level performance estimates4 based on low-level simulation results. Another impact concerns design reuse. There is a continuous evolution in embedded system hardware, and the designers’ understanding of the system, as reflected by increasingly accurate performance models. Our approach allows the framework to evolve with such changes, which translate into modification of existing modelling paradigms or addition of new paradigms. If an existing paradigm has to be modified (e.g., a set of parameters that characterize a particular resource is to be expanded), it is important to ensure that existing model information is not lost. Finally, the concept of a model database allows model migration [MO], i.e., automatic conversion of the database schema that represents the old modelling paradigm into a new schema that represents the modified paradigm. Model migration combined with an update of model interpreters and other tools, ensures that legacy model information is reused for later designs. Formal mechanisms to describe system abstraction: The second idea is that of meta-modelling. Domain-specific modelling environments (“networked embedded systems” is an example of a domain) provide the user with abstractions that can be used to instantiate a class of systems in terms of those abstractions. This Model Integrated Computing (MIC) [SK97] approach then allows for various computational transforms to be performed on these models. Meta-modelling is the extension of this philosophy to include the modelling of the modelling environments themselves
3
4
The following sections describe the integration of a network simulator ns-2, a node-level simulator Wattch, and a high-level estimator based on a system-wide energy model. The following sections demonstrate the refinement of high-level model parameters through low-level simulation using the ns-2 and Wattch simulators.
102
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
For instance, in the context of SoC modelling and simulation, a particular application modelling paradigm (such as [LM87]) allows the designer to represent a large number of applications that can be abstracted in terms of that model. Most of the modelling and simulation environments for embedded systems support a set of widely used application modelling paradigms. This allows for the modelling of a very large class of real applications. Almost none of these frameworks, however, have a formal representation for the modelling paradigms themselves. Although it is theoretically possible to extend these environments to support new modelling paradigms, the process is tedious at best, and impractical in most cases. By making the meta-model as the primary entity in the framework, our approach enables the definition of an arbitrary number of modelling paradigms. The Generic Modelling Environment (GME2000) [GM] developed at the Institute for Software Integrated Systems, Vanderbilt University, is a graphical tool suite that supports automatic synthesis of domain-specific modelling environments. GME2000 provides the graphical user interface and underlying software infrastructure for MILAN. The next section describes how the above concepts are applied to develop a modelling and simulation environment for application development on distributed sensor networks.
2.
MODELLING AND SIMULATION OF A DISTRIBUTED SENSOR NETWORK
2.1
The Scenario
The block diagram of the seven-node Automatic Target Recognition application chosen for this case study5 is shown in Figure 7-2. The seven nodes form a sensor array that performs real-time target tracking. Each of the seven nodes is equipped with sensors to monitor acoustic signals from the environment. One of the nodes (‘clusterhead’) processes the sampled signals, computes line-of-bearing (LOB) estimate of the target, and transmits it to the end-user. By gathering LOB estimates from multiple such clusters, 5
The ATR application was chosen because it is one of the challenge problems of the DARPA Power Aware Computing and Communications program that is funding the MILAN effort. The model and implementation is general enough for the design of any system that involves a set of sensor nodes with data communication within them.
POWER-AWARE EMBEDDED SYSTEM DESIGN USING THE MILAN FRAMEWORK
103
the exact location of the target can be obtained. There are three main stages in this computation. First, the sample of each channel is Fourier transformed. A frequency domain beamforming (BF) algorithm estimates target bearing along twelve different directions (beams), and delay-sum BF delays each signal by a time specified by the microphone array geometry for coincidence on a given beam. Once the signal energy in each of the twelve directions is obtained, the LOB estimator finds the direction with the largest signal energy and transmits it to the end user.
A naïve approach to task mapping in this system is for all sensors to collect and transmit samples in a raw format to the clusterhead where FFT, BF and LOB are performed for the entire data set of the sensor array. All the clusterhead processing should be accomplished before the next set of samples is transmitted, thereby meeting end-to-end throughput requirements. A more energy-efficient design for this system is for each of the six sensor nodes to perform the FFT computation locally and transmit its result to the clusterhead, which computes BF and LOB on the results [WC01]. For the same throughput requirement, this approach is obviously superior to the naïve implementation. For instance, if dynamic voltage scaling is available, the voltage/frequency of the sensor nodes can be lowered to save power. The increase in per-node FFT processing time is compensated by the fact that the seven FFTs are now performed in parallel instead of sequentially at the clusterhead. The node configuration in our case study consists of a processor (with DVS if available), memory, sensor, and a radio card. Each node can have different values for parameters such as radio card transmission/reception energy, processor frequency, memory capacity, etc.
2.2
Design Objectives
The objectives of the sensor network designer are as follows:
104
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
To estimate the performance of task implementations (FFT, BF, and/or LOB) on each node configuration in terms of execution time and energy consumption. Multiple (software) implementations could be available for each algorithm. To rapidly obtain approximate estimates of system-wide power consumption of a particular task-to-node mapping by using a high-level analytical model available to the designer. To obtain detailed, cycle-accurate estimates of energy consumption in the network and for each node, for a specific mapping. To refine the analytical model parameters based on low-level simulations of the sensor network.
3.
SYNTHESIS OF A DOMAIN-SPECIFIC MODELING ENVIRONMENT
The structure and properties of the target system are described by the user through modelling paradigms. Modelling paradigms are the basic building blocks and composition rules that govern how any system in a particular domain is to be modelled. The composition rules and semantics associated with each block depend on the particular paradigm. MILAN currently provides an application modelling paradigm, a resource modelling paradigm, and a paradigm to model the task-to-resource mapping. GME2000 provides a graphical UML-like language to formally describe the modelling paradigms, which are then automatically synthesized into a domain-specific modelling environment as described by the paradigms. In this chapter, the ATR application implemented on a seven-node sensor network is a specific instance of a system in the broader “domain” of distributed sensor networks.
3.1
Application Modelling
The basic block of the application modelling paradigm in this case study is an object called a “task group”. A task group can consist of one or more tasks that process a single input sample and produce an output. However, a task group is assumed to be atomic, i.e., the current input sample should be completely processed before the computations on the next sample can be started. Pipelining within a task group is not supported; mostly for ease of high-level performance modelling. The total application is modelled by the user graphically as a set of such task group blocks with directed connections.
POWER-AWARE EMBEDDED SYSTEM DESIGN USING THE MILAN FRAME WORK
105
The directed connections represent the data transmission between tasks. The amount of data transferred between a pair of task groups is to be explicitly indicated by the designer by labelling the appropriate directed connection. The actual implementations (codes) of the individual tasks are indicated by labelling each task block with the name of the file that contains the code for that functionality. Note that the application modelling paradigm is just a formal mechanism to capture information about the system that will be useful for simulation and performance estimation. The modelling paradigm itself does not impose any semantics regarding the nature of computation or communication that is represented by the blocks and the directed connections respectively. The same information can be processed in semantically different ways by multiple model interpreters, depending on the objective of the processing (e.g., visualization, simulator configuration, etc.). Figure 7-3 shows the combined modelling paradigm for application, resource, and mapping models.
The general MILAN application modelling paradigm as described in allows each task within the application to have alternates at the design level and/or the implementation level. An example of a design-level
106
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
alternate is a parallel implementation of an algorithm as compared to its sequential implementation. An example of an implementation-level alternate is a C-language code of a particular algorithm for a RISC processor versus its hardware implementation on an FPGA. The MILAN user can indicate explicit design and implementation alternatives in the application model to capture this design space of possible implementations, instead of just a point solution. We chose not to implement task alternates as part of the application modelling paradigm for the distributed sensor network system, because the focus of this chapter is on demonstrating multi-granularity simulation and automatic parameter refinement of the high-level analytical model, and not automatic design space exploration.
3.2
Resource Modelling
The resource model captures all information required for driving the integrated simulators and other tools. The set of attributes associated with a particular component of the resource model is a union of the sets of attributes required by each of the integrated simulators for that component. A new simulator being integrated into MILAN might require parameter values that are not captured by the existing modelling paradigm. Extending the paradigm and generating a new modelling environment that does capture the additional information is not difficult. This is because the resource modelling paradigm itself is defined using the graphical meta-modelling language that is automatically synthesized by GME into the domain-specific modelling environment exported to the user. The resource modelling paradigm for the distributed sensor network consists of a node as the basic building block. Each node contains a CPU, a memory unit, a sensor, and a radio card for transmitting and receiving information. Each node also has a set of coordinates in a 2-dimensional plane that indicate its position relative to other nodes in the area. The attributes that are to be provided by the designer for each block are required to drive the integrated simulators as described in the next section. Figure 7-4 shows an actual resource instance described using the paradigm. A simple modelling paradigm to explicitly associate a task group with a particular node instance was also implemented for this case study. The mapping paradigm allows the user to experiment with different task allocation strategies and evaluate system performance. The modelling paradigms described here are prototype implementations and do not provide all the capabilities ideally required for modelling a generic distributed sensor network. For example, task scheduling is not explicitly modelled. Also, automatic design space exploration is not supported because the designer has
POWER-AWARE EMBEDDED SYSTEM DESIGN USING THE MILAN FRAME WORK
107
to indicate the values of all attributes relating to the network and each node, and also indicate the mapping.
Table 7-1 lists some of the important attributes that can be specified and modified by the user through the domain-specific graphical modelling environment for this system. Some parameters are used to configure lowlevel simulators, and other parameters are used by the high-level analytical model to rapidly estimate approximate system-wide performance values.
108
4.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
HIERARCHICAL SIMULATION AND AUTOMATIC MODEL REFINEMENT
The previous section dealt with the nature of the user interface to the modelling and simulation environment for distributed sensor networks. To demonstrate the hierarchical simulation and automatic model refinement through MILAN, we integrated two low-level simulators and one high-level performance estimator. The accuracy of the performance prediction depends on the quality of simulators being integrated, and is not guaranteed by MILAN, which provides only the framework for integration. The focus of this work is on power-aware design of distributed embedded systems. Therefore, the Wattch simulator was included to provide node-level energy consumption estimates, and the ns-2 network simulator [NS] was used to evaluate the energy consumed in data transmission through the wireless network. The system-wide energy model described in [SP02] was implemented and integrated as the high-level estimator. All the simulation tools are driven through the single system specification by the use of model interpreters (defined in Section 2). Merely using the separate model interpreters for Wattch and ns-2 does not provide an idea of the system-wide performance, even at the low level. This is because the interval between successive data transmissions among the sensor nodes depends on the time taken by the individual nodes to process the periodic input from the sensor. We implemented a small wrapper code around the two model interpreters that parses the output of the Wattch simulator (computation cycles) to automatically configure the transmission interval for the ns-2 network simulation. If the user changes the task-to-node mappings or the implementation of one or more tasks, the change in processing latency is consistently reflected in the network simulation, and accurate estimates of total system energy are obtained. Three of the main parameters required by the high-level analytical model in [SP02] are the computation energy per operation of the processor, the storage energy per byte for the memory element, and the energy for transmitting (receiving) a byte of information through the radio card in the sensor node. These values are expected to be already available to the highlevel estimator. The designer can obtain these through real experiments, offline simulations, data sheets for the hardware elements, or from prior experience. The accuracy of these estimates determines the accuracy of the prediction of system-wide performance. When low-level simulations are run (through ns-2 and Wattch in this instance), these parameters can be estimated from the accurate energy estimates obtained from the simulation.
POWER-AWARE EMBEDDED SYSTEM DESIGN USING THE MILAN FRAMEWORK
109
In MILAN, automatic refinement of the analytical model parameters is possible because these are stored in the model database like any other system attribute. All model interpreters can read from and write to any of the fields of the model database. In the distributed sensor network modelling environment that we implemented, the initial values of these parameters are entered by the user through the graphical interface. When low-level simulations are run, these values are calculated by the model interpreters as part of the feedback mechanism for simulation results, and used to update the user-specified values with more accurate ones. When the high-level estimator is invoked again, it uses the refined values of the parameters, and thereby yields more accurate performance estimates for the system.
The interaction between the simulators is illustrated in Figure 7-5. By sharing the information through the centralized repository, the simulators do not need to directly interact with each other. Also, the designer is not required to have any knowledge about configuring and executing simulators, and interpreting the output(s). The high-level estimation, low-level simulations, and parameter refinement are transparent to the designer, allowing him/her to focus on the broader design aspects of the target system.
5.
DESIGN SPACE EXPLORATION AND OPTIMIZATION
The modelling and simulation environment for distributed embedded systems that was described in the previous sections allowed the user to
110
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
specify and evaluate different system configurations. No design space exploration (DSE) and optimization tool was implemented as part of this particular case study to compute the optimal system configuration based on the performance requirements. In this section, we briefly touch upon the support for DSE in the context of the broader MILAN framework. As system complexity increases and performance requirements and power constraints become more stringent, the search for an optimal solution will necessitate evaluation of an exponential number of alternate system designs. This design space is defined along four dimensions: 1. Application alternates: Each task has multiple implementations, for the same hardware platform or different platforms. Each implementation has a different effect on the performance of the component and of the system as a whole. 2. Hardware alternates: Even for the same implementation, say a C code, there is a choice of the target processor. A processor such as the SA1100 might be a good choice to reduce the system's power consumption, but the execution time of that task might violate end-to-end throughput requirements. 3. Architecture knobs: Knobs refer to the hardware features that are provided by emerging architectures to support low-power system design both for single-node and distributed systems. A common example is the dynamic voltage-scaling knob, which allows an application to control the voltage and frequency of the processor at runtime. 4. Mapping and scheduling: The four dimension of the design space is defined by different mappings and schedules of task execution on the underlying hardware. Each mapping and schedule will naturally have different performance characteristics. The design and implementation alternates in the MILAN application modelling paradigm allow the user to model the design space of possible application implementations instead of just a point solution. A simple drag-and-drop mechanism to specify hardware resources also gives the designer the freedom to easily explore possible hardware configurations. For a given application implementation and hardware configuration, a mapping paradigm provides explicit control over the matching of tasks to resources. The space of possible implementations in any reasonably complex realworld system is extremely large. Even providing a high-level estimator is not useful if the designer has to manually select each possible design and evaluate its performance. MILAN therefore provides an automatic design
POWER-AWARE EMBEDDED SYSTEM DESIGN USING THE MILAN FRAMEWORK
111
space exploration mechanism [MP02] that traverses this design space and identifies the set of designs (if any) that meet the constraints6. Automatic design space exploration is possible in our general approach because (a) all aspects of the system (application, resources, mapping, and constraints) are defined through formal modelling paradigms, and (b) all model information is stored in the model database in a canonical form. The exact DSE technique depends on the designer. Separating the storage of model information from its access through a well-defined interface means that any third-party DSE tool can be plugged into the framework. The assumption is that the model parameters in the database are sufficient for that DSE tool. Even in cases where additional parameters about the system are required by a new DSE tool, the modelling paradigm can be extended through the graphical meta-modelling language.
6.
RELATED WORK
The general design approach followed in ARTEMIS most closely resembles ours. The significant difference is our use of a metamodelling language to define domain-specific modelling paradigms. This provides the designer with a formal mechanism to modify existing paradigms and/or define new paradigms, and makes our framework extensible. ARTEMIS targets Kahn Process Networks as the application modelling paradigm, and does not provide a well-defined mechanism using which, the designer could add new paradigms if desired. Other features unique to our framework are the use of the model database to enable plug-nplay tool integration, refining high-level models based on low-level simulations, etc. Other design environments CO, SE] exist that enable cosimulation of programmable embedded systems. Co-simulation requires an a priori decision by the designer about the division of task implementations into hardware and software. This might not be always possible while designing complex systems with a large number of heterogeneous components and possible task implementations. Our framework allows the user to model the design space as against a point solution, and an automatic design space exploration tool assists in pruning the design space.
6
Constraints are specified in the Object Constraint Language [WK99].
112
7.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
CONCLUDING REMARKS
The motivation behind the work described in this chapter is to demonstrate the usage of MILAN to create a unified, easy-to-use environment for the design of complex, distributed embedded systems. With the increase in system complexity and performance requirements, the most important capability of such a design environment is to facilitate rapid performance evaluation of a given system design, and efficient exploration of the design space. Plug-and-play simulator integration, multi-granularity simulation that exploits the simulation time vs. accuracy trade-off, and automatic refinement of analytical model parameters contributes towards this end. The case study we described is one of the efforts towards leveraging the core principles of MILAN to address design problems in different domains, and enhancing the capabilities of MILAN as a simulator integration framework. Another effort is exploring the possibilities of using MILAN for domain-specific modelling of system-wide energy consumption for reconfigurable architectures and using it for energyefficient datapath synthesis for selected scientific kernels on FPGAs. In continuation of the work towards creating a distributed embedded systems modelling and simulation environment using MILAN, we are currently working towards the implementation and integration of tools to assist in automatic synthesis of “optimal” task-to-node mappings for energy minimization in sensor networks.
Chapter 8 SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
Mitali Singh and Viktor K. Prasanna Department of Electrical Engineering - Systems University of Southern California, Los Angeles 3740 McClintock Ave, CA, US 90089
Abstract:
Energy is a critical performance metric in collaborative and distributed wireless networks. An integrated approach that considers system-level energy tradeoffs (such as communication versus computation energy) is essential for energy efficient application development in these networks. In this chapter, we present a system-level model for estimating the energy dissipation in these networks, and discuss energy reduction techniques for the Automatic Target Recognition (ATR) problem in a wireless environment. We show that by using our techniques and analysis up to 80% reduction can be achieved in the overall system energy. Finally, we discuss the impact of changing technology and energy costs on the effectiveness of these techniques.
Key words:
System-level tradeoffs, Computation, Communication, Sensors, Wireless.
1.
INTRODUCTION
Major breakthroughs in the deep sub-micron technology have led to the emergence of ubiquitous computing [WE93]. Small, inexpensive devices are embedded into everyday items as part of a networked world, providing new services to the information and communication technology consumer. These devices interface with the environment using actuators and sensors, have limited processing capability and memory storage, and communicate via wireless links. Moreover, the lifetime of these devices is determined by their
114
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
battery life, and thus, energy efficiency has emerged as an important design metric. In recent years, the hardware technology has advanced rapidly. Several low power embedded platforms are available in the market today, which provide software control for power reduction. New software techniques are being investigated that permit applications to exploit the hardware power controls for energy reduction. For example, the Dynamic Voltage Scaling (DVS) technique allows low energy computation by lowering the processor voltage and frequency. Similarly, radio modules are being designed that can be turned off when not in use. The transmission power and the bandwidth of the radio can be controlled for power reduction. Such hardware malleability permits reduction in energy dissipation by a large factor, but complicates the task of an application designer. In addition to the conventional software optimization, the application designer must also understand the interplay between a large set of architecture parameters. The real-time nature of these applications further complicates the design process. In this chapter, we focus upon system-level energy analysis and optimization for collaborative computation in small-sized wireless networks such as sensor networks. Typical applications for such networks involve data aggregation through sensors followed by collaborative computation and communication to process data, which is then transmitted to the base station. There are several system-level tradeoffs that need to be evaluated. For example, data compression before transmission can reduce the communication energy at the cost of computation overheads. The energy reduction achieved will depend on the relative energy costs for computation and communication. Moreover, the mapping of the tasks on the nodes determines the rate and amount of computation or communication required in the system. We analyze the system-level tradeoffs based on the energy costs of the state-of-the-art technology. We present an integrated, system-level model and energy trade-off analysis for application development on these networks. Our analysis is not based on hardware level (low level) power models. It exploits a coarse but fairly accurate high-level energy model, which has been designed for fast estimation of energy dissipation in the system and analysis of the various system-level energy tradeoffs. The aim of this model is to allow a designer to rapidly prune the design space to a smaller subset, which can then be subjected to low level simulations for higher accuracy [MI, The remaining of this chapter is organized as follows. Related research is discussed in Section 2. We define an integrated system-level energy model in Section 3, and discuss its integration into the MILAN framework in Section 4. The ARL [US] application of Automatic Target Recognition
SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
115
(ATR) in wireless environment, and several energy reduction techniques and tradeoffs are discussed in Section 5. This ATR problem is a challenge problem considered by the DARPA PACC community [DAa]. We present our results in Section 6, which show that energy reduction by 80% can be achieved for the ATR application using our techniques. Finally, we conclude with some discussion on the design of a system level tool for integrated energy management in Section 7.
2.
RELATED WORK
Several research groups have focused upon a system-level energy analysis and we discuss a few of them below: L. Benini et al. [BM99] define a system to be a collection of components whose combined operation provides a useful service and discuss techniques for system-level power optimizations. However, they focus on system level abstraction of architecture models for single and multiprocessor systems and do not consider distributed systems. Several efforts have focused upon analyzing the power dissipation involved in wireless communication. Feeney and Nilsson [FN01] present detailed measurements of the energy consumption of an IEEE 802.11 wireless network interface operating in ad hoc network mode. J. Ebert et al. analyze power consumption of a PC4800 PCMCIA wireless interface. These results have been used to obtain the communication parameters for our system level model. Energy efficient MAC and routing protocols (such as PAMAS [SR98a]) have been proposed to reduce communication energy. We primarily focus upon the application layer for developing energy reduction techniques. The task scheduling and resource allocation model for a system is also being studied with energy as an additional constraint. Kang et al. model the application as task chains and analyze energy versus latency tradeoffs. F. Gruian et al. [GK99] exploit constraint programming for energy efficient design for a multi-processor network. Many research groups have investigated the computation energy dissipated at a node, and many power simulators exist in the market today. Our analysis uses the SA1100 energy models and the JouleTrack [JT] simulator for computation energy analysis. Wang et al. [WC01] have analyzed the ATR problem in a wired network. They reduced the computation energy of the application by using Dynamic Voltage Scheduling techniques. On the contrary, we investigate the problem in a wireless environment and focus on reducing communication energy, which
116
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
has a larger impact on the overall energy dissipation in the current application.
3.
OUR SYSTEM-LEVEL ENERGY MODEL
In this section, we define a system-level model for energy analysis of collaborative computation in small-sized wireless networks. We define overall system energy for such a system to be the sum of the energy dissipated at all the participating nodes. Energy dissipated at a node consists of the computation energy, communication energy, storage energy and sensing energy as illustrated in Figure 8-1.
Each of these energy components depend on a large set of architecture knobs (processor voltage, radio RF, among others) that we discuss later in the section. Changing the setting of any of these knobs has system-wide effects. It is important for an application designer to understand the local (for the specific energy component) and global (system-wide) energy dissipation as a function of these knobs. This is a non-trivial task as the set of knobs is large. In order to facilitate analysis, it is required that system-level simulations are performed to obtain rapid energy and performance estimates. However, there are no system-level simulators in the market today that can be used to estimate energy for the entire application. Moreover, even the component
SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
117
specific simulators that exist in the market today perform low-level, time intensive simulations. To facilitate rapid, system-level energy estimation, our system-level energy model can be integrated into the MILAN framework [MI] (see Section 4). To start with, energy analysis is performed at a coarser level of granularity and then the pruned design space (containing solutions that meet the application constraints) is subjected to more detailed and higher accuracy simulations. Feedback from the lower level simulations is used to refine the high level analytical models. In this section, our goal is to identify some of the system-level energy cost parameters and define our system-level energy model that permits a rapid analysis of the system energy in an integrated manner. We briefly discuss the various energy components of the system and our choice for the model parameters. Computation Energy: This is the energy dissipated for performing computations on data. Several models have been utilized for energy analysis at the processor such as the RT model and the instruction level model [JT]. Table 8-1 illustrates power measurements for several instructions on SA1100 [JT]. It was observed that there was less than 36% variation in the current drawn by various instructions. Thus, at a coarser level of simulations, a uniform power cost can be associated for all the instructions without much loss in accuracy. Energy dissipated by an instruction is thus a product of the power cost and the time (or computation cycles) taken by an instruction. Thus, we define to be the energy (nJ) per computation cycle. It is important to note that is not a constant but depends on several parameters such as the processor voltage, frequency and precision. We define computation energy as follows:
Using the values from Table 8-1, at the given processor setting
the value of can be fixed to lie between 1.26-1.83. This value can be refined using hierarchical simulations (see Section 4). Note that there may be other processors where the power costs for various instructions may vary largely.
118
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
In such scenarios it may be possible to classify a set I of instruction types and replace the above equation by
, where represents the energy cost per cycle of instruction type i and Computation represent the total number of computation cycles taken by instructions of type i. The exact number of computation cycles can be estimated using computation complexity analysis. Consider an algorithm with complexity g (n) based on a high-level analysis. There are constants associated for transformations from algorithm to code and code to the execution sequence. takes into account the computation cycles spent as base overheads (such as program initialization, operating system overheads, among others) and characterizes the average number of computation cycles per algorithmic operation for the algorithm. Thus, the total number of computation cycles executed can be approximated as The parameters and can be estimated using low-level simulations (see Section 5.2). Storage Energy: This component represents the energy dissipated for storing data in the network. It is proportional to the number of memory banks that are required remain active to store data. From Table 8-2 it can be seen that power dissipation in the inactive state is very small as compared to the active state. We assume it to be negligible. For simplicity we consider memory to be organized as banks of size M, which can be activated or inactivated independently. To store data of size N bytes, banks are required to remain active. Note, we only consider data storage energy. Data access energy (memory read/writes) forms part of the computation energy as costs associated with memory read/write instructions. Let be the energy (nJ) dissipated to store one byte of data for unit time. Then storage energy for the node is defined as
Based on the values in Table 8-2 the value of
lies in the range 16.5-90.
SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
119
Communication Energy: Consider nodes communicating over a wireless channel. The total energy dissipated is proportional to the amount of data transmitted or received. We assume that the radio (and network card) can be placed in three power modes (transmission Tx, reception Rx, and sleep). Table 8-3 represents energy dissipation for state-of-the-art NICs. Note, the power dissipation in the sleep mode is small and we assume it to be negligible in our analysis. Since there is not a large difference between power dissipation in the Tx and Rx modes, we consider the power cost function to be the same for both. The power dissipation is also effected by the transmission range and operation bandwidth of the card. Since our application (see Section 5) requires high bandwidth, we consider the cards to be operating at the maximum bandwidth. Also, we consider only small sized networks (node distance within 4-8 feet), and thus require the lowest RF level setting for the cards. Under on these assumptions, the communication energy dissipated at a node for reception and transmission is given by: Based on the energy costs of the state-of-the-art technology (see Table 83), the parameter can be approximated as 1000.
Note that we make several implicit assumptions to simplify our communication model. Firstly, we consider only single-hop transmissions. We consider the bytes received or transmitted to be the effective number of bytes and not as per the application requirements. For example if n bytes need to be transmitted and the channel throughput is r. Then the effective number of bytes is n / r. Here, r is computed using analytical models for communication parameters such as the communication protocols, channel noise, environmental error rate, collisions, interference, and path fading, among others. Sensing Energy: In order to interface with the physical world, the nodes are equipped with sensing elements. The choice of the sensing elements and thus the sensing energy depends on the application. Magnetic or temperature sensors may consume negligible energy. For example the Passive Solid-State Sensor (PSSM) [LI00] requires no input power. On the other hand significant energy may be dissipated in acoustic or seismic sensors depending on their design. We define sensing energy as follows:
120
, where
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
is the energy cost for sensing one input sample.
Energy dissipation at a node: Thus, total energy dissipation at a node j is given by:
Total energy dissipation in the system with m sensors:
From the system level model parameters obtained above obtained above, it is evident that the communication costs overshadow the computation costs by a large factor. The ratio is over 500. Thus we will focus on reduction of overall energy by analyzing system level tradeoffs that reduce communication energy at the cost of increased computation. Due to unavailability of energy profiles of the sensing element, we do not incorporate sensing energy in our analysis.
4.
HIERARCHICAL SIMULATION USING MILAN [MI]
Model-based Integrated SimuLAtioN (MILAN) is a model based extensible framework that facilitates rapid, multi-granular energy and performance evaluation of a large class of systems, by seamless integration of different widely used simulators and design tools into a unified environment. The design flow of the MILAN framework is shown in Figure 8-2. Design Space Exploration: In the first step the user provides the application graph, the resource model, and the mapping. MILAN exploits hierarchical simulation for rapid and accurate design space exploration. In the initial phase a high level simulator (based on high level analytical models) is used to rapidly prune the solution space. The small set of candidate solutions
SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
121
(those that meet the application constraints) is then subjected to low level component specific simulations to obtain results with higher accuracy. Refinement of Model parameters: MILAN utilizes feedback from the lowlevel simulators to update the cost functions of the high level analytical models. In the previous section, we obtained a coarse, high level model for system-level energy estimation. We defined ranges for the component specific energy costs. These would serve as initial energy costs in the “coarse” system-level model in the second stage of the design process. In the third stage, the feedback from low level simulations would be used to refine these parameters so that the resultant energy estimates (after a few iterations) are highly accurate.
122
5.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
AN ILLUSTRATIVE EXAMPLE –AUTOMATIC TARGET RECOGNITION (ATR)
There are several system level energy tradeoffs that must be considered in designing applications to be mapped on distributed networks. We illustrate our energy reduction techniques and computation versus communication tradeoffs using the ARL [US] application for Automatic Target Recognition (ATR) in a wireless environment. This problem is a challenge problem being considered by the DARPA PACC community [DAa]. A brief description of the problem is given in the following subsection.
5.1
The ATR Application
This problem involves detection and tracking of vehicles in a battlefield, which has sensors distributed over it. The sensors are organized as small clusters of 7 nodes each, with one node in each cluster acting as a cluster head. The diameter of the cluster is small (4-8 ft). The sensors collect seismic and acoustic data to detect the presence of a vehicle in the field. The data is processed at clusters in proximity of the target and the Line of Bearing (LOB) of the vehicle (target) is transmitted to the base station where tracking is performed.
SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
123
Figure 8-3 depicts the topology of the 7-sensor cluster with the cluster head placed in the center. Each sensor collects 1K samples of data and transmits it to the clusterhead. The kernels involved here are a Fast Fourier Transform (FFT), followed by delay-and-sum beamforming (BF) and an LOB estimation algorithm. The LOB estimate is then transmitted to the base station where the tracking algorithm is deployed. New data samples are collected every second. The state-of-the-art solution [WC01] to this problem considers only Dynamic Voltage Scaling at the node-level for energy reduction. As opposed to transmitting the sampled data to the clusterhead, the surrounding sensors now perform an FFT on their 1K data samples and transmit the result to the clusterhead. The clusterhead is now required to compute an FFT on 1K samples only instead of 7K as in the former case. Thus it can operate at a lower voltage and frequency without causing excessive delay. No prior analysis has been performed for the communication energy dissipated in this application. It is critical to evaluate communication energy as it dominates computation energy for this problem. In the following section we evaluate the communication and computation tradeoffs for this problem and propose several energy reduction techniques.
5.2
Energy Analysis for the ATR
Base Line Scenario (BL): We consider our base case for energy analysis as the following: Six sensors compute FFT over 1024 data points and transmit the results using the 802.11 protocol for communication, to the cluster head. The cluster head itself also performs an FFT on its own sampled data and then utilizes the received values for the beamforming algorithm. For our communication/computation trade-off analysis, we consider energy costs of performing FFT, data storage, and data transmission/reception. All energy costs are computed in nJ. Computation Energy: The Computation energy for Thus, for computing We used coarse parameters initially and then tuned those using low-level simulations. Time and energy estimates for 16-bit, fixed-point, real-valued FFT were obtained using JouleTrack simulations and the parameters and were estimated for various problem sizes as illustrated in Table 8-5. These values were obtained using energy and time (to estimate number of computation cycles) measurements from JouleTrack for various problem sizes and then tuning the parameters to match these measurements. For
124
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
parameter values can be estimated as
the computation energy
Storage Energy: Consider 1 memory bank of size 4 MB to be sufficiently large to store data and program. Note the total data stored as a node is only 2n bytes and 14n at the cluster head. For this is much smaller to 4 MB. The memory remains active for the entire time (1 sec to process one set of data). Assuming storage energy is given by 360 nJ. This is negligible compared with the computation energy. Communication Energy: We assume 16-bit precision. Each node transmits n samples = 2n data bytes to the cluster head. In all there are 6 transmissions and receptions of data. The total communication energy is given by For 802.11 we assume r = 31% (see Section 5.3). Thus total energy dissipation for communication between nodes is given by For energy dissipation is given by 77000n nJ. From our analysis, it is evident that the communication energy costs are much higher than computation energy costs. Thus, we focus upon reduction of communication energy at the expense of increased computation.
5.3
System-level Energy Tradeoffs
In this section we analyze several communication versus computation energy tradeoffs and apply them to the ATR application for obtaining overall energy reduction in the system. Data Compression (DC): The communication energy can be decreased by reducing the amount of data that is transmitted to the clusterhead. For example data can be compressed or redundant data can be filtered out. We considered the LZW algorithm for our analysis. We generated random samples of data and compressed them using LZW. Data files with data samples ranging from 200 to 1800 were analyzed. On the average data
SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
125
compression reduced the resultant data to half its original number of bytes. The computation overheads were proportional to the data size being compressed. Figure 8-4 shows the overall energy reduction achieved as a function of the number of data samples to be transmitted. (Note that due to random generation of data the bytes transmitted are not always linearly proportional to the number of samples. Thus we see a glitch in the curve). We observed that for 1024 bytes of data with compression by a factor of two, we could reduce overall energy from 18.878 mJ to 14 mJ. However, a more effective technique was application specific data filtering. It was observed that the transmitted data represented frequency components of the acoustic data from 0-1024 Hz. Only the frequency range between 20-250 Hz is useful and needs to be transmitted. Remaining frequencies are not useful and can be filtered out. After computing the FFT, only the values corresponding to the useful frequency range were transmitted. Thus, the data to be transmitted was reduced to one fourth with negligible computation overheads.
Compression was applied after filtering the data. The resultant data was compressed by a factor of 0.3 with computation overheads of only 0.851 mJ. The data to be transmitted was reduced by one-sixth and overall energy dissipation was reduced to 3.934 mJ. We applied a standard compression algorithm to reduce communication energy. Other coding and compression techniques must be evaluated for their computation overheads and the amount of compression achieved. C.
126
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Tang et al. are investigating application specific coding that exploits spatial and temporal correlation between successive data frames. Forward Error Correction (FEC): This technique involves large computation overheads for coding and decoding data. However, it permits transmission of data at a much lower signal power. For our analysis, we used convolutional coding and Viterbi decoding [TC]. We analyzed the energy tradeoffs for various values of parameter K, which represents the constraint length for the algorithm. The computational complexity of the decoding algorithm grows exponentially with K. The energy per symbol to noise density ratio for various bit error rates reduces with increasing K for an environment with a given BER as illustrated in Figure 8-5.
We observed maximum overall energy reduction by choosing K = 3. The results are illustrated in Figure 8-6. The first bar represents the overall system energy for communicating 2048 bytes of data without using FEC. FEC with K = 3 reduces energy per symbol to noise density ratio by 3.5 dB (see Figure 8-5). Thus transmission power can be decreased by a factor of 3 resulting in lower communication energy as shown by the second bar in Figure 8-6. The third bar illustrates the energy overheads for computing FEC with K = 3. Lastly, the impact of using this technique on the overall energy (communication +computation overheads) is shown. Energy reduction by
SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
127
50% can be achieved. Several other advanced codes [AH] promise energy per bit to noise ratio reduction up to 10 dB implying that the transmission power can be reduced by 10. However, it is important to examine them for the computation overheads involved. Scheduling Transmissions (ST): The 6 surrounding nodes transmit data to the cluster head. Since, they begin transmitting at the same time (after computing FFT) in each period, a large number of collisions take place. Simulations using the 802.11 back off algorithm showed that on average over a million iterations, 19 time slots were required to transmit the data. Note we assume that a sensor sends all its data in a single time slot. The number of timeslots required can be reduced to 6 if TDMA scheduling is used for data transmission. The cluster head initiates the round of communication by sending a beacon signal. After hearing the beacon signal, each node knows exactly when to turn on the radio to transmit data to the cluster head. When one node transmits, the others are switched off. This reduces communication energy by 69% over the baseline scenario. The overheads for this scheme are in terms of time synchronization between nodes. However, in a 7-node cluster these are negligible. In larger settings these could become significantly high.
128
6.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
INTERPRETIVE SIMULATION RESULTS
In the previous section, we discussed several energy tradeoffs and their effect on the overall energy dissipation in the system. We used interpretive simulation results to obtain energy estimates. The computation costs were obtained using the JouleTrack simulator. The communication costs were estimated as a function of the data size received or transmitted, and the energy cost per byte for transmission and reception. In the first scenario the parameters were taken as (1000, 2) as illustrated in Table 8-4. Thus the communication to computation ratio was assumed to be 500. The total computation costs for performing FFT, LOB and Beam forming were estimated as 3.28 mJ through simulations using Joule Track. We assumed 2048 bytes to be sent from each periphery sensor to the clusterhead in the baseline (BL) case. The channel throughput using 802.11 protocols was assumed to be 31%. Based on these assumptions, the communication energy was estimated as 94.12 mJ resulting in an overall energy dissipation of 97.4 mJ.
Data Compression (DC) reduced the number of transmission bytes to onefifth reducing communication energy to 15.68 mJ at an increased computation overhead of 9 mJ. Thus, the overall energy was reduced to 15.68 +10.2 + 3.28 = 29.16 mJ. Forward error Correction (FEC) permitted transmission power reduction by a factor of 3. The computation overheads
SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
129
involved were (5.337 × 6) mJ using Convolutional coding and Viterbi decoding with constraint length of 3. Scheduling Transmissions (ST) between the nodes, collisions were avoided and channel throughput was improved by 69%. Since the number of participating nodes is small and they are placed close to each other, synchronization overheads were considered to be negligible. Lastly, the impact of applying all these simultaneously (ALL) was evaluated. The transmission power was reduced to one third, the data transmitted was reduced to one-fifth and no packet loss due to collisions was assumed. Note that the computation heads for the ALL case are smaller than the sum of individual DC, FEC and ST cases. Data compression is used to reduce the data set to be transmitted. Thus, FEC is applied on a smaller data set resulting in smaller computation overheads. The overall system energy was reduced to 15.42 mJ. Thus an overall energy reduction by 80% was achieved as illustrated in Figure 8-7. Low power architectures are advancing rapidly. The above results are relevant in the current scenario. However, some of these techniques will not be beneficial in future when the energy metrics for the implementation platform change. We believe the ratio 500 that we used for our analysis will decrease in future with advancements in the technology. Figure 8-8 illustrates an energy prediction using a "futuristic scenario", where the ratio is reduced to 300. This is achieved by keeping fixed and reducing
130
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
The overall energy is reduced for all the scenarios including the baseline scenario. However, most of the techniques discussed are relatively less effective because computation overheads become significant. Techniques such as scheduled transmissions are not affected by this ratio since they had negligible computation overheads. In the new scenario, the communication energy for the application is reduced drastically, but the computation overheads are high. Thus, only overall energy reduction by 67% is achieved.
7.
DISCUSSION
This chapter is based on a “coarse” performance model that is utilized to obtain rapid estimates for overall energy dissipation in a small-sized wireless networks consisting of nodes performing collaborative computation. The model parameters for estimating energy costs for various operations were estimated. Based on the state-of-the-art, we assumed a ratio of 500 for the energy consumed to transmit a byte of data to that required for performing one cycle of computation. Using this model, potential energy reduction for the ATR application was discussed. It was demonstrated that there is a nontrivial interplay between the various parameters in reducing overall system energy. For example, sophisticated compression techniques reduced the communication energy but at the expense of the node computation energy. Similarly, the storage overheads must be considered. Thus, this chapter presents a vertically integrated approach that considers various knobs and energy optimization techniques in an integrated manner. This chapter highlights the benefits of using sophisticated coding and compression techniques for energy reduction. We will further explore algorithms that reduce data communication and permit more efficient error correction and evaluate them for the computation overheads. These would permit low power transmissions and improved performance even under extreme environmental conditions. The impact of communication/ computation energy efficiency ratio in system level energy optimization was also demonstrated. As this ratio reduces, performing communication in close neighbours as in the ATR application becomes less expensive. As a result of this, several node-level optimizations become relevant and their impact must be evaluated from the overall energy reduction perspective. We also discussed integration of our model into the MILAN framework in Section 4. This permits construction of a system-level tool that can be
SYSTEM-LEVEL ENERGY TRADEOFFS FOR COLLABORATIVE COMPUTATION IN WIRELESS NETWORKS
131
utilized for obtaining rapid and yet accurate system energy estimations for various mappings and parameter settings. The high level model permits rapid design space exploration, while the hierarchical simulations improve accuracy of results by through refinement of model parameters using lowlevel simulations.
ACKNOWLEDGMENTS We would like to thank the participants of the PACMAN [PA] and MILAN [MI] projects for their valuable help and suggestions.
This page intentionally left blank
Chapter 9 OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
Ramesh Karri and Piyush Mishra Department of Electrical and Computer Engineering Polytechnic University, Brooklyn 6 Metrotech Center, NY, US 11201
Abstract:
Deployment of security protocols in battery-powered mobile devices has elevated energy consumption to an important design metric of network design. In this chapter we identified the various sources of energy consumption during the setup, operation and tear down of a secure wireless session. We used Internet Security Protocol (IPSec) for our analysis and developed techniques based on information compression, session negotiation protocol optimization and choice of cryptographic primitives to reduce the energy consumed by a secure wireless session. A mobile test bed was developed to validate our energy management schemes which showed that the proposed schemes were able to reduce the session establishment energy by more than 6.5× and the secure data communication energy by more than 25× during data transmission and by more than 3.8× during data reception.
Key words:
Mobile, Security protocols, Wireless, Energy-efficiency, IPSec, Secure session.
1.
INTRODUCTION
Rapidly evolving personalized network applications, such as online health, commerce and education services, have fuelled the need for securing data communication networks [CL00]. Security protocols used to provide the required security mechanisms employ session negotiation protocols for establishing and managing secure sessions and secure data exchange protocols for secure data communications. In addition to data confidentiality,
134
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
authenticity and integrity security protocols also provides features such as system resource protection and audit-trails. Traditionally, researchers have focused on security, complexity, and throughput metrics while designing security protocols for wired networks. Due to the increasing size of the mobile computing and communication device market deployment of computation and communication intensive security protocols in battery-powered mobile devices has elevated energy consumption to another important design metric [SE00]. Further, lack of well-defined boundaries in wireless networks and other physical constraints imply stronger security requirements, which in turn increase the energy consumed by security protocols operating on these mobile devices. There are two main sources of energy consumption during a secure wireless session: (i) cryptographic computations used to establish the secure session and to support encryption and authentication during secure data transaction and (ii) message exchanges during secure session establishment and data transfers during secure data transactions. We considered a Symbol PPT2800™ Pocket PC device running Windows CE™ 3.0 operating system and equipped with an 11 Mbps Spectrum24™ wireless LAN adapter card as the mobile test bed1 to measure the energy consumed by a secure wireless session while transmitting 64 KB data over an 802.11b WLAN channel. Secure data transaction used 3DES encryption [DE], SHA-256 message authentication code [SH] and consumed 952 milli Joules.
Figure 9-1 shows that idle system consumes 44% of the system energy followed by data transmission and cryptographic computations which consume 35% and 21% of the system energy respectively. Idle system energy corresponds to the energy consumed by the mobile test bed between 1
Detailed description of mobile test bed and experimentation methodology is outlined in section 3.1
OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
135
the transmissions of packets and is determined by the sustained throughput of the system, which in turn depends upon the network conditions, application requirements, etc. In this chapter we will accurately measure the energy consumed by various components of a security protocol used for establishing and managing a secure wireless session, present techniques to minimize their energy consumption and investigate the associated energy vs. security tradeoffs. We selected Internet Security Protocol (IPSec) for our study since network layer security protocols are comprehensive, mobile and transparent to users.
1.1
Related Research
Techniques developed to reduce the energy consumed by wireless data communication include adaptive network interface control, data compression, optimized network protocols and adaptive error control techniques. Woesner et. al. studied the power saving features of wireless LAN standards and presented simulation studies for energy-efficient ad-hoc configurations Ebert et. al. presented a packet length dependent power control mechanism for optimal RF power level while Rulnick and Bambos considered autonomous transmitters to determine optimal level of transmit power given a set of quality-of-service constraints and information on the nature of channel and the level of interference at the receiver [RB96]. Kravets and Krishnan presented a transport level protocol to selectively suspend communication and shut down the communication device and studied the trade-off between power consumption and data delay [KK99]. Kravets et. al. presented a pay-off adaptation based energy-efficient scheme for distributed applications Rohl et. al. studied the influence of typical parameters on the power saving mechanisms in IEEE 802.11 Singh and Raghavendra developed a power-efficient multi-access protocol for ad-hoc radio networks and showed that the idea can be easily extended to other access protocols [SR98a, SR98b]. Zorzi and Rao developed probing schemes for energy-efficient error control protocols and a formal approach to track complex models for power sources including dynamic charge recovery in batteries [ZR97a, ZR97b]. Lettieri et. al. presented another energy-efficient error control protocol with hybrid combination of an appropriate forward error correction (FEC) code and automatic repeat request (ARQ) protocol that adapts over time for each data stream
136
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Our study differs from these works in two aspects: (1) it focuses on the energy consumption characteristics of computation-intensive security protocols which, till now, have received little attention and (2) unlike most of the other simulation based studies, we will use real-life mobile test bed to validate the techniques presented for reducing the energy consumed by secure wireless sessions.
1.2
Outline
In section 2 we describe negotiation, management and operation of secure wireless sessions within the IPSec framework. In section 3 we describe the experimental setup and methodology and use the results of energy measurement experiments to estimate the energy consumed during IPSec secure sessions. In section 4 we present the techniques for optimizing the energy consumed by secure wireless sessions and validate these techniques using IPSec framework. Section 5 concludes this chapter.
2.
IPSEC SECURITY PROTOCOL
Security protocols first negotiate security associations (SAs) between the communicating parties using a session negotiation protocol. Secure session negotiation entails (1) mutual authentication of the communicating parties, (2) parameter negotiation to agree upon the SAs primitives (for example, a list of data encryption and authentication algorithms and their parameters) and the key exchange and management protocol and its parameters, (3) key exchange and management to generate a set of secret keys shared exclusively among the communicating parties, and (4) SAs establishment to establish a secure session using the negotiated SAs. Secure session negotiation protocols should ensure perfect forward secrecy and be scalable. After successfully establishing a secure session security protocols carry out secure data communication using the agreed upon SAs. IPSec session negotiation uses Internet Key Exchange (IKE) protocol [HC98] to establish and manage SAs. Design of IPSec session negotiation protocol is influenced by Station-to-Station (STS) [DO92+], SKEME [KR96], and OAKLEY [OR98] protocols. It uses Diffie-Hellman key exchange and management [DH76] to generate the shared secret keys and one of four authentication mechanisms - pre-shared secret, public key signature, public key encryption and revised public key encryption- for mutual authentication (see [HC98] or [CH01] for detailed description of each mechanism).
OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
137
IPSec session negotiation protocol first authenticates the communicating parties and runs a public-key based key exchange and management protocol (Diffie-Hellman) to generate the first shared SA using either main or aggressive mode. Aggressive mode collapses the 6 messages of the main mode into 3 messages at the expense of constrained negotiation space and unsecured identities. Then, under the protection of this first SA, it runs a private-key based key exchange and management protocol frequently to establish and manage multiple IPSec SAs. In general, the first SA is negotiated between the gateways and the proxies, while IPSec SAs are negotiated on behalf of the end clients. In a mobile environment the mobile client may act as its own proxy.
Figure 9-2 shows the protocol messages exchanged during first SA negotiation in the main mode and Figure 9-3 shows the protocol messages exchanged during IPSec SA negotiation. HDR contains session-specific information (such as session ID etc), SA contains a list of cryptographic algorithms, nonces are large random numbers, and IDs are the unique identities of the communicating parties. Parameters in ‘[]’ are optional. After successfully establishing the secure session IPSec (either at the client or at the server) accepts plain text messages, computes the MAC, encrypts the data and transmits it. At the other end, received data is decrypted and verified. Security of a session is enhanced by periodically refreshing the SAs.
138
3.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
ENERGY CONSUMPTION OF A SECURE WIRELESS SESSION
We computed the total energy consumed during a secure session negotiation as the energy consumed for authenticating the communicating parties (sign and verify certificates) + energy consumed for negotiating the parameters (exchange SA primitives) + energy consumed for key exchange and management (generate shared secrets) + energy consumed for SA establishment (generate secret keys for encryption + generate secret keys for message authentication (MAC) and the total energy consumed for secure data exchange as the energy consumed to authenticate data (sign and verify) + energy consumed to secure data (encrypt and decrypt) + energy consumed to exchange data (transmit and receive) + energy consumed to manage SAs.
3.1
Test Bed for Energy Measurements
The mobile test bed shown in Figure 9-4 consists of a PPT2800™ Pocket PC device [SP] equipped with an 11 Mbps Spectrum24™ wireless LAN Adapter card (IEEE 802.11b) [SSb], both from Symbol Technologies Inc. Pocket PC is running WindowsCE™ 3.0 operating system on a 32-bit, 206 MHz StrongArm™ SA-1110 processor with 16 MB flash ROM, 16 MB RAM, 16 KB instruction cache and 32-way set associative 8 KB data write back data cache. The WLAN card is operating in polling mode P12. We measure the current drawn by an application executing on the mobile test bed using a Tektronix TCP202 current probe (DC to 50 MHz, Min 2
See section 3.2.1
OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
139
sensitivity: 10 mA/div, DC accuracy: ±1% with probe calibrator) and a Tektronix TDS 3054 oscilloscope (4 channel, 500 MHz, 5 GS/s) [TI]. Voltage was held constant at 4 V, the nominal operating voltage of the mobile test bed. In order to ensure consistency and accuracy of our results, we averaged each of our results over several thousand iterations for each application with data residing in the main memory and data and instruction caches enabled.
3.2
Sources of Energy Consumption
This section presents the results of our energy measurement experiments for various sources of energy consumption. 3.2.1
Wireless Transceiver Subsystem
The 11 Mbps Spectrum24® LA-4121 wireless LAN card operating at 5 V supports a continuous access mode (CAM) and five polling modes, P1 to P5 [SSb]. Current consumed by the WLAN card during active transmission and reception is approximately uniform across all polling modes. Table 9-1 shows that the current, and hence power, consumed by LA-4121 wireless LAN card depends upon its mode of operation. Transmission energy is the product of power consumed in transmit-mode and the time to transmit data.
140
3.2.2
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION Message Authentication Code
We used SHA-256, a variation of a 256-bit symmetric block encryption algorithm, as the message authentication code (MAC) [SH], SHA-256 encrypts the intermediate hash values using the message blocks as the keys. Figure 9-5 shows the energy consumed by optimized ‘C’ implementation of SHA-256 for different data sizes.
3.2.3
Data Encryption
Data Encryption Standard (DES) and triple-DES (3DES) are private key encryption algorithms that have been widely used for more than 20 years now to ensure data privacy [DE]. Recently National Institute of Standards and Technologies (NIST) selected Rijndael as the Advanced Encryption Standard (AES) to replace DES and 3DES in systems with higher security and performance requirements [AE]. AES supports multiple user key lengths (128, 192, or 256 bits) and multiple data block sizes (128, 192 or 256 bits) [DR]. Security level and the energy consumption of a private key encryption algorithm increase with the number of encryption rounds and the length of the user key. Table 9-2 summarizes the energy consumed by round-key generation and encryption of optimized ‘C’ implementations of AES. Energy consumed by AES key generation increases with the key size at a rate greater than the energy consumed by its encryption due to an increase in the complexity of key generation and an increase in the number of round keys to be generated.
OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
3.3
Energy Consumed by a Secure Wireless Session
3.3.1
Negotiating a Security Association
141
Table 9-3 summarizes the energy consumed during IPSec secure session parameter negotiation and mutual authentication as a function of size of messages exchanged and cryptographic computations performed. We assume that client is the initiator and server is the responder. Energy values in bold correspond to the client. Client SA proposal includes DES [DE], 3DES [DE] and AES [AE] encryption algorithms for Encapsulating Security Payload (ESP) protocol [KE02] and SHA-256 [SH] message authentication code for Authentication Header (AH) protocol [KE98] and server selects 3DES and SHA-256 for the SA. Mutual authentication is pre-shared secret based and the first SA negotiation is carried out in the main mode.
142
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Table 9-4 shows the energy consumed by the IPSec key exchange to generate the shared secret and derive the secret keys for establishing IPSec SAs.
Table 9-5 shows the energy consumed by IPSec SA establishment. More than 90% of the energy consumed during SA establishment is due to the exchange of large size certificates.
Table 9-6 summarizes the total energy consumed by the IPSec session negotiation protocol at the client and at the server in main and aggressive modes corresponding to the various authentication mechanisms. From Table 9-6 we can see that although aggressive mode exchanges only three messages it consumes approximately the same amount of energy as the main
OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
143
mode that exchanges six messages. This is because both modes exchange approximately the same amount of information and perform identical cryptographic computations.
As far as authentication schemes are concerned, IPSec clients using public-key encryption and pre-shared secret based authentication consume equivalent energy while the energy consumed by client supporting revised public key encryption based authentication is comparable to the one supporting public-key signature based authentication. Of the 1521 milli Joules consumed by a client supporting revised public-key encryption based authentication 89% is consumed by the message exchanges and 11% is consumed by public key cryptographic computations. 3.3.2
Secure Data Transaction
Following successful secure session establishment, secure data exchange protocol accepts plain text messages, computes the MAC, encrypts the data and transmits it. At the other end, received data is decrypted and verified. Security of a session is enhanced by periodically refreshing the SA and the encryption and the MAC keys. Table 9-7 summarizes the energy consumed during secure wireless data transmission assuming following security association: 3DES encryption, SHA-256 MAC, key refresh rate that entails re-computing encryption and MAC keys every 128 KB of data and SA refresh every 2 MB of data. It does not include the energy consumed by SA refreshes which is essentially the same as the energy consumed during secure session negotiation. Energy consumed by idle system is inversely proportional to the sustained throughput of the system, where sustained throughput of a system is determined by a variety of factors including the network condition, efficiency of the wireless protocols and the throughput requirements of the application. Energy consumed by data transmission and reception increases linearly with the input data size while the energy
144
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
consumed by cryptographic computations increases linearly with both data size and security level.
For example, while transferring an 8 KB of data does not entail any key refresh overhead, transferring 2560 KB of data entails 19 key refreshes, consuming 245 milli Joules each at the client and at the server. Refreshing the secret keys entails generating new encryption and MAC keys and generating fresh round keys using the new encryption key. Similarly, large encryption keys and higher number of encryption rounds also improves the level of security at the cost of extra energy consumption and performance degradation. Cryptographic computations (key refresh, data encryption and MAC authentication) consume 7.7% of the total energy for transferring 8 KB data, and this increases to 8.4% of the total energy for transferring 2560 KB data.
4.
DESIGNING ENERGY-EFFICIENT SECURITY PROTOCOLS
We will now describe techniques to optimize the energy consumed by security protocols by systematically considering the various sources of energy consumption - authentication, parameter negotiation, key exchange and management and secure data exchange - and study the impact of these techniques on the energy consumption characteristics of the protocols providing these services.
4.1
Reducing the Energy Consumed by Data Exchanges
Data exchanges account for a considerable fraction of the energy consumed by session negotiation (more than 90%) and secure data communication (more than 40%). Therefore, reducing the amount of data exchanged during a secure wireless session can significantly reduce its
OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
145
energy consumption. This can be achieved by reducing either the size of the data or the number of data exchanges or some combination thereof. 4.1.1
Data Compression
Compressing data before encryption and transmission and decompressing it after reception and decryption reduces the energy consumed during secure wireless data communication if the energy savings due to the reduced data size are more than the extra energy consumed by compression and decompression. Similarly, compressing session negotiation messages before transmission and decompressing them after reception may reduce the energy consumed by secure session negotiations. To study the impact of compression we used optimized ‘C’ implementation of DEFLATE loss-less data compression algorithm [DC]. Compression level, history window size, and memory-level are the three important parameters that affect the energy consumed by DEFLATE compression. Table 9-8 summarizes the energy consumed by DEFLATE while compressing 1KB, 8 KB and 64 KB size benchmarks from Calgary corpus [BE90].
It can be seen that matching the compression block size to the data cache size (8 KB for our mobile test bed) saves significant energy. Further, increasing either the compression level or the memory level results in a proportional increase in the energy consumed without a corresponding increase in the compression ratio, while increasing the size of the history window yields a proportional increase in the compression ratio without a corresponding increase in the energy consumed. We found that medium compression level (level 5), medium memory level (level 5), and maximum history window size (32 KB) combination achieves a compression ratio close to the best while consuming significantly less energy. Decompression 3
CL: Compression level, ML: Memory level
146
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
energy is very small compared to the energy for compression (~10× less for DEFLATE) since decompression involves fewer and simpler computations. Hence, energy consumed by the client can be reduced significantly if the server/gateway compresses all the data following session initiation messages.
Table 9-9 shows a 1.13× reduction in the energy consumed by IPSec session negotiation protocol by compressing the messages that exchange authentication certificates and shared secret.
Energy consumed during transmission and reception of uncompressed and compressed, 3DES encrypted 2560 KB data is summarized in Table 910. Energy consumed by data transmission is 2× the energy consumed by 3DES encryption which in turn is 0.65× the energy consumed by DEFLATE data compression for 8 KB compression block size. Besides reducing the size of the data to be encrypted and transmitted, compression also reduces the energy consumed by key refreshes. For example, if encryption and MAC keys are refreshed after exchanging every 128 KB of data, an uncompressed
OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
147
2560 KB secure data communication requires 19 key refreshes and consumes 245 milli Joules, while the compressed 736 KB data (=2560 KB÷Compression ratio of 3.48) requires only 5 key refreshes and consumes 64.5 milli Joules. Therefore, data compression reduces (a) transmission, reception, encryption and decryption energy during secure data communication (b) number of key refreshes required and the corresponding energy, and (c) energy consumed by the idle system. It allows either a higher level of security (large-size certificates and keys) within an energy budget or minimizes the energy consumed while maintaining a minimum level of security. 4.1.2
Refreshing the Security Association
Wireless networks are inherently unreliable and discontinuous resulting in frequent secure session negotiations. Network services may become unavailable due to bad radio coverage, shortage of resources or network roaming. Therefore, session resumption and transaction recovery, together with fast secret key generation are key to energy efficiency of mobile clients. As shown in the last section, compressing the messages exchanged during secure session negotiation reduces the energy consumed by the mobile client by more than 10%. Client energy can also be reduced by modifying the session negotiation protocols such that the server looks up the client’s certificate from its own source (session negotiation variant 1). Embedding the client’s shared secret in its certificate can further reduce this energy. When establishing a new session, a client-server pair can exchange new client and server nonces and combine these with previously negotiated security association (session negotiation variant 2). Finally, implanting the shared secret in the server and mobile client eliminates the energy consumed by shared secret exchange messages (session negotiation variant 3). Table 911 shows the energy consumed by these variants of IPSec secure session negotiation protocol.
148
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
We propose an adaptive session negotiation protocol that uses session negotiation variant 1 to establish a new secure session and session negotiation variant 2 to refresh the security association by exchanging new client and server random numbers if the session lasts beyond a certain number of messages determined by the security requirements of the session or if the session is disrupted abruptly due to bad channel conditions or temporary network outage.
4.2
Reducing the Energy Consumed by Cryptographic Computations
Cryptographic computations constitute as much as 10% of the energy consumed during session negotiation and 60% of the energy consumed during secure data communication. Energy consumed by cryptographic computations can be reduced by (1) selecting energy-efficient cryptographic mechanisms, (2) trading-off security for energy, and (3) energy-efficient hardware acceleration. This chapter does not discuss the last technique which has already been covered extensively in literature [GC01, KM02]. 4.2.1
Choice of Cryptographic Mechanism
Choice of authentication, key exchange and management, and data encryption mechanisms can reduce the energy consumed by security protocols at the mobile clients. IPSec session negotiation protocol uses Diffie-Hellman key exchange and management for exchanging shared secrets and RSA public-key scheme for mutual authentication. In wired networks, these two operations are isolated to ensure perfect forward secrecy; otherwise anybody who somehow gains access to the RSA private keys can obtain access to the future as well as the past communications. On the other hand, in a mobile wireless environment such risks are minimal due to the relatively shorter life-span of secure wireless sessions. For example, IPSec session negotiation protocol derives all secret keys using the ephemeral nonces which expire as soon as the wireless session terminates. Therefore, energy consumed by the IPSec session negotiation can be reduced by using RSA protocol for both exchanging the shared secrets and for mutual authentication. This observation is confirmed by results in Table 9-12 where replacing Diffie-Hellman key exchange and management protocol with the RSA key exchange and management protocol reduces the session negotiation energy consumption by more than 1.5×.
OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
149
Similarly, Table 9-13 shows that replacing 64-bit 3DES encryption with 128-bit key AES encryption reduces the energy consumed by secure data communication by approximately 1.2×. This is due to the elegant design of AES to better exploit features like pipelining and parallel processing and due to the larger data block size.
4.2.2
Optimizing the Security Association
There exists an inherent trade-off between the security level and the energy consumption of a secure wireless session. Energy consumption increases with the increasing level of security. For example, energy consumed by Diffie-Hellman key management and exchange protocol depends upon the algebraic group used. Size of parameters exchanged between the communicating parties can have substantial impact on the security and energy consumption characteristics of a secure session negotiation protocol.
A client also has a choice of either reducing the encryption key size or the number of encryption rounds while increasing the key refresh rate or vice versa to reduce the system energy while maintaining a desired level of security. Table 9-14 shows the performance characteristics of AES
150
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
encryption as a function of the user key size. The trade-off depends upon the relative energy consumption of the key refreshes and the data encryption mechanism. For example, for a secure session transmitting 2.56 MB data using 3DES encryption, reducing the number of rounds of encryption by 2×, and correspondingly increasing the key refresh rate by 2× reduces the session energy by l.05×. On the other hand, energy consumed by a secure wireless session using 128-bit key AES encryption is reduced by l.05× by increasing the encryption key size to 256 bits and reducing the key refresh rate by 2×. 4.2.3
Reducing the Energy Consumed by Authentication Protocol
Mutual authentication of the communicating parties during secure session negotiation consumes significant energy. Table 9-6 shows that public key signature based authentication consumes maximum energy since it entails computation of public-key signatures and exchange of large certificates. Public key encryption based authentication is comparatively energy-efficient due to the absence of the certificate exchanges, even though it requires 2 public-key encryption operations at the client. Revised public key encryption based authentication is almost as energy-inefficient as the public key signature based authentication since it also involves exchange of large certificates. Pre-shared key based authentication scheme consumes least energy but is unsuitable for large-sized networks and mobile operations. An optimized session negotiation protocol based on revised public key encryption is most suitable for wireless environment since it allows the client to send the URL of its certificate to the server instead of the certificate. Therefore, it is energy-efficient, scalable, involves only one public-key encryption at the client, does not carry out private-key encryption and transmission of the large certificate and uses ephemeral shared secrets (based on the exchanged nonces). In general, most mobile transactions either do not need user authentication or can use simple password based authentication schemes. With the increasing mobility of wireless devices across heterogeneous wireless networks frequency of session establishment, and hence authentication is increasing. A provision for unidirectional authentication together with simple password based schemes can significantly reduce the energy consumed by a mobile client during secure wireless sessions.
OPTIMIZING IPSEC FOR ENERGY-EFFICIENT SECURE WIRELESS SESSIONS
5.
151
SUMMARY
A security protocol offers three levels of security: refreshing the security associations, refreshing the encryption and the MAC keys and varying the length of the secret keys and the number of rounds of encryption. Our proposed schemes affect security protocols at all three levels of security, as shown in Table 9-15.
Let us examine the impact of the presented techniques on the energy consumption characteristics of a secure wireless session while transmitting 20 MB data over an 11 Mbps WLAN channel with key refreshes every 128 KB of data and session refreshes every 2 MB of data.
Table 9-16 compares the energy consumed by an un-optimized scheme using basic session negotiation protocol, supporting 3DES encryption and SHA-256 MAC in software and no compression scheme with the energy consumed by an optimized scheme using adaptive session negotiation
152
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
protocol, supporting 128-bit key AES encryption and SHA-256 MAC in hardware and DEFLATE data compression. We assume a compression ratio of 3.48 corresponding to the data block size of 8 KB. Details of hardware implementation of cryptographic mechanisms can found in [KM02]. Figures in ‘()’ refer to the frequency of the corresponding operations. For example, un-optimized scheme performs 9 session negotiations and 150 key refreshes. Optimized scheme reduces the energy consumed during data transmission by more than 2× and the energy consumed during data reception by more than 3.8×. Since energy saved due to hardware acceleration is not very significant, adopting a performance, energy consumption and area trade-off based software-hardware co-design approach is more beneficial. In this chapter we investigated the energy consumption characteristics of computation-intensive security protocols. We presented techniques to reduce the energy consumed by security protocols during a secure wireless session and used a real-life mobile test bed to demonstrate the energy savings obtained by implementing these techniques. This research can be extended by developing a comprehensive communication security architecture that will integrate these and other accurate energy-models for various components of the security protocols with accurate energy models of other networking components.
ACKNOWLEDGMENT This work was supported by New York State Office of Science, Technology and Academic Research (NYSTAR) and Wireless Internet Centre for Advanced Technology (WICAT) at Polytechnic University, Brooklyn, NY.
Chapter 10 NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
Debashis Panigrahi, Sujit Dey, and Anand Raghunathan* Department of Electrical and Computer Engineering University of California, San Diego {dpani, dey} @ ece.ucsd.edu * C &C Research Labs, NEC, USA, Princeton [email protected]
Abstract:
Wireless web access is projected to be a primary driving application for the success of next generation wireless data services. However, enabling efficient wireless web access has several bottlenecks, including varying wireless channel conditions and limited battery capacity of handheld devices. In this chapter, we propose a framework to address these bottlenecks by shaping the content delivered to a handheld appropriately, depending on current network/channel conditions, in order to minimize energy consumption. A critical part of the framework is estimation of energy consumption by a handheld in accessing web content. To estimate energy consumption, we develop an energy model for wireless web access by PalmVII handheld, considering the effect of network-related parameters as well as applicationlevel parameters. Next, we propose energy-conserving transformation techniques that change the organization of the information delivered to a handheld based on current network conditions. We demonstrate that significant energy savings can be achieved by the proposed network-aware content shaping techniques.
Key words:
Content shaping, Energy efficiency, Wireless web.
1.
INTRODUCTION
Wireless access to web-based applications is projected to be one of the primary driving factors behind the adoption and growth in the use of
154
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
wireless handheld devices and network services. The increase in communication bandwidth provided by next generation wireless networks, together with the increasingly complex protocols employed, and the rich functionality of wireless web-based applications, will elevate battery constraints to a design challenge of primary importance. Additionally, battery capacity is projected to increase at a much slower rate than the energy requirements of high-performance handheld devices [PO95,KI98, Hence, it is critical to consider energy consumption and battery life during the design of radio and handset appliance architectures as well as the software that runs on them, including network protocols and networked applications. Recognizing the energy challenges mentioned above, researchers have started working on various techniques to improve the energy efficiency of wireless appliances. Techniques for low-power hardware implementations of various components of wireless handhelds, including processor, display, and radio transceivers, have been proposed. While optimizing the hardware architecture and implementation does yield considerable energy savings, it is equally important to consider energy issues during the design of the network protocols and applications. Techniques for low-power protocols across different protocol layers have recently been investigated [SS97, In this chapter, we propose to develop content-level optimization techniques for web-based applications to conserve energy, further extending the above efforts. In order to analyze and optimize energy consumption for web-based applications, it is critical to develop an accurate energy model for the target device along with the supported wireless network interfaces. A characteristic of wireless networks that significantly affects the energy consumption is the varying channel conditions. In addition to modelling effects of applicationlevel parameters, such as volume of data transfer, an accurate energy model should also capture the effects of dynamic channel variations, an important characteristic of wireless communications. In the area of energy modelling for handheld devices, several attempts have been made to characterize the power consumption of PDAs without wireless network access capabilities Power measurements on network interfaces in handheld devices were presented in FN01]. However, none of the above models address the possible effects of channel variations on energy consumption. In our previous work we proposed an energy model for wireless web access for a PalmVII handheld considering applicationlevel parameters, such as bytes received/transmitted, compression, encryption, etc. In this chapter, we further enhance the model to consider the effects of network variations, such as received signal strength, network
NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
155
load, and error control techniques. We demonstrate that dynamic channel variations have significant effects on the energy consumed to access webbased information. Next, using the developed energy model, we propose techniques to shape the content delivered to mobile clients by appropriately modifying and organizing the content, termed as content shaping, depending on current wireless channel conditions and access patterns of users. In the area of organizing information on web sites, several personalization techniques have been proposed to configure the look and feel of a web site depending on a user's interests and past access patterns Similarly, techniques have been proposed to shape web sites for handhelds with display limitations [AI]. Additionally, transcoding techniques have been proposed to change the format/coding of multimedia content delivered to handhelds with lowresolution and small displays [CE99, These methods are complimentary to our content shaping approach. To our knowledge, our work is the first to demonstrate that content shaping techniques lead to significant savings in energy consumption, and hence improvements in battery life. The rest of the chapter is organized as follows. We introduce our energy model in Section 2, emphasizing the effect of network-related parameters and the validation of the energy model. In Section 3, we describe our transformation techniques to reduce energy consumption and present experimental results that evaluate their potential for energy savings.
2.
ENERGY MODELING
In this Section, we present our energy model, which is built using data accumulated by measuring the energy consumed by a Palm VII handheld for various web access patterns. We first describe the wireless access architecture of Palm.Net [BW], the wireless Internet Service Provider (ISP) used by the Palm VII handheld. Next, we present the data acquisition framework used for energy measurements, and report the energy model resulting from our experiments.
2.1
Palm.Net Wireless Access Architecture
The wireless environment used for Palm VII wireless internet access is shown in Figure 10-1. A key component of the wireless environment is the wireless gateway server that resides at the data centers. The handhelds communicate with the wireless gateway servers using the BellSouth
156
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Wireless Data network, which uses the MOBITEX wireless packet protocol [MW, BW]. The wireless gateway servers use standard web and security protocols (TCP, HTTP, and SSL) to communicate with web servers over the wired network, whereas on the wireless channel, protocols designed to tolerate channel errors, low bandwidth, and high latency, such as reliable UDP, are employed [MW].
2.2
Data Acquisition
The energy consumption of the Palm VII handheld is measured by integrating the product of the supply voltage and the current drawn over time. The Palm VII handheld has two sources of power: (i) a NiCd rechargeable battery, operating at 5V, is used to supply power to the radio transceiver, and (ii) two AAA alkaline batteries, operating at 3V, are used to supply power to the rest of the handheld. Hereafter, the NiCd battery is termed as the radio battery, and the AAA alkaline batteries are collectively referred to as the system battery.
Figure 10-1 shows the setup used for energy measurements. For the purpose of energy measurements, the radio and system batteries were removed from the handheld, and replaced by laboratory DC power sources of the same voltage. Hence, the supply voltages were assumed to be
NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
157
constant over the duration of measurement. The currents drawn from the radio and system batteries were measured by sampling the voltage drop across resistances connected in series to the power supplies, as shown in Figure 10-2. The voltage drops were sampled using the DAQ-1602/PCI data acquisition card [DAb], operating at 1K samples/sec. The sampled data can be analyzed and displayed using the DaqEZ software [DAb]. A current profile displayed using the DaqEZ software is shown in Figure 10-2. In the figure, the top waveform corresponds to the current drawn from the radio battery, while the bottom waveform corresponds to the current drawn from the system battery. For our energy measurements, we developed a test-bed that consists of a client test program running on the Palm VII handheld, and a set of web sites that reside on a web server. The client test programs were developed using the networking primitives available in the PalmOS library [PO]. We executed several client test programs by changing the parameters of interest, and measured the energy consumption for each execution under diverse network conditions.
2.3
Energy Measurements and Modelling
In this Section, we present our energy model for wireless web-based applications. First, we discuss the various parameters that impact the energy
158
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
consumption. We then present a mathematical model for energy consumption, based on these parameters. We use the data gathered by the experimental set-up presented earlier, and perform regression fitting in order to derive the values of the constants/ coefficients used in our energy model. The factors that affect the energy consumption for wireless web access can be classified into two categories: (i) application-level parameters, and (ii) network-related parameters. Application-level parameters correspond to the parameters that are determined by the application-level communication primitives used in wireless web-based applications. The application-level parameters considered in this model include the volume of data transmitted/received, the compression and encryption schemes employed, and the use of web page caching. Network-related parameters include the wireless channel signal strength, noise level, and network latency. We presented an energy model considering the effect of application-level parameters in In this chapter, we concentrate on modelling the effect of network-related parameters. In our work, we consider only the network-related parameters that may have an effect at the application layer. For example, channel effects, such as multi-path fading [RA], are better addressed at lower protocol layers. In this model, we consider the parameters network latency and signal strength, whose effect can be visible at the application layer, and later propose application layer transformations to adapt content in response to variations in these network parameters. Network Latency: Network latency is one of the parameters related to the wireless network environment that can significantly affect the energy consumption. In our context, the network latency is defined as the delay from the time when the HTTP request is made by the application to the time when the packets containing the response are received. Network latency is caused by the wireless network in getting access to the channel as well as by the web server and the wired network in responding back to the request. The handheld consumes energy during this period while it is waiting for the response. Our measurements indicated that the energy overhead due to network latency increases linearly with the duration of latency. Signal Strength: Signal strength is another parameter that can potentially affect the energy consumption. The main factors affecting the signal strength include the distance from the base station, shadow fading, channel noise, etc. As the received signal strength decreases, the handheld radio increases the power level of the transmitted signal in order to compensate for poor channel
NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
159
conditions, thus increasing the total energy consumption. Additionally, low signal strength leads to more errors in the received signal, and hence greater number of re-transmissions at the link layer, as dictated by the protocol used by Palm [MW]. In order to figure out the dependencies between the signal strength and the level of current used for the transmitted signal, we monitored the radio battery current as we launch the diagnostic software available in Palm VII that reports the current signal strength. Similarly, to evaluate the effect of signal strength on re-transmissions, we analyzed different traces of the Palm radio’s current, and summarized the findings in terms of an average number of re-transmissions per packet for different signal strength values. Figure 10-3 shows the overall effect of signal strength on energy consumption. We plot measured energy consumption for a few traffic patterns (with different bytes transmitted/received) under different signal strength conditions. We quantify signal strength by a number between 1 and 10, where 1 corresponds to very good signal strength and 10 to very bad signal strength. It can be noted that for any traffic pattern, the energy consumption increases with signal strength degradation. Additionally, the rate of increase in energy consumption is dependent on the volume of data traffic. For example, as the signal strength degrades from 2 to 10, the increase in energy consumption to transmit 2048 Bytes is 7 Joules, whereas the corresponding increase for transmitting 64 Bytes is 1 Joule.
Using the above dependencies of energy consumption on signal strength, we scale the energy consumed by modifying the coefficients of the energy model based on the signal strength, and add another term to the energy
160
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
model, which captures the energy overhead due to re-transmissions, as explained later in the section. Energy Model Based on the above observations and experimental results, we enhanced the energy model presented in in which we considered only the application-level parameters, such as amount of data transmitted and received, compression, encryption, etc. In order to understand the different factors contributing to energy consumption, we show in Figure 10-4 the different steps involved in executing a HTTP transaction. We analyze energy consumption of each step separately, and find the dependency between the energy consumption and the related parameters. Finally, as the different steps do not overlap in the time domain, we can add the energy consumed in each step to estimate the total energy. The resulting energy model is presented in Figure 10-5.
The terms in the energy model shown in Figure 10-5 correspond to distinct operations in a web transaction, namely connection setup, waiting for the response, receiving, transmission, encryption/decryption, and compression/decompression. The first three terms of the energy model
NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
161
correspond to the connection setup and close step (phases B and I as shown in Figure 10-4), packet transmission steps (phases C and D, E), and packet receiving steps (phases F and G, H), respectively. As presented before, the RF current level is dependent on the current channel signal strength, and hence the energy consumption of the steps involving communication of data should depend on the current channel signal strength. In order to characterize the above effect, we make the coefficients C0, Cr, and Ct vary according to the signal strength. The fourth and fifth terms in the energy model correspond to the computational energy consumption in the encryption and compression steps. Note that, in the Palm.Net environment, compression is done only for downlink traffic (i.e. data received by the wireless client), and encryption is enabled only for upload traffic [MW]. Hence, energy consumed for encryption depends on Bytes transmitted (T), whereas energy consumed for compression depends on Bytes received (R). Finally, the last term in the energy model represents the energy consumed in idle (waiting mode) and packet re-transmissions (F and H), which depends on the current channel signal strength and network latency. Both signal strength and network latency are calibrated on a scale of 1 to 10, where each number represents a specific signal strength (%) and network latency (seconds). Next, we present the validation of the proposed energy model.
162
2.4
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Validation of Energy Model
In order to validate our energy model, we compared the energy estimated by the energy model with the measured energy consumption for fifteen different random web transactions under diverse network conditions. Table 10-1 presents the results of our comparison. In columns 2, 3, 4, and 5, we report the amount of data transmitted (bytes), data received (bytes), network latency, and signal strength for each test case respectively. As presented earlier, we quantify network latency and signal strength on a scale of 1 to 10, where each number represents a specific signal strength (%) and network latency (seconds). Column 6 reports energy measured for each transaction, and column 7 reports energy estimated by our proposed energy model.
We also plot the measured energy and estimated energy for each test case in Figure 10-6. It can be seen from the figure that for most test cases our energy estimate closely matches the measured energy. For two out of fifteen test cases, there is a large gap between the estimated energy and the measured energy. These errors are due to the assumption of a constant channel condition within a single HTTP transaction, which may not be true in real network conditions.
NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
163
Also, for a few test cases, the number of re-transmissions assumed in the energy model represents the average case, which may lead to some error in energy estimates. In particular, for test case 1, there were a lot of retransmissions, which corresponds to a very extreme case, and hence the estimated energy does not match well with the measured energy. Next, we present application-level content shaping techniques, which use the above energy model to optimize energy consumed by handheld accessing webbased information.
3.
NETWORK-AWARE CONTENT SHAPING
Our approach to enabling energy efficient web-based applications is based on optimal shaping of the information delivered to the mobile client. In this Section, we demonstrate how significant energy savings can be achieved by optimal design of web sites taking into consideration current network conditions as well as access patterns of the users. The design of a web-based application involves presenting the necessary information to the client in a structured form (organized into a set of web pages, with appropriate links between them for ease of navigation). The organization of information into web pages should ideally take into consideration the various issues related to wireless web access, such as energy, display size, bandwidth, display resolution etc. Currently, different standards are being proposed, for example, web-clipping [PW], and WAP
164
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
[WA], to address some of the above constraints, such as display size and bandwidth. However, in these standards, the organization of web sites is fixed for all handhelds, and does not provide the capability to adapt to the changing network conditions. We believe that significant savings in energy can be achieved by shaping the content of the web sites according to the current network conditions and access patterns of users. Before we present content shaping techniques, we present a data structure called Web Flow Graph, which is used in our optimizations to represent the organization of information in a web site. 3.1
Web Flow Graph
We represent the information that a web site contains abstractly by a graph data structure called Web Flow Graph (WFG). An example WFG is shown in Figure 10-7. Each node in this graph represents a piece of information or a web page, and each edge represents the link between two web pages. The HTML files corresponding to each node are listed in the right portion of the figure. For each node, we annotate three attributes, namely (i) Bytes to be transmitted by the wireless client to retrieve it (T), (ii) Bytes received by the wireless client (R), and (iii) priority of the information contained in the node (P). The priority values reflect the importance of the information contained in the node from the content provider's point-of-view. We use the priority values as a guidance factor in some of our transformation techniques. As we transform the original web site, the organization of the information is changed, which may have effects on the user experience as he/she browses the web. We try to characterize the users’ or publisher’s perspective by a Quality of Content (QoC) metric, which is computed as follows.
, where Pi = priority of node i, W_trans = transformed WFG, and W_orig = original WFG
NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
165
We associate two attributes to each edge of the graph, representing access statistics and semantic relationship between information nodes. We capture access statistics by associating, for each edge a weight (between 0 and 1) that represents the conditional probability of traversing the link from Vi to Vj. Similarly, we use a semantic relationship index for each edge that represents the semantic relationship between the information contained in the two nodes it connects. For example, semantic relationship between C and H is 0, which corresponds to "commercial" relation, referring to advertisements present on the pages. Similarly, there are types of semantic relationships, including summarization, composition, elaboration, navigation, etc. We use the semantic relationship index to guide some of our transformation techniques. We use a web-crawler program WebBot [WB] to construct the backbone WFG for any given website. After that, we annotate the graph with appropriate access statistics collected by processing access logs from web servers. Finally, we annotate the WFG with priority and semantic relationship index information. The last step currently has to be done manually by the content provider/organizer. In order to estimate the average energy consumption, we first generate random sessions with accesses to different web pages inside the web organization guided by the access
166
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
statistics information. We use our energy model to estimate average energy consumed to access the website by using the PalmVII energy model proposed in Section 3. We iterate through the whole process as we apply different transformation techniques. The overall methodology used to capture the WFG and estimate energy consumption is shown in Figure 10-8.
3.2
Transformation Techniques
First, we present four different techniques to reduce energy consumption depending on the current network condition. We will use the example WFG shown in Figure 10-7 to demonstrate results of our transformation techniques. In each of the transformation techniques, we follow a generic methodology to select the node(s) on which the transformation can be applied. First, we compute a metric using the information provided in WFG, for example, the ratio of bytes transmitted (T) and the bytes to be received (R). Then, we compare the computed metric with a threshold value, and based on the comparison results we select the nodes for transformations. We vary the threshold value based on the channel condition, characterized by signal strength. We will present the metrics used as we discuss the transformation techniques.
NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
167
Merging
As the name suggests, in this technique, we combine two or more nodes into one node. In accessing any node (or web page), a handheld transmits the address/URL of the node to the gateway server. So, by combining two nodes, the information to be transmitted is reduced for some access patterns, i.e. when both the nodes need to be accessed. It also reduces the latency of retrieving the nodes when both nodes are accessed. We combine the nodes only when the merging operation leads to energy saving in the average case. Consider two nodes Nl and N2, which are candidates to be merged. Supposed that p is the access probability associated with the edge from Nl to N2.When both nodes are accessed, it leads to savings in energy consumption due to decrease in bytes transmitted. Let us denote the savings in transmit energy by However, when only one node is accessed (with probability 1-p), it increases the overall energy consumption due to increase in bytes received. Let us denote the increase in energy consumption for receiving additional unnecessary information by Then, after considering the access statistics, the average savings in energy consumption after the merging is So the nodes should be combined only when the above expression is positive. To simplify the decision, let us assume a linear energy model (with E = x*T + y*R where E is energy, T and R are bytes to be transmitted and received respectively, and x and y are linear coefficients that depend on the channel condition). With the above simplified energy model, the average energy savings and the condition for transformation can be written as , where x and y are coefficients that depend on the channel condition. To select the nodes based on the information of WFG, we compute the ratio of the bytes to be transmitted scaled by p, i.e. (p*T), and the bytes to be received scaled by (1-p), i.e., (l-p)*R, and compare it with a merging threshold ratio. The nodes are merged only when the ratio is greater than the merging threshold ratio. The merging threshold ratio is set according to the current network condition, reflecting the relation between E and T/R. Intuitively, under harsh channel conditions, since the energy per byte of transmission is high, the above scheme would lead to merging of nodes with higher R (bytes to be received) value, while good channel conditions would favour less merging. After the nodes are merged, appropriate changes are made to the access probability values. Note that, we do not loose any content in this transformation, and hence the quality of content (QoC) remains the
168
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
same. We applied the merging technique to the example web site shown in Figure 10-7.
Table 10-2 summarizes the savings in energy under different network conditions (characterized by different signal strengths), for access statistics as annotated in the web flow graph of Figure 10-7. Splitting This technique is just opposite to the merging technique presented above. Here, we split a node into different sub-nodes. Here, we possibly reduce energy consumed in receiving information, since on the average only a subset of nodes in the transformed graph is accessed. However, energy consumed in transmitting the address information from the wireless client to the server is increased. Splitting techniques are useful to reduce the amount of information to be received and also reduce the overall latency of the web session. Summarization of large web documents can be thought of as a special case of splitting technique. In this case, we consider documents with size larger than a threshold size and, similar to the above approach, we use the ratio of bytes transmitted (T) to bytes received (R) as the decision metric (assuming the access probability of the edge between split nodes is 1/2). We split only when the computed ratio is less than a splitting threshold ratio. The splitting threshold ratio value decreases as the network condition deteriorates because, in bad channel conditions over-splitting would lead to higher energy consumption for transmitting the HTTP requests. When we apply the splitting technique on the example web design, it achieves an energy savings of 7% for bad channel conditions (4 and 5), and does not affect the energy consumed for good channel conditions. Deletion In order to conserve energy, this technique deletes some of the information nodes from the web site organization. Examples of such information nodes could include advertisements, multimedia nodes, etc. Here, the clients conserve energy by not retrieving the deleted information.
NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
169
In the process, we decrease the quality of the content delivered to the user. We base the aggressiveness of our deletion technique on the priority of the information node and the size of the node. We also consider semantic relationships while identifying the nodes to delete. Similar to the above approaches, we select a combination of threshold values for all the above parameters depending on the current network condition. For example, we delete small, low priority nodes first. We check the semantic relation index of all candidate nodes for deletion and delete only those nodes that are permitted by the semantic relationship. Table 10-3 shows the effect of the deletion techniques on the energy consumption and QoC under different channel conditions. It can be seen from the table that significant savings (27%) in energy can be achieved, with a penalty of reduced QoC (around 15%).
Migration In this technique, we move nodes into different locations in the organization of the web site. By appropriately placing different nodes based on access patterns of users, the number of intermediate web accesses need to retrieve the required information is reduced (fewer links traversed to get to the desired information), thus reducing the energy consumption. In order to decide which nodes to migrate, for each node, we calculate the conditional probability of accessing any other node not connected directly to the node. For example, in the WFG shown in, conditional probability of reaching node G from node A is 0.5. If the conditional probability is more than a migration threshold, we migrate the child node (G) closer to the parent node (A). As in other transformation techniques, we change the migration threshold depending on the current network condition.
170
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Table 10-4 shows the effect of the migration technique on energy consumption when different nodes are migrated according to the channel conditions.
In addition to the above server-based techniques, pre-fetching can be used from the client side to reduce energy consumption. Pre-fetching will reduce the idle energy consumed while waiting for the data in bad network conditions with long network latency. In we presented a generic class of pre-fetching algorithms, which use the access probability associated with each link to decide which pages to pre-fetch. In that scheme, a page is pre-fetched only if the access probability is more than a pre-fetching threshold. Our experiments showed that significant savings in energy
NETWORK-AWARE CONTENT SHAPING FOR ENERGY EFFICIENT WIRELESS WEB ACCESS
171
consumption can be achieved by appropriately selecting the pre-fetching threshold. In Figure 10-9, we show two example transformed WFGs after we apply the techniques (deletion, merging, splitting, and migration) sequentially under two distinct channel conditions. For each transformed WFG, we provide the channel condition, average energy consumption for the original WFG, and average energy consumption for transformed WFG. It can be seen that significant savings (17%) can be achieved after we apply the presented transformation techniques. In future work, we will investigate in detail possible inter-dependencies between the presented transformation techniques, and how the above-presented techniques can be applied simultaneously to produce optimal organization of information for different channel conditions.
4.
CONCLUSIONS
In this chapter, we developed an energy model for wireless web access using a measurement based methodology for a Palm VII handheld while considering the effect of network related parameters such as signal strength, network delay and re-transmissions. Using the energy model, we proposed application-layer content shaping techniques in order to reduce energy consumption in accessing web-based information. The proposed content shaping techniques adapt to the current network conditions and user preference to deliver appropriate information to the mobile client in a manner that minimizes energy consumed while retaining quality of content.
This page intentionally left blank
Chapter 11 INDIRECT HTTP: AN ENERGY EFFICIENT EXTENSION OF HYPERTEXT TRANSFER PROTOCOL FOR WEB BROWSING
Jen-yi Pan*, Wei-Tsong Lee** and Nen-Fu Huang* *Department of Computer Science, National Tsing Hua University, Hsin-Chu, Taiwan, 300; **epartment of Information Engineering, Feng-Chia University, Seatwen, Taichung, Taiwan, 407
Abstract:
Access to the Internet via personal communication system (PCS) is expected to become a vital part of future wireless operators’ service offerings. In addition, the World Wide Web (WWW) has become the most important application and service over the Internet. The Internet and WWW are very critical, so that users hope to enjoy all kinds of services in the Internet anywhere and in anytime. One of the greatest limitations to that goal, however, is finite power supply. Since batteries provide limited power, a general constraint of wireless communication is the short continuous operation time of mobile devices. In this chapter, we propose a realizable energy efficient extension of hypertext transfer protocol (HTTP) for web browsing. The chapter explains the energy efficient issues of the HTTP/1.1, and proposes an energy efficient extension of HTTP/1.1. Performance of the proposed extension is analyzed in terms of the factor of power reduction. This study also demonstrates a referable methodology to propose and analyze an energy efficient protocol of application layer, which can promote the technology of power-aware communication, computing, and networking.
Key words:
Power conservation, Energy efficient protocol, Wireless Internet, HTTP/1.1, Wireless web proxy, Wireless web browsing.
174
1.
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
INTRODUCTION
Wireless communications have made spectacular progress in recent years. Access to the Internet via personal communication system (PCS) is expected to become a vital part of future wireless operators’ service offerings. Third-generation communication systems designed to carry multimedia traffic such as voice, video, audio, animation, images, and data transmission are under intensive research investigation. In particular, the merge of various wireless communication systems and the Internet has become more significant so that users can enjoy all kinds of services in the Internet while owning mobility. For example, modern wireless networks can support Internet applications for web accessing. Many issues need to be addressed for such combination. Host mobility and wireless-related characteristics add a new dimension to many research issues, such as network protocols and, WWW access. The World Wide Web (WWW) has become the most important application over the Internet. The network traffic statistics generated [TM99] by the computer center of ministry of education in Taiwan confirms that eighty-five percent of network traffic in Taiwan belongs to Hypertext Transfer Protocol (HTTP) The Internet and WWW are very essential, so that users hope to enjoy all kinds of services in the Internet anywhere and in anytime. One of the greatest limitations to that goal, however, is finite power supply. Since batteries provide limited power, a general constraint of wireless communication is the short continuous operation time of mobile devices. Based on the above facts, we should present a practical energy efficient HTTP for web browsing. The chapter explains the energy efficiency issues of the HTTP/1.1, and proposes an energy efficient extension of HTTP/1.1. Performance of the proposed extension is analyzed in terms of the factor of power reduction. Comparing to the original HTTP/1.1, the power saving of the protocol extension is proportional to the ratio of the transmission time of wide area network (WAN) to the transmission time on the air for each web object, which means the better performance can be achieved when the speed of wireless local area network (wireless LAN) is much faster than the speed of WAN, such as some high-performance wireless Ethernet providing 22 Mb/s transmission The power saving of proposed extension also depends on the media access control layer (MAC layer), which affects the power consumption while the transceiver receiving one packet in different lengths of time. After the study, we not only proposed an energy efficient extension of HTTP/1.1 over TCP/IP for wireless Internet, but also demonstrate a referable
INDIRECT HTTP: AN ENERGY EFFICIENT EXTENSION OF HYPERTEXT TRANSFER PROTOCOL FOR WEB BROWSING
175
process to propose and analyze an energy efficient protocol of application layer, which can promote the technology of power-aware communication, computing, and networking. The rest of this chapter is organized as follows. Section 2 highlights the related works of hypertext transfer protocol and energy efficiency issues over the HTTP. Section 3 presents our energy efficient extension for the HTTP. Section 4 analyzes the performance of this energy efficient extension. Concluding remarks are finally made in section 5.
2.
RELATED WORKS
The Hypertext Transfer Protocol (HTTP) is an application-level protocol for distributed, collaborative, hypermedia information systems. HTTP has been in use by the World-Wide Web global information initiative since 1990. The HTTP protocol is a request/response protocol. A client sends a request to the server in the form of a request method, Uniform Resource Identifier (URI), and protocol version, followed by a MIME-like message containing request modifiers, client information, and possible body content over a connection with a server. The server responds with a status line, including the message's protocol version and a success or error code, followed by a MIME-like message containing server information, entity meta-information, and possible entity-body content. Most HTTP communication is initiated by a user agent and consists of a request to be applied to a resource on some origin server. In HTTP/1.0, most implementations used a new connection for each request/response exchange. In HTTP/1.1, a connection may be used for one or more request/response exchanges, although connections may be closed for a variety of reasons. In this chapter, each item, which transmitted in one request/response exchange, is called a web object. The GET requests dominate nearly all of the HTTP traffic, and the current version of HTTP is HTTP/1.1. Hence, we discuss only the energy efficient extension of the GET method in HTTP/1.1.
2.1
Persistent HTTP Connections
Prior to persistent connections, a separate TCP connection was established to fetch each URL, increasing the load on HTTP servers and causing congestion on the Internet. The use of inline images and other associated data often require a client to make multiple requests of the same server in a short amount of time. Analysis of these problems and results from
176
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
a prototype implementation are available in the references of HTTP/1.1 (RFC 2616) Figure 11-1 shows the scenario of a persistent HTTP connection. The web client sends a request “GET A” to the web server through the base station. The transmission media between wireless web client and the base station is the air. The base station is a bridge between the air and the wired network. Between the base station and the web server is the wide area network (WAN). When the web server receives a “GET A” it responds with an “OK A” status code and the content of A called web object A. The colour-filled area below “OK A” is the transmission of web object A. After the web client gets the whole web object A, it sends the next request “GET B” to get the web object B, without closing and reopening an HTTP connection.
Persistent HTTP connections have a number of advantages: By opening and closing fewer TCP connections, CPU time is saved in routers and hosts (clients, servers, proxies, gateways, tunnels, or caches), and memory used for TCP protocol control blocks can be saved in hosts. Thus, the power consumption also is reduced. Decreasing the number of packets caused by TCP opens reduces network congestion. In addition, allowing TCP sufficient time to determine the congestion state of the network also relieves overcrowding because of its congestion control mechanism. Without network congestion, unnecessary retransmissions can be reduced, and hence more energy can be saved. Latency on subsequent requests is reduced since there is no time spent in TCP's connection opening handshake. Therefore, the energy for opening handshake is saved.
INDIRECT HTTP: AN ENERGY EFFICIENT EXTENSION OF HYPERTEXT TRANSFER PROTOCOL FOR WEB BROWSING
177
HTTP can evolve more gracefully, since errors can be reported without the penalty of closing the TCP connection. The energy for reopening handshake is also saved. Consequently, HTTP/1.1 suggests implementations should implement persistent connections, and the persistent connection really saves more energy.
2.2
Pipelining
HTTP requests and responses can be pipelined on a connection. Figure 11-2 illustrates the scenario of pipelining in one connection. The web client sends the “GET A” to the web server, and then sends the “GET B” without waiting for the response of “GET A”.
Pipelining allows a client to make multiple requests without waiting for each response, allowing a single TCP connection to be used much more efficiently, with much lower elapsed time. Thus, the energy is used more efficiently. A web server must send its responses to those requests in the same order that the requests were received. For a long-term connection, the initial response time can be neglected comparing with the connection holding time.
2.3
Web Proxy
Another means of managing energy and bandwidth for applications on mobile clients is to use web proxy [BO00, WA99, Figure 11-3 demonstrates the scenario of HTTP operation when a web proxy is between the web client and the web server. First, the web client sends a request “GET A” to its web proxy, and then sends another request “GET B” because of
178
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
pipelining. Then, the proxy receives “GET A”, but it doesn’t have the cached web object A. Hence, the proxy sends “GET A” to the web server. After that, the proxy receives the pipelined request “GET B”. In this scenario, the web proxy has the cached web object B. However, the proxy must send its responses to those requests in the same order that the requests were received. Thus, the only thing it can do is to wait the response from the web server. Then, the web server responses “OK A”, and sends the web object A to the web proxy. At the same time, the web proxy forwards the web object A to the web client. After transmitting web object A, the proxy then transmits the cached web object B to the web client. The darker colour means the web object is cached in the web proxy, and may take shorter time to transmit because the web object B doesn’t need to download from the possibly congested WAN.
The web proxy does not only save the bandwidth accessing to the Internet, but also reduce the mean transmission time of WAN for every web object. The shorter transmission time also may reduce the power consumption of transceivers.
3.
PROPOSED PROTOCOL EXTENSION
The scenario of proposed extension of HTTP is shown in Figure 11-4. Differing from the web proxy scenario of the original HTTP/1.1, the proposed extension uses the status code “202 Accepted” to reply the request method “GET”. This usage is not shown on the specification of HTTP/1.1. Besides, the response carries a “Retry-After” header to suggest the client when to get the web object again in the proposed extension. In original
INDIRECT HTTP: AN ENERGY EFFICIENT EXTENSION OF HYPERTEXT TRANSFER PROTOCOL FOR WEB BROWSING
179
HTTP/1.1 this header is not included in the response of the status code “202 Accepted”. The “Retry-After” response-header field is originally used with a 503 (Service Unavailable) response to indicate how long the service is expected to be unavailable to the requesting client. It is also used with any 3xx (Redirection) response to indicate the minimum time the user-agent is asked wait before issuing the redirected request. The value of this field can be either an HTTP-date or an integer number of seconds (in decimal) after the time of the response [FG99+].
The proposed extension reduces the “convoy effect” over web browsing, which is similar to the convoy effect in job scheduling of operation system. The web object which needs longer transmission time of WAN will occupy the persistent connection to the web server for a long time, and hence the following web objects requested through the same persistent connection also will also have a long response time because a web server must send its responses to those requests in the same order that the requests were received. For the proposed extension of HTTP/1.1, the proxy immediately responses a status code “202 Accepted” to postpone the request while receiving a request which needs longer transmission time of WAN. Therefore, the following requests will not be blocked and get shorter response time. During the “Retry-After” period, the web client doesn’t need to care about the transmission of web objects in WAN, and may temporary suspend the connection or even make its transceiver enter power-saving mode because the proxy will not send any packets to the web client without requesting, except the proxy decides to shutdown connections or does a keep-alive probe (RFC 1122). The shutdown action can be detected when
180
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
the client sends requests again. The keep-alive probe duration can be known in advance and even adjusted by tuning kernel variables [SO]. Furthermore, the web objects of postponed requests will be downloaded into the proxy in the “Retry-After” period, and then web clients can receive these web objects faster on the air without the proxy simultaneously connecting to the web server. Hence, the power consumption also can be reduced for shorter working time of wireless transceiver on web clients. Because the web client may not fetch the web object at the first request, we call this extension of HTTP by “Indirect HTTP”.
4.
PERFORMANCE EVALUATION
4.1
Power Consumption Modelling
Referring to the Amdahl’s Law [AM67], we have similar discussion for the power consumption. The power consumption C for downloading each web object can be divided into two parts. One part is not varied with the downloading time, noted by For example, may contain the power consumption for receiving every packet of the web object. The other part, noted by is positively linearly proportional to the downloading time for the object. For example, may contain the power consumption for listening to every packet address to determine which packets on the air should be received. Hence,
Moreover, the non-varied fraction of power consumption the following equation.
is defined by
The downloading time speedup S of proposed method is defined as
INDIRECT HTTP: AN ENERGY EFFICIENT EXTENSION OF HYPERTEXT TRANSFER PROTOCOL FOR WEB BROWSING
181
Suppose the proposed method decrease a fraction of the power consumption, and the remainder of the power consumption is unaffected. Therefore, we have a power consumption function of S for proposed method, defined as
Furthermore, the factor of power reduction can be defined as
We can rewrite PR(S) with the non-varied fraction of power consumption as follows.
Then, we can derive the limitation of the factor of power reduction for an infinite speedup, as follows.
4.2
Speedup for Proposed Extension
The overall downloading time for one web object is determined by the transmission time on the air, and the transmission time in wide area networks (WAN). The larger transmission time dominates the other one. We assume the transmission time of each web object on the air has the memory less property, and is represented by a random variable which negatively exponential distributed with the mean
182
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Hence, we have a probability distribution function (PDF) and a cumulative distribution function (CDF) for this random variable, as follows.
Similarly, we assume the transmission time of each web object in WAN also has the memory less property, and is represented by a random variable which also negatively exponential distributed with the mean
Thus, we have the PDF and the CDF for the random variable as follows.
Moreover, the overall downloading time for the original method is noted by the random variable determined by the above two random variable.
Therefore, the CDF of follows.
is noted by
and we can derive as
INDIRECT HTTP: AN ENERGY EFFICIENT EXTENSION OF HYPERTEXT TRANSFER PROTOCOL FOR WEB BROWSING
The PDF of
is noted by
The expected value of
183
and we can derive from above.
is derived as follows.
The downloading time for the proposed method only depends on the transmission time on the air. Hence, the speedup due to enhancement of proposed extension is
4.3
Numerical Results
To simplify the discussion, we define the ratio of the mean transmission time of WAN to the mean transmission time on the air, noted by
Then, we can rewrite the speedup due to enhancement of proposed extension as follows.
184
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
Figure 11-5 shows the factor of power reduction by varying the nonvaried fraction of power consumption and the ratio of the mean transmission time of WAN to the mean transmission time on the air Higher PR means the proposed method has more saving on power consumption than the original one. For a certain the PR goes higher when increases. This means the proposed method performs better when the transmission speed of wireless LAN is much faster than the WAN’s. In addition, the PR for each has the upper bound For example, when equals to 0.9, the limitation of PR is 1.11.
For a certain the PR increases hyperbolically when decreases. This means the proposed method performs better when the non-varied fraction of power consumption decreases. For example, suppose the wireless LAN has the speed of 2Mbps, and one 512kbps ADSL is used to access the Internet. Then, the power consumption of original method is 1.2 times of the proposed one when equals to 0.8.
INDIRECT HTTP: AN ENERGY EFFICIENT EXTENSION OF HYPERTEXT TRANSFER PROTOCOL FOR WEB BROWSING
5.
185
CONCLUSIONS
Wireless Internet is expected to be the future trend of mobile computing and personal communications. Besides Wireless LAN technology supporting sufficient bandwidth of air interface, the power management is also an important issue for personal communications. The technology of TCP/IP and HTTP plays an essential role in the wireless Internet service. This chapter demonstrates an energy efficient extension of HTTP/1.1. Performance of the proposed extension is analyzed in terms of the factor of power reduction. Based on a similar discussion, this energy efficient extension also works on an energy-limited portable device with a wired network interface. Comparing to the original HTTP/1.1, the power saving of the protocol extension is proportional to the ratio of the transmission time of wide area network (WAN) to the transmission time on the air for each web object, which means the better performance can be achieved when the speed of wireless local area network (wireless LAN) is much faster than the speed of WAN. The power saving of proposed extension also depends on the nonvaried fraction of power consuming. For example, a different media access control layer may affect the power reduction of this extension. This chapter demonstrates a referable process to propose and analyze an energy efficient protocol of application layer, which can promote the technology of power-aware communication, computing, and networking.
This page intentionally left blank
References
[AB]
Acoustic Ballistic Module data sheet, SenTech Inc. J. R. Agre, L. P. Clare, G. J. Pottie, and N. P. Romanov, “Development platform for self-organizing wireless sensor networks,” Proceedings, SPIE The International Society for Optical Engineering, Vol. 3713, pp. 257-68, April 1999. C. R. Anderson, P. Domingos, and D. S. Weld. "Personalizing web sites for mobile devices," Proceedings, Conference on the World Wide Web (WWW10), May 2001.
[AE]
Advanced Encryption Standard. http://csrc.nist.gov/encryption/aes. S. Acharya, M. J. Franklin, and S. B. Zdonik, “Prefetching from broadcast disks,” International Conference on Data Engineering (ICDE), pp. 276285, February 1996. S. Appadwedula, M. Goel, N. R. Shanbhag, D. L. Jones, and K. Ramchandran, “Total system energy minimization for wireless image transmission,” Journal of VLSI Signal Processing Systems, Vol. 27(1/2), pp. 99-117, February 2001.
[AH]
Advanced Hardware Architectures. http://www.aha.com
[AI]
Adaptive Info: Personalizing the wireless Web. http://www.adaptiveinfo.com. S. Agarwal, S. V. Krishnamurthy, R. H. Katz, and S. K. Dao, “Distributed power control in ad hoc wireless networks,” IEEE International Symposium on Personal Indoor Mobile Radio Communications (PIMRC), San Diego, CA, September 2001.
[AM]
Annapolis Micro Systems Wildcard FPGA board.
188
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION http://www.annapmicro.com/products.html
[AM67]
G. Amdahl, “Validity of the single-processor approach to achieving large-scale computational capabilities,” AFIPS Conference Proceedings, AFIPS Press, Vol. 30, pp. 483, 1967. A. A. Abidi, G. J. Pottie, and W.J. Kaiser, “Power-conscious design of wireless circuits and systems,” Proceedings, IEEE, Vol.88, No. 10, pp. 152845, October 2000. J. B. Andresen, T. S. Rappaport, and S. Yoshida, “Propagation measurements and models for wireless communications channels,” IEEE Communications Magazine, Vol. 33, No. 1, January 1995. A. V. Aho, R. Sethi, and J. D. Ullman, “Compilers: Principles, Techniques and Tools,” Addison-Wesley, 1986.
[AS96]
E. de Angel and E. E. Swartzlander, “Survey of low power techniques for VLSI design,” Conference on Innovative Systems in Silicon, pp. 159-69, October 1996. W. Adjie-Winoto, E. Schwartz, H. Balakrishnan, and J. Lilley. "The design and implementation of an intentional naming system," Operating Systems Review, Vol. 33, No. 5, pp. 186-201, December 1999.
[BE90]
T.C. Bell, “Text compression,” Prentice Hall, Englewood Cliffs, NJ, 1990.
[BF92]
T. Berman and J. Freedman, “Non-interleaved Reed-Solomon coding over a bursty channel,” Milcomm, pp. 580-583, 1992. F. Balarin, P. Giusto, A. Jurecska, C. Passerone, E. Sentovich, B. Tabbara, M. Chiodo, H. Hsieh, L. Lavagno, A. Sangiovanni-Vincentelli, and K. Suzuki, “Hardware-software co-design of embedded systems: The POLIS approach,” Kluwer Academic Publishers, 1997. A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, “Message multicasting in heterogeneous networks,” ACM Symposium on Theory of Computing (STOC), pp. 448-453, 1998. M. Bhardwaj, T. Garnett, and A. P. Chandrakasan, “Upper bounds on the lifetime of sensor networks,” Proceedings, IEEE International Conference on Communication (ICC), June 2001.
[BJ98]
A. Buczak and V. Jamalabad, “Self-organization of a heterogeneous sensor network by genetic algorithms, intelligent engineering systems through artificial neural networks,” ASME Press, New York, C.H. Dagli, et al. (eds.), Vol. 8, pp. 259-264, 1998.
References
189 R. Burne, I. Kadar, J. Whitson and E. Eadan, “A self-organizing, cooperative UGS network for target tracking,” Proceedings, SPIE Conference on Unattended Ground Sensor Technologies and Applications, Orlando, Florida, April 2000.
[BM97]
L. Benini and G. de Micheli, “Dynamic power management: design techniques and CAD tools,” Kluwer Academic Publishers, 1997.
[BM99]
L. Benini and G. D. Micheli, “System-level power optimization: Techniques and tools,” International Symposium on Low-Power Electronics and Design (ISLPED), August 1999.
[BO00]
G. Barish and K. Obraczke, “World Wide Web caching: trends and techniques,” IEEE Communications Magazine, Vol. 38, No. 5, pp. 178-184, May 2000. A. Bakshi, V, K. Prasanna, A. Ledeczi, A. Agrawal, J. Davis, B. Eames, S. Mohanty, V. Mathur, S. Neema, G. Nordstrom, C. Raghavendra, and M. Singh, “MILAN: A model based integrated simulation framework for design of embedded systems,” ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES), June 2001.
[BP02]
A. Bakshi, and V. K. Prasanna, “Power-aware embedded system design using the MILAN framework,” IEEE Workshop on Integrated Management of Power Aware Communications, Computing and Networking (IMPACCT), May 2002.
[BR86]
R. E. Bryant, “Graph-based algorithms for Boolean function manipulation,” IEEE Transactions on Computers, Vol. 35, No. 8, August 1986.
[BS]
Bluetooth Special Interest Group. http://www.bluetooth.com/technology/ K. Birman, A. Schiper, and P. Stephenson, “Lightweight causal and atomic group multicast,” ACM Transactions on Computer Systems, Vol. 9, No. 3, pp. 272-314, August 1991. D. Brooks, V. Tiwari, and M. Martonosi, “Wattch: A framework for architectural-level power analysis and optimizations,” International Symposium on Computer Architecture (ISCA), June 2000.
[BW]
Bellsouth wireless data network services. http://www.bellsouthwd.com/solutions/personal_solutions.html
[BW00]
G. Borriello and R. Want, “Embedded computation meets the World Wide Web,” ACM Communications, Vol. 43, No. 5, pp. 59-66, May 2000.
[CA98]
W. E. Combs and J. E. Andrews, “Combinatorial rule explosion eliminated by a fuzzy rule configuration,” IEEE Transactions on Fuzzy Systems, Vol. 6, No. l, pp. 1-11, February 1998.
190
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
[CA98]
W. E. Combs and J. E. Andrews, “Combinatorial rule explosion eliminated by a fuzzy rule configuration,” IEEE Transactions on Fuzzy Systems, Vol. 6, No. l, pp. 1-11, February 1998.
[CA99]
W. J. Canover, “Practical nonparametric statistics,” 3rd edition. New York: Wiley, 1999. G. Coulouris, J. Dollimore, and T. Kindberg, “Distributed systems: concepts and design”, Addison-Wesley, Reading, Massachusetts, 1988.
[CE99]
C. S. Chandra and C. S. Ellis, “JPEG Compress metric as a quality aware image transcoding,” Proceedings, Symposium on Internet Technologies and Systems, USENIX, October 1999. C. S. Chandra, A. Gehani, C. S. Ellis, and A. Vahdat, “Transcoding characteristics of web images,” Proceedings, Multimedia Computing and Networking (MMCN), January 2001.
[CH99]
S. Chen, “Routing support for providing guaranteed end-to-end Quality of Service,” Ph.D. Thesis Dissertation, University of Illinois at UrbanaChampaign, 1999.
[CH01]
P. C. Cheng, “An architecture for the Internet Key Exchange Protocol,” IBM Systems Journal, Vol. 40, No. 3, pp. 721-746, 2001. http://www.research.ibm.com/journal/si/403/cheng.pdf S. Choi, J. Jang, S. Mohanty, and V. K. Prasanna, “Domain-specific modelling for rapid system-wide energy estimation of reconfigurable architectures,” Proceedings, International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA), June 2002. T. L. Cignetti, K. Komarov, and C. S. Ellis, “Energy estimation tools for the Palm”, Proceedings, ACM MwWiM: Modelling, Analysis and Simulation of Wireless and Mobile Systems, pp 96-103, 2000. T. H. Cormen, C. E. Leiserson, and R. L. Rivest, “Introduction to Algorithms,” MIT Press, 1990.
[CL00]
D. Clark, “Encryption advances to meet Internet challenges,” IEEE Computer online magazine, December 2000. http://www.computer.org/computer/articles/August/technews800.htm
[CO]
CoWare N2C. http://www.coware.com
[CT99]
J.H. Chang and L. Tassiulas, “Routing for maximum system lifetime in wireless ad-hoc networks,” Allerton Conference on Communication, Control, and Computing, September 1999.
References
191
[DAa]
DARPA ITO, Power Aware Computing/Communication Program. http://www.darpa. mil/ito/research/pacc/index. html
[DAb]
DAQ-1602 PCI data acquisition card. http://www.quatech.com/shopquatech/products/prod419.asp
[DC]
DEFLATE Compressed Data Format Specification version 1.3. http://www.kblabs.com/lab/lib/rfcs/1900/rfcl951.txt.html
[DC90]
S. Deering and D. Cheriton, “Multicast routing in datagram inter-networks and extended LANs,” ACM Transactions on Computer Systems, Vol. 8, No. 2, pp. 85-110, May 1990.
[DE]
Data Encryption Standard. http://csrc.nist.gov/encryption
[DH76]
W. Diffie, M. E. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, Vol. IT-22, No. 6, pp. 644-654, November 1976.
[DI59]
E. W. Dijkstra, “A note on two problems in connection with graphs,” Numeriche Mathematik, Vol. 1, pp. 269-271, 1959. W. Diffie, P. V. Oorschot, M. Wiener, “Authentication and authenticated key exchange,” Design, Codes and Cryptography, Vol. 2, pp. 107-125, March 1992.
[DR]
J. Daemen and V. Rijmen, “Rijndael for AES,” AES Candidate Conference. http://www.esat.kuleuven.ac.be/~rijmen/rijndael/rijndaeldocV2.zip
[DS86]
R. B. D'Agostino and M. A. Stephens, "Goodness-of-fit Techniques," New York: M. Dekker, 1986. A. Dan, D. Sitaram, and P. Shahabuddin, “Scheduling policies for an ondemand video server with batching,”ACM Multimedia, pp. 391-398, October 1994. M.J. Dong, K.G. Yung, and W.J. Kaiser, “Low power signal processing architectures for network microsensors,” ACM International Symposium on Low Power Electronics and Design (ISLPED), pp. 173-177, August 1997 J.P. Ebert, B. Bums, and A. Wolisz, “A trace-based approach for determining the energy consumption of a WLAN network interface,” European Wireless, February 2002. D. Estrin, R. Govindan, and J. Heidemann. "Embedding the Internet: Introduction," ACM Communications, Vol. 43, No. 5, pp.38-42, May 2000.
192
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION D. Estrin, R. Govindan, and J. Heidemann. "Embedding the Internet: Introduction," ACM Communications, Vol. 43, No. 5, pp.38-42, May 2000.
[EK72]
J. Edmonds and R. M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems,” Journal of the ACM, Vol. 19, No. 2, pp. 248-264, April 1972.
[ES]
ESD Project 25403 “SOFLOPO” Public Deliverables. http://www.vlsi.ee.upatras.gr/soflopo/ J. Ebert, B. Stremmel, E. Wiederhold, A. Wolisz, “An energy-efficient power control approach for WLANs,” Journal of Communications and Networks, Vol. 2, pp. 197-206, September 2000. E. Erkip, Y. Wang, D. Goodman, Y. Wu, and X. Lu, “Energy efficient coding and transmission,” Proceedings, IEEE Vehicular Technology Conference, May 2001.
[FF62]
L.R. Ford and D.R. Fulkerson, “Flow in Networks,” Princeton University Press, 1962. K. Farkas, J. Flinn, G. Back, D. Grunwald, and J. Anderson, “Quantifying the energy consumption of a pocket computer and a Java virtual machine,” Proceedings, ACM SIGMETRICS, June 2000. R. T. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, and T. Berners-Lee, “Hypertext Transfer Protocol - HTTP/1.1,” IETF RFC 2616, June 1999.
[FN01]
L. M. Feeney and M. Nilsson, “Investigating the energy consumption of a wireless network interface in an ad hoc networking environment,” IEEE International Conference on Computer Communication (INFOCOM), April 2001. M. Goel, S. Appadwedula, N. R. Shambhag, K. Ramchandran, and D. L. Jones, “A low-power multimedia communication system for indoor wireless applications,” IEEE Multimedia Signal Processing Workshop, pp. 473-482, 1999.
[GC01]
J. Goodman and A. P. Chandrakasan, “An energy-efficient reconfigurable public-key cryptography processor,” IEEE Journal of Solid State Circuits, Vol. 36, No. 11, November 2001.
[GG92]
A. Gersho and R. M. Gray, “Vector quantization and signal compression,” Kluwer Academic Publishers, Norwell, Massachusetts, 1992.
References
193
[GI60]
E. N. Gilbert, “Capacity of a burst noise channel,” Bell System Technology Journal, Vol. 39, pp. 1253-1266, September 1960.
[GJ79]
M.R. Garey and D. S. Johnson. “Computers and intractability: a guide to the theory of NP-completeness,” W.H. Freeman and Company, New York, 1979.
[QK99]
F. Gruian and K. Kuchcinski, “Low-energy directed architecture selection and task scheduling,” Euromicro Conference, September 1999.
[GM]
Generic Modeling Environment. http://www.isis.vanderbilt.edu/. S. Guha, N. Mishra, R. Motwani, and L. O'Callaghan, “Clustering data streams,” IEEE Symposium on Foundations of Computer Science, pp. 359-66, November 2000. S. Guha, A. Meyerson, and K. Munagala, “Hierarchical placement and network design problems,” IEEE Symposium on Foundations of Computer Science, pp. 603-612, 2000. T. Givargis, F. Vahid, and J. Henkel, “A hybrid approach for core-based system-level power modelling,” Proceedings, Asia and South Pacific Design Automation Conference (ASP-DAC), January 2000.
[HC98]
D. Harkins and D. Carrel, “The Internet Key Exchange (IKE),” Request for Comment, November 1998. http://www.ietf.org/rfc/rfc2409.txt W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocols for wireless microsensor networks,” Hawaii International Conference on System Sciences (HICSS), January 2000. C. Heegard, J. T. Coffey, S. Gummadi, P. A. Murphy, R. Provencio, E. J. Rossin, S. Schrum, and M. B. Shoemake, “High-performance wireless Ethernet,” IEEE Communications Magazine, Vol. 39, No.11, pp. 64-73, November 2001. I. W. Habib, R. Morris, H. Saito, and B. Pehrson, eds., Special Issue on Computational and Artificial Intelligence in High Speed Networks, IEEE Journal on. Selected Areas in Communications, Vol. 15, No. 2, Feb 1997.
[HP96]
J. L. Hennesey and D. A. Patterson, “Computer Architecture: A Quantitative Approach,” Morgan-Kauffman Publishers, 1996.
[HS00a]
P. J. M. Havinga and G. J. M. Smit, “Design techniques for low power systems,” Journal of Systems Architecture, Vol. 46, No. 1, 2000.
[HS00b]
P. Havinga and G. Smit, “Energy-efficient TDMA medium access control protocol scheduling,” Proceedings Asian International Mobile Computing Conference (AMOC), November 2000.
194
[HS00b]
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION P. Havinga and G. Smit, “Energy-efficient TDMA medium access control protocol scheduling,” Proceedings Asian International Mobile Computing Conference (AMOC), November 2000. P. Havinga, G. Smit, M. Bos, “Energy efficient adaptive wireless network design,” Symposium on Computers and Communications (ISCC), Antibes, France, July 2000. W. Heinzelman, A. Sinha, A. Wang, and A. Chandrakasan, “Energy-scalable algorithms and protocols for wireless microsensor networks,” Proceedings, International Conference on Acoustics, Speech, and Signal Processing (ICASSP), June 2000. C. Intanagonwiwat, D. Estrin, R. Govindan, and J. Heidemann, “Impact of network density on data aggregation in wireless sensor networks,” International Conference on Distributed Computing Systems (ICDCS), pp. 1 16, November 2001.
[IT]
ITU-T Recommendation communication,” 1998.
[JA96]
D. Jaggar, “Advanced RISC Machines Architectural Reference Manual,” Prentice-Hall, 1996.
H.263,
“Video
coding
for
low
bit
rate
Z. Jiang, L. F. Chang, B. J. J. Kim, and K. K. Leung, “Incorporating proxy services into wide area cellular IP networks,” Wireless Communications and Mobile Computing, Jon Wiley & Sons, Vol. 1, No. 3, pp. 299-312, July 2001. C. E. Jones, K. M. Sivalingam, P. Agrawal, and J. C. Chen, “A Survey of energy efficient network protocols for wireless networks,” Wireless Networks, Kluwer Academic Publishers, Vol. 7, No.4, July 2001.
[JT]
JouleTrack: A web based software energy profiling tool. http://dry-martini.mit.edu/JouleTrack/arm/ R. Kravets, K. Calvert, K. Schwan, “Payoff adaptation of communication for distributed interactive applications,” Journal on High Speed Networking: Special Issue on Multimedia Communications, 1998. D. Kang, S. Crago, and J. Suh, “Power-aware design synthesis techniques for distributed real-time systems,” Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES), June 2001. B. Kienhuis, E. Depettere, P. van der Wolf, and K. Vissers, “A methodology to design programmable embedded systems,” LNCS series of Springer-Verlag(c), Vol. 2268, SAMOS: Systems, Architectures, Modeling, and Simulation, editors E. F. Deprettere, J. Teich, and S. Vassiliadis, November 2001.
References
195
[KE02]
S. Kent, “IP Encapsulating Security Payload,” Internet draft, March 2002. http://www. ietf. org/internet-drafts/draft-ietf-ipsec-esp-v3-02.txt
[KI98]
H. A. Kiehne, “Battery technology handbook,” Mercel Dekker, 1998.
[KI00]
B. Kienhuis, “Y-chart methodology and models of computation and architecture,” IEEE/ACM Design Automation Conference (DAC) tutorial on Embedded System Design, June 2000.
[KK99]
R. Kravets and P. Krishnan, “Power management techniques for mobile communication,” Proceedings, ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), August 1999.
[KM02]
R. Karri and P. Mishra, “Optimizing the energy consumed by secure wireless session - Wireless Transport Layer Security case study,” ACM/Kluwer Journal of Mobile Networks and Applications (MONET), 2002. F. Koushanfar, M. Potkonjak, and A. Sangiovanni-Vincentelli, “Fault tolerance in wireless ad-hoc sensor networks,” IEEE Sensors, June 2002.
[KR96]
H. Krawczyk, “SKEME: A versatile secure key exchange mechanism for internet,” Proceedings, Internet Society Symposium on network and Distributed Systems Security, February, 1996. K. Lahiri, A. Raghunathan, S. Dey, and D. Panigrahi, “Battery-driven system design: A new frontier in low power design,” (Embedded Tutorial), Proceedings, ASPDAC/ VLSI Design Conference, pp. 261-267, January 2002. Q. Li, J. Aslam, and D. Rus, “Online power-aware routing in wireless ad-hoc networks,” Proceedings, ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Rome, Italy, pp. 97-107, 2001. A. Ledeczi, A. Bakay, M. Maroti, P. Volgyesi, G. Nordstrom, J. Sprinkle, and G. Karsai, “Composing domain-specific design environments,” IEEE Computer, pp. 44-51, November 2001. P. Lettieri, C. Fragouli, M. B. Srivastava, “Low power error control for wireless links,” Proceedings, ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Budapest, Hungary, pp. 139-150, August 1997. A. R. Lebeck, X. Fan, H. Zeng, and C. S. Ellis, “Power aware page allocation,” Proceedings, International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), November 2000.
[LI60]
J. C. R. Licklider, “Man-computer symbiosis,” IEEE Transactions on Human Factors in Electronics, Vol. 1, pp. 4-11, March 1960.
196
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION
[LI60]
J. C. R. Licklider, “Man-computer symbiosis,” IEEE Transactions on Human Factors in Electronics, Vol. 1, pp. 4-11, March 1960.
[LI00]
Yi-Qun Li, “An innovative passive solid-state magnetic sensor,” Sensors Magazine, Vol. 17, No. 10, October 2000. http://www. sensorsmag. com/articles/1000/52/main. shtml Q. Liang, N. N. Karnik, and J. M. Mendel, “Connection admission control in ATM network using survey-based type-2 fuzzy logic systems,” IEEE Transactions on Systems, Man, and Cybernetics, Part C, Vol. 30, No. 3, pp. 529-539, August 2000.
[LM87]
E. A. Lee and D. G. Messerschmitt, “Static scheduling of synchronous data flow programs for digital signal processing,” IEEE Transactions on Computers, pp. 24-35, Vol. 36, No. 1, January 1987. M. Lajolo, A. Raghunathan, and S. Dey, L. Lavagno, “Efficient power coestimation techniques for system-on-chip designs,” Proceedings, IEEE Design and Test Europe (DATE), March 2000.
[LR02]
S. Lindsey and C. S. Raghavendra, “PEGASIS: power-efficient gathering in sensor information systems,” Proceedings, IEEE Aerospace Conference, March 2002. P. Lettieri, C. Schurgers, and M. Srivastava, “Adaptive link layer strategies for energy efficient wireless networking,” Wireless Networks, Vol. 5, No 5, pp. 339-55, 1999. S. Lindsey, K. Sivalingam, and C. S. Raghavendra, “Power optimization in routing protocols for wireless and mobile networks,” Handbook of Wireless Networks and Mobile Computing, Ed. Ivan Stojmenovic, John Wiley and Sons, 2001. M. Tien-Chien Lee, V. Tiwari, S. Malik, and M. Fujita, “Power analysis and minimization techniques for embedded DSP software,” IEEE Transanctions on VLSI Systems, Vol. 5, No. 5, pp. 123-135, March 1997.
[LT98]
T. Lan and A. H. Tewfik, “Power optimized mode selection for H.263 video coding and wireless communications,” International Conference on Image Processing, Vol. 2, pp. 113-117, 1998.
[LW]
Lucent WaveLAN (ORINOCO). http://www.wavelan.com S. Mohanty, S. Choi, J. Jang, and V. K. Prasanna, “A model-based methodology for application specific energy efficient data path design using FPGAs,” Proceedings, IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP), July 2002.
References
197
[ME01]
J. M. Mendel, “Uncertain Rule-Based Fuzzy Logic Systems,” Prentice-Hall, Upper Saddle River, NJ, 2001.
[MI]
MILAN project. http://milan.usc.edu. S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak, “Exposure in wireless ad-hoc sensor networks,” International Conference on Mobile Computing and Networking (MOBICOM), pp. 139-150, July 2001. S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage problems in wireless ad-hoc sensor networks,” IEEE Conference on Computer Communications (INFOCOM), Vol. 3, pp. 1380-1387, April 2001. R. Marculescu, A. Nandi, L. Lavagno, and A. Sangiovanni-Vincentelli, “System-level power/performance analysis of portable multimedia systems communicating over wireless channels,” Proceedings, IEEE/ACM International Conference on Computer Aided Design (ICCAD), November 2001.
[MO]
Model-based synthesis of generators for embedded http://www.isis.vanderbilt.edu/Projects/mobies/default.html
[MO59]
E. F. Moore, “The shortest path through a maze,” International Symposium on Theory of Switching, Harvard University Press, pp. 285-292, 1959
systems.
S. Mohanty, V. K. Prasanna, S. Neema, and J. Davis, “Rapid design space exploration of heterogeneous embedded systems using symbolic search and multi-granular simulation,” Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES), June 2002. S. Meguerdichian, S. Slijepcevic, V. Karayan, and M. Potkonjak, “Localized algorithms in wireless ad-hoc networks: location discovery and sensor exposure,” ACM Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 106-116, October 2001.
[MW]
Mobitex Wireless Packet Protocol. http://www.mobitex.org
[NS]
Network Simulator - ns-2. http://www.isi.edu/nsnam/ns
[OH00]
S. Ohr, “Batteries take on wireless challenge,” EE Times, October 6 2000.
[OR98]
H. Orman, “OAKLEY key determination protocol,” Request for Comment, November 1998. http://www.ietf.org/rfc/rfc2412.txt
[PA]
PACMAN project. http://pacman.usc.edu.
198
[PA]
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION PACMAN project. http://pacman.usc.edu. T. Pering, T. Burd, and R. Broderson, “Dynamic voltage scaling and the design of a low-power microprocessor system,” International Symposium on Computer Architecture (ISCA), June 1998. A. D. Pimentel, L. O. Hertzberger, P. Lieverse, P. van der Wolf, and E. F. Deprettere, “Exploring embedded-systems architectures with Artemis,” IEEE Computer, pp. 57-63, Vol. 34, No. 11, November 2001.
[PK00]
G. J. Pottie and W. J. Kaiser "Wireless integrated network sensors," Communications of the ACM, Vol. 43, No. 5, pp. 51-58, May 2000.
[PO]
Palm OS 3.0 software development kit. http://www.palmos.com/dev/tech/tools/sdk30.html
[PO95]
R. Powers, “Batteries for low power electronics,” Proceedings, IEEE, Vol. 83, pp. 687-93, April 1995.
[PP91]
S. Prakash and A. Parker, “Synthesis of application-specific multiprocessor architectures,” IEEE/ACM Design Automation Conference (DAC), pp. 8-13, June 1991.
[PR01a]
J. G. Proakis, “Digital Communications”, Mc Graw Hill, New York, NY, 2001. D. Panigrahi, A. Raghunathan, G. Lakshminarayana, and S. Dey, “Energy modelling for wireless internet access,” IEEE International Conference on Third Generation Wireless and Beyond, May 2001. N. R. Potlapally, S. Ravi, A. Raghunathan, “Optimizing public-key algorithms for efficient security processing on wireless handsets,” IEEE International Conference on Communication (ICC), April 2002.
[PW]
Palm Web Clipping. http://www.palm.com/products/palmvii/webclipping.html
[PW99]
M. Pedram and Q. Wu, “Design considerations for battery-powered electronics,” Proceedings, IEEE/ACM Design Automation Conference (DAC), 1999.
[RA]
T. S. Rappaport, “Wireless Communications: Principles and Practices,” Prentice Hall Communications Engineering and Emerging Technologies Series.
[RA00a]
J. M. Rabaey, “PicoRadio supports ad-hoc ultra-low power wireless networking,” Computer, Vol. 33, No. 7, pp. 42-48, July 2000.
References
199
[RB96]
J. M. Rulnick and N. Bambos, “Mobile power management for maximum battery life in wireless communications network,” IEEE International Conference on Computer Communications (INFOCOM), CA, USA, Vol. 2, pp. 443-450, March 1996.
[RB97]
J. M. Rulnick and N. Bambos, “Mobile power management for wireless communication networks,” Wireless Networks, Vol. 3, No. 1, pp.3-14, 1997.
[RM99]
V. Rodoplu and T. H. Meng, “Minimum energy mobile wireless networks,” IEEE Journal on Selected Areas in Communication, Vol. 17, No. 8, pp. 13331344, August 1999. J. M. Rabaey, M. Potkonjak, F. Koushanfar, S. Li, and T. Tuan, “Challenges and opportunities in broadband and wireless communication designs,” IEEE/ACM International Conference on Computer Aided Design (ICCAD), pp. 76-82, November 2000. C. Rohl, H. Woesner, A. Wolisz, “A short look on power saving mechanisms in the wireless LAN standard draft IEEE 802.11,” Advances in Wireless Communications, Kluwer Academic Publishers, 1998.
[SA]
SA-1100 Models, the UAMPS Project. http://www.mtl.mit.edu/research/icsystems/uamps. T. Simunic, L. Benini, and G. De Micheli, “Energy efficient design of batterypowered embedded systems,” Special Issue of IEEE Transactions on VLSI, May 2001.
[SC00]
A. Sinha and A. Chandrakasan, “Energy aware software,” Proceedings, International Conference on VLSI Design, pp. 50-55, Calcutta, India. January 2000.
[SC01]
A. Sinha and A. P. Chandrakasan, “JouleTrack - A web-based tool for software energy profiling,” Proceedings, IEEE/ACM Design Automation Conference (DAC), June 2001.
[SE]
Synopsys Eagle, http://www.synopsys.com/
[SE00]
J. A. Senn, “The emergence of M-Commerce,” IEEE Computer, pp. 148-150, December 2000. K. Stuhlmüller, N. Färber, M. Link and B. Girod, “Analysis of video transmission over lossy channels,” IEEE Journal on Selected Areas in Communications, Vol. 18 (6), pp. 1012-1032, June 2000. M. Stemm, P. Gauthier, D. Harada, and R. Katz, “Reducing power consumption of network interfaces in hand-held devices,” Proceedings, International Workshop on Mobile Multimedia Communications, September 1996.
200
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION M. Stemm, P. Gauthier, D. Harada, and R. Katz, “Reducing power consumption of network interfaces in hand-held devices,” Proceedings, International Workshop on Mobile Multimedia Communications, September 1996.
[SH]
Secure Hash Standard SHA-256. http://csrc.nist.gov/encryption/tkhash.html A. Savvides, C. C. Han, and M. B. Srivastava, “Dynamic fine-grained localization in ad-hoc wireless sensor networks,” International Conference on Mobile Computing and Networking (MOBICOM), pp. 166-179, July 2001. A. Safwat, H. Hassanein, and H. Mouftah, “Power-aware fair infrastructure formation for wireless mobile ad hoc communications,” Proceedings, IEEE GLOBECOM 2001, pp. 2832-2836, San Antonio, TX, September 2001.
[SK97]
J. Sztipanovits and G. Karsai, “Model-integrated computing,” IEEE Computer, April 1997. G. Sinevriotis, A. Leventis, D. Anastasiadou, C. Stavroulopoulos, T. Papadopoulos, T. Antonakopoulos, and T. Stouraitis, “SOFLOPO: Towards systematic software exploitation for low-power designs,” Proceedings, International Workshop of the European Low Power Initiative for Electronic System Design (ESDLPD), pp. 95-110, 2000. J. R. Smith, R. Mohan and C.S. Li, “Content-based transcoding of images in the internet,” Proceedings, International Conference on Image Processing, 1998.
[SMOO]
G. S. Sukhatme and M. J. Mataric, “Embedding robots into the internet,” Communications of the ACM, Vol. 43, No. 5, pp. 67-73, May 2000.
[SO]
“Solaris™ 2.x - Tuning your http://www.sean.de/Solaris/soltune.html
[SP]
Symbol PPT2800 series portable pen terminal.
[SP01]
S. Slijepcevic and M. Potkonjak, “Power efficient organization of wireless sensor networks,” IEEE International Conference on Communications (ICC), Vol. 2, pp. 472-476, June 2001.
[SP02]
M. Singh and V. K. Prasanna, “System level energy trade-offs for collaborative computation in wireless networks,” IEEE Workshop on Integrated Management of Power Aware Communications, Computing and Networking (IMPACCT), May 2002.
[SR95]
N. Srour and J. Robertson, “Remote netted acoustic detection system: Final report,” ARL Technical Report, ARL-TR-706, April 1995.
TCP/IP
stack
and
more,”
References
201
[SR98b]
S. Singh, C. S. Raghavendra, “Power efficient MAC protocol for multihop radio networks,” Proceedings, IEEE International Symposium on Personal, Indoor, Mobile Radio Communication (PIMRC), Boston, USA, Vol. 1, pp. 153-157, September 1998.
[SSa]
SimpleScalar tool set. http://www.cs.wisc.edu/~mscalar
[SSb]
Symbol Spectrum24® High Rate LA 41X1 PC Card.
[SS97]
K. M. Sivalingam, M. Srivastava, P. Agrawal, and J. C. Chen, "Low-power access protocols based on scheduling for wireless and mobile ATM networks,” Proceedings, IEEE Universal Personal Communications, pp. 420-33, October 1997.
[SS99]
G. Sinevriotis and T. Stouraitis, “Power Analysis of the ARM 7 Embedded Microprocessor,” Proceedings, International Workshop-Power and Timing Modeling, Optimization and Simulation (PATMOS), pp261-270, 1999.
[ST87]
T. Srikanth and S. Toueg, “Optimal clock synchronization,” Journal of the ACM, Vol. 34, No. 3, pp. 626-645, July 1987. S. Singh, M. Woo, and C. S. Raghavendra, “Power-aware routing in mobile ad hoc networks,” Proceedings, ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Dallas, TX, pp. 181-190, 1998.
[TA95]
A. Tanenbaum, “Distributed operating systems,” Prentice Hall, Englewood Cliffs, N.J., 1995.
[TB96]
D. L. Tennenhouse and V. G. Bose, “The SpectrumWare approach to wireless signal processing,” Wireless Networks, Vol. 2, No. 1, pp. 1-12, 1996.
[TC]
Tutorial on convolutional coding with Viterbi decoding, http://home.netcom.com/~chip.f/viterbi/simrslts.html
[TE00]
D. Tennenhouse, "Proactive computing," Communications of the ACM, Vol. 43, No. 5, pp. 43-50, May 2000.
[TI]
Tektronix Inc. http://www.tektronix.com
[TL98]
V. Tiwari and M. Tien-Chien Lee, “Power analysis of a 32-bit embedded microcontroller,” VLSI Design Journal, Vol. 7, No. 3, 1998 V. Tiwari, S. Malik, and A. Wolfe, “Power analysis of embedded software: A first step towards software power minimization,” IEEE Transanctions on VLSI Systems, Vol. 2, No. 4, pp. 437-445, December 1994. V. Tiwari, S. Malik, and A. Wolfe, “Instruction level power analysis and optimization of software,” Journal of VLSI Signal Processing, 1-18, Kluwer Academic Press, 1996.
202
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION V. Tiwari, S. Malik, and A. Wolfe, “Power analysis of embedded software: A first step towards software power minimization,” IEEE Transanctions on VLSI Systems, Vol. 2, No. 4, pp. 437-445, December 1994. V. Tiwari, S. Malik, and A. Wolfe, “Instruction level power analysis and optimization of software,” Journal of VLSI Signal Processing, 1-18, Kluwer Academic Press, 1996.
[TM99]
The Ministry of Education, Taiwan, R.O.C, “The TANet Traffic,” The Ministry of Education Computer Center Newsletter, No. 8807, pp. 83-114, July 1999.
[TO01]
C. K. Toh, “Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks,” IEEE Communications Magazine, Vol. 39, No. 6, pp. 138-147, July 2000. C. Tang, C. S. Raghavendra, and V. K. Prasanna, “An energy efficient distributed source coding scheme in wireless sensor networks,” Manuscript, Department of Electrical Engineering, USC, April 2002.
[US]
US Army Research Laboratory. http://www.arl.mil.
[WA]
WAP Forum. http://www.wapforum.org
[WA99]
J. Wang, “A survey of web caching schemes for the internet,” ACM Computer Communication Review, Vol. 29, No.5, pp. 36-46, October 1999.
[WB]
WebBot. http://www.webbot.org
[WC01]
A. Wang and A. Chandrakasan, “Energy efficient system partitioning for distributed wireless sensor networks,” IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), May 2001.
[WE92]
M. Weiser, “The computer for the 21st century,” Scientific American (International Edition), Vol. 265, n. 3, pp. 66-75, September 1991.
[WE93]
M. Weiser, “Some computer science issues in ubiquitous computing,” Communications of ACM, Vol. 36, No. 7, pp 75 – 84, July 1993. H. Woesner, J. P. Ebert, M. Schlager, A. Wolisz, “Power saving mechanisms in emerging standards for wireless LANs: The MAC-level perspective,” IEEE Personal Communication Systems, pp. 40-48, 1998.
[WK99]
J. B. Warmer and A. G. Kleppe, “The object constraint language: precise modelling with UML,” Addison Wesley Longman, Reading, Massachusetts, 1999.
References
203
[XL01]
Y. Xue and B. Li, “A location-aided power-aware routing protocol in mobile ad hoc networks,” Proceedings, IEEE GLOBECOM 2001, San Antonio, TX, pp. 2837-2841, Sept 2001.
[XS01]
Shugong Xu and Tarek Saadawi, “Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks,” IEEE Communications Magazine, June 2001. T. Yu, D. Chen, G. Pottie, and K. Yao, “Blind de-correlation and deconvolution algorithm for multiple-input multiple-output system,” The International Society for Optical Engineering, Vol. 3807, pp. 200-209, July 1999. K. Yao, R. E. Hudson, C. W. Reed, D. Chen, and F. Lorenzelli, “Blind beamforming on a randomly distributed sensor array system,” IEEE Journal on Selected Areas in Communications, Vol.16, No.8, pp. 1555-1567, October 1998. W. Ye, N. Vijaykrishnan, and M. Kandemir, M. J. Irwin, “The design and use of SimplePower: A cycle-accurate energy estimation tool,” Proceedings, IEEE/ACM Design Automation Conference (DAC), June 2000.
[YW95]
T.-Y. Yen and W. Wolf, “Communication synthesis for distributed embedded systems,” International Conference on Computer-Aided Design (ICCAD), pp. 288-294, October 1995. M. Younis, M. Youssef and K. Arisha, “Energy-aware routing in cluster-based sensor networks,” submitted. M. Youssef, M. Younis and K. Arisha, “A constrained shortest-path energyaware routing for wireless sensor networks,” Wireless Communication and Networking Conference (WCNC), Orlando, Florida, March 2002. http://www.sentech-acoustic.com/
[ZR97a]
M. Zorzi, R. R. Rao, “Error control and energy consumption in communications for nomadic computing,” IEEE Transactions on Information Theory, Vol. 46, pp. 279-289, March, 1997.
[ZR97b]
M. Zorzi, R. R. Rao, “Energy constrained error control for wireless channels,” IEEE Personal Communications, Vol. 4, pp. 27-33, December 1997.
This page intentionally left blank
Index
Advanced Encryption Standard 140 Amdahl’s Law 180 Authentication Header 141 Battery 70 Channel 10 AWGN channel 1 Compression 145 Computational complexity 77 Convoy effect 179 Data dissemination 74 Data Encryption Standard 140 Data Multicast 72 DEFLATE 145 Diffie-Hellman 136 Distortion 2 source distortion 2 Distributed systems 75 Downloading time speedup 180 Encapsulating Security Payload 141 Energy-Efficient 144 Factor of power reduction 181 Graph theoretic 71
H.263 2 Hypertext Transfer Protocol 175 Indirect HTTP 180 Internet Key Exchange 136 Internet Security Protocol 135 Keep-alive probe 179 Limitation of the factor of power reduction 181 Minimum Cover problem 77 Multi-Hop Wireless Network 72 Non-varied fraction of power consumption 180 Pipelining 177 Power consumption 11 source power 11 Power cosumption transmit power 14 Ratio of the mean transmission time of WAN to the mean transmission time on the air 183 RS coder 3
206
SYSTEM-LEVEL POWER OPTIMIZATION FOR WIRELESS MULTIMEDIA COMMUNICATION Steiner tree 72
SA Security Association Secure sessions 133 Security association 136 Session negotiation 136 SHA-256 140 Shortest path 83
Triple-DES 140 Web proxy 177
