Leveraging channel diversity to gain efficiency and robustness for wireless broadcast

Abstract

This paper addresses two primary questions: (i) How much faster can we disseminate information in a large wireless network if we have multiple communication channels available (as compared to relying on only a single communication channel)? (ii) Can we still disseminate information reliably, even if some subset of the channels are disrupted? In answer to the first question, we reduce the cost of broadcast to O(log log n) rounds/hop, approximately, for sufficiently many channels. We answer the second question in the affirmative, presenting two different algorithms, while at the same time proving a lower bound showing that disrupted channels have unavoidable costs. © 2011 Springer-Verlag.