An approximation algorithm for connected dominating set in wireless ad hoc network

The dominating set problem in graphs asks for a minimum size subset of nodes with the following property: each node is required to either to be in the dominating set, or adjacent to some nodes in the domination set. The connected dominating set is a dominating set which is connected. The connected dominating set in unit-disk graph has been proposed as virtual backbone or spine for wireless ad hoc network. This paper propose a simple and effective distributed algorithm namely INMCDS algorithm for wireless ad hoc network, By this algorithm, the rout searching of wireless network is centralized in connect dominating set. The simulation experiment show that the algorithm we proposed could construct a proximately optimal minimum connect dominating set speedily. For the network topology changed as several node is disabled, the localized maintaining algorithm could construct a new MCDS speedily by the information of neighbouring nodes, so as to resolve the problem very well.