(3.235.108.188) 您好!臺灣時間:2021/02/25 08:13
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林志忠
研究生(外文):Chih-Chung Lin
論文名稱:考慮多解析度之時間與空間編碼的無線感測網路無失真壓縮
論文名稱(外文):Lossless Data Compression with Multi-resolution Temporal and Spatial Coding in Wireless Sensor Networks
指導教授:張瑞益張瑞益引用關係
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:工程科學及海洋工程學研究所
學門:工程學門
學類:綜合工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:56
中文關鍵詞:無線感測網路無失真資料壓縮時間相關性空間相關性多解析度資料查詢
外文關鍵詞:Wireless sensor networklossless data compressiontemporal correlationspatial correlationmulti-resolution data query
相關次數:
  • 被引用被引用:0
  • 點閱點閱:237
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:2
在一些要求高精準度量測的無線感測網路(Wireless Sensor Networks)應用中,感測節點必須作長時間感測資料的無失真量測與查詢。然而,感測節點的電力通常有限,為了延長節點的使用時間,如何減少耗電成為許多研究主要考量的重點。
現有方法需要透過無失真資料壓縮,或透過查詢感測區域的概況(rough overview)以降低傳輸資料量。然而,目前並無任何方法有同時考量多解析度之感測資料在時間與空間的相關性作無失真壓縮。因此,本研究針對無線感測網路的省電需求,提出一種考慮多解析度之時間與空間編碼的無失真壓縮,稱之為LMTSC (Lossless Data Compression with Multi-resolution Temporal and Spatial Coding)。
LMTSC將每一點感測資料視為影像的一個畫素,如此可將整體感測資料視為一連串的影像,接著利用畫素在時間以及影像在空間的相關性作無失真資料壓縮,以有效降低感測節點所要傳輸的資料量,進而減少耗電。除此之外,本研究提出動態取樣方法,利用不同取樣率取回資料,並將資料透過無失真壓縮作傳送,提供不同解析度的資料查詢。
本研究利用實際的感測資料評估LMTSC之效能,並將LMTSC與著名的MEC作比較。模擬結果顯示,LMTSC不需像MEC作事前的資料訓練,即可達到較好的資料壓縮率。由於傳輸資料量低,故整體耗電比MEC節省26%。若要維持相同樣取樣點(耗電量),本研究所提出的動態取樣方法比傳統靜態取樣方法可接受較精準的誤差界限要求;若要維持在相同的誤差界限底下作取樣,動態取樣方法可較傳統靜態取樣方法節省20%以上的電力。由於LMTSC可大幅節省節點的耗電,極適合應用於無線感測網路。

In some WSN (Wireless Sensor Network) applications which require high-accuracy measurements, sensor nodes are used to do long-term lossless measurement and query. However, the limited power makes the power saving become a critical issue of studies.
In the existing methods, sensed data can be reduced by lossless data compression or querying rough overview of the sensed area. To the best of our knowledge, since none of previous method takes both temporal and spatial correlation of sensed data into consideration for lossless data compression, they usually cannot obtain a good compression ratio. Therefore, these requirements motivate us to propose the LMTSC (Lossless Data Compression with Multi-resolution Temporal and Spatial Coding) method.
LMTSC regards each sensed data as a pixel of an image, and the whole sensed data as sequential images. Using temporal correlation of pixels and spatial correlation of images can reduce the data transmitted and the power consumed efficiently. Besides, we propose a dynamic sampling method which uses various sample rates and lossless data compression to provide different resolution data query.
In this paper, we use the real-world sensed data to evaluate LMTSC and make a comparison with MEC. The simulation results reveal that LMTSC has a good compression ratio than MEC without any data training. As the high compression ratio, LMTSC saves 26% power consumption than MEC. For reaching the identical sample point (power consumption), the dynamic sampling method can tolerate a smaller error bound. For reaching the same error bound, the dynamic sampling method can save more than 20% power consumption than static sampling method. Since LMTSC can make a significant power saving, it is very suitable for WSN.

口試委員會審定書 #
誌謝 I
中文摘要 II
英文摘要 III
目錄 IV
圖目錄 VI
表目錄 VIII

第一章 簡介 1
1.1 前言 1
1.2 研究動機 1
1.3 論文架構 3

