周美麗, 余 敏

(江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院,江西 南昌 330022)

基于車流密度的VANETs路由協(xié)議*

周美麗, 余 敏

(江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院,江西 南昌 330022)

在節(jié)點(diǎn)高速移動(dòng)的車載自組織網(wǎng)絡(luò)(VANETs)中，道路交通狀況極大地影響著網(wǎng)絡(luò)中的數(shù)據(jù)傳輸性能。在貪婪周邊無狀態(tài)路由(GPSR)協(xié)議的基礎(chǔ)上加以改進(jìn)，提出了基于車流密度的VANETs由協(xié)議?？紤]了車流密度以及節(jié)點(diǎn)運(yùn)動(dòng)速度、方向等影響因素，設(shè)計(jì)車流密度的計(jì)算方法，利用新的轉(zhuǎn)發(fā)策略替代GPSR的貪婪轉(zhuǎn)發(fā)策略，能夠選擇車流密度較好的路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，避免因車流密度分布不均勻而產(chǎn)生的局部最大現(xiàn)象。同時(shí)能夠?qū)τ捎诠?jié)點(diǎn)高速運(yùn)動(dòng)引起的鏈路中斷進(jìn)行預(yù)測(cè)，提出有效的修復(fù)機(jī)制，從而建立鏈路穩(wěn)健的VANETs路由。采用Matlab仿真平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，與已有的GPSR，GPCR協(xié)議進(jìn)行比較分析。仿真結(jié)果表明:提出的路由協(xié)議相比于其它2種路由協(xié)議在時(shí)延和分組轉(zhuǎn)發(fā)率方面得到顯著改善，性能優(yōu)越，非常適合在城市場(chǎng)景中。

車載自組織網(wǎng)絡(luò)； 車流密度； 鏈路中斷

0 引 言

車載自組織網(wǎng)絡(luò)(vehicle Ad-Hoc networks,VANETs), 是移動(dòng)自組織多跳網(wǎng)路中極具應(yīng)用價(jià)值的研究方向。利用 VANETs可以實(shí)現(xiàn)事故告警、輔助駕駛、道路交通信息查詢、車輛間通信、自動(dòng)繳費(fèi)和Internet 信息服務(wù)等應(yīng)用，不僅能提高交通效率，還為司機(jī)的通行提供可靠安全的支持和多重便利。由于VANETs網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的高度動(dòng)態(tài)變化在傳輸數(shù)據(jù)時(shí)很具有挑戰(zhàn)性，越來越受到工業(yè)界和學(xué)術(shù)界的高度關(guān)注，因此,VANETs路由協(xié)議的研究成為了當(dāng)前的熱點(diǎn)方向。

