Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints
| Title | Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints |
| Publication Type | Conference Papers |
| Year of Publication | 2008 |
| Authors | Chafekar D, Kumart VSA, Marathe MV, Parthasarathy S, Srinivasan A |
| Conference Name | IEEE INFOCOM 2008. The 27th Conference on Computer Communications |
| Date Published | 2008/04/13/18 |
| Publisher | IEEE |
| ISBN Number | 978-1-4244-2025-4 |
| Keywords | Algorithm design and analysis, approximation algorithm, Approximation algorithms, approximation theory, Computer networks, Computer science, graph theory, graph-based model, Interference constraints, polynomial time algorithm, Propagation losses, Protocols, radio networks, radiofrequency interference, signal to interference plus noise ratio, Signal to noise ratio, Throughput, wireless interference, wireless network, Wireless networks |
| Abstract | A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting. |
| DOI | 10.1109/INFOCOM.2008.172 |