一種軟件定義車載自組織網絡的QoS 路由算法

杜欣欣，胡曉輝，趙佳楠

（蘭州交通大學電子與信息工程學院，蘭州 730070）

0 概述

車載自組織網絡（Vehicular Ad-Hoc Network，VANET）是以車輛為節點的特殊移動自組織網絡（Mobile Ad-Hoc Network，MANET）［1］。VANET 高動態特性會導致拓撲頻繁變化和網絡碎片，使當前建立的相關QoS 指標變化迅速，所選的最佳路由會變得低效甚至不可行。而基于VANET 的經典路由協議（AODV、OLSR 等）主要集中在最小化所提供路徑的跳數上［2］，不同服務業務QoS 保障困難，如消防、救護車、警車緊急消息和視頻流媒體等對傳輸時延、抖動、分組丟失率有嚴格制約，若約束無法得到有效的保證，可能會影響用戶的視覺體驗和聽覺體驗，甚至會造成重大交通事故。受多個QoS 約束搜索可行路由被定義為NP-Hard 問題，即無法在時間域內求解多項式問題。因此，需要合理的方案解決該問題。

軟件定義網絡（Software-Defined Network，SDN）是一種新興的網絡架構，它在物理上解耦控制平面和數據平面，在邏輯上通過抽象網絡基礎設施，將控制和智能決策集中在控制器中［3］，能更有效地實現網絡資源分配和調度。因此，將SDN 應用于VANET以簡化應用功能，協調路邊基礎設施（RSU），建立可靠和高效的V2V 和V2I 通信路由，并為VANET 中QoS 優化提供了全新的解決方案。

目前，VANET 中QoS 路由主要基于QoS 參數，由源車輛主動或按需尋找下一跳直至目的車輛。文獻［4］利用車輛移動速度、密度和衰落條件提出一種基于移動感知區域的VANET 蟻群優化路由算法。使用蟻群算法來尋找網絡中節點之間的多跳路由，以幫助解決鏈路故障。為了實現可擴展性，將網絡劃分為多個區域并采用主動方式來查找區域內的路由；對于區域間的路由則使用存儲在每個區域的本地信息來進行查找，從而減少廣播和擁塞。但由于使用主動的方法來更新域內路由表，導致了較高的路由控制開銷。文獻［5］將勢態感知模型和蟻群機制相結合，提出一種基于勢態感知的車輛自組織網絡QoS 路由算法，該算法的目標是尋找受多種QoS約束的最佳路徑。為了降低計算最優路由所帶來的風險，利用情景感知級別和蟻群算法制定了相關的對策，以保證數據的可靠傳輸。但當網絡密度增加時，已建立的路由可能會變得更長，降低了路由的可靠性。如果未發送數據包的一個片段，則會丟棄整個數據包從而造成算法的丟包率較高。文獻［6］提出一種基于OLSR 協議的機制，以建立穩定和可持續的移動自組網。在該機制中通過計算鄰節點的相對移動度，之后將其代入到穩定性函數中，以穩定性函數作為主要路徑選擇準則從而選擇穩定和可持續的多點中繼。該機制在多QoS 約束下減少了多點中繼的路由表重計算過程，但并未考慮負載平衡和節點剩余能量等指標。文獻［7］提出一種基于適應度的AODV 路由協議，在車輛節點組成網絡后，通過廣播Hello 報文發現源節點和目的節點之間的路由。然后，結合QoS 適度值和歐幾里得距離來確定穩定的下一跳節點，但在路由維護階段依舊采用了AODV 原有維護更新方式，這將消耗大量的能量。文獻［8］提出一種基于QoS 約束、不信任值和移動約束的路由協議。該協議利用QoS 要求、不信任值和移動性約束參數來計算每個車輛的QoS 值，基于此值來選擇傳輸路徑，保證了鏈路的穩定性。但VANET 的仿真場景過于簡單，缺少二維復雜路況，不適用于真實場景。

