何旭1，楊韻怡1，林怡陽1，鄒志強(qiáng)2,3，沈澍2,3

　　（1.南京郵電大學(xué) 貝爾英才學(xué)院，江蘇 南京 210046；2.南京郵電大學(xué) 計算機(jī)學(xué)院，江蘇 南京 210003；3.江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003）

       摘要：提出了一種基于壓縮感知和雙簇頭交替的無線傳感器網(wǎng)絡(luò)分層路由算法CS-DC HA(Compressed Sensing-Double Cluster Head Alternation)。該算法對DCHS(Deterministic Clusterhead Selection)算法進(jìn)行改進(jìn)，利用壓縮感知理論優(yōu)化稀疏采樣過程；采用雙簇頭交替方法進(jìn)行路由選擇，進(jìn)而實(shí)現(xiàn)減低能耗；同時以貝葉斯算法進(jìn)行稀疏信號重構(gòu)。通過實(shí)驗(yàn)可以看出，相比于傳統(tǒng)的無線傳感器監(jiān)測網(wǎng)絡(luò)，CS-DCHA算法保證了在一定的信號重構(gòu)精度條件下，能降低無線傳感器網(wǎng)絡(luò)的能耗并延長其生存時間。

　　關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);分簇路由算法;壓縮感知;貝葉斯恢復(fù)算法

0引言

　　無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks,WSNs）是集信息采集、傳輸、處理于一體的綜合系統(tǒng)［1］。近年來，WSNs應(yīng)用于許多領(lǐng)域，尤其是環(huán)境監(jiān)測方面，如水域和森林地理信息采集、污染監(jiān)測等方向［23］。

　　監(jiān)測任務(wù)通常持續(xù)時間長且使用區(qū)域特殊，節(jié)點(diǎn)供能困難，故WSNs生命周期一般較短。而在工作過程中，數(shù)據(jù)通信耗能約占總耗能的90%［4］。因此，可從減少數(shù)據(jù)通信和能耗均勻分布兩方面考慮WSNs路由算法的設(shè)計。

　　WSNs規(guī)模較大時，分簇路由能有效降低通信耗能［5］。DCHS作為一種分簇路由協(xié)議，兼顧了簇頭選舉和數(shù)據(jù)傳輸兩個階段的能量均衡問題［5］。但在選簇頭和建簇過程中，簇頭耗能較高，此時簇頭已未必適合繼續(xù)擔(dān)任簇頭，所以簇頭選舉時重新選出主副簇頭，在數(shù)據(jù)傳輸階段實(shí)現(xiàn)雙簇頭交替［6］（Double Cluster Head Alternation,DCHA）。

　　采樣過程中，有些測量值（如水溫和氣壓）在長時間大范圍內(nèi)才會變化，即能夠進(jìn)行稀疏表示。經(jīng)稀疏表示后，節(jié)點(diǎn)所需的采樣頻率顯著降低，從而降低能耗。近年來由美國科學(xué)院院士DONOHO D等人提出的壓縮感知(Compressed sensing,CS)理論［7］很好地符合這一點(diǎn)。CS要求觀測的數(shù)據(jù)只是原始信號的一個很小子集，可減少采樣次數(shù)，降低系統(tǒng)能耗［8］。

　　針對監(jiān)測對象存在時空稀疏性的WSNs，本文首先分析了CS理論用于WSNs采樣壓縮的過程；接著從減少數(shù)據(jù)通信量角度出發(fā)，給出了能量受限的WSNs應(yīng)用CS理論采樣的系統(tǒng)模型，提出相應(yīng)的觀測矩陣；最后，從能量均衡方面考慮，使用DCHS確保簇頭能量充足，在此基礎(chǔ)上采用DCHA方法，進(jìn)一步降低簇頭耗能，延長整個WSNs的生命周期。

1壓縮感知理論

　　1.1基本原理

　　在標(biāo)準(zhǔn)CS框架中［7］，觀測到的自然界的物理信號記為x∈RN，且在某個變換基上有稀疏表示即：

　　x=Ψα，αl0=K，KN(1)

　　其中，α為稀疏變換系數(shù)；K為變換系數(shù)中非零元個數(shù)。在實(shí)驗(yàn)中，采用離散余弦變換(Discrete Cosine Transform, DCT)來稀疏原始信號。

　　下面對信號進(jìn)行某種隨機(jī)采樣，使得

　　y=Φx=ΦΨα，y∈RN，Φ∈RM×N(2)

　　其中，y為隨機(jī)采樣的線性測量值；Φ為觀測矩陣；A=ΦΨ為感知矩陣。

　　根據(jù)y恢復(fù)出稀疏系數(shù)的估計值α。通用的恢復(fù)方法表達(dá)式為：

　　α=argminααl0，s.t.y=ΦΨα(3)

