移動傳感網(wǎng)社區(qū)間能量均衡路由算法

高秋田，楊文忠,，張振宇,，石 研，李雙雙

(1.新疆大學 軟件學院，烏魯木齊 830008； 2.新疆大學 信息科學與工程學院，烏魯木齊 830046) (*通信作者電子郵箱ywz_xy@163.com)

移動傳感網(wǎng)社區(qū)間能量均衡路由算法

高秋田1，楊文忠1,2*，張振宇1,2，石 研1，李雙雙2

(1.新疆大學 軟件學院，烏魯木齊 830008； 2.新疆大學 信息科學與工程學院，烏魯木齊 830046) (*通信作者電子郵箱ywz_xy@163.com)

在資源受限的無線移動傳感器網(wǎng)絡(luò)(MWSN)中設(shè)計能效路由是一個挑戰(zhàn)性難題。針對移動傳感器網(wǎng)絡(luò)中社區(qū)間路由節(jié)點能量消耗過快的問題，提出了一種社區(qū)間能量均衡路由算法(ERAI)。設(shè)計了一個新的基于節(jié)點的剩余能量以及相遇可能性的轉(zhuǎn)發(fā)能力路由度量FC。利用此度量FC和相遇節(jié)點的去向信息選擇中繼節(jié)點來轉(zhuǎn)發(fā)消息。實驗數(shù)據(jù)顯示，ERAI路由算法在首個節(jié)點消亡時間上與Epidemic和PROPHET路由算法相比分別推遲了12.6%～15.6%和4.5%～8.3%，且節(jié)點剩余能量均方差小于Epidemic和PROPHET路由算法。實驗結(jié)果表明，ERAI在一定程度上均衡了各節(jié)點的能耗，延長了網(wǎng)絡(luò)的生命周期。

移動傳感網(wǎng)；社區(qū)；能量均衡；相遇概率；生命周期

0 引言

近年來，隨著一些實際應(yīng)用的需要，如野生動物生活規(guī)律監(jiān)測[1]、牧區(qū)牲畜監(jiān)測、移動目標跟蹤[2]、城市車聯(lián)網(wǎng)等，由這些移動物體攜帶傳感器在移動的過程中常常會出現(xiàn)“大世界小世界”[3]的聚集現(xiàn)象，從而形成多個偶有聯(lián)系的區(qū)域(社區(qū))。傳感器節(jié)點擁有的能量有限且能量消耗完便無法參與數(shù)據(jù)收集、傳輸?shù)冗^程。如何延長網(wǎng)絡(luò)生命周期一直是無線移動傳感器網(wǎng)絡(luò)(Mobile Wireless Sensor Network, MWSN)研究的難題。

層次路由通過分簇在一定程度上緩解了節(jié)點能耗不均衡的問題。文獻[4]結(jié)合改進的粒子群聚類算法與群集間路由算法，提出了一種自適應(yīng)高能效分簇路由協(xié)議(Adaptive Energy-Efficient Clustering Routing Protocol, AECRP)。在初始化階段，根據(jù)節(jié)點能量、簇內(nèi)分布和簇的分布情況提出了基于粒子群算法的分簇方法；在穩(wěn)定階段傳輸數(shù)據(jù)。為了避免靠近基站的簇能量消耗過快，AECRP為基站附近的簇首設(shè)置了能量閾值E，若此類簇首剩余能量低于E時不再轉(zhuǎn)發(fā)任何消息。文獻[5]結(jié)合混合壓縮感知(Compressed Sensing, CS)理論提出了基于混合CS的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)六邊形格狀優(yōu)化分簇路由算法：首先建立基于混合CS的六邊形格狀WSN分簇模型；然后對全網(wǎng)數(shù)據(jù)傳輸次數(shù)進行量化分析，并求解混合CS的WSN六邊形格狀最優(yōu)分簇半徑；最后實現(xiàn)基于混合CS的WSN六邊形格狀優(yōu)化分簇路由算法。層次路由雖在一定程度上緩解了節(jié)點能耗不均衡的問題，但并未考慮節(jié)點的移動性。

