Deterministic collision free communication despite continuous motion

We present a deterministic solution for nodes in a mobile wireless ad hoc network to communicate reliably and maintain local neighborhood information. The nodes are located on a two-dimensional plane and may be in continuous motion. In our solution we tile the plane with hexagons. Each hexagon is assigned a color from a finite set of colors. Two hexagons of the same color are located sufficiently far apart so that nodes in these two hexagons cannot interfere with each other’s broadcasts. Based on this partitioning we develop a periodic deterministic schedule for mobile nodes to broadcast. This schedule guarantees collision avoidance. Broadcast slots are tied to geographic locations instead of nodes and the schedule for a node changes dynamically as it moves from tile to tile. The schedule allows nodes to maintain information about their local neighborhood. This information in turn is used to keep the schedule collision-free. We demonstrate the correctness of our algorithm, and discuss how the periodic schedule can be adapted for different scenarios. The periodic schedule, however, does not address the problem of initial neighbor discovery at start-up. We give a separate algorithm for this problem of initially discovering nodes present within communication range at start-up.