A Constant Approximation Algorithm for Interference Aware Broadcast in Wireless Networks

Broadcast protocols play a vital role in multihop wireless networks. Due to the broadcast nature of radio signals, a node´s interference range can be larger than its transmission range, i.e., it can interfere with other node´s reception even if the latter is not within its transmission range. To design an efficient broadcast protocol, both the collision and the interference among multiple transmissions must be addressed. However, most of the previous works on wireless broadcast protocols either treated interference in the same way as collision or did not consider interference at all. In this paper, we study a more general model in which interference is distinguished from collision, and propose a simple and yet efficient interference and collision free broadcast protocol. Our objective is to minimize the makespan, i.e., the earliest time such that every node receives the message. By exploiting the geometry property of the nodes that interfere with each other, we show that our algorithm is a constant approximation algorithm, it guarantees to deliver the message to all nodes within a small constant factor of the optimal makespan. We apply our algorithm under both the unit disk graph model and the more realistic radio irregularity model. The experimental results show that our algorithm consistently outperforms the previous algorithms.