NFV 中基于量子遺傳算法的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法

邱航，湯紅波，游偉，趙宇，柏溢

（信息工程大學(xué)信息技術(shù)研究所，河南 鄭州 450002）

0 引言

網(wǎng)絡(luò)功能虛擬化（NFV,network function virtualization）作為5G 的關(guān)鍵技術(shù)之一，使網(wǎng)絡(luò)服務(wù)的部署和管理變得更加靈活和高效。NFV 將傳統(tǒng)網(wǎng)絡(luò)設(shè)備解耦成通用的商用硬件（交換機(jī)或服務(wù)器等）和獨(dú)立的軟件功能，軟件功能也稱虛擬網(wǎng)絡(luò)功能（VNF,virtual network function），可以基于云原生技術(shù)靈活部署[1]?；?G 服務(wù)化架構(gòu)，NFV 與軟件定義網(wǎng)絡(luò)共同實(shí)現(xiàn)了5G 網(wǎng)絡(luò)架構(gòu)的轉(zhuǎn)型，特別是基于NFV 的網(wǎng)絡(luò)切片技術(shù)促進(jìn)了垂直行業(yè)的蓬勃發(fā)展[2]。云環(huán)境中，服務(wù)提供商接收服務(wù)請(qǐng)求后以虛擬網(wǎng)絡(luò)功能轉(zhuǎn)發(fā)圖（VNF-FG,VNF-forwarding graph）的形式部署網(wǎng)絡(luò)服務(wù)實(shí)例，為用戶按需提供定制化網(wǎng)絡(luò)服務(wù)。VNF-FG 包含一系列服務(wù)相關(guān)的VNF，并通過(guò)有向虛擬鏈路相互連接[3]。同時(shí)，各種VNF-FG 需要被部署在NFV 基礎(chǔ)設(shè)施（NFVI,NFV infrastructure）上才能為用戶提供服務(wù)。因此，有效的VNF-FG 部署對(duì)網(wǎng)絡(luò)服務(wù)的性能和資源使用開銷有著極大的影響。

當(dāng)前最新的研究熱點(diǎn)是尋找多樣化約束和優(yōu)化目標(biāo)下最優(yōu)的VNF-FG 部署方案[4-6]。文獻(xiàn)[6]將VNF-FG 部署算法分為精確式算法、啟發(fā)式算法、元啟發(fā)式算法和基于機(jī)器學(xué)習(xí)的算法。精確式算法主要采用傳統(tǒng)數(shù)學(xué)方法建立最優(yōu)化模型，例如混合整數(shù)線性規(guī)劃[7]、混合整數(shù)二次規(guī)劃[8]，然后采用數(shù)學(xué)求解器（例如CPLEX、Gurobi 等）求解，但局限于小規(guī)模網(wǎng)絡(luò)求解，擴(kuò)展性較差。啟發(fā)式算法[9-10]大多基于設(shè)計(jì)者來(lái)自經(jīng)驗(yàn)的創(chuàng)新性想法，較適用于實(shí)際網(wǎng)絡(luò)場(chǎng)景，通過(guò)一些操作來(lái)減少求解過(guò)程的搜索空間，但受設(shè)計(jì)者水平的影響較大，獲得最優(yōu)解的性能難以保障。元啟發(fā)式算法是在啟發(fā)式算法基礎(chǔ)上的改進(jìn)，其混合了隨機(jī)算法和局部搜索算法，常見的有遺傳算法[11]、模擬退火算法[12]等?；跈C(jī)器學(xué)習(xí)的算法是近些年隨著機(jī)器學(xué)習(xí)的發(fā)展而興起的算法，主要以強(qiáng)化學(xué)習(xí)為主[13-14]，通過(guò)智能體與環(huán)境不斷交互訓(xùn)練，最終獲得最佳部署方案。在部署完成后，用戶流量的變化也促使服務(wù)提供商必須修改運(yùn)行中的VNF 實(shí)例容量以保障服務(wù)質(zhì)量和優(yōu)化資源使用效率[15]。VNF 實(shí)例的容量調(diào)整可分為2種方式：水平擴(kuò)縮容，通過(guò)增減實(shí)例數(shù)量的方式實(shí)現(xiàn)；垂直擴(kuò)縮容，通過(guò)修改已存在實(shí)例資源容量的方式實(shí)現(xiàn)[16]。此外，因?yàn)楫?dāng)前VNF 多采用微服務(wù)架構(gòu)設(shè)計(jì)，已有部分VNF 支持通過(guò)調(diào)整內(nèi)部VNF組件的容量進(jìn)行細(xì)粒度擴(kuò)縮容。

