基于遺傳壓縮感知的無線傳感器網絡數據壓縮方法

張 娜

基于遺傳壓縮感知的無線傳感器網絡數據壓縮方法

張 娜

(河南城建學院計算機科學與工程學院 河南 平頂山 467036)

考慮到無線傳感器網絡WSNs能量、通信帶寬、計算能力及成本有限，不適合大規模數據傳輸，同時存在數據冗余，需要進行數據壓縮處理，提出一種新的基于遺傳算法的壓縮感知CS(Compressive Sensing)重構方法，應用于無線傳感器網絡數據壓縮中。詳細闡述分布式WSNs數據壓縮特點，壓縮感知基本理論，基于遺傳算法的CS重構新方法以及在WSNs數據壓縮中的應用。通過實驗仿真證明，從壓縮比、節點平均能耗、網絡生存時間和網絡時延四個方面，與DCCM算法及CCS算法的WSNs數據壓縮算法進行比較，提出的算法具有較高的壓縮比，提高了采集數據的重構精度，降低了數據冗余度和網絡通信量，提高了網絡效率。

無線傳感器網絡 壓縮感知 遺傳算法 壓縮比 生命周期

0 引 言

隨著WSNs不斷的發展，信號采集需要的帶寬和數據量現已成幾何方式增長。因此必須建立新型采樣機制以減少成本、通信量、延時、能源消耗和信息數據量[1]。WSNs的能量消耗常常直接決定了整個系統的穩定性與可靠性，而數據壓縮對提升無線傳感器網絡的通信吞吐量非常顯著[2]。傳感器網絡的能量消耗最主要集中于三個部分，分別為信號采樣、信號處理與信號傳輸，其中能量消耗絕大部分在信號傳輸環節[3]。壓縮傳輸信號可以有效地減少能量消耗，在對WSNs的數據壓縮進行設計時應該考慮到兩點：(1) 節點處理能力低；(2) 受限的內存資源。因此所設計的壓縮算法的能量消耗必須盡可能少[4]。數據壓縮的關鍵在于壓縮算法消耗的能量應小于數據傳輸的能量。

雖然壓縮感知CS是近幾年才興起的領域，但是它已經表現出了很強大的生命力與發展潛力。很多學者都在這個領域進行嘗試，希望能有所貢獻和突破。壓縮感知把稀疏信號壓縮和采樣兩個步驟合并進行，為了滿足一個特性：在監控區域內傳感器節點能耗與計算能力都十分有限的情況下，而遠端匯聚終端卻擁有持續能量供給與強大的計算能力。王英杰等[5]提出無線傳感器網絡中分布式數據壓縮方法，應用到無線傳感器網絡數據壓縮算法中，取得不錯的效果；任學軍等[6]提出了一種適合無線傳感器網絡的混合編碼數據壓縮算法；王玲等[7]提出基于時間相關性的無線傳感器網絡數據壓縮與優化算法；張建明等[8]提出傳感網絡中誤差有界的分段逼近數據壓縮算法，取得不錯效果。傳統數據壓縮方法雖然編碼復雜但是解碼簡單。這意味著用有限資源的傳感器節點進行復雜的編碼算法，而在資源相對豐富的簇頭節點進行簡單的解碼算法?；谝陨戏治?，本文提出一種新的基于遺傳算法的壓縮感知重構方法，應用于無線傳感器網絡數據壓縮中。不僅能使壓縮編碼部分變得更簡單，使傳輸的數據更少，還能使解碼算法相對更簡易，提高壓縮比和采集數據的重構精度，降低了數據冗余度和網絡通信量，提高了網絡效率。

1 分布式WSNs數據壓縮

在監測區域內的成千上百個微型傳感器節點組成了無線傳感器網絡，能夠協作地對網絡覆蓋區域內對象的信息進行感知、采集和處理，最后經處理的信息發送給基站終端。通常情況下，WSNs是全分布式網絡，而就其中的每個傳感節點而言，一方面它們對信息具有獨立的感知、處理和通信能力，但是另一方面它們的通信范圍、能量、甚至計算能力等都是有限的。因此無法解決規模較大的復雜性問題。為了將傳感節點的處理能力充分地利用起來，節點之間就必須相互合作，突破單個節點的限制，共同完成任務，解決實際問題，從而提高網絡性能。

