張棋飛,桂 超,宋 鶯,孫寶林,戴志鋒

(湖北經(jīng)濟(jì)學(xué)院 信息與通信工程學(xué)院,湖北 武漢 430205)

機(jī)會(huì)網(wǎng)絡(luò)是一種在通信鏈路間歇式連通狀況下,利用節(jié)點(diǎn)移動(dòng)帶來的接觸機(jī)會(huì)實(shí)現(xiàn)數(shù)據(jù)傳輸?shù)淖越M織網(wǎng)絡(luò)[1].作為一種新興的網(wǎng)絡(luò)形態(tài),機(jī)會(huì)網(wǎng)絡(luò)面臨著許多在傳統(tǒng)網(wǎng)絡(luò)環(huán)境中不曾遭遇的困難和挑戰(zhàn)[2],其分組路由問題更是引起了研究者的極大關(guān)注[3?5].機(jī)會(huì)網(wǎng)絡(luò)路由機(jī)制基于節(jié)點(diǎn)間鏈路間歇式連通狀況,利用節(jié)點(diǎn)移動(dòng)帶來的接觸機(jī)會(huì)實(shí)現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)[6].在沒有找到合適的下一跳節(jié)點(diǎn)前,節(jié)點(diǎn)攜帶數(shù)據(jù)并等待連接機(jī)會(huì),如圖1 所示.在t1 時(shí)刻,源節(jié)點(diǎn)S與目標(biāo)節(jié)點(diǎn)D分別位于兩個(gè)不連通的子區(qū)域,在它們之間無法建立起一條完整的傳輸路徑.于是,S將數(shù)據(jù)轉(zhuǎn)發(fā)給自己的鄰居節(jié)點(diǎn)B,由B攜帶該數(shù)據(jù)在t2 時(shí)刻轉(zhuǎn)發(fā)給下一跳節(jié)點(diǎn)E.最后,在t3 時(shí)刻,節(jié)點(diǎn)E將數(shù)據(jù)交付給最終的目標(biāo)節(jié)點(diǎn)D.

Fig.1 Illustration of routing in opportunistic networks圖1 機(jī)會(huì)網(wǎng)絡(luò)路由示意圖

機(jī)會(huì)網(wǎng)絡(luò)采取數(shù)據(jù)捎帶轉(zhuǎn)發(fā)模式,即節(jié)點(diǎn)在自由運(yùn)動(dòng)過程中尋找機(jī)會(huì)轉(zhuǎn)發(fā)數(shù)據(jù),其運(yùn)動(dòng)軌跡一般不受所攜帶數(shù)據(jù)的影響.這種方式維護(hù)了節(jié)點(diǎn)的獨(dú)立性,卻給數(shù)據(jù)傳輸帶來一定影響,導(dǎo)致投遞率降低,傳輸時(shí)延增加.我們認(rèn)為:針對(duì)不同的通信需求應(yīng)該采取不同的傳輸策略,尤其對(duì)那些具有較高傳輸要求的應(yīng)用更應(yīng)如此[7].在某些情況下,應(yīng)該允許節(jié)點(diǎn)犧牲運(yùn)動(dòng)獨(dú)立性,調(diào)整運(yùn)動(dòng)軌跡,以構(gòu)建快速、穩(wěn)定、有效的通信連接.同時(shí)也應(yīng)該看到:運(yùn)動(dòng)軌跡的調(diào)整必然會(huì)改變節(jié)點(diǎn)的運(yùn)動(dòng)狀態(tài),對(duì)原有的任務(wù)調(diào)度造成影響.因此需要綜合考慮節(jié)點(diǎn)的任務(wù)調(diào)度以及數(shù)據(jù)轉(zhuǎn)發(fā)需求,設(shè)計(jì)節(jié)點(diǎn)的運(yùn)動(dòng)轉(zhuǎn)發(fā)機(jī)制,實(shí)現(xiàn)數(shù)據(jù)的有效轉(zhuǎn)發(fā).本文第1 節(jié)介紹典型的機(jī)會(huì)路由協(xié)議.第2節(jié)設(shè)計(jì)基于運(yùn)動(dòng)的機(jī)會(huì)路由算法.仿真實(shí)驗(yàn)結(jié)果在第3 節(jié)給出.最后一節(jié)總結(jié)全文.

1 相關(guān)工作

機(jī)會(huì)路由的初衷是為了滿足稀疏移動(dòng)環(huán)境下的自組織網(wǎng)絡(luò)通信要求[8].經(jīng)過多年的發(fā)展和完善,目前已成為實(shí)現(xiàn)間歇式連通環(huán)境下數(shù)據(jù)收集與內(nèi)容共享的一項(xiàng)重要技術(shù).根據(jù)消息的傳輸策略不同,可以將機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議分成3 類[1]:基于副本的路由、基于主動(dòng)運(yùn)動(dòng)的路由以及基于效用的路由等.

(1) 基于副本的路由

基于副本的路由策略通過在網(wǎng)絡(luò)中產(chǎn)生一定數(shù)量的消息副本提高目的節(jié)點(diǎn)接收消息的成功率,可分為單副本傳輸和多副本傳輸.Direct Transmission[9]采用單副本傳輸策略,源節(jié)點(diǎn)緩存消息直到遇到目標(biāo)節(jié)點(diǎn).每個(gè)數(shù)據(jù)包只傳輸一次,且沒有其他副本,網(wǎng)絡(luò)開銷最小,但時(shí)延大,分組投遞率低.多副本傳輸基于洪泛策略,又可分為全網(wǎng)洪泛和部分洪泛.Epidemic Routing 采用全網(wǎng)洪泛機(jī)制,為每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)摘要向量,存儲(chǔ)本地的分組消息列表.節(jié)點(diǎn)相遇時(shí),通過交換摘要向量獲得新的消息.消息以洪泛方式在全網(wǎng)快速擴(kuò)散,最終抵達(dá)目標(biāo)節(jié)點(diǎn).如果資源條件允許,可以找到一條最短路徑從而獲得較低時(shí)延.然而由于副本數(shù)目太多,會(huì)給網(wǎng)絡(luò)帶來巨大開銷.2-Hops[9]算法采取了部分洪泛策略,通過將消息拷貝給最先遇到的n個(gè)中繼節(jié)點(diǎn),限制消息只在兩跳范圍內(nèi)傳輸,從一定程度上避免了冗余信息過多的問題.Spray &Wait[10]同樣采取部分洪泛策略,源節(jié)點(diǎn)定義分組在Spray階段被轉(zhuǎn)發(fā)的最大次數(shù),每個(gè)收到該副本的節(jié)點(diǎn)按照一定比例將副本轉(zhuǎn)發(fā).一旦副本數(shù)目減少到1,則進(jìn)入Wait階段,節(jié)點(diǎn)攜帶副本直至遇到目標(biāo)節(jié)點(diǎn).

