Localization using boundary sensors: An analysis based on graph theory

Yunhui Zheng, David J. Brady, Pankaj K. Agarwal

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


We consider sensors, such as fibers, lasers, and pyroelectric motion detectors, that fire when objects cross a boundary. A moving object can be localized by analyzing sequences of boundary crossings. We consider the number of distinct sequences and object positions that can be achieved using boundary sensors in one- and two-dimensional spaces. For 1D systems we use representations of sensor sequences on graphs to derive limits on the number of object locations that can be monitored by a given sensor population and sequence length. For 2D systems we show that in certain circumstances the ratio of the number of unique sensor sequences to the number of unique object paths is exponential in the sequence length and we argue that the probability of unique identification is high for sufficiently large sequences. We also prove the triangle grid can track an object with error limited to a small neighborhood.

Original languageEnglish (US)
Article number21
JournalACM Transactions on Sensor Networks
Issue number4
StatePublished - Oct 1 2007
Externally publishedYes


  • Boundary sensor
  • Deployment graph
  • Deployment sequence
  • Sensor sequence
  • Sequence graph

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Localization using boundary sensors: An analysis based on graph theory'. Together they form a unique fingerprint.

Cite this