一種基于立體交通場景的CAB廣播路由算法

袁學松， 張 靜， 袁 濤， 韋佳佳

(1.安徽機電職業技術學院 信息工程系， 安徽 蕪湖 241000; 2.合肥工業大學 計算機信息學院， 合肥 230009)

一種基于立體交通場景的CAB廣播路由算法

袁學松1，2*， 張 靜1， 袁 濤1， 韋佳佳1

(1.安徽機電職業技術學院 信息工程系， 安徽 蕪湖 241000; 2.合肥工業大學 計算機信息學院， 合肥 230009)

針對立體交通環境下，經典車載自組網廣播協議可能出現的數據誤傳率高、網絡延時大、傳輸不可靠等問題.提出了一種基于路側單元裝置(RSU， Road Side Unit)的準確高效的廣播算法CAB(Cubic traffic Adaptive Broadcast Routing Algorithm).該算法根據立體交通不同的應用場景，將廣播分為前向、后向和全向類型.同時，通過特殊hello包交換鄰居節點信息.通過統計鄰居表信息來選擇下一跳轉播節點，以達到縮短廣播時延，提高廣播效率的目的.針對立體交通中數據誤傳率高的問題，引入了車道判別方案和一跳廣播確認機制提高其傳輸的可靠性.使用NS-3和VanetMobiSim仿真結果表明，與現有經典的廣播算法相比，該協議在立體交通場景下有更好的包到達率、更輕的網絡負載和更低的傳輸時延.

車載自組網； 廣播協議； 網絡負載； 包到達率； 傳輸時延

近年來，隨著機動車的逐漸增多，很多城市的交通狀況逐漸惡化，導致各大中型城市均開始立體交通的建設.立體交通系統可以解決城市中交通擁擠、空間緊缺等問題.傳統的車聯網(Vanet)通常研究簡單的平面道路(如：高速公路場景、具有十字路口的交通場景、具有建筑物阻礙場景等)，很多經典的路由廣播協議也是基于上述場景構建的.在立體交通中，這些協議可能會出現節點選擇錯誤導致的誤傳現象，會使廣播路由協議效率降低，同時增加網絡的負擔.若能針對傳統經典Vanet廣播路由協議進行改進并將其應用到立體交通中去，必將提高Vanet在該場景下的廣播效率.

1Vanet廣播協議與相關場景問題描述

1.1相關廣播協議分析

在Vanet中廣播路由協議一直是一個較為熱門的研究領域.由于當廣播節點較為密集時，很容易重復廣播，產生冗余數據.輕則影響Vanet的性能，導致網絡負載過重，重則會產生廣播風暴[1]，導致網絡崩潰.為了避免廣播風暴的產生，近年來國內外的研究人員針對不同場景研發出不同的廣播路由算法.其中文獻[2-3]提出的基于概率和基于距離-位置的方法已被廣泛應用在普通公路的廣播算法中；Lim在文獻[4]中提出了使用Hello包來交換廣播節點間信息，建立鄰居表方案；此類方法還有很多，如SBA(Scalable Broadcast Algorithm)[5]、LFRB(A Location-based Fast and Reliable Multi-hop Broadcast Algorithm)[6]等.這些路由協議通常情況下可以減少重傳次數，減低網絡負載.但在負載較重的Vanet環境中，快速變化的拓撲會導致路由維護成本大大增加，造成網絡擁塞，降低廣播的可靠性.Korkmaz等提出的UMB(urban multi-hop broadcast)[7]協議和AMB(Ad hoc Multi-hop Broadcast)[8]協議針對直行道路場景和具有十字路口的場景，提出了RTS/CTS的握手機制和車輛節點充當中繼器的機制.有效的提高了廣播數據傳輸的可靠性，減少了硬件的開銷，取得了良好的效果.但是上述協議均是在傳統道路場景中提出的，不適合當前城市立體交通的狀況.

本文針對立體交通中存在誤廣播與無效廣播、轉播節點丟失、稀疏交通流場景下節點找不到轉播節點的問題，提出了一種基于立體交通廣播自適應路由算法(CAB).該算法使用特殊的Hello包檢測機制、鄰居節點預測機制并使用了攜帶轉發策略[9]和RSU[10-11]裝置有效的解決了上述問題.

1.2立體交通場景相關問題描述

城市立體交通與普通城市道路在很多方面有不同之處.在對普通道路設計廣播算法時，需要考慮十字路口、建筑障礙物等因素，而在設計城市高架、下穿橋的廣播算法時需考慮城市立體交通相關行駛準則.CAB算法將針對城市中立體交通的相關地理特性和車輛運動的相關規律提出以下3個設計要點.

1) 誤廣播與無效廣播問題

圖1是某市一個簡單的下穿橋式立體交通.當車輛在下穿橋下發起廣播時，橋上的車輛由于在廣播區域內，會作為目的廣播節點，收到該廣播信息.但由于車輛行駛在不同的道路上，將橋下車輛的消息廣播給橋上車輛是沒有意義的，這樣就會產生“誤廣播現象”.如果在同一個道路上，車輛想通知自己后向車輛該路段發生了交通事故，但由于廣播是全向廣播，消息同時被傳送給了前方車輛，前方車輛已經過該路段，得到的消息是無意義的，這樣就會浪費網絡資源導致“無效廣播”現象.

2) 轉播節點丟失問題

當行駛中的車輛A要廣播數據包時，首先通過hello包找到距離自己較遠的轉播節點B.如果B在A通信的邊緣地帶且高速運動，當A轉播消息給B時，B已經不在A的通信范圍內了，這種情況就會導致轉播節點丟失問題.

3) 稀疏交通流[12]的廣播問題

在一些特殊的時段(如：凌晨)，城市高架路車輛較少，如果車輛節點想廣播信息，可能在廣播區域內找不到可以轉播的節點，傳統的做法是該節點將數據包攜帶轉播，當有節點可以廣播時再進行廣播操作.這樣可能導致廣播效率低下，許多節點不能及時得到消息.

2CAB廣播算法

算法假設在城市立體交通中行駛的車輛均有GPS和電子地圖裝置，這些裝置可以獲取汽車的實時位置信息和海拔信息，這些信息有利于算法判斷其是否在同一個平面上行駛.同時，車輛節點內還需有可獲得車輛行駛速度、加速度、車輛行駛方向等信息的傳感器，這些重要信息也將被應用到算法中.

2.1立體交通場景的廣播模型

在CAB算法中，設定了3種場景廣播模型(前向廣播、后向廣播和全向廣播).通常，在不同維度和方向行駛的車輛廣播的意義不大.在同向車道中行駛的車輛的前向廣播常用于通知前方車輛后發有突發事件和重要車輛如：救護車、救火車等，希望前方車輛可以讓出某個車道.后向廣播常用于通知后方車輛前方有事故發生，希望后方減速或者繞行.全向廣播在本算法中主要是用于稀疏車流場景下攜帶轉播和路側裝置(RSU)進行的廣播.

本算法定義了節點廣播數據包的包頭格式如圖2所示.

通過在經典協議的數據包包頭增加了域，來實現算法的場景自適應.其中，在廣播節點的基本信息中增加了地理位置信息，該信息是通過車載GPS獲得的廣播節點具體經緯度和海拔信息.節點的運動速度和運動方向也是車載設備獲取的.當在廣播范圍內的節點，海拔不同的時候，說明兩車不在同一個維度，也就沒有必要進行廣播.包頭的FLAG位表示數據包的傳播方向(前向、后向還是全向).當FLAG為0是表示廣播包的傳播對象是與該節點同運動方向的前向節點；當FLAG為1時.表示廣播包的目標節點為和其同向運動的后方節點；當其為-1時，表示全向傳播.算法如何確定FLAG位是決定算法成功的關鍵.BR為廣播的范圍，為該數據包廣播的區域.當在稀疏車流場景下，源節點未能找到下一跳的目的的節點時會攜帶轉播.當到達路側單元(RSU)還未找到任何轉播節點時，會將數據包轉發給RSU.算法為了提高傳輸效率設計了RSU節點，廣播數據包包頭格式如圖3所示.在RSU廣播包頭中由于刪除了運動節點的信息，數據包傳輸過程中網絡負載有所降低.

圖4模擬了兩個運動節點在車道上行駛的過程，在該過程中A和B通過hello包來交換相互的節點運動信息.廣播源節點A(X，Y)以速度運動，節點B(X1，Y1)以速度同向運動，A節點的運動方向角度為，而B節點的運動方向角度為.當表示A與B節點同向運動，否則為反向運動(如本算法不研究反向運動的廣播包傳輸).兩個節點的相對位置為矢量K=(X1-X，Y1-Y)，那么K的方向決定了A，B節點的前后位置.假設K的方向為，那么表示節點B為A的前向節點，否則為反向節點.這樣只要通過hello包相互交換各個節點的運動方向，就可以了解到各節點與廣播源的前后關系，使數據傳播更有目的性.

2.2Hello包機制與鄰居信息檢測[13]維護機制

算法采用hello包機制來維護廣播網絡的拓撲結構.在hello包機制中重要的是高效而又準確的維護鄰居轉播節點.每個節點都會周期性的廣播自己的hello包，各節點間通過該信標來交換信息，從而維護局部網絡拓撲信息.在CAB算法中hello包結構如圖5所示，它包含了自身的節點運動信息、1跳鄰居表信息和2跳鄰居個數信息.

各節點首先通過交換hello包信息來確定廣播模型.源節點希望花費最少的時間將自己的信息廣播到最遠端，并且能廣播給更多的節點.這樣就需要合理的選擇下一跳轉播節點.傳統的方法是選擇離源節點最遠的一個節點進行傳輸，這樣可能造成“低效率傳輸”和“傳輸不可達”的情況.如圖6當t時刻C節點時A節點理想的下一跳節點，但在轉播時，網絡的拓撲已發生變化.C′明顯不是A′最合適的下一跳節點.圖7中，在t時刻A選擇了B作為自己的轉播節點，在轉播時，B′已超出了A′的通信范圍，造成了傳輸不可達.這兩種情況都是忽略節點的移動性所造成的，都會造成局部網絡的重新構建，數據包的重發，進而引起網絡的擁塞.

CAB算法充分考慮到節點的移動特性，使用提前預測的機制來進行下一跳轉播節點的選擇.高效而又準確的維護網絡拓撲的鄰居節點.如圖8，該圖是一個典型的鄰居轉播預測圖.在t時刻，A的轉播節點應該是C節點.但節點A并不會馬上選擇C作為下一跳轉播節點，而是對網絡拓撲進行預測.A通過交流的hello包了解到各節點的速度和運動方向，計算經過Δt的路由存活時間各節點的可能位置，再來判定誰是可靠的、最遠的轉播節點.這時A會選擇D節點作為自己的轉播節點.由于廣播節點在選擇下一跳時不僅需要考慮可靠的傳輸到下一跳，而且希望盡快擴散到廣播區域.這就需要下一跳節點具有更多的下1跳鄰居和2跳鄰居.所以，給hello包增加了這兩個域，當hello包周期性交換信息時，廣播節點會選擇在可靠距離范圍內的、傳播距離最遠的、且1跳和2跳節點較多的轉播節點去轉發數據包.

2.3可靠的一跳廣播確認機制

在數據包傳輸過程中，為了能可靠的傳輸廣播包，節點和節點間將采用“1跳確認握手”機制.局部拓撲數據廣播過程都是由若干跳過程組成的，只要保證每一跳都是可靠的，整個數據廣播過程就是可靠的.當廣播節點A經過hello包信息交換后，選擇了B作為其轉播節點.算法會按照圖2的包頭格式進行數據包的發送.在發送過程中將自己的ID信息放入Source域，表示廣播是由A發起.同時，確定幾個備用的轉播節點，將信息放在BRN域中.節點A會啟動定時器和計數器，定時器設定為超時時間，計數器設定為超時次數.在一定時間內A未收到B的回復包，A會啟動重發機制，計數器自減一，當計數器為0時表示B不在A的傳輸范圍內，A會通過交流hello包及時改變自己的轉播節點.

2.4算法描述

CAB廣播算法是通過Hello包機制來維護鄰居和確定轉發節點的.同時，節點交流hello包可以避免不同海拔(不在一個道路)上的節點進行數據包的誤傳輸.在立體交通中增加了RSU裝置，以保證在稀疏的交通流場景下數據更可靠的傳輸.圖9為車輛節點和路側裝置的數據包轉發方案和鄰居節點的維護方案流程圖.

算法具體可描述為：

1) 源節點廣播數據包，首先通過各鄰居節點通過Hello包的信息交換判斷車輛節點的海拔高度(由于城市交通的坡度影響，允許一定誤差).如果海拔高度不同，說明節點不在同一道路上，行駛互不干擾，不進行數據的轉發.如果在一個海拔高度上則進行過程2)操作；

2) 通過hello包機制和鄰居維護機制，根據場景的需要更新源節點的FN域和BN域.將在通信范圍內，廣播節點前向的節點放入hello包的FN域，將后向節點放入BN域.同時，通過鄰居hello包計算源節點2跳節點的數目，并將其存放在hello包中.源節點更新完hello包后進入3)；

3) 通過節點運動預測機制判斷是否有合適的轉播節點，若有進入4)，若沒有進入5)；

4) 通過“1跳確認機制”可靠的傳送數據給轉播節點；

