基于混合信息和冗余傳輸的VANETs路由協議

宋 亮, 韓江洪,2, 劉征宇

(1.合肥工業大學 計算機與信息學院,安徽 合肥 230009; 2.安全關鍵工業測控技術教育部工程研究中心,安徽 合肥 230009; 3.合肥工業大學 機械工程學院,安徽 合肥 230009)

基于混合信息和冗余傳輸的VANETs路由協議

宋 亮1, 韓江洪1,2, 劉征宇2,3

(1.合肥工業大學 計算機與信息學院,安徽 合肥 230009; 2.安全關鍵工業測控技術教育部工程研究中心,安徽 合肥 230009; 3.合肥工業大學 機械工程學院,安徽 合肥 230009)

車輛節點的快速移動導致網絡拓撲頻繁變化和無線鏈路質量不穩定,這為車載自組織網絡(vehicular ad-hoc networks,VANETs)路由協議的研究帶來挑戰。為了應對這些挑戰,文章提出了基于混合信息和冗余傳輸的VANETs路由協議。針對城市環境下道路的特點抽象出一個以交叉路口為頂點,以路段為邊的無向圖,并依托部署在路口的固定節點收集交通和網絡的實時信息為每條邊賦予權值,然后運用Dijkstra算法計算任意2個交叉路口間的最短路徑;針對路段內的數據傳輸,綜合考慮距離、速度和鏈路可靠性等因素來選擇下一跳節點,并通過冗余傳輸技術提高數據傳輸的成功率。通過仿真實驗對比現有協議,驗證了該路由協議在性能上的優越性。

車載自組織網絡(VANETs);城市環境;混合信息;鏈路可靠性;冗余傳輸

車載自組織網絡(vehicular ad-hoc networks,VANETs)是自組織網絡的一個新的研究和應用領域,是移動自組織網絡(mobile ad hoc networks,MANETs)的一種新應用形態[1]。VANETs可以實現車與車、車與路基設備的信息交換,其典型應用包括行駛安全、交通優化和車載娛樂[2-3]。VANETs主要研究方向包括可靠路由協議機制、MAC層協議及機制、隱私和安全保護機制以及位置驗證等[4-5]。

在VANETs中,尤其在城市環境下,用戶可能會查詢特定區域內的交通情況或數公里外的信息(加油站、飯店等),或者將感應到的信息發送到數公里外的匯聚節點,未來在VANETs中通過P2P共享音頻、視頻數據也是可預見的需求。這些應用的數據會通過多跳的方式在大范圍車輛間傳遞，因此需要適用于大規模VANETs的車與車間的多跳路由協議。相比于高速公路環境,城市環境由于車輛多、道路復雜和數據傳輸需求多的原因,其路由協議是人們研究的熱點。

傳統基于拓撲的路由協議[6-8]無法解決路由建立的開銷大、時間延遲無法忍受等缺陷,效果并不理想。而基于位置的路由協議是通過鄰居節點和目的節點的地理位置來選擇下一跳節點,不需要維護路由表或保存路徑,因此受到研究者的關注。其中比較著名的是貪婪周邊無狀態路由協議(greedy perimeter stateless routing,GPSR)。GPSR采用貪婪轉發和周邊轉發2種模式。相比于基于拓撲的路由,GPSR協議在高速公路場景下取得了不錯的效果。但是在城市環境下,由于建筑物和路口的存在,GPSR的性能受到限制,文獻[9]說明了GPSR協議并不適合城市場景;文獻[10]提出的GPCR協議和文獻[11]提出的GpsrJ+協議對GPSR進行了改進,但并沒有充分考慮到城市環境的道路特點。由于城市道路能夠以路段為邊、路口為頂點天然形成一張無向圖,地理源路由(geographic source routing,GSR)[12]可以根據這張圖和地理信息,利用Dijkstra算法計算出到目的地的最短路徑,再采用貪婪策略實現數據轉發。然而當交通密度很低時,則沒有足夠的節點轉發數據包，因此很多研究[13-15]是利用交通信息設計路由協議的。其中比較典型的是GyTAR路由協議[14],其通過平衡車輛流量和目的節點的距離來選擇下一跳轉發路口，數據到達路口節點后,當前轉發節點根據得分公式計算相鄰路口的得分,得分高者作為下一個轉發路口。文獻[15]提出車輛輔助數據傳輸(vehicle-assisted data delivery，VADD)路由協議,根據預載入的歷史統計數據來選擇車輛密度盡可能大的路徑傳遞消息;顯然,如果有路段出現突發事件導致其車輛密度與歷史統計情況有明顯變化,VADD就不能相應地作調整。文獻[16]提出了STAR路由協議,考慮了交通信號燈對路由協議的影響。