SDN 控制器可以利用車輛數據來定位轉發決策，然后確定轉發信息分組和到達目的地的最合適路由。文獻［9］實現了AODV 在SDN-VANET 中的應用，并且基于最基本的QoS 指標對其性能進行了分析，證明了SDN 架構具有一定的優勢。但所選QoS 指標過于單一，不符合實際業務所需的QoS。文獻［10］采用了集中式控制器來高效尋找數據報文的有效傳遞路徑。但是，由于所提出的解決方案依賴復雜的預測機制來更新網絡拓撲，導致計算延遲大，吞吐量低，不適用于密集車輛情況。而文獻［11］采用另一種動態更新車輛拓撲的方法，減少了對路由發現的泛洪需求。該算法依賴信標消息不斷更新和跟蹤拓撲的動態變化，并使用馬爾科夫鏈模型來確定路由的優先級。但由于算法復雜度高，在高密度環境下擴展性較差。文獻［12］提出一種基于霧計算的軟件定義車載自組織網絡新型節能多播路由協議。此外，還提出了一種基于優先級的調度算法和分類算法，用于在對組播請求進行分類后根據其應用類型和期限約束對組播請求進行調度，地理分區概念的應用減少了SDN 控制器的負載開銷。該協議有效減少了平均端到端延遲、歸一化開銷負載和多播能量消耗。但該協議也存在一定的局限性，一方面是沒有考慮到車輛的安全驗證，另一方面是車輛的快速接入和斷開造成多播協議的開銷較大。

本文將SDN 和VANET 相結合，構造SDN-VANET異構混合網絡，并提出一種應用于SDN-VANET 架構的QoS 路由算法，利用SDN 的高靈活性、可編程性等優勢保障業務傳輸QoS。該算法在業務調度階段，SDN控制器優先調度傳輸截止時間少的車輛業務，保障緊急業務傳輸。然后在路由選擇階段，基于蛙跳算法設計出自適應混合中繼選擇算法。通過設計與QoS 約束相匹配的適應度函數來衡量轉發路徑的優劣，并能根據當前網絡狀態自適應地更新改進轉發策略。最后在路由維護階段設置備選鏈路機制和資源消耗閾值，保障業務傳輸的QoS。

1 系統模型

1.1 SDN-VANET 架構

SDN 控制器為VANET 路由策略提供了更好的適應性和靈活性，在SDN 控制器集中調節下可以實現車輛數據統籌調配，以改善管理車與車（Vehicle to Vehicle，V2V）和車與基礎設施（Vehicle to Infrastructure，V2I）通 信。SDN-VANET 架構如圖1所示。

圖1 SDN-VANET 架構Fig.1 SDN-VANET architecture

SDN-VANET 架構是混合了IEEE 802.11p、蜂窩網絡和SDN 的重構體系，利用不同通信技術完成WAVE 協議族的控制數據平面消息轉發［13］。SDNVANET 主要包括應用層、控制層和數據層。

應用層：通過北向接口向下層提供關系數據庫、車載應用、身份認證信息、環境服務和安全服務等商業服務應用。

控制層：SDN 控制器收集車輛信息（如車輛位置、速度）、網絡拓撲信息和交通流信息，并通過南向接口進行流表項的更新，下達路由轉發、拓撲管理和交換管理等命令。

數據層：由車輛節點、RSU 和基站組成。RSU 和基站為車輛與SDN 控制器通信提供了4G 網絡和WAVE 無線網絡等異構接入方式。車輛裝載具有V2V 和V2I 通信功能的車載單元（On Board Unit，OBU），定期發送通知到SDN 控制器以增強網絡配置并接收來自SDN 控制器控制消息依此來執行數據包的轉發行為。具體模型如下：

1）每個RSU 負責一個區域，且每個RSU 之間互不沖突。

2）當車輛進入一個新區域時，能自動發起對應區域RSU 的通信響應并通過GPS 定期向RSU 匯報自身坐標、速度和加速度等動力學信息。車輛與RSU 通過IEEE 802.11p 協議交換信息。RSU 僅傳輸SDN 控制器下達的流表項命令，無法幫助車輛轉發數據包。

3）RSU 能夠感知本區域所有入網車輛，并動態存儲維護一個車輛信息表，一旦車輛離開該區域，RSU 將自動刪除離開車輛的信息。

1.2 路徑參數

