車載時延容忍網(wǎng)絡(luò)路由協(xié)議研究

姜海濤，張宏，李千目

(南京理工大學 計算機科學與工程學院，江蘇 南京 210094)

1 引言

車載網(wǎng)絡(luò)是一種依靠安裝有無線通信設(shè)備的車輛實現(xiàn)數(shù)據(jù)傳輸?shù)臒o線自組織網(wǎng)絡(luò)[1]。近年來，隨著無線通信技術(shù)以及車輛GPS系統(tǒng)的發(fā)展，車載網(wǎng)絡(luò)得到了廣泛的應(yīng)用。例如將車流量信息通過車載網(wǎng)絡(luò)廣播給公路上的車輛，司機可以提前更改行車路線，避開擁塞路段；將交通事故信息傳遞給最近的警察局和急救中心，事故可以得到及時的處理；司機通過車載網(wǎng)絡(luò)查詢附近的加油站、餐館等信息，方便出行。

將傳統(tǒng)的MANET（mobile ad hoc network）路由協(xié)議直接應(yīng)用于車載網(wǎng)絡(luò)，并不能取得令人滿意的性能[2]。其主要原因有以下2點：1）MANET中總是在源和目的間尋求一條代價最低的鏈路傳輸數(shù)據(jù)，將鏈路的中斷視為短暫的異常情況。但是在車載網(wǎng)絡(luò)中，車輛的高移動性致使車輛間的連接經(jīng)常中斷，難以保證持續(xù)穩(wěn)定的連接。2）在車輛密度較低的情況下，車輛很可能處于孤立的狀態(tài)，不存在可通信的鄰居車輛，導致數(shù)據(jù)分組的丟棄。車載網(wǎng)絡(luò)具有間歇連通性和低密度性使其更加符合時延容忍網(wǎng)絡(luò)[3](DTN, delay-tolerant networks)的特點。時延容忍網(wǎng)絡(luò)是一種在源節(jié)點和目的節(jié)點之間不存在端到端鏈路的條件下，依靠存儲轉(zhuǎn)發(fā)的異步通信方式實現(xiàn)數(shù)據(jù)交換的無線自組網(wǎng)絡(luò)。目前已經(jīng)有相關(guān)工作采用時延容忍的思想設(shè)計車載路由協(xié)議，并取得了一些研究成果。文獻[4]中提出了MDDV協(xié)議，利用車輛攜帶數(shù)據(jù)到目標區(qū)域，并將數(shù)據(jù)分組擴散給區(qū)域內(nèi)的車輛。文獻[5]中提出的VADD路由協(xié)議，基于歷史交通流量信息，車輛可以在路口選擇一個合適的傳遞方向，最終將數(shù)據(jù)傳遞到目的地。但是在這2種方法中，數(shù)據(jù)的目的地或目的區(qū)域都是固定的，無法適用于移動節(jié)點的情況。文獻[6]中基于對中國上海市區(qū)出租車移動路線的研究，引入車載網(wǎng)絡(luò)(SUVnet)的概念，并對傳染路由進行了改進，提出DAER路由協(xié)議。但是文章假設(shè)節(jié)點知道目的節(jié)點的當前位置，這種假設(shè)在一定條件下是無法滿足的。文獻[7]引入固定基礎(chǔ)設(shè)施輔助數(shù)據(jù)的傳輸，當車輛發(fā)現(xiàn)自己的移動方向背離數(shù)據(jù)分組的目的地時，則將數(shù)據(jù)分組轉(zhuǎn)發(fā)給固定設(shè)施，由后繼的車輛從固定設(shè)施獲取數(shù)據(jù)分組繼續(xù)傳遞過程。這種方法可以保證數(shù)據(jù)傳遞的準確性，但需要額外增加一些基礎(chǔ)設(shè)施。

針對車載時延容忍網(wǎng)絡(luò)中數(shù)據(jù)傳遞的問題，本文首先分析了車輛的移動模型，定義不同移動模型之間的關(guān)系，并提出一種模型相似度評價機制（MMSE, movement model similarity evaluation scheme）；然后基于MMSE提出了一種面向移動范圍轉(zhuǎn)發(fā)動態(tài)多副本（MROFDM, movement range oriented forwarding and dynamic multi-coyies）路由協(xié)議。該協(xié)議利用移動模型間的相似度和車輛的本地實時信息，將數(shù)據(jù)向目的節(jié)點的移動范圍內(nèi)轉(zhuǎn)發(fā)，同時采用副本均衡策略，動態(tài)調(diào)整不同類型數(shù)據(jù)分組的副本數(shù)目。實驗結(jié)果顯示，MROFDM 協(xié)議與傳統(tǒng)的多副本路由協(xié)議相比，在車載網(wǎng)絡(luò)環(huán)境下具有很好的可行性和適應(yīng)性。

2 車載網(wǎng)絡(luò)模型

