一種基于聯絡歷史的車載容遲網絡路由算法

宋志華,暴建民,謝元發,周 雅

(南京郵電大學，江蘇 南京 210023)

一種基于聯絡歷史的車載容遲網絡路由算法

宋志華,暴建民,謝元發,周 雅

(南京郵電大學，江蘇 南京 210023)

移動車載容遲網絡(VDTN)是一種特殊的容忍延遲網絡，其消息從一端到另一端由移動的車輛節點攜帶轉發。由于不同源節點和目的節點之間端到端通信路徑不存在，因此，移動車載容遲網絡中端到端的聯系是松散的，且導致傳遞消息至目的節點的可能性大幅度減小。因此，在移動車載自組織網絡下應用的一系列路由算法不能很好地應用于VDTN。所以在VDTN中，路由算法成為一項具有挑戰性的任務。文中提出了一種基于節點之間的聯絡歷史的路由算法(CONHR)，指的是通過已有聯絡歷史記錄的移動節點，比較中繼計數區域中數值的大小，選擇出最佳的移動節點，讓其攜帶并轉發消息至目的節點。這種歷史記錄包含每個移動節點過去遇到的中繼節點的信息。結果顯示，基于節點之間聯絡歷史的路由算法(CONHR)與其他算法在消息投遞率、平均時延、開銷比上具有更好的表現。

移動車載容遲網絡；聯絡歷史；CONHR算法；容忍延遲網絡

0 引 言

DTN網絡是一種在其生存周期內不需要端到端聯系的特殊網絡，但該類型網絡的缺點表現在較窄的傳輸范圍、無線通信時的能耗限制、不同的網絡分割等方面。但可以通過不均勻的數據傳輸率，間歇長短，較長或變化復雜的延遲以及傳輸過程中較高的出錯率區別這些網絡，比如星際網絡[1](IPN)、水下傳感器網[2]、無線移動傳感器網絡(WMSN)、手持設備網絡、戰術通信網[3]、移動車載容遲網絡[4](VDTN)等。

VDTN作為新型的車輛通信網絡，可以實現車輛與車輛之間(Vehicle to Vehicle,V2V)、車輛與路邊基礎設施之間(Vehicle to Infrastructure,V2I)的多跳無線通信。其中，車輛將被視為可移動節點，節點間利用中繼節點相互傳遞消息，而中繼節點是一種存儲更多消息記錄的緩存空間區域，并且散布在車輛行駛路徑的道路交叉處，接收或發送消息給移動節點。

DSDV[5],DSR[6]以及AODV[7]是車載自組織網絡(MANET)針對路由數據包的幾個常見的路由協議。它們是通過在源節點與目的節點之間建立端到端的路徑來傳送數據。這一類協議都是為了找到最短傳輸路徑，并在此路徑基礎上路由數據包。但在DTN網絡中，不能直接找到源節點到目的節點的最短路徑，只有通過一段時間不同網絡分區中的子路徑的疊加方式找到較優路徑。正因如此，使得VDTN網絡路由算法變得富有挑戰性。所以在VDTN網絡中，不是為了找到最短路徑，更多的是確保消息到達目的節點。

DTN路由算法是大量的節點以存儲-攜帶-轉發的機制進行的，基本的路由算法是基于洪泛策略，有First Contact[8]算法、Spray-and-Wait算法[9]，以及基于節點歷史的路由算法，比如Prophet[10]算法，節點利用節點間相遇的歷史信息和傳遞性來估計到達目的節點的概率選擇下一跳節點。

針對VDTN，文中提出一種路由算法—基于節點之間聯絡歷史的路由算法(Contact History Routing)。

1 基于節點聯絡歷史的路由算法-CONHR算法

1.1 算法背景

(1)視作移動節點的車輛高速運動，節點在很短的時間內彼此相遇，節點之間交換信息的時間非常短暫，所以傳遞的消息數目非常少。