2 壓縮感知(CS)理論介紹

傳統的數據采樣方法：“采樣—壓縮—傳輸—解壓縮”有可能會失效。然而壓縮感知采樣由于具有簡單采樣、復雜解碼的特性，因此能有效地解決這一問題。壓縮感知與先信號采樣再消除信號冗余部分的傳統方法不同，它直接將壓縮后的信號進行采樣，并且同時進行壓縮和采樣，省去了大量沒用的信號采樣部分[9]。

壓縮感知包括三個方面：信號的稀疏表示、編碼測量與重構方法。信號能夠進行壓縮感知的先決條件是信號可以進行稀疏表示或者可壓縮，即在某個變換基下，信號可以使用一種較為簡潔的方式進行表達。它的非零系數個數必須遠遠小于自然信號中非零值的個數[10]。

對于有限長的一維信號x∈Rn(n∈N)， 假設其在某正交基Ψ={ψi}上是P稀疏的(1≤P

(1)

式中，θi為稀疏矩陣投影系數，式(1)可簡寫為：

x=Ψθ

(2)

式中，θ為n×1維的稀疏矩陣列向量，Ψ稱作稀疏變換矩陣。

由壓縮感知理論可知，當信號x稀疏或者經過稀疏變換Ψ后稀疏時， 可以用一個不相關的m×n維觀測矩陣Ψ(m≤ n，m∈N)對x進行線性變換， 得到觀測值y， 即：

ym×1=Φm×nxn×1=Φm×nΨn×nθn×1

(3)

可以看出觀測值y的元素個數比x的元素個數要少，這樣便實現了對感知信號的壓縮采樣。另外通過求解l1范數下的最優化問題完成將觀測集合y進行重構得到信號x，即：

θ=argmin‖θ‖1s.t. y=ΦΨθ

(4)

3 基于遺傳算法CS新重構方法

由壓縮感知理論可知，基于遺傳算法的CS新型重構方法與基于匹配的傳統重構算法相異，區別比較大。它主要從目標函數的優化出發，把稀疏重構結果等同于生物中的染色體。假設在一定規模的種群中，經過復制、選擇、交叉互換及變異等遺傳過程之后，經迭代無限逼近最優最接近感知節點采樣值的重構結果，之后從稀疏重構結果中獲得各非零元素的位置信息；再通過最小二乘法得到各非零元素的幅度信息，最終完成重構處理，完成感知數據壓縮信息傳輸過程。因此，本文基于遺傳算法的壓縮感知新型重構方法能夠在稀疏度未知的情況下重構出最終的稀疏結果。

3.1 稀疏重構結果中各非零元素位置信息

1) 種群與編碼方案

2) 復制

在父代染色體產生子代的過程中，要求給定遺傳代溝GGAP具體數值，GGAP∈(0，1)。假設每代種群中的個體數B乘以1-GGAP個最優個體直接被復制到下一代。而其他子代個體，由選擇運算產生。

3) 選擇

選擇目標函數值定義為：

(5)

最終的迭代優化目標是使目標函數取得最小值，即求得min{f}。

本文采用線性排序估算適應度Ji，首先對目標函數值進行降序排列。將最小適應度染色體個體放置在排序的目標函數值列表的首個位置，最適應個體放置在位置Bi上，Bi為種群個體數量。每個染色體個體根據其在排序種群中的位置W0通過計算可推出適應度值Ji， 即：

(6)

4) 交叉

遺傳算法的交叉選用單點交叉，在個體編碼串中用交叉概率隨機選取一個新的交叉點，對兩個配對個體進行部分染色體互換。

5) 變異

遺傳算法的變異使用基本位變異，將個體編碼串中按遺傳過程中變異概率隨機選定的某一基因座上的數值進行基本位變異運算，執行過程如下：

(1) 按變異概率在每一個個體上指定某一基因座為變異點；

(2) 對每一個染色變異點的基因值進行取反運算，從而得到新一代的遺傳染色個體。

經過一系列的操作過程，再通過MAXGEN迭代(MAXGEN為最大遺傳代數)就可以收斂得到最優染色體，即為最優解。一般最優染色體主要由“0”或“1”編碼組成，其中“1”為稀疏結果中的非零元素，另外稀疏結果中非零元素的位置信息與它的位置信息相對應。

