面向車載自組織網絡路由的軌跡預測算法

黎 陽 王 哲 張楚文 戴惠辰 徐文佺 姬雪楓 萬 穎 劉 斌

(清華大學計算機科學與技術系 北京 100084)

(liyang-12@mails.tsinghua.edu.cn)

面向車載自組織網絡路由的軌跡預測算法

黎 陽 王 哲 張楚文 戴惠辰 徐文佺 姬雪楓 萬 穎 劉 斌

(清華大學計算機科學與技術系 北京 100084)

(liyang-12@mails.tsinghua.edu.cn)

在車載自組織網絡(vehicular ad hoc network, VANET)(也稱車聯網)中，基于地理位置的路由協議能夠較好地適應網絡拓撲的動態性變化和鏈路質量的不穩定性.由于位置信息需要在鄰居節點間采用信標分組進行交互，信標分組間隔內的轉發決策可能因車輛節點位置的移動而不準確，需要進行位置預測來修正車輛節點的位置.已有的位置預測算法存在普適性差或預測誤差大的問題.針對上述問題，提出了一種新的預測算法，首次通過測量得到車輛加速度服從正態分布的結論，利用線性回歸進行預測，并采用反饋機制進行結果修正.利用真實車輛軌跡進行測試，新的預測算法的預測精度大為提高.然后，提出了一種新的基于位置的即時路由協議.在該協議中，發送節點利用鄰居節點位置和目的節點位置計算出轉發下一跳.將新的位置預測算法加入到即時路由協議中，實時預測和更新車輛的位置.利用SUMO軟件生成了基于真實地圖道路軌跡的車輛運動模型，結合NS3網絡仿真平臺進行了仿真實驗.實驗結果表明：采用新的預測算法后，相比傳統的GPSR協議和不帶預測的即時路由協議，新方法的收包率提高、延遲下降，并且協議開銷顯著降低.

車載自組織網絡；即時路由；軌跡預測；地理位置路由協議；命名數據網絡

隨著智能汽車系統和自動駕駛技術的興起，車載自組織網絡(vehicular ad hoc network, VANET)(也稱車聯網)其V2X(vehicle to everything)技術迎來了巨大的發展機遇.而在基礎設施(LTE-V-Cell或802.11p路邊單元)無法接入的情況下，VANET是一種重要的通信方式[1-3].但是，由于網絡拓撲的動態性變化和鏈接質量的不穩定性，車載自組織網絡在維持端到端通信過程中面臨極大的挑戰.由于全球定位系統正成為車輛的一個必備裝置，實現基于位置的車載自組織網絡路由協議成為可能[4-6].基于位置的路由協議需要通過鄰居和目的節點的位置信息來進行路由決策.而獲取鄰居位置需要鄰居節點間定時交互信標分組(beacon packet).為了降低開銷和提高路由協議的準確性，如何選取信標分組的發送間隔成為一個重要問題.

在基于位置的VANET路由算法中，如經典的路由算法GPSR[4]，在源節點發出一個分組之后，每經過一跳都要根據當前節點掌握的鄰居節點位置和目的節點位置選取下一跳轉發節點.由于信標分組有一定的發送間隔(如1s)，當前路由決策節點掌握的其他節點位置信息并不是最新的.但是在某個數據分組的傳輸時間內，在一般的城市道路模型中，車輛的拓撲變化相對較為緩慢.基于這個基本觀察，之前的研究提出了基于預測進行路由的思想，即在信標分組間隔之內，使用預測的位置信息[7-10]作為節點路由選擇的依據.

但是，之前基于位置預測的研究文章[7-10]對于車輛行駛狀況的抽象較為理想化，并且很多算法需要借助電子地圖進行輔助判斷，普適性較差.本文提出了一種新的車輛位置預測算法，對車輛行駛軌跡進行了重新建模，發現車輛加速度服從正態分布的特性，降低了預測開銷，并利用真實車輛運行數據進行測量實驗，得到了新型的路由協議中的位置預測算法.為了驗證新的位置預測算法的有效性，設計了一種新型的即時路由協議(instant routing, IR)進行驗證.

本文的主要貢獻有3個方面:

1) 實驗發現，車輛行駛過程中加速度更加服從正態分布的特征，提出了一種新的車輛位置預測算法，從理論上分析了預測算法的正確性；

2) 利用真實車輛行駛軌跡數據驗證了新的車輛位置預測算法的有效性；

3) 設計了一種新型的基于位置信息的即時路由協議IR，并且利用NS3和SUMO工具驗證了新的車輛位置預測算法對路由協議性能提升的效果.

1 相關工作

目前，研究者提出了兩大類基于位置預測的算法：1)對2個節點的可通信時長進行預測，經典算法有文獻[7-9]；2)直接對節點的行駛軌跡進行預測[10].

據我們所知，Menouar等人[7]最早提出基于位置預測的算法.作者將2個車輛節點的可通信時間記為Lifetimelink，利用節點速度vi，vj和節點間的距離di,j進行預測.另外，作者考慮到車道之間的距離可能相當大，因此也需要考慮車道之間的距離ω.若設無線通信半徑為R，則有預測模型：

(1)

