徐 婷,王新紅,王 平

(同濟大學電子與信息工程學院,上海201804)

車聯(lián)網(wǎng)中基于多優(yōu)先級的自適應動態(tài)路由協(xié)議*

徐 婷,王新紅,王 平

(同濟大學電子與信息工程學院,上海201804)

本論文介紹了一種車聯(lián)網(wǎng)中的多優(yōu)先級的自適應動態(tài)路由協(xié)議(MPDAR),著重介紹了不同優(yōu)先級等級消息的分發(fā)機制,該路由協(xié)議利用了車輛的地理位置和速度信息,并保證了1)車聯(lián)網(wǎng)中不同類型消息具有不同的QoS要求;2)完全分布式路由協(xié)議。最后,本論文應用ViSSIM交通仿真軟件和NS-2網(wǎng)絡(luò)模擬軟件,對MPDAR協(xié)議進行仿真。結(jié)果表明,MPDAR路由協(xié)議較其他路由協(xié)議性能有所改進。

多優(yōu)先級 自適應 隊列控制 路由協(xié)議

0 引 言

車聯(lián)網(wǎng)作為新興的通信技術(shù),可以實現(xiàn)車與車之間,車與路邊基礎(chǔ)設(shè)施間的多跳無線通信,以提供多種車輛安全應用與非安全應用[1]。相對于傳統(tǒng)的移動自組織網(wǎng)絡(luò),車聯(lián)網(wǎng)有自身獨有的特點:①高動態(tài)拓撲結(jié)構(gòu),車輛的高速移動導致車聯(lián)網(wǎng)的拓撲結(jié)構(gòu)快速變化甚至網(wǎng)絡(luò)中斷;②足夠的能量和存儲空間。車聯(lián)網(wǎng)中的通信節(jié)點是車輛,它們具有足夠的存儲空間和數(shù)據(jù)處理能力;③移動軌跡可預測。車輛的移動受限于已經(jīng)建好的道路,只要提供了速度和街道地圖,車輛的未來狀態(tài)就可以在一定時間內(nèi)被預測;④車聯(lián)網(wǎng)的應用場景多樣化,包括車輛安全、道路交通效率、信息與娛樂等應用。以上特點使得車聯(lián)網(wǎng)的路由方法存在很多新問題和新挑戰(zhàn),傳統(tǒng)路由協(xié)議在車聯(lián)網(wǎng)中難以獲得理想的性能。

1 研究背景

前期的車聯(lián)網(wǎng)路由協(xié)議主要集中在基于拓撲的路由協(xié)議,如AODV、DSR、DSDV等。隨著GPS和電子地圖的廣泛應用,基于地理位置的路由協(xié)議成為主流研究方向,如GPSR、A-STAR等。文獻[2-3]分別提出了一種基于可靠性和實時性的路由協(xié)議,這些路由協(xié)議主要用于單一場景,具有局限性。文獻[4]提出了一種基于Qos的網(wǎng)格化路由協(xié)議GVGrid,它把地理區(qū)域分為網(wǎng)格,然后將數(shù)據(jù)包沿著道路穿過不同的網(wǎng)格轉(zhuǎn)發(fā)。但GVGrid是在密集網(wǎng)絡(luò)假設(shè)下提出的,不能完全適用于復雜的VANET環(huán)境。文獻[5]提出高速公路中基于優(yōu)先級的安全消息的傳輸,文中的優(yōu)先級分類方式參考了IEEE802. 11e中的消息優(yōu)先級分類方案,滿足了對安全消息的快速可靠傳輸。但文中對非安全消息未做討論。文獻[6]提出了一種應用更廣泛的基于優(yōu)先級路由協(xié)議,該路由方案根據(jù)802.11p將消息分成了兩類:高優(yōu)先級和低優(yōu)先級。協(xié)議中對低優(yōu)先級的消息轉(zhuǎn)發(fā)方式實際上是一種機會轉(zhuǎn)發(fā),有很大的時延和不可靠性。文獻[7]提出針對不同優(yōu)先級的消息,采取不同的下一跳節(jié)點選擇方式,保證了緊急消息的快速傳輸,但該方案采用普通的優(yōu)先權(quán)隊列控制方式,容易導致低優(yōu)先級隊列中的分組很久得不到處理,引起“饑餓”。從路由協(xié)議發(fā)展來看,車聯(lián)網(wǎng)下的大部分路由協(xié)議設(shè)計的重點放在保證所有消息的時延、可靠性等方面,而不同的消息有不同的QoS要求,因此這會導致緊急的安全消息,往往不能夠得到及時轉(zhuǎn)發(fā),而對于非安全消息,往往處于“饑餓”狀態(tài)。因此,本論文將對不同的業(yè)務范圍產(chǎn)生的數(shù)據(jù)包劃分不同的優(yōu)先級,并放入不同的控制隊列中,并自適應的選擇路由方式,由此保證較好的網(wǎng)絡(luò)性能。

