Randomized Multi-Source Broadcast Protocols in Multi-Hop Radio Networks

Abstract

In [LBA93], a suite of randomized broadcast protocols was presented for the problem of broadcasting a message in arbitrary multi-hop radio networks. These protocols improved upon that of Bar-Yehuda et al. in most of the typical cases. Unfortunately, in those protocols it is assumed that only a single broadcast by a single node is in progress at any point in time. Hence, those protocols are of limited use in practice. In this paper, we present a suite of randomized multi-source broadcast protocols in multi-hop radio networks, in which more than one broadcast can be in progress at any point in time. The protocols are compared with each other in several typical cases.