基于節點能耗均衡的WSN 覆蓋策略

馮 琳，冉曉旻，梅關林

（信息工程大學 信息系統工程學院，河南 鄭州450001）

0 引 言

無線傳感器 網 絡 （wireless sensor networks，WSN）［1］可以對目標數據進行多目標、多角度地收集，完成探測任務［2］。如何有效組網覆蓋是關鍵前提，組網覆蓋問題是指如何確保部署節點形成的覆蓋范圍達到監測環境的要求［3］，而尋求合適無線傳感器的覆蓋部署策略是研究組網技術的首要問題，有效解決好節點數目與節點能耗之間矛盾問題［4］，決定著網絡工作階段成本代價、感知能力、通信保障、監控追蹤等服務指標的改善［5］。網絡生存時間作為衡量無線傳感器網絡性能好壞的重要指標之一，是當前研究的一大熱點。當前應用在各個領域的傳感器節點通常采用自供電模式，且它們具有單次部署數量大、單個體積小、布設環境惡劣等特點。組網地理環境復雜，甚至充滿極大危險性，對于多次重復布設以及補充布設提出了挑戰，因此網絡對單次布設所能達到的服務時長依賴性極強。網絡的性能會隨著節點耗能的死亡而慢慢喪失，在現有條件下，研究如何有效利用初次部署節點發揮最優的網絡服務周期至關重要。如何在大規模的網絡環境下最有效地利用節點能量，保證節點能耗的均衡性，延長網絡生存時間是節能覆蓋優化研究的一項重要內容。

網絡生存時長是指目標區域在一直滿足設定覆蓋率這一前提要求下WSN 所能持續工作的最大時長。改善網絡節點能耗的均衡性，促使整體節點能耗降低并趨于更強的同步性，即保證所有節點趨于同一時間段耗能完畢，也就是通常說的一致的生存時間。在地理環境復雜、危險性極高的區域進行無線監測網的構建需要付出很高的代價，不允許節點重新補充布設，而且對網絡的覆蓋性能要求通常比較高，不允許局部節點過早因耗能過度 “死亡”導致覆蓋區域盲區出現。因此要求一次性部署完畢后在保證一直滿足覆蓋要求下最大程度延長網絡的生存時長。

無線傳感網監測如圖1所示。

圖1 無線傳感網監測

假定模型為事件驅動型網絡，節點在執行感知任務時消耗的能量占主導地位，處于休眠狀態的節點不具有感知能力，不會引起能量消耗。

1 相關工作及應用模型

1.1 相關工作

針對WSN 覆蓋優化中的重難點問題，相關研究人員進行了大量工作。朱藝華等［6］從路由的分流角度出發，研究了如何在數據的分組與轉發跳數的基礎上進行改善算法以延長網絡生存時間。經典方法則從另一個角度提出輪換“活躍”和 “休眠”節點的節能覆蓋方法，在不影響網絡整體覆蓋性能的前提下減少了節點的耗能量，有效的延長了網絡的生命周期［7］。也有相關研究通過引入拓撲控制中的功率思想，并用GA 求解數學模型，實現節約能耗的目的［8］。韓志杰等提出了節點自適應傳感半徑調整算法，在不影響覆蓋性能的前提下，從降低節點覆蓋的冗余度出發，有效地實現了節點最佳覆蓋范圍的選擇以及對覆蓋的控制［9］。LU 等通過比較由于距離Sink節點遠近不同而導致的節點能耗差異，得到節點部署的密度函數，在不影響覆蓋效果的情況下有效地均衡了整個網絡的能量消耗，避免了覆蓋空洞的出現［10］。對于異構傳感器的研究者采用多條直線采樣覆蓋的方法，將二維平面的覆蓋優化問題轉化為對一維直線的覆蓋優化問題，通過建立非線性二次優化數學模型求次優解的辦法最終實現異構傳感器節點的覆蓋優化目標［11］。另一方面，改進策略也是優化覆蓋性能的重要手段，比較經典的有以節點簇為代表的LEACH 策略以及在它基礎上進行改進的HEED 算法等，后者從延長網絡生存時長的角度出發，考慮到節點剩余能量、通信代價等因素，提出了一種新的簇頭選舉方法，該方法的缺點也很明顯，要求所有節點的通信半徑必須保持一致且WSN 網絡節點必須保持均勻分布，實用性不強。還有部分相關文獻從其它角度提出網絡節能優化算法，但都離不開節點 “活躍”和“休眠”兩個狀態的有效切換。基于該思想的WSN 節能優化相關策略的關鍵就是在確保覆蓋要求的前提下最大化輪換節點集合數目。