2 MPDAR算法設(shè)計

首先,本文假設(shè):

1)車聯(lián)網(wǎng)中的車輛都配備GPS、電子地圖設(shè)備,可以獲取自身的位置、速度等信息。

2)車輛間通過定期廣播信標消息,可以獲取其他車輛的位置、速度等信息。

3)若車輛處于繁忙狀態(tài),則其會廣播告知周圍節(jié)點。

參照歐洲D(zhuǎn)SRC標準SAE-J2735[8],車聯(lián)網(wǎng)中的消息可以劃分為8個等級:0-7(暫時無消息劃分為0等級),等級越高,消息的優(yōu)先級越高。消息的優(yōu)先級劃分有兩個指標:重要性和緊急程度,如表1所示。

表1 消息優(yōu)先級等級劃分機制Table 1 Priority classification mechanism of message

對于高優(yōu)先級消息,如車輛碰撞預警,需要快速、可靠的分發(fā),而對于低優(yōu)先級消息,如電子地圖下載、娛樂消息等,只需盡力傳輸即可。另有一類低優(yōu)先級消息,雖重要性程度低,但時延要求高,需要快速分發(fā),如ETC電子支付。

2.1 多優(yōu)先級消息隊列控制

對于多種優(yōu)先級消息的隊列控制,采用改進的加權(quán)公平隊列。如圖1所示,高優(yōu)先級隊列High-Priority Quene采用先進先出機制,且當該隊列中有消息時,優(yōu)先發(fā)送該隊列消息;低優(yōu)先級隊列Low-Priority Quene有三種分隊列,每個分隊列都采用先進先出的排隊機制,且其發(fā)送時間權(quán)值比為3:2:1。

圖1 改進的加權(quán)公平隊列Fig.1 Improved WFQ

傳輸層的消息分類器將不同優(yōu)先級的packet放入不同的控制隊列。其中,優(yōu)先級等級為7或6的packet放入High-Priority Quene隊列;優(yōu)先級等級為5或4的packet放入發(fā)送時間權(quán)值為3的Low -Priority Quene分隊列;優(yōu)先級等級為3或1的packet放入發(fā)送時間權(quán)值為2的Low-Priority Quene分隊列;優(yōu)先級等級為2的packet放入發(fā)送時間權(quán)值為1的Low-Priority Quene分隊列。

2.2 不同優(yōu)先級消息的路由轉(zhuǎn)發(fā)機制

不同優(yōu)先級消息QoS要求不同,因此采用不同的轉(zhuǎn)發(fā)機制。當車輛需要轉(zhuǎn)發(fā)消息時,首先會查找周圍車輛節(jié)點,并收集其位置、速度、繁忙狀態(tài)等信息,再根據(jù)消息的優(yōu)先級等級,選取最佳下一跳轉(zhuǎn)發(fā)節(jié)點,直到到達目的節(jié)點。

圖2應用場景中,車輛節(jié)點3處于繁忙狀態(tài),并通過信標消息告知周圍節(jié)點。車輛S為源節(jié)點,D為目的節(jié)點。S通過查找路由表,發(fā)現(xiàn)其鄰居節(jié)點有車輛1、3、4、5四個節(jié)點。以下為S到D的所有可能路徑:R1(S-3-D)、R2(S-1-2-D)、R3(S-1-3-D)、R4(S-4-5-3-D)、R5(S-4-5-6-D)、R6(S-5-3-D)、R7(S-5-6-D)。

圖2 場景Fig.2 Scenario

(1)低優(yōu)先級隊列消息分發(fā)機制

