Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints
Authors:
- Deepti ChafekarDCDeepti Chafekar
- V. S. Anil KumarVKV. S. Anil Kumar
- Madhav V. MaratheMMMadhav V. Marathe
- Srinivasan ParthasarathySPSrinivasan Parthasarathy
- Arvind SrinivasanASArvind Srinivasan
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 1166-1174
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.Keywords
This publication has 13 references indexed in Scilit:
- Complexity in geometric SINR2007
- Cross-layer latency minimization in wireless networks with SINR constraints2007
- Topology control meets SINR2006
- The Complexity of Connectivity in Wireless Networks2006
- Algorithmic aspects of capacity in wireless networksACM SIGMETRICS Performance Evaluation Review, 2005
- On power efficient communication over multi-hop wireless networks: joint routing, scheduling and power control2005
- Capacity bounds for ad hoc and hybrid wireless networksACM SIGCOMM Computer Communication Review, 2004
- Characterizing achievable rates in multi-hop wireless networks2003
- Capacity, delay and mobility in wireless ad-hoc networks2003
- A unified framework and algorithm for (T/F/C)DMA channel assignment in wireless networks2002