第二章 文獻探討 4
2.1 Dictionary-based Compression 4
2.2 Wavelet-based Compression 5
2.3 Huffman Coding-based Compression 6
2.3.1 SHC (Static Huffman Coding) 6
2.3.2 MAHC (Modified Adaptive Huffman Coding) 6
2.4 Predictive Coding-based Compression 6
2.4.1 MEC (Minimizing Energy Consumptions) 6
2.4.2 JPEG-LS 7
2.4.3 SFALIC (Simple Fast and Adaptive Lossless Image
Compression Algorithm) 8
2.5 Multi-resolution Data Compression 8
2.5.1 MRCQ (Multi-Resolution Compression Query) 8

第三章 LMTSC無失真壓縮架構 11
3.1 時間相關編碼 13
3.2 空間相關編碼 17
3.3 LMTSC之時間與空間編碼解碼流程 21
3.4 多解析資料查詢 21
3.4.1 時間的多解析度架構 22
3.4.2 空間的多解析度架構 27

第四章 模擬結果 33
4.1 LMTSC時間空間壓縮 33
4.1.1 Case 1:時間相關度較高、空間相關度較高的溫度資料 38
4.1.2 Case 2:時間相關度較低、空間相關度較高的地震資料 40
4.1.3 Case 3:時間相關度較高、空間相關度較低的心電圖資料 43
4.1.4 Case 4:時間相關度較低、空間相關度較低的腦電波圖資料 46
4.2 Modified LMTSC時間空間壓縮 48
4.3 LMTSC之動態取樣 51

第五章 結論與未來研究 53

參考文獻 54


