A calculus approach to energy-efficient data transmission with quality-of-service constraints

ABSTRACT

Transmission rate adaptation in wireless devices provides a unique opportunity to trade off data service rate with energy consumption. In this paper, we study optimal rate control to minimize transmission energy expenditure subject to strict deadline or other quality-of-service (QoS) constraints. Specifically, the system consists of a wireless transmitter with controllable transmission rate and with strict QoS constraints on data transmission. The goal is to obtain a rate-control policy that minimizes the total transmission energy expenditure while ensuring that the QoS constraints are met. Using a novel formulation based on cumulative curves methodology, we obtain the optimal transmission policy and show that it has a simple and appealing graphical visualization. Utilizing the optimal "offline" results, we then develop an online transmission policy for an arbitrary stream of packet arrivals and deadline constraints, and show, via simulations, that it is significantly more energy-efficient than a simple head-of-line drain policy. Finally, we generalize the optimal policy results to the case of time-varying power-rate functions.

REFERENCES

• 1: A. K. Katsaggelos, Y. Eisenberg, F. Zhai, R. Berry, and T. Pappas, "Advances in efficient resource allocation for packet-based real-time video transmission," Proc. IEEE, vol. 93, no. 1, pp. 135-147, Jan. 2005.
• 2: A. Ephremides, "Energy concerns in wireless networks," IEEE Trans. Wireless Commun., vol. 9, no. 4, pp. 48-59, Aug. 2002.
• 3: A. Jalali, R. Padovani, and R. Pankaj, "Data throughput of CDMA-HDR a high efficiency high data rate personal communication wireless system," in Proc. IEEE Veh. Technol. Conf., 2000, vol. 3, pp. 1854-1858.
• 4: S. Nanda, K. Balachandran, and S. Kumar, "Adaptation techniques in wireless packet data services," IEEE Commun. Mag., vol. 38, no. 1, pp. 54-64, Jan. 2000.
• 5: Murtaza Abbasali Zafer , Eytan Modiano, Dynamic rate-control and scheduling algorithms for quality-of-service in wireless networks, Massachusetts Institute of Technology, Cambridge, MA, 2007
• 6: M. Zafer and E. Modiano, "A calculus approach to minimum energy transmission policies with quality of service guarantees," Proc. IEEE INFOCOM, vol. 1, pp. 548-559, Mar. 2005.
• 7: R. Berry and R. Gallager, "Communication over fading channels with delay constraints," IEEE Trans. Inf. Theory, vol. 48, no. 5, pp. 1135-1149, May 2002.
• 8: B. Prabhakar, E. Biyikoglu, and A. El Gamal, "Energy-efficient transmission over a wireless link via lazy packet scheduling," in Proc. IEEE INFOCOM, Apr. 2001, vol. 1, pp. 386-394.
• 9: A. Fu, E. Modiano, and J. Tsitsiklis, "Optimal energy allocation for delay-constrained data transmission over a time-varying channel," in Proc. IEEE INFOCOM, Apr. 2003, vol. 2, pp. 1095-1105.
• 10: M. Khojastepour and A. Sabharwal, "Delay-constrained scheduling: Power efficiency, filter design and bounds," in Proc. IEEE INFOCOM, Mar. 2004.
• 11: P. Nuggehalli, V. Srinivasan, and R. R. Rao, "Delay constrained energy efficient transmission strategies for wireless devices," in Proc. IEEE INFOCOM, Jun. 2002, vol. 3, pp. 1765-1772.
• 12: E. Uysal-Biyikoglu and A. El Gamal, "On adaptive transmission for energy-efficiency in wireless data networks," IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 3081-3094, Dec. 2004.
• 13: R. Cruz, "A calculus for network delay (Parts I & II)," IEEE Trans. Inf. Theory, vol. 37, no. 1, pp. 114-131, 132-141, Jan. 1991.
• 14: B. Collins and R. Cruz, "Transmission policies for time varying channels with average delay constraints," in Proc. 1999 Allerton Conf. Commun., Control Comput., Monticello, IL, 1999.
• 15: Bars Ata, Dynamic Power Control in a Wireless Static Channel Subject to a Quality-of-Service Constraint, Operations Research, v.53 n.5, p.842-851, September-October 2005 [doi>10.1287/opre.1040.0188]
• 16: L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
• 17: M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic power allocation and routing for time varying wireless networks," IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 89-103, Jan. 2005.
• 18: Alexander L. Stolyar, Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm, Queueing Systems: Theory and Applications, v.50 n.4, p.401-457, August 2005 [doi>10.1007/s11134-005-1450-0]
• 19: Atilla Eryilmaz , R. Srikant , James R. Perkins, Stable scheduling policies for fading wireless channels, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.411-424, April 2005 [doi>10.1109/TNET.2004.842226]
• 20: Xin Liu , Edwin K. P. Chong , Ness B. Shroff, A framework for opportunistic scheduling in wireless networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.4, p.451-474, 15 March 2003 [doi>10.1016/S1389-1286(02)00401-2]
• 21: S. Borst and P. Whiting, "Dynamic rate control algorithms for CDMA throughput optimization," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, vol. 2, pp. 976-985.
• 22: M. Zafer and E. Modiano, "Joint scheduling of rate-guaranteed and best-effort services over a wireless channel," in Proc. IEEE CDC-ECC, Spain, Dec. 2005, pp. 6022-6027.
• 23: A. Goldsmith, "The capacity of downlink fading channels with variable rate and power," IEEE Trans. Veh. Technol., vol. 46, no. 3, pp. 569-580, Aug. 1997.
• 24: J. Le Boudec and P. Thiran, Network Calculus. New York: Springer-Verlag, 2001, LNCS 2050.
• 25: James D. Salehi , Shi-Li Zhang , Jim Kurose , Don Towsley, Supporting stored video: reducing rate variability and end-to-end resource requirements through optimal smoothing, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.397-410, Aug. 1998 [doi>10.1109/90.720873]
• 26: Bruno Gaujal , Nicolas Navet , Cormac Walsh, Shortest-path algorithms for real-time scheduling of FIFO tasks with minimal energy use, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.907-933, November 2005 [doi>10.1145/1113830.1113838]
• 27: I. S. Gradshteyn and I. M. Ryzhik, Table of Integrals, Series and Products . San Diego, CA: Academic, 2000.
• 28: W. Rudin, Principles of Mathematical Analysis, 3rd ed. Singapore: McGraw-Hill, 1976.
• 29: E. R. Pinch, Optimal Control and the Calculus of Variations. London, U.K.: Oxford Univ. Press, 1993.
• 30: David G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, Inc., New York, NY, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Management, Performance

Keywords:
delay, energy, network calculus, quality of service (QoS), rate control, wireless