基于鏈路穩定度的車載網路由協議研究

李南南， 張曦煌

(江南大學 物聯網工程學院，江蘇 無錫 214122)

?

基于鏈路穩定度的車載網路由協議研究

李南南， 張曦煌

(江南大學 物聯網工程學院，江蘇 無錫 214122)

針對車載網中節點移動速度快，拓撲結構變化速度快的特點，以及AODV協議廣播式路由鏈路存活時間短、平均端到端時延大等問題，提出了一種通過計算鏈路穩定度的方式來改進AODV協議。在節點進行廣播時，首先計算轉發角度，然后，再將投影最長和鏈路生存時間最長作為綜合選擇條件，以此高效地選擇路徑相對較短以及鏈路相對穩定的路由。通過這種方式，改進后的AODV協議很好地解決了網絡中鏈路易斷裂的問題，提高了數據包的投遞率，降低了平均端到端的時延。利用NS2仿真軟件進行性能仿真，結果表明：改進后的AODV協議在包遞率、平均時延和吞吐量方面優于傳統模型。

車載網； AODV協議； 鏈路穩定度； 端到端時延； NS2

0 引 言

近年來，車載自組織網VANET(vehicular Ad Hoc network)作為現代智慧交通系統(intelligent transportation system,ITS)的重要組成部分越來越引起人們關注，其通過車輛與車輛(V2V)之間以及車輛與基站(V2I)之間的交互，實現車輛與車輛、車輛與公眾網絡的動態通信，在現代交通管理、交通信息查詢等方面有很大的應用前景。

VANET屬于一種特殊的移動自組織網絡[1]，特殊性在于網絡中的車輛節點高速移動。正因如此，整個網絡的拓撲結構不穩定，隨時改變，車載網的鏈路穩定性較差，所以，選擇高效的路由協議成為了亟待解決的問題。根據車載網的特點，目前，普遍使用的協議有基于拓撲結構的路由協議[2]和基于地理位置的路由協議[3]，其中，基于拓撲結構的路由協議包括無線自組織網按需平面距離矢量路由(Ad Hoc on-demand distance vector routing，AODV)協議[4,5]、動態源路由(dynamic source routing，DSR)協議[6]等;基于地理位置的路由協議包括貪婪轉發與周邊轉發相結合的無狀態路由(greedy perimeter stateless routing，GPSR)協議[7]、圖形源路由(graphic source routing，GSR)協議[8]等。由于在城市環境中的車輛并不是隨機分布的，運動軌跡具有規律性，并且存在建筑物阻擋信號的問題，只考慮位置信息并不能得到最佳的傳輸路徑，因此，在城市場景中應用GPSR協議是不適合的。GSR協議通過電子地圖獲取道路拓撲結構，并利用Dijkstra算法[9]選取最優的數據傳輸路徑，但是GSR協議只根據道路拓撲結構選擇數據傳輸路徑，當網絡狀態不好，車輛節點分散且周圍障礙物較多時，路由的可靠性難以保證。在城市車載網中普遍使用基于拓撲結構的路由協議，又因為DSR協議只適合于稀疏網絡，對于城市場景中的密集車輛節點運動不具有適用性，因此，相比于DSR協議，AODV協議更適合在城市場景中使用。然而，由于車輛高速移動，網絡中的拓撲結構也隨時發生變化，AODV協議的鏈路存活時間變短，鏈路容易斷裂，網絡中的包交付率和端到端時延大大降低。因此，針對城市環境下車載網的特點，考慮到AODV協議的不足，在原有協議基礎上提出了一種考慮鏈路穩定度[10]的路由協議。該協議將鏈路生存時間和鏈路投影長度作為限定因素進行考慮，在選擇數據傳輸路徑的時候能夠保證鏈路穩定性更高，路徑相對較短。

1 AODV協議的改進方案

1.1 AODV協議

