Differential forms for target tracking and aggregate queries in distributed networks

Rik Sarkar, Jie Gao

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

10 Scopus citations

Abstract

Consider mobile targets moving in a plane and their movements being monitored by a network such as a field of sensors. We develop distributed algorithms for in-network tracking and range queries for aggregated data (for example returning the number of targets within any user given region). Our scheme stores the target detection information locally in the network, and answers a query by examining the perimeter of the given range. The cost of updating data about mobile targets is proportional to the target displacement. The key insight is to maintain in the sensor network a function with respect to the target detection data on the graph edges that is a differential one-form such that the integral of this one-form along any closed curve C gives the integral within the region bounded by C. The differential one-form has great flexibility making it appropriate for tracking mobile targets. The basic range query can be used to find a nearby target or any given identifiable target with cost O(d) where d is the distance to the target in question. Dynamic insertion, deletion, coverage holes and mobility of sensor nodes can be handled with only local operations, making the scheme suitable for a highly dynamic network. It is extremely robust and capable of tolerating errors in sensing and target localization. Due to limited space, we only elaborate the advantages of differential forms in tracking of mobile targets. The same routine can be applied for organizing many other types of informations, for example streaming scalar sensor data (such as temperature data field), to support efficient range queries. We demonstrate through analysis and simulations that this scheme compares favorably with existing schemes that use location services for answering aggregated range queries of target detection data.

Original languageEnglish (US)
Title of host publicationMobiCom'10 and MobiHoc'10 - Proceedings of the 16th Annual International Conference on Mobile Computing and Networking and 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing
PublisherAssociation for Computing Machinery
Pages377-388
Number of pages12
ISBN (Print)9781450301817
DOIs
StatePublished - 2010
Externally publishedYes
Event16th Annual Conference on Mobile Computing and Networking, MobiCom 2010 - Chicago, IL, United States
Duration: Sep 20 2010Sep 24 2010

Publication series

NameProceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM

Other

Other16th Annual Conference on Mobile Computing and Networking, MobiCom 2010
Country/TerritoryUnited States
CityChicago, IL
Period9/20/109/24/10

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Differential forms
  • Multi-target tracking
  • Range queries
  • Sensor networks

Fingerprint

Dive into the research topics of 'Differential forms for target tracking and aggregate queries in distributed networks'. Together they form a unique fingerprint.

Cite this