王廣彧，劉春鳳，2，趙增華，舒炎泰

(1.天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300072;2.天津市認(rèn)知計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，天津 300072)

1 概述

車載自組織網(wǎng)絡(luò)(Vehicular Ad Hoc Network，VANET)依靠安裝無線通信設(shè)備的車輛進(jìn)行數(shù)據(jù)傳輸，能夠提供互聯(lián)網(wǎng)移動(dòng)接入、輔助駕駛、事故預(yù)警等應(yīng)用［1-2］，是智能交通系統(tǒng)的重要組成部分，近年來受到工業(yè)界和國(guó)內(nèi)外科研院所的普遍關(guān)注。作為一種特殊的移動(dòng)自組織網(wǎng)絡(luò)(Mobile Ad Hoc Networks，MANET)，VANET 節(jié)點(diǎn)受道路狀況、交通機(jī)制的影響，具有高速移動(dòng)、分布不均等特征［3-5］，造成通信時(shí)間短、鏈路頻繁斷裂、鏈路容量受限，使得車輛之間的高效數(shù)據(jù)傳輸面臨極大的挑戰(zhàn)。

現(xiàn)有的VANET 路由算法大致分為2 類:地理位置路由和容遲網(wǎng)絡(luò)(Delay Tolerant Network，DTN)路由。GPSR (Greedy Perimeter Stateless Routing)［6］是一種典型的地理位置路由算法，將分組轉(zhuǎn)發(fā)給在地理位置上更靠近目的節(jié)點(diǎn)的鄰居。在連通性較好的網(wǎng)絡(luò)中，地理位置路由的分組投遞率較高且時(shí)延較低，但在連通性較差的網(wǎng)絡(luò)中，分組在多跳之后往往找不到合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)而被丟棄，網(wǎng)絡(luò)的整體投遞率很低。另一類路由算法，如文獻(xiàn)［3］算法，借助于DTN 網(wǎng)絡(luò)存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)的思想，來實(shí)現(xiàn)非連通區(qū)域的數(shù)據(jù)傳輸，解決車載網(wǎng)絡(luò)在間歇連通和低密度情況下的數(shù)據(jù)傳輸問題。這類算法在稀疏網(wǎng)絡(luò)中可以提升分組投遞率，但分組的端到端時(shí)延一般較高?；旌下酚伤惴ㄈ鏕eo+DTN［7］結(jié)合了地理位置路由在連通性較好網(wǎng)絡(luò)中低時(shí)延和DTN 路由在連通性較差網(wǎng)絡(luò)中高投遞率的特點(diǎn)。但Geo+DTN 完全依賴導(dǎo)航系統(tǒng)提供車輛位置或軌跡信息，靈活性較差，其DTN 模式只是簡(jiǎn)單的存儲(chǔ)-攜帶，直到可以轉(zhuǎn)回貪婪轉(zhuǎn)發(fā)模式，未充分利用位置信息做出更優(yōu)的轉(zhuǎn)發(fā)決策。

本文針對(duì)城市車載自組織網(wǎng)絡(luò)場(chǎng)景中地理位置路由和DTN 路由的不足，及車載網(wǎng)絡(luò)路由算法在獲取車輛位置信息方面的局限性，提出一種適用于城市場(chǎng)景的、基于卡爾曼預(yù)測(cè)的混合路由算法KPHR。該算法利用卡爾曼濾波對(duì)車輛位置進(jìn)行實(shí)時(shí)預(yù)測(cè)來輔助路由計(jì)算。在GPSR 算法的基礎(chǔ)上，結(jié)合容遲網(wǎng)絡(luò)(DTN)路由存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)的思想，在貪婪模式或邊緣模式中，當(dāng)無轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，切換至DTN 模式存儲(chǔ)攜帶分組;在DTN 模式中，利用位置信息選擇合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)，當(dāng)網(wǎng)絡(luò)連通時(shí)，切換至貪婪轉(zhuǎn)發(fā)模式。