假設(shè)網(wǎng)絡(luò)的規(guī)模限定在一個范圍內(nèi)，其中部分車輛安裝有無線通信設(shè)備（例如在某個擁有數(shù)十萬輛汽車的城市中，只有千余輛汽車安裝有無線通信設(shè)備），在這些車輛之間需要實現(xiàn)消息的傳遞。目前大部分車輛還不具備無線通信能力，同時在所有車輛上安裝通信設(shè)備，并不是很現(xiàn)實，因此本文的這種假設(shè)是合理的。本文中的車輛均指安裝無線通信設(shè)備的車輛。

車載網(wǎng)絡(luò)中存在3種重要的實體：車輛、路口和路段，其中前者處于運動當中，而后兩者相對固定。那么路口和路段構(gòu)成了網(wǎng)絡(luò)的靜態(tài)結(jié)構(gòu)，可以用平面圖 G = { V, E}表示，每個的路口為一個頂點，即V中一個元素，如果路段連接2個路口，那么E中增加一條邊。目前很多大城市路網(wǎng)逐步發(fā)展成由隧道、立交橋構(gòu)成的立體圖。本文從平面路網(wǎng)的情況入手，研究基礎(chǔ)的車載時延容忍網(wǎng)絡(luò)路由協(xié)議[5,7,8]，在以后的工作中會考慮立體城市路網(wǎng)的情況。

如果消息的目的地是固定的，那么可以計算出從源節(jié)點到目的固定傳輸路線，消息經(jīng)過若干路段和路口之后，到達目的節(jié)點[5]。在本文中，源和目的車輛都處于運動之中，使得路由過程不可預(yù)先確定，而是中繼車輛逐跳決定消息的傳輸，不過這正迎合了時延容忍網(wǎng)絡(luò)異步通信的特點。車輛在行駛的過程中，大部分時間內(nèi)不存在鄰居車輛，只有當2個車輛相遇時，消息交換才可能發(fā)生，這滿足時延容忍網(wǎng)絡(luò)間歇性連接的特點。車輛會攜帶消息移動，增加了消息傳遞的時延，這更體現(xiàn)出時延容忍網(wǎng)絡(luò)的本質(zhì)特點。但是車輛作為網(wǎng)絡(luò)中的節(jié)點，被限定在圖G上運動，這是普通時延容忍網(wǎng)絡(luò)所不具有的，因此可以將車載網(wǎng)絡(luò)視為時延網(wǎng)絡(luò)的一個特定實例。下一節(jié)會結(jié)合節(jié)點的移動模型和車載網(wǎng)絡(luò)的特點，給出MMSE。

3 車輛移動模型相似度評價機制

時延容忍網(wǎng)絡(luò)相比較于傳統(tǒng)的MANET網(wǎng)絡(luò)的顯著特點，很大程度上是由于節(jié)點的頻繁運動造成的。在以往的研究中，提出并使用了多種移動模型，例如：隨機移動模型中節(jié)點之間的相遇概率符合指數(shù)分布[9]；擺渡路由中信使具有固定運行軌跡[10]；基于區(qū)域的移動模型中，節(jié)點的移動傾向于回到自己的區(qū)域[11]。本文認為單純的使用一種模型很難描述出所有車輛的移動特點，因此定義3類模型描述不同車輛的移動。

定義 1 固定模型（FM, fixed model），車輛按照固定的路線移動。例如公交、企業(yè)的班車等停靠固定的站點，符合FM移動模型。使用移動路線中經(jīng)過的路口描述該移動模型。

定義 2 規(guī)律模型（RM, regular model），車輛的移動遵循一定的統(tǒng)計規(guī)律，例如人們開車往返于家庭和單位之間。通過2個參數(shù)描述此類的移動模型：車輛經(jīng)常出沒的地點和隨機移動的概率。前者使用車輛經(jīng)常出沒的路口（稱為固定路口）表示，而后者反應(yīng)了車輛不在固定路口或者不向固定路口移動的概率。

定義3 不確定模型（UM, uncertainty model），車輛隨機移動，不具備穩(wěn)定性因素。例如出租車根據(jù)乘客的需求決定目的地，而每個乘客的需求通常是無關(guān)的。

車載網(wǎng)絡(luò)中主要融合了上述 3種不同的移動模型，但實際應(yīng)用中車輛的移動方式肯定更為復雜，車輛的移動模型也值得在以后的工作中進一步的研究。本文統(tǒng)一使用如下的結(jié)構(gòu)描述節(jié)點的移動模型：

其中，vehicleid表示標識了的車輛。rnd表示車輛隨機移動的概率，F(xiàn)M模型固定為 0，UM模型固定為1，而RM模型為實際的隨機概率，介于0到1之間。vertexs是一個數(shù)組，且vertex[]s iV∈，如果是FM模型，那么表示車輛移動路線上的路口，如果是RM模型，表示車輛的固定路口，如果是UM模型，那么為空。通過rnd可以計算出移動模型的類型：

