Wireless Network Weakly Connected Dominating Set Construction Algorithm

In recent years, the scope of wireless network's application is getting broader. But ordinary wireless networks like Ad-hoc network and so on are infrastructureless. This feature makes them different from the wired infrastructure networks. Wired networks are not energy supply limited which must be considered in wireless networks. Therefore building a special virtual backbone in the ordinary wireless networks to take charge of routing is important for the wireless equipment charged by battery power and the development of wireless network.Dominating set (DS) as a backbone network has already been widely used in the wireless networks to select the active nodes. DS with all disconnected nodes is a minimum independent set. In order to turn a DS to the virtual backbone to take on topology control, searching, broadcasting, and node covering, many researchers have done a lot of works about the methods of employing the connected dominating set as a backbone network. But a lot of connecting nodes must be added to maintain the connection of the DS which increases the amount of active nodes and energy consumption. Thus by relaxing the connecting requirement of DS, we could decrease the number of nodes in DS. And the method of using weakly connected dominating set (WCDS) as the backbone network in the wireless networks is proposed.This thesis proposes two methods of constructing WCDS separately from centralized algorithm and distributed algorithm based on previous works. For the centralized algorithm, we construct the WCDS with the method of edge dominating set. And the time complexity of this algorithm is O(|N|+|E|). At the same time we proposed two pruning strategies in guaranty of the WCDS's connection and the domination to reduce the size of WCDS we construct. As to the distributed algorithm, we propose a construct strategy based on the time competition for the WCDS in the wireless networks. And this distributed algorithm doesn't need a global node but decides which nodes are the dominators by their priority. The complexity of the algorithm is also O(|N|+|E|). We prove the correctness of both algorithms from theory and show the effectiveness of them by simulation. Compared to existent results, the algorithms we proposed produce weakly dominating sets with smaller size.