壓縮感知下最短路徑的無線網絡數據收集算法

魏連鎖， 馬敬云， 郭 媛

( 齊齊哈爾大學 計算機與控制工程學院,黑龍江 齊齊哈爾 161006 )

0 引言

無線傳感器網絡(Wireless Sensor Networks, 簡稱WSNs)[1-4]是由大量傳感器節點組成，對數據進行收集、處理、傳輸的一個無線自組織網絡。由于傳感器節點的鋪設成本與功耗日益降低，WSNs在數據收集[5-7]、海洋環境監測等方面的應用價值越來越大[8]。同時，數據收集是WSNs各個應用中數據通信不可或缺的重要環節，參與數據收集的數據通常具有一定的稀疏性，可將壓縮感知(Compressed Sensing, 簡稱CS)[9-10]稀疏隨機投影技術應用于WSNs數據收集過程。由于傳感器節點能量有限且不能及時更換，減少投影過程的節點能耗成為WSNs數據收集和處理的關鍵。目前，對WSNs數據收集過程主要針對數據包的收發能耗，采取有效途徑使數據收集過程中的數據包數目減少，可有效減少網絡能耗。存在問題：(1)壓縮處理數據時，采取數據先收集后壓縮的方式，對資源受限的無線傳感器網絡造成資源浪費；(2)數據傳輸過程中，未考慮節點多跳通信與網絡數據處理，而是將節點收集數據包直接發送至匯聚節點。因此，在設計算法時，對數據處理以減少網絡節點能耗是WSNs數據收集算法需要考慮的因素。

人們提出多種將壓縮感知(CS)應用于WSNs數據收集的算法，如BAJWA W U等[11]將CS技術應用到WSNs數據收集過程，在數據的傳輸過程中未進行數據處理，而是將收集到的數據直接發送給匯聚節點，網絡能耗由于參與數據收集的節點數目冗余而過大。在降低節點數據量方面，較多將稀疏投影應用于WSNs數據收集，如楊浩等[12]提出區域化的壓縮感知數據收集算法，將壓縮感知稀疏隨機投影矩陣引入WSNs數據收集，對每部分單獨壓縮，解決數據收集過程中數據量過大的問題，但稀疏投影矩陣的設計過于復雜；WU C等[13]提出的基于CS減少數據冗余的WSNs數據收集算法，稀疏隨機投影矩陣的建立相對簡單，采用網格編碼的形式降低數據的冗余度，但算法中冗余數據的數目過大，造成過多的網絡能耗。

文獻[11-13]的WSNs數據收集算法主要集中于數據傳輸的方式而忽略網絡能耗，真實的WSNs數據收集算法過程產生大量能耗，人們提出多種解決方案，如CHOU C T等[14]提出的算法綜合考慮節點能耗問題，以較小的能耗獲取收集的節點數據，在數據收集效果較好的情況下減少網絡能耗，但算法需要交換信息的節點數目較多且采用的是窮舉法，復雜度過大，只能用在小型無線傳感器網絡中；VELMANI R等[15]提出的算法可應用在大型無線傳感器網絡中，但恢復原始數據需要收集的節點數目隨網絡規模的變大而增加，網絡能耗隨之變大。

將壓縮感知稀疏隨機投影矩陣與WSNs數據收集過程相結合，設計能耗低、網絡負載均衡的WSNs數據收集算法具有重要意義。WSNs數據收集算法需綜合考慮數據通信節點數量對網絡能耗的影響，同時避免因觀測數過少而導致重構誤差變大的問題。筆者綜合考慮節點能耗、重構誤差等因素，采用壓縮感知稀疏隨機投影技術，提出低能耗、誤差小的無線傳感器網絡數據收集算法，為WSNs數據收集方案的發展提供思路。

1 系統模型

1.1 壓縮感知模型

根據壓縮感知理論，當原始信號由某個稀疏矩陣稀疏化時，可通過一個投影矩陣將稀疏信號投影為低維列向量，求解一個凸優化問題，重構出原始信號。其中，投影矩陣的制定必須符合有限等距約束條件(Restricted Isometry Property,簡稱RIP)[16]，即

(1)

式中：當δK∈(0,1)時，矩陣Φ滿足K階約束等距，即可近似地重建原始信號矩陣X，X=[x1,x2,…,xn]N，為N維原始信號。

