車載網(wǎng)絡(luò)GPSR路由算法的改進

龔丁海

(河池學院 數(shù)學與統(tǒng)計學院，廣西 宜州 546300)

車載網(wǎng)絡(luò)GPSR路由算法的改進

龔丁海

(河池學院 數(shù)學與統(tǒng)計學院，廣西 宜州 546300)

汽車的普及帶來的社會問題促進了車載網(wǎng)絡(luò)的發(fā)展，GPSR是應用于節(jié)點移動速度快和網(wǎng)絡(luò)拓撲變化頻繁的車載網(wǎng)絡(luò)的路由協(xié)議。該協(xié)議會存在路由選擇錯誤和路由中斷的問題，易造成數(shù)據(jù)包丟失，導致網(wǎng)絡(luò)服務(wù)質(zhì)量低。針對GPSR存在路由投遞率低、傳輸時延大的問題，提出了一種改進的GPSR算法。該算法根據(jù)節(jié)點的移動速度，預測節(jié)點間的距離，并選取移動緩慢的、穩(wěn)定的節(jié)點作為中繼節(jié)點，保持路由選擇的可靠性。理論分析表明，在一定的通信范圍內(nèi)，選擇穩(wěn)定的節(jié)點作為中繼節(jié)點能提高路由投遞率，降低傳輸延時。在NS2仿真平臺上，對比兩個協(xié)議在端到端的延時，數(shù)據(jù)包接收的成功率、抖動率以及吞吐量等方面的性能。仿真結(jié)果表明，改進算法要優(yōu)于GPSR協(xié)議，改進后的算法提高了協(xié)議性能，更加符合實際車載網(wǎng)的應用。

GPSR；車載網(wǎng)絡(luò)；移動速度；路由算法

0 引 言

車輛的增多一定程度上造成了交通擁堵和交通安全的嚴峻形勢，這促使智能交通系統(tǒng)(Intelligent Transportation System，ITS)的發(fā)展。車載網(wǎng)絡(luò)VNETs(Vehicular Ad Hoc Networks)[1]作為ITS的核心部分,是利用WLAN技術(shù)，通過車與車、車與設(shè)施之間實現(xiàn)無線多跳通信，其目標是為了在道路交通中建立一個自組織、部署方便、費用低廉、結(jié)構(gòu)開放的車輛間進行通信的網(wǎng)絡(luò)，以實現(xiàn)交通預警、輔助駕駛、道路交通信息查詢等應用。車載網(wǎng)絡(luò)是一種特殊的移動Ad Hoc網(wǎng)絡(luò)，它以車輛間通信為設(shè)計目標[2]，符合延時容忍網(wǎng)絡(luò)[3](Delay-Tolerant Networks，DTN)拓撲變化頻繁、間歇連通性等特征。這些特點使得傳統(tǒng)的移動自組織網(wǎng)路由協(xié)議難以適用于VANETs,因此，車載網(wǎng)絡(luò)的路由設(shè)計成為研究熱點。目前，VANETs路由協(xié)議主要分為三類:基于拓撲的路由協(xié)議、基于地理位置的路由協(xié)議和基于地圖的路由協(xié)議[4]?；诘乩砦恢玫穆酚蓞f(xié)議是根據(jù)車輛按固定的行駛路線提出的。

GPSR(Greedy Perimeter Stateless Routing)是基于地理位置的路由協(xié)議,采用貪婪轉(zhuǎn)發(fā)與周邊轉(zhuǎn)發(fā)相結(jié)合的策略[5-6]，節(jié)點不需要關(guān)注網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，而是依靠鄰居節(jié)點的地理位置信息形成路由，并完成轉(zhuǎn)發(fā)。在實際的車載網(wǎng)絡(luò)環(huán)境中，車輛移動速度快，網(wǎng)絡(luò)拓撲變化頻繁，GPSR將面臨著路由選擇錯誤和路由中斷的問題，易造成路由投遞率下降、傳輸時延增大甚至路由轉(zhuǎn)發(fā)失敗等問題，進而降低網(wǎng)絡(luò)的服務(wù)質(zhì)量[7-8]。因此，國內(nèi)外研究者提出了一些對GPSR路由協(xié)議的改進算法。文獻[9]通過更新鄰居節(jié)點的位置信息，配合鄰居節(jié)點數(shù)目來選擇下一跳節(jié)點，實現(xiàn)傳輸路徑的優(yōu)化。文獻[10-13]利用節(jié)點間形成的方向角度選擇下一跳，解決周邊轉(zhuǎn)發(fā)跳數(shù)多的問題，實現(xiàn)節(jié)約能量、縮短跳數(shù)、提高網(wǎng)絡(luò)穩(wěn)定性的目的。文獻[14]基于對鄰居傳感器節(jié)點的能量感知，提出了有動態(tài)負載均衡能力的GPSR路由算法。這些改進方法在解決路徑優(yōu)化問題的同時往往考慮節(jié)能的要求，并且在進行下一跳選擇的過程中單調(diào)地考慮節(jié)點的位置或方向角度信息，沒有有效地利用實際交通環(huán)境中的車輛移動速度、通信范圍等因素。

