喬文欣，盧 皓，李雄偉，倪祥龍，陳立偉

(1.陸軍工程大學(xué) 石家莊校區(qū)，河北 石家莊 050003；2.北京航天飛行控制中心，北京 100094；3.北京空間信息中繼傳輸技術(shù)研究中心，北京 100094；4.電子信息系統(tǒng)復(fù)雜電磁環(huán)境效應(yīng)國家重點(diǎn)實(shí)驗(yàn)室，河南 洛陽 471003)

0 引言

隨著微小衛(wèi)星系統(tǒng)與互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，融合地面網(wǎng)絡(luò)和衛(wèi)星網(wǎng)絡(luò)覆蓋空、天、地、海和深空等自然環(huán)境，能夠提供全天候無縫高速網(wǎng)絡(luò)接入的星地融合網(wǎng)絡(luò)逐漸成為當(dāng)前產(chǎn)業(yè)界和學(xué)術(shù)界研究的重要領(lǐng)域之一[1]。通過與SDN/NFV[2](Software Defined Networking/Network Function Virtualization)、5G[3]、邊緣計(jì)算[4]和物聯(lián)網(wǎng)[5]等新型網(wǎng)絡(luò)技術(shù)的結(jié)合，更賦予了星地融合網(wǎng)絡(luò)高效便捷的管理控制能力和靈活可拓展的網(wǎng)絡(luò)服務(wù)支持[6]。在星地融合網(wǎng)絡(luò)架構(gòu)下，按照實(shí)際用戶業(yè)務(wù)需要和服務(wù)需求提供差異化的獨(dú)立網(wǎng)絡(luò)切片，或部署相應(yīng)的虛擬網(wǎng)絡(luò)功能(Virtual Network Function,VNF)，其目的都是利用有限的網(wǎng)絡(luò)資源或服務(wù)資源來滿足多樣化的用戶業(yè)務(wù)需求和服務(wù)需求，以獲取更佳的網(wǎng)絡(luò)資源配置與服務(wù)體驗(yàn)。然而，星地融合網(wǎng)絡(luò)自身所具備的網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)性，以及用戶業(yè)務(wù)請(qǐng)求和任務(wù)需求隨態(tài)勢(shì)實(shí)時(shí)變化的特點(diǎn)，都使得一次性的資源部署及優(yōu)化策略與動(dòng)態(tài)變化的網(wǎng)絡(luò)狀態(tài)不再適配，從而導(dǎo)致網(wǎng)絡(luò)性能惡化、用戶服務(wù)質(zhì)量體驗(yàn)下降和網(wǎng)絡(luò)運(yùn)維成本增加等情況發(fā)生。例如，衛(wèi)星節(jié)點(diǎn)或用戶節(jié)點(diǎn)移動(dòng)可能導(dǎo)致傳輸鏈路質(zhì)量下降或連接中斷，使得原有端到端傳輸路徑不能正常工作。所以，當(dāng)星地融合網(wǎng)絡(luò)的網(wǎng)絡(luò)狀態(tài)和用戶需求的動(dòng)態(tài)性嚴(yán)重影響到業(yè)務(wù)流量傳輸或服務(wù)部署質(zhì)量時(shí)，需要尋找新的調(diào)整方法來保持流量傳輸和服務(wù)質(zhì)量。

針對(duì)上述問題，將原有服務(wù)節(jié)點(diǎn)上部署的虛擬網(wǎng)絡(luò)功能通過在線遷移或重新實(shí)例化的方式，遷移到資源更充足或路徑更合理的新服務(wù)節(jié)點(diǎn)所在位置，然后按照新位置引導(dǎo)業(yè)務(wù)流量按照新的服務(wù)路徑傳輸，能夠在一定程度上緩解負(fù)載不均衡和服務(wù)質(zhì)量下降等問題[7-8]。這種調(diào)整方式被稱為服務(wù)遷移與重構(gòu)，目前在移動(dòng)邊緣網(wǎng)絡(luò)[9-11]、物聯(lián)網(wǎng)[12]和霧計(jì)算[13]等領(lǐng)域有著許多相關(guān)研究，但在多源異構(gòu)且動(dòng)態(tài)性強(qiáng)的星地融合網(wǎng)絡(luò)中，其研究還處于起步階段。不同于一般網(wǎng)絡(luò)框架，星地融合網(wǎng)絡(luò)的動(dòng)態(tài)性主要源于內(nèi)部網(wǎng)絡(luò)結(jié)構(gòu)變化和外部用戶需求變化兩方面因素。內(nèi)部網(wǎng)絡(luò)結(jié)構(gòu)變化包括衛(wèi)星節(jié)點(diǎn)和地面MEC節(jié)點(diǎn)的移動(dòng)性、節(jié)點(diǎn)和鏈路的新增或失效等因素；外部用戶需求變化包括用戶節(jié)點(diǎn)移動(dòng)導(dǎo)致業(yè)務(wù)和服務(wù)請(qǐng)求接入位置移動(dòng)，業(yè)務(wù)和服務(wù)的請(qǐng)求類型和質(zhì)量要求發(fā)生變化等因素。因此，如何在保證網(wǎng)絡(luò)服務(wù)質(zhì)量的同時(shí)，為星地網(wǎng)絡(luò)用戶提供連續(xù)且可靠的高質(zhì)量網(wǎng)絡(luò)服務(wù)和業(yè)務(wù)支持，是當(dāng)前星地融合網(wǎng)絡(luò)研究的關(guān)鍵挑戰(zhàn)之一。

