伍龍昶 石 英 張煥清 華逸倫

(武漢理工大學(xué)自動(dòng)化學(xué)院 武漢 430070)

基于下一跳前向轉(zhuǎn)發(fā)節(jié)點(diǎn)密度的GPSR改進(jìn)協(xié)議*

伍龍昶 石 英 張煥清 華逸倫

(武漢理工大學(xué)自動(dòng)化學(xué)院 武漢 430070)

分析了一種適用的地理位置路由協(xié)議——貪婪周邊無狀態(tài)路由協(xié)議(greedy perimeter stateless routing protocol,GPSR).針對(duì)其路由空洞過多帶來的投遞率下降、時(shí)延增加等問題，提出了一種綜合考慮接近率和下一跳節(jié)點(diǎn)前向轉(zhuǎn)發(fā)區(qū)域密度的改進(jìn)算法GPSR-D.利用網(wǎng)絡(luò)仿真平臺(tái)NS3對(duì)AODV、GPSR和GPSR-D協(xié)議進(jìn)行仿真研究，結(jié)果表明基于位置的GPSR在投遞率和平均時(shí)延上均較基于拓?fù)涞腁ODV更好，改進(jìn)后的GPSR-D在不增加平均端到端時(shí)延的基礎(chǔ)上減少了約1/2的路由空洞數(shù)，分組投遞率提高了5%.

車載自組網(wǎng)；貪婪周邊無狀態(tài)路由；路由空洞；接近率；前向轉(zhuǎn)發(fā)區(qū)域；NS3仿真

0 引 言

車載自組織網(wǎng)絡(luò)(vehicular ad hoc network,VANET)是一種臨時(shí)的、自由組織的車間通信網(wǎng)絡(luò)，融合了車輛間直接互連，間接互連及車輛與路邊固定設(shè)施互連方式，用來傳遞緊急安全信息和提供網(wǎng)絡(luò)服務(wù)[1-2].作為傳統(tǒng)移動(dòng)自組織網(wǎng)絡(luò)的衍生，車載自組織網(wǎng)絡(luò)具有無中心、自組織、臨時(shí)性和多跳路由等特點(diǎn)，其高度動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和有限的無線傳輸帶寬嚴(yán)重制約了網(wǎng)絡(luò)傳輸?shù)目煽啃?，尤其是多媒體服務(wù)質(zhì)量[3-4].交通信息能影響道路擁堵擴(kuò)散過程[5]，有效緩解因車輛保有量激增和交通基礎(chǔ)設(shè)施建設(shè)相對(duì)緩慢帶來的交通問題，為了實(shí)現(xiàn)信息的有效傳遞，需要簡(jiǎn)潔高效、魯棒性強(qiáng)的路由協(xié)議來提供網(wǎng)絡(luò)服務(wù)支持.目前，車載自組網(wǎng)路由協(xié)議大多從傳統(tǒng)的移動(dòng)自組織網(wǎng)絡(luò)發(fā)展而來，主要分為基于拓?fù)浜突诘乩砦恢眯畔⒌穆酚?其中，基于地理位置信息的路由協(xié)議結(jié)合了網(wǎng)絡(luò)拓?fù)浜偷乩砦恢猛負(fù)?，?yōu)化了路由決策，適用于受道路拓?fù)浣Y(jié)構(gòu)影響的無線網(wǎng)絡(luò).Karp等[6]提出了一種經(jīng)典的地理位置路由協(xié)議——貪婪周邊無狀態(tài)路由協(xié)議(greedy perimeter stateless routing protocol,GPSR)，利用貪婪轉(zhuǎn)發(fā)策略和周邊轉(zhuǎn)發(fā)恢復(fù)策略來建立路由，具有高效簡(jiǎn)潔、擴(kuò)展性好的特點(diǎn).但此算法在遇到路由空洞時(shí)存在跳數(shù)增加、非最佳路徑等問題.文中通過仿真研究改進(jìn)GPSR算法，以減少路由空洞，提高轉(zhuǎn)發(fā)性能，為車聯(lián)網(wǎng)提供更高效的通信服務(wù).

1 GPSR基本原理

1.1 算法描述

GPSR協(xié)議是一種基于地理位置信息的自組網(wǎng)路由協(xié)議，核心思想是貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā).每個(gè)節(jié)點(diǎn)周期性地廣播Hello信標(biāo)，該信標(biāo)包含本節(jié)點(diǎn)的ID標(biāo)識(shí)及地理位置信息.與此同時(shí)，每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)鄰居位置表，接收到Hello信標(biāo)后更新并存儲(chǔ)其鄰居節(jié)點(diǎn)的編號(hào)和位置信息.當(dāng)有數(shù)據(jù)分組發(fā)送時(shí)，首先使用貪婪轉(zhuǎn)發(fā)算法遍歷鄰居位置表，計(jì)算鄰居節(jié)點(diǎn)與目的節(jié)點(diǎn)的歐式距離，選取距離值最小的鄰居進(jìn)行下一跳轉(zhuǎn)發(fā).類似的，每個(gè)中間節(jié)點(diǎn)通過貪婪轉(zhuǎn)發(fā)算法進(jìn)行分組轉(zhuǎn)發(fā)直至到達(dá)目的節(jié)點(diǎn)或者貪婪轉(zhuǎn)發(fā)失敗.當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離比所有鄰居節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離更近時(shí)，貪婪轉(zhuǎn)發(fā)失敗，數(shù)據(jù)分組陷入局部最優(yōu)，即傳播路徑上出現(xiàn)了路由空洞，此時(shí)，GPSR從貪婪轉(zhuǎn)發(fā)模式轉(zhuǎn)換到周邊轉(zhuǎn)發(fā)模式.周邊轉(zhuǎn)發(fā)模式通過相對(duì)鄰域圖、加百利圖等平面化算法簡(jiǎn)化網(wǎng)絡(luò)拓?fù)洌負(fù)鋱D中的交叉邊，然后通過右手法則選取下一跳節(jié)點(diǎn)，即源-目的節(jié)點(diǎn)的邊以逆時(shí)針方向旋轉(zhuǎn)遍歷鄰居節(jié)點(diǎn)，故數(shù)據(jù)分組在順時(shí)針方向上圍繞路由空洞進(jìn)行轉(zhuǎn)發(fā)，直至恢復(fù)貪婪轉(zhuǎn)發(fā)模式或者到達(dá)目的節(jié)點(diǎn).

1.2 算法特點(diǎn)

GPSR算法簡(jiǎn)潔高效、復(fù)雜度低，由于只利用一跳節(jié)點(diǎn)范圍的狀態(tài)信息進(jìn)行路由選擇，可擴(kuò)展性強(qiáng)，適用于大規(guī)模網(wǎng)絡(luò).GPSR算法高效而完備，其貪婪算法充分利用了鄰居節(jié)點(diǎn)的位置信息，選取傳播最遠(yuǎn)的轉(zhuǎn)發(fā)節(jié)點(diǎn)，實(shí)現(xiàn)了數(shù)據(jù)分組的高效轉(zhuǎn)發(fā)；周邊轉(zhuǎn)發(fā)算法在平面圖的基礎(chǔ)上利用右手法則進(jìn)行周邊遍歷，直至恢復(fù)貪婪轉(zhuǎn)發(fā)模式，保障了路由協(xié)議的完備性.

GPSR也存在著一些局限性，貪婪算法選取的轉(zhuǎn)發(fā)節(jié)點(diǎn)通?？拷ㄐ胚吘?，如果節(jié)點(diǎn)在Hello周期內(nèi)移動(dòng)出了該范圍，會(huì)導(dǎo)致傳輸失敗.周邊轉(zhuǎn)發(fā)模式雖然能保證數(shù)據(jù)分組能夠走出路由空洞，但每次轉(zhuǎn)發(fā)都需要平面化拓?fù)鋪硐徊孢?，以增加轉(zhuǎn)發(fā)跳數(shù)為代價(jià)來減少路由環(huán)路，并且大多數(shù)情況下轉(zhuǎn)發(fā)路徑不是最佳，因此頻繁的路由空洞會(huì)造成GPSR算法性能的劇烈下降.

