簡玉梅,張韓飛,高 飛,阮麟杰,張登珠,洪晴駿,趙旭東

(1.上海工程技術(shù)大學(xué)電子電氣工程學(xué)院,上海 201602;2.江蘇淮陰師范學(xué)院,江蘇 淮陰 223300)

一種基于Agent自信度的簇間多跳路由協(xié)議*

簡玉梅1*,張韓飛2,高 飛1,阮麟杰1,張登珠1,洪晴駿1,趙旭東1

(1.上海工程技術(shù)大學(xué)電子電氣工程學(xué)院,上海 201602;2.江蘇淮陰師范學(xué)院,江蘇 淮陰 223300)

為了均衡無線傳感器網(wǎng)絡(luò)中的能量消耗問題,延長網(wǎng)絡(luò)的生存時(shí)間,提出了一種基于Agent自信度的無線傳感器網(wǎng)絡(luò)多跳路由協(xié)議。該協(xié)議引入節(jié)點(diǎn)剩余能量、初始能量和節(jié)點(diǎn)的自信度來調(diào)節(jié)傳感器節(jié)點(diǎn)隨機(jī)數(shù)的大小。簇間通信時(shí),綜合考慮簇頭節(jié)點(diǎn)的剩余能量,簇頭節(jié)點(diǎn)距離Sink節(jié)點(diǎn)的距離,簇頭節(jié)點(diǎn)的自信度3個(gè)因素,簇頭節(jié)點(diǎn)和Sink節(jié)點(diǎn)之間使用單跳和多跳相結(jié)合的傳輸方式。每次重選簇頭前都動(dòng)態(tài)的修改節(jié)點(diǎn)的自信度。通過實(shí)驗(yàn)表明,相較于LEACH協(xié)議和ASCH協(xié)議,提出的協(xié)議能夠很好的延長網(wǎng)絡(luò)的壽命。

無線傳感器網(wǎng)絡(luò);非均勻分簇;agent自信度

無線傳感器網(wǎng)絡(luò)由具有感知、處理和無線通信能力的傳感器節(jié)點(diǎn)通過自組織方式形成網(wǎng)絡(luò)。如何合理地利用傳感器節(jié)點(diǎn)有限的能量延長網(wǎng)絡(luò)壽命是傳感器網(wǎng)絡(luò)設(shè)計(jì)的主要問題。每個(gè)節(jié)點(diǎn)能夠通過拓?fù)淇刂茩C(jī)制自動(dòng)轉(zhuǎn)發(fā)監(jiān)測數(shù)據(jù)。目前,拓?fù)淇刂埔呀?jīng)形成功率控制和睡眠調(diào)度兩個(gè)主流研究方向。在睡眠調(diào)度中,分簇被證明為解決這一問題的有效機(jī)制,簇中節(jié)點(diǎn)分為簇頭節(jié)點(diǎn)和簇成員節(jié)點(diǎn)。

文獻(xiàn)[1]總結(jié)了一個(gè)有效簇算法需要同時(shí)具有的特點(diǎn):①完全分布式的簇算法有利于節(jié)省網(wǎng)絡(luò)能量和提高網(wǎng)絡(luò)的可擴(kuò)展性。②簇頭盡量均勻分布,盡量減少算法本身的開銷。③簇算法能夠很好的處理節(jié)點(diǎn)能量異構(gòu)問題。

近年來,諸多學(xué)者對無線傳感器網(wǎng)絡(luò)分簇算法進(jìn)行了大量研究,提出很多分布式分簇算法的同時(shí)也取得了大量成果。

常見簇算法有固定分簇算法和非均勻分簇算法。固定分簇算法將網(wǎng)絡(luò)分為大小相等的區(qū)域,各區(qū)域內(nèi)的節(jié)點(diǎn)分別構(gòu)成一個(gè)簇,每輪只從每個(gè)簇中重新選擇簇頭,不改變各個(gè)簇的組成[2]。非均勻分簇構(gòu)造出大小不等的簇,建簇時(shí)節(jié)點(diǎn)可以考慮放棄距離最近的簇頭而選擇距離基站較近的簇頭,從而構(gòu)造出離基站越遠(yuǎn)就越大的非均勻簇[3]。

