Research On Connected Dominating Set Algorithm In AdHoc Sensor Networks

Ad Hoc sensor network is a kind of large-scale?self-organization?no infrastructure to support and other features network. It can be applied to various fields and has important practical significance. The network uses connected dominating set as a virtual network backbone in order to perform data aggregation and network communication, which performing broadcast networks and routing. Aiming to build minimum connected dominating set in the Ad Hoc sensor network, this paper carried out the following studies:we obtained a better way to solve the set of currently connected dominating effect which is based on the two-stage approach by analyzing existing algorithm. So we proposed three improved algorithm for that.For the first phase—MIS stage, this paper analyzes the existing algorithms based on covering collaborative. Such thought of collaborative cover algorithm can make the problem closer to the optimal solution, but it also reduces the coverage efficiency. This paper improve this with the new dominator option:selecting a dominator from the dominator of the three-hop neighbor node under the current node preferentially. If there not exists, selecting next node domination from the two-hop neighbor node in order to cover as little as possible, which increases coverage efficiency.For the second phase—Steiner tree construction phase, most algorithms use the greedy way to find Steiner node. Such algorithm is simple but easy to fall into local optima. This paper improve this:the choice of Steiner nodes is added the weights for the corresponding process and the detection processing phase in order to detect the presence of redundant nodes. We proposed two improved Steiner tree algorithm--IK-ST algorithm and ML-ST algorithm and reduce the size of the disposable set further.In the simulation experiment, the paper first compares the IC-M1S algorithm and the algorithm proposed by Rajiv Misra by comparing the MIS number of nodes obtained to measure the performance. Then optimize the Steiner tree building phase in Rajiv Misra algorithm by IK-ST and ML-ST Algorithm by comparing the number of Steiner nodes obtained to measure the performance. The results show that the proposed algorithm optimization algorithms than previously has been greatly improved dominate the set scale.