基于運行軌跡特征分析的車輛自組織網(wǎng)路由算法

陶樺，馮富琴，肖鵬，譚誠偉，陶軍

?

基于運行軌跡特征分析的車輛自組織網(wǎng)路由算法

陶樺1,2，馮富琴1,2，肖鵬1,2，譚誠偉1,2，陶軍1,2

（1. 東南大學(xué)計算機科學(xué)與工程學(xué)院，江蘇南京 210096；2. 東南大學(xué)教育部計算機網(wǎng)絡(luò)和信息集成重點實驗室，江蘇南京210096）

首先基于車輛trace數(shù)據(jù)提取了粗粒度的車輛移動信息，在此基礎(chǔ)上，繼續(xù)研究了trace數(shù)據(jù)的細粒度的車輛移動模型；然后基于移動模型提出了車輛自組織網(wǎng)絡(luò)的路由算法（RPT-D），根據(jù)車輛移動特征將報文更快地傳輸?shù)侥康牡?；接著將對傳輸?shù)腝oS需求放入報文選路目標中，得到擴展性和選路結(jié)果更好的RPT-GA算法；最后通過仿真實驗，分別從傳輸時延、投遞成功率、跳數(shù)和輔助報文數(shù)量等4個性能參數(shù)角度，基于車輛trace數(shù)據(jù)將所提出的路由算法與經(jīng)典的車輛自組織網(wǎng)路由算法（IGRP和GPSR）進行比較，實驗結(jié)果驗證了所提算法的有效性。

車輛自組網(wǎng)；車輛trace；路由算法；傳輸時延；投遞成功率

1 引言

車輛自組織網(wǎng)簡稱車載網(wǎng)（VANET，vehicular ad hoc network），是一種特殊的移動自組織網(wǎng)絡(luò)，其利用車輛間的數(shù)據(jù)傳遞為駕乘人員提供交通行駛數(shù)據(jù)或娛樂信息的散播，對智能交通系統(tǒng)（ITS, intelligent transmutation system）的實施起到了有力的支撐。車載網(wǎng)在ITS系統(tǒng)中的應(yīng)用包括：交互式交通管制、實時路況分析、路線推薦、周邊信息服務(wù)和車禍預(yù)警等。這些應(yīng)用的開展都離不開車輛間數(shù)據(jù)傳輸方法的支持，高效的數(shù)據(jù)傳輸依賴于底層路由。

由于車輛相對高速的移動使車載網(wǎng)具有拓撲變化快、車輛（節(jié)點）的計算能力和緩存容量較高、車輛行駛在已知道路上、車輛的行駛信息和位置信息可知等特點。正是由于這些特點，傳統(tǒng)移動自組織網(wǎng)絡(luò)（MANET, mobile ad hoc network）的路由算法難以應(yīng)用于車載網(wǎng)?，F(xiàn)有的車輛自組織網(wǎng)路由在路由決策時，缺乏對車輛行駛和道路信息的全局了解，基于局部拓撲實施的優(yōu)化操作難以獲得最優(yōu)的效果。實驗表明，在車載網(wǎng)中使用傳統(tǒng)MANET路由，數(shù)據(jù)投遞率低，且傳輸時延和輔助報文數(shù)較大。另一方面，由于車輛能配備可充電裝置（如光伏或動能回收等設(shè)備），故車載網(wǎng)通常不考慮諸如MANET中的節(jié)點能量受限問題。因此，車載網(wǎng)應(yīng)用需要符合其網(wǎng)絡(luò)特點的路由算法的支持[1]。為解決車載網(wǎng)中的數(shù)據(jù)傳輸問題，向上層應(yīng)用提供支撐，車載網(wǎng)路由的研究吸引了學(xué)術(shù)界和工業(yè)界大量的關(guān)注。

為全面地了解車載網(wǎng)全局拓撲和車輛移動特性，以獲取較為全面的網(wǎng)絡(luò)信息，對現(xiàn)有車輛的行駛軌跡（trace）進行分析顯得尤為必要。目前，許多城市的出租車和公交車都已經(jīng)配備GPS，其生成的諸如車輛速度、方向、位置、狀態(tài)等的車輛軌跡信息（車輛trace數(shù)據(jù)），為車輛的運營和行駛提供了決策依據(jù)。同時出租車和公交車是城市公共交通的基礎(chǔ)，是構(gòu)成車載網(wǎng)的骨干節(jié)點，通過分析它們的軌跡信息，有助于勾勒車載網(wǎng)拓撲的全局信息，并將這些信息融入到車載網(wǎng)路由的制定中，克服現(xiàn)有路由的局限?，F(xiàn)有的許多研究開始重視車輛trace數(shù)據(jù)的研究和利用，但這方面的研究尚不夠全面，難以體現(xiàn)車載網(wǎng)的特有特征。為此，本文將挖掘車輛trace中更多的屬性，提煉天氣信息與車輛分布的關(guān)系、時段信息與車輛等待時間的關(guān)系、節(jié)假日拓撲、高峰期拓撲、載客和非載客狀態(tài)的行為等屬性，并將其融入到路由設(shè)計中。在此基礎(chǔ)上，根據(jù)車輛的trace數(shù)據(jù)對相關(guān)路由算法進行實際的軌跡測試和驗證，評估其效果。

