一種星地融合網絡動態服務遷移重構方法

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

(1.陸軍工程大學 石家莊校區，河北 石家莊 050003；2.北京航天飛行控制中心，北京 100094；3.北京空間信息中繼傳輸技術研究中心，北京 100094；4.電子信息系統復雜電磁環境效應國家重點實驗室，河南 洛陽 471003)

0 引言

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

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

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

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

1 問題描述

星地融合網絡服務遷移重構過程如圖1所示。星地融合網絡的基本結構包含由衛星網絡、無人平臺和地面網絡組成的3層平面網絡結構，以及地面管理控制中心和GEO衛星控制器組成的2層控制結構。假設LEO衛星邊緣節點和地面邊緣節點都具備一定算力和存儲資源，可以根據部署策略承載多種VNFs，能夠為用戶提供高速網絡接入、邊緣側服務支持、數據中繼和鏈路回程。同時，無人機節點和衛星節點都擁有通信中繼和鏈路回程能力，由于無人機受能源和荷載限制，暫不考慮將無人機節點作為承載VNF的邊緣節點，僅承擔中繼轉發功能。衛星網絡平面中的衛星節點通過定向無線通信鏈路互相連接，包括微波、激光、6G通信中的毫米波和自由空間光學鏈路等，因而支持高速數據傳輸。

圖1上方為星地融合網絡用戶提出服務請求的基本過程，當前服務提供的對象為可移動車輛終端用戶，車載終端用戶從人口密集型核心城區由西向東駛向偏遠地區，該車輛用戶執行任務所需求的服務功能鏈為有順序的網絡功能VNF-1，VNF-2和VNF-3。

圖1 星地融合網絡服務遷移重構過程Fig.1 Service migration and reconfiguration process of satellite-terrestrial integrated network

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

車輛用戶移動至偏遠地區后，此時失去地面邊緣節點的接入支持和服務支持，管理控制平面根據實時網絡狀態信息和車輛用戶服務請求，運行服務遷移和重構算法得出最優遷移位置和遷移路徑。例如，將地面邊緣節點N3上的VNF-1遷移至衛星邊緣節點N9上，將N1上的VNF-2遷移至衛星邊緣節點N7上，遷移路徑按照最短路徑進行。遷移后用戶車輛的數據流量按照SFP2(N9-N7-N2)到達目的節點N4，以滿足車輛用戶的通信需求和服務需求，并保持通信和服務的連續性及可靠性。

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

2 服務遷移重構模型構建

2.1 系統模型

假設當前星地融合網絡中地面邊緣節點和衛星邊緣節點的數量已知且固定，網絡用戶和衛星節點可隨時間變化而移動，各個節點和鏈路之間的連接狀態和資源狀態可通過SDN/NFV全局狀態感知能力獲取，即網絡拓撲狀態和網絡資源狀態可知。不同用戶對網絡服務請求的服務需求和資源需求到達呈一定規律。

① 底層物理網絡模型

② 服務請求

表1 主要符號及定義Tab.1 Main notations and definitions

服務請求部署狀態和物理網絡資源使用情況隨時間變化而變化，利用SDN/NFV集中控制功能可以獲取當前時刻的網絡狀態，每個邊緣節點所能承載的用戶服務請求數與當前剩余資源和用戶請求數有關。

2.2 優化目標

考慮到用戶端到端時延是影響服務體驗最重要的性能指標之一，可將時延作為服務遷移問題的優化目標。除了數據傳輸過程產生的端到端時延，服務遷移過程會在原有時延的基礎上產生額外時延，因此需要作為遷移成本另外考慮。

因此，星地融合網絡中的服務遷移和重構問題的優化目標可以定義為：在保證服務連續性的同時，最小化端到端時延和遷移成本。下面給出端到端時延和遷移成本的公式化描述，以及服務遷移和重構問題的優化目標及約束條件。

① 端到端時延

端到端時延的計算為用戶服務請求到達邊緣接入點，用戶數據通過網絡傳輸并依次通過服務路徑中的服務功能所在節點，完成所有服務功能所產生的時延，主要包括傳播時延Dp、傳輸時延Dtr和處理時延Dpr三部分，可表示為：

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

(1)

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

(2)

(3)

(4)

② 遷移成本

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

(5)

2.3 問題建模