由于節(jié)點4比源節(jié)點S距離目的節(jié)點D更遠,時延加大;車輛1雖比5更接近目的節(jié)點,但車輛5與D是同向而車輛1與D是反向而行,連接穩(wěn)定性差;節(jié)點3為繁忙節(jié)點,可能導致高時延。通過比較后,源節(jié)點將選擇鄰居節(jié)點5作為下一跳轉(zhuǎn)發(fā)節(jié)點。同理,車輛5將選擇節(jié)點6作為下一跳轉(zhuǎn)發(fā)節(jié)點,直到到達目的節(jié)點D。由此可知,若消息進入低優(yōu)先級隊列,則轉(zhuǎn)發(fā)過程中選擇的路徑為S-5-6-D。

(2)高優(yōu)先級隊列消息分發(fā)機制

由于該隊列消息要求可靠性高、時延小,因此采用廣播的消息分發(fā)機制。繁忙節(jié)點3接到該廣播消息后,由于該廣播消息進入高優(yōu)先級隊列,節(jié)點3將停止轉(zhuǎn)發(fā)正在發(fā)送的消息,優(yōu)先轉(zhuǎn)發(fā)該高優(yōu)先級消息。同時,為防止所有車輛都在同一時間內(nèi)轉(zhuǎn)發(fā)該廣播消息,產(chǎn)生廣播風暴,需要規(guī)定消息生存時間并限制轉(zhuǎn)發(fā)跳數(shù)。根據(jù)源節(jié)點和目的節(jié)點的車輛位置、速度方向,判斷消息的廣播方向,若鄰居節(jié)點在轉(zhuǎn)發(fā)節(jié)點的反向廣播方向,則該鄰居節(jié)點無需對該廣播消息進行轉(zhuǎn)發(fā)。由此可知,若消息進入高優(yōu)先級隊列,則轉(zhuǎn)發(fā)過程中選擇的路徑為S-3-D。

3 性能仿真及分析

3.1 VISSIM以及NS-2仿真工具

VISSIM是一種微觀交通系統(tǒng)模擬軟件,用以建模和分析各種交通條件下,城市交通和公共交通的運行狀況。既可以在線生成可視化的交通運行狀況,也可以離線輸出各種統(tǒng)計數(shù)據(jù),如:位置、速度、方向等。

NS-2[9]是一種面向網(wǎng)絡(luò)的離散事件模擬器,它以O(shè)Tcl腳本語言作為前臺,C++語言作為后臺,可以進行LAN、WAN和無線等網(wǎng)絡(luò)的仿真。

3.2 仿真結(jié)果

在仿真實驗中,MAC層使用的協(xié)議為IEEE802.11,場景參數(shù)配置如表2所示。

表2 仿真試驗場景Table 2 Simulation scenario

圖3、圖4和圖5為仿真結(jié)果圖。

圖3 不同通信量時的丟包率Fig.3 Packet-loss rates for different number of traffics

圖4 不同通信量時的吞吐量Fig.4 Throughputs for different number of traffics

圖5 不同通信量時的端到端平均時延Fig.5 Average delay for different number of traffics

圖3～5可以看出,當通信量低時,MPDAR的優(yōu)勢并不明顯,但仍然優(yōu)于AODV和GPSR兩種協(xié)議.隨著通信量的加大,MPDAR的優(yōu)勢逐漸增強,原因是MPDAR引入多種數(shù)據(jù)包控制隊列,優(yōu)先級高的數(shù)據(jù)包能夠得到及時轉(zhuǎn)發(fā),優(yōu)先級低的數(shù)據(jù)包也能得到公平轉(zhuǎn)發(fā)。隨著通信量的繼續(xù)增大,繁忙節(jié)點增加,網(wǎng)絡(luò)逐漸產(chǎn)生擁塞,因此丟包率、時延隨之增加,但由于MPDAR的多種改進隊列控制機制,使得在高通信量情況下,仍能保證相對較高的通信質(zhì)量。仿真結(jié)果表明,MPDAR的性能較AODV和GPSR兩種協(xié)議都有所改進。

4 結(jié) 語

綜上所述,MPDAR算法重點在于根據(jù)不同消息的優(yōu)先級,提供了兩種不同的發(fā)送隊列,并自適應的采取不同的路由轉(zhuǎn)發(fā)方式。仿真結(jié)果表明,MPDAR的網(wǎng)絡(luò)性能有所提高,確保了安全消息的低時延、高可靠性的要求,又同時保證了非安全消息的吞吐量要求,有效滿足車聯(lián)網(wǎng)不同業(yè)務的Qos需求。

[1] 王非,王新紅,李想,等.VANET自適應門限MAC層退避算法研究[J].通信技術(shù).2012,45(10):46-49.