針對GPSR路由算法的不足及其存在的問題，提出一種改進的車載網(wǎng)絡(luò)GPSR路由算法—IGPSRs，并從數(shù)據(jù)包投遞率、端到端平均時延、抖動率及吞吐量等方面與傳統(tǒng)GPSR路由算法進行了性能仿真和對比分析。仿真結(jié)果表明，IGPSRs的性能要優(yōu)于GPSR路由算法，更合適實際的網(wǎng)絡(luò)環(huán)境。

1 改進的路由算法(IGPSRs)

1.1 GPSR路由算法及路由問題

GPSR路由協(xié)議將貪婪轉(zhuǎn)發(fā)和邊界轉(zhuǎn)發(fā)相結(jié)合。在發(fā)送數(shù)據(jù)前不關(guān)注路由的構(gòu)建和存儲，移動節(jié)點直接根據(jù)節(jié)點本身、鄰居節(jié)點和目的節(jié)點的位置信息制定數(shù)據(jù)轉(zhuǎn)發(fā)策略。為實現(xiàn)數(shù)據(jù)的有效轉(zhuǎn)發(fā)，數(shù)據(jù)分組需要攜帶目的節(jié)點的地理位置信息，節(jié)點通過周期性廣播分組獲取相鄰節(jié)點的地理位置信息，源節(jié)點或中間節(jié)點根據(jù)這些位置信息，將數(shù)據(jù)分組傳送一個或多個距離目的節(jié)點更近的鄰節(jié)點。通常情況下，各節(jié)點利用貪婪轉(zhuǎn)發(fā)算法來選擇下一跳轉(zhuǎn)發(fā)節(jié)點,但是當局部最優(yōu)化現(xiàn)象發(fā)生時,貪婪轉(zhuǎn)發(fā)算法失效,此時啟動周邊轉(zhuǎn)發(fā)算法選擇下一跳轉(zhuǎn)發(fā)節(jié)點[15]。

GPSR協(xié)議的優(yōu)點是采用局部最優(yōu)的貪婪算法,避免了在節(jié)點中建立、維護、存儲路由表,路由開銷小;能保證只要網(wǎng)絡(luò)連通性不被破壞,一定能夠發(fā)現(xiàn)可達路由;使用接近于最短歐氏距離的路由,數(shù)據(jù)傳輸時延小。其缺點是需要地理位置信息的支持和需要維護鄰居節(jié)點位置信息[2]。車載網(wǎng)移動中節(jié)點的移動速度較快，網(wǎng)絡(luò)拓撲變化頻繁。如果節(jié)點移動了，那下一跳會發(fā)生變化，也就意味著要重新調(diào)用路由算法。在GPSR算法中，越遠的節(jié)點由于移動速度過快，容易超出通信范圍，導致數(shù)據(jù)包在轉(zhuǎn)發(fā)的過程中丟失，降低了服務(wù)質(zhì)量。文中結(jié)合VANETs網(wǎng)絡(luò)的特點,針對傳統(tǒng)GPSR存在的問題,提出一種基于節(jié)點移動速度和節(jié)點間距離的改進GPSR車載路由算法(IGPSRs)。

1.2 IGPSRs算法思想

IGPSRs算法通過對節(jié)點的移動路徑進行預測，找出那些在通信范圍內(nèi)停留時間盡可能長的節(jié)點作為中繼節(jié)點。在通信范圍內(nèi)的節(jié)點所停留的時間越長，表明節(jié)點移動的速度越慢，節(jié)點越穩(wěn)定。

IGPSRs算法的改進策略主要體現(xiàn)在以下幾方面：