為了實現路由在VANET 中的執行過程，以加權間接圖G（V，E）形式對車輛節點構成的組網拓撲進行建模，其中V代表車輛節點，E是網絡中車輛節點之間路徑的集合［14］。對于任意兩個節點i和j之間的路徑，使用ei，j，e∈E表示。在路徑ei，j中，為了方便對網絡參數進行描述和研究，路徑參數選擇帶寬Bi，j、時 延Ti，j、抖 動Di，j和傳輸能量消耗Ci，j。除考慮帶寬、時延和抖動等基本QoS 因素外，還特別考慮了傳輸能量因素。隨著電動汽車的發展趨勢越來越明顯，傳輸能量也應是考慮的參數之一。

車輛節點i和j之間的路徑傳輸能量消耗定義為：

其中：Cs是轉發數據所需能量；Cr接收數據所需能量。

當兩個車輛節點需轉發數據量為k，距離為l時，Cs定義為［15］：

其中：Eelc為電耗能參數；l0為兩個節點之間的傳輸距離閾值；ε1為放大參數。

當接收數據量為k時，Cr(k)定義為：

1.3 約束條件

在某個時隙內，組網中可能存在多個車輛同時需要轉發多個數據包數據的情況，為了避免網絡阻塞和問題路由，在設計協議時需要對數據包轉發條件加以限制。其次還需對剩余帶寬及時進行校正，確保下一個車輛業務也能有效傳輸。

約束1如果數據從節點i發送到j，變量λ將取值1；否則，其值將為0。

約束2當流從節點i發送到節點j時，不得從節點j回流到節點i，用于避免循環。

約束3從節點i發送到節點j的數據流必須小于或等于從節點i到j的鏈路剩余帶寬。其中bi，j為節點i和j鏈路剩余帶寬。

約束4為了提高選擇最佳路徑時的準確性，組網中節點i和j之間的鏈路的剩余帶寬必須在執行轉發或丟棄動作后進行更新［16］。bi，j的計算如式（7）所示：

2 基于SDN-VANET 的QoS 路由算法

2.1 協議概述

車輛節點i進入RSU 控制區域后，向RSU 提交業務請求消息Si，業務請求消息Si主要包含：源節點（Source_IP Address），目的節點（Destination_IP Address），傳輸的信息量（Size），截止日期（Dealine），QoS 約束信息。業務請求消息Si格式如圖2 所示。

圖2 業務請求消息格式Fig.2 Service request message format

在圖2 中，Type 為消息類型，數值定義為1 表 示業務請求消息，Reserved 為保留位，為后續RSU 設置優先級而預留，B、T、D、C則代表此項業務所需帶寬BQoS、時延TQoS、抖動DQoS以及能耗CQoS。

RSU 根據截止日期在Reserved 中為其添加優先級Pi，其中Pi與截止時間成負相關，即截止日期越小優先級越高。之后RSU 向SDN 提交Si，Si將進入等待隊列W_queue 等待調度。SDN 控制器根據Pi調度隊列中的請求，完成車輛節點的業務請求，為其尋找合適的節點進行轉發。車輛業務申請流程如圖3 所示。

圖3 車輛業務申請流程Fig.3 Procedure of vehicle service application

協議主要分為鄰居發現、路由選擇和路由維護3 個部分。

1）鄰居發現

車輛節點定時向RSU 發送Hello 包，匯報車輛自身基本信息。當RSU 收到Hello 包后，會將包信息加入到該區域的車輛信息表中，根據車輛的通信范圍尋找該車輛的鄰居節點，并寫入該區域的車輛信息表。然后RSU 回傳一個包含該車輛地理信息以及車輛鄰居節點信息的AckHello 包。車輛也可以根據回傳的AckHello 包信息判斷是否自己脫離了該RSU控制區域，如果脫離了該區域RSU，車輛將重新發送Hello 包直到下一個RSU 返回AckHello 包。RSU 所維護的車輛信息表包括以下字段：車輛ID（Vehicle ID），鄰居節點ID（Neighbor），下一跳（Next hop），flag 標記（Flag），車輛是否被選擇為中繼轉發節點和不轉發列表（Not forwarding）。不轉發列表定義為當且僅當車輛被選擇為中繼節點且有意義時，將執行SDN 控制器下達的不轉發命令，不轉發列表中車輛發來的所有數據包。車輛信息表結構如表1 所示。

表1 RSU 車輛信息表結構Table 1 RSU vehicle information table structure

2）路由選擇

