田 耕 李 娜

（1.零八一電子集團有限公司 成都 611700）（2.北京機電工程研究所 北京 100074）

1 引言

隨著5G、物聯(lián)網(wǎng)等網(wǎng)絡技術的興起，網(wǎng)絡規(guī)模逐漸增加且用戶請求的服務也更多樣、更復雜，支持靈活遷移、升級和動態(tài)部署的新型網(wǎng)絡體系已成為未來網(wǎng)絡發(fā)展的必然趨勢。網(wǎng)絡功能虛擬化（Network Functions Virtualization，NFV）誕生［1］，使用虛擬化技術實現(xiàn)軟硬分離與解耦。

網(wǎng)絡功能虛擬化是一種先進且高效的解決方案，不過NFV 實施需要面對一個不可忽視的問題，即NFV 資源分配（NFV Resource Allocation，NFV-RA）［2］。NFV 資源分配包括三個階段：虛擬網(wǎng)絡功能鏈的構(gòu)建（VNF Chain Composition，VNF-CC）、虛擬網(wǎng)絡功能轉(zhuǎn)發(fā)圖映射（VNF Forwarding Gr-aph Embedding，VNF-FGE）［3］和虛擬網(wǎng)絡功能調(diào)度（VNF Scheduling，VNF-S）［4］。前兩部分通常組合統(tǒng)稱為虛擬網(wǎng)絡功能放置問題（VNF Placement，VNF-P）。虛擬網(wǎng)絡功能放置問題（VNF-P）是對已到達的服務功能鏈（SFC）進行VNF 映射和流量路由。SFC 是一組有順序的VNF。VNF-P 問題通常用線性規(guī)劃模型和啟發(fā)式算法來求解。對于VNF-P 問題構(gòu)建線性規(guī)劃類模型且以啟發(fā)式算法來求解是現(xiàn)有研究中的主流方法。例如，F(xiàn)ang 等［5］研究了載波網(wǎng)絡中可靠性感知的VNF 部署問題，將兩種可靠性保護機制表述為整數(shù)線性規(guī)劃模型，并提出了基于動態(tài)規(guī)劃和拉格朗日松弛的啟發(fā)式算法。

NFV 環(huán)境中節(jié)點的資源是有限的。大多數(shù)VNF-S 問題研究僅關注調(diào)度順序的優(yōu)化而忽略了VNF 的放置對調(diào)度的影響。VNF-P 和VNF-S 是緊密相連的，將二者統(tǒng)籌考慮、全局尋優(yōu)既是技術演進趨勢，也是NF-V 落地面臨的艱巨挑戰(zhàn)。目前對于VNF-P和VNF-S聯(lián)合優(yōu)化的研究有限且不成熟。例如，Alameddine 等［6］提出了一種跨層策略，用于解決服務功能映射問題、流量路由問題和服務調(diào)度問題等三個互相關聯(lián)的問題，將服務功能鏈調(diào)度問題公式化為混合整數(shù)線性問MILP。目前，啟發(fā)式算法是現(xiàn)有求解方法中的主流。例如，Li等［7］將VNF 映射與調(diào)度問題表述為一個MILP 模型并提出了一個兩階段的啟發(fā)式算法，實現(xiàn)了具有Qos 保證的負載均衡。Wang 等［8］將VNF 放置和調(diào)度相結(jié)合表述為0～1整數(shù)規(guī)劃問題，提出了一種啟發(fā)式的算法來分兩個階段求解。然而，啟發(fā)式算法旨在短時間內(nèi)搜索到目標問題的合法解，局限于局部搜索容易陷入局部最優(yōu)導致算法性能不穩(wěn)定。同時解的差異性很大，求解質(zhì)量無法保證。

針對上述問題，本文提出了一種VNF 放置和調(diào)度聯(lián)合優(yōu)化的模型，將VNF 放置和在此基礎上的VNF 調(diào)度視為統(tǒng)一整體。在放置的基礎上，優(yōu)化每個計算節(jié)點VNF 的執(zhí)行順序，保證了所得服務完成時間的可靠性。本文基于探路者算法提出了一種改進的進化算法，設計了群體劃分機制加強了算法的全局搜索性能，避免陷入局部最優(yōu)。提出交叉和變異策略，減小了對解的破壞，增強算了的局部搜索能力且增加了種群多樣性。提出了精英保留策略加速了算法的收斂。實驗結(jié)果表明，與傳統(tǒng)進化算法相比，該方法在求解質(zhì)量和穩(wěn)定性上具有顯著優(yōu)勢。此外選取了仿真環(huán)境中的3個代表性指標進行分析，進一步確定了實驗結(jié)果的準確性和結(jié)論的可靠性。

