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

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. College of Computing Georgia Institute of Technology Atlanta, Georgia 30332--0280 Author's current address: Bellcore, P.O. Box 7040, Red Bank, NJ 07701-5699. 1 Introduction A radio network is a collection of radios that communicate with each other over radio channels. If all units in a network can hear each other, the r..