若源節點所傳輸數據的目的節點為其鄰居節點，則直接進行傳輸，否則SDN 控制器根據隨機點路移動模型和源節點所提出業務請求的截止時間，預測在該時限內各車輛位置，確定符合截止日期約束的備選中繼車輛。在中繼選擇過程中為滿足不同業務的QoS 約束指標，提出一種基于改進的自適應混合蛙跳中繼選擇算法（Adaptive Hybrid Shuffled Frog Leading Algorithm，AH-SFLA）。在保障各約束的同時，以最小化QoS 資源將數據包從源車輛傳輸到目的車輛。

3）路由維護

若車輛出現異常情況即無法進行通信，此時SDN 控制器根據AH-SFLA 的計算進行次優替換。次優路徑替換的首尾是故障車輛的前驅和后繼，這樣有利于提高計算效率，降低控制器運算開銷。同時為避免車輛被過度選擇為中繼，設置車輛資源消耗變換率閾值，來動態實現車輛資源維護［17］。若車輛i的初始資源為Qi，在被選為中繼節點后帶寬資源變為，當節點資源變化率滿足以下不等關系式時：

即表明車輛i的資源消耗變化達到了設定的閾值R。這時車輛i向SDN 控制器申請重路由請求，SDN 控制器收到重路由請求后，根據AH-SFLA 算法重新選擇一條通信鏈路。這種動態路由維護的方式可以減少車輛被過度使用，及網絡故障問題發生的概率。

2.2 基于改進的自適應蛙跳中繼節點選擇算法

蛙跳算法是進化計算領域一種新興有效亞啟發式、結合遺傳學模因演算的群體進化算法，該算法擁有優良高效的計算性能和解空間能力［18］。為了找到多QoS 約束下的最優路徑，本文提出了AH-SFLA 算法，該算法結合當前網絡狀態自適應地動態搜尋最優解。主要步驟如下：

步驟1種群編碼。設有N個車輛節點，dmax為種群中節點最大出度，則車輛節點的基因維數L定義如式（9）所示：

通過采用二進制編碼來表示節點的基因位，即可選路徑。若車輛節點出度為1，該節點可選下一跳僅有1 個，用一位二進制比特位0 對該路徑進行編碼；若車輛節點通信范圍內可選擇作為下一跳的節點有4 個，用兩個二進制比特位00、01、10、11 來表示4 個可選的傳輸路徑，并以此類推。如果車輛節點的出度超過了基因維數，則采取整取余的方法對多出的維數進行編碼，并對余數編碼作特殊標記以便區分。如果車輛節點編碼數小于基因維數，則剩下的基因位將忽略不計。

步驟2適度函數構造。AH-SFLA 在進化搜索中主要依賴種群內部環境條件，以適度值為基準進行搜索和改進［19］。AH-SFLA 適應函數是基于QoS約束加權和之比而制定的，該函數是用于量化約束確定傳輸最優路徑，保障各業務QoS 同時降低傳輸能量消耗。因此，適度函數如式（10）所示：

其中：μb、μc、μt和μd表示相應指標的權重因子，即不同的業務需求，對不同的約束所占比重有所不同。例如視頻流的業務需求，μb和μt的權重因子大于其他業務需求。

步驟3初始化種群。滿足通信范圍和截止日期約束的N個車輛節點組成初始種群X={X1，X2，…，XN}，在約束D維問題的解空間中第i個節點表示Xi={xi1，xi2，…，xiD}。初始種群確定以后，將種群N內的每個節點按照式（10）計算適度值并降序排序，且記錄種群中適度值最小的節點為Xg_best。

步驟4子種群劃分。初始種群劃為J個子種群，并將第1 個節點分配給子種群1，第2 個節點分配給子種群2，第J個節點分配給子種群J，第J+1 個節點分配給子種群1，以此類推直到每個子種群內包含I個節點，初始種群與子種群關系滿足N=I×J。同時需記錄子種群中適度值最小的節點Xf_best和適度值最大節點Xf_worst。

步驟5局部搜索。局部搜索僅對子種群內適度值最大的車輛節點Xf_worst進行進化更新策略，更新策略如式（11）和式（12）所示：

