Congestion Games and Their Application to Spectrum Sharing

Recent advances in software defined radio and cognitive radio have given wireless devices the ability and opportunity to dynamically access spectrum, thereby potentially significantly improving spectrum efficiency and user performance. With this opportunity comes the challenge of designing the right mechanism that allows users to share spectrum effectively. In this talk I will present our recent study in decentralized multi-user frequency adaptation. Our approach is primarily based on the notion of congestion games; this is a class of strategic games that model the competition for resources by multiple selfish users. Some appealing features of this game include that any asynchronous improvement updating sequence by users is finite and results in a Nash Equilibrium, which also turns out to be a local optimal solution to a global/system objective function called the potential function. On the other hand, the standard definition of a congestion game does not capture the spatial reuse and pair-wise interference characteristics of wireless communication. I will discuss two approaches to address this problem. The first approach lies in a re-definition of resource which implicitly captures pair-wise interference. Using this approach I will reverse-engineer two existing interference minimizing algorithms and show that they can be mapped into and derived from equivalent congestion games. I will then use the same approach to forward-engineer a base station frequency adaptation algorithm. Our second approach introduces an extension to the classical congestion games that explicitly models spatial reuse. I will discuss the properties of this generalized congestion game under a variety of conditions.