Efficient construction of connected dominating set in wireless ad hoc networks

Connected dominating set based routing is a promising approach for enhancing the routing efficiency in wireless ad hoc networks. However, finding the minimum dominating set in an arbitrary graph is a NP-hard problem. We propose a simple and efficient distributed algorithm for constructing a connected dominating set in wireless ad hoc networks with time complexity O(n) and message complexity O(nlog n). The dominating set generated with our algorithm can be more reliable and load balanced for routing as compared with some well-known algorithms. The simulation results demonstrate that our algorithm outperforms previous work in terms of the size of the resultant connected dominating set.