Shape segmentation and applications in sensor networks

Xianjin Zhu, Rik Sarkar, Jie Gao

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

41 Scopus citations


Many sensor network protocols in the literature implicitly assume that sensor nodes are deployed uniformly inside a simple geometric region. When the real deployment deviates from that, we often observe degraded performance. It is desirable to have a generic approach to handle a sensor field with complex shape. In this paper, we propose a segmentation algorithm that partitions an irregular sensor field into nicely shaped pieces such that algorithms and protocols that assume a nice sensor field can be applied inside each piece. Across the segments, problem dependent structures specify how the segments and data collected in these segments are integrated. This unified topology-adaptive spatial partitioning would benefit many settings that currently assume a nicely shaped sensor field. Our segmentation algorithm does not require sensor locations and only uses network connectivity information. Each node is given a 'flow direction' that directs away from the network boundary. A node with no flow direction becomes a sink, and attracts other nodes in the same segment. We evaluate the performance improvements by integrating shape segmentation with applications such as distributed indices and random sampling.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM 2007
Subtitle of host publication26th IEEE International Conference on Computer Communications
Number of pages9
StatePublished - 2007
Externally publishedYes
EventIEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications - Anchorage, AK, United States
Duration: May 6 2007May 12 2007

Publication series

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


OtherIEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications
Country/TerritoryUnited States
CityAnchorage, AK

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Shape segmentation and applications in sensor networks'. Together they form a unique fingerprint.

Cite this