適應城市交通環境的改進型車載路由優化方法設計

摘 要： 為了優化城市交通環境中車載自組織網絡中路由協議的鏈路存活時間、吞吐量等性能指標，在拓撲反應式路由協議的基礎上，引入車載網絡節點的位置信息，設計基于動態實時位置信息變化的車載路由協議優化模型。該模型按照十字路口車輛優先和相對位置為同方向節點優先轉發的原則，根據路由信息表中位置信息區分轉發控制包，并給出該路由算法的面向C++語言的UML建模圖及其算法流程圖。通過NS2仿真平臺仿真表明，與傳統的路由模型相比，該模型優化了VANETs網絡中鏈路存活時間、時延、吞吐量等性能指標。

關鍵詞： 路由協議； M?AODV； 十字路口； UML建模； NS2仿真

中圖分類號： TN926?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2016）14?0100?06

Design of improved vehicle?mounted routing optimization method suiting for

city traffic environment

XUE Ming， HU Yan

（Henan University of Technology， Zhengzhou 450001， China）

Abstract： In order to optimize the performance indexes of routing protocol link survival time and throughput in vehicle?mounted Ad Hoc network of city traffic environment， and on the basis of the topology reactive routing protocol， the position information of the vehicle?mounted network nodes is introduced to design the vehicle?mounted routing protocol optimization model （M?AODV） based on the dynamic change of real?time location information. This model is based on the priority forwarding principle of the crossroad vehicles and the relative location as the nodes in the same direction， and used to distinguish the forwarding control packets according to the position information in routing information table. The UML modeling graph of the routing algorithm and algorithm flow chart oriented to C++ language are given. The simulation results obtained from NS2 simulation platform show that， in comparison with the traditional routing model， the proposed model can optimize the performance indexes in VANETs， such as network link survival time， time delay， throughput， etc.

Keywords： routing protocol； M?AODV； crossroad； UML modeling； NS2 simulation

隨著道路數目和車輛數目的比例嚴重失衡的情況愈發嚴重，中國的交通擁堵難題亟待解決，車載自組織網絡（VANETs）應運而生。VANETs作為智能交通系統的信息傳送平臺，可以獲得即時的交通信息和道路狀況等信息，很大程度上提高駕駛過程中的安全性，繼而進一步地減少交通問題[1]。但是目前作為VANETs 中的核心工作內容的認證安全、路由協議等仍然存在一定問題，比如網絡負載過大、自私節點拒絕合作、間斷性等[2?3]。

這里所設計的路由協議M?AODV（Improved Ad Hoc on?demand Distance Vector Routing）主要是在基于拓撲的反應式路由協議AODV原理，引入動態實時相對位置信息，通過路由表中的位置信息區分轉發，區分分類轉發的原則是根據車輛間相對位置進行節點分類，采用十字路口車輛優先和相對位置為同方向節點優先轉發的方式實現控制包的尋路，進而優化VANETs網絡中鏈路存活時間、時延、吞吐量等性能指標。

1 車載優化路由模型建立與分析

1.1 車載網路由優化模型的基本原理

不同拓撲的位置、節點方向、速度等在很大程度上會影響路由性能，越是臨近車輛的方向，其連通度的制約性越強[4]。這一模型按照各個節點位置關系進行劃分，主要涉及到[α]類、[90°α]類、[β]類三種節點，其中，對于它們的相對位置關系，第一種是同一路段同向/異向；第二種是同一路段夾角[90°]；第三種是在某角度的偏離節點。具體情況見圖1，自E開始，其第一種節點主要是包括A，C，F，I，它的第二種節點主要是涉及到B，D，G，H。對于C來說，其屬于十字路口節點（或者稱做協調交叉節點，專指處在十字交叉路口范圍內的節點，其特殊地方在于，其同時擁有[α]類、[90°α]類節點），B，D是它的第二種，而A，E，F，I屬于它的第一種類型。在這里通過三個參數進行表達（M，N，K），其中字母M代表的意思是路段，而字母N主要代表的是行駛方向，而字母K主要代表是否是十字路口，各節點利用位置服務器得到其所在處所的相關數據資料。假定所有車均配備了GPS導航，那么它就能夠非常輕松的將自己的地址得到，各節點也會將自己的路段告知臨近節點。劃分路段過程中，分界點主要是十字路口的節點，各節點僅僅對其位置與路段ID進行廣播，十字路口節點信標的廣播信息將以“[+]”號表示十字路。