WANG Fei,WANG Xin-hong,LI Xiang,et al.The MAC Layer Backoff Algorithm Based On Adaptive Threshold For VANET[J].Communications Technology.2012, 45(10):46-49.

[2] EIZA M H,NI Qiang.A Reliability-Based Routing Scheme For Vehicular Ad Hoc Networks(VANETs)On Highways[C]//Proceedings of the 2012 IEEE 11th International Conference on Trust,Security and Privacy in Computing and Communications.Liverpool,United Kingdom:The IEEE Computer Society,2012:1578-1585.

[3] NZOUONTA J,RAJGURE N,WANG Gui-ling,et al. VANET Routing On City Roads Using Real-Time Vehicular Traffic Information[J].IEEE Transaction OnVehicular Technology,Sept.2009,58(07):3609-3626.

[4] SUN Wei hua,HIROZUMIY,KUSUMOTO Y,et al.GVGrid:A QoS Routing Protocol For Vehicular Ad Hoc Networks[C]//Proceedings of the 14th International Workshop on Quality of Service(IWQoS′06).New Haven, CT,USA:The IEEE Computer Society,2006:130-139.

[5] CHAKKAPHONG S,AURA G.Priority-BasedInter-Vehicle Communication ForHighway Safety Messaging Using IEEE802.11e[C]//Proceedings of 65th IEEE Vehicular Technology Conference,VTC spring 2007.Dublin,Ireland:The IEEE Computer Society,2007:2595-2599.

[6] JIN Zhi-gang,DENGWei,YAN Ning-xiao,et al.A Study of Multi-Priority Opportunistic Directional Routing For VANET[C]//Proceedings of the2010 Wireless Communications and Signal Processing(WCSP).Suzhou,China: IEEE Xplore Digital Library,2010:184-188.

[7] CHEN Jian,ZHOU Mi,LI Deshi,et al.A Priority Based Dynamic Adaptive Routing ProtocolFor Wireless Sensor Networks[C]//Proceedings of the First Intelligent Networks and Intelligent Systems,ICINIS2008. Wuhan,China:International Journal of Intelligent Engineering and Systems,2008:160-164.

[8] DSRC Committee of the SAE.PA 1596-001(SAEJ2735 -2008)Dedicated Short Range Communications(DSRC) Message Set Dictionary[S].[s.l.]:Society of Automotive Engineers,2008:230-235.

[9] 陳春梅.基于NS2的網(wǎng)絡(luò)仿真與性能分析[J].通信技術(shù).2010,43(08):48-50.

CHEN Chun-mei.Network Simulation And Performance Analysis based on NS-2[J].Communications Technology,2010,43(08):48-50.

XU Ting(1989-),female,M.Sci., mainly engaged in broadband wireless communications.

王新紅(1974—),女,博士,副教授,主要研究方向為寬帶無線通信;

WANG Xin-hong(1974-),female,Ph.D.,associate professor,mainly engaged in broadband wireless communications.

王 平(1978—),男,博士,副教授,主要研究方向為寬帶無線通信。

WANG Ping(1978-),male,Ph.D.,associate professor, mainly engaged in broadband wireless communications.

Multi-Priority Dymamic Adaptive Routing Protocol for VANET

XU Ting,WANG Xin-hong,WANG Ping
(College of Electronics and Information Engineering,Tongji University,Shanghai 201804,China)

This paper describes a MPDAR(Multi-Priority Dynamic Adaptive Routing)protocol for VANET,focusing on distribution mechanism for messages with different priorities.By using the geographic and speed information of vehicles,the routing protocol could provide different QoSs for different types of messages and fully-distributed routing protocol.The proposed MPDAR protocol is simulated and evaluated with two simulation software called VISSIM and NS-2.The results show that the performance of MPDAR protocol is better than that other routing protocols.

multi-priority;adaptive;queue control;routing protocol

TP316.8

A

1002-0802(2014)02-0163-04

10.3969/j.issn.1002-0802.2014.02.009

徐 婷(1989—),女,碩士,主要研究方向為寬帶無線通信;

國家高技術(shù)研究發(fā)展計劃(863計劃)(No.2012AA111902);中央高校基本科研業(yè)務費專項資金項目(No.0800219162);國家自然科學基金青年科學基金項目(No.61103179)

Foundation Item:National High Technology Research and Development Program of China(863 Program)(No.2012AA111902);The Fundamental Research Funds for the Central Universities(No.0800219162);The National Natural Science Foundation of China (No.61103179)