在VANETs的路由協(xié)議中，基于地理位置信息的路由協(xié)議是最為普遍采用的設(shè)計(jì)思想。以貪婪周邊無狀態(tài)路由(GPSR)[1]為代表的基于地理位置的路由協(xié)議采用貪婪轉(zhuǎn)發(fā)的思想，選擇離目標(biāo)節(jié)點(diǎn)最近的下一跳進(jìn)行路由轉(zhuǎn)發(fā)，能迅速發(fā)現(xiàn)和建立路由，具有高效、低路由開銷和良好的可擴(kuò)展性等特點(diǎn)，特別適合于節(jié)點(diǎn)移動(dòng)速度較快的VANETs。但是在城市道路中，道路兩邊的建筑物阻擋無線信號(hào)的傳播，造成空洞的形成，嚴(yán)重影響已有的基于位置的路由協(xié)議的性能, 文獻(xiàn)[2,3]中對(duì)該問題已有介紹。Lochert C等人提出了貪婪周邊協(xié)調(diào)器路由(greedy perimeter coordinator routing，GPCR)[4]協(xié)議，通過在十字路口部署固定節(jié)點(diǎn)做出數(shù)據(jù)轉(zhuǎn)發(fā)決策，解決了建筑物對(duì)無線信號(hào)的屏蔽作用。但該協(xié)議沒有考慮道路上車輛稀少、密度分布不均勻而產(chǎn)生的局部最大現(xiàn)象，路由時(shí)可能發(fā)生中斷，而自動(dòng)回退，增大時(shí)延和跳數(shù)，降低路由效率。2008 年，Lee K C等人提出了城市VANETs環(huán)境下的地標(biāo)覆蓋路由(LOUVRE)[5]協(xié)議。利用車輛自主發(fā)現(xiàn)密度的方式輔助路由選擇，提出了車輛自主發(fā)現(xiàn)道路密度的算法。通過“洪泛”方式傳播道路密度的評(píng)估值，使全網(wǎng)的所有車輛都能建立起各路段是否具有傳輸通路的認(rèn)識(shí)，如此眾多的洪泛消息極易引起網(wǎng)絡(luò)擁塞，產(chǎn)生較大的發(fā)送時(shí)延。除此之外，在VANETs中由于節(jié)點(diǎn)的快速移動(dòng)的特性，會(huì)使得已經(jīng)建立的路由鏈路發(fā)生中斷，出現(xiàn)鏈路不穩(wěn)定等問題[6～10]。因此，本文在GPSR協(xié)議的基礎(chǔ)上加以改進(jìn)，提出了基于車流密度的VANETs路由協(xié)議。仿真實(shí)驗(yàn)結(jié)果表明：該路由協(xié)議在時(shí)延和分組轉(zhuǎn)發(fā)率方面得到顯著改善。

1 基于車流密度的VANETs路由協(xié)議

1.1 3種類型節(jié)點(diǎn)

為了避開建筑物對(duì)無線信號(hào)的屏蔽效應(yīng)，在十字路口部署固定的節(jié)點(diǎn)稱為十字路口節(jié)點(diǎn)。在此假設(shè)每輛車(節(jié)點(diǎn))都安裝了GPS，除了獲得位置信息還能獲得節(jié)點(diǎn)所在的路段信息。對(duì)于路段的劃分，以十字路口的節(jié)點(diǎn)為分界點(diǎn)，2個(gè)十字路口的連線即為同一路段。每個(gè)節(jié)點(diǎn)需要廣播自己的位置和所在路段(記為ID)，對(duì)于十字路口節(jié)點(diǎn)信標(biāo)的廣播信息將會(huì)“+”號(hào)來表示十字路口。節(jié)點(diǎn)可劃分為三類：

1)普通節(jié)點(diǎn)

該節(jié)點(diǎn)的信標(biāo)廣播的ID與所有鄰居節(jié)點(diǎn)的ID號(hào)一致，即為普通節(jié)點(diǎn)。

2)預(yù)測(cè)節(jié)點(diǎn)

該節(jié)點(diǎn)的鄰居表中存在一個(gè)十字路口節(jié)點(diǎn)，即為預(yù)測(cè)節(jié)點(diǎn)。

3)十字路口節(jié)點(diǎn)

該節(jié)點(diǎn)鄰居表中各個(gè)路段的ID都有，自身ID標(biāo)記為“+”，即為十字路口節(jié)點(diǎn)。每個(gè)十字路口節(jié)點(diǎn)存儲(chǔ)并維護(hù)一張與其相鄰的各個(gè)十字路口節(jié)點(diǎn)所組成的路段的車流密度表。

1.2 計(jì)算道路車流密度的算法

十字路口節(jié)點(diǎn)廣播Query查詢信息至與之相連路段的所有節(jié)點(diǎn)，節(jié)點(diǎn)將返回自身的節(jié)點(diǎn)號(hào)和鄰居節(jié)點(diǎn)數(shù)到十字路口節(jié)點(diǎn)。十字路口節(jié)點(diǎn)通過返回的信息包，計(jì)算路段中響應(yīng)的節(jié)點(diǎn)數(shù)和所有節(jié)點(diǎn)的鄰居數(shù)之和。

