Contention aware connected dominating set construction algorithm for wireless multi-hop networks

Abstract

Efficient data dissemination among a set of mobile hosts is one of the most important concerns in wire-less multi-hop networks. Broadcast and Multi-cast are two techniques that are being widely used for communicating among a group of nodes. The elementary flooding used for broadcasting requires each node to participate in forwarding task of a message that leads to notorious broadcast storm problem caus-ing redundant transmissions, contentions and collisions. One convenient promising solution to overcome this problem is to construct a virtual backbone and connected dominating set (CDS). Several centralized (e.g. Minimum Connected dominating set (MCDS)) and distributed (e.g. Dominant Pruning (DP)) algo-rithms have been designed to compute CDS in order to reduce the number of rebroadcasting. 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 thesis, we propose a new heuristic dubbed as Contention Aware Connected Dominating Set (CACDS) to construct a CDS that will intelligently select the nodes to reduce contention. A centralized algorithm has been deduced first to construct CDS using the global topology information of a wireless network. 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 infor-mation and reduces contention. We have shown the detail analysis of how the proposed heuristics work better in terms of contention minimization compared to the state-of-the-art algorithms for constructing CDS. Though the total number of transmissions increases in the proposed approaches but the number of contentions among the forwarding nodes has been significantly reduced. In centralized environment, with the increase of 0-5% forwarding nodes, our heuristic generates almost 90-100% contention free CDS. In distributed environment, we need to increase the forwarding nodes by 1-5% to mitigate almost 4-19% contention in CDS.