深井無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議*

余修武,劉 琴,劉 永,李向陽,梁北孔(.南華大學(xué)環(huán)境與安全工程學(xué)院,湖南 衡陽 4200;2.金屬礦山安全與健康國家重點實驗室,安徽 馬鞍山 243000;3.湖南省鈾尾礦庫退役治理技術(shù)工程技術(shù)研究中心,湖南 衡陽 4200)

為保證國民經(jīng)濟的持續(xù)發(fā)展,需要對礦井進行深部開采。然而隨著井下開采工作的推進,其環(huán)境也愈加惡劣,存在高溫、高濕、通風(fēng)性差等問題,因此在井下建立完善的的安全監(jiān)控監(jiān)測系統(tǒng)是十分必要的。有線安全監(jiān)控系統(tǒng)并不能很好地適應(yīng)此復(fù)雜環(huán)境,一是系統(tǒng)易腐蝕,設(shè)備遭到破壞,會導(dǎo)致整個系統(tǒng)癱瘓;二是需要鋪設(shè)較多的電纜,使得整個系統(tǒng)的成本偏高。

無線傳感器網(wǎng)絡(luò)[1-3]WSNs(Wireless Sensor Networks)是一種自組織網(wǎng)絡(luò),能實時監(jiān)控對象,且具有強抗毀性,靈活易于擴展,可以部署在復(fù)雜惡劣甚至是危險的環(huán)境中,因此將WSNs應(yīng)用于深井安全監(jiān)控系統(tǒng)中[4-5],可以保障網(wǎng)絡(luò)通信的有效性與可靠性。無線傳感器節(jié)點一旦部署就無法充電或進行電源更換,如何有效均衡能耗,延長網(wǎng)絡(luò)壽命就是WSNs路由協(xié)議設(shè)計的關(guān)鍵[6-7]。

基于分簇的層次式路由方式能有效減少節(jié)點對Sink節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù),減少網(wǎng)絡(luò)冗余信息,降低能耗,延長網(wǎng)絡(luò)生存周期。LEACH算法[8-9]是最早采用均勻分簇的路由算法,各個節(jié)點等概隨機擔(dān)任簇首,但離Sink節(jié)點近的簇首能量消耗較快,易造成能量空洞。PEGASIS協(xié)議[10]是對LEACH算法的改進,減小節(jié)點間的平均通信距離來降低網(wǎng)絡(luò)通信能耗,然而卻不能對低能量的節(jié)點進行篩選。EEUC算法[11]引入了非均勻競選半徑的概念,使靠近Sink節(jié)點的簇規(guī)模相對較小,這樣Sink節(jié)點附近簇首轉(zhuǎn)發(fā)數(shù)據(jù)的能耗相應(yīng)降低,該算法在一定程度上可以解決簇首能耗不均導(dǎo)致的“熱區(qū)”問題。李鑒等[12]提出了一種能量均衡的非均勻分簇的路由算法(EBUC-M),根據(jù)新的閾值公式來選擇簇首,以此均衡簇首間能耗。

根據(jù)深井WSNs路由的特點以及應(yīng)用需求,提出一種無線傳感器網(wǎng)絡(luò)非均勻分簇的路由協(xié)議UCRP(Uneven Clustering Routing Protocol)來均衡簇首間的能耗,并保證數(shù)據(jù)傳輸?shù)挠行耘c可靠性,延長網(wǎng)絡(luò)生存周期。

1 網(wǎng)絡(luò)與能耗模型

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

根據(jù)深井巷道線型特征,進行WSNs布設(shè)時采用人工部署,節(jié)點一旦部署就不再移動。假設(shè)有N個無線傳感器節(jié)點均勻布設(shè)在長為L,寬為M的矩形監(jiān)測區(qū)域內(nèi)(L?M),根據(jù)文獻[13],網(wǎng)絡(luò)遵從以下原則:①Sink節(jié)點位于巷道的出口或入口處,其能量和計算能力不受限制且始終處于蘇醒狀態(tài);②節(jié)點布署在巷道內(nèi),且都是同構(gòu)的,能感知自己的剩余能量,并且每個節(jié)點具有唯一ID;③可根據(jù)距離來調(diào)整安裝好的節(jié)點的發(fā)射和接收功率。

1.2 無線通信模型

能量消耗[14]是設(shè)計WSNs路由算法時的重要部分,無線通信模型如圖1所示。

圖1 無線通信模型

無線信號能量消耗模型由發(fā)送電路能耗和發(fā)送放大電路能耗兩部分組成。當(dāng)節(jié)點發(fā)送l bit數(shù)據(jù)時,節(jié)點接收1 bit信息所需能耗為Ee,發(fā)送放大電路能耗與發(fā)送距離d有關(guān),在自由空間中n通常取為2,在多徑衰落區(qū)域n通常取4。發(fā)送放大模塊消耗的能量系數(shù)為εm,節(jié)點每次發(fā)送數(shù)據(jù)能耗ETx和接收數(shù)據(jù)能耗ERx分別如式(1)所示:

ETx=lEe+lεmdn
ERx=lEe

(1)

信號在深井巷道中多徑效應(yīng)尤為明顯,應(yīng)采用多徑衰減信號模型,即n應(yīng)取4。

2 UCRP協(xié)議

整個無線網(wǎng)絡(luò)的能量消耗主要在集中在信息轉(zhuǎn)發(fā)階段,均衡此階段的能耗就尤為重要。UCRP協(xié)議按照周期采集數(shù)據(jù)(即輪循環(huán)機制),每一輪分為2個階段:①非均勻分簇階段。傳感器節(jié)點考慮自身到Sink節(jié)點的距離并計算出距離因子,保證數(shù)據(jù)傳輸路徑的最優(yōu)性,同時考慮節(jié)點的剩余能量因子,使剩余能量高的候選簇首擔(dān)任最終簇首;②數(shù)據(jù)轉(zhuǎn)發(fā)階段。分為簇內(nèi)單跳和簇間多跳通信兩部分,當(dāng)簇首與Sink節(jié)點距離小于一定范圍時,就可以直接將數(shù)據(jù)發(fā)送至Sink節(jié)點。

首先介紹與UCRP協(xié)議相關(guān)的定義。

定義1距離因子。距離因子df表示節(jié)點當(dāng)前位置與Sink節(jié)點的位置關(guān)系,0≤df≤1。

定義2剩余能量因子。剩余能量因子Er(i)表示節(jié)點i當(dāng)前剩余能量與簇內(nèi)平均剩余能量的關(guān)系,0≤Er(i)≤1。

定義3全網(wǎng)平均剩余能量估計。對分布式路由算法而言統(tǒng)計全網(wǎng)的平均剩余能量是非常困難的,因此只能對其進行一個粗略的估計,如式(2)所示:

(2)

式中:N表示節(jié)點數(shù),E0為全網(wǎng)初始總能量E0=0.5N,r為仿真輪數(shù),Erd為每一輪消耗的能量。

2.1 非均勻分簇階段

非均勻分簇階段包括簇首競選、非均勻競爭半徑和簇的形成。

①簇首競選

(3)

式中:ω為調(diào)節(jié)參數(shù),ω∈[0,1],E(i)表示節(jié)點i當(dāng)前剩余能量。該權(quán)值W綜合考慮了節(jié)點剩余能量以及距離因子。節(jié)點的剩余能量越高,權(quán)值也越大;距離因子越大,就越容易成為簇首。

②非均勻競爭半徑

簇首節(jié)點越靠近Sink節(jié)點,需要承擔(dān)轉(zhuǎn)發(fā)數(shù)據(jù)的任務(wù)越重,這樣會引起簇首節(jié)點過早死亡而導(dǎo)致的“熱區(qū)”問題。為了避免這種情況的發(fā)生,UCRP協(xié)議設(shè)計時,使距離Sink節(jié)點近的簇規(guī)模減小,簇數(shù)增多,這樣可以由多個簇首分擔(dān)路由數(shù)據(jù)至Sink節(jié)點,為此需要為簇首節(jié)點設(shè)定競爭半徑Rc。假設(shè)最大的競爭半徑為Rmax,這里先給出鄰居節(jié)點和鄰居節(jié)點數(shù)的定義。