綜上所述,對于城市場景下的VANETs路由協議,基于街道自然形成的道路拓撲一般可以分為路段選擇和路段轉發2個部分。很多研究者對數據包到達路口后如何選擇下一個轉發路段進行了研究,有基于距離的、有基于信號燈的、有基于車流密度的等，但對于某個路段的網絡負載并沒有進行考慮。而對于路段轉發,大部分研究者沿用簡單的貪婪轉發策略,也有研究者進行了簡單改進。而數據包在路段中轉發十分重要,否則由于重傳造成的延時十分嚴重。

因此,本文針對路段內可靠傳輸和路段選擇問題,提出一個適用于城市環境的基于混合信息和冗余傳輸的路由協議(a hybrid information and redundant transmission based routing protocol for VANETs,HIRTP)。該協議根據部署在交叉路口的固定節點收集到的交通和網絡實時信息,計算出到目的地的最短路徑,并依此路徑沿著道路進行轉發;在路段內轉發的過程中綜合考慮車速和無線信道的質量來選擇下一跳節點,并利用冗余傳輸技術提高數據傳輸成功率。

1 HIRTP路由協議描述

1.1 假設條件

本文的研究工作基于以下幾點假設:

(1) 每個節點都配備有GPS設備,能夠獲取自身的位置信息和同步的時鐘信號。

(2) 每個節點都配備具有電子地圖的導航系統,從而能夠獲取相關的街道信息,即街道ID和長度、交叉路口ID和位置以及整個區域的道路拓撲結構。即使部分車輛沒有導航系統,可以向周圍車輛或固定節點請求城市街道的拓撲信息。

(3) 交叉路口裝有固定節點用于交通和網絡信息的收集。這種假設有一定的道理,隨著智能交通的發展,智能化的交通信號燈成為可能,可以將固定節點的功能集成到交通信號燈中。

(4) 源節點在轉發數據前可以通過位置服務獲取目的節點的位置信息。

(5) 通過在1跳鄰居范圍內周期性地廣播HELLO消息,可以獲得鄰居節點的位置、速度、移動方向、所在路段等信息。

1.2 鏈路可靠性預測

根據文獻[17],車輛的速度服從正態分布。用h(v)表示車速v的概率密度函數,H(v)表示概率分布函數,則有:

(1)

(2)

其中,μ為車速的期望值;σ2為車速的方差。2輛車之間的速度差為Δv=vi-vj(i、j分別表示車輛i、車輛j)。因為vi和vj服從正態分布,所以Δv也服從正態分布。為了方便討論，Δv取正值(下文中Δv表示|Δv|),因此概率密度函數要乘以2。2輛車之間的相對距離dij可以用相對速度Δv和時間t表示,即dij=Δvt,從而Δv=dij/t。用R表示車輛節點間的無線通信范圍,則2輛車保持通信的最大距離為2R,即2輛車的相對距離從-R到R進行變化。用f(T)表示車輛能夠持續通信時間T的概率密度函數,可得:

T≥0

(3)

給出車輛i、j間鏈路持續有效時間Tp的預測公式,即

(4)

其中,Lij為車輛i和j之間的距離;(xi,yi)和(xj,yj)分別為車輛i和j的位置坐標;θ為:

