對於大部分無線感測網路，無線傳輸是最耗電的功能，而資料匯集在無線感測網路中，是最耗費傳輸量的行為之一。為了要節省資料匯集所需的傳輸量，資料壓縮是最直接的方式。由於傳統壓縮會造成節點本身過多的計算負擔，因此對於無線感測網路，壓縮傳感的應用成為一個很熱門的話題。現有基於壓縮傳感的資料匯集之研究中，Hierarchical Compressive Data Gathering (HCDG) 是目前最省電的架構。在HCDG架構下，分群演算法與傳輸量有著很密切的關係，目前在HCDG的研究中，是以Random Clustering method作為它們的分群演算法，但Random Clustering method並不是一個最佳的方法，因此我們針對HCDG架構提出一個基於壓縮性的分群方法 Compressibility-Based Clustering Algorithm (CBCA)，我們進一步透過數學上的分析，找出對於CBCA最佳化的參數，並證明我們的方法相較於先前的研究，有更好的表現。我們以風災警報系統的水位資料進行模擬實驗，我們驗證了數學分析的結果，並且在最低的傳輸量下仍然維持percent root difference (PRD) <5%的重建品質。

For most wireless sensor networks (WSN), wireless transmission is a major contributor to power consumption. Data gathering is one of the important functions in WSN, but this introduces a lot of wireless transmission overhead. Data compression is the most common approach, to reducing the transmission required for data gathering. However, conventional data compression will cause heavy in-node computation, and thus applying compressive sensing (CS) with wireless data gathering has attracted growing attention. With regard existing CS-based data gathering work, Hierarchical Compressive Data Gathering (HCDG) is the most transmission-efficient architecture. For HCDG, the clustering algorithm used has a close relation with the amount of transmission data that is gathered, and existing HCDG works adopt the Random Clustering method as their clustering algorithm, although this still has a lot of transmission. We thus proposed a Compressibility-Based Clustering Algorithm (CBCA) for HCDG, demonstrate that CBCA has lower transmission than the Random Clustering method, and find the optimal parameters of CBCA through mathematical analysis. We used water level data collected form an inundation monitoring system in our simulation experiment, and the results verify the mathematical analysis, and demonstrate the recovery quality still maintains a percent root difference (PRD) <5% at the optimal parameters of CBCA.

