Rik Sarkar, Xianjin Zhu, Jie Gao, Leonidas J. Guibas, and Joseph S. B. Mitchell, Iso-Contour Queries and Gradient Descent with Guaranteed Delivery in Sensor Networks, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), May, 2008.

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.

Bibtex: 

@inproceedings{szggm-icqgdgdsn-08,
	author="Rik Sarkar and Xianjin Zhu and Jie Gao and Leonidas J. Guibas and Joseph S. B. Mitchell",
	title="Iso-Contour Queries and Gradient Descent with Guaranteed
Delivery in Sensor Networks",
	booktitle="Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08)",
	month="May",
	year="2008"
}