一種軟件定義車載自組織網(wǎng)絡(luò)的QoS 路由算法

杜欣欣，胡曉輝，趙佳楠

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

0 概述

車載自組織網(wǎng)絡(luò)（Vehicular Ad-Hoc Network，VANET）是以車輛為節(jié)點(diǎn)的特殊移動自組織網(wǎng)絡(luò)（Mobile Ad-Hoc Network，MANET）［1］。VANET 高動態(tài)特性會導(dǎo)致拓?fù)漕l繁變化和網(wǎng)絡(luò)碎片，使當(dāng)前建立的相關(guān)QoS 指標(biāo)變化迅速，所選的最佳路由會變得低效甚至不可行。而基于VANET 的經(jīng)典路由協(xié)議（AODV、OLSR 等）主要集中在最小化所提供路徑的跳數(shù)上［2］，不同服務(wù)業(yè)務(wù)QoS 保障困難，如消防、救護(hù)車、警車緊急消息和視頻流媒體等對傳輸時延、抖動、分組丟失率有嚴(yán)格制約，若約束無法得到有效的保證，可能會影響用戶的視覺體驗和聽覺體驗，甚至?xí)斐芍卮蠼煌ㄊ鹿省Ｊ芏鄠€QoS 約束搜索可行路由被定義為NP-Hard 問題，即無法在時間域內(nèi)求解多項式問題。因此，需要合理的方案解決該問題。

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

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

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

本文將SDN 和VANET 相結(jié)合，構(gòu)造SDN-VANET異構(gòu)混合網(wǎng)絡(luò)，并提出一種應(yīng)用于SDN-VANET 架構(gòu)的QoS 路由算法，利用SDN 的高靈活性、可編程性等優(yōu)勢保障業(yè)務(wù)傳輸QoS。該算法在業(yè)務(wù)調(diào)度階段，SDN控制器優(yōu)先調(diào)度傳輸截止時間少的車輛業(yè)務(wù)，保障緊急業(yè)務(wù)傳輸。然后在路由選擇階段，基于蛙跳算法設(shè)計出自適應(yīng)混合中繼選擇算法。通過設(shè)計與QoS 約束相匹配的適應(yīng)度函數(shù)來衡量轉(zhuǎn)發(fā)路徑的優(yōu)劣，并能根據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)自適應(yīng)地更新改進(jìn)轉(zhuǎn)發(fā)策略。最后在路由維護(hù)階段設(shè)置備選鏈路機(jī)制和資源消耗閾值，保障業(yè)務(wù)傳輸?shù)腝oS。

1 系統(tǒng)模型

1.1 SDN-VANET 架構(gòu)

SDN 控制器為VANET 路由策略提供了更好的適應(yīng)性和靈活性，在SDN 控制器集中調(diào)節(jié)下可以實現(xiàn)車輛數(shù)據(jù)統(tǒng)籌調(diào)配，以改善管理車與車（Vehicle to Vehicle，V2V）和車與基礎(chǔ)設(shè)施（Vehicle to Infrastructure，V2I）通 信。SDN-VANET 架構(gòu)如圖1所示。

圖1 SDN-VANET 架構(gòu)Fig.1 SDN-VANET architecture

SDN-VANET 架構(gòu)是混合了IEEE 802.11p、蜂窩網(wǎng)絡(luò)和SDN 的重構(gòu)體系，利用不同通信技術(shù)完成WAVE 協(xié)議族的控制數(shù)據(jù)平面消息轉(zhuǎn)發(fā)［13］。SDNVANET 主要包括應(yīng)用層、控制層和數(shù)據(jù)層。

應(yīng)用層：通過北向接口向下層提供關(guān)系數(shù)據(jù)庫、車載應(yīng)用、身份認(rèn)證信息、環(huán)境服務(wù)和安全服務(wù)等商業(yè)服務(wù)應(yīng)用。

控制層：SDN 控制器收集車輛信息（如車輛位置、速度）、網(wǎng)絡(luò)拓?fù)湫畔⒑徒煌餍畔?，并通過南向接口進(jìn)行流表項的更新，下達(dá)路由轉(zhuǎn)發(fā)、拓?fù)涔芾砗徒粨Q管理等命令。

數(shù)據(jù)層：由車輛節(jié)點(diǎn)、RSU 和基站組成。RSU 和基站為車輛與SDN 控制器通信提供了4G 網(wǎng)絡(luò)和WAVE 無線網(wǎng)絡(luò)等異構(gòu)接入方式。車輛裝載具有V2V 和V2I 通信功能的車載單元（On Board Unit，OBU），定期發(fā)送通知到SDN 控制器以增強(qiáng)網(wǎng)絡(luò)配置并接收來自SDN 控制器控制消息依此來執(zhí)行數(shù)據(jù)包的轉(zhuǎn)發(fā)行為。具體模型如下：

