移動邊緣計算環境下基于改進GPSR的VANET路由算法

陳 登，潘 力

(1.川北幼兒師范高等專科學校，四川 廣元 628017; 2.鄭州工程技術學院，鄭州 450044)

0 引言

目前隨著生活水平的日益提高，私家車車輛保有量的提升在一定程度上造成的交通擁堵和安全問題形勢嚴峻，因此智能交通系統(ITS，intelligent transportation system)應運而生[1-2]。而車載自組織網絡(VANET，vehicular ad-hoc network)作為ITS的核心部分[3]，在實現有效的路側通信和數據傳輸過程中發揮著重要作用。

車輛網絡是利用移動自組織網絡(MANET，mobile ad hoc network)原理建立的，利用無線局域網(WLAN，wireless local area network)技術，通過車與車、車與設施之間實現多跳通信，在不同的距離上建立移動網絡[4]。如果一個車輛離開定義的范圍，則在網絡中添加另一個節點或車輛以保持通信的有效性[5]。在MANET的幫助下，它在車對車(V2V，vehicle to vehicle)模式[6]和車對基礎設施(V2I，vehicle to infrastructure)模式[7]過程中傳輸了多個數據。此外，VANET還改善了旅行時的道路安全，并提供視頻、音頻傳輸、電子郵件通信等多種服務。在數據傳輸過程中，VANET利用諸如Zigbee、WLAN、LTE、基于紅外的通信等無線技術，成功地將數據、多跳信息、協同感知信息發送到不同的目的地，即使它們處于較遠位置。由于VANET能有效地與車輛協同工作來提高通信質量，在道路數據通信過程中發揮著重要的作用[8]。但仍然面臨著一些諸如安全性、數據認證、隱私、數據訪問控制、數據機密性、數據不可否認性、數據完整性、網絡可用性以及難以預測車輛位置等方面的挑戰。此外，無基礎設施的通信過程在通信時也會遇到擁塞問題。

針對上述挑戰，學者們進行了一定的研究。例如，文獻[8]提出了一種改進貪婪周邊無狀態路由(IGPSR，improved greedy perimeter stateless routing)的車聯網路由算法，該算法根據節點的移動速度預測節點間的距離，并選取移動緩慢的、穩定的節點作為中繼節點，以確保路由選擇的可靠性，一定程度上提高了GPSR路由投遞率低、傳輸時延大的問題。文獻[9]開發了一個基于貪婪交通燈隊列的路由協議系統，用于在城市環境中傳輸車輛數據，該系統在減少數據傳輸延遲的同時，有效地管理了業務負載。文獻[10]介紹了用于在車輛自組織網絡中傳輸數據的微生物啟發單播路由協議(MIURP,microbial-inspired unicast routing protocol)，利用單播路由過程達到最小延遲和最大分組傳輸率的效果。文獻[11]使用貪婪路由協議(GRP,greedy routing protocol)管理節點移動性和網絡開銷問題，該方法使用有助于最小化車輛定位誤差的鏈路質量因子來檢查節點之間的鏈路，應用卡爾曼濾波器檢測鏈路質量，提高了車輛網絡中數據傳輸的效率。文獻[12]提出了用于管理車輛網絡中存在偏差的流量感知路由協議(DFERP,deviation of flow-aware exist routing protocols)，該方法通過計算期望的連通度值來處理交通信息，根據收集的信息選擇以最小延遲將信息成功傳輸到目的地的路由。文獻[13]提出了一種新的自適應業務路由協議(ABRP,adaptive business routing protocol)，用于在車載網絡中傳輸數據時管理路徑、鏈路的可靠性，通過使用可靠性參數和啟發式函數的自適應路由過程確保在VANET中成功的數據傳輸。

針對上述VANET路由算法中傳輸數據質量較低、且數據傳輸的吞吐量較小等問題，提出了移動邊緣計算環境下，結合改進貪婪周邊無狀態路由(GPSR，greedy perimeter stateless routing)和自適應鏈路質量評估的VANET路由算法(IGPSR-MSD)。主要創新點總結如下：

1)將邊緣計算架構應用于VANET能夠有效緩解計算量大、與車輛有限且不均的資源分布之間的矛盾。

