TY - GEN
T1 - Iso-contour queries and gradient descent with guaranteed delivery in sensor networks
AU - Sarkar, Rik
AU - Zhu, Xianjin
AU - Gao, Jie
AU - Guibas, Leonidas J.
AU - Mitchell, Joseph S.B.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/51349115672
U2 - 10.1109/INFOCOM.2007.149
DO - 10.1109/INFOCOM.2007.149
M3 - Conference contribution
AN - SCOPUS:51349115672
SN - 9781424420261
T3 - Proceedings - IEEE INFOCOM
SP - 1633
EP - 1641
BT - INFOCOM 2008
T2 - INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications
Y2 - 13 April 2008 through 18 April 2008
ER -