Localized broadcasting with guaranteed delivery and bounded transmission redundancy

The common belief is that localized broadcast algorithms are not able to guarantee both full delivery and a good bound on the number of transmissions. In this paper, we propose the first localized broadcast algorithm that guarantees full delivery and a constant approximation ratio to the minimum number of required transmissions in the worst case. The proposed broadcast algorithm is a self-pruning algorithm based on one round of information exchange. Using the proposed algorithm, each node determines its forwarding status in O(Delta(G) log Delta(G)), where Delta(G) is the maximum node degree of the network. By extending the proposed algorithm, we show that localized broadcast algorithms can achieve both full delivery and a constant approximation ratio to the optimum solution with message complexity O(N), where N is the total number of nodes in the network and each message contains a constant number of bits. We also show how to save bandwidth by reducing the size of piggybacked information. Finally, we relax several system-model assumptions, or replace them with practical ones, in order to improve the practicality of the proposed broadcast algorithm.