方向和位置泛洪的車聯(lián)網(wǎng)區(qū)域路由協(xié)議

孫友偉，孫小田，王 楠

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

?

方向和位置泛洪的車聯(lián)網(wǎng)區(qū)域路由協(xié)議

孫友偉，孫小田，王 楠

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

為提高車載自組網(wǎng)路由發(fā)現(xiàn)、數(shù)據(jù)傳輸效率，對區(qū)域路由協(xié)議進(jìn)行改進(jìn)。考慮到車載自組網(wǎng)(VANET)通信環(huán)境(道路布局、方向、位置等)多樣性，通過判斷節(jié)點間位置關(guān)系縮小泛洪區(qū)域，下一跳優(yōu)先選擇該區(qū)域內(nèi)與源或目的節(jié)點移動方向相同的節(jié)點，進(jìn)一步減少轉(zhuǎn)發(fā)節(jié)點數(shù)目，以此精細(xì)化限制泛洪。為適應(yīng)VANET拓?fù)漕l繁變化鏈路脆弱特性，目的節(jié)點優(yōu)先選擇相同移動方向節(jié)點數(shù)最多，且平均鄰居節(jié)點數(shù)最多的鏈路，保證數(shù)據(jù)可靠傳輸。仿真結(jié)果顯示:改進(jìn)方案較好地克服了原協(xié)議全向洪泛引起的網(wǎng)絡(luò)開銷大、單一跳數(shù)路由選擇導(dǎo)致的丟包率、重傳率較高等缺點，能夠較好地適應(yīng)VANET網(wǎng)絡(luò)通信。

車載自組網(wǎng);區(qū)域路由協(xié)議;位置信息;移動方向;平均鄰居節(jié)點數(shù)目

0 引 言

車載自組網(wǎng)[1，2](vehicle Ad Hoc network,VANET)是指車和車或車和路邊單元之間自發(fā)建立的一個多跳網(wǎng)絡(luò)，更好地適應(yīng)道路、車輛引起的交通變化，確保人們能夠暢通出行、安全出行、快樂出行。VANET因其拓?fù)漕l繁變化、節(jié)點移動性強、鏈路脆弱、運動軌跡受限于道路布局等特點，路由技術(shù)要求嚴(yán)苛[3]。

目前可用在VANET中的路由協(xié)議分為先應(yīng)式、反應(yīng)式和混合式路由協(xié)議[4,5]。由于網(wǎng)絡(luò)拓?fù)渥兓畔⒅辉诰植糠秶鷥?nèi)、短期時間內(nèi)產(chǎn)生影響，因此,采用分區(qū)機制的混合路由協(xié)議更加適用于VANET[6,7]。目前對典型混合式路由—區(qū)域路由協(xié)議[8](zone routing protocol,ZRP)的研究主要集中在優(yōu)化區(qū)域半徑，引入位置輔助等方面[9,10]。

VANET中車輛行駛軌跡受道路布局、交通規(guī)則等限制，數(shù)據(jù)傳輸只能沿著道路布局傳播，路由方向可能需要隨著道路布局發(fā)生“拐彎”。傳統(tǒng)ZRP未考慮到VANET實際通信環(huán)境，不太適用于VANET[11]。因此，本文根據(jù)VANET特性提出ZRP改進(jìn)方案(DL-ZRP)。提出一種基于移動方向和位置泛洪機制，并利用節(jié)點的鄰居節(jié)點數(shù)和相同方向節(jié)點數(shù)共同進(jìn)行路由選擇，從而提高ZRP協(xié)議各項性能參數(shù)，以滿足VANET需求。

1 改進(jìn)方案DL-ZRP

1.1 路由發(fā)現(xiàn)

VANET中，汽車移動軌跡受道路布局、時速、紅綠燈等條件約束，行駛路線及移動信息具有可預(yù)測性?；诙ㄏ騾^(qū)域的泛洪機制[12]因未考慮到道路限制、節(jié)點方向、位置關(guān)系等因素，不適用于VANET。如圖1，當(dāng)源、目的節(jié)點不在同一道路上且相距較遠(yuǎn)時，確定的定向路由請求區(qū)域內(nèi)節(jié)點較少，路由成功概率較低。