隨著業(yè)務(wù)類型變化和流量增長(zhǎng)，服務(wù)提供商不僅要維持原來(lái)的服務(wù)和應(yīng)用功能，還需要通過(guò)額外的轉(zhuǎn)發(fā)圖（添加新的轉(zhuǎn)發(fā)路徑、新的VNF 和新的服務(wù)鏈等）擴(kuò)展其已經(jīng)部署的VNF-FG 實(shí)例，進(jìn)而實(shí)現(xiàn)服務(wù)應(yīng)用升級(jí)。例如，在5G 應(yīng)用中，初始部署的網(wǎng)絡(luò)切片以面向高清視頻通話為主，現(xiàn)在因?yàn)橛脩魯?shù)量增加導(dǎo)致流量增長(zhǎng)，服務(wù)提供商需要增加用戶面功能（UPF,user plane function）進(jìn)行負(fù)載分擔(dān)，避免用戶體驗(yàn)質(zhì)量不佳；同時(shí)，部分用戶需要使用視頻會(huì)議功能，需添加相關(guān)安全VNF 以保護(hù)視頻傳輸過(guò)程中的信息安全、減少抖動(dòng)，因此服務(wù)提供商需要在初始部署網(wǎng)絡(luò)切片的基礎(chǔ)上添加額外的VNF 并調(diào)整轉(zhuǎn)發(fā)路徑，在擴(kuò)展完成后提供安全保障的視頻通話業(yè)務(wù)。網(wǎng)絡(luò)服務(wù)擴(kuò)展包含2 個(gè)階段，第一階段是初始VNF-FG 的擴(kuò)展，即添加新的VNF 和虛擬鏈路；第二階段是將擴(kuò)展的VNF 和虛擬鏈路部署在NFVI 以更新網(wǎng)絡(luò)服務(wù)和應(yīng)用。需要注意的是，在網(wǎng)絡(luò)服務(wù)擴(kuò)展過(guò)程中不能對(duì)已經(jīng)部署且正在運(yùn)行的服務(wù)和應(yīng)用產(chǎn)生影響，尤其是高可靠低時(shí)延網(wǎng)絡(luò)服務(wù)難以容忍中斷、遷移和破壞等情況對(duì)服務(wù)質(zhì)量和體驗(yàn)的影響[17]。在網(wǎng)絡(luò)服務(wù)的生命周期內(nèi)，服務(wù)提供商通過(guò)運(yùn)行/業(yè)務(wù)支撐系統(tǒng)聯(lián)合NFV管理和編排（MANO,management and orchestration）功能，實(shí)現(xiàn)在滿足用戶新的應(yīng)用需求或業(yè)務(wù)升級(jí)時(shí)進(jìn)行網(wǎng)絡(luò)服務(wù)擴(kuò)展。

為滿足上述需求，文獻(xiàn)[18]研究了動(dòng)態(tài)環(huán)境中服務(wù)功能鏈的重調(diào)整問(wèn)題，假設(shè)多條服務(wù)鏈可共用同種VNF，設(shè)計(jì)了一種聯(lián)合新到達(dá)服務(wù)請(qǐng)求的優(yōu)化部署和正在運(yùn)行服務(wù)鏈的再調(diào)整方法，以滿足用戶接入點(diǎn)變化的需求等。文獻(xiàn)[19]第一次提出服務(wù)圖擴(kuò)展問(wèn)題并將其建模為整數(shù)線性規(guī)劃，為改善精確式算法的擴(kuò)展性，提出了基于斯坦納樹的VNF-FG擴(kuò)展（STVE,Steiner tree based for VNF-FG extension）算法和特征分解的VNF-FG 擴(kuò)展（EDVE,eigen decomposition for VNF-FG extension）算法2 種啟發(fā)式算法。STVE 算法基于斯坦納樹模型，采用最小跳最短路徑算法進(jìn)行擴(kuò)展網(wǎng)絡(luò)功能的部署；EDVE算法采用Umeyama 特征分解方法計(jì)算虛擬網(wǎng)絡(luò)功能轉(zhuǎn)發(fā)圖和基礎(chǔ)設(shè)施物理圖的最優(yōu)匹配，實(shí)現(xiàn)網(wǎng)絡(luò)功能的擴(kuò)展部署和路由路徑選擇。2 種算法相對(duì)數(shù)學(xué)規(guī)劃擴(kuò)展性有所提高，但其復(fù)雜度仍為O(N3)。然而，未來(lái)通信需要支撐更大范圍的服務(wù)和應(yīng)用，這必然導(dǎo)致網(wǎng)絡(luò)拓?fù)洳粩鄶U(kuò)展，而且部分網(wǎng)絡(luò)節(jié)點(diǎn)（如空天衛(wèi)星、車聯(lián)網(wǎng)節(jié)點(diǎn)等）具有移動(dòng)屬性而導(dǎo)致網(wǎng)絡(luò)拓?fù)浒l(fā)生變化。同時(shí)，由于用戶和行業(yè)的多樣化業(yè)務(wù)需求，運(yùn)營(yíng)商需要為其定制化網(wǎng)絡(luò)服務(wù)按需提供資源，且通過(guò)業(yè)務(wù)實(shí)時(shí)感知、測(cè)量和資源調(diào)度等手段保障業(yè)務(wù)質(zhì)量，這將導(dǎo)致未來(lái)網(wǎng)絡(luò)具有更高的動(dòng)態(tài)性和復(fù)雜性。上述方法采用靜態(tài)的計(jì)算方式，假設(shè)基礎(chǔ)設(shè)施網(wǎng)絡(luò)的拓?fù)浜唾Y源狀態(tài)不會(huì)發(fā)生變化，在動(dòng)態(tài)網(wǎng)絡(luò)中的求解效率和最優(yōu)解的質(zhì)量將難以得到保障。面向未來(lái)動(dòng)態(tài)復(fù)雜的云網(wǎng)絡(luò)場(chǎng)景，本文研究的網(wǎng)絡(luò)服務(wù)擴(kuò)展問(wèn)題不僅需要在應(yīng)用層擴(kuò)展初始VNF-FG 以添加新的VNF 和虛擬鏈路，而且需要完成擴(kuò)展VNF 在基礎(chǔ)設(shè)施層的最優(yōu)化部署。

