基于字典學習和壓縮感知的WSN數據壓縮

楊欣宇，李愛萍，段利國，趙菊敏

(太原理工大學 信息與計算機學院，山西 晉中 030600)

0 引 言

作為物聯網(internet of things，IoT)[1]的重要組成部分，無線傳感網 (wireless sensor networks，WSN)[2]已被普遍應用于環境監測、軍事防御、智慧農業等各個領域，應用普及產生的數據量與日俱增，由此造成的存儲、傳輸、處理等需求也越來越大，WSN數據壓縮的研究多年來一直是IoT應用推廣最為關鍵的技術之一。

近年來，已有多種方法進行WSN數據的壓縮[3]研究，但壓縮效果仍有進一步提升的空間。LUO等[4]提出將壓縮感知(compressed sensing，CS)[5]理論應用于大規模WSN數據收集，該方法能大幅、有效提高數據壓縮比，但針對不同應用場景中監測數據的特征差異，采用固定的稀疏基運算時會出現稀疏表示結果不精確、數據重構精度低的問題。此外，感知節點處理能力有限，經典的基于CS的WSN數據壓縮方法直接在感知節點上進行稀疏變換、矩陣測量等大量運算，不僅縮短網絡壽命而且延緩了傳輸時間。

基于上述問題，提出一種基于字典學習和CS的WSN數據壓縮模型。模型改進K-SVD初始字典，利用歷史數據集訓練適應數據特征的K-SVD稀疏基，從而保證在減少數據傳輸量的同時提高數據恢復精度；優化基于CS的WSN數據收集模型，把復雜的稀疏變換由感知節點轉移到基站，延長網絡壽命。在Berkeley實驗室的溫度數據集[6]上做對比實驗，其結果表明，針對時空相關性較強的監測數據的壓縮和恢復效果，本文方法比已有的OEGMP、基于DCT稀疏基的CS壓縮等方法有明顯提升。

1 相關工作

1.1 WSN組成及特點

WSN由部署在監測區域內的眾多感知節點和功能強大的融合中心(基站或匯聚節點)構成，感知節點之間以多跳自組的方式，把監測數據傳送到融合中心[2]。WSN感知節點的計算、存儲能力、通訊帶寬及電源能量都很有限，需要盡可能節省能耗。因此，有必要對WSN中感知層收集的大量數據在傳輸之前進行壓縮，然后在應用層進行解壓后再使用。

一般的WSN數據具有數據量大、實時性強、時空相關性等性質，且不同場景下的WSN，產生的監測數據特征也各不相同。

1.2 壓縮感知理論

壓縮感知理論于2006年由Donoho等[5]正式提出以來，已被廣泛應用于無線通信、圖像處理、數據采集等領域，其主要內容包括3部分：信號的稀疏變換、矩陣測量和信號重構，如圖1所示。

圖1 CS理論組成部分

設N×1維信號X是稀疏的，或者在某個變換域上可進行稀疏分解得到式(1)

X=Ψθ

(1)

θ是稀疏度為K(K?N) 的N×1維列向量，即θ中只有K個非零項。然后將該稀疏系數投影到另一個與變換基Ψ不相關的、維數為M×N(M?N) 的觀測矩陣Φ上，得到M×1維觀測集合y， 如式(2)所示，其中ACS稱為傳感矩陣

y=Φθ=ΦΨTX=ACSX

(2)

Candès、Tao等給出式(2)存在確定解的充分必要條件是：Φ與Ψ互不相關[7]，那么可以憑借這些觀測值求解式(3)而得到信號X的精確恢復

(3)

信號的稀疏性或可壓縮性，是CS應用的基礎和前提，也是數據重構的關鍵，所以尋找一個能夠把信號有效稀疏表示的稀疏基，成為研究CS的重要內容之一。

1.3 現有的WSN數據壓縮方法

隨著WSN應用規模不斷擴大，數據量不斷倍增，已有許多工作人員對提高數據壓縮效率，減少數據傳輸量展開了深入研究[3,8]。

WSN監測數據大多在時間和空間上具有相關性。消除時間冗余較經典的算法，有預測編碼類[9]、線性回歸算法[10]等。通常通過路由結構來處理具有空間相關性的數據，LEACH(low energy adaptive clustering hierarchy)算法[11]在目前WSN數據壓縮領域得到了良好的應用。喬建華等[8]全面闡述了基于CS的WSN壓縮數據收集算法，表明CS理論在WSN中的適用性，總結出壓縮比較小、稀疏基不適、數據恢復不精確等問題。Xie等[12]將差分矩陣用作稀疏基，結合改進的LEACH算法對WSN數據作壓縮研究，實驗結果表明該方法有效減少了數據傳輸量，但壓縮步驟較復雜。因此，使用路由算法是提高數據壓縮率的有效方法之一，同時，將稀疏變換轉移到基站可有效降低壓縮復雜度并減少節點能耗。

