Distributed learning for utility maximization over CSMA-based wireless multihop networks
2014 (English)In: Proceedings - IEEE INFOCOM, 2014, 280-288 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
2014. 280-288 p.
Carrier communication, Carrier sense multiple access, Communication channels (information theory), Game theory, Learning algorithms, Medium access control, Multi agent systems, Stochastic control systems, Wireless ad hoc networks, Wireless networks, Equilibrium analysis, Game-theoretic model, Internet congestion control, MAC (medium access control), Road transportation networks, Stochastic approximations, Utility maximizations, Wireless multi-hop network, Computer games
IdentifiersURN: urn:nbn:se:kth:diva-167625DOI: 10.1109/INFOCOM.2014.6847949ISI: 000361544200032ScopusID: 2-s2.0-84904438997ISBN: 9781479933600OAI: oai:DiVA.org:kth-167625DiVA: diva2:813877
33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014, 27 April 2014 - 2 May 2014, Toronto, ON
QC 201505252015-05-252015-05-222015-10-29Bibliographically approved