圖1 定向區(qū)域限制泛洪局限性例圖Fig 1 Example of restricted flooding area

考慮到道路限制因素，提出基于方向和位置泛洪機制。利用GPS設(shè)備可獲取汽車位置坐標(biāo)、速度、方向等信息，結(jié)合電子地圖，可判斷兩節(jié)點是否處在同一道路，繼而可利用移動方向關(guān)系、位置關(guān)系精細(xì)化限制泛洪。

1.1.1 汽車節(jié)點方向定義

根據(jù)道路布局多樣性，汽車移動方向可大致分為4個區(qū)域，如圖2。例如，汽車移動方向?qū)儆凇氨薄眳^(qū)域，即認(rèn)為方向為北。兩汽車節(jié)點間移動方向關(guān)系共有10種。

圖2 汽車移動方向分類Fig 2 Classification of automobile movement direction

1.1.2 兩汽車節(jié)點位置關(guān)系

曼哈頓模型中，根據(jù)目的節(jié)點D在源節(jié)點S的具體方位，可得出兩者處在同一條道路上時，位置關(guān)系為正北、正南、正西、正東；不在同一道路上，位置關(guān)系為東北、西北、西南、東南。如圖3，D正北位于S的正北方位，D東北位于S的東北方位。

圖3 汽車節(jié)點位置關(guān)系分類Fig 3 Classification of location relationship of automobile

1.1.3 基于移動方向和位置泛洪機制

當(dāng)源節(jié)點S、目的節(jié)點D不在同一道路時，路由方向可能需要隨著道路布局發(fā)生“拐彎”。為有效限制泛洪，通過詳細(xì)列舉分析S,D間的方向關(guān)系、位置關(guān)系，考慮兩節(jié)點間鏈路持續(xù)時間(移動方向相關(guān))，可利用位置判斷(縮小泛洪區(qū)域)、方向判斷(減少轉(zhuǎn)發(fā)個數(shù))來限制泛洪。

1)位置判斷

VANET中，最佳路由請求區(qū)域既要盡可能覆蓋S,D的有效活動區(qū)域和尋路所必須的中間節(jié)點，又要充分限制無效泛洪，還要考慮道路、位置、方向等?；诖耍恢门袛嘞拗品汉檫^程如下(把道路抽象為二維平面)：

中間節(jié)點I接收到源節(jié)點S廣播的路由請求(routing request,RREQ)，首先判斷S,D是否處在同一道路上。

①S和D處在同一道路，位置關(guān)系為正北、正南、正西、正東。此種單一位置關(guān)系將二維平面分為2個區(qū)域，此時無論S,D方向關(guān)系如何，S只需朝著D所在區(qū)域(1/2區(qū)域)泛洪即可有效縮小泛洪區(qū)域。如圖4，D正北位于S的正北位置，有效中間節(jié)點區(qū)域為位于S北部區(qū)域(含東北和西北區(qū)域以及坐標(biāo)邊界)。因此，只需在該區(qū)域內(nèi)(陰影部分)泛洪，即I判斷自己是否處在S北部區(qū)域內(nèi)，是,則轉(zhuǎn)發(fā)RREQ;否則,丟棄。

②S和D不在同一道路，位置關(guān)系為東北、西北、西南、東南。此種雙重位置關(guān)系將二維平面分為4個區(qū)域，此時無論S,D方向關(guān)系如何，S只需朝著D所在區(qū)域(1/4區(qū)域)泛洪即可有效縮小泛洪區(qū)域。如圖4，D東北位于S的東北位置，有效中間節(jié)點區(qū)域為S東北區(qū)域(含坐標(biāo)邊界)。因此，只需在該區(qū)域內(nèi)(陰影部分)泛洪，即I判斷自己是否處在S東北區(qū)域，是,則轉(zhuǎn)發(fā)RREQ;否則,丟棄。

圖4 位置判斷舉例Fig 4 Example of location judgment

2)方向判斷

