基于接觸信息的自適應機會網絡路由算法

武淑艷 韓毅剛 傅秋宇 馮 飛

(南開大學電子信息與光學工程學院 天津 300350)

?

基于接觸信息的自適應機會網絡路由算法

武淑艷 韓毅剛 傅秋宇 馮 飛

(南開大學電子信息與光學工程學院 天津 300350)

考慮到實際網絡環境的不斷變化以及機會網絡節點總是在密集與稀疏場景間隨機切換的特點，提出一種能夠借助節點接觸信息進行網絡環境判斷的自適應路由算法——CIAONR(Contact Information-based Adaptive Opportunity Network Routing)。CIAONR在節點分布式采集接觸信息的過程中，利用節點接觸延遲與生存期的關系判斷節點所處網絡環境。然后依據CIAONR約束條件指導轉發路徑的選擇，最終按照對應交互流程完成消息交付。理論分析和仿真結果表明，CIAONR算法在不同網絡環境下均保持較高投遞率，網絡開銷和延遲也控制在一定范圍內，具有普適效果。

機會網絡 路由算法 接觸信息 自適應

0 引 言

機會網絡是一種基于節點接觸形成通信機會進而通過逐跳轉發實現數據交互的移動自組織網絡MANET(Mobile Ad-Hoc Network)，是實現間歇式連通環境下節點通信的基本方法。早期機會網絡主要應用于野生動物追蹤、災難環境臨時組網、偏遠地區網絡覆蓋等場景，應用局限性較大。近幾年隨著各種便攜式設備迅速發展和普及，移動設備感知、計算、通信、存儲等能力越來越強，物聯網、車聯網快速興起，智慧城市等新概念每日更新，機會網絡因其對網絡全連通無要求的特點，更符合實際環境的需求，再次受到高度關注。

機會網絡中，節點環境常在密集與稀疏間進行反復切換[1-2]，如大量野生動物群聚生活，車聯網用戶在社區間穿梭等場景，而現有機會網絡路由算法的研究和評估主要側重于在一個特定場景下投遞率、傳輸延遲和轉發代價之間的權衡，對網絡環境快速變化這一特點的考慮和研究相對較少。節點接觸信息主要包括節點接觸時長、接觸延遲、相遇頻率等，能夠較全面地將當前網絡環境進一步量化，為機會網絡路由算法提供自適應調整依據。因此，本文著眼于機會網絡中節點的接觸信息，提出了一種自適應路由算法——CIAONR，對密集、稀疏網絡拓撲能夠自行判定，進而達到提高不同網絡環境下投遞率，控制網絡開銷和延遲的目的，有效提高了路由的普適效果。

1 相關工作

機會網絡數據傳輸的主要工作方式為“存儲-攜帶-轉發”，如何選擇轉發時機和轉發中繼節點是機會網絡路由算法主要解決的問題[3]。現有機會轉發策略基本分為兩類，即零信息型和信息輔助型[4]，見圖1所示。

圖1 機會網絡轉發策略分類

零信息型是最早提出的機會網絡路由算法，包括Epidemic、Spray and Wait等算法。Epidemic算法是一種模仿傳染病擴散的洪泛算法，相遇即轉發存儲，在網絡資源充足的情況下能夠獲得最優的延時性能，但由于網絡中存在大量的分組副本，網絡開銷也相對增大。Spray and Wait算法針對Epidemic進行了改進，通過向網絡中洪泛固定數目的分組副本來實現保持較低的傳輸延遲和網絡開銷的目的，其傳輸量遠小于Epidemic，網絡延遲接近最優，具有較好的擴展性。在此基礎上，研究學者進一步提出了將網絡編碼技術應用于機會網絡的路由算法，對Epidemic算法進行了一系列改進[5]。Katti等提出基于機會的網絡編碼方法COPE，有效提高無線網絡的傳輸容量和吞吐量。Chachulski等對COPE進行了改進，提出MORE協議將編碼信息路由到多跳鄰居節點，網絡吞吐量進一步提升。

由于充分利用了實際網絡中反映出來的信息，近年來信息輔助型策略更受關注。PROPHET算法依據歷史信息提出了基于節點接觸概率的傳輸預測路由算法，在社區模型場景中性能較好。GBP算法在此基礎上考慮了節點分組情況，認為同組節點不應保存相同副本，通過本地信息引導分組副本到達目的節點，在網絡開銷上表現出色，但網絡延遲較大[6]。Burgess等學者提出的MaxProp算法根據鏈路的歷史數據進行數據分組的優先級劃分，然后按照優先級調度數據分組，獲得了較高的成功送達率，但網絡開銷、傳輸延遲都隨之增大。Tan等學者對下一條鄰居節點進行歷史傳輸時間標記，建立了局部最小傳輸延遲算法MTDA[7]，減小了節點之間的傳輸延遲。在利用鄰居節點信息指導路由轉發方面，任智等學者提出了基于旁聽的機會網絡路由算法ORON[8]，通過旁聽鄰居節點信息設計博弈策略從而激勵節點交易。