　　一般而言，l0問題（0-范數(shù)）屬于NP-hard問題，目前很難由多項(xiàng)式法求解。有研究表明，可以把求解l0轉(zhuǎn)化為求解l1,從而轉(zhuǎn)化為線性規(guī)劃問題［8］，再用多項(xiàng)式法求解，即

　　α=argminααl1，s.t.y=ΦΨα(4)

　　通過求解l1，得到與原問題相同的解。求出α后，再對α進(jìn)行逆變換，即x=Ψα，從而得到最終的信號估計值。

　　CS的核心思想：以原始信號的可稀疏性，通過變換空間來描述信號。只需采集少數(shù)特殊的線性觀測數(shù)據(jù)，通過求解一個優(yōu)化問題從少量觀測數(shù)據(jù)中恢復(fù)信號。傳統(tǒng)編解碼理論的框圖如圖1所示，CS理論的編解碼框圖如圖2［9］所示?！?/p>

　　圖1、圖2反映了兩者的區(qū)別。傳統(tǒng)方法按照Nyquist采樣定理完成采樣后，再進(jìn)行壓縮編碼，故CS采樣得到的壓縮數(shù)據(jù)的數(shù)據(jù)量遠(yuǎn)小于傳統(tǒng)采樣，大大降低了采樣和通信的耗能。

　　1.2構(gòu)建觀測矩陣

　　CS主要由信號的稀疏表示、觀測矩陣和重構(gòu)算法構(gòu)成。其中，建立觀測矩陣是關(guān)鍵過程［10］。

　　DONOHO D提出了相關(guān)性判別理論: 觀測矩陣Φ與稀疏基Ψ的不相干程度越高，稀疏信號的精確重構(gòu)所需的觀測數(shù)越少。DCHS結(jié)合CS后，簇的數(shù)量取決于觀測向量的行數(shù)［11］，應(yīng)為μ2klogN，即：簇頭百分比為p=klogNN。其中，k為信號的稀疏度，N為局域內(nèi)節(jié)點(diǎn)的個數(shù),μ2為稀疏矩陣和觀測矩陣的相干性。

　　CS常采用隨機(jī)觀測矩陣，這類矩陣元素往往獨(dú)立同分布。測量矩陣和稀疏信號大多不相干，需重建的測量數(shù)小，但所需存儲空間大且計算復(fù)雜度高。一般的分簇路由算法存在簇頭通信和處理負(fù)擔(dān)過重的缺點(diǎn)。因此，提出CS-DCHA，采用DCHS分簇,然后構(gòu)造CS觀測矩陣，系統(tǒng)模型如圖3所示。其中，所有節(jié)點(diǎn)依據(jù)地理信息和通信距離劃分簇。觀測矩陣由各簇的觀測向量組成，每簇的觀測向量僅在本簇節(jié)點(diǎn)位置處非零。

　　觀測向量僅在簇頭上存儲，每簇的節(jié)點(diǎn)數(shù)也相對較少，對存儲空間和計算復(fù)雜度的要求有所降低。

　　建立觀測矩陣的具體過程如下［12］：在觀測向量中本簇節(jié)點(diǎn)位置處置1，表示該節(jié)點(diǎn)屬于當(dāng)前簇。簇頭封裝觀測向量與數(shù)據(jù)，一同發(fā)送給sink節(jié)點(diǎn)。sink節(jié)點(diǎn)從所有簇頭中提取數(shù)據(jù)和觀測向量，并將所有觀測向量組合在一起形成觀測矩陣Φ∈RM×N，其中Mμ2klogN［13］。這就是一“輪”中觀測矩陣的建立過程。重復(fù)執(zhí)行上述步驟，并形成新的觀測矩陣。

2CS-DCHA算法

　　CS-DCHA算法主要包含兩個階段：成簇階段和穩(wěn)定階段。成簇階段又可分為選舉簇頭與形成簇；穩(wěn)定階段是WSNs正常工作階段，此階段采用雙簇頭交替。

　　2.1CS-DCHA算法的成簇階段

　　在選簇頭時，每個節(jié)點(diǎn)產(chǎn)生一個0~1隨機(jī)數(shù)，若該隨機(jī)數(shù)小于閾值，則該節(jié)點(diǎn)選為簇頭。

　　閾值的計算公式為：

　　其中，p為簇頭占節(jié)點(diǎn)總數(shù)的比例；r為目前的輪次；rmod(1/p)為本輪循環(huán)中當(dāng)選過簇頭的節(jié)點(diǎn)個數(shù)；Encurrent為節(jié)點(diǎn)當(dāng)前能量；En_max為節(jié)點(diǎn)初始能量；G為在近1/p輪中未擔(dān)任簇頭的節(jié)點(diǎn)集合。在選舉簇頭時，將能耗比例較低的節(jié)點(diǎn)優(yōu)先選為簇頭。