1）每個RSU 負(fù)責(zé)一個區(qū)域，且每個RSU 之間互不沖突。

2）當(dāng)車輛進(jìn)入一個新區(qū)域時，能自動發(fā)起對應(yīng)區(qū)域RSU 的通信響應(yīng)并通過GPS 定期向RSU 匯報自身坐標(biāo)、速度和加速度等動力學(xué)信息。車輛與RSU 通過IEEE 802.11p 協(xié)議交換信息。RSU 僅傳輸SDN 控制器下達(dá)的流表項命令，無法幫助車輛轉(zhuǎn)發(fā)數(shù)據(jù)包。

3）RSU 能夠感知本區(qū)域所有入網(wǎng)車輛，并動態(tài)存儲維護(hù)一個車輛信息表，一旦車輛離開該區(qū)域，RSU 將自動刪除離開車輛的信息。

1.2 路徑參數(shù)

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

車輛節(jié)點(diǎn)i和j之間的路徑傳輸能量消耗定義為：

其中：Cs是轉(zhuǎn)發(fā)數(shù)據(jù)所需能量；Cr接收數(shù)據(jù)所需能量。

當(dāng)兩個車輛節(jié)點(diǎn)需轉(zhuǎn)發(fā)數(shù)據(jù)量為k，距離為l時，Cs定義為［15］：

其中：Eelc為電耗能參數(shù)；l0為兩個節(jié)點(diǎn)之間的傳輸距離閾值；ε1為放大參數(shù)。

當(dāng)接收數(shù)據(jù)量為k時，Cr(k)定義為：

1.3 約束條件

在某個時隙內(nèi)，組網(wǎng)中可能存在多個車輛同時需要轉(zhuǎn)發(fā)多個數(shù)據(jù)包數(shù)據(jù)的情況，為了避免網(wǎng)絡(luò)阻塞和問題路由，在設(shè)計協(xié)議時需要對數(shù)據(jù)包轉(zhuǎn)發(fā)條件加以限制。其次還需對剩余帶寬及時進(jìn)行校正，確保下一個車輛業(yè)務(wù)也能有效傳輸。

約束1如果數(shù)據(jù)從節(jié)點(diǎn)i發(fā)送到j(luò)，變量λ將取值1；否則，其值將為0。

約束2當(dāng)流從節(jié)點(diǎn)i發(fā)送到節(jié)點(diǎn)j時，不得從節(jié)點(diǎn)j回流到節(jié)點(diǎn)i，用于避免循環(huán)。

約束3從節(jié)點(diǎn)i發(fā)送到節(jié)點(diǎn)j的數(shù)據(jù)流必須小于或等于從節(jié)點(diǎn)i到j(luò)的鏈路剩余帶寬。其中bi，j為節(jié)點(diǎn)i和j鏈路剩余帶寬。

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

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

2.1 協(xié)議概述

車輛節(jié)點(diǎn)i進(jìn)入RSU 控制區(qū)域后，向RSU 提交業(yè)務(wù)請求消息Si，業(yè)務(wù)請求消息Si主要包含：源節(jié)點(diǎn)（Source_IP Address），目的節(jié)點(diǎn)（Destination_IP Address），傳輸?shù)男畔⒘浚⊿ize），截止日期（Dealine），QoS 約束信息。業(yè)務(wù)請求消息Si格式如圖2 所示。

圖2 業(yè)務(wù)請求消息格式Fig.2 Service request message format

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

RSU 根據(jù)截止日期在Reserved 中為其添加優(yōu)先級Pi，其中Pi與截止時間成負(fù)相關(guān)，即截止日期越小優(yōu)先級越高。之后RSU 向SDN 提交Si，Si將進(jìn)入等待隊列W_queue 等待調(diào)度。SDN 控制器根據(jù)Pi調(diào)度隊列中的請求，完成車輛節(jié)點(diǎn)的業(yè)務(wù)請求，為其尋找合適的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。車輛業(yè)務(wù)申請流程如圖3 所示。

圖3 車輛業(yè)務(wù)申請流程Fig.3 Procedure of vehicle service application

協(xié)議主要分為鄰居發(fā)現(xiàn)、路由選擇和路由維護(hù)3 個部分。

1）鄰居發(fā)現(xiàn)

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

表1 RSU 車輛信息表結(jié)構(gòu)Table 1 RSU vehicle information table structure

2）路由選擇

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

3）路由維護(hù)

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

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

2.2 基于改進(jìn)的自適應(yīng)蛙跳中繼節(jié)點(diǎn)選擇算法

蛙跳算法是進(jìn)化計算領(lǐng)域一種新興有效亞啟發(fā)式、結(jié)合遺傳學(xué)模因演算的群體進(jìn)化算法，該算法擁有優(yōu)良高效的計算性能和解空間能力［18］。為了找到多QoS 約束下的最優(yōu)路徑，本文提出了AH-SFLA 算法，該算法結(jié)合當(dāng)前網(wǎng)絡(luò)狀態(tài)自適應(yīng)地動態(tài)搜尋最優(yōu)解。主要步驟如下：

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

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

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