定義 4 等價關(guān)系。2個固定模型，遵循同樣的移動線路。例如同一條公交線路上車輛。

定義5 相似關(guān)系。2個規(guī)律模型，2個固定模型，一個固定模型與一個規(guī)律模型的固定路口或者移動線存在交集。例如2條公交線路具有相同的站點，那么這2條線路上的車輛會經(jīng)過一段重疊的路段。

定義 6 獨立關(guān)系。2個規(guī)律模型或者一個規(guī)律模型和一個固定模型的固定路口或者移動線路不存在交集。例如兩私家車輛經(jīng)常出沒于不同的地點，它們的運動范圍相對獨立，故稱為獨立關(guān)系。

定義 7 平行關(guān)系。2個固定模型的移動線路不存在交集。例如2條不存在相同站點的公交線路上的2個車輛，它們基本不會相遇，類似于同一平面中永不相交的2條平行直線，故稱為平行關(guān)系。

定義8 默認關(guān)系。不屬于以上4種情況，都歸為默認關(guān)系。這5種關(guān)系可以反映出2個節(jié)點移動模型之間的相似度，如圖1所示。

圖1 移動模型之間的相似度

本文將默認關(guān)系相似度定義為 0，UM 模型不存在固定的路口或移動線路，因此與其他任何模型之間的相似度都為 0。相似關(guān)系中，相似度隨著重疊路口數(shù)目的增加而增加，極限情況下，2個模型的移動路線完全一致，就形成了等價關(guān)系，相似度定義為 1。獨立關(guān)系中，相似度隨著節(jié)點運動隨機性的減少而減少，極限情況下，2個模型的線路都是固定的，就形成了平行關(guān)系，相似度定義為-1。移動模型相似度反應(yīng)了節(jié)點移動范圍的重合程度。正的相似度說明節(jié)點的移動范圍固定且重合，從而增加節(jié)點間的相遇概率，因此有助于數(shù)據(jù)的傳輸。同理負的相似度會阻礙數(shù)據(jù)的傳輸。根據(jù)移動模型M1和M2間的不同關(guān)系，本文使用式（6）計算M1和M2之間的相似度

4 MROFDM路由協(xié)議

時延容忍網(wǎng)絡(luò)中，通常采用基于受限副本數(shù)的路由協(xié)議，這是一種性能與能耗之間的折中方案，目前已經(jīng)得到了廣泛的認可[9,12]?；贛MSE本文提出MROFDM路由協(xié)議，其基本過程是：源節(jié)點產(chǎn)生數(shù)據(jù)分組后通過副本均衡策略產(chǎn)生L個副本并進行可縮減的分發(fā)，之后每個副本獨立地執(zhí)行轉(zhuǎn)發(fā)過程，直到其中一個副本到達目的節(jié)點。

假設(shè)路段和路口是固定不變的，并且每個車輛具有所有路段和路口的信息。車輛的移動模型是確定的信息，對移動模型信息執(zhí)行一次全局的洪泛過程，不會占用過多的網(wǎng)絡(luò)資源，就可以讓每個車輛保存所有車輛的移動模型。此外每個車輛知道自己的當前目的地。下面從數(shù)據(jù)轉(zhuǎn)發(fā)和副本分發(fā)與均衡2個方面詳細介紹路由協(xié)議的實現(xiàn)過程。

4.1 面向移動范圍轉(zhuǎn)發(fā)策略

在介紹轉(zhuǎn)發(fā)策略之前，先定義某個頂點dvV∈與移動模型M之間的距離 DM ：

其中， d is( v1, v2)函數(shù)用于計算頂點 v1和 v2之間的距離，MD表示 vd與vertexsm頂點中最近頂點的距離。

時延容忍網(wǎng)絡(luò)路由協(xié)議的轉(zhuǎn)發(fā)過程可以描述為：當2個節(jié)點 n1和 n2相遇后，對于 n1緩沖區(qū)內(nèi)的數(shù)據(jù)分組 pi，其目的節(jié)點為 nd，副本數(shù)目為1（副本數(shù)目大于1的情況將在4.2節(jié)中介紹），若 n2更適合做 pi中繼節(jié)點，則 n1將數(shù)據(jù)分組轉(zhuǎn)發(fā)給 n2，n2緩沖區(qū)內(nèi)的數(shù)據(jù)分組亦然。因此轉(zhuǎn)發(fā)的過程實為尋找合適中繼節(jié)點的過程。

本文使用MMSE分別評價dn與1n移動模型以及dn與2n移動模型的相似度，由相似度高的節(jié)點持有ip，如果相似度相同，則根據(jù)節(jié)點的實時信息，分別計算1n和2n的當前目的地與dn的移動模型之間的距離，由距離短的節(jié)點持有ip。如果距離為undefined，由原來的節(jié)點繼續(xù)持有ip。