(5)

在時刻t,通過對f(T)從t到t+Tp求積分,可以得到一個概率值,用其表示車輛i和j間鏈路的可靠性lr(i,j),其計算公式如下:

(6)

1.3 可靠路段轉發協議

在一條直路上轉發數據時,即路段轉發模式下,通常的機制是傳輸范圍內最遠的車輛(離交叉路口最近的車輛)為下一跳轉發節點,即貪婪轉發模式。在該模式下,源節點到目的節點的路由跳數最小,從而一跳傳輸距離也最遠。

通常來說,隨著傳輸距離的增加傳輸損耗也會增加,無線鏈路的質量會降低。而且在VANETs環境下由于車輛節點的快速移動,傳輸損耗和鏈路質量降低會更加明顯,從而導致數據包丟失和傳輸時延增加。因此,本文提出如下2點改進:① 在選擇下一跳節點時不僅考慮距離因素,還綜合考慮車輛節點的速度和無線鏈路質量;② 選擇2個節點作為下一跳節點,通過冗余提高傳輸成功率。

首先討論選擇下一跳節點的標準。車輛節點將其通信范圍劃分成N段,每一段給定一個權重因子ω,由遠到近分別為1/N，2/N，3/N，…，l。N的確定方法為:根據城市道路最高限速vlimit(一般為50 km/h)和HELLO消息的間隔時間Ts,即由2vlimitTs確定每一段的大致距離,然后由R/(2vlimitTs)確定N的值。劃分好段后,車輛節點依據如下公式計算每個鄰居節點的得分,即

score(j)=-ω[lblr(i,j)+lbPS(i,j)]

(7)

其中,i為當前車輛節點;j為i的某個鄰居節點;lr(i,j)由(6)式計算得到;PS(i,j)的定義如下:

PS(i,j)=(1-pf)(1-pr)

(8)

其中,pf為i到j數據包傳輸的錯誤率;pr為反向鏈路的錯誤率。pf可由鄰居節點通過HELLO消息通報,pr由當前節點測得，PS(i,j)體現了無線鏈路的質量。

與空白組比較，模型組和各給藥組大鼠血清中IL-1β、TNF-α水平均顯著升高，差異均有統計學意義（P＜0.01）。與模型組比較，各給藥組大鼠血清中IL-1β、TNF-α水平均顯著下降，且八角楓水提液高劑量組大鼠血清中IL-1β水平顯著低于陽性組，陽性組和八角楓水提液高劑量組大鼠血清中TNF-α水平均顯著低于其低、中劑量組，差異均有統計學意義（P＜0.05）；其余各給藥組組間比較，差異均無統計學意義（P＞0.05），詳見表4。

由(7)式可知,得分最低的節點應該被選為下一跳節點。

基于冗余的傳輸機制如圖1所示。

當前轉發節點選中其鄰居節點中2個得分最低的節點作為下一跳的2個接收節點。在數據包中指定2個接收節點的ID,并依據得分確定優先級。當車輛節點接收到數據包后,若數據包中優先級高的ID和自身ID相等則立即轉發數據包(見圖1a);若優先級低的ID和自身ID相等,則確定一個退避時間Tw，在退避時間Tw內若監聽到相同數據包的轉發,則丟棄該數據包,否則在Tw時間后由該節點轉發數據包(見圖1b)。Tw的計算公式為:

Tw=(1+β)S/B

(9)

其中,S為數據包的大小;B為有效帶寬;β為0～1的一個隨機數。

圖1 基于冗余的傳輸機制

1.4 路段選擇協議

在城市環境下,VANETs路由協議有一個關鍵問題要解決,那就是擁有數據包的車輛到達路口后應該選擇哪一個路段進行轉發,即路段選擇策略問題。最簡單的策略是選擇長度最短的路段。但不同路段的車流密度不同,部分路段可能出現網絡分割現象。尋找到目的地的路由路徑如圖2所示,車輛S要向車輛D傳輸數據,依據最短路段策略選擇路段1轉發數據。顯然路段1由于車流密度較低,出現網絡分割現象,進而導致傳輸延時極大增加。如果經由S→2→3→4→D傳輸就不會有那么大的延時,因此獲取路段的車流密度等信息十分重要。