5) 判斷在節點廣播區域是否有路側裝置，如果沒有進入(1)，如果有進入(2)；

(1) 車輛節點將數據包攜帶轉播，同時周期性的更新hello包，尋找合適的廣播節點和RSU.轉至過程3)；

(2) 廣播數據包通過“1跳確認機制”發送給RSU.RSU根據廣播包中FLAG標志位，確定是前向還是后向廣播.通過自身高功率發射至相應區域，同時，通過有線機制傳送給前向或者后向的RSU裝置，并由該裝置進行全向廣播.

3仿真實驗分析

為了驗證CAB算法在立體交通場景工作的有效性，本文將使用交通仿真工具VanetMobiSim[14-15](VehicularAdHocNetworksMobilitySimulator)對真實場景進行構建，并將產生的節點軌跡文件使用離散時間模擬器NS-3進行網絡性能仿真.將仿真結果與較適合城市道路，經典的UMB協議和AMB協議進行各種網絡性能的比較.

3.1交通環境模型與車輛運動模型的參數

本文分別對較為簡單立體交通模型和稍復雜的立體交通場景進行仿真實驗.仿真的場景如圖10和圖11所示，在圖10描述的是只有一個長3km、寬2km的立交橋場景的模型.圖11是一個立體交通由A、B、C、D四條路組成，每條路長3km.其中，C與A、B交匯時采用下穿橋式道路模型，D與A、B交匯時采用高架式道路模型.仿真參數分別如表1所示.

在仿真中，廣播數據包發送速率為1packet/s，數據包類型為CBR，且廣播節點、廣播時間和廣播方向都是隨機的.在該場景中RSU設置為每公里1個，且在兩條道路交匯處必有1個RSU.通過分車道控制節點在道路上行駛的速度和加速度模擬車輛隨機分布的運動形態.

3.2仿真結果與分析

本次仿真實驗主要采用廣播包到達率、平均廣播開銷以及平均延時3個指標來衡量算法在簡單和復雜立體交通場景下的優劣性.在車輛密度不斷變化下，比較UMB協議、AMB協議和CAB算法的性能.

在簡單的交通場景中，由圖12～14可以看出，CAB算法的各個網絡性能指標與UMB和AMB協議差異不大.由于CAB算法加入了鄰居節點的預測方案減少了無效傳輸，節點的平均時延降低明顯.但由于采用了RSU導致在平均廣播開銷的指標上略高于其他協議.在復雜的交通場景下由圖15可知，平均廣播開銷為某一個廣播包傳輸給各節點的數據總量，它的計算方法為將場景中傳輸數據總量除以廣播包數據總量.CAB算法由于增加了RSU節點，同時采用“1跳確認機制”，這些因素都會導致額外的數據包的產生.而其他兩種協議，由于數據為全向傳播，也會產生很多無用的數據包.總體上，CAB算法在場景中的平均廣播開銷要略小于AMB和UMB協議.圖16為廣播包到達率，由于采用了可靠的“1跳確認機制”，CAB算法幾乎達到100%的包到達率，較其他兩種算法有更好的性能.圖17中，CAB算法的節點平均延時也較為穩定，隨著車輛密度的增加始終保持在20ms，其他兩種協議在立體交通場景下由于會產生誤傳，會導致重傳增加了節點傳輸的平時延時.

4結束語

本文將Vanet廣播協議應用于城市立體交通通信領域，提出了一種新的CAB算法，該算法無論是在稀疏車流還是在稠密車流的場景中都能夠保證廣播包的到達率，但由于增加了hello控制包和廣播包的控制字段，并使用了RSU節點和保證可靠性的“1跳確認機制”，平均廣播開銷性能與經典協議相當.算法增加的RSU節點可能會使硬件成本提升.通過仿真表明，CAB算法較其他類似算法更適合于城市立體交通場景的可靠數據傳輸，具有較大的應用價值.

[1]TSENGYC，NISY，CHENYS，etal.Thebroadcaststormprobleminamobileadhocnetwork[C]// 5thAnnualACM/IEEEInternationalConferenceonMobileComputingandNetworking， 1999: 153-167．

[2]LOCHERTC，HARTENSTEINH，TIANJ，etal.AroutingstrategyforvehicularAdHocnetworksincityenvironments[J].ProcofIntelligentVehiclesSymposium， 2003:156-161．

[3]WILLIAMSB，CAMPT.ComparisonofbroadcastingtechniquesformobileAdHocnetworks[C]//ProceedingsoftheInternationalSymposiumonMobileAdHocNetworkingandComputing(MobiHoc)，Lausanne，Switzerland， 2002:194-205．

