article

Approximation algorithms for minimum energy transmission scheduling in rate and duty-cycle constrained wireless networks

Authors:

Rajgopal Kannan,

Shuangqing Wei,

Vasu Chakravarthy,

Muralidhar RangaswamyAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 18, Issue 1

Pages 296 - 306

https://doi.org/10.1109/TNET.2009.2026900

Published: 01 February 2010 Publication History

Abstract

We consider a constrained energy optimization called Minimum Energy Scheduling Problem (MESP) for a wireless network of users transmitting over time slots, where the constraints arise because of interference between wireless nodes that limits their transmission rates along with load and duty-cycle (ON-OFF) restrictions. Since traditional optimization methods using Lagrange multipliers do not work well and are computationally expensive given the nonconvex constraints, we consider approximation schemes for finding the optimal (minimum energy) transmission schedule by discretizing power levels over the interference channel. First, we show the toughness of approximating MESP for an arbitrary number of users N even with a fixed M. For any r < 0, we demonstrate that there does not exist any (r,r)-bicriteria approximation for this MESP, unless P = NP. Conversely, we show that there exist good approximations for MESP with given N users transmitting over an arbitrary number of M time slots by developing fully polynomial (1,1+Ɛ) approximation schemes (FPAS). For any Ɛ>0, we develop an algorithm for computing the optimal number of discrete power levels per time slot (o(1/Ɛ)), and use this to design a (1,1+Ɛ)-FPAS that consumes no more energy than the optimal while violating each rate constraint by at most a 1+Ɛ-factor. For wireless networks with low-cost transmitters, where nodes are restricted to transmitting at a fixed power over active time slots, we develop a two-factor approximation for finding the optimal fixed transmission power value P_opt that results in the minimum energy schedule.

References

[1]

S. Singh and C. Raghavendra, "Pamas: Power aware multi-access protocol with signaling for ad hoc networks," 1999.

[2]

W. Ye, J. Heidemann, and D. Estrin, "An energy-efficient MAC protocol for wireless sensor networks," 2002 {Online}. Available: citeseer. ist.psu.edu/ye01energyefficient.html

[3]

W. Ye, J. Heidemann, and D. Estrin, "Medium access control with coordinated, adaptive sleeping for wireless sensor networks," 2003 {Online}. Available: citeseer.ist.psu.edu/ye04medium.html

[4]

E. Uysal-Biyikoglu, B. Prabhakar, and A. El Gamal, "Energy-efficient packet transmission over a wireless link," IEEE/ACMTrans. Netw., vol. 10, no. 4, pp. 487-499, Aug. 2002.

[5]

E. Uysal-Biyikoglu and A. E. Gamal, "On adaptive transmission for energy efficiency in wireless data networks," IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 3081-3094, Dec. 2004.

[6]

Y. Yu, B. Krishnamachari, and V. Prasanna, "Energy-latency trade-offs for data gathering in wireless sensor networks," in Proc. IEEE INFOCOM, May 2004, vol. 1.

[7]

S. Hanly and D. Tse, "Power control and capacity of spread-spectrum wireless networks," Automat., vol. 35, no. 12, pp. 1987-2012, 1999.

[8]

K. Wang, C. Chiasserini, R. Rao, and J. Proakis, "A distributed joint scheduling and power control algorithm for multicasting in wireless ad hoc networks," in Proc. IEEE ICC, May 11-15, 2003, vol. 1, pp. 725-731.

[9]

T. ElBatt and A. Ephremides, "Joint scheduling and power control for wireless ad hoc networks," IEEE Trans. Wireless Commun., vol. 3, no. 1, pp. 74-85, Jan. 2004.

[10]

G. J. Foschini and Z. Miljanic, "A simple distributed autonomous power control algorithm and its convergence," IEEE Trans. Veh. Technol., vol. 42, no. 4, pp. 641-646, Nov. 1993.

[11]

N. Bambos, "Toward power-sensitive network architectures in wireless communications: Concepts, issues, and design concepts," IEEE Personal Commun., vol. 5, no. 3, pp. 50-59, Jun. 1998.

[12]

S. Kandukuri and N. Bambos, "Power control multiple access (PCMA) in wireless communication networks," in Proc. IEEE INFOCOM, Mar. 2000, pp. 386-395.

[13]

T. ElBatt and A. Ephremides, "Joint scheduling and power control for wireless ad hoc networks," in Proc. IEEE INFOCOM, Apr. 2002, vol. 2, pp. 976-984.

[14]

