Information Spreading in Stationary Markovian Evolving Graphs

被引：45

作者：

Clementi, Andrea ^{[1
]}

Monti, Angelo ^{[2
]}

Pasquale, Francesco ^{[3
]}

Silvestri, Riccardo ^{[2
]}

机构：

[1] Univ Roma Tor Vergata, Dipartimento Matemat, Rome, Italy

[2] Univ Roma La Sapienza, Dipartimento Informat, Rome, Italy

[3] Univ Salerno, Dipartimento Informat & Applicaz RM Capocelli, I-84100 Salerno, Italy

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2011年 / 22卷 / 09期

关键词：

Mobile ad hoc networks; flooding; random graphs;

D O I：

10.1109/TPDS.2011.33

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the stationary phase by analyzing the completion time of the flooding mechanism. We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs. Geometric Markovian evolving graphs where the Markovian behaviour is yielded by n mobile radio stations, with fixed transmission radius, that perform independent random walks over a square region of the plane. Edge-Markovian evolving graphs where the probability of existence of any edge at time t depends on the existence (or not) of the same edge at time t(-1). In both cases, the obtained upper bounds hold with high probability and they are nearly tight. In fact, they turn out to be tight for a large range of the values of the input parameters. As for geometric Markovian evolving graphs, our result represents the first analytical upper bound for flooding time on a class of concrete mobile networks.

引用

页码：1425 / 1432

页数：8