article

Low-complexity and distributed energy minimization in multihop wireless networks

Authors:

Ness B. ShroffAuthors Info & Claims

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

Pages 501 - 514

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

Published: 01 April 2010 Publication History

Abstract

In this work, we study the problem of minimizing the total power consumption in a multihop wireless network subject to a given offered load. It is well-known that the total power consumption of multihop wireless networks can be substantially reduced by jointly optimizing power control, link scheduling, and routing. However, the known optimal cross-layer solution to this problem is centralized and with high computational complexity. In this paper, we develop a low-complexity and distributed algorithm that is provably power-efficient. In particular, under the node-exclusive interference model and with suitable assumptions on the power-rate function, we can showthat the total power consumption of our algorithm is at most (2 + Ɛ) times as large as the power consumption of the optimal (but centralized and complex) algorithm, where is an arbitrarily small positive constant. Our algorithm is not only the first such distributed solution with provable performance bound, but its power-efficiency ratio is also tighter than that of another suboptimal centralized algorithm in the literature.

References

[1]

L. Lin, X. Lin, and N. B. Shroff, "Low-complexity and distributed energy minimization in multi-hop wireless networks," in Proc. IEEE INFOCOM, Anchorage, Alaska, May 2007, pp. 1685-1693.

[2]

I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: A survey," Comput. Netw., vol. 38, no. 4, pp. 393-422, 2002.

Digital Library

[3]

T. P. Ruggaber and J. W. Talley, "Detection and control of combined sewer overflow events using embedded sensor network technology," in Proc. World Water Congress, Anchorage, Alaska, May 2005, p. 306.

[4]

J. Luo and J.-P. Hubaux, "A survey of inter-vehicle communication," EPFL, Lausanne, Switzerland, Tech. Rep., 2004.

[5]

I. F. Akyildiz, X. Wang, and W. Wang, "Wireless mesh networks: A survey," Comput. Netw., vol. 47, no. 4, pp. 445-487, 2005.

Digital Library

[6]

R. L. Cruz and A. V. Santhanam, "Optimal routing, link scheduling and power control in multi-hop wireless networks," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, vol. 1, pp. 702-711.

[7]

M. J. Neely, "Energy optimal control for time varying wireless networks," IEEE Trans. Inf. Theory, vol. 52, no. 7, pp. 2915-2934, Jul. 2006.

Digital Library

[8]

R. Bhatia and M. Kodialam, "On power efficient communication over multi-hop wireless networks: Joint routing, scheduling and power control," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, vol. 2, pp. 1457-1466.

[9]

M. J. Neely and R. Urgaonkar, "Optimal backpressure routing for wireless networks with multi-receiver diversity," Ad Hoc Netw., vol. 7, no. 5, pp. 862-881, Jul. 2009.

Digital Library

[10]

X. Lin and N. B. Shroff, "The impact of imperfect scheduling on cross-layer rate control in wireless networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, vol. 3, pp. 1804-1814.

[11]

X. Lin and N. B. Shroff, "The impact of imperfect scheduling on cross-layer congestion control in wireless networks," IEEE/ACM Trans. Netw., vol. 14, no. 2, pp. 302-315, Apr. 2006.

Digital Library

[12]

X. Lin, N. B. Shroff, and R. Srikant, "A tutorial on cross-layer optimization in wireless networks," IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1452-1463, Aug. 2006.

Digital Library

[13]

K. Kar, M. Kodialam, T. V. Lakshman, and L. Tassiulas, "Routing for network capacity maximization in energy-constrained ad-hoc networks," in Proc. IEEE INFOCOM, 2003, vol. 1, pp. 673-681.

[14]

Q. Li, J. Aslam, and D. Rus, "Online power-aware routing in wireless ad-hoc networks," in Proc. ACM MobiCom, 2001, pp. 97-107.

Digital Library

[15]

L. Lin, N. B. Shroff, and R. Srikant, "Energy-aware routing in sensor networks: A large system approach," Ad Hoc Netw., vol. 5, no. 6, pp. 818-831, Aug. 2007.

Digital Library

[16]

C.-K. Toh, "Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks," IEEE Commun. Mag., vol. 39, no. 6, pp. 138-147, Jun. 2001.

Digital Library

[17]

Y. Xue, Y. Cui, and K. Nahrstedt, "A utility-based distributed maximum lifetime routing algorithm for wireless networks," IEEE Trans. Veh. Technol., vol. 55, no. 3, pp. 797-805, May 2006.

[18]

B. Hajek and G. Sasaki, "Link scheduling in polynomial time," IEEE Trans. Inf. Theory, vol. 34, no. 5, pp. 910-917, Sep. 1988.

Digital Library

[19]

S. Sarkar and L. Tassiulas, "End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks," in Proc. IEEE Conf. Decision Control, Maui, HI, Dec. 2003, vol. 1, pp. 564-569.

[20]

Y. Yi and S. Shakkottai, "Hop-by-hop congestion control over a wireless multi-hop network," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, vol. 4, pp. 2548-2558.

[21]

L. Lin, X. Lin, and N. B. Shroff, "Low-complexity and distributed energy minimization in multi-hop wireless networks," Purdue University, Tech. Rep., 2006 {Online}. Available: http://min.ecn.purdue.edu/~linx/ papers.html

[22]

S. Boyd and L. Vandenberghe, Convex Optimization. New York: Cambridge Univ. Press, 2004.

Digital Library

[23]

