基于節點運動的機會網絡路由算法?

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

(湖北經濟學院 信息與通信工程學院,湖北 武漢 430205)

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

Fig.1 Illustration of routing in opportunistic networks圖1 機會網絡路由示意圖

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

1 相關工作

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

(1) 基于副本的路由

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

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

基于主動運動的路由機制通過引入部分能夠實現主動移動的特殊節點,來為其他普通節點提供通信服務.DataMULEs[11]引入了MULE 節點,在移動過程中收集傳感器數據,實現稀疏傳感器網絡環境下的數據采集.Message Ferrying[12]協議在區域內部署Ferry 節點,按預定義路徑或普通節點的通信請求,在移動過程中實現數據的轉發.Zhao 等人[13]在Message Ferrying 的基礎上,提出使用多個Ferry 節點以提高系統的可靠性和傳輸效率.

(3) 基于效用的路由

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

以上路由機制中,基于副本的路由策略通過在網絡中生成多個消息副本來保證數據的傳輸.這種消息的復制對網絡資源要求很高,會在網絡中產生大量冗余,導致資源浪費.基于主動運動的路由通過引入某些具有移動功能的特殊節點來輔助數據的傳輸.此類節點往往具有較強的運動能力、通信能力以及存儲能力,與普通節點差別很大.而且算法假設目標節點的位置是固定的,并沒有考慮到移動節點間的數據通信.而基于效用的路由策略主要利用相遇預測、鏈路狀態以及上下文等信息計算效用值,并沒有充分考慮數據傳輸的不同要求以及節點自身的運動特質對路由的影響.

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

2 MBOR 路由算法

2.1 數據傳輸機制

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

采用直接交付方式固然可以提高分組投遞率,提升傳輸可靠性,但使用不當也會帶來不利影響.尤其網絡中可能存在無法實現直接交付的情況,此時若強行采用直接交付,只會惡化網絡性能.因此,數據的傳輸必須遵循一定規則.本文從數據傳輸的角度出發設計數據轉發優先級評價模型,同時結合節點活動區間劃分方案,設計機會網絡環境下的數據傳輸規則.

2.1.1 數據轉發優先級評價模型

為了適應不同的應用需求,結合機會網絡自身弱連接、間歇性通信的特點,構建數據轉發優先級評價模型對待傳數據進行分類,使數據的傳輸同網絡資源的調度以及應用的需求更好地進行匹配.數據轉發優先級是節點在處理數據傳輸時決定數據被轉發的優先等級,節點根據優先級的大小對數據采取不同的轉發策略.

影響數據轉發優先級的因素包括數據的傳輸、數據的內容以及應用的要求.我們認為:數據轉發優先級與數據內容的重要程度成正比,與參與傳輸的節點鏈優先級成正比,與應用的時延要求成反比.基于此,定義數據轉發優先級(data forwarding priority,簡稱DFP)函數為:

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

其中,Gj代表節點j的優先級.

2.1.2 節點活動范圍劃分

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

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

從圖中可以看出:

?常規訪問區域是節點訪問頻率最高的區域,節點去往常規訪問區域的概率最大.如果有需要發往該區域的數據,節點可以隨身攜帶,在訪問過程中捎帶完成數據交付,此時,數據的轉發對優先級沒有要求.

?隨機訪問區域是節點偶爾會訪問的區域,節點對該區域的訪問是隨機的,如果有數據要發往該區域,則節點需要調整運動路線,這對于數據的優先級有一定要求.

?權限訪問區域是節點尚未訪問過但是可以訪問的區域,若要節點改變路線前往權限訪問區域,需要較高的轉發優先級.

?禁止訪問區域代表節點不能訪問的區域,節點無法前往禁止訪問區域.

2.1.3 基于數據轉發優先級與節點活動范圍分布的傳輸規則設計

考慮到數據傳輸要求的多樣性以及節點活動范圍的分布,根據目標區域所在的位置信息,結合自身任務以及攜帶數據的轉發優先級要求,動態調整運動路線,優先保證高優先級數據的有效轉發.考慮到任務調度的復雜性以及節點的運動路線規劃,基于活動范圍分布情況,將節點的任務調度與活動區間進行映射以簡化設計.

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

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

根據目標區域的不同分布以及轉發數據的不同級別,節點采取不同的數據傳輸策略,見表1.

Table 1 Data transmission rules表1 數據傳輸規則

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

2.1.4 差異化副本傳輸策略

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