在壓縮感知投影矩陣過程中，投影矩陣Φ的稀疏度越高，消耗的能量越少。目前，投影矩陣研究大多是在投影次數和重構算法上對基于壓縮感知的投影機制做優化，采用稀疏投影觀測矩陣[17]減少單個投影值產生的損失。稀疏隨機投影矩陣表達式為

圖1 基于壓縮感知的稀疏隨機投影數據收集過程Fig.1 Sparse random projection data collection process based on compressed sensing

(2)

式中：φij為隨機投影因數；p為φij取相應值時的概率；α為投影矩陣的稀疏程度。

稀疏投影過程：首先，生成稀疏投影矩陣，在每次投影過程中節點i從投影矩陣的第i行中選擇出φij≠0的節點；然后，投影節點根據路徑選擇策略獲取節點數據，將投影節點本身的數據與感知節點傳遞的數據融合后，再通過路徑選擇策略傳遞給Sink節點，匯聚節點從這些節點中任意選取m個節點的數據；最后在Sink節點處通過m個觀測值重構原始信號。基于壓縮感知的稀疏隨機投影數據收集過程見圖1。圖1基于稀疏投影的一次數據收集過程，參與投影過程的節點為1、3、7，則融合數據為

y1=φ11x1+φ13x3+φ17x7,

(3)

式中：xi為節點收集數據。轉換為矩陣形式，即

(4)

原始信號X的重構過程是指通過一定的重構算法，將原始信號稀疏化后的低維觀測向量再重構為X。通過求解最小l0范數實現，但l0范數的求解為非確定性多項式(Nondeterminism Polynomial, 簡稱NP)問題，可將之轉化為最小l1范數[18]求解得出，即

(5)

s.t.ΦX=y,

求解過程為一個線性優化問題，可以運用貪婪迭代算法求解；采用正交匹配追蹤(Orthogonal Matching Pursuit, 簡稱OMP)算法[19]作為信號重構算法。

1.2 數據收集模型

在能量有限的無線傳感器網絡中，節點能耗過大導致網絡陷入癱瘓，因此減少網絡能耗，以最少的能耗實現數據有效收集是關鍵。將CS與路徑選擇策略相結合引入數據收集過程，可解決節點信息冗余對網絡資源帶來的浪費及數據沖突造成信息收集效率低等問題。

由n個傳感器節點組成的無線傳感器網絡模型見圖2。由圖2可知，在數據收集過程中，使用的數據傳輸信道為無線信道，由傳感節點、感知節點、投影節點、匯聚節點構成。在第i輪數據收集過程中，隨機選取m個節點進行數據收集傳輸至匯聚節點，其表達式為

yi=ΦX+λ=φi1x1+φi2x2+…+φimxm+λi,

(6)

式中：yi為m個節點傳輸至匯聚節點的融合數據矩陣；φim為隨機投影矩陣Φ的第i個列向量；xm為節點收集數據；λ為噪聲矢量，在不考慮噪聲的情況下為0。

圖2 n個傳感器節點組成的無線傳感器網絡Fig.2 Wireless sensor network composed of n sensor nodes

圖3 基于壓縮感知的數據收集機制Fig.3 Data acquisition mechanism based on compressed sensing

由式(4)將圖3轉換成矩陣的形式，即

(7)

式中：

(8)

傳統的稀疏投影模型先將數據傳遞到某個投影節點后再傳遞給匯聚節點，但有較多的節點到匯聚節點的距離小于到投影節點的距離。若繼續按照傳統的稀疏投影進行數據傳輸，增加數據傳輸過程的數據量，產生的能耗也大，故直接將此類節點傳輸到匯聚節點，然后與投影節點傳到匯聚節點的數據融合處理。相較于傳統的稀疏投影模型，可使基于最短路徑樹的數據收集模型中參與節點的數量顯著降低，產生的網絡能耗有效減少(見圖4)。

圖4 基于壓縮感知的最短路徑樹數據收集過程Fig.4 Shortest path tree data acquisition process based on compressed sensing

1.3 能耗模型

