Connected Dominating Set Algorithm Study In Ad Hoc Networks

Ad Hoc is a special type of wireless mobile network in which a collection of mobile hosts with wireless network interfaces forms a temporary network, without the aid of any established infrastructure or centralized administration. In Ad Hoc network all routing and network management functions must be performed by ordinary nodes. Due to the features of dynamic topology, multi-hop communication, and strict resource limitations, Ad Hoc routing becomes the most challenge problem. Almost all existing topology-based routing protocols involve the global flooding, which suffers from the notorious broadcast storm problem. This causes high protocol overhead and interference to ongoing traffics. Inspired by the physical backbone in the wired network, many researchers proposed the concept of virtual backbone infrastructure, which organizes the hierarchical structure of ordinary nodes to achieve scalability and efficiency.In order to achieve that, new algorithms have emerged that rely on a virtual network infrastructure, which organizes ordinary nodes into a hierarchy. The construction of this infrastructure is the primary application of Connected Dominating Sets (CDSs) in wireless networks. A CDS can create a virtual network backbone for packet routing and control. Messages can be routed from the source to a neighbor in the dominating set, along the CDS to the dominating set member closest to the destination node, and then finally to the destination. In this dissertation, the dominating set theory is well studied and the recently proposed CDS (Connected Dominating Set) construction algorithm is analyzed. In order to resolve the problems described above, a new improved algorithm is proposed.When evaluating a CDS algorithm, there's four parameters show the performance: performance bounds, degree of localization, time and message complexities, and stability with respect to nodal movement.The state of host's power, host's degree, and its mobility plays an important role in keeping stability of a virtual backbone. With a view to this feature,the paper introduces a simple and efficient heuristic algorithm for calculating the virtual backbone by seeking a minimum connected dominating set with minimal ' weight. It gives the rule how to calculate the weight of the nodes. The minimality of the weight-based choice of backbone nodes guarantees that the most suitable nodes have been chosen for the role of backbone nodes so that they can properly coordinate all the other nodes and keep stability of the virtual backbone in the network. It also gives a simple method how to maintenance the CDS when the topology changes. The analysis shows that the algorithm has better performance than some others. The minimality of the virtual backbone is assured by designing optimization algorithm. As a result, it can effectively decrease the overhead of control packets dissemination.