混合式實時交通信息的VANETs的地理路由

潘韻，孫蘭娟

池州學院數學與計算機科學系，安徽池州247000

1 引言

車輛自組織網絡VANETs（Vehicle Ad hoc Networks）作為智能交通的重要組成部分，通過車間通信V 2V（Vehicle to Vehicle communication）以及車輛與路邊設施間通信，高效地實現事故預警、輔助駕駛、道路交通信息查詢，以及Internet接入服務等多種應用[1]。VANETs廣泛應用于事故預警、保障交通安全、交通管理、乘客娛樂，并為用戶提供舒適、安全的駕駛環境，使得VANETs在智能交通起著至關重要的作用，有望成為物聯網的典型應用之一[1-2]。

相對于傳統的移動自組織網絡，VANETs具有高動態的拓撲結構、間斷性的網絡連接、高度不可靠的鏈路、深度開放的網絡等特點。VANETs的這些特點使得傳統的路由協議難于直接應用。為此，2000年，Karp[3]提出GPSR（Greedy Perimeter Stateless Routing）協議。GPSR無需復雜的維護路由，僅依據通信雙方選擇轉發節點，開銷低。盡管GPSR適用于節點高速運動的場景，但是GPSR尋找的轉發節點不是最優解，從而導致路由經常中斷，不得不恢復策略，造成數據傳輸時延增大。研究成果表明，傳統的路由協議應用于VANETs時，數據包的成功傳輸率小于50%，延遲大且延遲抖動劇烈。如何設計有效的路由協議從而保障通信消息的安全、實時、可靠地傳遞，是VANETs研究的熱點問題[4]。

GSR[5]屬于基于位置的路由協議，根據地理信息，利用迪杰斯特拉Dijkstra算法計算最短路徑，之后采用貪婪轉發策略實現數據的轉發。然而GSR的不足之處在于：當交通密度很低時，就沒有足夠的節點轉發數據包。在低密度的交通情況下，端與端的連接率低。此外，A-STAR[6]也屬基于位置的路由協議。A-STAR考慮了靜態交通流量信息，并利用基于錨節點策略，為數據包尋找高連接率的路徑。A-STAR將公交巴士作為錨節點。文獻[7]也提出基于位置的路由協議GPCR，GPCR在每個十字路口選擇一個節點作為協調節點。在數據轉發過程中，轉發節點采用貪婪策略，并擇優選擇協調節點作為下一跳轉發節點。上述的這些路由協議在路由決策時并沒有考慮交通的實時狀態信息，這將會增加路由斷裂的幾率。

文獻[8]提出VADD（Vehicle-Assisted Data Delivery）方案。VADD結合車輛的位置以及方向信息，并利用基于數據包傳遞到目的節點的概率。其主要有三種數據包轉發模式：Intersection、Straightway、Destination。當數據包傳遞到道路交叉口時，就啟用Intersection模式，擇優選擇延遲最小的路段組建路由。當離開道路交叉口時，就啟用Straightway模式，并沿道路轉發數據包。當數據包傳遞到目的節點附近時，進入Destination模式。Junichiro[9]提出新的方案，通過預先計算源節點與目的節點可能路由的概率，并基于一定的數學模型。通過計算這些概率，建立一擬用的路由表。

DTSG[10]（Dynamic Time-Stable Geocast）方案。DTSG將網絡區域分為：目的區域定義為ZOR（Zone of Relevance）；轉發區域為ZOF（Zone of Forwarding）。在ZOR內節點表示數據包的目的節點，而ZOF內的節點為數據包的轉發節點。實施DTSG可分兩步：首先在ZOR內擴散數據包，再使數據包在預設時長內持久的存在于ZOR中?？蓜討B預設時長，無任何額外的開銷。

