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

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

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

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

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

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

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

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

貪婪型周邊無狀態(tài)路由協(xié)議(Greedy Perimeter Stateless Routing, GPSR)[1]是移動自組網(wǎng)中一種常用路由協(xié)議，它通過預(yù)先獲取位置信息，利用源節(jié)點(diǎn)和目的節(jié)點(diǎn)的位置來制定數(shù)據(jù)包轉(zhuǎn)發(fā)策略，其具體轉(zhuǎn)發(fā)過程包括兩種模式[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ā)分組時，會繼續(xù)采用同樣的方法進(jìn)行轉(zhuǎn)發(fā)，最終被傳至目的節(jié)點(diǎn)。貪婪轉(zhuǎn)發(fā)的缺點(diǎn)是路由空洞問題[3]。當(dāng)遭遇路由空洞時，則會轉(zhuǎn)入周邊轉(zhuǎn)發(fā)模式，順著路由空洞的周邊通過右手定則尋找新的路由。當(dāng)貪婪轉(zhuǎn)發(fā)條件再次滿足時，可以自動轉(zhuǎn)回貪婪模式，直到數(shù)據(jù)分組發(fā)送到目的節(jié)點(diǎn)[4]。

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

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

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

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

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

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

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

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

(2) 考慮到MANET網(wǎng)絡(luò)的隨機(jī)移動性，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是隨時間不斷變化的，給出一種“等待轉(zhuǎn)發(fā)模式”。節(jié)點(diǎn)S在轉(zhuǎn)發(fā)過程中遭遇路由空洞時，對鄰居表進(jìn)行維護(hù)，獲取其他節(jié)點(diǎn)的速度和方向，對節(jié)點(diǎn)的移動位置進(jìn)行預(yù)測，并預(yù)測節(jié)點(diǎn)鄰居關(guān)系的變化，選取在下一時刻能夠跳入自己轉(zhuǎn)發(fā)范圍且在目的節(jié)點(diǎn)方向上的點(diǎn)，作為最佳邊緣節(jié)點(diǎn)。如果存在這樣的最佳邊緣節(jié)點(diǎn)，則等待一個最小時間間隔Δt，在下一時刻最佳邊緣節(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ā)過程如圖2所示。源節(jié)點(diǎn)S的邊緣節(jié)點(diǎn)Q和M在下一時刻跳入S的轉(zhuǎn)發(fā)范圍之內(nèi)，且Q即為最佳邊緣節(jié)點(diǎn)，下一時刻新增點(diǎn)Q′和點(diǎn)M′，此刻S不再是最佳主機(jī)，則可以繼續(xù)采用貪婪策略進(jìn)行轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)過程為S→Q′→D，最終到達(dá)目的節(jié)點(diǎn)D。

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

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

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

2 仿真分析

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

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

使用NAM動畫演示工具記錄仿真過程，動畫截圖如圖3所示。

圖3 NAM動畫演示

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

圖4 平均端到端時延對比

數(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ù)包的個數(shù)。原GPSR協(xié)議和改進(jìn)協(xié)議在不同速度轉(zhuǎn)發(fā)過程中的路由平均跳數(shù)變化情況如圖5所示，從中可見，改進(jìn)協(xié)議可以適當(dāng)?shù)亟档推骄鴶?shù)。

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

3 結(jié)束語

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

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

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

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

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

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

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

[8] 于耕，孫翔，李洪烈，等. 基于機(jī)會轉(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ù)據(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