在GPSR的基礎(chǔ)上，唐國明等[7]提出了基于左、右手法則的改進(jìn)算法，在遇到路由空洞時(shí)根據(jù)節(jié)點(diǎn)所處的區(qū)域選取相應(yīng)的左右手法則進(jìn)行轉(zhuǎn)發(fā)，以減少路由跳數(shù)，提高分組投遞率.Kumar等[8]通過速度和方向預(yù)測(cè)節(jié)點(diǎn)位置來選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，以減少Hello信標(biāo)周期內(nèi)因節(jié)點(diǎn)移動(dòng)而導(dǎo)致的鏈路失效.Sabri等[9]結(jié)合轉(zhuǎn)發(fā)方向角和當(dāng)前節(jié)點(diǎn)范圍分布因素選擇下一跳節(jié)點(diǎn)，以減少路由環(huán)路并提高性能.Chung等[10]提出了基于定時(shí)器的貪婪轉(zhuǎn)發(fā)策略，定時(shí)器與距離成反比，超時(shí)即廣播數(shù)據(jù)分組，其他節(jié)點(diǎn)接收到該分組的副本時(shí)丟棄該分組，該策略避免了額外的信息交換.

這些改進(jìn)方法雖然優(yōu)化了路由效果，但均根據(jù)本地節(jié)點(diǎn)的狀態(tài)信息作為轉(zhuǎn)發(fā)策略依據(jù)，沒有充分考慮網(wǎng)絡(luò)中的其他信息，轉(zhuǎn)發(fā)節(jié)點(diǎn)的選取具有一定的局限性.且改進(jìn)后的算法雖然優(yōu)化了路由空洞的恢復(fù)策略，但并沒有從根本上解決或減少遇到空洞的問題.

2 GPSR算法改進(jìn)

2.1 前提條件

1) 所有車輛節(jié)點(diǎn)均配備GPS或其他定位設(shè)備，可以實(shí)時(shí)獲知自身所在位置信息并被統(tǒng)一編址.

2) 通過網(wǎng)格位置服務(wù)、反應(yīng)式位置服務(wù)和層次位置服務(wù)等位置請(qǐng)求服務(wù)，能夠獲取目的節(jié)點(diǎn)的位置[11].

3) 車輛節(jié)點(diǎn)通信范圍近似為一個(gè)平面，通信模塊工作于混雜模式下.

2.2 基本思想

通過下一跳節(jié)點(diǎn)的鄰居分布情況來加強(qiáng)轉(zhuǎn)發(fā)節(jié)點(diǎn)尋優(yōu)的過程，綜合考慮接近率和下一跳節(jié)點(diǎn)前向轉(zhuǎn)發(fā)區(qū)域密度因素，以此作目標(biāo)評(píng)價(jià)函數(shù)，優(yōu)化轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇，以減少路由空洞幾率，提高路由性能，從而提出了基于下一跳節(jié)點(diǎn)前向轉(zhuǎn)發(fā)區(qū)域密度的改進(jìn)算法GPSR-D.

2.2.1 接近率

圖1為接近率的示意圖，由圖1可知，車輛節(jié)點(diǎn)S為信息流源節(jié)點(diǎn)，車輛節(jié)點(diǎn)D為目的節(jié)點(diǎn)，節(jié)點(diǎn)X為節(jié)點(diǎn)S的任一鄰居節(jié)點(diǎn)，R為S節(jié)點(diǎn)的通信范圍.實(shí)線段表示節(jié)點(diǎn)之間的歐式距離，虛線弧表示以該距離為半徑，目的節(jié)點(diǎn)為圓心作的圓弧.貪婪算法根據(jù)歐式距離選取距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，定義接近率為

(1)

式中：x和y為各節(jié)點(diǎn)的坐標(biāo)值；R為節(jié)點(diǎn)的通信范圍.

圖1 接近率示意圖

接近率反映了鄰居節(jié)點(diǎn)在數(shù)據(jù)傳輸方向上接近通信邊緣的程度，其取值范圍為[-1,1]，值為正且越大時(shí)，轉(zhuǎn)發(fā)節(jié)點(diǎn)的優(yōu)先權(quán)越大.值為負(fù)時(shí)則不列入候選轉(zhuǎn)發(fā)節(jié)點(diǎn).

2.2.2 前向轉(zhuǎn)發(fā)區(qū)域密度