數(shù)據(jù)分組轉(zhuǎn)發(fā)過程中分別利用了模型相似度和實時目的地轉(zhuǎn)發(fā)策略，其目的就在于讓數(shù)據(jù)分組向著目的節(jié)點的移動范圍發(fā)送，故稱之為面向移動范圍的轉(zhuǎn)發(fā)策略。

4.2 副本均衡策略

根據(jù)數(shù)據(jù)分組目的節(jié)點的移動模型，可以將數(shù)據(jù)分組分為3類：FM數(shù)據(jù)分組、RM數(shù)據(jù)分組和UM數(shù)據(jù)分組。4.1節(jié)中的轉(zhuǎn)發(fā)策略存在一個盲區(qū)，對于UM數(shù)據(jù)分組，其目的節(jié)點與其余節(jié)點移動模型的相似度均為 0，同時與所有頂點的距離均為undefined。這是由于很難挖掘UM模型規(guī)律所造成的。

現(xiàn)有研究已證明增加副本數(shù)目可以提高路由的性能，并且給出了副本數(shù)的計算方式[12]，因此對于UM數(shù)據(jù)分組，可以通過適當增加副本數(shù)目的策略提高路由性能。然而憑空增加副本數(shù)目帶來會加劇網(wǎng)絡(luò)負載，所以本文使用副本均衡的策略，在副本的分發(fā)階段，保證傳輸成功率的前提下，動態(tài)地縮減FM和RM數(shù)據(jù)分組的副本數(shù)，并將縮減的副本數(shù)補充給UM數(shù)據(jù)分組。

分發(fā)是指源節(jié)點將數(shù)據(jù)分組的L個副本傳遞給 L - 1個不同的節(jié)點，自己保留一個副本，每個節(jié)點拒絕多次接收同一個數(shù)據(jù)分組的副本。當2個節(jié)點 n1和 n2相遇后，傳統(tǒng)的副本分發(fā)執(zhí)行過程為：對于節(jié)點 n1緩沖區(qū)內(nèi)的數(shù)據(jù)分組 pi，其目的節(jié)點為nd，副本數(shù)目為 l ＞ 1 ，且 n2緩沖區(qū)內(nèi)沒有 pi的副本，那么 n1將 l2個副本發(fā)送給 n2，自己保留l1個，需要確定l1與 l2的值，使得l1+ l2= l， n2緩沖區(qū)內(nèi)的數(shù)據(jù)分組亦然。

基于 MMSE可以得到，如果 n2與 nd移動模型的相似度大于 0，那么它們具有較高的相遇概況，可以將 n2視為 pi的合適中繼節(jié)點。在確定 l1與l2值時，讓 l1+ l2≤ l，達到動態(tài)縮減副本并且保證傳輸成功率的目的。本文使用式（8）計算 l1與l2值

這種動態(tài)縮減分發(fā)策略，在發(fā)現(xiàn)合適中繼節(jié)點時，根據(jù)中繼節(jié)點和目的節(jié)點移動模型之間的相似度，動態(tài)縮減副本的數(shù)目，同時在未遇到合適中繼節(jié)點時，使用二元分發(fā)策略[12]快速分發(fā)副本。每個節(jié)點使用變量bal累計縮減的副本數(shù)

當節(jié)點創(chuàng)建新的UM數(shù)據(jù)分組的時候，如果其bal的值大于0，則可以適當為其補充ex個副本，同時相應(yīng)減少bal的值。節(jié)點數(shù)據(jù)分組的產(chǎn)生速率為λ1，其中UM數(shù)據(jù)分組占γ，那么UM數(shù)據(jù)分組的產(chǎn)生率為λ=λ1? γ。假設(shè)動態(tài)縮減速率為redu，為了保持副本的縮減速率與補充速率之間的平衡，ex需要滿足

節(jié)點使用遞推的方式計算redu

其中，Δli表示第i次縮減的副本數(shù)目，△ti表示第i- 1次縮減和第i次縮減之間經(jīng)歷的時間， ti表示第i次縮減的時間戳。在計算縮減速率時使用時間戳作為權(quán)重，可以保證估計的實時性，同時兼顧歷史數(shù)據(jù)。節(jié)點在每次分發(fā)之后更新縮減速率并累計bal值，在每次產(chǎn)生UM數(shù)據(jù)分組后計算ex值，確定副本數(shù)目并減少bal值。

4.3 路由協(xié)議完整描述

