機會網(wǎng)絡(luò)中基于社團的能量均衡路由算法

姚明輝,張 勝,王 瑜,黃 毅

(南昌航空大學(xué) 信息工程學(xué)院,南昌 330063)

1 引 言

機會網(wǎng)絡(luò)是由延遲容忍網(wǎng)絡(luò)(DTN)和移動自組網(wǎng)絡(luò)(MANET)發(fā)展而來的新型網(wǎng)絡(luò).它是一種源節(jié)點和目標(biāo)節(jié)點之間不存在完整鏈路,利用節(jié)點移動帶來的相遇機會實現(xiàn)通信的延遲容忍自組網(wǎng)絡(luò)[1].該類網(wǎng)絡(luò)具有節(jié)點部署稀疏、節(jié)點通信距離短、存儲容量有限和拓撲結(jié)構(gòu)多變等特點.隨著延遲容忍網(wǎng)絡(luò)和移動自組網(wǎng)絡(luò)研究和應(yīng)用的不斷深入,機會網(wǎng)絡(luò)越來越受到人們的關(guān)注,逐漸成為研究熱點.該網(wǎng)絡(luò)廣泛應(yīng)用[2,3]于野生動物監(jiān)測、手持設(shè)備組網(wǎng)、車載網(wǎng)絡(luò)、環(huán)境監(jiān)測和交通管理等領(lǐng)域.應(yīng)用前景十分廣闊.

機會網(wǎng)絡(luò)節(jié)點之間是利用節(jié)點移動帶來的相遇機會進行通信.因此,節(jié)點之間的通信鏈路具有間斷性,傳統(tǒng)的基于完整鏈路通信的路由算法已不再適用機會網(wǎng)絡(luò).取而代之的是＂存儲-攜帶-轉(zhuǎn)發(fā)＂的消息轉(zhuǎn)發(fā)模式.這種新的消息轉(zhuǎn)發(fā)模式的核心挑戰(zhàn)是:(1)消息轉(zhuǎn)發(fā)時機與消息轉(zhuǎn)發(fā)節(jié)點如何選取;(2)源節(jié)點和目標(biāo)節(jié)點之間的最優(yōu)通信鏈路如何確定;(3)不同網(wǎng)絡(luò)模型對轉(zhuǎn)發(fā)機制的影響.

為了提出能夠適用于機會網(wǎng)絡(luò)的消息傳輸機制,國內(nèi)外研究人員提出了許多路由機制,主要有:基于轉(zhuǎn)發(fā)的路由策略(如:Direct Delivery[4]等);基于復(fù)制的路由策略(如:PRoPHET[5]等).這些算法多采用多副本機制,雖然可以提高消息傳輸成功率和降低傳輸延遲.但,數(shù)據(jù)復(fù)制會給帶寬有限的機會網(wǎng)絡(luò)帶來很大的網(wǎng)絡(luò)開銷,也給存儲空間有限的節(jié)點帶來很大的存儲開銷.多副本路由策略不適合于資源受限的機會網(wǎng)絡(luò)．在節(jié)點能量和帶寬受限的情況下,單副本路由機制在網(wǎng)絡(luò)資源開銷方面有較強的優(yōu)勢.

在許多應(yīng)用中,機會網(wǎng)絡(luò)節(jié)點一般由人類(或動物)攜帶,而人的移動具有社會屬性.通過分析人類行為可以發(fā)現(xiàn),人類行為具有時空受限特性.因此,機會網(wǎng)絡(luò)節(jié)點移動也具有時空受限特性,即節(jié)點的移動受到時間和空間的限制,表現(xiàn)出周期特性.有效的利用機會網(wǎng)絡(luò)的時空特性,能提高節(jié)點間的消息傳輸效率.雖然研究者已經(jīng)提出了許多基于節(jié)點社會特性的路由策略,但是針對節(jié)點的時空受限特性還有待進一步的研究,在路由策略方面需進一步提高消息傳輸效率和均衡網(wǎng)絡(luò)能量.針對節(jié)點移動的時空特性,本文設(shè)計了一種時空受限的移動模型,并在此基礎(chǔ)上提出一種路由算法.本文的主要貢獻如下:

