劉麗萍, 裴金金

(天津大學 電氣與自動化工程學院，天津 300072)

基于時延期望的車載自組織網絡機會路由算法

劉麗萍, 裴金金

(天津大學電氣與自動化工程學院，天津300072)

針對車載自組織網絡中，車輛隨機運動的環(huán)境下源節(jié)點、目的節(jié)點均為運動中的車輛時數(shù)據(jù)傳輸效率低下的問題，提出了一種基于時延期望的機會路由算法。算法融合了概率論和統(tǒng)計學知識，綜合考慮目的節(jié)點軌跡預測和數(shù)據(jù)時效性兩方面需求，得到時延期望參數(shù)，以該參數(shù)作為整個數(shù)據(jù)傳輸過程中每一次數(shù)據(jù)轉發(fā)中繼節(jié)點選擇標準，保證數(shù)據(jù)能夠及時、有效地由移動中的源節(jié)點轉發(fā)至移動中的目的節(jié)點。

車載自組織網絡； 時延期望； 機會路由算法

0 引 言

車載自組織(Ad Hoc)網絡是以車輛上安裝了智能計算機系統(tǒng)、無線通信設備以及車輛傳感器和全球定位系統(tǒng)(GPS)等設備為基礎構建的無線車輛通信網絡[1],是移動Ad Hoc網絡的一個子類。車載自組織網絡中,車輛節(jié)點分布不均勻并持續(xù)運動導致網絡拓撲結構變化快、鏈路可用時間短,且應用信息具有實時性要求,使車載自組織網絡數(shù)據(jù)傳輸面臨很大挑戰(zhàn)。

目前,車載自組織網絡路由協(xié)議主要分為三類：基于拓撲的路由協(xié)議、基于地圖的路由協(xié)議、基于地理位置的路由協(xié)議[2]?；谕負涞穆酚蓞f(xié)議中,所有節(jié)點地位平等,網絡拓撲結構通過節(jié)點的路由表來維護,每個節(jié)點既要參與信息的轉發(fā)又要維護路由表,該協(xié)議又分為先應式路由和反應式路由兩類,按需距離矢量(As Hoc on-demand distance vector,AODV)[3]路由協(xié)議是典型的反應式路由協(xié)議,源節(jié)點與目的節(jié)點通信前先建立一條可靠的路徑,路由選擇基于網絡拓撲,但路由有效期很短?；诘貓D的路由協(xié)議,將車輛位置信息在地圖中定位,再結合電子導航地圖提供的豐富道路信息,由節(jié)點集、道路集、十字路口集作為計算最優(yōu)轉發(fā)路徑的判據(jù),全局狀態(tài)路由(global state routing,GSR)[4]協(xié)議利用電子地圖技術和Dijkstm算法來計算一跳到達目的節(jié)點的最短路徑,即源節(jié)點通過電子地圖計算好一個到目的節(jié)點的十字路口序列,數(shù)據(jù)將沿著這條路徑傳至目的節(jié)點。貪婪周邊無狀態(tài)路由(greedy perimeter stateless routing,GPSR)[5]協(xié)議是基于地理位置的路由協(xié)議,采用貪婪轉發(fā)和周邊轉發(fā)的算法相結合的一種轉發(fā)策略,每個節(jié)點需要在一定周期內廣播自身位置信息,源節(jié)點在進行數(shù)據(jù)包轉發(fā)時,需要計算鄰居節(jié)點與目的節(jié)點的距離[6],選擇離目的節(jié)點更近的鄰居節(jié)點作為下一跳中繼節(jié)點。

道路車輛密度和速度的快速變化帶來的不穩(wěn)定網絡拓撲使得GPSR協(xié)議出現(xiàn)路由選擇錯誤和路由中斷問題,由于數(shù)據(jù)源和目的地均處于隨機運動中的車輛,軌跡不能預設,使得網絡拓撲變化更快,導致鏈路可用時間更短,給車輛節(jié)點之間數(shù)據(jù)轉發(fā)帶來更大困難。