AODV協議的工作過程分為路由發現、路由本地修護和路由刪除三部分。如果源車輛有數據要傳輸給目的車輛，源車輛就開始路由發現過程，源車輛通過廣播RREQ分組到目的車輛來尋找數據傳輸路徑，在此廣播過程中，所經過的每個中間車輛節點都要建立反向路由，當目的車輛收到RREQ分組后，就沿著反向路由發送應答分組RREP，直到源車輛收到RREP分組，此時，源車輛到目的車輛的數據傳輸路徑建立完成。傳輸路徑建立完成后，進入路由維護狀態，當路徑中有車輛節點移出傳輸范圍，或者由于某種原因不能進行數據傳輸時，啟動路由修復過程。路由修復過程中尋找路由的方式與路由發現過程中尋找路由的方式相同，修復狀態維持到這條路徑不再被需要或者路徑斷開為止。在車載網中，車輛高速運動，數據傳輸路徑極易斷裂，當路徑斷裂后，如果源車輛還要和目的車輛進行數據通信，那么源車輛將再次啟動路由發現過程，尋找一條合適的路徑進行數據傳輸。當不再需要數據通信時啟動路由刪除過程。

1.2 AODV協議的改進

根據AODV協議的工作過程，傳統的AODV協議使用廣播方式進行路由選擇，沒有對路由進行對比，再加上車載網本身的特點，傳遞路徑很容易斷裂以至于鏈路失效。本文改進了傳統的AODV協議。在車輛進行路由探測時，首先根據每個車輛節點的坐標來計算每個待轉發車輛節點的轉發角，如圖1所示，θ為節點B的轉發角。如果|θ|的取值范圍在(0°，90°)之間，符合要求;否則，舍去。圖中源車輛節點S會選擇B作為轉發車輛節點而不選擇車輛節點A。

圖1 轉發角的選擇

計算轉發角后，根據投影最長和鏈路生存時間2個方面計算鏈路穩定度，并將鏈路穩定度p作為衡量標準。下一跳選擇鄰居表中p值最大的節點

(1)

式中 Ti為自身節點到節點i的鏈路生存時間；Li為自身節點與節點i的連線在自身節點到目的節點連線上的投影長度；Tmin為Ti中的最小值；Tmax為Ti中的最大值；Lmin為Li中的最小值；Lmax為Li中的最大值。

相鄰節點i和j之間的鏈路存活時間的計算如下

(2)

式中 a=vicosθi-vjcosθj；b=xi-xj；c=visinθi-vjsinθj;d=yi-yj，(xi,yi)為節點i的坐標；(xj,yj)為節點j的坐標；vi和vj分別為節點i和j的移動速度；θi和θj分別為節點i和j的移動方向；R為節點i和j之間的最大通信距離。

計算各鄰節點的投影長度

(3)

式中 (x1,y1)為待轉發車輛節點的坐標;(x2,y2)為目的車輛節點的坐標;(x3,y3)為鄰節點的坐標。在鄰居表中比較各個鄰節點的投影長度，下一跳選擇投影較長的鄰節點。

2 改進協議的關鍵數據結構與算法流程

2.1 關鍵數據結構

由于改進后的路由協議要在路由探測時根據式(1)計算節點間的鏈路穩定度，因此，節點必須將自身的位置和速度信息發送給鄰節點，那么原來的HELLO分組就要作相應的修改，修改后的分組中應該加入節點的位置、速度、IP地址以及生存時間等信息。由于在傳統的AODV協議中鄰節點的IP地址和鏈路生存時間已經存儲在鄰居表中了，并且鏈路生存時間一般默認為40s,因此,在改進后的AODV協議中，鄰居表里還要加入鄰節點的坐標和速度，所以修改后的鄰居表的結構體定義如下：

structnbnode_location

{

doublenode_x;

doublenode_y;

doublenode_speed;

};

structAODV_Neighbor

{

structnbnode_locationnb_node_location;

nsaddr_tneighbor_IP;

doublelifetime;

AODV_Neighbor*next;

}