分簇?cái)?shù)據(jù)融合算法LEACH(Low-Energy Adaptive Clustering Hierarchy)[4]是最具有代表性的一種層次路由協(xié)議,基于輪的概念,每輪分為簇的建立和數(shù)據(jù)通信階段,簇頭角色需要周期性地在整個(gè)網(wǎng)絡(luò)中輪轉(zhuǎn),節(jié)點(diǎn)成為簇頭的選擇概率P恒定,每個(gè)傳感器節(jié)點(diǎn)根據(jù)每輪產(chǎn)生的隨機(jī)數(shù)與P計(jì)算出的閾值T(n)進(jìn)行比較決定是否成為簇頭。簇頭廣播自己成為簇頭的消息,其他節(jié)點(diǎn)根據(jù)自身到簇頭的通信代價(jià)選擇一個(gè)簇頭加入。在穩(wěn)定階段,各個(gè)簇成員在相應(yīng)通信時(shí)隙內(nèi)將數(shù)據(jù)發(fā)送至簇頭,簇頭融合數(shù)據(jù)后發(fā)往基站。目前很多層次路由協(xié)議都是基于LEACH協(xié)議進(jìn)行的相關(guān)改進(jìn),EADEEG協(xié)議[1]使用鄰居節(jié)點(diǎn)平均剩余能量與節(jié)點(diǎn)本身剩余能量的比值,作為競爭簇頭的參數(shù),減少簇形成過程中控制消息的開銷,但存在“孤點(diǎn)”問題。文獻(xiàn)[5]以節(jié)點(diǎn)的“度”作為節(jié)點(diǎn)競爭簇頭輔助參數(shù),解決了EADEEG協(xié)議中“孤點(diǎn)”問題。文獻(xiàn)[6]在“度”的基礎(chǔ)上,也考慮了剩余能量,距離,并構(gòu)造了最小生成樹來傳輸數(shù)據(jù)。文獻(xiàn)[7]提出分布式分簇算法EEDC,選擇高能量和低通信開銷的節(jié)點(diǎn)作為簇頭,在簇頭預(yù)選時(shí),假設(shè)不斷增加節(jié)點(diǎn)成為候選節(jié)點(diǎn)的選擇概率P來保證候選簇頭的個(gè)數(shù)。文獻(xiàn)[8]提出LEACH-T算法,基于節(jié)點(diǎn)分布密度、節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)信號強(qiáng)度等,降低了節(jié)點(diǎn)的使用能耗,延長網(wǎng)絡(luò)使用時(shí)間。文獻(xiàn)[9]提出將簇頭節(jié)點(diǎn)分為管理節(jié)點(diǎn),融合節(jié)點(diǎn),轉(zhuǎn)發(fā)節(jié)點(diǎn),通過優(yōu)化結(jié)構(gòu)來節(jié)省網(wǎng)絡(luò)能耗。文獻(xiàn)[10]結(jié)合LEACH和PEGASIS算法將網(wǎng)絡(luò)內(nèi)所有傳感器節(jié)點(diǎn)以區(qū)域?yàn)閱挝患铣纱?形成簇頭鏈提高網(wǎng)絡(luò)生命期。文獻(xiàn)[11]將單跳通信方式改成多跳通信方式,由簇頭負(fù)責(zé)將鄰居簇首的數(shù)據(jù)轉(zhuǎn)發(fā)給Sink節(jié)點(diǎn)。文獻(xiàn)[12]將節(jié)點(diǎn)分為主要簇頭和次要簇頭,以此減少簇頭的重選時(shí)間。文獻(xiàn)[13]提出了SENMA算法,將移動(dòng)Agent引入了分簇算法中,簇成員不和簇通信,由MA完成通信功能。

上述文獻(xiàn)中,LEACH不考慮簇頭當(dāng)前剩余能量,需要較為嚴(yán)格的時(shí)間同步,由于P恒定,容易使低剩余能量的節(jié)點(diǎn)被選為候選簇頭,LEACH協(xié)議在簇形成階段,每個(gè)簇頭需要向全網(wǎng)廣播,能量消耗大;EEDC中雖然考慮了能量且動(dòng)態(tài)的修改P,但沒有給出具體修改方法,使得算法的可驗(yàn)證性不強(qiáng);ASCH算法[14]根據(jù)簇頭節(jié)點(diǎn)所處的地理位置、剩余能量及簇內(nèi)成員節(jié)點(diǎn)數(shù)目,動(dòng)態(tài)決定是否需要在簇內(nèi)產(chǎn)生助理簇頭,但存在每個(gè)簇頭都要計(jì)算一次是否需要產(chǎn)生動(dòng)態(tài)助理簇頭的閾值,帶來了額外的開銷。

針對以上算法的不足,本文引入帶有Agent中的自信度,將每個(gè)節(jié)點(diǎn)都設(shè)想為一個(gè)Agent,構(gòu)建基于Agent自信度的多跳路由協(xié)議EACMRA(An Embedded Agent Cluster Head Multi-hops Routing Algorithm)。

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

設(shè)在二維坐標(biāo)系中,在一個(gè)邊長為L的正方形區(qū)域內(nèi)隨機(jī)均勻分布n個(gè)傳感器節(jié)點(diǎn),具有如下性質(zhì):①傳感器網(wǎng)絡(luò)為靜態(tài)網(wǎng)絡(luò),節(jié)點(diǎn)部署后不再移動(dòng)。每個(gè)節(jié)點(diǎn)有一個(gè)全局唯一的id標(biāo)識。假設(shè)編號為1,2,…,n,唯一的匯聚節(jié)點(diǎn)Sink編號為0。②節(jié)點(diǎn)有相同的初始能量,其能量是有限且不可再充。③節(jié)點(diǎn)的無線發(fā)射功率可控,即節(jié)點(diǎn)可以根據(jù)接收者的距離來調(diào)整其發(fā)射功率。④網(wǎng)絡(luò)節(jié)點(diǎn)都是全雙工通信,能與基站直接通信。假設(shè)能量從節(jié)點(diǎn)i傳輸?shù)焦?jié)點(diǎn)j消耗的能量等同于從節(jié)點(diǎn)j傳輸?shù)焦?jié)點(diǎn)i消耗的能量。

