魏連鎖， 馬敬云， 郭 媛

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

0 引言

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

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

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

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

1 系統(tǒng)模型

1.1 壓縮感知模型

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

(1)

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

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

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

(2)

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

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

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

(3)

式中：xi為節(jié)點收集數(shù)據(jù)。轉換為矩陣形式，即

(4)

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

(5)

s.t.ΦX=y,

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

1.2 數(shù)據(jù)收集模型

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

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

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

(6)

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

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

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

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

(7)

式中：

(8)

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

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

1.3 能耗模型

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

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

(9)

Er(b)=b×Ee,

(10)

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

根據(jù)式(7)改進能耗模型，將路徑損失考慮在數(shù)據(jù)收集的過程中。若在一次數(shù)據(jù)收集的過程中，一共有m個節(jié)點參與，則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)為路徑損失函數(shù)；dk為損失因數(shù)；f為信號頻率；k為路徑損失指數(shù)(在實際應用中，通常取1.5)；a(f)為吸收因數(shù)。由式(12-13)可以看出，數(shù)據(jù)傳輸距離d越大，路徑損失A(d,f)越大，能耗Er(b,d)越多。

節(jié)點接收數(shù)據(jù)的能量消耗表達式為

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

(14)

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

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

(15)

2 算法實例

2.1 步驟

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

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

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

步驟4對參與傳輸?shù)墓?jié)點進行判斷。若節(jié)點到Sink節(jié)點的距離dSink小于投影節(jié)點的距離dUi，即dSink

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

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

算法偽代碼見表1。

表1 算法偽代碼

續(xù)表1

2.2 算法時間復雜度分析

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

3 算法仿真與分析

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

3.1 參數(shù)設置

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

表2 算法仿真參數(shù)設置

3.2 實驗結果

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

(1)重構誤差；

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

(3)網絡生命周期(按照執(zhí)行輪數(shù)，以網絡中出現(xiàn)第一個死亡節(jié)點作為一個生命周期)。

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

(16)

式中：

(17)

(18)

(19)

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

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

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

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

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

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

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

圖8 網絡執(zhí)行輪數(shù)與存活節(jié)點數(shù)的關系Fig.8 The relationship between the number of network execution rounds and the number of viable nodes

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

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

4 結論

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

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