3.2 稀疏結果中各非零元素幅度信息的確定

知道稀疏結果中各非零元素位置信息后，再在各個位置上利用最小二乘法做投影來確定其幅度信息。假設稀疏結果中有一個非零元素在第j位置上，那么該非零元素的幅度為：

(7)

其中,Tj表示T的第j列，而：

T=ΦΨ

(8)

其中，T稱為恢復矩陣。通過非零元素的幅度計算， 就可得到稀疏結果中各非零元素幅度信息。

綜合上述內容，基于遺傳算法的CS新型重構方法算法流程如圖1所示。

圖1 基于遺傳算法的CS新型重構方法流程

4 CS新型重構方法在WSNs數據壓縮中的應用

遺傳壓縮感知新型重構算法在無線傳感器網絡數據壓縮中的應用如圖2所示。

圖2 遺傳壓縮算法在數據壓縮中應用

遺傳壓縮感知算法與WSNs數據傳輸的具體應用相結合，能夠對數據進行壓縮后傳輸，具體過程歸納如下：首先，采集的數據通過傳輸到達簇頭節點，簇頭節點對數據進行壓縮存儲并處理，如圖2所示。然后，簇頭節點對各個傳感器節點獲得的數據進行分析，接著把壓縮數據結果傳送到匯聚終端，最終各個節點的信號在終端聯合恢復重構出來。基于遺傳算法進行CS的步驟如下：

(1) 遠端匯聚終端發布命令。由匯聚終端發布的監測命令通過多跳路由傳送到簇頭節點，簇頭節點以廣播的方式將命令轉發給每個簇內的傳感器節點。

(2) 簇頭節點匯聚監測數據。各個傳感器節點根據任務命令采集感知的信息，然后將采集得到的數據傳輸到簇頭節點，簇頭節點存儲信息數據，經過規定時間后開始處理。

5 實驗仿真與分析

本文采用Matlab仿真平臺對本文提出的遺傳壓縮感知數據壓縮算法進行驗證，其中電腦配置為處理器Pentium 2 GHz，內存為2 GB的PC環境下運行。在無線傳感器網絡數據壓縮算法中，用到比較多的有簡單的差分編碼壓縮算法DCCM(differential code compression method)和協作壓縮感知CCS(Cooperative Compressed Sensing)算法[11]等。本文將與DCCM算法及CCS算法[12]進行比較分析。遺傳算法參數設置：遺傳算法種群大小為40，最大遺傳代數MAXGEN=300，遺傳代溝GGAP=0.95，交叉概率px=0.7，變異概率pm=0.03。實驗中無線傳感器網絡所用的參數如表1所示。

表1 仿真實驗參數

無線傳感器網絡數據壓縮算法性能評價指標本文主要從傳感器數據序列簡單壓縮有效性及與其他算法的壓縮比、節點平均能耗、生存時間和網絡時延等方面進行對比。

5.1 傳感器數據序列壓縮感知的有效性

為了對本文提出的改進壓縮感知算法有效性有一個相對直觀的理解，將傳感器采集到的一組數據進行實驗。其中數據長度N=100，原始數據、壓縮感知重構后的數據和本文提出的算法重構后的數據對比圖如圖3所示。 從圖3中可以看出，CCS算法重構率在83.7%，本文算法的重構率94.8%，均方根誤差較小。本文提出的算法完成精確的重建，且重構信號質量穩定，保證高精度的還原性。

圖3 傳感器數據序列壓縮重構效果圖

5.2 壓縮比

壓縮比CR(compression ratio)的計算公式為：

CR=SCP/SOR

(9)

其中，SOR為初始數據量，SCP為壓縮之后的數據量。另外CR數值越小，那么壓縮之后的數據量占原始數據量比重越小，說明壓縮性能越優。三種算法壓縮比對比如圖4所示。

圖4 三種算法壓縮比對比

