Study on enhancement of dominating sets in Ad Hoc wireless networks

Abstract

An essential component of effective use of Ad Hoc Wireless networks is proper utilization of available resources and network stability. There has been a recent increase of interest in Ad Hoc networks, partly due to the fact that Ad Hoc networks can be implemented without requiring any support from existing wired backbone or costly hardware setup. The effective utilization of the power of the Ad Hoc networks lies in scalability, stability, maintainability and rapid convergence of these networks. The route detection and route formation in the Ad Hoc networks should be done instantaneously. Performing effective route detection on such environments can be best achieved when the broadcasting is improved and the redundancy in route detection is removed. In this thesis work, a cluster based algorithm as well as a localized algorithm for Connected Dominating Set formation have been proposed. The Clustering algorithm forms disjoint logical groups of nodes with a lead node as head of the cluster. The cluster head takes part in the routing and has additional tasks of cluster maintenance. The clusters form a logical backbone and the Route search space is limited to the no. of clusters. But, the method forms suboptimal routes. The Connected Dominating Set based algorithm forms a logical backbone of connected gateways. The broadcast packets are retransmitted by these nodes. The routes are computed by shortest path algorithm. Changes in the backbone does not have impact on the ongoing communications. New routes are computed upon failure of existing routes. The results obtained using this algorithm are compared with other methods across a range of different scenarios with 100 nodes upon a simulation area of 100 X 100 twips. The Connected Dominating Set algorithm distributes the dominating nodes equally along the entire range while others are being biased towards higher “id” nodes. The Connected Dominating Set based algorithm is excelling the cluster algorithm in Search space size.