此外，Chen、Bulut等學者從人文社會的角度提出了根據社會關系進行節點劃分的機會網絡路由算法[9-11]，在社區等特定場景下獲得較好的網絡性能，但適用場景局限性較大。

2 基于接觸信息的自適應路由算法

為打破路由算法適用場景局限的問題，重點考慮機會網絡環境變化的特點，提出基于接觸信息的自適應路由算法CIAONR。本節主要從網絡模型、數據模型等方面詳述了節點對接觸信息的整合和應用，并進行了深入的理論分析。

2.1 機會網絡模型

定義1 網絡模型。機會網絡用帶權有向圖G=(V,E,F)表示，其中節點集合V={v1,v2, …,vn}，網絡規模為n，n>1；網絡鏈路集合E=?∪{e1,e2,…,em}，ek=vivj表示節點vi與節點vj之間的鏈路，節點鏈路規模為m，1≤m≤n(n-1)；F(ek)表示em的權值集。

定義2 鏈路權重模型。F(ek)為鏈路ek=vivj的權值集合，F(ek)={Tk,Lk,Pk}，Tk表示節點vi與節點v=之間的鏈路持續時間均值，Tk>0；Lk表示節點vi與節點vj之間的鏈路相鄰兩次建立的時間延遲均值，Lk>0；Pk表示節點vi與節點vj之間的鏈路建立概率，即節點vi與節點vj的接觸概率，0≤Pk≤1。

性質1 節點鏈路為有向模型，鏈路建立對兩節點作用一致，即vivj與vjvi表示的是同一條鏈路。但從兩節點方向看鏈路對應權重不完全相同，鏈路有方向之分。

定義3 節點模型。在節點規模為n的機會網絡中，每個節點維護3個n×n數據矩陣，即接觸概率矩陣PALL、接觸時間矩陣TALL、延遲矩陣LALL。矩陣行列交叉點即為對應節點對接觸信息，如PALL矩陣的第i行第j列值Pij即為從本節點角度看節點vi與節點vj的接觸頻率，如圖2所示，PALL第一行為節點v1與其他(n-1)個節點的接觸概率，以此類推。各矩陣均記錄了上一次更新時間LastUpdateTime，節點相遇則以此為依據重新計算概率值或進行相應數據更新。

圖2 節點接觸概率矩陣PALL

由于鏈路建立對兩節點作用效果是對等的，則接觸時間、接觸延遲對兩節點而言均一致。節點接觸概率根據各節點接觸其他節點的頻率會發生相應變化，因而存在差異。節點更新接觸概率時會進行歸一化處理，接觸概率矩陣PALL行向量逐項求和為1。

定義4 節點相遇概率。從移動模型角度看，節點兩兩相遇的概率為[12]：

(1)

其中，ω為移動模型常量，對應特定移動模型為固定值。R為節點通信范圍，在本文中也設置為常量。A為節點移動區域面積，在此以輻射區域計算。本式可簡化為：

(2)

定義5 平均傳輸字節數。節點進行多次分組復制后，對每次傳輸的字節數求均值記為該節點的平均傳輸字節數，用符號BAVG表示，每次進行傳輸后自動更新。

2.2 數據交互模型

機會網絡中節點的信息傳遞完全依賴節點相遇機會來完成，網絡中傳遞的數據分組類型主要有3種，即摘要向量SV、數據分組副本、分組到達確認信息ACK。在本算法中，摘要向量SV主要包含本節點維護的3個n×n數據矩陣信息，分組到達確認信息ACK則用于通知所有節點已成功交付的數據分組。具體交互流程如圖3所示。

1) 節點vi與節點vj相遇首先交換本節點攜帶的以對方為目的節點的數據分組，并將已成功交付信息加入到ACK中。

2) 交換vi與vj各自維護的SV向量表，進行PALL、TALL、LALL的交換更新，根據最新數據重新計算緩存區內數據分組副本的開銷，更新數據分組隊列。

3) 交換ACK信息，對應刪除緩存區內已成功交付數據分組的副本。

4) 依據數據分組隊列進行數據分組副本傳遞，更新各副本的剩余副本數量值，完成交互，更新TALL中對應本節點相關數據。