2 基于卡爾曼濾波的車輛實(shí)時(shí)位置預(yù)測(cè)

車輛實(shí)時(shí)位置在VANET 數(shù)據(jù)傳輸協(xié)議設(shè)計(jì)中扮演著重要角色。地理位置路由通常面臨轉(zhuǎn)發(fā)決策所使用的位置信息時(shí)效性較低的問題［8］。如圖1 所示(白色節(jié)點(diǎn)表示節(jié)點(diǎn)S 記錄的鄰居節(jié)點(diǎn)的歷史位置，黑色節(jié)點(diǎn)表示節(jié)點(diǎn)的實(shí)際位置)，S 根據(jù)歷史位置信息選擇A 節(jié)點(diǎn)作為目的為D 的下一跳節(jié)點(diǎn)，但A 此時(shí)已離開S 的通信范圍移動(dòng)至A'。S 將選擇B 作為下一跳，但實(shí)際上C 為當(dāng)前距離D 最近的節(jié)點(diǎn)。

圖1 地理位置路由中位置信息示意圖

目前在VANET 路由算法中，常用2 種方法獲取車輛位置信息:(1)利用導(dǎo)航系統(tǒng)獲知一條預(yù)先設(shè)定好的車輛運(yùn)行軌跡，如Geo +DTN 和GeOpps［9］。這種方法的缺陷是，導(dǎo)航系統(tǒng)給出的行進(jìn)路線通常不是最優(yōu)路線，而且司機(jī)必須沿著該固定線路行駛。另外，GPS 的可用性和精度問題往往被忽視［10］。(2)基于一定的運(yùn)動(dòng)模型進(jìn)行假設(shè)或推測(cè)，如AGF［11］。由于運(yùn)動(dòng)模型的固有缺陷，這種方法得到的預(yù)測(cè)精度往往很低，對(duì)路由決策的幫助有限，因此使用卡爾曼預(yù)測(cè)器進(jìn)行高精度車輛位置預(yù)測(cè)的方法輔助路由協(xié)議。

卡爾曼預(yù)測(cè)器是Kalman 提出的遞歸預(yù)測(cè)器［12］，用于從一系列噪聲中遞歸地估計(jì)線性離散系統(tǒng)的狀態(tài)［13］。卡爾曼預(yù)測(cè)器無需考慮多個(gè)過去的輸出信號(hào)，其原理是通過現(xiàn)時(shí)狀態(tài)觀測(cè)值Yk修正現(xiàn)時(shí)狀態(tài)預(yù)測(cè)值，根據(jù)修正結(jié)果來預(yù)測(cè)下一時(shí)刻狀態(tài)預(yù)測(cè)值Xk+1，保證其同下一時(shí)刻狀態(tài)實(shí)際值的均方誤差最小。

考慮一個(gè)給定初始狀態(tài)為X0的離散時(shí)間動(dòng)態(tài)系統(tǒng):

其中，wk和vk是獨(dú)立白噪聲過程，在k 時(shí)刻對(duì)應(yīng)的協(xié)方差矩陣為Qk和Rk。

遞歸的卡爾曼預(yù)測(cè)方程為:

預(yù)測(cè)修正系數(shù)為:

預(yù)測(cè)均方誤差為:

為預(yù)測(cè)車輛位置，假設(shè)網(wǎng)絡(luò)中的每一輛車都裝備了GPS 接收器，從而可知自身當(dāng)前的位置。車輛運(yùn)動(dòng)可以描述為由二維位置Pos=［x y］T和速度向量Vel=［vxvy］T組成的狀態(tài)向量X=［x y vxvy］T?？梢钥闯觯瑒?dòng)態(tài)狀態(tài)方程即是一個(gè)航位推演過程，預(yù)測(cè)器用同一時(shí)刻GPS 接收值即觀測(cè)值來對(duì)推演結(jié)果進(jìn)行修正。在實(shí)際計(jì)算中，由于動(dòng)態(tài)模型不夠精確描述真實(shí)運(yùn)動(dòng)過程、隨時(shí)間累積增加的取整誤差等原因，狀態(tài)預(yù)測(cè)誤差可能會(huì)變得很大?？柭A(yù)測(cè)的結(jié)果可以認(rèn)為是觀測(cè)模型新測(cè)量值和基于先前所有舊測(cè)量值的預(yù)測(cè)之間的權(quán)重調(diào)節(jié)值。為提高預(yù)測(cè)精度，達(dá)到降低舊信息的權(quán)重、提高新測(cè)量值的權(quán)重，采用記憶衰減法，給預(yù)測(cè)均方差矩陣P 乘以一個(gè)衰減因子S ＞1。

