Optimal Gathering in Radio Grids with Interference - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2011

Optimal Gathering in Radio Grids with Interference

Résumé

We study the problem of gathering information from the nodes of a radio network into a central node. We model the network of possible transmissions by a graph and consider a binary model of interference in which two transmissions interfere if the distance in the graph from the sender of one transmission to the receiver of the other is $d_I$ or less. A {\em round} is a set of non-interfering transmissions. In this paper, we determine the exact number of rounds required to gather one piece of information from each node of a square two-dimensional grid into the central node. If $d_I = 2k-1$ is odd, then the number of rounds is $k(N-1)-c_k$ where $N$ is the number of nodes and $c_k$ is a constant that depends on $k$. If $d_I = 2k$ is even, then the number of rounds is $(k+\frac{1}{4})(N-1)-c'_k$ where $c'_k$ is a constant that depends on $k$. The even case uses a method based on linear programming duality to prove the lower bound, and sophisticated algorithms using the symmetry of the grid and non-shortest paths to establish the matching upper bound. We then generalize our results to hexagonal grids.
Fichier principal
Vignette du fichier
journal.submitfinal.pdf (857.22 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00610038 , version 1 (24-07-2011)

Identifiants

  • HAL Id : inria-00610038 , version 1

Citer

Jean-Claude Bermond, Joseph Peters. Optimal Gathering in Radio Grids with Interference. 2011. ⟨inria-00610038⟩
162 Consultations
134 Téléchargements

Partager

Gmail Facebook X LinkedIn More