Iso-Contour Queries and Gradient Descent with Guaranteed Delivery in Sensor Networks

Rik Sarkar, Xianjin Zhu, Jie Gao, Leonidas J. Guibas, Joseph S. B. Mitchell

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

Abstract

We study the problem of data-driven routing and navigation in a distributed sensor network over a continuous scalar field. Specifically, we address the problem of searching for the collection of sensors with readings within a specified range. This is named the iso-contour query problem. We develop a gradient based routing scheme such that from any query node, the query message follows the signal field gradient or derived quantities and successfully discovers all iso-contours of interest. Due to the existence of local maxima and minima, the guaranteed delivery requires preprocessing of the signal field and the construction of a contour tree in a distributed fashion. Our approach has the following properties: (i) the gradient routing uses only local node information and its message complexity is close to optimal, as shown by simulations; (ii) the preprocessing message complexity is linear in the number of nodes and the storage requirement for each node is a small constant. The same preprocessing also facilitates route computation between any pair of nodes where the the route lies within any user supplied range of values.
Original languageEnglish
Title of host publicationINFOCOM 2008. 27th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 13-18 April 2008, Phoenix, AZ, USA
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages960-967
Number of pages8
ISBN (Print)978-1-4244-2025-4
DOIs
Publication statusPublished - 2008

Fingerprint

Dive into the research topics of 'Iso-Contour Queries and Gradient Descent with Guaranteed Delivery in Sensor Networks'. Together they form a unique fingerprint.

Cite this