1.2 應用模型

1.2.1 節點感知型

通常采用較多的感知模型有兩種，分別為布爾感知模型與概率感知模型，布爾 （0—1）模型是一種明確劃分感知范圍的模型，概率感知模型對復雜環境中異構傳感器具有較強的實用性，在相關文獻中該模型得到有效應用［12］。布爾模型簡單實用，適合作為節點狀態切換優化策略的假設模型。假定節點覆蓋的目標區域為二維平面，傳感器節點用si表示，（xi，yi）為相對應的節點坐標，則目標點p（xp，yp）被節點si檢測的概率為

目標點p 被整個監測區域內的傳感器節點同時進行檢測的聯合檢測概率為

式中：sall——對目標節點具有感知能力的傳感器節點集合。n——所有被部署的傳感器節點。

1.2.2 覆蓋模型

（1）區域覆蓋率：

感知模型為1.2.1章節中假設模型，考慮到優化目標的性能評價標準，對監測區域進行網格劃分 （m×n），并將其離散成對應的像素點。本文中，網絡覆蓋率定義為滿足式 （2）要求的單元格數量與總的單元格數量的比值，即

如果目標區域中的任一像素點都能夠被至少一個節點的感知范圍所覆蓋，則稱該區域實現完全覆蓋。圖2是本文采用的完全覆蓋節點部署，為了更好驗證后續的效果，初期布設我們假定節點趨于均勻分布，避免節點過度集中的情況出現。該系統中，出現在任何網格點上的目標都能夠被檢測到。

（2）能量均衡：

1）局部能量Ek：對目標區域進行均勻網格劃分，網格數量為k。第k（k∈K）網格的局部能量為該網格中所有節點剩余能量的均值，即

圖2 傳感器節點覆蓋

式中：nk——第k 網格中所包含的節點數量，Ekω——第k網格中節點ω 的剩余能量。

2）能量均衡系數Em：在1）中求得局部能量的基礎上分別得到其中的最大值、最小值以及平均值，定義最大值與最小值的差值與平均值的比值代表感知網絡的能量均衡系數Em，即

Em的大小能夠很好地體現出整個網絡不同區域之間節點能耗的均衡性，Em的值越小說明所有節點整體能量消耗越均衡，反之則代表能耗均衡性越差。

（3）網絡生存時長：

f3代表對網絡生存時間的歸一化處理，當網絡節點由于耗能導致覆蓋率下降到某一設定值時我們認為網絡生存時長結束，進行歸一化處理后得到f3。

因此下式可以作為一個整體優化目標函數

式中：ω1、ω2、ω3——不同子目標函數對應的權值，其滿足關系式ω1＋ω2＋ω3＝1。顯然整體目標函數f的值將介于0～1之間，其值越大，說明整體優化效果越好。f1代表式（3）中的覆蓋率指標，f2則表示式（5）中的能量均衡系數。

1.2.3 節點假設條件

（1）布設節點均為同構節點，具有相同的性能參數（如初始能量、能耗參數、感知半徑、通信半徑、節點狀態切換能力等），感知模型與覆蓋模型滿足1.2.1章節所述。

（2）節點能夠通過GPS或者其它定位算法等得到自身的位置信息，且每個節點能夠準確獲取其鄰居節點的地理位置信息。

