Gossiping with interference in radio chain networks

Jean-Claude Bermond 1 Takako Kodate 2 Joseph Yu 3
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : IIn this paper, we study the problem of gossiping with neighboring interference con- straint in radio chain networks. Gossiping (or total exchange information) is a protocol where each node in the network has a message and is expected to distribute its own mes- sage to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and efficient algorithms that attain this makespan. We focus on the case where the transmission network is a chain (directed path or line) network. We consider synchronous protocols where it takes one unit of time (step) to transmit a unit-length message. During one step, a node receives at most one message only through one of its two neighbors. We suppose that during one step, a node cannot be both a sender and a receiver (half duplex model). Moreover we have neighboring interference constraints with which a node cannot receive a message if one of its neighbors is sending. A round consists of a set of non-interfering (or compatible) calls and uses one step. We solve completely the gossiping problem for Pn, the chain network on n nodes, and give an algorithm that completes the gossiping in 3n − 5 rounds (for n > 3), which is exactly the makespan.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-02424017
Contributor : Jean-Claude Bermond <>
Submitted on : Thursday, December 26, 2019 - 2:32:36 PM
Last modification on : Monday, January 13, 2020 - 3:22:04 PM

File

BKY19-hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02424017, version 1

Collections

Citation

Jean-Claude Bermond, Takako Kodate, Joseph Yu. Gossiping with interference in radio chain networks. 2019. ⟨hal-02424017⟩

Share

Metrics

Record views

102

Files downloads

184