Analysis On The Connected Dominating Set Problem In Wireless Sensor Network

With the rapid development of sensor technology and a wide variety of applications of wireless sensor network (WSN), wireless sensor network has been extensively studied at home and abroad. Besides, in WSN, there is no fixed or pre-defined infrastructure and the nodes need to carry other nodes'traffic and are vulnerable to fail. It is desire to consider a multi-connected wulti-dominating set which functions a fault tolerant virtual backbone to make sure that many sensors monitor the same data and the data reports via different paths.Considering many good features of wireless sensor. network and connected dominating set, the minimum multi-connected multi-dominating set problem is studied in this paper. Firstly, we describe and analysis some effective algorithms to the connected dominating set problem. Secondly, we present an approximation algorithm and a new analysis method using the graph theory to the minimum k:-connected m-dominating set problem in a simple disk graph in which the transmission ranges of all nodes in the WSN are not necessary equal according to the existing theoretical results as following. Our algorithm contains four steps which are constructing a connected dominating set, then a k-dominating set, then a k-connected k-dominating set and a k-connected m-dominating set in the end (k and m are positive integers and k is not bigger than m). We prove that there is an approximation ratio as well. Finally, we propose a new model that is the totally minimum m-connected k-dominating set problem in a simple disk graph in which the transmission ranges of all nodes in the WSN can be different (k and m are positive integers). We give a centralized approximation algorithm and a theoretical analysis using approximation theory and graph theory which results in a guaranteed approximation ratio.