2)傳統GPSR路由決定因素單一，存在易超過通信范圍、造成鏈路不穩定的問題。為此，本文考慮了節點移動性，根據節點間距離來估計鏈路穩定性，實現鏈路的動態更新，提高鏈路質量。

3)為了提高傳統GPSR的傳送率，設計了一種鏈路傳輸速率估計方法。最后根據鏈路穩定性和和傳輸速率來選擇合適的中繼節點，提高網絡穩定性和成功傳送率。

通過SUMO仿真平臺對路由算法的性能進行評估，結果表明所提算法受車輛密度、交通流以及車輛相對速度的影響較小，且提高了分組傳送率，減少端到端延遲，降低了通信開銷。

1 系統模型

VANET是城市交通道上的無線自組織網絡，由圍繞X*Y網絡區域移動的N輛車組成，其通信模型如圖1所示。網絡中的車輛均裝有GPS等無線通信設備，并利用RFID技術將數據傳輸至網絡傳輸層進行分析和處理。在VANET中主要的通信模式有兩種：車輛間通信和車輛到路邊通信設施間的通信。其中，邊緣計算資源層主要負責資源的優化分配過程與資源共享。例如，車輛間的V2V通信，安全告警類業務的傳輸可能需要多跳通信，但跳數的增加會引起時延增大，導致可靠性降低。當某一部分的業務實體出現資源短缺時，可以利用邊緣服務協助計算、存儲。因此，需要將不同車聯網業務的需求映射為對通信接入方式和計算資源的選擇，實現不同局部范圍內車輛間的資源共享。

為不失一般性，本研究假設一共有L個路旁接入設施(RSU或公共WIFI)。同時，每一個路旁接入設施都配置相應的邊緣服務器。

在VANET中，兩輛車會被物理距離d隔開，因此通過使用專用短程通信和802.11標準定義的車輛環境中的無線接入通信技術進行連接。車輛在行駛過程中具有機動性，速度和方向均會發生改變。假設(xm,ym)和(xn,yn)是車輛m和n的位置坐標，則兩者間的距離為[14]：

(1)

車輛m和n之間相對速度vs的估算公式為：

(2)

式中，vm和vn分別是車輛m和n的速度。

2 提出的VANET路由算法

VANET是通過多跳將數據從發送節點轉發到目的節點，因此如何選擇最優的下一跳節點來轉發數據是路由算法設計的關鍵[15]。所提方法使用改進貪婪周邊無狀態路由(GPSR，greedy perimeter stateless routing)協議保證網絡通信的穩健，并采用自適應鏈路質量評估提高通信效率。

2.1 問題描述

(3)

式中，▽φ是不成功的數據傳播因子。如果鏈路不可用，則不進行傳輸。

使用目標車輛上信息接受失敗情況來估計不成功傳播因子，其為成功發送請求和失敗發送請求的組合，其中失敗請求根據鏈路故障和車輛節點移動進行計算。不成功傳播因子[16]為：

(4)

式中，dv為目標車輛，qp為網絡中的車輛m和dv之間路徑p的鏈路質量。

其中鏈路質量qp表示兩個車輛之間鏈路的最大可用性，表示為：

qp=(e-1)*Nn+(1-d)×Nnt

(5)

式中，(e-1)為m和dv之間路徑車輛的數量。Nn和Nnt分別為確保lm,n=1而發送的信標消息數量，以及在時間t由車輛m生成的信標總數。對于進行V2V通信的車輛n與車輛m而言，車輛n的信噪比可表示為:

(6)

(7)

其中:Nρ為在車隊中處于頻段ρ的車輛數目。

路由算法的目標是最大化數據成功傳輸概率，并且保證最大數據傳輸量，獲得更好的傳輸速率。

2.2 GPSR協議

GPSR路由協議將貪婪轉發和邊界轉發相結合。節點直接根據節點自身、鄰居節點和目的節點的位置信息制定數據轉發策略。另外，節點通過周期性廣播包含自身位置信息的Hello數據包，獲取相鄰節點的位置信息，從而更新鄰居路由表。通常情況下，節點利用貪婪策略來選擇下一跳節點，當局部最優現象發生時，啟動周邊轉發策略選擇下一跳轉發節點[17]。

GPSR協議流程圖如圖2所示。