為驗(yàn)證卡爾曼預(yù)測(cè)車輛位置的精度，利用真實(shí)車輛軌跡計(jì)算其預(yù)測(cè)位置，并衡量預(yù)測(cè)位置與真實(shí)位置的誤差。實(shí)驗(yàn)結(jié)果如表1 所示。約有99%的預(yù)測(cè)誤差小于30 m，遠(yuǎn)小于車輛的通信范圍距離，這保證了基于卡爾曼預(yù)測(cè)的位置信息的可用性。

表1 卡爾曼預(yù)測(cè)精確度測(cè)試結(jié)果

3 基于卡爾曼預(yù)測(cè)的混合路由

在地理位置路由GPSR 的基礎(chǔ)上，結(jié)合DTN 路由在稀疏網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)膬?yōu)點(diǎn)，提出一種基于位置預(yù)測(cè)的混合路由算法KPHR。KPHR 是一種地理位置路由和DTN 路由的混合路由算法，可以在城市場(chǎng)景中高效的工作。KPHR 有和GPSR 類似的貪婪模式和邊緣模式。除此之外，基于卡爾曼預(yù)測(cè)器的車輛位置預(yù)測(cè)和鏈路調(diào)度感知緩存保證了KPHR 在城市場(chǎng)景中具有高效性。

3.1 假設(shè)

假設(shè)每一個(gè)節(jié)點(diǎn)都裝備了導(dǎo)航系統(tǒng)來獲取自己的位置和速度，發(fā)送節(jié)點(diǎn)可以通過位置服務(wù)獲知目的節(jié)點(diǎn)的位置和速度，節(jié)點(diǎn)會(huì)周期性廣播HELLO 分組發(fā)現(xiàn)鄰居節(jié)點(diǎn)。

3.2 車輛實(shí)時(shí)位置預(yù)測(cè)

網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)設(shè)置如第2 節(jié)所述的卡爾曼預(yù)測(cè)器。源節(jié)點(diǎn)通過位置發(fā)現(xiàn)服務(wù)獲得目的節(jié)點(diǎn)的位置信息Pos 和速度信息Vel。節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組和HELLO 分組中帶有本節(jié)點(diǎn)的位置信息、速度信息以及發(fā)送時(shí)間。每個(gè)節(jié)點(diǎn)上的卡爾曼預(yù)測(cè)器利用這些信息，周期性地計(jì)算其目標(biāo)節(jié)點(diǎn)和鄰居節(jié)點(diǎn)在當(dāng)前時(shí)刻的預(yù)測(cè)位置和速度向量。在接下來的轉(zhuǎn)發(fā)決策中，任何要求位置和速度信息的計(jì)算，都使用卡爾曼預(yù)測(cè)器計(jì)算結(jié)果，這樣可以有效解決節(jié)點(diǎn)運(yùn)動(dòng)信息在路由決策中時(shí)效性低的問題。

3.3 鏈路調(diào)度感知的分組緩存

