Optimal gathering protocols on paths under interference constraints

We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d≥1d≥1, which implies that nodes within distance dd in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any dd in the first case, and for 1≤d≤41≤d≤4, in the second case.