汽車移動受道路限制，同一道路上節(jié)點移動方向并不相同(單雙車道、十字路口等)，僅位置判斷并不能很好地限制泛洪。VANET中，兩節(jié)點移動方向相同，鏈路持續(xù)時間可能較長，因此，還可依據(jù)節(jié)點移動方向關(guān)系限制泛洪。根據(jù)移動方向的不同，源節(jié)點S的鄰居節(jié)點分為：同向鄰節(jié)點、反向鄰節(jié)點、垂直鄰節(jié)點。路由轉(zhuǎn)發(fā)應(yīng)選擇同向或反向的節(jié)點轉(zhuǎn)發(fā)。這是因為互為垂直關(guān)系的兩節(jié)點鏈路持續(xù)時間短，隨時都有斷裂可能；互為同向關(guān)系的兩節(jié)點鏈路較為穩(wěn)定；互為反向關(guān)系的兩節(jié)點鏈路脆弱，但如果源節(jié)點周圍沒有同向鄰節(jié)點，通過位置判斷，反方向的前方鄰節(jié)點也可作為補充路由傳遞數(shù)據(jù)。

①S和D處于同一道路(方向關(guān)系為同向或反向)，位置判斷后泛洪區(qū)域較大，則處在1/2區(qū)域內(nèi)的中間節(jié)點I需要繼續(xù)進(jìn)行方向判斷來減小轉(zhuǎn)發(fā)節(jié)點個數(shù)。I接收RREQ后，判斷自己與S移動方向關(guān)系。同向和反向鄰節(jié)點轉(zhuǎn)發(fā)RREQ，垂直方向鄰節(jié)點丟棄。

②S和D不在同一道路(方向關(guān)系同向、反向、垂直均有可能)。路由方向可能需要隨著道路布局發(fā)生“拐彎”。處在1/4區(qū)域內(nèi)的中間節(jié)點I此時無需再進(jìn)行方向判斷。因為此時泛洪區(qū)域為最佳泛洪區(qū)域，繼續(xù)縮小區(qū)域可能導(dǎo)致找不到路由；S，D方向關(guān)系存在多種可能，繼續(xù)進(jìn)行方向判斷可能導(dǎo)致有效中間節(jié)點數(shù)目變少，不利于路由發(fā)現(xiàn)。

綜上，基于方向和位置泛洪機制的中間節(jié)點I路由發(fā)現(xiàn)流程如圖5。

圖5 基于移動方向和位置泛洪機制Fig 5 Flooding mechanism based on moving direction and location

1.2 路由選擇

VANET中，汽車節(jié)點頻繁加入或退出，以及速度、方向變化等因素，使得鏈路脆弱，路由維持時間較短，單純依據(jù)最小跳數(shù)選擇路由可行性低。一個節(jié)點的鄰居節(jié)點數(shù)目一定程度上反映了網(wǎng)絡(luò)局部拓?fù)湫畔?，若該?jié)點周圍鄰居節(jié)點較多，則節(jié)點所在鏈路斷裂修復(fù)成功可能性較大，所用時間也較短。因此，路由應(yīng)優(yōu)先選擇平均鄰居節(jié)點數(shù)較多的鏈路。

路由轉(zhuǎn)發(fā)階段，規(guī)定與S/D同向或反向中間節(jié)點均轉(zhuǎn)發(fā)RREQ。但互為反向關(guān)系的兩節(jié)點鏈路較脆弱，路由應(yīng)優(yōu)先選擇鏈路上與S/D相同方向節(jié)點數(shù)目較多的鏈路。僅當(dāng)中間節(jié)點周圍沒有同向鄰節(jié)點時，才選擇反向鄰節(jié)點傳遞數(shù)據(jù)。

綜合考慮，最優(yōu)路徑選擇由二者共同決定(定義組合判據(jù)L，詳見下文)。當(dāng)目的節(jié)點首次接收RREQ后，并不立刻回復(fù)路由應(yīng)答(routing reply,RREP)，等待Δt，對比此時間內(nèi)建立的j條鏈路的L值，優(yōu)先選擇L值最大的鏈路傳輸數(shù)據(jù)。具體如下：

1)RREQ中增加neighbor_number、sd_number字段。中間節(jié)點I通過泛洪機制判定后，還需進(jìn)行如下操作：

①I查詢自身鄰居列表，獲取鄰節(jié)點個數(shù)后累加至neighbor_number字段，最終的RREQ中neighbor_number字段(該數(shù)值記為Nsum_number)就記錄了整條鏈路上所有節(jié)點的鄰居節(jié)點數(shù)目和。