(2) 基于主動(dòng)運(yùn)動(dòng)的路由

基于主動(dòng)運(yùn)動(dòng)的路由機(jī)制通過引入部分能夠?qū)崿F(xiàn)主動(dòng)移動(dòng)的特殊節(jié)點(diǎn),來為其他普通節(jié)點(diǎn)提供通信服務(wù).DataMULEs[11]引入了MULE 節(jié)點(diǎn),在移動(dòng)過程中收集傳感器數(shù)據(jù),實(shí)現(xiàn)稀疏傳感器網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)采集.Message Ferrying[12]協(xié)議在區(qū)域內(nèi)部署Ferry 節(jié)點(diǎn),按預(yù)定義路徑或普通節(jié)點(diǎn)的通信請(qǐng)求,在移動(dòng)過程中實(shí)現(xiàn)數(shù)據(jù)的轉(zhuǎn)發(fā).Zhao 等人[13]在Message Ferrying 的基礎(chǔ)上,提出使用多個(gè)Ferry 節(jié)點(diǎn)以提高系統(tǒng)的可靠性和傳輸效率.

(3) 基于效用的路由

基于效用的路由策略通過引入效用值評(píng)估選擇合適的下一跳節(jié)點(diǎn),避免消息的盲目轉(zhuǎn)發(fā).PQBCF[14]算法設(shè)計(jì)了一個(gè)中間中心度指標(biāo),用來描述節(jié)點(diǎn)在信息傳輸過程中的參與度和重要度.Zhao 等人[15]從延長網(wǎng)絡(luò)存活時(shí)間的角度出發(fā),提出了一種差分概率轉(zhuǎn)發(fā)機(jī)制,以節(jié)點(diǎn)的剩余能量為度量設(shè)計(jì)轉(zhuǎn)發(fā)策略,以最大化網(wǎng)絡(luò)生存時(shí)間.SMART[16]協(xié)議通過在鄰居節(jié)點(diǎn)之間交換朋友關(guān)系,將節(jié)點(diǎn)接觸概率的計(jì)算放在發(fā)送端進(jìn)行,降低節(jié)點(diǎn)間信息交換次數(shù).PeopleRank[17]協(xié)議基于經(jīng)典的PageRank算法分布式計(jì)算節(jié)點(diǎn)中心度,降低傳統(tǒng)社會(huì)化網(wǎng)絡(luò)分析方法的復(fù)雜性.BUBBLE[18]協(xié)議考慮節(jié)點(diǎn)的社會(huì)地位,對(duì)節(jié)點(diǎn)進(jìn)行聚類后,利用節(jié)點(diǎn)所在的社區(qū)信息及中心度信息轉(zhuǎn)發(fā)數(shù)據(jù).SCOR[19]算法利用網(wǎng)絡(luò)中的社會(huì)上下文信息,通過BP 神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)節(jié)點(diǎn)的移動(dòng)行為.針對(duì)機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)模式帶來的較為嚴(yán)重的流量分配不公以及投遞成功率不公問題,FSMF[20]算法引入用戶社會(huì)關(guān)系馬爾科夫鏈模型對(duì)用戶的社會(huì)關(guān)系進(jìn)行評(píng)價(jià);同時(shí),為了提高公平性,根據(jù)用戶的社會(huì)關(guān)系限制消息副本的數(shù)量并限制轉(zhuǎn)發(fā)副本的數(shù)量.PICD[21]針對(duì)節(jié)點(diǎn)循環(huán)運(yùn)動(dòng)的場(chǎng)景,考慮節(jié)點(diǎn)與匯聚點(diǎn)間存在間歇多跳路徑的情況,將消息容忍的延遲與傳輸概率的計(jì)算相結(jié)合,利用節(jié)點(diǎn)間的周期間歇連通性改善路由性能.PROPHET[22]協(xié)議為網(wǎng)絡(luò)中的每一對(duì)節(jié)點(diǎn)計(jì)算投遞概率,利用接觸概率的傳遞性更新投遞預(yù)測(cè)概率值,實(shí)現(xiàn)數(shù)據(jù)從低概率節(jié)點(diǎn)向高概率節(jié)點(diǎn)的轉(zhuǎn)移,直至抵達(dá)目標(biāo)節(jié)點(diǎn).TOR[23]算法針對(duì)惡意的網(wǎng)絡(luò)環(huán)境設(shè)計(jì)基于信任機(jī)制的路由算法,對(duì)參與轉(zhuǎn)發(fā)的中間節(jié)點(diǎn)進(jìn)行信任度評(píng)估,利用信任廣播周期性地將最新信任路由表反饋給其他節(jié)點(diǎn),從而簡化傳統(tǒng)信任關(guān)系評(píng)估和傳播的復(fù)雜性.在消息轉(zhuǎn)發(fā)過程中,采用沿著信任度遞增的梯度轉(zhuǎn)發(fā),提高轉(zhuǎn)發(fā)成功率.

以上路由機(jī)制中,基于副本的路由策略通過在網(wǎng)絡(luò)中生成多個(gè)消息副本來保證數(shù)據(jù)的傳輸.這種消息的復(fù)制對(duì)網(wǎng)絡(luò)資源要求很高,會(huì)在網(wǎng)絡(luò)中產(chǎn)生大量冗余,導(dǎo)致資源浪費(fèi).基于主動(dòng)運(yùn)動(dòng)的路由通過引入某些具有移動(dòng)功能的特殊節(jié)點(diǎn)來輔助數(shù)據(jù)的傳輸.此類節(jié)點(diǎn)往往具有較強(qiáng)的運(yùn)動(dòng)能力、通信能力以及存儲(chǔ)能力,與普通節(jié)點(diǎn)差別很大.而且算法假設(shè)目標(biāo)節(jié)點(diǎn)的位置是固定的,并沒有考慮到移動(dòng)節(jié)點(diǎn)間的數(shù)據(jù)通信.而基于效用的路由策略主要利用相遇預(yù)測(cè)、鏈路狀態(tài)以及上下文等信息計(jì)算效用值,并沒有充分考慮數(shù)據(jù)傳輸?shù)牟煌笠约肮?jié)點(diǎn)自身的運(yùn)動(dòng)特質(zhì)對(duì)路由的影響.

機(jī)會(huì)網(wǎng)絡(luò)的部分概念來源于早期的間歇式連通網(wǎng)絡(luò)和延遲容忍網(wǎng)絡(luò),這兩種網(wǎng)絡(luò)著重強(qiáng)調(diào)應(yīng)用的延遲容忍特性.但隨著機(jī)會(huì)網(wǎng)絡(luò)研究的不斷深入,其內(nèi)涵覆蓋更為廣泛,承載的業(yè)務(wù)類型日漸豐富,數(shù)據(jù)傳輸?shù)囊笠苍絹碓蕉鄻踊?在這種情況下,如果還是按照傳統(tǒng)模式依靠節(jié)點(diǎn)隨機(jī)運(yùn)動(dòng)帶來的有限連接機(jī)會(huì)來傳輸數(shù)據(jù),勢(shì)必?zé)o法滿足應(yīng)用多樣化的傳輸需求[7].既然機(jī)會(huì)網(wǎng)絡(luò)是利用節(jié)點(diǎn)移動(dòng)帶來的接觸機(jī)會(huì)傳輸數(shù)據(jù),就應(yīng)該充分利用節(jié)點(diǎn)的運(yùn)動(dòng)特性更好地為數(shù)據(jù)通信服務(wù).某些情況下,為了滿足應(yīng)用的要求,甚至可以犧牲節(jié)點(diǎn)的獨(dú)立性來保障傳輸?shù)馁|(zhì)量.我們知道,機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)在運(yùn)動(dòng)過程中尋找轉(zhuǎn)發(fā)機(jī)會(huì),正是節(jié)點(diǎn)的運(yùn)動(dòng)為數(shù)據(jù)交換提供了可能.運(yùn)動(dòng)獨(dú)立性從運(yùn)動(dòng)的角度反映了節(jié)點(diǎn)保障傳輸任務(wù)的能力.一般來說,當(dāng)前傳輸任務(wù)的優(yōu)先級(jí)越高,節(jié)點(diǎn)的運(yùn)動(dòng)獨(dú)立性越強(qiáng),在傳輸過程中越不易受到外來任務(wù)的干擾.節(jié)點(diǎn)的任務(wù)調(diào)度按照優(yōu)先級(jí)順序從高到低依次執(zhí)行.當(dāng)節(jié)點(diǎn)承擔(dān)的新的傳輸任務(wù)優(yōu)先級(jí)高于其原有的任務(wù)調(diào)度時(shí),應(yīng)該犧牲節(jié)點(diǎn)的運(yùn)動(dòng)獨(dú)立性,將其原有任務(wù)暫時(shí)掛起,通過調(diào)整節(jié)點(diǎn)的運(yùn)動(dòng)路線來保障高優(yōu)先級(jí)任務(wù)的執(zhí)行.基于此,本文研究機(jī)會(huì)網(wǎng)絡(luò)路由機(jī)制的關(guān)鍵技術(shù),以機(jī)會(huì)網(wǎng)絡(luò)的運(yùn)動(dòng)特性為切入點(diǎn),以提高分組路由性能為基本目標(biāo),從應(yīng)用的需求及網(wǎng)絡(luò)資源的調(diào)度出發(fā),設(shè)計(jì)了基于運(yùn)動(dòng)的機(jī)會(huì)路由算法MBOR(motion based opportunistic routing),通過調(diào)整節(jié)點(diǎn)的運(yùn)動(dòng)軌跡,在滿足不同數(shù)據(jù)傳輸要求的同時(shí)提高分組投遞率,降低傳輸時(shí)延.

2 MBOR 路由算法

2.1 數(shù)據(jù)傳輸機(jī)制

數(shù)據(jù)在路由到目的地的過程中,一般要經(jīng)歷中繼轉(zhuǎn)發(fā)和直接交付兩個(gè)階段.通常而言,為了獲得穩(wěn)定的數(shù)據(jù)傳輸質(zhì)量以及較低的分組延遲,往往要求參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)數(shù)目越少越好,最好能夠直接交付[24].尤其對(duì)于機(jī)會(huì)網(wǎng)絡(luò)這種在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間可能都不存在一條完整傳輸路徑的情況,采取直接交付更為可靠.然而數(shù)據(jù)的直接交付是有前提的,即數(shù)據(jù)攜帶節(jié)點(diǎn)與目的節(jié)點(diǎn)之間是可以構(gòu)建直連通路的,而這恰恰是多數(shù)網(wǎng)絡(luò)環(huán)境所不具備的.由于傳統(tǒng)網(wǎng)絡(luò)采用了存儲(chǔ)-轉(zhuǎn)發(fā)的數(shù)據(jù)交換方式,對(duì)于那些無法實(shí)現(xiàn)直接交付的節(jié)點(diǎn),只能通過尋找合適的下一跳,將數(shù)據(jù)中繼轉(zhuǎn)發(fā)至目的地.而機(jī)會(huì)網(wǎng)絡(luò)獨(dú)有的存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)方式給了我們一個(gè)新的選擇,節(jié)點(diǎn)可以攜帶數(shù)據(jù)直至直接交付.也就是說,機(jī)會(huì)網(wǎng)絡(luò)可以允許節(jié)點(diǎn)在無法實(shí)現(xiàn)直接交付的情況下繼續(xù)攜帶數(shù)據(jù),直至完成直接交付.

采用直接交付方式固然可以提高分組投遞率,提升傳輸可靠性,但使用不當(dāng)也會(huì)帶來不利影響.尤其網(wǎng)絡(luò)中可能存在無法實(shí)現(xiàn)直接交付的情況,此時(shí)若強(qiáng)行采用直接交付,只會(huì)惡化網(wǎng)絡(luò)性能.因此,數(shù)據(jù)的傳輸必須遵循一定規(guī)則.本文從數(shù)據(jù)傳輸?shù)慕嵌瘸霭l(fā)設(shè)計(jì)數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)評(píng)價(jià)模型,同時(shí)結(jié)合節(jié)點(diǎn)活動(dòng)區(qū)間劃分方案,設(shè)計(jì)機(jī)會(huì)網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)傳輸規(guī)則.

2.1.1 數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)評(píng)價(jià)模型

為了適應(yīng)不同的應(yīng)用需求,結(jié)合機(jī)會(huì)網(wǎng)絡(luò)自身弱連接、間歇性通信的特點(diǎn),構(gòu)建數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)評(píng)價(jià)模型對(duì)待傳數(shù)據(jù)進(jìn)行分類,使數(shù)據(jù)的傳輸同網(wǎng)絡(luò)資源的調(diào)度以及應(yīng)用的需求更好地進(jìn)行匹配.數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)是節(jié)點(diǎn)在處理數(shù)據(jù)傳輸時(shí)決定數(shù)據(jù)被轉(zhuǎn)發(fā)的優(yōu)先等級(jí),節(jié)點(diǎn)根據(jù)優(yōu)先級(jí)的大小對(duì)數(shù)據(jù)采取不同的轉(zhuǎn)發(fā)策略.

影響數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)的因素包括數(shù)據(jù)的傳輸、數(shù)據(jù)的內(nèi)容以及應(yīng)用的要求.我們認(rèn)為:數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)與數(shù)據(jù)內(nèi)容的重要程度成正比,與參與傳輸?shù)墓?jié)點(diǎn)鏈優(yōu)先級(jí)成正比,與應(yīng)用的時(shí)延要求成反比.基于此,定義數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)(data forwarding priority,簡稱DFP)函數(shù)為:

其中,m代表數(shù)據(jù),γ表示從源節(jié)點(diǎn)s到當(dāng)前節(jié)點(diǎn)i的傳輸節(jié)點(diǎn)集合,Bm,Lm和Gγ(s,i)分別代表內(nèi)容優(yōu)先級(jí)、時(shí)延優(yōu)先級(jí)和節(jié)點(diǎn)鏈優(yōu)先級(jí).其中:內(nèi)容優(yōu)先級(jí)從信息內(nèi)容的角度反映數(shù)據(jù)的重要性,體現(xiàn)不同內(nèi)容的差異價(jià)值,可分為普通信息(ordinary information)、重要信息(important information)和重大信息(major information),優(yōu)先級(jí)依次遞增;時(shí)延優(yōu)先級(jí)體現(xiàn)應(yīng)用對(duì)傳輸時(shí)延的要求,可分為盡力而為傳輸(best effort delivery)、加急傳輸(urgent delivery)以及緊急傳輸(critical delivery),緊迫性依次遞增;節(jié)點(diǎn)鏈優(yōu)先級(jí)代表參與數(shù)據(jù)傳輸?shù)墓?jié)點(diǎn)的優(yōu)先程度,覆蓋整個(gè)傳輸節(jié)點(diǎn)鏈.凡有重要節(jié)點(diǎn)參與的傳輸,節(jié)點(diǎn)鏈優(yōu)先級(jí)要高,滿足:

其中,Gj代表節(jié)點(diǎn)j的優(yōu)先級(jí).

2.1.2 節(jié)點(diǎn)活動(dòng)范圍劃分

將節(jié)點(diǎn)的運(yùn)動(dòng)范圍劃分為4 個(gè)區(qū)域,分別為常規(guī)訪問區(qū)域(routine access area,簡稱RAA)、隨機(jī)訪問區(qū)域(RanDom acess area,簡稱 RDA)、權(quán)限訪問區(qū)域(authorized access area,簡稱 AAA)以及禁止訪問區(qū)域(InAccessible area,簡稱IAA),如圖2 所示.圖中的黑點(diǎn)代表節(jié)點(diǎn)的訪問足跡,深灰色區(qū)域代表常規(guī)訪問區(qū)域,淺灰色區(qū)域是隨機(jī)訪問區(qū)域,陰影部分表示權(quán)限訪問區(qū)域,其他部分則為禁止訪問區(qū)域.

Fig.2 Illustration of range of node activities圖2 節(jié)點(diǎn)活動(dòng)范圍示意圖

從圖中可以看出:

?常規(guī)訪問區(qū)域是節(jié)點(diǎn)訪問頻率最高的區(qū)域,節(jié)點(diǎn)去往常規(guī)訪問區(qū)域的概率最大.如果有需要發(fā)往該區(qū)域的數(shù)據(jù),節(jié)點(diǎn)可以隨身攜帶,在訪問過程中捎帶完成數(shù)據(jù)交付,此時(shí),數(shù)據(jù)的轉(zhuǎn)發(fā)對(duì)優(yōu)先級(jí)沒有要求.

?隨機(jī)訪問區(qū)域是節(jié)點(diǎn)偶爾會(huì)訪問的區(qū)域,節(jié)點(diǎn)對(duì)該區(qū)域的訪問是隨機(jī)的,如果有數(shù)據(jù)要發(fā)往該區(qū)域,則節(jié)點(diǎn)需要調(diào)整運(yùn)動(dòng)路線,這對(duì)于數(shù)據(jù)的優(yōu)先級(jí)有一定要求.

?權(quán)限訪問區(qū)域是節(jié)點(diǎn)尚未訪問過但是可以訪問的區(qū)域,若要節(jié)點(diǎn)改變路線前往權(quán)限訪問區(qū)域,需要較高的轉(zhuǎn)發(fā)優(yōu)先級(jí).

?禁止訪問區(qū)域代表節(jié)點(diǎn)不能訪問的區(qū)域,節(jié)點(diǎn)無法前往禁止訪問區(qū)域.

2.1.3 基于數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)與節(jié)點(diǎn)活動(dòng)范圍分布的傳輸規(guī)則設(shè)計(jì)

考慮到數(shù)據(jù)傳輸要求的多樣性以及節(jié)點(diǎn)活動(dòng)范圍的分布,根據(jù)目標(biāo)區(qū)域所在的位置信息,結(jié)合自身任務(wù)以及攜帶數(shù)據(jù)的轉(zhuǎn)發(fā)優(yōu)先級(jí)要求,動(dòng)態(tài)調(diào)整運(yùn)動(dòng)路線,優(yōu)先保證高優(yōu)先級(jí)數(shù)據(jù)的有效轉(zhuǎn)發(fā).考慮到任務(wù)調(diào)度的復(fù)雜性以及節(jié)點(diǎn)的運(yùn)動(dòng)路線規(guī)劃,基于活動(dòng)范圍分布情況,將節(jié)點(diǎn)的任務(wù)調(diào)度與活動(dòng)區(qū)間進(jìn)行映射以簡化設(shè)計(jì).

基于優(yōu)先級(jí)評(píng)價(jià)模型,將數(shù)據(jù)的轉(zhuǎn)發(fā)優(yōu)先級(jí)分為3 個(gè)等級(jí):緊急數(shù)據(jù)(emergency data)、優(yōu)先數(shù)據(jù)(priority data)和普通數(shù)據(jù)(plain data),優(yōu)先級(jí)依次遞減.結(jié)合節(jié)點(diǎn)活動(dòng)范圍劃分方案,確立數(shù)據(jù)傳輸規(guī)則的總體設(shè)計(jì)思路是:對(duì)緊急數(shù)據(jù)采取直接交付優(yōu)先原則,對(duì)普通數(shù)據(jù)以不影響節(jié)點(diǎn)的原有狀態(tài)為原則.

將節(jié)點(diǎn)的運(yùn)動(dòng)模式分為3 種,即固有運(yùn)動(dòng)(inherent move)模式、主動(dòng)運(yùn)動(dòng)(active move)模式以及協(xié)調(diào)運(yùn)動(dòng)(coordinated move)模式:在固有運(yùn)動(dòng)模式下,節(jié)點(diǎn)不受攜帶數(shù)據(jù)的影響,保持自身原有的運(yùn)動(dòng)狀態(tài),最大限度保障獨(dú)立性;在主動(dòng)運(yùn)動(dòng)模式下,節(jié)點(diǎn)為了實(shí)現(xiàn)數(shù)據(jù)的有效傳輸而改變運(yùn)動(dòng)狀態(tài),主動(dòng)調(diào)整自身的運(yùn)動(dòng)軌跡和行進(jìn)路線,朝著更有利于實(shí)現(xiàn)數(shù)據(jù)直接交付的方向運(yùn)動(dòng);在協(xié)調(diào)運(yùn)動(dòng)模式下,節(jié)點(diǎn)需要兼顧原有的任務(wù)調(diào)度和新的數(shù)據(jù)傳輸要求,適當(dāng)調(diào)整運(yùn)動(dòng)軌跡.

根據(jù)目標(biāo)區(qū)域的不同分布以及轉(zhuǎn)發(fā)數(shù)據(jù)的不同級(jí)別,節(jié)點(diǎn)采取不同的數(shù)據(jù)傳輸策略,見表1.

Table 1 Data transmission rules表1 數(shù)據(jù)傳輸規(guī)則

從表中可以看出,對(duì)緊急數(shù)據(jù)而言,除非目標(biāo)節(jié)點(diǎn)位于禁止訪問區(qū)域內(nèi),否則節(jié)點(diǎn)會(huì)主動(dòng)調(diào)整自己的行進(jìn)路線,朝著目標(biāo)節(jié)點(diǎn)方向運(yùn)動(dòng),實(shí)現(xiàn)數(shù)據(jù)的直接交付;對(duì)優(yōu)先數(shù)據(jù)來說,如果目標(biāo)節(jié)點(diǎn)位于常規(guī)訪問區(qū)域內(nèi),說明在轉(zhuǎn)發(fā)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間建立直接通信的可能性較大.鑒于優(yōu)先數(shù)據(jù)的轉(zhuǎn)發(fā)要求并非十分迫切(優(yōu)先數(shù)據(jù)的優(yōu)先級(jí)低于緊急數(shù)據(jù)),此時(shí)可依靠轉(zhuǎn)發(fā)節(jié)點(diǎn)的固有運(yùn)動(dòng)來實(shí)現(xiàn)數(shù)據(jù)的直接交付.其傳輸時(shí)延與緊急數(shù)據(jù)相比會(huì)有所增加,但是節(jié)點(diǎn)的運(yùn)動(dòng)狀態(tài)可以不受影響,保證了獨(dú)立性.而針對(duì)目標(biāo)節(jié)點(diǎn)位于隨機(jī)訪問區(qū)域的情況,則有必要通過節(jié)點(diǎn)的主動(dòng)運(yùn)動(dòng)實(shí)現(xiàn)數(shù)據(jù)的直接交付.倘若目標(biāo)節(jié)點(diǎn)位于轉(zhuǎn)發(fā)節(jié)點(diǎn)不曾訪問過的區(qū)域(包括權(quán)限訪問區(qū)域和禁止訪問區(qū)域),則需要通過尋找合適的下一跳節(jié)點(diǎn)來實(shí)現(xiàn)數(shù)據(jù)的有效轉(zhuǎn)發(fā).對(duì)優(yōu)先級(jí)最低的普通數(shù)據(jù)來說,目標(biāo)節(jié)點(diǎn)所處區(qū)域?qū)Σ扇〉臄?shù)據(jù)傳輸策略并無太大影響,節(jié)點(diǎn)的運(yùn)動(dòng)軌跡也不會(huì)因此發(fā)生改變,節(jié)點(diǎn)始終保持原有的運(yùn)動(dòng)狀態(tài),保證了獨(dú)立性.

2.1.4 差異化副本傳輸策略

機(jī)會(huì)網(wǎng)絡(luò)通常采用多副本傳輸策略來保障數(shù)據(jù)的投遞,同時(shí)也會(huì)給系統(tǒng)帶來一定開銷.考慮到數(shù)據(jù)轉(zhuǎn)發(fā)的優(yōu)先級(jí)要求,我們認(rèn)為,不同類型的數(shù)據(jù)傳輸其目標(biāo)也不盡相同.對(duì)緊急數(shù)據(jù)而言,及時(shí)且有效的投遞是第一要義;而對(duì)普通數(shù)據(jù)來說,系統(tǒng)開銷問題則更受關(guān)注,投遞失敗在一定程度上也是可以容忍的.基于此,我們?cè)O(shè)計(jì)了基于數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)的差異化副本傳輸策略.

?針對(duì)低優(yōu)先級(jí)數(shù)據(jù)采取條件轉(zhuǎn)發(fā)策略,選擇合適的中繼節(jié)點(diǎn)完成數(shù)據(jù)的傳輸,依靠節(jié)點(diǎn)的固有運(yùn)動(dòng)轉(zhuǎn)發(fā)數(shù)據(jù),將副本數(shù)量控制在較低水平,以降低系統(tǒng)開銷.

?針對(duì)高優(yōu)先級(jí)數(shù)據(jù),采取運(yùn)動(dòng)交付輔以洪泛傳輸?shù)膹?fù)合方式.一方面,通過節(jié)點(diǎn)的主動(dòng)運(yùn)動(dòng)實(shí)現(xiàn)數(shù)據(jù)的直接交付;另一方面采取洪泛策略,將數(shù)據(jù)轉(zhuǎn)發(fā)給遇到的節(jié)點(diǎn).這種并行的傳輸方式能夠保障數(shù)據(jù)的及時(shí)有效投遞.

?為降低對(duì)其他傳輸任務(wù)的干擾,為優(yōu)先級(jí)最高的緊急數(shù)據(jù)傳輸設(shè)計(jì)互斥保護(hù)機(jī)制(mutex protection),規(guī)定只有第1 個(gè)收到該緊急數(shù)據(jù)的節(jié)點(diǎn)采取主動(dòng)運(yùn)動(dòng)轉(zhuǎn)發(fā)方式,其他節(jié)點(diǎn)只需進(jìn)行洪泛,仍然維持自身原有的運(yùn)動(dòng)狀態(tài).

?節(jié)點(diǎn)的主動(dòng)運(yùn)動(dòng)傳輸可以與洪泛傳輸有效互補(bǔ),彌補(bǔ)了部分場(chǎng)景下洪泛傳輸覆蓋范圍不足的問題,保

證了數(shù)據(jù)的有效投遞,進(jìn)一步降低傳輸時(shí)延.

2.1.5 同向數(shù)據(jù)捎帶傳輸策略

主動(dòng)運(yùn)動(dòng)轉(zhuǎn)發(fā)有可能造成節(jié)點(diǎn)向同一目標(biāo)區(qū)域聚集,如圖3 所示.源節(jié)點(diǎn)Src將數(shù)據(jù)傳遞給鄰居節(jié)點(diǎn)A和B.A,B皆處于主動(dòng)運(yùn)動(dòng)狀態(tài),由于互斥保護(hù)機(jī)制,只能將數(shù)據(jù)分別洪泛擴(kuò)散給C,D和E,F.節(jié)點(diǎn)D和F可以進(jìn)行運(yùn)動(dòng)轉(zhuǎn)發(fā),攜帶數(shù)據(jù)向目標(biāo)區(qū)域運(yùn)動(dòng).節(jié)點(diǎn)E由于已經(jīng)處于主動(dòng)運(yùn)動(dòng)狀態(tài),只能繼續(xù)洪泛給節(jié)點(diǎn)G,使得G也向目標(biāo)區(qū)域運(yùn)動(dòng),在一定程度上導(dǎo)致節(jié)點(diǎn)向同一目標(biāo)區(qū)域聚集,帶來局部通信流量增大,且會(huì)造成網(wǎng)絡(luò)資源浪費(fèi).考慮到中繼節(jié)點(diǎn)向同一目標(biāo)區(qū)域運(yùn)動(dòng)過程中可能遭遇,我們采取同向數(shù)據(jù)捎帶傳輸策略,通過節(jié)點(diǎn)間的協(xié)商實(shí)現(xiàn)數(shù)據(jù)的捎帶傳遞,既釋放了網(wǎng)絡(luò)資源,又避免了流量沖突.

Fig.3 Illustration of how nodes converge together圖3 節(jié)點(diǎn)聚集示意圖

2.2 效用函數(shù)設(shè)計(jì)

在現(xiàn)實(shí)網(wǎng)絡(luò)環(huán)境中,受限于某些條件,如節(jié)點(diǎn)分布、運(yùn)動(dòng)狀態(tài)、節(jié)點(diǎn)級(jí)別、可用資源等,導(dǎo)致節(jié)點(diǎn)的運(yùn)動(dòng)范圍受到一定限制,無法實(shí)現(xiàn)直接交付.此時(shí),只能通過尋找合適的中繼節(jié)點(diǎn)來轉(zhuǎn)發(fā)數(shù)據(jù).因此,中繼節(jié)點(diǎn)的選擇就成為一個(gè)重要問題.

一般來說,節(jié)點(diǎn)i為網(wǎng)絡(luò)中所有節(jié)點(diǎn)維護(hù)一個(gè)效用函數(shù)Ui(?),τi(j)代表節(jié)點(diǎn)i和節(jié)點(diǎn)j的相遇間隔時(shí)間,Ui(?)是τi(?)的單調(diào)遞減函數(shù),有:

A節(jié)點(diǎn)攜帶有去往目標(biāo)節(jié)點(diǎn)D的數(shù)據(jù),當(dāng)且僅當(dāng)滿足:

數(shù)據(jù)才會(huì)由A轉(zhuǎn)發(fā)至B.效用函數(shù)的設(shè)計(jì)對(duì)路由性能的影響很大.

2.2.1 運(yùn)動(dòng)自由度模型

機(jī)會(huì)網(wǎng)絡(luò)利用節(jié)點(diǎn)運(yùn)動(dòng)帶來的連接機(jī)會(huì)傳輸數(shù)據(jù),應(yīng)該充分利用節(jié)點(diǎn)的運(yùn)動(dòng)特性,更好地為數(shù)據(jù)傳輸服務(wù).尤其在進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時(shí),需要重點(diǎn)考量節(jié)點(diǎn)的運(yùn)動(dòng)性.運(yùn)動(dòng)自由度Fi代表節(jié)點(diǎn)進(jìn)行自由運(yùn)動(dòng)的能力,取決于節(jié)點(diǎn)的活動(dòng)范圍Ri、節(jié)點(diǎn)中心度Hi以及剩余能量Ei,滿足:

其中,α和β分別代表影響因子,δi表示擾動(dòng)因素.活動(dòng)范圍反映節(jié)點(diǎn)的活動(dòng)區(qū)域分布情況,滿足:

其中,T表示網(wǎng)絡(luò)節(jié)點(diǎn)集合.可以看出,禁止訪問區(qū)域范圍越小,節(jié)點(diǎn)的活動(dòng)空間越廣,運(yùn)動(dòng)自由度越大.節(jié)點(diǎn)中心度反映節(jié)點(diǎn)在通信過程中的地位,取決于上下游節(jié)點(diǎn)間的通信聯(lián)系.定義入度(incoming degree)代表將數(shù)據(jù)直接轉(zhuǎn)發(fā)給自己的上游節(jié)點(diǎn)數(shù)目占節(jié)點(diǎn)總數(shù)的比例,出度(outgoing degree)代表接收轉(zhuǎn)發(fā)數(shù)據(jù)的直接下游節(jié)點(diǎn)數(shù)目占節(jié)點(diǎn)總數(shù)的比例,有:

其中,Ii和Oi分別代表節(jié)點(diǎn)i的入度和出度,i?1 和i+1 分別表示節(jié)點(diǎn)i的直接上游節(jié)點(diǎn)和直接下游節(jié)點(diǎn),N代表節(jié)點(diǎn)數(shù)目.入度越高,說明節(jié)點(diǎn)的通信樞紐地位越強(qiáng),越容易成為流量匯聚中心;出度越高,表示節(jié)點(diǎn)擁有的轉(zhuǎn)發(fā)選擇越多,通信適應(yīng)性越強(qiáng).基于此,定義機(jī)會(huì)網(wǎng)絡(luò)的節(jié)點(diǎn)中心度指標(biāo)Hi滿足:

其中,u,v分別代表中心度入權(quán)和中心度出權(quán).節(jié)點(diǎn)中心度越高,對(duì)其運(yùn)動(dòng)限制能力越強(qiáng),運(yùn)動(dòng)自由度越低.剩余能量代表節(jié)點(diǎn)當(dāng)前的能量水平,對(duì)其進(jìn)行歸一化處理,得到:

考慮到節(jié)點(diǎn)能耗與數(shù)據(jù)收發(fā)的關(guān)系最為密切[25,26],建立數(shù)據(jù)收發(fā)與能耗之間的關(guān)聯(lián):

節(jié)點(diǎn)的剩余能量水平越高,運(yùn)動(dòng)能力越強(qiáng),運(yùn)動(dòng)自由度越高.綜合式(5)～式(14),得到:

2.2.2 效用函數(shù)模型

傳統(tǒng)觀點(diǎn)認(rèn)為:節(jié)點(diǎn)中心地位越高,在轉(zhuǎn)發(fā)中所起的作用越大,越適合成為中繼節(jié)點(diǎn).而實(shí)際在資源均等的情況下,節(jié)點(diǎn)中心度越高,流量越集中,往往會(huì)導(dǎo)致局部通信擁塞,反而不利于數(shù)據(jù)的傳輸.利用節(jié)點(diǎn)的運(yùn)動(dòng)特性轉(zhuǎn)發(fā)數(shù)據(jù),應(yīng)該將運(yùn)動(dòng)性放在首位考慮.同時(shí),為了體現(xiàn)傳輸?shù)奶攸c(diǎn),將數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)同步納入效用函數(shù)參考模型,定義效用函數(shù)滿足:

綜合式(1)、式(2)、式(15)、式(16),有:

效用函數(shù)能夠綜合反映節(jié)點(diǎn)的運(yùn)動(dòng)水平和數(shù)據(jù)優(yōu)先級(jí)狀況,表征傳輸?shù)亩嘀貙傩?剔除與數(shù)據(jù)直接相關(guān)的變量,定義效用函數(shù)指標(biāo)UFI(utility function index)為

在傳輸高優(yōu)先數(shù)據(jù)時(shí),優(yōu)先考慮數(shù)據(jù)的投遞,通過節(jié)點(diǎn)的主動(dòng)運(yùn)動(dòng)和洪泛傳輸來保障;在傳輸普通數(shù)據(jù)時(shí),優(yōu)先考慮系統(tǒng)開銷以及節(jié)點(diǎn)原有的任務(wù)調(diào)度,通過衡量節(jié)點(diǎn)鏈優(yōu)先級(jí)以及節(jié)點(diǎn)的運(yùn)動(dòng)性來決定是否轉(zhuǎn)發(fā).通常來說,節(jié)點(diǎn)鏈優(yōu)先級(jí)越高,節(jié)點(diǎn)運(yùn)動(dòng)性越強(qiáng),越適合成為轉(zhuǎn)發(fā)節(jié)點(diǎn).節(jié)點(diǎn)在相遇時(shí),通過比較UFI值,使得數(shù)據(jù)從UFI值較低的一方向較高的一方傳輸,實(shí)現(xiàn)數(shù)據(jù)的轉(zhuǎn)發(fā).

2.3 算法設(shè)計(jì)與實(shí)現(xiàn)

隨著GPS 等設(shè)備的廣泛應(yīng)用,節(jié)點(diǎn)的位置已經(jīng)成為網(wǎng)絡(luò)中的一個(gè)重要信息.系統(tǒng)配備節(jié)點(diǎn)位置服務(wù)器統(tǒng)一對(duì)節(jié)點(diǎn)的位置信息進(jìn)行管理.節(jié)點(diǎn)采取預(yù)發(fā)布形式將自己的行程安排提前公布,供需要的節(jié)點(diǎn)查詢.預(yù)發(fā)布行程的消息格式如圖4 所示.

Fig.4 Itinerary pre-release message圖4 行程預(yù)發(fā)布消息

其中,結(jié)束時(shí)間屬于可選項(xiàng).如果節(jié)點(diǎn)位置發(fā)生較大變化,即當(dāng)前位置與預(yù)發(fā)布行程位置的距離偏差超過偏航閾值時(shí),需要主動(dòng)向服務(wù)器推送實(shí)時(shí)位置更新消息,格式如圖5 所示.

Fig.5 Real time location update message圖5 實(shí)時(shí)位置更新消息

位置服務(wù)器按照接收消息的序列號(hào)更新位置信息列表,供節(jié)點(diǎn)查詢.當(dāng)收到節(jié)點(diǎn)的位置查詢請(qǐng)求時(shí),位置服務(wù)器返回目標(biāo)的當(dāng)前位置信息.

節(jié)點(diǎn)相遇后,交換擴(kuò)散向量列表DiffusionVector和轉(zhuǎn)發(fā)消息隊(duì)列MessageQueue,然后針對(duì)擴(kuò)散向量集合DV中的每個(gè)數(shù)據(jù)包pkt∈DV,根據(jù)其消息類型進(jìn)行如下處理.

3 實(shí)驗(yàn)仿真及性能評(píng)估

使用ONE(opportunistic networking environment)[27]工具進(jìn)行仿真.在現(xiàn)實(shí)生活場(chǎng)景中,節(jié)點(diǎn)往往以群組形式出現(xiàn),且不同群組中的節(jié)點(diǎn)具有不同屬性.以園區(qū)場(chǎng)景為例,群組對(duì)象包括3 類:高管(senior executives)、中層管理人員(mid-level management)以及普通工人(workers),其中:高管的節(jié)點(diǎn)優(yōu)先級(jí)最高,中層管理人員次之,普通工人優(yōu)先級(jí)最低.園區(qū)分布如圖6 所示,包含住宅區(qū)(包括員工宿舍、管理公寓、高級(jí)公寓)、生活區(qū)(包括餐廳I和餐廳II、超市、學(xué)校、幼兒園、醫(yī)院、商業(yè)區(qū))、生產(chǎn)區(qū)(包括生產(chǎn)區(qū)I～VII)以及辦公區(qū)(包括管理服務(wù)區(qū)I,II以及高管辦公區(qū)).根據(jù)不同對(duì)象的日常行為特點(diǎn),定義各自的訪問區(qū)域界定見表2.

Fig.6 Sketch map of an industrial park圖6 園區(qū)示意圖

Table 2 Illustration of visit area definition for park staff表2 園區(qū)人員訪問區(qū)域界定

各優(yōu)先級(jí)參數(shù)均統(tǒng)一設(shè)置為3 級(jí),對(duì)應(yīng)優(yōu)先級(jí)值分別為4,2 和1.不同參數(shù)的數(shù)量占比均以百分比形式顯示,見表3.依據(jù)表3 中各優(yōu)先級(jí)參數(shù)值及其比例,計(jì)算數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級(jí)取值概率,結(jié)果見表4.其他實(shí)驗(yàn)參數(shù)見表5.

Table 3 Priority values and occupation ratios表3 優(yōu)先級(jí)值與占比

Table 4 DFP values and probabilities表4 DFP 取值及其概率

Table 5 Experimental parameters表5 實(shí)驗(yàn)參數(shù)

選取Direct Transmission(DT)、Epidemic Routing、Spray and Wait(S&W)以及PRoPHET,與MBOR 進(jìn)行比較,考察算法性能.

(1) 分組投遞率:成功接收的分組數(shù)目占發(fā)送的分組數(shù)目的比例.

改變節(jié)點(diǎn)密度,統(tǒng)計(jì)得到各協(xié)議的分組投遞率如圖7 所示.

Fig.7 Impact of node number on packet delivery ratio圖7 節(jié)點(diǎn)數(shù)目對(duì)分組投遞率的影響

提高節(jié)點(diǎn)密度可以從一定程度上提升網(wǎng)絡(luò)連接性,使投遞的分組數(shù)目增多,但同時(shí)也會(huì)產(chǎn)生更多的冗余.由于采用了全網(wǎng)洪泛策略,Epidemic 的分組投遞率最低.與其相比,DT 的單副本傳輸策略、S&W 的部分洪泛機(jī)制以及PRoPHET 的節(jié)點(diǎn)選擇機(jī)制均能有效降低產(chǎn)生的分組數(shù)目,獲得比Epidemic 的盲轉(zhuǎn)發(fā)更高的分組投遞率.MBOR 的運(yùn)動(dòng)轉(zhuǎn)發(fā)機(jī)制能更好地保證分組的投遞.盡管其差異化副本傳輸策略針對(duì)高優(yōu)先級(jí)數(shù)據(jù)同樣采取洪泛方式進(jìn)行傳輸,但此類數(shù)據(jù)往往占比較低.對(duì)于數(shù)量最多的普通數(shù)據(jù),MBOR 采取條件轉(zhuǎn)發(fā)策略,在抑制副本數(shù)目、限制盲目洪泛的同時(shí)選擇更具運(yùn)動(dòng)靈活性的節(jié)點(diǎn)參與數(shù)據(jù)轉(zhuǎn)發(fā),進(jìn)一步提升投遞成功率.