其中，鄰節點的橫坐標用node_x表示;鄰節點的縱坐標用node_y表示;鄰節點的運動速度用node_speed表示; 鄰節點的IP地址用neighbor_IP表示; 鄰節點的默認鏈路生存時間用lifetime來表示。

2.2 算法流程

根據現實生活中的情況，目前，大量車輛都裝有GPS定位系統，所以,每個車輛節點均能方便地獲取自身以及目的車輛節點的位置和速度等各種息。當源車輛和目的車輛之間進行通信時，源車輛開始查詢自身的鄰居表中是否有可直接抵達目的車輛節點的路由，如果存在，就直接進行數據傳輸；否則，源車輛節點將發送路由請求，并采用廣播的方式進行路由探測。算法流程如下：1)根據各個待轉發節點的坐標計算待轉發節點的轉發角，如果滿足提前設定的角度范圍，則作為可供轉發的節點;否則，舍棄該節點。2)根據鏈路穩定度來選取路由，通過計算其所有鄰節點的p值，并選取p值最大的節點發送消息。3)該鄰節點再查看自身的鄰居表，確定是否探測到到達目的節點的路由，如果有則確立從源車輛到達目的車輛的傳輸路徑，并進行數據傳輸；如果沒有探測到路由，這時,還要考慮該節點是否超時，如果沒有超時，則依照上述相同的方式進行路由探測;否則,將超時信息反饋給源車輛，源車輛重新進行廣播探測。AODV改進協議的算法流程如圖2所示。

圖2 算法流程

3 協議仿真與性能分析

為了驗證改進后的AODV協議的有效性，采用Network Simulator(NS2)模擬實驗，并用VanetMobiSim交通流量仿真器模擬車輛運動模型。實驗從網絡中的數據包投遞率、平均端到端時延以及吞吐量三個指標對傳統的AODV協議和改進后的AODV協議進行了分析。實驗選擇不同的節點密度，仿真數據的車輛節點個數分別為30，60，90，120，150，180；網絡傳播模型為TwoRayWay，天線類型為OmniAntenna，數據包的發送率為5個/s，包的大小為512 B，數據包類型為CBR，節點間的數據傳輸使用UDP協議。其他主要的仿真參數設置:仿真區域大小1 500 m×1 500 m;紅綠燈數9個;車道數為雙車道；車加速最大加速度0.6 m/s2;車減速最大加速度0.5 m/s2;平均速度30 m/s;紅綠燈交替時間10 s;最大傳輸范圍250 m;仿真時間300 s。

圖3為數據包投遞率隨著車輛節點密度的增加而不斷變化的曲線。由于改進后的協議在路由探測時，將鏈路的生存時間作為選擇因素，所以網絡中數據傳輸路徑的維持時間更久，穩定性增強，鏈路斷裂的次數減少，因此，網絡中的數據包投遞率在改進后的AODV協議中明顯提高。而且隨著節點密度的增大，網絡的連通性增強，網絡中可供轉發的節點增多，節點更容易找到合適的下一跳，所以，數據包的投遞率呈上升趨勢。當網絡的連通性比較高時，網絡中的數據包投遞率趨于穩定，并且穩定在95 %左右。

圖3 數據包投遞率比較

圖4為在車輛密度不同時，平均端到端的時延的變化曲線。由于改進后的AODV協議在廣播探測路由時，首先計算了轉發角度，極大地降低了廣播冗余，提高了轉發效率。然后，再將鏈路長度作為選擇因素，通過對比之后選擇較短的路徑，大大地降低了端到端的時延，在平均端到端時延方面，改進后的AODV協議比傳統AODV協議效果要好，時延降低。當節點數目的增加時，網絡中可供轉發的節點增多，這樣更容易選擇投影長度較長的路徑，因此，平均端到端時延隨著節點密度的增大會越來越低。

圖4 端到端時延比較

圖5為隨著車輛節點密度的不斷變化，網絡吞吐量的變化曲線。由于改進后的協議在進行數據傳輸時的鏈路穩定性增強，所以改進后的AODV協議在單位時間內成功傳送數據的數量(吞吐量)比較高，隨著節點數目的增加，鏈路的穩定性更強，傳輸路徑更短，吞吐量會更大，因此，吞吐量隨著節點密度的增大會越來越高。

