基于動態(tài)競爭的能量均衡非均勻路由協(xié)議

王宣懿，曾子維，王 剛

（遼寧科技大學(xué) 計算機與軟件工程學(xué)院，遼寧 鞍山 114051）

無線傳感器網(wǎng)絡(luò)（Wireless sensor networks，WSN）由路由感知通信與計算能力的傳感器節(jié)點組成，節(jié)點以自組織方式組成多到一的通信網(wǎng)絡(luò)，再把采集到的數(shù)據(jù)以多跳的方式發(fā)送到sink 節(jié)點［1］。傳感器節(jié)點主要靠電池提供能量，因此WSN 中能量消耗很受重視，降低能耗與提高網(wǎng)絡(luò)壽命是路由協(xié)議研究的重點之一［2-3］。

為了延長網(wǎng)絡(luò)生存周期，已提出很多分簇和多跳路由算法。最著名的分簇算法為Heinzelmen研究的LEACH（Low-energy adaptive clustering hierarchy）［4］。每一輪分為初始化階段和穩(wěn)定工作階段。但在LEACH算法中簇間通信采用單跳，全部節(jié)點都可和匯聚點直接通信，距離基站較遠的節(jié)點都會進行遠距離通信［5］。因此，簇頭能耗不均從而導(dǎo)致部分節(jié)點過早死亡。并且簇頭選舉的次數(shù)過于頻繁，消耗了較多能量。在選舉過程中也未考慮節(jié)點的剩余能量與位置分布。之后，PEGASIS［6］、EECS［7］、HEED［8］等優(yōu)化算法被陸續(xù)提出，簇間多跳也陸續(xù)被廣泛應(yīng)用。多跳導(dǎo)致靠近基站的簇頭節(jié)點需承載較多的轉(zhuǎn)發(fā)任務(wù)，能耗高從而過早死亡，出現(xiàn)“熱區(qū)”現(xiàn)象。為解決這一問題，蔣暢江等［9］提出 EEUC（Energy efficient uneven cluster）算法，該算法采用簇間多跳模式節(jié)省網(wǎng)絡(luò)能耗，候選簇頭通過節(jié)點位置采用競爭半徑不同的非均勻構(gòu)造簇策略，形成大小不等的簇。但是，在邊緣區(qū)域中轉(zhuǎn)發(fā)數(shù)據(jù)量很少，該算法僅考慮距離不考慮剩余能量作為負載大小不夠全面，并僅以到基站的距離和競爭半徑作為確定下一跳簇頭集合的這種方式總能耗較大。針對此問題，文獻［10］提出高效的非均勻分簇EUCA（Efficient uneven cluster）算法。熊科等［11］提出一種采用雙簇頭均衡能量消耗的非均勻分簇算法。在采用非均勻分簇思想時均需要基于競爭半徑理論，但現(xiàn)有分簇路由協(xié)議中仍存在簇頭選舉不當(dāng)和網(wǎng)絡(luò)能耗不均等問題。因此，本文從提高簇頭選舉質(zhì)量和提升簇間路由效率出發(fā)，針對現(xiàn)有計算閾值和競爭半徑的方法，提出基于概率模型的分簇路由算法（Energy optimized uneven cluster routing，EOUCR）。EOUCR算法在分簇前通過動態(tài)的設(shè)定閾值，得到優(yōu)質(zhì)候選簇頭，再基于各節(jié)點的動態(tài)競爭半徑選出真正簇頭。根據(jù)路由代價函數(shù)計算出各鄰居節(jié)點路由代價值，選擇函數(shù)代價最優(yōu)的簇頭節(jié)點擔(dān)任中繼節(jié)點，得到全局最優(yōu)路徑。期望在網(wǎng)絡(luò)運行過程中能有效均衡節(jié)點能耗，延長網(wǎng)絡(luò)壽命。

1 系統(tǒng)模型和定義

1.1 節(jié)點能耗模型