本文提出了一種基于時延期望的機會路由協(xié)議,基于概率論和統(tǒng)計學中的期望原理,將數(shù)據(jù)當前所在車輛節(jié)點到目的節(jié)點將要經過的交叉路口的時延期望作為路由中繼節(jié)點選擇依據(jù),根據(jù)實時的交通狀況進行調整,獲得較高的數(shù)據(jù)傳輸成功率和較低的數(shù)據(jù)傳輸時延。

1 系統(tǒng)模型

1.1 網絡模型

車載自組織網絡中,車輛節(jié)點間可進行通信,遠距離的車輛節(jié)點間可以通過中繼節(jié)點多跳轉發(fā)的方式進行通信[7]。網絡構架中存在3種重要的實體：車輛、路口和路段,前者處于運動中,后兩者相對固定。數(shù)據(jù)轉發(fā)[8]完全依靠行駛中車輛的存儲、攜帶和轉發(fā)完成,轉發(fā)過程為：

1)計算攜帶數(shù)據(jù)車輛與其他車輛的距離。若不存在鄰居節(jié)點,由該車輛繼續(xù)攜帶數(shù)據(jù)；否則,進行下一步判斷。

2)若攜帶數(shù)據(jù)車輛一跳通信范圍內存在鄰居節(jié)點,選擇最優(yōu)的鄰居節(jié)點作為下一跳中繼節(jié)點,進行數(shù)據(jù)轉發(fā)。

3)數(shù)據(jù)由源節(jié)點轉發(fā)至目的節(jié)點,轉發(fā)過程結束。

1.2 移動模型

為了更接近真實的城市道路場景[9],準確反映車輛運動規(guī)律,包括節(jié)點位置、速度、運動時間等,并考慮到仿真模型精確性需求,設計了一種簡單且符合實際的道路模型[10]。如圖1所示,首先,采取方格形道路,路口分為十字路口、丁字路口和L形路口。車輛運動軌跡受拓撲結構限制,只能在定義的路段上沿道路直線行駛,每次連續(xù)運動均由路段的起始點開始,運動到路段的終止點結束,然后,隨機選擇下一條路段開始新的運動。車輛速度分為4個等級,每個車輛的速度和加速度隨機。將整個車載網絡道路地圖建模成一個有向圖G(J,E),J為地圖上交叉路口的集合,E為連接交叉路口的道路集合。兩個交叉路口間的可行路徑path及路徑長度D可由Dijkstra算法直接獲得。在交通圖G中,N和P為非常重要的2個參數(shù),N為車輛集合,ni∈N為車輛集合中的某一個車輛,P為車輛行駛軌跡集合,pni∈P為車輛ni的行使軌跡,nsour為源車輛節(jié)點,ntar為目標車輛節(jié)點,車輛在時刻t的位置被定義為pni(t),也可用坐標(xni(t),yni(t))表示其在地圖中的位置,其中x和y分別為位置的經度和緯度。對于車輛運動特點,V為各車輛行駛速度集合,vi∈V為車輛ni的速度,A為各車輛加速度集合,ai∈A表示車輛ni的加速度,道路限速為Vm。

圖1 車載自組織網絡構架

2 算法設計

2.1 問題分析

1)數(shù)據(jù)源和目的地均為處于運動中的車輛,網絡拓撲變化更快,導致鏈路可用時間更短。

2)車輛沿道路隨機運動,其軌跡無法預設,給車輛軌跡預測增加難度。

3)車載自組織網絡的大部分應用均有實時性的要求,故數(shù)據(jù)需在其有效期(time to live,TTL)內到達目的節(jié)點。

針對以上問題,采用基于時延期望的車載自組織網絡機會路由算法,實現(xiàn)車載自組織網絡中高效率的V2V數(shù)據(jù)傳輸。時延期望指數(shù)據(jù)當前所在車輛節(jié)點到目的節(jié)點將要經過的交叉路口的時延期望值,為了提高鏈路的準確性,需要對目的節(jié)點的運動進行預測,又因為車輛節(jié)點完全沿道路隨機運動,軌跡不可預設,僅根據(jù)目的節(jié)點運動速度和運動方向對其進行一步交叉路口預測。為了滿足數(shù)據(jù)的實時性要求,又加入了數(shù)據(jù)時效性參數(shù),時延期望即目的節(jié)點軌跡預測和數(shù)據(jù)時效性綜合考慮得出的結果。