[1]I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey on Sensor Networks,” IEEE Communication Magazine, Vol. 40, pp. 102-114, August 2002.
[2]R. Szewczyk, E. Osterweil, J. Polastre, M. Hamilton, A. Mainwaring, and D. Estrin, “Habitat Monitoring with Sensor Networks,” ACM Communication, Vol. 47, pp. 34-40, June 2004.
[3]R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, and D. Culler, “An Analysis of a Large Scale Habitat Monitoring Application,” SenSys: ACM Proceedings of Embedded Networked Sensor Systems, Vol. 47, pp. 214-226, November 2004.
[4]C. F. Garcia-Hernandez, P. H. Ibarguengoytia-Gonzalez, J. Garcia-Hernandez, and J. A. Perez-Diaz, “Wireless Sensor Networks and Applications: a Survey,” International Journal of Computer Science and Network Security, Vol. 7, pp. 264-273, February 2007.
[5]D. Culler, D. Estrin, and M. Srivastava, “Guest Editors'' Introduction: Overview of Sensor Network,” IEEE Computer, Vol. 37, pp. 41-49, August 2004.
[6]G. Pottie, W. Kaiser, “Wireless Integrated Network Sensors,” ACM Communication, Vol. 43, pp. 51-58, May 2000.
[7]N. Kimura and S. Latifi, “A Survey on Data Compression in Wireless Sensor Networks,” IEEE International Conference on Information Technology: Coding and Computing, Vol. 2, pp. 8-13, April 2005.
[8]Zhang, T., Madhani, S., van den Berg, E., “Sensors on patrol (SOP): using mobile sensors to detect potential airborne nuclear, biological, and chemical attacks,” IEEE Military Communications Conference, Vol. 5, pp. 2924-2929, October 2005.
[9]B. Zhou, C. Hu, H. B. Wang, R. Guo, “A Wireless Sensor Network for Pervasive Medical Supervision,” IEEE International Conference of Integration Technology, Vol. 1, pp. 470-477, March 2007.
[10]National Taiwan Central Weather Bureau. Homepage: http://www.cwb.gov.tw/
[11]Welch, T.A., “A technique for high-performance data compression,” IEEE Computer, Vol. 17, pp. 8-19, June 1984.
[12]Ziv, J. and Lempel,A., “A universal algorithm for sequential data compression,” IEEE Transaction Information Theory, Vol. 23, pp. 337-343, May 1977.
[13]J. Ziv and A. Lempel., “Compression of Individual Sequences via Variable-Rate Coding,” IEEE Transactions on Information Theory, Vol. 5, pp. 530-536, September 1978.
[14]C. M. Sadler and M. Martonosi, “Data Compression Algorithms for Energy-Constrained Devices in Delay Tolerant Networks,” 4th ACM Internet Conference Embedded Networked Sensor Systems, Vol. 2, pp. 265-278, November 2006.
[15]K. C. Barr and K. Asanovi’c, “Energy-aware lossless data compression,” ACM Transactions on Computer Systems, Vol. 24, pp. 250-291, August 2006.
[16]D. S. Taubman and M. W. Marcellin, “JPEG2000: Fundamentals, Standards, and Practice,” published by Kluwer Academic Publishers, 2002.
[17]G. K. Wallace, “The JPEG still picture compression standard,” ACM Communications, Vol.34, pp. 30-44, December 1991.
[18]D. Ganesan, B. Greenstein, D. Estrin, J. Heidemann, and R. Govindan, “Multiresolution Storage and Search in Sensor Networks,” ACM Transaction Storage, Vol. 1, pp. 277-315, August 2005.
[19]F. Marcelloni and M. Vecchio, “An Efficient Lossless Compression Algorithm for Tiny Nodes of Monitoring Wireless Sensor Networks,” Published by Oxford University Press on behalf of The British Computer Society, Vol. 52, pp. 969-987, April 2009.
[20]C. Tharini and P. V. Ranjan, “Design of Modified Adaptive Huffman Data Compression Algorithm for Wireless Sensor Network,” Journal of Computer Science, Vol. 5, pp. 466-470, June 2009.
[21]M. Y. Javed and A. Nadeem, “Data compression through adaptive Huffman coding schemes,” IEEE International technical conference, Vol. 2, pp. 187-190, October 2000.
[22]Y. Liang and W. Peng, “Minimizing energy consumptions in wireless sensor networks via two-modal transmission,” ACM SIGCOMM, Vol. 40, pp. 12-18, January 2010.
[23]M. J. Weinberger and G. Seroussi, “The LOCO-I Lossless Image Compression Algorithm Principles and Standardization into JPEG-LS,” IEEE Transactions on Image Processing, Vol. 9, pp. 1309-1324, August 2000.
[24]R. Starosolski, “Simple Fast and Adaptive Lossless Image Compression Algorithm,” Silesian University of Technology, Institute of Computer Science, Vol.34, pp. 65-91, January 2007.
[25]Howard, P.G., Vitter and J.S., “Fast and efficient lossless image compression,” IEEE Data Compression Conference, pp. 351-360, April 1993.
[26]X. L. Wu, “Efficient Lossless Compression of Continuous-tone Images via Context Selection and Quantization,” IEEE Transactions on Image Processing, Vol. 6, pp. 656-64, May 1997.
[27]Y. C. Wang, Y. Y. Hsieh and Y. C. Tseng, “Multiresolution Spatial and Temporal Coding in a Wireless Sensor Network for Long-Term Monitoring Applications,” IEEE Transactions on Computers, Vol. 58, pp. 827-838, June 2009.
[28]ChEAS: Chequamegon Ecosystem Atmosphere Study. Homepage: http://cheas.psu.edu/data/.
[29]U.S. Geological Survey Earthquake Hazards Program. Homepage: http://earthquake.usgs.gov/.
[30]Physionet homepage. Homepage: http://www.physionet.org/cgi-bin/ATM.
[31]The Sensor company, Sensirion. Homepage: http://www.sensirion.com.
[32]J. Teuhola, “A compression method for clustered bit-vectors,” Information Processing Letters, Vol. 7, pp. 308-311, October 1978.
[33]Pbmplus. Homepage: http://www.acme.com/software/pbmplus/.
[34]Netpbm toolkit. Homepage: http://netpbm.sourceforge.net/.
[35]Bzip2 homepage. Homepage: http://www.bzip.org/.
[36]J. Kovacevic and M. Vetterli, “Nonseparable two- and three-dimensional wavelets,” IEEE Transactions on Signal Processing, Vol. 43, pp. 1269-1273, August 1995.
[37]V. Vijayaraj, A. M. Cheriyadat and P. Sallee, “Overhead image statistics,” IEEE Applied Imagery Pattern Recognition Workshop, pp. 1-8, October 2008.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