CASE: Connectivity-based skeleton extraction in wireless sensor networks

Hongbo Jiang*, Wenping Liu, Dan Wang, Chen Tian, Xiang Bai, Xue Liu, Ying Wu, Wenyu Liu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations


Many sensor network applications are tightly coupled with the geometric environment where the sensor nodes are deployed. The topological skeleton extraction has shown great impact on the performance of such services as location, routing, and path planning in sensor networks. Nonetheless, current studies focus on using skeleton extraction for various applications in sensor networks. How to achieve a better skeleton extraction has not been thoroughly investigated. There are studies on skeleton extraction from the computer vision community; their centralized algorithms for continuous space, however, is not immediately applicable for the discrete and distributed sensor networks. In this paper we present CASE: a novel Connectivity-bAsed Skeleton Extraction algorithm to compute skeleton graph that is robust to noise, and accurate in preservation of the original topology. In addition, no centralized operation is required. The skeleton graph is extracted by partitioning the boundary of the sensor network to identify the skeleton points, then generating the skeleton arcs, connecting these arcs, and finally refining the coarse skeleton graph. Our evaluation shows that CASE is able to extract a well-connected skeleton graph in the presence of significant noise and shape variations, and outperforms state-of-the-art algorithms.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2009 - The 28th Conference on Computer Communications
Number of pages5
StatePublished - 2009
Event28th Conference on Computer Communications, IEEE INFOCOM 2009 - Rio de Janeiro, Brazil
Duration: Apr 19 2009Apr 25 2009

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other28th Conference on Computer Communications, IEEE INFOCOM 2009
CityRio de Janeiro

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'CASE: Connectivity-based skeleton extraction in wireless sensor networks'. Together they form a unique fingerprint.

Cite this