宋志華,暴建民,謝元發(fā),周 雅

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

一種基于聯(lián)絡(luò)歷史的車載容遲網(wǎng)絡(luò)路由算法

宋志華,暴建民,謝元發(fā),周 雅

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

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

移動車載容遲網(wǎng)絡(luò)；聯(lián)絡(luò)歷史；CONHR算法；容忍延遲網(wǎng)絡(luò)

0 引 言

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

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

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

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

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

1 基于節(jié)點聯(lián)絡(luò)歷史的路由算法-CONHR算法

1.1 算法背景

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

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

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

1.2 算法假設(shè)

1.2.1 總體假設(shè)

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

(2)假定網(wǎng)絡(luò)中出現(xiàn)兩種終止節(jié)點：源節(jié)點和目的節(jié)點。它們作為網(wǎng)絡(luò)中的固定節(jié)點并且被安置在兩個不同的終端上。

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

(4)中繼節(jié)點是固定節(jié)點，也稱為路邊單元，利用存儲和轉(zhuǎn)發(fā)機制，分布在網(wǎng)絡(luò)中不同的道路交叉處來提高消息投遞率。與ONE中所說的中繼節(jié)點不同在于是否有中繼計數(shù)區(qū)域。

1.2.2 消息生成與復(fù)制策略

消息只能由源節(jié)點產(chǎn)生；源節(jié)點、中繼節(jié)點、移動節(jié)點秘密進行消息的轉(zhuǎn)發(fā)，即雙方通信時只有對方才能獲知彼此的消息。

1.2.3 調(diào)度與丟棄策略

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

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

1.2.4 轉(zhuǎn)發(fā)/限制的洪泛策略

基于限制的洪泛策略的消息轉(zhuǎn)發(fā)：利用節(jié)點間的相遇進行消息的復(fù)制，然后通過中繼節(jié)點進行消息的轉(zhuǎn)發(fā)，直至目的節(jié)點。

1.3 算法過程

CONHR遵循兩個過程：一是關(guān)于移動節(jié)點的歷史創(chuàng)建與更新；二是消息的轉(zhuǎn)發(fā)與傳遞。

1.3.1 移動節(jié)點的歷史創(chuàng)建或更新

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

表1 不同節(jié)點的歷史存儲

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

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

1.3.2 消息轉(zhuǎn)發(fā)與傳遞

無論何時源節(jié)點S相遇移動節(jié)點M，S都會檢查M存儲的歷史信息是否已經(jīng)存在于S的歷史記錄中。如果該歷史記錄對S通信范圍內(nèi)的所有移動節(jié)點有效，S節(jié)點則選擇該范圍內(nèi)中繼計數(shù)最高的移動節(jié)點作為下一節(jié)點進行消息轉(zhuǎn)發(fā)。

當移動節(jié)點之間相遇時，也會檢查彼此的歷史記錄信息，選擇中繼計數(shù)最高的移動節(jié)點作為下一節(jié)點進行消息轉(zhuǎn)發(fā)。

在以下出現(xiàn)的兩個場景中，如果移動節(jié)點之間具有相同的中繼計數(shù)或中繼計數(shù)均為0，那么隨機選取范圍內(nèi)的移動節(jié)點作為下一節(jié)點進行消息轉(zhuǎn)發(fā)。

2 仿真實驗

2.1 模擬器

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

2.2 仿真環(huán)境與配置

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

表2 環(huán)境模擬參數(shù)表

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

表3 ONE仿真器評估指標

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

2.3 模擬結(jié)果與分析

首先，通過改變節(jié)點數(shù)量，比較各個算法的消息投遞率，評價CONHR的穩(wěn)定性。

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

當節(jié)點數(shù)量增加時，節(jié)點之間與中繼節(jié)點之間的聯(lián)系增加，因此中繼計數(shù)增加。CONHR算法的核心在于計算中繼計數(shù)區(qū)域中的數(shù)值大小，從而決定消息的轉(zhuǎn)發(fā)路徑。因此，中繼計數(shù)越大，消息投遞率越大。

圖1 消息投遞率vs節(jié)點數(shù)量

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

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

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

圖2 平均時延vs節(jié)點數(shù)量

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

CONHR算法在開銷比上優(yōu)于Prophet算法和First Contact算法。相比之下，它具有更高的消息投遞率和中繼較少的信息。但Spray-and-Wait算法具有中繼更少數(shù)量的消息，由于在Spray-and-Wait算法中，其中繼節(jié)點直到遇見目的節(jié)點才會轉(zhuǎn)發(fā)與傳遞消息，故導(dǎo)致其路由開銷比比CONHR算法更小。

如圖3所示，當節(jié)點數(shù)量增多，CONHR算法的路由開銷比略有增加。這是由于節(jié)點數(shù)量越來越多，其中繼節(jié)點的數(shù)量也會相應(yīng)增加進行消息的轉(zhuǎn)發(fā)。

3 結(jié) 論

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

4 結(jié)束語

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

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

[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] 王 豐，暴建民，彭慧珺.延遲容忍網(wǎng)絡(luò)中移動模型對路由算法的影響[J].計算機技術(shù)與發(fā)展，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] 孫踐知.機會網(wǎng)絡(luò)路由算法[M].北京：人民郵電出版社，2013.

[14] 孫踐知，韓忠明，陳 丹,等.Wait and Spray：一種改進的機會網(wǎng)絡(luò)路由算法[J].計算機工程與應(yīng)用，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

江蘇省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃(SZDG2015043)

宋志華(1995-)，女，研究方向為容遲容斷網(wǎng)絡(luò)；暴建民，正高級工程師，碩士生導(dǎo)師，研究方向為物聯(lián)網(wǎng)。

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