①設(shè)計了節(jié)點移動模型RTSM,該模型體現(xiàn)了節(jié)點的時空受限特性和周期特性,反應(yīng)了機會網(wǎng)絡(luò)節(jié)點的移動規(guī)律,符合實際場景需求.

②通過綜合考慮節(jié)點的相遇概率、相遇周期和剩余能量,設(shè)計了基于社團的能量均衡路由算法.該算法利用節(jié)點移動的時空特性,保證了消息高效傳輸、均衡了節(jié)點能量、延長了網(wǎng)絡(luò)生存期.

2 相關(guān)工作

2.1 移動模型

機會網(wǎng)絡(luò)移動模型是以刻畫節(jié)點相遇特征為核心.移動模型決定了節(jié)點的相遇概率與相遇時間分布.而機會網(wǎng)絡(luò)就是利用節(jié)點的相遇來實現(xiàn)消息的傳輸.因此,與傳統(tǒng)的延遲容忍網(wǎng)和移動自組網(wǎng)相比,機會網(wǎng)絡(luò)移動模型的研究更為重要.

目前,在機會網(wǎng)絡(luò)移動模型研究方面取得了很多研究成果.文獻[6,7]綜述了機會網(wǎng)絡(luò)移動模型研究現(xiàn)狀.從移動模型研究角度可以將移動模型分為兩類:一類是基于理論的移動模型,另一類是基于真實場景的移動模型.前者主要從理論方面構(gòu)建分析移動模型,如,隨機移動模型、高斯-馬爾科夫移動模型等.后者主要通過分析節(jié)點的真實移動軌跡構(gòu)建移動模型.如:基于社區(qū)的移動模型、基于地圖的移動模型、基于工作日的移動模型、基于事件的移動模型等.

本文主要研究的是基于真實場景的移動模型.分析節(jié)點的真實移動軌跡可以發(fā)現(xiàn),節(jié)點的移動具有時間和空間受限特性.即節(jié)點會按照一定的時間到同一個地點聚集,如,學(xué)生需要按照課表在指定的時間到指定的教室上課;員工會按照公司規(guī)定時間到辦公室上班等.針對節(jié)點這種社會特性文獻[8]提出了用戶移動模型.該模型將節(jié)點的空間分為家社區(qū)和其他社區(qū),節(jié)點以更大的概率留在家社區(qū).該模型很好的反應(yīng)的節(jié)點的空間特性,但沒有考慮節(jié)點的時間特性;文獻[9]提出了時變的用戶移動模型,該模型很好的反應(yīng)了節(jié)點的時間特性,但并沒有體現(xiàn)節(jié)點的空間受限特性.文獻[10,11]也提出了具有類似特性的節(jié)點移動模型,但都沒有同時考慮節(jié)點的時間和空間受限特性.

本文根據(jù)節(jié)點的時空受限特性設(shè)計了移動模型.節(jié)點的移動受到時間和空間的限制,同時具有周期特性.該模型體現(xiàn)了節(jié)點移動的時空受限社會特性,符合一定場景的需求.

2.2 路由算法

目前,越來越多的研究者關(guān)注機會網(wǎng)絡(luò)路由算法,國內(nèi)外研究者從不同的角度提出了許多機會網(wǎng)絡(luò)路由算法.最早的算法大多從消息復(fù)制方面增強機會網(wǎng)絡(luò)的消息傳輸.Epidemic算法和Spray and Wait是基于洪泛的思想增加網(wǎng)絡(luò)中消息副本數(shù)量來提高路由效率;PRoPHET,MaxProp算法通過相遇概率決定消息是否轉(zhuǎn)發(fā).