分簇路由大都假設(shè)節(jié)點的位置固定，并未考慮節(jié)點的移動性。為了實現(xiàn)移動節(jié)點間的數(shù)據(jù)傳輸，文獻[6]提出了傳染病路由(Epidemic Routing)，其采用洪泛的轉(zhuǎn)發(fā)機制。在節(jié)點緩存和能量充足的場景下，Epidemic路由可達到較好的網(wǎng)絡(luò)性能，但在能量受限的移動傳感器網(wǎng)絡(luò)中，泛洪轉(zhuǎn)發(fā)策略會使節(jié)點能量消耗太快。之后出現(xiàn)了n-Epidemic[7]、能量感知的Epidemic路由(Energy-Aware Epidemic Routing, EAER)[8]、Spray and Focus[9]、使用歷史相遇數(shù)據(jù)和傳遞性的概率路由協(xié)議(Probabilistic ROuting Protocol using History of Encounters and Transitivity, PROPHET)[10]等，但文獻[8-10]僅僅在Epidemic路由的基礎(chǔ)上調(diào)整消息副本數(shù)，并沒有很好地解決節(jié)點能耗不均衡的問題。

BUBBLE RAP[11]使用節(jié)點的活躍度建立全局和社區(qū)內(nèi)部的排序表，消息攜帶者總是選擇排名靠前的節(jié)點來轉(zhuǎn)發(fā)消息。由于BUBBLE RAP采用單拷貝，消息的延時較長，若某節(jié)點只在社區(qū)內(nèi)非常活躍，而在整個系統(tǒng)排名時必然排在前面，但它只適合社區(qū)內(nèi)部的數(shù)據(jù)轉(zhuǎn)發(fā)，并不適合社區(qū)間的數(shù)據(jù)轉(zhuǎn)發(fā)。IFR(Integrating Forwarding and Replication)[12]利用節(jié)點的中心度將網(wǎng)絡(luò)中的節(jié)點劃分為若干社區(qū)。社區(qū)間采用多拷貝的數(shù)據(jù)轉(zhuǎn)發(fā)方法；社區(qū)內(nèi)采用Epidemic算法。若節(jié)點個數(shù)增大，消息副本數(shù)將迅速增多，節(jié)點的能量也會消耗殆盡。文獻[13]提出了基于友誼關(guān)系的移動社會網(wǎng)絡(luò)路由(Friendship Based Routing, FBR)，利用節(jié)點所具有的多個社會特征提出了社會壓力(Social Pressure Metric, SPM)和相對社會壓力(Relative Social Pressure Metric, RSPM)兩個度量指標。根據(jù)SPM和RSPM構(gòu)造友誼社區(qū)，采用消息的單副本傳輸策略。若網(wǎng)絡(luò)很龐大，F(xiàn)BR算法的交付率不是最優(yōu)的。為了提高路由的效率，文獻[14]提出了基于社交鏈路感知路由(Social Link Awareness Based Routing, SLABR)，在社區(qū)間采用單拷貝傳輸機制，總是傳輸給社會關(guān)系強且與目的節(jié)點屬于同一社區(qū)的節(jié)點；社區(qū)內(nèi)使用多副本二進制擴散的機制。雖然使用二進制轉(zhuǎn)發(fā)機制有效地控制了副本的數(shù)量，但是沒有考慮社區(qū)內(nèi)節(jié)點關(guān)系的差異性和節(jié)點當前的剩余能量。以上算法大都選擇排名靠前的節(jié)點作為中繼節(jié)點，必然加快這部分節(jié)點的能量消耗。吳大鵬等[15]利用消息擴散程度和節(jié)點當前剩余能量，并結(jié)合節(jié)點相遇概率預(yù)測方法，提出了能量有效的副本分布狀態(tài)感知路由機制(Energy Efficient Copy Distributing status aware Routing mechanism, EECDR)，分布式地選擇中繼節(jié)點。隨之楊鵬等[16]提出了節(jié)點剩余能量均衡路由(Node Residual Energy Balanced routing, NREB)，根據(jù)節(jié)點的活躍程度以及當前剩余能量選擇轉(zhuǎn)發(fā)節(jié)點。

為了解決移動傳感器網(wǎng)絡(luò)社區(qū)間路由節(jié)點能量消耗過快的問題，本文提出了一種社區(qū)間能量均衡路由算法(Energy-balanced Routing Algorithm for Inter-community, ERAI)。ERAI將消息傳輸分為兩個階段：第一階段，社區(qū)間傳輸，從相遇節(jié)點中首先選擇下一時刻前往社區(qū)與消息的目的社區(qū)相同的節(jié)點，然后綜合考慮節(jié)點的剩余能量以及與目的社區(qū)相遇情況選擇轉(zhuǎn)發(fā)節(jié)點，不僅均衡了節(jié)點的能量消耗，而且縮短了延遲；第二階段，社區(qū)內(nèi)傳輸，綜合考慮節(jié)點的剩余能量及社區(qū)內(nèi)節(jié)點間的相遇情況選擇轉(zhuǎn)發(fā)節(jié)點，在均衡節(jié)點能耗的同時延長了網(wǎng)絡(luò)生命周期。

