移動(dòng)自組織網(wǎng)絡(luò)中基于位置預(yù)測(cè)的貪心周界無(wú)狀態(tài)路由改進(jìn)算法

白曉萌 楊釋心 李東

摘 要： 針對(duì)移動(dòng)自組織網(wǎng)絡(luò)的工作機(jī)理、通信方式和應(yīng)用，分析了基于地理位置的貪心周界無(wú)狀態(tài)路由（GPSR）算法的路由協(xié)議.節(jié)點(diǎn)相對(duì)速度過(guò)快時(shí)，GPSR通信性能不穩(wěn)定.考慮在原有協(xié)議的基礎(chǔ)上，修改并實(shí)現(xiàn)了改進(jìn)的貪心周界無(wú)狀態(tài)路由（IGPSR）算法.IGPSR協(xié)議考慮了源節(jié)點(diǎn)、目的節(jié)點(diǎn)、備選中繼節(jié)點(diǎn)的速度和方向，根據(jù)節(jié)點(diǎn)的當(dāng)前速度，計(jì)算之后某一時(shí)間內(nèi)節(jié)點(diǎn)的位置，以此確定最佳中繼節(jié)點(diǎn).仿真結(jié)果表明：當(dāng)節(jié)點(diǎn)高速移動(dòng)時(shí)，IGPSR協(xié)議比GPSR協(xié)議具有更低的丟包率.

關(guān)鍵詞： 移動(dòng)自組織網(wǎng)絡(luò); 貪心周界無(wú)狀態(tài)路由（GPSR）算法; 改進(jìn)的貪心周界無(wú)狀態(tài)路由（IGPSR）算法

中圖分類號(hào)： TN 929.52文獻(xiàn)標(biāo)志碼： A文章編號(hào)： 1000-5137（2019）01-0070-05

Abstract： This paper elaborated the working mechanism，communication mode and application of mobile ad hoc network.Besides，it analyzed the greedy perimeter stateless routing （GPSR） protocol based on geographic location.For the reason that the GPSR protocol may result in a higher packet loss rate because of high relative speed，this paper modified and implemented the improved greedy perimeter stateless routing （IGPSR） algorithm which took into account the speed and direction of the source nodes，destination nodes，and alternative relay nodes.The position of the node could be calculated and predicted with the current speed of the node，thus the best relay node was identified.Simulation experiments showed that the IGPSR routing protocol had a lower packet loss rate than the GPSR routing protocol when nodes moving at high speed.

Key words： mobile ad hoc network; greedy perimeter stateless routing （GPSR） algorithm; improved greedy perimeter stateless routing （IGPSR） algorithm

0 引 言

貪心周界無(wú)狀態(tài)路由（GPSR）算法是基于地理位置信息實(shí)現(xiàn)路由的一種協(xié)議.當(dāng)節(jié)點(diǎn)需要向節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組時(shí)，選擇一個(gè)最鄰近的節(jié)點(diǎn)作為數(shù)據(jù)分組的下一跳目標(biāo)，并傳送數(shù)據(jù).該過(guò)程不斷重復(fù)直到數(shù)據(jù)分組到達(dá)目的節(jié)點(diǎn)[1-2].

LI等[3]為保證GPSR路由協(xié)議建立的鏈路穩(wěn)定性，提出了一種結(jié)合節(jié)點(diǎn)關(guān)聯(lián)強(qiáng)度預(yù)測(cè)和GPSR-R的混合路由協(xié)議.CLAUSEN等[4]分析了傳統(tǒng)GPSR協(xié)議在城市交通條件下存在的缺陷，針對(duì)其鏈路質(zhì)量低、投遞率受速度影響大、低節(jié)點(diǎn)密度適應(yīng)性差等問(wèn)題，在GPSR協(xié)議的基礎(chǔ)上提出了一種改進(jìn)路由協(xié)議.

上述研究都未考慮因節(jié)點(diǎn)的高速運(yùn)動(dòng)而導(dǎo)致其實(shí)際地理位置與所記錄位置的偏差問(wèn)題，節(jié)點(diǎn)間鏈路持續(xù)時(shí)間較短、易毀，會(huì)導(dǎo)致信息的傳輸成功率下降.針對(duì)這一問(wèn)題，本文作者提出了改進(jìn)的貪心周界無(wú)狀態(tài)路由（IGPSR）算法，該算法考慮了源節(jié)點(diǎn)、目的節(jié)點(diǎn)、備選中繼節(jié)點(diǎn)的速度和方向等因素，并根據(jù)節(jié)點(diǎn)的當(dāng)前速度計(jì)算之后某一時(shí)間內(nèi)節(jié)點(diǎn)的位置，并據(jù)此選擇最佳中繼節(jié)點(diǎn).

2 IGPSR算法

考慮加入速度參數(shù)作為選擇下一跳的另一指標(biāo)，并且調(diào)節(jié)位置參數(shù)與速度參數(shù)的權(quán)重，以適應(yīng)不同節(jié)點(diǎn)密度下的路由轉(zhuǎn)發(fā)情況.原GPSR協(xié)議中的報(bào)文包含節(jié)點(diǎn)IP地址和地理位置信息，在IGPSR協(xié)議中，則需額外添加節(jié)點(diǎn)的運(yùn)動(dòng)速度信息.