其中，s的取值與2個車輛節點的相對行駛方向有關.若兩輛車相向行駛，則s=1，否則s=-1.上述模型是一個確定性的預測模型，其優點在于節點間交互信息較少，只需要知道節點間的速度信息，即可進行預測.但是，由于這個模型沒有引入任何的先驗假設，因此在面對不同的路況和不同的車節點拓撲時，其適應性不夠好.WangXiufeng等人[8]提出可以假設道路上行駛車輛的速度為隨機變量，且服從一般的正態分布N(μ,σ2).作者通過推導，得出了兩輛車通信時長的預測模型：

t.

(2)

上述預測模型只利用了車輛的速度信息，需要交互的信息較少，計算方法也較為簡潔.但是，這個預測模型是一個一維的預測模型，即只考慮兩輛車的速度方向在一條直線上，不具備普適性.與文獻[8]類似，Eiza等人[9]同樣基于車輛速度服從正態分布的假設，但是利用了基于網絡拓撲的演化圖(evolving graph)給出了詳細的路由算法.文章估計了2個車節點的通信時長及其置信度，由此構建一個圖，節點為車輛，邊權為車輛節點的可通信時長及置信度，利用EG-Dijkstra算法選擇路由.

Xue Guangtao等人[10]利用變階Markov模型對車輛的行駛模式進行識別，通過借鑒自然語言處理中的機器學習方法，對大量車輛運行數據進行建模，為較大時間跨度的預測提供了可能性.但是，上述方法并不適用于VANET路由選擇.原因是：1)車輛運行的軌跡模式十分復雜，是相當于定制化的數據模式，普適性較差；2)如果使用上述軌跡預測方法進行路由，需要結合地圖信息，然而在許多車載自組織網絡應用場景中，并沒有精確的電子道路地圖.

綜上，這些算法各有側重，但是都無法較好地應用于基于位置的路由協議計算.為此，我們將在第2節中提出一種新的預測算法.

2 基于加速度的預測算法

在本節中，我們將提出一種新的基于加速度的預測算法.本節中的實驗數據均來自真實的道路車輛運行數據.首先我們將在2.1節提出一種基于加速度正態分布假設的樸素預測方法；針對樸素預測算法對于拐彎預測較差的情況，我們將在2.2節中提出一種改進的預測算法.

2.1樸素預測算法

我們對基于速度正態假設的預測算法[8-9]進行了分析.從本質上講，Wang Xiufeng等人[8]提出的預測算法是在勻速運動的假設上進行的，即假設在同一時刻道路上各種車輛的速度分布為正態分布，但在一段時間內各個車輛保持勻速.上述假設導致了預測模型的實時性較差.我們從新的角度思考，不再考慮所有路上車輛的速度分布，轉而考慮單個車輛的速度作為隨機過程的統計規律.我們通過實車實驗得到了一輛汽車在城市道路運行的軌跡，并統計了一段時間內的運行速度，如圖1所示.從圖1我們可以發現速度的正態分布規律不夠明顯，因此我們進一步分析了加速度的分布.我們利用車輛軌跡，取時間間隔為1 s，計算加速度，得到了加速度分布直方圖，如圖2所示.從圖2可以看出，加速度擁有較好的正態性.如果設每一時刻的加速度為一隨機變量a，則應該有a服從N(μ,σ2).

Fig. 1 Velocity-frequency statistics圖1 速度-頻率統計圖

Fig. 2 Acceleration-frequency statistics圖2 加速度-頻率統計圖

基于上述假設，我們可以給出一種基礎預測算法.隨機變量a服從正態分布N(μ,σ2)，其密度函數滿足：

(3)

有了上述概率密度函數，一個重要問題是對分布參數進行估計.由于我們已經擁有了較大量真實車輛運行軌跡數據，因此基于統計的參數估計是首要選擇.假設已經有n個加速度數據ai,i=1,2,…,n,則：

(4)

(5)

(6)

為了使距離預測盡可能準確，我們設總的預測時間為T，并給出區間[0,T]上的一個分割：0=t0lt;t1lt;t2lt;…lt;tn=T，記預測結果為

(7)

其中，i=1,2,…,n.則最終的預測結果為

(8)

在實際情況中，方便的方法是取所有分割長度相等，記為Δt.所以，可得到一維車輛節點位置預測算法1.

算法1. 一維車輛節點位置預測算法.

輸入：當前車輛速度v、加速度參數μ和σ、積分步長Δt、預測時間T；

輸出：T時間后的車輛位移x.

① time←0;

② x←0;

③ temp←v;

④Fortime≤Tdo

⑤ a←normal_variable_producer(μ,σ);

⑥ x←x+temp×Δt+aΔt22;

⑦ temp←temp+aΔt;

⑧ time←time+Δt;

⑨EndFor

Fig. 3 Absolute error of simple prediction圖3 樸素預測的絕對誤差

針對上述算法，利用一段直路上的真實行車軌跡對這個算法進行了檢驗，其中取Δt=0.1s，得到結果如圖3所示.圖3中，橫軸表示取不同的預測時長T，縱軸表示在該條件下進行多次預測的誤差的平均值.從圖3可以看出，即使在預測時長較長時，其效果仍然較好，說明該模型是正確可用的.但值得指出的是，當預測時長T較大時，預測結果將失去意義，因為真實車輛并不能在一條直線道路上長時間行駛而不拐彎或掉頭.