結(jié)合4.1節(jié)與4.2節(jié)的內(nèi)容，算法1描述了完整的MROFDM路由協(xié)議。其中，n.mm表示節(jié)點n的移動模型，n.des表示節(jié)點n的當前目的地，n.bal用于累計動態(tài)減少的副本數(shù)目。msg表示數(shù)據(jù)分組，msg.to為該數(shù)據(jù)分組的目的節(jié)點，msg.copies為數(shù)據(jù)分組的副本數(shù)目，msg.new()方法用于判斷數(shù)據(jù)分組是否為新創(chuàng)建的，msg.clone()方法用于復制一個相同的數(shù)據(jù)分組。 ()calex 函數(shù)用于計算動態(tài)增加的副本數(shù)目，并減少 .nbal的值。 ()sim 函數(shù)用于計算2個移動模型之間的相似度。 ()dis函數(shù)用于計算分發(fā)的副本數(shù)目。 m d ( )函數(shù)用于計算 n.des與移動模型之間的距離。 u dredu ( )函數(shù)用于更新縮減速率。算法的第 2)～4)行描述了源節(jié)點動態(tài)增加副本數(shù)目的過程；第 5)～7)行表示如果遇到目的節(jié)點，直接完成數(shù)據(jù)的傳遞；第 10)～14)行描述了分發(fā)過程；第16)～20)行描述了轉(zhuǎn)發(fā)過程。

算法1 節(jié)點n1和n2接觸后的路由過程

1) for(every msg in n1 cache){

2) if(msg.new() && msg.to.mm == UM){

3) msg.copies += calex();

//使用式(10)計算ex的值, 同時更新bal的值

4) }

5) if(msg.to == n2){

//遇到目的節(jié)點完成數(shù)據(jù)傳遞

6) send msg to n2; countinue;

7) }

8) s1 = sim(msg.to.mm, n1.mm); s2 = sim(msg.to.mm, n2.mm)

//使用式(6)計算移動模型之間相似度

9) if(msg.copies ＞ 1){

10) msg1 = msg.clone();

11) dis(l1,l2);

//使用式(8)計算分發(fā)副本數(shù)

12) n1.bal += (msg.copies - l1 - l2);

//使用式(9)更新bal的值

13) msg.copies = l1; msg1.copies = l2;send msg1to n2;

14) udredu(n1);

//使用式(11)更新縮減速率

15) }else{

16) if(s2 ＞ s1){

17) send msg to n2;

18) }else if(to.mm != UM &&md(n2.des, to.mm) < md(n1.des , to.mm) ){

//使用式(7)計算目的地與移動模型之間的距離

19) send msg to n2;

20) }

21) }

22) }

23) //n2 do the same process as n1

5 仿真實驗及結(jié)果分析

在機會網(wǎng)絡(luò)的ONE（opportunistic network en-vironment）平臺上[13]編寫仿真程序，實現(xiàn)了MROFDM 路由協(xié)議，并設(shè)計一個場景，檢驗協(xié)議的性能。該場景中設(shè)置1 104個路口和1 200條路段，并且設(shè)定3種移動節(jié)點：bus節(jié)點遵從固定的移動模型，沿著預(yù)定的路線往返運動，設(shè)置5條由路口連成的固定線路，平均分配bus到這5條線路；car節(jié)點遵從規(guī)律移動模型，初始設(shè)定3個路口作為固定路口，并且以 20%～30%的概率隨機選取任意一個路口作為目的地，以 70%～80%的概率選擇固定路口為目的地；taxi節(jié)點遵從不確定移動模型，隨機選擇任意路口作為目的地。默認情況下仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

實驗過程中，平均每個節(jié)點大約會產(chǎn)生30個數(shù)據(jù)分組，數(shù)據(jù)分組的目的節(jié)點在全局范圍內(nèi)隨機選擇。在上述環(huán)境中，模擬了本文提出的MROFDM協(xié)議，以及只支持轉(zhuǎn)發(fā)策略的固定副本（MROFSM）路由協(xié)議，同時作為比較，實現(xiàn)了傳統(tǒng)的噴霧等待路由[12]（SW）和PROPHET 路由[14]（PROP）。

5.1 移動模型的相似度

本文基于車輛移動模型的相似度實現(xiàn)路由策略，在路由前會首先計算所有節(jié)點移動模型之間的相似度。由于遵從隨機移動模型的taxi節(jié)點與其余節(jié)點移動模型的相似度均為0，因此圖2只顯示出bus節(jié)點之間、car節(jié)點之間、bus節(jié)點與car節(jié)點之間的移動模型相似度分布情況。

圖2中顯示，bus節(jié)點之間的移動模型相似度呈現(xiàn)3種情況：同一條公交線路上bus節(jié)點之間相似度為 1，不同公交線路但是存在部分重合站點的bus節(jié)點之間相似度在0.25左右，不同公交線路且不存在重合站點的 bus節(jié)點之間相似度為-1。car節(jié)點之間的移動模型相似度也呈現(xiàn)3種情況：極少部分固定路口完全相同的car節(jié)點之間相似度接近0.5，少部分存在相同固定路口的car節(jié)點之間相似度在0.1左右，大部分car節(jié)點不存在相同的固定路口，它們之間相似度在-0.45左右。bus節(jié)點和car節(jié)點之間的移動模型相似度存在2種情況：一些car節(jié)點的固定路口與bus節(jié)點的線路存在交集，它們之間相似度在0.05左右，否則節(jié)點之間相似度大約在-0.75。從整體的相似度分布可以看出，存在共同路口的移動模型之間，滿足等價或相似關(guān)系，計算得到的相似度值為正數(shù)，否則移動模型之間形成獨立或平行關(guān)系，計算得到的相似度值為負數(shù)，這與第3節(jié)中定義是吻合的。

