基于路徑探索的車載自組網貪婪路由算法

湯星峰，徐卿欽，馬世緯

（移動通信技術重慶市市級重點實驗室（重慶郵電大學通信與信息工程學院），重慶 400065）

（?通信作者電子郵箱S170101085@stu.cqupt.edu.cn）

0 引言

車載自組網（Vehicular Ad-hoc NETwork，VANET）是一種新興技術，它將新一代無線網絡集成到車輛中，旨在實現車輛之間的通信，以改善道路安全和提供必要的服務［1］。車載自組網作為一種特殊的移動自組網，在智能交通和智慧城市的發展中發揮著重要的作用［2］。車載自組網主要包含兩種類型的應用：安全預警和娛樂服務。安全預警消息，比如碰撞警告、前車變速預警等，是以廣播的形式進行傳播，對時延有很高的要求。而娛樂服務，比如文件共享、對特定路段的視頻請求等，是通過多跳單播路由來實現的，具有一定的時延容忍特性。本文所提出的算法是應用在車輛間娛樂服務的多跳單播路由中。

在車載自組網多跳單播路由算法中，基于地理位置轉發的路由算法在車載自組網環境中具有更好的性能。文獻［3-5］通過預測車輛的運動以及設定路口中繼車輛的方式來轉發數據包，雖然減小了車輛間鏈路的斷開概率，但在頻繁變化的拓撲中，通過預測的方式選擇下一跳轉發車輛具有較高的計算復雜度，對數據包的傳輸時延也有較大的影響。文獻［6-8］中將車輛速度、密度等作為參數，計算出各個路段的權重值。結合地理信息和城市拓撲，使用Dijkstra算法計算從源車輛到目的車輛的最短路徑，然后使用貪婪轉發的方式將數據包發送到目的車輛。雖然算法中考慮了城市車輛的密度，避免數據包在車輛稀疏的道路中傳輸，但這類算法沒有考慮車輛密度變化的實時性，缺少對道路中車輛密度的實時反饋。文獻［9-10］提出了車輛與車輛和車輛與路邊單元的混合路由方式，車輛通過路邊單元轉發能很好地適應車輛拓撲的變化，降低發送時延，但路邊單元的部署和成本問題以及可擴展性問題是該路由算法的難點。

為了提高數據包的到達率，降低數據包端到端時延。本文在以上研究成果的基礎上提出了基于路徑探索的車載自組網貪婪路由算法（Vehicular ad-hoc network Greedy routing algorithm based on Path Exploration，VGPE）。本文所提算法將數據路由分為路徑探索和限制貪婪轉發兩個過程，充分考慮城市環境的特殊性，在快速變換的車輛拓撲結構中具有很好的適應性和可擴展性。

本文的主要工作如下：1）結合數字地圖規劃出的多條路由路徑，提出了基于人工蜂群算法的路徑探索策略，以找到時延最小的路由路徑轉發數據包。2）在車輛的信標消息中加入速度、車輛所在路段ID 等字段，以便在選擇轉發車輛時能確保數據傳輸穩定，且使得整個路由跳數最少。3）在貪婪轉發數據包時使用限制性策略，避免數據包轉發到陷入路由空洞的車輛。

1 問題引出

在介紹本文路由算法之前，先對城市道路中的車輛作如下假設：

1）城市道路上的每輛車都安裝了全球定位系統（Global Positioning System，GPS）導航系統和所在城市的數字地圖，車輛可以通過GPS和數字地圖獲得當前車輛所在道路的編號和位置坐標。

2）車輛之間的傳輸信號無法穿過城市道路兩邊的建筑物，所以不同道路上的車輛想要傳輸信息必須通過在交叉路口車輛的轉發。

3）不同類型的車輛，比如出租車、公交車、大貨車等在轉發數據時都不作區分，擁有相同的轉發半徑、數據發送速率等參數。