圖3 節點相遇交互流程

2.3 關于節點接觸信息的CIAONR約束條件

在機會網絡的信息交互過程中，節點接觸信息是對節點運動、通信最直接而有效的量化表示。大量數據分析顯示，移動網絡中大部分節點相遇間隔時間較短，呈現近似的冪律分布[13-16]，即節點的移動和相遇有社區聚集現象。同社區節點在較短時間內可以產生大量的相遇，而不同社區的節點相遇則需要較長的時間。

文獻[16]數據顯示，在一個較長的單位時間T里，有超過95%的相遇發生在遠不足10%的時間中，相遇發生的時間間隔短，稱為節點處于BUSY狀態；而在剩下的T的90%時間中，僅發生了不足5%的相遇，相遇時間間隔長，節點處于SPARE狀態。當節點處于BUSY狀態(在本社區內運動)，應積極的與接觸節點進行高效快速的信息交互；處于SPARE狀態下(在社區間運動)，節點則應以低開銷為前提給相遇節點盡可能多的散布副本。因此根據節點接觸頻率、接觸時長、接觸時延有效判斷節點社區分組和所處狀態，進而作出能夠自動調整的路由算法是非常有必要的。

假設一個小型網絡由6個節點組成，每組包含2個節點，具體分布如圖4所示。為簡化模型，節點隨機移動，節點接觸概率p接觸采用改進后的增量平均化方法進行估算和更新，見式(3)：

(3)

其中，p遇由式(1)給出。α為接觸概率衰減因子，α∈(0,1)。k是兩節點相遇延遲的時間單位數。計算公式如下：

(4)

圖4 小型網絡節點分布圖

假設有消息M要從節點1發送到節點4，消息M的生存期為TTTL，可進行一次副本復制。節點1首先向節點x傳送1個副本，節點x可在節點2、節點3、節點5和節點6中進行選擇。節點1或節點x若在TTTL到期前遇到節點4則可完成交付。

傳送副本過程中，認為同一社區內節點相遇概率高于不同社區間節點相遇概率，簡化后如式(5)，a為不同社區間距離表示。

(5)

(6)

當x=3時，則A組、C組各有1個副本存在，消息M送達概率為p1,3→4。

(7)

計算二者之差，

(8)

由于α∈(0,1)，(k2-k1)≥1且為正整數，所以αk2-k1<1，(r+a)2>r2，易得p1,3→4-p1,2→4<0，即p1,3→4

顯然，當x=5、x=6時，

由此可知，當消息生存期足夠長，僅量化考慮延遲對數據分組交付的影響時，將副本傳送給本組內節點能夠獲得較大投遞率，對應場景為密集環境。而在文獻[6]中理論分析認為，當不考慮延遲對交付的影響，僅考慮消息生存期限制時，傳遞到不同社區節點的交付概率比傳遞給同社區節點交付概率大，在此情況下傳遞給頻繁相遇的節點會對消息的傳輸起到增大開銷的作用，對應稀疏場景。綜上所述，對于信息的投遞時機與投遞對象應根據節點所處環境進行相應調整，從而達到投遞率最大化，網絡開銷最小化的目的。

(10)

1) 當TCompare≥T閾時，認為節點處于密集環境，將消息優先傳送給接觸概率大的節點；

2) 當TCompare

2.4 數據分組隊列與節點接觸度隊列維護規則

對于數據分組隊列，當分組跳數小于等于閾值T分組時，按照跳數進行排序，假定跳數小的數據分組送達率高，優先發送跳數小的數據分組；當分組跳數大于閾值T分組時，按照路徑開銷排序，單跳路徑開銷計算公式如下：

(11)

使用Dijkstra算法求出最小開銷路徑，根據消息的最小開銷進行排序。

節點接觸度隊列按照各節點與本節點接觸度進行排序。節點相遇時，首先按照消息隊列順序讀取數據分組，查詢下一跳節點與本節點接觸度p下一跳。當TCompare≥T閾時，僅將滿足p下一跳≥T節點的消息發送給對應下一跳節點，否則跳過該消息，讀取下一消息；當TCompare

3 仿真結果及分析

采用機會網絡專用仿真平臺ONE分別在不同網絡規模和不同節點容量下進行建模和仿真，以數據分組成功投遞率、網絡開銷、數據分組平均端到端時延三個指標對Epidemic、Spray And Wait、GBP[5]和CIAONR算法性能進行比較。

3.1 仿真參數設置

仿真實驗使用赫爾辛基(Helsinki)部分地區為背景，主要參數設置如表1所示。

