Thumbnail
Access Restriction
Open

Author Bermond, Jean-Claude ♦ Kodate, Takako ♦ Yu, Joseph
Source Hyper Articles en Ligne (HAL)
Content type Text
File Format PDF
Language English
Subject Keyword gossiping ♦ radio networks ♦ ring ♦ interference ♦ info ♦ Computer Science [cs]/Discrete Mathematics [cs.DM] ♦ Computer Science [cs]/Data Structures and Algorithms [cs.DS] ♦ Computer Science [cs]/Networking and Internet Architecture [cs.NI]
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.
Educational Use Research
Learning Resource Type Proceeding