前向轉(zhuǎn)發(fā)區(qū)域見圖2，S為源節(jié)點(diǎn)，D為目的節(jié)點(diǎn)，X為節(jié)點(diǎn)S的任一鄰居節(jié)點(diǎn).以X節(jié)點(diǎn)為原點(diǎn)，將X的通信范圍劃分為4個(gè)象限，統(tǒng)計(jì)每個(gè)象限的鄰居節(jié)點(diǎn)數(shù)，將之附加在Hello信標(biāo)中進(jìn)行廣播.節(jié)點(diǎn)S接收到節(jié)點(diǎn)X的Hello信標(biāo)后，計(jì)算X與D節(jié)點(diǎn)的方向角，該方向角所處的180°區(qū)域范圍記作數(shù)據(jù)分組的前向轉(zhuǎn)發(fā)區(qū)域.

圖2 前向轉(zhuǎn)發(fā)區(qū)域示意圖

以圖中X，D點(diǎn)位置為例，其夾角處于(315,45]范圍，可以認(rèn)為前向轉(zhuǎn)發(fā)區(qū)域?yàn)?象限和4象限.定義前向轉(zhuǎn)發(fā)區(qū)域密度的評(píng)價(jià)函數(shù)為

(2)

式中：∑ni為前向轉(zhuǎn)發(fā)區(qū)域的節(jié)點(diǎn)數(shù)之和；N為區(qū)域內(nèi)飽和節(jié)點(diǎn)閾值.fden取值范圍為[0,1]，值越高，轉(zhuǎn)發(fā)優(yōu)先權(quán)越大.大于節(jié)點(diǎn)數(shù)閾值N，可認(rèn)為前向轉(zhuǎn)發(fā)區(qū)域內(nèi)已有較好的連通性，此時(shí)fden取值1，轉(zhuǎn)發(fā)策略恢復(fù)成貪婪轉(zhuǎn)發(fā).

結(jié)合上述接近率和密度模型作為節(jié)點(diǎn)優(yōu)選評(píng)價(jià)指標(biāo)，多目標(biāo)函數(shù)為

maxF=max[fdis,fden]T

s.t. (xX-xS)2+(yX-yS)2≤R2

(3)

重構(gòu)多目標(biāo)函數(shù)的評(píng)價(jià)函數(shù)為

F=max{ρfdis+(1-ρ)fden}

s.t. (xX-xS)2+(yX-yS)2≤R2

(4)

式中：ρ為目標(biāo)權(quán)重，表示接近率在評(píng)價(jià)機(jī)制中所占比重.經(jīng)過實(shí)驗(yàn)，ρ從0.1～1.0，步長(zhǎng)為0.1，N從2～10，步長(zhǎng)為2，根據(jù)結(jié)果選取較優(yōu)參數(shù)ρ=0.7和N=8.結(jié)果表明，貪婪算法中，距離對(duì)路由性能的影響更大，同時(shí)下一跳節(jié)點(diǎn)的前向區(qū)域密度也是不可忽視的因素.

為了利用下一跳節(jié)點(diǎn)的狀態(tài)信息，Hello信標(biāo)更改為

IDX0Y0N1N2N3N4

其中：ID為每個(gè)節(jié)點(diǎn)的唯一標(biāo)識(shí)符；X0、Y0為節(jié)點(diǎn)在平面坐標(biāo)下的當(dāng)前位置；N1-N4分別為節(jié)點(diǎn)4個(gè)象限的鄰居節(jié)點(diǎn)數(shù).

2.3 算法流程

GPSR-D算法分為以下6步.

步驟1 網(wǎng)絡(luò)中所有節(jié)點(diǎn)周期性廣播Hello信標(biāo).收到信標(biāo)，則更新位置表中鄰居節(jié)點(diǎn)的位置、分區(qū)節(jié)點(diǎn)數(shù)等信息.

步驟2 信息源節(jié)點(diǎn)S通過位置請(qǐng)求服務(wù)獲取目的節(jié)點(diǎn)D的地理位置.

步驟3 如果D在S通信范圍內(nèi)，則直接轉(zhuǎn)發(fā)到目的節(jié)點(diǎn).

步驟4 轉(zhuǎn)發(fā)節(jié)點(diǎn)計(jì)算鄰居節(jié)點(diǎn)集NN的接近率fdis.

步驟5 如果fdis>0，計(jì)算該鄰居節(jié)點(diǎn)的評(píng)分F并加入候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集CN，否則回到步驟4計(jì)算下一鄰居節(jié)點(diǎn).

