杜欣欣，胡曉輝，趙佳楠

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

0 概述

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

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

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

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

本文將SDN 和VANET 相結(jié)合，構(gòu)造SDN-VANET異構(gòu)混合網(wǎng)絡(luò)，并提出一種應(yīng)用于SDN-VANET 架構(gòu)的QoS 路由算法，利用SDN 的高靈活性、可編程性等優(yōu)勢(shì)保障業(yè)務(wù)傳輸QoS。該算法在業(yè)務(wù)調(diào)度階段，SDN控制器優(yōu)先調(diào)度傳輸截止時(shí)間少的車輛業(yè)務(wù)，保障緊急業(yè)務(wù)傳輸。然后在路由選擇階段，基于蛙跳算法設(shè)計(jì)出自適應(yīng)混合中繼選擇算法。通過(guò)設(shè)計(jì)與QoS 約束相匹配的適應(yīng)度函數(shù)來(lái)衡量轉(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é)下可以實(shí)現(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ò)北向接口向下層提供關(guān)系數(shù)據(jù)庫(kù)、車載應(yīng)用、身份認(rèn)證信息、環(huán)境服務(wù)和安全服務(wù)等商業(yè)服務(wù)應(yīng)用。

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

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

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

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

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

1.2 路徑參數(shù)

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

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

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

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

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

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

1.3 約束條件

在某個(gè)時(shí)隙內(nèi)，組網(wǎng)中可能存在多個(gè)車輛同時(shí)需要轉(zhuǎn)發(fā)多個(gè)數(shù)據(jù)包數(shù)據(jù)的情況，為了避免網(wǎng)絡(luò)阻塞和問(wèn)題路由，在設(shè)計(jì)協(xié)議時(shí)需要對(duì)數(shù)據(jù)包轉(zhuǎn)發(fā)條件加以限制。其次還需對(duì)剩余帶寬及時(shí)進(jìn)行校正，確保下一個(gè)車輛業(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時(shí)，不得從節(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為了提高選擇最佳路徑時(shí)的準(zhǔn)確性，組網(wǎng)中節(jié)點(diǎn)i和j之間的鏈路的剩余帶寬必須在執(zhí)行轉(zhuǎn)發(fā)或丟棄動(dòng)作后進(jìn)行更新［16］。bi，j的計(jì)算如式（7）所示：

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

2.1 協(xié)議概述

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

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

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

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

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

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

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

車輛節(jié)點(diǎn)定時(shí)向RSU 發(fā)送Hello 包，匯報(bào)車輛自身基本信息。當(dāng)RSU 收到Hello 包后，會(huì)將包信息加入到該區(qū)域的車輛信息表中，根據(jù)車輛的通信范圍尋找該車輛的鄰居節(jié)點(diǎn)，并寫入該區(qū)域的車輛信息表。然后RSU 回傳一個(gè)包含該車輛地理信息以及車輛鄰居節(jié)點(diǎn)信息的AckHello 包。車輛也可以根據(jù)回傳的AckHello 包信息判斷是否自己脫離了該RSU控制區(qū)域，如果脫離了該區(qū)域RSU，車輛將重新發(fā)送Hello 包直到下一個(gè)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)且有意義時(shí)，將執(zhí)行SDN 控制器下達(dá)的不轉(zhuǎn)發(fā)命令，不轉(zhuǎn)發(fā)列表中車輛發(fā)來(lái)的所有數(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)路移動(dòng)模型和源節(jié)點(diǎn)所提出業(yè)務(wù)請(qǐng)求的截止時(shí)間，預(yù)測(cè)在該時(shí)限內(nèi)各車輛位置，確定符合截止日期約束的備選中繼車輛。在中繼選擇過(guò)程中為滿足不同業(yè)務(wù)的QoS 約束指標(biāo)，提出一種基于改進(jìn)的自適應(yīng)混合蛙跳中繼選擇算法（Adaptive Hybrid Shuffled Frog Leading Algorithm，AH-SFLA）。在保障各約束的同時(shí)，以最小化QoS 資源將數(shù)據(jù)包從源車輛傳輸?shù)侥康能囕v。

3）路由維護(hù)

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

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

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

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

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

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

步驟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í)降低傳輸能量消耗。因此，適度函數(shù)如式（10）所示：

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

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

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

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

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

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

其中：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 實(shí)現(xiàn)

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

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

3 仿真實(shí)驗(yàn)與性能分析

在仿真實(shí)驗(yàn)中，聯(lián)合SUMO［20］、Mininet-wifi 和POX［21］來(lái)仿真SDN-VANET 環(huán)境［22］。城市道路模擬是通過(guò)Openstreetmap 和SUMO 創(chuàng)建的1 500 m×1 000 m甘肅省蘭州市街道區(qū)域，如圖4所示。而POX和Mininetwifi 則實(shí)現(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］在不同場(chǎng)景下進(jìn)行對(duì)比。IGA 是基于遺傳算法而設(shè)計(jì)的多約束單播路由協(xié)議，該協(xié)議在計(jì)算適度函數(shù)時(shí)引入一種新的懲罰函數(shù)和約束權(quán)重，加快了種群“優(yōu)勝劣汰”的速度。而IICSFLA是結(jié)合免疫算法和蛙跳算法的路由協(xié)議，該協(xié)議的更新策略是通過(guò)克隆變異種群最優(yōu)節(jié)點(diǎn)完成的。IGA 的參數(shù)配置如表3 所示。

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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