(2)當節點以預計路線移動時，節點之間相遇的頻率增加，比如出租車司機。節點會多次移動到同一位置，比如去公司的職員。與特定中繼節點有相遇歷史的移動節點會對以后轉發消息的決策產生重大影響，例如一個節點在過去已經遇到該中繼節點，在未來的時間點就有較大的概率會再次遇到。

針對上述VDTN移動節點的特征，文中提出了CONHR算法。它是基于聯絡歷史的一種算法，該聯絡歷史是由源節點與移動節點產生的，是關于在網絡中與不同的中繼節點相遇的聯絡歷史記錄。在該算法中，每個節點產生并存儲這一相遇聯絡歷史記錄，并轉發消息給網絡中有較大可能與更多的中繼節點相遇的移動節點(即中繼計數較大的節點)，直至到達目的節點。

1.2 算法假設

1.2.1 總體假設

(1)網絡中的每一個節點都有獨特的識別標志，以至于網絡中的其他節點都能夠識別。

(2)假定網絡中出現兩種終止節點：源節點和目的節點。它們作為網絡中的固定節點并且被安置在兩個不同的終端上。

(3)具有手持設備的車輛(同構或異構)作為移動節點攜帶信息。移動模型[11]設置為基于地圖的模型 MapBasedMovement。

(4)中繼節點是固定節點，也稱為路邊單元，利用存儲和轉發機制，分布在網絡中不同的道路交叉處來提高消息投遞率。與ONE中所說的中繼節點不同在于是否有中繼計數區域。

1.2.2 消息生成與復制策略

消息只能由源節點產生；源節點、中繼節點、移動節點秘密進行消息的轉發，即雙方通信時只有對方才能獲知彼此的消息。

1.2.3 調度與丟棄策略

(1)調度策略是對隊列中的隨機消息進行調度。

(2)終止策略考慮到消息的生存周期TTL。如果消息時間達到了生存周期，將從隊列中丟棄。

1.2.4 轉發/限制的洪泛策略

基于限制的洪泛策略的消息轉發：利用節點間的相遇進行消息的復制，然后通過中繼節點進行消息的轉發，直至目的節點。

1.3 算法過程

CONHR遵循兩個過程：一是關于移動節點的歷史創建與更新；二是消息的轉發與傳遞。

1.3.1 移動節點的歷史創建或更新

表1顯示歷史記錄存儲在VDTN不同類型的節點中。

表1 不同節點的歷史存儲

首先，源節點與移動節點的歷史記錄設置為NULL。當移動節點與中繼節點第一次相遇時，移動節點在相應的中繼計數區域存儲這次相遇的歷史記錄。當移動節點M與源節點S相遇，源節點S從移動節點M傳遞的信息中尋找與中繼節點相遇的信息，并存儲這些記錄：移動節點的編號為該移動節點相遇到的中繼節點編號及其相遇過的節點編號。當移動節點相遇時，它們創建類似于與源節點相遇時的歷史記錄信息，并交換之間存儲的信息。

當源節點與移動節點再次相遇時，便會更新相應的歷史記錄，移動節點之間再次相遇時，亦是如此。

1.3.2 消息轉發與傳遞

無論何時源節點S相遇移動節點M，S都會檢查M存儲的歷史信息是否已經存在于S的歷史記錄中。如果該歷史記錄對S通信范圍內的所有移動節點有效，S節點則選擇該范圍內中繼計數最高的移動節點作為下一節點進行消息轉發。

當移動節點之間相遇時，也會檢查彼此的歷史記錄信息，選擇中繼計數最高的移動節點作為下一節點進行消息轉發。

在以下出現的兩個場景中，如果移動節點之間具有相同的中繼計數或中繼計數均為0，那么隨機選取范圍內的移動節點作為下一節點進行消息轉發。

2 仿真實驗

2.1 模擬器

對網絡環境的模擬主要靠網絡模擬器。文中實驗采用的是機會網絡模擬器(Opportunistic Networks Environment，ONE)[12]。ONE仿真系統是在SINDTN和CATDTN項目資助下由芬蘭Nokia研究中心開發的用于機會網絡研究的仿真平臺，專門用于研究DYN網絡。它基于離散事件的模擬引擎，其擴展功能強大。