從圖4可以看出，隨著節點數據采集量的增加，三種算法的壓縮比都在逐漸下降，下降的幅度不是很大。相比較而言，CCS算法的壓縮比低于DCCM算法的壓縮比，壓縮性能較優，而本文提出的GA-CS壓縮算法的壓縮比比CCS算法的壓縮比還低，壓縮性能最好。因為該算法很好地挖掘了無線傳感器網絡以數據為中心、數據之間的相關性的特點。編碼過程中最大程度的去除了節點之間的冗余信息，得到了不錯的壓縮效果，并且隨著節點采集數據量的增加，它的壓縮比越來越小，逐步趨于平穩。另外給出遺傳算法的收斂性和收斂時間如圖5所示。遺傳迭代算法在180代左右數據平緩，達到收斂，同時仿真時間消耗4.83 s。

圖5 遺傳算法迭代收斂曲線

5.3 節點平均能耗

節點能耗是衡量無線傳感器網絡性能參數的一個重要參數，同樣適合數據壓縮算法性能評價。數據傳輸過程中會增加數據壓縮時的計算能耗，但在感知節點整個通信過程中的能量消耗而言，數據壓縮計算能耗可以忽略不計。仿真中只考慮感知節點的無線通信能耗，設定仿真節點的初始能量、收發功率、數據包發送速率，同時根據數據分組長度計算每次發送數據后節點剩余的能量。計算網絡發送與接收時的剩余能量差值就可知道網絡運行中的能耗。三種算法的平均能耗如圖6所示。

圖6 三種算法平均能耗對比

從圖6可以看出，節點數據采集量相同時，CCS算法的平均能量消耗比DCCM算法要低，而本文提出的算法比DCCM算法的平均能耗還低。隨著感知節點發送數據包數量的增加，三種算法的平均能耗都隨之增加，但本文提出的算法能耗增加幅度最小。這主要因為本文提出遺傳壓縮感知數據壓縮算法能更好的挖掘感知節點之間的數據相關性，最大化的降低了冗余節點信息，提高了算法的壓縮精度。

5.4 網絡生存時間

同樣地網絡生存時間是無線傳感器網絡重要的性能指標，直接反應網絡壽命的長短。本文分別對這三種算法的網絡生存時間進行了仿真，仿真結果如表2所示。

表2 節點死亡時間輪數對比

從整體來看，本文提出的GA-CS算法節點死亡時間輪數都比DCCM算法和CCS算法要長，當網絡感知節點10%能量耗盡時，GA-CS算法節點死亡速度為DCCM算法的77%和CCS算法的88%；在網絡感知節點50%能量耗盡時，GA-CS算法節點死亡速度為DCCM算法的88.3%和CCS算法的93.7%；在網絡感知節點75%能量耗盡時，GA-CS算法節點死亡速度為DCCM算法的77.9%和CCS算法的84.4%；在100%的節點能耗耗盡時，GA-CS算法節點的網絡輪詢時間分別多出3004和1478輪。可以看出，本文提出基于GA-CS算法無線傳感器網絡中的網絡壽命明顯比另兩種算法的壽命要長。這主要是因為在數據壓縮之后，減小了網絡內部的數據冗余，減少了數據傳輸過程中的能耗，延長了網絡壽命。因此，本文提出的算法適用于能量有限、計算有限及成本有限的無線傳感器網絡。

5.5 網絡時延

網絡時延TY包括兩部分時間組成，從感知節點發送數據到接收節點收到數據包的傳輸延時TS和接收到數據包的節點進行數據壓縮算法產生的計算耗時TC，計算公式為：

TY=TS+TC

(10)

三種算法的網絡時延如圖7所示。

圖7 三種算法網絡時延對比

從圖7可以看出，三種算法的網絡時延都隨著節點數據采集的增加而延長。當節點的采集量較小時，DCCM算法的網絡時延比CCS算法要短，短0.05 s，而比GA-CS算法的網絡時延短了0.1 s，這主要是由于對數據進行壓縮而消耗的計算延時。但隨著節點數據采集量的增加，發送的數據包較大時，DCCM算法的網絡時延明顯比CCS算法要長，比GA-CS算法的網絡時延更長。這里主要的時間消耗不是數據壓縮計算延時，主要是數據采集量增大后的時間傳輸時間延時?？梢钥闯霰疚奶岢龅幕贕A-CS算法的數據壓縮算法，有效地降低了網絡中所需要傳輸的數據量，從而達到減少網絡延時的目的。

6 結 語

