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

孫友偉, 孫小田, 王　楠

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

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

孫友偉, 孫小田, 王楠

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

摘要:為提高車載自組網通信中路由發現和數據傳輸的效率，對區域路由協議進行改進。在分組中加入節點坐標、速度和時間字段，各節點接收分組后，記錄或更新此信息到自身位置緩存表。路由發現階段，節點位移大于位置更新半徑時才更新路由，以此減少路由發現次數；非目的節點查詢位置緩存表或路由表后直接應答，以此加快路由發現時間。數據傳輸階段，節點通過定向區域轉發以限制泛洪，以此降低控制開銷。通過搭建車聯網場景，對60個節點在5～50 m/s速度下進行仿真實驗，結果顯示，改進方案可使時延降低6%～13%，分組投遞率增加6%～20%。另當節點速度大于35 m/s時，可使控制開銷減少7%～14%。

關鍵詞:車載自組網;區域路由協議;位置信息;位置緩存表;定向限制泛洪

車載自組網(VehicleAdhocNetwork,VANET)是指車人、車車、車路和車云之間，通過實時交通信息的采集、共享、發布和處理，更好地對道路和車輛進行實時監控和調度，以保障人們的出行安全和出行效率[1-2]。在VANET中，汽車節點隨機運動具有很高移動性，對路由技術有著更為嚴苛的要求，以適應快速變化的網絡拓撲重構[3]。VANET路由協議可分為先應式、反應式和混合式3種[4-5]，大部分由移動自組網路由協議改進而來，因各有側重，缺乏普遍適用性，難以滿足VANET不同場景的實際需求[6-7]。

作為混合路由協議的代表，區域路由協議(ZoneRoutingProtocol,ZRP)[8]將網絡劃分為若干虛擬區域，區域內采用先應式路由，區域間采用反應式路由。當源節點存在通信需求時，首先查詢源節點和目的節點是否處在同一區域內。若在，則直接發送；若不在，啟動區域間路由發現，由邊界傳播分解協議(BordercastResolutionProtocol,BRP)構造邊界廣播樹，將路由請求直接擴散到邊界節點，由邊界節點進行區域內查找，直至找到目的節點。ZRP繼承并結合了先應式和反應式路由的優點，可用于VANET。目前，關于ZRP協議的研究主要集中在優化區域半徑和引入位置輔助方面[9-10]。

ZRP中分組傳播均通過廣播形式全向擴散，占用大量信道資源，開銷較大。借鑒現實生活中尋找目標的方法，假設知道目標位置，即可有針對性地只在目標活動軌跡范圍內進行查找，從而更快更省地找到目標。

本文擬對ZRP進行改進，利用節點位置信息(坐標、速度和時間)指導路由發現過程，繼而通過計算定向區域轉發進行精細化限制泛洪，給出基于位置和定向泛洪的區域路由協議(Location-basedandRestricted-floodingZRP,LR-ZRP)，以求提高ZRP協議路由發現和數據傳輸的效率，滿足VANET對時延、開銷的特殊需求。

1區域路由協議改進

1.1位置更新

ZRP協議中，區域內路由協議(IntrazoneRoutingProtocol,IARP)使用先應式路由，周期性交換路由信息，將由拓撲變化產生的信息傳播限制在區域內部，區域間路由協議(InterzoneRoutingProtocol,IERP)使用反應式路由，需要時才開始路由發現[11]。ZRP區域劃分重疊度較高，若網絡拓撲變化較慢，節點相對位置變化較小，則頻繁盲目地發起路由更新，容易導致多余網絡開銷，增加延時。

LR-ZRP引入位置觸發機制，結合周期性更新和位置更新，繼而指導路由更新。LR-ZRP能夠根據節點運動狀況，對尋路過程作出及時自適應修復或優化路由，從而更準確有效地維護區域內路由。

1.1.1位置觸發更新機制

借鑒無線通信手機尋找基站的方式，當節點發現自己的位置區移動到一個新地方，就主動告知，向周圍節點發起位置更新。例如，設置位置更新半徑R，節點在時刻t0位于(X0，Y0)，時刻t1運動到(X1，Y1)，若

則主動廣播一個位置更新分組(LocationUpdatePacket,LUDP)給周圍節點，其中包括節點當前速度、時間和坐標字段，否則，不更新位置。如此，則可保證位置信息的實時性。

1.1.2周期性更新機制

由于累積效應，各節點自身位置變化不大，但是節點之間間距變大，鏈路可能發生變化?；蛘哂捎谖恢米兏⒋嬖跁r效性，節點位置并沒有變化，但受網絡信號影響，無法找到該節點。保留周期性位置更新，要求節點每隔一定時間，不管位置區有沒有變化，都發起向周圍節點發起位置更新，可保證位置信息的有效性。

當LR-IARP結合位置觸發和周期性位置更新，獲知到區域內節點位置信息引起的路由發生變化后，主動通知LR-IERP進行路由更新。LR-IERP可及時進行無效路由修復和最佳路由優化。

1.2位置緩存表

定位設備只可幫助節點獲知到自身位置信息[12]，包括當前速度、時間和坐標，但路由發現時，還需知道其他節點位置信息，且位置信息越即時，路由就越精確。LR-ZRP協議中，通過位置觸發和周期性更新機制，各節點需要維護一張位置緩存表和一張路由表。位置緩存表記錄著周圍節點的位置信息，并定期清除無效信息，它就像是一張局部網絡拓撲圖。

LR-ZRP協議請求分組分為位置請求分組(LocationRequest,LREQ)和路由請求分組(RoutingRequest,RREQ)2種。每個LREQ分組均記錄自身節點、目的節點以及所經過中間節點的即時位置信息。當節點接收到LREQ分組后，都會對比時間字段的值，判斷時間新舊程度，創建或更新此信息到自己的位置緩存表，繼而優化或修復路由表。各節點位置信息實時更新，為定向精細化限制路由提供有效保障。

ZRP協議規定，只有目的節點所在區域內的節點，才可對接收到的路由請求回送路由應答，所以路由發現所用時間比較長。LR-ZRP協議中，源節點查找目的節點時，只需查詢當前節點位置緩存表或路由表，存在目的節點位置信息或路由信息，即可直接進行應答，能減小路由查詢時間。

1.3路由定向查找轉發

ZRP協議中，當目的節點處在本地區域之外時，IERP只能發起全向廣播進行盲目尋找，網絡開銷太大。LR-IERP利用節點實時位置信息，按位置區進行分區域尋找，能有目的地定向精準查找，有助減少廣播風暴產生。

源節點S通過查詢位置緩存表，獲知目的節點D在時刻t0所處位置和速度，估算D在時刻t1的可能活動范圍。最佳路由請求區域必須盡可能覆蓋S和D的有效活動區域，以及包含尋路所必須的中間節點。綜合考慮各節點位置估計誤差和時刻t1目的節點D可能區域預測誤差，以及搜索區域必須盡可能覆蓋必需的中間節點，還要充分限制無效泛洪，確定較為合理的路由請求區域。

若目的節點D在時刻t0位于(X0，Y0)，Vmax是t0到t1時間段內D的最大速度，則在時刻t1，D的可能活動區域是以r=Vmax×(t1-t0)為半徑的圓形區域。以該圓形區域的外接四邊形3個頂點和過S與D連線L的垂線,確定矩形區域ABCE，即為路由請求區域(圖1)。點A，B，C和E的縱橫坐標分別為

圖1　LR-ZRP請求區域

中間節點通過計算自己到矩形框各頂點的距離和，對比A點到B、C和E的距離和，從而判斷自己是否處在區域內。位于路由請求區域內節點才能參與轉發，若在區域之外，則不再繼續傳播，由此限制泛洪。

由于GPS設備各節點位置估計誤差、t1時刻D節點可能區域預測誤差以及有限搜索范圍未覆蓋有效中間節點等原因，都可能導致規定時間內未找到路由，則要修正搜索范圍重新查找，極端情況下回歸ZRP協議廣播查找。

邊界傳播分解協議LR-BRP工作機制類似于BRP，在此不再贅述。

2改進協議的路由轉發過程

2.1源節點獲取目的節點位置信息

源節點S存在通信需求時，需先獲知D位置，具體過程描述如下。

步驟1S查找自身位置緩存表中是否存在D的位置信息。若有，轉步驟4。若無，轉步驟2。

步驟2LR-IARP在本地區域內廣播位置請求。若成功，回送位置應答給S，并轉步驟4；若不成功，轉步驟3。

步驟3沿著BRP邊界樹，廣播位置請求。若成功，放入D位置信息，回送位置應答，轉步驟5；若不成功，回送位置錯誤。

步驟4判斷S和D是否同處一個區域。若是，直接轉發；否則，轉步驟5。

步驟5依據S和D的坐標計算路由請求區域，并加入S和D位置信息后生成路由請求，借助BRP邊界樹轉發。

具體流程如圖2所示。

圖2LR-ZRP中S的尋路流程

2.2中間節點的處理

中間節點可能是區域內部節點或廣播樹邊界節點，對其處理過程可描述如下。

步驟1 中間節點根據接收到的路由請求所攜帶信息和自身位置緩存表，對比信息新舊程度，互相更新。其中包括S、D的位置信息。

步驟2中間節點判斷是否為重復接收。若是，丟棄；若否，轉步驟3。

步驟3中間節點對比自身和路由請求所攜帶的D位置信息。若是目的節點，沿先前累積路由回送路由應答；若否，轉步驟4。

步驟4中間節點通過計算判定自己是否存在于確定的請求區域內部。如果不在，丟棄；如果在，轉步驟5。

步驟5中間節點標記所經路由記錄，繼續轉發。直至找到目的節點D。

步驟6S接收路由應答之后，確定路由已經成功建立，開始傳輸。至此，LR-ZRP尋路結束。

以上流程如圖3所示。

圖3　LR-ZRP中中間節點的尋路流程

3性能評估

使用NetworkSimulator(version2)進行仿真分析，具體參數見表1。節點隨機運動生成場景。由于LR-ZRP加入了位置觸發更新機制，需要設置檢測周期:節點速度小于30m/s時，每2s檢測一次; 其余設置為1s。

表1　仿真參數

3.1分組投遞率

節點運動加快導致位移范圍增大，網絡中無效鏈路增多，分組投遞率均隨之減小。同等速度狀況，LR-ZRP的分組投遞率較之ZRP的分組投遞率更好，如圖4所示，這是因為：ZRP區域內是周期性路由更新，無法根據節點當前實時運動狀況，針對性自適應修復和優化路由，鏈路失效導致分組投遞率較低：LR-ZRP結合位置觸發和周期性更新方式，借助位置緩存表信息，及時修正路由發現，能更加準確、有效地維護區域內外路由，分組投遞率也相應較高。

圖4　分組投遞率

3.2控制開銷

LR-ZRP協議引入了位置信息，控制開銷包括位置控制開銷和路由控制開銷兩部分。ZRP與LR-ZRP控制開銷隨速度的變化情況如圖5所示。隨著最大移動速度增加至大約35m/s，LR-ZRP控制開銷開始小于ZRP控制開銷，說明當節點移動稍快時，LR-ZRP控制開銷增加幅度較小。仿真初始，節點運動較慢，相應位移變化范圍也較小，相較于ZRP只有路由開銷，LR-ZRP包函了位置更新開銷和路由開銷兩部分，總的控制開銷自然大于ZRP；但當節點運動速度逐漸增加時，節點位置變化開始有些劇烈，ZRP沒有位置控制分組，但節點快速移動可能導致路由失效，需要重新發起路由，開銷增大，而此時LR-ZRP優勢漸顯，根據頻繁的節點位置更新，路由及時修復或優化，確定出來的路由請求區域也更加精確，相較于ZRP盲目全向泛洪，LR-ZRP控制開銷更小。

圖5　控制開銷

3.3平均端到端時延

ZRP與LR-ZRP的平均端到端時延均呈增長趨勢。同等速度狀況，LR-ZRP平均端到端時延少于ZRP，如圖6所示，這是因為：ZRP協議的節點運動狀態變化會造成原路由失效，只有目的節點所在區域內的節點接收到路由請求之后才可回送路由應答，時延較大；LR-ZRP引入位置緩存表，只需當前節點位置緩存表或路由緩存表中存在目的節點位置信息或路由信息，即可進行應答，減小了路由查詢時間。LR-ZRP利用節點實時性位置信息，及時調整路由，網絡自適應能力較之ZRP更優，所以平均端到端時延少于ZRP。

圖6　平均端到端時延

4結語

VANET旨在保障道路交通安全、提高出行效率和防范治理擁堵，更好地應對車輛數量激增帶來的各類挑戰。通過分析VANET常見路由協議，結合當前實際問題，對ZRP進行改進，得出一種基于位置信息和定向泛洪的新型區域路由協議(LR-ZRP)。仿真分析顯示，LR-ZRP在控制開銷和分組投遞率方面均優于ZRP。另在節點較高速度下，LR-ZRP控制開銷增長幅度趨于平緩。

參考文獻

[1]許富龍,劉志建.車載自組織網絡路由協議研究進展與比較[J/OL].電訊技術,2013,53(10):1393-1400[2015-12-24].http://mall.cnki.net/magazine/article/DATE201310027.htm.DOI:10.3969/j.issn.1001-893x.2013.10.027.