②I判斷自己是否和S/D為同方向(S/D任一即可)，是,則sd_number字段加1;否則,不操作。最終的RREQ的sd_number(該數(shù)值記為Nsd_number)字段就記錄了該條鏈路中與S/D同方向的節(jié)點個數(shù)。

2)ZRP允許目的節(jié)點所在區(qū)域內(nèi)的節(jié)點應(yīng)答RREQ。為根據(jù)鏈路狀況更好地選擇路由，規(guī)定只有目的節(jié)點才可回復(fù)RREP。目的節(jié)點允許重復(fù)接收同一源節(jié)點發(fā)送的RREQ。

3)目的節(jié)點接收RREQ后，計算鏈路平均鄰居節(jié)點數(shù)(k為跳數(shù)，Ni為該鏈路第i個節(jié)點的鄰居節(jié)點數(shù)目)

4)路由選擇以整條鏈路平均鄰居節(jié)點數(shù)Navg_neighbor和與S/D同向節(jié)點數(shù)Nsd_number作為計算權(quán)值的參數(shù)，根據(jù)節(jié)點密度的不同，選取適當(dāng)?shù)募訖?quán)系數(shù)a，第i條鏈路權(quán)值計算方法如下

Li=aNavg_neighb or+(1-a)Nsd_number

Lopt=max{L1,L2,L3,…，Li}

目的節(jié)點通過計算選取Lopt的鏈路回送RREP給前驅(qū)節(jié)點。

2 性能評估

城市道路場景中，車輛運動軌跡受道路布局和交通規(guī)則限制，節(jié)點數(shù)目較多，且城區(qū)限速0～60 km/h。因此，仿真主要考慮車輛密度因素。

本次使用Network Simulator version 2，結(jié)合VanetMobosim軟件生成的trace信息進(jìn)行仿真，參數(shù)見表1。

表1 仿真參數(shù)

2.1 分組投遞率

圖6反映了車輛密度與分組投遞率關(guān)系。車輛較少時，網(wǎng)絡(luò)吞吐率較好，分組投遞率較高；車輛達(dá)到80個時，吞吐率較低，大量分組丟失、重傳，再丟失、再重傳，網(wǎng)絡(luò)逐漸堵塞嚴(yán)重，分組投遞率急劇下降。DL-ZRP較之ZRP，分組投遞率變化平緩，且相同車輛密度下，分組投遞率較小。這是因為DL-ZRP中分組包括位置分組(ZRP不存在)、路由分組、數(shù)據(jù)分組，無形中占用了一小部分帶寬；但DL-ZRP基于方向和位置泛洪機制，RREQ較少，帶寬占用小，同時路由選擇最優(yōu)組合判據(jù)，分組傳輸成功率較高，緩解了網(wǎng)絡(luò)擁塞，分組投遞率高于ZRP。

圖6 分組投遞率Fig 6 Packet delivery rate

2.2 控制開銷

圖7中，ZRP與DL-ZRP控制開銷隨車輛增多均呈上升趨勢。車輛較少(小于60)時，雖然DL-ZRP存在額外位置分組，增加了一部分開銷，但其采用基于方向和位置泛洪機制，RREQ較少，相較于ZRP廣播泛洪，控制開銷相差不大。當(dāng)車輛數(shù)目達(dá)到70個，通信量大幅增加，ZRP由于區(qū)域內(nèi)、外均采用廣播，控制開銷激增。而DL-ZRP基于方向和位置泛洪機制，總控制開銷較少，且組合判據(jù)選擇的鏈路可靠性高，避免了鏈路修復(fù)、消息重傳產(chǎn)生的額外開銷，較于ZRP，DL-ZRP控制開銷更小。

圖7 控制開銷Fig 7 Control overhead

2.3 平均端到端時延

圖8反映了平均端到端時延隨密度變化情況。車輛數(shù)目小于60個，網(wǎng)絡(luò)相對稀疏，路由發(fā)現(xiàn)較快，相應(yīng)平均端到端時延較小。當(dāng)車輛數(shù)目大于80個，吞吐量降低，大量分組重傳造成擁塞惡化，端到端時延激增。DL-ZRP平均端到端時延優(yōu)于ZRP，雖然DL-ZRP計算量較大、位置處理增加了網(wǎng)絡(luò)時延，但其基于方向和位置泛洪機制、以及組合判據(jù)的路由選擇，網(wǎng)絡(luò)開銷減少，分組傳輸成功率較高，同向鄰節(jié)點轉(zhuǎn)發(fā)使得分組快速傳播至目的節(jié)點，正確的傳播方向大大縮短了傳輸時間，優(yōu)勢大于劣勢，從而平均端到端時延小于ZRP。

