基于均勻分布的機會網絡消息轉發策略

張樹東 張 蓓

1(首都師范大學信息工程學院 北京 100048)2(成像技術北京市高精尖創新中心 北京 100048)3(電子系統可靠性技術北京市重點實驗室 北京 100048)

基于均勻分布的機會網絡消息轉發策略

張樹東1,2張 蓓1,3

1(首都師范大學信息工程學院 北京 100048)2(成像技術北京市高精尖創新中心 北京 100048)3(電子系統可靠性技術北京市重點實驗室 北京 100048)

為了篩選出轉發性能更優的中繼節點，提高機會網絡的消息投遞成功率并減少消息傳輸時間，提出一種基于均勻分布的機會網絡消息轉發策略。該策略將攜帶消息的節點盡可能均勻地分布在網絡中，使相同大小的空間內具有相同節點密度和攜帶消息節點個數，增大攜帶消息節點同目標節點相遇的概率。實驗結果表明，與現有的消息轉發策略相比，基于均勻分布的消息轉發策略所需歷史相遇數據較簡單，算法復雜度低，對節點的緩存和能量要求不高，能有效改善機會網絡的消息傳輸性能。

機會網絡 均勻分布 消息轉發

0 引 言

機會網絡OppNet(Opportunistic network)是一種特殊的自組織網絡。同傳統的移動自組織網絡MANET不同，機會網絡不需要數據源節點與目的節點之間一定存在完整的端到端通信鏈路，不要求網絡的全連通，它實現數據通信的方法是“存儲，攜帶，轉發”，在節點的移動中尋求通信機會，就算網絡中的通信聯絡處于斷開狀態或者存在嚴重的網絡拓撲不連續時，也能通過節點間的相遇來完成數據的轉發和交互[1]。機會網絡作為一種網絡通信新技術，是移動自組織網絡新的發展方向，具有組網方式靈活、支持分布式控制等特點，在野生動物追蹤、城市車載網絡、災難應急救援、偏遠山區建設等方面有廣泛的應用前景[2]，讓人們能夠在任何時間、任何地點獲得計算機信息服務。

1 相關工作

對于機會網絡來說，數據的傳輸依賴于節點的移動，消息是以多跳的方式到達目的地，因此，在機會網絡的消息傳遞過程中，最需要解決的基本問題是：如何選擇最理想的下一跳節點，如何選擇恰當的轉發時機，如何才能確保消息從源節點成功傳輸到目的節點。消息轉發機制是機會網絡的核心，它決定通過何種策略進行消息傳遞，需要考慮消息傳輸的成功率、傳輸的延遲時間和消息在網絡傳遞中的冗余份數等，有效的消息轉發策略是機會網絡數據傳輸高效可靠的保證。按照策略的不同，目前現有的消息轉發機制可以大致分為零信息型和信息輔助型[3]。

零信息型消息轉發策略是指那些在消息轉發過程中不需要額外信息輔助的轉發策略，這種策略設計思路直觀明了，且較易實現，有很多經典算法都屬于這種策略。例如：Spyropoulos等人在2004年提出的Direct Delivery算法，在該算法中，源節點攜帶的消息只有在遇見目的節點的時候才會進行轉發，隨著網絡節點數量增多，發生的傳輸延遲和傳遞失敗的可能性都急劇增大[4]；Vahdat等人在2000年提出的Epidemic算法采用了洪泛的方式，兩個節點相遇后會通過對比各自的消息存儲哈希表，并交換以獲得彼此沒有的數據，這種算法能提高消息傳遞成功率，但是這種傳染轉發機制會造成網絡的信息冗余度大，對節點的能量值和緩存空間要求很高[5]；2-HOP算法以及其改進算法Spray and Wait都是采用兩跳轉發路由機制[6]，源節點將消息傳遞給與之相遇的N個節點，再將這N個節點作為消息轉發的中轉站，最終由他們將數據轉發給目的節點，這種類型的算法能提高傳遞成功率以及降低傳遞時延，而且消息冗余份數不多。

信息輔助型消息轉發策略是指那些在轉發過程中需借助輔助信息的轉發策略，不同的算法會采用不同的輔助信息。例如：概率轉發協議(Prophet)借助節點間的歷史相遇信息，來預測每個節點同目的節點相遇的概率，節點只將信息轉發給那些比自己更有可能碰到目標的相遇節點，從而降低了通信開銷[7]。Context-AwareRouting路由協議綜合節點運動速度、節點能夠提供的剩余能量、網絡拓撲變化情況、同目的節點相遇概率等情境信息來評估節點參與數據轉發的可能性[8]。在擦除編碼路由機制中，首先利用網絡編碼技術將原始信息分解成多個數據塊，目的節點根據編碼算法來解析接收到的數據塊就可以得到原始信息[9]。

