基于壓縮感知和雙簇頭交替的WSNs路由算法*

何 旭，楊韻怡，林怡陽，鄒志強，沈 澍

(1.南京郵電大學 貝爾英才學院，江蘇 南京 210046；2.南京郵電大學 計算機學院，江蘇 南京 210003；3.江蘇省無線傳感網(wǎng)高技術研究重點實驗室，江蘇 南京 210003)

基于壓縮感知和雙簇頭交替的WSNs路由算法*

何 旭1，楊韻怡1，林怡陽1，鄒志強2,3，沈 澍2,3

(1.南京郵電大學 貝爾英才學院，江蘇 南京 210046；2.南京郵電大學 計算機學院，江蘇 南京 210003；3.江蘇省無線傳感網(wǎng)高技術研究重點實驗室，江蘇 南京 210003)

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

無線傳感器網(wǎng)絡;分簇路由算法;壓縮感知;貝葉斯恢復算法

0 引言

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

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

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

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

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

1 壓縮感知理論

1.1 基本原理

在標準CS框架中[7]，觀測到的自然界的物理信號記為x∈RN，且在某個變換基上有稀疏表示即：

(1)

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

下面對信號進行某種隨機采樣，使得

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

(2)

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

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

(3)

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

(4)

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

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

圖1 傳統(tǒng)采樣處理理論的框圖

圖2 壓縮感知理論的采樣處理框圖

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

1.2 構建觀測矩陣

CS主要由信號的稀疏表示、觀測矩陣和重構算法構成。其中，建立觀測矩陣是關鍵過程[10]。

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

圖3 系統(tǒng)模型

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

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

2 CS-DCHA算法

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

2.1 CS-DCHA算法的成簇階段

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

閾值的計算公式為：

(5)

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

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

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

圖4 臨時簇頭選舉和簇的形成效果圖

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

(6)

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

ER(i)=kEelec

(7)

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

(8)

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

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

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

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

(9)

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

ω1+ω2+ω3=1

(10)

(11)

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

則新的簇頭選舉公式為：

(12)

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

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

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

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

(13)

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

(14)

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

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

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

CS-DCHAAlgorithmInput:sparsitylevelk,numberofnodesN,thresholdtokeepWSNsworkingNminOutput:measurementmatrixΦ∈RM×NInitialization:randomarrayα∈RN,energyarrayEcurrent∈RN,thresholdtochoosetemporaryclusterheadT∈RN,numberofsurvivingnodesNlive=N,thresholdenergytoworkEminRepeat(1)choosetemporaryclusterhead:ifα(n)

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

3 仿真結果

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

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

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

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

圖7 部分數(shù)據(jù)恢復效果圖

4 結論

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

[1] 李建中，高宏. 無線傳感器網(wǎng)絡的研究進展[J].計算機研究與發(fā)展,2008,45(1):1-15.

[2] 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.

[3] 胡嬌,孫堅,王曉薇,等.基于WSNs水環(huán)境云端監(jiān)測系統(tǒng)研究[J].微型機與應用,2015,34 (11):60-63.

[4] 王泉,張納溫,張金成.壓縮感知在無線傳感器網(wǎng)絡數(shù)據(jù)采集中的應用[J].傳感技術學報,2014,27(11):1562-1567.

[5] 沈波,張世永,鐘亦平.無線傳感器網(wǎng)絡分簇路由協(xié)議[J].軟件學報,2006,17(7): 1588-1600.

[6] 趙小川,周正,秦智超.基于雙簇頭交替和壓縮感知的WSN路由協(xié)議[J].軟件學報,2012,23(1):17-24.

[7] DONOHO D.Compressed sensing[J]. IEEE Transactions on Information Theory,2006, 52(4):1289-1306.

[8] Zou Zhiqiang, Hu Cunchen, Zhang Fei,et al. WSNs data acquisition by combining hierarchical routing method and compressive sensing [J]. Sensors, 2014, 14(9): 16766-16784.

[9] 邵文澤，韋志輝.壓縮感知基本理論: 回顧與展望[J].中國圖象圖形學報,2012,17 (1):1-12.

[10] 劉曉靜,唐加山.一種構造壓縮感知測量矩陣的新方法[J].微型機與應用,2014,33 (4):74-76.

[11] TAO T. Compressed sensing-robust recovery of sparse signals fromlimited measurements[EB/OL].(2008-08-02)[2015-10-27].https//terrytao.files.wordpress.com/2008/03/anziam.pdf.

[12] 鄒志強,王悅,沙超,等.無線傳感器水下監(jiān)測網(wǎng)絡稀疏采樣和近似重構[J].儀器儀表學報,2012,33(12):2728-2734.

[13] Hu Haifeng, Yang Zhen, Bao Jianmin. Wavelet transform based distributed compressed sensing in wireless sensor networks[J].China Communications,2012,9(2):1-12.

The routing algorithm of WSNs based on compressive sensing theory and the double cluster head mechanism

He Xu1,Yang Yunyi1,Lin Yiyang1,Zou Zhiqiang2,3,Shen Shu2,3

(1.Honors College, Nanjing University of Posts and Telecommunications, Nanjing 210046, China;2.College of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210003, China;3.Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Nanjing 210003, China)

An energy efficient routing algorithm in Wireless Sensor Networks(WSNs) named CS-DCHA was proposed based on Double Cluster Head Alternation(DCHA) and Compressed Sensing(CS). This CS-DCHA improves the algorithm of Deterministic Cluster-Head Selection (DCHS) by applying CS in the sparse sampling process. CS-DCHA can distribute the energy load evenly during the transmission by using DCHA. And Bayesian Compressed Sensing(BCS) algorithm is used to approximate the recovery of the original signal with a lower signal reconstruction error. The simulation results show that the CS-DCHA algorithm can help to save more energy and expend the lifetime of WSNs significantly, in the case that the precision of signal reconstruction reaches a certain level.

Wireless Sensor Networks(WSNs); clustering routing algorithm; Compressed Sensing (CS); Bayesian Compressed Sensing(BCS)

國家自然科學基金資助項目(61373137，61401221，61472193)；江蘇省科技支撐計劃(社會發(fā)展)(BE2014718)；江蘇省自然科學基金項目(BK2012436,BK20141429)；南京郵電大學自然科學基金項目(NY213037);大學生STITP省級項目(SYB2013002)

TP33

A

1674-7720(2016)04-0068-04

何旭，楊韻怡，林怡陽，等．基于壓縮感知和雙簇頭交替的WSNs路由算法[J] .微型機與應用，2016，35(4)：68-71，75.

2015-10-27)

何旭(1994-)，男，本科生，主要研究方向：無線傳感器網(wǎng)絡。

楊韻怡(1993-)，女，本科生，主要研究方向：無線傳感器網(wǎng)絡。

鄒志強(1967-),男,通信作者,博士,副教授，主要研究方向：無線傳感器網(wǎng)絡，社會網(wǎng)絡及移動互聯(lián)網(wǎng)絡的研究與應用。E-mail:zouzq@njupt.edu.cn。