圖2 移動模型相似度分布

5.2 路由協(xié)議的性能比較

所有協(xié)議的副本數(shù)目是相同的，因此各個協(xié)議對節(jié)點緩沖區(qū)資源的需求也在同一數(shù)量級，本文會在5.3節(jié)中對此進行比較。本節(jié)先從傳輸成功率和延時2個方面對4種路由協(xié)議的整體性能進行對比和分析。在實驗中，分別改變節(jié)點數(shù)目以及數(shù)據(jù)分組的副本數(shù)目，比較不同路由協(xié)議的性能。圖3和圖4分別顯示了節(jié)點數(shù)目為45至150時（每次遞增15個，每種節(jié)點增加5個），4種路由協(xié)議的成功率和延時。

圖3 不同節(jié)點數(shù)目條件下的傳輸成功率

圖4 不同節(jié)點數(shù)目條件下的傳輸延時

從圖3中可以看出，路由協(xié)議的性能基本不受節(jié)點數(shù)目的影響。與噴霧等待路由和PROPHET路由相比，本文提出的轉(zhuǎn)發(fā)策略可以明顯地提高傳輸成功率，這說明利用移動模型相似度和實時轉(zhuǎn)發(fā)策略是有效的。模型相似度高的節(jié)點具有較高的相遇概率，而實時策略將數(shù)據(jù)分組帶往目的節(jié)點的移動范圍，讓數(shù)據(jù)分組在未來有較高的概率遇到目的節(jié)點或者合適的中繼節(jié)點。MROFDM 協(xié)議在MROFSM的基礎(chǔ)上，可以再提升1%～2%的傳輸成功率。這說明副本均衡策略是有效的。PROPHET路由根據(jù)歷史信息做出轉(zhuǎn)發(fā)決定，為數(shù)據(jù)傳輸提供一定的幫助，因此性能略高于噴霧等待路由。從延時的角度分析，也可以得到相同的結(jié)論，MROFDM 協(xié)議在提高成功率的同時，有效地降低了端到端的延時。隨著節(jié)點數(shù)目的增加，各協(xié)議的延時均呈現(xiàn)略微下降趨勢，這主要是因為增加節(jié)點數(shù)目會減少節(jié)點的平均相遇間隔，有助于降低傳輸延時。

圖5和圖6分別顯示了數(shù)據(jù)分組的副本為2～14個時（每次遞增1個），4種路由協(xié)議的成功率和延時?？傮w看來，隨著副本數(shù)目的增加，各個協(xié)議的性能都有所提升，這與經(jīng)典理論是吻合的[12]。4種協(xié)議性能之間的相對關(guān)系與圖3和圖4的結(jié)果一致的。此外圖中還說明：1）隨著副本數(shù)目的增加，各個路由協(xié)議之間的性能差距在縮小，這是因為高副本數(shù)已經(jīng)為噴霧等待路由性能帶來較為優(yōu)秀的性能，因此性能的提升空間有限；2）在副本數(shù)目較低的時候，難以從原本就有限的副本數(shù)中縮減副本，基本沒有執(zhí)行副本均衡過程，因此 MROFDM與MROFSM的性能是相同；3）在副本數(shù)目較高的時候，增加副本數(shù)目對協(xié)議性能的提升不再明顯，MROFDM與MROFSM的性能趨于一致。

圖5 不同副本數(shù)目條件下的傳輸成功率

圖6 不同副本數(shù)目條件下的傳輸延時

上面2組實驗結(jié)果已經(jīng)說明MROFDM協(xié)議具有比傳統(tǒng)路由更加優(yōu)秀的性能，但是MROFDM協(xié)議與MROFSM 協(xié)議相比，性能并沒有顯著提升。在本次的實驗中，分別統(tǒng)計目的節(jié)點為bus節(jié)點的數(shù)據(jù)分組（bus數(shù)據(jù)分組），目的節(jié)點為car節(jié)點的數(shù)據(jù)分組（car數(shù)據(jù)分組），目的節(jié)點為taxi移動模型的數(shù)據(jù)分組（taxi數(shù)據(jù)分組），3種數(shù)據(jù)分組的傳輸成功率和延時，以詳細分析面向移動范圍轉(zhuǎn)發(fā)與副本均衡策略的作用。由于節(jié)點數(shù)目對協(xié)議的性能影響不大，并且成功率的提升與延時的減少是相互印證的，因此下面主要考察不同副本數(shù)目條件下，協(xié)議的傳輸成功率。