2 研究現(xiàn)狀

2.1 車載自組織網(wǎng)路由算法

當(dāng)前，車載網(wǎng)路由算法可分為單播路由和廣播路由2類。在廣播路由算法的研究中，REAR 算法根據(jù)節(jié)點的接收概率選擇下一跳路由（節(jié)點）[1]。文獻[2]通過改進REAR算法中等待時間的計算方法，提出一種廣播路由算法RPR (receipt-based probabilistic routing)。相對于REAR算法，RPR算法在報文使用數(shù)量、數(shù)據(jù)傳輸時延和覆蓋率等方面都進行了優(yōu)化。SB（smart broadcast）[3]是一種基于位置的分布式廣播路由算法，SB中加入了RTB（request-to- broadcast）和CTB（clear-to-broadcast）報文，通過增加傳輸?shù)膱笪臄?shù)量和減少二次廣播時延，獲得更好的廣播效果。UMB（urban multi-hop broadcast）算法同樣使用了RTB和CTB來選擇廣播節(jié)點[4]。

依據(jù)路由測度的不同，車載網(wǎng)路由可分為：基于網(wǎng)絡(luò)連通性和基于地理位置等信息的方法。在基于網(wǎng)絡(luò)連通性的路由方面，文獻[5]改進了AODV（ad hoc on-demand distance vector routing），以適應(yīng)車載網(wǎng)拓撲變化快、鏈路不穩(wěn)定的特點，同時利用同向行駛車輛的移動保持連通時間，尋找更穩(wěn)定的鏈接。PAODV（prior AODV）在選擇下一跳節(jié)點時，過濾連接不穩(wěn)定的節(jié)點，解決了AODV中控制報文過多的問題[6]。文獻[7]將同方向、可一跳或多跳傳輸數(shù)據(jù)的車輛節(jié)點劃分為簇。通過分析現(xiàn)有高速公路數(shù)據(jù)，發(fā)現(xiàn)高速公路的車輛趨于成簇，將車載網(wǎng)車輛行駛建模為分簇模型，并簡化路由的復(fù)雜性。文獻[8]分析了簇內(nèi)最后一個成員的概率、簇成員間的平均距離、簇間的平均距離、簇內(nèi)平均成員數(shù)、簇的平均長度等簇特征，然后計算了車輛稀疏環(huán)境下車輛間的連通概率，并設(shè)計了相關(guān)的路由算法。文獻[9]和文獻[10]則分別使用分簇方法提出了適用于不同場景的路由算法。CAR（connectivity-aware routing）算法通過優(yōu)化之后的PGB算法找到目標車輛的位置，然后設(shè)置“錨點”記錄車輛的行駛軌跡，以提高投遞率[11]。在基于地理位置的路由方面，PBR（position-based routing）算法將基于位置的路由和多播技術(shù)相結(jié)合，以同時保障路由算法的頑健性和高效性[12]。文獻[13]在MOPR方法中增加了鄰居節(jié)點移動軌跡的預(yù)測，提出了MORA（movement-based routing algorithm），延長節(jié)點間的連通時間。GPSR算法把車載網(wǎng)抽象成一張地圖，每次轉(zhuǎn)發(fā)數(shù)據(jù)時都將其轉(zhuǎn)發(fā)給離終點最近的節(jié)點，如果無這樣的節(jié)點，則使用右手法則來拓展搜索的范圍[14]。由于GPSR是為廣義的無線移動網(wǎng)絡(luò)設(shè)計的貪婪轉(zhuǎn)發(fā)策略，并沒有考慮車載網(wǎng)的特性，因此文獻[15]和文獻[16]對GPSR在車載網(wǎng)中的應(yīng)用做了相應(yīng)的優(yōu)化。文獻[17]提出IGRP (intersection-based geographical routing protocol)算法，通過分析報文發(fā)送軌跡上的十字路口信息，評估報文投遞路線，基于每條路上的時延、跳數(shù)、CP（connectivity probability）和BER（bit error rate），結(jié)合QoS路由判據(jù)，計算相關(guān)路徑的參數(shù)，利用遺傳算法求解最優(yōu)路徑。此外，在本課題組前期的工作中，利用路邊單元（RSU）的放置來增加網(wǎng)絡(luò)拓撲的連通性，進而提高高速公路上車輛間數(shù)據(jù)散發(fā)的性能[18]。

2.2 車輛trace數(shù)據(jù)集

目前，記錄車輛軌跡的數(shù)據(jù)集主要包括：出租車trace數(shù)據(jù)和公交車trace數(shù)據(jù)。這2種車輛也正是車載自組織網(wǎng)絡(luò)中對車流量貢獻相對穩(wěn)定的，且最有可能進行軌跡預(yù)測的節(jié)點。由于公交車是按照固定線路行駛，相對出租車的trace記錄，各公交站點都可以成為公交車的網(wǎng)絡(luò)接入點，并提供一些輔助信息，因此其trace的記錄更加便捷，數(shù)據(jù)內(nèi)容也更豐富。當(dāng)前車載網(wǎng)中對于trace數(shù)據(jù)的研究主要體現(xiàn)在通過對車載網(wǎng)建模，為上層路由、數(shù)據(jù)傳播、移動模擬、交互模型和節(jié)點檢測等提供更為精確的網(wǎng)絡(luò)模型和節(jié)點移動模型[19~23]。