1 社區(qū)與能耗模型

本章主要介紹了兩部分：社區(qū)模型和能量消耗模型。

1.1 社區(qū)模型

傳感器節(jié)點由移動實體攜帶在移動的過程中常常會出現(xiàn)“大世界小世界”的聚集現(xiàn)象，從而形成多個不同的、偶爾有聯(lián)系的區(qū)域，本文稱這樣的區(qū)域為社區(qū)。社區(qū)模型作如下假設(shè)：

1)本文中的社區(qū)是節(jié)點在移動過程中形成的。

2)網(wǎng)絡(luò)中的節(jié)點都是移動的，且每個節(jié)點x有唯一的ID，并且只屬于一個社區(qū)，表示為Cx。

3)所有節(jié)點的初始能量和緩存大小都是相同的。設(shè)置一個能量閾值Ethr，當節(jié)點剩余能量小于Ethr時，節(jié)點不再參與消息傳輸。

4)所有節(jié)點之間都是相互信任的，相遇時彼此交換去向信息。

5)所有節(jié)點都能感知自己的剩余能量。

6)消息攜帶節(jié)點只與其通信范圍內(nèi)的節(jié)點交換消息。

7)社區(qū)間不需要擺渡節(jié)點，社區(qū)之間是通過往返于社區(qū)間的節(jié)點來交換消息的。

1.2 能耗模型

傳感器節(jié)點一般由感知單元、處理單元(包括處理器與存儲器)和無線通信單元組成，其中無線通信單元[17]是主要的耗能單元。本文使用文獻[18]提出的一階無線通信能量模型如圖1，忽略節(jié)點在感知、計算、存儲等過程中的能量消耗，主要考慮發(fā)送能耗、接收能耗與探測能耗。

圖1 一階無線通信模型

由此可知，傳輸距離為d，發(fā)送kbit的消息，所消耗的能量如式(1)所示：

(1)

其中：d0為距離閾值，Eelec表示發(fā)送或接收每比特數(shù)據(jù)時的能量消耗，εfsd2和εmpd4是發(fā)送每比特數(shù)據(jù)放大器的能量消耗。

由于移動傳感網(wǎng)利用節(jié)點移動帶來的相遇(在彼此通信范圍內(nèi))機會傳輸數(shù)據(jù)，距離較短，因此本文僅考慮d

節(jié)點接收kbit的消息所消耗的能量如式(2)所示：

ERx(k)=ERx-elec(k)=kEelec(k)

(2)

中繼節(jié)點轉(zhuǎn)發(fā)kbit的消息，首先要接收kbit的消息，然后將收到的消息發(fā)送出去，因此，轉(zhuǎn)發(fā)kbit的消息所消耗的能量如式(3)所示：

ERTx(k)=ETx(k,d)+ERx(k)=kEelec+kεfsd2+kEelec= 2kEelec+kεfsd2

(3)

節(jié)點探測能耗是指節(jié)點在移動的過程中探測周圍以發(fā)現(xiàn)其與哪些節(jié)點相遇所消耗的能量[15]。節(jié)點在移動的過程中周期性地廣播探測分組(DEtection GRouping, DEGR)(如圖2(a)所示)，收到DEGR分組的節(jié)點回復(fù)確認分組(COnfirm GRouping, COGR)(如圖2(b)所示)。令節(jié)點發(fā)送DEGR和接收COGR所消耗能量相同，設(shè)為ed，節(jié)點的探測周期為Tc，ci為第i次探測接收COGR的個數(shù)。在t時刻，移動節(jié)點廣播DEGR的次數(shù)是一定的，接收COGR的個數(shù)越多，Ede值越大，則Ede的計算公式如式(4)所示。

圖2 兩種分組的消息格式