目前，國內(nèi)外學(xué)者對(duì)星地融合網(wǎng)絡(luò)服務(wù)遷移重構(gòu)相關(guān)問題的研究已取得了一定的成果。文獻(xiàn)[12]建立了衛(wèi)星智能城市車輛聯(lián)網(wǎng)場(chǎng)景下的計(jì)算資源地理遷移模型，通過霧節(jié)點(diǎn)感知道路狀態(tài)和車輛情況，并提出了一種基于資源定價(jià)的車輛路徑選擇方案，其主要?jiǎng)?chuàng)新在于不同需求情況下的定價(jià)策略算法，但在遷移策略計(jì)算效率方面略顯不足。文獻(xiàn)[14]提出了一種基于天基的在軌服務(wù)體系架構(gòu)，能夠根據(jù)實(shí)時(shí)上下行流量變化進(jìn)行動(dòng)態(tài)業(yè)務(wù)遷移，以優(yōu)化遷移節(jié)點(diǎn)時(shí)延和能量消耗為目標(biāo)，建立了天基邊緣云服務(wù)遷移模型并進(jìn)行仿真驗(yàn)證，但服務(wù)遷移對(duì)象和范圍僅針對(duì)衛(wèi)星節(jié)點(diǎn)及其上的在軌服務(wù)，未考慮星地節(jié)點(diǎn)之間的遷移問題。文獻(xiàn)[15]研究了空天網(wǎng)絡(luò)場(chǎng)景下的通信服務(wù)動(dòng)態(tài)資源分配和重配置問題，將機(jī)上用戶資源分配問題建模為多周期廣義分配問題，并提出了一種深度Q學(xué)習(xí)控制框架優(yōu)化資源分配和重配置方法。文獻(xiàn)[16-17]考慮車輛聯(lián)網(wǎng)場(chǎng)景的動(dòng)態(tài)性，研究了空天地協(xié)同的車輛聯(lián)網(wǎng)場(chǎng)景下的在線動(dòng)態(tài)VNF映射和調(diào)度問題，提出了2種基于禁忌搜索算法的VNF映射和重調(diào)度算法，能夠有效獲得近似最優(yōu)VNF遷移方案。綜上，雖然當(dāng)前已有一些學(xué)者從不同的角度對(duì)星地融合網(wǎng)絡(luò)及相似網(wǎng)絡(luò)架構(gòu)的遷移重構(gòu)問題進(jìn)行了研究，但其針對(duì)性和優(yōu)化效果略顯不足，需要進(jìn)一步深入探討。

為此，本文重點(diǎn)研究了星地融合網(wǎng)絡(luò)架構(gòu)下內(nèi)外部網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)性導(dǎo)致的服務(wù)遷移重構(gòu)問題。首先，給出以節(jié)點(diǎn)移動(dòng)性和用戶需求變化為主要觸發(fā)因素的服務(wù)遷移重構(gòu)基本步驟，并將其中的遷移位置和路徑選擇問題建模為一個(gè)經(jīng)典整數(shù)線性規(guī)劃問題；然后，提出了一種基于模糊量子遺傳算法的動(dòng)態(tài)服務(wù)遷移重構(gòu)(Fuzzy Logic Quantum Genetic Algorithm Based Dynamic Service Migration and Reconfiguration,FQGA-SR)方法，利用其量子編碼和并行計(jì)算的優(yōu)勢(shì)進(jìn)行優(yōu)化決策求解；最后，對(duì)所提算法的有效性和效率進(jìn)行了仿真實(shí)驗(yàn)驗(yàn)證。

1 問題描述