2 EACMRA協(xié)議

與LEACH類似,EACMRA也按輪運(yùn)行,每輪包括候選簇頭的選擇和最終簇頭的確定。候選簇頭的選擇主要是判斷生成的隨機(jī)數(shù)和每個(gè)節(jié)點(diǎn)的T(n),當(dāng)T(n)大于隨機(jī)數(shù),則被標(biāo)識為候選簇頭,但是由于在相近的范圍內(nèi),可能滿足條件的節(jié)點(diǎn)很多,所以為了保證簇頭節(jié)點(diǎn)的數(shù)量,有必要在候選簇頭的基礎(chǔ)上在進(jìn)行一次簇頭選擇。減少由于簇頭間距太小,簇與簇間重疊范圍大而增加的網(wǎng)絡(luò)總能量損耗。以保證選擇的簇頭同時(shí)滿足3個(gè)條件:簇頭節(jié)點(diǎn)有足夠的剩余能量來保證數(shù)據(jù)傳遞;簇頭與簇內(nèi)節(jié)點(diǎn)之間的距離在正常通信范圍內(nèi);簇頭和簇頭節(jié)點(diǎn)之間距離不會(huì)太近,避免簇頭的冗余。

2.1 候選簇頭選擇

每輪首先由網(wǎng)關(guān)發(fā)出分簇廣播啟動(dòng)本輪簇頭的選舉,該信息包含網(wǎng)絡(luò)中所有簇頭剩余能量的平均值Eav,凡是小于平均值的節(jié)點(diǎn)都被標(biāo)示為普通節(jié)點(diǎn),該節(jié)點(diǎn)不能參與候選簇頭的競爭。與LEACH協(xié)議相似,網(wǎng)絡(luò)中所有非普通節(jié)點(diǎn)隨機(jī)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù),如果這個(gè)隨機(jī)數(shù)小于閾值T(n),則成為候選簇頭,如果大于T(n)則該節(jié)點(diǎn)暫時(shí)成為普通節(jié)點(diǎn)。

文獻(xiàn)[15]提出承擔(dān)中繼任務(wù),越靠近Sink的簇頭能耗越大,簇頭概率應(yīng)與節(jié)點(diǎn)到Sink的距離成反比,將LEACH協(xié)議中的閾值函數(shù)乘以經(jīng)驗(yàn)因子,通過改變閾值,使簇頭概率隨距離連續(xù)變化。

節(jié)點(diǎn)成功傳輸數(shù)據(jù)的影響因素很多,比如硬件質(zhì)量,現(xiàn)場的環(huán)境,以及有無遮擋等,當(dāng)所有外在條件都一樣的情況下,多個(gè)節(jié)點(diǎn)可以成為候選簇頭,但是有的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的成功率低(轉(zhuǎn)發(fā)10次,成功3次),有的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)成功率高(轉(zhuǎn)發(fā)10次,成功6次),為了防止小范圍內(nèi)多個(gè)節(jié)點(diǎn)都能選為簇頭導(dǎo)致簇太密集,簇頭過多,本文結(jié)合文獻(xiàn)[15],提出引入Agent的自信度,將自信度引入到T(n)的選擇過程中,將節(jié)點(diǎn)的自信度作為選擇因素,自信度主要用來區(qū)別節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)成功的情況,通過自信度在多個(gè)都可以成為最終簇頭的候選簇頭中選出數(shù)據(jù)轉(zhuǎn)發(fā)成功率高的節(jié)點(diǎn),從而減少數(shù)據(jù)的重傳,進(jìn)而減少能量消耗。

自信度定義如下:定義節(jié)點(diǎn)Agentm作為簇頭能成功轉(zhuǎn)發(fā)數(shù)據(jù)tj的信心為自信度。自信度是反應(yīng)一個(gè)節(jié)點(diǎn)能否順利完成指定任務(wù)的信譽(yù)(信譽(yù)越高,說明節(jié)點(diǎn)越滿足條件,越有能力在接下來的任務(wù)中順利完成任務(wù))[15]。

本文在LEACH協(xié)議中使用的T(n)公式上進(jìn)行了改進(jìn),T(n)的公式如(1):

(1)

式中:p為簇頭節(jié)點(diǎn)數(shù)目占總節(jié)點(diǎn)數(shù)目的比率,為了保證協(xié)議的性能,我們參考LEACH協(xié)議中的最優(yōu)簇頭數(shù)取值,r為當(dāng)前的輪數(shù),G表示當(dāng)前網(wǎng)絡(luò)中還沒有成為正式簇頭的節(jié)點(diǎn)集合。