(1)當節(jié)點處于數(shù)據(jù)報文轉(zhuǎn)發(fā)選擇下一跳節(jié)點時，對本節(jié)點維護的位置坐標進行預測分析，下一跳節(jié)點除滿足貪心算法轉(zhuǎn)發(fā)機制的要求外，還必須滿足距離位于λa與a之間,其中0<λ<1。

(2)對GPSR路由協(xié)議中節(jié)點周期性發(fā)送hello報文機制。每個節(jié)點動態(tài)更新鄰居的生存時間。

(3)目的節(jié)點發(fā)送查詢包。目的節(jié)點查詢后，每個節(jié)點維護SINK鏈表。目的節(jié)點發(fā)送的查詢包，沒有應答，但它讓每個節(jié)點維護目的節(jié)點表，以貪心算法選擇路徑來轉(zhuǎn)發(fā)數(shù)據(jù)包，目的節(jié)點為接收數(shù)據(jù)包的目的節(jié)點。目的節(jié)點發(fā)送查詢包必不可少，如目的節(jié)點僅發(fā)送hello包，則源節(jié)點無法預知路徑，造成無路徑的情況。

1.3 IGPSRs算法分析

相鄰兩個節(jié)點間的通信越長，表明生存時間越長，節(jié)點之間的通信越穩(wěn)定，但時延也可能越大。車載網(wǎng)絡(luò)中每個節(jié)點的通信范圍是有限的，在IGPSRs中，設(shè)定一個最大通信界限，即節(jié)點的通信范圍最大為a,同時選取一個系數(shù)λ(0<λ<1)，用來表示某一個節(jié)點的通信能力。根據(jù)不同的拓撲結(jié)構(gòu)選擇最優(yōu)化的λa，在通信范圍λa與a之間選擇停留時間最長的節(jié)點作為中繼節(jié)點，該中繼節(jié)點滿足在最優(yōu)通信范圍內(nèi)停留時間最長這個雙重條件，是一個穩(wěn)定的節(jié)點。

假設(shè)節(jié)點(車輛)沿同一方向直線運動，兩節(jié)點間的最大通信半徑范圍為d，時間間隔為t，相對速度為v,則節(jié)點移出的距離為vt,處于連接的范圍為d-vt。在直線范圍內(nèi)，滿足d-vt=d(1-λ)。λ的取值與設(shè)定的時間和最大速度有關(guān)。速度與取樣時間t越大，則λ越大。

取時間段T，假定車的加速度滿足：

(1)

其中，an為加速度；λ為一個正值，其變化范圍為[0，1]；φ1、φ2為最小速度和最大速度的閾值。

假定車輛n以速度vn移動，在間隔時間T內(nèi)轉(zhuǎn)發(fā)數(shù)據(jù)包，中繼節(jié)點與轉(zhuǎn)發(fā)節(jié)點j的鄰居距離初始為ΔdTj，在下一個時序T+1，車輛n的移動速度為：

(2)

轉(zhuǎn)發(fā)節(jié)點與中繼節(jié)點j的距離計算公式為：

Δd=ΔdTj+(dj-dn)

(3)

將式(1)與式(2)代入式(3)計算得到：

(4)

由式(4)可知，Δd與車輛速度相關(guān)。如果vn+1-vn≥φ2或者vn+1-vn≤φ1，則車輛j與車輛i的距離以式(5)發(fā)生變化：

(5)

隨著時間的變更，設(shè)移動的距離最大值為dmax，則：

(6)

假設(shè)二者連接的時間為Δt，連接時間的概率為：

p(Δdj)=Δt/(tT+1-tT)

(7)

假定車輛之間可進行通信，需滿足條件p(Δdj)≥ε。對于中繼節(jié)點，如果ε設(shè)置為1，也就表示兩個車輛在移動過程中，保持在連通狀態(tài)。

所有的節(jié)點靠近目標節(jié)點滿足條件式(7)，但會導致比較大的延時。以貪心算法最大距離轉(zhuǎn)發(fā)，會造成網(wǎng)絡(luò)的不連通性。因此選擇穩(wěn)定的節(jié)點作為中繼，用于提高整個網(wǎng)絡(luò)的性能。

2 仿真實驗和結(jié)果分析

2.1 仿真實驗的描述

