一種基于地理信息的改進(jìn)GPSR算法

張馨心 石振剛

摘要：針對車載自組織網(wǎng)絡(luò)（VANET）中基于地理信息的GPSR協(xié)議在轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)通信鏈路不夠穩(wěn)定的問題文章，提出了一種改進(jìn)的路由算法——GPSR-S算法。該算法根據(jù)任一車輛節(jié)點(diǎn)在不同時(shí)刻的地理坐標(biāo)，分別計(jì)算出它們的運(yùn)行速度和運(yùn)動方向，再通過速度和方向計(jì)算節(jié)點(diǎn)間通信鏈路的維持時(shí)間，兼顧鏈路穩(wěn)定性和距離，選出可靠的下一跳。利用網(wǎng)絡(luò)仿真平臺NS-3對GPSR、GPSR-S進(jìn)行仿真，結(jié)果表明GPSR-S算法在數(shù)據(jù)包傳遞率、端到端時(shí)延方面的性能得到了提升，更適合在車載自組網(wǎng)中應(yīng)用。

關(guān)鍵詞：車載自組織網(wǎng)絡(luò)??路由算法??GPSR??數(shù)據(jù)包投遞率??端到端時(shí)延

中圖分類號：TN92?????????文獻(xiàn)標(biāo)識碼：A

An?Improved?GPSR?Algorithm?Based?on?Geographic?Information

ZHANG?Xinxin??SHI?Zhengang

（Shenyang?Ligong?University，?Shenyang，?Liaoning?Province，?110159?China）

Abstract：?This?paper?proposes?an?improved?routing?algorithm—the?GPSR-S?algorithm?aiming?at?the?problem?that?the?GPSR?protocol?based?on?geographic?information?in?vehicular?ad?hoc?networks?（VANET）?is?not?stable?enough?for?communication?links?when?forwarding?data?packets.?According?to?the?geographical?coordinates?of?any?vehicle?nodes?at?different?times，?the?algorithm?calculates?their?running?speed?and?movement?direction?respectively，?then?calculates?the?maintenance?time?of?the?communication?link?among?nodes?by?speed?and?direction，?taking?into?account?the?stability?and?distance?of?the?link，?and?selects?a?reliable?next?hop.?The?network?simulation?platform?NS-3?is?used?to?simulate?GPSR?and?GPSR-S，?and?the?results?show?that?the?performance?of?GPSR-S?algorithm?in?terms?of?packet?delivery?rate?and?end-to-end?delay?is?improved，?which?is?more?suitable?for?use?in?the?VANET.

Key?Words：?Vehicular?ad?hoc?network;?Routing?algorithm;?GPSR;?Packet?delivery?rate;?End-to-end?delay

隨著汽車數(shù)量增加，交通問題也日益嚴(yán)重，對人們的生活造成了影響。研究人員開發(fā)了智能交通系統(tǒng)（Intelligent?Transport?System，?ITS）[1]以保證道路的利用率。車載自組織網(wǎng)絡(luò)（Vehicular?Ad?Hoc?Networks，VANET）[2]作為ITS的重要部分，受到了廣泛關(guān)注。路由協(xié)議作為VANET中的重要一環(huán)，成為了研究的熱點(diǎn)。

針對GPSR協(xié)議應(yīng)用在車載自組網(wǎng)的不足之處，提出了改進(jìn)的GPSR-S算法。GPSR-S對下一跳節(jié)點(diǎn)的選擇進(jìn)行了改進(jìn)，綜合考慮鏈路質(zhì)量和距離兩個(gè)因素的影響選出穩(wěn)定的下一跳。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法，可以提高數(shù)據(jù)包投遞的成功率，減少傳輸時(shí)延。

1?GPSR算法

貪婪周邊無狀態(tài)路由協(xié)議（Greedy?Perimeter?Stateless?Routing，GPSR）[3]是典型的基于地理信息的路由協(xié)議。GPSR采用信標(biāo)機(jī)制[4]，該算法中的節(jié)點(diǎn)會定時(shí)發(fā)送含有節(jié)點(diǎn)編號和位置的hello消息，每個(gè)節(jié)點(diǎn)的位置都能被得知。GPSR算法共有兩種模式：貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)[5]。轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，GPSR首先調(diào)用貪婪轉(zhuǎn)發(fā)，如圖1（a）所示。圖中，實(shí)線圓表示最大通信范圍，黑色小圓表示節(jié)點(diǎn)。源節(jié)點(diǎn)S根據(jù)目的節(jié)點(diǎn)D的位置，選擇通信范圍內(nèi)離D最近的節(jié)點(diǎn)為下一跳，將數(shù)據(jù)包轉(zhuǎn)發(fā)給該節(jié)點(diǎn)。當(dāng)某個(gè)節(jié)點(diǎn)發(fā)現(xiàn)通信范圍內(nèi)沒有比自身離D更近的節(jié)點(diǎn)時(shí)就發(fā)生了局部最優(yōu)，貪婪轉(zhuǎn)發(fā)失敗，GPSR采用周邊轉(zhuǎn)發(fā)。發(fā)生局部最優(yōu)的區(qū)域稱為路由空洞[6]，這時(shí)GPSR算法通過右手定則[7]確定下一跳。GPSR的周邊轉(zhuǎn)發(fā)如圖1（b）所示，陰影部分表示路由空洞，S陷入局部最優(yōu)，通過右手定則確定傳輸路徑為S→A→B→C→D。

