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

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: Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780617]
• 3: René Beier , Peter Sanders , Naveen Sivadasan, Energy Optimal Routing in Radio Networks Using Geometric Data Structures, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.366-376, July 08-13, 2002
• 4: Levente Buttyán , Jean-Pierre Hubaux, Stimulating cooperation in self-organizing mobile ad hoc networks, Mobile Networks and Applications, v.8 n.5, p.579-592, October 2003 [doi>10.1023/A:1025146013151]
• 5: Mario Ζagalj , Jean-Pierre Hubaux , Christian Enz, Minimum-energy broadcast in all-wireless networks:: NP-completeness and distribution issues, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570667]
• 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: Andrea E. F. Clementi , Miriam Di Ianni , Riccardo Silvestri, The minimum broadcast range assignment problem on linear multi-hop wireless networks, Theoretical Computer Science, v.299 n.1-3, p.751-761, 18 April 2003 [doi>10.1016/S0304-3975(02)00538-8]
• 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: Stephan Eidenbenz , V. S. Anil Kumar , Sibylle Zust, Equilibria in topology control games for ad hoc networks, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.2-11, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941081]
• 14: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 15: Jon Feldman , Matthias Ruhl, The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.299, October 17-18, 1999
• 16: Michele Flammini , Alfredo Navarra , Ralf Klasing , Stéphane Pérennes, Improved approximation results for the minimum energy broadcasting problem, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022644]
• 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: Iris Gaber , Yishay Mansour, Centralized broadcast in multihop radio networks, Journal of Algorithms, v.46 n.1, p.1-20, January 2003 [doi>10.1016/S0196-6774(02)00292-4]
• 19: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 20: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power consumption in packet radio networks, Theoretical Computer Science, v.243 n.1-2, p.289-305, July 28, 2000 [doi>10.1016/S0304-3975(98)00223-0]
• 21: Guy Kortsarz , David Peleg, Approximating the weight of shallow Steiner trees, Discrete Applied Mathematics, v.93 n.2-3, p.265-285, July 20, 1999 [doi>10.1016/S0166-218X(99)00111-0]
• 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: Weifa Liang, Constructing minimum-energy broadcast trees in wireless ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513815]
• 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 , B. Schieber, Improved approximations for shallow-light spanning trees, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.536, October 19-22, 1997
• 27: J. F. Nash, "Non-cooperative games," Annals of Mathematics, vol. 54, pp. 286--295, 1951.
• 28: Madan Natu , Shu-Cherng Fang, On the point-to-point connection problem, Information Processing Letters, v.53 n.6, p.333-336, March 24, 1995 [doi>10.1016/0020-0190(94)00216-L]
• 29: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 30: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 31: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 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. Călinescu , X. Y. Li , O. Frieder, Minimum-energy broadcasting in static ad hoc wireless networks, Wireless Networks, v.8 n.6, p.607-617, November 2002 [doi>10.1023/A:1020381720601]
• 34: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Energy-efficient broadcast and multicast trees in wireless networks, Mobile Networks and Applications, v.7 n.6, p.481-492, December 2002 [doi>10.1023/A:1020716919751]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Adaptable architectures
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Performance