無線傳感器網絡由于能量、通信帶寬、計算能力及成本有限，不適合大規模數據傳輸，同時存在數據冗余，需要進行數據壓縮處理。本文提出一種新的基于遺傳算法的壓縮感知重構方法，應用于無線傳感器網絡數據壓縮過程中。對GA-CS算法進行的性能分析， 從壓縮比、節點平均能耗、網絡生存時間和網絡時延四個方面，與DCCM算法及CCS算法的WSNs數據壓縮算法進行比較。實驗驗證表明，本文提出的算法具有較高的壓縮比，提高了采集數據的重構精度，降低了數據冗余度和網絡通信量，提高了網絡效率。

[1] Erratt N,Liang Y.Compressed data-stream protocol:an energy-efficient compressed data-stream protocol for wireless sensor networks[J].Let Communications,2011,5(18):2673-2683.

[2] Liu Xiang,Jun Luo,Rosenberg C.Compressed Data Aggregation:Energy-Efficient and High-Fidelity Data Collection[J].Networking,IEEE/ACM Transactions on,2013,21(6):1722-1735.

[3] Shancang Li,Li Da Xu,Xinheng Wang.Compressed Sensing Signal and Data Acquisition in Wireless Sensor Networks and Internet of Things[J].Industrial Informatics,IEEE Transactions on,2013,9(4):2177-2186.

[4] 曾凡文,王永利,劉冬梅.可調重構誤差的傳感數據時間相關壓縮算法[J].計算機應用與軟件,2011,28(11):279-282.

[5] 王英杰,鞠時光,陰曉加.無線傳感器網絡中分布式數據壓縮方法[J].計算機工程,2010,36(18):88-90.

[6] 任學軍,房鼎益.一種適合無線傳感器網絡的混合編碼數據壓縮算法[J].小型微型計算機系統,2011,32(6):1055-1058.

[7] 王玲,石為人,石欣.基于時間相關性的無線傳感器網絡數據壓縮與優化算法[J].計算機應用,2013,33(12):3453-3456.

[8] 張建明,林亞平,傅明.傳感網絡中誤差有界的分段逼近數據壓縮算法[J].軟件學報,2011,22(9):2149-2165.

[9] 尹亞光,丁貴廣.無線傳感器網絡中的數據壓縮技術研究[J].計算機應用與軟件,2010,27(7):1-4.

[10] 范祥輝,李士寧,杜鵬雷.WSN中一種自適應無損數據壓縮機制[J].計算機測量與控制,2010,18(2):463-465.

[11] 蔣鵬,吳建峰,吳斌.基于自適應最優消零的無線傳感器網絡數據壓縮算法研究[J].通信學報,2013,34(2):1-7.

[12] 吳大鵬,孫青文,唐季超.能量有效的無線傳感器網絡協作壓縮感知機制[J].電子與信息學報,2012,34(11):2687-2693.

WIRELESS SENSOR NETWORK DATA COMPRESSION METHOD BASED ON GENETIC COMPRESSED SENSING

Zhang Na

(InstituteofComputerScienceandEngineering,HenanUniversityandUrbanConstruction,Pingdingshan467036,Henan,China)

In view of that the wireless sensor networks (WSNs) are limited in energy, communication bandwidth, computing capability and cost, they are not suitable for large-scale data transmission, and that there is the presence of data redundancy meanwhile and has the need of data compression, we put forward a new genetic algorithm-based compressed sensing (CS) reconstruction method, and applied it to wireless sensor network data compression. In this paper we expatiate on the features of distributed WSNs data compression, the basic theory of compressed sensing, as well as the genetic algorithm-based new CS reconstruction method and its application in WSNs data compression. It was proved through experimental simulation that compared with WSNs data compression algorithms using DCCM algorithm and CCS algorithm in four aspects of compression ratio, average nodes energy consumption, network lifecycle and network delay, the proposed algorithm had higher compression ratio, improved the reconstruction accuracy of the collected data, reduced the data redundancy and network traffic, and improved the network efficiency.

Wireless sensor networks Compressive sensing Genetic algorithm Compression ratio Lifecycle

2014-10-08。國家自然科學基金項目(61202248)；河南省科技發展計劃科技攻關重點項目(122102210412)。張娜，博士，主研領域：模式識別與智能系統。

TP393

A

10.3969/j.issn.1000-386x.2016.04.031