（3）所有節點具有統一的能耗模型，為便于其它優化目標值得獲取，假定節點能耗只與其活躍時間有關，其處于活躍狀態周期內時每秒耗能為0.1J，且節點能夠得到自身的能量剩余量。

2 WSN 覆蓋策略

2.1 輪換活躍／休眠節點優化策略

節點 “活躍”和 “休眠”狀態的相關定義請見參考文獻［7］，“輪換優化策略”的主要思想是通過調整節點狀態切換形式達到優化網絡生存時長的目的。節點的每個輪換周期都由self－scheduling階段和working兩個階段組成，在進行判定階段主要進行的工作分為兩步：

（1）各節點首先向滿足感知條件的鄰居節點進行通告信息的廣播，通告信息主要指節點身份、節點位置信息等，對鄰居節點進行定義

ri＝rj說明為同構傳感器節點，在本文中滿足該件。

（2）節點判定自身對目標的感知任務是否可以交給鄰居節點代替完成，如若可以則需要產生相應的信息進行通告，之后該節點可以進入 “休眠狀態”，判定后找不到替代工作的節點則需要繼續執行感知任務。

針對上一段提出的節點輪換活躍與休眠策略，節點自身感知任務能夠被鄰居節點替代必須滿足以下位置條件：

由幾何知識，節點方向角為

中心角為

由固有的條件：0＜d（i，j）≤r可得中心角的變化范圍：120°≤θj→i＜180°由此可得：一個節點必須至少由3個鄰居節點才能覆蓋其感知區域，才有條件進入休眠狀態。

覆蓋盲區產生條件：節點根據之前描述的判定標準判定自身是否可以在下一狀態進入休眠，當相鄰節點同時滿足條件并在下一輪換周期同時執行休眠操作時，產生如圖3（b）所示的覆蓋盲區。

如在圖3 （a）所示，節點e的感知范圍完全可以被鄰近節點 （a、c、f）完全覆蓋替代，同樣，節點f的感知區域也能夠同時被其鄰近節點 （b、d、e）完全覆蓋替代，因此判定節點e、f都滿足 “休眠”條件，但當這兩個節點同時執行休眠任務時就會出現部分區域無法被任何感知節點覆蓋的現象，即所謂的 “盲區”，如圖3 （b）中虛線包圍區域所示。

圖3 “盲區”

早期的基于延長網絡生存周期的節點活躍／休眠覆蓋策略雖然在節約網絡節點能量，延長系統生命周期方面有明顯改進，但覆蓋 “盲點”的出現直接影響了網絡的覆蓋效果。因此該策略對于一些敏感、危險多發區域的覆蓋感知效果魯棒性較差。

2.2 基于消除盲區的覆蓋策略的改進

針對2.1章節中覆蓋 “盲區”的出現，文獻 ［7］提出一種改進方法，主要思想是在保持原有的感知覆蓋效果下最大限度減少網絡生存周期中工作節點的數量，既做到了“盲點”消除，又節省了網絡節點能量。在判定節點是否向休眠狀態轉化之前先要經歷退避時間：只有經歷了該退避時間Td之后節點才能自檢，且該退避時間是隨機的，當然，周圍節點的密度也可以作為計算退避時間Td的重要參考，這樣可以對網絡中 “活躍”節點的數量進行控制，從而達到減少節點能耗的目的。只有消除覆蓋過程中的 “盲區”，才能確保網絡功能運轉正常，在節點在進行 “休眠”之前加入等待時間Tw，Tw具有一定的隨機性，節點在等待時間過程中監聽其鄰居節點的狀態是否發生變化。

該策略實際上是LEACH 策略的一個擴展，它不僅能夠有效控制網絡中的冗余節點，而且對于節點狀態輪換失誤、節點失效都具有很好的魯棒性，因此對網絡的覆蓋優化改善效果明顯。研究結果表明該策略能夠有效消除傳統策略導致的覆蓋 “盲區”，而且網絡生存時間較LEACH 策略延長了1.7倍，但是其在如何進一步均衡節點的能耗方面沒有涉及，這也是該策略值得改進之處。