節(jié)點(diǎn)的運(yùn)動(dòng)速度信息是一個(gè)二維向量，假定節(jié)點(diǎn)只在x和y方向上有速度.IGPSR依然采取原協(xié)議中的beacon算法，周期性地更新各個(gè)節(jié)點(diǎn)的IP地址、位置信息和節(jié)點(diǎn)的速度信息，并根據(jù)這些信息維護(hù)鄰居節(jié)點(diǎn)列表.計(jì)算源節(jié)點(diǎn)、目的節(jié)點(diǎn)、可選中繼節(jié)點(diǎn)的加權(quán)位置，并選取鄰居節(jié)點(diǎn)中加權(quán)距離最小的節(jié)點(diǎn)作為中繼節(jié)點(diǎn).

3 仿真結(jié)果

為了探究IGPSR路由協(xié)議的性能，在公路場(chǎng)景下對(duì)比IGPSR和GPSR路由協(xié)議的傳輸成功率Packet Deliver Ratio（PDR）和時(shí)延.使用Network Simulation 3軟件作為仿真平臺(tái)，Mac層選擇802.11作為接入?yún)f(xié)議，節(jié)點(diǎn)間最大傳輸距離設(shè)置為250 m，業(yè)務(wù)數(shù)據(jù)包的發(fā)送頻率為1個(gè)·s-1.

分源節(jié)點(diǎn)和目的節(jié)點(diǎn)同向運(yùn)動(dòng)及反向運(yùn)動(dòng)兩種情況進(jìn)行仿真，并計(jì)算兩種路由協(xié)議下的傳輸成功率（PDR）和時(shí)延.

同向運(yùn)動(dòng)時(shí)，構(gòu)建直線雙向模型，模型中包含50個(gè)節(jié)點(diǎn)，平均節(jié)點(diǎn)密度為10節(jié)點(diǎn)·km-1，節(jié)點(diǎn)速度分別為20，30，40，50，60，70，80 km·h-1，節(jié)點(diǎn)初始位置在一定范圍內(nèi)隨機(jī)放置.引入隨機(jī)速度，使仿真更加接近真實(shí)節(jié)點(diǎn)的運(yùn)動(dòng)狀態(tài).隨機(jī)地從節(jié)點(diǎn)中選取15對(duì)節(jié)點(diǎn)作為源節(jié)點(diǎn)和目的節(jié)點(diǎn)，并發(fā)送250個(gè)數(shù)據(jù)包測(cè)試它們之間的PDR和時(shí)延.

4 結(jié) 論

在高度動(dòng)態(tài)的自組織網(wǎng)絡(luò)中，傳統(tǒng)的GPSR協(xié)議由于節(jié)點(diǎn)的實(shí)際位置與beacon中的位置信息有較大差距，導(dǎo)致信息的傳輸成功率較低，當(dāng)節(jié)點(diǎn)運(yùn)動(dòng)速度變大時(shí)，尤為明顯.本文作者提出的基于節(jié)點(diǎn)運(yùn)動(dòng)方向與速度的IGPSR算法，能夠通過(guò)對(duì)節(jié)點(diǎn)的當(dāng)前位置做出預(yù)測(cè)，從而提高信息的傳輸成功率.對(duì)于高速移動(dòng)的自組織網(wǎng)絡(luò)，本算法在提高信息傳輸成功率方面的工作具有顯著成效.

參考文獻(xiàn)：

[1] 倪紅彪，李卓.基于節(jié)點(diǎn)關(guān)聯(lián)強(qiáng)度預(yù)測(cè)和GPSR-R的混合路由算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2018，39（10）：3024-3028，3038.

NI H B，LI Z.Hybrid routing protocol combined with node correlation strength prediction and GPSR-R[J].Computer Engineering and Design，2018，39（10）：3024-3028，3038.

[2] 高田翔，石英，劉子偉，等.城市VANET中基于路網(wǎng)和QoS模型的GPSR協(xié)議改進(jìn)方法[J/OL].計(jì)算機(jī)工程，2018[2018-03-13].https：//doi.org/10.19678/j.issn.1000-3428.0049361.

GAO T X，SHI Y，LIU Z W，et al.Improvement of GPRS protocol based on road network and QoS models for urban VANET[J].Computer Engineering，2018[2018-03-13].https：//doi.org/10.19678/j.issn.1000-3428.0049361.

[3] LI K，F(xiàn)OY E，F(xiàn)ERREON J C，et al.Immune evasion by hepatitis C virus NS3/4A protease-mediated cleavage of the Toll-like receptor 3 adaptor protein TRIF[J].Proceedings of the National Academy of Sciences，2005，102（8）：2992-2997.

[4] CLAUSEN T，JACQUET P.Optimized link state routing protocol （OLSR）[R].Paris：INRIA，2003.

（責(zé)任編輯：馮珍珍，包震宇）