 |
Center for Nonlinear Studies |
We consider the problem of maximizing the number of supported connections in arbitrary wireless networks, where a transmission is supported if and only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. The aim is to choose transmission powers for each connection so as to maximize the number of connections for which this threshold is met. We believe that analyzing this problem is important both in its own right and also because it arises as a subproblem in many other areas of wireless networking. We also feel that this problem is intriguing since it involves both continuous aspects (i.e. choosing the transmission powers) as well as discrete aspects (i.e. which connections should be supported). In this talk we will give approximation algorithms for this problem with approximation ratios independent of the number of connections. We will also discuss some related game theory, showing that for a natural game played by the transmitters the price of anarchy is also independent of the number of connections. Finally, we will show how the techniques used to prove the price of anarchy can be extended to design distributed approximation algorithms for the problem.
Host: Feng Pan