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

陶樺，馮富琴，肖鵬，譚誠(chéng)偉，陶軍

?

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

陶樺1,2，馮富琴1,2，肖鵬1,2，譚誠(chéng)偉1,2，陶軍1,2

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

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

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

1 引言

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

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

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

2 研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 車輛的移動(dòng)模型

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

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

其中，wd[]表示第個(gè)時(shí)間段的矩陣平均值。

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

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

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

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

。

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

表4給出了26日、27日與wd的矩陣的相似度對(duì)比，將這2天對(duì)應(yīng)時(shí)間段的矩陣與wd進(jìn)行對(duì)比?？梢钥闯?，它們的矩陣相似度很高，平均相似度為0.98，最小相似度為0.96。同樣，表5也給出相應(yīng)相似度對(duì)比，其相似度也較高，說(shuō)明采用此方法對(duì)后續(xù)工作日的矩陣和矩陣進(jìn)行預(yù)測(cè)是可行的。

最后，本文使用同樣的方法對(duì)we、we進(jìn)行驗(yàn)證，選出6個(gè)周末，其中，4個(gè)數(shù)據(jù)用來(lái)計(jì)算we，其余2個(gè)日期（24日和25日）用來(lái)驗(yàn)證模型的準(zhǔn)確性。表6和表7為對(duì)比結(jié)果?？梢钥闯鰓e、we與這2個(gè)驗(yàn)證日期的矩陣相似度較高，使用這樣的方式對(duì)周末的矩陣和矩陣進(jìn)行預(yù)測(cè)是較為可信的。

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

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

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

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

1) 車輛到目標(biāo)區(qū)域的平均時(shí)間

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

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

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

車輛到達(dá)的概率可計(jì)算為

(=) =

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

=1?(0)=1?

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

t=(2)

4.2 RPT-D算法

由于本文將城市地圖劃分成100 m×100 m的單元格，車輛節(jié)點(diǎn)位于相應(yīng)的單元格內(nèi)，報(bào)文可以傳遞到源節(jié)點(diǎn)傳輸范圍內(nèi)的相關(guān)節(jié)點(diǎn)，其延遲為t，如式(2)所示。此時(shí)車載網(wǎng)中的路由問(wèn)題可以建模為在網(wǎng)絡(luò)拓?fù)渲袑ふ业侥康牡卮鷥r(jià)最小的路徑，本文通過(guò)Dijkstra算法來(lái)求解，并將算法記為RPT-D。

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

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

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

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

1) RPT-D算法分析

通過(guò)斐波那契堆和最小優(yōu)先級(jí)隊(duì)列優(yōu)化之后實(shí)現(xiàn)的Dijkstra算法時(shí)間復(fù)雜度是(||+||log||)，其中，||是拓?fù)渲羞叺臄?shù)量?？紤]到由矩陣抽象出的拓?fù)溥厰?shù)較小，使用矩陣來(lái)優(yōu)化拓?fù)涞倪厰?shù)。例如，拓?fù)溥叺臄?shù)量為=2 750 000時(shí)，優(yōu)化后的算法復(fù)雜度為(2 750 000+220 000)=(106)。根據(jù)當(dāng)前計(jì)算機(jī)的計(jì)算能力，RPT-D算法所需時(shí)間不超過(guò)0.01 s。

2) RPT-D算法的問(wèn)題

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

4.3 RPT-GA算法

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

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

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

Step 2 選擇操作。

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

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

所有路徑的時(shí)延之和記為sum，則

此時(shí)，路徑被排除的概率為

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

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

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

Step 4 執(zhí)行變異。

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

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

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

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

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

5.1 不同平均報(bào)文傳輸距離的傳輸性能

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

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

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

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

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

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

為了對(duì)比不同時(shí)段網(wǎng)絡(luò)拓?fù)鋵?duì)傳輸?shù)挠绊?，本文?duì)每一組和的12個(gè)不同網(wǎng)絡(luò)拓?fù)?，在?shù)據(jù)傳輸距離均為8 km的場(chǎng)景中，對(duì)相關(guān)傳輸性能進(jìn)行實(shí)驗(yàn)。

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

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

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

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

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

6 結(jié)束語(yǔ)

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

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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61272532, No.61370206, No.61370209）；教育部中國(guó)移動(dòng)聯(lián)合基金資助項(xiàng)目（No.MCM20150502）；江蘇省自然科學(xué)基金資助項(xiàng)目（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é)博士生，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)、網(wǎng)絡(luò)安全。

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

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

譚誠(chéng)偉（1989-），男，浙江嘉興人，東南大學(xué)碩士生，主要研究方向?yàn)闄C(jī)會(huì)社會(huì)網(wǎng)絡(luò)、無(wú)線傳感網(wǎng)絡(luò)。

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