本文主要的研究工作如下。

1) 建立云網(wǎng)絡(luò)中網(wǎng)絡(luò)服務(wù)擴(kuò)展問(wèn)題的整數(shù)線性規(guī)劃模型。以最小化資源開銷為目標(biāo)，并滿足初始服務(wù)部署不變約束、擴(kuò)展VNF 唯一性部署約束、資源容量約束，以及節(jié)點(diǎn)親和性約束等。該問(wèn)題已被證明是一個(gè)NP 難題，在大規(guī)模網(wǎng)絡(luò)中計(jì)算復(fù)雜度高，求解時(shí)間長(zhǎng)，不具備良好的擴(kuò)展性。

2) 針對(duì)未來(lái)云網(wǎng)絡(luò)的動(dòng)態(tài)性和復(fù)雜性，設(shè)計(jì)了一種基于量子遺傳算法（QGA,quantum genetic algorithm）的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法。采用量子態(tài)作為基本信息單元，利用量子態(tài)特性，通過(guò)量子并行計(jì)算來(lái)解決大規(guī)模網(wǎng)絡(luò)中擴(kuò)展部署求解的復(fù)雜性。

3) 仿真結(jié)果表明，所提算法在擴(kuò)展成功率和平均資源開銷方面與現(xiàn)有的最小斯坦納樹和特征分解算法相比均表現(xiàn)較好，驗(yàn)證了所提算法的有效性。

1 系統(tǒng)模型

1.1 NFV 基礎(chǔ)設(shè)施

NFV 基礎(chǔ)設(shè)施可以表示為一個(gè)無(wú)向加權(quán)圖G=(N,L)，其中，N和L分別表示底層節(jié)點(diǎn)集合和物理鏈路集合。一個(gè)底層節(jié)點(diǎn)n∈N可能由一臺(tái)或多臺(tái)商用服務(wù)器構(gòu)成，其通過(guò)云計(jì)算技術(shù)可以實(shí)現(xiàn)資源的集中池化管理并支持實(shí)例化VNF。底層節(jié)點(diǎn)n∈N的可用處理資源容量表示為Cn。底層節(jié)點(diǎn)之間通過(guò)高速光纖全雙工連接，連接節(jié)點(diǎn)m∈N和n∈N的物理鏈路表示為lm,n∈L，其可用帶寬為Bm,n。

1.2 VNF 轉(zhuǎn)發(fā)圖

用戶請(qǐng)求可以表示為一個(gè)有向加權(quán)圖Gr=(N r,Lr)，其中，Nr表示相關(guān)VNF 集合，L r表示VNF-FG 中有向虛擬鏈路的集合。對(duì)于任意VNFf∈Nr，cf表示將其實(shí)例化在一個(gè)虛擬機(jī)或者容器中需要的處理資源（包括計(jì)算、存儲(chǔ)和網(wǎng)絡(luò)等資源）。對(duì)于連接相鄰VNFf∈Nr和g∈Nr的虛擬鏈路，其帶寬需求為。因此，為了提供用戶服務(wù)請(qǐng)求，服務(wù)提供商必須部署所有需求的VNF，并根據(jù)虛擬鏈路的方向?qū)ふ液线m的路由路徑以按照預(yù)定的順序依次通過(guò)相關(guān)VNF 序列。

