李南南， 張曦煌

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

?

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

李南南， 張曦煌

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

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

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

0 引 言

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

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

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

1.1 AODV協(xié)議

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

1.2 AODV協(xié)議的改進(jìn)

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

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

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

(1)

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

相鄰節(jié)點(diǎn)i和j之間的鏈路存活時(shí)間的計(jì)算如下

(2)

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

計(jì)算各鄰節(jié)點(diǎn)的投影長(zhǎng)度

(3)

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

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

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

由于改進(jìn)后的路由協(xié)議要在路由探測(cè)時(shí)根據(jù)式(1)計(jì)算節(jié)點(diǎn)間的鏈路穩(wěn)定度，因此，節(jié)點(diǎn)必須將自身的位置和速度信息發(fā)送給鄰節(jié)點(diǎn)，那么原來(lái)的HELLO分組就要作相應(yīng)的修改，修改后的分組中應(yīng)該加入節(jié)點(diǎn)的位置、速度、IP地址以及生存時(shí)間等信息。由于在傳統(tǒng)的AODV協(xié)議中鄰節(jié)點(diǎn)的IP地址和鏈路生存時(shí)間已經(jīng)存儲(chǔ)在鄰居表中了，并且鏈路生存時(shí)間一般默認(rèn)為40s,因此,在改進(jìn)后的AODV協(xié)議中，鄰居表里還要加入鄰節(jié)點(diǎn)的坐標(biāo)和速度，所以修改后的鄰居表的結(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é)點(diǎn)的橫坐標(biāo)用node_x表示;鄰節(jié)點(diǎn)的縱坐標(biāo)用node_y表示;鄰節(jié)點(diǎn)的運(yùn)動(dòng)速度用node_speed表示; 鄰節(jié)點(diǎn)的IP地址用neighbor_IP表示; 鄰節(jié)點(diǎn)的默認(rèn)鏈路生存時(shí)間用lifetime來(lái)表示。

2.2 算法流程

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

圖2 算法流程

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

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

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

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

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

圖4 端到端時(shí)延比較

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

圖5 吞吐量比較

4 結(jié) 論

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

[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ìn)展[J].電子學(xué)報(bào)，2011，12(39)：2868-2879.

[3] 馬志欣，劉海英，謝顯中.基于地理位置的車載網(wǎng)絡(luò)地理路由算法[J].計(jì)算機(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] 郭彥芳.一種改進(jìn)的基于能量?jī)?yōu)化的AODV路由協(xié)議[J].無(wú)線電通信技術(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ú)線傳感網(wǎng)，嵌入式系統(tǒng)，計(jì)算機(jī)網(wǎng)絡(luò)，圖形與圖像處理，計(jì)算機(jī)分布式控制與智能控制等研究工作。

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-)，女，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感網(wǎng)絡(luò)，嵌入式系統(tǒng)，計(jì)算機(jī)網(wǎng)絡(luò)。