另外，原則上講Δt的取值應該越小越好，但是，在實際操作中，Δt只要不過大，對預測結果的影響就很小.為了保證積分的正確性，TΔt必須是整數.需要進一步說明的是，在實際應用場景下對加速度的正態分布的參數估計可以采用多種方法.其中一種方法是：在預測開始時，用一個按2.1節所述方法估計的先驗參數，之后再隨著時間的推移，不斷修正參數.本文主要討論最基本的預測算法原理，所以將不對上述工程細節展開探討.

在此基礎上，加上對速度方向的預測，即可對車輛二維坐標位置進行預測.基于對車輛位置的預測，可以很容易預測接下來需要的參數，如通信時長等.在預測速度方向時，一個樸素的想法是將開始預測時的速度方向作為接下來預測的速度方向.通過上述思想，利用一段真實車輛行駛軌跡，得到了樸素算法的實驗結果如圖4所示.其中，圓圈表示實際的運行軌跡，十字表示預測的運行軌跡，預測時長T=10s.預測的絕對誤差分布如圖5所示，表示的是每次預測誤差的分布圖.橫軸表示預測誤差，縱軸表示出現這種誤差的頻率.通過圖5可以得到在這種樸素的預測方法下，誤差大多數都集中在10m以下.

Fig. 4 Trajectory prediction result of simple prediction圖4 樸素預測算法的軌跡預測結果

Fig. 5 Error distribution of simple prediction圖5 樸素預測算法的誤差分布

在圖4中，大多數的大誤差點都集中在拐彎處，如圖6所示.事實上，由于我們對速度方向的預測是基于預測時的速度方向，導致預測實質上是在一維方向上的預測.因此，如果在預測時，車輛恰好在拐彎的過程中，則拐彎的偏差就會較大，極端情況下可能有50 m的誤差.

Fig. 6 Trajectory prediction result of simple prediction: local map圖6 樸素預測算法的軌跡預測結果：局部圖

2.2改進的車輛位置預測算法

Fig. 7 Examples of right-angle turning圖7 直角拐彎示例

為了避免在拐彎預測中產生較大的偏差，一個自然的想法是通過預知拐彎的發生來改善預測結果.對于一段的道路情況，拐彎是一個漸變的過程，拐彎時長通常在8～10 s.以一個常見的90°拐彎為例，拐彎過程如圖7所示.這是一張車輛運行的軌跡圖，繪制間隔為1 s，即每一個點表示一輛車在某一時刻的位置，連續的點之間的間隔為1 s.通過圖7可以想到，如果樸素預測算法的預測發生在恰好要拐彎的第4秒或之后幾秒，此時的預測誤差將會非常大.因此，改進這種誤差的關鍵是能夠預測到拐彎的發生.

一個直觀的想法是，假設拐彎是一個相對均勻的過程.實際上，這個假設符合實際情況，因為在一般道路上拐彎時的速度要小于直線駕駛時的速度.如果一個普通的90°拐彎要持續10 s，則每一秒的轉角平均下來為9°.如果我們發現了一輛車在第3,4秒的時間內速度方向有連續的改變，那么我們便可以預知一個拐彎.將這種思想進行推廣，如果我們每一次預測時的速度方向都是按照前幾秒的速度方向來估計，其效果應該遠好于之前的樸素預測.最簡單有效地利用上述思想的方法就是線性軌跡.在實際中，用車輛運動軌跡的切線方向表示速度方向.而在離散軌跡中，用折線段來近似車輛軌跡，則可用折線段斜率表示速度方向.注意，為了避免出現斜率過大的情形，應適當地在局部進行坐標系的旋轉，以防止因為斜率過大導致的計算預測不準確.

現假設已觀測到n組數據，每一組數據包括連續m秒的速度方向數據(ki 1,ki 2,…,ki m)，并知道接下來的速度方向為ki(i=1,2,…,n)，則可建立線性回歸模型：

(9)

其中，i=1,2,…,n.將式(9)表示成矩陣式，則記：

(10)

(11)

則這個模型可以表示為

(12)

按照最小二乘法估計參數β，應最小化誤差平方和，即考慮代價函數：

(13)

(14)

由此可得到速度方向的線性預測模型：

(15)

在統計學上，為了評價模型的精確性，要引入相關系數來刻畫.為此，記：

(16)

更一般地，我們定義相關系數

(17)

容易說明0lt;R2lt;1，且相關系數越大表明模型的線性越好.盡管不存在理論上的一個閾值，使得相關系數大于這個閾值時認為模型的精確度較高，但在實際工程應用中，一般認為當R2gt;0.5時，模型就已經充分可用.為使用該模型對車輛行駛方向進行預測，首先應該確定回歸變元數量m的取值.相關系數隨變元數量變化的結果如圖8所示.圖8的橫軸表示選取了前n(n=1,2,…,13)秒的速度方向來線性擬合這一時刻的速度方向，縱軸表示線性回歸系數.從回歸之后的結果我們知道這種線性是統計顯著的，回歸系數在0.6左右，表示模型精確度尚可.在圖8中，我們發現，取n=7是比較合適的；若ngt;7，則之后的變量影響極小，不必考慮.