節(jié)點能耗由感知、通信、數(shù)據(jù)處理三方面構(gòu)成，其中通信能耗占最大比例。采用Heinzelman［12］的簡單能量模型，依據(jù)通信距離長短分為自由空間模型和多路徑衰減模型。在實際應(yīng)用中，傳輸能量基于一個閾值距離d0，當(dāng)通信距離小于d0時，此時考慮為自由空間模型；否則將使用多路徑衰減模型。

節(jié)點發(fā)送l比特數(shù)據(jù)到離自身距離為d的節(jié)點所消耗的能量計算式

節(jié)點接收l比特的數(shù)據(jù)需消耗的能量計算式為

式中：Eelec代表發(fā)送與收發(fā)單位能量消耗，nJ/bit；d為傳輸距離，m；εfs代表采用空間自由模型功率放大損耗，pJ/（bit·m-2）；εmp代表采用多路徑衰減模型功率放大損耗，pJ/（bit·m-2）。

1.2 網(wǎng)絡(luò)模型

假設(shè)本文網(wǎng)絡(luò)中的節(jié)點在以下環(huán)境中：基站與網(wǎng)絡(luò)中的節(jié)點隨機部署，部署后位置固定，基站能量充足。同構(gòu)節(jié)點初始能量相同且節(jié)點間可自由通信。節(jié)點分布均勻，具有相同的概率成為簇頭。節(jié)點可根據(jù)接收到的RSSI（Received signal strength indication）信號強弱計算自身到節(jié)點的距離［13］，并可根據(jù)需要調(diào)整發(fā)射功率。本算法試圖將網(wǎng)絡(luò)采用非均勻分簇，使距離基站較近的簇范圍較小，遠離基站的簇范圍較大，調(diào)整簇間轉(zhuǎn)發(fā)數(shù)據(jù)平衡達到均衡網(wǎng)絡(luò)的效果。

1.3 網(wǎng)絡(luò)生存時間

采用數(shù)據(jù)發(fā)送的輪數(shù)來表示網(wǎng)絡(luò)生存時間，每一輪數(shù)據(jù)傳輸，節(jié)點將監(jiān)測到的全部信息都發(fā)送給sink節(jié)點，統(tǒng)計節(jié)點發(fā)送數(shù)據(jù)所消耗的能量，監(jiān)控節(jié)點剩余能量，記載第一個節(jié)點剩余能量為零的輪數(shù)或死亡節(jié)點到達一定比例時的輪數(shù)。

2 基于動態(tài)競爭的非均勻分簇路由協(xié)議

EOUCR協(xié)議是一個分布式的并行成簇算法，有良好的擴充性。在成簇過程中采用輪循環(huán)方法，每一輪包含兩個階段：設(shè)置簇階段和穩(wěn)態(tài)路由轉(zhuǎn)發(fā)階段。本算法主要工作是對網(wǎng)絡(luò)實現(xiàn)非均勻分簇，在候選簇頭的選舉和競爭以及簇間路由選擇上進行協(xié)作設(shè)計。

（1）設(shè)置簇階段：分為簇頭選擇和構(gòu)成分簇兩方面。首先通過與本文提出的閾值T(n)比較，得出候選簇頭。參考相對剩余能量和位置參數(shù)得到簇競爭半徑選舉出最終簇頭，既避免低能節(jié)點擔(dān)任簇頭，也通過監(jiān)測位置使通信過程傳輸能耗降低且均衡，減少時延。

（2）穩(wěn)態(tài)路由轉(zhuǎn)發(fā)階段：由簇內(nèi)通信和簇間到基站通信組成。采用簇內(nèi)單跳簇間多跳相結(jié)合的方式，以減少能耗為目的設(shè)計簇間路由。

節(jié)點在第r輪時理想狀態(tài)下通信半徑平均值

式中：在一正方形M×M監(jiān)測區(qū)域，隨機部署N個節(jié)點，且每個節(jié)點被選作簇頭的概率為p；Nr為第r輪時網(wǎng)絡(luò)中存活節(jié)點的個數(shù)。

基于理想通信半徑平均值范圍內(nèi)的存活節(jié)點集合。節(jié)點的完美鄰居節(jié)點集合定義

