HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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

Ralf Klasing 1 Nelson Morales 1 Stéphane Pérennes 1
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.
Document type :
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:55:28 PM
Last modification on : Friday, February 4, 2022 - 3:19:54 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:30:16 PM


  • HAL Id : inria-00070575, version 1



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


Files downloads