Abstract: In Ad-hoc networks, a minimum connected dominating set (MCDS) can be used as a virtual backbone to improve the performance of source allocation and prolong the system lifetime. In this paper, we firstly proved a useful theorem about adjacent matrix Secondly, using the theorem and the relationship between maximum independent set and minimum dominating set,we proposed a fast approximation algorithm based on adjacent matrix for constructing MCDS in Ad-hoc networks. hhe correctness, complexity and approximation rate of the proposed algorithm were analyzed respectively. Simulation results show that new algorithm can efficiently and fast construct virtual backbone in Ad-hoc networks.

Key words: Ad-hoc networks, Maximal independent set, Adjacent matrix, Greedy strategy, Connected dominating set