袁學(xué)松，袁　濤，王　蒙，張　靜

(1.安徽機(jī)電職業(yè)技術(shù)學(xué)院 信息工程系，安徽 蕪湖 241000；2.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009)

?

一種可靠的GPSR改進(jìn)算法在內(nèi)河航道中的應(yīng)用研究

袁學(xué)松1,2，袁濤1，王蒙1，張靜1

(1.安徽機(jī)電職業(yè)技術(shù)學(xué)院 信息工程系，安徽 蕪湖 241000；2.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009)

摘要：內(nèi)河航道船舶之間采用高頻、甚高頻等方式進(jìn)行信息交換，存在著干擾嚴(yán)重、成本昂貴等問題，為改善并豐富內(nèi)河航道的通信模式，將城市交通中應(yīng)用較為成熟的車載自組網(wǎng)(Vanet)技術(shù)引入到航道通信中，建立了可靠的端到端的船舶通信方式。針對傳統(tǒng)的Vanet中GPSR(GreedyPerimeterStatelessRouting)路由協(xié)議相關(guān)算法易形成“空洞”、節(jié)點(diǎn)傳輸不可靠的缺點(diǎn)，提出了改進(jìn)算法GPSR-CH(GPSRforChannel)。該算法通過增加可靠航標(biāo)節(jié)點(diǎn)、改進(jìn)Hello包結(jié)構(gòu)、預(yù)測船舶的運(yùn)動軌跡等方案大大增強(qiáng)了傳輸?shù)目煽啃?。在?nèi)河航道模型環(huán)境下的仿真結(jié)果表明，GPSR-CH比經(jīng)典的GPSR及其他幾種改進(jìn)算法有更低的分組丟包率和傳輸時延。

關(guān)鍵詞：航道通信;Vanet；GPSR；GPSR-CH；航標(biāo)節(jié)點(diǎn)

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.017

近年來，內(nèi)河航道事故頻發(fā)，有的是因?yàn)樾》秶臉O端天氣(如2015年的“東方之星號”事件)，有的是因?yàn)榇安皇煜に那闆r而導(dǎo)致的船只相撞事故，這些事故如果能早期預(yù)警并干預(yù)是完全可以避免的。隨著“車聯(lián)網(wǎng)”技術(shù)的日趨成熟，設(shè)想若將車載自組網(wǎng)(Vanet)[1]中GPSR(GreedyPerimeterStatelessRouting)[2]的路由算法應(yīng)用到船舶預(yù)警和船舶通信管理上并加以改進(jìn)，必將豐富船載設(shè)備單一的通信模式，提高船舶的通信效率。目前，基于GPSR的改進(jìn)協(xié)議已有不少，如GPSR-AD(GPSRBasedonAngleandDistance)[3]從節(jié)點(diǎn)的運(yùn)動軌跡和相對運(yùn)動角度來考慮如何選擇下一跳節(jié)點(diǎn)并維護(hù)鄰居節(jié)點(diǎn)信息，在多節(jié)點(diǎn)復(fù)雜拓?fù)洵h(huán)境中能有效解決“空洞”問題；NGPSR(NewGPSR)[4]協(xié)議在處理多障礙物對數(shù)據(jù)包傳輸?shù)挠绊懮弦脖冉?jīng)典的GPSR協(xié)議有更高的分組到達(dá)率；GPSRIP(GPSRImproveProtocol)[5]協(xié)議可以根據(jù)節(jié)點(diǎn)自身的運(yùn)動規(guī)律和相關(guān)自身特征增加下一跳的位置預(yù)測，從而減少路由的開銷，降低了節(jié)點(diǎn)間傳輸時延；GPSR-PV(GPSRBasedonPositionVector)[6]協(xié)議通過冗余鏈路撤銷方案來縮小目的節(jié)點(diǎn)的選擇范圍，該算法能有效提高鏈路質(zhì)量。本文針對內(nèi)河航道問題，提出一種新的改進(jìn)算法GPSR-CH(GPSRforChannel)，并做了傳真實(shí)驗(yàn)。

1內(nèi)河航道的相關(guān)問題描述

內(nèi)河航道較城市路面有很多不同之處。例如，航道不存在城市路面的十字路口、城市建筑物障礙、紅綠燈交通規(guī)則等問題，但航道中存在不同于城市路面相關(guān)航行的規(guī)則。本文針對航道的相關(guān)地理特性提出以下兩個設(shè)計(jì)要點(diǎn)：