步驟6 如果候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集為空，則進(jìn)入周邊轉(zhuǎn)發(fā)模式，否則選取評(píng)分F最高的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā).

2.4 算法特點(diǎn)

GPSR-D優(yōu)點(diǎn)在于不僅僅考慮本地節(jié)點(diǎn)獲取的狀態(tài)信息，還考慮下一跳節(jié)點(diǎn)的鄰居分布情況，保證了下一跳仍處于高效的貪婪轉(zhuǎn)發(fā)模式.同時(shí)數(shù)據(jù)分組在前向轉(zhuǎn)發(fā)區(qū)域上密度越大，不失一般性，可以認(rèn)為其連通性越強(qiáng)，出現(xiàn)路由空洞的幾率越小，可以有效減少路由空洞帶來的性能下降問題.相較于GPSR的本地優(yōu)化策略，GPSR-D考慮兩跳狀態(tài)信息優(yōu)選節(jié)點(diǎn)，既給轉(zhuǎn)發(fā)策略提供更多的選擇信息，又避免了多跳狀態(tài)信息造成的路由開銷.

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 仿真場(chǎng)景搭建

利用開源網(wǎng)絡(luò)仿真平臺(tái)NS3搭建仿真場(chǎng)景，對(duì)GPSR-D進(jìn)行仿真，并與GPSR和AODV路由協(xié)議進(jìn)行比較.分析路由協(xié)議在數(shù)據(jù)分組投遞率、平均端到端時(shí)延，以及路由空洞數(shù)等方面的性能表現(xiàn).

仿真實(shí)驗(yàn)以空曠地帶車輛節(jié)點(diǎn)自由行駛作為仿真場(chǎng)景，為了增加轉(zhuǎn)發(fā)跳數(shù)，將交通場(chǎng)景抽象成1 500 m×300 m的矩形區(qū)域，采用隨機(jī)游走模型，仿真場(chǎng)景參數(shù)見表1.

表1 仿真場(chǎng)景參數(shù)

設(shè)計(jì)兩組實(shí)驗(yàn)，一組實(shí)驗(yàn)中車輛最高速度為20 m/s，車輛數(shù)從20～160變化，步進(jìn)值為20，驗(yàn)證協(xié)議在不同節(jié)點(diǎn)密度下的性能表現(xiàn)；另一組實(shí)驗(yàn)中車輛數(shù)為40，車輛最高速度從0～40 m/s變化，步進(jìn)值為5，驗(yàn)證協(xié)議在不同速度下的性能表現(xiàn).

3.2 仿真結(jié)果分析

對(duì)于兩組實(shí)驗(yàn)，以不同的隨機(jī)數(shù)種子執(zhí)行5次，取結(jié)果的平均值.實(shí)驗(yàn)1仿真研究AODV、GPSR和GPSR-D在不同節(jié)點(diǎn)密度下關(guān)于分組投遞率、平均端到端時(shí)延，以及路由空洞數(shù)等方面的性能表現(xiàn)，實(shí)驗(yàn)結(jié)果見圖3～5.

圖3為不同節(jié)點(diǎn)密度下的分組投遞率對(duì)比結(jié)果.由圖3可知，在40個(gè)節(jié)點(diǎn)之后，隨著節(jié)點(diǎn)數(shù)的增加，AODV的投遞率從85%急劇下降到40%附近，由于AODV基于網(wǎng)絡(luò)拓?fù)溥M(jìn)行路由選擇，需要泛洪路由消息控制幀：請(qǐng)求包RREQ、應(yīng)答包RREP和錯(cuò)誤包RERR，網(wǎng)絡(luò)規(guī)模越大，轉(zhuǎn)發(fā)路徑越長(zhǎng)，路由控制信息就越多，容易造成廣播泛洪和網(wǎng)絡(luò)擁塞.GPSR和GPSR-D的投遞率隨節(jié)點(diǎn)數(shù)曲線下降緩慢，

圖3 不同節(jié)點(diǎn)密度投遞率

維持在80%附近，由于其貪婪特性，理論上在達(dá)到一定的密度閾值即可有較好表現(xiàn)，但受信道競(jìng)爭(zhēng)和退避算法的影響，隨著節(jié)點(diǎn)數(shù)增加，其投遞率略有下降，其中改進(jìn)后的算法GPSR-D投遞率表現(xiàn)平均比GPSR高5個(gè)百分點(diǎn)以上，體現(xiàn)了GPSR-D考慮下一跳前向區(qū)域連通性進(jìn)行轉(zhuǎn)發(fā)的優(yōu)點(diǎn).

