On spectrum sharing games

摘要: Efficient spectrum-sharing mechanisms are crucial to alleviate the bandwidth limitation in wireless networks. In this paper, we consider following question: can free spectrum be shared efficiently? We study problem context of 802.11 or WiFi Each access point (AP) a network must assigned channel for it service users. There only finitely many possible channels that assigned. Moreover, neighboring points use different so as avoid interference. Currently these by administrators who carefully conflicts and loads. Channel among APs operated entities currently resolved an ad hoc manner (i.e., not coordinated way) at all. view assignment game, where players providers acquired sequentially. price anarchy which is ratio between total coverage worst Nash equilibrium game what would if were done optimally central authority. provide bounds on depending assumptions underlying type bargaining allowed providers. The key tool analysis identification equilibria with solutions maximal coloring appropriate graph. relate games approximation factor local optimization algorithms maximum k-colorable subgraph problem. also speed convergence games.