圖2 尋找到目的地的路由路徑

僅考慮車流密度會造成部分路段網絡負載過重,因此本文綜合考慮車流密度和網絡延時。本文通過部署在交叉路口的固定節點(stationary node,SN)對道路的車輛密度和網絡延遲信息進行收集。SN將其每個相鄰路段劃分成不同區域,劃分方法為:

(9)

其中,L為路段的長度;R為車輛節點的無線通信范圍;XS為路段劃分成的區域數。SN周期性向相鄰路口發送交通信息探測包(traffic information probe packet,TPP),在TPP中記錄其初始化的時間。TPP在傳輸過程中盡量傳遞到每個區域的中心。一旦車輛節點發現自己是離當前區域中心最近節點時,就將其鄰居節點數記錄在TPP包中(包括自身)。以此策略一直傳輸到相鄰路口的SN,并記錄TPP包到達的時間。收到TPP包的SN為相應的路段計算車流密度和傳輸延時。車流密度根據TPP包中記錄的XS個區域中的車輛數和路段長度得到;傳輸延時由TPP包到達時間和初始化時間相減得到。通過TPP探測包,SN為相鄰路段維護車流密度和傳輸延時2個權值,以時間戳表示記錄的新舊。不同SN通過廣播共享各自的信息,因此每個SN會有所有路段的信息。

因為每條路段有2個權值,所以需要將這混合權值融合成單一權值。根據文獻[18],路段出現網絡分割現象的概率P的計算公式為:

(10)

其中,L為路段的長度;R為無線通信范圍;ρ為相應路段的車流密度。根據P為路段的延時增加一個懲罰值,從而得到修正后的延時dc,其計算公式為:

dc=d0+Pd0

(11)

其中,d0為實際測得的延時值。

最后,當有數據在2個不相鄰的路口間傳輸時,運用Dijkstra算法求出修正后延時最小的路由路徑。

1.5 數據轉發過程

城市環境下,道路的自然拓撲結構可以抽象為一個無向圖G(V,E),其中頂點V表示交叉路口集合,邊E表示連接2個相鄰交叉路口的路段集合。由1.4可知,每一條邊維護一個修正后的延時作為權值,每一個SN設備擁有整個圖的權值信息。因此,對于給定的2個交叉路口可以求出最短延時路由。

當源車輛節點需要向目的車輛節點傳輸數據時,源車輛節點首先向相鄰的路口發送路由請求包。收到路由請求包的路口SN計算離目的節點最近的路口的最短延時路由,然后發送路由回復包給源車輛節點。源車輛節點收到SN回復的信息后,將路由信息存儲在數據包的包頭。數據包在傳輸過程中分為2種方式。首先是路段轉發,依據1.3的策略選擇下一跳節點;當數據包到達路口時,依據包頭中的路由信息選擇相應路段進行轉發，當出現路由錯誤時,由當前轉發節點向鄰近路口重新請求路由信息。

2 仿真及結果分析

仿真采用的平臺為NS2;仿真設定的區域大小為3 000 m×2 500 m,每條道路都是雙向通行的路段;MAC協議為IEEE802.11p。仿真的具體參數見表1所列。

為了更好地分析各協議的性能,本文主要比較不同協議在數據包遞交率和平均端到端延時2個方面的性能。數據包遞交率是指源節點發送的數據包與目標節點接收到的數據包之比。平均端到端延時是指數據包從源節點到達目的節點所需的平均時間長度。

表1 仿真參數