文獻[19]設(shè)計了一種區(qū)域劃分法的建模方法，首先通過計算VKT (vehicle kilometers traveled)和ART (accumulative residence time)等信息來識別熱點，即VKT和ART達到一定數(shù)量或排名比較靠前區(qū)域，將上海交通圖分為12個包含熱點區(qū)域，計算車輛在相鄰區(qū)間的轉(zhuǎn)移概率和在某一區(qū)域的等待時間。車輛一旦進入某一區(qū)域，會有2個選擇：1）在該區(qū)域逗留一段時間；2）離開去下一區(qū)域。依據(jù)這些移動屬性來預(yù)測車輛的運行軌跡。

有些路由選擇算法讓車輛按照概率在多個可能的方向中選取移動方向，且賦予各方向不同概率的計算方法[20,21]。這些方法需要以城市地圖作為輸入?yún)?shù)，將地圖抽象為數(shù)據(jù)結(jié)構(gòu)存儲起來，并以此提取可能的路徑，計算各個路徑的使用概率。通常源和目的節(jié)點間的最短路徑就是車輛理性行駛而選擇的路徑。這樣車輛的行駛被抽象為：從一個點移動到另一個，停留平均等待時間后，移動到下一個，重復(fù)這樣的運動。本文在前期的工作中，利用對trace數(shù)據(jù)的分析，探索基于位置的數(shù)據(jù)轉(zhuǎn)發(fā)機制，并將車輛的trace數(shù)據(jù)應(yīng)用于方案的測試和分析中[24]。

本文通過對車輛trace的分析，提取相關(guān)的軌跡特征，并基于這些特征設(shè)計相應(yīng)的車載網(wǎng)路由算法，以提高其性能。

3 基于trace數(shù)據(jù)的車輛移動模型

3.1 單位面積車輛出現(xiàn)次數(shù)

本文使用的車輛trace數(shù)據(jù)是基于上海超過4 000輛出租車移動產(chǎn)生的GPS信息，記錄時間為2007年1月~2月，數(shù)據(jù)內(nèi)容包括：車輛的經(jīng)度、緯度、速度、方向、時間戳、是否載客等信息，車輛信息采集周期不固定（在30 ~61 s）。此外，還將上海市地圖用100 m×100 m的正方形方格進行劃分和編號，用和分別表示劃分網(wǎng)格中的橫向編號和縱向編號，并基于trace數(shù)據(jù)統(tǒng)計每個方格在指定的時間內(nèi)車輛出現(xiàn)的累計次數(shù)UAVAT（unit area vehicle appearing time），整個網(wǎng)絡(luò)的UAVAT值按照行列形成的矩陣則稱為矩陣。

定義1 （相似度）已知1,2,3,…,為個矩陣，則(1,2,3,…,U)為這個矩陣的相似度

(1,2,3,…,)=(1)

由定義1可知，(1,2,3,…,)反映了1,2,3,…,間相似關(guān)系，顯然(1,2,3,…,)越接近于1，矩陣間的差異越小，反之差異越大。

首先，比較了不同時間段的矩陣結(jié)果，通過式（1），可計算出矩陣間的相似度。表1為上海31天內(nèi)各個時間段的矩陣相似度。由表1可知，每個時間段與相鄰時間段的相似度都較高，而與其他時間段的相似度則降低。可以看出，城市的矩陣隨著時間不斷變化，不能單純以天為單位來研究相關(guān)車輛的屬性，因此，進一步將一天劃分為12個時間段，計算各時間段的矩陣，來描述車載網(wǎng)拓撲的時間變化。

在此基礎(chǔ)上，以天為單位，計算了一周內(nèi)相同間段的矩陣，由表2可見，城市中出租車的行駛狀態(tài)不僅與時間段相關(guān)，還與日期的特殊性有關(guān)：周一到周五的矩陣相似度較大；而周末（周六與周日）較為相似，但彼此間矩陣的相似度較小。

表1 同一天不同時間段的UAVAT矩陣相似度

表2 不同日期相同時間段的UAVAT矩陣比較

3.2 單位面積內(nèi)車輛停留時間

單位面積內(nèi)車輛停留時間UAVRT（unit area vehicle residence time），在文獻[16]中首次被提出，作為判斷某個單位區(qū)域熱度的依據(jù)。本文也將采用該尺度來衡量各單元格的相關(guān)屬性，UAVRT的計算方法與UAVAT基本相似，只需將車輛停留次數(shù)替換為車輛停留時間。

首先將一天分為12個時間段，計算每個時間段的矩陣以及彼此之間的相似度。與相同，時間段不同的矩陣之間的相似度比較低，因此與矩陣的計算一樣，為了減少實驗值的誤差，這里不使用統(tǒng)一的矩陣來表示所有的情況。

表3為一周時間內(nèi)相同時間段的矩陣的比較，可以看出5個工作日期間車輛的行駛狀態(tài)比較接近，周末2天車輛的行駛狀態(tài)比較接近，但是彼此間的狀態(tài)差距較大。