GPSR協議的優點在于：使用局部最優的貪婪算法，無需在節點中構建并動態更新路由表，路由開銷較小；只要網絡是連通的，便能獲得可以傳輸數據的路由；采用與最短歐氏距離相近的路由，數據傳輸時延較小。

然而，VANET中車輛節點的移動較快，網絡拓撲結構動態變化較大。節點的移動會使路由中下一跳會節點變化，需要重新調用路由算法。這就導致傳統GPSR協議存在一些缺點，主要有：

1)GPSR協議中沒有充分考慮節點的移動速度信息，可能會使用距離越遠的節點。如果這個節點移動速度較快，易超出通信范圍，導致路徑有效時間將會很短。這不僅造成數據包在轉發過程中丟失，降低服務質量，而且還會導致頻繁調整路由，降低算法效率。

2)GPSR協議僅簡單地根據距離信息確定路由策略，并未考慮鏈路的數據傳輸速率。傳輸速率受到交通道路拓撲中的靜態和動態屬性影響，如路段上的車流密度、方向等。

2.3 改進GPSR協議

結合VANET的網絡特點，針對GPSR協議存在的問題，提出了基于節點移動速度(MS，moving speed)和節點間距離(ND，node distance)的改進GPSR協議(IGPSR-MSD)。根據節點移動速度和距離來估計消息傳輸速率和鏈路穩定性權重，從而選擇出高鏈路質量且高消息傳輸率的最佳鏈路。

2.3.1 鏈路質量估計

由于GPSR路由協議沒有考慮動態交通拓撲屬性，可能產生錯誤或不可用的鏈路，因此需要對鏈路質量進行自適應評估，使用一個權重因子對鏈路節點進行修正。

假定節點最大通信范圍R，且系數δ(0<δ<1)表示某個節點的通信能力。本文在拓撲結構中節點通信范圍δR～R內，選取鏈路質量較高的節點作為中繼節點。通常節點停留時間越長，表明節點移動速度越緩慢，則該節點越穩定[18]。

假定車輛k以速度vk移動，在間隔時間T內轉發數據包，中繼節點與轉發節點j的相鄰距離開始為ΔdTj，則下個時間間隔T+1內車輛k的移動距離為：

(8)

式中，at為車輛的加速度。轉發節點與中繼節點j間的距離Δd與車輛移動速度vk相關，計算公式為：

Δd=ΔdTj+(dj-dk)=

(9)

通過距離Δd來計算鏈路穩定性權重α(lm,n)，計算如下：

(10)

圖3 中繼節點選擇過程

根據鏈路穩定性權重α(lm,n)可以將不可用的鏈路從列表中丟棄，以此精簡局部最優解。如果兩個或多個局部最優解相同時，則由其中最大值生成全局解。在傳統的路由過程中，為了選擇最優的相鄰節點，需要估計與節點相關的度量。為了提高通信速率，選擇通信范圍內的最大節點數目以最大化帶寬，有利于提高數據傳輸速率。

2.3.2 數據傳輸速率估計

假設兩輛車之間的相對速度分布Δv為：

(11)

式中，μk和σk是消息發送節點的平均速度和標準偏差向量，ρRi是通信范圍R內的鄰居的密度，dmax為移動距離設定的最大值。

假定兩節點的連接時間為Δt，那么鏈路lm,n中的消息傳輸成功的概率[19]為：

(12)

當消息傳輸成功概率滿意一定條件時，進行消息傳輸。對于中繼節點，如果lm,n=1，即兩車在移動過程中，處于連通狀態。

則中繼節點與轉發節點的消息傳輸速率Δmjk為：

(13)

從上式中可以看出，數據傳輸速率與節點的速度有關。

最后，可以根據鏈路穩定性權重α(lm,n)和數據傳輸速率來動態評估鏈路質量，從而選擇出最佳中繼節點的相鄰節點。因此，可以克服傳統GPSR協議中鏈路質量評估沒有考慮到動態特性的問題。

3 實驗結果與分析

仿真中的區域設置為5 km×5 km的區域內，包含最多400個車輛節點，車輛速度設置為20到100 km/h，通信半徑為250 m。本仿真實驗一共有10個(5+5)路旁接入設施，其中5個接入設施隨車輛的移動而逐漸遠離車輛。車載 CPU和MEC服務器性能均設置為1 GHz。MAC層協議為IEEE802.11，傳輸層協議為UDP，信標消息大小為512 Bytes，帶寬為2 Mbps，數據包發送間隔時間為5 s。