　　簇形成時，要考慮兩點(diǎn)要素：簇頭間的負(fù)載平衡和簇能量消耗總和最小。節(jié)點(diǎn)當(dāng)選簇頭后，全域廣播該消息，其他節(jié)點(diǎn)接收到由多個簇頭廣播的消息，分別計算到這些臨時簇頭的距離，加入通信代價最小的簇頭所在網(wǎng)絡(luò)，向當(dāng)前簇頭發(fā)送剩余能量與地理位置等信息，從而形成簇。

　　選舉簇頭與形成簇的效果如圖4所示。sink節(jié)點(diǎn)、簇頭、簇內(nèi)節(jié)點(diǎn)構(gòu)成一個兩跳網(wǎng)絡(luò)。sink節(jié)點(diǎn)負(fù)責(zé)全局的數(shù)據(jù)融合；簇頭負(fù)責(zé)區(qū)域內(nèi)的數(shù)據(jù)轉(zhuǎn)發(fā)和計算處理；簇內(nèi)節(jié)點(diǎn)負(fù)責(zé)信息感知。

　　WSNs能耗模型采用自由空間模型與多徑衰減模型［6］。當(dāng)通信距離大于閾值d0，發(fā)送數(shù)據(jù)所需能量正比于距離的4次方，反之正比于距離的平方。發(fā)送方發(fā)送k bit數(shù)據(jù)消耗的能量由發(fā)射電路損耗與功率放大損耗兩個部分構(gòu)成，可表示為

　　ET（i）=kEelec+kεfsd2,d<d0

　　kEelec+kεmpd4,d≥d0（6）

　　接收k bit數(shù)據(jù)所需的能量為：

　　ER(i)=kEelec(7)

　　其中，Eelec是收發(fā)單位數(shù)據(jù)消耗的能量，而閾值為：

　　其中，εfs和εmp是兩種情況下功率放大器消耗的能量比例系數(shù)。

　　2.2CS-DCHA算法的穩(wěn)定階段

　　在穩(wěn)定階段，首先解決雙簇頭選舉問題。在簇形成后，重選主、副簇頭。

　　在成簇過程中，原簇頭已獲得所有成員節(jié)點(diǎn)相關(guān)信息，用集中式算法來選舉簇頭。計算節(jié)點(diǎn)競爭力［6］:

　　定義簇頭選舉的能量閾值Eelect為發(fā)送和接收50個數(shù)據(jù)包的能量消耗，若節(jié)點(diǎn)能量小于Eelect，則不參加競選。定義簇內(nèi)備選節(jié)點(diǎn)的競爭力為C;En_current為備選節(jié)點(diǎn)的剩余能量;dmax為備選節(jié)點(diǎn)到簇內(nèi)其他節(jié)點(diǎn)的最大距離;daver為備選節(jié)點(diǎn)到簇內(nèi)其他節(jié)點(diǎn)的平均距離,計算公式如式（11）所示；dtoBS為備選節(jié)點(diǎn)到基站的距離；d0為無線通信能耗模型中的距離閾值；ω1、ω2、ω3為權(quán)重系數(shù)，且：

　　其中，dto_node_i為備選節(jié)點(diǎn)到簇內(nèi)第i個節(jié)點(diǎn)的距離，N為簇內(nèi)節(jié)點(diǎn)總數(shù)。

　　則新的簇頭選舉公式為：

　　I=max0<i<N（Ci）(12)

　　求解出式(12)的最優(yōu)解與次優(yōu)解。

　　選舉簇頭時，備選節(jié)點(diǎn)距基站越近、剩余能量越大、到其他節(jié)點(diǎn)的平均距離越小，其競爭力越強(qiáng)。原簇頭遍歷所有成員節(jié)點(diǎn)，選取C值最大和次大的節(jié)點(diǎn)為主、副簇頭。

　　選舉結(jié)果如圖5所示。與圖4不同的是，在這個兩跳網(wǎng)絡(luò)中，黃、綠線分別代表主、副簇頭交替與sink節(jié)點(diǎn)通信，而簇內(nèi)部結(jié)構(gòu)不變。

　　在穩(wěn)定階段的交替機(jī)制中，對Nslot個時隙周期進(jìn)行操作。時隙周期總數(shù)由式（13）求得［6］：

　　其中，T為每輪數(shù)據(jù)傳輸階段的時間，Tslot為時隙周期。設(shè)m個時隙周期為一組，將Nslot個時隙周期分為H組，且

　　當(dāng)H為奇數(shù)時，主簇頭工作，副簇頭退化為普通節(jié)點(diǎn)；當(dāng)H是偶數(shù)時，反之。如此交替，節(jié)點(diǎn)將數(shù)據(jù)發(fā)送到當(dāng)值簇頭，簇頭將數(shù)據(jù)發(fā)送給sink節(jié)點(diǎn)，大幅推遲簇頭的死亡時間。