表3 不同日期相同時間段的UAVRT矩陣比較

3.3 車輛的移動模型

通過上文的分析，證明城市的和矩陣不僅與時間段相關(guān)，而且與周末及工作日相關(guān)。如果把所有時間下的車輛軌跡數(shù)據(jù)都抽象為一個矩陣和矩陣是不合理的，不能夠正確反映車載網(wǎng)的拓撲和車輛的密度。因此，將歷史trace數(shù)據(jù)分為2種場景：工作日和周末。同時，將所有的歷史trace數(shù)據(jù)分為12個時間段，00:00:00 ~ 01:59:59、02:00:00~03:59:59，…，22:00:00 ~ 23:59:59。然后，為每個時間段計算矩陣和矩陣，求出各個時段矩陣和矩陣的平均值，這些平均值可以作為車輛的移動模型計算的依據(jù)。

定義2wd為工作日的矩陣平均值數(shù)組

其中，wd[]表示第個時間段的矩陣平均值。

定義3wd為工作日的矩陣平均值數(shù)組

其中，wd[]為時間段的矩陣平均值。

定義4we為周末的矩陣平均值數(shù)組

定義5we為周末的矩陣平均值數(shù)組

。

本文使用四元組wd,wd,we,we表示車流量模型。下面對本文提出的模型wd、wd進行驗證，從已有的trace中選出12個工作日，其中，10個工作日用來計算wd、wd，另外2天（1月26日和27日）用來驗證計算出來的wd和wd參數(shù)的準確性。

表4給出了26日、27日與wd的矩陣的相似度對比，將這2天對應(yīng)時間段的矩陣與wd進行對比?？梢钥闯觯鼈兊木仃囅嗨贫群芨?，平均相似度為0.98，最小相似度為0.96。同樣，表5也給出相應(yīng)相似度對比，其相似度也較高，說明采用此方法對后續(xù)工作日的矩陣和矩陣進行預(yù)測是可行的。

最后，本文使用同樣的方法對we、we進行驗證，選出6個周末，其中，4個數(shù)據(jù)用來計算we，其余2個日期（24日和25日）用來驗證模型的準確性。表6和表7為對比結(jié)果。可以看出we、we與這2個驗證日期的矩陣相似度較高，使用這樣的方式對周末的矩陣和矩陣進行預(yù)測是較為可信的。

4 基于trace的車載網(wǎng)路由的研究

下面，本文將提出一種基于trace的路由協(xié)議（RPT, routing protocol based on trace data），RPT算法是屬于基于地理位置信息的路由算法，以車輛trace得到其移動模型，通過遺傳算法（genetic algorithm）和Dijkstra算法計算最優(yōu)路徑。

4.1 數(shù)據(jù)傳輸時間

數(shù)據(jù)的傳輸有2種方式：1）車輛周圍沒有適合的節(jié)點，車輛攜帶數(shù)據(jù)分組；2）車輛將數(shù)據(jù)通過無線方式傳遞給下一跳。第2種方式所需的傳輸時間可忽略不計。假設(shè)車輛通過當(dāng)前單元格到達目標區(qū)域（單元格）的平均時間為，目標區(qū)域內(nèi)有節(jié)點的概率為，則數(shù)據(jù)通過單元格的平均傳輸時間=(1?)。

1) 車輛到目標區(qū)域的平均時間

由車輛trace可知車輛各時間段內(nèi)在單元格的平均速度。假設(shè)車輛到達目標區(qū)域需要經(jīng)過個單元格，那么可得車輛在其中行駛的距離s，結(jié)合各單元格對應(yīng)的平均速度v，可求得到達目標區(qū)域的平均時間為。

2) 單元格內(nèi)存在車輛節(jié)點的概率

每個單元格在過去的時間段內(nèi)通過車輛節(jié)點的數(shù)量為we[][,]或者wd[][,]，其中，和表示劃分網(wǎng)格中的橫向編號和縱向編號，文獻[16]和文獻[25]證明了車輛節(jié)點到達符合泊松分布，那么單元格每間隔的到達強度為

車輛到達的概率可計算為

(=) =

這樣，單元格內(nèi)存在節(jié)點的概率為

=1?(0)=1?

根據(jù)車輛通過單元格的平均時間travel和單元格內(nèi)有一個或多個車輛節(jié)點的概率，數(shù)據(jù)分組通過單元格的平均時間t

t=(2)

4.2 RPT-D算法

由于本文將城市地圖劃分成100 m×100 m的單元格，車輛節(jié)點位于相應(yīng)的單元格內(nèi)，報文可以傳遞到源節(jié)點傳輸范圍內(nèi)的相關(guān)節(jié)點，其延遲為t，如式(2)所示。此時車載網(wǎng)中的路由問題可以建模為在網(wǎng)絡(luò)拓撲中尋找到目的地代價最小的路徑，本文通過Dijkstra算法來求解，并將算法記為RPT-D。

1) RPT-D算法分析

通過斐波那契堆和最小優(yōu)先級隊列優(yōu)化之后實現(xiàn)的Dijkstra算法時間復(fù)雜度是(||+||log||)，其中，||是拓撲中邊的數(shù)量。考慮到由矩陣抽象出的拓撲邊數(shù)較小，使用矩陣來優(yōu)化拓撲的邊數(shù)。例如，拓撲邊的數(shù)量為=2 750 000時，優(yōu)化后的算法復(fù)雜度為(2 750 000+220 000)=(106)。根據(jù)當(dāng)前計算機的計算能力，RPT-D算法所需時間不超過0.01 s。

