Fast construction of broadcast scheduling and gossiping in dynamic ad hoc networks

Authors:

• Krzysztof Krzywdziński

Abstract

This paper studies the minimum latency broadcast schedule (MLBS) problem in ad hoc networks represented by unit disk graphs. In our approach we use an algorithm, which does not need BFS tree. We introduce a construction, which does not depend on a source, can be found in constant number of synchronous rounds, uses only short messages and produces broadcast schedule with latency at most 258 times optimum. The advantage of our construction over known algorithms is its ability to adapt fast to the changes in the network, such as adding, moving or deleting vertices (even during the broadcasting). We also study the minimum-latency gossiping (all-to-all broadcast) problem in unit disk graphs. Our algorithm is the best result for gossiping in unit disk graph in unbounded-size messages model. Since our construction of broadcast scheduling does not depend on the source, it may be also used to solve other problems concerning broadcasting in unit disk graphs, such as single source multiple message broadcasting and multi channel broadcast scheduling. © 2010 IEEE.