# On the Complexity of Bandwidth Allocation in Radio Networks with Steady Traffic Demands

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper we define and study a call scheduling problem that is motivated by radio networks. In such networks the physical space is a common resource that nodes have to share, since concurrent transmissions cannot be interfering. We study how one can satisfy steady bandwidth demands according to this constraint. This leads to the definition of a call scheduling problem. We show that it can be relaxed into a simpler problem: The call weighting problem, which is almost a usual multi-commodity flow problem, but the capacity constraints are replaced by the much more complex notion of non interference. Not surprisingly this notion involve independent sets, and we prove that the complexity of the call weighting problem is strongly related to the one of the independent set problem and its variants (max-weight, coloring, fractional coloring). The hardness of approximation follows when the interferences are described by an arbitrary graph. We refine our study by considering some particular cases for which efficient polynomial algorithm can be provided: the Gathering in which all the demand are directed toward the same sink, and specific interference relations: namely those induced by the dimension $1$ and $2$ Euclidean space, those cases are likely to be the practical ones.
Keywords :
Document type :
Reports
Domain :

Cited literature [22 references]

https://hal.inria.fr/inria-00070575
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:55:28 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:30:16 PM

### Identifiers

• HAL Id : inria-00070575, version 1

### Citation

Ralf Klasing, Nelson Morales, Stéphane Pérennes. On the Complexity of Bandwidth Allocation in Radio Networks with Steady Traffic Demands. [Research Report] RR-5432, INRIA. 2004, pp.27. ⟨inria-00070575⟩

Record views