skip to main content
article

Energy efficient communication in ad hoc networks from user's and designer's perspective

Published: 01 January 2005 Publication History

Abstract

We consider a game that models the creation of a wireless ad hoc network, where nodes are owned by selfish agents. We study a novel cost sharing model in which agents may pay for the transmission power of the other nodes. Each agent has to satisfy some connectivity requirement in the final network and the goal is to minimize its payment with no regard to the overall system performance. We analyze two fundamental connectivity games, namely broadcast and convergecast. We study pure Nash equilibria and quantify the degradation in the network performance called the price of anarchy resulting from selfish behavior. We derive tight bounds on the price of anarchy for these games. We also study centralized network design. One of the most important problems in wireless ad hoc networks is the minimum-energy broadcast. Recently, there appeared many new applications such as real-time multimedia, battlefield communications and rescue operations that impose stringent end-to-end latency bounds on the broadcasting time. However, the existing algorithms that minimize the broadcasting energy tend to produce solutions with high latency. In this paper we consider the problem of bounded-hop broadcast. We present approximation and heuristic algorithms for this problem.

References

[1]
C. Ambuhl, A. E. F. Clementi, M. Di Ianni, N. Lev-Tov, A. Monti, D. Peleg, G. Rossi and Riccardo Silvestri, "Efficient algorithms for low-energy bounded-hop broadcast in ad-hoc wireless networks," Proc. of the 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS'04), pp. 418--427, 2004.
[2]
E. Ansheleich, A. Dasgupta, E. Tardos and T. Wexler, "Near-optimal network design with selfish agents," Proc. of the 35th Symp. on Theory of Computing (STOC'03), pp. 511--520, 2003.
[3]
R. Beier, P. Sanders and N. Sivadasan, "Energy optimal routing in radio networks using geometric data structures," Proc. of the 29th International Colloquium on Automata, Languages and Programming (ICALP'02), pp. 366--376, 2002.
[4]
L. Buttyan and J. P. Hubaux, "Stimulating cooperation in self-organizing mobile ad hoc networks," Mobile Networks and Applications, Vol. 8, pp. 579--592, 2003.
[5]
M. Cagalj, J. P. Hubaux and C. Enz, "Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues," Proc. of the 8th Annual International Conference on Mobile Computing and Networking (MobiCom'02), pp. 172--182, 2002.
[6]
G. Calinescu, S. Kapoor, A. Olshevsky and A. Zelikovsky, "Networks lifetime and power assignment in ad hoc wireless networks," Proc. of the 11th European Symposium on Algorithms (ESA'03), pp. 114--126, 2003.
[7]
G. Calinescu, S. Kapoor and M. Sarwat, Bounded Hops Power Assignment in Ad-hoc Wireless Networks," Proc. IEEE Wireless Communications and Networking Conference (WCNC'04).
[8]
I. Caragiannis, C. Kaklamanis and P. Kanellopoulos, "Energy efficient wireless network design," Proc. of 14th Int. Symp. on Algorithms and Computation (ISAAC'03), pp. 585--594, 2003.
[9]
J. Cartigny, D. Simplot and I. Stojmenovic, "Localized minimum-energy broadcasting in ad-hoc networks," Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03), 2003.
[10]
W. T. Chen, N. F. Huang, "The Strongly Connecting Problem on Multihop Packet Radio Networks," IEEE Trans. Commun., Vol. 37(3), pp. 293--295, 1989.
[11]
A. E. F. Clementi, A. Ferreira, P. Penna, S. Perennes and R. Silvestri, "The minimum broadcast range assignment problem on linear multi-hop wireless networks," Theor. Comput. Sci., Vol. 1-3(299), pp. 751--761, 2003.
[12]
J. Crowcroft, R. Gibbens, F. Kelly and S. Ostring, "Modelling Incentives for Collaboration in Mobile Ad Hoc Networks," Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03), 2003.
[13]
S. Eidenbenz, V. S. Anil Kumar and S. Zust, "Equilibria in topology control games for ad hoc networks," Proc. of the Joint Workshop on Foundations of Mobile Computing (DIALM-POMC'03), pp. 2--11, 2003.
[14]
A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. Shenker, "On a network creation game," Proc. of the 22nd ACM Symposium on Principles of Distributed Computing (PODC'03), pp. 347--351, 2003.
[15]
J. Feldman and M. Ruhl, "The Directed Steiner Network problem is tractable for a constant number of terminals", Proc. of the 40th IEEE Symposium on Foundations of Computer Science (FOCS'99), pp. 299--308, 1999.
[16]
M. Flammini, R. Klasing, A. Navarra and S. Perennes, "Improved Approximation Results for the Minimum Energy Broadcasting Problem," Proc. of the Joint Workshop on Foundations of Mobile Computing (DIALM-POMC'04).
[17]
S. Funke, D. Matijevic, and P. Sanders, "Approximating energy efficient paths in wireless multi hop networks," Proc. of the 11th European Symposium on Algorithms (ESA'03), pp. 230--241, 2003.
[18]
I. Gaber and Y. Mansour, "Centralized broadcast in multihop radio networks," Journal of Algorithms, Vol. 46(1), pp. 1--20, 2003.
[19]
M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP Completeness," W. H. Freeman, San Francisco, 1979.
[20]
L. M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, "Power consumption in packet radio networks," Theoretical Computer Science, Vol. 243, pp. 289--305, 2000.
[21]
G. Kortsarz and D. Peleg, "Approximating the weight of shallow Steiner trees," Discrete Applied Mathematics, Vol. 93, pp. 265--285, 1999.
[22]
E. Koutsoupias, C. H. Papadimitriou, "Worst-case equilibria," Proc. of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS'99), pp. 404--413, 1999.
[23]
S. Krumke, R. Liu, E. Lloyd, M. Marathe, R. Ramanathan and S. Ravi, "Topology control problems under symmetric and asymmetric power thresholds," Proc. International Conference on Ad hoc and Wireless Networks (ADHOC-NOW'03), pp. 187--198.
[24]
W. Liang, "Constructing minimum-energy broadcast trees in wireless ad hoc networks," Proc. of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'02), pp. 112--122, 2002.
[25]
P. Michiardi and R. Molva, "A game theoretical approach to evaluate cooperation enforcement mechanisms in mobile ad hoc networks," Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03), 2003.
[26]
J. Naor and B. Schieber, "Improved approximations for shallow-light spanning trees," Proc. of the IEEE Conf. on Foundations of Computer Science (FOCS'97), pp. 536--541, 1997.
[27]
J. F. Nash, "Non-cooperative games," Annals of Mathematics, vol. 54, pp. 286--295, 1951.
[28]
M. Natu and S. Fang, "On the point-to-point connection problem," Information Processing Letters, Vol. 53(6), pp. 333--336, 1995.
[29]
T. S. Rappaport, "Wireless Communications: Principles and Practices," Prentice Hall, 1996.
[30]
T. Roughgarden and E. Tardos, "How bad is selfish routing?" Journal of the ACM, Vol. 49(2), pp. 236--259, 2002.
[31]
S. Singh, C. Raghavendra, and J. Stepanek, "Power-aware broadcasting in mobile ad hoc networks," Proc. of the 10th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC'99), pp. 181--190, 1999.
[32]
V. Srinivasan, P. Nuggehalli, C. F. Chiasserini and R. R. Rao, "Cooperation in wireless ad hoc networks," Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03), pp. 808--817, 2003.
[33]
P. J. Wan, G. Calinescu, X. Y. Li and O. Frieder, "Minimum-energy broadcast routing in static ad hoc wireless networks," Wireless Networks, 2002.
[34]
J. E. Wieselthier, G. D. Nguyen and A. Ephremides, "Energy-Efficient Broadcast and Multicast Trees in Wireless Networks," Mobile Networks and Applications (MONET). Vol. 7(6), pp. 481--492, 2002.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMOBILE Mobile Computing and Communications Review
ACM SIGMOBILE Mobile Computing and Communications Review  Volume 9, Issue 1
January 2005
82 pages
ISSN:1559-1662
EISSN:1931-1222
DOI:10.1145/1055959
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2005
Published in SIGMOBILE Volume 9, Issue 1

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2013)Improved multicriteria spanners for Ad-Hoc networks under energy and distance metricsACM Transactions on Sensor Networks10.1145/2489253.24892549:4(1-25)Online publication date: 23-Jul-2013
  • (2010)Efficient and fair routing for mesh networksMathematical Programming: Series A and B10.5555/3112662.3112955124:1-2(285-316)Online publication date: 1-Jul-2010
  • (2010)Efficient and fair routing for mesh networksMathematical Programming10.1007/s10107-010-0356-8124:1-2(285-316)Online publication date: 14-May-2010
  • (2010)Designing Fast Converging Cost Sharing Methods for Multicast TransmissionsTheory of Computing Systems10.1007/s00224-009-9207-547:2(507-530)Online publication date: 1-Aug-2010
  • (2008)ILP-Based energy minimization techniques for banked memoriesACM Transactions on Design Automation of Electronic Systems10.1145/1367045.136705913:3(1-40)Online publication date: 25-Jul-2008
  • (2008)On Nash equilibria for multicast transmissions in ad-hoc wireless networksWireless Networks10.1007/s11276-006-8817-y14:2(147-157)Online publication date: 1-Mar-2008
  • (2006)Fast distributed algorithm for convergecast in ad hoc geometric radio networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2005.11.00466:4(578-585)Online publication date: 1-Apr-2006
  • (2006)Multicast transmissions in non-cooperative networks with a limited number of selfish movesProceedings of the 31st international conference on Mathematical Foundations of Computer Science10.1007/11821069_32(363-374)Online publication date: 28-Aug-2006

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media