車輛在城市中以基于地理位置的貪婪方式轉發數據包時，可能會形成如圖1中所示的情況。源車輛S根據貪婪轉發的方式將數據包發送給在源車輛S 通信范圍內離目的車輛D最近的車輛A。而車輛A 在以相同的方式轉發數據包時，因為道路兩邊建筑物的遮擋，車輛A 接收不到車輛E 的位置消息，在車輛A 的鄰居列表中車輛B 離目的車輛D 最近，所以車輛A 將數據包發送給車輛B。但車輛B 所在的路段中的車輛無法將數據包轉發給目的車輛，且車輛B 所在路段中的車輛與目的車輛的距離都比車輛B 與目的車輛的距離大，所以數據的發送會進入恢復模式。根據恢復模式的規則，車輛B 會把數據發送給車輛C，車輛C 再把數據發送給車輛E，車輛E與目的車輛的距離小于車輛B，從而繼續貪婪轉發。由此可以看出，基于地理位置的貪婪路由算法可能因城市場景的特殊性，無法將數據發送到正確的路徑上，從而造成路由跳數的增多，增大了數據路由的時延和丟包率。

在城市場景中使用基于地理位置的貪婪方式轉發數據包時，最短路徑并不一定就是最優路徑，有可能在最短路徑上車輛稀疏，連接性不好，路由時延和丟包率反而更大。因此本文先使用人工蜂群算法對數據包路由路徑進行探索，再對數據包進行轉發。

圖1 貪婪轉發局限性示意圖Fig.1 Schematic diagram of greedy forwarding limitation

2 基于人工蜂群算法的路由路徑探索策略

2.1 人工蜂群算法介紹

人工蜂群（Artificial Bee Colony，ABC）算法是一種模仿蜜蜂采蜜的群智能優化算法［11］。人工蜂群算法初始化后包含三個階段：雇傭蜂階段、跟隨蜂階段和偵查蜂階段。

1）雇傭蜂階段。在雇傭蜂階段，雇傭蜂通過式（1）來尋找蜜源［12］。

其中：φ是在[-1，1]中取值的隨機數；xij是初始化時產生的蜜源，xkj代表在初始蜜源中與xij不相等的蜜源，i代表蜜源的編號，j代表蜜源的維度。一個蜜源就表示一個解。在雇傭蜂找到新的蜜源后，比較vij和xij適應度的值，選擇具有更優適應度值的蜜源作為本次尋找的結果。適應度的值為蜜源花粉的數量。

2）跟隨蜂階段。在雇傭蜂確定要開采蜜源后，雇傭蜂返回蜂巢通過舞蹈分享蜜源信息。跟隨蜂采用輪盤賭的方法選擇雇傭蜂所找到的蜜源來開采。輪盤賭的方法是：通過（其中fiti是蜜源i的適應度的值，N是初始化時蜜源的個數）所得出的數比在［0，1］產生的一個均勻分布的隨機數大，則跟隨蜂就去開采這個雇傭蜂所找的蜜源，否則不開采。

3）偵查蜂階段。在搜索過程中，如果一個蜜源經過多次迭代，在達到閾值limit前沒有找到更優適應度值的蜜源，則這個蜜源將會被拋棄，雇傭蜂將會變成偵查蜂，通過式（2）產生一個新的蜜源來代替被拋棄的蜜源。

其中，xmin_j和xmax_j分別表示解中第j維的最小值和最大值。

2.2 人工蜂群算法在路由路徑探索中的應用

將人工蜂群算法查找最優值的過程應用在車載自組網數據路由路徑探索中，以應對城市環境中車輛拓撲的快速變化。在城市環境中，把一條從源車輛到目的車輛的路由路徑作為人工蜂群算法中的一個蜜源，人工蜂群算法的每次迭代都要找出所有蜜源中適應度值最大的蜜源作為跟隨蜂的開采蜜源，也就是數據包轉發的路徑。而適應度的值就是雇傭蜂發現的蜜源的花粉數量，在本文中就是探測包在各個路徑上的傳輸時延，傳輸時延越少說明適應度的值越大。適應度的值如式（3）所示：