3 基于節點能耗均衡的網絡生存時間延長策略

現有的無線傳感器主要采用自攜帶電池的方法進行供電，局限于節點自身體積的大小，電池電量有限，且這一問題在短時間內無法根治；感知網絡通常應用在山區海島、戰場前沿等布設難度極大的領域，因此如何最小化網絡運行過程中發生的能量消耗，優化網絡的整體生存時間是進行研究的關鍵，才能減少節點的重復補充布設，降低網絡運行成本。

3.1 網絡生存時間的延長

如第一節中介紹，某些特定環境不僅單純有在保持覆蓋率的基礎上降低節點耗能有要求，對基于節點能耗均衡性下的網絡生存時長的延長提出了更高的標準。在本文中我們定義網絡生存時間為從網絡建立到由于部分節點耗能完畢而導致網絡覆蓋率下降到某一設定值時網絡所歷經的時間周期。

3.2 改進思想及目的

首先對節點剩余能量進行百分比量化，為后續改進節點進入休眠狀態前的退避時間Tw做準備，促使剩余能量較少的節點有更大的機率進入休眠狀態。該改進策略不僅要求能夠消除原有的覆蓋盲區，在均衡節點能耗與延長網絡生存時間也需要發揮明顯作用。

（1）根據式 （7）可計算周圍節點的數量，由此周圍節點密度決定退避時間Td，顯然，密度越小退避時間會相應縮短，利于降低節點的整體能耗

式中：Ni——節點i周圍節點的數量；No——所有節點周圍節點的最大值；Ta——設定的基礎退避值，根據具體的布設場景進行設置。

（2）節點根據計算得到的剩余能量量化值決定Tw的值，從而保證節點能量剩余較少的更早地進入休眠狀態，均衡網絡的能量消耗。也是本文研究的關鍵所在

式中：Tw——節點進入休眠狀態的等待時間；To——最大等待時間；Em與Eo——節點的剩余能量與初始能量；α——均衡系數，可自行設定。

3.3 覆蓋優化流程

根據改進策略的思想得到覆蓋優化的具體流程如圖4所示。

算法步驟：

（1）按照1.2.2章節中的覆蓋模型對目標區域進行部署覆蓋，并依據式 （3）計算覆蓋率fn；

（2）每個時間輪Tn開始前首先計算當前的覆蓋率fn與能量均衡系數fE，并判斷fn與標準fo的關系，若fn＜fo，則認為網絡生存時間結束；若fn≥fo，則繼續下面步驟；

（3）由式 （7）得到節點的鄰居節點數量并計算鄰居節點密度，根據式 （11）計算得到退避時間Td；

圖4 覆蓋優化流程

（4）根據2.1 章節中的準則判定可進入休眠狀態的節點；

（5）由式 （12）得到等待時間Tw，執行退避時間后節點進入休眠狀態；

（6）進入下一次判定循環。

4 仿真與結果分析

本文在MATLAB2009 平臺下進行仿真實驗，節點在50m×50m 環境下按照圖1的覆蓋示意圖進行區域覆蓋部署。傳感器感知半徑均為5m，通信半徑均為10m，節點初始能量均為30J，傳感器采集頻率為0.2 Hz，不考慮網絡中心匯聚節點，采集目的節點為所布設所有節點，假定節點處于活躍狀態時耗能為1J／輪 （5s），節點處于休眠狀態時耗能可忽略。

圖5呈現的是目標區域的節點覆蓋效果。為了更好地驗證本文策略優化性能，區域要確保實現全覆蓋且部分區域達到多重覆蓋，這是后面研究覆蓋盲區的消除以及節點的能耗均衡共同的重要前提。