2.2 仿真環境與配置

文中將利用ONE[13]仿真平臺對CONHR路由算法進行大量的仿真實驗。首先對將要進行的場景參數進行設置(見表2)，中繼節點設置為10，源節點、目的節點、移動節點、中繼節點均在模擬場景中。

表2 環境模擬參數表

仿真中采用的評估指標有：消息投遞率、平均時延、開銷比。具體含義見表3。

表3 ONE仿真器評估指標

將CONHR算法與Prophet算法、Spray-and-Wait算法以及First Contact算法進行對比，對于Spray-and-Wait[14]算法，設置其最大副本數量為6。

2.3 模擬結果與分析

首先，通過改變節點數量，比較各個算法的消息投遞率，評價CONHR的穩定性。

如圖1所示，當節點數量由50到250變化時，發現所有算法的消息投遞率都增加了。其中，CONHR算法消息投遞率增長的最快。原因如下：

當節點數量增加時，節點之間與中繼節點之間的聯系增加，因此中繼計數增加。CONHR算法的核心在于計算中繼計數區域中的數值大小，從而決定消息的轉發路徑。因此，中繼計數越大，消息投遞率越大。

圖1 消息投遞率vs節點數量

其次，通過改變節點的數量，比較各個算法的平均時延，評價其性能。

如圖2所示，對于所有的算法，當越來越多的節點進行消息轉發與傳遞時，其平均時延會降低。相比較而言，CONHR算法較為穩定。

從圖2中看到，當節點數量在50～90范圍內變化時，其平均時延降低；當節點數量在90～130范圍內變化時，其平均時延上升；當節點數量在130～170范圍內變化時，平均時延又降低。這是由于越來越多的消息投遞率并未增加的節點進行了消息轉發。當越來越多的節點進行消息轉發，網絡將會變得擁塞，以及花費更多的時間來轉發消息，因此傳遞時延也相應地增加，這也是CONHR算法在節點數量90～130范圍變化時平均時延上升的原因。

圖2 平均時延vs節點數量

最后，通過改變節點的數量，比較各個算法的開銷比，評價其性能。

CONHR算法在開銷比上優于Prophet算法和First Contact算法。相比之下，它具有更高的消息投遞率和中繼較少的信息。但Spray-and-Wait算法具有中繼更少數量的消息，由于在Spray-and-Wait算法中，其中繼節點直到遇見目的節點才會轉發與傳遞消息，故導致其路由開銷比比CONHR算法更小。

如圖3所示，當節點數量增多，CONHR算法的路由開銷比略有增加。這是由于節點數量越來越多，其中繼節點的數量也會相應增加進行消息的轉發。

3 結 論

通過ONE模擬器的模擬結果顯示，CONHR算法在消息投遞率、平均時延、開銷比上的確比Prophet算法、First Contact算法效果好，盡管在開銷比上比Spray-and-Wait算法略低。這是由于找到中繼計數較大的節點時其增加了路由開銷，但在另外兩個方面上還是勝于Spray-and-Wait算法。因此CONHR算法在移動車載容遲網絡中具有較好的性能表現。

4 結束語

在使用CONHR算法時，首先利用有限制的洪泛策略傳遞消息給具有歷史記錄的移動節點，被選擇的移動節點的中繼計數較高的優先，這樣可能會導致額外的路由開銷比，這點還是需要深入研究。

CONHR算法將中繼節點視為儲存歷史記錄的變量，在未來將包含與目的節點相遇計數，聯系時間間隔以及剩余緩存空間，這樣也會增加更多的變量來儲存歷史記錄，也會導致節點需要額外的存儲空間、額外的路由開銷。今后，將基于這些變量找到一種更加高效的路由算法。

[1] Voyiatzis A.A survey of delayed-and disruption-tolerant networking applications[J].Journal of Internet Engineering,2012,5(1):331-334.

