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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

1 壓縮感知理論

1.1 基本原理

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

(1)

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

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

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

(2)

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

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

(3)

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

(4)

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

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

圖1 傳統采樣處理理論的框圖

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

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

1.2 構建觀測矩陣

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

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

圖3 系統模型

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

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

2 CS-DCHA算法

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

2.1 CS-DCHA算法的成簇階段

在選簇頭時，每個節點產生一個0～1隨機數，若該隨機數小于閾值，則該節點選為簇頭。

閾值的計算公式為：

(5)

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

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

選舉簇頭與形成簇的效果如圖4所示。sink節點、簇頭、簇內節點構成一個兩跳網絡。sink節點負責全局的數據融合；簇頭負責區域內的數據轉發和計算處理；簇內節點負責信息感知。

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

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

(6)

接收kbit數據所需的能量為：

ER(i)=kEelec

(7)

其中，Eelec是收發單位數據消耗的能量，而閾值為：

(8)

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

2.2 CS-DCHA算法的穩定階段

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

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

(9)

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

ω1+ω2+ω3=1

(10)

(11)

其中，dto_node_i為備選節點到簇內第i個節點的距離，N為簇內節點總數。

則新的簇頭選舉公式為：

(12)

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

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

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

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

(13)

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

(14)

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

式(14)中，m為喚醒因子。若m為1，則主副簇頭輪換頻繁，會耗費額外能量用于通信模塊的頻繁喚醒；若m太大，副簇頭工作時主簇頭需要較長的睡眠時間，主簇頭對簇的動態管理(如更換簇頭、新節點加入等) 會受到影響。因此，應根據實際情況來靈活設置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在成簇后，以主副簇頭的剩余能量為迭代的循環條件，存活節點數為迭代的終止條件，循環完成雙簇頭選舉、交替采樣傳輸的工作。

3 仿真結果

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

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

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

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

圖7 部分數據恢復效果圖

4 結論

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

[1] 李建中，高宏. 無線傳感器網絡的研究進展[J].計算機研究與發展,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水環境云端監測系統研究[J].微型機與應用,2015,34 (11):60-63.

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

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

[6] 趙小川,周正,秦智超.基于雙簇頭交替和壓縮感知的WSN路由協議[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] 鄒志強,王悅,沙超,等.無線傳感器水下監測網絡稀疏采樣和近似重構[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)；江蘇省科技支撐計劃(社會發展)(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-)，男，本科生，主要研究方向：無線傳感器網絡。

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

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