Fig. 8 Correlation coefficients with different number of variables圖8 擬合變量個數對線性回歸系數的影響

基于以上結果，我們將預測的過程細分，預測逐秒進行，每次都通過回歸系數計算出一個新的速度方向，可以得到新算法如算法2所示:

算法2. 改進的車輛位置預測算法.

輸入：當前車輛速度v、加速度參數μ和σ、積分步長Δt、預測時間T、前7s的斜率向量k;

輸出：T時間后的車輛位置x.

① time←0;

②x=0;

③Fortime≤Tdo

④ temp_k=linear_predict(k);

⑤x←x+position_predict(v,μ,σ,Δt,1,

temp_k);

⑥constructanewkaccordingtotemp_k;

⑦ time←time+1;

⑧EndFor

其中，position_predict(v,μ,σ,Δt,1,temp_k)表示利用之前的樸素預測算法預測位置，預測時長T=1s，距離為按照樸素預測算法得到的結果x，方向是temp_k.按照這個算法得到的預測結果如圖9所示，其局部放大圖如圖10所示.圖10中的點表示的意思與之前的軌跡圖類似.在這里，我們沒有考慮線性預測過程的誤差ε，先令ε=0.

Fig. 9 Trajectory prediction result of improved prediction圖9 改進預測算法的軌跡預測結果

Fig. 10 Trajectory prediction result of improved prediction: local map圖10 改進預測算法的軌跡預測結果：局部圖

從圖10中不難看到，對拐彎的預測已經改善很多.這里要說明的是，這種預測算法的最大誤差會發生在預測時車輛剛剛要進入拐彎，即圖7中提到的拐彎的第1秒.但這時的最大誤差顯然會遠小于之前樸素預測算法的最大誤差.為說明這一點，我們可以簡單計算如下：設一個拐彎總長度為40 m，拐彎前后各行駛20 m，車輛勻速行駛，拐彎總時間為10 s，預測時間T=10 s.我們假設一維預測是準確的，即忽略一維預測帶來的誤差，則樸素的位置預測算法的誤差發生在恰好拐彎處：

改進的預測算法的最大誤差發生在剛拐彎時：

因此，改進算法的誤差已得到大幅改善.

仔細觀察圖9和圖10，可以發現這個預測圖有一定的誤差，是因為未考慮ε造成的.一般而言，在線性預測模型中，總是假定ε服從某種分布(較常見的，如上面模型假設的正態分布)，從而給出對ε的估計.但是，在實際應用場景中，這個估計一般比較困難.因此，我們轉而直接考察預測結果的誤差.取定一個局部坐標系，用坐標來表示地圖上的點，并考慮x，y兩個方向上的誤差.我們統計了隨著預測時間的增長誤差的累計情況，如圖11所示:

Fig. 11 Error accumulation on x-axis with time varing圖11 x方向上誤差隨預測時間的累積

從圖11中容易看出誤差的累積是高度線性的.值得說明的是，每一次預測的誤差的線性關系不盡相同，圖11中表示的是一個平均的結果.y方向的結果與之類似，在此不再給出.基于該結果，雖然不能很好地估計速度方向線性預測中的誤差ε，但是可以通過修正最終的預測結果來使誤差降低.一個操作上的難題是如何利用這個信息，我們可以從反饋的角度思考.如果我們預測10 s之后車輛的位置，那么其實可以不斷修正這個預測結果，修正的方式就是利用圖11的結果.例如，可以在預測后3 s內統計出誤差的線性增長關系，在最后一并給出最終的預測結果.最初的3 s可以不進行預測，利用舊的位置信息進行路由決策，然后預測系統的誤差補償機制開始運作后，隨著窗口滑動，可以得到連續的修正預測結果.誤差修正后的實驗結果及局部放大圖如圖12和圖13所示，預測時長T=10 s.其中，圖上各點的意義與之前的軌跡圖類似.在矯正了誤差之后，預測結果已經很好.

Fig. 12 Trajectory prediction result after error correction圖12 誤差修正后的軌跡預測結果

Fig. 13 Trajectory prediction result after error correction: local map圖13 誤差修正后的軌跡預測結果：局部圖

我們新提出的預測算法與已有算法有較大不同，體現在2方面：1)新算法是基于加速度正態性假設進行的預測；2)新算法是實時性的預測，可以直接給出預測后的地理位置，方便基于位置的路由協議的使用.第3節，將介紹如何將我們的預測方法用于實際路由協議，并驗證其在實際路由決策中的有效性.

3 基于位置信息的即時路由協議

即時路由協議(IR)是一種基于GPS信息的路由協議，從本質上看也是一種基于地理位置的路由協議.IR協議專門被設計為適用于高速變化拓撲的車聯網，所以IR放棄了像其他協議如AODV[11]那樣去修復端到端的連接，這一過程被證明是很耗時的.相反，IR可以采用第2節提到的預測算法，利用保存的周邊節點的地理位置信息去計算預估合適的下一跳，并轉發給該下一跳節點.另外，IR還可以平衡查找路由和計算路由之間的比例，在節點位置關系變化不大時，利用之前計算出的下一跳結果進行轉發.下面，我們將詳細介紹IR協議的設計.