星地融合網(wǎng)絡(luò)服務(wù)遷移重構(gòu)過程如圖1所示。星地融合網(wǎng)絡(luò)的基本結(jié)構(gòu)包含由衛(wèi)星網(wǎng)絡(luò)、無人平臺(tái)和地面網(wǎng)絡(luò)組成的3層平面網(wǎng)絡(luò)結(jié)構(gòu)，以及地面管理控制中心和GEO衛(wèi)星控制器組成的2層控制結(jié)構(gòu)。假設(shè)LEO衛(wèi)星邊緣節(jié)點(diǎn)和地面邊緣節(jié)點(diǎn)都具備一定算力和存儲(chǔ)資源，可以根據(jù)部署策略承載多種VNFs，能夠?yàn)橛脩籼峁└咚倬W(wǎng)絡(luò)接入、邊緣側(cè)服務(wù)支持、數(shù)據(jù)中繼和鏈路回程。同時(shí)，無人機(jī)節(jié)點(diǎn)和衛(wèi)星節(jié)點(diǎn)都擁有通信中繼和鏈路回程能力，由于無人機(jī)受能源和荷載限制，暫不考慮將無人機(jī)節(jié)點(diǎn)作為承載VNF的邊緣節(jié)點(diǎn)，僅承擔(dān)中繼轉(zhuǎn)發(fā)功能。衛(wèi)星網(wǎng)絡(luò)平面中的衛(wèi)星節(jié)點(diǎn)通過定向無線通信鏈路互相連接，包括微波、激光、6G通信中的毫米波和自由空間光學(xué)鏈路等，因而支持高速數(shù)據(jù)傳輸。

圖1上方為星地融合網(wǎng)絡(luò)用戶提出服務(wù)請(qǐng)求的基本過程，當(dāng)前服務(wù)提供的對(duì)象為可移動(dòng)車輛終端用戶，車載終端用戶從人口密集型核心城區(qū)由西向東駛向偏遠(yuǎn)地區(qū)，該車輛用戶執(zhí)行任務(wù)所需求的服務(wù)功能鏈為有順序的網(wǎng)絡(luò)功能VNF-1，VNF-2和VNF-3。

圖1 星地融合網(wǎng)絡(luò)服務(wù)遷移重構(gòu)過程Fig.1 Service migration and reconfiguration process of satellite-terrestrial integrated network

車輛用戶移動(dòng)前，由于周圍具備臨近地面邊緣接入點(diǎn)，能夠提供充足的邊緣算力與服務(wù)支撐，從而通過網(wǎng)絡(luò)功能路徑(Service Function Path,SFP)SFP1(N3-N1-N2)到達(dá)目的節(jié)點(diǎn)N4，并分別由地面邊緣節(jié)點(diǎn)N3，N1和N2承載服務(wù)功能VNF-1，VNF-2和VNF-3。

車輛用戶移動(dòng)至偏遠(yuǎn)地區(qū)后，此時(shí)失去地面邊緣節(jié)點(diǎn)的接入支持和服務(wù)支持，管理控制平面根據(jù)實(shí)時(shí)網(wǎng)絡(luò)狀態(tài)信息和車輛用戶服務(wù)請(qǐng)求，運(yùn)行服務(wù)遷移和重構(gòu)算法得出最優(yōu)遷移位置和遷移路徑。例如，將地面邊緣節(jié)點(diǎn)N3上的VNF-1遷移至衛(wèi)星邊緣節(jié)點(diǎn)N9上，將N1上的VNF-2遷移至衛(wèi)星邊緣節(jié)點(diǎn)N7上，遷移路徑按照最短路徑進(jìn)行。遷移后用戶車輛的數(shù)據(jù)流量按照SFP2(N9-N7-N2)到達(dá)目的節(jié)點(diǎn)N4，以滿足車輛用戶的通信需求和服務(wù)需求，并保持通信和服務(wù)的連續(xù)性及可靠性。

本文研究的重點(diǎn)是通過服務(wù)遷移和重構(gòu)算法為VNF遷移找到合適的遷入位置，以及在滿足約束限制的情況下，最小化遷移成本，優(yōu)化服務(wù)遷移路徑。

2 服務(wù)遷移重構(gòu)模型構(gòu)建

2.1 系統(tǒng)模型

假設(shè)當(dāng)前星地融合網(wǎng)絡(luò)中地面邊緣節(jié)點(diǎn)和衛(wèi)星邊緣節(jié)點(diǎn)的數(shù)量已知且固定，網(wǎng)絡(luò)用戶和衛(wèi)星節(jié)點(diǎn)可隨時(shí)間變化而移動(dòng)，各個(gè)節(jié)點(diǎn)和鏈路之間的連接狀態(tài)和資源狀態(tài)可通過SDN/NFV全局狀態(tài)感知能力獲取，即網(wǎng)絡(luò)拓?fù)錉顟B(tài)和網(wǎng)絡(luò)資源狀態(tài)可知。不同用戶對(duì)網(wǎng)絡(luò)服務(wù)請(qǐng)求的服務(wù)需求和資源需求到達(dá)呈一定規(guī)律。

① 底層物理網(wǎng)絡(luò)模型

② 服務(wù)請(qǐng)求

表1 主要符號(hào)及定義Tab.1 Main notations and definitions

服務(wù)請(qǐng)求部署狀態(tài)和物理網(wǎng)絡(luò)資源使用情況隨時(shí)間變化而變化，利用SDN/NFV集中控制功能可以獲取當(dāng)前時(shí)刻的網(wǎng)絡(luò)狀態(tài)，每個(gè)邊緣節(jié)點(diǎn)所能承載的用戶服務(wù)請(qǐng)求數(shù)與當(dāng)前剩余資源和用戶請(qǐng)求數(shù)有關(guān)。

2.2 優(yōu)化目標(biāo)

考慮到用戶端到端時(shí)延是影響服務(wù)體驗(yàn)最重要的性能指標(biāo)之一，可將時(shí)延作為服務(wù)遷移問題的優(yōu)化目標(biāo)。除了數(shù)據(jù)傳輸過程產(chǎn)生的端到端時(shí)延，服務(wù)遷移過程會(huì)在原有時(shí)延的基礎(chǔ)上產(chǎn)生額外時(shí)延，因此需要作為遷移成本另外考慮。

因此，星地融合網(wǎng)絡(luò)中的服務(wù)遷移和重構(gòu)問題的優(yōu)化目標(biāo)可以定義為：在保證服務(wù)連續(xù)性的同時(shí)，最小化端到端時(shí)延和遷移成本。下面給出端到端時(shí)延和遷移成本的公式化描述，以及服務(wù)遷移和重構(gòu)問題的優(yōu)化目標(biāo)及約束條件。

① 端到端時(shí)延

端到端時(shí)延的計(jì)算為用戶服務(wù)請(qǐng)求到達(dá)邊緣接入點(diǎn)，用戶數(shù)據(jù)通過網(wǎng)絡(luò)傳輸并依次通過服務(wù)路徑中的服務(wù)功能所在節(jié)點(diǎn)，完成所有服務(wù)功能所產(chǎn)生的時(shí)延，主要包括傳播時(shí)延Dp、傳輸時(shí)延Dtr和處理時(shí)延Dpr三部分，可表示為：

D(t)=Dp(t)+Dtr(t)+Dpr(t)，

(1)

式中，傳播時(shí)延主要與星地、星間鏈路的物理長度Dis(fk,fv)有關(guān)，計(jì)算公式如下：

(2)

(3)

(4)

② 遷移成本

遷移成本指的是星地融合網(wǎng)絡(luò)的服務(wù)遷移過程中，因執(zhí)行遷移動(dòng)作所產(chǎn)生的額外運(yùn)營成本和開銷。由于本文所關(guān)注的重點(diǎn)在于用戶和衛(wèi)星節(jié)點(diǎn)移動(dòng)性所引發(fā)的服務(wù)遷移，在此僅考慮單個(gè)VNF進(jìn)行遷移和重構(gòu)的情況。每進(jìn)行一次服務(wù)遷移，所產(chǎn)生的遷移成本主要包括在遷入節(jié)點(diǎn)位置實(shí)例化新VNF所花費(fèi)的成本，以及遷移路徑選擇所產(chǎn)生的額外時(shí)延。當(dāng)服務(wù)遷移動(dòng)作所經(jīng)過的路由節(jié)點(diǎn)越多、路徑可用帶寬越小，則所產(chǎn)生的遷移成本越高、業(yè)務(wù)因遷移導(dǎo)致的中斷時(shí)間越長，不利于用戶服務(wù)體驗(yàn)。與此同時(shí)，遷移路徑所經(jīng)過的節(jié)點(diǎn)可用路由跳數(shù)替代，遷移成本的計(jì)算可以用遷移路徑跳數(shù)導(dǎo)致的額外傳播時(shí)延和遷移路徑帶寬相關(guān)的額外傳輸時(shí)延衡量。由于實(shí)例化新VNF所花費(fèi)成本與遷移位置無關(guān)，因此僅考慮額外時(shí)延，則遷移成本Mc可表示為：

(5)

2.3 問題建模

當(dāng)星地融合網(wǎng)絡(luò)中內(nèi)外部環(huán)境變化觸發(fā)服務(wù)遷移條件時(shí)，采用服務(wù)遷移和重構(gòu)優(yōu)化模型求解最優(yōu)服務(wù)遷移策略，主要為遷入節(jié)點(diǎn)和遷移路徑的選擇問題。考慮網(wǎng)絡(luò)用戶的服務(wù)體驗(yàn)及運(yùn)營成本，將最小化端到端時(shí)延和遷移成本作為優(yōu)化目標(biāo)，可表示為：

minCm(t)=min[w1D(t)+w2Mc(t)]，

(6)

s.t.∑Msu(ni,fk)≤1 , ?ni∈Nsn,fk∈Fs，