數據能否精確重構不僅取決于重構算法，還依賴于數據能否稀疏表示。K-SVD字典學習算法[13]與壓縮感知理論的結合已在多個領域進行了大量研究，朱路等[14]將其用于圖像降噪，弓震等[15]使用該技術對地震資料去噪。在壓縮感知框架下，K-SVD字典對各類數據都展現出了較好的稀疏表示效果。綜上，本文訓練K-SVD字典對WSN數據進行稀疏表示，結合壓縮感知進行WSN數據壓縮研究。

2 K-SVD字典學習

信號的稀疏性是運用CS的前提，雖然在物理環境采集的大多信號并不稀疏，但在某個變換域上可進行稀疏分解的信號就是可壓縮的。K-SVD學習算法能夠適應數據本身特征，對數據稀疏表示。

K-SVD字典學習的主要思想[13]：根據原始樣本數據Y訓練完備字典矩陣D∈Rn×n，D包含n個原子di∈{d1,d2,…,dn}，S為樣本Y在字典D上的稀疏表示，如式(4)所示

Y=DS

(4)

(5)

式中：包含兩個自變量：字典D和稀疏系數S， 要求得使目標函數取最小值時自變量的值，一般是固定其中一個變量，求解另一個變量，如此迭代進行。字典D通過SVD分解或者最小二乘法逐列更新，可以利用已有的經典方法求解稀疏系數S， 如正交匹配追蹤[16](orthogonal matching pursuit，OMP)、基追蹤等算法。本文擬采用OMP算法求解S。

3 基于K-SVD字典和壓縮感知的WSN數據壓縮

本文提出一種基于K-SVD字典和壓縮感知的WSN數據壓縮模型，如圖2所示，模型主要分為3個部分：①在基站，使用改進的K-SVD字典學習算法訓練歷史數據集，得到適合該數據類型的稀疏變換基Ψ；②在感知層，各個簇內的感知節點收集一段時間內的監測數據xi傳輸到簇頭，簇頭只需保存觀測矩陣Φ進行CS壓縮；③壓縮數據yj經過多跳傳輸在基站完成重構。

圖2 基于K-SVD字典和CS的WSN數據壓縮模型

本文模型改進字典學習算法，將離散余弦變換[17](discrete cosine transform，DCT)設定為K-SVD字典學習算法的初始字典，能夠消除數據相關性，加快算法收斂速度，訓練效果更佳；利用LEACH算法[11]將感知節點分簇，對一段時間內采集的數據，傳輸到簇頭進行CS壓縮，可以同時消除數據間的時空冗余，提高壓縮率；改變經典的壓縮感知框架，假設WSN數據在某個變換基上是稀疏可壓縮的，在各個簇頭只進行壓縮感知矩陣測量，將復雜的稀疏變換由感知層轉移到基站。該模型符合WSN中，感知節點硬件資源和能耗有限、基站計算能力較強的特點，有效減輕感知節點負擔，減少壓縮步驟。

3.1 改進的K-SVD字典訓練

由于WSN數據時空相關性較強，在某個變換基上可以稀疏表示，具有CS理論的可壓縮性前提，所以需要對WSN數據進行稀疏變換。傳統的稀疏基結構固定，如DCT、DWT等，不能對各種信號都進行準確的稀疏表示，影響數據重構效果，使用K-SVD字典學習算法可以有效解決這個問題。不需要事先固定稀疏基的形式，而是通過不斷迭代和更新，根據已有信號的特征訓練出合適的稀疏變換字典，提高數據重構精度。本文的K-SVD算法在基站利用歷史數據訓練稀疏基，不僅為感知節點減輕負擔，而且為稀疏變換提供了更可靠和強大的計算能力。

傳統的K-SVD字典學習算法，隨機抽取樣本的數據設置為初始字典進行字典訓練，由于WSN監測數據通常具有較大的時空冗余，數值間的變化幅度較小，數值過于相似，初始字典中存在一定的線性相關性，因此會影響稀疏系數的求解效果，造成字典迭代更新時停滯不變的狀況。離散余弦變換基[17]結構固定，擁有較強的“能量集中”性質，將時域轉換為頻域，信號的能量通常匯集在頻域較低的部分，因此能夠有效去除數據間的相關性。為解決字典訓練效果不佳的問題，本文將DCT設置為初始字典，如式(6)

(6)

