A Contention Aware Connected Dominating Set Construction Algorithm for Wireless Ad Hoc Networks
The nodes in wireless ad hoc networks frequently need to broadcast messages for route discovery and other services. The naive flooding requires every node to forward a message exactly once and causes serious performance bottleneck due to redundant traffic, contention, and collision.One convenient solution to overcome this problem is to construct a connected dominating set (CDS) as virtual backbone. Several centralized and distributed algorithms have been designed to compute CDS in order to reduce the number of rebroadcasts. However, none of the approaches aim at minimizing contentions. Contention is a phenomenon that occurs when a group of nodes want to transmit over a shared channel. During contention only one node gets access to the channel and the others defer their transmission for a later time. In this paper, a new heuristic dubbed as Contention Aware Connected Dominating Set (CACDS) has been proposed to construct a CDS that intelligently selects the nodes to reduce contention. A centralized algorithm has been deduced first to construct CDS using the global topology information. Since it is difficult to gather the entire topology information, a distributed counterpart has also been presented where a node selects a subset of nodes from its immediate neighbors as forwarding nodes based on 2 hop neighborhood information and reduces contention. Experimental results show that proposed heuristics significantly reduce contention and outperform other state of the art algorithms in minimizing contention with a little increase in number of forwarding nodes.
2018 14th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)