Abstract:

We propose a minimum connected dominating set (MCDS) construction algorithm called static wireless networks’ minimum connected dominating set (SWNMCDS) based on multiple spanning trees and sub networknode degree united weight for static wireless networks. At first, a probability p is set, and every node randomly generates a probability. The nodes whose generated probability is less than p become root node candidates. The root node candidates within two hops exchange information with each other to determine the final root nodes. Based on the node weight, the root nodes generate multiple connected trees respectively. All the connected trees are connected with each other into a minimum connected dominating set based on the selected connected nodes according to the sub networknode degree weight. Analysis results show that the upper bound of the performance ratio is 2β(2+H(Δ)), and the time complexity as well as the message complexity is O(Δ2), where Δ is the size of the biggest one hop neighbor set, and β  is the number of spanning trees. Compared with the traditional algorithm MCDS, the SWNMCDS has a smaller connected dominating set.

Key words: multiple spanning trees;sub network-node degree united weight;minimum connected dominating set;static wireless network