張涵笑，慕福奇，呂欣巖

(1. 中國科學(xué)院物聯(lián)網(wǎng)研究發(fā)展中心，江蘇 無錫 214135；2. 中國科學(xué)院大學(xué) 微電子學(xué)院，北京 100049；3. 江蘇中科羿鏈通信技術(shù)有限公司，江蘇 無錫 214135)

0 引言

隨著物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展與普及，人們身邊越來越多的數(shù)據(jù)被監(jiān)測和記錄。例如使用較為廣泛的環(huán)境信息監(jiān)測傳感器，在工廠、醫(yī)院、運(yùn)輸、家庭等各種場景都有應(yīng)用。這類環(huán)境監(jiān)測數(shù)據(jù)包含溫度、濕度和PM2.5濃度等多種類型，這些數(shù)據(jù)的持續(xù)上傳形成了海量的歷史時序數(shù)據(jù)。如何高效地存儲這些數(shù)據(jù)是物聯(lián)網(wǎng)技術(shù)研究的重要內(nèi)容，許多研究者從數(shù)據(jù)壓縮入手以減少數(shù)據(jù)占用的存儲空間。

旋轉(zhuǎn)門壓縮算法(Swinging Door Trending，SDT)是常用的時序數(shù)據(jù)壓縮算法[1-3]。研究人員針對各種實際使用場景對傳統(tǒng)的SDT算法提出了不同的改進(jìn)方案。如增加強(qiáng)制記錄限來解決變化幅度較小的數(shù)據(jù)很長時間不被保存的問題[4]；保存兩記錄點之間的原始數(shù)據(jù)的逼近線段來代替記錄原始數(shù)據(jù)點以提高壓縮比[5]；預(yù)先對原始數(shù)據(jù)進(jìn)行平滑和去噪處理，然后再使用SDT算法進(jìn)行壓縮以提高壓縮率[6]；將SDT算法與無損壓縮算法結(jié)合起來，進(jìn)一步提高壓縮率[7]；根據(jù)數(shù)據(jù)變化幅度來動態(tài)調(diào)整壓縮偏差以提高壓縮率；記錄對壓縮精度影響最大的數(shù)據(jù)點來提高壓縮精度[8]。這些改進(jìn)基本都是根據(jù)應(yīng)用場景的不同，在運(yùn)算性能、壓縮率和壓縮精度三項指標(biāo)間進(jìn)行權(quán)衡，以達(dá)到最適合應(yīng)用場景的壓縮方案。以上方法或增加數(shù)據(jù)處理步驟，或引入了復(fù)雜的數(shù)學(xué)計算，在提高壓縮率或壓縮精度的同時也增加了算法復(fù)雜度，而對于海量數(shù)據(jù)的處理算法是否高效尤為重要。這些方法對所要處理的所有數(shù)據(jù)一視同仁，均使用相同的壓縮策略。而現(xiàn)實中，如對環(huán)境監(jiān)測數(shù)據(jù)，往往比較關(guān)心高于或低于某一限值的異常值，對于數(shù)據(jù)在正常值附近波動并不那么敏感。在這種情況下，對所有數(shù)據(jù)使用相同的壓縮策略是不合適也不高效的。本文提出一種基于數(shù)據(jù)敏感自適應(yīng)的SDT改進(jìn)算法，根據(jù)數(shù)據(jù)的敏感程度使用不同的壓縮策略，能更好地適用這種場景。

1 旋轉(zhuǎn)門壓縮算法簡介

旋轉(zhuǎn)門壓縮算法是一種用于時序數(shù)據(jù)壓縮的有損壓縮算法[9-11]。其原理如圖1所示。

圖1 標(biāo)準(zhǔn)SDT算法示意圖