(1)船舶的路由節(jié)點(diǎn)丟失問題

當(dāng)航行中的節(jié)點(diǎn)A要發(fā)送數(shù)據(jù)包時，首先會查找自己的路由表，得到離自己最近的下一跳節(jié)點(diǎn)B。如果該節(jié)點(diǎn)在船舶節(jié)點(diǎn)A通信的邊緣地帶且高速運(yùn)動，則當(dāng)A傳給B時，B已經(jīng)不在A的傳輸范圍內(nèi)了，這種情況就會導(dǎo)致鏈路斷開問題。在GPSR或其他的改進(jìn)算法中會使用周邊轉(zhuǎn)發(fā)的方法進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，但是在特殊的航道上有時可能沒有其他的節(jié)點(diǎn)傳輸，這樣就會導(dǎo)致A在一定時間內(nèi)無法傳輸信息。

(2)航道模型下地理障礙問題

在內(nèi)河中有很多特殊的航道，比如超過50°彎的航道、超寬航道、有江心洲的航道等，這些航道需要按照特殊的地理?xiàng)l件設(shè)置障礙物，在仿真過程中障礙物的正確設(shè)置與否直接影響仿真網(wǎng)絡(luò)性能的準(zhǔn)確性。圖1是針對內(nèi)河實(shí)際航道環(huán)境對GPSR、GPSR-AD等算法進(jìn)行仿真實(shí)驗(yàn)的結(jié)果。

圖1　3種算法在內(nèi)河航道環(huán)境下的分組到達(dá)率

仿真結(jié)果表明，經(jīng)典算法在內(nèi)河航道中分組送達(dá)率較低，該指標(biāo)反映數(shù)據(jù)包傳輸?shù)目煽啃裕?dāng)節(jié)點(diǎn)數(shù)增加時，分組送達(dá)率下降非常明顯。針對以上問題，本文提出一種新的改進(jìn)GPSR算法。

2一種可靠的路由算法

GPSR-CH算法是改進(jìn)的GPSR算法，它通過增加固定航標(biāo)節(jié)點(diǎn)，修改節(jié)點(diǎn)間傳輸信標(biāo)報(bào)文來維護(hù)航道中各船舶節(jié)點(diǎn)的鄰居關(guān)系表，并使用經(jīng)典貪婪轉(zhuǎn)發(fā)算法建立路由，來創(chuàng)建一個可靠的傳輸過程。該算法的關(guān)鍵問題和算法實(shí)現(xiàn)如下。

2.1船舶節(jié)點(diǎn)和航標(biāo)節(jié)點(diǎn)的信標(biāo)設(shè)計(jì)

在GPSR協(xié)議中，通信節(jié)點(diǎn)需周期性地交流信標(biāo)報(bào)文，通知鄰居節(jié)點(diǎn)自身的信息。但標(biāo)準(zhǔn)的GPSR信標(biāo)報(bào)文只包含各個節(jié)點(diǎn)的IP地址和由外部設(shè)備得到的地理位置信息,很顯然這并不能滿足船舶通信的需求。在GPSR-CH協(xié)議中將信標(biāo)報(bào)文分成兩類。

(1)固定航標(biāo)節(jié)點(diǎn)報(bào)文

該節(jié)點(diǎn)需周期性向周圍的區(qū)域船舶廣播，由相關(guān)傳感器獲得水流速度、風(fēng)速及相關(guān)信息。圖2為航標(biāo)節(jié)點(diǎn)的信標(biāo)報(bào)文格式，該格式中的節(jié)點(diǎn)IP和節(jié)點(diǎn)位置均為固定值，由傳感器得到的流速和風(fēng)速均為矢量值，不僅有大小，還有速度的偏向角θ。

圖2航標(biāo)節(jié)點(diǎn)信標(biāo)格式

(2)船舶節(jié)點(diǎn)信標(biāo)報(bào)文

圖3為船舶節(jié)點(diǎn)的信標(biāo)報(bào)文格式。由于要預(yù)測在生存周期中的鄰居節(jié)點(diǎn)，故在信標(biāo)中添加了由自身得到的矢量速度。同時，由于可能出現(xiàn)的節(jié)點(diǎn)故障，將節(jié)點(diǎn)健康狀況加入到報(bào)文中。在算法中要規(guī)避船舶相撞，故在信標(biāo)報(bào)文中添加了節(jié)點(diǎn)安全距離的標(biāo)識，船舶節(jié)點(diǎn)的安全距離為該船舶全長的一半，在每個節(jié)點(diǎn)中該值為固定值。