2 放置和調(diào)度的聯(lián)合優(yōu)化

2.1 底層網(wǎng)絡與服務請求建模

將底層網(wǎng)絡抽象成一個無向的連通圖G=(V,E)，其中V 表示節(jié)點集合，V={v1,v2,…,v|M|}。E 表示連接節(jié)點之間的鏈路集合，E={e1,e2,…,e|E|}。兩個節(jié)點之間相互通信時，數(shù)據(jù)在鏈路中傳輸會產(chǎn)生鏈路時延。D(e)表示鏈路e的鏈路時延，其中e?E。V中任何節(jié)點都具有轉(zhuǎn)發(fā)數(shù)據(jù)流的能力，并且包含相應的資源，包括計算資源、內(nèi)存資源和IO 資源。部署某種VNF并且維護它的運行需要占用一定的資源。

每個VNF 虛擬機只能提供一個特定的虛擬網(wǎng)絡功能，在某一時刻只能為一條SFC 提供服務。每個SFC 由一系列有序的VNF 組成。SFC 的集合表示為S={s1,s2,...,s|S|}，VNF 的集合為F={f1,f2,...,f|F|}，其中 |S|和 |F|分別表示SFC 與VNF 的種類數(shù)量。其中sn為一個元組，，記錄著第n 種SFC 中包含的VNF 種類和順序，fin?sn，表示sn中的第i 個虛擬網(wǎng)絡功能，n=1,2,...,|S|，i=1,2,...,|sn|。

2.2 問題描述

網(wǎng)絡模型隨機生成并部署幾條SFC，模擬動態(tài)SFC 到達，對新SFC 集合編碼VNF 放置位置，多個SFC可共用VNF實例。在確定放置位置后，采用先到先服務策略調(diào)度所有SFC，得到最大完成時延。每一條SFC 都在承載VNF 的計算節(jié)點之間建立一條滿足約束條件的服務路徑（Service Path，SP）路徑表示為Path(si)。Path(si)=(Vsi,Lsi)，其中Vsi?si表示si中部署的VNF實例集合，Lsi={l1,l2,...,lΓ}，li?E表示Path(si)的邏輯鏈路集合，Γ為邏輯鏈路的數(shù)量。因為SFC 內(nèi)VNF 有序，數(shù)據(jù)流過Path(si)也是有序的，所以邏輯鏈路為有向邊。此外多個邏輯鏈路能部署在同一條物理鏈路上。

調(diào)度過程中考慮三種時延：VNF 在計算節(jié)點上為SFC 提供服務的處理時延；VN-F 之間的數(shù)據(jù)流在鏈路上的傳輸時延；VNF 被多個SFC 共享，VNF 實例在為一個SFC 提供服務時，其他SFC 產(chǎn)生的等待時延。

根據(jù)優(yōu)化目標和約束條件，建立了相應的VNF放置和調(diào)度聯(lián)合模型。

最小化：

其中：

約束條件：

上述優(yōu)化問題中，目標函數(shù)（1）表示S-FC 集合中所有服務執(zhí)行結(jié)束的完成時間最小化。約束（2）Delay(si)表示單個SFC的總時延，無論是初始放置或新到達的SFC。Delay(f)表示f 的處理時延。Delay(l)表示用戶服務請求經(jīng)過邏輯鏈路l時，鏈路上的傳輸時延。Delay(l)表示用戶服務請求經(jīng)過邏輯鏈路l時，鏈路上的傳輸時延。約束（3）～（5）中vi表示任意一個節(jié)點，F(xiàn)(vi)表示該節(jié)點上部署的VNF 實例集合。Rcom(fl)，Rmem(fl)，Rio(fl)表示任意VNF 實例fl部署所需要的計算資源、內(nèi)存資源和IO 資源。Rcom(vi)，Rmem(vi)，Rio(vi)表示節(jié)點vi包含的計算資源、內(nèi)存資源和IO資源。約束（6）中表示邏輯鏈路l(l?Lsi)是否部署在e 上若是則值為1，否則值為0.lbw表示邏輯鏈路l所需的帶寬資源。

