李南南， 張曦煌

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

?

基于鏈路穩(wěn)定度的車載網(wǎng)路由協(xié)議研究

李南南， 張曦煌

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

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

車載網(wǎng)； AODV協(xié)議； 鏈路穩(wěn)定度； 端到端時延； NS2

0 引 言

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

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

1 AODV協(xié)議的改進方案

1.1 AODV協(xié)議

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

1.2 AODV協(xié)議的改進

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

圖1 轉(zhuǎn)發(fā)角的選擇

計算轉(zhuǎn)發(fā)角后，根據(jù)投影最長和鏈路生存時間2個方面計算鏈路穩(wěn)定度，并將鏈路穩(wěn)定度p作為衡量標準。下一跳選擇鄰居表中p值最大的節(jié)點

(1)

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

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

(2)

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

計算各鄰節(jié)點的投影長度

(3)

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

2 改進協(xié)議的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)與算法流程

2.1 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

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

structnbnode_location

{

doublenode_x;

doublenode_y;

doublenode_speed;

};

structAODV_Neighbor

{

structnbnode_locationnb_node_location;

nsaddr_tneighbor_IP;

doublelifetime;

AODV_Neighbor*next;

}

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

2.2 算法流程

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

圖2 算法流程

3 協(xié)議仿真與性能分析

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

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

圖3 數(shù)據(jù)包投遞率比較

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

圖4 端到端時延比較

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

圖5 吞吐量比較

4 結(jié) 論

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

[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路由協(xié)議的研究進展[J].電子學(xué)報，2011，12(39)：2868-2879.

[3] 馬志欣，劉海英，謝顯中.基于地理位置的車載網(wǎng)絡(luò)地理路由算法[J].計算機應(yīng)用，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] 郭彥芳.一種改進的基于能量優(yōu)化的AODV路由協(xié)議[J].無線電通信技術(shù)，2016,42(4)：25-28.

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

[7] 黃文靜.自組織車聯(lián)網(wǎng)中GPSR路由協(xié)議的研究發(fā)展[J].傳感器與微系統(tǒng),2014,33(4):1-5.

[8] 黃 弘，湯 祤.基于地理位置的VANET可靠路由協(xié)議[J].研究與開發(fā)，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.

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

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-)，女，碩士研究生，主要研究方向為無線傳感網(wǎng)絡(luò)，嵌入式系統(tǒng)，計算機網(wǎng)絡(luò)。