其中，τSD是探測包從源車輛通過路徑中車輛的多跳轉發到達目的車輛的時延。

步驟一 初始化階段。在初始化階段要確定蜜源的個數，即備選路徑集。如圖2 所示，圖中In是各個路口的編號。當源車輛響應目的車輛的數據請求，向目的車輛發送數據包之前，源車輛先通過車載的城市道路的數字地圖，找到經過最少路口數到達目的車輛的路徑，在圖2 中，就是最短路徑L1。本文規定，從源車輛到目的車輛的路徑中，只要經過的路口數小于等于最短路徑路口數的2 倍，都加入車輛發送路徑探索包的備選路徑集中，在圖2 中就有路徑L2、L3，從而路徑集｛L1，L2，L3｝就是初始化的蜜源集。

圖2 路徑探索示意圖Fig.2 Schematic diagram of path exploration

步驟二 雇傭蜂階段。源車輛分別向初始化階段所產生的路徑集中的所有路徑發送路徑探索消息（Routing Path Exploration Message，RPEM），即雇傭蜂。路由路徑探索消息的格式如圖3所示。

圖3 路徑探索消息格式Fig.3 Path exploration message format

1）類型：表示不同的數據包類型。其值為1 時，表示路徑探索包；值為2時，表示目的車輛回復包。

2）路徑條數：記錄初始化時路徑集中的路徑條數，也就是探索包的發送個數，以便目的車輛對接收到的探索包個數進行驗證。

3）所要經過路段的ID 序列：規定路徑探索包所要經過路段的ID序列，包括源車輛和目的車輛所在路段。

4）探索包發送時間：記錄探索包發送時間，以便在探索包到達目的車輛后計算路徑的傳輸時延。

5）多跳轉發跳數計數器：記錄探索包從源車輛到目的車輛被轉發的跳數。

路由路徑探索消息通過第3 章中的限制性貪婪路由策略以多跳的形式轉發到目的車輛。當目的車輛收到源車輛的路徑探索消息時，比較各個路徑探索消息的適應度值，適應度越大說明這條路徑連接性越好、時延越少，因此目的車輛按具有最大適應度值的路徑向源車輛回送一個應答消息（Routing Path Exploration Response Message，RPERM）。應答消息的格式如圖3 中所示，和路徑探索消息的格式一樣，只不過在應答消息中類型值為2，所經過的路段ID 序列為所選定的路徑中各路段的ID號。

步驟三 跟隨蜂階段，即數據發送階段。當源車輛接收到目的車輛的應答消息后，記錄選定路徑的轉發時延，即蜜源適應度的值，將路徑的路段ID 序列寫入數據包的包頭，發送數據包。數據包就會根據選定的路徑通過多跳的方式轉發數據包。

步驟四 偵查蜂階段。當目的車輛每次收到數據包后都會通過所選路徑向源車輛發送應答消息。源車輛收到應答消息后計算適應度的值，當有其他路徑適應度的值連續三次大于當前路徑適應度的值時，將適應度值最大的路徑中各路段的ID 寫入數據包頭部，切換數據包轉發路徑，以適應路徑中車輛拓撲的變化。

3 車輛間消息轉發的限制性貪婪轉發策略

3.1 車輛間的信標消息

在傳統的貪婪周邊無狀態路由（Greedy Perimeter Stateless Routing，GPSR）協議中，車輛間的信標消息是用來交換位置信息的。在本文算法中，給車輛間的信標消息增加了幾個字段，以傳遞更多有用的信息。信標消息的格式如圖4所示。

圖4 信標消息的格式Fig.4 Beacon message format

1）車輛的行駛方向：表示為一個路口號對（車輛駛離的路口號，車輛駛向的路口號）。

2）車輛所在路段的ID：可以結合車輛上的數字地圖和GPS定位來獲得，如果車輛在交叉路口上，則車輛所在路段的ID就是車輛所在交叉路口的編號。

