A General Framework of Skeleton Extraction in Sensor Networks

Wenping Liu, Yang Yang, Kai Peng, Hongbo Jiang, Xiaofei Liao, Wei Wei, Bo Li, Jing XingIEEE Sensors Journal 2015 · DOI

Abstract

In sensor networks, skeleton (also known as medial axis) extraction is recognized as an appealing approach to support many applications, such as load-balanced routing and location-free segmentation. Existing solutions in the literature rely heavily on the identified boundaries, posing severe limitations on the applicability of the skeleton extraction algorithm. In this paper, we conduct the first work of a connectivity-based and boundary-free skeleton extraction scheme in sensor networks, and propose a centrality-and-connectivity-based boundary-free algorithm, which is simple, distributed, and scalable, and can correctly identify a few skeleton nodes and connects them into a meaningful representation of the network, without reliance on any constraint on communication radio model or nodal distribution. The key idea of our algorithm is to exploit the necessary (but not sufficient) condition of skeleton points: the intersection area of the disk centered at a skeleton point <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> should be the largest one as compared with the other points on the chord generated by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> , where the chord is referred to as the line segment connecting <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> and the tangent point in the boundary. To that end, we present the concept of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> -centrality of a point, quantitatively measuring how central a point is. Accordingly, a skeleton point should have the largest value of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> -centrality, as compared with the other points on the chord generated by this point. We then propose a distributed algorithm to connect the identified skeleton nodes, while obtaining two by-products, i.e., the boundaries and the segmentation result of the network. We also design a light-weight scheme based on the Voronoi diagram, entitled Voronoi-based skeleton extraction algorithm, that yields a skeleton with less communication overhead while sacrificing slightly the skeleton accuracy, providing a tradeoff between skeleton accuracy and communication cost.
BibTeX
@article{liu2015general,
  author = {Wenping Liu and Yang Yang and Kai Peng and Hongbo Jiang and Xiaofei Liao and Wei Wei and Bo Li and Jing Xing},
  title = {{A General Framework of Skeleton Extraction in Sensor Networks}},
  journal = {IEEE Sensors Journal},
  year = {2015},
  doi = {10.1109/jsen.2015.2496268},
}

Loading related content...

Figure