CHAPTER 19: Information Spreading in Dynamic Networks: An Analytical Approach

Sensor networks is one of the most relevant concrete examples of dynamic networks. Their dynamic behaviour 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 [16, 15, 18, 17, 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 view. Does the dynamic unknown behaviour of sensor networks always slow-down the speed of information spreading? Which is the real impact of this dynamic behaviour on the completion time of some basic communication protocols? Can unknown random node-mobility be exploited to asymptotically speed-up information spreading? This new general approach provides some clean mathematical answers to the above fundamental questions.