[1] I. Akyildiz, "A Survey on Sensor Networks", IEEE Commun. Mag., vol. 40, no. 8, pp.102 -114 2002
[2] Raja Jurdak, Antonio G. Ruzzelli, and Gregory M.P. O'Hare. Radio sleep mode optimization in wireless sensor networks. IEEE Transactions on Mobile Computing, 9(7):955-968, 2010.
[3] O. Gnawali , R. Fonseca , K. Jamieson , D. Moss and P. Levis "Collection tree protocol", Proc. 7th ACM Conf. Embedded Netw. Sensor Syst., pp.1 -14 2009.
[4] R. Shah, J. Rabaey, Energy aware routing for low energy ad hoc sensor networks, in: Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Orlando, FL, March 2002
[5] F. Ye et al., A scalable solution to minimum cost forwarding in large scale sensor networks, in: Proceedings of International Conference on Computer Communications and Networks (ICCCN), Dallas, TX, October 2001
[6] F. Ye et al., A two-tier data dissemination model for large-scale wireless sensor networks, in: Proceedings of Mobicom'02, Atlanta, GA, September, 2002
[7] K. Kalpakis, K. Dasgupta, P. Namjoshi, Maximum lifetime data gathering and aggregation in wireless sensor networks, in: Proceedings of IEEE International Conference on Networking (NETWORKS '02), Atlanta, GA, August 2002
[8] R. Cristescu, B. Beferull-Lozano, M. Vetterli, and R. Wattenhofer. Network correlated data gathering with explicit communication: Np-completeness and algorithms. IEEE/ACM Trans. on Networking, 14(1):41–54, Feb. 2006.
[9] A. Ciancio, S. Pattem, A. Ortega, and B. Krishnamachari. Energy-efficient data representation and routing for wireless sensor networks based on a distributed wavelet compression algorithm. In Proc. of IPSN, pages 309–316, 2006.
[10] J. A´cimovi´c, B. Beferull-Lozano, and R. Cristescu. Adaptive distributed algorithms for power-efficient data gathering in sensor networks. In Proc. of Intl. Conf. on Wireless Networks, Comm. and Mobile Computing, pages 946–951, Jun. 2005.
[11] R. Baraniuk. Compressive sensing. IEEE Signal Processing Magazine, 24(4):118–121, Jul. 2007.
[12] E. J. Cand`es and M. B. Wakin. An introduction to compressive sampling. IEEE Signal Processing Magazine, 25(2):21–30, Mar. 2008.
[13] D. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289–1306, Apr. 2006.
[14] C. Luo, F. Wu, J. Sun, and C.-W Chen, "Compressive Data Gathering for Large-Scale Wireless Sensor Networks," in Proc. of the 15th ACM MobiCom, 2009.
[15] L. Xiang, J. Luo, and A. Vasilakos, "Compressed data aggregation for energy efficient wireless sensor networks," Proc. of the 8th IEEE SECON (to appear), 2011.
[16] J. Luo, L. Xiang, and C. Rosenberg, "Does Compressed Sensing Improve the Throughput of Wireless Sensor Networks?" in Proc. of the IEEE ICC, 2010.
[17] X. Xu, R. Ansari, and A. Khokhar, “Power-efficient hierarchical data aggregation using compressive sensing in WSNs,” in Proceedings of the IEEE International Conference on Communications (ICC '13), pp. 1769–1773, 2013.
[18] M. Davenport. Random observations on random observations: Sparse signal acquisition and processing. PhD thesis, Rice University, Aug. 2010.
[19] D. L. Donoho, M. Elad, and V. Temlyakov, “Stable recovery of sparse overcomplete representations in the presence of noise,” IEEE Transactions Information Theory, vol. 52, no. 1, pp. 6–18, January 2006.
[20] E. J. Cand´es and T. Tao, “Decoding by linear programming,” IEEE Transactions Information Theory, vol. 51, no. 12, pp. 4203–4215, December 2005.
[21] H. Mohimani, M. Babaie-Zadeh, and C. Jutten, “A fast approach for overcomplete sparse decomposition based on smoothed l0 norm,” IEEE Transactions On Signal Processing, vol. 57, no. 1, pp. 289–301, January 2009.
[22] D. L. Donoho, “For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution,” Technology Report, 2004.
[23] (2005) l1-magic: Recovery of sparse signals via convex programming. [Online]. Available: www.acm.caltech.edu/l1magic/downloads/l1magic.pdf.
[24] X. Wu and M. Liu. In-situ soil moisture sensing: measurement scheduling and estimation using compressive sensing. In Proceedings of the 11th International Conference on Information Processing in Sensor Networks (IPSN ’12), New York, NY, USA, 2012. ACM
[25] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci Wireless sensor networks: a survey Comput. Networks (Elsevier), 38 (4) (2002), pp. 393–422
[26] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Coverage problems in wireless ad hoc sensor networks,” in Proc. IEEE INFOCOM, 2001, pp. 1380–1387.
[27] J. Hou , C. Wu , Z. Yuan , J. Tan , Q. Wang and Y. Zhou "Research of Intelligent Home Security Surveillance System Based on ZigBee", International Symposium on Intelligent Information Technology Application Workshops, pp.554 -557 2008
[28] R. G. Baraniuk "Compressive sensing", IEEE Signal Processing Mag., vol. 24, no. 4, pp.118 -120 2007
[29] R. Chartrand and V. Staneva, "Restricted isometry properties and nonconvex compressive sensing." Preprint.
[30] R. G. Baraniuk , V. Cevher , M. F. Duarte and C. Hegde "Model-based compressive sensing", IEEE Trans. Inf. Theory, vol. 56, no. 4, pp.1982 -2001 2010
[31] J. Romberg "Compressive sensing by random convolution", SIAM J. Imag. Sci.
[32] G. H. Mohimani , M. Babaie-Zadeh and C. Jutten "Complex-valued sparse representation based on smoothed $ell ^{0}$ norm", Proc. Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), pp.3881 -3884 2008
[33] H. Mohimani , M. Babaie-Zadeh and C. Jutten "A fast approach for overcomplete sparse decomposition based on smoothed norm", IEEE Trans. Signal Process., vol. 57, no. 1, pp.289 -301 2009
[34] E. van den Berg and M. P. Friedlander SPGL1: A solver for large-scale sparse reconstruction., [online] Available: http://www.cs.ubc.ca/labs/scl/spgl1
[35] J. A. Tropp and A. C. Gilbert "Signal recovery from random measurements via orthogonal matching pursuit", IEEE Trans. Inf. Theory, vol. 53, no. 12, pp.4655 -4666 2007
[36] Y. C. Pati , R. Rezaiifar and P. S. Krishnaprasad "Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition", Proc. 27th Annu. Asilomar Conf. Signals, Systems, and Computers, vol. 1, pp.40 -44 1993
[37] R. Chartrand "Fast algorithms for nonconvex compressive sensing: MRI reconstruction from very few data", Proc. IEEE Int. Symp. Biomed. Imag. (ISBI), 2009
[38] "Z. Zhang, T.-P. Jung, S. Makeig, and B. D. Rao, Compressed sensing for energy-efficient wireless telemonitoring of non-invasive fetal ECG via block sparse bayesian learning, submitted to IEEE Trans. Biomed. Eng., 2012. Preprint available at: http://arxiv.org/abs/1205.1287"
[39] Xie R, Jia X (2014) Transmission-efficient clustering method for wireless sensor networks using compressive sensing. IEEE Transactions on Parallel and Distributed Systems 25(3):806–815
[40] C. Luo, F. Wu, J. Sun, and C.W. Chen, “Efficient Measurement Generation and Pervasive Sparsity for Compressive Data Gathering,” IEEE Trans. Wireless Comm., vol. 9, no. 12, pp. 3728-3738, Dec. 2010.
[41] TelosB, Available: http://www.willow.co.uk/html/telosb_mote_platform.html
[42] MSP430 F1611, Available: http://focus.ti.com/docs/prod/folders/print/msp430f1611.html
[43] CC2420, Available: http://focus.ti.com/docs/prod/folders/print/cc2420.html
[44] 802.15.4, Available: http://www.ieee802.org/15/pub/TG4.html
[45] FTDI, Available: http://www.ftdichip.com/Documents/DataSheets/ds232b18.pdf.
[46] PhidgetSBC3, Available: http://www.phidgets.com/docs/1073_User_Guide
[47] PhidgetInterfaceKit 8/8/8, Available: http://www.phidgets.com/docs/1018_User_Guide
[48] S. Lindsey and C.S. Raghavendra, "PEGASIS: Power-Efficient Gathering in Sensor Information Systems," Proc. Int',l Conf. Comm. (ICC ',01), 2001.
[49] Xie D, Zhou Q, Liu J, et al. A Chain-Based Data Gathering Protocol under Compressive Sensing Framework for Wireless Sensor Networks. Computational and Information Sciences (ICCIS), 2013 Fifth International Conference on. IEEE. 2013. 1479–1482.