路線圖由交叉口和長車道組成，通過對車輛發送功率的標定來建立通信范圍，并且為車輛確定適當的網絡、傳輸層協議以及應用類型。將本文提出的IGPSR-MSD路由算法與現有的文獻[10]提出的MIURP、文獻[8]提出的IGPSR和文獻[13]提出的ABRP算法進行比較。分別在不同的車輛密度、交通流和車輛移動速度情況下，從分組傳送率、通信開銷和端到端延遲等指標上進行對比分析。

3.1 車輛密度的影響

車輛密度將直接影響車載自適應網絡性能。車輛密度的變化改善了網絡連通性，也改善了干擾區域。仿真實驗以65 km/h的速度分析車輛密度對分組傳送率[20]、丟包率[21]以及通信開銷[22]的影響。其中設置車輛數量為30到400之間不等。

3.1.1 分組傳送率

將所提算法的分組傳送率與現有算法進行對比，結果如圖4所示。車輛密度增加，高度集中導致暫停或者慢速通信。所提算法中通過估計Δmjk優化數據速率，根據Δv和Δd選擇最優的中繼節點，并且驗證α(lm,n)，選擇一條穩健的鏈路以確保傳送率最大。

圖4 車輛數量與分組傳送率

從圖4中可看出，相比于其他算法，所提出的IGPSR-MSD算法的分組傳送率最高，并且隨著車輛的增加，該值也逐漸增大。文獻[13]中考慮了靜態和動態的道路信息，但未充分鏈路質量的影響，因此分組傳送率較低。文獻[8]根據節點的移動速度預測節點間的距離，但對中繼節點的選擇標準太過寬泛，分組傳送率有待提高。文獻[10]僅考慮車輛速度和位置等因素的影響，但對于道路信息等未進行動態更新，因此分組傳送率較低。

此外，將所提算法的丟包率與現有算法進行對比，結果如表1所示。由于最優的中繼節點選擇，IGPSR-MSD中節點間重新連接和路由鏈路錯誤的數量較少，并且自適應鏈路質量評估確保了可靠鏈路，提高了成功的分組傳送，降低了丟包率。

表1 車輛數量與丟包率(100%)

3.1.2 通信開銷

車輛數量的增加導致控制信息交換的速率增加，其中路由請求和響應確認的總數用于估計通信開銷。將所提算法的通信開銷與現有算法進行對比，結果如圖5所示。在提出的IGPSR-MSD算法中，車輛的狀態經過初步分類，車輛距離和鏈路權重α(lm,n)共同決定數據轉發時的中繼節點選擇，以實現較少的控制消息。

圖5 車輛數量與通信開銷

從圖5中可看出，所提出的IGPSR-MSD算法的通信開銷最小，尤其隨著車輛數量的增加，該優勢越明顯，由于其選擇最優的中繼節點，無需傳送大量的控制信息。文獻[13]中由于考慮道路信息的靜態和動態信息，且缺乏高效的傳輸策略，因此通信開銷較多。文獻[8]利用IGPSR完成VANET路由，其中根據移動節點實時預測車輛，且選擇中繼節點，對通信的要求較高，開銷也較高。文獻[10] 通過使用可靠性參數和啟發式函數的自適應路由過程確保在VANET中成功的數據傳輸，動態調整路徑，因此通信開銷相比文獻[8]和文獻[10]有所降低。

3.2 交通流的影響

評估交通流量對所提出算法和現有算法在端到端延遲和分組傳送率等方面的影響。不同的流量會增加網絡擁堵的可能性，從而影響車輛的速度和數據的傳輸速錄。實驗中設置交流流量為1到6不等，其中1代表各個路口基準交通流量，設置為15輛/分鐘。

3.2.1 端到端延遲

交通流的增加導致通信過程中的分組傳送時間延長。將所提算法的端到端延遲與現有算法進行對比，結果如圖6所示。所提出的IGPSR-MSD算法中，通過基于移動方向選擇速度和距離較小的節點來保證鏈路的可用性。基于距離和最優的δc的節點選擇提高了鏈路的穩定性，qp保證了傳輸質量，防止了響應時間的延長。因此，與現有算法相比，IGPSR-MSD具有更少的延遲。

