Routing based on a minimum connected dominating set (MCDS) in ad hoc wireless networks is a promising approach

where the search space for a route is reduced to nodes in the set (also called gateway nodes).This paper introduces MWMCDS

a simple and efficient heuristic algorithm for calculating minimum connected dominating set with maximal weight in the topology graph G of an Ad hoc wireless network.The maximality of the weight-based choice of gateway nodes guarantees that the most suitable nodes have been chosen for the role of gateway nodes so that they can properly coordinate all the other nodes in the network.As a result

it can keep stability of the MCDS and provide a highly effective communication base for broadcast and routing operation in the whole network.Simulation resluts show that the proposed algorithm can ensure the maximality of sum of CDS' weight and the minimality of CDS' size.So the scheme can be potentially used in designing efficient routing algorithms based on a MCDS.