Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints

Authors:
  • DCDeepti Chafekar
    Deepti Chafekar
  • VKV. S. Anil Kumar
    V. S. Anil Kumar
  • MMMadhav V. Marathe
    Madhav V. Marathe
  • SPSrinivasan Parthasarathy
    Srinivasan Parthasarathy
  • ASArvind Srinivasan
    Arvind Srinivasan

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.

This publication has 13 references indexed in Scilit: