方向和位置泛洪的車聯網區域路由協議

孫友偉，孫小田，王 楠

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

?

方向和位置泛洪的車聯網區域路由協議

孫友偉，孫小田，王 楠

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

為提高車載自組網路由發現、數據傳輸效率，對區域路由協議進行改進。考慮到車載自組網(VANET)通信環境(道路布局、方向、位置等)多樣性，通過判斷節點間位置關系縮小泛洪區域，下一跳優先選擇該區域內與源或目的節點移動方向相同的節點，進一步減少轉發節點數目，以此精細化限制泛洪。為適應VANET拓撲頻繁變化鏈路脆弱特性，目的節點優先選擇相同移動方向節點數最多，且平均鄰居節點數最多的鏈路，保證數據可靠傳輸。仿真結果顯示:改進方案較好地克服了原協議全向洪泛引起的網絡開銷大、單一跳數路由選擇導致的丟包率、重傳率較高等缺點，能夠較好地適應VANET網絡通信。

車載自組網;區域路由協議;位置信息;移動方向;平均鄰居節點數目

0 引 言

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

目前可用在VANET中的路由協議分為先應式、反應式和混合式路由協議[4,5]。由于網絡拓撲變化信息只在局部范圍內、短期時間內產生影響，因此,采用分區機制的混合路由協議更加適用于VANET[6,7]。目前對典型混合式路由—區域路由協議[8](zone routing protocol,ZRP)的研究主要集中在優化區域半徑，引入位置輔助等方面[9,10]。

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

1 改進方案DL-ZRP

1.1 路由發現

VANET中，汽車移動軌跡受道路布局、時速、紅綠燈等條件約束，行駛路線及移動信息具有可預測性。基于定向區域的泛洪機制[12]因未考慮到道路限制、節點方向、位置關系等因素，不適用于VANET。如圖1，當源、目的節點不在同一道路上且相距較遠時，確定的定向路由請求區域內節點較少，路由成功概率較低。

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

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

1.1.1 汽車節點方向定義

根據道路布局多樣性，汽車移動方向可大致分為4個區域，如圖2。例如，汽車移動方向屬于“北”區域，即認為方向為北。兩汽車節點間移動方向關系共有10種。

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

1.1.2 兩汽車節點位置關系

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

圖3 汽車節點位置關系分類Fig 3 Classification of location relationship of automobile

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

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

1)位置判斷

VANET中，最佳路由請求區域既要盡可能覆蓋S,D的有效活動區域和尋路所必須的中間節點，又要充分限制無效泛洪，還要考慮道路、位置、方向等。基于此，位置判斷限制泛洪過程如下(把道路抽象為二維平面)：

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

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

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

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

2)方向判斷

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

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

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

綜上，基于方向和位置泛洪機制的中間節點I路由發現流程如圖5。

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

1.2 路由選擇

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

路由轉發階段，規定與S/D同向或反向中間節點均轉發RREQ。但互為反向關系的兩節點鏈路較脆弱，路由應優先選擇鏈路上與S/D相同方向節點數目較多的鏈路。僅當中間節點周圍沒有同向鄰節點時，才選擇反向鄰節點傳遞數據。

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

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

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

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

2)ZRP允許目的節點所在區域內的節點應答RREQ。為根據鏈路狀況更好地選擇路由，規定只有目的節點才可回復RREP。目的節點允許重復接收同一源節點發送的RREQ。

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

4)路由選擇以整條鏈路平均鄰居節點數Navg_neighbor和與S/D同向節點數Nsd_number作為計算權值的參數，根據節點密度的不同，選取適當的加權系數a，第i條鏈路權值計算方法如下

Li=aNavg_neighb or+(1-a)Nsd_number

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

目的節點通過計算選取Lopt的鏈路回送RREP給前驅節點。

2 性能評估

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

本次使用Network Simulator version 2，結合VanetMobosim軟件生成的trace信息進行仿真，參數見表1。

表1 仿真參數

2.1 分組投遞率

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

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

2.2 控制開銷

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

圖7 控制開銷Fig 7 Control overhead

2.3 平均端到端時延

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

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

3 結 論

本文針對VANET關鍵技術的路由算法，結合實際通信環境，提出適用于VANET的ZRP改進方案(DL-ZRP)。改進方案僅針對網格型道路布局進行了改進。下一步需考慮各地道路布局多樣性，結合實際通信環境，優化完善并實地驗證。

[1] 許富龍,劉志建.車載自組織網絡路由協議研究進展與比較[J].電訊技術,2013,53(10):1393-1400.

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

[3] 周美麗,余 敏.基于車流密度的VANETs路由協議[J].傳感器與微系統,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] 黃 欣,余思東,萬榮澤.面向城市環境VANETS的基于Beacon控制的路由協議[J].計算機測量與控制,2014,22(12):4078-4080.

[6] 陳耀華,彭凌西.關于VANETs路由協議的研究現狀與進展[J].傳感器與微系統,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路由協議的NDP優化與仿真分析[J].無線電工程,2007,37(7):4-6,43.

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

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

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

[12] 張棋飛,劉 威,楊宗凱,等.基于位置信息的自適應Ad Hoc路由協議[J].計算機科學,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-),男，陜西西安人,教授,從事通信網絡研究工作。