圖2分組格式中各字段的含義如下：NOP表示協(xié)議版本信息；Nid為發(fā)送節(jié)點ID；CNid為發(fā)送節(jié)點所屬社區(qū)；Eres為發(fā)送節(jié)點剩余能量；Cgoi為發(fā)送節(jié)點即將前往社區(qū)；Nb廣播ID；DNid,Cid表示目的節(jié)點為Nid，所屬社區(qū)為Cid。

(4)

(5)

(6)

其中Einit為節(jié)點的初始能量。

2 ERAI路由算法描述

移動傳感網(wǎng)中節(jié)點間的相遇總是短暫的，利用節(jié)點間短暫的接觸特性轉(zhuǎn)發(fā)消息。本章主要從以下4部分描述ERAI路由算法：路由度量指標、社區(qū)間消息傳輸、社區(qū)內(nèi)消息傳輸和ERAI流程。

2.1 路由度量指標

根據(jù)節(jié)點的相遇信息和當前擁有的能量提出了轉(zhuǎn)發(fā)能力(Forwarding Capacity, FC)，即作為中繼節(jié)點轉(zhuǎn)發(fā)消息的能力。另外相遇概率(Encounter Probability, EP)表示節(jié)點與社區(qū)或社區(qū)內(nèi)的節(jié)點間聯(lián)系強度。

2.1.1 相遇概率EP

1)節(jié)點與社區(qū)的相遇概率。

在周期T內(nèi)，t時刻節(jié)點x與社區(qū)Cy內(nèi)的節(jié)點相遇，EPt(x,Cy)的計算過程如式(7)所示：

EPt(x,Cy)=EPt-1(x,Cy)+(1-EPt-1(x,Cy))/Δt

(7)

其中：Δt表示在周期T內(nèi)，節(jié)點x與社區(qū)Cy內(nèi)的節(jié)點相遇的時間間隔，即Δt=tc-tc-1，tc是當前相遇時刻，tc-1為最近一次相遇時刻。

若在周期T內(nèi)節(jié)點x與社區(qū)Cy內(nèi)任何節(jié)點都沒有相遇，EPt(x,Cy)的值也會隨著Δt的增大而減少，如式(8)所示：

EPt(x,Cy) =EPt-1(x,Cy)*λk

(8)

其中，λ∈[0,1]，k=?Δt/T」，Δt=t-tc-1，t為當前時刻，tc-1為最近一次相遇時刻。

2)社區(qū)內(nèi)節(jié)點間的相遇概率。

同一社區(qū)內(nèi)的節(jié)點x與y相遇，更新概率度量值EPt(x,y)，如式(9)所示：

EPt(x,y)=EPt-1(x,y)+(1-EPt-1(x,y))/Δt

(9)

其中，Δt表示在周期T內(nèi)，節(jié)點x與節(jié)點y前后兩次相遇時間間隔，即Δt=tc-tc-1，tc是當前相遇時刻。

若在周期T內(nèi)節(jié)點x與y沒有相遇，EPt(x,y)將隨著Δt的增大而減小，具體計算公式如式(10)所示：

EPt(x,y) =EPt-1(x,y)*λk

(10)

其中，λ∈[0,1]，k=?Δt/T」，Δt=t-tc-1，t為當前時刻，tc-1為節(jié)點x與節(jié)點y最近一次相遇時刻。

2.1.2 轉(zhuǎn)發(fā)能力FC

(11)

根據(jù)節(jié)點相遇信息和節(jié)點當前擁有的能量計算FC。節(jié)點x與社區(qū)Cy的轉(zhuǎn)發(fā)能力FC(x,Cy)的計算公式如式(12)所示；在相同社區(qū)內(nèi)，節(jié)點x與節(jié)點y的FC(x,y)計算公式如式(13)所示：

(12)

(13)

其中，β為權(quán)重因子，β∈(0,1)。

2.2 社區(qū)間消息傳輸

消息攜帶者與目的節(jié)點隸屬于不同的社區(qū)，消息成功投遞到目的節(jié)點所在社區(qū)是社區(qū)間消息傳輸?shù)年P(guān)鍵。當消息攜帶者與目的節(jié)點的社區(qū)不同時，將執(zhí)行社區(qū)間消息傳輸，具體步驟如下。

步驟1 節(jié)點x攜帶消息m移動，目的節(jié)點為d。在t時刻與節(jié)點xi(i=1,2,…,n)相遇。

步驟2 節(jié)點xi中是否有前往Cd社區(qū)的，若有，跳轉(zhuǎn)到步驟3；否則，跳轉(zhuǎn)到步驟1。

