OpenHarmony啃論文俱樂部——物聯(lián)網(wǎng)搖擺門趨勢算法
【本期看點】
- Hadoop和Spark框架的性能優(yōu)化系統(tǒng)。
- 云計算重復數(shù)據(jù)刪除技術降低冗余度。
- 壓縮框架Ares如何統(tǒng)一不同算法。
- 在線數(shù)據(jù)壓縮“搖擺門趨勢”。
- 揭秘新型移動云存儲SDM。
【技術DNA】
物聯(lián)網(wǎng)
什么是物聯(lián)網(wǎng)?物聯(lián)網(wǎng)是通過信息傳感設備，按照某種協(xié)議，把任何物品與互聯(lián)網(wǎng)連接起來，進行信息交換和通信，在這個網(wǎng)絡中，物與物之間能夠彼此進行“交流”，現(xiàn)實世界的物與數(shù)字世界相連，而無需人的干預，實現(xiàn)智能化。它的滲tou性強、帶動作用大、綜合效益好，能夠?qū)崿F(xiàn)“物物相連的互聯(lián)網(wǎng)”，像智能家居、智能醫(yī)療、智能城市…
而由設備收集的數(shù)據(jù)的傳輸和存儲是物聯(lián)網(wǎng)(IoT)的重要組成部分。如今，數(shù)據(jù)生成的增長速度遠遠快于存儲能力。云計算可以以最小的管理工作快速啟動和供應，并為物聯(lián)網(wǎng)帶來巨大的優(yōu)勢。但當傳輸無關或冗余數(shù)據(jù)時會消耗更多能，使用通信信道，處理對應用程序貢獻很小的數(shù)據(jù)，無疑是一種浪費。
壓縮傳輸和存儲的數(shù)據(jù)是必要的，所以提出了在物聯(lián)網(wǎng)應用中使用擺動門趨勢(SDT)。
擺動門趨勢(SDT)
擺動門趨勢(SDT)是一種在線有損數(shù)據(jù)壓縮算法，通常用于監(jiān)看控制和數(shù)據(jù)采集系統(tǒng)，目的在于存儲來自過程信息系統(tǒng)的歷史數(shù)據(jù)。壓縮偏差(CD)是它最重要的參數(shù)，它代表當前樣本和當前用于表示之前收集的數(shù)據(jù)的線性趨勢之間的最大差異。
傳統(tǒng)SDT算法是在一定誤差范圍內(nèi)，用起點和終點確定的直線代替兩點之間其他的數(shù)據(jù)點，SDT 算法的壓縮率關鍵取決于容差(門)的大小。而在起點上下距離為CD的地方有上邊界UP和下邊界LP，構成了旋轉(zhuǎn)的兩扇門。這兩扇門在壓縮過程中一旦打開之后就不能關閉，直到該壓縮區(qū)間壓縮結(jié)束。如果兩扇門的內(nèi)角和大于或者等于180度，壓縮停止，否則壓縮繼續(xù)。該壓縮區(qū)間結(jié)束之后,以壓縮區(qū)間的終點為下一壓縮區(qū)間的起點繼續(xù)壓縮。
SDT結(jié)構簡單，計算復雜度較低，并且使用線性趨勢來表示一個數(shù)據(jù)量。通過帶有固定樞軸的“擺動門”連續(xù)構造圖形來過濾數(shù)據(jù)。但因為容差CD參數(shù)應該是預先運行時定義的“門”，所以有時候并不準確，后文將提出改進方法。
八個步驟
- 接收到第一點。
- 建立上下樞軸點。
- 接收下一點。
- 計算相對于上下樞軸的當前坡度。
- 比較當前坡度與之前的極端坡度。
- 當某個點在平行四邊形外時，計算最后一個點與當前點之間的斜率。交叉的邊界被調(diào)整為與其他邊界平行。計算出交叉邊界與斜率之間的一個攔截點，并確定一個新的第一點。
- 傳送點c作為輸出信號的壓縮數(shù)據(jù)流中的輸出點。
性能標準
壓縮誤差(CE)和壓縮率(CR)是評估壓縮算法性能的重要指標。
CE測量壓縮后觀察到的相對誤差量，它的計算方法是將未壓縮數(shù)據(jù)(Ti)與解壓縮過程(T0i)后的壓縮數(shù)據(jù)結(jié)果之間的差異的總和，除以未壓縮數(shù)據(jù)的絕對值的總和。
CR旨在評估壓縮過程的效率，并表示使用壓縮算法實現(xiàn)的樣本的減少。它被計算為壓縮樣本除以未壓縮樣本的補充。
提出稱為壓縮標準(CC)，良好的壓縮體現(xiàn)于CC值接近于1，對應于高CR和低CE值。
論文中提出4個不同數(shù)學方程版本：
算術平均值(MEAN)：
指數(shù)移動平均線：
沒有零的平均數(shù)：
范圍：
運用這四種方程式更方便找到最優(yōu)解。
相關工作
這一部分介紹一些物聯(lián)網(wǎng)環(huán)境的數(shù)據(jù)壓縮算法以及SDT的更多內(nèi)容。
物聯(lián)網(wǎng)中的數(shù)據(jù)壓縮
對物聯(lián)網(wǎng)輸入數(shù)據(jù)流的近似算法
這個算法的主要的思想是利用數(shù)據(jù)中的一部分值去近似表示所有的數(shù)據(jù)。算法的特點是計算復雜度低，壓縮率高，但是錯誤率高。
下面結(jié)合原論文中的一組圖來直觀地感受算法的過程：
輸入一組具有相同時間間隔的離散時序數(shù)據(jù)，并按照時間將其從1開始編號。
將上述編好號的數(shù)據(jù)分為“最大值”和“最小值”兩個部分，其中最大值的定義為比前一個數(shù)據(jù)大的值，最小值的定義為比前一個數(shù)據(jù)小的值，如果一個數(shù)據(jù)位于序列的開始或結(jié)尾或者與前一個數(shù)據(jù)的值相等，則可以同時標記為兩個狀態(tài)。
分別在“最大值”和“最小值”中找到它們對應的極值。
按順序連接“最大值”和“最小值”對應的極值點。
增量壓縮編碼方案
所謂增量，指的是一組數(shù)據(jù)中相鄰值之間的差，通過記錄一組差值和初始值即可表示整個數(shù)據(jù)。下面介紹基于增量壓縮的編碼方案，論文中的分析場景是一組溫度數(shù)據(jù)的壓縮。
數(shù)據(jù)特點：
傳感器通過ADC將現(xiàn)實世界中的溫度轉(zhuǎn)換為一個個離散的數(shù)據(jù)，而且這個數(shù)據(jù)是有限的，假設ADC可以將溫度映射到包含1024個值的集合，那么對應的某一時刻的溫度也即該時刻的狀態(tài)一定對應狀態(tài)空間S中的一個狀態(tài)。假設傳感器記錄溫度的頻率為f_sfs，則數(shù)據(jù)之間的時間間隔為T=1/f_sT=1/fs，我們用u(nT)\in S, n=0, 1, ..., \inftyu(nT)∈S,n=0,1,...,∞表示一組ADC的輸出，那么增量可以表示為\Delta(kT)=u[kT]-u[(k-1)T]Δ(kT)=u[kT]?u[(k?1)T]，或者簡寫為\Delta(k)=u(k)-u(k-1)Δ(k)=u(k)?u(k?1)，對一組增量進行統(tǒng)計分析：
可以看出\DeltaΔ出現(xiàn)的頻率服從正態(tài)分布，而且-1、0、和1這三個值的頻率加起來接近0.9。參考Huffman編碼的思想，如果可以設計一套編碼方案，可以用較短的編碼代替出現(xiàn)頻率高的\DeltaΔ，那么可以達到比較好的壓縮效果。
增量壓縮：
考慮到傳感器、ADC能夠檢測出的溫度的變化是有限的，即當數(shù)據(jù)變化量小于一個閾值\thetaθ時，可以認為它們是相等的。作者設計了六個基本的符號，其中三個可以直接表示\DeltaΔ的值為0,\theta,-\theta0,θ,?θ，剩余的三個符號需要結(jié)合起來表示\DeltaΔ的絕對值大于\thetaθ的情況：
表一 六個基本符號。
表二 \Delta的絕對值大于\theta的情況。
如果增量的絕對值超過一個閾值，那么采用FLAG+UPF/DOWNF+FLAG的方式表示增量的大小，其中UPF或者DOWNF的個數(shù)為abs(\Delta/\theta)-1abs(Δ/θ)?1。當增量很大時，數(shù)據(jù)不進行編碼，否則編碼后的比特數(shù)比原比特數(shù)還要大，但是這種情況出現(xiàn)的概率極低。
云存儲中物聯(lián)網(wǎng)傳感器數(shù)據(jù)的壓縮和存儲優(yōu)化
在論文中作者提出一種用于 IoT 數(shù)據(jù)的兩層壓縮框架，該框架可減少數(shù)據(jù)量，同時保持最小錯誤率并且避免帶寬浪費。在該方案中，首先在霧節(jié)點以 50% 的壓縮率進行了初始壓縮，在云存儲中再將數(shù)據(jù)壓縮到了 90%。論文還表明解壓后誤差與原始數(shù)據(jù)相差 0% 到 1.5%。
具體步驟為：
1、霧節(jié)點的壓縮。
a. 從傳感器節(jié)點接受一組數(shù)據(jù)。
b. 判斷傳感器節(jié)點是否注冊，如果是則進行下一步驟，否則拋棄數(shù)據(jù)。
c. 對數(shù)據(jù)進行升序排序，并且計算兩個連續(xù)值的平均值，通過此步驟將數(shù)據(jù)壓縮為原來的50%。
d. 將壓縮后的數(shù)據(jù)寫入文件發(fā)送到云端。
2、云壓縮。
a. 接受來自霧節(jié)點的數(shù)據(jù)文件。
b. 判斷霧節(jié)點是否注冊，如果是則進行下一個步驟，否則拋棄數(shù)據(jù)。
c. 從文件中讀取數(shù)據(jù)，然后統(tǒng)計每一個值出現(xiàn)的頻率，重新寫入文件，記錄為兩列，此時壓縮率達到90%。
例：數(shù)據(jù)由1到10的100個值組成，最終得到十個數(shù)和它們對應的頻率。
SDT
自適應SDT
自適應SDT(Adaptive Swinging Door Trending)基本過程與SDT相同，只是采用了自適應的壓縮偏差CD。通過使用指數(shù)移動平均(EMA)為過濾器分析數(shù)據(jù)。指數(shù)移動平均與線性移動平均不同的是可以在使數(shù)據(jù)趨于平滑的同時突出局部的變化，因此采用了加權平均，離當前時刻越近的值權重越大。
式中的N是需要人為設定的參數(shù)，所以ASDT的一個缺點在于需要提前設置EMA的參數(shù)。
改進的SDT
改進的SDT(ISDT)的目標是1) 檢測并消除異常值，2) 采用自適應的壓縮偏差獲得更好的壓縮效果。
ISDT相比于之前提到的SDT多了強制存儲記錄限制(Forced Storage-Recording Limit, FSRL)和調(diào)整因子(adjustment factor, F_{adj}\in(0, 1)Fadj∈(0,1))，這兩個值是自適應調(diào)整壓縮偏差的關鍵。
ISDT檢測異常值
SDT算法結(jié)束當前壓縮區(qū)間、開啟新的壓縮區(qū)間的條件是最大上角(a_{umax})和最大下角(a_{lmax})最大上角(aumax)和最大下角(almax)之和大于等于180。在ISDT中，當一個數(shù)據(jù)值x_kxk滿足開啟新的壓縮區(qū)間時，并不會立即關閉當前區(qū)間，而是檢查下一個數(shù)據(jù)值x_{k+1}xk+1是否可以包含在當前的壓縮區(qū)間內(nèi)。如果可以，則表明x_kxk是一個異常值，因此不記錄這個值，而是從x_{k+1}xk+1開始繼續(xù)當前壓縮區(qū)間。
ISDT自適應壓縮偏差
我們先理解FSRL，即強制存儲記錄限制，意思是當一個壓縮區(qū)間記錄k個值且k=FSRL時，即使下一個值可以包含在當前的區(qū)間內(nèi)，但是強制關閉當前區(qū)間并以當前點為下一個區(qū)間的初始值。
如果一個區(qū)間在區(qū)間長度達到FSRL后被強制截斷，說明當前的壓縮偏差偏大或者數(shù)據(jù)處于穩(wěn)定階段，那么可以用CD:=CD\times f_{adj}CD:=CD×fadj替換原來的壓縮區(qū)間;反之，如果在區(qū)間長度達到FSRL前關閉，說明當前壓縮偏差設置地偏小或者數(shù)據(jù)波動較大，這時可以用CD:=CD/f_{adj}CD:=CD/fadj替換原來的壓縮區(qū)間。
分布式SDT
支持智能電網(wǎng)的電力物聯(lián)網(wǎng)具有以下特點：
- 具有大量傳感器。
- 具有多種傳感器。
- 具有非常高的數(shù)據(jù)采集頻率。
- 具有高度異構的網(wǎng)絡。
正式因為由于上述特點，如果將傳感器收集的所有原始時間序列數(shù)據(jù)通過網(wǎng)絡傳輸?shù)絺鞲袛?shù)據(jù)中心，然后壓縮和保留，帶寬和計算網(wǎng)絡和傳感數(shù)據(jù)中心的資源需求分別是不可接受的。傳感器對原始傳感數(shù)據(jù)進行壓縮，然后將初始壓縮的數(shù)據(jù)傳輸?shù)絺鞲袛?shù)據(jù)中心，在傳感數(shù)據(jù)中心進一步壓縮和保留數(shù)據(jù)。這樣，網(wǎng)絡和傳感數(shù)據(jù)中心的帶寬和計算資源需求都會顯著降低。
DSDT是傳統(tǒng)SDT的分布式版本，與上文提到的 IoT 數(shù)據(jù)的兩層壓縮框架類似，在傳感器節(jié)點壓縮數(shù)據(jù)可以減少傳輸?shù)膲毫Α６?，由于SDT算法本身的優(yōu)點，每次更新壓縮區(qū)間只需要確定一個初始點和壓縮偏差即可，所以可以實現(xiàn)壓縮中心轉(zhuǎn)移的操作，即壓縮中心在傳感數(shù)據(jù)中心和傳感器之間可以動態(tài)的變化，具體如何轉(zhuǎn)移取決于計算資源和帶寬資源的分配。下圖為SDT和DSDT區(qū)別的直觀解釋：