假設(shè)路段的長(zhǎng)度為L(zhǎng)，有n個(gè)節(jié)點(diǎn)響應(yīng)十字路口節(jié)點(diǎn)的Query查詢信息,節(jié)點(diǎn)的通信半徑為r,n個(gè)節(jié)點(diǎn)的鄰居數(shù)之和為m(十字路口節(jié)點(diǎn)不作為鄰居節(jié)點(diǎn)數(shù)計(jì)算)，那么該路段連通必須滿足n≥L/2r;否則,數(shù)據(jù)經(jīng)此路段無法成功傳輸。原理如圖1所示。

圖1 原理圖Fig 1 Principle diagram

圖1中路段長(zhǎng)度為8r,節(jié)點(diǎn)通信半徑為r,可看出此路段數(shù)據(jù)要經(jīng)過路段兩端成功傳輸至少保證有4個(gè)節(jié)點(diǎn)。車流密度ρ的計(jì)算公式如下

(1)

如圖2所示的十字路口節(jié)點(diǎn)a維護(hù)的車流密度表可表示為：

1)a—b路段：{nodes:3,ρ:4/3},十字路口節(jié)點(diǎn)不作為鄰居節(jié)點(diǎn)數(shù)計(jì)算，A,B,C的鄰居節(jié)點(diǎn)數(shù)分別為1，2，1；

2)a—f路段：{nodes:0;ρ:0}；

3)a—e路段：{nodes:0;ρ:0}；

4)a—d路段：{nodes:2;ρ:1} 。

其中,nodes表示路段中的節(jié)點(diǎn)數(shù)，ρ為節(jié)點(diǎn)密度。由于a—f路段和a—e路段均只有一個(gè)節(jié)點(diǎn),會(huì)出現(xiàn)傳輸中斷，可判斷此路段車流密度稀疏，不適宜進(jìn)行路由傳輸。這種情況將nodes和ρ均設(shè)為0。

圖2 車流密度示意圖Fig 2 Diagram of vehicle density

1.3 設(shè)計(jì)路由轉(zhuǎn)發(fā)機(jī)制

在新協(xié)議中，針對(duì)定義的3種不同節(jié)點(diǎn)采用新的轉(zhuǎn)發(fā)機(jī)制替代GPSR的貪婪轉(zhuǎn)發(fā)策略，如下：

1)普通貪婪轉(zhuǎn)發(fā)模式

普通節(jié)點(diǎn)仍采取貪婪轉(zhuǎn)發(fā)模式。

2)受限的貪婪轉(zhuǎn)發(fā)模式

當(dāng)數(shù)據(jù)包轉(zhuǎn)發(fā)至預(yù)測(cè)節(jié)點(diǎn)時(shí)，通過判斷預(yù)測(cè)節(jié)點(diǎn)與目的節(jié)點(diǎn)的位置關(guān)系。如果在同一路段則執(zhí)行貪婪轉(zhuǎn)發(fā)模式，則無需經(jīng)過十字路口節(jié)點(diǎn);否則，將數(shù)據(jù)包傳給十字路口的節(jié)點(diǎn)進(jìn)行路由選擇。

3)決策轉(zhuǎn)發(fā)模式

當(dāng)數(shù)據(jù)包轉(zhuǎn)發(fā)至十字路口節(jié)點(diǎn)時(shí)，決策轉(zhuǎn)發(fā)策略如下：

(1)若目的節(jié)點(diǎn)在十字路口所相連的路段，則選擇與目的節(jié)點(diǎn)在同一路段的下一跳節(jié)點(diǎn)進(jìn)行貪婪轉(zhuǎn)發(fā)。

(2)若目的節(jié)點(diǎn)不在十字路口所處路段，則采取如下步驟：

a.首先，十字路口節(jié)點(diǎn)根據(jù)自身坐標(biāo)和目的節(jié)點(diǎn)的坐標(biāo)，判斷目的節(jié)點(diǎn)在十字路口節(jié)點(diǎn)的哪個(gè)方位(將方位分為左上、左下、右上、右下)。每一個(gè)方位對(duì)應(yīng)2個(gè)路段(如圖3所示，目的節(jié)點(diǎn)H在十字路口節(jié)點(diǎn)a左上方位對(duì)應(yīng)a—b，a—d2個(gè)路段)。