T(n)=

(2)

本文定義各個(gè)節(jié)點(diǎn)初始自信度C(Agenti,tj)為1,自信度大于0表示節(jié)點(diǎn)有能力傳輸數(shù)據(jù),簇頭節(jié)點(diǎn)成功傳輸數(shù)據(jù)后自信度更新如公式(3)所示:

(3)

從式(2)、式(3)可以看出,自信度C和簇頭傳輸數(shù)據(jù)的成功率成正比。自信度的變化主要用來區(qū)別數(shù)據(jù)的傳輸是否成功。比如節(jié)點(diǎn)A和節(jié)點(diǎn)B,兩個(gè)節(jié)點(diǎn)的其他因素都一樣(硬件質(zhì)量,現(xiàn)場環(huán)境,有無遮擋,剩余能量,離Sink節(jié)點(diǎn)的距離等),在傳輸相同次數(shù)的數(shù)據(jù)時(shí),節(jié)點(diǎn)A傳輸成功5次,節(jié)點(diǎn)B傳輸成功4次,傳輸相同次數(shù),傳輸過程中消耗的能量一樣,節(jié)點(diǎn)剩余能量一樣。但兩個(gè)節(jié)點(diǎn)的自信度將會(huì)不一樣,節(jié)點(diǎn)A的自信度大于節(jié)點(diǎn)B,在選擇候選簇頭時(shí),將選擇節(jié)點(diǎn)A,這樣可以避免節(jié)點(diǎn)傳輸失敗帶來的數(shù)據(jù)重傳產(chǎn)生的能量消耗。

從式(2)、式(3)可以看出,在自信度和剩余能量一樣的情況下,節(jié)點(diǎn)離Sink節(jié)點(diǎn)越遠(yuǎn)被選為簇頭節(jié)點(diǎn)的概率就越低。在相同條件下,第r輪節(jié)點(diǎn)i自信度越大,剩余能量越多,離Sink節(jié)點(diǎn)越近的節(jié)點(diǎn)成為簇頭的概率就越高,就可以生成離Sink節(jié)點(diǎn)越遠(yuǎn)簇越小,可以讓靠近Sink節(jié)點(diǎn)的簇頭為簇間的數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留能量。

2.2 最終簇頭確定

在這個(gè)階段,只有候選簇頭節(jié)點(diǎn)才能競爭成為最終的簇頭節(jié)點(diǎn)。通過比較候選簇頭節(jié)點(diǎn)一階無線通信范圍內(nèi)所有鄰居節(jié)點(diǎn)的自信度,選擇自信度最大的節(jié)點(diǎn)作為最終簇頭[16]。

每個(gè)候選簇頭節(jié)點(diǎn)以通信半徑Rc廣播一條Node_Msg消息(包含節(jié)點(diǎn)自身ID,節(jié)點(diǎn)剩余能量,到基站的距離,自信度),同時(shí)也接收其他候選簇頭節(jié)點(diǎn)的消息。候選簇頭節(jié)點(diǎn)根據(jù)接收的消息創(chuàng)建一個(gè)候選簇頭鄰居列表。如果候選簇頭的自信度不低于其任意一個(gè)鄰居候選簇頭節(jié)點(diǎn)的自信度,則該候選簇頭為最終簇頭,并以通信半徑Rc廣播自己為簇頭節(jié)點(diǎn)的消息RealCH_Msg(包含ID,剩余能量,通信代價(jià),自信度和簇頭標(biāo)識)。

2.3 簇間通信

簇間通信主要負(fù)責(zé)完成數(shù)據(jù)轉(zhuǎn)發(fā)。

EACMRA協(xié)議采用與LEACH協(xié)議相同的一階無線電模型,當(dāng)發(fā)送的距離很近時(shí)(d≤d0),采用自由空間信道模型,當(dāng)距離遠(yuǎn)時(shí)使用多路徑衰減模型。當(dāng)兩個(gè)在經(jīng)過距離d傳輸1-bit信息時(shí),發(fā)送端能量消耗如式(4)。式(5)表示接收kbit數(shù)據(jù)的能量耗損,僅僅是由電路耗損引起的。式6為將接收的數(shù)據(jù)和自身的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合所需要的能耗。

(4)

節(jié)點(diǎn)接收能量消耗為:

ERx(l)=l·Eelec

(5)

數(shù)據(jù)融合能量消耗為:

EGx(l)=l·Egather

(6)

式中:l為數(shù)據(jù)長度,Eelec為節(jié)點(diǎn)發(fā)送1bit數(shù)據(jù)能耗,單位為J/bit。若傳輸距離小于等于閾值d0,采用自由空間模型。當(dāng)傳輸距離大于d0,采用多路徑衰減模型;εfs和εmp分別為自由空間模型和多徑模型下的能量損耗,單位為J/(bit·m2),J/(bit·m4)d0。論文取距離閾值為d0=87.7m[16]。