圖5 吞吐量比較

4 結 論

對目前普遍使用的車載網路由協議進行了分析，并針對基于拓撲結構的路由協議的不足，結合城市場景的特殊性，對傳統AODV協議進行了改進。在原有的AODV協議中加入車輛節點的位置和速度信息，在尋找路由建立數據傳輸路徑時先計算轉發角度，再綜合考慮鏈路的生存時間和鏈路長度2方面，將鏈路穩定度作為數據通信的節點。通過分析仿真結果表明：改進后的AODV協議在數據包的投遞率、平均端到端的時延和吞吐量方面都得到了明顯改進。但是改進后的協議也存在著一點不足，即由于節點在路由探測時要計算轉發角度、鏈路生存時間和路徑長度，增大了路由開銷。所以，下一步工作將選擇合適的方法減小路由開銷。

[1] Ranjan P，Ahirwar K K.Comparative study of VANET and MA-NET protocols[C]∥Proc of International Conference on Advance Computing and Communication Technology,2011:517-523.

[2] 于海寧，張宏莉.VANETs路由協議的研究進展[J].電子學報，2011，12(39)：2868-2879.

[3] 馬志欣，劉海英，謝顯中.基于地理位置的車載網絡地理路由算法[J].計算機應用，2013，41(5)：107-110,128.

[4] Cai J,Zhu Y B.An improved AODV routing protocol in urban vehicular Ad Hoc networks[J].Computer Engineering and Science,2013,35(1):61-66.

[5] 郭彥芳.一種改進的基于能量優化的AODV路由協議[J].無線電通信技術，2016,42(4)：25-28.

[6] 盧 穎，陳日莉.基于多描述編碼和距離的車載網DSR路由技術研究[J].傳感器與微系統，2011，30(10)：15-18.

[7] 黃文靜.自組織車聯網中GPSR路由協議的研究發展[J].傳感器與微系統,2014,33(4):1-5.

[8] 黃 弘，湯 祤.基于地理位置的VANET可靠路由協議[J].研究與開發，2015，12(1)：18-20,38.

[9] Zhou J,Shen Y,Xia Y,et al.Intelligent transportation Dijkstra shortest path analysis of fuzzy dynamic method[J].Technology & Economy in Areas of Communications,2014,16(4):9-12.

[10] Zhou P.Based on the weighted link stability of vehicular Ad-Hoc network on-demand routing protocol[J].Application Research of Computers,2015,32(6):1811-1815.

張曦煌，男，教授，主要從事無線傳感網，嵌入式系統，計算機網絡，圖形與圖像處理，計算機分布式控制與智能控制等研究工作。

Research on routing protocol for vehicular network based on link stability

LI Nan-nan， ZHANG Xi-huang

(School of IOT Engineering,Jiangnan University,Wuxi 214122,China)

Since vehicular network has characteristics such as node move fast,topology change rapidly,and AODV protocol broadcast-style routing has the problems such as short link survival time,long average end-to-end delay,a mode is proposed by calculating the link stability to improve AODV protocol.The new protocol choose shorter route and relatively stable routing efficiently by calculating angle forwarding considering two factors which are the longest projection and the longest link survival time when the node is broadcasting.In this way,the improved AODV protocol solves the problem of the network link fracture well,increases the packet delivery ratio and reduces average end-to-end delay.By using the NS2 network simulation software,the results show that the improved AODV protocol is superior to conventional model in packet delivery ratio,average end-to-end delay and throughput.

vehicular network; AODV protocol; link stability; end-to-end time delay; NS2

10.13873/J.1000—9787(2017)07—0012—04

2016—07—07

TP 393

A

1000—9787(2017)07—0012—04

李南南(1991-)，女，碩士研究生，主要研究方向為無線傳感網絡，嵌入式系統，計算機網絡。