其具體的轉發步驟如下：某節點接到路由包，第一步需要判定自身到底屬于哪一種節點，要是屬于普通節點，那么將會先轉向十字路口鄰居節點，然后才開始先[α]后[β]類鄰居節點進行；要是自己屬于十字路口節點，在這種情況下，將會先[α]和[90°α]節點，完成之后，接著選擇第二類實施轉發。主要操作步驟如圖2所示。轉發過程按照這個順利進行，旨在充分確保十字路口優先、同路段同向/反向優先、最后是各個路段與本地節點非[0°]或[90°]的節點。這樣有助于路由包以相對較高的速度進行傳送，在一定程度上增加了鏈路存活時間，同時能夠在一定程度上降低端到端時延。

1.2 [α]類節點鏈路存活時間

VANETs中，兩節點不間斷連接的時間即為鏈路存活時間。假定沒有包丟失率，時間[t0=0]，在[i]與[j]間有某鏈路，假定[X]所指代的是在建立鏈路過程中兩節點的距離，其值處于[0，300]這一個區間之中。通常而言，[X]符合對數正態分布[5]，假定[μ∈-∞，+∞，σ≥0]，同時一切節點均沒有出現超速。在這里通過[vt]和[at]分別指代節點在[t≥0]的速度與加速度，這樣就能夠得出：

[at=0， a0=0at=a0， a0>0，t≤vmax-v0a00， otherwiseat=a0， a0<0，t<-v0a00， otherwise] （1）

對于式（1），其節點速度比[vmax]小，同時在零以上。假定節點剛開始是[v0]，那么就得出下面的公式：

[vt=v0+0taxdx ] （2）

式中：[ax]是[t=x]的加速度，那么就會得出式（3）：[vt=v0， a0=0vt=v0+a0?t， a0>0vmax， otherwisevt=v0+a0?t， a0<0 0， otherwise] （3）

通過上文中對于加速度與速度的界定，則[0，t]范圍中的行駛距離[st]可以表示如下：

[st=0tvxdx] （4）

對[i]，[j]節點，[t] 時刻的行駛距離、速度和加速度三者依次可以通過下面的方式進行表達：也就是[sit]，[vit]，[ait]與[sjt]，[vjt]，[ajt]，那么就能夠得出：

[sit=0tvixdx， sjt=0tvjxdx] （5）

所以，[i]與[j]兩者距離就能夠通過下式進行表達：

[Δs=sjt-sit+X] （6）

在這里，只有正、逆向行駛兩種，對于第一種，此時的[st≥0]，[vt≥0；]而對于第二種，此時的[st≤0]，[vt≤0]，沿正方向，[j]在[i]之前時[X≥0]，即：

[p（t）=1， Δs≥0-1， otherwise]

對鏈路存活概率計算，因[vt=v0+at?t]，所以就能夠得：

[st=0tvxdx=0tv0+a0?xdx =v0?t+12a0t2 ] （7）

假定[sjt-sit=at2+bt+c]，所以就能夠得到下面的方程：

[at2+bt+c+X-300=0]

由于鏈路在[t]時刻將斷開[6]，要是[a≠0]，那么對上面的方程求解，則能夠得出：[t=-b±b2-4ac+X-3002a]，即解[t1]，[t2]。在這里，要是[a=0]，那么就能夠求出：[t=300-c-Xb]。[X]符合對數正態分布，其累計分布函數可通過下式表達：

[Fxx=12+12erflnx-μσ2 ] （8）

所以就能夠求出它的概率分布函數，具體為：

[Ptt0=Pt≤t0=P-b±b2-4ac+X-3002a≤t0 =X≥-at20+bt0+c-300， a>0X≤-at20+bt0+c-300， a<0 =1-FX-at20+bt0+c-300， a>0FX-at20+bt0+c-300， a<0] （9）

當[a=0]時，在這種情況下，就能夠獲得以下結果：

[Ptt0=Pt≤t0=P300-c-Xb≤t0 =1-FX-bt0+c-300， b>0FX-bt0+c-300， b<0] （10）

繼而求出其分布函數具體如式（11）所示：

[Ptt0=1-FX-at20+bt0+c-300，a>0，b∈-∞，∞FX-at20+bt0+c-300， a<0，b∈-∞，∞1-FX-bt0+c-300， a=0，b>0FX-bt0+c-300， a=0，b<0 ] （11）

給定[t0]，則能夠對[Ptt0]進行計算。按照對數正態分布均值是[eμ+σ22]，則能夠得出相應的存活時間。

1.3 [90°α]和[β]類節點鏈路存活時間

在移動過程中，[90°α]與[β]類節點位置關系，存在大量不同的情況，此處僅僅對下列幾種場景進行闡述。

1.3.1 場景 1：單節點移動