當星地融合網絡中內外部環境變化觸發服務遷移條件時，采用服務遷移和重構優化模型求解最優服務遷移策略，主要為遷入節點和遷移路徑的選擇問題。考慮網絡用戶的服務體驗及運營成本，將最小化端到端時延和遷移成本作為優化目標，可表示為：

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)為優化問題的目標函數，其目的是獲得端到端時延和遷移成本最小的最優遷移位置和遷移路徑，其中w1和w2分別為端到端時延D(t)和遷移成本Mc(t)的修正系數，用于動態調整不同服務對時延和遷移成本的不同需求。式(7)～式(12)為約束條件，主要考慮底層物理網絡資源限制與服務遷移需求之間的均衡。其中，式(7)和式(8)保證一個服務遷入節點和鏈路最多只能映射到一個底層物理節點和鏈路上；式(9)保證服務遷入節點的計算資源需求不超過所映射到的底層節點計算資源容量；式(10)保證服務遷移鏈路的帶寬資源需求不超過所映射到的底層鏈路帶寬資源容量；式(11)利用布爾變量表示該底層節點是否被選為當前服務部署節點，1為部署，0為否；式(12)同上，代表該底層鏈路是否被選為服務請求虛擬鏈路，1為映射，0為否。

3 算法設計及描述

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

因此，選擇采用量子機器學習與傳統算法結合的模式，提出了一種基于模糊邏輯(Fuzzy Logic，FL)和量子遺傳算法(Quantum Genetic Algorithm,QGA)的服務遷移優化算法。將對所提算法的基本步驟進行詳細闡述，并給出算法的偽碼，為算法的仿真實驗驗證給出鋪墊。

3.1 基本步驟

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

3.1.1 建立最短路徑矩陣S

首先，建立FQGA-SR算法的輸入矩陣S，用于表示底層網絡Gsn內任意兩底層節點間的關聯關系，矩陣S的第i行和第j列代表節點ni和節點nj之間所部署SFC的最小時延。利用k-Dijkstra算法計算兩節點間的最短路徑，得到矩陣S。

3.1.2 FQGA-SR算法初始化

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

(13)

3.1.3 子種群進化

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

(14)

可將適應度函數Fit(Xc)表示為Fit(Xc)=[Obj]-1，Obj為當前優化目標，即最小化端到端時延和遷移成本。根據適應度函數定義H2，用于衡量當前與適應度密切相關的程度，則H2可表示為：

(15)

式中，Fit*(Xb)為當前適應度最高的值。

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

3.1.4 量子旋轉門和變異的自適應調整策略

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

3.1.5 量子變異操作

3.2 算法描述

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

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

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

另外，基于FQGA的遷移策略優化算法運行在星地融合網絡的控制平面上，通過GEO衛星控制器實時收集全網狀態信息，并結合地面管理控制中心的云計算中心及邊緣節點算力，能夠快速有效地得到最優遷移決策，實現VNF遷移并為遷入節點和相關鏈路重新分配網絡資源，以完成服務遷移重構步驟。

4 仿真實驗及分析

4.1 參數設置

為評估所提算法在星地融合網絡服務遷移優化問題中的有效性和性能表現，本文建立了仿真實驗平臺進行驗證。仿真實驗在Intel Core i7-10710U CPU @3.3 GHz、16 GB RAM的主機上運行，采用Matlab 2018b與STK 11聯合仿真實驗，用于模擬衛星星座組網和地面網絡連接狀態信息。

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

表2 仿真參數設置Tab.2 Simulation parameters setting

在上述網絡拓撲下，單位時間內到達的SFC請求服從泊松分布，服務請求到達率λ為[0.05,0.2]，每個SFC包含[2,6]個VNFs，生存時間為[30,80]ms，每個VNFs所產生的處理時延為[120,200]ns。上述仿真參數服從各自取值范圍的隨機分布，實驗結果以10次重復實驗取平均值。

4.2 結果分析

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

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

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

圖3為不同流量負載狀態下，端到端時延隨服務請求數量變化的示意圖，其中圖3(a)和圖3(b)分別為流量負載60%和90%的狀態。

(a) 流量負載60%

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

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

圖4(a)和圖4(b)分別為服務重構請求到達率λ=0.05和λ=0.2時，服務重構成功率隨重構請求數量變化的情況。

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

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

圖5 算法運行時間比較Fig.5 Comparison of algorithm running time

5 結束語

針對星地融合網絡服務遷移重構優化決策問題，在考慮用戶需求動態性和網絡拓撲結構移動性的基礎上，設計了一種端到端時延及遷移成本最小化的聯合優化模型，并結合模糊邏輯和量子遺傳算法對模型進行了求解。實驗結果表明，本文提出的FQGA-SR算法在收斂性、有效性和網絡性能方面具有良好的表現，能夠有效地提升遷移重構優化部署效率。