其中：rand 為0～1 的隨機小數；Ri為移動步長，滿足-Rmax≤Ri≤Rmax約 束，Rmax為其移動最大步長；若，則用更新后的取代當前子種群最差節點Xf_worst，否則以概率pm動態進行變異更新。pm由SDN 控制器依據當前網絡狀態下的帶寬可用率、數據堆積率、車輛節點穩定性以及對應影響因子構成。更新策略如式（13）、式（14）和式（15）所示：

對于變異更新操作，在正常情況下根據數據流的性能要求指標采取相應的變異方案，產生對應的個體。若更新過后的適應度仍沒有取得改進，則按式（16）隨機生成新的個體并替換。

其中：max 是當前網絡狀態下隨機最大值；min 為隨機最小值。

步驟6全局搜索。局部搜索完成后，將重新混合構成的下一代種群記錄適度值最小車輛節點Xg_best。判斷算法是否達到最大迭代次數G，若滿足則結束搜索并輸出；否則將繼續進行搜索。

2.3 AH-SFLA 實現

為了更好地適應VANET 動態變化，AH-SFLA會根據當前網絡狀態對轉發路徑進行動態調整更新，這主要是通過局部搜索中變異更新操作產生當前網絡狀態下的可選路徑，根據適度值選擇轉發代價較小路徑轉發，達到自適應目的。算法基本流程為首先對VANET 中車輛節點進行基因編碼，通過車輛移動模型和數據包截止時間約束確定初始種群，根據式（10）計算適度值，進行子種群劃分。SDN 控制器基于當前網絡狀態對子種群的最差個體進行動態變異更新，并對更新后的子種群混合再次計算適度值選出新種群最優，這樣的動態更新策略能更好地自適應VANET 的動態變化，最大化地利用網絡資源，保障各業務的QoS。算法偽代碼如下：

算法1AH-SFLA 中繼節點選擇算法

3 仿真實驗與性能分析

在仿真實驗中，聯合SUMO［20］、Mininet-wifi 和POX［21］來仿真SDN-VANET 環境［22］。城市道路模擬是通過Openstreetmap 和SUMO 創建的1 500 m×1 000 m甘肅省蘭州市街道區域，如圖4所示。而POX和Mininetwifi 則實現SDN 控制器和車輛節點的模擬和配置，從而建立SDN-VANET 的仿真環境。環境參數配置表如表2 所示。

圖4 蘭州市道路拓撲Fig.4 Lanzhou city road topology

表2 環境參數配置Table 2 Environmental parameter configuration

為了證明本文路由協議的有效性和SDN 體系架構優越性，將所提出的路由協議和單播路由協議IGA［23］、IICSFLA［24］在不同場景下進行對比。IGA 是基于遺傳算法而設計的多約束單播路由協議，該協議在計算適度函數時引入一種新的懲罰函數和約束權重，加快了種群“優勝劣汰”的速度。而IICSFLA是結合免疫算法和蛙跳算法的路由協議，該協議的更新策略是通過克隆變異種群最優節點完成的。IGA 的參數配置如表3 所示。

表3 IGA 參數配置Table 3 IGA parameter configuration

模擬實驗中使用的性能指標如下：

平均端到端延遲［25］：指數據包從源傳輸到目的地所需的平均時間延遲，包括所有類型的延遲，如排隊延遲、傳送延遲以及路由發現緩沖延遲。

丟包率：是指測試中所丟失數據包數量占所發送數據組的比率。

標準化路由開銷［26］：發送控制數據包與成功接收數據包之間的比率。該度量不考慮控制器的控制開銷。

場景1研究車輛密度對AH-SFLA、IGA 和IICSFLA 性能的影響，此場景的參數如表4 所示。

表4 場景1 參數配置Table 4 Scenario 1 parameter configuration

