張繼榮, 趙曉彤, 屈軍鎖, 崔 燕

(1.西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121; 2.電信科學(xué)技術(shù)第四研究所 研發(fā)中心, 陜西 西安 710061)

改進(jìn)的貪婪型周邊無(wú)狀態(tài)路由協(xié)議

張繼榮1, 趙曉彤1, 屈軍鎖1, 崔 燕2

(1.西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121; 2.電信科學(xué)技術(shù)第四研究所 研發(fā)中心, 陜西 西安 710061)

對(duì)貪婪型周邊無(wú)狀態(tài)路由協(xié)議加以改進(jìn)。在報(bào)頭中加入鄰居節(jié)點(diǎn)的移動(dòng)速度和方向信息，當(dāng)節(jié)點(diǎn)轉(zhuǎn)發(fā)過(guò)程遭遇路由空洞時(shí)，據(jù)此信息預(yù)測(cè)鄰居節(jié)點(diǎn)下一時(shí)刻的位置。若預(yù)測(cè)位置不符合貪婪轉(zhuǎn)發(fā)要求，仍繼續(xù)周邊轉(zhuǎn)發(fā)模式，否則，進(jìn)入“等待轉(zhuǎn)發(fā)模式”，即經(jīng)過(guò)一個(gè)極小的等待時(shí)延后，跳轉(zhuǎn)回到貪婪轉(zhuǎn)發(fā)模式，以減少周邊轉(zhuǎn)發(fā)過(guò)程存在的大量冗余。借助仿真軟件Network Simulator version 2搭建網(wǎng)絡(luò)環(huán)境，對(duì)改進(jìn)協(xié)議與原協(xié)議在節(jié)點(diǎn)速度為10～40 m/s的情況下仿真，比較其端到端時(shí)延和平均跳數(shù)，結(jié)果顯示，改進(jìn)協(xié)議在給定環(huán)境中能夠降低時(shí)延5%～17%，減少跳數(shù)5%左右。

路由空洞；貪婪型周邊無(wú)狀態(tài)路由協(xié)議；Network Simulator

貪婪型周邊無(wú)狀態(tài)路由協(xié)議(Greedy Perimeter Stateless Routing, GPSR)[1]是移動(dòng)自組網(wǎng)中一種常用路由協(xié)議，它通過(guò)預(yù)先獲取位置信息，利用源節(jié)點(diǎn)和目的節(jié)點(diǎn)的位置來(lái)制定數(shù)據(jù)包轉(zhuǎn)發(fā)策略，其具體轉(zhuǎn)發(fā)過(guò)程包括兩種模式[2]，即貪婪轉(zhuǎn)發(fā)模式和周邊轉(zhuǎn)發(fā)模式。

GPSR協(xié)議優(yōu)先采用貪婪轉(zhuǎn)發(fā)模式，源節(jié)點(diǎn)選擇距離目的節(jié)點(diǎn)最近的鄰居節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，鄰居節(jié)點(diǎn)收到轉(zhuǎn)發(fā)分組時(shí)，會(huì)繼續(xù)采用同樣的方法進(jìn)行轉(zhuǎn)發(fā)，最終被傳至目的節(jié)點(diǎn)。貪婪轉(zhuǎn)發(fā)的缺點(diǎn)是路由空洞問(wèn)題[3]。當(dāng)遭遇路由空洞時(shí)，則會(huì)轉(zhuǎn)入周邊轉(zhuǎn)發(fā)模式，順著路由空洞的周邊通過(guò)右手定則尋找新的路由。當(dāng)貪婪轉(zhuǎn)發(fā)條件再次滿(mǎn)足時(shí)，可以自動(dòng)轉(zhuǎn)回貪婪模式，直到數(shù)據(jù)分組發(fā)送到目的節(jié)點(diǎn)[4]。