IR共有3種形式的數據包，分別為Beacon包、Interest包和Data包.其中Beacon包是節點間用來交換地理位置信息的，周期性發送；Interest包是節點用來請求數據而發送的，包含所需數據的名稱；而Data包顧名思義就是數據包，用來響應Interest包，里面包含著請求者所需的數據.

IR工作機制如圖14所示.首先，每個節點周期性地發送Beacon包，攜帶自身ID、GPS信息和運動速度信息，發送給鄰居節點.所有接收到該Beacon包的節點都被視為該節點的鄰居節點.每個節點創建并維護一張鄰居列表(neighbor list)，收到Beacon包后就把該鄰居節點更新到該表中；若之后一段時間未收到來自某鄰居的Beacon包，則把該節點從鄰居列表中刪除(表項的時間戳過期，自動刪除).把請求數據的節點consumer稱為源節點，數據提供者(provider)稱為目的節點，其他轉發了Interest包或者Data包的節點forwarder都稱為中間結點.上述類似的思想在命名數據網絡NDN[12-17]中被廣泛使用.

Fig. 14 Forwarding calculation procedure of instant routing圖14 即時路由的計算轉發過程

當源節點想要發送包含所需數據名稱的Interest包時，如果是該節點第1次請求某一數據，它并不知道誰擁有內容，所以該節點會通過廣播Interest包尋找數據，周圍節點收到廣播的Interest包后，則會繼續廣播Interest包，直到抵達最終目的節點，然后目的節點將Data包按原路徑返回源節點.這樣源節點就獲得了目的節點的地理位置信息，從而用于請求后續數據分組，并且每一次分組帶回來的GPS信息也都會實時更新目的節點的位置，以確保目的節點位置信息最新.

如果節點不是第1次請求數據，而是之前已經請求并獲得了數據的部分分組，并且當通過發送Interest包請求數據的剩余其他分組時，就會根據已獲得的目的節點GPS信息(之前請求數據包時返回的信息)去查找路由表，如果路由表中存在相應路由表項，并且該表項未過期且合法，則節點就根據路由表中信息來發送Interest包.如果不存在相應表項或表項不合法，則協議會啟動計算下一跳過程，根據節點鄰居表中的歷史GPS信息，來計算預測周圍節點中距離目的地最近的節點，然后將其作為下一跳，并把Interest包發送給那個節點，該節點的轉發過程與上述過程相同，查表或計算預測，這樣Interest包就能經過不斷地轉發到達目的地，目的節點則會按照Interest來時的路徑把數據分組反向傳遞回源節點，每一次返回的數據包都會將目的節點的最新位置帶回源節點.

Fig. 15 Procedure of setting up the reverse link圖15 反向鏈路建立過程

下面詳細介紹計算預測算法和建立反向鏈路過程，這些都是IR顯著區別于其他路由算法的內容.計算預測算法是IR路由協議的最大特色之一，Beacon包的發送是具有一定周期的，并且周期不能太短，不然就會造成很大的協議包開銷，影響帶寬利用率.并且在Beacon包的周期內，節點會移動，在車聯網應用場景下移動速度相對較快.考慮到這個情況，我們初始設計了一個比較簡單的線性預測算法來專門預測當前時刻周圍節點的地理位置，從而能準確找到合適的下一跳，使得發送數據包更精確和有效.

首先做這樣一個假設，即在Beacon包的周期范圍內，車輛節點的速度是恒定的.因此我們可以根據車輛的速度來預測位移，進而得出位置.具體方法為：首先基于節點歷史Beacon包周期獲取的鄰居節點地理位置信息，先計算出上一周期鄰居節點的速度向量(包含大小和方向)，從而計算出從上一個Beacon 周期到現在為止鄰居節點的相對位移，通過向量運算得到鄰居節點當前的位置，然后在當前節點和目的節點位置的連線方向上，在預先設定好的夾角閾值θthreshold范圍內，通過計算在鄰居節點中找出距目的節點最近的節點，并將計算出的節點作為新的下一跳節點更新到路由表中.不過該方法除了需要GPS 信息的交換之外，每個節點還須維護其鄰居節點的速度信息.如圖14所示，C′，D′，F′是A節點在上一Beacon周期所獲取的鄰居節點地理位置信息，F′是過去路由表中的下一跳.現在A想發送數據給B，但發現路由表項過期，于是啟動預測計算算法，預測出C′，D′，F′所對應的當前鄰居節點位置C,D,F，并在夾角閾值θthreshold范圍內，通過計算和判斷，將D點作為自己的下一跳.

