Random distributed multiresolution representations with significance querying

ABSTRACT

We propose random distributed multiresolution representations of sensor network data, so that the most significant encoding coefficients are easily accessible by querying a few sensors, anywhere in the network. Less significant encoding coefficients are available by querying a larger number of sensors, local to the region of interest. Significance can be defined in a multiresolution way, without any prior knowledge of the source data, as global summaries versus local details. Alternatively, significance can be defined in a data-adaptive way, as large differences between neighboring data values. We propose a distributed encoding algorithm that is robust to arbitrary wireless communication connectivity graphs, where links can fail or change with time. This randomized algorithm allows distributed computation that does not require strict global coordination or awareness of network connectivity at individual sensors. Because computations involve sensors in local neighborhoods of the communication graph, they are communication-efficient. Our framework uses local interaction among sensors to enable flexible information retrieval at the global level.

REFERENCES

• 1: Lin Xiao , Stephen Boyd , Sanjay Lall, A scheme for robust distributed sensor fusion based on average consensus, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 2: Dzulkifli S. Scherber , Haralabos C. Papadopoulos, Locally constructed algorithms for distributed computations in ad-hoc networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984625]
• 3: V. Saligrama, M. Alanyali, and O. Savas. Asynchronous Distributed Detection in Sensor Networks. submitted to IEEE Transactions on Signal Processing, 2005.
• 4: M. Alanyali, S. Venkatesh, O. Savas, and S. Aeron. Distributed Bayesian Hypothesis Testing in Sensor Networks. Proceedings of American Control Conference, 2004.
• 5: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 6: Martin Vetterli , Jelena Kovačevic, Wavelets and subband coding, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 7: S. Mallat. A Wavelet Tour of Signal Processing. Academic Press, San Diego, CA, 1999.
• 8: A. Giridhar and P.R. Kumar. Computing and Communicating Functions Over Sensor Networks. IEEE Journal on Selected Areas in Communications, vol. 23, no. 4, pp. 755--764, 2003.
• 9: R. Wagner, S. Sarvotham, and R. Baraniuk. A Multiscale Data Representation for Distributed Sensor Networks. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2005.
• 10: R. Wagner, H. Choi, R. Baraniuk, and V. Delouille. Distributed Wavelet Transform for Irregular Sensor Network Grids. Proceedings of the IEEE Workshop on Statistical Signal Processing, 2005.
• 11: Deepak Ganesan , Deborah Estrin , John Heidemann, Dimensions: why do we need a new data handling architecture for sensor networks?, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.143-148, January 2003 [doi>10.1145/774763.774786]
• 12: Deepak Ganesan , Ben Greenstein , Denis Perelyubskiy , Deborah Estrin , John Heidemann, An evaluation of multi-resolution storage for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958502]
• 13: Wim Sweldens, The lifting scheme: a construction of second generation wavelets, SIAM Journal on Mathematical Analysis, v.29 n.2, p.511-546, March 1998 [doi>10.1137/S0036141095289051]
• 14: J.M. Hellerstein, W. Hong, S. Madden, and K. Stanek. Beyond Average: Towards Sophisticated Sensing with Queries. Proceedings of the 2nd International Symposium on Information Processing in Sensor Networks, 2003.
• 15: Joseph M. Hellerstein , Wei Wang, Optimization of in-network data reduction, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052207]
• 16: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 17: R.G. Gallager. Low Density Parity-Check Codes. MIT Press, Cambridge, MA, 1963.
• 18: Alexandros G. Dimakis , Vinod Prabhakaran , Kannan Ramchandran, Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms

Keywords:
arbitrary communication graphs, multiresolution representations, robust distributed algorithms, wireless sensor networks