Distributed learning for utility maximization over CSMA-based wireless multihop networks

Game-theoretic modeling and equilibrium analysis have provided valuable insights into the design of robust local control rules for the individual agents in multi-agent systems, e.g., Internet congestion control, road transportation networks, etc. In this paper, we introduce a non-cooperative MAC (Medium Access Control) game for wireless networks and propose new fully-distributed CSMA (Carrier Sense Multiple Access) learning algorithms that are probably 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 a novel cost function in agents' utilities so that the proposed game admits an ordinal potential function with (asymptotically) no price-of-anarchy. The game formulation naturally leads to known game-based learning rules to find a Nash equilibrium, but they are computationally inefficient and often require global information. Towards our goal of fully-distributed operation, we propose new fully-distributed learning algorithms by utilizing a unique property of CSMA that enables each link to estimate its temporary link throughput without message passing for the applied CSMA parameters. The proposed algorithms can be thought as 'stochastic approximations' to the standard learning rules, 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, which is a utility-optimal point, numerically evaluate their performance to support our theoretical findings and further examine various features such as convergence speed and its tradeoff with efficiency.