圖5 為不同網絡密度對AH-SFLA、IGA 和IICSFLA 協議的性能度量。圖5（a）顯示了AHSFLA、IGA 和IICSFLA 的平均E2E 延遲。從圖中可以明顯看出，AH-SFLA 的平均E2E 延遲要低于IGA和IICFLA，相比IGA 和IICFLA，AH-SFLA 分別平均提高了57.74%和46.6%。SDN 控制器根據中繼節點選擇算法計算最佳傳輸路徑，以此為依據更新流表項。車輛節點無需啟動泛洪機制尋找下一跳，而通過更新后的流表完成轉發操作。圖5（b）顯示了3 種路由協議的丟包率與車輛密度之間的關系。AHSFLA 比IGA 和IICFLA 的丟包率平均降低了29.9%和18.6%。隨車輛密度的增加，3 種路由協議的丟包率都有所下降，這是因為在車輛密度較低時車輛間的連通性較差，但隨著車輛節點的增多，車輛節點會面機遇的概率增加，降低了空路由的概率。在車輛密度稀疏時AH-SFLA 協議的丟包率高于其他兩種路由協議，原因是數據包轉發受到了流表更新的限制，但隨著車輛密度的增加，SDN 控制器可以靈活地選擇最佳路由，使得數據包受流表限制減少，因此車輛間的數據傳輸更加可靠。圖5（c）描述了3 種路由協議車輛密度與標準化路由開銷之間的關系。相比其他兩個協議，AH-SFLA 的標準化路由開銷分別提高了36.93%和27.2%。在AH-SFLA 協議中，SDN 控制器計算出最佳路徑下發更新流表，以在指定路徑上的節點建立車輛間通信。此外，由于在確定路徑時考慮了穩定性參數，減少了重復路由通信，車輛間通信將變得更加穩定。IGA 和IICSFLA 協議在缺乏網絡狀況全局概覽的情況下，通過貪婪和泛洪路由技術進行通信，標準化路由開銷隨著車輛數量的增加而顯著增加。

圖5 不同車輛密度下IGA，IICSFLA 和AH-SFLA 的性能指標Fig.5 Performance indexs of IGA，IICSFLA and AHSFLA with different vehicle densities

場景2研究車速對 AH-SFLA、IGA 和IICSFLA 性能影響，在不同最大車速下根據評價指標來證明AH-SFLA 的有效性。此場景的參數配置如表5 所示。

表5 場景2 參數配置Table 5 Scenario 2 parameter configuration

圖6展示了不同速度下AH-SFLA、IGA和IICSFLA協議的性能指標。

圖6 不同車速下IGA，IICSFLA 和AH-SFLA 的性能指標Fig.6 Performance indexs of IGA，IICSFLA and AHSFLA with different speed

圖6（a）所示為AH-SFLA、IGA 和IICSFLA 的平均E2E 延遲。通過增加車輛速度，車輛間通信鏈路斷開更加頻繁，尋找新路徑的過程將增加延遲。然而AH-SFLA 的平均E2E 延遲優于IGA 和IICSFLA，因為AH-SFLA 協議可以通過SDN 控制器掌握全局拓撲信息，能及時校正更新流表項從而延遲較低。如圖6（b）所示，AH-SFLA 協議丟包率分別優于IGA的31.1%和IICSFLA 的21.32%。在高動態拓撲變化情況下，如何保證在多QoS 約束下尋找最優路徑點，SDN 控制器的優勢顯而易見。如圖6（c）所示，當車輛速度從5 m/s 逐漸増長到30 m/s 時，網絡中鏈路斷裂次數增多，3 個協議的標準化路由開銷隨之增加。車輛移動速度増加，導致IGA 和IICSFLA 協議在建立路由時極易發生斷裂，需要發送大量控制報文來進行路由的重新建立。而AH-SFLA 具有QoS 路由維護機制，在車輛通信出現斷裂時能及時恢復，比其他兩種協議在標準化路由開銷方面有著較好的性能表現。

4 結束語

VANET 是一種特殊的MANET，具有節點高速移動、拓撲動態變化的特點，但也導致QoS 無法得到有效保障。針對該問題，本文將SDN 與VANET 相結合，提出一種適用于SDN-VANET 的QoS 路由算法。SDN 控制器根據全局信息，計算出一條符合業務QoS 需求且轉發代價最小的解作為轉發路徑。同時根據VANET 動態變化，通過適度函數自適應地調整轉發路徑。仿真結果表明，AH-SFLA 協議在平均E2E 延遲、丟包率、標準化路由開銷方面都有所提高，在保證QoS 上具有一定的優勢。下一步將引入博弈理論對VANET 中因資源有限而出現的自私車輛進行分析研究，并結合演化博弈，設計有效的懲罰機制促使自私車輛轉發數據包，降低協議的丟包率。