Distributed local broadcasting algorithms in the physical interference model

Abstract

Given a set of sensor nodes V where each node wants to broadcast a message to all its neighbors that are within a certain broadcasting range, the local broadcasting problem is to schedule all these requests in as few timeslots as possible. In this paper, assuming the more realistic physical interference model and no knowledge of the topology, we present three distributed local broadcasting algorithms where the first one is for the asynchronized model and the other two are for the synchronized model. Under the asynchronized model, nodes may join the execution of the protocol at any time and do not have access to a global clock, for which we give a distributed randomized algorithm with approximation ratio O(log n).