2) RPT-D算法的問題

使用RPT-D算法得到路徑的時延是最短的，但是如果需要路由考慮其他限制條件，如跳數(shù)、誤碼率等參數(shù)時，RPT-D算法往往難以同時滿足多個優(yōu)化條件。

4.3 RPT-GA算法

為了進行多目標優(yōu)化，本文采用遺傳算法進行具有多個優(yōu)化目標參數(shù)的最優(yōu)路徑的求解。這里，增加一個路由判據(jù)：跳數(shù)，故現(xiàn)在路由判據(jù)為源與目的節(jié)點間的時延和跳數(shù)。本文將求解算法記為RPT-GA(routing protocol based on trace using genetic algorithm)，RPT-GA算法通過如下步驟完成。

Step 1 確定編碼方式和初始化族群。

路徑使用一系列二元組表示，單個二元組標明了相關(guān)矩陣中位置，因此，一系列二元組便標記出從源到目的的路徑，然后使用廣度優(yōu)先的方法來初始化族群，族群的初始化大小為。

Step 2 選擇操作。

假設(shè)路徑的編號為1, 2, 3, …,，則每條路徑的跳數(shù)記為HC，車輛能夠通過多跳的方式將報文傳輸出去的條件是該車輛下一跳區(qū)域內(nèi)存在車輛，依據(jù)單元格內(nèi)存在節(jié)點的概率，則

首先，依據(jù)HC對路徑進行篩選，將族群中所有值大于th的路徑全部篩除。這樣剩下的路徑都是滿足小于th的路徑。其中，th為假定閾值，所有路徑須滿足跳數(shù)小于th。然后，將路徑時延記為D，則

所有路徑的時延之和記為sum，則

此時，路徑被排除的概率為

因此，時延大的路徑被排除的可能性就越大，循環(huán)此操作，直到群組數(shù)量為。

Step 3 基于概率的交叉優(yōu)化。

接下來，將從路徑族群中任選2條路徑，依據(jù)概率cross進行交叉操作，即從2條路徑中提取公共節(jié)點，然后將2條路徑上位于公共節(jié)點后的部分交換。如存在多個公共節(jié)點，則隨機選擇一個作為路徑交換的起始點。通過路徑交叉的方式得到更多的路徑，并增加路徑優(yōu)化的可能性，從而優(yōu)化最終的族群。

Step 4 執(zhí)行變異。

與Step3相似，進行變異操作基于概率mutation進行。與Step 3不同的是變異的對象為一條路徑。具體的操作方式有2種：1) 在傳輸范圍內(nèi)將2跳傳輸合并為一跳；2) 將一跳傳輸隨機地拆分為2跳。這2種變異方式按照50%的概率進行，即如果選擇對一條路徑進行變異，則變異的時候以50%的概率按照方式1變異，50%的概率按照方式2變異，這2種變異操作在實際中都有意義。由于有可能路徑上的節(jié)點很多，因此路徑微小的改變便可能影響整體的優(yōu)化結(jié)果。

與RPT-D算法相比，RPT-GA算法的結(jié)果可能不是時延最短的，但所得路徑的累積跳數(shù)卻能滿足相應(yīng)的要求和約定，使算法能夠兼顧兩方面的優(yōu)化效果。同時，RPT-GA算法還表現(xiàn)出較強的擴展性。例如，可以考慮除本文提到的跳數(shù)和時延以外的約束條件，可加入相應(yīng)的QoS約束條件（誤碼率、連通概率等）。

表4 Awd與1月26日和27日UAVAT矩陣相似度

表5 Rwd與1月26日和27日UAVRT矩陣相似度

表6 Awe與1月24日和25日UAVAT矩陣相似度

表7 Rwe與1月24日和25日UAVRT矩陣相似度

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

下面采用NS-2工具對RPT-D算法和RPT-GA算法進行仿真實驗。為了更好地評估2種算法的性能，還對經(jīng)典的基于位置的路由算法GPSR算法和IGRP算法進行實現(xiàn)，在傳輸時延、跳數(shù)、輔助報文數(shù)量等性能指標上對它們進行橫向?qū)Ρ群头治觥?/p>

首先根據(jù)在上海市范圍內(nèi)車輛trace的數(shù)據(jù)對不同時間段拓撲變化進行模擬，使用不同時間段的矩陣，網(wǎng)絡(luò)節(jié)點數(shù)根據(jù)模擬時間段trace數(shù)據(jù)中的車輛數(shù)而確定（總數(shù)量約4 000左右）。仿真中，默認車輛節(jié)點的傳輸半徑是250 m。車輛的移動軌跡將按照trace數(shù)據(jù)生成，各車輛節(jié)點根據(jù)其trace數(shù)據(jù)行駛。對網(wǎng)絡(luò)拓撲進行多組實驗，每組實驗的數(shù)據(jù)傳輸距離，即報文發(fā)送位置（源節(jié)點）與接收端（目的地）間的距離在[0，25 000]m隨機變化，且每個傳輸將要傳輸報文100個，仿真持續(xù)時間為300 s。

