A Neural Network Model to Minimize the Connected Dominating Set for Self-Configuration of Wireless Sensor Networks

摘要

A wireless ad hoc sensor network consists of a number of sensors spreading across a geographical area. The performance of the network suffers as the number of nodes grows, and a large sensor network quickly becomes difficult to manage. Thus, it is essential that the network be able to self-organize. Clustering is an efficient approach to simplify the network structure and to alleviate the scalability problem. One method to create clusters is to use weakly connected dominating sets (WCDSs). Finding the minimum WCDS in an arbitrary graph is an NP-complete problem. We propose a neural network model to find the minimum WCDS in a wireless sensor network. We present a directed convergence algorithm. The new algorithm outperforms the normal convergence algorithm both in efficiency and in the quality of solutions. Moreover, it is shown that the neural network is robust. We investigate the scalability of the neural network model by testing it on a range of sized graphs and on a range of transmission radii. Compared with Guha and Khuller's centralized algorithm, the proposed neural network with directed convergency achieves better results when the transmission radius is short, and equal performance when the transmission radius becomes larger. The parallel version of the neural network model takes time $O(d)$ , where $d$ is the maximal degree in the graph corresponding to the sensor network, while the centralized algorithm takes $O(n^2)$. We also investigate the effect of the transmission radius on the size of WCDS. The results show that it is important to select a suitable transmission radius to make the network stable and to extend the lifespan of the network. The proposed model can be used on sink nodes in sensor networks, so that a sink node can inform the nodes to be -n-na coordinator (clusterhead) in the WCDS obtained by the algorithm. Thus, the message overhead is $O({cal M})$, where ${cal M}$ is the size of the WCDS.