Quality of routing congestion games in wireless sensor networks

ABSTRACT

We consider congestion games in wireless sensor networks that offer quantitatively distinct classes of routing paths. Each routing class is characterized by a service cost. Within a routing class, the maximum link congestion is also an important metric for measuring the quality of the paths. Here, we study routing games where each player i selfishly selects a path with a respective routing class that simultaneously minimizes its maximum edge congestion C_i and service cost S_i, in other words minimizes C_i + S_i. We examine the quality of Nash-equilibria and prove that the price of stability is 1. The price of anarchy is bounded above by min(C*, S*) · m log n, where m is the number of routing classes, n is the size of the graph, and C* and S* are the optimal coordinated congestion and service costs. Thus, under certain circumstances, the player's selfishness does not hurt the social welfare and actually the equilibria can give good approximations for the coordinated optimal social cost.

REFERENCES

• 1: R. Banner and A. Orda. Bottleneck routing games in communication networks. In Proc. INFOCOM, 2006.
• 2: C. Busch and M. Magdon-Ismail. Atomic routing games on maximum congestion. In Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM), pages 79--91, Hong Kong, China, June 2006.
• 3: George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060600]
• 4: J. R. Correa, A. S. Schulz, and N. E. Stier Moses. Computational complexity, fairness, and the price of anarchy of the maximum latency problem. In Proc. 10th Conf. on Integer Programming and Combinatorial Optimization (IPCO), 2004.
• 5: Robert Cypher , Friedhelm Meyer auf der Heide , Christian Scheideler , Berthold Vöcking, Universal algorithms for store-and-forward and wormhole routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.356-365, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237982]
• 6: Artur Czumaj , Piotr Krysta , Berthold Vöcking, Selfish traffic allocation for server farms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509952]
• 7: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 8: Dimitris Fotakis , Spyros C. Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul G. Spirakis, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.123-134, July 08-13, 2002
• 9: D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish unsplittable flows. In Proc. ICALP, 2004.
• 10: Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien, Computing Nash equilibria for scheduling on restricted parallel links, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007446]
• 11: M. Garing, T. Lücking, M. Mavronicolas, and B. Monien. The price of anarchy for polynomial social cost. In Proc. MFCS, 2004.
• 12: M. Garing, T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. Nash equilibria in discrete routing games with convex latency functions. In Proc. ICALP, 2004.
• 13: Matthias Hollick , Ivan Martinovic , Tronje Krop , Ivica Rimac, A Survey on Dependable Routing in Sensor Networks, Ad hoc Networks, and Cellular Networks, Proceedings of the 30th EUROMICRO Conference, p.495-502, August 31-September 03, 2004 [doi>10.1109/EUROMICRO.2004.8]
• 14: E. Koutsoupias, M. Mavronicolas, and P. Spirakis. Approximate equilibria and ball fusion. In Proc. SIROCCO, 2002.
• 15: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proc. STACS, 1999.
• 16: F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-scheduling in O(congestion + dilation) steps. Combinatorica, 14:167--186, 1994.
• 17: T. Leighton, B. Maggs, and A. W. Richa. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica, 19:375--401, 1999.
• 18: L. Libman and A. Orda. Atomic resource sharing in noncooperative networks. Telecomunication Systems, 17(4):385--409, 2001.
• 19: T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. A new model for selfish routing. In Proc. STACS, 2004.
• 20: Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece [doi>10.1145/380752.380846]
• 21: D. Monderer and L. S. Shapely. Potential games. Games and Economic Behavior, 1996.
• 22: Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258659]
• 23: 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]
• 24: Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237983]
• 25: R. W. Rosenthal. A class of games possesing pure-strategy Nash equilibria. International Journal of Game Theory, 1973.
• 26: Tim Roughgarden, The maximum latency of selfish routing, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 27: Tim Roughgarden, Selfish routing with atomic players, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 28: 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]
• 29: T. Roughgarden and Éva Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior, 47(2):389--403, 2004.
• 30: Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Selfish load balancing and atomic congestion games, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007941]
• 31: Wikipedia. SCADA. http://en.wikipedia.org/wiki/SCADA.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

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

General Terms:
Algorithms, Theory

Keywords:
Nash equilibrium, algorithmic game theory, congestion games, price of anarchy, price of stability