此外，服務(wù)提供商需要能夠根據(jù)用戶新的應(yīng)用需求提供新的網(wǎng)絡(luò)服務(wù)部署方案，或者通過(guò)添加額外的VNF 和虛擬鏈路擴(kuò)展正在運(yùn)行的網(wǎng)絡(luò)服務(wù)以滿足新的應(yīng)用需求。對(duì)于新服務(wù)請(qǐng)求的部署，很多工作已經(jīng)對(duì)此開展研究，本文作者團(tuán)隊(duì)也做出了部分成果[20-21]。本文重點(diǎn)關(guān)注已部署網(wǎng)絡(luò)服務(wù)的擴(kuò)展問(wèn)題。VNF-FG 擴(kuò)展示意如圖1 所示，其中，實(shí)線部分表示用戶請(qǐng)求的初始VNF-FG，點(diǎn)畫線和虛線部分分別表示因?yàn)樾碌膽?yīng)用需求和流量增長(zhǎng)而額外添加的VNF 和虛擬鏈路。本文要解決的是一種更加通用的網(wǎng)絡(luò)服務(wù)擴(kuò)展問(wèn)題，即通過(guò)添加額外的VNF 和新的虛擬鏈路來(lái)調(diào)整網(wǎng)絡(luò)功能和轉(zhuǎn)發(fā)圖，不僅可以添加新類型VNF 和虛擬鏈路來(lái)匹配新的業(yè)務(wù)需求（如VNF4），而且在流量增長(zhǎng)時(shí)可以添加已有類型VNF 以適應(yīng)負(fù)載變化（如VNF2）。初始VNF-FG 已經(jīng)部署在基礎(chǔ)設(shè)施之上并正在為用戶提供服務(wù)，為了不影響初始服務(wù)的提供，服務(wù)提供商需要在初始請(qǐng)求部署的基礎(chǔ)上執(zhí)行網(wǎng)絡(luò)服務(wù)擴(kuò)展部署，在擴(kuò)展部署完成后更新以提供新的服務(wù)。擴(kuò)展的VNF-FG 表示為= (Nr∪N e,Lr∪Le)，其中，Ne和Le分別表示額外添加的擴(kuò)展VNF 集合和擴(kuò)展虛擬鏈路集合。額外添加的VNF 種類和數(shù)量是由用戶新的應(yīng)用需求決定的，而虛擬鏈路是服務(wù)提供商根據(jù)網(wǎng)絡(luò)服務(wù)對(duì)流量的處理順序確定的流量在VNF 之間的轉(zhuǎn)發(fā)路徑。擴(kuò)展VNFf∈Ne的屬性用請(qǐng)求的處理資源cf表示，擴(kuò)展虛擬鏈路的權(quán)重用請(qǐng)求的帶寬表示。特別地，如果在VNF-FG 擴(kuò)展中初始虛擬鏈路的流量增加，已部署虛擬鏈路的請(qǐng)求帶寬應(yīng)更新為初始帶寬和增加帶寬。例如，圖1 中接入點(diǎn)和VNF1之間的流量由于擴(kuò)展VNF2而增加。

圖1 VNF-FG 擴(kuò)展示意

1.3 整數(shù)線性規(guī)劃

VNF-FG 部署的優(yōu)化目標(biāo)直接取決于服務(wù)提供商的收益和成本，且同時(shí)需要滿足盡可能多的用戶需求。因此，本文的優(yōu)化目標(biāo)設(shè)置為最小化服務(wù)提供商網(wǎng)絡(luò)服務(wù)部署的資源使用開銷。優(yōu)化目標(biāo)包含底層節(jié)點(diǎn)處理資源開銷和物理鏈路帶寬開銷兩部分，如式(1)所示。

為統(tǒng)一底層節(jié)點(diǎn)處理資源開銷和物理鏈路帶寬開銷兩部分的計(jì)算單位，借鑒網(wǎng)絡(luò)資源的經(jīng)濟(jì)學(xué)衡量資源方式[22]，設(shè)φ和ξ分別表示每單位底層節(jié)點(diǎn)處理資源和物理鏈路帶寬的價(jià)格。

網(wǎng)絡(luò)服務(wù)擴(kuò)展過(guò)程不能影響正在提供服務(wù)的網(wǎng)絡(luò)服務(wù)實(shí)例的運(yùn)行，即保持初始化的VNF 部署和流量路由不能改變。初始的網(wǎng)絡(luò)服務(wù)部署包含2 個(gè)部分：VNF 部署和虛擬鏈路映射。初始VNF 部署和虛擬鏈路路由約束分別如式(2)和式(3)所示，分別保證正在運(yùn)行的VNF 部署位置和虛擬鏈路的路由路徑不變，其中，nf表示VNFf∈Nr的初始部署位置。

然后，部署擴(kuò)展的VNF 和虛擬鏈路。式(4)保證每個(gè)擴(kuò)展的VNFf∈Ne必須部署且僅部署在一個(gè)底層節(jié)點(diǎn)n∈N上，即一個(gè)VNF（可能包含多個(gè)VNF組件）不能分割部署在多個(gè)物理節(jié)點(diǎn)上。同時(shí)，式(5)確保部署在節(jié)點(diǎn)n∈N上的所有VNF 請(qǐng)求的處理資源之和不能超過(guò)節(jié)點(diǎn)可用處理資源容量。

虛擬鏈路的映射根據(jù)連接情況需要分為2 種情況討論。一種情況是當(dāng)虛擬鏈路的一端是初始VNF，另一端是擴(kuò)展VNF 時(shí)，根據(jù)虛擬鏈路的源節(jié)點(diǎn)和目的節(jié)點(diǎn)不同，可分為式(6)和式(7)這2 個(gè)約束。