5.1 不同平均報文傳輸距離的傳輸性能

為排除其他因素的干擾，在對比報文不同的平均傳輸距離對傳輸性能的影響時，本文使用了相同時間段的trace進行分析，所涉及的trace數(shù)據(jù)為2007-01-26 08:00:00 ~ 2007-01-30 08:05:00時間段。

在圖1中，傳輸時延隨著傳輸距離的增大而增大，顯然報文的傳輸距離越長，需要的時間也就越多。由圖1可見，RPT-D算法的時延是最小的。由于RPT-D是全局優(yōu)化的路由選擇，因此，時延是唯一的選擇判據(jù)；IGRP算法則能夠?qū)SU覆蓋范圍內(nèi)的節(jié)點路由進行局部優(yōu)化，因此，IGRP所獲得的傳輸時延較RPT-D略高；RPT-GA則使用遺傳算法對路徑依據(jù)時延和跳數(shù)2個參數(shù)進行優(yōu)化，因此，時延不再是唯一的考慮，還需要兼顧跳數(shù)的優(yōu)化，使算法的執(zhí)行力最高，但RPT-GA算法的時延卻相對較高。

在圖2中，分析了距離對跳數(shù)的影響，顯然跳數(shù)會隨傳輸距離的增加而增大，且跳數(shù)與時延呈反比的趨勢。RPT-GA算法所獲得的平均跳數(shù)最小，因為在RPT-GA算法中，跳數(shù)作為優(yōu)化目標之一對遺傳算法的相關(guān)路徑進行篩選，將刪除跳數(shù)大的路徑，保證了路徑的最大跳數(shù)值。GPSR算法跳數(shù)較小的原因在于其貪婪地選擇距離目的地最近的節(jié)點加入路徑，此時，雖然路徑的跳數(shù)較少，但有可能將報文傳遞到節(jié)點較少的區(qū)域，此時將只能靠路過的車輛自己攜帶報文投遞，傳輸延遲可能會倍增。RPT-D算法和IGRP算法跳數(shù)較大的原因在于它們會為了尋找時延更短路徑，放棄跳數(shù)更少的路徑。

在圖3中，RPT-D和RPT-GA算法使用的輔助報文數(shù)較少，究其原因是這2種算法都對節(jié)點的輔助報文數(shù)量進行了限制。IGRP算法使用的輔助報文數(shù)量較之其他算法高了很多，原因是IGRP算法常需要RSU的輔助，因此，車輛需將其數(shù)據(jù)中繼到RSU，再由RSU進行傳遞。

由圖4可知，報文投遞率與傳輸時延的走勢相似，這是由于時延較小的方法選取的路徑往往跳數(shù)較大，即連通度較好的網(wǎng)絡(luò)中的路徑，這類路徑經(jīng)過的區(qū)域往往車輛相對密集，報文能較快地傳向目的地。此時，不會造成報文長期滯留在某個車輛節(jié)點，又因難以找到合適的下一跳，造成報文超時或緩沖區(qū)的溢出而丟棄。因此，RPT-D算法和IGRP算法的報文投遞率較高，其他算法的投遞率較低。

5.2 不同時段網(wǎng)絡(luò)的傳輸效果

為了對比不同時段網(wǎng)絡(luò)拓撲對傳輸?shù)挠绊懀疚膶γ恳唤M和的12個不同網(wǎng)絡(luò)拓撲，在數(shù)據(jù)傳輸距離均為8 km的場景中，對相關(guān)傳輸性能進行實驗。

圖5呈現(xiàn)的是4種路由算法在不同拓撲中網(wǎng)絡(luò)時延的表現(xiàn)，軸為trace中的相關(guān)時間段，如軸的5表示04:00:00~05:00:00時間段的傳輸時延。結(jié)果表明在早晚高峰時段，由于車輛密集、車速緩慢，報文不需借助Carry-and-Forward的方式傳輸，大部分可以通過車輛間多跳傳輸完成，故路由算法的傳輸時延均有所降低。

從圖6中可看到，在早晚高峰時段，由于車輛數(shù)和車輛密度增加，多跳傳輸成為優(yōu)選，相應(yīng)的傳輸跳數(shù)不斷增加。RPT-D算法和IGRP算法則能有更多優(yōu)化的多跳傳輸路徑可供選擇，在縮短傳輸延遲的同時，增加了一些傳輸跳數(shù)。由于RPT-GA算法和GPSR算法更注重將報文及時地送到離目的地更近的節(jié)點，因此，車輛數(shù)和密度的增加對于這2種算法影響不大，選擇的路徑會更接近源節(jié)點和目的地位置間的最小跳數(shù)。另一方面，這2種算法在車輛密度較大的道路上會優(yōu)先使用多跳的傳輸，因此，在車輛密度和數(shù)量增大時，這2種算法所需跳數(shù)會相應(yīng)的增加。