圖8 平均端到端時延Fig 8 Average end-to-end delay

3 結(jié) 論

本文針對VANET關(guān)鍵技術(shù)的路由算法，結(jié)合實際通信環(huán)境，提出適用于VANET的ZRP改進(jìn)方案(DL-ZRP)。改進(jìn)方案僅針對網(wǎng)格型道路布局進(jìn)行了改進(jìn)。下一步需考慮各地道路布局多樣性，結(jié)合實際通信環(huán)境，優(yōu)化完善并實地驗證。

[1] 許富龍,劉志建.車載自組織網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展與比較[J].電訊技術(shù),2013,53(10):1393-1400.

[2] 張瑞鋒.車載自組網(wǎng)通信技術(shù)研究綜述[J].汽車研究與開發(fā),2014,4(2):79-85.

[3] 周美麗,余 敏.基于車流密度的VANETs路由協(xié)議[J].傳感器與微系統(tǒng),2014,33(4):118-121.

[4] Gavin Holland,Nitin Vaidya.Analysis of TCP performance over mobile Ad Hoc networks[J].Wireless Networks,2002,8(2):275-288.

[5] 黃 欣,余思東,萬榮澤.面向城市環(huán)境VANETS的基于Beacon控制的路由協(xié)議[J].計算機測量與控制,2014,22(12):4078-4080.

[6] 陳耀華,彭凌西.關(guān)于VANETs路由協(xié)議的研究現(xiàn)狀與進(jìn)展[J].傳感器與微系統(tǒng),2014,33(3):1-4.

[7] Pomenka P.Wireless local area networks:A comprehensive guid-e[J].Radioengineering,2002,11(4):30-33.

[8] 馬明輝,武曉慶,武穆清.ZRP路由協(xié)議的NDP優(yōu)化與仿真分析[J].無線電工程,2007,37(7):4-6,43.

[9] 李 琳,武穆清.ZRP區(qū)域路由協(xié)議分析[J].數(shù)字通信世界,2007(11):52-55.

[10] 邱朋義,王洪玉.基于位置信息的AODV路由協(xié)議[D].大連:大連理工大學(xué),2008.

[11] 施榮華,羅棋峰.一種MANET中基于位置信息的ZRP路由協(xié)議[J].湖南大學(xué)學(xué)報:自然科學(xué)版,2009,36(8):38-42.

[12] 張棋飛,劉 威,楊宗凱,等.基于位置信息的自適應(yīng)Ad Hoc路由協(xié)議[J].計算機科學(xué),2007,34(5):20-24.

Zone routing protocol based on direction and location flooding for VANET

SUN You-wei,SUN Xiao-tian,WANG Nan

(School of Communication and Information Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710121,China)

In order to improve efficiency of data transmission and routing discovery in VANET,zone routing protocol is improved.Considering the diversity of VANET communication environment,including road layout,moving direction,location,etc,restricted flooding mechanism is to reduce the flooding area by judging the position relationship between nodes,to further reduce the forwarding node number,the next hop select the nodes that has the same movement direction with source node.In order to adapt to frequent changes in the VANET,the destination node select preferentially the link that has the maximum of average number of neighbor nodes and number of nodes in the same direction of movement.Simulation results show that the improved protocol overcome some downside of original protocol,such as the large overhead caused by omnidirectional flooding,high packet loss rate and high retransmission rate caused by the way of simple routing selection etc,and the improved ZRP scheme is proved better adapt to vehicles communication in VANET.

VANET;zone routing protocol;location information;direction of movement;average number of neighbor nodes

10.13873/J.1000—9787(2016)11—0136—04

2016—01—21

TN 913.6

A

1000—9787(2016)11—0136—04

孫友偉(1956-),男，陜西西安人,教授,從事通信網(wǎng)絡(luò)研究工作。