此外,具有社會特性的復(fù)雜路由算法也被相繼提出.文獻[12]提出一種基于社區(qū)機會網(wǎng)絡(luò)的消息傳輸算法.該算法根據(jù)節(jié)點之間的相遇頻繁程度,將節(jié)點劃分為不同的社區(qū),自適應(yīng)的控制消息拷貝數(shù)量并依靠活躍節(jié)點傳輸消息.文獻[13]提出了一種預(yù)測輔助的動態(tài)多副本數(shù)據(jù)傳輸機制.該方法根據(jù)節(jié)點時空維度相遇特征預(yù)測節(jié)點接觸概率,引入?yún)^(qū)間數(shù)不確定理論描述節(jié)點接觸的不確定性.文獻[14]根據(jù)節(jié)點周期性的運動規(guī)律,將時間離散化并給定了時間片上節(jié)點的接觸概率,提出了一種機會路由算法.文獻[15]根據(jù)節(jié)點周期性相遇規(guī)律,假設(shè)節(jié)點在相同時間段有相同的相遇概率,根據(jù)節(jié)點的歷史相遇概率提出概率轉(zhuǎn)發(fā)機制的路由.文獻[16]將節(jié)點流行度和歸屬團體相結(jié)合,通過具有高流行度的節(jié)點來傳輸消息,提出了高傳輸成功率消息傳輸?shù)穆酚伤惴?文獻[17]提出了一種基于區(qū)域朋友關(guān)系的機會路由算法.該算法利用節(jié)點的歷史接觸信息構(gòu)造了節(jié)點親密度評價模型,進而利用節(jié)點的當(dāng)前位置和親密關(guān)系傳輸數(shù)據(jù).文獻[18]利用節(jié)點興趣提出了機會網(wǎng)絡(luò)興趣社團路由算法(ICR),該算法定義了節(jié)點興趣和消息興趣,通過節(jié)點興趣的相似性來劃分社團,然后通過節(jié)點同目標(biāo)節(jié)點是否屬于同一個興趣社團來確定消息的轉(zhuǎn)發(fā)策略.

為了平衡節(jié)點能量消耗,研究者也提出了一些能量均衡的路由算法.文獻[19]綜合考慮消息擴散程度和節(jié)點剩余能量,并結(jié)合節(jié)點相遇概率預(yù)測方法,提出了能量有效的副本分布狀態(tài)感知路由機制.文獻[20]提出了一種自適應(yīng)動態(tài)功率控制的節(jié)能路由算法.該算法通過改進基于接收信號強度指示值的節(jié)點測距機制,將功率控制范圍擴展到全部來減少節(jié)點能耗.文獻[21]提出基于節(jié)點探測的能量均衡機制.該機制先通過泊松分布模型得到有效的探測概率,然后,根據(jù)相關(guān)計算得出探測接觸數(shù),最后,探測有效的能量均衡點.

本文在上述移動模型基礎(chǔ)之上,考慮節(jié)點的移動規(guī)律和節(jié)點的能量提出了基于社團的能量均衡路由算法,該算法分為社團內(nèi)的消息傳輸策略和社團間的消息傳輸策略.本文提出的消息傳輸策略保證了消息的高效傳輸、均衡了節(jié)點能量和延長了網(wǎng)絡(luò)生存期.

3 移動模型

3.1 空間劃分

在該模型中,將整個區(qū)域S劃分為若干個子區(qū)域,稱為活動區(qū).活動區(qū)是指在規(guī)定的時間內(nèi)同一個社團的節(jié)點參與活動的區(qū)域.活動區(qū)的形狀設(shè)置為圓形.區(qū)域S內(nèi)除去所有活動區(qū)外,剩余的區(qū)域為非活動區(qū),用S0表示.如圖1所示,在區(qū)域S內(nèi)包含三個活動區(qū)S1、S2和S3以及非活動區(qū)S0.因此,如果網(wǎng)絡(luò)中包含n個活動區(qū)域,即{S1,S2,…,Sn} 那么,區(qū)域S可以表示為:

S=S0∪S1∪S2∪…∪Sn

3.2 時間劃分

現(xiàn)有的節(jié)點移動模型主要考慮節(jié)點位置、方向、速度等特點,很少考慮節(jié)點移動的時空受限特性和周期特性.針對節(jié)點的這一社會特性,本文將仿真時間劃分為兩個時間段,即,tf時間段,和tr時間段.tf時間段為所有節(jié)點在仿真區(qū)域自由移動的時間;tr時間段為社團節(jié)點在活動區(qū)參加活動的時間.tr和tf交替發(fā)生具有周期特性.如圖2所示.

