具備位元失真控制機制之樹狀結構線性壓縮方法及其在無線感測資料壓縮上的應用

Tree-Structured Linear Approximation with Optimal RD Control for Data Compression in WSNs.

王楚茗(Chu-Ming Wang)

指導教授 ： 王家祥

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

摘要

Wireless Sensor Networks (WSNs) 已經成為人類生活中不可或缺的一部份，而關於WSNs的各種研究也蓬勃的發展，而其中如何降低Sensor的電量消耗以延長整體WSNs的使用時間是相當重要的議題。整體來說，Sensor最主要消耗電力的行為就是資料傳輸，因此要怎麼在Sensor有限的運算資源下找到一個運算簡單的方法減少傳輸資料的數量正是我們想探討的問題。由於WSNs的資料短時間內不會有過大的變化，因此Model Based的方法相當適合，而其中又屬Linear Model Based的方法最為簡單而有效。有許多方法都在探討如何能找出恰當的直線來代表一串資料和線段如何切割等等的問題，在我們的方法中，我們逐步以二等分的方式將所有資料分割成小段放入二元樹的節點中。接著我們利用二元樹的最佳修剪演算法來尋找恰當的線段分割，sink端會利用修剪過程中取得的Rate-Distortion相關資訊進行target Distortion的分配，每個sensor將分配到的target Distortion當作門檻值來從之前的樹狀切割過程中選擇恰當的結果。切割後的樹的葉子集合就是用來壓縮的資料分段，每一段資料我們都使用Linear Regression進行壓縮，而基於這種分割方式的特性，只要能夠擁有二元樹的結構，我們就能輕鬆的反推出每條線段的起點與終點。然而這樣的切割方式會受到二元樹的限制，減少可能的切割選擇，因此在最後我們將檢查各相鄰兩葉子的線段是否能進行結合，搭配離群資料的偵測與單獨傳送，來對最後的結果進行優化。

關鍵字

無線感測網路 ； 能源節省 ； 位元失真最佳化 ； 離群值 ； 線性近似

並列摘要

Wireless sensor networks (WSNs) are basically unreliable data gathering systems that utilizes a large number of small, battery-powered, and resource-limited sensing devices to monitor certain/various phenomena in the real world. These systems can contribute to intelligent services such as, surveillance, healthcare, environmental and utility monitoring. In WSNs, hundreds or thousands of these disposable sensor nodes are connected wirelessly to communicate either among each other or directly to the base station. How to reduce the power consumption and also lengthen the system life time is one of the key issues to sustain the services effectively. According to the radio model, packet transmission is depletes a much more substantial amount of the energy budget when compared to sensing and processing. Therefore, it is desirable to compress or filter the sensing data to a minimum in order to reduce the transmission power required.
The model-based scheme is a promising solution of data compression for WSNs because the data streams are highly correlated temporally. In this thesis, a tree-structured linear approximation with optimal rate-distortion (RD) control method to deal with the temporal data stream is proposed. This method approximates temporal data by a piecewise linear function, consisting of connected line segments. Initially, a set of possible line segments of equal size are maintained as a complete binary tree for N consecutive data of current stream in each of sensor nodes. Next, a RD pruning process is applied to trim the tree to several candidate forms of incomparable RD pairs. Then, an optimal distortion allocation procedure is employed to allocate the distortions to sensor nodes accordingly. With the assigned distortion value, each tree is further shrunken by iteratively merging possible pair of segments to a minimum rate (# of line segments) while obeying the distortion. Finally, a refinement procedure, with the assistance of outlier removal, is implemented to further compress the data streams.
A real life data set is applied to demonstrate the effectiveness of the thesis. For nearly all combinations with distortion requirements, the proposed method outperforms the earlier approaches in terms of data reduction.

並列關鍵字

WSNs ； energy preservation ； linear approximation ； rate-distortion optimization ； outliers

參考文獻

[1] Hazem Elmeleegy, Ahmed K. Elmagarmid, Emmanuel Cecchet, Walid G. Aref, and Willy Zwaenepoel, “Online Piece-wise Linear Approximation of Numerical Streams with Precision Guarantees,” VLDB, Vol. 2, No. 1, pp. 145-156, August 2009.

[2] Philip A. Chou, Tom Lookabaugh, and Robert M. Gray. "Optimal Pruning with Applications to Tree-Structured Source Coding and Modeling," IEEE Transactions on Information Theory, Vol. 35, No. 2, pp. 299-315, March 1989.

[5] D.E. Knuth, “The Art of Computer Programming, vol.1,” MA: Addison-Wesley, 1973.

[6] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, “Data Structures and Algorithms,” Reading, MA: Addison-Wesley, 1983.

[8] S. Mallat, and F. Falzon, "Analysis of low bit rate image transform coding," IEEE Transactions on Signal Processing , Vol. 46, p.p. 1027-1042, April 1998.