算法在如下假設基礎上進行：1)車輛節(jié)點均配置了無線通信設備,任何2個車輛節(jié)點在其通信范圍內,可彼此通信；2)車輛節(jié)點配置全球定位系統(tǒng)(GPS)定位設備,能實時獲取自身位置信息；3)向目的節(jié)點發(fā)送數(shù)據(jù)前,源節(jié)點通過位置服務協(xié)議獲取目的節(jié)點的當前位置及速度；4)所有車輛節(jié)點能獲取自身當前位置所在信息,包括道路及道路長度、交叉路口及交叉路口的位置、道路的拓撲結構。

2.2 運動建模

根據(jù)車輛節(jié)點的移動特點,通過其運動速度、加速度、方向等數(shù)據(jù),即可得出有效鏈路。對一個車輛節(jié)點,速度分別為v,加速度為a,道路限速為Vm,則其在[0,t]時刻運行路程為

(1)

在同一路段上,t時刻車輛節(jié)點i和j的距離為

Di,j(t)=Si(t)-Sj(t)+D0

(2)

如果Di,j≤R,則在t時刻內鏈路有效,兩車輛節(jié)點之間可以通信；否則,鏈路無效,自動斷開鏈路鏈接。

在圖1所示的網絡移動模型中,車輛節(jié)點運動軌跡受拓撲結構限制,在路段上沿道路直線行駛,某一路段的運動結束后,隨機選擇下一條路段開始新的運動。車輛節(jié)點在路口a選擇下一條路段方向的概率為

(3)

2.3 基于時延期望的機會路由算法

算法用于將數(shù)據(jù)從移動中的源節(jié)點傳遞至移動的目的節(jié)點,而數(shù)據(jù)傳輸?shù)倪^程要求完全依靠行駛中車輛的存儲、攜帶和機會轉發(fā)完成。因此,尋找每次數(shù)據(jù)轉發(fā)的最佳中繼節(jié)點是本文算法的最重要的組成部分。在整個數(shù)據(jù)轉發(fā)過程中,時延期望即目的節(jié)點軌跡預測和數(shù)據(jù)時效性綜合考慮得出的結果。

根據(jù)目的節(jié)點運動速度和運動方向對其進行一步交叉路口預測,此時得到時延期望為

(4)

式中Di,a(t)為車輛與其將要經過的路口的距離；兩個路口之間的最短路徑長度：Da,b(由最短路徑Dijkstra算法求得)。

由于數(shù)據(jù)的傳輸有實時性的要求,需在其TTL內到達目的節(jié)點。故在數(shù)據(jù)轉發(fā)過程中,需要對數(shù)據(jù)進行有效性判斷,若數(shù)據(jù)已過期,則舍棄該數(shù)據(jù)；否則,繼續(xù)進行轉發(fā)。定義數(shù)據(jù)有效性為

(5)

為了保證車載自組織網絡中數(shù)據(jù)能夠及時、有效地由移動中的源節(jié)點轉發(fā)至移動中的目的節(jié)點,需要綜合目的節(jié)點軌跡預測和數(shù)據(jù)時效性兩方面來考慮,此時,能夠得到時延期望

EETi,b(t)=ETi,b(t)×MI(t)

(6)

本文算法框架描述如下：

1)周期性廣播目的節(jié)點運動信息。

2)攜帶數(shù)據(jù)車輛節(jié)點尋找其鄰居節(jié)點。

3)攜帶數(shù)據(jù)的車輛節(jié)點及其鄰居節(jié)點分別計算自身與目的節(jié)點的時延期望EETi,b(t)。

4)由步驟(3)計算結果判斷當前車輛節(jié)點繼續(xù)攜帶數(shù)據(jù)前行還是將數(shù)據(jù)轉發(fā)給鄰居節(jié)點。

5)當前攜帶數(shù)據(jù)的車輛節(jié)點檢查數(shù)據(jù)的有效性,若數(shù)據(jù)已經無效,則該數(shù)據(jù)將被丟棄。

6)重復上述步驟,直到數(shù)據(jù)被轉發(fā)至目的節(jié)點或者數(shù)據(jù)失效為止。