許多學者也提出利用實時交通信息的路由協議。文獻[11]提出優化的貪婪交通流量感知的路由協議GyTAR（Improved Greedy Traffic Aware Routing Protocol）。GyTAR利用實時的道路流量以及道路地圖信息選擇路由。如果轉發節點處于十字路口區域，它將從鄰近的十字路口收集道路的實時信息選擇下一個轉發的十字路口。然而，GyTAR僅從一跳鄰居節點收集交通信息，這些信息并不充分。利用不充分的信息難以選擇最優的路由。文獻[12]提出靜態節點輔助適應式路由SADV（Static-Node Assisted Adaptive Routing Protocol）。SADV在節點密度時，通過十字路口部署靜態節點收集實時的信息，利用這些信息預測車輛的移動。靜態節點在十字路口采取等待策略，直到有高的數據包遞交率才轉發數據。這種方式可以避免繞路，但是數據包傳輸時延取決于車輛密度。因此，SADV的性能優劣受到節點密度的影響。

為此，本文提出混合式的感知交通信息路由HTAR。HTAR不部署靜態節點，同時利用道路流量以及網絡流量信息決策路由。節點廣播這些混合式信息。通過共享這些信息，有利于節點選擇更優的路由。

2 HTAR

2.1 假設

本文提出的算法基于以下幾點假設：

（1）網絡中的節點均裝有GPS設備，能獲取自己準確的位置信息；同時節點都有無線通信設備，任何兩個節點在其通信范圍內，就能彼此通信。

（2）源節點在向目標節點發送數據前，通過位置服務已獲取目標節點、鄰居節點的位置信息。

（3）網絡中的節點能獲取街道信息，包括：（a）道路的拓撲結構；（b）交叉路口的ID、位置；（c）道路ID、長度。

2.2 HTAR基本概念

2.2.1 鄰居節點的相關信息

HTAR方案的節點周期性向鄰居廣播“Hello”消息，以便鄰居節點能獲取周圍節點的實時信息。接收節點依據實時信息，選擇最合適的數據轉發節點。Hello消息的格式如下所示：

其中，Road ID為此節點所處的道路號，Location（x，y）表示節點所在的位置。A t junction（True or False）代表此節點是否處于在交叉路口。表中的最后一列的內容取決于A t junction的值。如果A t junction是“True”，最后一列存放節點停留于十字路口的時間（Time to Leave Junction，TTLJ），否則的話，就存放Channel load，其表示道路擁堵率。

一旦節點收到來自其他節點的“Hello”消息，將其存放在自己的鄰居信息表中，格式如下所示：

2.2.2 交叉功能節點的選取

在每個交叉路口，需選擇一個功能節點，作為此交叉路口的信息收集者，負責從鄰近道路周期地收集實時交通信息。功能節點主要負責以下三方面的任務：

（1）及時收集鄰近道路交通、網絡流量信息；

（2）根據所收集的信息，依據算法計算道路的權值；

（3）向鄰近交叉路口分發道路的權值數據。

在HTAR方案中，根據節點所處不同的情況，將節點的狀態分為四種，分別為：休眠（sleep）、監視（monitor）、競爭（com pete）、發布（spread）。根據不同的輸入信息（激勵），四種狀態可相互轉換。

當節點不處于交叉路口，就進入sleep狀態。每次節點第一次進入交叉路口，它將sleep狀態轉變為monitor狀態。在monitor狀態時，節點設定一個Tm秒的倒數計時器。設置計時器的目的就是監視交叉路口是否存在功能節點。因為功能節點周期地向鄰居節點分發更新過的權值信息包W IU（Updated Weight Information），如果在Tm內未收到權值信息包，表明當前沒有功能節點。如果在Tm內，節點收到了W IU，則節點仍處于monitor狀態并重新設置當前的計數器。如果沒有收到，節點進入compete狀態。

處于com pete狀態的節點需設置Tc倒數計時器與其他節點競爭成為功能節點。Tc由式（1）計算。

所有處于spread狀態的節點都是功能節點。它們必須周期性收集鄰近交通信息，并向鄰居節點廣播已更新的權值信息。當功能節點離開交叉路口，它需要從處于交叉路口的節點中選擇一個節點繼承它的位置，即作為下一輪功能節點。TTLJ可通過式（2）計算：

其中，D(t)表示節點離交叉路口的路程，V(t)表示節點當前速度。如果HTAR能獲取其他的一些信息，如交通燈時間，TTLJ的值將更準確。TTLJ值越大，表明節點停留在交叉路口的時間越長。如前所述，處于交叉路口的節點周期地廣播含有TTLJ值的Hello消息。當前的功能節點依據TTLJ的值擇優選取功能節點的繼承者，具有TTLJ最大值的節點，被選中。通過這種方式，HTAR能夠降低因更換功能節點的開銷。繼承節點選定后，節點將離開交叉路口，同時進入sleep狀態。繼承節點也隨之進入spread狀態。

四種不同狀態的轉移如圖1所示。

圖1 節點狀態轉移圖

2.2.3 功能節點的任務

由上述分析可知，功能節點有三項任務必須完成，分別為匯集交通信息、評估道路權值，以及廣播道路權值。

2.2.3.1 匯集交通信息

在HTAR中，功能節點需收集兩類交通信息。一類是道路中節點的密度信息，另一類是網絡交通擁塞信息，其用道路堵塞率Channel Load表示。通過此值判斷道路是否堵塞。

為此，功能節點向鄰近的功能節點發送交通信息收集包（Traffic Information Collection，TIC）。在收集信息的開始，HTAR將道路進行分段。將每兩個交叉路口間的道路依據通信范圍R分段，按式（3）劃分：其中，Nseg為道路所分的段數，L為兩交叉路口之間的道路長度。如圖2為道路劃分示意圖。

圖2 道路劃分示意圖

在信息收集過程中，每個TIC包盡量傳遞到每段道路的中心。為此，每次轉發時，從鄰居信息表中選取離此段中心最近的節點作為轉發點。一旦接收節點發現自己是離此段道路中心最近的節點，就將此段道路的節點密度以及道路堵塞信息加入到TIC包中，然后再轉發給下一段道路，直到沒有下一跳轉發TIC包或新的繼任功能節點收到此TIC包。如果新的繼任功能節點收到TIC包，它將此TIC包復制并發送給源功能節點。原功能節點收到后，將分析交通信息并更新道路的權值。如下描述了TIC的格式：

其中，兩列Junction ID分別表示源交叉路口、目的交叉路口；Numbers of Nodes表示某路段的節點的數目；Segment ID表示道路的段數號；Channel Load表示此段道路的堵塞率。

（1）道路密度交通信息

靠近每段中心區域的節點收到TIC數據包，并首先計算鄰居節點的數目，然后將此值存入上述TIC格式中的“Number of Nodes”區域。如下顯示了由功能節點收到TIC包的示例，其中，A、B表示源交叉路口、目的交叉路口。

（2）網絡流量堵塞信息

如前所述，在道路的節點必須周期地廣播hello消息，該消息中包含了Channel Load的信息。一旦進入道路，功能節點監視道路情況，計算道路堵塞時間，并計算堵塞率。如式（4）所示：

其中，Tmeasure(n)表示節點n檢測路段的時間，Tbusy(n)表示此路段忙的時間。

多個節點一起檢測路段忙的時間。整個路段上的CLi由式（5）計算：

其中，i∈Nseg；Ni為此路段i的節點數目；Time Stam p表示產生TIC包時戳；Channel Load表示道路堵塞率。

2.2.3.2 評估道路權值

評估道路權值時，利用Dijkstra算法去計算最短路徑。功能節點收到TIC包，就按式（6）計算道路的權值Weiroad：

其中，Li表示路段的長度；C1、C2為兩個常數，且C1＞C2；CTth為路段負荷的門限值；Weiroad值越小，路由路徑越好。

功能節點計算了每條路段的權值后，將這每條權值存于權值信息表，其格式如下所示：

2.2.3.3 道路權值信息的分發

功能節點利用權值信息更新包（Weight Information Update，W IU）周期性地分發最新的道路權值，格式如下所示：