式中：u表示DCT矩陣維度，x(n) 是原始數據值。對于高度相關的WSN數據，DCT具有非常好的能量緊湊性，作為初始字典可以有效消除數據間的相關性，提高稀疏字典收斂速度和稀疏表示效果。

(7)

(8)

(9)

對E′k采用奇異值(SVD)分解，分解完成后的左矩陣的第一列賦值給dk， 將新的dk更新到字典D的第k列，即完成了字典的第k列原子的更新。上述過程與稀疏編碼循環執行，直到字典中的各列原子全部更新完畢，本文的字典訓練過程如算法1所示。學習字典訓練時，因為在算法中嵌套兩層循環以更新字典，其中第一層是更新稀疏編碼，第二層在當前編碼下更新字典，要更新字典的n列原子，那么在更新過程中，學習字典的更新需要進行n次，因此該算法時間復雜度為O(n2)， 空間復雜度為O(n)。

算法1：改進的K-SVD字典學習算法

Input：原始樣本、初始字典、稀疏系數

Output：稀疏字典

Begin

(1)初始化：初始字典←DCT稀疏基，j=1；

(2)稀疏編碼：根據上一步得到的字典，求解稀疏編碼；

(3)字典更新：逐列更新字典

3)Ek只選擇索引ωk對應的列得到E′k

5)j=j+1.

(4)判斷樣本稀疏表示后誤差是否達到指定閾值， 若達到輸出字典， 否則繼續執行步驟(2)、 步驟(3)。

End

3.2 感知端數據壓縮

通常，WSN感知節點部署密集，收集監測數據時間間隔較短，數據在時間和空間上存在較高的冗余度，為了處理數據的時空相關性，本文采用LEACH[11]路由算法將感知節點分簇。該算法是以循環的方式隨機選擇簇頭節點，簇頭向周邊節點廣播信息后自組分簇。每個簇內，感知節點將各自采集的一段時間內的數據傳輸到簇頭，在簇頭接收并整合原始數據后，使用CS理論實現WSN數據的壓縮，壓縮數據通過多跳的方式傳送到基站。

鑒于WSN中感知節點計算能力和處理能力有限，本文模型對傳統的CS數據壓縮算法作出改進，假設WSN監測數據都具有可壓縮性，采集到的數據集可以直接進行矩陣觀測，不再需要在感知層完成稀疏變換，該方法可以有效縮短傳輸時延，降低數據壓縮復雜度，減輕感知節點負擔。WSN數據壓縮分為4個步驟：①感知節點間根據自身所剩能量角逐簇頭節點，劃分簇群；②簇內節點傳輸一段時間內的監測數據到簇頭節點；③在簇頭節點完成CS矩陣測量，實現數據壓縮；④壓縮信息以多跳的方式傳輸到基站。

具體壓縮過程如下：第i個節點在一段時間內采集的數據序列的表示如式(10)所示，則簇內n個節點在這段時間內采集的數據可表示成一個m×n維矩陣X， 如式(11)所示

xi=[xi1,xi2,…,xim]T

(10)

(11)

其中，矩陣的列向量代表簇內每個節點的時間序列數據，行向量代表各個節點在相同時間感知的數據，這樣收集來的數據具備了較強的時空相關性，完成數據壓縮可以同時消除時間和空間冗余，提高數據壓縮率。為了方便CS矩陣測量，我們將矩陣X的元素按列的順序展開表示，得到N×1(N=m*n) 維列向量，如式(12)所示

vec(X)=[x11,x12,…,x1m,x21,x22,…,xnm]T

(12)

如圖2所示，在每個簇頭節點，觀測矩陣Φ與簇頭數據vec(X) 相乘，即可完成WSN數據的壓縮步驟，得到壓縮數據y， 如式(13)所示

y=Φ·vec(X)

(13)

壓縮數據經過多跳傳輸，到達基站。為了保證數據可以精確重構，本文使用與大部分正交基高度不相關的高斯矩陣[5]作為觀測矩陣。此處觀測矩陣設定為M×N(M?N) 維，則壓縮數據是M×1維，壓縮后的數據傳輸量遠遠小于原始數據量。通過上述分析可得，WSN數據的壓縮率取決于觀測矩陣的維度，當數據總量N固定時，觀測矩陣行數M越小，則數據壓縮比越小，壓縮效率越高。

3.3 基站數據重構

數據重構是在基站對壓縮數據的解壓縮過程。根據上述分析，基站已知觀測矩陣Φ、適用于該環境數據的稀疏基Ψ(即字典D)和來自感知層的壓縮數據y。由于原始數據X在稀疏基上是可稀疏變換的，可以表示成稀疏基Ψ和稀疏系數θ相乘的形式，如式(1)所示，結合式(13)，原始數據X的求解可以轉換為式(14)