針對子目標函數——覆蓋率進行仿真，結果如圖6 所示。為了簡化仿真程序，我們只對布設75個傳感器節點的情景進行仿真分析，當區域覆蓋率下降到90%時認為網絡生存時間終結。

圖5 目標區域覆蓋效果

圖6 覆蓋率變化曲線

網絡運行初期既沒有節點死亡也沒有覆蓋盲區的出現，區域覆蓋率將持續保持100%，如圖6 所示的初期平穩直線。隨著時間推移，出現節點耗能完畢，導致覆蓋率出現下降趨勢，如圖中從第24×5s開始所示，到150×5s時覆蓋率下降到標準以下。當然，在第44×5s之前覆蓋率雖然一直保持在100%并不代表這段時間沒有節點死亡，只是少數死亡節點并沒有影響到整體的覆蓋性能。

圖7展示的是3種不同方法的覆蓋率隨時間變化曲線。起始階段普通輪換機制由于覆蓋盲點的出現導致網絡初期覆蓋率無法保持在100%，如圖7 中普通輪換機制曲線所示；本文方法由于對節點進行了均衡能耗處理，覆蓋率下降具有一定的規律性且較緩慢，文獻 ［7］中的方法雖然也在普通機制的基礎上進行了改進，但由于節點能耗均衡性較差，優化效果并不理想，如圖7文獻［7］算法曲線所示。

圖8是另一個子目標函數——均衡值的數據統計，之前已經提到均衡值越小代表節點的能耗均衡性越良好。由于沒有采取任何均衡措施，前兩種方法得到的均衡值不會有太大差異，從圖8普通輪換機制與文獻 ［7］算法的均值點可以證實該結論。而本文的均衡值要明顯低于前兩種方法，隨著網絡生存時間的推移，均衡差值會越來越大，說明均衡性發揮的作用會越來越明顯，正如圖8所示。

圖7 覆蓋率變化對比曲線

圖8 均衡值隨時間變化統計

圖9展示的是網絡中死亡節點數量隨時間的變化曲線。雖然普通輪換機制休的休眠策略容易導致大量覆蓋空洞，影響整體覆蓋率，但普通輪換機制使得更多的節點處于休眠狀態，死亡節點的數量要少于本文算法與文獻 ［7］算法，如圖9普通輪換機制曲線所示。本文算法對于節點能耗均衡性使得死亡節點數量要少于文獻 ［7］算法，正如圖9文獻 ［7］算法與本文算法對比曲線所示。

圖10是不同策略網絡生存時間的對比，分別對節點數量為50、75、100不同情況下的生存時間進行統計。文獻［7］法由于時延的引入，降低了活躍節點的數量，對節點的整體能耗降低起到了一定作用，相對應延長了網絡的生存時間；而本文方法在時延的基礎上加入了能耗均衡性的考慮，將進一步延長網絡的生存時間，且當節點數目增大時，節點的能耗均衡所起到的效果會更加明顯，正如圖10所示當節點數目為100時本文策略下的網絡生存時間比節點數量為75時提高效果更優一樣。

圖9 死亡節點數量變化曲線

圖10 網絡生存時間對比

5 結束語

針對式 （6）提出的整體優化目標函數對其3個子函數進行了數據采集并分別進行了方法效果對比。在均衡值、網絡生存時間以及節點死亡率方面本文提出的策略都表現出了更優良的性能，為一些敏感、偏遠、危險的布設區域爭取了更多的網絡生存時間，避免了多次重復部署的危險性，降低了布設與維護代價。為后期特定場景的針對性需求提供了研究基礎，在此基礎上我們將對覆蓋優化進行更為細致的探討。當然，文章進行探討時將節點簡單分為活躍于睡眠兩種狀態，沒有考慮節點處理、轉發、通信多種狀態以及作為Sink節點等多種情況引起的耗能不均衡，節點能耗模型有待進一步細化深入。