P. Chaporkar, K. Kar, X. Luo, and S. Sarkar, "Throughput and fairness guarantees through maximal scheduling in wireless networks," IEEE Trans. Inf. Theory, vol. 54, no. 2, pp. 572-594, Feb. 2008.

Digital Library

[24]

P. Chaporkar, K. Kar, and S. Sarkar, "Achieving queue length stability through maximal scheduling in wireless networks," presented at the Inf. Theory Appl. Inaugural Workshop, San Diego, CA, Feb. 2006.

[25]

X. Wu, R. Srikant, and J. R. Perkins, "Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks," IEEE Trans. Mobile Comput., vol. 6, no. 6, pp. 595-605, Jun. 2007.

Digital Library

[26]

X. Wu, R. Srikant, and J. R. Perkins, "Queue-length stability of maximal greedy schedules in wireless network," presented at the Inf. Theory Appl. Inaugural Workshop, San Diego, CA, Feb. 2006.

[27]

A. Israeli and A. Itai, "A fast and simple randomized parallel algorithm for maximal matching," Inf. Process. Lett., vol. 22, no. 2, pp. 77-80, Jan. 1986.

Digital Library

[28]

A. Gupta, X. Lin, and R. Srikant, "Low-complexity distributed scheduling algorithms for wireless networks," in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 1631-1639.

[29]

D. Bertsekas, A. Nedic, and A. E. Ozdaglar, Convex Analysis and Optimization. Nashua, NH: Athena Scientific, 2003.

Cited By

Basu PSalonidis TKraczek BSaghaian SSydney AKo BLa Porta TChan K(2020)Decentralized placement of data and analytics in wireless networks for energy-efficient executionIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155222(486-495)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1109/INFOCOM41043.2020.9155222
Jia RZhang JLiu XLiu PFu LWang X(2019)Optimal Rate Control for Energy-Harvesting Systems with Random Data and Energy ArrivalsACM Transactions on Sensor Networks10.1145/329353515:1(1-30)Online publication date: 10-Feb-2019
https://dl.acm.org/doi/10.1145/3293535
Zuo SDeng HHou I(2017)Energy Efficient Algorithms for Real-Time Traffic Over Fading Wireless ChannelsIEEE Transactions on Wireless Communications10.1109/TWC.2017.265689816:3(1881-1892)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TWC.2017.2656898
Show More Cited By

Index Terms

Low-complexity and distributed energy minimization in multihop wireless networks
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance
2. Networks
  1. Network services
    1. Network management

Recommendations

Network coded ALOHA for wireless multihop networks
WCNC'09: Proceedings of the 2009 IEEE conference on Wireless Communications & Networking Conference

The purpose of this paper is to show the possibility of combining slotted ALOHA with network coding in wireless multihop networks. In particular, we focus on a star topology in which outer nodes exchange data with each other through a center node. The ...
Cross-layer optimization and network coding in CSMA/CA-based wireless multihop networks

In this paper, we consider the CSMA/CA multihop networks where the two end-nodes transmit their packets to each other and each intermediate node adopts network coding for delivering bidirectional flows. In addition, the neighbor nodes are randomly ...
A distributed CSMA algorithm for throughput and utility maximization in wireless networks

In multihop wireless networks, designing distributed scheduling algorithms to achieve the maximal throughput is a challenging problem because of the complex interference constraints among different links. Traditional maximal-weight scheduling (MWS), ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 18, Issue 2

April 2010

339 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 2010

Revised: 14 April 2009

Received: 12 June 2008

Published in TON Volume 18, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
253
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Basu PSalonidis TKraczek BSaghaian SSydney AKo BLa Porta TChan K(2020)Decentralized placement of data and analytics in wireless networks for energy-efficient executionIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155222(486-495)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1109/INFOCOM41043.2020.9155222
Jia RZhang JLiu XLiu PFu LWang X(2019)Optimal Rate Control for Energy-Harvesting Systems with Random Data and Energy ArrivalsACM Transactions on Sensor Networks10.1145/329353515:1(1-30)Online publication date: 10-Feb-2019
https://dl.acm.org/doi/10.1145/3293535
Zuo SDeng HHou I(2017)Energy Efficient Algorithms for Real-Time Traffic Over Fading Wireless ChannelsIEEE Transactions on Wireless Communications10.1109/TWC.2017.265689816:3(1881-1892)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TWC.2017.2656898
Garcia-Rois JGomez-Cuba FRiza Akdeniz MGonzalez-Castano FBurguillo-Rial JRangan SLorenzo B(2015)On the Analysis of Scheduling in Dynamic Duplex Multihop mmWave Cellular SystemsIEEE Transactions on Wireless Communications10.1109/TWC.2015.244698314:11(6028-6042)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1109/TWC.2015.2446983
Sadi YColeri Ergen S(2015)Energy and Delay Constrained Maximum Adaptive Schedule for Wireless Networked Control SystemsIEEE Transactions on Wireless Communications10.1109/TWC.2015.241160214:7(3738-3751)Online publication date: 8-Jul-2015
https://dl.acm.org/doi/10.1109/TWC.2015.2411602
Lahetkangas KCodreanu MAazhang B(2015)Route Discovery Protocol for Energy Efficient Networks With MIMO LinksIEEE Journal on Selected Areas in Communications10.1109/JSAC.2015.248121733:12(2735-2748)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1109/JSAC.2015.2481217

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.

Figures

Tables

Media

View Issue’s Table of Contents