在無線傳感器網絡數據收集過程中，數據處理所需能耗遠小于數據收發能耗，因此主要考慮數據收發能耗，忽略影響不大的因素(節點數據處理的能耗等),建立能耗模型。應用文獻[20-21]的通信能耗模型，假定兩個節點間的距離為d，發送的數據包長度為b，則任一節點發送數據的能量消耗表達式為

Et(b,d)=Ee×b+b×εad2,

(9)

Er(b)=b×Ee,

(10)

式(9-10)中：Et(b,d)為將長度為b的數據發送距離d需要的能耗；Ee為發送能耗因數；εa為能耗放大因數；Er(b)為數據接收能耗。

根據式(7)改進能耗模型，將路徑損失考慮在數據收集的過程中。若在一次數據收集的過程中，一共有m個節點參與，則Et(b,d)表達式為

Et(b,d)=m[Ee×b×A(d,f)+b×εad2]=

(11)

式中：

A(d,f)=dk·a(f)d,

(12)

(13)

式(12-13)中：A(d,f)為路徑損失函數；dk為損失因數；f為信號頻率；k為路徑損失指數(在實際應用中，通常取1.5)；a(f)為吸收因數。由式(12-13)可以看出，數據傳輸距離d越大，路徑損失A(d,f)越大，能耗Er(b,d)越多。

節點接收數據的能量消耗表達式為

Er(b)=m(b×Ee),

(14)

式中：Er(b)為數據接收能耗。

總體上，除了數據收發能耗以外，傳感器節點數據的處理及尋找最短節點等也產生一定的能量消耗，但收發能耗較小時，這部分將不納入總體能耗計算。總能耗Etl可表示為

(15)

2 算法實例

2.1 步驟

步驟1對數據進行初始化和預處理。依據節點在網絡中的位置對節點執行一維化操作，將數據轉化到一維空間進行處理。

步驟2獲取節點的鄰接矩陣，通過最短路徑算法(Dijkstra算法)分別將網絡中各個節點到節點的最短路徑與最短距離計算出來。

步驟3根據式(2)生成稀疏投影矩陣Φm×n=[φ1,φ2,…,φn]，其中φi(1≤i≤m)為每一個數據包的隨機投影因數，將其加入投影節點集合Ui={Ui(1),Ui(2),…,Ui(lgn)}。從Φm×n中選取非零元素對應的節點加入感知節點集合Γi={Γi(1),Γi(2),…,Γi(n/m)}；隨機從感知節點集合中選取一個作為投影節點，根據步驟2得到各個節點到匯聚節點的最短路徑，生成一個最短路徑樹集合。此外，矩陣的行數由獲取數據包的數量m決定，且每一行代表一條傳輸路徑。

步驟4對參與傳輸的節點進行判斷。若節點到Sink節點的距離dSink小于投影節點的距離dUi，即dSink

步驟5重復對步驟4執行m次，Sink節點得到可以恢復數據的所有m個測量值，再匯聚節點進行信息重構。

步驟6若不同的投影節點在傳輸過程中某一節點處開始重合，則在該結點處先將數據融合再傳輸。

算法偽代碼見表1。

表1 算法偽代碼

續表1

2.2 算法時間復雜度分析

算法的復雜度是衡量一個算法計算量的重要指標。文中算法的核心是數據的傳輸部分，主要包含路徑選擇和數據轉發兩個階段。數據轉發的時間復雜度為O(1)，路徑選擇策略的時間復雜度為O(n2)，故文中算法的時間復雜度為O(n2)。

3 算法仿真與分析

以python語言為工具，在pycharm集成開發環境下進行算法仿真實驗，并對無線傳感網中節點的能耗及存活量與對比算法[22]進行對比分析。該實驗將CS與最短路徑結合應用于數據收集過程，數據收集效率提升，網絡能耗顯著降低，網絡生命周期變長。

3.1 參數設置

算法仿真實驗的相關參數設置見表2。

表2 算法仿真參數設置

3.2 實驗結果

通過三個標準全方位、多角度分析算法的性能，即

(1)重構誤差；

(2)網絡節點最大能量消耗；

(3)網絡生命周期(按照執行輪數，以網絡中出現第一個死亡節點作為一個生命周期)。

實驗中，采用重構誤差τ對重構效果進行評價，表達式為

(16)

式中：

(17)

(18)