城市場(chǎng)景中節(jié)點(diǎn)分布極其不均，發(fā)送節(jié)點(diǎn)和目的節(jié)點(diǎn)常處于不同網(wǎng)絡(luò)劃分中，造成數(shù)據(jù)不可達(dá)，可以借助于DTN 網(wǎng)絡(luò)存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)的概念克服該問題。在每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)FIFO 隊(duì)列來緩存那些由于缺乏合適轉(zhuǎn)發(fā)鄰居而將要被丟棄的分組。每個(gè)分組維護(hù)一個(gè)計(jì)時(shí)器來標(biāo)明在隊(duì)列中的生存時(shí)間。緩存隊(duì)列會(huì)周期性檢查分組計(jì)時(shí)器并丟棄超時(shí)分組。

每當(dāng)節(jié)點(diǎn)遇見一個(gè)新鄰居節(jié)點(diǎn)，就計(jì)算從該鄰居到目的節(jié)點(diǎn)的距離distnb和角度θnb，以及從本節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離distn和角度θn。定義傳輸增益為θn與θnb之間的差和distn與distnb之間的差權(quán)重之后的和。較高的傳輸增益表明該分組有更高的概率傳輸至目的節(jié)點(diǎn)。節(jié)點(diǎn)按照傳輸增益將緩存中的分組按降序排序，并依次發(fā)送給鄰居節(jié)點(diǎn)直至傳輸增益為負(fù)。節(jié)點(diǎn)鄰居發(fā)現(xiàn)過程的偽代碼具體如下:

3.4 KPHR 轉(zhuǎn)發(fā)策略

當(dāng)節(jié)點(diǎn)收到一個(gè)分組時(shí)，首先檢查該分組的目的節(jié)點(diǎn)是否在自己的鄰居表中。這會(huì)大大減輕目的節(jié)點(diǎn)離開初始位置的影響。然后節(jié)點(diǎn)會(huì)采用與GPSR 算法的貪婪模式和邊緣模式類似的規(guī)則處理該分組。該步驟所使用的節(jié)點(diǎn)位置和速度的計(jì)算都使用預(yù)測(cè)值，具體轉(zhuǎn)發(fā)策略如下:

(1)節(jié)點(diǎn)檢查自身是否是目的節(jié)點(diǎn)。如果是，則節(jié)點(diǎn)接收該分組。

(2)否則節(jié)點(diǎn)檢查該分組的目的節(jié)點(diǎn)是否是當(dāng)前節(jié)點(diǎn)的一個(gè)鄰居。如果是，當(dāng)前節(jié)點(diǎn)發(fā)送該分組至目的節(jié)點(diǎn)。

(3)否則節(jié)點(diǎn)檢查該分組的轉(zhuǎn)發(fā)模式(貪婪模式或邊緣模式)，并依照相應(yīng)的轉(zhuǎn)發(fā)策略計(jì)算下一跳節(jié)點(diǎn)。如果下一跳節(jié)點(diǎn)存在，當(dāng)前節(jié)點(diǎn)發(fā)送該分組至下一跳節(jié)點(diǎn)。

(4)否則將該分組存入緩存隊(duì)列。當(dāng)遇見一個(gè)新的鄰居節(jié)點(diǎn)時(shí)，按照3.3 節(jié)所述的節(jié)點(diǎn)發(fā)現(xiàn)過程進(jìn)行轉(zhuǎn)發(fā)。

4 性能分析

