姜海濤，張宏，李千目

(南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210094)

1 引言

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

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

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

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

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

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

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

3 車輛移動(dòng)模型相似度評(píng)價(jià)機(jī)制

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

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

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

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

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

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

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

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

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

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

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

圖1 移動(dòng)模型之間的相似度

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

4 MROFDM路由協(xié)議

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

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

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

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

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

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

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

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

4.2 副本均衡策略

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

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

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

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

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

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

節(jié)點(diǎn)使用遞推的方式計(jì)算redu

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

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

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

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

1) for(every msg in n1 cache){

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

3) msg.copies += calex();

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

4) }

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

//遇到目的節(jié)點(diǎn)完成數(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)計(jì)算移動(dòng)模型之間相似度

9) if(msg.copies ＞ 1){

10) msg1 = msg.clone();

11) dis(l1,l2);

//使用式(8)計(jì)算分發(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)計(jì)算目的地與移動(dòng)模型之間的距離

19) send msg to n2;

20) }

21) }

22) }

23) //n2 do the same process as n1

5 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

5.1 移動(dòng)模型的相似度

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

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

圖2 移動(dòng)模型相似度分布

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

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

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

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

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

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

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

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

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

圖7～圖9分別顯示了3種數(shù)據(jù)分組的傳輸成功率。圖7顯示與噴霧等待路由相比，本文提出的轉(zhuǎn)發(fā)策略可以提升bus數(shù)據(jù)分組的傳輸成功率，且MROFDM協(xié)議與MROFSM協(xié)議bus數(shù)據(jù)分組的傳輸成功率是一致，并沒有因?yàn)閯?dòng)態(tài)縮減副本數(shù)目而減少。圖8顯示car數(shù)據(jù)分組的傳輸成功率在本文轉(zhuǎn)發(fā)策略的幫助下，也有較為顯著的提升。圖9顯示MROFDM協(xié)議是唯一可以提升taxi數(shù)據(jù)分組傳輸成功率的協(xié)議，盡管效果并不是很明顯。實(shí)驗(yàn)過程中，每次動(dòng)態(tài)增加的副本數(shù)大約為1～2個(gè)，因此n個(gè)副本時(shí)MROFDM協(xié)議的taxi數(shù)據(jù)分組傳輸成功率與n+2個(gè)副本時(shí)噴霧等待協(xié)議的taxi數(shù)據(jù)分組傳輸成功率基本一致的。比較 3組實(shí)驗(yàn)結(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ù)分組的傳輸成功率

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

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

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

5.3 實(shí)時(shí)性及隨機(jī)誤差分析

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

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

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

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

圖12 每次實(shí)驗(yàn)的傳輸成功率

6 結(jié)束語

本文通過對(duì)車載網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)模型的分析，提出 MMSE評(píng)價(jià)移動(dòng)模型相似度?；诠?jié)點(diǎn)模型的相似度，從副本轉(zhuǎn)發(fā)與均衡 2個(gè)方面，設(shè)計(jì)了

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

[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] 王博，黃傳河，楊文忠. 時(shí)延容忍網(wǎng)絡(luò)中基于效用轉(zhuǎn)發(fā)的自適應(yīng)機(jī)會(huì)路由算法[J]. 通信學(xué)報(bào)，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] 李陟，查玄閱，劉鳳玉等. 公交時(shí)延容忍網(wǎng)絡(luò)中基于索引的多級(jí)分組路由算法[J]. 計(jì)算機(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] 徐佳，李千目，張宏等. 機(jī)會(huì)網(wǎng)絡(luò)中的自適應(yīng)噴霧路由及其性能評(píng)估[J]. 計(jì)算機(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.