步驟3 相遇節(jié)點中對前往Cd社區(qū)的節(jié)點計算FC(xi,Cd)，若max(FC(xi,Cd))>FC(x,Cd)，節(jié)點x將消息m轉(zhuǎn)發(fā)給xi；否則，跳轉(zhuǎn)到步驟1。

ERAI：社區(qū)間消息傳輸。

當節(jié)點x攜帶消息m(目的節(jié)點d)與節(jié)點xi(前往社區(qū)Cgoi)相遇時Begin

1)

for eachxido

2)

ifCgoi=Cdthen

3)

if max(FC(xi,Cd))>FC(x,Cd) then

4)

x.SendMessageTo(xi)

5)

end if

6)

end if

7)

end for

End

ERAI路由算法中社區(qū)間消息傳輸過程的時間開銷主要是FC的計算開銷。根據(jù)FC計算過程，節(jié)點需分別計算節(jié)點與目標社區(qū)的相遇概率以及節(jié)點當前擁有的能量。對于節(jié)點與目標社區(qū)相遇概率的更新，需計算前后兩次相遇的時間間隔，時間復(fù)雜度為O(1)；同理，在更新節(jié)點當前剩余能量中，節(jié)點需計算網(wǎng)絡(luò)從運行到當前時間發(fā)送與接收消息的總數(shù)，時間復(fù)雜度為O(1)。由于節(jié)點FC是由節(jié)點與目標社區(qū)的相遇概率與當前剩余能量線性相加而得，算法中語句執(zhí)行次數(shù)為常數(shù)，因此ERAI執(zhí)行一次社區(qū)間消息傳輸?shù)臅r間復(fù)雜度為O(1)，轉(zhuǎn)發(fā)n個消息的時間復(fù)雜度為O(n)。由此看出，ERAI具有較高的執(zhí)行效率。社區(qū)間消息傳輸算法能夠正確執(zhí)行社區(qū)間的消息傳輸。

2.3 社區(qū)內(nèi)消息傳輸

若消息進入目的社區(qū)，節(jié)點將實施社區(qū)內(nèi)消息傳輸。

假設(shè)在社區(qū)內(nèi)，節(jié)點x攜帶消息m，目標節(jié)點為d，且Cx=Cd。在t時刻，節(jié)點x與xi(i=1,2,…,n)相遇，消息傳輸過程如下所示：

1)若xi=d，即相遇節(jié)點中存在目標節(jié)點d，則節(jié)點x將消息m轉(zhuǎn)發(fā)給節(jié)點xi，并廣播消息m的ACK。

2)若xi≠d且max(FC(xi,d))>FC(x,d)，則節(jié)點x將消息m直接轉(zhuǎn)發(fā)給節(jié)點xi，并將m從緩存中刪除；否則，節(jié)點x節(jié)點消息m繼續(xù)移動，直到下一個相遇機會。

ERAI：社區(qū)內(nèi)消息傳輸。

當節(jié)點x攜帶消息m(目的節(jié)點d)與節(jié)點xi相遇 Begin

1)

for eachxido

2)

ifxi==dthen

3)

x.SendMessageTo(xi)

4)

x.deleteMessage

5)

else

6)

if max(FC(xi,d))>FC(x,d) then

7)

x.SendMessageTo(xi)

8)

x.deleteMessage

9)

end if

10)

end if

11)

end for

End

ERAI路由算法中社區(qū)內(nèi)消息傳輸過程的時間開銷主要是FC的開銷。根據(jù)節(jié)點FC計算過程，節(jié)點需分別計算節(jié)點與目的節(jié)點的相遇概率以及自身當前剩余能量。對于節(jié)點與目的節(jié)點相遇概率的更新，需計算前后兩次相遇的時間間隔，時間復(fù)雜度為O(1)；同理，在更新節(jié)點當前剩余能量中，節(jié)點需計算網(wǎng)絡(luò)從運行到當前時間發(fā)送與接收消息的總數(shù)，時間復(fù)雜度為O(1)。由于節(jié)點FC是由節(jié)點與目的節(jié)點的相遇概率與當前剩余能量線性相加而得，算法中語句執(zhí)行次數(shù)為常數(shù)，因此ERAI執(zhí)行一次社區(qū)內(nèi)消息傳輸?shù)臅r間復(fù)雜度為O(1)，轉(zhuǎn)發(fā)n個消息的時間復(fù)雜度為O(n)。由此看出，ERAI具有較高的執(zhí)行效率。社區(qū)內(nèi)消息傳輸算法能夠正確執(zhí)行社區(qū)內(nèi)的消息傳輸。

2.4 ERAI流程

ERAI路由算法分為社區(qū)間和社區(qū)內(nèi)消息傳輸。節(jié)點s攜帶消息m移動，首先比較Cs與Cm是否屬于同一社區(qū)，若屬于同一社區(qū)將執(zhí)行社區(qū)間消息傳輸過程，否則執(zhí)行社區(qū)內(nèi)消息傳輸過程。ERAI流程如圖3所示。

3 仿真結(jié)果與性能分析

本文主要從網(wǎng)絡(luò)中首個節(jié)點消亡時間、節(jié)點剩余能量均方差(Residual Energy Mean Square Error)、節(jié)點消亡數(shù)以及數(shù)據(jù)包交付率(Packet Delivery Ratio, PDR)四個指標評估ERAI路由算法的性能。節(jié)點剩余能量均方差與PDR的計算公式如式(14)～(16)所示。

節(jié)點剩余能量平均值(average residual energy)：

(14)

節(jié)點剩余能量均方差：

(15)

數(shù)據(jù)包交付率(PDR)：

(16)

圖3 ERAI的流程

3.1 仿真環(huán)境設(shè)置

本文采用ONE(Opportunistic Network Environment)[19]對ERAI的性能進行仿真，并和機會網(wǎng)絡(luò)中Epidemic和PROPHET路由進行了對比。假定場景中有300個移動節(jié)點，在4 500 m×3 400 m區(qū)域內(nèi)移動。假設(shè)300個節(jié)點被分為8個組(社區(qū))分別用C1～C8表示，每個社區(qū)的節(jié)點數(shù)為[30,90]。每個節(jié)點的通信半徑為50 m，消息的存活時間(Time To Live, TTL)為3 600 s。由于實驗需要節(jié)點間相遇的歷史信息，仿真開始時先進行了900 s的預(yù)處理過程。具體仿真場景設(shè)置如表1所示。

表1 仿真場景設(shè)置

3.2 實驗結(jié)果與分析

1)首個節(jié)點消亡時間比較。

圖4所示，在相同初始能量下，ERAI路由算法中首個節(jié)點消亡時間最遲。由于Epidemic采用洪泛轉(zhuǎn)發(fā)策略，大量相同的數(shù)據(jù)副本重復(fù)擴散將導(dǎo)致節(jié)點能量消耗速度提高，而PROPHET路由機制總是將消息傳輸給概率值高的節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)，一直使用概率值高的節(jié)點必然使這部分節(jié)點能量消耗速度高于其他節(jié)點，提高了這部分節(jié)點消亡速度。而ERAI路由算法考慮了節(jié)點剩余能量，避免使用剩余能量較低的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，延遲了節(jié)點消亡時間，從而延長網(wǎng)絡(luò)的生命周期。ERAI路由算法下網(wǎng)絡(luò)中首個節(jié)點消亡時間相比Epidemic與PROPHET路由算法分別延遲了12.6%～15.6%和4.5%～8.3%。

圖4 首個節(jié)點消亡時間比較

2)節(jié)點剩余能量均方差比較。

圖5顯示，在仿真時間相同時ERAI的節(jié)點剩余能量均方差值最小，說明節(jié)點剩余能量集中。由于ERAI充分考慮了節(jié)點的剩余能量，避免能量低的節(jié)點過早失效，與Epidemic和PROPHET相比ERAI中各節(jié)點的能量消耗較均衡。

圖5 節(jié)點剩余能量均方差比較

3)節(jié)點消亡數(shù)比較。

從圖6可以看出，隨著仿真時間的流逝，網(wǎng)絡(luò)中節(jié)點消亡數(shù)都是逐漸增加的，但在相同仿真時間下ERAI的節(jié)點消亡數(shù)是最少的。由于ERAI在選擇中繼節(jié)點時均衡了節(jié)點的能量消耗，延遲了節(jié)點消亡的時間，在一定程度上延長了網(wǎng)絡(luò)的生存周期。

4)交付率比較。

從圖7可以看出，在仿真開始時，節(jié)點擁有充足的能量和緩存，Epidemic展現(xiàn)了最好的性能，但是隨著時間的流逝，ERAI具有較高的PDR。這是由于Epidemic采用洪泛機制，大量副本的轉(zhuǎn)發(fā)加快了節(jié)點的能量消耗和緩存空間占據(jù)，而ERAI不僅均衡了節(jié)點的能量消耗，避免節(jié)點因能量不足或失效而丟棄消息，并考慮了節(jié)點前往社區(qū)和節(jié)點間的相遇頻繁程度，增大了PDR。

圖6 節(jié)點消亡數(shù)比較

圖7 數(shù)據(jù)包交付率比較

4 結(jié)語

本文針對移動傳感器網(wǎng)絡(luò)中社區(qū)間路由節(jié)點能量消耗過快的問題，提出了一種移動傳感網(wǎng)社區(qū)間能量均衡路由算法(ERAI)。首先考慮了節(jié)點的去向信息，然后結(jié)合節(jié)點當前剩余能量和相遇情況，選擇轉(zhuǎn)發(fā)節(jié)點。大量實驗驗證，ERAI在一定程度上均衡了各節(jié)點的能耗，延長了網(wǎng)絡(luò)的生命周期。未來的主要工作是采用機器學習方法預(yù)測移動節(jié)點下一時刻前往的社區(qū)，優(yōu)化節(jié)點在消息傳輸過程中的能量消耗，延長網(wǎng)絡(luò)生命周期。

References)

[1] WARH T, CROSSMAN C, HU W, et al. The design and evaluation of a mobile sensor/actuator network for autonomous animal control [C]// IPSN’07: Proceedings of the 6th International Conference on Information Processing in Sensor Networks. New York: ACM, 2007: 206-215.

[2] JAVIDI T, KRISHNAMACHARI B, ZHAO Q, et al. Optimality of myopic sensing in multi-channel opportunistic access [C]// ICC 2008: Proceedings of the 2008 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2008: 2107-2112.

[3] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs [C]// MobiHoc’07: Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York: ACM, 2007: 32-40.

[4] XIA L, WANG G, LIU Z, et al. An energy-efficient routing protocol based on particle swarm clustering algorithm and inter-cluster routing algorithm for WSN [C]// Proceedings of the 25th Chinese Control and Decision Conference. Piscataway, NJ: IEEE, 2013: 4029-4033.

[5] 崔燦,孫毅,陸俊,等.基于混合CS的WSN六邊形格狀優(yōu)化分簇路由算法研究[J].通信學報,2016,37(5):176-183.(CUI C, SUN Y, LU J, et al. Research on a hexagonal lattice optimal clustering routing algorithm based on hybrid CS for WSN [J]. Journal on Communications, 2016, 37(5): 176-183.)

[6] VAHDAT A, BECKER D. Epidemic routing for partially-connected Ad Hoc networks [D]. Durham, NC: Duke University, 2000.

[7] LU X F, HUI P. An energy-efficientn-epidemic routing protocol for delay tolerant networks [C]// NAS’10: Proceedings of the 2010 IEEE Fifth International Conference on Networking, Architecture, and Storage. Washington, DC: IEEE Computer Society, 2010: 341-347.

[8] RANGO F D, AMELIO S, FAZIO P. Enhancements of epidemic routing in delay tolerant networks from an energy perspective [C]// IWCMC 2013: Proceedings of the 9th IEEE International Wireless Communications and Mobile Computing Conference. Piscataway, NJ: IEEE, 2013: 731-735.

[9] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Spray and focus: efficient mobility-assisted routing for heterogeneous and correlated mobility [C]// PERCOMW ’07: Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops. Washington, DC: IEEE Computer Society, 2007: 79-85.

[10] LINDGREN A, DORIA A, SCHELEN O. Probabilistic routing in intermittently connected networks [J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3): 19-20.

[11] HUI P, CROWCROFT, YONEKI E. BUBBLE rap: social-based forwarding in delay-tolerant networks [J]. IEEE Transactions on Mobile Computing, 2011, 10(11): 1576-1589.

[12] LI Y, CAO Y, LI S, et al. Integrating forwarding and replication in DTN routing: a social network perspective [C]// Proceedings of the 2011 IEEE 73rd Vehicular Technology Conference. Piscataway, NJ: IEEE, 2011: 1-5.

[13] BULUT E, SZYMANSKI B K. Exploiting friendship relations for efficient routing in mobile social networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(12): 2254-2265.

[14] WANG K, GUO H. An improved routing algorithm based on social link awareness in delay tolerant networks [J]. Wireless Personal Communications, 2014, 75(1): 397-414.

