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

張馨心 石振剛

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

關鍵詞：車載自組織網絡??路由算法??GPSR??數據包投遞率??端到端時延

中圖分類號：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

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

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

1?GPSR算法

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

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

2?改進的GPSR算法

針對上述數據包轉發過程中存在鏈路不穩定的問題，對其進行改進。改進GPSR-S算法不僅采用貪婪方式，還對鏈路質量加以考慮，選出穩定的下一跳。

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

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

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

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

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

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

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

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

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

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

發送節點的一跳范圍內的任一鄰居節點與目的節點之間的距離可通過公式（8）計算得出。

（8）

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

通過上述計算可以得到發送節點和每個鄰居節點間的鏈路持續時間以及每個鄰居節點與目的節點間的距離，設置一個權重函數如下。

（9）

式（9）中，和為系數，且，為權重值。

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

3?仿真實驗

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

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

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

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

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

4?結語

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

參考文獻

[1] 張樂樂，王麗，肖小玲.我國智能交通系統的發展現狀和趨勢[J].電腦知識與技術，2021，17（3）：247-249.

[2] 劉文晶，劉巧.IEEE?802.11p車載通信網絡架構解析[J].廣東通信技術，2022，42（4）：18-21.

[3] 祝經，周新力，宋斌斌，等.無人機自組網GPSR路由協議研究[J].兵器裝備工程學報，2021，42（12）：81-86.

[4] 伍龍昶.車聯網GPSR路由協議改進及城市交通下的性能仿真[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] 溫衛，張衡陽.車載自組網切線切換路由空洞處理算法研究[J].江西理工大學學報，2019，40（5）：93-97.

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

[8] 朱宏輝.車聯網中基于地理位置路由協議研究[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.