在如上所述的信息輔助型消息轉發策略的基礎上，本文提出了一種基于均勻分布的機會網絡消息轉發策略——UDR，與以往的方法不同，該策略的主要出發點基于這樣一個事實：如果在相同大小的空間內，具有相同節點密度和攜帶消息節點個數，攜帶消息節點均勻分布在空間內，比其他分布方式與目標節點的平均相遇機會最大。所以UDR的核心思想是將攜帶消息的節點均勻地分布在網絡中，從而提高消息傳遞成功率，降低傳輸時延。基于ONE平臺[10]的仿真實驗表明，UDR相較于其他轉發策略，在提高投遞成功率和降低傳輸時延上具有一定的優勢。

2 基于均勻分布的機會網絡消息轉發策略模型

2.1 機會網絡結構描述

機會網絡沿用了時延容忍網絡的構架，網絡結構是平面的，非層次的，在網絡中，各個節點之間不存在地位區別，所有節點均平等。假設一個機會網絡，在初始狀態下，一共有R個傳感器節點隨機不均勻分布在大小為A×B的二維空間里，其中消息是由源節點S生成，要傳遞到目的節點D；在消息傳遞過程中，C表示攜帶消息節點的集合，最大消息攜帶節點數量N，即C中元素個數最多為N，N的選取與網絡空間成正比，與節點間通信半徑成反比；允許的最大消息延遲時間為Tp,Tp的值由機會網絡的應用場景決定。該網絡還具有如下性質：

(1) 信息發送者通過中間節點的存儲轉發將信息發送給目標節點；

(2) 信息發送者共有N-1次數據轉發機會；

(3) 中間節點不能再轉發消息，只能傳遞給目標節點；

(4) 網絡中有1個發送者和N-1個中間節點，共N個節點攜帶消息，通過選擇N-1個中間節點，構成消息攜帶節點集合使其與目標節點有最大的幾率相遇。

2.2 轉發算法描述

為了盡可能在提高傳遞成功率的情況下減少投遞時延，本文將整個網絡看作一個整體，盡可能使網絡中攜帶消息的節點均勻分布，從而提高攜帶消息節點和目的節點的相遇機會。首先根據歷史相遇記錄得出節點平均相遇時間,綜合節點移動速度計算各個節點同源節點之間的距離，再構建候選中間節點池，按照一定的篩選規則選擇節點放入該節點池中，池中先到的節點作為消息轉發中間結點，將消息傳遞給該節點。如果攜帶消息節點的數量小于預先設置的網絡中攜帶消息節點數量的最大值，那么繼續計算網絡中其他節點到中繼節點的距離，繼續選擇節點將消息傳遞下去，直到網絡中攜帶信息的節點數量達到預設最大值。最后,等待消息節點同目的節點相遇，傳遞消息成功。算法的邏輯流程如圖1所示。

圖1 算法的邏輯流程圖

具體算法步驟如下：

(1) 在初始情況下，攜帶消息節點的集合C中只有發送消息的源節點S，統計歷史相遇記錄得到節點的平均相遇時間T，根據T和節點移動速度V計算源節點S到網絡中其他節點的估計距離D，i表示其中的某個節點，它同源節點S的之間距離Di以及與源節點S的下次預期相遇時間Ti的計算公式如下：

Di=T×Vi

(1)

Ti=T-上次相遇時刻到現在的時間長

(2)

(2) 由于距離源節點S最遠的節點不一定會在可容忍的等待時間Tp內到來，為了減少由于等待帶來的網絡延遲，建立候選中間節點池，按照一定的規則，篩選節點進入該池中，池中先到的節點作為消息轉發中間結點。篩選規則內容如下所示：

① 將所有節點按Di值由大到小排列；

② 將Di值最大的5個節點放入池中(提高轉發效率)；

③ 根據應用場景確定延遲最大容忍值Tp，取Ti

(3) 當池中一個節點到達時，將消息傳遞給該節點，同時消息轉發節點將自己與其他節點平均相遇時間信息傳遞給節點S；將該節點放入C中。

(4) 判斷C中結點個數是否已達到N個，如果已達到，執行步驟6，否則執行步驟5。

(5) 計算其他節點到C中節點距離DC，設Nodei是第i個其他節點，設Cj是C中第j個節點，Tij是節點的平均相遇時間，Nodei到C中節點距離DCi的計算公式如式(3)所示，再返回步驟2，繼續執行。

DCi=squr(∑(Tij×Nodei的移動速度)2)

(3)