(7)

(8)

(9)

(10)

Msu(ni,fk)={0,1}，?ni∈Nsn,fk∈Fs，

(11)

(12)

式(6)為優(yōu)化問題的目標(biāo)函數(shù)，其目的是獲得端到端時(shí)延和遷移成本最小的最優(yōu)遷移位置和遷移路徑，其中w1和w2分別為端到端時(shí)延D(t)和遷移成本Mc(t)的修正系數(shù)，用于動(dòng)態(tài)調(diào)整不同服務(wù)對(duì)時(shí)延和遷移成本的不同需求。式(7)～式(12)為約束條件，主要考慮底層物理網(wǎng)絡(luò)資源限制與服務(wù)遷移需求之間的均衡。其中，式(7)和式(8)保證一個(gè)服務(wù)遷入節(jié)點(diǎn)和鏈路最多只能映射到一個(gè)底層物理節(jié)點(diǎn)和鏈路上；式(9)保證服務(wù)遷入節(jié)點(diǎn)的計(jì)算資源需求不超過所映射到的底層節(jié)點(diǎn)計(jì)算資源容量；式(10)保證服務(wù)遷移鏈路的帶寬資源需求不超過所映射到的底層鏈路帶寬資源容量；式(11)利用布爾變量表示該底層節(jié)點(diǎn)是否被選為當(dāng)前服務(wù)部署節(jié)點(diǎn)，1為部署，0為否；式(12)同上，代表該底層鏈路是否被選為服務(wù)請(qǐng)求虛擬鏈路，1為映射，0為否。

3 算法設(shè)計(jì)及描述

由模型可知，服務(wù)遷移重構(gòu)優(yōu)化問題是一個(gè)整數(shù)線性規(guī)劃(Integrated Linear Programming，ILP)問題，即最優(yōu)遷入節(jié)點(diǎn)決策和遷移路徑選擇問題?？紤]到衛(wèi)星節(jié)點(diǎn)和用戶的動(dòng)態(tài)性及移動(dòng)性，該問題的求解空間較為龐大。經(jīng)典的精確求解、啟發(fā)式求解和元啟發(fā)式求解算法在一定程度上都具有局限性，不適用于大規(guī)模離散狀態(tài)空間問題[18]。經(jīng)典遺傳算法是一種隨機(jī)啟發(fā)式搜索算法，與精確求解算法相比，該算法效率較高，且其中交叉和變異步驟具有隨機(jī)性，在一定程度上能夠避免算法陷入局部最優(yōu)，但過大的隨機(jī)性設(shè)置會(huì)使求解空間變大、求解效率降低。量子遺傳算法是在經(jīng)典遺傳算法的基礎(chǔ)上，將量子算法中量子疊加態(tài)能夠并行計(jì)算以加速求解過程的優(yōu)勢(shì)，作用于種群編碼方式和進(jìn)化策略，進(jìn)一步提升遺傳算法原有的求解效率和全局尋優(yōu)能力。而且，該算法能夠彌補(bǔ)染色體組合交叉和變異隨機(jī)性帶來的求解空間過大、求解困難的缺陷，在文獻(xiàn)中已展示出良好的性能表現(xiàn)，能夠在較小種群規(guī)模下，快速收斂到全局最優(yōu)解。

因此，選擇采用量子機(jī)器學(xué)習(xí)與傳統(tǒng)算法結(jié)合的模式，提出了一種基于模糊邏輯(Fuzzy Logic，F(xiàn)L)和量子遺傳算法(Quantum Genetic Algorithm,QGA)的服務(wù)遷移優(yōu)化算法。將對(duì)所提算法的基本步驟進(jìn)行詳細(xì)闡述，并給出算法的偽碼，為算法的仿真實(shí)驗(yàn)驗(yàn)證給出鋪墊。

3.1 基本步驟

基于模糊量子遺傳算法的服務(wù)遷移重構(gòu)(FQGA-SR)算法的基本步驟如下。

3.1.1 建立最短路徑矩陣S

首先，建立FQGA-SR算法的輸入矩陣S，用于表示底層網(wǎng)絡(luò)Gsn內(nèi)任意兩底層節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系，矩陣S的第i行和第j列代表節(jié)點(diǎn)ni和節(jié)點(diǎn)nj之間所部署SFC的最小時(shí)延。利用k-Dijkstra算法計(jì)算兩節(jié)點(diǎn)間的最短路徑，得到矩陣S。

3.1.2 FQGA-SR算法初始化

初始化種群及個(gè)體，設(shè)觀測(cè)序列個(gè)數(shù)為Xc，量子比特概率空間為Niche，染色體量子比特編碼長度為K和種群規(guī)模為M。利用量子比特編碼的方式構(gòu)造初始種群及個(gè)體，采用量子疊加態(tài)形式表達(dá)染色體，能夠在保持種群規(guī)模的前提下，大幅提升種群基因型的多樣性。