圖3船舶節(jié)點(diǎn)信標(biāo)格式

2.2船舶的鄰居關(guān)系相關(guān)預(yù)測方法

在GPSR協(xié)議中，如果要防止由于節(jié)點(diǎn)(船舶)運(yùn)動而產(chǎn)生的“空洞”現(xiàn)象，只能根據(jù)實(shí)際拓?fù)洵h(huán)境預(yù)測各節(jié)點(diǎn)的相對移動位置(雖然北斗系統(tǒng)由惡劣天氣引起的信號衰減非常小，適用于內(nèi)河航道系統(tǒng)，但北斗系統(tǒng)的二維水平精度為100 m,對于長江內(nèi)河航道而言100 m誤差不足以避免船舶相撞)。本文使用船載北斗系統(tǒng)獲取其大致的經(jīng)度、緯度和矢量速度等參數(shù)。同時，航標(biāo)節(jié)點(diǎn)通過自身傳感器獲取矢量風(fēng)速、矢量水流速度等參數(shù)廣播給區(qū)域內(nèi)的各船舶，船舶節(jié)點(diǎn)根據(jù)該信息結(jié)合自身的運(yùn)動參數(shù)，對船舶移動性進(jìn)行預(yù)測估算，并維護(hù)鄰居節(jié)點(diǎn)，從而很好地維護(hù)各船舶節(jié)點(diǎn)的通信關(guān)系。

圖4　船舶鄰居關(guān)系預(yù)測

若L′R，說明Δt時刻后互為無效節(jié)點(diǎn)，則在維護(hù)彼此路由時，刪除該鄰居節(jié)點(diǎn)。當(dāng)經(jīng)過Δt時間后，L′

2.3GPSR-CH算法

GRSR-CH算法是根據(jù)移動船舶節(jié)點(diǎn)和固定航標(biāo)節(jié)點(diǎn)來保持鄰居關(guān)系的完整性，不會因?yàn)楣?jié)點(diǎn)數(shù)目過少而產(chǎn)生斷路，也不會因?yàn)楣?jié)點(diǎn)運(yùn)動速度過快而產(chǎn)生“空洞”。圖5和圖6分別為船舶節(jié)點(diǎn)和航標(biāo)節(jié)點(diǎn)的數(shù)據(jù)包轉(zhuǎn)發(fā)方案和鄰居節(jié)點(diǎn)的維護(hù)方案。

圖5 船舶節(jié)點(diǎn)轉(zhuǎn)發(fā)方法圖6 航標(biāo)節(jié)點(diǎn)轉(zhuǎn)發(fā)方法

算法具體可描述為

(1)船舶節(jié)點(diǎn)根據(jù)周期性廣播Hello包來維護(hù)鄰居節(jié)點(diǎn)，同時，發(fā)現(xiàn)鄰居航標(biāo)S并記錄在路由表中。若目的節(jié)點(diǎn)在鄰居表中，則進(jìn)行相關(guān)數(shù)據(jù)包的轉(zhuǎn)發(fā)。若目的節(jié)點(diǎn)不在鄰居中則進(jìn)行(2)操作；

(2)使用貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)策略對數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)操作，并且每個節(jié)點(diǎn)都通過鄰居表信息管理來維護(hù)自身鄰居表，直至發(fā)送成功。若無鄰居節(jié)點(diǎn)或經(jīng)過預(yù)測鄰居節(jié)點(diǎn)均為無效節(jié)點(diǎn)則進(jìn)入(3)；

(3)傳輸給相應(yīng)的鄰居航標(biāo)S,同時顯示數(shù)據(jù)轉(zhuǎn)發(fā)成功；

(i)航標(biāo)S在收到源節(jié)點(diǎn)的信息后存儲到閃存中，并尋找目的節(jié)點(diǎn)是否在自身的服務(wù)范圍內(nèi)，若在則直接轉(zhuǎn)發(fā)，并回復(fù)源節(jié)點(diǎn)ACK信息。若不在自身的服務(wù)范圍內(nèi)則轉(zhuǎn)至(ii)；

(ii)組播到拓?fù)渲邢鄳?yīng)的航標(biāo)Sn,Sn-1,Sn+1,…。各航標(biāo)通過方法(i)尋找目的節(jié)點(diǎn)并傳輸，并回復(fù)源節(jié)點(diǎn)ACK信息，傳輸結(jié)束。

3仿真實(shí)驗(yàn)分析

