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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

23 Citations (Scopus)


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
Title of host publicationIEEE INFOCOM 2009 - The 28th Conference on Computer Communications
Number of pages5
Publication statusPublished - 12 Oct 2009
Event28th Conference on Computer Communications, IEEE INFOCOM 2009 - Rio de Janeiro, Brazil
Duration: 19 Apr 200925 Apr 2009


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

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this