Gathering algorithms on paths under interference constraints

Description

We study the problem of gathering information from the nodes of a multi-hop radio network into a pre-determined destination node under interference constraints which are modeled by an integer d 1, so that any node within distance d of a sender cannot receive calls from any other sender. A set of calls which do not interfere with each other is referred to as a round. We give algorithms and lower bounds on the minimum number of rounds for this problem, when the network is a path and the destination node is either at one end or at the center of the path. The algorithms are shown to be optimal for any d in the rst case, and for 1 d 4, in the second case.

Abstract

International audience

Additional details