W. Yu and R. Lui, "Dual methods for nonconvex spectrum optimization of multicarrier systems," IEEE Trans. Commun., vol. 54, no. 7, pp. 1310-1322, Jul. 2006.

[15]

T. Shu, M. Krunz, and S. Vrudhula, "Joint optimization of transmit power-time and bit energy efficiency in CDMA wireless sensor networks," IEEE Trans. Wireless Commun., vol. 5, no. 11, pp. 3109-3118, Nov. 2006.

[16]

T. Rappaport, Wireless Communications: Principles and Practice, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2001.

[17]

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.

[18]

V. M. K. Chan and W. Yu, "Joint multiuser detection and optimal spectrum balancing for digital subscriber lines," EURASIP J. Appl. Signal Process., no. 2, pp. 1-13, 2006, Article ID 80941, Special Issue on Advanced Signal Processing Techniques for Digital Subscriber Lines.

[19]

S. Verdu, Multiuser Detection. London, U.K.: Cambridge Univ. Press, 1998.

[20]

H. Moon and D. Cox, "Efficient power allocation for coded OFDM systems vehicular technology conference," in Proc. 2004 IEEE Veh. Technol. Conf., Adelaide, Australia, Sep. 2004, vol. 6, pp. 4366-4370.

[21]

H. Moon, "Efficient power allocation for codedOFDM systems," Ph.D. dissertation, Stanford Univ., Stanford, CA, 2004.

[22]

D. P. Bertsekas, Nonlinear Programming, 2nd ed. Belmont, MA: Athena Scientific, 1999.

[23]

D. Bertsekas, G. Lauer, N. Sandell, and T. Posbergh, "Optimal shortterm scheduling of large-scale power systems," IEEE Trans. Autom. Control, vol. AC-28, no. 1, pp. 1-11, Jan. 1983.

[24]

E. Dorit Hochbaum, Approximation Algorithms for NP-Hard Problems, 1st ed. Boston, MA: PWS, 1997.

[25]

R. Kannan, S.Wei, C. Chakravarthy, and G. Seetharaman, "Using misbehavior to analyze strategic versus aggregate energy minimization in wireless sensor networks," Int. J. Distrib. Sensor Netw., vol. 2, no. 3, pp. 225-249, Sep. 2006.

[26]

T. M. Cover and J. A. Thomas, Elements of Information Theory, 1st ed. New York: Wiley, 1991.

[27]

E.-S. Jung and N. H. Vaidya, "A power control mac protocol for ad hoc networks," in Proc. ACM MobiCom, Sep. 2002, pp. 36-47.

Cited By

Wang GPeng YFeng PWang N(2014)An energy consumption minimization routing scheme based on rate adaptation with QoS guarantee for the mobile environmentComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.09.00674:PB(48-57)Online publication date: 9-Dec-2014
https://dl.acm.org/doi/10.1016/j.comnet.2014.09.006

Index Terms

Approximation algorithms for minimum energy transmission scheduling in rate and duty-cycle constrained wireless networks

Recommendations

Minimum Transmission Time Encoding in Multi-rate Wireless Networks
PACCS '09: Proceedings of the 2009 Pacific-Asia Conference on Circuits, Communications and Systems

The minimum transmission time encoding problem is proposed in single-hop multi-rate wireless networks. Moreover, we formulate this problem as a minimum weighted clique partition of graph. The simulation results show that the minimum transmission time ...
High-Priority Minimum-Interference Channel Assignment in Multi-Radio Multi-Channel Wireless Networks
ICTCE '18: Proceedings of the 2nd International Conference on Telecommunications and Communication Engineering

Wireless network nodes equipping multi-radio interfaces on each node and using multi-channel for transmission can greatly enhance the network performance. In this paper, we study the channel assignment problem in the multi-radio multi-channel wireless ...
Threshold ALOHA with sensing data lookup in low-duty-cycle wireless networks
Abstract
Slotted ALOHA is a well-known multiple access control protocol that devices use to access a radio channel in wireless networks. Age of information (AoI) is a key network performance indicator that represents the elapsed time between the time data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 18, Issue 1

February 2010

332 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2010

Revised: 08 May 2008

Received: 26 May 2007

Published in TON Volume 18, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
142
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang GPeng YFeng PWang N(2014)An energy consumption minimization routing scheme based on rate adaptation with QoS guarantee for the mobile environmentComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.09.00674:PB(48-57)Online publication date: 9-Dec-2014
https://dl.acm.org/doi/10.1016/j.comnet.2014.09.006

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents