改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由算法*

張文梅,廖福保

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

?

改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由算法*

張文梅1,廖福保2*

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

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中不均勻分簇引起能量空洞的問(wèn)題,提出了改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由算法。該算法先根據(jù)節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)到基站的距離、節(jié)點(diǎn)“度”和節(jié)點(diǎn)到簇頭的距離等因素選舉簇頭;沒(méi)有成為簇頭的節(jié)點(diǎn)選擇加入到距離最近的簇頭所在的簇中,從而將整個(gè)網(wǎng)絡(luò)劃分為大小不等的簇;然后簇頭再根據(jù)簇頭剩余能量、簇頭到基站的距離構(gòu)造基于最小生成樹的最優(yōu)傳輸路徑;通過(guò)簇內(nèi)節(jié)點(diǎn)單跳、樹內(nèi)簇頭多跳通信的方式將數(shù)據(jù)最終傳輸?shù)交?。仿真結(jié)果表明,該路由算法能有效節(jié)約能量和均衡節(jié)點(diǎn)能耗,從而延長(zhǎng)網(wǎng)絡(luò)的生命周期。

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

無(wú)線傳感器網(wǎng)絡(luò)通常包括了大量的傳感器節(jié)點(diǎn)和用于收集和發(fā)送數(shù)據(jù)的基站組成,這些傳感器節(jié)點(diǎn)采集監(jiān)控區(qū)域的數(shù)據(jù),通過(guò)自組網(wǎng)方式將采集到的數(shù)據(jù)上傳給基站。由于傳感器節(jié)點(diǎn)大多采用電池供電,很難對(duì)傳感器節(jié)點(diǎn)進(jìn)行能量補(bǔ)充,因此設(shè)計(jì)能量高效的路由算法是WSN研究的熱點(diǎn)[1-2]。

LEACH[3]為最早提出的分簇路由算法,它能有效降低能耗并提高網(wǎng)絡(luò)生命周期,但簇頭到基站通過(guò)單跳方式傳輸會(huì)使距離基站遠(yuǎn)的簇頭消耗過(guò)多能量。研究表明在簇頭到基站間采用多跳方式傳輸更節(jié)約能量[4],然而距離基站近的簇頭需要轉(zhuǎn)發(fā)其他簇頭的數(shù)據(jù),必然造成離基站近的簇頭消耗過(guò)快,導(dǎo)致能耗不均衡。針對(duì)近基站簇頭能耗過(guò)大造成能耗不平衡的問(wèn)題,文獻(xiàn)[5]提出的EEUC算法、文獻(xiàn)[6]提出的DEBUC算法均采用非均勻分簇,能有效均衡能量消耗,延長(zhǎng)網(wǎng)絡(luò)生命周期,但其簇頭選擇采用概率和門限值來(lái)決定,不能保證所選擇的簇頭最優(yōu)。文獻(xiàn)[7]提出EBUCA算法利用剩余能量和節(jié)點(diǎn)密度設(shè)置簇頭選擇閾值,并根據(jù)簇頭密度及與基站的距離構(gòu)建非均勻的簇半徑,達(dá)到均衡節(jié)點(diǎn)能耗的目的;文獻(xiàn)[8]提出冗余簇頭并減少簇頭選擇的次數(shù)來(lái)延長(zhǎng)網(wǎng)絡(luò)生命周期;文獻(xiàn)[9]對(duì)簇頭選擇與簇頭更換提出了改進(jìn)措施,能提高網(wǎng)絡(luò)性能,但其簇頭更換僅在簇內(nèi)進(jìn)行也會(huì)造成能耗不均衡。

文獻(xiàn)[10]在非均勻分簇的基礎(chǔ)上,簇頭路由中采用蟻群算法進(jìn)行優(yōu)化,能延長(zhǎng)網(wǎng)絡(luò)生命周期,但并沒(méi)有考慮鏈路質(zhì)量,可能造成局部路徑最優(yōu)。文獻(xiàn)[11-12]在非均勻分簇的基礎(chǔ)上,簇頭路由構(gòu)造最小生成樹,在構(gòu)造樹時(shí)只考慮了傳輸能耗以及簇頭的剩余能量或只考慮了與基站的距離。

本文綜合以上問(wèn)題,提出了改進(jìn)的非均勻分簇路由算法。算法在簇頭選擇時(shí)綜合考慮節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)“度”、簇內(nèi)節(jié)點(diǎn)與簇頭的距離、節(jié)點(diǎn)到基站的距離等因素,將整個(gè)網(wǎng)絡(luò)劃分為不均勻的簇,簇內(nèi)節(jié)點(diǎn)通過(guò)單跳方式將數(shù)據(jù)發(fā)送給簇頭;然后簇頭與基站之間根據(jù)簇頭剩余能量以及與基站的距離構(gòu)造以基站為根節(jié)點(diǎn)的最小生成樹,簇頭通過(guò)最小生成樹組織的路由以多跳方式將數(shù)據(jù)傳送給基站。該算法能很好地均衡節(jié)點(diǎn)能耗,達(dá)到有效延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。

1 相關(guān)模型

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

為便于研究,本文假設(shè)傳感器網(wǎng)絡(luò)具有如下性質(zhì):①節(jié)點(diǎn)部署后不再移動(dòng)且能量有限,基站位置固定而能量不受限;②每個(gè)節(jié)點(diǎn)具有相同的初始能量,且有相同的通信和數(shù)據(jù)處理能力,可自由調(diào)整發(fā)射功率;③每個(gè)節(jié)點(diǎn)具有唯一的標(biāo)識(shí),用Si表示第i各節(jié)點(diǎn),則節(jié)點(diǎn)集合S={S1,S2,…,Sn};④節(jié)點(diǎn)可以根據(jù)接收到的信號(hào)強(qiáng)度RSSI來(lái)計(jì)算發(fā)出者到自己的近似距離;⑤基站能夠和所有節(jié)點(diǎn)進(jìn)行通信。

1.2 能量模型

由于無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸時(shí)所耗的能量遠(yuǎn)大于其他的能耗[13]。本文采用文獻(xiàn)[3]中的無(wú)線通信能耗模型,發(fā)送數(shù)據(jù)時(shí)其能耗公式如下:

(1)

節(jié)點(diǎn)接收k比特?cái)?shù)據(jù)的能耗為:

ERx(k)=kEelec

(2)

為簡(jiǎn)化問(wèn)題,假定通信均采用自由空間模型,簇頭j內(nèi)的節(jié)點(diǎn)數(shù)為n,則簇內(nèi)成員節(jié)點(diǎn)i發(fā)送k比特?cái)?shù)據(jù)到簇頭j所消耗的能量為

(3)

式中:dij為成員節(jié)點(diǎn)i與簇頭j之間的距離。

簇頭j所消耗的能量包括接收簇內(nèi)n個(gè)節(jié)點(diǎn)數(shù)據(jù)所耗能量、發(fā)送這些數(shù)據(jù)所耗的能量、接收和轉(zhuǎn)發(fā)來(lái)自其他m個(gè)簇頭數(shù)據(jù)所耗的能量,其公式如下(為方便研究,假如每個(gè)簇內(nèi)均有n個(gè)節(jié)點(diǎn)數(shù)據(jù)):

Ej=(m+1)n[ETx(k,d)+ERx(k)]=

(m+1)nk(2Eelec+εfsd2)

(4)

式中:d為簇頭到下一跳的距離。

由式(3)、式(4)可知,簇頭的能耗由簇內(nèi)節(jié)點(diǎn)數(shù)n、要轉(zhuǎn)發(fā)的數(shù)據(jù)量k以及簇內(nèi)節(jié)點(diǎn)與簇頭的距離dij以及到下一跳的距離d決定的,因此優(yōu)化簇頭選擇和數(shù)據(jù)傳輸路徑能有效降低能耗。

2 改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由算法

類似于LEACH,本算法采用“輪”方式運(yùn)行,每輪分為簇建立階段和數(shù)據(jù)傳輸階段。在簇建立階段選擇綜合考慮剩余能量、節(jié)點(diǎn)與基站的距離、節(jié)點(diǎn)的“度”以及簇內(nèi)節(jié)點(diǎn)與簇頭距離等因素,采用時(shí)序的方式選擇簇頭。在數(shù)據(jù)傳輸階段,根據(jù)簇頭剩余能量及簇頭與基站間的距離建立基于最小生成樹的最優(yōu)傳輸路徑。

2.1 概念描述

為便于描述,對(duì)本文所涉及的概念說(shuō)明如下:

①競(jìng)選半徑。節(jié)點(diǎn)競(jìng)選簇頭時(shí)的半徑,本文采用文獻(xiàn)[5]的公式計(jì)算競(jìng)選半徑。

(5)

②鄰居節(jié)點(diǎn)。節(jié)點(diǎn)Si和Sj互為鄰居節(jié)點(diǎn)滿足

dij

(6)

式中:dij節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離。

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

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

④平均剩余能量Eavg。節(jié)點(diǎn)根據(jù)鄰居表中鄰居節(jié)點(diǎn)的剩余能量計(jì)算出平均剩余能量。

(7)

⑤平均距離davg。節(jié)點(diǎn)根據(jù)鄰居表中鄰居節(jié)點(diǎn)與該節(jié)點(diǎn)的距離計(jì)算出平均距離。

(8)

⑥簇頭競(jìng)爭(zhēng)時(shí)間t。從節(jié)點(diǎn)收到基站通知簇頭競(jìng)爭(zhēng)到本節(jié)點(diǎn)發(fā)出簇頭競(jìng)爭(zhēng)消息的等待時(shí)間。

(9)

式中:α為[0.9,1]之間的隨機(jī)數(shù),T為規(guī)定的簇頭競(jìng)爭(zhēng)持續(xù)時(shí)間,ei為節(jié)點(diǎn)剩余能量,β、γ為距離調(diào)節(jié)因子。從式中可以看出,簇頭競(jìng)爭(zhēng)時(shí)間t由節(jié)點(diǎn)剩余能量、到基站的距離以及鄰居節(jié)點(diǎn)與該節(jié)點(diǎn)的距離決定,剩余能量越低、到基站越遠(yuǎn)、鄰居節(jié)點(diǎn)平均距離越大,t的取值就越大。

2.2 簇頭選舉

在無(wú)線傳感器網(wǎng)絡(luò)分簇算法中,簇頭選舉對(duì)有效管理網(wǎng)絡(luò)能耗至關(guān)重要。文獻(xiàn)[5-7]均證明了非均勻分簇能有效均衡簇頭能耗,緩解能量空洞。本文在非均勻分簇的基礎(chǔ)上建立了本文的簇頭選舉算法,網(wǎng)絡(luò)中所有節(jié)點(diǎn)都參與簇頭競(jìng)爭(zhēng),采用時(shí)序的方式選擇簇頭。

簇頭選擇的算法步驟:

第1步 基站向全網(wǎng)廣播一個(gè)分簇信號(hào)PAR_MSG,所有節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度計(jì)算其到基站的距離Di,然后根據(jù)式(5)確定其競(jìng)爭(zhēng)半徑Ri。

第2步 各節(jié)點(diǎn)競(jìng)選半徑Ri/2范圍內(nèi)廣播競(jìng)選消息Comp_MSG,該消息包括節(jié)點(diǎn)的ID、剩余能量ei。

第3步 各節(jié)點(diǎn)收到來(lái)自另外節(jié)點(diǎn)的競(jìng)選消息Comp_MSG,根據(jù)接收到的信號(hào)強(qiáng)度計(jì)算兩節(jié)點(diǎn)間的距離d,再根據(jù)式(6)將滿足條件的節(jié)點(diǎn)加入到鄰居節(jié)點(diǎn)表中。

第4步 各節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)表中的信息,按照式(7)、式(8)分別計(jì)算出平均剩余能量Eavg和平均距離davg。節(jié)點(diǎn)再根據(jù)式(9)計(jì)算出自身的簇頭競(jìng)爭(zhēng)時(shí)間t。

第5步 基站廣播簇頭選舉信號(hào)Sel_MSG,以同步各節(jié)點(diǎn)的時(shí)間。

第6步 節(jié)點(diǎn)接收到Sel_MSG信號(hào)后,啟動(dòng)自身時(shí)鐘開始計(jì)時(shí)并監(jiān)聽其他節(jié)點(diǎn)信號(hào)。

第7步 若節(jié)點(diǎn)i在本身的簇頭競(jìng)爭(zhēng)時(shí)間t到來(lái)前收到鄰居表中其他節(jié)點(diǎn)的簇頭宣告成功的消息SUC_MSG,節(jié)點(diǎn)i廣播競(jìng)選失敗的消息FAI_MSG,退出簇頭競(jìng)選。

第8步 若節(jié)點(diǎn)i收到鄰居表其他節(jié)點(diǎn)的FAI_MSG消息,就把這個(gè)節(jié)點(diǎn)從鄰居表中刪除。

第9步 若節(jié)點(diǎn)i在本身的簇頭競(jìng)爭(zhēng)時(shí)間t到之后還沒(méi)有收到鄰居表中其他節(jié)點(diǎn)的SUC_MSG消息,則該節(jié)點(diǎn)在競(jìng)選半徑內(nèi)廣播SUC_MSG消息成為簇頭。

第10步 選舉結(jié)束后,沒(méi)有成為簇頭的節(jié)點(diǎn)選擇加入到鄰居表中距離最近的簇頭所在的簇中。離簇頭越近,簇內(nèi)通信可以節(jié)省能量。

第11步 分簇完成后,各個(gè)簇頭在競(jìng)選半徑范圍內(nèi)廣播簇頭消息CLU_MSG,并收集其他簇頭廣播的消息,為后續(xù)路由做準(zhǔn)備。CLU_MSG信息包括簇頭ID、剩余能量。

算法中將整個(gè)網(wǎng)絡(luò)劃分為大小不等的簇,靠近基站的簇半徑小,有利于均衡能耗;簇頭競(jìng)爭(zhēng)時(shí)間考慮了剩余能量、到基站距離以及簇內(nèi)節(jié)點(diǎn)到簇頭的平均距離等因素,能夠保證選舉的簇頭綜合性能最優(yōu)。

2.3 簇間路由

分簇及簇頭選舉結(jié)束后,簇間通信采用多跳路由,以基站為樹根,簇間路由采用最小生成樹方式來(lái)組織。先將每個(gè)簇抽象為一個(gè)點(diǎn),用邊把相鄰的簇連接起來(lái),構(gòu)造一個(gè)帶權(quán)的連通圖G=(V,E)表示無(wú)線傳感器網(wǎng)絡(luò),其中V是點(diǎn)集(包括所有簇頭和基站的集合),E為邊集。

發(fā)送和接收同樣長(zhǎng)度的數(shù)據(jù),通信能耗由節(jié)點(diǎn)間距離決定,因此權(quán)值計(jì)算時(shí)綜合考慮簇頭間距離和簇頭剩余能量,權(quán)值計(jì)算如式(10)所示:

(10)

式中:wij為簇頭i、j的邊的權(quán)值,dij簇頭i、j之間的距離,ei、ei為簇頭i、j的剩余能量,ρ為可變參數(shù),不能相互接收信息的兩個(gè)簇頭的邊的權(quán)值w設(shè)為無(wú)窮大。從式中可以看出,權(quán)值由簇頭間距離和簇頭的剩余能量決定,剩余能量越低、簇頭間距離越遠(yuǎn),wij的取值就越大,則簇頭要負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)的概率降低,從而節(jié)省自身能量,延長(zhǎng)生命周期,達(dá)到整個(gè)網(wǎng)絡(luò)能量均衡。

根據(jù)簇頭選擇過(guò)程中計(jì)算得到的簇頭到基站的距離Di以及相鄰簇頭的廣播信息CLU_MSG,簇間路由利用Prim構(gòu)造最小生成樹的具體算法步驟:

第1步 各簇頭根據(jù)本身到基站的距離Di及剩余能量ei,計(jì)算Di/ei的值,若Di/ei值小于h(h為常量)的簇頭集合為C={C1,C2,…},集合C中的簇頭可以直接將數(shù)據(jù)傳輸給基站。

第2步 在有向連接圖G=(V,E)中,將集合C中的簇頭節(jié)點(diǎn)和基站加入到集合U中,將集合C中的簇頭到基站的邊加入到集合T中。

第3步 各簇頭根據(jù)接收到的CLU_MSG信息,依照接收到的信號(hào)強(qiáng)度計(jì)算兩節(jié)點(diǎn)間的距離d,再依據(jù)式(10)計(jì)算出簇頭間每條邊的權(quán)值w(不包括集合C中簇頭到基站的邊)。

第4步 從所有u∈U,v∈V-U的邊中選擇權(quán)值wuv最小的邊,將簇頭v加入到U中,將邊(u,v)加入到集合T中。

第5步 重復(fù)執(zhí)行第4步,直到U=V為止。此時(shí)集合T中的所有邊就構(gòu)造了一棵最小生成樹。

第6步 依據(jù)已確定的最小生成樹的結(jié)構(gòu),節(jié)點(diǎn)調(diào)整傳輸功率,調(diào)整為能夠到達(dá)其最小生成樹的所有一跳鄰居,從而節(jié)省能量。

當(dāng)節(jié)點(diǎn)數(shù)據(jù)到達(dá)簇頭時(shí),簇頭根據(jù)以上生成的最小生成樹,以多跳方式將數(shù)據(jù)傳輸?shù)交尽?/p>

2.4 算法分析

假定無(wú)線傳感器網(wǎng)絡(luò)中共有個(gè)N節(jié)點(diǎn),產(chǎn)生了M個(gè)簇頭,則算法時(shí)間復(fù)雜度為O(N2)。

證明 成簇開始時(shí),基站廣播PAR_MSG信息,各節(jié)點(diǎn)計(jì)算競(jìng)選半徑,時(shí)間復(fù)雜度為O(N);每個(gè)節(jié)點(diǎn)計(jì)算節(jié)點(diǎn)間距離并加入到對(duì)應(yīng)鄰居表中,時(shí)間復(fù)雜度為O(N2);每個(gè)節(jié)點(diǎn)計(jì)算自身的簇頭競(jìng)爭(zhēng)時(shí)間,時(shí)間復(fù)雜度為O(N2);基站廣播簇頭選舉信號(hào)Sel_MSG,各節(jié)點(diǎn)啟動(dòng)時(shí)鐘計(jì)時(shí),時(shí)間復(fù)雜度為O(N);各節(jié)點(diǎn)計(jì)時(shí)開始根據(jù)簇頭競(jìng)爭(zhēng)時(shí)間來(lái)進(jìn)行簇頭選舉,時(shí)間復(fù)雜度為O(N2)。因此非均勻分簇及簇頭選舉的成簇算法時(shí)間復(fù)雜度為O(N+N2+N2+N+N2),即O(N2)。

簇間路由中,算法開始時(shí)構(gòu)造帶權(quán)的連通圖的時(shí)間復(fù)雜度為O(M2);各簇頭計(jì)算Di/ei值的時(shí)間復(fù)雜度為O(M);計(jì)算簇頭間距離和權(quán)值w的時(shí)間復(fù)雜度為O(M2);依照權(quán)值w構(gòu)造最小生成樹的時(shí)間復(fù)雜度為O(M2)。因此簇間路由算法的時(shí)間復(fù)雜度為O(M2+M+M2+M2),即O(M2)。

根據(jù)以上分析,因?yàn)镹?M,因此整個(gè)算法的時(shí)間復(fù)雜度為O(N2)。

3 實(shí)驗(yàn)仿真

采用OPNET仿真軟件對(duì)本文算法、EEUC協(xié)議和EBUCA協(xié)議進(jìn)行比較仿真模擬。實(shí)驗(yàn)仿真參數(shù)如表2所示,傳感器節(jié)點(diǎn)隨機(jī)分布,簇點(diǎn)融合數(shù)據(jù)的能量忽略不計(jì)。為了比較,本實(shí)驗(yàn)相關(guān)參數(shù)與文獻(xiàn)[5]的相同,取c=0.5,而ρ=0.5。圖1為存活節(jié)點(diǎn)數(shù)隨運(yùn)行輪數(shù)的變化情況,圖2為剩余總能量隨運(yùn)行輪數(shù)的變化情況。

表2 實(shí)驗(yàn)仿真參數(shù)表

圖1 生命周期對(duì)比

圖2 剩余總能量對(duì)比

