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

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

1 引 言

機(jī)會網(wǎng)絡(luò)是由延遲容忍網(wǎng)絡(luò)(DTN)和移動自組網(wǎng)絡(luò)(MANET)發(fā)展而來的新型網(wǎng)絡(luò).它是一種源節(jié)點和目標(biāo)節(jié)點之間不存在完整鏈路,利用節(jié)點移動帶來的相遇機(jī)會實現(xiàn)通信的延遲容忍自組網(wǎng)絡(luò)[1].該類網(wǎng)絡(luò)具有節(jié)點部署稀疏、節(jié)點通信距離短、存儲容量有限和拓?fù)浣Y(jié)構(gòu)多變等特點.隨著延遲容忍網(wǎng)絡(luò)和移動自組網(wǎng)絡(luò)研究和應(yīng)用的不斷深入,機(jī)會網(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)用前景十分廣闊.

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

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

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

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

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

2 相關(guān)工作

2.1 移動模型

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

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

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

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

2.2 路由算法

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

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

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

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

3 移動模型

3.1 空間劃分

在該模型中,將整個區(qū)域S劃分為若干個子區(qū)域,稱為活動區(qū).活動區(qū)是指在規(guī)定的時間內(nèi)同一個社團(tuán)的節(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時間段為社團(tuán)節(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é)點進(jìn)行社團(tuán)劃分和確定活動區(qū).根據(jù)節(jié)點的相遇持續(xù)時間將節(jié)點劃分為不同的社團(tuán)并為它們分配活動區(qū),這些節(jié)點稱為受限節(jié)點.沒有被組成社團(tuán)的節(jié)點稱為自由節(jié)點.社團(tuán)的具體劃分步驟如下:

1.初始化節(jié)點i的社團(tuán)為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劃分到社團(tuán)Cx

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

(3)

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

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

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

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

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

4 路由算法

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

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

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

網(wǎng)絡(luò)中的每個節(jié)點維護(hù)一個轉(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ù).

故,社團(tuán)內(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機(jī)制,當(dāng)目標(biāo)節(jié)點收到消息時,向網(wǎng)絡(luò)中發(fā)送ACK數(shù)據(jù)包響應(yīng)消息,收到數(shù)據(jù)包的節(jié)點通過對比數(shù)據(jù)包的信息刪除該消息的冗余副本,這樣既能減少資源浪費,又能節(jié)約節(jié)點能量.

4.2 社團(tuán)間的消息傳輸

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

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

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

pt(Cy)=e-βTc

(8)

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

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

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

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

(9)

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

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

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

(10)

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

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

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

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

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

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

基于上述參數(shù)和仿真場景,對CMOT[24],PRoPHET,Epidemic和本文提出的算法在節(jié)點個數(shù)、節(jié)點移動速度、節(jié)點緩存和消息TTL不同下進(jìn)行了算法的傳輸成功率、平均時延、網(wǎng)絡(luò)負(fù)載的對比分析.最后,對比了不同算法的節(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算法在社團(tuán)間主要依靠社團(tuán)活動的周期來建立社團(tuán)間的消息傳輸路徑,只有當(dāng)社團(tuán)有活動時,才可以傳輸消息.圖5(c)表明,隨著節(jié)點密度的增加,4中算法的網(wǎng)絡(luò)負(fù)載都在增加.EBRC算法具有最低的網(wǎng)絡(luò)負(fù)載.

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ò)負(fù)載明顯增加,而EBRC算法和CMOT算法幾乎不變.EBRC算法的負(fù)載最低.

表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ò)負(fù)載隨之減少.且EBRC算法的網(wǎng)絡(luò)負(fù)載遠(yuǎn)遠(yuǎn)低于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ò)負(fù)載明顯增加,EBRC算法具有較低的網(wǎng)絡(luò)負(fù)載.

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ù),因此,具有很好的能量利用,達(dá)到網(wǎng)絡(luò)能量均衡的效果.

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

6 結(jié) 論

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