GPSR 協(xié)議使用貪婪思想進(jìn)行轉(zhuǎn)發(fā)分組，降低了開(kāi)銷(xiāo)，提高了協(xié)議的穩(wěn)定性[5]，但協(xié)議存在的問(wèn)題也很多。針對(duì)局部區(qū)域內(nèi)節(jié)點(diǎn)多次承擔(dān)轉(zhuǎn)發(fā)任務(wù)而能量耗盡的問(wèn)題，文獻(xiàn)[6]提出一種改進(jìn)的路由算法IGPSR，該算法結(jié)合能量的前向區(qū)域劃分機(jī)制和概率傳輸機(jī)制在鄰居節(jié)點(diǎn)中選擇下一跳節(jié)點(diǎn)，有效保證鄰居節(jié)點(diǎn)能量的均衡消耗；針對(duì)可能出現(xiàn)的路由隔斷和延時(shí)增加問(wèn)題，文獻(xiàn)[7]所給改進(jìn)方案，有效改善了路由錯(cuò)誤和冗余問(wèn)題；針對(duì)邊界節(jié)點(diǎn)能量消耗大和遇到路由空洞時(shí)路由效率低下的問(wèn)題，文獻(xiàn)[8]提出一種基于機(jī)會(huì)轉(zhuǎn)發(fā)的改進(jìn)協(xié)議O-GPSR；為了實(shí)現(xiàn)傳輸節(jié)點(diǎn)路徑的最優(yōu)化，文獻(xiàn)[9]根據(jù)每個(gè)節(jié)點(diǎn)中維護(hù)的鄰居節(jié)點(diǎn)相關(guān)信息進(jìn)行分析，選擇轉(zhuǎn)發(fā)過(guò)程的下一跳節(jié)點(diǎn)。

本文擬針對(duì)周邊轉(zhuǎn)發(fā)過(guò)程中由于使用右手定則而產(chǎn)生的跳數(shù)增多和路徑冗余問(wèn)題，給出一種新的GPSR協(xié)議改進(jìn)方法。通過(guò)在報(bào)頭中添加鄰居節(jié)點(diǎn)的移動(dòng)速度和方向信息，使節(jié)點(diǎn)在遇到路由空洞時(shí)能夠預(yù)測(cè)鄰居節(jié)點(diǎn)下一時(shí)刻的位置，從而判斷是否能夠符合貪婪轉(zhuǎn)發(fā)的條件，添加了“等待轉(zhuǎn)發(fā)模式”，即在等待一個(gè)極小的時(shí)延后，再次跳轉(zhuǎn)到貪婪轉(zhuǎn)發(fā)模式，以減少周邊轉(zhuǎn)發(fā)過(guò)程存在的大量冗余。

1 GPSR協(xié)議改進(jìn)

1.1 GPSR協(xié)議存在的問(wèn)題

在周邊轉(zhuǎn)發(fā)的過(guò)程中，數(shù)據(jù)包會(huì)開(kāi)拓一條到目的節(jié)點(diǎn)的轉(zhuǎn)向路徑，而這條路徑通常會(huì)很長(zhǎng)，造成了能量的浪費(fèi)和過(guò)多的延時(shí)。如圖1所示，假設(shè)節(jié)點(diǎn)S檢測(cè)到路由空洞，自身成為了最佳主機(jī)，則采用周邊轉(zhuǎn)發(fā)模式，轉(zhuǎn)發(fā)過(guò)程為S→L→M→N→P→Q→D，且在節(jié)點(diǎn)密度增大的時(shí)候，周邊轉(zhuǎn)發(fā)模式也會(huì)使路由跳數(shù)增多，導(dǎo)致信道資源浪費(fèi)和時(shí)延的增加。這一問(wèn)題正是需要改進(jìn)之處。

圖1 GPSR協(xié)議遭遇路由空洞轉(zhuǎn)發(fā)過(guò)程

1.2 GPSR協(xié)議改進(jìn)思想

(1) 在每個(gè)節(jié)點(diǎn)維護(hù)的鄰居表中，加入鄰居節(jié)點(diǎn)的移動(dòng)方向、速度等信息，在獲取鄰居節(jié)點(diǎn)的地理坐標(biāo)位置的同時(shí)，也需要獲得鄰居節(jié)點(diǎn)X，Y，Z三個(gè)方向的速度，通過(guò)方向和速度預(yù)測(cè)鄰居節(jié)點(diǎn)位置。

(2) 考慮到MANET網(wǎng)絡(luò)的隨機(jī)移動(dòng)性，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是隨時(shí)間不斷變化的，給出一種“等待轉(zhuǎn)發(fā)模式”。節(jié)點(diǎn)S在轉(zhuǎn)發(fā)過(guò)程中遭遇路由空洞時(shí)，對(duì)鄰居表進(jìn)行維護(hù)，獲取其他節(jié)點(diǎn)的速度和方向，對(duì)節(jié)點(diǎn)的移動(dòng)位置進(jìn)行預(yù)測(cè)，并預(yù)測(cè)節(jié)點(diǎn)鄰居關(guān)系的變化，選取在下一時(shí)刻能夠跳入自己轉(zhuǎn)發(fā)范圍且在目的節(jié)點(diǎn)方向上的點(diǎn)，作為最佳邊緣節(jié)點(diǎn)。如果存在這樣的最佳邊緣節(jié)點(diǎn)，則等待一個(gè)最小時(shí)間間隔Δt，在下一時(shí)刻最佳邊緣節(jié)點(diǎn)跳入后繼續(xù)采取貪婪轉(zhuǎn)發(fā)模式進(jìn)行下一跳轉(zhuǎn)發(fā)。如果不存在這樣的邊緣轉(zhuǎn)發(fā)節(jié)點(diǎn)，則仍然采用周邊轉(zhuǎn)發(fā)模式，使用右手定則進(jìn)行轉(zhuǎn)發(fā)。

