一種基于地理信息的改進GPSR算法

張馨心 石振剛

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

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

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

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

1?GPSR算法

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

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

2?改進的GPSR算法

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

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

式（1）、式（2）中，、分別為節(jié)點在上一時刻和當前時刻的坐標。

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

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

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

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

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

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

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

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

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

（8）

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

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

（9）

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

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

3?仿真實驗

實驗采用NS-3[9]仿真平臺對GPSR算法和改進的GPSR-S算法進行性能仿真，對兩種算法的性能進行分析比較。

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

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

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

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

4?結(jié)語

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

參考文獻

[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)，周新力，宋斌斌，等.無人機自組網(wǎng)GPSR路由協(xié)議研究[J].兵器裝備工程學報，2021，42（12）：81-86.

[4] 伍龍昶.車聯(lián)網(wǎng)GPSR路由協(xié)議改進及城市交通下的性能仿真[D].武漢：武漢理工大學，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].江西理工大學學報，2019，40（5）：93-97.

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

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