基于最小生成樹的非均勻分簇路由協(xié)議*

廖福保,張文梅

(1.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院計算機系,廣州 510507;2.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院機電系,廣州 510507)

基于最小生成樹的非均勻分簇路由協(xié)議*

廖福保1,張文梅2*

(1.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院計算機系,廣州 510507;2.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院機電系,廣州 510507)

針對無線傳感器網(wǎng)絡(luò)中利用分簇技術(shù),簇首到Sink節(jié)點通信采用多跳路由方式容易引起“能量空洞”的問題,提出了基于最小生成樹的非均勻分簇路由協(xié)議。該協(xié)議在簇首選舉階段,以節(jié)點剩余能量、節(jié)點度、節(jié)點能量消耗速度為權(quán)重計算簇首競爭等待時間,選用簇首競爭等待時間小的節(jié)點為簇首,以均衡能量;簇形成后,以剩余能量、簇間的距離和能量消耗為參數(shù)構(gòu)建基于最小生成樹的最優(yōu)傳輸路徑通過多跳方式將數(shù)據(jù)發(fā)送到Sink節(jié)點。仿真結(jié)果表明,該路由協(xié)議能有效均衡能耗,延長網(wǎng)絡(luò)生命周期,延緩“能量空洞”的形成。

無線傳感器網(wǎng)絡(luò);非均勻分簇;能量均衡;最小生成樹

無線傳感器是由大量的傳感器節(jié)點和一個或多個Sink節(jié)點組成,傳感器節(jié)點采集數(shù)據(jù)上傳到Sink節(jié)點。這些傳感器節(jié)點采用電池供電,能量有限且不能被補充。因此如何降低傳感器能耗,在網(wǎng)絡(luò)層提供節(jié)能算法是無線傳感器網(wǎng)絡(luò)研究的熱點[1-3]。

有研究表明先將傳感器進行分簇,通過簇首多跳方式上傳數(shù)據(jù)到Sink節(jié)點有利于節(jié)省能量[4-5]。然而采用多跳方式,離Sink節(jié)點越近的傳感器,由于要轉(zhuǎn)發(fā)其他簇首數(shù)據(jù),其能量消耗越快,從而形成“能量空洞”,這時其他傳感器節(jié)點將不能上傳數(shù)據(jù)到Sink節(jié)點,造成能量的浪費和網(wǎng)絡(luò)生命周期的縮短。

為解決“能量空洞”問題,很多研究者提出了不同的簇首選舉和多跳路由選擇方法。文獻[6]提出的EEUC算法、文獻[7]提出的DEBUC算法采用非均勻分簇,靠近Sink節(jié)點的簇小、簇內(nèi)節(jié)點少,可以減少簇內(nèi)能量消耗而節(jié)省能量用于轉(zhuǎn)發(fā)數(shù)據(jù),從而能有效均衡能量消耗,延長網(wǎng)絡(luò)生命周期,但兩個算法都是根據(jù)概率和門限值來選舉簇首,并不能確保選舉出來的簇首最優(yōu)。文獻[8]提出了EBUCA算法,也采用非均勻分簇,該算法根據(jù)剩余能量和節(jié)點密度來設(shè)置簇首選舉的閾值,并沒有考慮能量消耗速度問題。

另外,在多跳路由的選擇方面,文獻[9-10]采用最小生成樹算法來進行路徑選擇,但在構(gòu)造最小生成樹時只考慮了簇首的剩余能量或到Sink節(jié)點的距離。

基于以上存在的問題,本文提出了基于最小生成樹的非均勻分簇路由協(xié)議。協(xié)議在簇首選舉時以節(jié)點的剩余能量、節(jié)點度、節(jié)點能量消耗速度等參數(shù)構(gòu)建節(jié)點的簇首競爭時間,競爭時間短的節(jié)點獲得簇首的機會大。簇首選舉完成后,以簇首剩余能量、簇間的距離、簇首能量消耗為參數(shù)構(gòu)造出以Sink節(jié)點為根節(jié)點的最小生成樹。數(shù)據(jù)傳輸時,簇內(nèi)數(shù)據(jù)傳輸采用單跳方式,簇首到Sink節(jié)點的通信通過最小生成樹組織的路由采用多跳方式。該算法能較好地均衡各個節(jié)點的能耗,從而延長傳感器網(wǎng)絡(luò)生命周期。

1 相關(guān)模型

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

本文假定各個傳感器節(jié)點隨機分布于監(jiān)控區(qū)域,且具有如下特征:①節(jié)點部署后不再移動且能量不能補充,Sink節(jié)點位置固定且唯一,能量也不受限;②節(jié)點能夠根據(jù)接收的信號強度計算發(fā)出信號節(jié)點到本節(jié)點的距離,且可以自由調(diào)整發(fā)射功率;③傳感器節(jié)點初始能量相同,具有相同的通信和數(shù)據(jù)處理能量;④傳感器節(jié)點都在Sink節(jié)點的通信范圍之內(nèi);⑤每個節(jié)點都有唯一的標(biāo)識ID。

1.2 能耗模型

由于無線傳感器網(wǎng)絡(luò)中節(jié)點通信所耗的能量遠大于其他的能耗[11],本文采用與文獻[12]一樣的無線通信模型,節(jié)點發(fā)送k比特數(shù)據(jù)所消耗的能量如下:

(1)

ERx(k)=k×Eelec

(2)

2 基于最小生成樹的非均勻分簇路由協(xié)議

與LEACH協(xié)議類似,本文協(xié)議也采用“輪”方式,每輪分為簇建立階段和數(shù)據(jù)傳輸階段。在簇的建立階段,以剩余能量、節(jié)點度、節(jié)點能量消耗速度等因素計算簇首競爭等待時間,采用時序的方式選擇簇首。在數(shù)據(jù)傳輸階段,以簇首剩余能量、簇首能量消耗和簇間距離為權(quán)重構(gòu)建基于最小生成樹的最優(yōu)傳輸路徑。

2.1 簇的形成

把在節(jié)點半徑Ri范圍內(nèi)的所有其他節(jié)點當(dāng)作該節(jié)點的鄰居節(jié)點,Ri通過式(3)計算得到。

(3)

每個節(jié)點保存一個鄰居節(jié)點表以存儲鄰居節(jié)點的相關(guān)信息,如表1所示。

表1 節(jié)點的鄰居表內(nèi)容

開始階段,Sink節(jié)點先全網(wǎng)廣播PAR_MSG消息,每個傳感器節(jié)點根據(jù)接收到的消息強度計算出該節(jié)點到Sink節(jié)點的距離d(i,DS),然后根據(jù)式(3)計算出節(jié)點半徑R。

每輪開始時,進入鄰居節(jié)點信息獲取時段(事先規(guī)定鄰居節(jié)點信息獲取的時長為T1),每個傳感器節(jié)點以半徑Ri廣播消息Comp_MSG,該消息包括有節(jié)點ID和剩余能量e、節(jié)點能耗ec。

當(dāng)T1時間到,鄰居節(jié)點表更新完畢,每個節(jié)點根據(jù)鄰居節(jié)點表計算出鄰居節(jié)點平均剩余能量Eavg、鄰居節(jié)點度(鄰居節(jié)點個數(shù))m、平均能耗ECavg、能耗速度Vec。節(jié)點能耗、平均剩余能量、平均能耗和能耗速度的計算公式如式(4)～式(7)所示。

ec=er-1-er

(4)

(5)

(6)

Vec=eci/ECavg

(7)

式(4)中:er為第r輪節(jié)點剩余能量,er-1為第r-1輪節(jié)點的剩余能量。由式(7)可知能耗速度為該輪中節(jié)點消耗的能量與平均消耗的能量之比。