(19)

首先，就算法對信號的重構效果進行仿真分析。文中算法與對比算法的重構誤差隨觀測數變化的曲線見圖5。仿真結果表明，對于觀測數的不同，重構誤差有所不同，隨觀測數增加，信號的重構質量呈遞增趨勢。算法的重構誤差隨觀測數增加而逐漸降低，在觀測數相同的情況下，文中算法的重構精度高于對比算法的。

圖5 觀測數與信號重構質量的關系Fig.5 The relationship between observed quantity and signal reconstruction quality

重構質量的對比關系見圖6。由圖6可知，在相同的觀測數下，文中算法的重構誤差小于對比算法的。原因在于投影過程中，文中采用的是稀疏投影矩陣，而對比算法采用的是密集矩陣。與對比算法相比較，信號的稀疏度越高，數據的重構誤差下降越慢，數據的重構質量越高，文中算法對信號的重構有較好的效果。

圖6 重構質量的對比關系Fig.6 Comparison relationship of reconstruct quality

不同算法網絡執行輪數與節點最大能耗的關系見圖7。在數據傳輸過程中，采用稀疏隨機投影矩陣，在數據的傳輸階段只進行信息中轉與信息傳輸操作，并不執行數據融合；在數據傳輸過程中，對比算法采用密集投影矩陣，在數據融合階段僅對節點數據簡單迭加。由圖7可知，隨網絡執行輪數的增加，節點的能耗呈遞增趨勢。在網絡執行輪數相同時，節點的最大能耗由高到低依次為傳統方案、對比算法與文中算法，且文中算法的能耗最小。同時，在文中算法中，當網絡執行到第55輪時，出現首個死亡節點，相較于對比算法(P=0.5，P為節點接入概率)，明顯延長網絡壽命，使網絡生命周期增加6輪；與對比算法(P=0.7)算法相比，網絡生命周期增加20輪，而傳統方案在網絡執行到第25輪時出現首個死亡節點。在能耗方面，文中算法相較于傳統算法既節約網絡能耗，又延長傳感器網絡的生存周期，具有較好的性能。

圖7 不同算法執行輪數與節點最大能耗的關系Fig.7 The relationship between the number of rounds executed by different algorithms and the maximum energy consumption of nodes

網絡執行輪數與存活節點數的關系見圖8。由圖8可知，在網絡執行的初始階段沒有死亡節點出現；隨網絡執行輪數的增加，網絡的節點能耗逐漸增大，網絡開始出現死亡節點，存活節點數逐漸減少。文中方案延長網絡的生命周期，其中，傳統算法在執行到第29輪時，出現首個節點因能量耗盡而死亡，而對比算法的次之。文中算法在執行到第79輪時，最晚出現死亡節點，與對比算法相對比，網絡的生命周期延長約2倍。傳統算法出現死亡節點的時間最早，節點的死亡速率最高，但隨網絡執行輪數越來越多，存活節點數目減少，死亡速率又趨于平緩。文中算法在初期節點死亡速率最低，隨執行輪數的增加，節點死亡速率增大后又趨于平緩。因此，文中算法的死亡節點出現的時間最晚，節約網絡能耗效果良好。

圖8 網絡執行輪數與存活節點數的關系Fig.8 The relationship between the number of network execution rounds and the number of viable nodes

3種算法的節點廣播半徑與網絡能耗比的關系見圖9。由圖9可知，隨節點廣播半徑的增加，網絡能耗比逐漸上升；在廣播半徑相同的情況下，傳統算法的能耗比例最高，對比算法的次之，文中算法的能耗比最低，效果最好。因此，文中算法可有效延長網絡壽命，解決數據收集能耗問題。

圖9 節點廣播半徑與網絡能耗比的關系Fig.9 The relationship between node broadcast radius and network energy consumption ratio

4 結論

(1)基于稀疏隨機投影壓縮感知下最短路徑的無線網絡數據收集算法與對比算法相比，在保證原始數據重構精度的前提下，能夠減少數據收集過程中的數據量，降低能耗；提出根據自身收集信號強度調節選擇數據發送概率機制，延長網絡壽命。

(2)文中算法為稀疏投影壓縮感知下的無線傳感器網絡的數據收集提供一種新的解決方案。