表1 主要仿真參數

在仿真時間1 000 s后隨機選取節點，在間隔時間區間[25,35]內隨機產生新消息，從1 000 s開始，到43 200 s結束，共計發送[1 206,1 688]個數據分組。選取隨機種子集合{128,130,132,134}，每組實驗做4次仿真，取統計結果的平均值進行分析。

3.2 固定節點緩存改變節點規模

在固定節點緩存容量為20 MB的情況下，對不同節點規模進行了仿真。圖5是隨著網絡中節點數量的增加各路由算法的成功投遞率變化趨勢。CIAONR算法在各種節點規模下均為最佳，在節點規模為400時，成功投遞率超過95%，接近100%。而在4 500 m×3 400 m的范圍內僅有50個節點時，由于CIAONR算法引入了自適應調整機制，在節點密度較低的情況下能夠做出自行判斷，成功投遞率接近60%，投遞效果較為穩定。

圖5 固定緩存改變節點規模-投遞率

圖6(a)為固定節點緩存容量的情況下，4種路由算法的網絡交付開銷率，開銷率用源節點產生的數據分組總數和所有節點轉發數據分組總數之比來進行評價。由于Epidemic算法“隨遇隨傳隨存”的工作模式，造成開銷率隨節點規模的增加而大幅度增加。為方便查看具體折線，特將Spray And Wait、GBP、CIAONR算法折線單獨在圖6(b)中做比較。

(a) 4種路由算法開銷率對比圖

(b) 3種路由算法開銷率對比圖圖6 固定緩存改變節點規模-開銷率

如圖6(b)所示，CIAONR算法在50～400個的節點規模中均保持低于9的開銷率，在節點密度較小的環境下略高于GBP算法，其原因為在較稀疏網絡環境下進行CIAONR算法進行了自適應的調整，傳送較多數據分組給組外節點，造成開銷率的上升，當節點規模達到300個后，則與GBP算法基本持平，到400個的節點規模時較之GBP還有所下降。

圖7為4種路由算法的平均時延趨勢圖，CIAONR算法平均交付時延在各規模網絡下均接近Spray And Wait算法的平均時延，低于Epidemic和GBP算法平均時延。在節點規模達到200個以后，其平均時延稍低于Spray And Wait算法，接近最優。

圖7 固定緩存改變節點規模-平均延遲

由圖5-圖7可知，在固定節點緩存容量為20 MB的情況下，CIAONR算法的投遞率始終高于另外3種算法，其網絡開銷在節點規模較小的時候雖略高于GBP算法，但在節點規模增大的過程中，也不斷接近甚至低于GBP算法。CIAONR算法的平均交付時延在較稀疏網絡環境中與Spray And Wait算法接近，始終低于另外2種算法。隨節點規模增大其平均時延逐步降低，超過200個的節點規模后平均時延低于Spray And Wait算法，接近最優。

3.3 固定節點規模改變節點緩存

圖8 固定節點規模改變緩存-投遞率

固定節點規模為200個，在不同節點緩存容量的情況下進行了算法仿真對比。圖8-圖10是隨著網絡中節點緩存容量的增加各路由算法的成功投遞率、網絡開銷、平均投遞延遲的變化趨勢。通過對比可得，CIAONR算法對節點緩存容量要求不高，除了容量為10、15 MB時稍有變化，達到20 MB后折線基本保持水平。仿真顯示，Epidemic算法隨節點緩存變化各參數變化較大，Spray And Wait算法在節點緩存為10 MB時也稍有不穩定，CIAONR與GBP算法對節點緩存容量要求最低。

(a) 4種路由算法開銷率對比圖

(b) 3種路由算法開銷率對比圖圖9 固定節點規模改變緩存-開銷率

圖10 固定節點規模改變緩存-平均延遲

經仿真驗證，CIAONR算法較之另外3種算法擁有高且普適的成功投遞率，雖然在節點密度較小時，網絡開銷和網絡延遲略高于GBP和Spray And Wait算法，但其差值小，且隨著節點規模增加，迅速得到改善，更適用于實際的網絡應用。

4 結 語

通過對實際網絡環境的觀察發現，移動節點總是在不同密度網絡中隨機切換，因此提出一種基于節點接觸信息的自適應路由算法——CIAONR算法。CIAONR算法充分利用各節點采集到的接觸信息，依據CIAONR約束條件自行判斷網絡環境并以此指導路由轉發，最終完成交付。仿真實驗驗證了CIAONR算法在投遞率方面的顯著提升，網絡開銷率也控制在較低范圍內，未來將在降低網絡延遲方面做進一步研究。