然后進入簇首選舉時間,每個節(jié)點根據(jù)式(8)計算自己的簇首競爭時間t。

(8)

式中:α為一個在(0,1)之間的隨機實數(shù)值,表示剩余能量和能耗速度的權(quán)重;T2為事先規(guī)定的簇首競爭時間。如果能耗速度過快,簇首會過早死亡,也會造成能量空洞,因此本文引入能耗速度,并作為簇首競爭時間的主要參數(shù)。

從式(8)可以看出,簇首競爭時間t由Eavg/ei和Vec決定。Eavg/ei表明節(jié)點相對于鄰居節(jié)點的剩余能量越高,被選中作為簇首的機會越大,保證有更多的能量用于簇間多跳數(shù)據(jù)傳輸。Vec作為簇首競爭時間的主要參數(shù),如果第r輪能耗速度Vec小,下一輪該節(jié)點簇首競爭時間t小,被選中作為簇首的機會就大;如果第r輪能耗速度Vec大,下一輪該節(jié)點簇首競爭時間t大,被選中作為簇首的機會就小,從而可以避免能耗速度快的節(jié)點成為簇首造成能量空洞現(xiàn)象。

在本協(xié)議中,如果一個節(jié)點在t時刻到來前沒有收到鄰居節(jié)點的Suc_MSG消息,則該節(jié)點在節(jié)點半徑Ri范圍內(nèi)廣播Suc_MSG消息,宣布簇首選舉成功。如果一個節(jié)點在t時刻到來前收到了鄰居節(jié)點的Suc_MSG消息,則廣播競選失敗的消息Fai_MSG,放棄簇首競選,進入休眠狀態(tài)。

當(dāng)T2時間到,簇首選舉完成,進入普通節(jié)點加入簇的時間,非簇首節(jié)點選擇鄰居節(jié)點中第1個被選簇首發(fā)出JOIN_MSG消息,申請加入到該簇,并在鄰居節(jié)點表中刪除其他節(jié)點。對于簇首節(jié)點,接收來自鄰居節(jié)點的JOIN_MSG消息,將不在本簇內(nèi)的鄰居節(jié)點從鄰居節(jié)點表中刪除,至此該輪的分簇過程完成。

圖1 簇首選舉流程圖

本文在非均勻分簇的基礎(chǔ)上進行簇首選擇,網(wǎng)絡(luò)中所有節(jié)點都參與簇首競爭,采用時序的方式選擇簇首。簇首選舉流程如圖1所示。

具體描述如下:

①Sink節(jié)點先全網(wǎng)廣播PAR_MSG消息,網(wǎng)絡(luò)中各節(jié)點收到PAR_MSG消息,根據(jù)式(3)計算出節(jié)點半徑Ri。

②在T1時段內(nèi),各節(jié)點以半徑Ri廣播消息Comp_MSG,該消息包括有節(jié)點ID和剩余能量e、節(jié)點能耗ec,每個節(jié)點根據(jù)收到的Comp_MSG消息更新鄰居表。

③T1時間到,各節(jié)點根據(jù)鄰居表計算平均剩余能量Eavg、鄰居節(jié)點度(鄰居節(jié)點個數(shù))m、平均能耗ECavg、能耗速度Vec,最后計算出簇首競爭時間ti。

④進入T2時間段,對于節(jié)點i有:

⑤if當(dāng)前時間

⑥if收到鄰居節(jié)點j的簇首成功消息Suc_CLU

⑦節(jié)點i廣播競選失敗的信息Fai_CLU

⑧節(jié)點i進入休眠狀態(tài)

⑨end if

⑩end if

本協(xié)議分簇算法將整個網(wǎng)絡(luò)劃分為非均勻的多個簇,靠近Sink節(jié)點的簇半徑更小,有利于均衡能耗;簇首競爭時間考慮了剩余能量、節(jié)點度、節(jié)點能量消耗速度等因素,能夠保證選舉出來的簇首綜合性能最優(yōu)。

2.2 簇間路由樹構(gòu)造

分簇完成后,為保證簇首間的跳轉(zhuǎn),各簇首以2Ri為半徑廣播簇首消息CLU_MSG(ID,e,ec),并收集其他簇首廣播的消息,計算簇首間距離,修改路由表信息。

簇間路由以Sink節(jié)點為樹根,采用最小生成樹方式來組織簇首到Sink節(jié)點的通信,通過多跳方式將數(shù)據(jù)傳輸?shù)絊ink節(jié)點。開始時將每個簇首抽象為點,把相鄰簇首用邊連接起來,把無線傳感器網(wǎng)絡(luò)構(gòu)造為一個帶權(quán)的連通圖G=(V,E),其中V是點集(包括所有簇首,不含Sink節(jié)點),E為邊集。

點i到點j的邊的權(quán)值wij,綜合考慮兩者間的距離、簇首j剩余能量和簇首j的能量消耗,其計算公式如下:

(9)

式中:wij為簇首i到簇首j的邊的權(quán)值,dij為簇首i到簇首j之間的距離,ej為簇首j剩余能量,ecj為簇首j的能耗,ρ為可變參數(shù)。為保證數(shù)據(jù)能逐步往Sink節(jié)點傳遞,簇首j到Sink節(jié)點的距離大于或等于簇首i到Sink節(jié)點的距離,則wij的值為無窮大。從式(9)中可以看出,wij值由dij、ej和ecj決定,簇首j剩余能量低、距離遠、能耗又大時,wij的取值越大,則簇首被選為數(shù)據(jù)轉(zhuǎn)發(fā)的概率越小,從而該簇首可以節(jié)省能量,數(shù)據(jù)通信時又可以節(jié)省通信能耗,延長生命周期,達到整個網(wǎng)絡(luò)能量均衡。

每輪簇間路由采用最小生成樹方式來構(gòu)建,設(shè)T為最小生成樹邊的集合,具體描述如下:

①將到Sink節(jié)點距離d(i,DS)≤d1的簇首添加到集合U中,該部分簇首的匯聚數(shù)據(jù)直接傳遞給Sink節(jié)點,設(shè)置這部分簇首到Sink節(jié)點的邊的權(quán)值為0并添加到集合T中。

②計算G=(V,E)中所有邊的權(quán)值。

③while(U!=V)

④從u∈U,v∈V-U的邊中選取權(quán)值wuv最小的邊,將其加入到T,將簇首v加入到U

⑤endwhile

最后的生成樹MT=(U,T)即為連通圖G的最小生成樹。各簇首根據(jù)最小生成樹MT,調(diào)整發(fā)射功率,調(diào)整為能夠到達其最小生成樹的所有一跳鄰居,從而節(jié)省能耗。

2.3 數(shù)據(jù)通信

簇首選舉和簇首路由樹構(gòu)建完成后,進入數(shù)據(jù)通信階段。簇內(nèi)節(jié)點采用TDMA方式將數(shù)據(jù)傳輸?shù)酱厥?然后簇首將數(shù)據(jù)融合,最后根據(jù)構(gòu)建的最小生成樹,以多跳通信方式將數(shù)據(jù)傳輸?shù)絊ink節(jié)點。

2.4 算法分析

假設(shè)在無線傳感器網(wǎng)絡(luò)中的節(jié)點數(shù)共有N個,生成的簇首節(jié)點有H個,下面分析本文算法的消息復(fù)雜度。

在簇的形成算法中,Sink節(jié)點廣播PAR_MSG信息,共1條;每個節(jié)點以半徑R廣播消息Comp_MSG,共N條;競選成功的節(jié)點發(fā)送Suc_CLU消息共H條,競選失敗的節(jié)點發(fā)送Fai_CLU消息共N-H條;競選失敗的節(jié)點發(fā)送JOIN_MSG消息加入到最近的簇首,共N-H條。

簇間路由樹構(gòu)造算法中,簇首以2Ri為半徑廣播簇首消息CLU_MSG共H條。因此每輪網(wǎng)絡(luò)中消息總開銷為:

1+N+H+(N-H)+(N-H)+H=3N+1

即消息復(fù)雜度為O(N),說明本文算法的消息開銷較小,能量高效。

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

本文協(xié)議選用OPNET進行仿真實驗,與EEUC協(xié)議、CSMST協(xié)議進行比較。在實驗中預(yù)先設(shè)定傳感器節(jié)點數(shù)量100個,傳感器節(jié)點隨機分布于100 m×100 m的矩形區(qū)域中,Sink節(jié)點位于中央位置。各仿真參數(shù):Eelec=50 nJ/bit,εmp=0.001 3 pJ/(bit·m4),εfs=10 pJ/(bit·m2),初始能量e=0.5 J,數(shù)據(jù)包大小600 bit。為了比較,本實驗取c=0.5,α=0.4,d1=10 m,而ρ=0.5,簇首數(shù)據(jù)融合的能耗忽略不計。

3.1 網(wǎng)絡(luò)生存周期

圖2為網(wǎng)絡(luò)中總存活節(jié)點數(shù)隨輪數(shù)的變化情況,從圖2可以看出出現(xiàn)首次死亡節(jié)點的輪數(shù)本文協(xié)議比EEUC和CSMST都滯后;從整個網(wǎng)絡(luò)的存活時間看,本文協(xié)議存活了1 620輪左右,相比EEUC協(xié)議提高了約450輪、比CSMST算法提高了約200輪。本文協(xié)議在選舉簇首不僅考慮剩余能量,還考慮節(jié)點能量消耗速度等因素,根據(jù)時序方式選擇簇首;在數(shù)據(jù)傳輸階段,EEUC考慮剩余能量進行多跳傳輸,CSMST算法考慮剩余能量和節(jié)點傳輸能耗構(gòu)造最小生成樹多跳傳輸,而本文算法綜合考慮中繼簇首剩余能量、簇間距離和能量消耗等因素構(gòu)造最小生成樹尋求最優(yōu)路由,節(jié)點死亡速度要慢很多,能有效延長網(wǎng)絡(luò)生存周期。

圖2 存活節(jié)點隨運行輪數(shù)變化對比

圖3 網(wǎng)絡(luò)總能耗隨運行輪數(shù)變化對比

3.2 網(wǎng)絡(luò)能耗

圖3為網(wǎng)絡(luò)消耗總能量隨輪數(shù)的變化情況,從圖中可以看出3種算法能耗有異,開始都成線性狀態(tài),但本文協(xié)議能耗更平緩,能耗速度更慢。

在相同輪次下,本文協(xié)議的能量消耗比EEUC協(xié)議和CSMST都明顯更低,本文算法在以剩余能量和能耗速度進行非均勻分簇,然后考慮剩余能量、簇間距離和能量消耗等因素構(gòu)造最小生成樹尋求最優(yōu)路由傳輸數(shù)據(jù)到Sink節(jié)點,能量消耗要慢很多,而且整個網(wǎng)絡(luò)的生命周期更長。

4 結(jié)語

本文借鑒非均勻分簇的思想計算節(jié)點半徑,提出了基于最小生成樹的非均勻分簇路由協(xié)議,該協(xié)議以剩余能量、節(jié)點度、節(jié)點能量消耗速度作為權(quán)重計算簇首選舉時間,通過時序方式選擇簇首;在簇首與Sink節(jié)點的數(shù)據(jù)通信階段采用多跳方式,綜合考慮中繼簇首剩余能量、簇間距離和能耗建立最小生成樹,找到一條最優(yōu)的數(shù)據(jù)傳輸路徑,減少通信能耗。仿真結(jié)果表明,本文協(xié)議可以有效均衡網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)生命周期。

