Bounds for Communication in Wireless Grids

Joseph Peters, School of Computing Science, Simon Fraser University

In a wireless network, a transmission can be received by a node if it is close enough to the sender. However, transmissions can interfere with each other and the interference distance is typically greater than the reception distance. Efficient communication protocols in these networks minimize the time to move information without interference.

In this talk, I will describe optimal protocols for the problem of collecting information into a central node of a two-dimensional square or hexagonal grid graph. The optimality of the protocols is proved using a new lower bound technique that is an adaptation to a discrete environment of a method based on linear programming duality for continuous flows.

This is joint work with Jean-Claude Bermond, CNRS-INRIA-University of Nice.