圖6 交通流與端到端延遲

從圖6中可看出，相比于現有算法，所提出的IGPSR-MSD算法的端到端延遲時間是最小的，雖然隨著交通流的增加，其延遲時間也會上升，但上升幅度明顯比現有方法緩。尤其是文獻[8]和文獻[10]由于缺乏高效的分流策略，無法快速獲得可靠的鏈路，其端到端延遲時間長，且隨著交通流的增加快速上升。文獻[13]利用ABRP算法自適應調整傳輸路徑，端對端延遲較小。

3.2.2 分組傳送率

交通流對所提算法與現有算法的分組傳送率的影響如圖7所示。所提出的IGPSR-MSD算法通過在通信時qp和Δd選擇可靠的鏈路來處理通信量。對于不同的車輛密度和速度，在任何時刻設置鏈路，通過在通信路徑中選擇適當的車輛，最大化Δmjk，以實現更高的分組傳送率。

圖7 交通流與分組傳送率

從圖7中可看出，所提算法的分組傳送率是最高的，但隨著交通流的增加，由于傳送時間延長，分組傳送率逐漸降低，但下降幅度在高交通流時較小。邊緣計算層的引入使得車聯網環境中的車輛間的資源優化調度策略變得更加靈活，進行通信、計算資源的合理分配，實現不同局部范圍內實體間的資源高效利用。文獻[8]根據節點的移動速度預測節點間的距離，并且選擇運動緩慢的節點作為中繼節點，一旦交通流增大，大部分節點運動緩慢，均可作為中繼節點，加快數據傳送，因此當交通流為5時有一個短暫的上升，但是節點數量有限，因此分組傳送率會再次降低。文獻[13]由于具有適用于較高交通流的路由協議，因此在交通流為4時有短暫的上升。文獻[10]利用單播路由過程，當交通流增大時，其數據傳輸壓力較大，因此分組傳送率持續降低。

3.3 車輛相對速度的影響

車輛速度的變化會導致頻繁的鏈路變化和路由更新，如果僅路由過程是周期性變化的，lm,n=1能夠處理車輛速度的干擾而不影響網絡性能。車輛相對速度對所提算法與現有算法性能的影響如圖8所示。所提出的IGPSR-MSD算法中，由于路由過程中通過分析有利的傳輸條件以確定最優的中繼節點，并且所需的信標信息最少，從而確保了鏈路的可用性。

圖8 車輛相對速度與信標信息

所提出的IGPSR-MSD算法所需的信標信息最少，這是因為算法中考慮了車輛相對速度分布Δv，并且優化鏈路選擇，因此對信標信息的依賴性較低。文獻[10]由于較依賴車輛速度和位置的信息，因此其信標信息較多。文獻[8]需要選擇中繼節點，對信標數量有一定的要求，隨著車輛相對速度越大，節點間距離越大，為了保證通信質量，對信標數量的需求也會提高。而文獻[13]中較多依靠靜態和動態道路信息，因此需要的信標信息較少。

4 結束語

為了提高VANET中的數據傳輸速率，所提出的移動邊緣計算環境下的IGPSR-MSD算法，結合了GPSR協議和自適應鏈路質量評估，通過鏈路穩定性權重和鏈路傳輸速率來選擇最優的中繼節點，確保鏈路的可靠性，完成高效的數據傳輸。IGPSR-MSD協議通過對車輛的通信范圍和位置、速度信息保持較好的鏈路穩定性，針對路由協議中可能出現的路徑錯誤，引入了自適應鏈路質量評估，簡化了中繼節點與轉發節點的數據流和傳輸流。實驗結果驗證了車輛密度、車輛流和車輛相對速度對所提算法的影響較小，并且分組傳送率較高、端到端延遲較短且通信開銷較小，鏈路選擇時對信標信息依賴程度不高。因此，所提算法能夠在眾多干擾下保持可靠的數據傳輸，適用于實際的車載網絡環境。

然而，所提方法中未考慮車輛方向突然改變這一因素的影響，并且實際道路信息復雜，目前考慮的因素有所欠缺。因此，后期將進一步完善VANET路由算法影響因素的分析并進行算法優化。