本節(jié)將KPHR 的性能和GPSR、帶緩存的GPSR(GPSR+buffer)進(jìn)行比較，使用分組投遞率和平均端到端時(shí)延作為算法性能評(píng)價(jià)指標(biāo)。GPSR 是一種典型的地理位置路由。GPSR+buffer 是在GPSR 的邊緣模式下加入緩存，在貪婪模式或邊緣模式下無法計(jì)算出下一跳節(jié)點(diǎn)時(shí)將分組存入緩存，直到能夠使用貪婪模式進(jìn)行轉(zhuǎn)發(fā)為止，是一種簡(jiǎn)單的混合路由算法。本文使用開源的真實(shí)車輛交通生成器VanetMobiSim 生成真實(shí)車輛移動(dòng)軌跡。利用TIGER (U.S.Census Bureau's Topologically Integrated Geographic Encoding and Referencing)數(shù)據(jù)庫中的真實(shí)地圖拓?fù)洌x取蒙哥馬利郡的一塊2 000 m ×1 000 m 的街區(qū)，使該拓?fù)淇梢栽贜S-2中使用。設(shè)置20 條CBR 流并隨機(jī)選取發(fā)送節(jié)點(diǎn)和目的節(jié)點(diǎn)。發(fā)送節(jié)點(diǎn)在仿真開始30 s 后開始持續(xù)發(fā)送60 s 數(shù)據(jù)。在所有分組發(fā)送后，仿真仍將運(yùn)行一段時(shí)間避免出現(xiàn)因仿真時(shí)間結(jié)束而分組未達(dá)的狀況。對(duì)任一特定的網(wǎng)絡(luò)場(chǎng)景設(shè)置，均采用5 個(gè)不同的隨機(jī)種子進(jìn)行仿真，最終結(jié)果取平均值，具體仿真參數(shù)設(shè)置如表2 所示。

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

圖2 對(duì)比了節(jié)點(diǎn)移動(dòng)速度為20 km/h～50 km/h時(shí)，不同節(jié)點(diǎn)數(shù)目下GPSR，GPSR +buffer 和KPHR的分組投遞率。3 種算法各自的分組投遞率開始都隨著節(jié)點(diǎn)數(shù)目的增加而增長(zhǎng)，直到節(jié)點(diǎn)數(shù)目為150時(shí)出現(xiàn)下降。這是因?yàn)榫W(wǎng)絡(luò)的鏈路容量有限，節(jié)點(diǎn)之間的控制分組開銷過大，造成網(wǎng)絡(luò)擁塞。因?yàn)橛蟹纸M緩存的存在，任意節(jié)點(diǎn)數(shù)目下KPHR 和GPSR+buffer 的分組投遞率都高于GPSR。但GPSR +buffer 在DTN 階段時(shí)只是簡(jiǎn)單地按貪婪條件選取轉(zhuǎn)發(fā)節(jié)點(diǎn);而KPHR 充分利用了節(jié)點(diǎn)位置信息計(jì)算投遞增益，可以選擇更合適的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，從而提升網(wǎng)絡(luò)整體效率，因而投遞率遠(yuǎn)高于只有簡(jiǎn)單緩存功能的GPSR+buffer。另外，KPHR 在每跳中都會(huì)判斷目的節(jié)點(diǎn)是否在當(dāng)前節(jié)點(diǎn)的鄰居表內(nèi)，從而減輕因目的節(jié)點(diǎn)移動(dòng)遠(yuǎn)離初始位置造成不可達(dá)的影響，也可以提升分組投遞率。

圖2 不同節(jié)點(diǎn)數(shù)量下的分組投遞率

圖3、圖4 分別對(duì)比了節(jié)點(diǎn)數(shù)目為100 時(shí)，不同節(jié)點(diǎn)運(yùn)動(dòng)速度下3 種算法的平均端到端時(shí)延和分組投遞率。可以看出隨著節(jié)點(diǎn)運(yùn)動(dòng)速度的增加，3 種算法各自的平均端到端時(shí)延都有所增加，而分組投遞率都有所降低。與GPSR+buffer 相比，KPHR 的平均端到端時(shí)延相差不大，但增長(zhǎng)更緩慢。而任意節(jié)點(diǎn)運(yùn)動(dòng)速度下，KPHR 的分組投遞率遠(yuǎn)高于GPSR 和GPSR+buffer。

圖3 不同節(jié)點(diǎn)運(yùn)動(dòng)速度下的平均端到端時(shí)延

圖4 不同節(jié)點(diǎn)運(yùn)動(dòng)速度下的分組投遞率

5 結(jié)束語

