THE WAVE EXPANSION APPROACH TO BROADCASTING IN MULTIHOP RADIO NETWORKS

In this paper we propose an algorithm for efficient communication between neighbors in multihop radio networks. The algorithm guarantees a bound on the transmission efficiency in a radio channel for arbitrary topology. The algorithm can be embedded in protocols for solving basic network problems such as broadcast, multicast, leader election, or finding shortest paths. We then specifically address the problem of bounded-time broadcasting utilizing the proposed algorithm. In the presented polynomial solution, we view the process of spreading information over the network as the expansion of a wave caused by a point of disturbance. The broadcast is originated at a source node, and is accomplished in repeated transmission periods, emulating a wave progressing away from the source. Using the proposed algorithm, a subset of potential transmitters is selected in each period so that a tightly bound proportion of potential receivers receive the transmission without collisions, guaranteeing a high level of spatial-reuse in the broadcast process. The spatial-reuse and the collision-free transmission properties of the algorithm, allow us to develop a broadcasting protocol with bounded delays shown to be better than in other currently known solutions. Specifically, the presented protocol gives a bound of r In2 N/r in a network consisting of N nodes with radius r. This result is at most logarithmically worse that the optimum given by at least r.