兩個(gè)傳感器節(jié)點(diǎn)Vi和Vj之間的距離di,j為式(7):

(7)

為了簡化分析問題,假設(shè)通信采用自由空間模型,并假設(shè)節(jié)點(diǎn)Vj接收到Vi數(shù)據(jù)后,直接將數(shù)據(jù)傳送到Sink,則傳送1比特的數(shù)據(jù)至Sink節(jié)點(diǎn),Vi消耗的能量如式(8):E2-hop=ETx(l,d(Vi,Vj))+[ERx(l)+ETx(l,d(Vj,DS))]

= l·Eelec+l·εfs·d2(Vi,Vj)+l·Eelec+l·Eelec+

l·εfs·d2d2(Vj,DS)=3·l·Eelec+

l·εfs(d2(Vi,Vj)+d2(Vj,DS)

(8)

由式(8)可知,能耗的高低取決于Vi和Vj間的距離,以及Vj和Sink節(jié)點(diǎn)間的距離。

在EACMRA協(xié)議中,按照前面的步驟,當(dāng)節(jié)點(diǎn)被選為簇頭后,經(jīng)過以下幾步完成數(shù)據(jù)的融合轉(zhuǎn)發(fā)。

①簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)發(fā)送時(shí)刻t設(shè)置

簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)發(fā)送的時(shí)刻t設(shè)置為與它和Sink的距離成反比,發(fā)送時(shí)隙到來后將簇內(nèi)節(jié)點(diǎn)采集的數(shù)據(jù)和其他簇頭轉(zhuǎn)來的數(shù)據(jù)一起發(fā)送,距離Sink較遠(yuǎn)的簇頭等待時(shí)間較短,距離Sink較近的節(jié)點(diǎn)等待時(shí)間長[15]。本文的等待時(shí)間T為:

T=15-sqrt(d)/100

式中:d為節(jié)點(diǎn)到Sink的距離,時(shí)間單位為s。15和100都可以取其他值,可以根據(jù)具體情況設(shè)置不同的等待時(shí)間。

②各節(jié)點(diǎn)開始與簇首進(jìn)行通信,將所采集到的數(shù)據(jù)周期性的發(fā)送給簇首節(jié)點(diǎn),還沒有輪到自己的時(shí)間片時(shí),進(jìn)入休眠狀態(tài)(節(jié)省能量)。簇頭將發(fā)送來的數(shù)據(jù)進(jìn)行融合,在等待了T時(shí)間后進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。

③考慮到距離Sink較遠(yuǎn)的簇首直接將數(shù)據(jù)發(fā)送到基站消耗的能量較大,所以區(qū)域內(nèi)的簇頭和基站的通信采用多跳的數(shù)據(jù)傳輸方式,這樣可以有效的節(jié)省能耗。簇首和基站采用單跳通信,則能量損耗將采用多徑衰落模型。

當(dāng)節(jié)點(diǎn)vi被選為簇頭以后,以較高的發(fā)射功率在網(wǎng)絡(luò)中廣播包括其ID,節(jié)點(diǎn)剩余能量Ei(r)和到基站的距離di的消息。簇頭vi收到其他簇頭vj的消息時(shí),計(jì)算兩個(gè)簇頭之間的距離d(vi,vj),如果d(vi,vj)小于傳感器節(jié)點(diǎn)的通信半徑R,則把節(jié)vj的信息保存在鄰居節(jié)點(diǎn)集合N(vi)中。表1為簇頭節(jié)點(diǎn)vi的鄰居簇頭節(jié)點(diǎn)路由信息表。

表1 簇頭節(jié)點(diǎn)vi的鄰居簇頭節(jié)點(diǎn)vj的路由信息表

傳感器節(jié)點(diǎn)vi需要將數(shù)據(jù)發(fā)送或者轉(zhuǎn)發(fā)時(shí),它的下一跳節(jié)點(diǎn)只能從其鄰居節(jié)點(diǎn)集合中選擇。如果d(vj,DS)大于通信半徑R,則選擇使用多跳路由將數(shù)據(jù)傳送給Sink節(jié)點(diǎn)。

④建立多跳路徑的過程如下:在鄰居節(jié)點(diǎn)中選擇權(quán)值最大的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn),如式(9)。

(9)

式中:Ei為節(jié)點(diǎn)被選為中繼節(jié)點(diǎn)的剩余能量,d(vi,vj)為簇頭節(jié)點(diǎn)M和中繼節(jié)點(diǎn)N之間的距離,d(vj,DS)為中繼節(jié)點(diǎn)到Sink節(jié)點(diǎn)的距離,(C(Agenti,tj))為節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的自信度。由cost計(jì)算公式可知,當(dāng)距離和剩余能量相同時(shí),自信度越大越容易成為下一跳節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)到Sink節(jié)點(diǎn)的距離小于通信半徑或者鄰居節(jié)點(diǎn)集合中沒有任何節(jié)點(diǎn)時(shí),則節(jié)點(diǎn)直接將數(shù)據(jù)發(fā)送到Sink節(jié)點(diǎn)。