[4]LIMH，KIMC.MulticastTreeconstructionandfloodinginwirelessAdHocnetworks[C]//Proceedingsofthe3rdACMInternationalWorkshoponModeling，AnalysisandSimulationofWirelessandMobileSystems，Boston，USA， 2000:61-68．

[5] 彭 偉， 盧錫城. 移動自組網絡中采用連通支配集的有效廣播技術[J]. 軟件學報. 2001， 12(4):529-535．

[6] 周 娜， 劉南杰， 趙海濤. 一種基于地理位置的車載自組網快速可靠廣播算法[J]. 計算機應用與軟件. 2014， 3(1)：108-110．

[7]KORKMAZG，EKICIE，OZGUNERF，etal.Urbanmulti-hopbroadcastprotocolforinter-vehiclecommunicationsystems[C]//ACMInternationalWorkshoponVehicularAdHocNetworksACM， 2004:2062-2063．

[8]KALININM，ZEGZHDAP，ZEGZHDAD，etal.Softwaredefinedsecurityforvehicularadhocnetworks[C]// 2016InternationalConferenceonInformationandCommunicationTechnologyConvergence(ICTC)，JejuIsland，SouthKorea， 2016: 533-537．

[9]TONGUZO，WISITPONGPHANN，FANB，etal.BroadcastinginVANET[C]//IEEE， 2007:7-12．

[10]DUBEYB，CHAUHANN，CHANDN.EfficientdataschedulingtechniqueatRSUforvehicularad-hocnetworks[C]//2016InternationalConferenceonInformationCommunicationandEmbeddedSystems(ICICES)，Chennai， 2016: 1-7．

[11]ALIG，RAHMANMA，CHONGPHJ，etal.OnefficientdatadisseminationusingnetworkcodinginMulti-RSUvehicularAdHocnetworks[C]// 2016IEEE83rdVehicularTechnologyConference(VTCSpring)，Nanjing， 2016: 1-5．

[12] 周連科. 基于交通流密度的VANET廣播技術研究[D].哈爾濱：哈爾濱工業大學， 2011:14-16．

[13] 郭煉祥. 城市車載自組網路由協議的研究[D].廣州：華南理工大學， 2011:32-35．

[14]ASHTAIWIA，ALTAYESHA，BELGHETK.IEEE802.11pperformanceevaluationatdifferentdrivingenvironments[C]//2015WorldSymposiumonComputerNetworksandInformationSecurity(WSCNIS)，Hammamet， 2015: 1-8．

[15]PERDANAD，SARIRF.PerformanceevaluationofcorruptedsignalcausedbyrandomwaypointandGauss-MarkovmobilitymodelonIEEE1609.4standards[C]//2015InternationalSymposiumonNext-GenerationElectronics(ISNE)，Taipei， 2015: 1-4．

A CAB broadcast routing algorithm based on 3D transportation scene

YUAN Xuesong1，2， ZHANG Jing1， YUAN Tao1， WEI Jiajia1

(1.Department of Information Engineering， Anhui Technical College of Mechanical and Electrical Engineering， Wuhu， Anhui 241000； 2.School of Computer and Information， Hefei University of Technology， Hefei 230009)

In this paper the vehicle self-organized network broadcasting protocol is studied under 3D transportation environment. In order to handle the data error， network delay， unreliable transmission， we propose a novel accurate and efficient algorithm Cubic traffic Adaptive Broadcast Routing (CAB) based on the Road Side Unit (RSU). In this algorithm， the broadcasting is divided into forward， backward and all-direction types according to the application in 3D transportation environment. Meanwhile， neighboring note information is exchanged using hello package exchange. By choosing the next broadcasting node based on the neighboring node statistics， the broadcasting efficiency is improved. For the data error problem in 3D transportation， the vehicle lane classification and the first jump confirmation method are introduce. Using NS-3 and VanetMobiSim to simulate the results， the proposed algorithm exhibits better package arrival rate， lower network loads， and smaller network delay， compared with the traditional broadcasting algorithms．

vehicle self-organized network; broadcasting protocol; network load; package arrival rate; transmission delay

2016-10-20.

安徽省教育廳2016年度高校領軍人才引進與培育計劃項目(gxfxZD2016324)；安徽省教育廳省級教學團隊項目(2014jxtd99)；2016安徽機電職業技術學院院級重點科研項目(2016zdzr10)．

1000-1190(2017)02-0143-08

TP393.02

A

*E-mail: ahjdyxs@126.com．