Combination of Relative Neighborhood Graph and Forbidden Set in the Design of Distributed Broadcast Algorithms for Wireless Ad Hoc Networks

A wireless ad hoc network typically comprises of nodes with energy supplied by batteries. Hence, energy conservation is crucial to extending the lifetimes of individual nodes and the network as a whole. In topology control type of broadcast algorithms, the distance between neighbors is used to adjust the transmission power to reduce energy consumption. One such example is based on relative neighborhood graph (RNG). In RNG each node maintains a list of relative neighbors and the information is employed to construct a broadcast path. In this paper, distributed broadcast algorithms are proposed that incorporate the notion of forbidden set in RNG to improve the performance. The key idea of forbidden set is to prohibit nodes with low remaining battery capacity from serving as rebroadcast nodes. Via this selection criterion, we can avoid the disruption of the broadcast path due to energy depletion at nodes with low energy capacity, thereby achieving the goal of elongating the lifetime of the broadcast path. Further power saving can be achieved by getting rid of redundant rebroadcasts. The procedure is described with illustrations. In particular, the removal of such redundancy is dependent on the source node. Simulation results confirm the improvement furnished by the proposed algorithms.