圖4為不同節(jié)點(diǎn)密度下的平均端到端時(shí)延對(duì)比結(jié)果，反映出基于拓?fù)涞腁ODV協(xié)議有著較高的時(shí)延基數(shù)，并受節(jié)點(diǎn)密度影響較大.GPSR-D的平均時(shí)延較GPSR相近，基本處于0.018 s以下的較小值，說明GPSR-D保持了貪婪算法的特性，轉(zhuǎn)發(fā)跳數(shù)少且受節(jié)點(diǎn)密度影響較小.

圖4 不同節(jié)點(diǎn)密度平均端到端時(shí)延

圖5為GPSR和GPSR-D在不同節(jié)點(diǎn)密度下遇到路由空洞的次數(shù).節(jié)點(diǎn)數(shù)為20時(shí)，路由空洞數(shù)均較高，這是由于節(jié)點(diǎn)分布稀疏，容易導(dǎo)致找不到合適的節(jié)點(diǎn)進(jìn)行貪婪轉(zhuǎn)發(fā).在節(jié)點(diǎn)數(shù)為40節(jié)點(diǎn)以上時(shí)，路由空洞數(shù)大幅下降，因?yàn)槊芏仍黾佣軌蚓S持較高效的貪婪轉(zhuǎn)發(fā).結(jié)果顯示GPSR-D較GPSR遇到路由空洞的幾率減少了約一半，有著更好的轉(zhuǎn)發(fā)性能.

圖5 不同節(jié)點(diǎn)密度路由空洞數(shù)

實(shí)驗(yàn)2仿真研究AODV，GPSR和GPSR-D在不同節(jié)點(diǎn)速度下的性能表現(xiàn)，實(shí)驗(yàn)結(jié)果見圖6～8.

圖6為不同速度下的分組投遞率對(duì)比結(jié)果.在低速情況下，鏈路中斷率低，三種路由協(xié)議均有較好的表現(xiàn)，GPSR和GPSR-D可以接近100%的投遞率.隨著速度的增加，網(wǎng)絡(luò)拓?fù)鋽嗔言絹碓筋l繁，數(shù)據(jù)分組投遞率也逐漸下降.結(jié)果顯示，GPSR-D在5 m/s以上的運(yùn)動(dòng)速度時(shí)，比GPSR有更高的投遞率.這是由于周邊轉(zhuǎn)發(fā)過程對(duì)位置信息較敏感，當(dāng)速度增加時(shí)，節(jié)點(diǎn)位置信息更容易失效而導(dǎo)致丟包現(xiàn)象，故減少了路由空洞數(shù)的GPSR-D丟包更少.

圖6 不同節(jié)點(diǎn)速度投遞率

圖7為不同速度下的平均端到端時(shí)延對(duì)比結(jié)果.AODV的時(shí)延呈波動(dòng)上升到約0.05 s，說明傳輸鏈路斷裂時(shí)，AODV需要額外的路由控制幀來進(jìn)行路由恢復(fù).GPSR-D的時(shí)延保持在0.008 s以下，大部分情況下傳輸時(shí)延相較于GPSR更低，表明減少路由空洞后，在一定程度上減少了平均端到端時(shí)延.

圖7 不同速度平均端到端時(shí)延

GPSR和GPSR-D在不同節(jié)點(diǎn)速度下遇到路由空洞的次數(shù)見圖8.在5 m/s的低速下，路由空洞幾乎為0，這是因?yàn)楣?jié)點(diǎn)位置的初始分配造成空洞數(shù)較少.在速度增加到10 m/s以上時(shí)，拓?fù)渥儞Q增強(qiáng)，路由空洞數(shù)增加，而GPSR-D平均減少一半以上遇到路由空洞的幾率，這是由于其通過下一跳狀態(tài)信息的收集處理，選取連通性更好的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā).

圖8 不同速度路由空洞數(shù)

4 結(jié) 束 語