[1] 吳磊, 王曉敏, 劉明,等. 延遲容忍傳感器網絡中基于群組運動的事件傳輸[J]. 軟件學報, 2012, 23(3): 629-647.

[2] Zhang H Y, Fan W H, Wang L, et al. Real-Time and reliable greedy geographical routing for mobile wireless sensor networks[J]. Journal of Computer Research and Development, 2009, 46(5): 713-722 (in Chinese with English abstract).

[3] 張三峰, 黃迪, 陳州. 一種面向機會網絡路由的最優停止決策方法[J]. 軟件學報, 2014, 25(6): 1291-1300.

[4] 馬華東, 袁培燕, 趙東. 移動機會網絡路由問題研究進展[J]. 軟件學報, 2015, 26(3): 600- 616.

[5] 任智, 劉智虎, 姚玉坤. 基于網絡編碼的機會網絡高效路由算法[J]. 通信學報, 2013, 34(9): 16-23.

[6] 楊帆, 來嘉哲. 基于分組的DTN路由協議[J]. 電子測量技術, 2015, 38(10): 144-148.

[7] 譚紫逸, 陳志剛, 吳嘉,等. 機會網絡多跳節點最小傳輸延遲算法設計[J]. 計算機應用研究, 2016, 33(8):2458-2461.

[8] 姚玉坤, 張強, 楊及開. 基于社會組的高投遞率機會網絡路由協議[J]. 計算機應用研究, 2017, 34(2):577-581.

[9] Chen K, Shen H. SMART: Lightweight distributed Social Map based Routing in Delay Tolerant Networks[C]// IEEE International Conference on Network Protocols. IEEE Computer Society, 2012:1-10.

[10] Bulut E, Szymanski B. Exploiting friendship relations for efficient routing in mobile social networks[J]. IEEE Trans. On Parallel and Distributed Systems, 2012, 23(12): 2254-2265.

[11] 任智, 譚永銀, 索建偉,等. 一種基于旁聽的機會網絡路由算法[J]. 計算機應用研究, 2016, 33(11):3396-3400.

[12] Zhang X, Neglia G, Kurose J, et al. Performance modeling of epidemic routing[J]. Computer Networks, 2007, 51(10): 2867-2891.

[13] Chaintreau A, Hui P, Crowcroft J, et al. Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms[C]// INFOCOM 2006. IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 23-29 April 2006, Barcelona, Catalunya, Spain. DBLP, 2006:1-13.

[14] Karagiannis T, Boudec J Y L, Vojnovic M. Power Law and Exponential Decay of Intercontact Times between Mobile Devices[J]. IEEE Transactions on Mobile Computing, 2010, 9(10):1377-1390.

[15] 程剛, 張云勇, 張勇. 基于人類真實場景的分時段的機會網絡移動模型[J]. 通信學報, 2013, 34(S1): 182-189.

[16] 蔡青松, 牛建偉, 劉燕. 機會網絡中的消息傳輸路徑特性研究[J]. 計算機研究與發展, 2011, 48(5): 793-801.

[17] Tie X,Venkataramani A,Balasubramanian A.R3:robust replication routing in wireless networks with diverse connectivity characteristics[C]//International Conference on Mobile Computing and Networking, MOBICOM 2011, Las Vegas, Nevada, Usa, September. 2011:181-192.

ADAPTIVE OPPORTUNITY NETWORK ROUTING ALGORITHM BASED ON THE CONTACT INFORMATION

Wu Shuyan Han Yigang Fu Qiuyu Feng Fei

(CollegeofElectronicInformationandOpticalEngineering,NankaiUniversity,Tianjin300350,China)

Considering the constantly changes in the actual network environment and the characteristics of opportunity networks nodes which always switch stochastically between dense and sparse scene, an adaptive routing algorithm called CIAONR which can judge the network environment with the node contact information is proposed. CIAONR uses nodes’ contact delay and lifetime to determine the network environment in which the nodes are located during the process of collecting the contact information. Then, according to the CIAONR constraints, the choice of the forwarding path is guided, and finally the message delivery is completed according to the corresponding interaction flow. Theoretical analysis and simulation results show that the CIAONR maintains a high delivery rate in different network environments, and the network overhead and delay are also controlled within a certain range, which has a universal effect.

Opportunity network Routing algorithm Contact information Adaptive

2016-07-01。武淑艷，碩士生，主研領域：計算機通信網絡，內容中心網絡，機會網絡。韓毅剛，副教授。傅秋宇，碩士生。馮飛，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2017.07.019