圖7～圖9分別顯示了3種數(shù)據(jù)分組的傳輸成功率。圖7顯示與噴霧等待路由相比，本文提出的轉(zhuǎn)發(fā)策略可以提升bus數(shù)據(jù)分組的傳輸成功率，且MROFDM協(xié)議與MROFSM協(xié)議bus數(shù)據(jù)分組的傳輸成功率是一致，并沒有因為動態(tài)縮減副本數(shù)目而減少。圖8顯示car數(shù)據(jù)分組的傳輸成功率在本文轉(zhuǎn)發(fā)策略的幫助下，也有較為顯著的提升。圖9顯示MROFDM協(xié)議是唯一可以提升taxi數(shù)據(jù)分組傳輸成功率的協(xié)議，盡管效果并不是很明顯。實驗過程中，每次動態(tài)增加的副本數(shù)大約為1～2個，因此n個副本時MROFDM協(xié)議的taxi數(shù)據(jù)分組傳輸成功率與n+2個副本時噴霧等待協(xié)議的taxi數(shù)據(jù)分組傳輸成功率基本一致的。比較 3組實驗結(jié)果，PROPHET協(xié)議僅能提升bus數(shù)據(jù)分組的成功率，其綜合性能略高于噴霧等待路由；MROFSM可以顯著提升bus數(shù)據(jù)分組與car數(shù)據(jù)分組的成功率，因此其性能大幅優(yōu)于噴霧等待路由；MROFDM 通過副本均衡策略，可以在不降低其他數(shù)據(jù)分組成功率的前提下，提升taxi數(shù)據(jù)分組的成功率。綜合以上分析，不難得出上一節(jié)中的結(jié)論。

圖7 bus數(shù)據(jù)分組的傳輸成功率

圖8 car數(shù)據(jù)分組的傳輸成功率

圖9 taxi數(shù)據(jù)分組的傳輸成功率

上述實驗都是在3種節(jié)點數(shù)目相等的條件下進行的。在本次實驗中，有意增加某種節(jié)點的數(shù)目并減少另外2種節(jié)點的數(shù)目，檢測MROFDM協(xié)議在不均衡節(jié)點類型環(huán)境下的性能。實驗中保持節(jié)點總數(shù)為90個，將某種節(jié)點的個數(shù)設(shè)置為50，其余2種設(shè)置為20。圖10給出實驗結(jié)果，為了便于比較，在圖10中加入3種節(jié)點數(shù)目相同時的數(shù)據(jù)。

圖10 不同節(jié)點比例條件下傳輸成功率

實驗結(jié)果顯示，在bus節(jié)點比例較高的情況下，協(xié)議的性能有所下降，這主要是由于在源和目的節(jié)點的相似度小于0時，缺乏隨機節(jié)點將數(shù)據(jù)分組帶往目的節(jié)點的運動區(qū)域，導致部分數(shù)據(jù)分組無法完成傳遞。其余情況下協(xié)議的性能與缺省情況基本一致，這說明本文提出的協(xié)議在3種移動模型的節(jié)點比例不均衡的環(huán)境下基本可以正常運行。

5.3 實時性及隨機誤差分析

上節(jié)中的結(jié)果均為仿真結(jié)束后統(tǒng)計得出，并不能實時反映協(xié)議的執(zhí)行情況。除了延時與成功率，網(wǎng)絡(luò)負載是一個衡量路由性能的實時指標。每隔1h統(tǒng)計所有節(jié)點緩沖區(qū)內(nèi)的數(shù)據(jù)分組總數(shù)，作為網(wǎng)絡(luò)負載。圖11顯示了默認情況下（6個副本，90個節(jié)點），網(wǎng)絡(luò)的實時負載信息。

圖11 網(wǎng)絡(luò)的實時負載

實驗開始后，隨著數(shù)據(jù)分組的不斷產(chǎn)生，網(wǎng)絡(luò)負載呈上升趨勢。實驗運行 4h后，新數(shù)據(jù)分組的產(chǎn)生的同時已有數(shù)據(jù)分組傳遞完成，網(wǎng)絡(luò)負載逐漸趨于平穩(wěn)。在實驗的最后 2h內(nèi)不再產(chǎn)生新的數(shù)據(jù)分組，網(wǎng)絡(luò)負載呈下降趨勢。MROFDM 協(xié)議可以更快地傳遞緩沖區(qū)內(nèi)的數(shù)據(jù)分組，因此具有最小的網(wǎng)絡(luò)負載。其余情況下的網(wǎng)絡(luò)負載也呈現(xiàn)相似的趨勢，本文就不再一一表述。

由于實驗中的許多元素都是隨機產(chǎn)生的，例如隨機為數(shù)據(jù)分組選擇目的節(jié)點，taxi節(jié)點隨機選擇目的地等，所以隨機誤差是難以避免的。本節(jié)最后通過90個節(jié)點時，噴霧等待和MROFDM協(xié)議的傳輸成功率，衡量實驗中的隨機誤差，圖 12顯示了實驗的具體結(jié)果。隨機因素在帶來結(jié)果波動的同時，也造成了副本數(shù)為 1n+ 時的實驗結(jié)果不一定優(yōu)于副本數(shù)為n時的情況?？梢妼嶒炛械碾S機因素確實會導致實驗結(jié)果中存在隨機誤差。但是隨著副本數(shù)目的增加，統(tǒng)計得到的平均傳輸成功率還是呈現(xiàn)上升趨勢，這體現(xiàn)了求取多次實驗結(jié)果的平均值作為仿真結(jié)果以消除隨機誤差的必要性。

