Vijay Raghunathan
Abstract
As embedded systems are being networked, often wirelessly, an increasingly larger share of their total energy budget is due to the communication. This necessitates the development of power management techniques that address communication subsystems, such as radios, as opposed to computation subsystems, such as embedded processors, to which most of the research effort thus far has been devoted. In this paper, we present techniques for energy efficient packet scheduling and fair queuing in wireless communication systems. Our techniques are based on an extensive slack management approach that dynamically adapts the output rate of the system in accordance with the input packet arrival rate. We use a recently proposed radio power management technique, dynamic modulation scaling (DMS), as a control knob to enable energy-latency trade-offs during wireless packet transmission. We first analyze a single input stream scenario, and describe a rate adaptation technique that results in significantly lower energy consumption (reductions of up to 10 ×), while still bounding the resulting packet delays. By appropriately setting the various parameters of our algorithm, the system can be made to traverse the energy-latency-fidelity trade-off space. We extend our techniques to a multiple input stream scenario, and present E2WFQ, an energy efficient version of the weighted fair queuing (WFQ) algorithm for fair packet scheduling. Simulation results show that large energy savings can be obtained through the use of E2WFQ, with only a small, bounded increase in worst case packet latency. Further, our results demonstrate that E2WFQ does not adversely affect the throughput allocation (and hence, fairness) of WFQ.
- Bagrodia, R., Meyer, R., Takai, M., Chen, Y., Zeng, X., Martin, J., Park, B., and Song, H. 1998. PARSEC: A parallel simulation environment for complex systems. IEEE Computer 31, 10 (Oct), 77--85.]] Google Scholar
Digital Library
- Benini, L. and DeMicheli, G. 1997. Dynamic Power Management: Design Techniques and CAD Tools. Kluwer Academic Publishers, Norwell, MA.]] Google ScholarDigital Library
- Bennett, J. C. R. and Zhang, H. 1996. WF2Q: Worst-case fair weighted fair queueing. In Proceedings of the Conference on Computer Communications (INFOCOM). IEEE, New York, 120--128.]]Google Scholar
- Chandrakasan, A. P. and Brodersen, R. W. 1996. Low Power CMOS Digital Design. Kluwer Academic Publishers, Norwell, MA.]]Google Scholar
- Cho, K. and Samueli, H. 2000. A 8.75-MBaud single-chip digital QAM modulator with frequency-agility and beamforming diversity. In Proceedings of the Custom Integrated Circuits Conference (CICC). IEEE, New York, 27--30.]]Google Scholar
- Demers, A., Keshav, S., and Shenker, S. 1989. Analysis and simulation of a fair queueing algorthm. In Proceedings of the Annual Conference of the Special Interest Group on Data Communication (SIGCOMM). ACM, New York, 3--12.]] Google ScholarDigital Library
- Gamal, A. E., Nair, C., Prabhakar, B., Biyikoglu, E. U., and Zahedi, S. 2002. Energy-efficient scheduling of packet transmissions over wireless networks. In Proceedings of the Conference on Computer Communications (INFOCOM). IEEE, New York, 1773--1782.]]Google Scholar
- Govil, K., Chan, E., and Wasserman, H. 1995. Comparing algorithms for dynamic speed-setting of a low-power CPU. In Proceedings of the International Conference on Mobile Computing and Networking (MOBICOM). ACM, New York, 13--25.]] Google ScholarDigital Library
- Goyal, P., Vin, H. M., and Cheng, H. 1996. Start-time fair queuing: A scheduling algorithm for integrated services in packet switching networks. In Proceedings of the Annual Conference of the Special Interest Group on Data Communication (SIGCOMM). IEEE, New York, 157--168.]] Google ScholarDigital Library
- Gruian, F. 2001. Hard real-time scheduling for low energy using stochastic data and DVS processors. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED). ACM, New York, 46--51.]] Google ScholarDigital Library
- Hong, I., Potkonjak, M., and Srivastava, M. B. 1998. On-line scheduling of hard real-time tasks on variable voltage processors. In Proceedings of the International Conference on Computer Aided Design (ICCAD). IEEE, New York, 653--656.]] Google ScholarDigital Library
- Ishihara, T. and Yasuura, H. 1998. Voltage scheduling problem for dynamically variable voltage processors. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED). ACM, New York, 197--202.]] Google ScholarDigital Library
- ITA. The internet traffic archive, http://ita.ee.lbl.gov.]]Google Scholar
- Jensen, J. L. W. V. 1906. Sur les fonctions convexes et les inegalites entre les valeurs moyennes. Acta. Mathematica 30, 175--193.]]Google ScholarCross Ref
- Keshav, S. 1997. An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network. Addison-Wesley, Reading, MA.]] Google ScholarDigital Library
- Lin, P., Bensaou, B., Ding, Q. L., and Chua, K. C. 2000. A wireless fair scheduling algorithm for error-prone wireless channels. In Proceedings of the International Workshop on Wireless Mobile Multimedia (WoWMOM). ACM, New York, 11--20.]] Google ScholarDigital Library
- Lu, S., Bharghavan, V., and Srikant, R. 1997. Fair scheduling in wireless packet networks. In Proceedings of the Annual Conference of the Special Interest Group on Data Communication (SIGCOMM). IEEE, New York, 63--74.]] Google ScholarDigital Library
- Min, R. and Chandrakasan, A. P. 2002. A framework for energy scalable communication in high-density wireless networks. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED). ACM, New York, 36--41.]] Google ScholarDigital Library
- Parekh, A. K. and Gallager, R. G. 1993. A generalized processor sharing approach to flow control in integrated services networks: The single-node case. IEEE Transactions on Networking 1, 3 (June), 344--357.]] Google ScholarDigital Library
- Pering, T. A., Burd, T. D., and Brodersen, R. W. 1998. The simulation and evaluation of dynamic voltage scaling algorithms. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED). ACM, New York, 76--81.]] Google ScholarDigital Library
- Pillai, P. and Shin, K. G. 2001. Real-time dynamic voltage scaling for low power embedded operating systems. In Proceedings of the Symposium on Operating Systems Principles (SOSP). ACM, New York, 89--102.]] Google ScholarDigital Library
- Prabhakar, B., Biyikoglu, E. U., and Gamal, A. E. 2001. Energy-efficient transmission over a wireless link via lazy packet scheduling. In Proceedings of the Conference on Computer Communications (INFOCOM). IEEE, New York, 386--394.]]Google Scholar
- Proakis, J. G. 1989. Digital Communications. McGraw Hill, New York.]]Google Scholar
- Rabaey, J. and Pedram, M. 1996. Low Power Design Methodologies. Kluwer Academic Publishers, Norwell, MA.]]Google Scholar
- Raghunathan, A., Jha, N. K., and Dey, S. 1998. High-level Power Analysis and Optimization. Kluwer Academic Publishers, Norwell, MA.]] Google ScholarDigital Library
- Raghunathan, V., Ganeriwal, S., Schurgers, C., and Srivastava, M. B. 2002a. E2WFQ: An energy efficient fair scheduling policy for wireless systems. In Proceedings of the Internation Symposium on Low Power Electronics and Design (ISLPED). ACM, New York, 30--35.]] Google ScholarDigital Library
- Raghunathan, V., Schurgers, C., Park, S., and Srivastava, M. B. 2002b. Energy aware wireless microsensor networks. IEEE Signal Processing Magazine 19, 2 (Mar.), 40--50.]]Google ScholarCross Ref
- Raghunathan, V., Spanos, P., and Srivastava, M. B. 2001. Adaptive power-fidelity in energy-aware wireless systems. In Proceedings of the Real-Time Systems Symposium (RTSS). IEEE, New York, 106--115.]] Google ScholarDigital Library
- Ramanathan, P. and Agrawal, P. 1998. Adapting packet fair queueing algorithms to wireless networks. In Proceedings of the International Conference on Mobile Computing and Networking (MOBICOM). ACM, New York, 1--9.]] Google ScholarDigital Library
- Schurgers, C., Aberthorne, O., and Srivastava, M. B. 2001a. Modulation scaling for energy aware communication systems. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED). ACM, New York, 96--99.]] Google ScholarDigital Library
- Schurgers, C., Raghunathan, V., and Srivastava, M. B. 2001b. Modulation scaling for real-time energy-aware packet scheduling. In Proceedings of the Global Telecommunications Conference (GLOBECOM). IEEE, New York, 3653--3657.]]Google Scholar
- Shin, Y. and Choi, K. 1999. Power conscious fixed priority scheduling for hard real-time systems. In Proceedings of the Design Automation Conference (DAC). ACM, New York, 134--139.]] Google ScholarDigital Library
- Shreedhar, M. and Varghese, G. 1995. Efficient fair queueing using deficit round robin. In Proceedings of the Annual Conference of the Special Interest Group on Data Communication (SIGCOMM). IEEE, New York, 231--242.]] Google ScholarDigital Library
- Sivalingam, K. M., Srivastava, M., Agrawal, P., and Chen, J. C. 1997. Low power access protocols based on scheduling for wireless and mobile ATM networks. In Proceedings of the Universal Personal Communications Conference. IEEE, New York, 420--433.]]Google Scholar
- Wang, A. Y., Cho, S. H., Sodini, C. G., and Chandrakasan, A. P. 2001. Energy efficient modulation and MAC for asymmetric RF microsensor systems. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED). ACM, New York, 106--111.]] Google ScholarDigital Library
- Weiser, M., Welch, B., Demers, A., and Shenker, S. 1994. Scheduling for reduced CPU energy. In Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI). ACM, New York, 13--23.]] Google ScholarDigital Library
- WINS. WINS project, Rockwell Incorporated, http://wins.rsc.rockwell.com.]]Google Scholar
Index Terms
- Energy efficient wireless packet scheduling and fair queuing
Recommendations
E2WFQ: an energy efficient fair scheduling policy for wireless systems
ISLPED '02: Proceedings of the 2002 international symposium on Low power electronics and designAs embedded systems are being networked, often wirelessly, an increasingly larger share of their total energy budget is due to the communication. This necessitates the development of power management techniques that address communication subsystems, ...
Energy-efficient multi-polling scheme for wireless LANs
In the past few years, IEEE 802.11 wireless LANs (WLANs) has rapidly gained large popularity for broadband wireless access. With the growing of various applications, users are demanding features such as higher throughput while keeping respectable ...
Fair and Efficient Packet Scheduling in Wormhole Networks
IPDPS '00: Proceedings of the 14th International Symposium on Parallel and Distributed ProcessingMost switch architectures for parallel systems are designed to eliminate only the worst kinds of unfairness such as starvation scenarios in which packets belonging to one traffic flow may not make forward progress for an indefinite period. However, ...
Comments