其中：μb、μc、μt和μd表示相應(yīng)指標(biāo)的權(quán)重因子，即不同的業(yè)務(wù)需求，對不同的約束所占比重有所不同。例如視頻流的業(yè)務(wù)需求，μb和μt的權(quán)重因子大于其他業(yè)務(wù)需求。

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

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

步驟5局部搜索。局部搜索僅對子種群內(nèi)適度值最大的車輛節(jié)點(diǎn)Xf_worst進(jìn)行進(jìn)化更新策略，更新策略如式（11）和式（12）所示：

其中：rand 為0～1 的隨機(jī)小數(shù)；Ri為移動步長，滿足-Rmax≤Ri≤Rmax約 束，Rmax為其移動最大步長；若，則用更新后的取代當(dāng)前子種群最差節(jié)點(diǎn)Xf_worst，否則以概率pm動態(tài)進(jìn)行變異更新。pm由SDN 控制器依據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)下的帶寬可用率、數(shù)據(jù)堆積率、車輛節(jié)點(diǎn)穩(wěn)定性以及對應(yīng)影響因子構(gòu)成。更新策略如式（13）、式（14）和式（15）所示：

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

其中：max 是當(dāng)前網(wǎng)絡(luò)狀態(tài)下隨機(jī)最大值；min 為隨機(jī)最小值。

步驟6全局搜索。局部搜索完成后，將重新混合構(gòu)成的下一代種群記錄適度值最小車輛節(jié)點(diǎn)Xg_best。判斷算法是否達(dá)到最大迭代次數(shù)G，若滿足則結(jié)束搜索并輸出；否則將繼續(xù)進(jìn)行搜索。

2.3 AH-SFLA 實現(xiàn)

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

算法1AH-SFLA 中繼節(jié)點(diǎn)選擇算法

3 仿真實驗與性能分析

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

圖4 蘭州市道路拓?fù)銯ig.4 Lanzhou city road topology

表2 環(huán)境參數(shù)配置Table 2 Environmental parameter configuration

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

表3 IGA 參數(shù)配置Table 3 IGA parameter configuration

模擬實驗中使用的性能指標(biāo)如下：

平均端到端延遲［25］：指數(shù)據(jù)包從源傳輸?shù)侥康牡厮璧钠骄鶗r間延遲，包括所有類型的延遲，如排隊延遲、傳送延遲以及路由發(fā)現(xiàn)緩沖延遲。

丟包率：是指測試中所丟失數(shù)據(jù)包數(shù)量占所發(fā)送數(shù)據(jù)組的比率。

標(biāo)準(zhǔn)化路由開銷［26］：發(fā)送控制數(shù)據(jù)包與成功接收數(shù)據(jù)包之間的比率。該度量不考慮控制器的控制開銷。

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

表4 場景1 參數(shù)配置Table 4 Scenario 1 parameter configuration

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

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

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

表5 場景2 參數(shù)配置Table 5 Scenario 2 parameter configuration

圖6展示了不同速度下AH-SFLA、IGA和IICSFLA協(xié)議的性能指標(biāo)。

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

圖6（a）所示為AH-SFLA、IGA 和IICSFLA 的平均E2E 延遲。通過增加車輛速度，車輛間通信鏈路斷開更加頻繁，尋找新路徑的過程將增加延遲。然而AH-SFLA 的平均E2E 延遲優(yōu)于IGA 和IICSFLA，因為AH-SFLA 協(xié)議可以通過SDN 控制器掌握全局拓?fù)湫畔?，能及時校正更新流表項從而延遲較低。如圖6（b）所示，AH-SFLA 協(xié)議丟包率分別優(yōu)于IGA的31.1%和IICSFLA 的21.32%。在高動態(tài)拓?fù)渥兓闆r下，如何保證在多QoS 約束下尋找最優(yōu)路徑點(diǎn)，SDN 控制器的優(yōu)勢顯而易見。如圖6（c）所示，當(dāng)車輛速度從5 m/s 逐漸増長到30 m/s 時，網(wǎng)絡(luò)中鏈路斷裂次數(shù)增多，3 個協(xié)議的標(biāo)準(zhǔn)化路由開銷隨之增加。車輛移動速度増加，導(dǎo)致IGA 和IICSFLA 協(xié)議在建立路由時極易發(fā)生斷裂，需要發(fā)送大量控制報文來進(jìn)行路由的重新建立。而AH-SFLA 具有QoS 路由維護(hù)機(jī)制，在車輛通信出現(xiàn)斷裂時能及時恢復(fù)，比其他兩種協(xié)議在標(biāo)準(zhǔn)化路由開銷方面有著較好的性能表現(xiàn)。

4 結(jié)束語

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