(13)

3.1.3 子種群進(jìn)化

模糊邏輯算法以隸屬度的形式將離散數(shù)據(jù)模糊化，能夠用單一模糊集合定義離散概率函數(shù)，以便高效獲取較為準(zhǔn)確的輸出結(jié)果。因此，利用模糊邏輯算法來描述包含概率幅的量子比特編碼的種群和個(gè)體，有助于獲取子種群的進(jìn)化。令H1表示子種群中|1〉與量子比特編碼數(shù)目K之間的比值，可表示為：

(14)

可將適應(yīng)度函數(shù)Fit(Xc)表示為Fit(Xc)=[Obj]-1，Obj為當(dāng)前優(yōu)化目標(biāo)，即最小化端到端時(shí)延和遷移成本。根據(jù)適應(yīng)度函數(shù)定義H2，用于衡量當(dāng)前與適應(yīng)度密切相關(guān)的程度，則H2可表示為：

(15)

式中，F(xiàn)it*(Xb)為當(dāng)前適應(yīng)度最高的值。

將H1和H2分別量化為c1級(jí)和c2級(jí)，其基本取值范圍為[0,1]。通過輸入H1和H2得到量子旋轉(zhuǎn)門相位Δθ和變異概率Pm。

3.1.4 量子旋轉(zhuǎn)門和變異的自適應(yīng)調(diào)整策略

利用量子旋轉(zhuǎn)門相位變換和變異操作實(shí)現(xiàn)染色體更新，令算法具備擴(kuò)展能力和探索能力，從而保證算法能夠快速收斂。通過調(diào)整量子旋轉(zhuǎn)門相位Δθ和變異概率Pm來調(diào)節(jié)H1和H2，實(shí)現(xiàn)。假設(shè)R為一個(gè)正實(shí)數(shù)，若H1Fit*(Xb)，則代表當(dāng)前個(gè)體Fit(Xc)優(yōu)于適應(yīng)度最高的值Fit*(Xb)。此時(shí)，利用模糊邏輯分別增大Δθ和Pm的值，從而增加H1。若H1>R且Fit(Xc)

3.1.5 量子變異操作

3.2 算法描述

按照FQGA-SR算法的基本步驟，將底層網(wǎng)絡(luò)Gsn、遷移需求R和染色體量子比特編碼長度K，以及種群規(guī)模M作為輸出，可利用FQGA算法得到最優(yōu)遷移策略Xb，則Xb={x1,x2,…,xi,…,xK}代表服務(wù)遷移后的節(jié)點(diǎn)承載VNF狀態(tài)，其中xi代表VNFf∈F部署在底層節(jié)點(diǎn)ni∈Nsn上。

為方便理解，F(xiàn)QGA-SR算法主要步驟偽代碼如下。算法將服務(wù)遷移問題分為2個(gè)部分：遷入節(jié)點(diǎn)選擇階段和最短遷移路徑選擇階段。其中，第3行用于獲取最短路徑矩陣S，第4行用于初始化FQGA的模型參數(shù)，第5～9行是種群進(jìn)化過程，第10～13行是FQGA的變異過程。