由于貪婪規(guī)則，所以貪婪轉(zhuǎn)發(fā)總是選取離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)為下一跳，這些節(jié)點(diǎn)通常處于轉(zhuǎn)發(fā)節(jié)點(diǎn)的通信邊緣處[8]。在VANET中，車輛高速移動，邊緣處的節(jié)點(diǎn)很容易駛出轉(zhuǎn)發(fā)節(jié)點(diǎn)的通信范圍，造成通信鏈路斷裂、數(shù)據(jù)轉(zhuǎn)發(fā)失敗。

2?改進(jìn)的GPSR算法

針對上述數(shù)據(jù)包轉(zhuǎn)發(fā)過程中存在鏈路不穩(wěn)定的問題，對其進(jìn)行改進(jìn)。改進(jìn)GPSR-S算法不僅采用貪婪方式，還對鏈路質(zhì)量加以考慮，選出穩(wěn)定的下一跳。

車載自組網(wǎng)中的車輛節(jié)點(diǎn)周期性地發(fā)送數(shù)據(jù)包，當(dāng)節(jié)點(diǎn)不間斷地收到來自同一節(jié)點(diǎn)的兩個(gè)或更多的數(shù)據(jù)包時(shí)，就可以計(jì)算出該發(fā)送節(jié)點(diǎn)的速度和角度，具體的計(jì)算公式如下。

式（1）、式（2）中，、分別為節(jié)點(diǎn)在上一時(shí)刻和當(dāng)前時(shí)刻的坐標(biāo)。

算法采用鏈路持續(xù)時(shí)間來衡量通信鏈路的質(zhì)量，鏈路持續(xù)時(shí)間越長則代表鏈路質(zhì)量越好。通過兩個(gè)節(jié)點(diǎn)的運(yùn)動速度和方向可以計(jì)算出鏈路持續(xù)時(shí)間。

假定任意兩個(gè)車輛節(jié)點(diǎn)為M和N，且在當(dāng)前時(shí)刻建立了通信。此時(shí)M和N的位置坐標(biāo)分別為、，通過式（1）和式（2）可計(jì)算出M和N的運(yùn)動速度和方向。此外，還可以計(jì)算出此時(shí)M和N之間的距離，計(jì)算公式如下。

假定一段時(shí)間內(nèi)車輛保持勻速行駛，運(yùn)動速度和方向不變，車輛M、N的速度大小分別為、，節(jié)點(diǎn)的通信范圍為，則鏈路的維持時(shí)間可分為以下5種情況。

情況一：車輛M、N同向行駛，前車的速度大于后車，那么M與N之間的鏈路維持時(shí)間為

情況二：車輛M、N同向行駛，前車速度小于后車速度，則M、N之間的鏈路維持時(shí)間為

情況三：車輛M、N同向行駛，兩車的速度相同且不變，則M、N之間的通信鏈路將會一直持續(xù)下去，鏈路維持的時(shí)間無窮盡。

情況四：車輛M、N相向行駛，則M、N之間的鏈路維持時(shí)間為

情況五：車輛M與N背向行駛，則車輛M、N之間的鏈路維持時(shí)間為

發(fā)送節(jié)點(diǎn)的一跳范圍內(nèi)的任一鄰居節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的距離可通過公式（8）計(jì)算得出。

（8）

式（8）中，為任一鄰居節(jié)點(diǎn)的位置，為目的節(jié)點(diǎn)的位置坐標(biāo)。

通過上述計(jì)算可以得到發(fā)送節(jié)點(diǎn)和每個(gè)鄰居節(jié)點(diǎn)間的鏈路持續(xù)時(shí)間以及每個(gè)鄰居節(jié)點(diǎn)與目的節(jié)點(diǎn)間的距離，設(shè)置一個(gè)權(quán)重函數(shù)如下。

（9）

式（9）中，和為系數(shù)，且，為權(quán)重值。

當(dāng)數(shù)據(jù)包被傳送至某個(gè)節(jié)點(diǎn)后，通過式（9）可計(jì)算出該節(jié)點(diǎn)與每個(gè)鄰居節(jié)點(diǎn)間的權(quán)重值，選擇權(quán)重值最大的鄰居節(jié)點(diǎn)為下一跳，這樣選出來的節(jié)點(diǎn)具有穩(wěn)定性。不斷重復(fù)此過程，直至將數(shù)據(jù)包送達(dá)目的節(jié)點(diǎn)。

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

