基于遺傳壓縮感知的無線傳感器網絡數(shù)據(jù)壓縮方法

張 娜

基于遺傳壓縮感知的無線傳感器網絡數(shù)據(jù)壓縮方法

張 娜

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

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

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

0 引 言

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

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

1 分布式WSNs數(shù)據(jù)壓縮

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

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

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

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

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

(1)

式中，θi為稀疏矩陣投影系數(shù)，式(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的元素個數(shù)比x的元素個數(shù)要少，這樣便實現(xiàn)了對感知信號的壓縮采樣。另外通過求解l1范數(shù)下的最優(yōu)化問題完成將觀測集合y進行重構得到信號x，即：

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

(4)

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

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

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

1) 種群與編碼方案

2) 復制

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

3) 選擇

選擇目標函數(shù)值定義為：

(5)

最終的迭代優(yōu)化目標是使目標函數(shù)取得最小值，即求得min{f}。

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

(6)

4) 交叉

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

5) 變異

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

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

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

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

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

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

(7)

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

T=ΦΨ

(8)

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

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

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

4 CS新型重構方法在WSNs數(shù)據(jù)壓縮中的應用

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

圖2 遺傳壓縮算法在數(shù)據(jù)壓縮中應用

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

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

(2) 簇頭節(jié)點匯聚監(jiān)測數(shù)據(jù)。各個傳感器節(jié)點根據(jù)任務命令采集感知的信息，然后將采集得到的數(shù)據(jù)傳輸?shù)酱仡^節(jié)點，簇頭節(jié)點存儲信息數(shù)據(jù)，經過規(guī)定時間后開始處理。

5 實驗仿真與分析

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

表1 仿真實驗參數(shù)

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

5.1 傳感器數(shù)據(jù)序列壓縮感知的有效性

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

圖3 傳感器數(shù)據(jù)序列壓縮重構效果圖

5.2 壓縮比

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

CR=SCP/SOR

(9)

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

圖4 三種算法壓縮比對比

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

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

5.3 節(jié)點平均能耗

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

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

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

5.4 網絡生存時間

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

表2 節(jié)點死亡時間輪數(shù)對比

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

5.5 網絡時延

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

TY=TS+TC

(10)

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

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

從圖7可以看出，三種算法的網絡時延都隨著節(jié)點數(shù)據(jù)采集的增加而延長。當節(jié)點的采集量較小時，DCCM算法的網絡時延比CCS算法要短，短0.05 s，而比GA-CS算法的網絡時延短了0.1 s，這主要是由于對數(shù)據(jù)進行壓縮而消耗的計算延時。但隨著節(jié)點數(shù)據(jù)采集量的增加，發(fā)送的數(shù)據(jù)包較大時，DCCM算法的網絡時延明顯比CCS算法要長，比GA-CS算法的網絡時延更長。這里主要的時間消耗不是數(shù)據(jù)壓縮計算延時，主要是數(shù)據(jù)采集量增大后的時間傳輸時間延時。可以看出本文提出的基于GA-CS算法的數(shù)據(jù)壓縮算法，有效地降低了網絡中所需要傳輸?shù)臄?shù)據(jù)量，從而達到減少網絡延時的目的。

6 結 語

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

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

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

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

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

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

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

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

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

[12] 吳大鵬,孫青文,唐季超.能量有效的無線傳感器網絡協(xié)作壓縮感知機制[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)；河南省科技發(fā)展計劃科技攻關重點項目(122102210412)。張娜，博士，主研領域：模式識別與智能系統(tǒng)。

TP393

A

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