Gossiping with interference in radio ring 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 : In this paper, we study the problem of gossiping with interference constraint in radio 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 message to every other node in the network. We focus on the case where the transmission network is a ring network that is a node has 2 neighbors and can only transmit to its neighbors (such an action is named a call). We consider synchronous protocols where it takes one unit of time (step) to transmit a unit-length message. During one step we suppose that a node cannot send and receive (half duplex model). Moreover communication is subject to interference constraints. We model them by a fixed integer dI ≥ 1, which implies that nodes within distance dI from a sender in the network cannot receive messages from another node. Here we focus on the case dI = 1, which implies that if a node receives a message from one of its neighbors, its other neighbor cannot send at the same time. A round consists of a set of non-interfering (or compatible) calls and uses one step. We solve completely the problem for ring networks, with unit length messages and dI = 1 by giving the minimum running time (makespan) of a gossiping protocol that is the minimum number of rounds needed to complete the gossiping. We first show lower bounds and then give gossiping algorithms which meet these lower bounds and so are optimal.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-02424099
Contributor : Jean-Claude Bermond <>
Submitted on : Thursday, December 26, 2019 - 4:55:40 PM
Last modification on : Monday, January 13, 2020 - 3:22:44 PM

File

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

Identifiers

  • HAL Id : hal-02424099, version 1

Collections

Citation

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

Share

Metrics

Record views

99

Files downloads

197