針對(duì)傳統(tǒng)GPSR路由轉(zhuǎn)發(fā)決策非全局最優(yōu)及遇到路由空洞存在的效率下降問題，提出了基于下一跳前向轉(zhuǎn)發(fā)區(qū)域密度的改進(jìn)算法GPSR-D.通過NS3仿真平臺(tái)對(duì)AODV，GPSR和GPSR-D協(xié)議進(jìn)行仿真比較，證實(shí)基于地理位置的路由在大規(guī)模網(wǎng)絡(luò)中的分組投遞率、平均端到端時(shí)延較基于拓?fù)涞穆酚蓞f(xié)議有較好的表現(xiàn)，且改進(jìn)后的GPSR-D算法雖然考慮更多約束條件，相較于GPSR算法，在不同節(jié)點(diǎn)密度和不同節(jié)點(diǎn)速度下，并未增加平均端到端時(shí)延，由于減少了路由空洞出現(xiàn)的次數(shù)，獲得了更高的分組投遞率.

[1]URQUIZA A, TRIPP B, ROMERO M A. Mitigation of packet duplication in VANET unicast protocols[J]. AD HOC Networks,2016,52(SI):63-77.

[2]ELIAS C E, ZHANG S J, LIU E J. Vehicular ad hoc networks (VANETs): current state, challenges, potentials and way forward[C]. Automation and Computing (ICAC), 2014 20th International Conference on, Bedfordshire，IEEE,2014.

[3]任智，姚玉坤，曹建玲，等.無線自組織網(wǎng)絡(luò)路由協(xié)議及應(yīng)用[M].北京:電子工業(yè)出版社,2015.

[4]馮振新，李臘元.典型Ad hoc網(wǎng)絡(luò)協(xié)議傳輸多媒體數(shù)據(jù)的性能分析[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2007,31(6):1075-1078.

[5]葉曉飛，包哲寧，鄧社軍，等.信息化條件下交通擁堵瓶頸識(shí)別與擴(kuò)散判別[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2014,38(5):1060-1064.

[6]KARP B, KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[C]. Proceedings of the 6th Annual International Conference on Mobile Computing and Networking(MobiCom2000), Boston，ACM,2000.

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

[8]KUMAR R, RAO S V. Directional greedy routing protocol (DGRP) in mobile ad-hoc networks[C]. International Conference on Information Technology, Bhubaneswar，IEEE,2008.

[9]SABRI M H, MOHAMMAD M K, TAT C W. Density-aware directional forwarding strategy for vehicular ad hoc networks[C]. Communications (MICC), 2015 IEEE 12th Malaysia International Conference on, Malaysia，IEEE,2015.

[10]CHUNG M H, SHIH Y L. Timer-based greedy forwarding algorithm in vehicular ad hoc networks[J]. Intelligent Transport Systems,2014,8(4):333-344.

[11]OMER K A A, LOBIYAL D K. Efficient grid location service scheme for MANET[J]. Inst of Electronics and Telecommunication Engineers,2015,52(2):177-185.

The Improvement of GPSR Protocol Based on the Node Density of the Next Hop’s Forwarding Region

WU Longchang SHI Ying ZHANG Huanqing HUA Yilun

(School of Automation, Wuhan University of Technology, Wuhan 430070, China)

A suitable routing protocol based on the geographic location, Greedy Perimeter Stateless Routing Protocol, is analyzed. In order to improve the performances of packet delivery rate and the delay caused by excessive routing void, an improved algorithm GPSR-D taking the approaching rate and the forwarding node density of the next hop into account for the optimum selecting of the forwarding node, is proposed. Through the network simulator of NS3, the performances of AODV, GPSR and GPSR-D are studied. It shows that from the view of packet delivery and the average delay, GPSR based on geographic location is better than that of AODV based on topology, and GPSR-D does better than GPSR for one half of the routing void decrease and the packet delivery rate increase of more than 5% without the extra average end-to-end delay.

vehicular ad hoc network; greedy perimeter stateless routing protocol; routing void; approaching rate; forwarding region; NS3 simulation

2017-04-07

*江蘇省重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(BE2016155)、國家自然科學(xué)基金項(xiàng)目(61374050，61673306，51477125)資助

TP393

10.3963/j.issn.2095-3844.2017.03.023

伍龍昶(1992—)：男，碩士生，主要研究領(lǐng)域?yàn)檐嚶?lián)網(wǎng)