Random Multiresolution Representations for Arbitrary Sensor Network Graphs

We propose a distributed multiresolution representation of sensor network data so that large-scale summaries are readily available by querying a small fraction of sensor nodes, anywhere in the network, and small-scale details are available by querying a larger number of sensors, locally in the region of interest. A global querier (such as a mobile collector or unmanned aerial vehicle) can obtain a lossy to lossless representation of the network data, according to the desired resolution. A local querier (such as a sensor node) can also obtain either large-scale trends or local details, by querying its immediate neighborhood. We want the encoding to be robust to arbitrary, even time-varying, wireless communication connectivity graphs. Thus we want to avoid cluster heads or deterministic hierarchies that are not robust to single points of failure. We propose a randomized encoding which enables both robustness, and distributed computation that does not require long distance coordination or awareness of network connectivity at individual sensors. Our distributed encoding algorithm operates on local neighborhoods of the communication graph