余修武李 佩劉 永肖人榕張 可

(1.南華大學資源環(huán)境與安全工程學院,湖南 衡陽421001；2.鈾礦冶放射性控制技術湖南省工程研究中心,湖南 衡陽421001；3.湖南省鈾尾礦庫退役治理工程技術研究中心,湖南 衡陽421001)

無線傳感器網絡(WSNs,wireless sensor networks)節(jié)點能量有限,且不易更換電源,如何合理高效利用能量,延長網絡壽命成為其研究的核心問題之一[1－3]。分層路由采用傳感器節(jié)點網絡分簇和利用簇首進行數據融合的思路,大大減少數據傳輸過程中對節(jié)點的能量消耗,延長網絡的生存時間。近些年,逐漸成為各國學者在路由協議層面的研究熱點。

LEACH算法作為均勻分簇路由算法的典型代表,采用節(jié)點等概率成為簇首的方式平衡網絡節(jié)點的能耗,但易出現“熱區(qū)”現象,造成網絡過早失效。李成法等[4]利用非均勻競選半徑的概念,使靠近基站的簇相對較小,這樣基站附近簇首轉發(fā)數據的能耗相應降低,從而緩解節(jié)點間的能量消耗不均的問題(EEUC)。Sarkar[5]等利用Firefly算法,通過選擇最佳簇頭來最大化網絡的能量效率和節(jié)點的壽命,以此提高網絡性能。潘蕾娜等[6]提出了一種基于信任與能耗均衡的安全分簇路由協議(SCR-TBE),采用模糊評判模型提升網絡的能耗均衡性和可靠性。劉偉等[7]提出了一種基于節(jié)點間相關性的能量有效分簇路由協議(BCCP),利用節(jié)點間位置相關性與節(jié)點剩余能量降低簇內能耗。牛玉剛等[8]提出一種帶有重疊區(qū)域的路由算法(OMU),該算法中簇首只用于簇內數據的接收與融合,由此減少簇首的能量消耗。以上算法雖在一定程度上緩解節(jié)點間能量消耗不均等問題,但其均衡節(jié)點間能耗的能力仍有待提升。其他的一些分層路由還有LEACHimproved[9], EIRNG[10], HCRA[11], GECR[12],CHRA[13]。

本文作者結合了LEACH算法的選舉簇首的方法,對閾值T(n)做出改進。引入節(jié)點與基站距離和節(jié)點能量等因素,使得靠近基站的節(jié)點成為候選簇首的幾率更大,從而靠近基站的候選簇首數更多。對EEUC算法的競爭半徑的公式做出改進,引入繼任簇首能量消耗因子和前任簇首能量消耗因子,提出一種基于動態(tài)競爭半徑的非均勻分簇路由協議(Non-uniform clustering routing protocol based on dynamic competitive radius,NCRP)。根據簇內節(jié)點和簇首節(jié)點的消耗情況,動態(tài)的改變簇的的大小,使得簇首間的能量消耗盡可能的均勻,大幅延長網絡的生存時間。

1 網絡能耗與模型

1.1 網絡模型假定

本文假定WSNs具備以下特征:①節(jié)點隨機地分布在監(jiān)測區(qū)域內,且具有唯一ID。②所有節(jié)點同構且初始能量相同,基站位于監(jiān)測區(qū)域外,能量無限且位置固定。③所有節(jié)點能夠根據接收信息的信號強度值判斷與信息發(fā)送者的近似距離,從而選取自身的發(fā)射功率。④節(jié)點能夠進行數據融合降低數據傳輸量。⑤節(jié)點能夠獲知當前自身剩余能量

1.2 能耗模型

發(fā)送數據能耗主要分為發(fā)送電路和功率放大電路兩部分。功率放大電路能耗主要由發(fā)射者與接收者之間的距離所決定,依據兩者之間距離大小與臨界距離的關系可分別采用自由空間模型和多路徑衰退模型[14],發(fā)送數據能耗如式(1)所示:

式中:d發(fā)射距離；l為發(fā)送的二進制位數；Eelec(nJ/bit)為射頻能耗系數；Efs為采用自由信道模型下的功率放大電路能耗系數；Emp為采用多路徑衰退模型下的功率放大電路能耗系數；dinit為臨界距離,dinit＝87 m。

式(2)為接收數據能耗

本文所使用的仿真參數設置為:Eelec＝50 nJ/bit；Efs＝10(pJ/bit)/m2；Emp＝0.0013(pJ/bit)/m4；dinit＝87 m。

1.3 數據融合模型

通過數據融合技術減少數據傳輸量,從而降低簇首轉發(fā)數據的能量消耗,進而達到降低整個網絡的能耗的目的。由于不同區(qū)域中數據有較大的差異,在本文仿真中不考慮簇間的數據融合。假設簇內的數據融合模型為:簇首接收每個節(jié)點發(fā)送的lbit數據,壓縮為lbit數據；數據融合能耗設定為ED＝5 nJ/bit。

2 NCRP算法

本協議采用LEACH協議的“輪”循環(huán)機制,一“輪”即為一個數據采集周期。每輪可分為非均勻分簇階段、簇間多跳路由構建階段和數據轉發(fā)階段,其中非均勻分簇階段又可分為簇首產生和簇的形成兩部分,在完成節(jié)點的非均勻分簇和簇間多跳路由構建之后再進行數據轉發(fā)。數據轉發(fā)階段可分為簇內單跳傳輸和簇間多跳傳輸兩部分。由于靠近基站的簇首在完成簇內數據收集后還需承擔轉發(fā)較遠簇首數據的任務,導致其能量消耗的速度更快。故本協議對Younis提出的LEACH算法做出改進,使得越靠近基站的節(jié)點成為候選簇首的概率更大。間接使得靠近基站形成更多的簇,從而達到均衡離基站遠近不同的節(jié)點之間的能量消耗,延長整個無線傳感器網絡的生存時間。

2.1 第一輪非均勻分簇

根據LEACH算法提出的概率式,加入節(jié)點與基站距離等因素對產生候選簇首的概率進行調節(jié),即:

式中:r表示當前的回合數,G是r前1/P回合未當選候選簇首的節(jié)點集合,P表示候選簇首數占總節(jié)點數的比例,dmax和dmin分別表示無線傳感器網絡之中節(jié)點與基站的最大距離和最小距離,d(Ni,BS)表示節(jié)點與基站的距離,Et(i)表示節(jié)點Ni初始總能量,Er(i)表示節(jié)點當前所剩能量。采用該概率計算公式,越靠近基站的節(jié)點,成為候選簇首的概率越大,從而使得靠近基站的區(qū)域形成更多的簇,簇的規(guī)模也越小,間接達到非均勻分簇的目的。

在網絡部署完成后,基站以給定的功率向全網廣播一個信號,用以各節(jié)點計算與基站的大致距離。節(jié)點Ni使用式(3)計算其自身成為候選簇首的概率,而后節(jié)點Ni隨機選取一個介于0～1之間的數,若該數小于Tn(i)則Ni當選為候選簇首,否則進入睡眠狀態(tài),待簇的形成階段被喚醒。

定義1定義一繼任簇首能量消耗因子,為

式中:Et(i)表示候選簇首Si初始總能量,Er(i)表示節(jié)點當前所剩能量。

定義2定義一前任簇首能量消耗因子σ,根據上一輪的同一簇的簇內節(jié)點與簇首能量消耗情況對下一輪的簇的規(guī)模進行調節(jié)。σ與上一任簇首的能量消耗Ec(j)成正比關系,與上一輪簇內成員節(jié)點消耗能量的均值成反比關系,為

式中:Ec(j)表示前任簇首Sj在上一輪數據采集周期所消耗的能量,表示上一輪以Sj為簇首的簇內成員節(jié)點消耗能量的平均值。

為了使距離基站較近的簇具有較小規(guī)模,在距離基站較近的區(qū)域應生成更多的簇首。因此,候選簇頭節(jié)點的競爭半徑應正比于它與基站的距離的函數關系.預先給定一Ro用于控制候選簇首的競爭半徑處于一個合理的范圍,以防產生過小或者過大規(guī)模的簇,進而使得簇內數據轉發(fā)能耗趨于合理。綜合考慮候選簇首當前所剩能量和上一輪的簇內能量消耗情況,重新定義候選簇首Ci的競爭半徑Rc(i)計算公式為

定義3

式中:dmax和dmin分別表示無線傳感器網絡之中節(jié)點與基站的最大距離和最小距離,d(Ci,BS)表示候選簇首與基站的距離,c1、c2和c3都是介于0～1之間的常數,且滿足關系c1＋c2＋c3＝1,可知Rc(i)介于0～Ro之間。

由于候選簇首競選成為最終簇首采用的局部競爭的方式,參與競選的候選簇首都保有一個鄰簇首信息表,詳見表1。

表1 候選簇首鄰居節(jié)點信息表

定義4在NCRP簇首競選算法中,候選簇首Ci的鄰居簇首集合NCi為NCi＝{Cj｜Cj是候選簇首,且d(Ci,Cj)

規(guī)則1在競選中,候選簇首Ci必須先比較鄰簇首集合NCi中的節(jié)點和自身的剩余能量的大小,需等待剩余能量比自身大的候選簇首先做出是否成為最終簇首的決定,而后Si才做出決定。

規(guī)則2在競選過程中,若候選簇首Ci的鄰簇首集合NCi中的節(jié)點都退出競選,則簇首Si宣布競選獲勝直接成為最終簇首。

規(guī)則3在競選過程中,若候選簇首Ci宣布其競選獲勝,則在Ci的競爭半徑內的所有候選簇首均要退出競選過程。

候選簇首競選出最終簇首參照參考文獻[4],所有候選簇首以Ro為半徑,采用相同的頻率廣播競選消息COMPETE_HEAD_MSG,該消息包含節(jié)點的ID、節(jié)點的競爭半徑以及節(jié)點當前所剩余的能量,候選簇首根據收到的相鄰候選簇首競選消息的強度判斷兩節(jié)點之間的近似距離,而后節(jié)點依據定義1構建鄰簇首集合NC,并保有鄰簇首信息表。節(jié)點等待鄰簇首集合中所有能量比自身高的節(jié)點先做出是否擔任最終簇首的決策。若Ci發(fā)現鄰簇首集合中的節(jié)點能量都小于自身,則Ci直接成為最終簇首并廣播消息FINAL_HEAD_MSG。若候選簇首Ci收到來自Cj廣播的競選獲勝消息FINAL_HEAD_MSG,首先判斷自身與候選簇首Cj之間的距離是否大于候選簇首Cj的競爭半徑Rc(j)。若大于,節(jié)點Ci將Cj從鄰居簇首集合中移除,繼續(xù)等待鄰簇首集合中比自身能量高的節(jié)點做出是否擔任最終簇首的決策。若小于,則Ci立刻退出競選并廣播消息QUIT_ELECTION_MSG告知它的鄰簇首。若Ci收到來自Cj退出競選的消息,則Ci將Cj從鄰居簇首集合中移除,并繼續(xù)等待。若Ci的鄰簇首集合中所有能量比自身高的節(jié)點都退出了競選,Ci直接成為最終簇首并廣播消息FINAL_HEAD_MSG。

在第一輪最終簇首產生后,之前未成為候選簇首被喚醒,所有競選出來的簇首以Ro為半徑,采用相同的頻率廣播招募簇成員消息RECRUIT_MSG。其他節(jié)點根據收到的消息RECRUIT_MSG的信號強度,選擇信號強度最強的簇,并廣播消息JOIN_CLUSTER_MSG用于通知該簇首。

由于第一輪非均勻分簇比較繁瑣,其中成簇算法產生過多的信息開銷。故之后的非均勻分簇在第一輪分簇形成的基本格局下簡化候選簇首的產生,以降低數據轉發(fā)以外的算法開銷,延長網絡生存時間。

2.2 第二輪及后續(xù)輪次非均勻分簇

在第一輪數據采集周期結束后,在第一輪后的每一輪數據采集周期前設定一個等待時間用于簇首判斷是否需要重新產生候選簇首。若在等待時間過后簇首未收到消息ELECT_MSG,那么將由每個簇首在簇內r前1/P回合未當選簇首成員節(jié)點中,選擇能量最高的個節(jié)點成為下一輪簇首,并廣播FINAL_HEAD_MSG通知簇內節(jié)點。為減少節(jié)點能耗開銷,在數據采集周期內的最后一次數據采集時,選擇簇首所需的節(jié)點信息采用“捎帶”的方式與采集的數據一起傳輸。若簇內不存在r前1/P回合未當選簇首成員節(jié)點,分簇過程參照第一輪分均勻分簇。通過該方式可減小非均勻分簇的能量開銷,延長網絡生存時間。

2.3 簇間多跳路由

NCRP協議采用簇內單跳和簇間多跳的方式進行數據傳輸。每個簇首需要從鄰居簇首中選擇一個作為其中繼節(jié)點,轉發(fā)至基站。由于不同簇之間的數據差異性較大,本協議簇間通信不進行數據融合,只轉發(fā)接收到簇首數據的完整數據包。

NCRP的簇間多跳路由建立采用文獻[14]中的貪婪算法建立最小代價函數來建立簇間多跳路由。簇首Sj運用貪婪算法在其鄰居簇首中選擇中繼節(jié)R Ni,中繼節(jié)點RNi在所有候選節(jié)點中具有最小代價函數,代價函數定義如下:

式中:neighor(si)表示簇首Si的鄰居簇首剩余能量均值,Ecurrent(sj)表示簇首Sj的剩余能量；Nnon－CH(Sj)表示簇首Sj的成員節(jié)點數,Nnon－CH(si)表示簇首Si的鄰居簇首成員節(jié)點數量的均值；dsi－sj表示簇首Si到簇首Sj的距離,dsj－BS表示簇首Sj到基站的距離,d0表示簇首到基站的臨界值；α,β,γ為加權系數,且滿足α＋β＋γ＝1。因此,cost(RNi)＝min{cost(i,j)}。如果簇首Si的中繼節(jié)點是本身,則直接發(fā)送數據到基站；否則,簇首Si發(fā)送數據到中繼節(jié)點RNi,當每個簇首都找到中繼節(jié)點,簇間多跳路由建立。

2.4 數據轉發(fā)階段

數據轉發(fā)包括簇內單跳和簇間多跳兩部分,在簇間多跳路由建立后,簇成員節(jié)點將采集的數據轉發(fā)給簇首,簇首再將收到的數據進行融合后轉發(fā)至其中繼節(jié)點。直至所有簇首將接收到的數據轉發(fā)到對應的中繼節(jié)點,表示數據轉發(fā)完成,數據采集周期結束。算法流程圖如圖1所示。

圖1 流程圖

3 算法分析

性質1NCRP協議的消息復雜度為O(N),N為總節(jié)點數。

證明在非均勻分簇算法中,節(jié)點成為候選簇首的概率為T,共有N×T個節(jié)點成為候選簇首并廣播N×T條COMPETE_HEAD_MSG消息。設共競選出K個最終簇首,廣播K條FINAL_HEAD_MSG消息,(N×T－K)個候選簇首退出競選并廣播(N×T－K)條QUIT_ELECTION_MSG消息。K個簇首廣播K條RECRUIT_MSG消息,(N－K)個節(jié)點廣播(N－K)條JOIN_CLUSTER_MSG消息。所有總的消息開銷為

即消息復雜度為O(N),此處分析的是第一輪分簇的消息復雜度,實際上只有滿足特定條件才會選取該分簇方式,通常情況會選取消息復雜度更低的后續(xù)輪次分簇的方式。盡管消息復雜度分析主要在分簇階段,但在實際應用中還應考慮簇間多跳路由和數據轉發(fā)的信息開銷。

4 實驗結果及分析

本文利用MATLAB R2017a對NCRP算法進行模擬,與LEACH和EEUC進行對比。400個節(jié)點被隨機分布在200 m×200 m的正方形區(qū)域內,為了更好與LEACH和EEUC做對比,本文選取與EEUC相同的參數設置,詳見表2。

表2 模擬參數表

為了評價NCRP算法的性能,分別從簇首的分布、簇首消耗能量的方差、死亡節(jié)點的分布和網絡的生存時間等方面與LEACH和EEUC算法進行對比分析。

4.1 簇首的分布

如圖2(a)、圖2(c)可以看出,由于LEACH和EEUC都是采用閾值的方式產生簇首,節(jié)點的成為簇首的概率都相等故產生的簇首隨機分布在網絡中。反觀圖2(b),由于NCRP算法引入節(jié)點與基站的距離因素和節(jié)點能量對閾值公式進行改進,靠近基站的節(jié)點有更大的幾率成為簇首。進而使得更多靠近基站的節(jié)點成為簇首,擔負起轉發(fā)外圍簇首數據的任務。

圖2 簇首分布圖

4.2 簇首消耗能量的方差

圖3為三種算法的簇首消耗能量的方差。在仿真實驗中,隨機抽取三種算法未出現死亡節(jié)點的前的10輪,用簇首消耗能量的方差衡量三種算法的簇首間能量消耗的均衡情況。發(fā)現三種算法中LEACH算法的方差最大,說明LEACH并沒用采取相應的方法對簇首間的能量消耗均衡。EEUC和NCRP算法相比于LEACH算法方差都小很多,說明EEUC和NCRP算法在簇首間能量消耗均衡方面遠優(yōu)于LEACH算法。NCRP算法方差略低于EEUC,說明NCRP在處理簇首間能耗差異方面優(yōu)于EEUC算法。

圖3 簇首消耗能量的方差

4.3 死亡節(jié)點的分布

節(jié)點間能量消耗不均是致使無線傳感器網絡過早失效的原因,圖4為三種算法在50%節(jié)點死亡時的死亡節(jié)點分布圖(×為死亡節(jié)點)。

從圖4(a)可以看出,LEACH算法遠離基站的死亡節(jié)點數量大于靠近基站的死亡節(jié)點數量,這說明LEACH算法節(jié)點間能耗均衡能力較差。反觀圖4(b)和圖4(c),死亡節(jié)點分布較為均勻。說明NCRP和EEUC算法在均衡節(jié)點能耗方面遠優(yōu)于LEACH算法,更有利于延長網絡的生存時間。

圖4 死亡節(jié)點分布圖

4.4 網絡生存時間

圖5為三種算法的網絡生存時間,LEACH算法第一個死亡節(jié)點出現在第268回合,EEUC算法是第742回合,而NCRP算法第一個死亡節(jié)點出現在第986回合,性能較LEACH提升了189.93%,較EEUC提升了32.88%。LEACH算法節(jié)點死亡50%出現在第423回合,EEUC是在第762回合,而NCRP算法節(jié)點死亡50%出現在第1023回合,性能較LEACH提升了88.42%,較EEUC提升了34.25%。這說明NCRP算法在競爭半徑的公式引入距離和能量等因素,使得競爭半徑RC更加趨于合理,有效地均衡了網絡中節(jié)點的能耗,延長了網絡的壽命。

圖5 網絡生存時間

5 結論

本文提出一種動態(tài)競爭半徑的非均勻分簇路由協議,在第一輪選舉候選簇首利用改進過的閾值公式可以使靠近基站區(qū)域產生更多的簇首用于轉發(fā)其他簇首的數據,有效均衡了整個傳感器網絡能量消耗。在NCRP算法中,在競爭半徑的計算中引入繼任能量消耗因子和前任能量消耗因子,使得競爭半徑更加合理。仿真實驗表明,NCRP能夠有效均衡節(jié)點間能耗,延長整個網絡的存活時間。