車載網絡GPSR路由算法的改進

龔丁海

(河池學院 數學與統計學院，廣西 宜州 546300)

車載網絡GPSR路由算法的改進

龔丁海

(河池學院 數學與統計學院，廣西 宜州 546300)

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

GPSR；車載網絡；移動速度；路由算法

0 引 言

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

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

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

1 改進的路由算法(IGPSRs)

1.1 GPSR路由算法及路由問題

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

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

1.2 IGPSRs算法思想

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

IGPSRs算法的改進策略主要體現在以下幾方面：

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

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

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

1.3 IGPSRs算法分析

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

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

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

(1)

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

假定車輛n以速度vn移動，在間隔時間T內轉發數據包，中繼節點與轉發節點j的鄰居距離初始為ΔdTj，在下一個時序T+1，車輛n的移動速度為：

(2)

轉發節點與中繼節點j的距離計算公式為：

Δd=ΔdTj+(dj-dn)

(3)

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

(4)

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

(5)

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

(6)

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

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

(7)

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

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

2 仿真實驗和結果分析

2.1 仿真實驗的描述

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

文中選用GPSR_KeLiu_SUNY_Bingham- ton.tg集成的GPSR協議，運行grid-deploy10x10.tcl的拓撲設置結構。分析IGPSRs協議與原GPSR協議性能的對比情況，選取通信半徑最大為250 m。

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

2.2 仿真實驗的分析

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

端到端平均時延=

圖1 接收成功率對比

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

圖2 延時的對比

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

圖3 抖動率的對比

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

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

圖4 吞吐量的對比

3 結束語

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

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

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

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

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

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

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

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

[8] 于 耕,孫 翔,李洪烈,等.基于機會轉發原理改進的GPSR算法[J].科學技術與工程,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] 孫 燾,韓 寧,馮 林.基于極大轉發角的地理位置路由GPSR算法改進[J].計算機工程與科學,2011,33(7):40-44.

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

[15] 王志剛.車載Adhoc網絡中基于車輛流密度的GPSR協議的改進研究[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)；廣西高校科學技術研究項目重點項目(ZD2014112);廣西壯族自治區中青年教師基礎能力提升項目(KY2016YB381)

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

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