Game Theoretic Perspective of Optimal CSMA

• Published in: IEEE transactions on wireless communications 2018-01, Vol.17 (1), p.194-209
• Main Authors: Jang, Hyeryung, Yun, Se-Young, Shin, Jinwoo, Yi, Yung
• Format: Article
• Language: English
• Subjects: CSMA; distributed algorithms; game theory; Games; Interference; Message passing; Multiaccess communication; Nash equilibrium; stochastic approximation; Throughput; wireless ad-hoc network; Wireless communication
• ISSN: 1536-1276; 1558-2248
• DOI: 10.1109/TWC.2017.2764081

Game-theoretic approaches have provided valuable insights into the design of robust local control rules for the individuals in multi-agent systems, e.g., Internet congestion control, road transportation networks, and so on. In this paper, we introduce a non-cooperative medium access control game for wireless networks and propose new fully distributed carrier sense multiple access (CSMA) algorithms that are provably optimal in the sense that their long-term throughputs converge to the optimal solution of a utility maximization problem over the maximum throughput region. The most significant part of our approach lies in introducing novel price functions in agents' utilities so that the proposed game admits an ordinal potential function with no price-of-anarchy. The game formulation naturally leads to game-based dynamics finding a Nash equilibrium, but they often require global information. Toward our goal of designing fully distributed operations, we propose new game-inspired dynamics by utilizing a certain property of CSMA that enables links to estimate their temporary throughputs without message passing. They can be thought of as stochastic approximations to the standard dynamics, which is a new feature in our work, not prevalent in other traditional game-theoretic approaches. We show that they converge to a Nash equilibrium, and numerically evaluate their performance to support our theoretical findings.