反向鏈路，顧名思義，是目的節點收到Interest包后將數據返回給源節點所要經過的路徑.對于建立反向鏈路過程，IR的做法和AODV做法雖看上去相似，但卻有本質的不同.首先，在AODV中，是通過協議包事先建立好源和目的節點間的來回路徑.而在IR中，是通過查表和計算路由相結合的方法，Interest包發往目的節點途中在中間節點建立了返回源節點的路由，數據返回過程很快，所以大部分節點位置幾乎沒變，只有少部分節點變化很大，導致鏈路中間斷開一小部分，這時可以在斷開位置利用預測計算來得到下一跳，計算幾次后就可能重新找到原來的反向路徑.如圖15所示，A點向目的節點B點發送Interest包，沿途的中間節點創建了返回A點的路由信息，從而建立了A到B的反向鏈路，B收到請求包后，準備將數據發回A，根據路由表應該發給下一跳H′，但根據最新的鄰居表顯示H′已不在B點可達范圍，故路由信息不合法，所以B啟動計算路由過程找到G點作為其下一跳，由于G點沒有參與Interest轉發，故不存在到A點的路由信息，所以G點也啟動計算路由過程找到D點作為其下一跳，D是反向鏈路的一部分，所以D根據其路由表信息就能將數據返回到A點.

以上描述的簡單線性預測較初步，我們將使用第2節提出的新型預測算法進行節點位置預測，以改進基礎版IR的性能.

4 實驗與結果

仿真實驗是在安裝于Ubuntu14.04上的NS3.26[18]和SUMO0.29.0[19]平臺上進行的.我們首先在OpenStreetMap[20]官網上選擇并下載了上海和重慶的局部地圖數據.其中，上海的局部地圖對應了地理范圍較大、節點較為稀疏的情形，如圖16所示.重慶的局部地圖對應了地理范圍較小、路網較密的情形，如圖17所示.我們根據地圖數據同時編寫了車流量文件，車輛規模為20～100輛車，隨機平均分布在地圖車道上，并在0～100 s內通過設定好的路線運動，遇到紅綠燈會等待，并且會根據道路選擇拐彎和掉頭，以達到盡可能地模擬真實環境的目的.最后，利用SUMO生成了車輛仿真Trace文件.

Fig. 16 Local map topology of Shanghai圖16 上海局部地圖拓撲

Fig. 17 Local map topology of Chongqing圖17 重慶局部地圖拓撲

在NS3中，我們設置了默認的底層模型，選擇802.11a作為物理層，AdhocMac作為鏈路層，創建并安裝無線網絡設備.然后選擇上面SUMO生成的Trace文件作為節點移動拓撲模型.接著安裝我們設計的基礎版IR路由協議(記為IR)，新型預測IR(記為IR_Prediction)，還有對比組GPSR協議(記為GPSR).完成之后，添加上我們設計的一個簡單應用，該應用采用client-server模式，client節點周期性發送Interest包，sever節點是每收到一個發送給自己的Interest包后就返回一個Data包，然后設置仿真時間為0～100 s后，就可以進行仿真了.具體實驗參數如表1所示：

Table 1 Simulation Parameter Configuration Table

我們在改變節點規模的情況下，分別對IR，IR_Prediction，GPSR進行了10組實驗，然后對實驗結果取平均，統計了每個節點的各項指標.我們選取了具有代表性的3個指標：收包率(round-trip delivery ratio, RTDR)、往返時延(round-trip time, RTT)和開銷率(overhead).其中,收包率的定義為接收到的所有Data包總數與發送的Interest包總數的比值;RTT的定義為接收到所需Data包的時間戳與發送對應的Interest包的時間戳的差值;開銷率定義為每當Sever收到一個Interest包或者Client收到Data包，網絡中需要額外傳輸多少字節的數據，包括協議包以及未抵達目的節點而丟棄的各種Interest包和Data包.3個統計量的定義和計算方法如表2所示.對于開銷率，RtotalByte代表某節點收到的所有包(包括協議包、轉發包、請求包和數據包)的字節數，Rits代表某Server節點收到的Interest包的數目， Interest包的總字節數是105(包含41 B的包頭)，Rdata代表某Client節點接收到發往自己的Data包的數目，Data包的總字節數是1 041(同樣包含41 B的包頭)，Hopup代表Interest包到達目的節點平均所經歷的跳數，Hopdown代表Data包發回源節點平均所經歷的跳數.

Table 2 Definitions of Experimental Indexes

下面，我們將分別給出在不同節點規模下，收包率、RTT和開銷率的實驗結果與分析.

4.1收包率實驗

Fig. 18 Round-trip delivery ratio of Shanghai topology圖18 上海拓撲的收包率

圖18和圖19分別表示了3種路由協議在上海和重慶兩張地圖上的收包率仿真結果.從圖18和圖19都可以看出，使用新型預測算法的IR_Prediction協議效果明顯好于基礎版IR和GPSR協議.需要說明的是，使用上海地圖拓撲時的收包率整體較低，是因為地圖過大及節點過于稀疏造成的.而從收包率趨勢來看，隨著節點密度增大，圖18上呈現了一種收包率上升的趨勢.這是因為上海地圖面積較大，在節點密度較小時，很多鏈路都可能處于最大通信距離的范圍之外.當節點密度增大時，可用連接變多，收包率有所提高.圖19中，隨著節點密度增大，收包率呈現出下降的趨勢.這是因為在重慶這張較小的地圖中，許多節點都處在一個CSMA沖突域中，隨著節點規模增大，沖突避讓發生頻率增大，使得收包率呈現下降的趨勢.不過總體上講，圖19中的收包率可以維持在較高的水平，大于70%.

Fig. 19 Round-trip delivery ratio of Chongqing topology圖19 重慶拓撲的收包率

