We propose RIDA, a novel robust information-driven data compression architecture for distributed wireless sensor networks. The key idea is to determine the data correlation among a group of sensors based on the data values to significantly improve compression performance rather than relying solely on spatial data correlation. A logical mapping approach assigns virtual indices to nodes based on the data content, which enables simple implementation of data transformation on resource-constrained nodes without any other information. We evaluate RIDA with both discrete cosine transform (DCT) and discrete wavelet transform (DWT) on publicly available real-world data sets. Our experiments show that 30% of energy and 80–95% of bandwidth can be saved for typical multihop data networks. Moreover, the original data can be retrieved after decompression with a low error of about 3%. In particular, for one state-of-the-art distributed data compression algorithm for sensor networks, we show that the compression ratio is doubled by using logical mapping while maintaining comparable mean square error. Furthermore, we also propose a mechanism to detect and classify missing or faulty nodes, showing accuracy and recall of 95% when half of the nodes in the network are missing or faulty. 1. Introduction With the continued evolution of sensor networking hardware, the ability to deploy large numbers of sensors is becoming possible [1]. Typically, sensor networks are deployed to gather environmental information with the sensors cooperating to forward data to a data sink. One of the main challenges with such sensor networks is the need to minimize wireless transmissions to conserve energy at sensors [2]. There are several basic ways to minimize the network traffic: in-network storage, data aggregation, and data compression. With in-network storage, sensors store data locally and only transmit data in response to a query [3–6]. The network discards old data to store newer data. With data aggregation, different sensors aggregate their data (sum, average, etc.) and only transmit the result to the sink [7–11]. Some applications may need raw data. For example, scientists might want to collect raw temperature data in an area to model and forecast the weather, as well as for archival. For such applications, data compression is preferred [6, 12–16]. Compression can be applied to the data stream from a single sensor [16]. Good compression performance can be obtained this way as a sensor typically generates similar data over time. However, if the compressed data from a single sensor is
References
[1]
T. He, S. Krishnamurthy, L. Luo et al., “VigilNet: an integrated sensor network system for energy-efficient surveillance,” ACM Transactions on Sensor Networks, vol. 2, no. 1, pp. 1–38, 2006.
[2]
D. B. Hoang and N. Kamyabpour, “An energy driven architecture for wireless sensor networks,” CoRR, abstract 1206.2005, 2012.
[3]
T. B. Matos, A. Brayner, and J. E. B. Maia, “Towards in-network data prediction in wireless sensor networks,” in Proceedings of the 25th Annual ACM Symposium on Applied Computing (SAC '10), pp. 592–596, New York, NY, USA, March 2010.
[4]
D. Ganesan, D. Estrin, and J. Heidemann, “Dimensions: why do we need a new data handling architecture for sensor networks,” ACM SIGCOMM Computer Communication Review, vol. 33, no. 1, pp. 143–148, 2003.
[5]
P. Bonnet, J. Gehrke, and P. Seshadri, “Towards sensor database systems,” in Proceedings of the 2nd International Conference on Mobile Data Management, pp. 3–14, Hong Kong, January 2001.
[6]
T. Srisooksai, K. Keamarungsi, P. Lamsrichan, and K. Araki, “Practical data compression in wireless sensor networks: a survey,” Journal of Network and Computer Applications, vol. 35, no. 1, pp. 37–59, 2012.
[7]
K. Akkaya, M. Demirbas, and R. S. Aygun, “The impact of data aggregation on the performance of wireless sensor networks,” Wireless Communications and Mobile Computing, vol. 8, no. 2, pp. 171–193, 2008.
[8]
X. Xu, S. Wang, X. Mao, S. Tang, and X. Li, “An improved approximation algorithm for data aggregation in multi-hop wireless sensor networks,” in Proceedings of the 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing (FOWANC '09), pp. 47–56, ACM, New York, NY, USA, May 2009.
[9]
Y. Zhu, R. Vedantham, S. J. Park, and R. Sivakumar, “A scalable correlation aware aggregation strategy for wireless sensor networks,” Information Fusion, vol. 9, no. 3, pp. 354–369, 2008.
[10]
S. Madden, M. J. Franklin, J. Hellerstein, and W. Hong, “Tinydb: an acquisitional query processing system for sensor networks,” ACM Transaction on Database System, vol. 30, no. 1, pp. 122–173, 2005.
[11]
C. Cappiello and F. A. Schreiber, “Quality- and energy-aware data compression by aggregation in WSN data streams,” in Proceedings of the 7th Annual IEEE International Conference on Pervasive Computing and Communications (PerCom '09), Washington, DC, USA, March 2009.
[12]
N. Kimura and S. Latifi, “A survey on data compression in wireless sensor networks,” in Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC '05), vol. 02, pp. 8–13, IEEE Computer Society, Washington, DC, USA, 2005.
[13]
N. Gehrig and P. L. Dragotti, “Distributed compression in camera sensor networks,” in Proceedings of the IEEE 6th Workshop on Multimedia Signal Processing, pp. 311–314, Siena, Italy, September 2004.
[14]
S. S. Pradhan, J. Kusuma, and K. Ramchandran, “Distributed compression in a dense micro-sensor network,” IEEE Signal Processing, vol. 19, no. 2, pp. 51–60, 2002.
[15]
A. Ciancio and A. Ortega, “A distributed wavelet compression algorithm for wireless multihop sensor networks using lifting,” in Proceedings of the 30th IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '05), pp. IV825–IV828, Philadelphia, Pa, USA, March 2005.
[16]
C. M. Sadler and M. Martonosi, “Data compression algorithms for energy-constrained devices in delay tolerant networks,” in Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys '06), pp. 265–278, Boulder, Colo, USA, November 2006.
[17]
T. Dang, N. Bulusu, and W. Feng, “Rida: a robust informationdriven data compression aorchitecture for irregular wireless sensor networks,” in Proceedings of the 4th the European Conference on Wireless Sensor Networks (EWSN '07), pp. 13–149, Delft, The Netherlands, January 2007.
[18]
R. Wagner, Distributed multi-scale data processing for sensor networks [Ph.D. thesis], Rice University, Houston, Tex, USA, 2007.
[19]
S. Madden, “Intel Research Lab at Berkeley,” November 2006, http://db.lcs.mit.edu/labdata/labdata.html.
[20]
SensorScope, “Sensorscope wireless distributed sensing sysem for environmental monitoring,” April 2008, http://sensorscope.epfl.ch/index.php.
[21]
S. K. Mitra, Digital Signal Processing: A Computer-Based Approach, Mc Graw Hill, New York, NY, USA, 2006.
[22]
T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons, New York, NY, USA, 1991.
[23]
M. Vetterli and J. Kovacevic, Wavelets and Subband Codding, Prentice Hall, Upper Saddle River, NJ, USA, 1995.
[24]
G. Shen, S. K. Narang, and A. Ortega, “Adaptive distributed transforms for irregularly sampled wireless sensor networks,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '09), pp. 2225–2228, IEEE Computer Society, Washington, DC, USA, April 2009.
[25]
G. Shen and A. Ortega, “Joint routing and 2D transform optimization for irregular sensor network grids using wavelet lifting,” in Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN '08), pp. 183–194, IEEE Computer Society, Washington, DC, USA, April 2008.
[26]
C. Luo, F. Wu, J. Sun, and C. W. Chen, “Compressive data gathering for large-scale wireless sensor networks,” in Proceedings of the 15th Annual International Conference on Mobile Computing and Networking (MobiCom '09), pp. 145–156, ACM, New York, NY, USA, 2009.
[27]
F. Oldewurtel, J. Ansari, and P. M?h?nen, “Crosslayer design for distributed source coding in wireless sensor networks,” in Proceedings of the 2nd International Conference on Sensor Technologies and Applications (SENSORCOMM '08), pp. 435–443, IEEE Computer Society, Washington, DC, USA, 2008.
[28]
D. L. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289–1306, 2006.
[29]
E. J. Candes and T. Tao, “Near-optimal signal recovery from random projections: universal encoding strategies?” IEEE Transactions on Information Theory, vol. 52, no. 12, pp. 5406–5425, 2006.
[30]
M. F. Duarte, S. Sarvotham, D. Baron, M. B. Wakin, and R. G. Baraniuk, “Distributed compressed sensing of jointly sparse signals,” in Proceedings of the 39th Asilomar Conference on Signals, Systems and Computers, pp. 1537–1541, Pacific grove, Calif, USA, November 2005.
[31]
M. F. Duarte, M. B. Wakin, D. Baron, and R. G. Baraniuk, “Universal distributed sensing via random projections,” in Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN '06), pp. 177–185, Nashville, Tenn, USA, April 2006.
[32]
M. Rabbat, J. Haupt, A. Singh, and R. Nowak, “Decentralized compression and predistribution via randomized gossiping,” in Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN '06), pp. 51–59, Nashville, Tenn, USA, April 2006.
[33]
W. Wang, M. Garofalakis, and K. Ramchandran, “Distributed sparse random projections for refinable approximation,” in Proceedings of the 6th International Symposium on Information Processing in Sensor Networks (IPSN '07), pp. 331–339, Cambridge, Mass, USA, April 2007.
[34]
W. Bajwa, J. Haupt, A. Sayeed, and R. Nowak, “Compressive wireless sensing,” in Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN '06), pp. 134–142, April 2006.
[35]
W. Bajwa, J. Haupt, A. Sayeed, and R. Nowak, “Joint source-channel communication for distributed estimation in sensor networks,” IEEE Transactions on Information Theory, vol. 53, no. 10, pp. 3629–3653, 2007.
[36]
W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks,” in Proceedings of the 33rd Annual Hawaii International Conference on System Siences (HICSS '00), vol. 2, p. 223, January 2000.
[37]
A. Krause, A. Gupta, C. Guestrin, and J. Kleinberg, “Near-optimal sensor placements: maximizing information while minimizing communication cost,” in Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN '06), pp. 2–10, ACM, New York, NY, USA, April 2006.
[38]
N. Patwari and A. O. Hero, “Manifold learning algorithms for localization in wireless sensor networks,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, pp. III857–III860, May 2004.
[39]
V. Shnayder, M. Hempstead, B. R. Chen, G. W. Allen, and M. Welsh, “Simulating the power consumption of large-scale sensor network applications,” in Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys '04), pp. 188–200, Baltimore, Md, USA, November 2004.
[40]
CrossBow, “Crossbow mica2 product webpage,” April 2008, http://www.xbow.com/Products/productdetails.aspx?sid=257.
[41]
TinyOS-1.x, “Tinyos-1.x official website,” April 2008, http://www.tinyos.net/tinyos-1.x/.