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

徐 婷,王新紅,王 平

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

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

徐 婷,王新紅,王 平

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

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

多優(yōu)先級(jí) 自適應(yīng) 隊(duì)列控制 路由協(xié)議

0 引 言

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

1 研究背景

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

2 MPDAR算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2應(yīng)用場(chǎng)景中,車輛節(jié)點(diǎn)3處于繁忙狀態(tài),并通過(guò)信標(biāo)消息告知周圍節(jié)點(diǎn)。車輛S為源節(jié)點(diǎn),D為目的節(jié)點(diǎn)。S通過(guò)查找路由表,發(fā)現(xiàn)其鄰居節(jié)點(diǎn)有車輛1、3、4、5四個(gè)節(jié)點(diǎn)。以下為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 場(chǎng)景Fig.2 Scenario

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

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

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

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

3 性能仿真及分析

3.1 VISSIM以及NS-2仿真工具

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

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

3.2 仿真結(jié)果

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

表2 仿真試驗(yàn)場(chǎng)景Table 2 Simulation scenario

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

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

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

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

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

4 結(jié) 語(yǔ)

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

[1] 王非,王新紅,李想,等.VANET自適應(yīng)門限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—),女,博士,副教授,主要研究方向?yàn)閷拵o(wú)線通信;

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

王 平(1978—),男,博士,副教授,主要研究方向?yàn)閷拵o(wú)線通信。

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—),女,碩士,主要研究方向?yàn)閷拵o(wú)線通信;

國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)(No.2012AA111902);中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(No.0800219162);國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(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)