Skeleton Extraction And Its Applications In Wireless Sensor Networks

Skeleton extraction is a hot topic in wireless sensor networks. The skeleton extraction is advantageous to the design of the high efficiency network algorithm, effectively reduces the node energy loss, prolongs the network life cycle. In this thesis, we study the skeleton extraction problem of 3D sensor networks. we propose a divergence based skeleton extraction algorithm in wireless sensor networks. Then we study the applications of skeleton, including network routing, information stora ge and retrieval, network segmentation in wireless sensor networks. The details are as follows:First, a divergence based skeleton extraction algorithm is studied. Suppose boundary information is known, the boundary nodes flood messages, and calculate the divergence of sensor nodes, based on node's divergence indicators, the skeleton nodes are identified. Skeleton nodes are connected to build a meaningful skeleton which is capable of adequately represent geometric features and topological characteristics of the network. The simulation results show that the algorithm can extract the skeleton of 3D sensor networks effectively.Second, a skeleton based routing algorithm is studied. The routing scheme is derived through local decisions based on the route travels indicators of the source and destination nodes and guarantees delivery with reasonable and natural routes. We show by both theoretical analysis and simulations that our skeleton based routing scheme is scalable, produces short routes, achieves excellent load balancing, and is very robust to variations in the network model.Third, a skeleton based information storage and retrieval algorithm is studied. Using the boundary information of the network, the skeleton is obtained by divergence based skeleton extraction algorithm. Based on the skeleton, we build a multi- tree storage structure and retrieval travels indicators. The information storage scheme stores data replica at a multi-tree storage structure and retrieval algorithm scheme retrieval the data based on the retrieval travels indicators of the producer. We show by simulation that information storage and retrieval algorithm provide short retrieval path length and more balanced traffic load on the sensors.Finally, a skeleton based network segmentation algorithm is studied. Using the boundary information of the network, the skeleton is obtained by divergence based skeleton extraction algorithm. Based on the skeleton information and boundary information, we obtain the skeleton inflection points and boundary concave points. The algorithm partitions an irregular sensor field into nicely shaped pieces by skeleton inflection points and boundary concave points. Our simulations show that the proposed algorithm has more superior performance under various sensor network models, always yielding appropriate segmentation results.