式中：d(i,j)為通訊半徑內(nèi)各節(jié)點i與j之間的距離，m；為節(jié)點j的剩余能量，J；V代表全部節(jié)點集合。

2.1 候選簇頭的生成策略

LEACH 算法在簇頭選舉階段，節(jié)點隨機生成［0，1］之間的隨機數(shù)，當(dāng)隨機數(shù)小于閾值T(n)時，該節(jié)點被選做簇頭。閾值計算式為

式中：p為每一輪中期望的簇頭數(shù)在網(wǎng)絡(luò)節(jié)點總數(shù)的比值；r為當(dāng)前所在的選舉輪數(shù)；G為剩下的1/p輪中沒有被選為簇頭的全部節(jié)點集合。

通過對LEACH 算法的不足及其改進算法的研究，結(jié)合EEUC 提出的成簇思想，在EOUCR 選取候選簇頭時引入相對剩余能量因子、相對簇內(nèi)節(jié)點密度因子和同簇節(jié)點匯聚度因子。

（1）相對剩余能量因子：單獨考慮剩余能量不能準(zhǔn)確判定剩余多少，因此在閾值定義中加入相對剩余能量，其值會隨著運行輪數(shù)變化波動，使閾值定義更為合理具有實時性。

（2）相對簇內(nèi)節(jié)點密度因子：理想通信半徑內(nèi)的實際節(jié)點個數(shù)與監(jiān)測范圍內(nèi)所有節(jié)點數(shù)的比。用來體現(xiàn)實際簇內(nèi)成員數(shù)量值。比值越大說明實際鄰居節(jié)點數(shù)量越大，被選為候選簇頭的概率越大。

（3）同簇節(jié)點匯聚度因子：節(jié)點i的完美鄰居節(jié)點集合內(nèi)的所有節(jié)點到i的距離的平均值與理想通信半徑的比值。其值代表簇內(nèi)節(jié)點匯聚緊密程度體現(xiàn)了簇結(jié)構(gòu)，當(dāng)比值越大說明匯聚程度差，簇內(nèi)通信時延大。

傳感器節(jié)點預(yù)先根據(jù)閾值選出候選簇頭節(jié)點，閾值T(n)計算式

式中：p為存活節(jié)點成為簇頭的期望；r為當(dāng)前循環(huán)輪數(shù)；G為最近1/p輪中未被選為簇頭的節(jié)點集合；Er表示當(dāng)前節(jié)點的剩余能量，J；Eavg為當(dāng)前所有存活節(jié)點的平均剩余能量，J；Ni為節(jié)點通信半徑內(nèi)的節(jié)點數(shù)；Nnum為總的節(jié)點數(shù)；Di-avg為節(jié)點i的理想鄰居節(jié)點集合內(nèi)各節(jié)點到i節(jié)點的平均距離，m；Ri為理想平均半徑；χ1、χ2、χ3代表三項因子的權(quán)重值并且χ1+χ2+χ3=1。

新的閾值T(n)特點：

（1）已成為過候選簇頭的節(jié)點在往后的1/p輪循環(huán)中均不能選為簇頭。

（2）隨著輪循環(huán)增加未當(dāng)選過候選簇頭的節(jié)點選為簇頭的概率逐漸升高。

（3）未成為簇頭的普通節(jié)點根據(jù)收到廣播信號的強弱加入信號最強的簇。

由于簇間多跳導(dǎo)致距離基站近的簇頭承擔(dān)的數(shù)據(jù)轉(zhuǎn)發(fā)量大且能量消耗高，因而失效概率較大。為緩解這種現(xiàn)象，本文提出的算法使靠近基站區(qū)域選舉的簇頭數(shù)較多，成簇規(guī)模較小。即減少簇內(nèi)通信能耗用于簇間轉(zhuǎn)發(fā)，從而達到簇間能耗平衡。遠離基站則相反。算法為每一個候選簇頭設(shè)定了競爭半徑，可以監(jiān)控簇頭在網(wǎng)絡(luò)中的位置分布，即競爭范圍Rc

式中：R是提前設(shè)定的最大競爭半徑；dmax代表網(wǎng)絡(luò)中節(jié)點到達BS的最大距離，m；dmin代表節(jié)點到達BS 的最小距離，m；α、β為位于0～1 之間的常量用于控制競爭半徑取值范圍。

2.2 簇頭節(jié)點的確定

簇頭節(jié)點的選擇決定了網(wǎng)絡(luò)能量均衡和數(shù)據(jù)收集效率。競選簇頭的算法內(nèi)容為，每個候選簇頭以范圍和相對應(yīng)的功率進行廣播自身報文，內(nèi)容包含節(jié)點自身ID、當(dāng)前剩余能量Eres、競爭半徑。同理也能獲知其他鄰居節(jié)點廣播信息。參與競選的所有候選簇頭節(jié)點都建立自己的鄰候選簇頭集合并維護一張鄰居節(jié)點信息集合表，內(nèi)容包含鄰居節(jié)點的ID、鄰居節(jié)點剩余能量Eres、鄰居節(jié)點競爭半徑。候選簇頭Si的鄰居節(jié)點集合

將剩余能量與簇頭集合中節(jié)點剩余能量進行比較，決定能否擔(dān)任真正簇頭。當(dāng)候選節(jié)點競爭成功時，向鄰居節(jié)點廣播勝任消息，鄰居候選簇頭節(jié)點接收消息后退出競選。簇頭競爭規(guī)則如圖1所示。R為相對應(yīng)的競爭半徑，Y1和Y3不在彼此鄰居范圍內(nèi)，Y4位于Y2的競爭范圍內(nèi)為其鄰居節(jié)點。因此Y1、Y3相互不影響，可同時成為簇頭，而Y2成為簇頭后Y4便退出競選。

確定簇頭節(jié)點后，簇頭向全網(wǎng)廣播競選成功消息。普通節(jié)點解除睡眠狀態(tài)，查看保存的通訊范圍內(nèi)簇頭信息表，當(dāng)只保存一個簇頭信息表時，直接加入其簇。當(dāng)保存多個簇頭信息表時，根據(jù)接收信號強度大小，選擇強度最大且通信代價最小的簇頭節(jié)點并發(fā)送申請加入消息。距離相等則加入通訊半徑更大的簇。

分簇結(jié)構(gòu)如圖2所示，實現(xiàn)整個監(jiān)測區(qū)域網(wǎng)絡(luò)的非均勻分簇，可以發(fā)現(xiàn)越是靠近基站的簇，成簇面積越小。在此基礎(chǔ)上簇頭對節(jié)點收集到的信息進行融合，以多跳的方式將數(shù)據(jù)發(fā)送給基站，進入數(shù)據(jù)通訊階段即路由傳輸階段。

2.3 EOUCR算法設(shè)計實現(xiàn)

在分簇階段，首先監(jiān)測范圍內(nèi)的所有節(jié)點并通過函數(shù)rand（0，1）生成隨機數(shù)R。當(dāng)隨機數(shù)小于閾值T(n)時，其節(jié)點成為候選簇頭，進行下一階段的競選。候選簇頭節(jié)點通過式（7）計算出競爭半徑Rc和簇頭剩余能量，并以廣播形式發(fā)送競選簇頭的消息Elect_msg。當(dāng)候選簇頭接收到其它的競選簇頭消息時，比較兩節(jié)點的距離，若小于兩者中任意一個節(jié)點的競爭半徑，將該節(jié)點存儲到自己的鄰居表內(nèi)，對比鄰居表中節(jié)點的剩余能量大小，如其值均小于自己，則當(dāng)選真正的簇頭，否則退出競選。競選成功的簇頭在通信范圍內(nèi)廣播競選成功信息Competehead_msg，普通節(jié)點若同時收到多個簇頭消息，根據(jù)接收信號的強度大小，即選擇距自己近的簇頭申請加入。若普通節(jié)點沒有收到任何簇頭消息，則自己成簇頭。直到監(jiān)測區(qū)域的所有節(jié)點都加入簇，成簇階段就結(jié)束了。本算法流程圖如圖3所示。

2.4 簇間基于能量代價多跳路由協(xié)議

當(dāng)設(shè)置簇階段過程結(jié)束后，WSN 進入穩(wěn)態(tài)路由轉(zhuǎn)發(fā)階段，此階段的主要目標(biāo)是在簇間選擇最優(yōu)的路徑進行數(shù)據(jù)傳輸，從而達到提升網(wǎng)絡(luò)性能的目的。EOUCR算法在傳輸距離較遠時，簇頭選出適合自己的其他簇頭節(jié)點作為中繼節(jié)點，通過中繼節(jié)點將數(shù)據(jù)轉(zhuǎn)發(fā)到基站。因此提前建立多跳傳輸路徑，選擇出可靠性高、能耗均衡的最優(yōu)路徑。詳細步驟如下：

首先節(jié)點采集數(shù)據(jù)，并將采集數(shù)據(jù)以TDMA的方式發(fā)送給自己的簇頭節(jié)點。簇頭把采集到的信息通過數(shù)據(jù)融技術(shù)進行融合然后轉(zhuǎn)發(fā)到匯聚節(jié)點或基站。當(dāng)簇頭有發(fā)送或轉(zhuǎn)發(fā)數(shù)據(jù)任務(wù)時，簇頭查看鄰居節(jié)點與基站的距離，選擇比自身更接近基站的向前鄰居簇頭節(jié)點并計算路由代價函數(shù)，選擇代價函數(shù)最優(yōu)的節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)。當(dāng)節(jié)點成為下一跳時，數(shù)據(jù)會成功地發(fā)送到該節(jié)點，直至數(shù)據(jù)轉(zhuǎn)發(fā)成功，形成可靠性高的最優(yōu)路徑。

向前鄰居節(jié)點的定義

路由代價函數(shù)

式中：ETx(l,d(i,j))為i和j節(jié)點間發(fā)送比特數(shù)據(jù)所消耗的能量，J；d(j,BS)是節(jié)點j與基站之間的距離，m；c1～c3為加權(quán)參數(shù)且滿足c1+c2+c3=1，經(jīng)反復(fù)實驗將其值設(shè)為0.4，0.3，0.3。

由式（10）可知，簇頭節(jié)點有更大概率成為下一跳節(jié)點的條件為：

（1）簇頭節(jié)點剩余能量高。（2）發(fā)送數(shù)據(jù)所需能量越少。（3）簇頭與基站的距離更近。（4）簇頭間的距離更短。

由于簇頭承擔(dān)了網(wǎng)絡(luò)中大量數(shù)據(jù)的通信與轉(zhuǎn)發(fā)，因此均衡各簇頭間的能量消耗是路由重要考慮因素之一，本文提出基于簇頭剩余能量以及發(fā)送數(shù)據(jù)消耗能量和簇頭間距離等因素來確定路由代價函數(shù)，動態(tài)選擇并調(diào)整下一跳簇頭節(jié)點，相比于EEUC等算法在均衡能耗方面更加出色。

3 仿真實驗與結(jié)果分析

3.1 仿真方法及參數(shù)設(shè)置

本文在MATLAB 平臺進行仿真實驗，將400個無線傳感器節(jié)點隨機部署在一個200 m×200 m的監(jiān)測區(qū)域內(nèi)，節(jié)點分布均勻且基站設(shè)立在坐標(biāo)（200 m，250 m）處，基站能量充足不做考慮。能量參數(shù)如表1所示［12］。

3.2 能耗均衡性

在算法比較時，考慮到文獻［13］定義網(wǎng)絡(luò)死亡節(jié)點數(shù)超過20%以上時將影響網(wǎng)絡(luò)正常工作。因此實驗記錄死亡節(jié)點占比超過20%時，網(wǎng)絡(luò)節(jié)點分布情況圖4所示。

表1 仿真場景及參數(shù)Tab.1 Simulation scenarios and parameters