FQGA-SR算法輸入 底層物理網(wǎng)絡(luò)Gsn,服務(wù)請(qǐng)求Gs,種群規(guī)模M,染色體長度K,進(jìn)化迭代次數(shù)T輸出 最優(yōu)遷移策略Xb1 foreach服務(wù)請(qǐng)求s∈Gsdo2 ifIsRequestSatisfied(Gsn,Gs) then3 利用k-Dijkstra算法計(jì)算最短路徑,并獲取最短路徑矩陣S4 根據(jù)式(13)初始化量子基因種群,獲取N(0)5 while(t

另外，基于FQGA的遷移策略優(yōu)化算法運(yùn)行在星地融合網(wǎng)絡(luò)的控制平面上，通過GEO衛(wèi)星控制器實(shí)時(shí)收集全網(wǎng)狀態(tài)信息，并結(jié)合地面管理控制中心的云計(jì)算中心及邊緣節(jié)點(diǎn)算力，能夠快速有效地得到最優(yōu)遷移決策，實(shí)現(xiàn)VNF遷移并為遷入節(jié)點(diǎn)和相關(guān)鏈路重新分配網(wǎng)絡(luò)資源，以完成服務(wù)遷移重構(gòu)步驟。

4 仿真實(shí)驗(yàn)及分析

4.1 參數(shù)設(shè)置

為評(píng)估所提算法在星地融合網(wǎng)絡(luò)服務(wù)遷移優(yōu)化問題中的有效性和性能表現(xiàn)，本文建立了仿真實(shí)驗(yàn)平臺(tái)進(jìn)行驗(yàn)證。仿真實(shí)驗(yàn)在Intel Core i7-10710U CPU @3.3 GHz、16 GB RAM的主機(jī)上運(yùn)行，采用Matlab 2018b與STK 11聯(lián)合仿真實(shí)驗(yàn)，用于模擬衛(wèi)星星座組網(wǎng)和地面網(wǎng)絡(luò)連接狀態(tài)信息。

通過STK和Matlab聯(lián)合仿真模擬星地融合網(wǎng)絡(luò)中衛(wèi)星網(wǎng)絡(luò)運(yùn)行情況，獲取衛(wèi)星節(jié)點(diǎn)各個(gè)時(shí)刻的可見性，星地、星間鏈路的可持續(xù)時(shí)間，以及地面節(jié)點(diǎn)衛(wèi)星過頂情況等。設(shè)置星地融合網(wǎng)絡(luò)架構(gòu)下的服務(wù)功能鏈重構(gòu)場(chǎng)景，服務(wù)遷移仿真參數(shù)設(shè)置如表2所示，地面設(shè)置1個(gè)核心云節(jié)點(diǎn)、15個(gè)地面邊緣節(jié)點(diǎn)(MEC節(jié)點(diǎn))、3個(gè)LEO衛(wèi)星邊緣節(jié)點(diǎn)(LEO節(jié)點(diǎn))，星地、星間及地面鏈路連接情況隨LEO衛(wèi)星節(jié)點(diǎn)運(yùn)行變化而變化。

表2 仿真參數(shù)設(shè)置Tab.2 Simulation parameters setting

在上述網(wǎng)絡(luò)拓?fù)湎?，單位時(shí)間內(nèi)到達(dá)的SFC請(qǐng)求服從泊松分布，服務(wù)請(qǐng)求到達(dá)率λ為[0.05,0.2]，每個(gè)SFC包含[2,6]個(gè)VNFs，生存時(shí)間為[30,80]ms，每個(gè)VNFs所產(chǎn)生的處理時(shí)延為[120,200]ns。上述仿真參數(shù)服從各自取值范圍的隨機(jī)分布，實(shí)驗(yàn)結(jié)果以10次重復(fù)實(shí)驗(yàn)取平均值。

4.2 結(jié)果分析

綜合考慮算法收斂性、端到端時(shí)延、服務(wù)重構(gòu)成功率和算法運(yùn)行時(shí)間4個(gè)性能指標(biāo)，本文將所提基于模糊量子遺傳算法的服務(wù)遷移重構(gòu)方法(FQGA-SR)與SEC-SM算法[14]、TS-MAPSCH算法[16]和MGA算法[13]進(jìn)行比較，以證明所提算法的有效性及性能表現(xiàn)。

算法收斂性比較如圖2所示。可以看出，所提出的FQGA-SR算法以最快的速度收斂到穩(wěn)定狀態(tài)，大約在迭代次數(shù)達(dá)到58左右趨于穩(wěn)定；TS-MAPSCH和SEC-SM算法速度其次，都在迭代次數(shù)200左右趨于穩(wěn)定；MGA算法收斂速度較慢，在280次左右。同時(shí)，所提FQGA-SR算法和TS-MAPSCH算法在端到端總時(shí)延的優(yōu)化結(jié)果方面表現(xiàn)較好。分析其原因，F(xiàn)QGA-SR算法引入了量子染色體編碼和量子交叉過程，大大地提升了計(jì)算效率，因而求解效果最好。而MGA算法采用傳統(tǒng)染色體編碼方式，在動(dòng)態(tài)網(wǎng)絡(luò)需求和大規(guī)模問題空間下求解較為困難，并且為了避免收斂到局部最優(yōu)，需要犧牲求解速度來提高求解精度，所以收斂速度較慢。

圖2 算法收斂性比較Fig.2 Comparison of algorithm convergence

圖3為不同流量負(fù)載狀態(tài)下，端到端時(shí)延隨服務(wù)請(qǐng)求數(shù)量變化的示意圖，其中圖3(a)和圖3(b)分別為流量負(fù)載60%和90%的狀態(tài)。

(a) 流量負(fù)載60%

(b) 流量負(fù)載90%圖3 端到端時(shí)延比較Fig.3 Comparison of end-to-end delay

