Information Spreading in Dynamic Networks: An Analytical Approach

Sensor networks are one of the most relevant concrete examples of dynamic networks. Their dynamic behavior is mainly due to the presence of node/link faults and node mobility. The aim of this chapter is to survey a new approach to study such dynamic networks, recently introduced in [15–19]. The major novelty of this approach relies on two basic issues. 1. The dynamic network is modeled as an evolving graph whose topology changes at every time according to some law/adversary. Both worst-case adversarial scenarios and graphs that evolve randomly are deeply studied. 2. This new approach provides a general framework where it is possible to determine the speed of information spreading from an analytical point of view. Does the dynamic unknown behavior of sensor networks always slow down the speed of information spreading? What is the real impact of this dynamic behavior on the completion time of some basic communication protocols? Can unknown random node mobility be exploited to asymptotically speedup information spreading? This new general approach provides some clean mathematical answers to the above fundamental questions