Optimal gathering in radio grids with interference

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 dI or less. A round is a set of compatible (i.e., 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 dI=2k−1 is odd, then the number of rounds is k(N−1)−ck where N is the number of nodes and ck is a constant that depends on k. If dI=2k is even, then the number of rounds is where 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.