Access Restriction

Author Huijia Lin ♦ Maohua Lu ♦ Milosavljevic, N. ♦ Jie Gao ♦ Guibas, L.J.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science ♦ Technology ♦ Engineering & allied operations ♦ Other branches of engineering
Subject Keyword Tree data structures ♦ Navigation ♦ Partial differential equations ♦ System Design ♦ Data structures ♦ Harmonic Function ♦ Distributed computing ♦ Information Gradients ♦ Wireless sensor networks ♦ Analytical models ♦ Data-centric Routing ♦ Load management ♦ Computer networks ♦ Robustness
Abstract In sensor networks we aim to achieve global objectives through local decisions at each node, based only on data available in the node's neighborhood. In this paper, we diffuse information away from source nodes holding desired data, so as to establish information potentials that allow network queries to navigate towards and reach these sources through local greedy decisions, following information gradients. We compute these information potentials by solving for a discrete approximation to a partial differential equation over appropriate network neighborhoods, through a simple local iteration that can be executed in a distributed manner and can be re-invoked to repair the information field locally when links fail, sources move, etc. The solutions to this equation are classical harmonic functions, which have a rich algebraic structure and many useful properties, including the absence of local extrema, providing a guarantee that our local greedy navigation will not get stuck. Unlike shortest path trees, which can also be used to guide queries to sources, information potentials are robust to low-level link volatility as they reflect more global properties of the underlying connectivity. By exploiting the algebraic structure of harmonic functions such potentials can be combined in interesting ways to enable far greater path diversity and thus provide better load balancing than is possible with fixed tree structures, or they can be used to answer range queries about the number of sources in a certain regions by simply traversing the boundary of the region. Potentials for multiple information types can be aggregated and compressed using a variant of the q-digest data structure. The paper provides both analytic results and detailed simulations supporting these claims.
Description Author affiliation: Comput. Sci., Cornell Univ., Boston, MA (Huijia Lin)
ISBN 9780769531571
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-04-22
Publisher Place USA
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 1.15 MB
Page Count 12
Starting Page 121
Ending Page 132

Source: IEEE Xplore Digital Library