The Research On Constructing Virtual Backbone In Wireless Sensor Network

Wireless sensor network has intensive potential on military and other fields for its unique advantages. More attention is paid to it and the research to each aspect of sensor network is also an active field in current academe. Constructing virtual backbones in the wireless sensor network for the routing is a very hot spot. Because of the constrain of energy, memory and computation capacity, the failure of nodes will cause the failure of the whole network and some important node should be watched reliably in some occasion. So constructing a k-connected k-dominating set as the virtual backbone is necessary to balance efficiency and fault tolerance. Previous work in this area has focused on selecting a small virtual backbone for high efficiency. We propose to construct a connected dominating set as a virtual backbone algorithm to balance efficiency and fault tolerance in wireless sensor network.In some wireless sensor network, usually, there is a sink node to achieve the global information, such as topology control or the node location, and the size of the wireless sensor network is large, so this thesis proposes a centralized heuristic algorithm to construct 1-connected 1-dominating set using the global information from the sink node. To improve the efficiency of the network, thesis also proposes a centralized heuristic algorithm to construct 2-connected 2-dominating set. The algorithm runs on the sink node and the connected dominating set educed from the algorithm forms the virtual backbone of the network. Because the algorithm gets the global information and the information is general, the size of the connected dominating set got from the centralized heuristic algorithm is smaller than that of distributed heuristic algorithm.If a sink node does not exist in some wireless sensor network, and the size of the wireless sensor network is large, this thesis proposes a distributed heuristic algorithm to construct the connected dominating set using the local information of the network. The algorithm constructs 2-connected 2-dominating set. In the algorithm, any node is chosen to be the starting node and the state of the other nodes is determined. The algorithm only needs the local information of the network and responses to the dynamic topology information, so the characteristic...