A點為數(shù)據(jù)開始記錄點，在A點上方和下方分別取兩點A+和A-，橫坐標(biāo)與A點相同，縱坐標(biāo)與A點相差一個容差參數(shù)ΔE。從A點開始向后遍歷數(shù)據(jù)，分別從A+和A-點向下一數(shù)據(jù)點B畫線，得到A+B與A-B兩扇門，∠AA+B與∠AA-B為兩扇門的夾角。用同樣的方式去處理后面的數(shù)據(jù)點，兩扇門的角度只能增大不能減小，且要保證兩夾角之和不能超過180°。如對于數(shù)據(jù)點C，需要將下面這扇門打開更大的角度來包含住C點，上面那扇門不變。因為兩扇門夾角不超過180°，所以本壓縮周期繼續(xù)。直到處理到E點時，此時上面的那扇門為A+D，要想包含E點，需要把下面的那扇門打開至A-E的位置。這樣兩扇門的夾角和就會超過180°，因此需要結(jié)束本次壓縮周期，記錄上一數(shù)據(jù)點D作為此周期的結(jié)束點，并將E點作為起點開始新的壓縮周期。使用這樣的方式，只記錄了A、D兩點的值，舍棄了中間的數(shù)據(jù)點B、C，達(dá)到壓縮數(shù)據(jù)的目的。

2 改進(jìn)的算法

通過研究標(biāo)準(zhǔn)SDT算法，本文提出了一種基于數(shù)據(jù)敏感度自適應(yīng)的SDT改進(jìn)算法(Sensitivity Adaptive Swinging Door Trending，SASDT)。與算法相關(guān)的參數(shù)及表示形式如下：

ΔE：容差參數(shù)；