2.4 EACMRA算法偽代碼

選擇候選簇頭和確定最終簇頭的偽代碼如下:

Ifrandom

Elseifrandom>T(n)//若隨機(jī)數(shù)大于T(n),節(jié)點(diǎn)為普通節(jié)點(diǎn)

Ifstate==Vi//標(biāo)記當(dāng)前候選簇頭的自信度

C[]theaverageconfidence//標(biāo)識各節(jié)點(diǎn)的自信度

BroadcastComepete_Msg//廣播信息

//鄰居集合里面選擇自信度大的節(jié)點(diǎn)作為最終的簇頭節(jié)點(diǎn)

For(j=0;j

ifC[j]>C(Vi)//選擇自信度最小的節(jié)點(diǎn)為下一跳節(jié)點(diǎn)

final_CH=Vj

elsefinal_CH=Vi

BroadcastRealCH_Msg//廣播簇頭信息

3 仿真實(shí)驗(yàn)及性能分析

本文使用Matlab作為模擬實(shí)驗(yàn)平臺,對EACMRA算法進(jìn)行仿真,分別從網(wǎng)絡(luò)生存周期和網(wǎng)絡(luò)能量消耗方面來評價(jià)EACMRA算法的性能。假設(shè)在100m×100m的網(wǎng)絡(luò)中隨機(jī)分布100個(gè)節(jié)點(diǎn),Sink節(jié)點(diǎn)位置為(50,150)。由文獻(xiàn)[8]仿真結(jié)果可知,當(dāng)傳感器節(jié)點(diǎn)為100,在100m×100m的區(qū)域里對應(yīng)簇頭個(gè)數(shù)為5時(shí),每輪消耗能量最少,網(wǎng)絡(luò)生命周期最長。所以本算法中規(guī)定簇頭選擇概率閾值為P1為0.05。定義各個(gè)節(jié)點(diǎn)的初始自信度為1,每個(gè)節(jié)點(diǎn)擁有相同的初始能量,仿真過程中的參數(shù)配置如表2。

表2 仿真參數(shù)設(shè)置

本文在相同場景下運(yùn)行LEACH、ASCH和EACMRA,通過改進(jìn)協(xié)議以平衡節(jié)點(diǎn)能量消耗、延長網(wǎng)絡(luò)存活時(shí)間及提高整體網(wǎng)絡(luò)能量效率為主要目標(biāo)。在模擬環(huán)境中隨機(jī)分布的100個(gè)節(jié)點(diǎn)如圖1所示。

圖1 隨機(jī)分布節(jié)點(diǎn)

根據(jù)式(2)選出候選簇頭,通過式(8)確定出最后的簇頭節(jié)點(diǎn),成功傳輸數(shù)據(jù)后相應(yīng)的增加該節(jié)點(diǎn)的自信度。

3.1 存活節(jié)點(diǎn)比較

圖2(a)為LEACH算法運(yùn)行一段時(shí)間后節(jié)點(diǎn)的狀態(tài)圖,紅色代表已經(jīng)死亡的節(jié)點(diǎn),o為正常能量節(jié)點(diǎn),十字表示高能量節(jié)點(diǎn)。圖2(b)為EACMRA算法運(yùn)行1 500輪后節(jié)點(diǎn)的存活情況。從圖中可以看出,LEACH在運(yùn)行了1 500輪之后存活節(jié)點(diǎn)數(shù)很少,而EACMRA算法中存活節(jié)點(diǎn)數(shù)很多。

圖2 節(jié)點(diǎn)的狀態(tài)圖

出現(xiàn)此情況主要是因?yàn)镋ACMRA算法在選擇簇頭節(jié)點(diǎn)時(shí)通過分步操作,先選出候選簇頭,在候選簇頭中選擇出自信度大的節(jié)點(diǎn)作為最終簇頭,此算法中添加了節(jié)點(diǎn)的自信度,保證了簇頭節(jié)點(diǎn)的傳輸成功率,減少了在LEACH算法中因?yàn)殡S機(jī)產(chǎn)生簇頭可能導(dǎo)致的數(shù)據(jù)重傳的概率,進(jìn)而減少了節(jié)點(diǎn)間的通信開銷,延長了節(jié)點(diǎn)的壽命。