4.2RTT實驗

Fig. 20 Round-trip time of Shanghai topology圖20 上海拓撲的RTT結果

圖20和圖21分別表示了3種路由協議在上海和重慶兩張地圖上的RTT仿真結果.RTT從一定程度上反映了網絡延遲情況，不過RTT的統計與收包率有一定關聯，因此不能單純地從RTT斷定協議工作狀況的優劣.從圖20和圖21的縱軸可以看出，上海地圖的RTT從總體上大于重慶地圖.在上海地圖上進行實驗，IR_Prediction協議與基礎版IR，GPSR在RTT上并沒有拉開差距，互有高低，在節點密度大時IR_Prediction協議的RTT還大于基礎版IR和GPSR，這是由于收包率提高造成的.這部分多收到的包會在一定程度上拉高RTT的數值.而在圖21中，重慶地圖呈現了相反的情況，在節點密度大時，由于收包率降低，部分沒收到的包就不再進入RTT的統計之中，反映出的結果反而是降低了RTT.上述結果的根本原因是RTT的統計僅考慮收到的包，而未收到的包并沒有加一個較大的值進入統計.

Fig. 21 Round-trip time of Chongqing topology圖21 重慶拓撲的RTT結果

通過上述收包率和RTT的實驗，可以說明新的預測算法在幫助IR協議進行路由決策方面相比基礎版IR有大的改進，可以顯著提升收包率和控制延遲.

4.3開銷實驗

Fig. 22 Protocol overhead of Shanghai topology圖22 上海拓撲的協議開銷

從圖22和圖23中可以看出，3種協議的開銷率都隨著節點密度的增加而逐漸增加.其中，圖22表示的上海的開銷率大于圖23表示的重慶的開銷率，因為上海地圖面積較大，收包率較低.在兩張圖中，IR_Prediction的開銷率均大幅優于基礎版IR和GPSR，因為IR_Prediction協議的重傳率低于IR和GPSR，使得開銷大大降低.

Fig. 23 Protocol overhead of Chongqing topology圖23 重慶拓撲的協議開銷

5 總 結

本文針對車載自組織網絡中基于位置的路由協議，提出了一種新的車輛位置預測算法.新算法首先通過測量得出車輛加速度服從正態分布的結論，利用線性回歸方法進行預測，并通過反饋系統修正預測誤差，克服了之前預測算法中普適性較差、預測誤差大的問題.然后，提出了一種新型的基于位置的即時路由協議，在新協議上驗證了預測算法的正確性.實驗結果表明，新的位置預測算法在保持網絡較高收包率、較低延遲的基礎上，使得協議開銷顯著下降.在未來的工作中，我們期望能夠在實車上實現即時路由協議和位置預測算法，實現實際車輛自組織網絡系統，利用真實應用場景驗證本文預測算法和路由協議的有效性.

[1]Awang, A, Husain K, Kamel N. Routing in vehicular ad-hoc networks: A survey on single- and cross-layer design techniques, and perspectives[J]. IEEE Access, 2017, 5(1): 9497-9517

[2]Garrosi M, Kalac M, Lorenzen T. Geo-routing in urban vehicular ad-hoc networks: A literature review[C]Proc of IEEE ICNC’17. Piscataway, NJ: IEEE, 2017: 865-871

[3]Lin Dan, Kang Jian, Squicciarini A, et al. MoZo: A moving zone based routing protocol using pure V2V communication in VANETs[J]. IEEE Trans on Mobile Computing, 2017, 16(5): 1357-1370

[4]Kung T, Karp B. GPSR: Greedy perimeter stateless routing for wireless networks[C]Proc of ACM MobiCom’00. New York: ACM, 2000: 243-254

[5]Alsaqour R, Abdelhaq M, Saeed R, et al. Dynamic packet beaconing for GPSR mobile ad hoc position-based routing protocol using fuzzy logic[J]. Journal of Network and Computer Applications, 2015, 47(C): 32-46

[6]Li Jia, Wang Ping, Wang Chao. Comprehensive GPSR routing in VANET communications with adaptive beacon interval[C]Proc of IEEE CPSCom’16. Piscataway, NJ: IEEE, 2016: 211-216

[7]Menouar H, Lenardi M, Filali F. Movement prediction-based routing (MOPR) concept for position-based routing in vehicular networks[C]Proc of IEEE VTC’07. Piscataway, NJ: IEEE, 2007: 2101-2105

[8]Wang Xiufeng, Wang Chunmeng, Cui Gang, et al. Practical link duration prediction model in vehicular ad hoc networks[J]. International Journal of Distributed Sensor Networks, 2015, 2015(1): 311-325

[9]Eiza M, Ni Qiang. An evolving graph-based reliable routing scheme for VANETs[J]. IEEE Trans on Vehicular Technology, 2013, 62(4): 1493-1504

[10]Xue Guangtao, Luo Yuan, Yu Jiadi, et al. A novel vehicular location prediction based on mobility patterns for routing in urban VANET[J]. EURASIP Journal on Wireless Communications and Networking, 2012, 222(1): 422-436