由圖1可以看出,本文算法從第1個(gè)節(jié)點(diǎn)失效到最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間都比EEUC和EBUCA算法滯后,這說(shuō)明本文算法能夠很好的均衡網(wǎng)絡(luò)能耗從而延長(zhǎng)網(wǎng)絡(luò)生命周期。不管是以首個(gè)節(jié)點(diǎn)死亡時(shí)間還是以最后一個(gè)節(jié)點(diǎn)死亡時(shí)間作為判斷標(biāo)準(zhǔn),本文算法都更優(yōu)。

圖2對(duì)比了3種算法每輪過(guò)后的剩余總能量,可以看出本文算法具有較小的坡度,波動(dòng)較小且生存時(shí)間更長(zhǎng),表明本文算法相對(duì)于EEUC和EBUCA算法能耗速度較慢且能耗較 小,更能有效地節(jié)約能量。

4 結(jié)語(yǔ)

本文對(duì)已有的無(wú)線傳感器網(wǎng)絡(luò)路由算法及其存在的問(wèn)題,借鑒非均勻分簇的思想,提出了改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由算法。改進(jìn)的算法在簇頭選擇階段綜合考慮剩余能量、節(jié)點(diǎn)到簇頭的距離、節(jié)點(diǎn)“度”以及節(jié)點(diǎn)到基站距離等因素,通過(guò)時(shí)序方式選擇簇頭;在數(shù)據(jù)傳輸階段,綜合考慮剩余能量和簇頭到基站距離建立最小生成樹,通過(guò)多跳方式進(jìn)行數(shù)據(jù)傳輸。實(shí)驗(yàn)結(jié)果表明,本文算法可以延長(zhǎng)節(jié)點(diǎn)的死亡時(shí)間,有效均衡網(wǎng)絡(luò)能耗,從而延長(zhǎng)網(wǎng)絡(luò)生命周期。

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

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

[3]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.

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

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

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

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

[8]馮冬芹,李光輝,全劍敏,等. 基于簇頭冗余的無(wú)線傳感器網(wǎng)絡(luò)可靠性研究[J]. 浙江大學(xué)學(xué)報(bào):工學(xué)版,2009,43(5):849-854.

[9]姚光順,溫衛(wèi)敏,張永定,等. 改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)簇首選擇策略及其路由算法[J]. 計(jì)算機(jī)應(yīng)用,2013,33(4):908-911,915.

[10]張榮博,曹建福. 利用蟻群優(yōu)化的非均勻分簇?zé)o線傳感器網(wǎng)絡(luò)路由算法[J]. 西安交通大學(xué)學(xué)報(bào),2010,44(6):33-38.

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

[12]鄒杰,史長(zhǎng)瓊,姬文燕. 基于粒子群優(yōu)化的非均勻分簇路由算法[J]. 計(jì)算機(jī)應(yīng)用,2012,32(1):131-133.

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

Improved Uneven Clustering Routing Algorithm for Wireless Sensor Networks*

ZHANGWenmei1,LIAOFubao2*

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

In order to solve the problem of energy hole in wireless sensor networks caused by uneven clustering protocol,an improved uneven clustering routing algorithm is proposed. In the cluster heads selection stage,the algorithm selects the cluster heads based on several factors,including the residual energy of node,the distance between node and base station,the "degree" of the node,and the distance between node and cluster head. Other nodes that can’t be cluster heads select to join the cluster nearest to complete the process of clustering and the network is divided into clusters with different size. In the stage of data transmission,the algorithm constructs the optimal transmission path based on minimum spanning tree,according to the residual energy of cluster heads,and the distance between cluster heads and base station as well. The ordinary nodes of a cluster sends the data to cluster head through a single jump,and cluster heads send the data to base station through the nodes of the tree by the more jumping communication. The simulation shows that the routing algorithm can efficiently reduce and balance the energy consumption,and prolong the wireless sensor network survival period.

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

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

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

項(xiàng)目來(lái)源:科技部國(guó)家星火計(jì)劃項(xiàng)目(2013GA780003)

2014-11-28 修改日期:2015-01-26

C:6150P

10.3969/j.issn.1004-1699.2015.05.021

TP3931

A

1004-1699(2015)05-0739-05