A Novel Skeleton Extraction Algorithm in Sensor Networks

摘要

This paper analyzes the problem of location-free skeleton extraction in sensor networks. Different from most of the previous solutions, the proposed algorithm has no dependency on boundary information. Our work is based on the proposed index of a node, named centrality, which can reflect the centeredness of the node. We first identify the node having the maximal centrality as the root skeleton node, based on whether a skeleton arc is obtained. Secondly, each node then computes its hop count distance to the skeleton arc, and the network is decomposed into a set of level sets. The node with the maximal centrality is identified as a skeleton node. Thirdly, these skeleton nodes are connected properly to form a coarse skeleton possibly with spurious branches. Finally, a pruning operation is conducted on the coarse skeleton, and the final skeleton is generated. Extensive simulations show the efficiency of the proposed algorithm.