　　式（14）中，m為喚醒因子。若m為1，則主副簇頭輪換頻繁，會耗費(fèi)額外能量用于通信模塊的頻繁喚醒；若m太大，副簇頭工作時主簇頭需要較長的睡眠時間，主簇頭對簇的動態(tài)管理(如更換簇頭、新節(jié)點(diǎn)加入等) 會受到影響。因此，應(yīng)根據(jù)實(shí)際情況來靈活設(shè)置m值。

　　綜上所述，CSDCHA的算法流程如下：

　　CSDCHA在成簇后，以主副簇頭的剩余能量為迭代的循環(huán)條件，存活節(jié)點(diǎn)數(shù)為迭代的終止條件，循環(huán)完成雙簇頭選舉、交替采樣傳輸?shù)墓ぷ鳌?/p>

3仿真結(jié)果

　　本文使用MATLAB對CSDCHA進(jìn)行驗(yàn)證。仿真場景為：N=256個傳感器節(jié)點(diǎn)均勻分布在160 m×160 m的正方形區(qū)域內(nèi)，基站位于區(qū)域外，坐標(biāo)為(80，170)。CS理論和分層路由結(jié)合，觀測矩陣的維數(shù)M≥4k［8］，假設(shè)k=10，則成為簇頭的最佳比例p≈0.15。仿真結(jié)束條件為存活節(jié)點(diǎn)數(shù)小于滿足CS采樣的最低需求。

　　仿真過程中，實(shí)現(xiàn)了數(shù)據(jù)處理、簇的劃分、簇頭選舉、觀測矩陣建立與數(shù)據(jù)傳輸以及數(shù)據(jù)壓縮與恢復(fù)的全過程。其中，重點(diǎn)觀察節(jié)點(diǎn)的生命周期和恢復(fù)精度。

　　生存周期方面，將CSDCHA、經(jīng)典LEACH、CS結(jié)合LEACH（記為LEACH_CS）以及CS結(jié)合高斯隨機(jī)矩陣（記為GM_CS）進(jìn)行對比，如圖6所示。由圖6可看出：GM_CS很快就有大量節(jié)點(diǎn)死亡，說明了采用分簇路由算法的必要性；LEACH_CS和LEACH相比，節(jié)點(diǎn)的生存時間有了很大的提升，說明CS在節(jié)省耗能方面的優(yōu)越性；CS-DCHA和LEACH_CS相比，在第一個節(jié)點(diǎn)死亡時間上更有優(yōu)勢，這是因?yàn)樵诜执氐幕A(chǔ)上，采用雙簇頭輪換傳輸，能量消耗更為分散，耗能更均勻。

　　恢復(fù)方面，采用BCS算法［8］。對稀疏系數(shù)進(jìn)行BCS估計，求出原始信號的估計值，部分恢復(fù)結(jié)果如圖7所示。經(jīng)測算，誤差率為0.003 8，恢復(fù)時間為0.045 s，誤差在允許范圍內(nèi)?！?/p>

4結(jié)論

　　本文提出了一種基于雙簇頭交替和CS理論的WSNs路由算法——CSDCHA算法，CSDCHA可以提高WSNs網(wǎng)絡(luò)的生命周期，并降低能量損耗。仿真結(jié)果證明了算法的可行性和有效性，且在網(wǎng)絡(luò)生命周期方面優(yōu)于經(jīng)典的LEACH路由算法和采用高斯隨機(jī)矩陣的CS方法。但該算法還存在一些不足，如分簇的過程中沒有考慮簇的大小均勻分布；觀測矩陣僅實(shí)現(xiàn)了從簇頭傳輸?shù)絪ink節(jié)點(diǎn)數(shù)據(jù)的稀疏表示，簇內(nèi)采集數(shù)據(jù)過程并未應(yīng)用CS理論。這些問題都需繼續(xù)研究。

參考文獻(xiàn)

　?。?］ 李建中，高宏. 無線傳感器網(wǎng)絡(luò)的研究進(jìn)展［J］.計算機(jī)研究與發(fā)展,2008,45(1):115.

　?。?］  Liu Yunhao, He Yuan, Li Mo, et al. Does wireless sensor network scale? A measurement study on GreenOrbs［J］. IEEE Transactions on Parallel Distributed Systems,2013,24(10):19831993.

　?。?］ 胡嬌,孫堅(jiān),王曉薇,等.基于WSNs水環(huán)境云端監(jiān)測系統(tǒng)研究［J］.微型機(jī)與應(yīng)用,2015,34 (11):6063.

　?。?］ 王泉,張納溫,張金成.壓縮感知在無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集中的應(yīng)用［J］.傳感技術(shù)學(xué)報,2014,27(11):15621567.