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

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

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

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

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

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

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

0 引言

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

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

分簇路由大都假設(shè)節(jié)點(diǎn)的位置固定，并未考慮節(jié)點(diǎn)的移動性。為了實(shí)現(xiàn)移動節(jié)點(diǎn)間的數(shù)據(jù)傳輸，文獻(xiàn)[6]提出了傳染病路由(Epidemic Routing)，其采用洪泛的轉(zhuǎn)發(fā)機(jī)制。在節(jié)點(diǎn)緩存和能量充足的場景下，Epidemic路由可達(dá)到較好的網(wǎng)絡(luò)性能，但在能量受限的移動傳感器網(wǎng)絡(luò)中，泛洪轉(zhuǎn)發(fā)策略會使節(jié)點(diǎn)能量消耗太快。之后出現(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]等，但文獻(xiàn)[8-10]僅僅在Epidemic路由的基礎(chǔ)上調(diào)整消息副本數(shù)，并沒有很好地解決節(jié)點(diǎn)能耗不均衡的問題。

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

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

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

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

1.1 社區(qū)模型

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

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

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

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

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

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

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

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

1.2 能耗模型

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

圖1 一階無線通信模型

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

(1)

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

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

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

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

(2)

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

圖2 兩種分組的消息格式

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

(4)

(5)

(6)

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

2 ERAI路由算法描述

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

2.1 路由度量指標(biāo)

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

2.1.1 相遇概率EP

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

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

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

(7)

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

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

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

(8)

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

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

同一社區(qū)內(nèi)的節(jié)點(diǎn)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é)點(diǎn)x與節(jié)點(diǎn)y前后兩次相遇時(shí)間間隔，即Δt=tc-tc-1，tc是當(dāng)前相遇時(shí)刻。

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

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

(10)

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

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

(11)

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

(12)

(13)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 ERAI流程

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

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

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

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

(14)

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

(15)

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

(16)

圖3 ERAI的流程

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

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

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

3.2 實(shí)驗(yàn)結(jié)果與分析

1)首個(gè)節(jié)點(diǎn)消亡時(shí)間比較。

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

圖4 首個(gè)節(jié)點(diǎn)消亡時(shí)間比較

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

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

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

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

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

4)交付率比較。

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

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

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

4 結(jié)語

本文針對移動傳感器網(wǎng)絡(luò)中社區(qū)間路由節(jié)點(diǎn)能量消耗過快的問題，提出了一種移動傳感網(wǎng)社區(qū)間能量均衡路由算法(ERAI)。首先考慮了節(jié)點(diǎn)的去向信息，然后結(jié)合節(jié)點(diǎn)當(dāng)前剩余能量和相遇情況，選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。大量實(shí)驗(yàn)驗(yàn)證，ERAI在一定程度上均衡了各節(jié)點(diǎn)的能耗，延長了網(wǎng)絡(luò)的生命周期。未來的主要工作是采用機(jī)器學(xué)習(xí)方法預(yù)測移動節(jié)點(diǎn)下一時(shí)刻前往的社區(qū)，優(yōu)化節(jié)點(diǎn)在消息傳輸過程中的能量消耗，延長網(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].通信學(xué)報(bào),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] 吳大鵬,樊思龍,張普寧,等.機(jī)會網(wǎng)絡(luò)中能量有效的副本分布狀態(tài)感知路由機(jī)制[J].通信學(xué)報(bào),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é)點(diǎn)剩余能量均衡的機(jī)會網(wǎng)絡(luò)路由機(jī)制[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。

國家自然科學(xué)基金資助項(xiàng)目(U1603115, 61262087, 61262089)；新疆高校教師科研計(jì)劃重點(diǎn)資助項(xiàng)目(XJEDU2012I09)；江西省青年科學(xué)基金資助項(xiàng)目(20151521020008)。

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

1001- 9081(2017)07- 1855- 06

10.11772/j.issn.1001- 9081.2017.07.1855