圖1 區(qū)域劃分示意圖Fig.1 Sketch map of regional division

圖2 時間劃分示意圖
Fig.2 Sketch map of time division

從圖2中,可以得出,

T=tf+tr

(1)

t=kT

(2)

其中,t為仿真時間,T為仿真周期,k為周期數(shù).

3.3 總體描述

移動模型共分為兩個階段,初始化階段和節(jié)點移動階段.在初始化階段:節(jié)點進行社團劃分和確定活動區(qū).根據(jù)節(jié)點的相遇持續(xù)時間將節(jié)點劃分為不同的社團并為它們分配活動區(qū),這些節(jié)點稱為受限節(jié)點.沒有被組成社團的節(jié)點稱為自由節(jié)點.社團的具體劃分步驟如下:

1.初始化節(jié)點i的社團為Cx;

2.當(dāng)節(jié)點i與節(jié)點j相遇時,記錄兩個節(jié)點的相遇開始時間tstart和結(jié)束時間tend,通過節(jié)點的相遇開始時間和結(jié)束時間可以計算出節(jié)點i與節(jié)點j此次相遇的持續(xù)時間te=tend-tstart.將這兩個節(jié)點每次相遇持續(xù)時間累加,更新節(jié)點的持續(xù)相遇時間te

3.當(dāng)節(jié)點i與節(jié)點j的持續(xù)相遇時間te大于閥值σ時,將節(jié)點j劃分到社團Cx

由Newman和Girvan提出的模塊度[22]來衡量社團劃分的好壞.其計算公式如下:

(3)

其中,Q為模塊度函數(shù),其值越大社團劃分效果越好.A為鄰接矩陣,m為圖中總邊數(shù),Pij代表節(jié)點i與節(jié)點j在模型中的邊數(shù).若節(jié)點i與節(jié)點j屬于同一個社團,則δ(Ci,Cj)為1,否則為0.

由公式(3)可知,取不同的閥值將得到不同的社團結(jié)構(gòu),使得獲得不同的Q值.經(jīng)試驗驗證,閥值σ為100秒為優(yōu)值.按此方法將網(wǎng)絡(luò)中的n個節(jié)點劃分為m個社團.該社團劃分允許節(jié)點不屬于任何社團,此節(jié)點為自由節(jié)點在仿真時間內(nèi)可以自由移動.社團個數(shù)是可變的.

隨著節(jié)點的移動和時間的變化,節(jié)點可能會選擇參加其他社團,網(wǎng)絡(luò)中的社團結(jié)構(gòu)也會隨之變化,因此,在每個周期開始之前都會有1000秒的初始化階段來更新節(jié)點間的相遇持續(xù)時間,根據(jù)節(jié)點的相遇持續(xù)時間重新對節(jié)點進行社團劃分,這樣不僅符合節(jié)點的移動規(guī)律而且能降低算法的時間復(fù)雜度.

圖3 移動模型流程圖Fig.3 Flow chart of mobility model

在節(jié)點移動階段:社團節(jié)點在tf時間段在整個仿真區(qū)域自由移動,在tr時間段到指定的活動區(qū)參加活動;自由節(jié)點在整個仿真時間都保持自由移動.具體流程如圖3所示.

4 路由算法

在機會網(wǎng)絡(luò)中,根據(jù)節(jié)點的移動規(guī)律將節(jié)點劃分為不同的社團有利于提高消息的傳輸效率.若,源節(jié)點和目標(biāo)節(jié)點處于同一個社團,可以在節(jié)點參加社團活動時將消息從源節(jié)點傳輸給目標(biāo)節(jié)點,這樣不僅避免了消息在其他社團中擴散降低網(wǎng)絡(luò)資源,而且提高了消息傳輸成功率.若,源節(jié)點和目標(biāo)節(jié)點不在同一社團,可以先利用即和源節(jié)點處于同一個社團又和目標(biāo)節(jié)點處于同一個社團的中繼節(jié)點將消息帶到目標(biāo)節(jié)點所在的社團,再通過社團內(nèi)的消息傳輸機制,將消息傳輸給目標(biāo)節(jié)點.若,源節(jié)點和目標(biāo)節(jié)點有一個參與社團或都不參與社團,可以利用節(jié)點在自由移動時間段構(gòu)建源節(jié)點與目標(biāo)節(jié)點之間的消息傳輸路徑,進而傳輸消息.在此情況下使用社團內(nèi)的消息傳輸機制.因此,該算法可分為社團內(nèi)的消息傳輸機制和社團間的消息傳輸機制.

4.1 社團內(nèi)的消息傳輸

PRoPHET算法是通過分析節(jié)點的移動行為,認為現(xiàn)實中的節(jié)點很可能不完全按照隨機的移動方式移動,而是基于某種重復(fù)行為模型,這種移動行為是可預(yù)測的.該算法定義了一個傳輸預(yù)測值來描述節(jié)點之間成功傳輸?shù)母怕?當(dāng)兩個節(jié)點相遇時,節(jié)點更新自身的傳輸預(yù)測值,并利用該值決定是否轉(zhuǎn)發(fā)數(shù)據(jù)分組.由于社團內(nèi)的節(jié)點相遇比較頻繁,相遇概率較高,如果直接使用該算法傳輸數(shù)據(jù)會使得社團內(nèi)存在大量消息副本,浪費資源,同時該算法沒用考慮節(jié)點的剩余能量,如果節(jié)點的相遇概率很高但是剩余能量很少,那么也不利于消息傳輸.因此,本文將PRoPHET作相應(yīng)的改進以適合社團內(nèi)的消息傳輸.在消息轉(zhuǎn)發(fā)時選擇目標(biāo)節(jié)點的一跳節(jié)點作為中繼節(jié)點轉(zhuǎn)發(fā),同時考慮節(jié)點的相遇概率和剩余能量來決定是否轉(zhuǎn)發(fā)數(shù)據(jù)分組.這樣不僅保證了傳輸成功率,而且平衡了節(jié)點能量消耗.

網(wǎng)絡(luò)中的每個節(jié)點維護一個轉(zhuǎn)發(fā)概率向量表,用來存儲節(jié)點的轉(zhuǎn)發(fā)概率,節(jié)點的轉(zhuǎn)發(fā)概率的計算分為轉(zhuǎn)發(fā)概率更新和老化.

當(dāng)節(jié)點i與節(jié)點j相遇時,節(jié)點間的相遇概率由公式(4)計算,

pm(i,j)=pm(i,j)old+(1-pm(i,j)old)×pinit

(4)

其中pinit為初始相遇概率為0.75.

節(jié)點剩余能量所占的比例pE,由公式(5)計算:

(5)

其中,Ec為節(jié)點的剩余能量,Ei為節(jié)點的初始總能量.

轉(zhuǎn)發(fā)概率由公式(6)計算.該公式保證了經(jīng)常相遇的且剩余能量多的節(jié)點轉(zhuǎn)發(fā)概率更大.

p(i,j)=αpm(i,j)+(1-α)pE

(6)

其中α為權(quán)值因子,由實驗可知,α=0.75最為合適.

節(jié)點i和j在時間單元內(nèi)沒用相遇,則其轉(zhuǎn)發(fā)概率逐漸老化,計算公式如(7)式所示.

p(i,j)=p(i,j)old×γk

(7)

其中,γ∈[0,1] 是一個初始化常數(shù),k為經(jīng)過的時間單元數(shù).經(jīng)試驗驗證,γ=0.98為最合適的常數(shù).

故,社團內(nèi)的消息傳輸策略為:當(dāng)兩個節(jié)點相遇時,通過比較兩個節(jié)點的轉(zhuǎn)發(fā)概率來確定是否轉(zhuǎn)發(fā)數(shù)據(jù)分組.若相遇節(jié)點到目標(biāo)節(jié)點的轉(zhuǎn)發(fā)概率大于當(dāng)前節(jié)點到目標(biāo)節(jié)點的轉(zhuǎn)發(fā)概率,則將消息轉(zhuǎn)發(fā)給相遇節(jié)點;否則,不轉(zhuǎn)發(fā).同時,算法增加了ACK機制,當(dāng)目標(biāo)節(jié)點收到消息時,向網(wǎng)絡(luò)中發(fā)送ACK數(shù)據(jù)包響應(yīng)消息,收到數(shù)據(jù)包的節(jié)點通過對比數(shù)據(jù)包的信息刪除該消息的冗余副本,這樣既能減少資源浪費,又能節(jié)約節(jié)點能量.

4.2 社團間的消息傳輸

社團間的消息傳輸?shù)年P(guān)鍵是找到連接社團的中繼節(jié)點,通過這些中繼節(jié)點構(gòu)成社團間的連通路徑,從而完成社團間的消息傳輸.由于節(jié)點可能參與不同的社團,因此,存在一些節(jié)點即與源節(jié)點在同一個社團又和目標(biāo)節(jié)點在同一個社團,可以通過這些節(jié)點建立社團之間的連接路徑.大量節(jié)點參與不同的社團可能存在多條連通社團間的路徑,找出這些路徑中的最佳路徑就可以完成社團間的消息傳輸.

如圖4所示,節(jié)點i要將消息傳給目標(biāo)節(jié)點d具體過程如下:假設(shè)節(jié)點i屬于Cx社團,節(jié)點d屬于Cy社團,節(jié)點j即屬于Cx社團又屬于Cy社團.當(dāng)社團Cx舉辦活動時,節(jié)點i將消息轉(zhuǎn)發(fā)給節(jié)點j,當(dāng)社團Cy舉辦活動時,節(jié)點j會將消息帶入到社團Cy,這樣就建立了Cx→Cy之間的鏈路,通過這樣的連通鏈路就可實現(xiàn)社團之間的消息傳輸.由于這種連通鏈路可能有很多條,為了找出社團間的最佳路徑,本文定義了傳輸概率.

由于不同的社團舉辦活動的周期不同,可以通過周期來確定社團間的最優(yōu)路徑.選擇頻繁參加活動的節(jié)點來傳輸消息.通過公式(8)將社團活動的周期轉(zhuǎn)化為效用值.

pt(Cy)=e-βTc

(8)

其中,Tc為節(jié)點參與社團活動的周期,β為保護因子,其取值與Tc有關(guān),本實驗設(shè)置為0.001.

圖4 社團間的消息傳輸示意圖Fig.4 Sketch map of message transmission between community

社團間的傳輸概率可由公式(9)計算:

pm(Cy)=p(i,j)pj(Cy)

(9)

節(jié)點在移動過程中傳輸概率是不斷更新和老化的.當(dāng)節(jié)點i與節(jié)點j建立社團間的連通鏈路時,通過公式(9)計算這條路徑的傳輸概率,如果新路徑的傳輸概率大于老路徑的傳輸概率,則更新傳輸概率.否則,不更新.

由于社團之間存在多條路徑,且這些路徑是隨著時間動態(tài)變化的,若通過節(jié)點j連接兩個社團之間的路徑一段時間內(nèi)沒有更新,則其傳輸概率逐漸老化,由公式(10)計算:

pm(i,j)=pm(i,j)old×ηk

(10)

其中,η∈[0,1] 是一個初始化常數(shù),經(jīng)實驗仿真,η=0.98是較為理想的常數(shù)值.k是經(jīng)過的時間單元個數(shù).

故,社團間的消息傳輸策略為:消息在社團間轉(zhuǎn)發(fā)時,通過參與多個社團的節(jié)點建立社團之間的連接路徑.當(dāng)節(jié)點遇到多個能到達目標(biāo)社團的節(jié)點時,將消息轉(zhuǎn)發(fā)給傳輸概率高的節(jié)點,由該節(jié)點將消息帶到目標(biāo)節(jié)點所在的社團,進而建立社團之間的最優(yōu)路徑.通過這條路徑將消息從一個社團帶到另一個社團.達到社團間消息傳輸?shù)哪康?

5 實驗及結(jié)果分析

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

本文使用由芬蘭Nokia研究中心開發(fā)的開源仿真工具ONE(Opportunistic Network Environment)[23]對提出的EBRC算法進行仿真.仿真之前,先進行10000s的初始化以完成社團劃分,仿真參數(shù)如表1.

5.2 實驗結(jié)果及分析

基于上述參數(shù)和仿真場景,對CMOT[24],PRoPHET,Epidemic和本文提出的算法在節(jié)點個數(shù)、節(jié)點移動速度、節(jié)點緩存和消息TTL不同下進行了算法的傳輸成功率、平均時延、網(wǎng)絡(luò)負載的對比分析.最后,對比了不同算法的節(jié)點剩余能量.

5.2.1 節(jié)點數(shù)對路由算法的影響

實驗設(shè)置節(jié)點的平均移動速度為6m/s,節(jié)點緩存大小為10M,消息TTL為300min.其他參數(shù)如表1所示.仿真結(jié)果如圖5所示.圖5(a)表明,隨著節(jié)點密度的增加,EBRC算法和CMOT算法的變化趨勢基本一致,同時可以看出節(jié)點密度對這兩種算法的傳輸成功率影響不大.在仿真算法中EBRC傳輸成功率最高.原因分析:

PRoPHET算法和Epidemic算法沒

圖5 節(jié)點數(shù)對路由算法的影響Fig.5 Influence of node numbers on algorithms

有考慮節(jié)點的聚集特性和周期特性,因此消息的投遞范圍有限,傳輸成功率較低.CMOT雖然考慮了節(jié)點的聚集特性,但是并不適用于周期性聚集的移動模型,所以其傳輸成功率略低于EBRC算法.圖5(b)表明,隨著節(jié)點密度的增加,EBRC,CMOT,PRoPHET算法的平均時延在一定范圍內(nèi)波動,整體變化不大,這說明節(jié)點密度對這3中算法的平均時延影響不大.相反,Epidemic算法的平均時延變化很大.同時可以看出,CMOT的平均時延略低于EBRC,這是因為EBRC算法在社團間主要依靠社團活動的周期來建立社團間的消息傳輸路徑,只有當(dāng)社團有活動時,才可以傳輸消息.圖5(c)表明,隨著節(jié)點密度的增加,4中算法的網(wǎng)絡(luò)負載都在增加.EBRC算法具有最低的網(wǎng)絡(luò)負載.

5.2.2 節(jié)點平均速度對路由算法的影響

實驗設(shè)置節(jié)點的個數(shù)為150個,節(jié)點緩存大小為10M,消息TTL為300min.其他參數(shù)如上表所示.仿真結(jié)果如圖6所示.從圖6(a)可以看出,節(jié)點的平均移動速度對4中算法的傳輸成功率影響不大,且EBRC路由算法高于PRoPHET算法和Epidemic算法.圖6(b)表明,隨著節(jié)點平均移動速度的增加,4種算法消息的平均時延大大降低,這是因為,當(dāng)移動速度大時,消息能更快的傳輸?shù)侥繕?biāo)節(jié)點,消息的平均延時會

降低.同時可以看出,當(dāng)節(jié)點平均移動速度小于8m/s時,EBRC算法的平均延時表現(xiàn)較好.圖6(c)可以看出,隨著節(jié)點移動速度的增加,PRoPHET算法和Epidemic算法的網(wǎng)絡(luò)負載明顯增加,而EBRC算法和CMOT算法幾乎不變.EBRC算法的負載最低.

表1 仿真參數(shù)設(shè)置
Table 1 Simulation parameter setting

圖6 節(jié)點平均速度對路由算法的影響Fig.6 Influence of node average speed on algorithms

5.2.3 節(jié)點緩存大小對路由算法的影響

實驗設(shè)置節(jié)點的個數(shù)為150個,節(jié)點平均移動速度為6m/s,消息TTL為300min.其他參數(shù)如上表所示.仿真結(jié)果如圖7所示.圖7(a)表明,隨著節(jié)點緩存的增加4種算法的傳輸成功率都在增加,其中EBRC算法和CMOT算法傳輸成功率增加較快,PRoPHET算法和Epidemic算法增加較慢.同時可以看出,EBRC算法有最高的傳輸成功率.圖7(b)表明,節(jié)點緩存對Epidemic算法的平均時延幾乎沒有影響,而對EBRC算法和CMOT算法的平均時延影響較大.同時可以看出,EBRC算法適用于緩存比較小的節(jié)點,隨著緩存的曾加,EBRC算法的延遲表現(xiàn)不佳.圖7(c)表明,隨著節(jié)點緩存的增加,網(wǎng)絡(luò)負載隨之減少.且EBRC算法的網(wǎng)絡(luò)負載遠遠低于PRoPHET算法和Epidemic算法表現(xiàn)最佳.

