Information Spreading in Stationary Markovian Evolving Graphs

被引:44
作者
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
关键词
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
相关论文
共 32 条
[1]  
[Anonymous], 1995, Reversible markov chains and random walks on graphs
[2]  
[Anonymous], EVOLUTION NETWORKS
[3]  
[Anonymous], 2007, P IEEE INT S WORLD W
[4]  
[Anonymous], 1996, Mobile Computing
[5]  
Avin C, 2008, LECT NOTES COMPUT SC, V5125, P121, DOI 10.1007/978-3-540-70575-8_11
[6]  
BANSAL N, 2003, P 22 IEEE INFOCOM
[7]   Parsimonious Flooding in Dynamic Graphs [J].
Baumann, Herve ;
Crescenzi, Pierluigi ;
Fraigniaud, Pierre .
PODC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2009, :260-269
[8]  
Brauer F., 2008, Mathematical epidemiology, V1945
[9]   A survey of mobility models for ad hoc network research [J].
Camp, T ;
Boleng, J ;
Davies, V .
WIRELESS COMMUNICATIONS & MOBILE COMPUTING, 2002, 2 (05) :483-502
[10]   Optimal controlled flooding search in a large wireless network [J].
Chang, NB ;
Liu, MY .
Proceedings of the Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, 2005, :229-237