Bottleneck Analysis for Routing and Call Scheduling in Multi-hop Wireless Networks

Cristiana Gomes 1, * Stéphane Pérennes 1 Hervé Rivano 1
* Corresponding author
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 address the routing and call scheduling problem in which one has to find a minimum-length schedule of selected links in a TDMA (Time Division Multiple Access) based wireless network. As we deal with a multi-hop networks, these selected links represent a routing solution (paths) providing enough capacity to achieve the routers requirements of bandwidth. We present a cross-layer formulation of the problem that computes joint routing and scheduling. We use a branch-and-price algorithm to solve optimally the problem. A column generation algorithm is used to cope with the exponential set of rounds. The branch-and-bound algorithm provides mono-routing. We run experiments on networks from the literature, with different number of gateways. Experimental results as well as theoretical insights let us conjecture that the bottleneck region analysis is enough to find the optimal solution. The bottleneck is usually the gateway considering almost uniform traffic. The \emph{integer round-up property} (IRUP) seems to hold for our problem.
Document type :
Reports
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00282200
Contributor : Cristiana Gomes <>
Submitted on : Monday, May 26, 2008 - 4:29:44 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Friday, May 28, 2010 - 6:24:19 PM

Files

INRIA_Report3.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00282200, version 1

Collections

Citation

Cristiana Gomes, Stéphane Pérennes, Hervé Rivano. Bottleneck Analysis for Routing and Call Scheduling in Multi-hop Wireless Networks. [Research Report] 2008, pp.11. ⟨inria-00282200⟩

Share

Metrics

Record views

390

Files downloads

280