Abstract: Most of existing work are based on the concept of minimum connect dominating set(MCDS)，which is only target for minimizing the number of backbone nodes, but not take the real characteristics of nodes into account when constructing the backbone. In the way, some low performance nodes could be the bottleneck of the backbone. Selecting more capable nodes as candidates to construct a high performance backbone, a minimum connected dominating set with high node performance(MCDS-HNP) algorithm was proposed, and the approximation ratio of the proposed algorithm was also presented. The simulation results demonstrate that the MCDS-HNP algorithm achieves better backbone performance while maintaining approximately the same backbone size.

Key words: Ad hoc networks, Heterogeneous networks, Network backbone, Connected dominating set, Wireless networks