3）車輛是否在交叉路口處：如果是，值為1；如果不是，值為0。當車輛在路段上行駛時，由于城市兩邊建筑的限制，車輛不能接收到其他路段上車輛的信標消息。當車輛接收到的信標消息中，路段ID數大于等于3時，說明車輛處在交叉路口上，則將信標消息的這個字段置為1。

4）在相同/相反行駛方向上車輛是否有下一跳：是為了避免將數據包發送給陷入路由空洞的車輛。

3.2 數據包的限制性貪婪轉發

數據包的限制性貪婪轉發優化了基于地理位置貪婪轉發中的三個問題。

3.2.1 優化問題一

如圖5 所示，傳統的基于地理位置的貪婪轉發路由協議，每次轉發都是以離目的車輛最近的鄰居車輛作為下一跳轉發車輛，這樣容易將數據包發送給陷入路由空洞的車輛，從而進入恢復模式，增加了路由的跳數。

為了解決這個問題，本文在車輛的信標消息中加入了“在相同/相反行駛方向上車輛是否有下一跳”這樣兩個字段。在車輛轉發數據包之前，先查看收到的鄰居車輛的信標消息中這兩個字段是否都等于1，只有在這兩個字段的值都為1 時，才能確定要轉發的下一跳車輛沒有陷入路由空洞中，從而將數據包轉發給選定的下一跳車輛。從圖5 中可以看出，因為在車輛C 的鄰居中沒有比車輛C 更接近目的車輛D 的下一跳車輛，所以車輛C 的是否有下一跳車輛這個字段置0，從而車輛S 就不會因為車輛C 距離目的車輛更近而把數據包發送給車輛C，而是把數據包發送給下一跳車輛字段置1 的車輛B。所以在數據每次轉發時并不是以離目的車輛最近作為轉發車輛選擇標準，還要借助“在相同/相反行駛方向上車輛是否有下一跳”這兩個字段進行篩選。

圖5 傳統貪婪轉發Fig.5 Traditional greedy forwarding

3.2.2 優化問題二

由于城市道路中車輛的高度動態性，所以在傳輸數據的過程中，接收車輛可能離開發送車輛的傳輸范圍造成鏈路中斷，導致數據傳輸失敗。

為了盡量避免車輛在傳輸數據時鏈路斷開，在數據傳輸方向上滿足下一跳車輛字段為1 的鄰居車輛中，本文使用信標消息中的車輛速度字段記錄的車輛實時速度計算出每一個鄰居車輛與數據包攜帶車輛的速度差，從而計算出接收車輛和鄰居車輛的鏈路連接時間，也稱為連接窗口時間。如果在鄰居車輛中有窗口時間大于數據包發送時間的鄰居車輛，就在這些鄰居車輛中選擇擁有最小的窗口時間的車輛作為轉發車輛；如果鄰居車輛的窗口時間都是小于數據包發送時間的，就選擇擁有最大窗口時間的鄰居車輛作為轉發車輛。當接收車輛和發送車輛之間的距離越來越大時，車輛之間鏈路連接時間Tlink的計算式如式（4）所示。

式中：Sni，ni+1為發送車輛ni和接收車輛ni+1之間的距離；250是指設定的車輛的通信半徑為250 m；Vni和Vni+1分別是發送車輛ni和接收車輛ni+1的速度。表示發送車輛ni和接收車輛ni+1的速度方向相同，表示發送車輛ni和接收車輛ni+1的速度方向相反。

如果接收車輛和發送車輛之間的距離越來越小時，就認為車輛之間鏈路的連接時間Tlink為∞。

數據包的發送時間tdata由式（5）計算得出。

式中：xdata表示數據包的大小；vdata表示數據包的發送速率；αt表示數據發送時的排隊時延；γt是信道爭用時間。

3.2.3 優化問題三