另一種情況是擴(kuò)展虛擬鏈路的兩端都是新擴(kuò)展的VNF，等同于一條新虛擬鏈路的部署。新虛擬鏈路的部署必須保證在底層鏈路路由的連續(xù)性，且不能產(chǎn)生回路。

式(10)保證物理鏈路剩余可用帶寬必須滿足映射在其上的虛擬鏈路帶寬需求之和。

一些VNF 因?yàn)榘踩蛩鼗驊?yīng)用需求必須部署在同一個(gè)節(jié)點(diǎn)上，因此式(11)也稱為節(jié)點(diǎn)親和性約束。

2 算法設(shè)計(jì)

VNF-FG 部署已經(jīng)被證明是一個(gè)NP 難題[6]，而網(wǎng)絡(luò)服務(wù)擴(kuò)展可以看作一個(gè)VNF-FG 部署的變體，所以VNF-FG 擴(kuò)展也是一個(gè)NP 難題。考慮到未來(lái)云網(wǎng)絡(luò)的動(dòng)態(tài)性和復(fù)雜性以及算法的擴(kuò)展性，本文設(shè)計(jì)了一種基于QGA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法。

近年來(lái)，量子計(jì)算作為一種新的計(jì)算模式取得了長(zhǎng)足的發(fā)展。與在傳統(tǒng)通用計(jì)算機(jī)上運(yùn)行的經(jīng)典算法相比，量子算法由于量子疊加和量子糾纏，在解決一些計(jì)算問(wèn)題時(shí)要快得多。與經(jīng)典算法相比的量子計(jì)算的加速通常被稱為量子霸權(quán)[23]。量子計(jì)算所展示的計(jì)算能力引起了研究人員越來(lái)越多的關(guān)注。隨著含噪聲的中等尺度量子器件的出現(xiàn)，探索量子計(jì)算的應(yīng)用成為當(dāng)前研究的熱點(diǎn)。文獻(xiàn)[24]提出了一種具有矩陣積態(tài)量子電路的Born 機(jī)器模型，該模型比一般參數(shù)化量子電路所需的量子比特更少，可以更好地利用近期量子器件中稀缺的量子比特資源。文獻(xiàn)[25]設(shè)計(jì)了一種改進(jìn)的量子粒子群優(yōu)化算法，可以改善傳統(tǒng)粒子群優(yōu)化算法的收斂效率，并提高搜索精度。QGA 是量子計(jì)算和遺傳算法的混合產(chǎn)物，是一種新興的概率性進(jìn)化算法[26]。由于不適當(dāng)?shù)倪x擇、交叉或變異操作等，遺傳算法可能出現(xiàn)收斂速度慢或陷入局部最優(yōu)解的問(wèn)題。QGA 將量子態(tài)矢量引入遺傳編碼，并采用量子邏輯門實(shí)現(xiàn)染色體的進(jìn)化，可以實(shí)現(xiàn)比遺傳算法更好的效果。

2.1 量子染色體編碼

QGA 用量子比特存儲(chǔ)和表達(dá)一個(gè)基因。量子比特的不同之處在于它可以為|0〉態(tài)或|1〉態(tài)，或者處在2 個(gè)量子態(tài)的疊加態(tài)。因此，量子染色體通常成對(duì)出現(xiàn)，染色體中第i個(gè)基因用αi和βi表示，且=1。量子比特編碼使一個(gè)染色體可以同時(shí)表達(dá)多個(gè)態(tài)的疊加，因此QGA 比經(jīng)典遺傳算法擁有更好的多樣性特征。相比于傳統(tǒng)QGA 的全隨機(jī)量子編碼，本文研究的網(wǎng)絡(luò)服務(wù)擴(kuò)展問(wèn)題涉及初始VNF 和擴(kuò)展VNF。如圖2 所示，量子染色體編碼分為2 個(gè)部分，前半部分是固定編碼，表示初始VNF的位置；后半部分表示擴(kuò)展VNF 可能部署的位置。本文在仿真部分采用50 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)?，因此每個(gè)VNF 的部署位置采用8 位編碼表示，總?cè)旧w的長(zhǎng)度為總VNF 的數(shù)量乘以8，即解碼階段每8位基因確定一個(gè)VNF 的部署位置。采用這種編碼方式，一方面可以保證已部署VNF 的位置不變而不影響正在運(yùn)行的網(wǎng)絡(luò)服務(wù)；另一方面可以減少染色體中需要進(jìn)化編碼的數(shù)量，相對(duì)提高收斂速度。同時(shí)，量子門旋轉(zhuǎn)策略僅在擴(kuò)展VNF 編碼部分執(zhí)行以尋找最優(yōu)部署位置。在染色體解碼時(shí)，需要先測(cè)量量子染色體的矢量態(tài)，然后將其解碼為0-1編碼。

圖2 量子染色體編碼

2.2 適應(yīng)度計(jì)算