源節點獲取每條路段的權值后，從中選取權值最小的路段作為數據包的轉發路途。

3 路由決策過程

定義G=(V，E)：節點邏輯關系的圖論表示方法，V、E分別表示點集和邊集。

與GSR、A-STAR一樣，HTAR利用最短路徑算法去計算路由。在路由發現過程中，將交叉路口（junction）看成點V，道路看成邊E，每條邊均有它自己的權值。對于給定的兩個點，HTAR能找出最佳路由。此外，HTAR是實時交通感知路由，因此可根據實時的信息更新權值。

每個源節點在數據開始傳輸時需建立路由。根據當前所處區域的不同，路由的建立分兩種情況。

第一類，節點處于非交叉口。不處于交叉口的節點收到一個數據包時，首先檢查這個包目的地，如果這個節點本身不是這個包的目的節點，那么節點根據數據包的目的地，尋求適合下一跳的轉發節點。如果能成功找到轉發節點，就將數據包傳遞給轉發節點；如果不能找到合適的轉發節點，就采用存儲緩存，直到能獲取下一跳節點。

第二類，節點處于交叉路口。處于交叉路口的節點收到數據包時，同樣先查看數據包的目的地，如果自己不是數據包的目的地，就進一步檢測這個包是否第一次到達此交叉路口。如果是第一次，立即為此數據包重新計算路由路徑并尋求最佳下一跳轉發節點。與第一類情況不同的是，處于交叉路口的節點如果不能為數據包找到下一個轉發節點，則重新計算路由路徑，并依據此路徑重新尋找下一跳轉發節點。具體的方案流程如圖3所示，假定節點ni收到數據包。

圖3 HTAR方案流程圖

4 仿真以及性能分析

為了評估所提出的路由的VANETs性能，對HTAR以及GSR、GyTAR、SADV進行仿真。選擇這兩個協議進行對比仿真，主要原因是：GSR是不考慮交通信息的代表協議；GyTAR是利用交通信息輔助路由的代表協議，并支持攜帶轉發技術。采用Network Simulator 2.31作為仿真平臺；仿真場景采用TraNS[13]的模型。仿真的具體參數如表1所示。

表1 仿真參數

為了更好地分析HTAR協議的性能，本文分別從數據包傳輸率（delivery ratio）、平均傳遞時延（delay）、網絡開銷（network cost）進行協議分析。數據包傳輸率是指源節點發送的數據包與被目標節點成功接受到的數據包之比，如式（7）所示。平均傳遞時延是指數據包從源節點到達目標節點所需要的平均時間長度。網絡開銷，即在運行協議期間為實現數據包傳遞功能，網絡中所產生的數據包與其傳遞跳計數的乘積的總和，包括位置服務數據包、交通信息數據包以及路由維護數據包等[14]。

本文針對節點數目為400時，數據包傳輸率、平均傳遞時延、網絡開銷隨CBR速率的變化情況進行仿真分析。

圖4給出了數據包傳輸率隨CBR速率的變化曲線。

圖4 Deliver Ratio隨CRB的變化情況

從圖4可知，CBR速率的增加，數據包傳輸率呈下降趨勢。同GSR、GyATR相比，HTAR具有較高的數據包傳輸率。這主要是原因HTAR充分考慮了交通實時信息，轉發路徑斷裂的機率下降，數據包傳輸率提高，能夠達到約0.85。而GSR協議沒有充分考慮到車流信息，遇到網絡分割時數據包丟失嚴重，數據包傳輸率極低。GyTAR協議在數據轉發時，考慮到道路上的局部交通信息，其數據包傳輸率高于GSR，但是由于其只考慮到局部的交通信息，沒有整個網絡的交通信息，所以數據包傳輸率低于HTAR。

圖5表述了CBR對平均傳遞時延的的影響情況。三個協議相比，GSR的時延最小，這主要是因為總是由最短的傳遞路徑向目標節點傳輸數據包。而HTAR、GyATR采用無線轉發、存儲轉發方式，數據包的平均時延相差不大。與GyATR相比，HTAR考慮到全網的交通信息，選擇節點密集的道路，充分利用了無線轉發功能，其時延低于GyATR。

圖5 平均傳遞時延隨CBR的變化情況

如圖6所示，隨著CBR速率的增加，三種協議的網絡開銷也隨之增加。由于GSR協議簡單，復雜度低，其所占用的網絡開銷最小，增加幅度緩慢。相對GSR，GyATR和HTAR協議較復雜，網絡開銷也同步增加。在低速時，HTAR的網絡開銷低于GyATR。

圖6 網絡開銷隨CBR的變化情況

5 結束語

基于VANETs的特性，提出適用于VANETs的路由協議HTAR。該協議通過功能節點的設置，獲取交通的實時信息。每個交叉路口設置一個功能節點，負責收集實時交通信息。根據車輛的通信范圍將道路分成路段，功能節點計算每條路段的權值，并將這些信息向鄰居節點以及鄰近的交叉路口發布。為了適應VANETs的拓撲結構的動態性，功能節點將節點密度以及每條路段的負荷信息融入交通信息中。因此，節點能選擇最佳的轉發節點，使路由路徑更健壯、更穩固。同時，提出通過設置倒數計時器方案選取功能節點，以減少網絡開銷。仿真結果表明，HTAR的數據包傳輸率達到0.85，平均傳輸時較小，不高于2 s，并且網絡開銷與同類協議相關，沒有明顯的增大。

[1]陳辰，韓偉力，王新.VANETS安全技術綜述[J].小型微型計算機系統，2011，32（5）：896-904.

[2]M inhas U F，Zhang J，Tran T，et al.Towards expanded trust management for agents in vehicular ad-hoc networks[J].International Journal of Computational Intelligence Theory and Practice，2010，5（1）：3-15.

[3]Karp B，Kung H T.GPSR：greedy perimeter stateless routing for wireless networks[C]//Proceedings of the 6th Annual International Conference on Mobile computing and Networking（Mobi Com’00）.Boston，MA，USA：ACM Library，2000：243-254.

[4]Chen C，Zhang J.A trust modeling framework for message propagation and evaluation in VANETSS[J].International Journal of Computational Intelligence Theory and Practice，2010，5（2）：8-16.

[5]Lochert C.A routing strategy for vehicular Ad hoc networks in city environments[C]//IEEE Intelligent Vehicles Symposium Proceedings，June 2003：156-161.

[6]Seet B.A-STAR：a mobile Ad hoc routing strategy for metropolis vehicular communications[C]//Proceedings of the 3rd International IFIP-TC6 Networking Conference，M ay 2004：989-999.

[7]Lochert C.Geographic routing in city scenarios[J].ACM SIGMOBILE Mobile Computing and Communication Review，2005，9（1）：69-72.

[8]Zhao J，Cao G.VADD：vehicle-assisted data delivery in vehicular ad hoc networks[J].IEEE Transactions on Vehicular Technology，2008，2（5）：123-128.

[9]Junichiro F.A probabilistic protocol for multi-hop routing in VANETs[C]//Proceedings of the IEEE International Conference on Communications Workshops，2009：345-352.

[10]Rahbar H，Naik K，Nayak A.DTSG：dynamic time-stable geocast routing in vehicular Ad hoc networks[C]//Proceedings of the 9th IFIP Annual Mediterranean，2010：1-7.

[11]Jerbi M.An improved vehicular Ad hoc routing protocol for city environments[C]//Proceeding of the IEEE International Conference on Communications，2007：3972-3979.

[12]Ding Y，Wang C，Xiao L.A static-node assisted adaptive routing protocol in vehicular networks[C]//Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks，2007：59-68.

[13]肖玲，李仁發，羅娟.車載自組網的仿真研究綜述[J].系統仿真學報，2009，21（17）：5330-5336.

[14]白翔宇，葉新銘，李軍.感知實時車流信息的VANETS路由仿真研究[J].系統仿真學報，2012，24（2）：428-436.