(6)N個中間節點等待與目標節點相遇，當其中一個節點與目標節點相遇后，傳遞消息。

(7) 消息傳遞結束。

3 實驗與分析

本文采用ONE(OpportunisticNetworkEnvironmentsimulator)[10]仿真平臺來進行比較實驗，ONE是由赫爾辛基大學設計開發的機會網絡環境模擬器，提供工具使用不同的路由協議來模擬機會網絡中消息的轉發，并記錄轉發過程中的各種數據。本文實驗的模擬地圖采用了ONE提供的赫爾辛基城市地圖模型，網絡中有三種節點類型，分別是行人、家庭轎車、有軌電車，每種節點移動速度不同，節點移動類型選用最短路徑模型SPMBM(shortestpathmap-basedmovement)運動模型。在該模型下，網絡中的節點會利用Dijkstra算法計算到目的節點的最短路徑作為移動方向，機會網絡具體的設置參數如表1所示。

表1 仿真配置參數

本文將UDR和根據節點間歷史相遇信息來估計轉發概率的Prophet算法、不需要輔助信息的無限制洪泛算法Epidemic以及兩跳轉發算法SprayandWait(SAW)進行對比仿真實驗。在保持其他參數值不變的情況下，依次改變節點緩存大小、消息存活時間，分析對比實驗結果來比較算法的性能優劣，比較的性能指標是投遞成功率、平均投遞時延。

(1) 投遞成功率(rd)，表示在實驗過程中，成功傳遞到目的節點的數據包數量(d)同仿真過程中產生的總數據包的數量(c)的比值，計算公式如下：

(4)

為了避免其他參數對仿真結果的影響，在網絡其余參數均保持不變的情況下，依次將網絡中節點緩存大小設置成5～50MB,節點緩存大小變化對轉發策略投遞成功率的影響如圖2所示。

圖2 不同節點緩存下的投遞成功率

在圖2中，隨著節點緩存的增大，三種轉發策略的投遞成功率都隨之提高，最終趨于一個最高值。但是從曲線中可以看出，UDR在緩存大小為20MB的時候投遞成功率可以達到0.825，而相同配置下的Epidemic和Prophet的投遞成功率才0.5左右。Epidemic策略中，每個相遇節點都是相互拷貝信息，在緩存空間很有限的前提下，有用的信息極可能被拋棄，而Prophet策略預測相遇概率的準確度有限，緩存的增加確實可能提高相遇概率，但是效果不是很明顯，故這兩種策略的投遞成功率較低。SAW的轉發原理同UDR類似，都是通過選取一定的中繼節點作為信息傳遞的跳板，但是由于SAW采取遇到即復制的貪婪策略，而UDR在選擇候選節點的時候更為謹慎，選出的節點在傳遞消息的性能上比SAW更高，從而具有更高的投遞成功率。

考慮到在實際情況中，傳感器節點的能量值不會很充分，當節點緩存大小為5MB時，將消息存活時間設置為30～300min,消息存活時間的變化對轉發策略投遞成功率的影響如圖3所示。

圖3 不同消息存活時間下的投遞成功率

可以看出，隨著消息存活時間的增加，四種轉發策略的投遞成功率開始是穩步上升的，當消息存活時間增大到100min以上時，投遞成功率漸趨穩定，當消息存活時間過長，會造成節點緩存中的冗余報文數量增大，從而對提高投遞成功率沒有什么幫助。但是UDR的投遞成功率在這四種算法中一直保持最高值或者接近最高值，這是因為在UDR的轉發過程中，所需的歷史相遇信息較為簡單，網絡中的無效數據較少，增大消息存活時間能增大網絡中的消息副本的數量，消息傳遞到目的節點的可能性也隨之增大。

(2) 平均投遞時延(al)，表示從源節點發出的消息到被成功傳遞到目的節點所消耗時間的平均值，用ti0表示發出第i個節點的時刻，ti表示該節點成功到達的時刻，平均投遞時延的計算公式如下：

(5)

機會網絡的設置同上，節點緩存大小和消息存活時間的變化對轉發策略平均投遞時延的影響分別如圖4和圖5所示。

圖4 不同節點緩存大小下的平均投遞時延

由圖4看出，四種轉發策略的平均投遞時延都隨著網絡中節點緩存的增大表現出上升趨勢，在節點的移動過程中，Epidemic算法的消息隊列很容易被消息副本填滿，所以它的平均延遲較另外三種算法偏高，UDR在選擇中繼節點的時候較Prophet和SAW更為準確，故能在保持高投遞成功率的情況下降低投遞時延。

