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
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Type de document :
Communication dans un congrès
20th Anniversary of Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Aug 2017, TOKYO, Japan. 〈http://www.jcdcgg.u-tokai.ac.jp/〉
Liste complète des métadonnées

Contributeur : Jean-Claude Bermond <>
Soumis le : vendredi 21 décembre 2018 - 12:37:53
Dernière modification le : dimanche 23 décembre 2018 - 01:22:47


abstract-final2017 .pdf
Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01963492, version 1


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. 〈http://www.jcdcgg.u-tokai.ac.jp/〉. 〈hal-01963492〉



Consultations de la notice


Téléchargements de fichiers