About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
4th International ICST Conference on Wireless Internet

Research Article

Quality of routing congestion games in wireless sensor networks

Download742 downloads
Cite
BibTeX Plain Text
  • @INPROCEEDINGS{10.4108/ICST.WICON2008.4914,
        author={Costas  Busch and Rajgopal  Kannan and Athanasios V.  Vasilakos},
        title={Quality of routing congestion games in wireless sensor networks},
        proceedings={4th International ICST Conference on Wireless Internet},
        publisher={ICST},
        proceedings_a={WICON},
        year={2010},
        month={5},
        keywords={Algorithmic game theory congestion games Nash equilibrium price of stability price of anarchy},
        doi={10.4108/ICST.WICON2008.4914}
    }
    
  • Costas Busch
    Rajgopal Kannan
    Athanasios V. Vasilakos
    Year: 2010
    Quality of routing congestion games in wireless sensor networks
    WICON
    ICST
    DOI: 10.4108/ICST.WICON2008.4914
Costas Busch1,*, Rajgopal Kannan1,*, Athanasios V. Vasilakos2,*
  • 1: Computer Science Department, Louisiana State University, 286 Coates Hall, Baton Rouge, LA 70803, USA
  • 2: Department of Computer Science & Telecommunications Engineering, University of Western, Macedonia, Greece 45431
*Contact email: busch@csc.lsu.edu, rkannan@csc.lsu.edu, vasilako@ath.forthnet.gr

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 Ci and service cost Si, in other words minimizes Ci + Si. 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.

Keywords
Algorithmic game theory congestion games Nash equilibrium price of stability price of anarchy
Published
2010-05-16
Publisher
ICST
http://dx.doi.org/10.4108/ICST.WICON2008.4914
Copyright © 2008–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL