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

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

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

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

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

1 相關(guān)工作

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

(1) 基于副本的路由

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

(2) 基于主動運動的路由

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

(3) 基于效用的路由

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

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

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

2 MBOR 路由算法

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

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

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

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

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

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

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

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

2.1.2 節(jié)點活動范圍劃分

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

Fig.2 Illustration of range of node activities圖2 節(jié)點活動范圍示意圖

從圖中可以看出:

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

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

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

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

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

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

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

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

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

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

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

2.1.4 差異化副本傳輸策略

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

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

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

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

?節(jié)點的主動運動傳輸可以與洪泛傳輸有效互補,彌補了部分場景下洪泛傳輸覆蓋范圍不足的問題,保

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

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

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

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

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

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

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

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

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

2.2.1 運動自由度模型

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

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

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

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

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

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

節(jié)點的剩余能量水平越高,運動能力越強,運動自由度越高.綜合式(5)～式(14),得到:

2.2.2 效用函數(shù)模型

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

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

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

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

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

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

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

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

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

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

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

3 實驗仿真及性能評估

使用ONE(opportunistic networking environment)[27]工具進行仿真.在現(xiàn)實生活場景中,節(jié)點往往以群組形式出現(xiàn),且不同群組中的節(jié)點具有不同屬性.以園區(qū)場景為例,群組對象包括3 類:高管(senior executives)、中層管理人員(mid-level management)以及普通工人(workers),其中:高管的節(jié)點優(yōu)先級最高,中層管理人員次之,普通工人優(yōu)先級最低.園區(qū)分布如圖6 所示,包含住宅區(qū)(包括員工宿舍、管理公寓、高級公寓)、生活區(qū)(包括餐廳I和餐廳II、超市、學(xué)校、幼兒園、醫(yī)院、商業(yè)區(qū))、生產(chǎn)區(qū)(包括生產(chǎn)區(qū)I～VII)以及辦公區(qū)(包括管理服務(wù)區(qū)I,II以及高管辦公區(qū)).根據(jù)不同對象的日常行為特點,定義各自的訪問區(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)先級參數(shù)均統(tǒng)一設(shè)置為3 級,對應(yīng)優(yōu)先級值分別為4,2 和1.不同參數(shù)的數(shù)量占比均以百分比形式顯示,見表3.依據(jù)表3 中各優(yōu)先級參數(shù)值及其比例,計算數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先級取值概率,結(jié)果見表4.其他實驗參數(shù)見表5.

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

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

Table 5 Experimental parameters表5 實驗參數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

改變節(jié)點緩存大小,考察各指標的變化情況,結(jié)果如圖12 所示.可以明顯看出,隨著緩存的增加,丟包減少,存儲的分組數(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 緩存大小對分組投遞率、延遲和投遞開銷率的影響

4 結(jié) 論

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