圖3為網(wǎng)絡(luò)剩余存活節(jié)點(diǎn)情況。LEACH在第943輪時(shí)出現(xiàn)死亡節(jié)點(diǎn),ASCH協(xié)議在950輪出現(xiàn)死亡節(jié)點(diǎn),相同條件下EACMRA算法死亡節(jié)點(diǎn)出現(xiàn)在第1 533輪,EACMRA算法從節(jié)點(diǎn)死亡到全部死亡的時(shí)間都往后延續(xù)了,而LEACH和ASCH算法節(jié)點(diǎn)死亡發(fā)生比較集中,這主要是因?yàn)樵诖仡^選擇時(shí)容易出現(xiàn)簇頭節(jié)點(diǎn)集中在網(wǎng)絡(luò)某一區(qū)域的現(xiàn)象,導(dǎo)致該區(qū)域的節(jié)點(diǎn)在很短的時(shí)間內(nèi)能耗過高,逐漸死亡,后面選擇出來的簇頭將會(huì)出現(xiàn)遠(yuǎn)離Sink節(jié)點(diǎn)的節(jié)點(diǎn)作為簇頭,這樣在傳輸過程中能耗大,節(jié)點(diǎn)死亡快。改進(jìn)協(xié)議EACMRA優(yōu)于LEACH協(xié)議和ASCH協(xié)議的地方在于在簇頭選擇過程中加入了其他元素,避免了簇頭節(jié)點(diǎn)集中的情況。

圖3 存活節(jié)點(diǎn)數(shù)示意圖

圖4 網(wǎng)絡(luò)剩余能量統(tǒng)計(jì)圖

3.2 剩余能量比較

圖4為網(wǎng)絡(luò)的剩余能量示意圖。雖然引入Agent的自信度,在每次計(jì)算通信代價(jià)時(shí)會(huì)帶來了一定量的計(jì)算開銷,但EACMRA算法節(jié)點(diǎn)總能量消耗速率低于LEACH算法和ASCH算法。EACMRA算法優(yōu)勢在于選擇候選簇頭時(shí),隨時(shí)更新節(jié)點(diǎn)的自信度,緩解了LEACH在選擇候選簇頭時(shí)的盲目性,減少了由于隨機(jī)選擇的簇頭節(jié)點(diǎn)最終不能成功傳輸數(shù)據(jù)導(dǎo)致的數(shù)據(jù)重傳,和二次選擇簇頭節(jié)點(diǎn)的通信開銷。由于數(shù)據(jù)傳輸失敗導(dǎo)致的簇頭節(jié)點(diǎn)再次選擇,以及數(shù)據(jù)傳輸帶來的能量消耗將遠(yuǎn)遠(yuǎn)大于每次簇頭節(jié)點(diǎn)進(jìn)行自身自信度修改的通信代價(jià)。

圖4中,LEACH算法和ASCH算法在1 500輪之前能量消耗情況基本相同,而EACMRA算法剩余能量明顯高,這主要是由于EACMRA算法中減少了簇頭節(jié)點(diǎn)的重新選擇,進(jìn)而減少能量消耗。

文獻(xiàn)[12]的CHCI算法和EACMRA算法有著類似的思想,CHCI算法在選擇主要簇頭后,在每個(gè)簇里再進(jìn)行一次次要簇頭選擇,以此來降低多次選擇簇頭的能耗,但是次要簇頭的選擇能耗遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)自信度的修改所需要的能耗,在相同的情況下,EACMRA算法更加節(jié)約能耗,能有效的延長網(wǎng)絡(luò)生存時(shí)間。

EACMRA算法和CMRAOL[16]算法在設(shè)計(jì)上有相同之處,EACMRA算法在CMRAOL算法的基礎(chǔ)上添加了節(jié)點(diǎn)的自信度,主要是用來避免當(dāng)出現(xiàn)相同的T(n)時(shí),如何選擇具體某個(gè)節(jié)點(diǎn)作為簇頭節(jié)點(diǎn),EACMRA算法較CMRAOL算法在每一次簇頭選擇的過程中增加的能耗為上一次簇頭節(jié)點(diǎn)自信度的動(dòng)態(tài)修改,而由此減少在CMRAOL算法中由于簇頭節(jié)點(diǎn)傳輸失誤帶來的二次簇頭選擇所產(chǎn)生的能耗,增加的能耗遠(yuǎn)遠(yuǎn)低于二次簇頭選擇所產(chǎn)生的能耗。

4 結(jié)束語

本文針對以往分簇路由協(xié)議的不足,在無線傳感器網(wǎng)絡(luò)中提出一種能量高效的EACMRA分簇算法,引入了Agent的心智系數(shù),并詳細(xì)闡述了候選簇頭和最終簇頭的確定過程。在簇建立階段,算法賦予每個(gè)節(jié)點(diǎn)相同的自信度,根據(jù)每個(gè)節(jié)點(diǎn)參與的情況動(dòng)態(tài)修改自信度,自信度在反過來參與到每次簇頭的重新選擇過程。在候選簇頭節(jié)點(diǎn)中選擇自信度大的節(jié)點(diǎn)作為最終簇頭節(jié)點(diǎn),通過在MATLAB下進(jìn)行仿真測試,文章分析了EACMRA算法中各個(gè)參數(shù)的作用及其對算法整體性能的影響。理論分析和仿真實(shí)驗(yàn)表明EACMRA較LEACH協(xié)議和ASCH協(xié)議延長了網(wǎng)絡(luò)壽命,減少了網(wǎng)絡(luò)中能量的消耗,更好地保證監(jiān)測覆蓋度。