5.2.4 消息TTL對路由算法的影響

圖7 節(jié)點緩存大小對路由算法的影響Fig.7 Influence of node cache size on algorithms

實驗設(shè)置節(jié)點的個數(shù)為150個,節(jié)點平均移動速度為6m/s,節(jié)點緩存為10M.其他參數(shù)如上表所示.仿真結(jié)果如圖8所示.

圖8 消息TTL對路由算法的影響Fig.8 Influence of TTL on algorithms

圖8(a)表明,隨著消息TTL的增加,EBRC算法和CMOT算法的傳輸成功率呈現(xiàn)增加后下降的趨勢變化,而PRoPHET算法和Epidemic算法的傳輸成功率呈下降趨勢.且EBRC算法的傳輸成功率最高.圖8(b)表明,當(dāng)消息TTL小于200min時EBRC算法的平均延遲隨著消息TTL的增加而增加;當(dāng)消息TTL大于200min時EBRC算法的平均延遲隨著消息TTL的增加幾乎不變.Epidemic算法的平均延遲最差.圖8(c)表明,隨著消息TTL的增加,4種算法的網(wǎng)絡(luò)負載明顯增加,EBRC算法具有較低的網(wǎng)絡(luò)負載.

5.2.5 節(jié)點剩余能量對比分析

實驗設(shè)置節(jié)點的個數(shù)為150個,節(jié)點平均移動速度為6m/s,節(jié)點緩存為10M,消息TTL為300min.其他參數(shù)如上表所示.仿真結(jié)果如圖9所示.

圖9表明,當(dāng)仿真時間結(jié)束時,對于PRoPHET算法和Epidemic算法大部分節(jié)點的剩余能量為0,一部分節(jié)點剩余很多能量,網(wǎng)絡(luò)能量不均衡.CMOT算法有一部分節(jié)點剩余能量為0,且其他節(jié)點的剩余能量也相差較大,網(wǎng)絡(luò)能量不均衡.EBRC算法所有節(jié)點剩余能量相差不大,且沒有節(jié)點能量為0,網(wǎng)絡(luò)能量較均衡.這是因為,EBRC算法考慮了節(jié)點的剩余能量,讓剩余能量多的節(jié)點傳輸數(shù)據(jù),剩余能量少的節(jié)點幾乎不會傳輸數(shù)據(jù),因此,具有很好的能量利用,達到網(wǎng)絡(luò)能量均衡的效果.

圖9 節(jié)點的剩余能量Fig.9 Residual energy of nodes

6 結(jié) 論

本文一方面根據(jù)機會網(wǎng)絡(luò)的移動特性結(jié)合社會網(wǎng)絡(luò)節(jié)點的社團和周期特性,提出了一種時空受限的移動模型,使得節(jié)點的移動更加符合具有社會特性實際場景.另一方面,在這種移動模型基礎(chǔ)之上,提出了基于社團的能量均衡路由算法.該算法在社團內(nèi)考慮節(jié)點的相遇概率和節(jié)點剩余能量來轉(zhuǎn)發(fā)消息;在社團間充分利用節(jié)點移動的周期特性來尋找社團間的最佳路徑進行消息傳輸.仿真結(jié)果表明,該算法提高了消息的傳輸成功率,降低了網(wǎng)絡(luò)負載,同時也實現(xiàn)的網(wǎng)絡(luò)能量均衡.本文的移動模型具有一些約束條件,這于現(xiàn)實場景存在一定差距,需要進一步完善,EBRC算法僅僅通過周期來確定最優(yōu)路徑,有一定的局限性,也需要相應(yīng)的優(yōu)化.