在城市環境中，當數據包轉發到交叉路口附近時，因為道路兩旁的建筑物的遮擋，發送車輛的鄰居表中可能沒有要轉發道路上的下一跳車輛，所以一般的解決方法是以交叉路口的車輛作為中轉車輛，進行數據包的轉發；但這樣可能會增加整個路由的轉發跳數。如圖6 所示，數據包轉發到車輛S，而下一個轉發路段與車輛S 所在路段同方向。車輛D 在車輛S的通信范圍內，車輛S 可以直接將數據包發送給車輛D，如果先將數據包發送給路口車輛A，再由A 轉發，則就會增加轉發跳數，從而增加轉發時延。

圖6 接收車輛和轉發車輛在同方向路段Fig.6 Receiving vehicles and forwarding vehicles in same direction

本文的優化方法是：車輛在轉發數據包前，通過查找數據包頭部字段“所經過路段的ID序列”，找到當前路段ID的下一個路段ID，然后查找當前車輛的鄰居列表中所有車輛所在路段的ID是否有與下一個路段ID相同的車輛，如果有就加入備選轉發車輛集，如果沒有再將字段車輛是否處于交叉路口置1的車輛加入備選轉發車輛集。

數據包貪婪轉發策略偽代碼如下所示。

4 實驗仿真與結果分析

4.1 實驗設置

使用NS3 和SUMO 軟件對本文所提出的路由算法（VGPE）進行了仿真，并將該算法與傳統路由算法GPSR［13］和改進的路由算法最大持續時間最小角的GPSR（Maxduration-Minangle GPSR，MM-GPSR）進行了對比。為了使仿真能反映更加真實的場景，本文使用OpenStreetMap 在北京市提取了一個2 000 m*3 000 m 的仿真區域，然后使用SUMO 將地圖文件生成城市道路文件，如圖7 所示，并在城市主干道路中生成車輛的移動軌跡文件，以便在后續仿真中使用。

圖7 城市道路圖Fig.7 City road map

NS3 網絡模擬器用于路由實現和性能評估，實驗中仿真參數的設置如表1所示。

表1 參數設置Tab.1 Parameter settings

4.2 評價指標

為了量化路由算法的性能，本文以下面三個評價指標對路由算法的性能進行分析，每個指標都進行了10 次實驗，取10次實驗的平均值以消除誤差。

4.2.1 數據包到達率

數據包到達率（Packet Delivery Ratio，PDR）：仿真時間內網絡中目的車輛接收到的數據包的總數Prcvd與源車輛發送的數據包的總數的Psend的比值，計算式如式（6）所示。

4.2.2 平均端到端時延

平均端到端時延（Average end To end Delay，ATD）：數據包i從源車輛到目的車輛所經過的時間Ti與目的車輛接收到的數據包總數的比值，計算式如式（7）所示。

4.2.3 平均端到端跳數

平均端到端跳數（Average end-To-end Hops，ATH）：數據包i從源車輛到目的車輛所經過的跳數xi與目的車輛接收到的數據包總數的比值，計算式如式（8）所示。

4.3 結果分析

圖8（a）中源車輛的發送速率為每秒4 個數據包，在這樣的數據包發送速率下比較了在道路中不同車輛數情況下，通過三種不同路由算法到達目的車輛的數據包到達率。從圖8（a）中可以看出，隨著道路中車輛數的增加，三種路由算法的數據包到達率都呈上升趨勢。本文所提路由算法（VGPE）因為規劃了數據傳播路徑，并優化了數據在十字路口的轉發，所以本文算法在道路中不同車輛數情況下，數據包到達率皆優于對比算法。在車輛數為400 時，本文算法的數據包到達率相較GPSR 路由算法提高了13.81%，相較MM-GPSR 路由算法提高了9.64%。

圖8（b）是在每秒8 個數據包的發送速率下，道路中不同車輛數的數據包到達率。從圖8 中可以看出，圖（b）三種路由算法的數據包到達率的趨勢和圖（a）基本相同，但在相同車輛數情況下，圖（b）與圖（a）相比，同一路由算法的數據包到達率有所下降，本文所提路由算法（VGPE）優勢減弱。在車輛數為400 時，本文算法的數據包到達率相較GPSR 路由算法提高了9.86%，相較MM-GPSR路由算法提高了7.35%。