b.十字路口節(jié)點(diǎn)根據(jù)步驟(a)判斷的方位所對(duì)應(yīng)的2條路段進(jìn)行選擇，查找車流密度表，選擇車流密度ρ較大連通性好的路段進(jìn)行貪婪轉(zhuǎn)發(fā)。

c.若這2條路段的車流密度ρ均為0，則等待一個(gè)時(shí)間T。如果T時(shí)間后可以傳輸，則轉(zhuǎn)到步驟(b)；如果T時(shí)間后ρ仍然為0，則采用GPSR經(jīng)典的右手周邊轉(zhuǎn)發(fā)模式。

如圖3所示，A為源節(jié)點(diǎn)，H為目的節(jié)點(diǎn)。根據(jù)本文的路由協(xié)議，源節(jié)點(diǎn)A將數(shù)據(jù)包傳輸?shù)绞致房诠?jié)點(diǎn)a時(shí)，節(jié)點(diǎn)a進(jìn)行決策轉(zhuǎn)發(fā)，選擇車流密度大的a—b路段進(jìn)行傳輸，傳輸路徑為A—a—C—D—b—F—G—h—H。如果按照GPSR貪婪轉(zhuǎn)發(fā)，十字路口節(jié)點(diǎn)會(huì)選擇離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)E，傳輸路徑為選擇A—a—E,由于沒有下一跳可進(jìn)行選擇，發(fā)生中斷，而自動(dòng)回退，大大降低了傳輸效率。從圖3中可以看出：基于車流密度的VANETs協(xié)議考慮了車流密度對(duì)數(shù)據(jù)傳輸?shù)挠绊?，通過十字路口節(jié)點(diǎn)選擇車流密度大、局部最優(yōu)的路段進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，達(dá)到全局較優(yōu)，明顯減少了跳數(shù)和傳輸時(shí)延，提高了傳輸效率。

圖3 新協(xié)議中的決策轉(zhuǎn)發(fā)Fig 3 Decision making and forwarding in new protocol

1.4 鏈路中斷預(yù)測(cè)和局部路由修復(fù)機(jī)制

由于VANETs中節(jié)點(diǎn)高速移動(dòng)的特點(diǎn)，可能會(huì)發(fā)生鏈路中斷。傳統(tǒng)的路由協(xié)議中，都是在鏈路中斷發(fā)生以后再重新進(jìn)行路由發(fā)現(xiàn)，這肯定會(huì)對(duì)數(shù)據(jù)的傳輸帶來一定的延時(shí)，尤其是對(duì)時(shí)間要求比較嚴(yán)格的系統(tǒng)，如碰撞避免系統(tǒng)，帶來的嚴(yán)重后果不堪設(shè)想，為了避免由于鏈路中斷而重新進(jìn)行路由發(fā)現(xiàn)時(shí)帶來的延時(shí)，本文提出一種鏈路中斷預(yù)測(cè)和修復(fù)機(jī)制。

當(dāng)節(jié)點(diǎn)處于某路段中時(shí)，以十字路口節(jié)點(diǎn)為標(biāo)桿，節(jié)點(diǎn)根據(jù)自身的位置移動(dòng)可判斷自己的運(yùn)動(dòng)方向，將包含自身位置信息的信標(biāo)信息中加入方向信息廣播給鄰居節(jié)點(diǎn)，因此，節(jié)點(diǎn)可以預(yù)測(cè)自己與鄰居節(jié)點(diǎn)間的相對(duì)距離，是否超出了通信半徑，可對(duì)鏈路中斷進(jìn)行提前預(yù)測(cè)。當(dāng)一條鏈路即將發(fā)生中斷，開始局部修復(fù)過程。該協(xié)議中，對(duì)鏈路中斷分為2種情況，因此，修復(fù)過程也分為2種：

1)有可以選擇的下一跳節(jié)點(diǎn)：此時(shí)，則根據(jù)動(dòng)態(tài)源路由(dynamic source routing,DSR)[6]算法，選擇合適的下一跳，并向源節(jié)點(diǎn)發(fā)送一個(gè)包含中斷鏈路信息的路由錯(cuò)誤信息，源節(jié)點(diǎn)在路由表中將此路由刪除。