實際仿真中使用NS-2平臺，在區(qū)域1 000 m*1 000 m的區(qū)域內(nèi)，設(shè)置30個節(jié)點，最大速度分別設(shè)置為2,4,6,8,10 m/s，通信半徑為40 m。MAC層協(xié)議采用IEEE802.11，數(shù)據(jù)包大小為512 Bytes。取hello包的發(fā)送間隔為5 s。

文中選用GPSR_KeLiu_SUNY_Bingham- ton.tg集成的GPSR協(xié)議，運行g(shù)rid-deploy10x10.tcl的拓撲設(shè)置結(jié)構(gòu)。分析IGPSRs協(xié)議與原GPSR協(xié)議性能的對比情況，選取通信半徑最大為250 m。

實驗采用數(shù)據(jù)分組到達率、平均延時、抖動率、吞吐量四個參數(shù)分析協(xié)議的性能。第一組實驗通過改變車輛平均移動速度，得到不同速度下的數(shù)據(jù)分組的接收成功率。第二組實驗通過改變車輛平均移動速度，得到相應的平均延時。第三組實驗進行抖動率改進協(xié)議的對比。第四組實驗進行吞吐量改進協(xié)議的對比。

2.2 仿真實驗的分析

如圖1所示，隨著移動速度的增加，運動場景的拓撲變化頻繁，IGPSRs協(xié)議的分組接收成功率高于GPSR協(xié)議，而且數(shù)據(jù)包接收的成功率在減小。

端到端平均時延=

圖1 接收成功率對比

從圖2可以看出，隨著移動速度的增加，端到端的平均延時會增加。而IGPSRs，由于選取的是車載網(wǎng)絡(luò)中相對穩(wěn)定的節(jié)點作為中繼節(jié)點，故延時比GPSR短,時延變化比GPSR更加平緩，即能夠更快地傳遞數(shù)據(jù)分組到達目的節(jié)點。

圖2 延時的對比

圖3比較了協(xié)議改進前后抖動率的對比，抖動由相鄰數(shù)據(jù)包延遲時間差除以數(shù)據(jù)包序號差得到。

圖3 抖動率的對比

從圖3可以看出，在相同場景下，IGPSRs協(xié)議的抖動率變化更小。GPSR協(xié)議采用貪心算法，數(shù)據(jù)包在轉(zhuǎn)發(fā)的過程中，由于較高的概率選用移動速度過快的節(jié)點，造成了接收數(shù)據(jù)包的時延較大，數(shù)據(jù)包接收與時延變化更加頻繁。

從圖4可以看出，在相同的場景下，IGPSRs的吞吐量更大。GPSR協(xié)議采用貪心算法，數(shù)據(jù)包被成功接收的時延更大，導致吞吐量較小。IGPSRs算法由于選取的中繼節(jié)點穩(wěn)定，故吞吐量更大。

圖4 吞吐量的對比

3 結(jié)束語

按照移動車載網(wǎng)中的GPSR協(xié)議，以貪心算法轉(zhuǎn)發(fā)數(shù)據(jù)包，則邊緣的節(jié)點容易脫離網(wǎng)絡(luò)，從而造成數(shù)據(jù)包的丟失。針對此問題，提出了一種基于GPSR路由協(xié)議的改進策略。改進策略中通過預測節(jié)點的位置，動態(tài)發(fā)送hello報文以及發(fā)送目的節(jié)點的查詢包等方式，在大量移動的節(jié)點中找出穩(wěn)定的節(jié)點作為數(shù)據(jù)包中轉(zhuǎn)的中繼，以提高網(wǎng)絡(luò)性能。理論分析和仿真結(jié)果均表明，改進算法在接收包的成功率，發(fā)送包的延時、抖動率、吞吐量等方面要優(yōu)于GPSR協(xié)議，且更適用于實際的車載網(wǎng)絡(luò)環(huán)境。

[1]ZeadallyS,HuntR,ChenYS,etal.VehicularAdhocnetworks(VANETS):status,results,andchallenges[J].TelecommunicationSystems,2012,50(4):217-241.

[2] 馮慧芳，趙 亮，王夢茹.一種基于可靠性的車載自組織網(wǎng)絡(luò)路由算法[J].微電子學與計算機,2014(10)：64-68.

[3] 王 博,黃傳河,楊文忠.時延容忍網(wǎng)絡(luò)中基于效用轉(zhuǎn)發(fā)的自適應機會路由算法[J].通信學報,2010,31(10):36-47.