?針對低優先級數據采取條件轉發策略,選擇合適的中繼節點完成數據的傳輸,依靠節點的固有運動轉發數據,將副本數量控制在較低水平,以降低系統開銷.

?針對高優先級數據,采取運動交付輔以洪泛傳輸的復合方式.一方面,通過節點的主動運動實現數據的直接交付;另一方面采取洪泛策略,將數據轉發給遇到的節點.這種并行的傳輸方式能夠保障數據的及時有效投遞.

?為降低對其他傳輸任務的干擾,為優先級最高的緊急數據傳輸設計互斥保護機制(mutex protection),規定只有第1 個收到該緊急數據的節點采取主動運動轉發方式,其他節點只需進行洪泛,仍然維持自身原有的運動狀態.

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

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

2.1.5 同向數據捎帶傳輸策略

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

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

2.2 效用函數設計

在現實網絡環境中,受限于某些條件,如節點分布、運動狀態、節點級別、可用資源等,導致節點的運動范圍受到一定限制,無法實現直接交付.此時,只能通過尋找合適的中繼節點來轉發數據.因此,中繼節點的選擇就成為一個重要問題.

一般來說,節點i為網絡中所有節點維護一個效用函數Ui(?),τi(j)代表節點i和節點j的相遇間隔時間,Ui(?)是τi(?)的單調遞減函數,有:

A節點攜帶有去往目標節點D的數據,當且僅當滿足:

數據才會由A轉發至B.效用函數的設計對路由性能的影響很大.

2.2.1 運動自由度模型

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

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

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

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

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

考慮到節點能耗與數據收發的關系最為密切[25,26],建立數據收發與能耗之間的關聯:

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

2.2.2 效用函數模型

傳統觀點認為:節點中心地位越高,在轉發中所起的作用越大,越適合成為中繼節點.而實際在資源均等的情況下,節點中心度越高,流量越集中,往往會導致局部通信擁塞,反而不利于數據的傳輸.利用節點的運動特性轉發數據,應該將運動性放在首位考慮.同時,為了體現傳輸的特點,將數據轉發優先級同步納入效用函數參考模型,定義效用函數滿足:

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

效用函數能夠綜合反映節點的運動水平和數據優先級狀況,表征傳輸的多重屬性.剔除與數據直接相關的變量,定義效用函數指標UFI(utility function index)為

在傳輸高優先數據時,優先考慮數據的投遞,通過節點的主動運動和洪泛傳輸來保障;在傳輸普通數據時,優先考慮系統開銷以及節點原有的任務調度,通過衡量節點鏈優先級以及節點的運動性來決定是否轉發.通常來說,節點鏈優先級越高,節點運動性越強,越適合成為轉發節點.節點在相遇時,通過比較UFI值,使得數據從UFI值較低的一方向較高的一方傳輸,實現數據的轉發.

2.3 算法設計與實現

隨著GPS 等設備的廣泛應用,節點的位置已經成為網絡中的一個重要信息.系統配備節點位置服務器統一對節點的位置信息進行管理.節點采取預發布形式將自己的行程安排提前公布,供需要的節點查詢.預發布行程的消息格式如圖4 所示.

Fig.4 Itinerary pre-release message圖4 行程預發布消息

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

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

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

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

3 實驗仿真及性能評估

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

Fig.6 Sketch map of an industrial park圖6 園區示意圖

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

各優先級參數均統一設置為3 級,對應優先級值分別為4,2 和1.不同參數的數量占比均以百分比形式顯示,見表3.依據表3 中各優先級參數值及其比例,計算數據轉發優先級取值概率,結果見表4.其他實驗參數見表5.

Table 3 Priority values and occupation ratios表3 優先級值與占比

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

Table 5 Experimental parameters表5 實驗參數

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

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

改變節點密度,統計得到各協議的分組投遞率如圖7 所示.

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

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

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

Fig.8 Impact of network load on packet delivery rate圖8 網絡負載對分組投遞率的影響

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

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

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

Fig.9 Impact of node number on packet delay圖9 節點數目對分組延遲的影響

Fig.10 Impact of network load on packet delay圖10 網絡負載對分組延遲的影響

(3) 投遞開銷率:節點轉發的數據包數量與成功投遞的數據包數量之間的比值.

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

Fig.11 Impact of network load on delivery overhead ratio圖11 網絡負載對投遞開銷率的影響

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

改變節點緩存大小,考察各指標的變化情況,結果如圖12 所示.可以明顯看出,隨著緩存的增加,丟包減少,存儲的分組數目增多,網絡中傳輸的分組數目也相應增大,投遞率增大.

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

4 結 論

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