實(shí)驗(yàn)采用NS-3[9]仿真平臺對GPSR算法和改進(jìn)的GPSR-S算法進(jìn)行性能仿真，對兩種算法的性能進(jìn)行分析比較。

實(shí)驗(yàn)的仿真場景設(shè)置為1?000?m×1?000?m的區(qū)域，節(jié)點(diǎn)的通信傳輸半徑為250?m，其他仿真參數(shù)的設(shè)置如表1所示。

設(shè)置實(shí)驗(yàn)，分析兩種算法在不同節(jié)點(diǎn)數(shù)下的性能比較。在實(shí)驗(yàn)中，將車輛的速度固定為15?m/s，車輛數(shù)以20的步長從20逐漸增加到140。

圖2是不同車輛數(shù)下的GPSR和GPSR-S的分組投遞率對比圖。由圖看出，當(dāng)車輛數(shù)較少時(shí)，節(jié)點(diǎn)間的通信鏈路較少，二者的分組投遞率較低。當(dāng)車輛數(shù)目增加時(shí)，網(wǎng)絡(luò)連通性增大，二者的分組投遞率也有所提升。不同的是，GPSR-S還考慮了鏈路的可靠性，避免了GPSR通信鏈路易斷裂問題。因此，GPSR-S比GPSR的分組投遞率更高。

圖3比較了GPSR和GPSR-S在不同車輛數(shù)目下的平均端到端時(shí)延。從圖中可以看出，隨著節(jié)點(diǎn)數(shù)量的增加，二者的平均端到端時(shí)延減小。原因是當(dāng)節(jié)點(diǎn)數(shù)較少時(shí)，算法經(jīng)常進(jìn)入周邊轉(zhuǎn)發(fā)，整體時(shí)延較大。隨著節(jié)點(diǎn)數(shù)量增加，轉(zhuǎn)發(fā)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)也增多，算法進(jìn)入周邊模式的概率降低，整體的時(shí)延減小。而GPSR-S與GPSR相較，時(shí)延更低，是因?yàn)镚PSR-S選擇的下一跳節(jié)點(diǎn)更加可靠，通信鏈路不易斷裂。

4?結(jié)語

針對GPSR算法在車載自組織網(wǎng)絡(luò)中應(yīng)用存在的鏈路不穩(wěn)定問題，改進(jìn)后的GPSR-S算法綜合考慮鏈路穩(wěn)定性和距離，將二者聯(lián)合作為決定因素選出穩(wěn)定的下一跳，決定傳輸路徑。仿真結(jié)果表明，GPSR-S算法在分組投遞率和平均端到端時(shí)延方面的表現(xiàn)比GPSR算法均有提高，GPSR-S算法的性能更優(yōu)于GPSR算法，可以更好地運(yùn)用在車載自組織網(wǎng)絡(luò)中。

參考文獻(xiàn)

[1] 張樂樂，王麗，肖小玲.我國智能交通系統(tǒng)的發(fā)展現(xiàn)狀和趨勢[J].電腦知識與技術(shù)，2021，17（3）：247-249.

[2] 劉文晶，劉巧.IEEE?802.11p車載通信網(wǎng)絡(luò)架構(gòu)解析[J].廣東通信技術(shù)，2022，42（4）：18-21.

[3] 祝經(jīng)，周新力，宋斌斌，等.無人機(jī)自組網(wǎng)GPSR路由協(xié)議研究[J].兵器裝備工程學(xué)報(bào)，2021，42（12）：81-86.

[4] 伍龍昶.車聯(lián)網(wǎng)GPSR路由協(xié)議改進(jìn)及城市交通下的性能仿真[D].武漢：武漢理工大學(xué)，2017.

[5] AMINA?B，?ASMAE?B，?MOHAMED?E.?A Novel?Greedy?Forwarding?Mechanism?Based?on?Density，?Speed?and?Direction?Parameters?for?Vanets?[J].International?Association?of?Online?Engineering，2020，14（8）：196-204.

[6] 溫衛(wèi)，張衡陽.車載自組網(wǎng)切線切換路由空洞處理算法研究[J].江西理工大學(xué)學(xué)報(bào)，2019，40（5）：93-97.

[7] 谷志茹，李敏，龍永紅，等.基于GPCR的車輛自組織網(wǎng)絡(luò)路由優(yōu)化方法[J].通信學(xué)報(bào)，2020，41（7）：152-164.

[8] 朱宏輝.車聯(lián)網(wǎng)中基于地理位置路由協(xié)議研究[D].成都：西南交通大學(xué)，2020.

[9] MARIJA?M，?NENAD?J.?A?Framework?for?Performance?Evaluation?of?VANETs?Using?NS-3?Simulator[J].?Promet-Traffic&Transportation，2020，32（2）：255-268.