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 : In this paper, we study the problem of gossiping with interference constraint in radio chain 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 The radio chain network is modeled as a symmetric dipath P n , where the vertices represent the nodes and the arcs represent the possible communications. A call (s, r) is defined as the transmission from the node s to the node r, in which s is the sender and r is the receiver and (s, r) is an arc of the dipath. The network is assumed to be synchronous and the time is slotted into steps. We suppose that each device is equipped with a half duplex interface; so, a node cannot both receive and transmit during a step. Interference model Furthermore, communication is subject to interference constraints. We use a binary asymmetric model of interference based on the distance in the communication digraph like the ones used in [1, 2, 6]. Let d(s, r) denote the distance, that is the length of a shortest directed path, from s to r in P n and d I be a non negative integer. We assume that when a node s transmits, all nodes v such that d(s, v) ≤ d I are subject to the interference from s transmission. So two calls (s, r) and (s ′ , r ′) do not interfere if d(s, r ′) > d I and d(s ′ , r) > d I. During a given step only non interfering (or compatible) calls can be done and we will define a round as a set of such compatible calls. We focus here on the case where d I = 1. Main result This problem has been studied in general in [5] where approximation results are given (see also the survey [4]). In [3] we solved completely the gossiping problem in radio ring networks within this model. Here we determine exactly the minimum number of rounds R needed to achieve a gossiping when transmission network is a dipath P n on n nodes and the interference distance is d I = 1. We first prove the lower bound and then give gossiping algorithms which meet this lower bound. Theorem 1 The minimum number of rounds R needed to achieve a gossiping in a chain network P n (n ≥ 3), with the interference model d I = 1 is : R = { 3n − 5 n ≥ 4 5 n = 3
Type de document :
Communication dans un congrès
21th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Sep 2018, Manila, Philippines
Liste complète des métadonnées

https://hal.inria.fr/hal-01960744
Contributeur : Jean-Claude Bermond <>
Soumis le : mercredi 19 décembre 2018 - 15:21:42
Dernière modification le : jeudi 7 février 2019 - 12:48:01

Fichier

abstractrev.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01960744, version 1

Collections

Citation

Jean-Claude Bermond, Takako Kodate, Joseph Yu. Gossiping with interference in radio chain networks. 21th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Sep 2018, Manila, Philippines. 〈hal-01960744〉

Partager

Métriques

Consultations de la notice

52

Téléchargements de fichiers

22