3 探路者算法分析與改進

3.1 傳統(tǒng)的探路者算法

一個種群經(jīng)常包含某種社會等級制度，某個個體領導著其他個體進行行動。但是領導是臨時性的，很少有人會知道食物源的確切位置，所以基于這種思想，提出了探路者算法［9］。在所提出的模型中，每個成員在二維、三維或d 維空間中都有一個位置。如果群體中的某個成員位于最有前途的區(qū)域，那么它將被選為探路者。假設問題的所有候選解都是個體的位置向量，群體中的個體可以在二維、三維和d維空間中運動。為了尋找獵物或食物源，提出了下面給出的模型。

其中t 是時間，x 是位置向量，n 為單位向量，fi是個體xi和個體xj的成對相互作用，fp是依賴于全局最優(yōu)個體而產(chǎn)生的全局成對相互作用，ε是振動矢量。

根據(jù)以下方程更新探路者的位置：

其中，xp是探路者的位置向量，Δx是探路者從一個點移動到另一個點的距離，A是波動率的向量。

從本質(zhì)上講，上述集群運動模型不能直接應用于解決優(yōu)化問題，還需要作一些修改才能使其適用。第一個修改如下：

式（9）用于更新種群中普通個體的位置，其中R1，R2為［0，1］間隨機向量，ε由式（12）生成。

第二個修改如下，式（10）用于更新探路者個體的位置。

其中，r3是在［0，1］范圍內(nèi)均勻生成的隨機向量，A在每次迭代過程中用式（11）生成。

3.2 改進的探路者算法

本文提出了改進的探路者算法，用于解決離散優(yōu)化問題。改進的算法修改了原始算法的更新策略，增強了全局搜索能力和求解精度。本文將連續(xù)空間的位置信息映射到SFC整數(shù)編碼向量中，將搜索空間按候選計算節(jié)點個數(shù)進行均勻劃分，從而適配離散優(yōu)化模型。1）整數(shù)編碼策略：原始探路者算法基于d 維空間內(nèi)動物群體的運動而提出，個體解為連續(xù)空間上的向量。本文將連續(xù)空間的位置信息映射到SFC 整數(shù)編碼向量中，將搜索空間按候選計算節(jié)點個數(shù)進行均勻劃分，從第一個候選節(jié)點開始順序分割整個搜索空間，從而用于求解離散優(yōu)化問題。2）精英保留策略：在每一代更新結(jié)束后對種群進行選擇，適應度優(yōu)秀的個體有更大的概率被保留到下一代，可以有效地保證算法的收斂性。3）群體劃分策略：如果探路者的解空間離全局最優(yōu)解較遠，種群很容易陷入局部最優(yōu)，早熟收斂后自然找不到更好的解。因此，將所有個體按照適應度進行排序并且分為兩組。前一組個體為適應度優(yōu)秀的個體Pre_population.后一組個體為適應度差的個體Post_population.Post_population 中個體的更新采用原始的個體更新公式。Pre_population 這個整體作為探路者（Pathfinder），在更新其他個體（Post_population）時，不再朝著某一個固定的Pathfinder 進化，而是從Pre_population集合中隨機選擇個體當成xp。該策略有效增強了算法的全局搜索能力，避免陷入局部最優(yōu)。4）個體交叉及變異搜索策略：受遺傳算法思想的啟發(fā)，Pre_population 中個體的更新時不再采用按維更新的策略，而從Pre_population 中隨機選取一個個體與當前個體按照概率pa=0.6 進行單點交叉。該策略減小了對解的破壞，提高了對較優(yōu)解空間的局部搜索能力?？紤]到交叉策略可能導致種群的多樣性降低，對更新后的Pre_population 個體按照概率pb=0.05進行按維變異。

算法1改進的PFA算法—iPFA

初始化階段

Step1：初始化種群P規(guī)模為N，最大迭代次數(shù)kmax，個體xi(i=1,2,...,N)，搜索空間上下界ub和lb；

Step2：計算個體適應度值，并進行排序；

主循環(huán)階段

Step3：whilek

進行群體劃分，將種群劃分為Pre_p 和Post_p 兩個部分；

Step4：forxiin Post_p