QGA 根據(jù)最大適應(yīng)度選擇進(jìn)化方向，但是網(wǎng)絡(luò)服務(wù)擴(kuò)展的優(yōu)化目標(biāo)是最小化資源開銷。因此，本文采用優(yōu)化目標(biāo)式(1)的負(fù)值作為適應(yīng)度函數(shù)。對(duì)于不滿足約束式(2)～式(11)的染色體，它的適應(yīng)度被定義為一個(gè)非常小的值以作為懲罰項(xiàng)，便于將其在選擇和進(jìn)化階段淘汰。根據(jù)染色體的適應(yīng)度，量子門旋轉(zhuǎn)策略將會(huì)向最優(yōu)的方向進(jìn)化。

2.3 量子門旋轉(zhuǎn)策略

量子門旋轉(zhuǎn)是實(shí)現(xiàn)進(jìn)化操作的執(zhí)行者，也是QGA 中實(shí)現(xiàn)量子并行運(yùn)算的關(guān)鍵。基于量子疊加態(tài)的編碼方式，量子門旋轉(zhuǎn)同時(shí)對(duì)一條染色體中的所有基因進(jìn)行變換，即量子并行運(yùn)算，使染色體向最優(yōu)個(gè)體的方向進(jìn)化，最后收斂獲取最優(yōu)解。因?yàn)楸疚奶厥獾木幋a方式，量子門旋轉(zhuǎn)操作僅在染色體的后半部分編碼執(zhí)行。本文采用的量子門旋轉(zhuǎn)策略如表1 所示，且染色體中每個(gè)基因的變換策略如下。

表1 中，xi表示當(dāng)前染色體的第i位編碼，besti表示當(dāng)前代內(nèi)最優(yōu)染色體的第i位編碼；f(x)表示染色體x的適應(yīng)度；s(αi,βi)表示旋轉(zhuǎn)角方向；Δθi表示旋轉(zhuǎn)角大小，其數(shù)值可以根據(jù)表1 中所列的選擇策略確定，也可以根據(jù)實(shí)際情況設(shè)定自適應(yīng)變化。量子門旋轉(zhuǎn)策略是將個(gè)體當(dāng)前測(cè)量值的適應(yīng)度f(wàn)(x)與該種群最優(yōu)個(gè)體的適應(yīng)度f(wàn)(best)進(jìn)行比較，如果f(x) ＞f(best)，則調(diào)整個(gè)體相應(yīng)位置量子比特，使(αi,βi)向有利于xi出現(xiàn)的方向進(jìn)化；相反，如果f(x) ＜f(best)，則調(diào)整個(gè)體中相應(yīng)位置量子比特，使(αi,βi)向有利于besti出現(xiàn)的方向進(jìn)化。

2.4 基于QGA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法

基于上述染色體編碼和量子門旋轉(zhuǎn)策略，本文在算法1中詳細(xì)描述了基于QGA的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法。步驟1)初始化QGA 參數(shù)，包含種群規(guī)模popsize 和最大迭代次數(shù)maxgen?；诔跏糣NF 和擴(kuò)展VNF的數(shù)量計(jì)算染色體長(zhǎng)度；在染色體初始化階段，隨機(jī)生成種群規(guī)模大小的個(gè)體數(shù)量；同時(shí)，因?yàn)榱孔泳幋a的特殊性，染色體數(shù)量是個(gè)體數(shù)量的2 倍（步驟2)～步驟3)）。由于QGA 采用量子比特作為編碼的基本單元，因此需要測(cè)量量子態(tài)，將其轉(zhuǎn)化為二進(jìn)制0-1 編碼形式，再計(jì)算每個(gè)染色體對(duì)應(yīng)的VNF 部署方案（步驟4)～步驟5)）。如果染色體對(duì)應(yīng)的VNF 部署方案滿足約束式(2)～式(11)，則它的適應(yīng)度可以根據(jù)適應(yīng)度函數(shù)求得，否則它的適應(yīng)度將會(huì)設(shè)為非常小的懲罰項(xiàng)值（步驟6)～步驟10)）。在最大迭代次數(shù)內(nèi)，根據(jù)表1 定義的量子門旋轉(zhuǎn)策略執(zhí)行種群進(jìn)化。重復(fù)步驟4)～步驟11)，更新并記錄所有染色體對(duì)應(yīng)的部署策略和適應(yīng)度（步驟12)～步驟15)）。最后，根據(jù)迭代結(jié)果，輸出最優(yōu)的擴(kuò)展VNF 部署方案。

表1 量子門旋轉(zhuǎn)策略

算法1基于QGA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法

輸入G=(N,E),=(Nr∪N e,Lr∪Le)

輸出最優(yōu)擴(kuò)展VNF 部署方案

1) 初始化參數(shù)：種群規(guī)模popsize，最大迭代次數(shù)maxgen

2) 基于VNF 數(shù)量計(jì)算染色體長(zhǎng)度

3) 隨機(jī)初始化生成種群

4) 測(cè)量染色體量子態(tài)并轉(zhuǎn)化為二進(jìn)制編碼

5) 計(jì)算每個(gè)染色體的適應(yīng)度

