Broadcasting in dynamic radio networks

摘要

It is reasonable to claim that almost all major questions related to radio broadcasting can be considered closed as far as static networks are considered: the network never changes during the entire protocol's execution. On the other hand, theoretical results on communication protocols in any scenario where the network topology may change during protocol's execution (i.e. a dynamic radio network) are very few.In this paper, we present a theoretical study of broadcasting in radio networks having dynamic unknown topology. The dynamic network is modeled by means of adversaries: we consider two of them. We first analyze an oblivious, memoryless random adversary that can be seen as the dynamic version of the average-case study presented by Elsässer and Gasieniec in JCSS, 2006. We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). This is the dynamic version of the worst-case study provided by Bar-Yehuda, Goldreich and Itai in JCSS, 1992.In both cases we provide tight bounds on the completion time of randomized broadcast protocols.