為驗(yàn)證本文提出的GPSR改進(jìn)算法的有效性，現(xiàn)通過NS-2仿真軟件分析該算法的各種性能。為了更真實(shí)地反映航道情景，算法采用MOVE[8](Mobility Model Generator for Vehicular Networks)軟件構(gòu)建真實(shí)航道場景。

3.1船舶運(yùn)動模型與航道模型的構(gòu)建

在一般的航道上，船舶都不會過分集中運(yùn)動在邊界上，在考慮多種運(yùn)動模型后，根據(jù)船舶的運(yùn)動特點(diǎn)選擇了高斯-馬爾科夫移動模型[9]。各船舶節(jié)點(diǎn)運(yùn)行均受到航道的制約，各節(jié)點(diǎn)的運(yùn)動軌跡均不可逾越相應(yīng)的航道，同時節(jié)點(diǎn)的信號傳輸也會遇到許多障礙物的影響。在圖7中，由于航道的彎曲雖然船舶可能均在有效的通信范圍內(nèi)，但信號的傳輸受到了航道彎曲的影響，導(dǎo)致通信中斷。本算法認(rèn)為河道的彎曲和障礙物可以完全阻斷信號傳輸，故航道模型采用了OM(Obstacle Mobility)[10]模型。

圖7仿真場景局部圖

本次仿真以真實(shí)的長江航道為依據(jù)，同時使用節(jié)點(diǎn)運(yùn)動模擬器SUMO(Simulation of Urban Mobility)[11]仿真運(yùn)動船舶節(jié)點(diǎn)。仿真場景為長10 km、寬2 km左右的彎曲河道，節(jié)點(diǎn)的傳輸范圍為250 m，船舶航行速度范圍為18.52-27.78 km/h，上下行航道均約為500 m，航標(biāo)按照航道實(shí)際設(shè)計(jì)，約500 m設(shè)置1個，分組長度為512 B，流量類型為CBR，仿真時間為600 s，節(jié)點(diǎn)數(shù)由10-200逐漸增加。

3.2仿真結(jié)果與分析

本次實(shí)驗(yàn)主要從分組送達(dá)率、路由開銷以及平均端到端延時等3個方面對GPSR-CH與GPSR、GPSR-AD以及NGPSR算法的性能進(jìn)行比較，并分析這4個算法在內(nèi)河航道真實(shí)場景中的性能，如圖8-10所示。

圖8　節(jié)點(diǎn)端到端平均延時

圖9　節(jié)點(diǎn)的分組到達(dá)率

圖10　節(jié)點(diǎn)的路由開銷

由圖8可知，當(dāng)內(nèi)河航道的船舶數(shù)量增加時，GPSR-CH、GPSR、GPSR-AD和NGPSR算法端到端的平均傳輸延時均有所增加。GPSR-CH算法由于增加了固定式航標(biāo)節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)增加時該性能指標(biāo)優(yōu)于其他算法。由圖9可知，GPSR-CH算法的分組送達(dá)率在節(jié)點(diǎn)數(shù)增加時，始終保持在一個比較穩(wěn)定的狀態(tài)，而其他算法當(dāng)節(jié)點(diǎn)增加可能會導(dǎo)致不可靠傳輸。由圖10可知，隨著船舶節(jié)點(diǎn)的增加，GPSR-CH算法的路由開銷較大，這是由于為增加傳輸可靠性增加了很多冗余的航標(biāo)節(jié)點(diǎn)。同時，在算法中加長了各類信標(biāo)報(bào)文也會加重網(wǎng)絡(luò)負(fù)擔(dān)。但總體來看，隨著節(jié)點(diǎn)增加，GPSR-CH的路由開銷和經(jīng)典GPSR算法相當(dāng)，仍處于可控狀態(tài)，但傳輸時延和丟包率大大減小。

4結(jié)束語

本文將GPRS改進(jìn)協(xié)議應(yīng)用在內(nèi)河航道的船舶通信領(lǐng)域中，提出了一種新的GPSR-CH算法，該算法可以很好地保證數(shù)據(jù)的送達(dá)率，但由于增加了廣播包并加長了與鄰居節(jié)點(diǎn)通信的信標(biāo)報(bào)文，路由開銷性能與GPSR相當(dāng)。仿真實(shí)驗(yàn)證明，GPSR-CH算法較其他類似算法更適合于內(nèi)河航道的可靠數(shù)據(jù)傳輸，在現(xiàn)實(shí)的內(nèi)河航道中有較大的應(yīng)用價(jià)值。