2)沒有可以選擇的下一跳節(jié)點(diǎn)：但如果發(fā)生中斷的節(jié)點(diǎn)距離源節(jié)點(diǎn)的跳數(shù)少于m，則發(fā)回一個(gè)包含鏈路中斷信息數(shù)據(jù)包給源節(jié)點(diǎn)，重新進(jìn)行路由發(fā)現(xiàn)；否則，在中斷處進(jìn)行 2 跳范圍內(nèi)廣播，進(jìn)行局部修復(fù)處理，并將包含錯(cuò)誤鏈路信息的數(shù)據(jù)包轉(zhuǎn)發(fā)回給源節(jié)點(diǎn)，讓源節(jié)點(diǎn)刪除此路由信息，以免在下一次路由選擇時(shí)再選擇此路徑。

2 實(shí)驗(yàn)仿真

本文采用Matlab對(duì)改進(jìn)后的基于車流密度的VANETs路由協(xié)議和GPSR,GPCR協(xié)議進(jìn)行大量仿真實(shí)驗(yàn)，在傳輸延遲和分組投遞成功率性能方面進(jìn)行比較分析。應(yīng)用VanetMobiSim來產(chǎn)生接近現(xiàn)實(shí)交通情況的拓?fù)浣Y(jié)構(gòu)仿真模型。設(shè)置場(chǎng)景大小為1 000 m×1 000 m，選擇節(jié)點(diǎn)數(shù)從40～180個(gè)隨機(jī)分布，隨機(jī)選擇一對(duì)節(jié)點(diǎn)進(jìn)行通信。節(jié)點(diǎn)間的最大有效通信距離為250 m，信道容量為2 MB/s。節(jié)點(diǎn)的最大運(yùn)動(dòng)速度為50 m/s，仿真持續(xù)時(shí)間為600 s。

從圖4中可以看出:當(dāng)節(jié)點(diǎn)個(gè)數(shù)增加時(shí)，3種協(xié)議平均端到端時(shí)延變化的比較。當(dāng)節(jié)點(diǎn)個(gè)數(shù)增多時(shí)，節(jié)點(diǎn)連通性更好，平均時(shí)延均在減小。本文所研究的路由協(xié)議，由于考慮到車流密度即連通性對(duì)路由的影響，在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)選擇連通性好的路徑轉(zhuǎn)發(fā)，傳輸時(shí)延大大減少。比GPSR的平均時(shí)延減少40 %，與GPCR比較也減少了25 %，實(shí)時(shí)性好。圖5顯示了數(shù)據(jù)分組成功投遞率的比較情況，相比之下，可以看出：采用本文的協(xié)議的數(shù)據(jù)分組成功投遞率基本持續(xù)在90 %以上較高水平，在節(jié)點(diǎn)較少時(shí)仍能保持較高成功率，且較穩(wěn)定。因此，從實(shí)驗(yàn)結(jié)果可以看出：本文所研究的基于車流密度的VANETs路由協(xié)議在數(shù)據(jù)分組的成功轉(zhuǎn)發(fā)率基本高達(dá)90 %多，時(shí)延也明顯減少，實(shí)時(shí)性強(qiáng)，遠(yuǎn)遠(yuǎn)優(yōu)于GPSR和GPCR協(xié)議，整體性能顯著提高。

圖4 平均端到端時(shí)延比較Fig 4 Comparison of average end-to-end time delay

圖5 數(shù)據(jù)分組成功投遞率比較Fig 5 Comparison of data packet successful delivery rate

3 結(jié) 論