[4] 李萬磊,朱梅麗,謝 波,等.高速公路環(huán)境下VANET路由性能研究[J].計算機工程與設(shè)計,2011,32(6):2163-2167.

[5]KarpB,KungHT.GPSR:greedyperimeterstatelessroutingforwirelessnetworks[C]//Proceedingsofthesixthannualinternationalconferenceonmobilecomputingandnetworking.Boston:ACMPress,2000:243-254.

[6] 唐國明，謝 羿，唐九陽,等.一種基于左、右手法則的GPSR分區(qū)邊界轉(zhuǎn)發(fā)路由協(xié)議[J].計算機應用研究,2011,28(3):1009-1101.

[7] 姚 堅,彭好佑,魏應彬.基于車載網(wǎng)絡(luò)GPSR路由協(xié)議的改進[J].計算機應用與軟件,2014,31(8):118-120.

[8] 于 耕,孫 翔,李洪烈,等.基于機會轉(zhuǎn)發(fā)原理改進的GPSR算法[J].科學技術(shù)與工程,2014,14(10):42-47.

[9]ShuWenjie,WangPing,GuoAihuang,etal.EnhancedGPSRusingneighbor-awarenesspositionupdateandbeacon-assistgeographicforwardinginvehicularadhocnetworks[C]//Proceedingsofthe2007IEEEinternationalconferenceonintelligentvehicles.[s.l.]:IEEE,2010:1143-1147.

[10]LinChiahung,YuanShiaoan,ChiuShihwei,etal.Progressface:analgorithmtoimproveroutingefficiencyofGPSR-likeroutingprotocolsinwirelessAdHocnetworks[J].IEEETransactionsonComputers,2010,59(6):822-834.

[11] 吳三斌,王小明,楊 濤,等.改進的GPSR模型及其仿真分析[J].計算機工程與應用,2011,47(8):100-104.

[12] 李道全,劉海燕,曹齊光,等.基于地理位置的路由算法-GPSR-AD[J].計算機應用,2009,29(12):3215-3217.

[13] 孫 燾,韓 寧,馮 林.基于極大轉(zhuǎn)發(fā)角的地理位置路由GPSR算法改進[J].計算機工程與科學,2011,33(7):40-44.

[14] 劉 宇,趙志軍,沈 強,等.能量感知的GPSR動態(tài)路由負載均衡[J].計算機工程與應用,2011,47(6):23-25.

[15] 王志剛.車載Adhoc網(wǎng)絡(luò)中基于車輛流密度的GPSR協(xié)議的改進研究[D].長春:吉林大學,2012.

Improved GPSR Routing Algorithm for VANETS

GONG Ding-hai

(School of Mathematics and Statistics，Hechi University，Yizhou 546300，China)

Social problems caused by the popularity of cars have promoted the Vehicular Ad Hoc Networks,and routing protocol of GPSR has been used in vehicle network in which the node moves fast and network topology changes frequently.However it easily leads to packet loss and low quality of service because routing errors and routing disruptions will exist in the agreement.To solve these problems which include lower delivery rate and large transmission delay,an improved GPSR algorithm has been proposed in which the relay node is chosen from the nodes that move slower and stably according to the moving speed of nodes and the distance between two nodes for maintaining reliability of route selection.Theoretical analyses show that the stable node chosen as a relay node can promote the routing delivery rate and reduce transmission delay within a certain range communications.Comparisons of end to end delay,delivery ratio and jitter rate between both the protocols on NS2 simulation platform have been conducted.Simulation results show that the improved algorithm is better than the GPSR and performance of the GPSR protocol has been enhanced more suitable for vehicle network.

GPRS;vehicle network;moving speed;routing algorithm

2016-05-02

2016-08-17

時間：2017-03-07

國家自然科學基金資助項目(61163065)；廣西高校科學技術(shù)研究項目重點項目(ZD2014112);廣西壯族自治區(qū)中青年教師基礎(chǔ)能力提升項目(KY2016YB381)

龔丁海(1979-)，男，碩士，講師，CCF會員(會員號：39178M)，研究方向為機會網(wǎng)絡(luò)、車載網(wǎng)絡(luò)和延遲容忍網(wǎng)絡(luò)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0920.014.html

TP393

A

1673-629X(2017)04-0104-04

10.3969/j.issn.1673-629X.2017.04.023