[1] 劉明,曹建農(nóng),陳貴海,等. EADEEG:能量感知的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議[J]. 軟件學(xué)報(bào),2007,18(5):1092-1109.

[2] Akl R,Sawant U. Grid-Based Coordinated Routing in Wireless Sensor Networks//Procof the Consumer Communications and Networking Conference[C]//Piscataway,NJ:IEEE,2007:860-864.

[3] 彭鐸,黎鎖平,楊喜娟. 一種能量高校的無線案傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J]. 傳感技術(shù)學(xué)報(bào),2014,27(12):1687-1691.

[4] Heinzelman W,Chandrakasan A,Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks[C]//Proofs the 33rd Conf on System Sciences. Piscataway. NJ:IEEE,2000:3005-3014.

[5] 周新蓮,吳敏,徐建波. BPEC_無線傳感器網(wǎng)絡(luò)中一種能量感知的分布式分簇算法[J]. 計(jì)算機(jī)研究與發(fā)展,2009:46(5):723-730.

[6] 張文梅,廖福保. 改進(jìn)的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(5):739-743.

[7] 齊迎迎,禹繼國,王楠楠. 無線傳感器網(wǎng)絡(luò)的節(jié)能分布式分簇算法[J]. 計(jì)算機(jī)工程,2011:37(3):83-86.

[8] 李悅,孫力娟,王汝傳,等. 一種改進(jìn)的無線傳感器網(wǎng)絡(luò)LEACH算法[J]. 計(jì)算機(jī)研究與發(fā)展,2011:48(z2):131-134.

[9] 陳東海,李長庚. 基于簇頭功能分化的無線傳感器網(wǎng)絡(luò)成簇算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(2):244-248.

[10] 常鐵原,王彤,朱桂峰. 一種改進(jìn)的簇頭成鏈路由協(xié)議[J]. 計(jì)算機(jī)工程,2012:2(3):85-87.

[11] Sun Yanqing,Peng Jian,Liu Tang,et al. Uneven Clustering Routing Protocol Based on Dynamic Partition for Wireless Sensor Network[J]. Journal on Communication,2014,35(1):198-206.

[12] 康琳,董增壽. 基于簇頭分級的改進(jìn)的非均勻分簇算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(12):1841-1845.

[13] 程文娟,穆自立,唐昊. 基于帶Mobile Agent的無線傳感器網(wǎng)絡(luò)的分簇算法[J]. 計(jì)算機(jī)研究與發(fā)展,2010,47(Suppl):88-91.

[14] 龍際珍,陳沅濤,鄧冬梅. 基于LEACH協(xié)議的助理簇頭分簇算法[J]. 計(jì)算機(jī)工程,2011,37(7):103-015.

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

[16] 陳炳才,么華卓,楊明川,等. 一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議[J]. 傳感技術(shù)學(xué)報(bào),2014,27(3):373-377.

An Inter-Cluster Multi-Hop Routing Protocol Based on the Confidence of Agen*

JIANYumei1*,ZHANGHanfei2,GAOFei1,RUANLinjie1,ZHANGDengzhu1,HONGQingjun1,ZHAOXudong1

(1.School of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China;2.Huaiyin Normal University,Huaiyin Jiangsu 223300,China)

In order to balance energy consumption of wireless sensor networks,and prolong survival time of the networks,presents an Inter-Cluster Multi-Hop Routing Protocol based on the confidence of Agent. This paper introduces residual energy,initial energy of the sensor nodes and confidence as three important components to adjusts the size of the sensor nodes random numbers. In inter-cluster communication process,cluster head nodes communicate with Sink node by single-hop and multi-hop,which considers the residual energy of cluster head nodes,the distance between cluster head node and Sink node,the confidence of cluster head node. Before re-elected cluster head,it dynamically modified the confidence. The result of experiment shows that,compared to LEACH protocol and ASCH protocol,the new protocol processed can prolong the life wireless sensor network.

Wireless Sensor Network(WSN);non-uniform clustering;the confidence of Agent

簡玉梅(1987-),女,碩士,實(shí)驗(yàn)師,研究方向?yàn)闊o線傳感器網(wǎng)絡(luò),智能運(yùn)算,jianyumei0628@126.com;張韓飛(1986-),男,碩士,中級,研究方向?yàn)槲锫?lián)網(wǎng)技術(shù),無線傳感器網(wǎng)絡(luò),zhanghanfei2006@163.com。

項(xiàng)目來源:上海市教育委員會(huì)科研創(chuàng)新項(xiàng)目重點(diǎn)項(xiàng)目(14ZZ156)

2016-03-17 修改日期:2016-08-29

TP393

A

1004-1699(2017)01-0126-07

C:7230

10.3969/j.issn.1004-1699.2017.01.023