Communication in dynamic radio networks

We study the completion time of distributed broadcast protocols in dynamic radio networks. The dynamic network is modelled by means of adversaries: we consider two of them that somewhat are the extremal cases. We first analyze the weakest one, i.e., an oblivious, memoryless random adversary. At each time slot t, a graph Gt is selected according to the well-known random graph model Gn,p. We derive a randomized protocol that, on input nand p, completes broadcasting in O(logn) time. Then, we prove that any randomized protocol has (logn)completion time. When p is unknown, we present an oblivious homogeneous version of the Bar Yehuda-Goldreich-Itai's randomized protocol having O(log2n) completion time and we prove a lower bound (log 2 n/loglogn) that holds for any randomized oblivious homogeneous protocol. We emphasize that the above (poly-)logarithmic upper bounds also hold when random graphs are sparse and disconnected, i.e., for p=o(lnn/n). We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). Up to now, it is not even known whether finite expected completion time is achievable against this adversary. We present a simple randomized protocol that works in O(n 2/log n) completion time. This bound is then shown to be optimal. Copyright © 2007 ACM.