Feasible rate allocation in wireless networks

Ramakrishna Gummadi, Kyomin Jung, Devavrat Shah, Ramavarapu Sreenivas

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Rate allocation is a fundamental problem in the operation of a wireless network because of the necessity to schedule the operation of mutually interfering links between the nodes. Among the many reasons behind the importance of efficiently determining the membership of an arbitrary rate vector in the feasibility region, is its high relevance in optimal cross layer design. A key feature in a wireless network is that links without common nodes can also conflict (secondary interference constraints). While the node exclusive model problem has efficient algorithms [8], it has long been known that this is a hard problem with these additional secondary constraints [1]. However, wireless networks are usually deployed in geographic areas that do not span the most general class of all graphs possible. This is the underlying theme of this paper, where we provide algorithms for two restricted instances of wireless network topologies. In the first tractable instance, we consider nodes placed arbitrarily in a region such that (a) the node density is bounded, and (b) a node can only transmit or interfere with other nodes that are within a certain limited radius. We obtain a simple (1 - ε) polynomial-time approximation scheme for checking feasibility (for any ε > 0). The second instance considers the membership problem of an arbitrary rate-vector in the feasible set, where the nodes are distributed within a slab of fixed width (there are no density assumptions). Specifically, the results in [13] are shown to extend to a much more general class of graphs, which we call the (dmin, d max) class of graphs, and this generalization is used to obtain a strongly polynomial time algorithm that decides membership of a rate-vector where the hosts are distributed within an infinite corridor with fixed cross-section.

Original languageEnglish (US)
Title of host publicationINFOCOM 2008
Subtitle of host publication27th IEEE Communications Society Conference on Computer Communications
Number of pages9
StatePublished - Sep 15 2008
Externally publishedYes
EventINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications - Phoenix, AZ, United States
Duration: Apr 13 2008Apr 18 2008

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


OtherINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications
Country/TerritoryUnited States
CityPhoenix, AZ

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Feasible rate allocation in wireless networks'. Together they form a unique fingerprint.

Cite this