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 ring networks. Gossiping (or total exchange information) is a protocol where each node in the network has a message and wants to distribute its own message 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. Transmission model A radio network consists of communication devices equipped with an half duplex interface. The network is assumed to be synchronous and the time is slotted into rounds. The half-duplex hypothesis implies that a node can transmit or receive at most one message during a round. The network is modeled as a digraph, where the vertices represent the nodes and the arcs represent the possible communications. The messages are transmitted through the communication over the arcs and we will denote a call such a transmission. Interference model We use a binary asymmetric model of interference based on the distance in the communication digraph like the ones used in [1, 2, 5]. Let d(u,v) denote the distance, that is the length of a shortest directed path, from u to v in G and dI be a non negative integer. We assume that when a node u transmits, all nodes v such that d(u,v) ≤ dI are subject to the interference from u’s transmission. So two calls (u, v) and (u′, v′) do not interfere if d(u, v′) > dI and d(u′,v) > dI. This problem has been studied in [4] where approximation results are given (see also the survey [3]). Here we focus on the case where the transmisson network is a ring network Cn on n nodes with the interference distance dI = 1. We presented some partial results at JCDCG^G 2013, and we have now solved completely the gossiping problem by giving the minimum running time (makespan). We show lower bounds and then give gossiping algorithms which meet these lower bounds and so are optimal.
Complete list of metadatas

https://hal.inria.fr/hal-01963492
Contributor : Jean-Claude Bermond <>
Submitted on : Friday, December 21, 2018 - 12:37:53 PM
Last modification on : Thursday, February 7, 2019 - 12:48:01 PM
Long-term archiving on : Friday, March 22, 2019 - 2:28:51 PM

File

abstract-final2017 .pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01963492, version 1

Citation

Jean-Claude Bermond, Takako Kodate, Joseph Yu. Gossiping with interference in radio ring networks. 20th Anniversary of Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Aug 2017, TOKYO, Japan. ⟨hal-01963492⟩

Share

Metrics

Record views

62

Files downloads

55