[15] 吳大鵬,樊思龍,張普寧,等.機會網(wǎng)絡(luò)中能量有效的副本分布狀態(tài)感知路由機制[J].通信學報,2013,34(7):49-58.(WU D P, FAN S L, ZHANG P N, et al. Energy efficient copy distributing status aware routing mechanism in opportunistic network [J]. Journal on Communications, 2013, 34(7): 49-58.)

[16] 楊鵬,劉豆,王汝言,等.節(jié)點剩余能量均衡的機會網(wǎng)絡(luò)路由機制[J].系統(tǒng)工程與電子技術(shù),2015,37(8):1894-1901.(YANG P, LIU D, WANG R Y, et al. Node residual energy balanced routing mechanism for opportunistic networks [J]. Systems Engineering and Electronics, 2015, 37(8): 1894-1901.)

[17] JUN H, AMMAR M H, ZEGURA E W. Power management in delay tolerant networks: a framework and knowledge-based mechanisms [C]// Proceedings of the Second Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. Piscataway, NJ: IEEE, 2005: 418-429.

[18] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

This work is partially supported by the National Natural Science Foundation of China (U1603115, 61262087, 61262089), the Teachers Research Fund of Xinjiang University (XJEDU2012I09), the Jiangxi Science Foundation for Yong Scholars (20151521020008).

GAOQiutian, born in 1991, M. S. candidate. Her research interests include mobile sensor network, network security.

YANGWenzhong, born in 1971, Ph. D., associate professor. His research interests include wireless sensor network, public opinion analysis, information safety.

ZHANGZhenyu, born in 1964, Ph. D., professor. His research interests include opportunity network.

SHIYan, born in 1991, M. S. candidate. Her research interests include mobile location, network security.

LIShuangshuang, born in 1992, M. S. candidate. Her research interests include wireless sensor network, routing protocol, Internet of things.

Energy-balancedroutingalgorithmforinter-communityinmobilesensornetwork

GAO Qiutian1, YANG Wenzhong1,2*, ZHANG Zhenyu1,2, SHI Yan1, LI Shuangshuang2

(1.CollegeofSoftwareEngineering,XinjiangUniversity,UrumqiXinjiang830046,China;2.CollegeofInformationScienceandTechnology,XinjiangUniversity,UrumqiXinjiang830046,China)

Energy efficient routing is a challenging problem in resource constrained Mobile Wireless Sensor Network (MWSN). Focused on the issue that the energy consumption of the inter-community routing in the mobile sensor network is too fast, an Energy-balanced Routing Algorithm for Inter-community (ERAI) was proposed. In ERAI, a new routing metric FC (Forwarding Capacity) based on the residual energy of nodes and the probability of encounter was designed. Then, this metric FC and the directional information of encountered nodes were used for selection of a relay node to forward the messages. The experimental data show that the death time of the first node of ERAI was later than that of Epidemic and PROPHET by 12.6%-15.6% and 4.5%-8.3% respectively, and the residual energy mean square deviation of ERAI was less than that of Epidemic and PROPHET. The experimental results show that the ERAI can balance the energy consumption of each node to a certain extent, and thus prolongs the network lifetime.

mobile sensor network; community; energy balance; encounter probability; network lifetime

TP393.01

:A

2017- 01- 06;

:2017- 02- 27。

國家自然科學基金資助項目(U1603115, 61262087, 61262089)；新疆高校教師科研計劃重點資助項目(XJEDU2012I09)；江西省青年科學基金資助項目(20151521020008)。

高秋田(1991—)，女，河南平輿人，碩士研究生，主要研究方向：移動傳感器網(wǎng)絡(luò)、網(wǎng)絡(luò)安全； 楊文忠(1971—)，男，河南南陽人，副教授，博士，主要研究方向：無線傳感器網(wǎng)絡(luò)、輿情分析、信息安全； 張振宇(1964—)，男，山西大同人，教授，博士，主要研究方向：機會網(wǎng)絡(luò)；石研(1991—)，女，河南商丘人，碩士研究生，主要研究方向：移動定位、網(wǎng)絡(luò)安全； 李雙雙(1992—)，女，山東濟寧人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)、路由協(xié)議、物聯(lián)網(wǎng)。

1001- 9081(2017)07- 1855- 06

10.11772/j.issn.1001- 9081.2017.07.1855