［1］XIAO Fu，WANG Ruchuan，SUN Lijuan.Coverage enhancing algorithm for wireless multi－media sensor networks based on three－dimensional perception ［J］.Journal of Electronics，2012，40 （1）：167－172 （in Chinese）.［肖甫，王汝傳，孫力娟.一種面向三維感知的無線多媒體傳感器網絡覆蓋增強算法［J］.電子學報，2012，40 （1）：167－172.］

［2］ZHANG Yayun，JI Zhicheng.Virtual force based multiple particle swarm optimization for deployment strategy in wireless sensor networks ［J］.Journal of Jiangnan University （Natural Science Edition），2012，11 （4）：428－431 （in Chinese）. ［張亞云，紀志成.虛擬力導向多粒子群算法的WSNs部署策略 ［J］.江南大學學報（自然科學版），2012，11 （4）：428－431.］

［3］Yadav J，Sandeep M.Coverage in wireless sensor networks：A survey ［J］.International of Electronics and Computer Science Engineering，2013，2 （2）：464－471.

［4］YAO Xiangguang，ZHOU Yongquan，LI Yongmei.Hybrid algorithm with artificial fish swarm algorithm and PSO ［J］.Application Research of Computers，2010，27 （6）：2084－2086（in Chinese）.［姚祥光，周永權，李詠梅.人工魚群與微粒群混合 優 化 算 法 ［J］.計 算 機 應 用 研 究，2010，27 （6）：2084－2086.］

［5］Siddappa M，Raju C.Survey on efficient coverage and connectivity of wireless networks using intelligent algorithm ［J］.Information Technology and Computer Science，2012，5：39－45.

［6］ZHU Yihua，YANG Chenxi，WU Wandeng，et al.Diffluent traffic routing algorithms trading of network lifetime and number of packet hops for wireless sensor networks［J］.Chinese Journal of Sensors and Actuators，2009，22 （2）：273－279 （in Chinese）.［朱藝華，楊晨曦，吳萬登，等.無線傳感器網絡權衡生存時間與數據分組跳數的分流路由算法 ［J］.傳感技術學報，2009，22 （2）：273－279.］

［7］Tian D，Georganas ND.A node scheduling scheme for energy conservation in large wireless sensor networks ［J］.Wireless Communications and Mobile Computing，2003，3 （2）：271－290.

［8］YIN Weili，CHEN Wei.Simulation research for wireless sensor networks based on genetic algorithm ［J］.Computer Simulation，2010，27 （10）：120－123 （in Chinese）. ［殷衛莉，陳巍.遺傳算法在無線傳感器網絡覆蓋中仿真研究 ［J］.計算機仿真，2010，27 （10）：120－123.］

［9］HAN Zhijie，WU Zhibin，WANG Ruchuan，et al.Novel coverage control algorithm for wireless sensor network ［J］.Journal on Communications，2011，32 （10）：174－184 （in Chinese）.［韓志杰，吳志斌，王汝傳，等.新的無線傳感器網絡覆蓋控制算法 ［J］.通信學報，2011，32 （10）：174－184.］

［10］Lu K，Liu G，Mao R，et al.Relay node placement based on balancing power consumption in wireless sensor networks［J］.IET Wireless Sensor Systems，2011，1 （1）：1－6.

［11］DU Xiaoyu，SUN Lijuan，GUO Jian，et al.Coverage optimization algorithm for heterogeneous WSNs ［J］.Journal of Electronics ＆ Information Technology，2014，36 （3）：696－702 （in Chinese）. ［杜曉玉，孫力娟，郭劍，等.異構無線傳感器網絡覆蓋優化算法 ［J］.電子與信息學報，2014，36（3）：696－702.］

［12］LIU Weiting，FAN Zhouyuan.Coverage optimization of wireless sensor networks based on chaos particle swarm algorithm［J］.Journal of Computer Applications，2011，31 （2）：338－340 （in Chinese）. ［劉維亭，范洲遠.基于混沌粒子群的無線傳感器網絡覆蓋控制 ［J］.計算機應用，2011，31 （2）：338－340.］