Maximum-lifetime routing: system optimization & game-theoretic perspectives

ABSTRACT

Routing traffic so as to maximize the lifetime of a transmission is a major problem in wireless networks. We address a two-way multicast problem, where a root wishes to transmit data to a subset of nodes, as well as receive data from them. In addition, we consider the anycast problem, wherethere is a subset of nodes that wish to communicate with each other. We consider both a per-hop multi-recipients environment, where over each hop, the transmission is received by all nodes within range, and a per-hop single-recipient environment, where over each hop the transmission is received by a single recipient. For both environments, our work consists of two parts. In the first part we focus on system optimization perspectives of the lifetime maximization problem, while in the second part we investigate the game-theoretic perspective of the respective problems.

We first note that, for the per-hop multi-recipients environment, an optimal solution can be computed in polynomial time. Nevertheless, for the per-hop single-recipient environment, we observe that computing an optimal solution is NP-hard. Accordingly, we provide a polynomial time algorithm that finds a 2-approximate solution for the case of uniform transmission power levels. For different transmission power levels, we provide an O(log² n) approximation algorithm for the general problem, and an O(log n) approximation algorithm for the special case where the set of terminals equals the set of all nodes, whose size equals n.

For each environment, we consider the corresponding noncooperative game scenario, and prove that by following the natural game course users converge to a Nash equilibrium. For the per-hop multi-recipients environment, we show that if the players join the game sequentially, the Nash equilibrium is (networkwide) optimal. For the per-hop single-recipient environment, we show that the price of anarchy is unbounded. On the other hand, we show that for both environments, the price of stability, where the best Nash equilibrium is considered, is 1; hence, optimal (networkwide) performance can be achieved if the initial configuration can be imposed on the players.

REFERENCES

• 1: Luzi Anderegg , Stephan Eidenbenz, Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939011]
• 2: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 3: Naouel Ben Salem , Levente Buttyán , Jean-Pierre Hubaux , Markus Jakobsson, A charging and rewarding scheme for packet forwarding in multi-hop cellular networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778418]
• 4: Sonja Buchegger , Jean-Yves Le Boudec, Performance analysis of the CONFIDANT protocol, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513828]
• 5: 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]
• 6: 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]
• 7: G. Calinescu, S. Kapoor, A. Olshevsky and A. Zelikovsky, "Network lifetime and power assignment in ad-hoc wireless networks", Proceedings of ESA'03, pp. 114--126, 2003.
• 8: Jae-Hwan Chang , Leandros Tassiulas, Maximum lifetime routing in wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.609-619, August 2004 [doi>10.1109/TNET.2004.833122]
• 9: Chandra Chekuri , Julia Chuzhoy , Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Non-cooperative multicast and facility location games, Proceedings of the 7th ACM conference on Electronic commerce, p.72-81, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134716]
• 10: R.R. Choudhury and N.H. Vaidya, "Performance of Ad Hoc routing using directional antennas", Journal of Ad Hoc Networks, 2004.
• 11: Jon Crowcroft , Richard Gibbens , Frank Kelly , Sven Östring, Modelling incentives for collaboration in mobile ad hoc networks, Performance Evaluation, v.57 n.4, p.427-439, August 2004 [doi>10.1016/j.peva.2004.03.003]
• 12: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 13: Patrik Floréen , Petteri Kaski , Jukka Kohonen , Pekka Orponen, Multicast time maximization in energy constrained wireless networks, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.50-58, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941087]
• 14: M. Fürer and B. Raghavachari, "An NC approximation algorithm for the minimum degree spanning tree problem", Proceedings of the 28th Annual Allerton Conference on Communications, Control and Computing, pp. 274--281, 1990.
• 15: Martin Fürer , Balaji Raghavachari, Approximating the minimum-degree Steiner tree to within one of optimal, Journal of Algorithms, v.17 n.3, p.409-423, Nov. 1994
• 16: 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
• 17: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 18: C. Hu, Y. Hong and J. Hou, "On mitigating the broadcast storm problem with directional antennas", Proceedings of IEEE ICC'03, 2003.
• 19: I. Kang and R. Poovendran, "Maximizing network lifetime of broadcasting over wireless stationary adhoc networks", Proceedings of IEEE International Conference on Communications (ICC), 2003.
• 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: E. Koutsoupias and C. Papadimitriou, "Worst-case equilibria", Proc. of STACS, LNCS, pp. 404--413, 1999.
• 22: D. Monderer and L.S. Shapley, "Potential Games", Games and Economic Behavior, Vol. 14, pp. 124--143, 1996.
• 23: Ariel Orda , Ben-Ami Yassour, Maximum-lifetime routing algorithms for networks with omnidirectional and directional antennas, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062742]
• 24: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 25: V. Rodoplu and T.H. Meng, "Minimum energy mobile wireless networks", IEEE Journal on Selected Areas in Communications, Vol. 17, pp. 1333--1344, 1999.
• 26: V. Srinivasan, P. Nuggehalli, C.-F. Chiasserini and R.R. Rao, "Cooperation in wireless ad-hoc networks", Proceedings of IEEE Iifocom'03, pp. 808--817, 2003.
• 27: V. Srivastava, J. Neel, A.B. MacKenzie, R. Menon, L.A. DaSilva, J. Hicks, J.H. Reed and R. Gilles, "Using game theory to analyze wireless ad hoc networks", IEEE Communications Surveys and Tutorials,Vol.7(4),pp. 46--56, 2005.
• 28: K. Wang, J.G. Proakis and R.R. Rao, "Energy-efficient routing algorithms using directional antennas for mobile Ad Hoc networks", International Journal of Wireless Information Networks, Vol. 9, pp. 83--109, 2002.
• 29: J.E. Wieselthier, G.D. Nguyen and A. Ephremides, "On the construction of energy-efficient broadcast and multicast trees in wireless networks", Proceedings of IEEE Infocom'00, pp. 585--594, 2000.
• 30: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Energy-Aware Wireless Networking with Directional Antennas: The Case of Session-Based Broadcasting and Multicasting, IEEE Transactions on Mobile Computing, v.1 n.3, p.176-191, July 2002 [doi>10.1109/TMC.2002.1081754]
• 31: S. Zhong, Y.R. Yang and J. Chen, "Sprite: a simple, cheat-proof, credit-based system for mobile ad-hoc networks", Proceedings of IEEE Infocom'03,pp. 1987--1997, 2003.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.0 General
          Subjects: Games

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
anycast game, multicast game, nash equilibrium, price of anarchy, price of stability