為了解決道路交通狀況極大地影響VANETs路由傳輸性能和鏈路穩(wěn)定性的問題，提出了基于車流密度的VANETs路由協(xié)議。充分考慮了車流密度和節(jié)點(diǎn)運(yùn)動(dòng)速度、方向等因素，能夠根據(jù)車流密度信息，選擇車流密度較好、局部最優(yōu)的路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，達(dá)到全局較優(yōu)，避免由于道路稀疏引起路由中斷而自動(dòng)回退的問題，大大減少時(shí)延和跳數(shù)。同時(shí)對(duì)由于節(jié)點(diǎn)高速運(yùn)動(dòng)引起的鏈路中斷進(jìn)行預(yù)測(cè)，及時(shí)有效地修復(fù)，保證了鏈路的實(shí)時(shí)性和穩(wěn)定性。通過仿真實(shí)驗(yàn)驗(yàn)證：該協(xié)議在數(shù)據(jù)傳輸中在性能方面得到顯著提高，具有高實(shí)時(shí)性和可靠性。

[1] Karp B,Kung T H.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proceedings of the 6th Annual Internatio-nal Conference on Mobile Computing and Networking(MOBICOM’00),Boston,MA,USA:ACM,2000:243-254.

[2] Lochert C,Hartenstein H,Tian J,et al.A routing strategy for vehicular Ad Hoc networks in city environments[C]∥Proceedings of the IEEE Intelligent Vehicles Symposium，IVS’03,Columbus,OH,USA,2003:156-161.

[3] Shu Zhengzheng,Yu Min,Zou Chengwu.An improved clockwise grid routing protocol based on geographic location information[C]∥2012 Second International Conference on Electric Information and Control Engineering，ICEICE 2012,Lushan,China,2012.

[4] Lochert C,Mauve M,Fussler H,et al.Geographic routing in city scenarios[J].ACM SIGMOBLE Mobile Computing and Communications Review,2005,9(1):69-72.

[5] Lee C K,Le M,Harri J.LOUVRE:Landmark overlays for urban vehicular routing environments[C]∥Proceedings of the 68th IEEE Vehicular Technology Conference，VTC-Fall’08,Calgary,Canada:2008-5.

[6] 符媛柯，唐 倫.車載自組織網(wǎng)絡(luò)路由協(xié)議及研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用，2013，33(7)：1793-1797，1801.

[7] Kouah Riad,Moussaoui Samira,Aissani Mohamed. Direction-based greedy forwarding in mobile wireless sensor networks[C]∥The Eighth Advanced International Conference on Telecommunications,AICT 2012,2012:69-74.

[8] Lai Liangli,Wang Qianping,Wang Qun.Research on one kind of improved GPSR algorithm[C]∥2012 International Conference on Computer Science and Electronics Engineering,2012:715-718.

[9] Singh Pranav Kumar, Lego Kapang, Tuithung Dr Themrichon. Simulation-based analysis of Ad Hoc routing protocol in urban and highway scenario of VANET[J].International Journal of Compu-ter Application,2011,12(10):42-49.

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

Routing protocol based on vehicle density in VANETs*

ZHOU Mei-li, YU Min

(School of Computer and Information Engineering,Jiangxi Normal University,Nanchang 330022,China)

In the VANETs of high-speed movement of nodes,road traffic conditions greatly affect the performance of data transmission in the network.On the basis of greedy perimeter stateless routing(GPSR) routing protocol,propose a routing protocol based on vehicle density in VANETs.The new protocol considers the factor of vehicle density and speed and direction of node movement,then designs the calculation method of vehicle density and makes new forwarding strategy instead of the greedy forwarding strategy of GPSR,which can select the path of better vehicle density to forwarding data to avoid phenomena of local maxima caused by uneven distribution of vehicle density.And can predict about link interruption caused by high-speed movement of nodes,then proposes effective repair mechanism to establish a stable VENETs routing of robust link.The performance of GPSR,and GPCR is compared by simulation using Matlab.The simulation results show that the capability of the new protocol is improved significantly compared with the other two routing protocols on delay time and forwarding rate and it is suitable to be applied in city scenes.

VANETs； vehicle density； link interruption

2013—08—15

國(guó)家自然科學(xué)基金資助項(xiàng)目(41164001)；國(guó)際科技合作專項(xiàng)項(xiàng)目(35—14)

TP 393

A

1000—9787(2014)04—0118—04

周美麗(1990-)，女，江西撫州人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。