LEACH 協(xié)議采用隨機選舉簇頭，選舉過程中缺少對剩余能量和距離的考慮，使節(jié)點死亡過于集中，當(dāng)網(wǎng)絡(luò)面積較大時，較邊緣的簇頭數(shù)據(jù)傳輸消耗能量較多，因此能量耗盡的節(jié)點更多分布在遠離基站的位置。在EEUC算法中，將穩(wěn)定傳輸階段的TDMA 優(yōu)化為CSMA，但沒有進行能量均衡化優(yōu)化，因此死亡節(jié)點的位置也相對集中在基站附近。本文算法結(jié)合了基于概率模型的閾值公式和動態(tài)競爭半徑，對簇頭選舉進行了優(yōu)化，死亡節(jié)點在整個數(shù)據(jù)中是均勻分布的，解決了熱區(qū)問題，使網(wǎng)絡(luò)能耗更均勻。

3.3 網(wǎng)絡(luò)生命周期

三種算法存活節(jié)點數(shù)的變化狀態(tài)如圖5 所示。本文提出的算法相對其他兩種算法有更長的網(wǎng)絡(luò)生命周期。本算法采用近基站范圍設(shè)立較多簇頭分擔(dān)每個節(jié)點轉(zhuǎn)發(fā)任務(wù)量，從而達到均衡能耗。所以本算法的第一個節(jié)點的死亡時間和網(wǎng)絡(luò)失效時間均晚于其他兩種算法。

3.4 算法穩(wěn)定性

在網(wǎng)絡(luò)拓撲結(jié)構(gòu)固定后，判斷分簇協(xié)議的穩(wěn)定性指標(biāo)是看每輪選舉出的簇頭數(shù)目偏差大小。本文分別從LEACH 算法、EEUC 算法和EOUCR算法運行過程中隨機抽取100輪，拋灑節(jié)點增至到600 個，統(tǒng)計每個協(xié)議簇頭的數(shù)目，如圖6 所示。LEACH算法的簇頭數(shù)目分布在55～104區(qū)間，分布零散且相差懸殊，這是由于LEACH算法采取隨機生成數(shù)和閾值競選簇頭的方法導(dǎo)致。EEUC 算法中采用局部競選機制，使簇頭生成的簇頭數(shù)目值相差較小，分布在15～23區(qū)間。而本文提出的算法簇頭數(shù)目集中分布在42～50 之間，成簇穩(wěn)定，因為本文采用均衡能量劃分非均勻分簇，靠近基站的簇范圍小，簇頭個數(shù)相對較多，整體生成簇頭數(shù)目差異小。

綜上所述，本節(jié)對三種算法進行了對比分析，得出本文提出的算法生成的簇頭數(shù)目更穩(wěn)定，具有更高的可靠性。

4 結(jié) 論

本文算法以均衡能耗，延長WSNs的網(wǎng)絡(luò)生命周期為目標(biāo)，并針對現(xiàn)有分簇路由算法存在的缺點和不足進行改進，提出了一種基于動態(tài)競爭的能量均衡非均勻路由協(xié)議。本算法的核心是對簇頭選舉閾值T(n)進行重新定義，加入相對剩余能量，相對簇內(nèi)節(jié)點密度和同簇節(jié)點匯聚度因子來約束候選簇頭的形成，以解決現(xiàn)有分簇過程中簇頭分布不合理和簇內(nèi)結(jié)構(gòu)松散等不合理現(xiàn)象。協(xié)議利用閾值與競爭半徑共同協(xié)作的方式，合理化分簇均衡能耗，平衡網(wǎng)絡(luò)負擔(dān)；在簇間穩(wěn)態(tài)路由轉(zhuǎn)發(fā)階段，通過能量代價函數(shù)，建立能耗代價最低的路由傳輸協(xié)議。

實驗結(jié)果表明，本文算法具有較好的穩(wěn)定性，能夠充分均衡傳輸任務(wù)達到均衡網(wǎng)絡(luò)能耗的效果，同時也顯著延長了網(wǎng)絡(luò)節(jié)點的生存周期。但實際環(huán)境中節(jié)點會有移動和結(jié)構(gòu)不同現(xiàn)象，下一步工作是對其進行改進，使其更適用于實際場合。