圖5顯示，隨著消息存活時間的增加，四種轉發策略的平均投遞時延都會增大。隨著消息存活時間的增加，有限的節點緩存空間迅速被各種數據占領，剩下的緩存不足以容納新的生成的數據。但是UDR轉發所需輔助信息很少，就算節點緩存不足，UDR的消息隊列中存儲的有用信息也不會被隨意丟棄。另外，UDR能夠更有效地選擇中繼節點，故而在四種轉發策略中表現出最佳或者接近最佳的平均投遞時延效果。

4 結 語

本文根據機會網絡消息轉發中的輔助信息，提出了一種基于均勻分布的消息轉發策略UDR。詳細介紹了UDR的轉發原理和詳細算法，并利用ONE仿真平臺，將UDR與另外三種經典消息傳輸機制Epidemic、Prophet和SprayandWait進行了對比試驗。分別在改變節點緩存大小以及消息存活時間的情況下，對四種算法的消息投遞成功率和平均投遞時延進行了分析比較。實驗結果表明，UDR較其他三種算法具有較高的投遞成功率以及較低的投遞時延，能夠更快更準確地將消息傳遞到目的節點。但是，UDR也有一定的缺陷，例如，隨著節點數量的改變，UDR在提高投遞成功率方面并沒有顯著的優勢。另外，本文只是探究了節點緩存大小和消息存活時間這兩個參數的改變對算法性能的影響，沒有驗證其他參數的設置是否能對算法性能造成更大的改變，這些問題在后續工作中會繼續優化。

[1]PelusiL,PassarellaA,ContiM.Opportunisticnetworking:dataforwardingindisconnectedmobileadhocnetworks[J].IEEECommunicationsMagazine,2006,44(11):134-141.

[2] 熊永平,孫立民,牛建偉,等.機會網絡[J].軟件學報,2009,20(1):124-137.

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

[4]SpyropoulosT,PsounisK,RaghavendraCS.Single-copyroutinginintermittentlyconnectedmobilenetworks[C]//2004FirstAnnualIEEECommunicationsSocietyConferenceonSensorandAdHocCommunicationsandNetworks,2004:235-244.

[5]VahdatA,BeckerD.Epidemicroutingforpartiallyconnectedadhocnetworks:CS-2000-06[R].TechnicalReportofDukeUniversity,2000.

[6]GrossglauserM,TseDNC.Mobilityincreasesthecapacityofadhocwirelessnetworks[J].IEEE/ACMTransactionsonNetworking,2002,10(4):477-486.

[7]LindgrenA,DoriaA,SchelénO.Probabilisticroutinginintermittentlyconnectednetworks[C]//FirstInternationalWorkshoponServiceAssurancewithPartialandIntermittentResources,2004:239-254.

[8]MusolesiM,MascoloC.CAR:context-awareadaptiveroutingfordelay-tolerantmobilenetworks[J].IEEETransactionsonMobileComputing,2009,8(2):246-260.

[9]WangY,JainS,MartonosiM,etal.Erasure-codingbasedroutingforopportunisticnetworks[C]//Proceedingsofthe2005ACMSIGCOMMWorkshoponDelay-TolerantNetworking(WDTN),Philadelphia,PA,USA.ACM,2005:229-236.

[10]Ker?nenA,OttJ,K?rkk?inenT.TheONEsimulatorforDTNprotocolevaluation[C]//Proceedingsofthe2ndInternationalConferenceonSimulationToolsandTechniques,Rome,Italy,2009:1-10.

MESSAGE FORWARDING STRATEGY BASED ON UNIFORM DISTRIBUTION IN OPPORTUNISTIC NETWORKS

Zhang Shudong1,2Zhang Bei1,3

1(CollegeofInformationEngineering,CapitalNormalUniversity,Beijing100048,China)2(BeijingAdvancedInnovationCenterforImagingTechnology,Beijing100048,China)3(BeijingKeyLaboratoryofElectronicSystemReliabilityandPrognostics,Beijing100048,China)

A new message forwarding strategy in opportunistic network is proposed based on uniform distribution router, which is to improve the performance of opportunistic networks of delivering messages, reduce transmission time of messages and screen out the better relay node of forwarding performance. This strategy distributed the nodes with message in the network as evenly as possible so that space of the same size of the same density of nodes with message, increasing the data delivery probability from the nodes with message to the destination node. Simulation results show that compared with existing algorithms, this strategy needs simpler history data, besides, with low algorithm complexity and low demand of nodes cache and energy, and it can improve the message transmission performance in opportunistic network.

Opportunistic network Uniform distribution Message forwarding

2016-01-12。國家科技支撐計劃項目(2013BAH19F01)。張樹東，教授，主研領域：計算機網絡，分布式計算。張蓓，碩士生。

TP3

A

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