# Optimal Gathering in Radio Grids with Interference

Optimal Gathering in Radio Grids with Interference - Download this document for free, or read online. Document in PDF available to download.

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués 2 School of Computing Science

Abstract : 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 $kN-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.

Keywords : Radio communication interference grids gathering

Author: ** Jean-Claude Bermond - Joseph Peters - **

Source: https://hal.archives-ouvertes.fr/