k：ΔE的調(diào)整系數(shù)(0

ΔEL-min:寬松標(biāo)準(zhǔn)容差范圍下限；

ΔEL-max:寬松標(biāo)準(zhǔn)容差范圍上限；

ΔES-min:嚴(yán)格標(biāo)準(zhǔn)容差范圍下限；

ΔES-max:嚴(yán)格標(biāo)準(zhǔn)容差范圍上限；

Smax:單個壓縮周期的最大步長；

S:本次壓縮周期的步長；

S1:上次壓縮周期的步長；

M:敏感數(shù)據(jù)區(qū)間；

T:當(dāng)前壓縮周期的壓縮類型，類型分為敏感數(shù)據(jù)壓縮與非敏感數(shù)據(jù)壓縮兩類。

2.1 算法思想

在傳統(tǒng)的旋轉(zhuǎn)門壓縮算法中，ΔE是決定壓縮率與壓縮精度的重要參數(shù)。本文基于兩個方面的因素來動態(tài)地調(diào)整ΔE的值，一是數(shù)據(jù)點的敏感程度，二是數(shù)據(jù)變化波動大小。

數(shù)據(jù)的敏感度區(qū)間可由用戶靈活設(shè)置，使得用戶關(guān)心的數(shù)據(jù)具有較小的壓縮誤差。原始數(shù)據(jù)敏感度較低時使用ΔE較大的寬松標(biāo)準(zhǔn)，對高敏感度的原始數(shù)據(jù)使用ΔE較小的嚴(yán)格標(biāo)準(zhǔn)，以此來提高低敏感度數(shù)據(jù)的壓縮率和高敏感度數(shù)據(jù)的壓縮精度。在寬松或嚴(yán)格的不同標(biāo)準(zhǔn)范圍內(nèi)，根據(jù)數(shù)據(jù)的波動大小來自動調(diào)整ΔE，做到進(jìn)一步精準(zhǔn)壓縮。

因為旋轉(zhuǎn)門壓縮算法的壓縮原理就是將變化波動小于某一值的一組連續(xù)數(shù)據(jù)用一條線段來擬合表示，所以一次壓縮周期的步長就表示了數(shù)據(jù)波動相對穩(wěn)定的連續(xù)長度?？梢杂貌介L來表征當(dāng)前數(shù)據(jù)的變化波動趨勢，當(dāng)步長較大時說明數(shù)據(jù)具有長時間穩(wěn)定的趨勢，反之則說明數(shù)據(jù)波動較大。在改進(jìn)的算法中，數(shù)據(jù)當(dāng)前壓縮周期的步長大于上一周期步長時說明數(shù)據(jù)波動在趨于穩(wěn)定，以系數(shù)k按比例增大ΔE可取得更好的壓縮率；反之則說明數(shù)據(jù)波動趨于變化，以系數(shù)k按比例減小ΔE來降低壓縮誤差。

2.2 算法步驟

算法：基于數(shù)據(jù)敏感度自適應(yīng)的SDT改進(jìn)算法

輸入：原始監(jiān)測時序數(shù)據(jù)

輸出：壓縮后的時序數(shù)據(jù)

步驟1：讀取待壓縮數(shù)據(jù)，根據(jù)數(shù)據(jù)是否在敏感區(qū)間M內(nèi)，判斷數(shù)據(jù)是否為敏感數(shù)據(jù)。若數(shù)據(jù)敏感度與當(dāng)前壓縮類型一致，則進(jìn)行步驟2；若不一致，則進(jìn)行步驟5。

步驟2：判斷當(dāng)前壓縮周期步長是否超過最大步長Smax，若未超過則進(jìn)行步驟3，若超過則進(jìn)行步驟4。

步驟3：根據(jù)旋轉(zhuǎn)門算法判斷待壓縮數(shù)據(jù)是否可以被當(dāng)前壓縮周期壓縮。若可以，則本壓縮周期步長加1，進(jìn)行步驟6；否則跳至步驟4。

步驟4：記錄上一個原始數(shù)據(jù)作為本壓縮周期的結(jié)尾數(shù)據(jù)。根據(jù)S與S1的比較結(jié)果來調(diào)整ΔE。當(dāng)S≥S1時，ΔE=ΔE*(1+k)；當(dāng)S

步驟5：記錄上一個原始數(shù)據(jù)作為本壓縮周期的結(jié)尾數(shù)據(jù)。根據(jù)當(dāng)前數(shù)據(jù)的敏感度旋轉(zhuǎn)相應(yīng)的壓縮標(biāo)準(zhǔn)，將使用的壓縮標(biāo)準(zhǔn)類型賦值給T。重置參數(shù)ΔE，若為寬松標(biāo)準(zhǔn)，則ΔE=(ΔEL-min+ΔEL-max)/2；若為嚴(yán)格標(biāo)準(zhǔn)，則ΔE=(ΔES-min+ΔES-max)/2。將S1和S初始化為1。使用這些參數(shù)，從當(dāng)前數(shù)據(jù)開始，啟動新的壓縮周期，進(jìn)行步驟1。

步驟6：判斷是否還有新數(shù)據(jù)，若有則執(zhí)行步驟1，若無則記錄本壓縮周期首尾數(shù)據(jù)，結(jié)束壓縮周期，退出。

基于數(shù)據(jù)敏感度自適應(yīng)的SDT改進(jìn)算法流程圖如圖2所示，本算法相比標(biāo)準(zhǔn)的SDT算法主要有兩方面改進(jìn)：一是根據(jù)數(shù)據(jù)敏感度的不同，采用不同的容差標(biāo)準(zhǔn)進(jìn)行壓縮，可以使得用戶敏感的數(shù)據(jù)具有較低的壓縮誤差，同時從非敏感數(shù)據(jù)部分得到壓縮率的補(bǔ)償；二是根據(jù)數(shù)據(jù)的波動情況動態(tài)地調(diào)整容差，可以進(jìn)一步提高壓縮率。

圖2 改進(jìn)的算法流程圖

3 算法分析

為了驗證改進(jìn)算法的有效性，本文使用Java語言編寫實現(xiàn)了標(biāo)準(zhǔn)SDT算法、文獻(xiàn)中最新研究的自適應(yīng)SDT算法(Adaptive Swinging Door Trending，ASDT)[6]和本文提出的基于數(shù)據(jù)敏感度的自適應(yīng)SDT算法(SASDT)，分別使用這三種算法處理相同的數(shù)據(jù)，以比較算法的性能。

3.1 評價指標(biāo)

本文將壓縮率CR、均方根誤差e以及壓縮耗時作為衡量算法性能的三個指標(biāo)[12]。計算公式如下：

其中，m是壓縮刪除的數(shù)據(jù)量，n是原始數(shù)據(jù)量。

3.2 對比分析

待壓縮的原始數(shù)據(jù)來源于實際環(huán)境監(jiān)測數(shù)據(jù)，包括溫度數(shù)據(jù)和濕度數(shù)據(jù)。選取10組監(jiān)測數(shù)據(jù)，每組數(shù)據(jù)量為10 000個。標(biāo)準(zhǔn)SDT算法中參數(shù)為：容差范圍ΔE=1.5，最大步長Smax=100；在ASDT算法中，容差參數(shù)ΔEmin=1，ΔEmax=2,最大步長Smax=100；在SASDT算法中，調(diào)整系數(shù)k=0.2，寬松標(biāo)準(zhǔn)容差參數(shù)ΔEL-min=1.5，ΔEL-max=3,嚴(yán)格標(biāo)準(zhǔn)容差參數(shù)ΔES-min=0.5，ΔES-max=1，最大步長Smax=100，敏感數(shù)據(jù)區(qū)間根據(jù)數(shù)據(jù)類型而定。對多組數(shù)據(jù)執(zhí)行壓縮算法后，得到性能平均結(jié)果如表1所示。

表1 各算法壓縮性能結(jié)果比較

從結(jié)果可以看出，相較于標(biāo)準(zhǔn)SDT算法，SASDT算法壓縮率有小幅提升，壓縮誤差減小了32%，效果明顯；與ASDT算法比較，SASDT算法在壓縮率與壓縮誤差上也均得到優(yōu)化。

SASDT算法復(fù)雜度與標(biāo)準(zhǔn)SDT算法相比，僅僅是在處理每個數(shù)據(jù)點時進(jìn)行一次比較來判斷數(shù)據(jù)的敏感度。而且調(diào)整容差的依據(jù)也是通過壓縮步長來判斷的，不需要額外增加計算和統(tǒng)計。因此，改進(jìn)算法的時間復(fù)雜度與標(biāo)準(zhǔn)SDT算法的復(fù)雜度差別不大，從表1中的結(jié)果也可以看出這點。而ASDT由于增加了數(shù)據(jù)處理步驟且引入了復(fù)雜的數(shù)學(xué)計算，因此在運(yùn)行時長上耗時較大，大約是SASDT算法的50倍。在海量數(shù)據(jù)的處理中，算法的運(yùn)行效率尤為重要。

圖3 壓縮恢復(fù)數(shù)據(jù)對比圖

從壓縮數(shù)據(jù)中選取一段進(jìn)行還原并繪制折線圖，比較標(biāo)準(zhǔn)SDT算法與SASDT算法壓縮數(shù)據(jù)的還原情況，結(jié)果如圖3所示。從圖3明顯可以看出，在1：00～3：00和5：00～9：00這兩個時間段中SASDT算法的壓縮精度更高，數(shù)據(jù)還原更準(zhǔn)確，保留了很多標(biāo)準(zhǔn)SDT算法中沒有的變化趨勢與細(xì)節(jié)。

3.3 應(yīng)用實例

本文提出的基于數(shù)據(jù)敏感度自適應(yīng)的SDT改進(jìn)算法已應(yīng)用在一個實時監(jiān)測系統(tǒng)中，使用效果如圖4所示。將系統(tǒng)中的歷史監(jiān)測數(shù)據(jù)進(jìn)行壓縮，可大大減少系統(tǒng)所需的存儲空間。由于算法復(fù)雜度低，運(yùn)行效率很高，能快速高效地對大量歷史數(shù)據(jù)進(jìn)行壓縮。同時數(shù)據(jù)解壓簡單高效，也能滿足系統(tǒng)實時查詢歷史數(shù)據(jù)的要求。數(shù)據(jù)還原能夠反映原始數(shù)據(jù)的變化狀態(tài)，而且對于敏感數(shù)據(jù)具有較高的還原精度。系統(tǒng)可以根據(jù)需要動態(tài)地調(diào)整敏感數(shù)據(jù)區(qū)間，也可以靈活地更改嚴(yán)格和寬松的容差范圍，以滿足系統(tǒng)需求的同時取得最好的壓縮效率與壓縮精度。目前，該系統(tǒng)已投入實際使用，數(shù)據(jù)壓縮及解壓功能運(yùn)行正常，用戶反饋良好，改進(jìn)算法的有效性與穩(wěn)定性得到了進(jìn)一步驗證。

圖4 實際應(yīng)用效果圖

4 結(jié)論

本文通過對應(yīng)用場景需求的分析以及對標(biāo)準(zhǔn)SDT算法的研究，從數(shù)據(jù)敏感度和動態(tài)調(diào)整容差兩個方面入手，提出并實現(xiàn)了基于數(shù)據(jù)敏感度自適應(yīng)的SDT改進(jìn)算法。該算法針對原始數(shù)據(jù)敏感度不同的問題，采用精度不同的容差標(biāo)準(zhǔn)，保證了用戶關(guān)心的數(shù)據(jù)的壓縮精度；同時，根據(jù)相鄰壓縮周期的步長變化，動態(tài)調(diào)整下一壓縮周期的容差值，這樣可以減少波動較小的

平穩(wěn)數(shù)據(jù)的記錄量，進(jìn)而提高數(shù)據(jù)壓縮率。該算法復(fù)雜度低，沒有增加復(fù)雜的數(shù)學(xué)計算，具有很高的效率。經(jīng)過性能對比及實際的使用，算法的有效性得到驗證，可靈活高效地應(yīng)用于各種環(huán)境中監(jiān)測數(shù)據(jù)的壓縮場景。

[1] 楊冠杰, 李悅. 工業(yè)實時數(shù)據(jù)壓縮算法的分析[J]. 自動化與儀器儀表, 2016(8):214-215.

[2] 劉佳寶, 梁奕, 方俊. 一種過程數(shù)據(jù)有損壓縮比的動態(tài)控制方法[J]. 計算機(jī)工程與應(yīng)用, 2013, 49(8):138-141.

[3] 趙旭東, 丁杰雄, 邊志遠(yuǎn),等. SDT改進(jìn)算法在數(shù)控系統(tǒng)監(jiān)控平臺中的應(yīng)用[J]. 制造技術(shù)與機(jī)床, 2014(10):155-159.

[4] Li Xinli, Qiu Hongkai, Zhu Yaochuan. Research and design of lossy compression algorithm in embedded real-time database[C]// Proceedings of the Second International Conference on Mechatronics and Automatic Control. Springer International Publishing, 2015:1027-1034.

[5] 邢銳, 祁奇, 鄭滔. 改進(jìn)的SDT算法[J]. 計算機(jī)工程與設(shè)計, 2013, 34(2):515-518.

[6] 張宗華, 葉志佳, 牛新征. 面向監(jiān)測數(shù)據(jù)壓縮的自適應(yīng)SDT算法[J]. 中國測試, 2017, 43(2):104-108.

[7] 張煒, 王英潔, 鄔蓉蓉. 面向油中溶解氣體監(jiān)測時序數(shù)據(jù)壓縮的改進(jìn)方法[J]. 電力建設(shè), 2017, 38(5):98-104.

[8] 邱紅鍇. 用電及能效信息采集系統(tǒng)嵌入式實時數(shù)據(jù)庫關(guān)鍵技術(shù)研究[D]. 北京：華北電力大學(xué), 2015.

[9] 于松濤, 王曉琨, 趙利強(qiáng),等. 基于容差動態(tài)調(diào)整的旋轉(zhuǎn)門(SDT)改進(jìn)算法[J]. 北京化工大學(xué)學(xué)報(自然科學(xué)版), 2013, 40(3):109-113.

[10] 曲奕霖, 王文海. 用于過程數(shù)據(jù)壓縮的自控精度SDT算法[J]. 計算機(jī)工程, 2010, 36(22):40-42.

[11] Chen Gang, Li Li. An optimized algorithm for lossy compression of real-time data[C]// IEEE International Conference on Intelligent Computing and Intelligent Systems. IEEE, 2010:187-191.

[12] 寧海楠. 一種基于SDT算法的新的過程數(shù)據(jù)壓縮算法[J]. 計算機(jī)技術(shù)與發(fā)展, 2010, 20(1):25-28.