固定節(jié)點(diǎn)數(shù)目、改變網(wǎng)絡(luò)負(fù)載大小,研究分組投遞率的變化情況如圖8 所示.從圖中可以明顯看出,隨著網(wǎng)絡(luò)負(fù)載的增加,各協(xié)議的投遞率均出現(xiàn)了明顯的下降.這是由于過大的負(fù)載造成緩存溢出,導(dǎo)致數(shù)據(jù)丟包,從而降低了投遞率.

Fig.8 Impact of network load on packet delivery rate圖8 網(wǎng)絡(luò)負(fù)載對(duì)分組投遞率的影響

(2) 傳輸延遲:消息從源節(jié)點(diǎn)發(fā)出直至抵達(dá)目標(biāo)節(jié)點(diǎn)所經(jīng)歷的時(shí)間.

由于DT 協(xié)議采取了單副本傳輸策略,節(jié)點(diǎn)緩存數(shù)據(jù)直到遇到目標(biāo)節(jié)點(diǎn),無需中繼,其傳輸時(shí)延取決于節(jié)點(diǎn)的相遇概率.對(duì)其他協(xié)議而言,隨著節(jié)點(diǎn)數(shù)目的增加,節(jié)點(diǎn)的路徑選擇增多,更容易找到一條時(shí)延更短的路徑,如圖9 所示.

傳輸時(shí)延受網(wǎng)絡(luò)流量變化的影響如圖10 所示.從圖中可以看出,隨著網(wǎng)絡(luò)負(fù)載的增加,丟包率逐步增大,增加了傳輸延遲.由于采用了全網(wǎng)洪泛策略,在負(fù)載較小的情況下,Epidemic 能夠獲得較低的傳輸時(shí)延.但是隨著流量的增加,丟包率會(huì)隨之上升,導(dǎo)致延遲增大.MBOR 協(xié)議通過節(jié)點(diǎn)的主動(dòng)運(yùn)動(dòng)對(duì)洪泛傳輸進(jìn)行適當(dāng)補(bǔ)充,有效彌補(bǔ)了洪泛傳播覆蓋范圍不足的問題.同時(shí),MBOR 的同向數(shù)據(jù)捎帶機(jī)制能夠在保證高優(yōu)先數(shù)據(jù)有效投遞的前提下釋放冗余的傳輸資源,優(yōu)化任務(wù)調(diào)度,進(jìn)一步降低傳輸時(shí)延.

Fig.9 Impact of node number on packet delay圖9 節(jié)點(diǎn)數(shù)目對(duì)分組延遲的影響

Fig.10 Impact of network load on packet delay圖10 網(wǎng)絡(luò)負(fù)載對(duì)分組延遲的影響

(3) 投遞開銷率:節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)包數(shù)量與成功投遞的數(shù)據(jù)包數(shù)量之間的比值.

投遞開銷率越高,說明節(jié)點(diǎn)完成數(shù)據(jù)傳輸所需的代價(jià)越大,占用資源越多.網(wǎng)絡(luò)負(fù)載對(duì)投遞開銷率的影響如圖11 所示.從圖中可以看出,由于DT 協(xié)議只會(huì)將數(shù)據(jù)直接交付給目標(biāo)節(jié)點(diǎn),無需控制信令的傳遞,不會(huì)產(chǎn)生額外的開銷,因此其開銷最低.Epidemic 的全網(wǎng)洪泛導(dǎo)致網(wǎng)絡(luò)中產(chǎn)生大量冗余分組,投遞開銷率較高.對(duì)MBOR 協(xié)議而言,由于需要獲取節(jié)點(diǎn)位置信息以及進(jìn)行運(yùn)動(dòng)轉(zhuǎn)發(fā),會(huì)在網(wǎng)絡(luò)中產(chǎn)生一定的控制開銷.與此同時(shí),MBOR 采取的數(shù)據(jù)捎帶傳輸策略可以釋放冗余的網(wǎng)絡(luò)資源,實(shí)現(xiàn)傳輸資源的二次分配,緩解局部流量擁塞.其差異化副本傳輸策略在保證高優(yōu)先數(shù)據(jù)投遞的同時(shí),也會(huì)抑制盲目轉(zhuǎn)發(fā)導(dǎo)致的分組冗余問題.同時(shí),節(jié)點(diǎn)挑選合適的中繼節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā),能進(jìn)一步降低網(wǎng)絡(luò)開銷.

Fig.11 Impact of network load on delivery overhead ratio圖11 網(wǎng)絡(luò)負(fù)載對(duì)投遞開銷率的影響

(4) 緩存對(duì)算法性能的影響.

改變節(jié)點(diǎn)緩存大小,考察各指標(biāo)的變化情況,結(jié)果如圖12 所示.可以明顯看出,隨著緩存的增加,丟包減少,存儲(chǔ)的分組數(shù)目增多,網(wǎng)絡(luò)中傳輸?shù)姆纸M數(shù)目也相應(yīng)增大,投遞率增大.

Fig.12 Impact of buffer size on packet delivery ratio,delay and delivery overhead ratio圖12 緩存大小對(duì)分組投遞率、延遲和投遞開銷率的影響

4 結(jié) 論

本文基于節(jié)點(diǎn)的運(yùn)動(dòng)特性設(shè)計(jì)機(jī)會(huì)網(wǎng)絡(luò)路由算法,通過對(duì)節(jié)點(diǎn)運(yùn)動(dòng)軌跡的調(diào)整,構(gòu)建快速有效的通信連接.綜合考慮數(shù)據(jù)的傳輸效率以及網(wǎng)絡(luò)開銷,設(shè)計(jì)差異化副本傳輸策略,針對(duì)不同優(yōu)先級(jí)數(shù)據(jù)采取不同的傳輸機(jī)制.基于節(jié)點(diǎn)運(yùn)動(dòng)水平設(shè)計(jì)效用函數(shù),實(shí)現(xiàn)中繼節(jié)點(diǎn)的優(yōu)化選擇.實(shí)驗(yàn)表明:MBOR算法能夠在限制系統(tǒng)開銷的同時(shí)保障分組的投遞,獲得更低的傳輸時(shí)延.