如圖7所示，4種路由算法中只有IGRP算法需要借助RSU進行通信，因此，IGRP算法使用的輔助報文數(shù)會隨著車輛的增多而上升；其他路由算法由于不需轉(zhuǎn)發(fā)輔助報文，因此，輔助報文數(shù)與網(wǎng)絡(luò)拓撲的其他節(jié)點關(guān)聯(lián)較少。正如前面的分析，RPT-D和RPT-GA算法與車輛行駛速度相關(guān)，在車流高峰期，車速較慢，車輛需要的輔助報文數(shù)較少；而車輛密度和數(shù)量的增加，使車輛間交互的HelloBeacon報文數(shù)也相應(yīng)地上升，因此，RPT-D和RPT-GA算法使用輔助報文數(shù)在高峰期和非高峰期差別不大。

如圖8所示，相關(guān)路由算法的投遞率與其時延的走勢相吻合。在車輛高峰期，4個算法的投遞率都很高，同樣的原因：車輛密度增大，車速降低，使報文的傳遞更快速穩(wěn)定。

由于本實驗中所使用的車輛trace數(shù)據(jù)均來自于實際環(huán)境中的車輛行駛軌跡，因此，在使用NS-2模擬時，車輛的方向、速度及行駛模式都能夠再現(xiàn)真實的車載網(wǎng)環(huán)境，實驗結(jié)果能夠驗證本文的相關(guān)路由算法的性能和可用性。

6 結(jié)束語

本文通過分析車輛的trace數(shù)據(jù)，將車載網(wǎng)的拓撲與實際車流量聯(lián)系起來，分析了不同時段（工作日、雙休日以及節(jié)假日）的車載網(wǎng)拓撲情況，進而更準確地預(yù)測未來的網(wǎng)絡(luò)拓撲，為路由的設(shè)計提供支持。在此基礎(chǔ)上，本文提出了2種基于車輛trace模型的路由算法：RPT-D算法使用經(jīng)典的Dijkstra算法計算下一跳節(jié)點，將2個區(qū)間的距離轉(zhuǎn)化為報文通過這2個區(qū)間的預(yù)計時間，在計算傳輸時延時不僅考慮車輛在不同單元格內(nèi)的速度，也兼顧了下一跳單元格內(nèi)車輛存在的概率，以更精確地估算時間；而RPT-GA則在RPT-D基礎(chǔ)上，增加了新的路由判據(jù)。

最后，通過仿真實驗評估了RPT-D和RPT-GA算法的有效性，與經(jīng)典的路由算法IGRP和GPSR進行橫向比較。仿真實驗結(jié)果表明，RPT-D和RPT-GA算法在傳輸時延、跳數(shù)、投遞成功率和輔助報文數(shù)等方面均有較好的表現(xiàn)，驗證了其有效性和可靠性。

[1] JIANG H, GUO H, CHEN L. Reliable and efficient alarm message routing in VANET[C]// 28th International Conference on Distributed Computing Systems Workshops, ICDCS'08. c2008: 186-191.

[2] TAO J, XIAO P, LIU Y, et al. A routing algorithm based on the probability of topology connectivity in vehicluar ad-hoc networks[J]. Journal of Southeast University, 2013,(3): 1-4.

[3] FASOLO E, ZANELLA A, ZORZI M. An effective broadcast scheme for alert message propagation in vehicular ad hoc networks[C]// IEEE International Conference on ICC'06. c2006: 3960-3965.

[4] KORKMAZ G, EKICI E, ?ZGüNER F, et al. Urban multi-hop broadcast protocol for inter-vehicle communication systems[C]// Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks. ACM, c2004: 76-85.

[5] DING B, CHEN Z, WANG Y, et al. An improved AODV routing protocol for VANET[C]// 2011 International Conference on Wireless Communications and Signal Processing (WCSP). c2011: 1-5.

[6] ABEDI O, BERANGI R, AZGOMI M A. Improving route stability and overhead on AODV routing protocol and make it usable for VANET[C]// 29th IEEE International Conference on Distributed Computing Systems Workshops, ICDCS Workshops' 09. c2009: 464-467.

[7] ABEDI O, FATHY M, TAGHILOO J. Enhancing AODV routing protocol using mobility parameters in VANET[C]// IEEE/ACS International Conference on Computer Systems and Applications. c2008: 229-235.