改進(jìn)后的路由轉(zhuǎn)發(fā)過(guò)程如圖2所示。源節(jié)點(diǎn)S的邊緣節(jié)點(diǎn)Q和M在下一時(shí)刻跳入S的轉(zhuǎn)發(fā)范圍之內(nèi)，且Q即為最佳邊緣節(jié)點(diǎn)，下一時(shí)刻新增點(diǎn)Q′和點(diǎn)M′，此刻S不再是最佳主機(jī)，則可以繼續(xù)采用貪婪策略進(jìn)行轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)過(guò)程為S→Q′→D，最終到達(dá)目的節(jié)點(diǎn)D。

圖2 改進(jìn)協(xié)議遭遇路由空洞時(shí)的轉(zhuǎn)發(fā)過(guò)程

1.3 改進(jìn)協(xié)議的優(yōu)勢(shì)

改進(jìn)GPSR協(xié)議在貪婪轉(zhuǎn)發(fā)失敗時(shí)，選定最佳邊緣節(jié)點(diǎn)并等待某一極小的時(shí)間間隔Δt，可避免平面周邊轉(zhuǎn)發(fā)中的多跳問(wèn)題。對(duì)比圖1與圖2可知，相對(duì)于直接選取周邊轉(zhuǎn)發(fā)模式，改進(jìn)GPSR協(xié)議在S點(diǎn)明顯降低了路由跳數(shù)，從而相對(duì)提高協(xié)議的效率。

2 仿真分析

基于Ubuntu采用NS2.35作為仿真平臺(tái)，仿真區(qū)域?yàn)?70 m×670 m，傳輸范圍250 m，仿真時(shí)間為250 s，利用setdest工具生成四個(gè)速度不同的場(chǎng)景文件，分別包含最大移動(dòng)速度為10 m/s， 20 m/s， 30 m/s， 40 m/s的100個(gè)隨機(jī)節(jié)點(diǎn)的坐標(biāo)以及移動(dòng)信息。相關(guān)仿真參數(shù)如表1所示。

表1 主要的網(wǎng)絡(luò)仿真參數(shù)

使用NAM動(dòng)畫(huà)演示工具記錄仿真過(guò)程，動(dòng)畫(huà)截圖如圖3所示。

圖3 NAM動(dòng)畫(huà)演示

平均端到端時(shí)延[10]是網(wǎng)絡(luò)中所有數(shù)據(jù)包端到端時(shí)延的平均值，包括了數(shù)據(jù)包在傳輸過(guò)程中的所有時(shí)延。圖4顯示了節(jié)點(diǎn)移動(dòng)速度不斷增大，平均端到端時(shí)延的變化曲線,從中可見(jiàn)，隨著速度增大，GPSR協(xié)議以及改進(jìn)協(xié)議的時(shí)延逐漸增加，這是由于速度變快時(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化也會(huì)加速，而改進(jìn)協(xié)議能夠減少路由轉(zhuǎn)發(fā)的跳數(shù)，進(jìn)而減少節(jié)點(diǎn)間的傳輸時(shí)間和排隊(duì)時(shí)間，相比原協(xié)議的端到端時(shí)延減小。

圖4 平均端到端時(shí)延對(duì)比

數(shù)據(jù)分組從源節(jié)點(diǎn)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)所經(jīng)歷的平均跳數(shù),可以表示為發(fā)送數(shù)據(jù)包與轉(zhuǎn)發(fā)數(shù)據(jù)包之和除以發(fā)送數(shù)據(jù)包的個(gè)數(shù)。原GPSR協(xié)議和改進(jìn)協(xié)議在不同速度轉(zhuǎn)發(fā)過(guò)程中的路由平均跳數(shù)變化情況如圖5所示，從中可見(jiàn)，改進(jìn)協(xié)議可以適當(dāng)?shù)亟档推骄鴶?shù)。