(1) 可靠的路段轉發策略與貪婪轉發策略的對比分析。從仿真區域中選取一條2 000 m長的路段(區域的邊緣路段)作為仿真路段,車輛數量為60,車輛的速度設定為10～50 km/h。數據包遞交率隨車速變化的情況如圖3所示,隨著車速的增加,數據包遞交率呈下降趨勢,而可靠的路段轉發策略與貪婪策略相比一直具有較高的數據包遞交率。貪婪策略的數據包遞交率較低的原因是其只考慮下一跳節點離目的地的距離,這很容易造成傳輸失敗。而可靠的路段轉發策略有以下2個優勢使得數據包遞交率較高:① 考慮了鏈路的可靠性和質量,增加了數據包傳輸的成功率;② 通過冗余保證了在第1個節點傳輸失敗后,由第2個節點來傳輸。

(2) HIRTP與GSR和GyTAR的性能對比分析。車輛節點數目對數據包遞交率的影響情況如圖4所示,隨著車輛節點數目的增加數據包遞交率呈上升趨勢,HIRTP使用基于冗余可靠機制進行傳輸,使得其數據包遞交率較高。

圖3 數據包遞交率隨平均車速變化的情況

圖4 數據包遞交率隨車輛數變化的情況

平均端到端延時隨車輛節點數目變化的情況如圖5所示,隨著車輛節點數目的增加平均端到端延時呈下降趨勢,而HIRTP延時最低,GyTAR比GSR延時低。這是由于HIRTP利用實時的全局網絡延時和車流密度信息進行路段選擇，而GyTAR只是利用了局部的車流密度信息,GSR僅根據距離而未考慮車流信息。隨著車輛數據的增加,各協議的延時趨同,這是由于此時的車流密度足夠保證數據的快速傳輸,對傳輸延時影響度降低。但是HIRTP同時考慮了網絡延時信息,因此能夠具有更小的延時。

圖5 平均端到端延時隨車輛數變化的情況

綜合來說,HIRTP的性能最佳。HIRTP通過可靠的路段轉發協議替代簡單的貪婪策略進行路段轉發,并且綜合考慮全局交通信息和網絡延時信息進行路段選擇,從而有效地提高了數據包遞交率,降低平均端到端延時。

3 結 論

可靠高效的路由協議是VANETs領域的重要技術之一。本文針對城市環境的特點,以高數據包遞交率和低數據傳輸延時為目標,依托在交叉路口設置固定節點,并利用采集的交通信息和網絡信息,提出了城市環境下基于混合信息和冗余傳輸的VANETs路由協議HIRTP。城市道路的天然結構就是一張無向圖,其中交叉路口為頂點,路口間的路段為邊;依據收集到的信息為每條邊賦予權值,利用Dijkstra算法計算出任意2個交叉路口間的最短路徑;對于路段內的數據轉發,綜合考慮距離、速度和無線鏈路的質量等因素來選擇下一跳轉發節點,并且通過選擇2個節點作為下一跳轉發節點,保證了數據高效快速的傳輸。仿真實驗結果表明,HIRTP具有較高的數據包遞交率和較低的平均端到端延時。

[1] 陳振,韓江洪,楊勇,等.VANET中利用空閑TDMA時隙協助發送數據的方法[J].通信學報,2015,36(7):92-101.

[2] REHMAN S U,KHAN M A,ZIA T,et al.Vehicular ad-hoc networks (VANETs): an overview and challenges[J].Eurasip Journal on Wireless Communications & Networking,2013,3(3):29-38.

[3] ZEADALLY S,HUNT R,CHEN Y S,et al.Vehicular ad hoc networks (VANETS): status,results,and challenges[J].Telecommunication Systems,2012,50(4):217-241.

[4] 徐會彬,夏超.VANETs路由綜述[J].計算機應用研究,2013,30(1):1-6.

[5] 常促宇,向勇,史美林.車載自組網的現狀與發展[J].通信學報,2007,28(11):116-126.

[6] EIZA M H,NI Q.An evolving graph-based reliable routing scheme for VANETs[J].IEEE Transactions on Vehicular Technology,2013,62(4):1493-1504.

