### Abstract

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 (d_{min}, 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 language | English (US) |
---|---|

Title of host publication | INFOCOM 2008 |

Subtitle of host publication | 27th IEEE Communications Society Conference on Computer Communications |

Pages | 1669-1677 |

Number of pages | 9 |

DOIs | |

State | Published - Sep 15 2008 |

Externally published | Yes |

Event | INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications - Phoenix, AZ, United States Duration: Apr 13 2008 → Apr 18 2008 |

### Publication series

Name | Proceedings - IEEE INFOCOM |
---|---|

ISSN (Print) | 0743-166X |

### Other

Other | INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications |
---|---|

Country | United States |

City | Phoenix, AZ |

Period | 4/13/08 → 4/18/08 |

### ASJC Scopus subject areas

- Computer Science(all)
- Electrical and Electronic Engineering

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

## Cite this

*INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications*(pp. 1669-1677). [4509748] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFOCOM.2007.153