6) if 染色體對(duì)應(yīng)的部署方案滿足約束

7) 計(jì)算當(dāng)前染色體對(duì)應(yīng)的適應(yīng)度

8) else

9) 適應(yīng)度設(shè)置為極小值

10) end if

11) 記錄最優(yōu)染色體的適應(yīng)度和部署方案

12) for gen=2:maxgen

13) 對(duì)種群執(zhí)行量子門旋轉(zhuǎn)策略，使種群進(jìn)化

14) 重復(fù)步驟4)～步驟11)

15) end for

16) 保留最優(yōu)個(gè)體，輸出其對(duì)應(yīng)的部署方案和適應(yīng)度

3 仿真分析

本節(jié)從擴(kuò)展成功數(shù)量、擴(kuò)展成功率和平均資源開銷方面比較本文提出的基于QGA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法與STVE 算法和EDVE 算法[19]。

3.1 仿真設(shè)置

仿真在一臺(tái)64 GB 內(nèi)存的Intel(R) Xeon(R) Silver 4210 CPU @ 2.20 GHz 虛擬機(jī)上進(jìn)行，算法的執(zhí)行工具是 MATLAB 2019b。本文使用 SNDlib 中的Germany50[27]拓?fù)鋪?lái)評(píng)估網(wǎng)絡(luò)服務(wù)擴(kuò)展算法的性能。底層節(jié)點(diǎn)的處理資源容量和物理鏈路的帶寬從[100,120]unit 內(nèi)隨機(jī)生成，每單位底層節(jié)點(diǎn)處理資源和物理鏈路帶寬的價(jià)格分別設(shè)置為φ=0.7和ξ=0.3。初始VNF-FG 的VNF 數(shù)量設(shè)置為[3,5]隨機(jī)，每個(gè)服務(wù)請(qǐng)求擴(kuò)展的VNF 數(shù)量為[1,3]。初始VNF-FG 中每個(gè)VNF 請(qǐng)求的處理資源需求和虛擬鏈路的帶寬需求均為10 unit。在網(wǎng)絡(luò)服務(wù)擴(kuò)展時(shí)，擴(kuò)展VNF 的處理資源需求和虛擬鏈路的帶寬資源需求為20 unit。仿真中隨機(jī)生成1 000 個(gè)VNF-FG 請(qǐng)求和相應(yīng)的擴(kuò)展請(qǐng)求。不失一般性，采用文獻(xiàn)[21]的方法部署初始VNF-FG。

3.2 結(jié)果分析

擴(kuò)展成功數(shù)量是指在滿足連接性約束和資源約束的條件下成功實(shí)現(xiàn)VNF-FG擴(kuò)展請(qǐng)求在NFVI部署的數(shù)量。擴(kuò)展成功率表示擴(kuò)展請(qǐng)求成功部署數(shù)量與總擴(kuò)展數(shù)量的比值。本文需要考慮擴(kuò)展請(qǐng)求的平均部署開銷。平均部署開銷是指成功擴(kuò)展VNF-FG 占用的平均資源開銷，其反映了所提算法的資源使用效率。

收斂速度是衡量一個(gè)算法性能的重要標(biāo)準(zhǔn)。本文所提基于QGA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法（圖中用QGA 表示）與GA 收斂速度對(duì)比如圖3 所示。從圖3 可以看出，基于QGA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法在收斂速度和最優(yōu)個(gè)體的適應(yīng)度方面均有改進(jìn)，這是因?yàn)槠淞孔颖忍氐木幋a方式可以表示量子疊加態(tài)，使染色體具有更好的多樣性；同時(shí)，量子并行計(jì)算也使搜索最優(yōu)解的速度得到提升。收斂速度和最優(yōu)個(gè)體的適應(yīng)度證明了所提算法在實(shí)際網(wǎng)絡(luò)場(chǎng)景中獲取最優(yōu)解方面的可行性。

圖3 收斂速度對(duì)比

擴(kuò)展成功數(shù)量與擴(kuò)展請(qǐng)求數(shù)量之間的關(guān)系如圖4 所示。基于QGA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法相對(duì)STVE 算法和EDVE 算法表現(xiàn)較好，擴(kuò)展成功數(shù)量分別為810、753、688。因?yàn)镋DVE 算法采用Umeyama 特征分解進(jìn)行最優(yōu)化匹配，所以它在靜態(tài)轉(zhuǎn)發(fā)圖與底層拓?fù)渚哂懈呦嗨菩詴r(shí)表現(xiàn)更好，實(shí)際網(wǎng)絡(luò)環(huán)境的動(dòng)態(tài)性和復(fù)雜性導(dǎo)致其在本文仿真實(shí)驗(yàn)中求解性能下降。STVE 算法本質(zhì)上是最短路徑策略?；赒GA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法的并行計(jì)算特點(diǎn)是對(duì)解空間的整體搜索，避免單點(diǎn)搜索的貪婪策略，獲得最優(yōu)解的質(zhì)量更高，從而提高資源利用效率。因此，基于QGA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法可以接受更多的擴(kuò)展請(qǐng)求。