[1] 李亞男,徐夫田,陳金鑫. 基于LEACH的WSNs分簇優(yōu)化策略[J]. 傳感技術(shù)學(xué)報,2014,27(5):670-674.

[2] 李建洲,王海濤,陶安. 一種能耗均衡的WSN分簇路由協(xié)議[J]. 傳感技術(shù)學(xué)報,2013,26(3):396-401.

[3] 蘇金樹,郭文忠,余朝龍,等. 負(fù)載均衡感知的無線傳感器網(wǎng)絡(luò)容錯分簇算法[J]. 計算機學(xué)報,2014,37(2):445-456.

[4] Mhatre V,Rosenberg C. Design Guidelines for Wireless Sensor Networks:Communication,Clustering and Aggregation[J]. Ad Hoc Networks,2004,2(1):45-63.

[5] 彭蕾,呂敬祥,劉秋平. 大規(guī)模無線傳感網(wǎng)絡(luò)的混合LEACH協(xié)議研究[J]. 傳感技術(shù)學(xué)報,2016,29(11):1737-1741.

[6] 李成法,陳貴海,葉懋,等. 一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 計算機學(xué)報,2007,30(1):27-36.

[7] 蔣暢江,石為人,唐賢倫,等. 能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J]. 軟件學(xué)報,2012,23(5):1222-1232.

[8] 盧先順,王瑩瑩,王洪斌,等. 無線傳感器網(wǎng)絡(luò)能量均衡的非均勻分簇算法[J]. 計算機科學(xué),2013,40(5):78-81.

[9] 陸晶,馬悅,吳曉軍. 一種基于最小生成樹的非均勻分簇路由算法[J]. 小型微型計算機系統(tǒng),2012,33(10):2293-2296.

[10] 張明才,薛安榮,王偉. 基于最小生成樹的非均勻分簇路由算法[J]. 計算機應(yīng)用,2012,32(3):787-790.

[11] Estrin D. Wireless Sensor Networks Tutorial Part Ⅳ:Sensor Network Protocols//Proc of the ACM Mobil Computing and Networking. New York:ACM,2002. 1-5.

[12] Heinzelman W,Chandrakasan A,Balakrishnam H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc of the 33rd Conf on System Sciences. Piscataway. NJ:IEEE. 2000:3005-3014.

廖福保(1976-),男,碩士,副教授,研究方向為計算機應(yīng)用、無線傳感器網(wǎng)絡(luò)與路由,fbliao2000@163.com;

張文梅(1978-),女,碩士,副教授,研究方向為計算機應(yīng)用、物聯(lián)網(wǎng),zwm200718@126.com。

UnevenClusteringRoutingProtocolBasedonMinimumSpanningTree*

LIAOFubao1,ZHANGWenmei2*

(1.Department of Computer,Guang Dong AIB Polytechnic College,Guangzhou 510507,China; 2.Department of Mechanics and Electronics,Guang Dong AIB Polytechnic College,Guangzhou 510507,China)

When the data is transmitted from cluster heads to Sink node via multi-hop communication,the energy hole may be caused. In order to solve the problem,an uneven clustering routing protocol based on minimum spanning tree is proposed. In the cluster heads selection stage,the protocol calculates the cluster head selection time of each node based on the residual energy,the node degree and the energy consumption rate. The protocol selects the cluster head by the cluster head selection time. In the stage of routing establishment,the protocol builds the optimal transmission path based on minimum spanning tree,according to the residual energy of cluster heads,the distance between cluster heads and energy consumption. The cluster heads send the data to Sink node through the nodes of the tree by multi-hop. The simulation shows that the routing protocol can effectively balance energy consumption,prolong the wireless sensor network survival period and delay the forming speed of energy hole.

wireless sensor networks;unequal clustering;energy balance;minimum spanning tree

項目來源:科技部國家星火計劃項目(2013GA780003)

2017-02-09修改日期:2017-04-13

TP393

:A

:1004-1699(2017)09-1412-05

10.3969/j.issn.1004-1699.2017.09.019