參考文獻(xiàn):

[1] Liu Haiqing,Yang Licai,Ding Sijing,et al.Logical connectivity prediction models for VANET based on nonlinear regression and ELM: An example of the AODV protocol[J]. International Journal of Future Generation Communication and Networking, 2014, 17(6):.217-230.

[2] Karp B,Kung H T.GPSR: Greedy perimeter stateless routing wireless networks[C].ACM/IEEE International Conference on Mobile Computing and Networking, Boston Massachusetts USA, 2000 : 243-254.

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

[4] 張好. 動態(tài)車載自組網(wǎng)密鑰管理方案的研究與仿真[D]. 北京: 北京郵電大學(xué), 2014.

[5] 包偉陽. 基于地理位置的車載網(wǎng)絡(luò)路由協(xié)議的研究[D]. 杭州: 杭州電子科技大學(xué), 2012.

[6] 吳晶, 吳怡.基于位置矢量的GPSR改進(jìn)協(xié)議[J]. 計(jì)算機(jī)應(yīng)用, 2012,32(S2):.65 -67,72.

[7] 李超, 韓江洪, 魏振春, 等.VANET場景下的GPSR_R路由算法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 38(2): 181-185.

[8] Karnadi F K,Mo Z H,Lan K.Rapid generation of realistic mobility models for VANET[C]. Proc of IEEE Wireless Communications and Networking Conference 2007. Hong Kong, China,2007:2506-2511.

[9] Tolety V.Load reduction in ad hoc networks using mobile servers[D].Dept. of Mathematical and Computer Sciences，Colorado School of Mines,1999.

[10] Jardosh A,Belding-roger E M,Almeroth K C, et al.Towards realistic mobility models for mobile ad hoc networks[C]. MobiCom '03 Proceedings of the 9th annual international conference on Mobile computing and networking, ACM, NY, USA, 2003: 217-229.

[11] Smith D, Djahel S，Murphy J.A SUMO based evaluation of road incidents' impact on traffic congestion level in smart cities，Local Computer Networks Workshops (LCN Workshops)[C]. 2014 IEEE 39th Conference on Edmonton, AB, 2014：702-710.

StudyonApplicationofReliableGPSRRoutingAlgorithminInlandWaterway

YUANXue-song1,2，YUANTao1,WANGMeng1，ZHANGJing1

(1.DepartmentofInformationEngineering,AnhuiTechnicalCollegeofMechanicalandElectricalEngineering,Wuhu,Anhui241000,China；2.SchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei,Anhui230009,China)

Abstract:Inthepastresearch,theinlandnavigationshipreliesonsatellite,highfrequencybandandveryhighfrequencybandradiocommunicationfordatatransmission.Inordertoenrichthecommunicationmethods,weestablishareliableend-to-endcommunicationforinnerriverships.InthispaperweintroducethematureVanettechnologyincitytrafficadhocvehiclenetwork.WefocusedontheGPSRroutineprotocolalgorithmsinVanet.Thetraditionalalgorithmiseasytoformholeandthetransmissionnodesarenotrobust.TheproposedalgorithmGPSR-CHcanimprovethereliabilitybyaddingnavigationindicationnodes,improvedHellopackagestructure,andpredictionofshipmotiontracks.Simulationresultsshowthat,theproposedalgorithmhaslowerpackageerrorrateandlowertransmissiondelayscomparedwiththetraditionalGPSRalgorithmanditsvariantsininlandnavigationchannelenvironment.

Keywords:channelcommunication;vanet;GPSR;GPSR-CH;beaconnode

* 收稿日期：2016-01-19

基金項(xiàng)目：安徽省教育廳2016年度高校領(lǐng)軍人才引進(jìn)與培育計(jì)劃項(xiàng)目(gxfxZD2016324)和安徽省教育廳省級教學(xué)團(tuán)隊(duì)(2014jxtd99)。

作者簡介：袁學(xué)松，男，安徽蕪湖人，碩士，安徽機(jī)電職業(yè)技術(shù)學(xué)院信息工程系講師，研究方向?yàn)榫W(wǎng)絡(luò)仿真技術(shù)、無線傳感網(wǎng)、數(shù)據(jù)挖掘。E-mail: ahjdyxs@126.com

中圖分類號：TPT393

文獻(xiàn)標(biāo)識碼：A

文章編號：1007-4260(2016)02-0072-05

網(wǎng)絡(luò)出版時間：2016-06-08 12:57網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.017.html