[8] WISITPONGPHAN N, BAI F, MUDALIGE P, et al. Routing in sparse vehicular ad hoc wireless networks[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(8): 1538-1556.

[9] BLUM J, ESKANDARIAN A, HOFFMAN L. Mobility management in IVC networks[C]// Proceedings IEEE Intelligent Vehicles Symposium. c2003: 150-155.

[10] JAAP S, BECHLER M, WOLF L. Evaluation of routing protocols for vehicular ad hoc networks in typical road traffic scenarios[C]//11th EUNICE Open European Summer School on Networked Applications, c2005: 584-602.

[11] NAUMOV V, GROSS T R. Connectivity-aware routing (CAR) in vehicular ad-hoc networks[C]//INFOCOM 26th IEEE International Conference on Computer Communications, c2007: 1919-1927.

[12] HARSCH C, FESTAG A, PAPADIMITRATOS P. Secure position-based routing for VANET[C]// IEEE 66th Vehicular Technology Conference. c2007: 26-30.

[13] MENOUAR M, LENARDI M, FILALI F. A movement prediction based routing protocol for vehicle-to-vehicle communications[J]. Communications, 2005, 21: 07-2005.

[14] KARP B, KUNG H T. GPSR: Greedy perimeter stateless routing for wireless networks[C]//The 6th Annual International Conference on Mobile Computing and Networking. ACM, c2000: 243-254.

[15] LI F, WANG Y. Routing in vehicular ad hoc networks: a survey[J]. IEEE Vehicular Technology Magazine, 2007, 2(2): 12-22.

[16] RAO S A, PAI M C, BOUSSEDJRA M, et al. GPSR-L: Greedy perimeter stateless routing with lifetime for VANETS[C]//8th International Conference on ITS Telecommunications, c2008: 299-304.

[17] SALEET H, LANGAR R, NAIK K, et al. Intersection-based geographical routing protocol for VANETs: a proposal and analysis[J]. IEEE Transactions on Vehicular Technology, 2011, 60(9): 4560-4574.

[18] TAO J, ZHU L, WANG X, et al. RSU deployment scheme with power control for highway message propagation in VANETs[C]. IEEE Global Communications Conference (GLOBECOM). c2014: 169-174.

[19] LI X, PAN G, WU Z, et al. Prediction of urban human mobility using large-scale taxi traces and its applications[J]. Frontiers of Computer Science, 2012, 6(1): 111-121.

[20] KIM M, KOTZ D, KIM S. Extracting a mobility model from real user traces[C]//INFOCOM. c2006: 1-13.

[21] ZHANG X, KUROSE J, LEVINE B N, et al. Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing[C]//The 13th Annual ACM International Conference on Mobile Computing and Networking. ACM, c2007: 195-206.

[22] YOON J, NOBLE B D, LIU M, et al. Building realistic mobility models from coarse-grained traces[C]//The 4th International Conference on Mobile Systems, Applications and Services. ACM, c2006: 177-190.

[23] ZHANG L, YU B, PAN J. GeoMob: a mobility-aware geocast scheme in metropolitans via taxicabs and buses[C]//IEEE INFOCOM, c2014: 1279-1787.

[24] TAO J, XU Y, TAN C, et al. Location-aware opportunistic forwarding in mobile opportunistic networks[C]// IEEE Wireless Communications and Networking Conference (WCNC). c2015: 1847-1852.

[25] PARK J S, LEE U, OH S Y, et al. Emergency related video streaming in VANET using network coding[C]//The 3rd International Workshop on Vehicular Ad Hoc Networks. ACM, c2006: 102-103.

Routing algorithm based on characteristics analysis of vehicle trace in vehicular ad hoc network

TAO Hua1,2, FENG Fu-qin1,2, XIAO Peng1,2, TAN Cheng-wei1,2,TAO Jun1,2

(1. School of Computer Science and Engineering, Southeast University, Nanjing 210096, China; 2. Key Laboratory of Computer Network and Information Integration, MOE, Southeast University, Nanjing 210096, China)

The coarse granularity vehicle mobility information is extracted from the vehicle trace data. Then a fine granularity mobility model was presented based on the coarse-grained mobility information. Based on the mobility model, a VANET routing algorithm, RPT-D, was proposed to quickly deliver the packets to the destination according to the mobility attributes. The RPT-GA algorithm, which was integrated with the QoS demands in the path selection objective, was designed. Finally, through the extensive simulations, the proposed algorithms are compared with other typical VANET routing algorithms, IGRP and GPSR, in terms of the transmission latency, the delivery ratio, the hop count and the extra package number. The simulation results verify the performance of the proposed algorithms.

vehicular ad hoc network, vehicle trace, routing algorithm, transmission latency, delivery ratio

TP393

A

10.11959/j.issn.1000-436x.2016124

2015-10-26；

2016-03-10

陶軍，juntao@seu.edu.cn

國家自然科學(xué)基金資助項目（No.61272532,No.61370206, No.61370209）；教育部中國移動聯(lián)合基金資助項目（No.MCM20150502）；江蘇省自然科學(xué)基金資助項目（No.BK20151416）

The National Natural Science Foundation of China (No.61272532, No.61370206, No.61370209), The MOE-CMCC Joint Foundation (No.MCM20150502), The Natural Science Foundation of Jiangsu Province (No.BK20151416)

陶樺（1976-），男，江蘇吳江人，東南大學(xué)博士生，主要研究方向為計算機網(wǎng)絡(luò)技術(shù)、網(wǎng)絡(luò)安全。

馮富琴（1992-），女，江蘇鹽城人，東南大學(xué)碩士生，主要研究方向為延遲容忍網(wǎng)絡(luò)中的緩存管理及路由策略。

肖鵬（1988-），男，江蘇海門人，東南大學(xué)碩士生，主要研究方向為車輛自組織網(wǎng)絡(luò)中的路由。

譚誠偉（1989-），男，浙江嘉興人，東南大學(xué)碩士生，主要研究方向為機會社會網(wǎng)絡(luò)、無線傳感網(wǎng)絡(luò)。

陶軍（1975-），男，江蘇南京人，東南大學(xué)副教授、博士生導(dǎo)師，主要研究方向為無線網(wǎng)絡(luò)、高性能網(wǎng)絡(luò)、信息經(jīng)濟學(xué)及分布式計算與系統(tǒng)。