圖4 擴(kuò)展成功數(shù)量與擴(kuò)展請(qǐng)求數(shù)量之間的關(guān)系

擴(kuò)展成功率與擴(kuò)展請(qǐng)求數(shù)量的關(guān)系如圖5 所示。當(dāng)擴(kuò)展請(qǐng)求數(shù)量較少時(shí)，因?yàn)橘Y源充足，所以服務(wù)擴(kuò)展請(qǐng)求可以被完全接受。隨著擴(kuò)展請(qǐng)求數(shù)量的增加，節(jié)點(diǎn)和帶寬資源逐漸被占據(jù)，導(dǎo)致后續(xù)的擴(kuò)展請(qǐng)求因?yàn)橘Y源約束而被拒絕，因此擴(kuò)展成功率逐漸下降。STVE 算法采用貪婪策略，局部中心節(jié)點(diǎn)被過(guò)度使用以致后續(xù)擴(kuò)展虛擬鏈路的請(qǐng)求帶寬無(wú)法滿足而導(dǎo)致擴(kuò)展請(qǐng)求失敗。EDVE 算法隨著底層資源消耗拓?fù)淦ヅ湫韵陆?，?dǎo)致擴(kuò)展成功率下降?；赒GA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法由于采用并行計(jì)算的方式，具有全局整體尋優(yōu)的特點(diǎn)，因此獲得的最優(yōu)解在資源使用率方面更占優(yōu)勢(shì)，擴(kuò)展成功率下降相對(duì)較慢。

圖5 擴(kuò)展成功率與擴(kuò)展請(qǐng)求數(shù)量之間的關(guān)系

平均資源開銷與擴(kuò)展請(qǐng)求數(shù)量之間的關(guān)系如圖6所示。從圖6 可以看出，隨著服務(wù)請(qǐng)求數(shù)量增加，平均資源開銷逐漸上升。這是因?yàn)殡S著擴(kuò)展請(qǐng)求的到達(dá)，底層網(wǎng)絡(luò)中靠近初始VNF-FG 部署的資源被逐漸占據(jù)，導(dǎo)致后續(xù)的擴(kuò)展方案必須擴(kuò)大范圍而使平均資源開銷上升。與其他2 種算法相比，基于QGA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法一方面因?yàn)榱孔颖忍鼐幋a方式提高了染色體的多樣性，避免陷入局部最優(yōu)；另一方面并行計(jì)算方式有更好的全局搜索能力而獲得更高的搜索精度，所以平均資源開銷上升較慢。最后，因?yàn)閿U(kuò)展請(qǐng)求被拒絕較多，所以平均資源開銷趨于穩(wěn)定。

圖6 平均資源開銷與擴(kuò)展請(qǐng)求數(shù)量之間的關(guān)系

算法執(zhí)行時(shí)間是衡量算法復(fù)雜度的一個(gè)重要指標(biāo)。不同網(wǎng)絡(luò)規(guī)模下算法執(zhí)行時(shí)間對(duì)比如圖7 所示?；赒GA 的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法在執(zhí)行時(shí)間方面相較于STVE 算法和EDVE 算法具有明顯優(yōu)勢(shì)，基本呈線性增長(zhǎng)。一方面，群體智能進(jìn)化算法采用群體搜索的方式，具有較好的全局搜索和并行性，使求解效率顯著提升；另一方面，量子計(jì)算采用量子疊加態(tài)作為基本單位，通過(guò)量子并行運(yùn)算可以提高運(yùn)算效率。因此，所提算法的時(shí)間復(fù)雜度明顯較低，且在大規(guī)模網(wǎng)絡(luò)中具有更好的適應(yīng)性。

圖7 不同網(wǎng)絡(luò)規(guī)模下算法執(zhí)行時(shí)間對(duì)比

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

針對(duì)服務(wù)提供過(guò)程中用戶新的應(yīng)用需求或額外的安全保護(hù)機(jī)制，本文對(duì)網(wǎng)絡(luò)功能虛擬化環(huán)境中的網(wǎng)絡(luò)服務(wù)擴(kuò)展方法進(jìn)行研究。將網(wǎng)絡(luò)服務(wù)擴(kuò)展分為2 個(gè)階段，分別為VNF-FG 擴(kuò)展和基礎(chǔ)設(shè)施層部署；考慮到不影響已部署網(wǎng)絡(luò)服務(wù)以及底層基礎(chǔ)設(shè)施的資源容量約束，建立了網(wǎng)絡(luò)服務(wù)擴(kuò)展的整數(shù)線性規(guī)劃模型；為應(yīng)對(duì)未來(lái)云網(wǎng)絡(luò)的復(fù)雜和動(dòng)態(tài)性，設(shè)計(jì)了一種基于量子遺傳算法的網(wǎng)絡(luò)服務(wù)擴(kuò)展算法。仿真結(jié)果表明，所提算法在擴(kuò)展成功率和平均資源開銷方面均具有較好的性能。