采用EETi,b(t)作為選擇中繼節(jié)點的衡量標準,即在相同情況下,擁有更小時延期望EETi,b(t)值的車輛節(jié)點能更快地將數(shù)據(jù)攜帶至目的節(jié)點。在整個車載自組織網絡中,將整個數(shù)據(jù)轉發(fā)過程中遇到的車輛數(shù)目標記為n=|Vmet|,將數(shù)據(jù)更新的次數(shù)標記為m=|t|。在每一次相遇過程中,計算一次EETi,b(t)值的復雜度為O(m),而每個備選的中繼節(jié)點均需要進行一次該的計算,在整個數(shù)據(jù)轉發(fā)的過程中,會發(fā)生n次這樣的相遇過程。因此,基于時延期望的路由算法復雜度為O(mn)。

3 性能分析

通過車輛數(shù)目的變化對數(shù)據(jù)傳輸時延、數(shù)據(jù)傳輸成功率、平均轉發(fā)次數(shù)3方面的影響進行仿真分析。

針對每個車載自組織網絡中的車輛數(shù)目,設置不同的隨機種子數(shù)以進行100次實驗得到算法的性能結果。每一組實驗中,車輛的軌跡會隨著隨機運動種子的不同而不同。實驗中選取3km×3km范圍內矩形街區(qū)的36個路口,設置車輛節(jié)點通信距離為100m,數(shù)據(jù)有效期為500s的場景下進行實驗,仿真時間為1000s,車輛數(shù)目為20,40,…,180,200,車輛最小速度為5m/s,車輛最大速度為25m/s。

3.1 數(shù)據(jù)傳輸時延

由圖2可知,隨著車輛數(shù)目N的增大,2種路由協(xié)議的平均傳輸時延均有一定的降低,因為當車輛數(shù)目增加時,單位面積內節(jié)點密度相應增加,有更多的鄰居節(jié)點參與轉發(fā),車輛通信時出現(xiàn)越來越少的中斷鏈路。同時,仿真結果表明：在不同的車輛數(shù)目下,算法較傳統(tǒng)的GPSR路由協(xié)議具有著更低的數(shù)據(jù)傳輸時延,在整個數(shù)據(jù)傳輸過程中,每次尋找最佳中繼節(jié)點時均要綜合考慮目的節(jié)點軌跡預測和數(shù)據(jù)時效性兩方面要求,根據(jù)時延期望對中繼節(jié)點進行選擇,相對于傳統(tǒng)的GPSR協(xié)議的貪婪轉發(fā)方式,有效提高了中繼節(jié)點選擇的正確率,從而直接降低了數(shù)據(jù)傳輸時延。

圖2 數(shù)據(jù)傳輸時延

3.2 數(shù)據(jù)傳輸成功率

數(shù)據(jù)的成功傳輸率指目的節(jié)點接收到的數(shù)據(jù)包與源節(jié)點發(fā)送的數(shù)據(jù)包的比例。由圖3可知,2種路由協(xié)議的數(shù)據(jù)傳輸成功率隨車輛密度增大均有所增加,因為車輛數(shù)目增加,直接表現(xiàn)為能夠參與數(shù)據(jù)轉發(fā)的鄰居節(jié)點數(shù)目增加,路由出現(xiàn)鏈路中斷的現(xiàn)象減少?；跁r延期望的機會路由算法數(shù)據(jù)傳輸成功率明顯高于傳統(tǒng)的GPSR協(xié)議,主要原因是新的路由協(xié)議在轉發(fā)過程中充分考慮了車輛運動速度、方向等問題,對目的節(jié)點運動進行準確預測,對已經失效的數(shù)據(jù)及時舍棄,及時減輕網絡負載,從而達到提高數(shù)據(jù)傳輸成功率的目的。

圖3 數(shù)據(jù)傳輸成功率

3.3 平均轉發(fā)次數(shù)

轉發(fā)次數(shù)是數(shù)據(jù)由源節(jié)點成功傳輸至目的節(jié)點過程中被轉發(fā)的跳數(shù)。轉發(fā)次數(shù)越少,說明數(shù)據(jù)傳輸過程中的決策越具備針對性。由圖4可知,隨著車輛密度增大,2種算法的平均轉發(fā)次數(shù)均在增長,因為車輛密度增加導致數(shù)據(jù)傳輸過程中所遇車輛數(shù)目隨之增加。但本文算法有效解決了傳統(tǒng)GPSR協(xié)議盲目轉發(fā)的問題,使其平均轉發(fā)次數(shù)更少,從而有效縮短了路由長度,更具針對性的完成數(shù)據(jù)傳輸過程。

