Equilibria in topology control games for ad hoc networks

ABSTRACT

We study topology control problems in ad hoc networks, where network nodes get to choose their power levels in order to ensure desired connectivity properties. Unlike most other work on this topic, we assume that the network nodes are owned by different entities, whose only goal is to maximize their own utility that they get out of the network without considering the overall performance of the network. Game theory is the appropriate tool to study such selfish nodes: we define several topology control games in which the nodes need to choose power levels in order to connect to other nodes in the network to reach their communication partners while at the same time minimizing their costs. We study Nash equilibria and show that -- among the games we define -- these can only be guaranteed to exist if all network nodes are required to be connected to all other nodes (we call this the Strong Connectivity Game). We give asymptotically tight bounds for the worst case quality of a Nash equilibrium in the Strong Connectivity Game and we improve these bounds for randomly distributed nodes. We then study the computational complexity of finding Nash equilibria and show that a polynomial-time algorithm finds Nash equilibria whose costs are at most a factor 2 off the minimum cost possible; for a variation called Connectivity Game, where each node is only required to be connected (possibly via intermediate nodes) to a given set of nodes, we show that answering the question, if a Nash equilibrium exists, is NP-hard, if the network graph satisfies the triangle inequality. For a second game called Reachability Game, where each node tries to reach as many other nodes as possible, while minimizing its radius, we show that 1+o(1)-approximate Nash equilibria exist for randomly distributed nodes. Our work is a first step towards game-theoretic analyses of ad hoc networks.

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 , 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: M. Beckmann, C.B. McGuire and C.B. Winsten. Studies in the Economics of transportation. Yale University Press, 1956.
• 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: S.C. Dafermos and F.T. Sparrow. The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards, Series B, 73 B(2), pp 91--118, 1969.
• 6: Sheetalkumar Doshi , Shweta Bhandare , Timothy X Brown, An on-demand minimum energy routing protocol for a wireless ad hoc network, ACM SIGMOBILE Mobile Computing and Communications Review, v.6 n.3, July 2002 [doi>10.1145/581291.581300]
• 7: A. Fabrikant, A. Luthra, E. Maneva, S. Papadimitriou, and S. Shenker. On a network creation game.
• 8: James A. Freebersyser , Barry Leiner, A DoD perspective on mobile Ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 9: 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
• 10: 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]
• 11: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 12: A. Mas-Collel, W. Whinston, and J. Green. Microeconomic Theory. Oxford University Press, 1994.
• 13: Charles E. Perkins, Ad hoc networking: an introduction, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 14: Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
• 15: Timothy Avelin Roughgarden , Eva Tardos, Selfish routing, 2002
• 16: T. Roughgarden, Designing Networks for Selfish Users is Hard, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.472, October 14-17, 2001

INDEX TERMS

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

General Terms:
Algorithms, Design, Theory

Keywords:
ad hoc networks, game theory, nash equilibrium, topology control