[11]Perkins, C, Belding-Royer E, Das S, et al. Ad hoc on-demand distance vector (AODV) routing[EBOL]. 2003[2017-05-23]. https:tools.ietf.orghtmlrfc3561

[12]Zhang Lixia, Afanasyev A, Burke J, et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 66-73

[13]Grassi G, Pesavento D, Pau G, et al. VANET via named data networking[C]Proc of IEEE INFOCOM’14 Workshop. Piscataway, NJ: IEEE, 2014: 410-415

[14]Ahmed S, Bouk S, Kim D. RUFS: Robust forwarder selection in vehicular content-centric networks[J]. IEEE Communications Letters, 2015, 19(9): 1616-1619

[15]Ahmed S, Bouk S, Yaqub M, et al. CODIE: Controlled data and interest evaluation in vehicular named data networks[J]. IEEE Trans on Vehicular Technology, 2016, 65(6): 3954-3963

[16]Bouk S, Ahmed S, Yaqub M, et al. DPEL: Dynamic PIT entry lifetime in vehicular named data networks[J]. IEEE Communications Letters, 2016, 20(2): 336-339

[17]Yaqub M, Ahmed S, Bouk S, et al. Interest forwarding in vehicular information centric networks: A survey[C]Proc of ACM SAC’16. New York: ACM, 2016: 724-729[18]NS-3 Consortium. Network simulator 3[EBOL].[2017-05-23]. https:

[19]Institute of Transportation Systems at the German Aerospace Center. Simulation of urban mobility(SUMO)[EBOL].[2017-05-23]. http:www.sumo.dlr.dewikiSimulation_of_Urban_MObility_-_Wiki

[20]OpenStreetMap Community. OpenStreetMap world map[EBOL].[2015-05-23]. http:www.openstreetmap.org

LiYang, born in 1989. PhD candidate at Tsinghua University. His main research interests include vehicular ad hoc network and network measurement.WangZhe, born in 1995. PhD candidate at Tsinghua University. His main research interests include vehicular ad hoc network and statistics.

ZhangChuwen, born in 1992. PhD candidate at Tsinghua University. His main research interests include high-performance switches/routers, named data networking and vehicle networks.

DaiHuichen, born in 1988. Postdoctoral research fellow in the Department of Computer Science and Technology, Tsinghua University. Received his PhD degree from the Department of Computer Science and Technology, Tsinghua University, in 2016. His main research interests include routing protocols in ad hoc wireless networks, content cache analysis, and SDN.

XuWenquan, born in 1995. PhD candidate at Tsinghua University. His main research interests include NDN and VANET.

JiXuefeng, born in 1994. PhD candidate at Tsinghua University. His main research interests include NDN and VANET.

WanYing, born in 1993. PhD candidate at Tsinghua University. His main research interests include named data networking，software defined networking and vehicular networks.

TrajectoryPredictionAlgorithminVANETRouting

Li Yang, Wang Zhe, Zhang Chuwen, Dai Huichen, Xu Wenquan, Ji Xuefeng, Wan Ying, and Liu Bin

(Department of Computer Science and Technology, Tsinghua University, Beijing 100084)

In vehicular ad hoc network (VANET), geographic routing protocols can preferably adapt to frequent topology changes and unstable link quality. Beacon messages are needed to share the positions of neighboring nodes, so forwarding decisions in the interval of successive beacon messages may be inaccurate due to the movement of the vehicle nodes. In this situation, trajectory prediction is needed to amend the positions of the vehicle nodes. Existing prediction algorithms are either lack of universality or suffered from large prediction errors. To solve the problems above, this paper proposes a new trajectory prediction algorithm, which is based on the measurement result that the vehicle accelerations obey normal distribution. The new algorithm uses linear regression to do the prediction and applies a feedback mechanism to amend error. The new trajectory prediction algorithm can greatly improve the prediction accuracy in several real trajectory trace tests. Then this paper proposes a new position based instant routing protocol. In instant routing protocol, a forwarder uses the predicted position of neighboring nodes and destination node to calculate the next hop. We apply our new trajectory prediction algorithm in instant routing to predict and update vehicle positions in real time. We use SUMO to generate real maps and vehicle trajectory traces, and use NS3 to do the simulation. Experimental results show that instant routing with the new trajectory prediction algorithm outperforms the traditional GPSR protocol and instant routing without trajectory prediction in terms of packet delivery ratio and network latency, while reducing protocol processing overhead remarkably.

vehicular ad hoc network (VANET); instant routing (IR); trajectory prediction; geographic routing protocol；named data networking (NDN)

his MSc and PhD degrees in computer science and engineering from Northwestern Polyte-chnical University, Xi’an, China in 1988 and 1993, respectively. Professor and PhD supervisor of Tsinghua University, Beijing, China. His main research interests include high-performance switches/routers, network processors, named data networking and software-defined networking.

2017-05-31；

2017-08-08

華為公司創新研究計劃項目；國家自然科學基金項目(61602271,61373143,61432009)；中國博士后科學基金項目(2016M591182)

This work was supported by the Huawei Innovation Research Program (HIRP), the National Natural Science Foundation of China (61602271, 61373143, 61432009), and the China Postdoctoral Science Foundation (2016M591182).

劉斌(liub@mail.tsinghua.edu.cn)

TP393.03