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. G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In Proc. STOC, 2005.
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. R. Cypher, F. Meyer auf der Heide, C. Scheideler, and B. Vöcking. Universal algorithms for store-and-forward and wormhole routing. In In Proc. of the 28th ACM Symp. on Theory of Computing, pages 356--365, 1996.
6. A. Czumaj, P. Krysta, and B. Vöcking. Selfish traffic allocation for server farms. In Proc. STOC, 2002.
7. A. Czumaj and B. Vöcking. Tight bounds for worst-case equilibria. In Proc. SODA, 2002.
8. D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis. The structure and complexity of Nash equilibria for a selfish routing game. In Proc. ICALP, 2002.
9. D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish unsplittable flows. In Proc. ICALP, 2004.
10. M. Garing, T. Lücking, M. Mavronicolas, and B. Monien. Computing nash equilibria for scheduling on restricted parallel links. In Proc. STOC, 2004.
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. M. Hollick, I. Martinovic, T. Krop, and I. Rimac. A survey on dependable routing in sensor networks, ad hoc networks, and cellular networks. In Proc. 30th EUROMICRO Conference, pages 495--502, 2004.
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. M. Mavronicolas and P. Spirakis. The price of selfish routing. In Proc. STOC, 2001.
21. D. Monderer and L. S. Shapely. Potential games. Games and Economic Behavior, 1996.
22. R. Ostrovsky and Y. Rabani. Universal O(congestion+dilation+log^1+ε N) local control packet switching algorithms. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, pages 644--653, New York, May 1997.
23. C. H. Papadimitriou. Algorithms, games and the internet. In Proc. STOC, pages 749--753, 2001.
24. Y. Rabani and É. Tardos. Distributed packet switching in arbitrary networks. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 366--375, Philadelphia, Pennsylvania, 22--24 May 1996.
25. R. W. Rosenthal. A class of games possesing pure-strategy Nash equilibria. International Journal of Game Theory, 1973.
26. T. Roughgarden. The maximum latency of selfish routing. In Proc. SODA, 2004.
27. T. Roughgarden. Selfish routing with atomic players. In Proc. SODA, 2005.
28. T. Roughgarden and Éva Tardos. How bad is selfish routing. Journal of the ACM, 49(2):236--259, March 2002.
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. S. Suri, C. D. Tóth, and Y. Zhou. Selfish load balancing and atomic congestion games. In Proc. SPAA, 2004.
31. Wikipedia. SCADA. http://en.wikipedia.org/wiki/SCADA.

Index Terms

• Networks

  • Network protocols

    • Network layer protocols

      • Routing protocols

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems