Brief announcement: distributed algorithms for approximating wireless network capacity

ABSTRACT

In this paper we consider the problem of maximizing wireless network capacity (a.k.a. one-shot scheduling) in both the protocol and physical models. We give the first distributed algorithms with provable guarantees in the physical model, and also give the first algorithms in the protocol model that do not assume transmitters can coordinate with their neighbors in the interference graph, so every transmitter chooses whether to broadcast based purely on local events. Our techniques draw heavily from algorithmic game theory and machine learning theory, even though our goal is a distributed algorithm. Indeed, our main results allow every transmitter to run any algorithm it wants, so long as its algorithm has a learning-theoretic property known as no-regret in a game-theoretic setting.

REFERENCES

• 1: Matthews Andrews and Michael Dinitz. Maximizing capacity in arbitrary wireless networks in the {SINR} model: complexity and game theory. In INFOCOM, 2009.
• 2: Peter Auer , Nicolò Cesa-Bianchi , Yoav Freund , Robert E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing, v.32 n.1, p.48-77, 2003 [doi>10.1137/S0097539701398375]
• 3: Avrim Blum , MohammadTaghi Hajiaghayi , Katrina Ligett , Aaron Roth, Regret minimization and the price of total anarchy, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374430]
• 4: Olga Goussevskaia, Magús Halldórson, Roger Wattenhofer, and Emo Welzl. Capacity of arbitrary wireless networks. In INFOCOM, 2009.
• 5: Olga Goussevskaia , Yvonne Anne Oswald , Roger Wattenhofer, Complexity in geometric SINR, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288122]
• 6: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, distributed algorithms, network capacity, no-regret