Optimal Gathering Algorithms in Multi-Hop Radio Tree-Networks with Interferences
Jean-Claude Bermond and Min-Li Yu
We study the problem of gathering information from the nodes of a multi-hop radio network into a pre-defined destination node under the interference constraints. In such a network, a message can only be properly received if there is no interference from another message being simultaneously transmitted. The network is modeled as a graph, where the vertices represent the nodes and the edges, the possible communications. The interference constraint is modeled by a fixed integer dI ≥ 1, which implies that nodes within distance dI in the graph from one sender cannot receive messages from another node. In this paper, we suppose that it takes one unit of time (slot) to transmit a unit-length message. A step (or round) consists of a set of non interfering (compatible) calls and uses one slot. We present optimal algorithms that give minimum number of steps (delay) for the gathering problem with buffering possibility, when the network is a tree, the root is the destination and dI = 1. In fact we study the equivalent personalized broadcasting problem instead.
Keywords: Radio networks, sensor networks, interferences, gathering, personalized broadcasting, data collection.