圖12 每次實驗的傳輸成功率

6 結(jié)束語

本文通過對車載網(wǎng)絡(luò)中節(jié)點移動模型的分析，提出 MMSE評價移動模型相似度。基于節(jié)點模型的相似度，從副本轉(zhuǎn)發(fā)與均衡 2個方面，設(shè)計了

MROFDM 路由協(xié)議。實驗結(jié)果顯示，與傳統(tǒng)協(xié)議相比，MROFDM 協(xié)議可以有效地提升路由性能。同時對實驗執(zhí)行過程中的實時性及隨機誤差進行了分析。以后的工作中將在以下方面進行進一步研究：1）研究針對于固定移動模型的路由方法，優(yōu)化固定移動模型節(jié)點比例高時協(xié)議的性能。2）考慮立體路網(wǎng)、復雜車輛移動模型、交通信號燈等因素，使路由過程更符合實際情況。

[1] GERLA M, KLEINROCK L. Vehicular networks and the future of the mobile Internet [J]. Computer Networks, 2011, 55(2)：457-469.

[2] CHOFFNES D R, BUSTAMANTE F E. An integrated mobility and traff i c model for vehicular wireless networks[A]. Proceedings of the 2nd ACM International Workshop on Vehicular Ad Hoc Networks[C].New York： ACM, 2005.69-78.

[3] 王博，黃傳河，楊文忠. 時延容忍網(wǎng)絡(luò)中基于效用轉(zhuǎn)發(fā)的自適應(yīng)機會路由算法[J]. 通信學報，2010, 31(10)： 36-47.WANG B, HUANG C H, YANG W Z. Adaptive opportunistic routing protocol based on forwarding-utility for delay tolerant networks[J].Journal on Communications, 2010, 31(10)： 36-47.

[4] WU H, FUJIMOTO R M, GUENSLER R, et al. MDDV： a mobility-centric data dissemination algorithm for vehicular networks[A].Proc of the 1st ACM Int Workshop on Vehicular Ad Hoc Networks(VANET)[C]. New York： ACM, 2004. 47-56.

[5] ZHAO J, CAO G. VADD： vehicle-assisted data delivery in vehicular ad hoc networks[A]. Proc of the INFOCOM 2006[C]. New York：IEEE Communications Society, 2006. 1-12.

[6] HUANG H Y, LUO P E, LI M, et al. Performance evaluation of SUV-net with real-time traffic data[J]. IEEE Trans on Vehicular Technology,2007,56(6)：3381-3396.

[7] DING Y, WANG C, XIAO L. A static-node assisted adaptive routing protocol in vehicular networks[A]. Proc of the 4th ACM Int Workshop on Vehicular Ad Hoc Networks[C]. New York： ACM Press, 2007. 59-68.

[8] 李陟，查玄閱，劉鳳玉等. 公交時延容忍網(wǎng)絡(luò)中基于索引的多級分組路由算法[J]. 計算機研究與發(fā)展，2011, 48(3)： 407-414.LI Z, ZHA X Y, LIU F Y, et al. Indexing based multi-level clustering routing algorithm in public transportation delay tolerant networks [J].Journal of Computer Research and Development, 2011, 48(3)： 407-414.

[9] 徐佳，李千目，張宏等. 機會網(wǎng)絡(luò)中的自適應(yīng)噴霧路由及其性能評估[J]. 計算機研究與發(fā)展，2010, 47(9)： 1622-1632.XU J, LI Q M, ZHANG H, et al. Performance evaluation of adptive sparay routing for opportuntic networks[J]. Journal of Computer Research and Development, 2010, 47(9)： 1622-1632.

[10] ZHANG Z, FEI Z M. Route design for multiple ferries in delay tolerant networks[A]. Wireless Communications and Networking Conference. IEEE[C]. 2007.3460-3465.

[11] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Performance analysis of mobility-assisted routing[A]. Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing[C]. New York： ACM, 2006. 49-60.

[12] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Spray and wait： an efficient routing scheme for intermittently connected mobile networks[A]. Proc of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking[C]. New York： ACM, 2005. 252-259.

[13] KER?NEN A, OTT J, K?RKK?INEN T. The One simulator for DTN protocol evaluation[A]. Proc of the ACM Int Conf on Simulation Tools and Techniques[C]. New York： ACM, 2009.1-10.

[14] LINDGRENY A, DORIA A, SCHELéN O. Probabilistic routing in intermittently connected networks[A]. ACM SIGMOBILE Mobile Computing and Communications Review[C]. New York： ACM, 2003.19-20.