[7] 楊永軍.基于位置信息的車聯網路由恢復方法[J].合肥工業大學學報(自然科學版),2015,38(8):1081-1085.

[8] HE Y,XU W J,LIN X H.A stable routing protocol for highway mobility over vehicular ad-hoc networks[C]//IEEE 81st Vehicular Technology Conference Spring.[S.l.]:IEEE,2015:1-5.

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

[11] LEE K C,HAERRI J,LEE U,et al.Enhanced perimeter routing for geographic forwarding protocols in urban vehicular scenarios[C]//IEEE Globecom Workshops.[S.l.]:IEEE,2007:1-10.

[12] LOCHERT C,HARTENSTEIN H,TIAN J,et al.A routing strategy for vehicular ad hoc networks in city environments[C]//IEEE Intelligent Vehicles Symposium.[S.l.]:IEEE,2003:156-161.

[13] 白翔宇,葉新銘,李軍.感知實時車流信息的VANET路由仿真研究[J].系統仿真學報,2012,24(2):428-436.

[14] JERBI M,MERAIHI R,SENOUCI S M,et al.GyTAR: improved greedy traffic aware routing protocol for vehicular ad hoc networks in city environments[C]//Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks.[S.l.]:ACM,2006:88-89.

[15] ZHAO J,CAO G H.VADD: vehicle-assisted data delivery in vehicular Ad Hoc networks[J].IEEE Computer Communications,2006,57(3):1-12.

[16] CHANG J J,LI Y,LIAO W,et al.Intersection-based routing for urban vehicular communications with traffic-light consideration[J].IEEE Wireless Communications,2012,19(1):82-88.

[17] EIZA M H,NI Q.A reliability-based routing scheme for vehicular ad hoc networks (VANETs) on highways[C]//2012 IEEE 11th International Conference on Trust,Security and Privacy in Computing and Communications.[S.l.]:IEEE Computer Society,2012:1578-1585.

[18] LIN L,XIAO X Q,XU M,et al.PCR-a position-and-connectivity-based routing protocol for VANETs[C]//7th International Conference on Ubiquitous Intelligence & Computing and Autonomic & Trusted Computing.[S.l.]:IEEE,2010:469-473.

AhybridinformationandredundanttransmissionbasedroutingprotocolforVANETs

SONG Liang1, HAN Jianghong1,2, LIU Zhengyu2,3

(1.School of Computer and Information, Hefei University of Technology, Hefei 230009, China; 2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of Ministry of Education, Hefei 230009, China; 3.School of Mechanical Engineering, Hefei University of Technology, Hefei 230009, China)

Routing protocol research for vehicular ad hoc networks(VANETs) confronts challenges because the rapid moving of vehicle node leads to the frequent changes of the network topology and the unstable quality of wireless link. In order to deal with these challenges, a hybrid information and redundant transmission based routing protocol for VANETs is proposed. According to the road characteristics in urban environment, an undirected graph is abstracted, where the intersections are vertices and road sections are edges. The real-time information of traffic and networks is collected by the stationary nodes deployed in the intersection, and a weight value is given for each edge, and then the shortest path between any two intersections is calculated by using the Dijkstra algorithm. As for the data transmission within road section, the next node is selected by considering the distance, speed and link reliability, and the success rate of data transmission is improved through redundant transmission technology. The simulation results indicate that the proposed routing protocol performs well.

vehicular ad-hoc networks(VANETs); urban environment; hybrid information; link reliability; redundant transmission

2016-03-24；

2016-04-11

國家電子信息產業發展基金資助項目(工信部財函[2011]506號);國家國際科技合作專項資助項目(2012DFB10060)

宋 亮(1990-),男,安徽六安人,合肥工業大學碩士生; 韓江洪(1954-),男,安徽涇縣人,合肥工業大學教授,博士生導師,通訊作者,E-mail:303617659@qq.com.

10.3969/j.issn.1003-5060.2017.10.009

TP393.03

A

1003-5060(2017)10-1343-06

(責任編輯 胡亞敏)