有限誤差霍夫曼編碼在無線感測網路的資料壓縮應用

Bounded Error Huffman Coding in Applications of Wireless Sensor Networks

林哲論(Che-Lung Lin)

指導教授 ： 張瑞益

國立臺灣大學/工學院/工程科學及海洋工程學研究所/碩士(2014年)

https://doi.org/10.6342/NTU.2014.11300

摘要

在現實情境中，無線感測網路(WSN)因為硬體的技術導致感測資料與實際物理量之間產生『有限誤差』；同時，WSN應用的考量中也允許『有限誤差』。我們過去的研究中，“有限誤差資料壓縮(Bounded Error Data Compression, BEC)”與“改進的有限誤差資料壓縮(Improved Bounded Error Data Compression, IBEC)”兩個方法皆是在資料允許誤差的前提下，將有限誤差運用於WSN運作階段的資料壓縮上，以降低感測裝置的耗電速度。本研究有別於BEC與IBEC，提出有限誤差霍夫曼編碼(Bounded Error Huffman Coding ,BEHC)，將有限誤差運用於霍夫曼編碼(Huffman Coding)，使系統在資料相關性壓縮中，避免以多餘的位元組成編碼，改善有限誤差的資料被壓縮成較長編碼的缺失，以增加資料的壓縮率。此外，本研究深入探討IBEC後，發現IBEC於資料格式和空間相關性壓縮的設計上仍然存在著缺失，故提出新改進有限誤差資料壓縮(New Improved Bounded Error Data Compression, NIBEC)，在運用BEHC的同時，針對IBEC的資料格式和空間相關性壓縮進一步地改進，以提升資料壓縮的效果。本研究以四種不同相關性程度的實際感測資料模擬NIBEC，並與IBEC做比較。結果顯示於處理相同資料時，當有限誤差為1%時，NIBEC可以進一步提升27%~47%的資料壓縮率，並且減少25%~43%的耗電量。以此證明NIBEC有效地改進了資料壓縮的效能。

關鍵字

無線感測網路 ； 有限誤差 ； 資料壓縮 ； 霍夫曼編碼 ； 空間相關性

並列摘要

The measurement error in realistic application for WSN exists due to hardware limitation and application conditions. On the other hand, how to prolong the life time of WSN is an important issue due to the limitation of battery capacity in sensors.
In previous research, both Bounded Error Data Compression (BEC) and Improved Bounded Error Data Compression (IBEC), used the bounded error in data compression under the condition of allowing data error to reduce the power consumption in WSN. Unlike BEC and IBEC, Bounded Error Huffman Coding (BEHC) proposed in this thesis uses the bounded error in Huffman coding. In data correlation compression, the compression ratio would be improved by that avoiding the excess bit composing the code and eliminating the defect of compressing the data under bounded error to longer code. In addition, after the research and observation of IBEC in this thesis, it shows that the data format and spatial correlation compression proposed by IBEC still has the defect. Therefore, New Improved Bounded Error Data Compression (NIBEC) which uses BEHC in off-line would be proposed to improve the data format and spatial correlation compression for higher effectiveness of compression.
In experiment result, four type raw data which have different correlation would be experimented and the results would compare with IBEC. The result shows that NIBEC improved 27%~47% compression ratio and reduced 25%~43% power consumption, and it proved that NIBEC improved the compression effectively.

並列關鍵字

Wireless Sensor Network ； bounded error ； data compression ； Huffman coding ； spatial correlation

參考文獻

[1] K. Dasgupta, K. Kalpakis, and P. Namjoshi, "An efficient clustering-based heuristic for data gathering and aggregation in sensor networks," in Wireless Communications and Networking, pp. 1948-1953, March 2003.

[4] Y. Liang and W. Peng, "Minimizing energy consumptions in wireless sensor networks via two-modal transmission," ACM SIGCOMM Computer Communication Review, vol. 40, pp. 12-18, January 2010.

[5] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey," Computer networks, vol. 38, pp. 393-422, March 2002.

[6] N. Kimura and S. Latifi, "A survey on data compression in wireless sensor networks," in Information Technology: Coding and Computing, 2005. ITCC 2005. International Conference on, pp. 8-13, April 2005.

[8] S. G. Rabinovich, "Measurement Errors and Uncertainties: Theory and Practice," ISBN: 9780387253589, 2005.