假定有節點[i]與[j]，對于[j]來說，其保持固定，它的起始距離是[d0]，對于[i]來說，其速度是[vi]，首次自[I] 傳至[I′]的時間是[t1，]兩者之間間距是[s1]，第二次所用的時間和距離分別是[t2]和[s2，]同時[I′]和[I″]為同向，具體情況如圖3所示。

圖中，[α=180°-β]，通過余弦定律就能夠得到：

式中：[s1=vi?t1]，[s2=vi?t2]，按照文獻[7]能夠得出[vi]，[st]是二次多項式，基于[vi（t）=v（0）+a（t）?t]就能夠得出式（14），如下：

假定[sjt-sit=at2+bt+c]，符合：[at2+bt+c+X-][300=0]，根據[α]與[90°α] 類節點鏈路存活時間的求解步驟，就能夠計算出[Ptt0]。

1.3.2 場景 2：雙節點同時異向等速移動

[i]與[j]在同一個時間內移動，假定[vi=vj=v，]見圖3（b）。[i]從[I]傳至[I′]，[j]從[J]傳至[J′]的時間是[t1]；[i]從[I′]傳至[I″]，[j]從[J′]傳至[J″]歷時[t2]；[I′]和[J′]兩者距是[a1]，[I″]和[J″]兩者距[a2]；因此，可得到：

[s1=vj?t1]，[s2=vi?t2]且存在[vi=vj，]按照文獻[8]就能夠解出[vi]與[vj]。按照[α]與[90°α]類節點鏈路存活時間的求解步驟，就能夠計算出[Ptt0]。

1.4 M?AODV模型的UML結構及算法實現流程圖

圖4中Routing_model為接口，其中定義Get_routng_model（），Create_Location（）等抽象方法。類AODV_routing_model繼承Routing_model接口，實現接口的抽象方法。其中AODV_routing_model（）、～AODV_routing_model（）為自身的構造函數和析構函數。接口Forward_mode與類M_AODV_forward_mode，還有Node_informatio與Get_node_information類似于接口Routing_model與類AODV_routing_model的關系。類Routing_table，Location，Attribution用于作為類AODV_routing_mode，M_AODV_forward_mode，Get_node_information的屬性成員。類MainClass為整個程序的入口，其中包括一些變量的定義與賦值、對其他類的方法的調用等操作。M?AODV算法流程如圖5所示。以上UML建模圖及算法流程圖可供下一步通過C++語言在NS2仿真平臺進行建模仿真實驗分析使用。

2 仿真實驗及性能比較

本文的仿真主要在NS2仿真平臺上進行。為了盡可能模仿真實的城市環境，在NS2上的移動模型是節點隨機于沒有障礙的平面中移動，與具體移動情況不一致，特別是與城市場景存在著很大的差異，無法真正體現路由協議的性能。所以通過MOVE軟件快速生成真實運動模型。MOVE這款軟件有三項模型生成功能，分別是地圖模型、交通模型和移動模型。通過該軟件平臺，可以利用其三項功能較好地模擬城市場景。對應三項功能[6]，在該方法中最后得到城市地圖、車輛移動模型、NS2交通模型。結合SUMO和NS2的模擬城市場景的框架圖，見圖6。

本文的十字路口覆蓋范圍參照文獻[7]，設定了一個包含十字路口由4段1 000 m長路段組成的簡單路網，其主要涉及到場景與車輛運動模型的生成這兩個方面內容。本文所用的仿真模型具體如表1所示。

在表1中，應用環境在NS2中的仿真模擬是通過上文提到的MOVE實現，在運動模式上本文是采用IDM[9]，該模型是一種微觀交通流模型，在仿真中將車輛視為移動的節點，因此能夠在任意時刻獲取仿真中任意車輛的狀態，即車輛所處的位置、速度、加速度、所處車道等。

此處仿真主要是通過拓撲反應式的AODV，DSR開展，將模型M?AODV下AODV，DSR性能表現和其在業內常用模型[10]的表現加以對比分析，其中涉及到：傳輸率、鏈路存活時間等。

2.1 鏈路存活時間和時延仿真

考慮到車載自組織網絡的動態實時變化特性，其網絡覆蓋范圍不是一個靜態參數，而是一個與節點行駛速度密切相關的變量，在節點發射功率一定的情況下，決定節點覆蓋范圍的是節點速率與自組織網絡鏈路存活時間。所以本文在這里著重分析網絡鏈路存活時間與節點速率之間的關系，以此來表現網絡覆蓋范圍對本文所設計方案的影響。圖7（a）是平均鏈路存活時間和速度關系的仿真結果，通過這個圖形能夠看出傳統模型的AODV，DSR鏈路存活時間比M?AODV的小，但是其AODV，DSR值不存在顯著的不同。究其根由：因M?AODV中，同路段、同直線方向的鏈路優先級高，該情況是由城市特殊應用環境所決定的，路由包傳至十字路口時，在這種應用環境下，一定比例的[β]類變成[90°α]節點，這樣就在很大程度上提高了輸送質量，正是由于這個原因，其存活時間有所增加。