定義4節(jié)點si的最大競爭半徑Rmax內(nèi)的所有其他節(jié)點稱為鄰居節(jié)點。si的鄰居節(jié)點集合如式(4)所示:

si.Vic={sj|d(si,sj)

(4)

鄰居節(jié)點數(shù)為Num=|si.Vic|。

簇首根據(jù)距離因子、剩余能量因子和鄰居節(jié)點數(shù)計算其競爭半徑Rc,如式(5)所示:

(5)

式中:c1、c2、c3為調(diào)節(jié)參數(shù),用來調(diào)節(jié)距離、能量和節(jié)點密度對競爭半徑的影響程度,且c1+c2+c3=1。由于簇首是各個簇中剩余能量最大的節(jié)點,故調(diào)節(jié)參數(shù)c2取值可以較小。c1、c3的取值則需要綜合考慮基站的位置和網(wǎng)絡(luò)的范圍大小,仿真中c1和c3取值相等。

③簇的形成

簇首確定后,在其競爭半徑內(nèi)廣播信息,等待成員節(jié)點的加入。普通節(jié)點接收信息強度并確定自身與簇首的近似距離,選擇信息經(jīng)過最短距離的簇首加入。

簇的形成過程也是為了均衡能耗,讓更多的節(jié)點加入到剩余能量因子較大的簇首中,同時還需考慮信息的傳輸距離。圖2給出UCRP的路由協(xié)議示意圖,其中大小不等的圓表示簇首節(jié)點的非均勻競爭半徑,帶箭頭的線表示簇首間的多跳數(shù)據(jù)轉(zhuǎn)發(fā)。

圖2 UCRP的路由協(xié)議

2.2 數(shù)據(jù)轉(zhuǎn)發(fā)階段

UCRP協(xié)議采用單跳與多跳的相結(jié)合的路由方式轉(zhuǎn)發(fā)數(shù)據(jù)。簇首先采集簇內(nèi)成員的信息并且進行數(shù)據(jù)融合,然后進行數(shù)據(jù)轉(zhuǎn)發(fā),選擇距離優(yōu)化的路徑進行發(fā)送。

簇內(nèi)通信采取單跳路由方式,成員節(jié)點直接將數(shù)據(jù)發(fā)送至所屬簇的簇首,減少路徑能量損耗;簇間通信采用多跳路由方式,一是可以減少鏈路總能耗,二是可以有效避免低能量節(jié)點成為簇首,過早耗盡網(wǎng)絡(luò)壽命;當(dāng)簇首與Sink節(jié)點距離小于一定范圍時,就可以直接將數(shù)據(jù)傳輸至Sink節(jié)點。

非均勻分簇可以有效均衡節(jié)點能耗,平衡網(wǎng)絡(luò)負(fù)載。根據(jù)距離因子、剩余能量因子和節(jié)點密度成簇,使剩余能量較高的節(jié)點成為簇首,同時使得簇首通信代價最小化。

2.3 算法分析

①在UCRP協(xié)議中,網(wǎng)絡(luò)廣播信息量的復(fù)雜度為O(N)。

證明:在非分均勻分簇階段,共有RT個候選簇首,因此需要廣播了RT條Compete_Msg,競選成功的候選簇首發(fā)出成功信號,設(shè)有n個簇首,那么需要廣播n條Head_Msg和n條Ch_Adv_Msg,而其余簇成員節(jié)點則廣播R-n條Join_Msg;在簇間路由建立時,n個簇首需要廣播n條Route_Msg,因此網(wǎng)絡(luò)的總信息開銷如式(6)所示:

RT+2n+R-n+n=(T+1)R+2n

(6)

所以,UCRP協(xié)議信息量的復(fù)雜度為O(N)。

②Rmax、c1、c2、c3對路由算法的影響。

Rmax的取值影響生成簇的數(shù)量。Rmax越大,簇半徑也隨之增大,則生成簇的數(shù)目減少。c1、c2、c3的取值體現(xiàn)了距離、能量和節(jié)點密度對簇半徑的影響,當(dāng)三者變化時,簇半徑也要明顯變化。

3 仿真實驗與參數(shù)分析

3.1 仿真實驗

為了驗證UCRP協(xié)議對深井巷道的監(jiān)測應(yīng)用效果,假定在一個L×M為1 000 m×10 m的巷道內(nèi),采用MATLAB進行仿真測試,與LEACH、EEUC以及EBUC-M算法與UCRP算法進行比較,仿真參數(shù)設(shè)置如表1所示。

圖3對比了4種協(xié)議的網(wǎng)絡(luò)生存時間變化的情況。從圖3可以看出,UCRP相比于其他3中協(xié)議有較長的網(wǎng)絡(luò)生存時間。而UCRP與EBUC-M的網(wǎng)絡(luò)生存時間相差不大,主要是這兩種算法都構(gòu)造了新的簇首選舉公式來選取簇首,降低了簇首轉(zhuǎn)發(fā)數(shù)據(jù)能耗,而UCRP的網(wǎng)絡(luò)生存時間略優(yōu)于EBUC-M是由于UCRP協(xié)議選取簇首時不僅對節(jié)點剩余能量進行考慮,還加入了距離因子,保證了簇首選擇的最優(yōu)性。

表1 仿真參數(shù)

圖3 死亡節(jié)點與生存周期關(guān)系

圖4 節(jié)點平均剩余能量與生存周期關(guān)系

3.2 參數(shù)分析

UCRP協(xié)議中所生成簇的數(shù)目和規(guī)模由Rmax和c1、c2、c3共同決定。Rmax決定了網(wǎng)絡(luò)中簇的最大規(guī)模。為確定Rmax對算法的影響,令Rmax從70按步長5增加到110時,第1個節(jié)點死亡時間(輪數(shù))的變化,如圖5所示。

圖5 第1個節(jié)點死亡時間隨Rmax變化圖

從圖5可知,當(dāng)Rmax=90 m時,第1個節(jié)點死亡時間(輪數(shù))值最大。由于在深井下信號多徑效應(yīng)明顯,為了達到較好數(shù)據(jù)傳輸,保證數(shù)據(jù)可靠性與實時性,需要合理布設(shè)傳感器節(jié)點。當(dāng)布設(shè)節(jié)點數(shù)較少時,可能會導(dǎo)致得到的數(shù)據(jù)不可靠;布設(shè)節(jié)點過多時,會增加傳感器設(shè)備的成本,也會產(chǎn)生較多冗余數(shù)據(jù),造成網(wǎng)絡(luò)帶寬擁堵,使得距離Sink節(jié)點近的簇首過早死亡,降低網(wǎng)絡(luò)生存周期。

調(diào)節(jié)參數(shù)c1、c2、c3的取值決定了簇規(guī)模大小的非均勻程度,綜合考慮3方面因素(距離、能量和節(jié)點密度)的權(quán)重。實驗中c1、c2、c3的取值,觀察第1個節(jié)點死亡時間(輪數(shù))隨之變化的情況,結(jié)果如表2所示。

表2 第1個節(jié)點死亡時間隨參數(shù)c1,c2,c3變化的趨勢

從表2可知,當(dāng)c1=0.4、c2=0.2和c3=0.4時,第1個死亡節(jié)點死亡時間(輪數(shù))最大,因為此時網(wǎng)絡(luò)分簇的非均勻程度最優(yōu),節(jié)點間的能耗較為平衡。

4 結(jié)束語

根據(jù)深井巷道線型拓?fù)浣Y(jié)構(gòu),提出了一種非均勻分簇路由協(xié)議,利用一個權(quán)值公式來進行簇首競選,權(quán)值越大越易成為簇首,有效均衡了網(wǎng)絡(luò)節(jié)點能耗;數(shù)據(jù)傳輸采用單跳與多跳結(jié)合的路由方式,不僅減少了鏈路能耗,還能平衡負(fù)載。仿真實驗表明,UCRP協(xié)議具有較好的網(wǎng)絡(luò)魯棒性,能有效降低節(jié)點能量開銷,均衡網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)壽命。

雖然本算法在仿真實驗環(huán)境下有較好的性能,但實際環(huán)境中存在異構(gòu)網(wǎng)絡(luò)和移動的節(jié)點,為了改善網(wǎng)絡(luò)能耗,需要根據(jù)深井巷道的實際情況,對算法做出合理改進。