Pre_P中選擇探路者更新xi，式（9）；

end for

Step5：forxixjin Pre_P

更新xixj，采用交叉搜索策略；

end for

Step6：forxiin Pre_P

更新個體解，采用變異搜索策略；

end for

Step7：適應度評估；

k=k+1；

輸出階段

Step8：輸出全局最優(yōu)個體xb；

4 算法性能評估

這個部分對提出的算法進行了仿真實驗并統(tǒng)計結(jié)果。通過不同場景下的仿真對比分析算法性能。本節(jié)設計了八個場景，前四個場景的拓撲為真實世界的拓撲，后四個場景為隨機的拓撲，由Python 中NETWORKX 生成。仿真實驗場景中節(jié)點資源包括：CPU資源、內(nèi)存資源和IO資源。CPU資源和內(nèi)存資源在30～50 之間隨機生成，IO 資源在50～70 之間隨機生成。實驗拓撲的鏈路時延在0.1ms～0.2ms 范圍內(nèi)隨機生成，拓撲鏈路最大帶寬為500Mb/s。不同節(jié)點的單位處理時延在1ms～2ms范圍內(nèi)隨機生成，邏輯鏈路的帶寬資源10Mb/s～30Mb/s之間隨機生成。

如3.2節(jié)所述，本文提出的iPFA算法基于整數(shù)編碼，并包含精英保留、群體劃分和個體交叉變異等策略。為了研究提出改進策略的有效性，本文比較了多個場景下的四種PFA 算法。本文所有實驗運行在PC 機上，其具體信息為Windows 10 OS，Intel（R）Core（TM）i5-4210 CPU 2.6 GHz and 8 GB RAM.通過對每種算法運行20 次，對每次求得的歷史最優(yōu)適應度取平均值，可以得到最終的歷史最優(yōu)適應度。本節(jié)主要采用歷史最優(yōu)適應度方差和平均值表格、學生t 檢驗以及畫箱線圖等方式來比較各個算法的性能。用圖表的形式直觀地對比算法的結(jié)果。

表1 實驗拓撲參數(shù)

對于本文提出的模型，選取了七個常見的進化算法進行對比實驗，有基于基因進化思想而提出的藤壺交配算法（BMO）［10］?；谖锢憩F(xiàn)象提出的引力搜索算法（GSA）［11］，球面進化算法（SEA）［12］，基于群體智能的提出的樽海鞘算法（SSA）［13］，粒子群算法（PSO）［14］。基于社會行為提出的團體分配算法（TAHA）［15］和社會模擬算法（S-MA）［16］。

表2對比算法在8個測試場景下得到的實驗結(jié)果。所有的測試場景下，iPFA 都能得到最優(yōu)的適應度，多次實驗的結(jié)果方差在大多數(shù)場景下都比較小，表明了算法的求解較為穩(wěn)定，實驗結(jié)果具普遍性。圖1 是九個算法的箱線圖。本文提出的算法的箱盒在最優(yōu)適應度值最小，且從箱線圖中可看出iPFA 算法相比于其他八種算法，數(shù)據(jù)更集中，箱型更緊湊，異常點分布合理，說明了在解決本文提出的VNF 放置與調(diào)度聯(lián)合優(yōu)化問題時性能最優(yōu)，且具有較高的穩(wěn)定性。

圖1 歷史最優(yōu)解箱線圖

表2 對比算法在8個場景下的實驗結(jié)果

5 結(jié)語

本文將NFV 資源調(diào)度中的兩個階段的問題相結(jié)合，提出了一種VNF 放置和調(diào)度聯(lián)合優(yōu)化的模型。滿足相應的約束的前提下，最小化服務功能鏈的最大完成時間。同時提出了一種基于探路者算法的改進優(yōu)化算法，優(yōu)化虛擬網(wǎng)絡功能的放置位置，調(diào)度采用先來先服務的策略使得所有服務功能鏈最大完成時間最短。通過多個場景的仿真測試，統(tǒng)計結(jié)果顯示與傳統(tǒng)的進化算法相比，該方法在解決放置和調(diào)度聯(lián)合優(yōu)化問題上有顯著優(yōu)勢。同時選取了仿真環(huán)境中的三個代表性指標進行分析，進一步確定的實驗結(jié)果的準確和普遍性，同時加強結(jié)論的可靠性和說服力。