圖5 不同速度下的跳數(shù)對(duì)比

3 結(jié)束語(yǔ)

針對(duì)GPSR協(xié)議中周邊轉(zhuǎn)發(fā)模式產(chǎn)生過(guò)多冗余的問(wèn)題，通過(guò)在報(bào)頭中加入鄰節(jié)點(diǎn)的移動(dòng)速度和方向信息，并引入一種“等待轉(zhuǎn)發(fā)模式”，從而給出改進(jìn)策略，使其在遭遇路由空洞時(shí)可以減少原協(xié)議的路由跳躍次數(shù)。借助NS2仿真驗(yàn)證，結(jié)果顯示，改進(jìn)協(xié)議還能夠降低平均時(shí)延。

[1] 黃喬永. 基于移動(dòng)模型的Ad Hoc路由協(xié)議仿真研究[D].昆明：昆明理工大學(xué)，2012:2-14.

[2] 林彥汝. 一種基于地理位置的Ad Hoc路由協(xié)議[D].廣州：暨南大學(xué)，2010:5-7.[3] 唐國(guó)明，謝羿，唐九陽(yáng). 一種基于左、右手法則的GPSR分區(qū)邊界轉(zhuǎn)發(fā)路由協(xié)議[J]. 計(jì)算機(jī)應(yīng)用研究，2011(3)：1099-1101.

[4] 王志剛. 車(chē)載Ad hoc網(wǎng)絡(luò)中基于車(chē)輛流密度的GPSR協(xié)議的改進(jìn)研究[D].長(zhǎng)春：吉林大學(xué)，2012:13-16.

[5] 張鵬明，李洪烈，林成浴. 基于地理定位信息的移動(dòng)自組網(wǎng)路由協(xié)議綜述[J].電訊技術(shù)，2012，52(9):3-7.

[6] 吳三斌，王小明，楊濤，等. 改進(jìn)的GPSR模型及其仿真分析[J]. 計(jì)算機(jī)工程與應(yīng)用，2011(1)：100-104.

[7] 彭好佑. 車(chē)載自組織網(wǎng)絡(luò)GPSR路由協(xié)議研究及算法改進(jìn)[D].?？冢汉Ｄ洗髮W(xué)，2013:4-20.

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

[9] Shu Wenjie, Wang Ping, Guo Aihuang, et. al. Enhanced GPSR using neighbor-awareness position update and beacon-assist geographic for-warding in vehicular ad hoc networks[C]//Proceedings of the 2007 IEEE International Conference on Inetlligent Vehicles Symposium. Xi’an: IEEE, 2009: 1143-1147.

[10]雷文君. 基于時(shí)分同步碼多址的無(wú)線數(shù)據(jù)傳輸方案[J].西安郵電學(xué)院學(xué)報(bào)，2012，17(6):9-10.

[責(zé)任編輯:瑞金]

An improved greedy perimeter stateless routing protocol

ZHANG Jirong1, ZHAO Xiaotong1, QU Junsuo1, CUI Yan2

(1. School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China; 2.Research and Development Center, The 4th Research Institute ofTelecommunications Science and Technology, Xi’an 710061, China)

An improvement to the greedy perimeter stateless routing protocol is proposed by adding the moving speed and direction of adjacent node to the header. According to the added information, the next location of an adjacent node can be predicted, as the forwarded node is suffering routing empty. If the predicted position does not match with the requirement of a greedy forwarding, it goes on with the perimeter forwarding mode, otherwise, it goes into a waiting mode, which means, after a minimal waiting time delay, it jumps back to the greedy forwarding mode, thus a large amount of redundancy in perimeter forwarding can be reduced. With simulation software Network Simulator version 2, a network environment is set up, in which, the end-to-end delay and the average hop count of the improved protocol and the original protocol is compared as the node speed varies in 10 ～ 40 m/s. Results show that, the improving methods can bring an reduce to the time delay of 5% ～ 17%, and to the hop of 5% around.

routing empty, greedy perimeter stateless routing protocol, Network Simulator

10.13682/j.issn.2095-6533.2015.04.003

2015-01-04

陜西省科技廳科學(xué)技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2012K06-50)

張繼榮(1963-)，女，博士，教授，從事現(xiàn)代通信網(wǎng)研究。E-mail:comnet@xupt.edu.cn 趙曉彤(1990-)，女，碩士研究生，研究方向?yàn)橥ㄐ啪W(wǎng)技術(shù)與應(yīng)用。E-mail:306967739@qq.com

TP393

A

2095-6533(2015)04-0016-04