圖8（c）是在每秒16個數據包的發送速率下，道路中不同車輛數的數據包到達率。從圖8（c）中可以看出，因為源車輛每秒發送的數據包數大于車輛一次緩存的數據包數量，必然有些數據包會因為緩沖區溢出而被丟棄，所以三種路由算法的數據包到達率都有大幅的降低。因為本文路由算法要進行路徑探索，在發送數據包過程中還要對路徑進行調整，所以在每秒16 個數據包的發送速率下，本文路由算法的數據包到達率低于GPSR 路由算法。綜上可以得出，本文路由算法適用于在每秒數據包發送速率低于車輛緩存數量的情況。

圖9（a）是在每秒發送4個數據包的發包速率和改變道路中車輛數情況下，通過三種不同路由算法到達目的車輛的平均端到端時延。由圖9（a）中可以看出，隨著道路中車輛數的增加，發送車輛更容易找到下一跳車輛進行轉發，所以三種路由算法的平均端到端時延都呈下降趨勢。但GPSR 路由算法由于可能將數據包發送到遠離目的車輛的路段從而進入恢復模式，增加了時延，所以在三個算法中GPSR 路由算法的時延最多。在車輛數為400 時，本文路由算法的時延相較GPSR、MM-GPSR降低了61.91%、27.28%。

圖9（b）、（c）是在每秒發送8、16 個數據包的發包速率和改變道路中車輛數情況下，通過三種不同路由算法到達目的車輛的平均端到端時延。計算端到端時延是通過目的車輛收到數據包的時延除以收到數據包的個數來求得的，因為過快的發包速率而被丟棄的溢出緩沖區的數據包無法到達目的車輛，因而不會被計入收到的數據包個數中，所以從圖9（b）、（c）中可以看出，數據包的發送速率對數據包的端到端時延影響并不大，三種路由算法的平局端到端時延總體趨勢不變。在圖9（b）中，車輛數為400時，本文路由算法的時延相較GPSR、MM-GPSR 降低了30.77%、14.29%。在圖9（c）中，車輛數為400 時，本文路由算法的時延相較GPSR、MM-GPSR 降低了22.22%、3.92%。

圖10（a）、（b）、（c）分別是以每秒4、8、16 個數據包的發送速率，并在道路中不同車輛數情況下，通過三種不同路由算法到達目的車輛的平均端到端跳數。從圖10 中可以看出，不同的數據包發送速率對平均端到端跳數影響不是很大，因為本文路由算法對各種可能出現冗余跳數的情況進行了優化，所以在不同數據包發送速率和不同車輛數情況下，本文算法的轉發跳數相對來說是最少的。GPSR 路由算法由于在恢復模式下轉發跳數的不確定性，所以平均端到端跳數不穩定。

圖8 不同數據包發送速率條件下包到達率比較Fig.8 Comparison of packet arrival rates under different data packet transmission rate conditions

圖9 不同數據包發送速率條件下平均端到端時延比較Fig.9 Comparison of average end-to-end delays under different data packet transmission rate conditions

5 結語

本文分析了城市環境的特殊性，以及傳統的基于地理位置轉發的貪婪路由算法在城市環境中的局限性，提出了基于路徑探索的貪婪路由算法。通過將人工蜂群算法運用到城市道路中選擇路由路徑，優化轉發車輛的選擇方法，使得路由算法能感知道路中車輛的變化，并作出相應的調整。實驗結果表明，本文提出的路由算法相較于傳統的和其他改進的地理位置路由算法具有較好的性能。

但是本文的路由算法應用在相距較遠的車輛之間進行數據路由時，會因為道路的復雜性使得路徑探索的復雜度和時延增加，從而造成整體路由性能下降。將路邊靜態節點作為中繼，轉發數據包，是克服車輛之間數據轉發距離過長而造成的性能下降的可行方法，接下來可在這些方面進行研究。