本文針對(duì)VANET 城市場(chǎng)景中，道路拓?fù)湎拗坪蛙囕v高速移動(dòng)導(dǎo)致的網(wǎng)絡(luò)間歇連通性給路由設(shè)計(jì)帶來的巨大挑戰(zhàn)，綜合考慮了地理位置路由在連通網(wǎng)絡(luò)中端到端時(shí)延較低、DTN 路由在稀疏網(wǎng)絡(luò)中投遞率較高的優(yōu)點(diǎn)，結(jié)合卡爾曼預(yù)測(cè)器的位置預(yù)測(cè)，充分利用車輛地理位置輔助轉(zhuǎn)發(fā)決策，在GPSR 的基礎(chǔ)上提出基于卡爾曼預(yù)測(cè)的混合路由算法KPHR。仿真結(jié)果表明，與GPSR 和GPSR +buffer 相比，KPHR在分組投遞率和端到端時(shí)延方面性能較好。下一步工作將考慮網(wǎng)絡(luò)連通性的影響，對(duì)網(wǎng)絡(luò)連通性進(jìn)行建模研究分析，優(yōu)化地理位置路由模式和DTN 模式之間的切換點(diǎn)，進(jìn)一步改善VANET 的傳輸性能。

［1］徐會(huì)彬，夏 超.VANETs 路由綜述［J］.計(jì)算機(jī)應(yīng)用研究，2013，30(1):1-6.

［2］Gerla M，Kleinrock L.Vehicular Networks and the Future of the Mobile Internet［J］.Computer Networks，2011，55(2):457-469.

［3］Wu Yuchen，Zhu Yanmin，Li Bo.Trajectory Improves Data Delivery in Vehicular Networks［C］//Proceedings of INFOCOM'11.Shanghai，China:［s.n.］，2011:2183-2191.

［4］Lee K，Yi Yung，Jeong J，et al.Max-contribution:On Optimal Resource Allocation in Delay Tolerant Networks［C］// Proceedings of INFOCOM'10.［S.l.］:IEEE Press，2010:1-9.

［5］Zhu Hongzi，Chang Shan，Li Minglu，et al.Exploiting Temporal Dependency for Opportunistic Forwarding in Urban Vehicular Networks［C］//Proceedings of INFOCOM'11.［S.l.］:IEEE Press，2011:2192-2200.

［6］Karp B，Kung H T.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks［C］//Proceedings of the 6th Annual International Conference on Mobile Computing and Networking.New York，USA:ACM Press，2000:243-254.

［7］Cheng P C，Weng J T，Tung L C，et al.GeoDTN +Nav:A Hybrid Geographic and DTN Routing with Navigation Assistance in Urban Vehicular Networks［J］.Mobile Networks and Applications，2010，15(1):61-82.

［8］Kim Y，Lee J J，Helmy A.Impact of Location Inconsistencies on Geographic Routing in Wireless Networks［C］//Proceedings of the 6th ACM International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems.San Diego，USA:ACM Press，2003:124-127.

［9］Leontiadis I，Mascolo C.Geopps:Geographical Opportunistic Routing for Vehicular Networks［C］//Proceedings of IEEE International Symposium on World of Wireless，Mobile and Multimedia Networks.［S.l.］:IEEE Press，2007:1-6.

［10］Leontiadis I，Costa P，Mascolo C.Extending Access Point Connectivity Through Opportunistic Routing in Vehicular Networks［C］//Proceedings of INFOCOM'10.［S.l.］:IEEE Press，2010:1-5.

［11］Naumov V，Baumann R，Gross T.An Evaluation of Intervehicle Ad Hoc Networks Based on Realistic Vehicular Traces［C］//Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing.Florence，Italy:ACM Press，2006:108-119.

［12］Kalman R E.A New Approach to Linear Filtering and Prediction Problems［J］.Journal of Basic Engineering，1960，82(1):35-45.

［13］Moghaddam B A，Haleh H，Ebrahimijam S.Forecasting Trend and Stock Price with Adaptive Extended Kalman Filter Data Fusion［C］//Proceedings of IEEE International Conference on Economics and Finance Research.Singapore:［s.n.］，2011:119-123.