[2] Partan J,Kurose J,Levine B N.A survey of practical issues in underwater networks[J].SIGMOBILE Mobile Computing Communication Review,2007,11(4):23-33.

[3] Krishnan R,Basu P,Mikkelson J M,et al.The spindle disruption-tolerant networking system[C]//Proc of military communications conference.[s.l.]:IEEE,2007:1-7.

[4] Wu H,Fujimoto R,Hunter M,et al.MDDV:a mobility-centric data dissemination algorithm for vehicular network[C]//Proceedings of the first international workshop on vehicular ad hoc networks.Philadelphia,PA,USA:[s.n.],2004:47-56.

[5] Perkins C,Bhagwat P.Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[J].ACM SIGCOMM Computer Communication Review,1994,24(4):234-244.

[6] Johnson D,Maltz D.Dynamic source routing in ad-hoc wireless networks[M]//Imielinski T,Korth H.Mobile computing.[s.l.]:Kluwer Academic Publishers,1996:153-181.

[7] Perkins C E,Royer E M.Ad hoc on-demand distance vector routing[C]//Proceedings of the 2nd IEEE workshop on mobile computing systems and applications.[s.l.]:IEEE,1999.

[8] Jain S,Fall K,Patra R.Routing in a delay tolerant network[C]//Proc of annual international conference of the special interest group on data communication.Portland,Oregon,USA:ACM,2004.

[9] Spyropoulos T,Psounis K,Raghavendra C S.Spray and wait:efficient routing in intermittently connected mobile networks[C]//Proceedings of ACM SIGCOMM workshop on delay tolerant networking.[s.l.]:ACM,2005.

[10] Lindgren A,Doria A,Schelen O.Probabilistic routing in intermittently connected networks[C]//Proc of lecture notes in computer science.[s.l.]:[s.n.],2004:239-254.

[11] 王 豐，暴建民，彭慧珺.延遲容忍網絡中移動模型對路由算法的影響[J].計算機技術與發展，2015,25(10):127-130.

[12] Ker?nen A,Ott J,K?rkk?inen T.The ONE simulator for DTN protocol evaluation[C]//Proceedings of the 2nd international conference on simulation tools and techniques.Rome,Italy:[s.n.],2009.

[13] 孫踐知.機會網絡路由算法[M].北京：人民郵電出版社，2013.

[14] 孫踐知，韓忠明，陳 丹,等.Wait and Spray：一種改進的機會網絡路由算法[J].計算機工程與應用，2011,47(31):91-93.

A Routing Algorithm of Vehicular Delay Tolerant Network Based on Contact History

SONG Zhi-hua，BAO Jian-min，XIE Yuan-fa，ZHOU Ya

(Nanjing University of Posts and Telecommunications，Nanjing 210023，China)

VDTN is a special delayed tolerant network,where messages are carried by moving vehicles from one end to another.Because there is no existence in the communication path from end to end between different source nodes and destination nodes,the relation from end to end is loose,and the possibilities of transferring messages to destination nodes decreases at a large scale.So a series of routing algorithms applied in the vehicle Ad-Hoc network cannot apply in VDTN greatly,routing algorithm in VDTN has become a challenging task.A routing algorithm based on contact history of nodes is proposed,which chooses the best moving nodes by nodes with contact history,and makes moving nodes whose relayed count is the biggest carry messages to destination nodes.The contact history contains information of relayed nodes which met with each node.The result suggests the routing algorithm based on contact history performs better in delivery ratio,average latency,overhead ratio than other algorithms.

VDTN;contact history;CONHR;delayed tolerant network

2015-11-03

2016-02-23

時間：2016-06-22

江蘇省大學生創新創業訓練計劃(SZDG2015043)

宋志華(1995-)，女，研究方向為容遲容斷網絡；暴建民，正高級工程師，碩士生導師，研究方向為物聯網。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0844.038.html

TP301.6

A

1673-629X(2016)07-0196-04

10.3969/j.issn.1673-629X.2016.07.042