圖7（b）是端到端時延和數據發送速率關系的仿真結果，在這里速率被歸一化了，假定原值是[x Kb/s]，那么歸一化后為[x800]。通過圖7（b）能夠看出：傳統DSR的端到端時延比傳統AODV大，而對于M?AODV來說，前者性能指數同樣比后者要好，其相同路由協議端到端平均時延比傳統的模型要大。究其根由：M?AODV主要是通過多次轉發進行，這就在一定程度上使得端到端時延有所增加。DSR協議對一個路由中到的一切路由請求RREQ分組做應答。所以源節點了解抵達目的節點的若干個路由。AODV里面，目的節點僅對首個抵達的路由請求分組RREQ應答，對其他RREQ可以忽略，所以DSR時延比AODV大。

2.2 路由開銷仿真

對于路由開銷來說，其和速度關系具體如圖8所示，它是一個源節點至目的路由需求下，一切節點發生交互的包的總量，其數量級處在[105]。隨速度的提高其個數呈2次指數提升，且DSR比AODV路由開銷大。這是因為，在源節點進行一次路由請求和應答過程中，目的節點路由和所到達過各中間節點的路由信息都會明晰。但是DSR協議即使是最新版之中不存在刪除失效的路由機制，同時不存在優先選擇路由的機制。這樣肯定會增大路由開銷。

2.3 吞吐率仿真

圖9（a），（b）分別是吞吐量和發送速率、節點速度的關系。

通過圖9可以看出吞吐量與發送速率呈正比例關系，而與節點速度成反比例關系，在傳統模型和本文所優化的M?AODV路由條件下，DSR吞吐量比AODV大，且M?AODV的DSR和AODV兩個指標要優于傳統模型。因為對于DSR來說，其通過源節點訪問的路由協議比AODV多，所以DSR路由協議可以在一定程度上有利于吞吐量的提高。第二，M?AODV注重十字路口及[α]類鄰居節點優先，提高了多數路由的抵達成功率與傳播效率，從而使其在一定程度上提高了吞吐量。

3 結 語

本文在傳統的AODV路由協議中，引入實時相對位置信息對車輛節點進行分類，采用十字路口優先、多次轉發等方式，優化VANETs網絡中鏈路存活時間、時延、吞吐量等性能指標。在實驗中，搭建了基于NS2的仿真環境，該環境利用MOVE方法構造城市環境，利用IDM模型構造車流量，通過仿真分析對比表明，本文所在設計的模型，在VANETs實踐應用中，DSR，AODV等關鍵指標得到明顯提升。下一步研究將會基于可重構思想對不同試驗場景，及其所對應的車在網絡傳輸協議引入上述思想進行分析，以期能夠針對不同的應用場景提供最合適的路由協議。

參考文獻

[1] 沈永增，姚敏杰，李曉鳳.基于城市路網的VANET按需路由策略研究[J].計算機應用與軟件，2012，29（6）：236?238.

[2] 蔡菁，王騰飛.基于移動模型的車載自組織網絡仿真技術研究[J].華中科技大學學報（自然科學版），2013，41（z2）：213?217.

[3] 何莉.車載自組織網絡中的匿名簽名及批驗證方案[J].計算機應用與軟件，2013，30（1）：306?309.

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

[5] 唐艷玲.二項分布及其應用、正態分布[J].數學教學通訊（數學金刊），2014（5）：25?27.

[6] 林航.車載自組織網絡移動模型研究[D].西安：西安電子科技大學，2013.

[7] 崔萌.城市場景下車載自組織網絡路由協議的改進[D].哈爾濱：哈爾濱工業大學，2012.

[8] SAGAR S， JAVAID N， SAQIB J， et al. On probability of link availability in original and modified AODV， FSR and OLSR using 802.11 and 802.11p [C]// Proceedings of 2012 IEEE International Conference on Open Systems. Kuala Lumpur： IEEE， 2012： 1?6.

[9] 白艷.汽車易駕駛性評價的隨機駕駛員模型方法[D].長春：吉林大學，2012.

[10] SURESH M， MOHANRAJ S， KAMALNATHAN C， et al. Performance analysis of AODV， DSR and ZRP protocols in vehicular Ad?Hoc network using Qualnet [J]. International journal of application or innovation in engineering management， 2013， 2（4）： 416?420.