Composable Information Gradients in Wireless Sensor Networks

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.

1. Introduction and Motivation

Recent advances in wireless sensor networks reveal the potential of such embedded networked systems for revolutionizing the way we observe, interact with, and influence the physical world. Early applications on distributed data collection systems have already identified the advantages of inexpensive networked sensors over more traditional centralized sensing systems. As technologies become mature and as sensor networks grow large in size and become inter-connected, we expect that sensor networks will move beyond military deployments and the monitoring of animal or other natural habitats to the places where humans work and live: homes, cars, buildings, roads, cities, etc. Note that in these human spaces a sensor network serves users embedded in the same physical space as the network, not a community of scientists remote from the observation site. Furthermore, there is often the need to deliver relevant information with very low latency, in order to allow users to act in a timely manner, as for example with first responders in disaster recovery scenarios.