圖4 平均轉發(fā)次數(shù)

4 結束語

提出了一種基于時延期望的機會路由算法。該算法融合了概率論和統(tǒng)計學知識,綜合考慮目的節(jié)點軌跡預測和數(shù)據(jù)時效性兩方面需求,得到時延期望參數(shù),以該參數(shù)作為整個數(shù)據(jù)傳輸過程中每一次數(shù)據(jù)轉發(fā)中繼節(jié)點選擇標準,保證數(shù)據(jù)能夠及時、有效地由移動中的源節(jié)點轉發(fā)至移動中的目的節(jié)點。仿真結果表明：與傳統(tǒng)的GPSR相比,在不同車輛密度情況下,算法在數(shù)據(jù)傳輸時延、傳輸成功率及平均轉發(fā)次數(shù)均有顯著提升。

[1] 馮 勇,梁 浩.車載自組織網絡中一種有效的匿名認證方法[J].計算機工程與應用,2010,46(23):126-128.

[2] 李萬磊,朱梅麗,謝 波,等.高速公路環(huán)境下VANET路由性能研究[J].計算機工程與設計,2011,32(6):2163-2172.

[3] Perkins C E,Royer E M.Ad Hoc on demand distance vector routing[C]∥Proceeding of the2nd IEEE Workshop on Mobile Computing Systems and Applications,Menlo Park:IEEE,1999:90-100.

[4] Lochert C,Hartenstein H,Tian J,et al.A routing strategy for vehicular Ad Hoc networks in city environments[C]∥Proceeding of IEEE Intelligent Vehicles Symposium,IV’03,IEEE,2003:156-161.

[5] Karp B,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proceeding of the6th Annual International Conference on Mobile Computing and Networking,MOBICOM’00, IEEE,2000:243-254.

[6] 盧 穎,陳日莉.基于多描述編碼和距離的車載網DSR路由技術研究[J].傳感器與微系統(tǒng),2011,30(10):15-18.

[7] 張國慶,慕德俊,洪 亮,等.城市場景下VANET路由協(xié)議大規(guī)模仿真研究[J].計算機仿真,2009,26(8):249-252.

[8] 王金龍,王呈貴,吳啟暉,等. Ad Hoc 移動無線網絡[M].北京:國防工業(yè)出版社,2004.

[9] 邁爾斯.智能交通系統(tǒng)手冊[M].北京:人民交通出版社,2007.

[10] 劉志遠,陳 晶,羅惠霞,等.城市環(huán)境下基于地理位置自適應的車載網絡路由協(xié)議[J].武漢大學學報:理學版,2014,60(3):201-210.

OpportunisticroutingalgorithmforvehicularAdHocnetworksbasedondelayexpection

LIU Li-ping, PEI Jin-jin

(SchoolofElectricalEngineering&Automation,TianjinUniversity,Tianjin300072,China)

In vehicular Ad Hoc networks,when vehicles are moving randomly,aiming at problem that efficiency of data transmission is low,propose an opportunistic routing algorithm based on time delay expection to against the situation when both the source node and the destination node are moving.Our opportunistic routing algorithm combines the theory of probability and statistics knowledge,to get the time delay expection parameters, the opportunistic routing algorithm incorporates the trajectory prediction of the destination node timeliness requirements of data packet.When the delay expection parameters are regarded as the selection standard of data packet’s next relay node,can ensure that the data packet can be forwarded from the moving source node to the moving destination node timely and effectively.

vehicular Ad Hoc networks； time delay expection； opportunistic routing algorithm

10.13873/J.1000—9787(2017)10—0150—04

2016—10—31

TP 393

A

1000—9787(2017)10—0150—04

劉麗萍(1979-),女,博士,副教授,從事無線傳感器網絡、網絡優(yōu)化研究工作。裴金金(1991-),女,通訊作者,碩士研究生,研究方向為無線傳感器網絡、車載自組織網絡,E—mail:pw1102@126.com。