[2]張瑞鋒.車載自組網通信技術研究綜述[J/OL].汽車工程學報,2014,4(2):79-85[2015-12-24].http://mall.cnki.net/magazine/article/QCYK201402001.htm.DOI:10.3969/j.issn.2095-1469.2014.02.01.

[3]姬興民,李金龍,盧光躍,等.基于AODV的平面多徑路由協議[J/OL].西安郵電大學學報,2015,20(2):21-25[2015-12-24].http://mall.cnki.net/magazine/article/XAYD201502005.htm.DOI:10.13682/j.issn.2095-6533.2015.02.005.

[4]BLUMJJ,ESKANDARIANA,HOFFMANLJ.Challengesofintervehicleadhocnetwork[J/OL].IEEETransactionsonIntelligentTransportationSystems,2004,5(4):347-351[2015-12-24].http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1364012.DOI:10.1109/TITS.2004.838218.

[5]田紅燕,徐成,劉彥.一種基于方向優先的車載Adhoc路由策略[J/OL].計算機應用研究,2010,27(04):1416-1418[2015-12-24].http://mall.cnki.net/magazine/article/JSYJ201004057.htm.DOI:10.3969/j.issn.1001-3695.2010.04.058.

[6]GUPTAP,KUMARPR.Thecapacityofwirelessnetworks[J/OL].IEEETransactionsonInformationTheory, 2000,46(2):388-404[2015-12-24].http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=825799.DOI:10.1109/18.825799.

[7]TZENGSF,HORNGSJ,LITR,etal.Enhancingsecurityandprivacyforidentity-basedbatchverificationschemeinVANET[J/OL].IEEETransactionsonVehicularTechnology.[2015-12-24].http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7047920.DOI:10.1109/TVT.2015.2406877.

[8]馬明輝,武曉慶,武穆清.ZRP路由協議的NDP優化與仿真分析[J/OL].無線電工程,2007,37(7):4-6[2015-12-24].http://mall.cnki.net/magazine/article/WXDG200707001.htm.DOI:10.3969/j.issn.1003-3106.2007.07.002.

[9]李琳,武穆清.ZRP區域路由協議分析[J/OL].數字通信世界,2007(11):52-55[2015-12-24].http://mall.cnki.net/magazine/article/SZTJ200711028.htm.DOI:10.3969/j.issn.1672-7274.2007.11.021.

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

[11] 施榮華,羅棋峰.一種MANET中基于位置信息的ZRP路由協議[J/OL].湖南大學學報(自然科學版),2009,36(8):38-42[2015-12-24].http://mall.cnki.net/magazine/article/HNDX200908007.htm.

[12] 張棋飛,劉威,楊宗凱.基于位置信息的自適應AdHoc路由協議[J/OL].計算機科學,2007,34(5):20-24[2015-12-24].http://mall.cnki.net/magazine/article/JSJA200705005.htm.DOI:10.3969/j.issn.1002-137X.2007.05.005.

[責任編輯:瑞金]

Location-basedandrestricted-floodingzoneroutingprotocolforvehicleadhocnetwork

SUNYouwei,SUNXiaotian,WANGNan

(SchoolofCommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:In order to improve the efficiency of data transmission and routing discovery in the process of the vehicle ad hoc network communication, the zone routing protocol(ZRP) is improved by adding coordinates, speed, and time fields in data packets. After receiving the packet, the node records or updates its own position cache table according to the position information. In the route discovery phase, when the position shift is bigger than the radius of the location update, then the node update the route, which can reduce the times of route discovery. According to the location cache table and routing table, the non-destination node replies directly to the route requests, which can reduce the route discovery time. In the data transmission phase, the node can transmit data by restricting flooding range to reduce the control overhead. Simulation experiments are carried out by building the car networking scene on the 60 nodes at 5～50 m/s speed. Results show that the improved protocol can reduce the delay about 6%～13%, and increase the packet delivery rate about 6%～20%. Besides, when the node speed is greater than 35 m/s, the control overhead can be reduced by 7% to 14%.

Keywords:vehicle ad hoc network, zone routing protocol, location information, position cache table, restricted flooding

doi:10.13682/j.issn.2095-6533.2016.02.009

收稿日期：2015-11-28

作者簡介：孫友偉(1956-)，男，教授，從事下一代通信網研究。E-mail:syw@xupt.edu.cn 孫小田(1990-)，女，碩士研究生，研究方向為物聯網技術及應用。E-mail:627877256@qq.com

中圖分類號：TN913.6

文獻標識碼：A

文章編號：2095-6533(2016)02-0046-06