可以看出，所提FQGA-SR算法求得的優(yōu)化結(jié)果較MAG算法、TS-MAPSCH算法和SEC-SM算法表現(xiàn)更好。其中，基于遺傳算法的MGA算法收斂速度稍慢，因此波動(dòng)幅度比其余算法稍大；SEC-SM算法的節(jié)點(diǎn)選擇主要依賴于最短路徑算法，未充分考慮資源狀態(tài)，所以部署結(jié)果端到端時(shí)延表現(xiàn)稍差。整體來看，隨著服務(wù)請(qǐng)求數(shù)量的增加，網(wǎng)絡(luò)中的剩余資源不斷減少，后續(xù)到達(dá)的服務(wù)請(qǐng)求部署和遷移受一定影響，端到端時(shí)延的數(shù)值稍顯增加。對(duì)比圖3(a)和圖3(b)，在流量負(fù)載達(dá)到90%時(shí)，網(wǎng)絡(luò)中剩余可用資源較少，可遷移和部署的節(jié)點(diǎn)及鏈路選擇余地較小，因而端到端時(shí)延整體相對(duì)增加。

圖4(a)和圖4(b)分別為服務(wù)重構(gòu)請(qǐng)求到達(dá)率λ=0.05和λ=0.2時(shí)，服務(wù)重構(gòu)成功率隨重構(gòu)請(qǐng)求數(shù)量變化的情況。

由圖4(a)可以看出，請(qǐng)求成功率FQGA-SR算法整體表現(xiàn)最優(yōu)，在重構(gòu)請(qǐng)求達(dá)到250時(shí)，仍能保持0.847的服務(wù)重構(gòu)成功率；其次為MGA算法和TS-MAPSCH算法，最后為SEC-SM算法，其成功率僅為0.765。分析其原因，所提FQGA-SR算法充分考慮了節(jié)點(diǎn)移動(dòng)性和當(dāng)前網(wǎng)絡(luò)拓?fù)錉顟B(tài)，因而能夠更好地做出遷移重構(gòu)決策，MGA算法和TS-MAPSCH算法同屬于啟發(fā)式算法，而SEC-SM算法考慮的觸發(fā)因素主要為流量變化情況，對(duì)網(wǎng)絡(luò)拓?fù)錉顟B(tài)變化感知不明顯，所以效果較差。對(duì)比圖4(a)和圖4(b)可知，隨著服務(wù)重構(gòu)請(qǐng)求到達(dá)率提升至λ=0.2，4種算法的服務(wù)重構(gòu)成功率都隨之下降，且MGA算法表現(xiàn)略優(yōu)于TS-MAPSCH算法。分析其原因，重構(gòu)成功率下降是由于遷移重構(gòu)算法在應(yīng)對(duì)到達(dá)密度較高的服務(wù)請(qǐng)求時(shí)，可能面臨節(jié)點(diǎn)和鏈路被占用，計(jì)算和帶寬資源還未釋放的情況，所以其重構(gòu)成功率較低；而MGA算法表現(xiàn)略優(yōu)，是由于基于遺傳算法的MGA算法在應(yīng)對(duì)較大求解空間規(guī)模時(shí)，其全局求解能力和求解效率略優(yōu)于基于禁忌算法的TS-MAPSCH算法。

圖5顯示了不同流量負(fù)載下的算法運(yùn)行時(shí)間，隨著流量負(fù)載逐漸增加，各算法運(yùn)行時(shí)間也隨之增加。仿真設(shè)置在流量負(fù)載40%～90%。顯然，所提FQGA-SR算法平均運(yùn)行時(shí)間遠(yuǎn)低于MGA算法、TS-MAPSCH算法和SEC-SM算法。以90%負(fù)載為例，F(xiàn)QGA-SR算法的平均運(yùn)行時(shí)間為2.27 s，MGA算法、TS-MAPSCH算法、SEC-SM算法分別為4.38,5.15和6.89 s，前者相比于后3種算法的運(yùn)行時(shí)間分別提升了48%,55%和67%。分析其原因，F(xiàn)QGA-SR算法利用量子疊加原理加速計(jì)算，能夠快速?zèng)Q策出遷移重構(gòu)方案，計(jì)算效率遠(yuǎn)高于其余3種算法；MGA算法在求解空間較大的情況下計(jì)算效率相對(duì)高于其余2種算法，但此時(shí)得到的解可能不是全局最優(yōu)解。

圖5 算法運(yùn)行時(shí)間比較Fig.5 Comparison of algorithm running time

5 結(jié)束語

針對(duì)星地融合網(wǎng)絡(luò)服務(wù)遷移重構(gòu)優(yōu)化決策問題，在考慮用戶需求動(dòng)態(tài)性和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)移動(dòng)性的基礎(chǔ)上，設(shè)計(jì)了一種端到端時(shí)延及遷移成本最小化的聯(lián)合優(yōu)化模型，并結(jié)合模糊邏輯和量子遺傳算法對(duì)模型進(jìn)行了求解。實(shí)驗(yàn)結(jié)果表明，本文提出的FQGA-SR算法在收斂性、有效性和網(wǎng)絡(luò)性能方面具有良好的表現(xiàn)，能夠有效地提升遷移重構(gòu)優(yōu)化部署效率。