(14)

由于M?N， 方程的個數遠小于未知數的個數，沒有確定性解，式(14)的l0范數問題屬于NP難問題，難以求解。通常，學者們會把l0范數問題看作是l1范數問題或l2范數問題來解決。Candès給出式(14)存在確定解的充分必要條件[7]是：Φ與Ψ互不相關，即滿足有限等距性質(restricted isometry property，RIP)，那么可以憑借這些壓縮數據求解式(14)而得到信號X的精確恢復。本文選用經典的OMP[16]算法對壓縮數據實現重構，加入閾值比較機制來控制算法進程，當數據恢復到理想效果，重構誤差小于設定閾值時，不管迭代次數是否達到初始設定總次數，迭代都可以提前結束，不用再進行后續求解。具體的重構過程如算法2所示。

算法2：OMP重構算法

OMP重構算法

Input：r0，t，Λ0，U0，A，k，ε

Begin

(1)r0←y，t←1，Λ0←?，U0←?；

(2)A的每列aj與rt-1相乘， 找到乘積最大時對應元素的下標， 即λt=argmax||，j=1,2,…,λ,…,n；

(3)令索引Λt=Λt-1∪λt， 索引矩陣Ut=Ut-1∪aλ；

(6)t=t+1， 比較rt與ε，rt<ε則執行步驟(8)， 否則步驟(7)；

(7)t>k繼續執行步驟(8)， 否則返回步驟(2)；

End

其中r0表示初始殘差，t表示迭代次數，Λ0表示索引集合，U0表示按Λ0選出的矩陣，A=ΦΨ，k為算法需要迭代次數。ε代表重構誤差閾值，和迭代次數k同時控制著重構算法的進度。稀疏基Ψ是經過對歷史樣本的字典學習訓練而得，所求的稀疏系數θ更為精確。這里，θ是k稀疏的，即在該向量中只有k個項是非零的，且重構迭代次數為k。 數據解壓縮過程中，重構迭代的次數越多，恢復的數據越精確，同時消耗的時間越多。但在實際應用中，需要根據場景的恢復精度需求選擇合適的迭代次數，加入閾值機制可節省重構時間，數據恢復達到指定效果即可停止重構。重構算法中傳感矩陣A的每列aj與rt-1相乘，A有n列，且需要找到乘積最大時對應元素的下標，因此OMP算法的時間復雜度為O(n2)。

4 實驗及結果分析

4.1 數據集及實驗環境

本文使用數據集[6]進行實驗，該數據集包含在Intel Berkeley實驗室中部署的傳感器收集的溫度、濕度、光強等數據信息。所涉及的算法通過Python編程語言實現，實驗環境為Intel Core i7-8550U CPU@1.8 GHz，運行內存8 GB，64位Windows10操作系統，PyCharm開發平臺。

4.2 性能評價指標

本文選擇3個評價指標來檢測本文模型的有效性。壓縮率(compression ration，CR)是指簇頭節點進行壓縮過后傳輸給匯聚節點的數據量與壓縮之前的原始數據量之比；均方根誤差(root mean square error，RMSE)用來權衡重構值與實際值之間的偏差，RMSE越小，則偏差值越小，恢復數據越精確；相對重構誤差(relative reconstruction error，RRE)反映數據恢復的可信程度。分別如式(15)～式(17)所示

(15)

(16)

(17)

4.3 實驗結果分析

4.3.1 K-SVD字典訓練

實驗處理數據集，取8個相鄰節點(編號14～21)，每個節點每隔一分鐘產生的溫度數據作為樣本訓練集，選取DCT作為初始字典，設定迭代次數和誤差閾值，實驗參數配置見表1。

表1 實驗參數配置

樣本訓練集如下，可以看出，監測數據間的時空相關性較強，相鄰數值相似，作為K-SVD字典學習算法的初始字典線性相關較高，影響字典訓練效果，選取DCT作為初始字典可消除數據相關，提高字典的稀疏表示能力

利用算法2訓練K-SVD字典，得出適應該數據集特征的稀疏變換字典。生成1024×1024維字典如下

4.3.2 簇的大小對數據重構效果的影響

為了確定使用本文模型對WSN數據壓縮時最優簇的大小，需要分析不同簇的大小對數據重構結果的影響。簇內數據量分別取32、64、128、256、512和1024，比較在不同壓縮率下的均方根誤差值。當簇內數據量為32，壓縮率為0.9時，均方根誤差為0.74，恢復數據與真實數據偏差較大，實驗結果表明，由于采集數據量較少，該模型不適用于簇內數據量小于32的情況。其它取值的實驗結果如圖3所示。

圖3 不同簇的大小對數據重構結果的影響

分析圖3結果，伴隨數據量的增長，RMSE逐漸趨于平穩狀態。當簇內數據量較大時，如簇的大小為512和1024，計算量也隨之增長，影響數據的恢復精度。因此當簇內數據量為128和256時，使用該模型壓縮效果更優。

4.3.3 重構迭代次數對數據重構效果的影響

由圖3可知，當簇內原始數據量為512時，重構數據與原始數據之間的均方根誤差約為0.14，此時本文模型的重構收斂速度如圖4所示。選取不同壓縮率，并在該壓縮條件下設置重構算法的不同迭代次數，記錄在不同壓縮率下采取不同迭代次數時，重構數據的RMSE。圖4固定重構數據的RMSE為0.14，代表數據已經有一個良好的恢復效果，統計在不同壓縮率下，達到RMSE為0.14時，OMP算法所需進行的迭代次數。由于改進的K-SVD字典的自適應特性和良好的稀疏表示能力，當數據壓縮率為0.2時，使用OMP算法重構數據所需的迭代次數僅為5次，重構數據的RMSE即可達到0.14，表明本文模型能較快收斂于最優解。

圖4 重構迭代次數和數據壓縮率的關系

4.3.4 對比其它WSN數據壓縮算法

為了比較本文模型與其它WSN數據壓縮算法的性能，將本文提出的壓縮模型分別與OEGMP[9]算法、固定稀疏基DCT算法、隨機選取K-SVD初始字典的CS數據壓縮算法進行對比實驗。實驗模擬了簇內收集數據量為256時，不同壓縮率下數據的恢復情況。如圖5所示，其中加入均方根誤差值(RMSE)為0.1的水平基線，OEGMP算法同樣采用數學的方法只需傳輸少量信息到基站，使用預測類算法解壓數據，但是只有在壓縮率高于0.5時，OEGMP算法的數據恢復精度較高，壓縮率低于0.5時，該算法的數據重構誤差遠大于本文算法；基于DCT稀疏基的CS壓縮算法，由于DCT正交基結構固定，沒有自適應能力，不適應本文實驗的WSN數據特征，壓縮重構效果較差；選取原始樣本作初始字典，未做改進的K-SVD字典學習算法直接訓練出的稀疏變換字典用于本實驗，樣本數據的相關性使得訓練字典稀疏表示不夠精確，重構效果不佳；本文模型改進K-SVD算法，初始字典選擇DCT稀疏基，消除數據相關性，訓練出的字典稀疏表示效果更優，可以看出在壓縮率為0.2時，RMSE即低于0.1，重構效果優于K-SVD初始字典隨機選取的算法，改進后的K-SVD字典對算法性能有一定的提升。

圖5 本文壓縮模型和其它壓縮算法的對比

4.3.5 本文模型壓縮數據恢復效果

取8個感知節點分一個簇，每個點向簇首傳輸32個數據，使用本文提出的基于字典學習和壓縮感知的WSN數據壓縮模型對簇首數據進行壓縮并恢復。分別計算在不同壓縮率下，重構數據與原始數據的相對誤差，如表2(有效數字取小數點后三位)所示，隨著壓縮率的增大，數據相對重構誤差越小。在壓縮率為0.2，OMP算法重構迭代次數為5時，數據重構僅耗時0.0687 s，重構數據與原始數據對比效果如圖6所示。

表2 恢復數據相對重構誤差

圖6 溫度恢復數據與原始數據對比

由圖6可知，本文模型在選取壓縮率為0.2時，能夠有效恢復原始數據，重構數據與原始數據的RMSE為0.098，可以滿足大部分實際應用需求。

5 結束語

本文針對WSN監測環境的數據收集問題，提出一種基于改進K-SVD字典和CS的WSN數據壓縮模型。該模型利用字典學習的自適應性，改進K-SVD字典學習算法，根據監測數據本身的特點訓練出適合該類數據的稀疏基，同時為了減輕感知節點負擔，將CS中的稀疏變換轉移在基站進行，為基于CS的WSN數據壓縮提供了一種新思路。

結合理論分析和實驗驗證，本文模型在WSN數據壓縮收集中使用不僅提高了壓縮效率、減少網絡傳輸能耗，而且能以較高精度恢復原始數據。但文中使用的高斯觀測矩陣所需存儲空間較大、計算復雜度較高，在本階段工作中沒有考慮到，今后我們將研究更適合WSN使用的內存小、結構簡單的觀測矩陣。