云環(huán)境下實現(xiàn)容器部署的加速粒子群優(yōu)化算法

陸海鋒 趙嘉凌 歐陽學名 周娜琴 左利云

摘 要：基于容器的微服務部署是一個具有挑戰(zhàn)性的問題，為獲得更好的用戶體驗并給云供應商帶來更多的利潤，需要在降低微服務的故障率和減少響應時間的同時提高資源利用率。提出了一種改進的加速粒子群優(yōu)化算法，用于解決集群中微服務容器部署的多目標優(yōu)化問題。該算法通過考慮微服務之間的調用關系，使得容器聚集在一起，從而降低服務的數(shù)據(jù)傳輸成本、減少故障率，并提高集群資源利用率。與現(xiàn)有部署算法相比，實驗結果表明，所提出的優(yōu)化算法在服務間的數(shù)據(jù)傳輸開銷、故障率和資源利用率等性能指標上有明顯改善。具體表現(xiàn)在：容器聚集度的提升達到40%以上，數(shù)據(jù)傳輸消耗平均有提升4%以上，故障率減少10%～20%，利用率提升3%左右。

關鍵詞：云計算； 微服務； 容器； 加速粒子群算法； 多目標優(yōu)化

中圖分類號：TP393.09?? 文獻標志碼：A

文章編號：1001-3695（2024）03-016-0756-08

doi：10.19734/j.issn.1001-3695.2023.07.0312

Accelerated particle swarm optimization algorithm forcontainer deployment in cloud environments

Lu Haifeng1， Zhao Jialing1， Ouyang Xueming2， Zhou Naqin3， Zuo Liyun4

（1.Information Center Dept.， Zhaoqing University， Zhaoqing Guangdong 526061， China; 2.School of Software， South China University of Technology， Guangzhou 510006， China; 3.Cyberspace Institute of Advanced technology， Guangzhou University， Guangzhou 510006， China; 4.School of Computer Science， Guangdong University of Petrochemical Technology， Maoming Guangdong 525000， China）

Abstract：Container-based microservice deployment is a challenging problem that aims to improve user experience and increase cloud providers profitability by reducing microservice failure rates and response times while maximizing resource utilization. This paper presented an enhanced accelerated particle swarm optimization algorithm to tackle the multi-objective optimization problem of microservice container deployment in a cluster. By considering the invocation relationships between microservices， the algorithm facilitated the aggregation of containers， thereby reducing data transmission costs， lowering failure rates， and enhancing cluster resource utilization. Experimental results demonstrate that the proposed optimization algorithm yields significant improvements in performance measures including data transmission overhead， failure rate， and resource utilization when compared to existing deployment algorithms. Specifically， the algorithm achieves a container aggregation improvement exceeding 40%， an average increase in data transmission consumption of over 4%， a decrease in failure rate by 10% to 20%， and an increase in utilization rate by roughly 3%. The aforementioned findings attest to the efficacy of the proposed algorithm.

Key words：cloud computing; microservices; container; accelerated particle swarm optimization; multi-objective optimization

0 引言

在云環(huán)境中，計算資源通常以虛擬機（VM）或容器的方式提供各種計算服務，而應用程序則采用微服務架構模式來向用戶提供服務［1～3］。

微服務架構已被廣泛應用于云應用系統(tǒng)的構建和部署。與傳統(tǒng)的單體式應用不同，微服務架構采用強解耦的方式將單體應用程序拆分成一組小粒度的服務，這些服務通常以VM和容器的形式分布在云數(shù)據(jù)中心（CDC）中。這些服務通過輕量級的通信方式進行交互，并通過組合構建應用系統(tǒng)［4］。用戶可以通過云平臺提供的操作來部署應用系統(tǒng)，而這些應用系統(tǒng)通過基于容器的調度引擎協(xié)調使用CDC的計算資源并進行交互。

基于容器的微服務部署和資源管理是一個重要問題。微服務架構已成為云計算領域的主導趨勢，將單塊應用程序拆分為多個面向場景的服務塊（微服務）。拆分過程導致高度動態(tài)的執(zhí)行場景，在這個場景中，各種串行的微服務以不同的方式競爭計算資源［5］。目前，基于操作系統(tǒng)級別容器的部署方法，如Linux容器（LXC）和Docker等，已成為微服務部署的主流技術。與虛擬機不同，這種容器是一種更輕量級的虛擬化方法，具有較少的計算和存儲資源需求，更短的啟動時間。容器使用命名空間來打包系統(tǒng)的計算資源，使得微服務的部署和擴展變得更加容易［6］。通過調整服務器和網(wǎng)絡資源來適應集群中工作負載的快速變化，以緩解資源耗盡或滿足服務性能的要求，Valsamas等人［7］研究了一種新的云編排策略，稱為虛擬化技術混合（VTB）。VTB考慮支持替代虛擬化選項的邊緣云，包括多類型、相同或類似服務的容器構建，方便它們有效地混合使用，以處理具有挑戰(zhàn)性資源需求的情況——具有不同的資源需求和性能能力，研究團隊還提供了一個相關的優(yōu)化框架，所提出的策略可增加服務的用戶數(shù)量，并能有效提高服務器和網(wǎng)絡資源的利用率。然而，構建高效的微服務部署和資源管理算法需要綜合考慮用戶的體驗質量和云提供商的利潤，例如降低微服務的響應時間和故障率，提高集群的資源利用率。為解決這一問題，本文通過優(yōu)化服務間的平均數(shù)據(jù)傳輸開銷、執(zhí)行故障率和集群的資源利用率，以實現(xiàn)用戶和云提供商間的利益平衡。在微服務部署過程中，根據(jù)微服務之間的調用關系進行容器實例的部署，微服務通過調用關系進行組合構建服務功能鏈（SFC）［8］。然后，將SFC中的微服務容器實例盡可能聚集在同一計算服務器節(jié)點或CDC中，以降低服務間的數(shù)據(jù)傳輸成本和提高集群資源利用率，同時考慮服務執(zhí)行的可靠性問題。

本文的主要貢獻如下：

a）確定了微服務部署的優(yōu)化目標，包括執(zhí)行容器聚集、服務間數(shù)據(jù)傳輸開銷、服務執(zhí)行故障率和集群資源利用率。針對這些優(yōu)化目標，構建了一個多目標優(yōu)化問題。

b）提出了一種改進的加速粒子群優(yōu)化算法來解決微服務容器部署的多目標優(yōu)化問題。該算法利用適應度函數(shù)值選擇全局最優(yōu)解，并通過調整粒子的速度和位置來搜索最優(yōu)解空間。

c）通過實驗結果表明，與其他算法相比，該算法在數(shù)據(jù)傳輸成本、故障率和資源利用率等性能指標上取得了顯著的改進，證明了該算法的可行性和有效性。

1 相關研究

微服務實例部署和CDC資源利用是IoT云環(huán)境中至關重要的問題，它直接影響到最終用戶和云服務提供商之間的利益平衡。CDC資源管理優(yōu)化是研究者們關注的熱點問題。目前已有多種相關的服務部署策略和調度方法：

首先，在云環(huán)境下，研究者傾向于采用元啟發(fā)策略來解決多目標優(yōu)化問題，以獲得最優(yōu)解（即Pareto解）。使用元啟發(fā)策略的主要原因在于它是一種隨機算法，具有不確定性的特點，并且不受優(yōu)化問題的數(shù)學性質的限制。此外，群體中的個體通過協(xié)作可以更好地適應環(huán)境和相互交互，有更多機會獲得全局最優(yōu)解。例如，Liu等人［9］提出了一種進化博弈算法優(yōu)化IoT環(huán)境中的服務組合和部署。Gao等人［10］為解決QoS和魯棒性的雙目標服務組合和優(yōu)化選擇（BoSCOS）問題，構建了兩個準則及其數(shù)學模型，并提出了一種增強多目標灰狼優(yōu)化器（SMOGWO）來高效解決上述模型。為優(yōu)化容器的分配和彈性管理，Ahmad等人［6］提出了一種非支配排序遺傳算法-Ⅱ（GA-NSGA-Ⅱ），該算法能解決云集群、容器、微服務等云架構中的資源管理優(yōu)化問題，并在系統(tǒng)供應、系統(tǒng)性能、系統(tǒng)故障和網(wǎng)絡開銷方面獲得明顯的改善和提高。Zhao等人［11］提出了一種基于歷史經(jīng)驗引導的信息素更新策略的蟻群優(yōu)化算法，以提高云中的微服務部署與資源管理效率和增強優(yōu)化，并通過學習自動機根據(jù)搜索歷史自適應地選擇適合的信息素更新方法。為完成無人機的任務卸載，Mousa等人［12］針對該混合整數(shù)非線性約束優(yōu)化問題，提出了一種采用新的變異和交叉操作符的離散差分進化算法，并應用蟻群優(yōu)化（ACO）算法來尋找無人機在集群頭部之間遍歷的最短路徑。針對在不同資源中心部署和啟動微服務實例的問題，Ma等人［13］提出了一個基于進化多目標理論的優(yōu)化問題模型，并用一種知識驅動的進化算法（NSGA-Ⅲ）來解決該問題模型，尋找不同資源中心微服務實例的最優(yōu)部署和啟動策略。

隨著任務或請求規(guī)模的增加和云資源的動態(tài)性，負載平衡、資源利用率、任務分配和系統(tǒng)性能等問題變得越來越突出。由于粒子群優(yōu)化算法在多目標優(yōu)化問題中的有效性，研究者們已將其應用于云環(huán)境中的優(yōu)化策略。與傳統(tǒng)優(yōu)化方法相比，元啟發(fā)式算法在解決微服務部署這類多目標優(yōu)化問題時具有獨特的優(yōu)勢，能夠降低問題的復雜性，廣泛應用于云環(huán)境中的多目標組合優(yōu)化問題中。在各種元啟發(fā)式算法中，粒子群優(yōu)化（PSO）是一種著名的元啟發(fā)式技術，用于解決優(yōu)化問題。PSO適用于動態(tài)任務調度、工作流調度和負載平衡。PSO在運行開始時具有很強的全局搜索能力，并在運行接近結束時進行局部搜索［14］。元啟發(fā)式算法包括加速粒子群優(yōu)化（APSO）、進化博弈策略、灰狼算法（WA）、遺傳算法（GA）、蜜蜂算法（HBA）、蟻群優(yōu)化（ACO）和人工魚群算法（AF）等。其中，APSO是粒子群優(yōu)化算法的改進版，通過使用群體的全局最優(yōu)解來促進算法的收斂性和隨機性［15］。本文針對優(yōu)化服務間的數(shù)據(jù)傳輸開銷、執(zhí)行部分和集群資源利用率，提出了一種改進的加速粒子群優(yōu)化算法，用于解決微服務容器部署的多目標優(yōu)化問題。

隨機初始化搜索解是其中的一個關鍵特征。然而，提供有效的初始化解可以顯著提高啟發(fā)式算法的性能。Alsaidy等人［16］提出了一種改進的粒子群優(yōu)化初始化方法，利用啟發(fā)式算法進行初始化，采用最長作業(yè)優(yōu)先到最快處理器（LJFP）和最小完成時間（MCT）算法來初始化PSO，該團隊提出的LJFP-PSO和MCT-PSO算法的性能通過最小化完成時間、總執(zhí)行時間、不平衡度和總能耗指標進行評估。在解決云計算中的任務調度問題時，Dubey等人［17］提出了一種新穎的混合任務調度算法——化學反應部分粒子群優(yōu)化（CR-PSO），可以在可用虛擬機上分配多個獨立任務。該算法增強了傳統(tǒng)的化學反應優(yōu)化和部分粒子群優(yōu)化，并通過結合特征進行混合化，以找到最佳的任務調度順序，使得任務可以基于需求和截止時間同時進行處理，以改善成本、能量和完成時間等因素的質量。

與前述工作不同，本文的優(yōu)化目標包括服務間的數(shù)據(jù)傳輸開銷、執(zhí)行故障率和微服務容器聚集值，并采用加速粒子群優(yōu)化算法（APSO）解決服務容器部署問題。本文提出的部署策略通過服務間的調用關系，將服務功能鏈中服務的執(zhí)行容器進行聚集，以降低服務的數(shù)據(jù)傳輸成本、執(zhí)行故障率，并提高CDC的資源利用率。改進的加速粒子群優(yōu)化算法（APSO-CDSM）用于解決基于微服務容器部署的多目標優(yōu)化問題，其優(yōu)越性主要體現(xiàn)在：

a）APSO-CDSM算法能有效地解決多目標優(yōu)化問題，通過使用APSO算法進行優(yōu)化，可以快速有效地找到微服務容器部署中的三個性能指標（服務間數(shù)據(jù)傳輸開銷、執(zhí)行部分和集群資源利用率）的近似最優(yōu)解，從而提高系統(tǒng)的性能和效率。

b）改進PSO算法。APSO-CDSM是PSO算法的改進版，通過利用群體的全局最優(yōu)解來促進算法的收斂性和隨機性。這種改進使得APSO-CDSM算法在運行初期具有很強的全局搜索能力，有助于找到全局最優(yōu)解；同時在運行接近結束時，算法會進行局部搜索，進一步優(yōu)化解的質量，能有效地提高全局搜索和局部搜索能力。這種全局搜索和局部搜索能力使APSO-CDSM算法在解決復雜問題時具備較好的收斂性和隨機性，更適用于解決復雜的多目標優(yōu)化問題，并且在算法性能方面可能具有更好的表現(xiàn)。

2 容器部署建模及目標模型

2.1 容器部署模型形式化描述

云平臺中，用戶可通過平臺提供的操作來部署應用程序?；谌萜鞯恼{度引擎根據(jù)微服務接收的用戶請求數(shù)和所需資源數(shù)，尋找合適的計算服務器來部署服務容器。為了實現(xiàn)用戶和云提供商之間的利益平衡，即減少服務執(zhí)行的響應時間和降低故障率，并提高集群的資源利用率，本文提出將同一服務功能鏈（SFC）中的微服務容器盡量聚集到同一個服務器節(jié)點或同一容器數(shù)據(jù)中心（CDC）。

設Users={userv|1≤v≤V}為用戶集，userv=〈ureqsv，uposv〉且v∈{V}，其中，ureqsv為用戶請求應用程序的次數(shù)，用戶所在的位置uposv=〈posx，posy〉。Apps={appc|1≤c≤C}表示應用程序集， appc=〈ureqsc，SFCc〉且c∈{C}。SFCc=〈MSsc，Edsc〉表示應用程序的服務功能鏈SFC，MSsc={MSi|1≤i≤I}。MSi=〈Msreqi，ReqsCPUi，ReqsStorei，ReqThri〉，其中，Msreqi表示請求服務MSi的次數(shù)；ReqsCPUi和ReqsStorei分別表示請求/調用服務MSi一次所需的CPU和存儲資源量；ReqThri表示請求/調用服務的最大次數(shù)（閾值）。

在CDC中，設PMs={pmj|1≤j≤M}為計算服務器集群。pmj=〈pmCPUj，pmStorej，pmposj〉。其中，pmCPUj、pmStorej分別為服務器的CPU資源和存儲資源；pmposj=〈pmxj，pmyj〉為服務器所在的位置。

令alloc（MSi）≡conk（k≥1）表示服務MSi被封裝在容器conk中執(zhí)行，當TReqsi=ureqsc×Msreqi≥ReqThri時，則需擴展容器實例以平衡負載；那么，容器實例擴展數(shù)量為Cinsi=［TReqsiReqThri］=［ureqsc×MsreqiReqThri］。在此，alloc（conk）≡pmj表示容器conk部署在服務器節(jié)點pmj，可允許多個容器實例部署在每個服務器中。由上述可知，I個微服務的容器實例部署在M個服務器節(jié)點可表示為［xij］I×M，xij=1表示微服務MSi的容器實例部署在節(jié)點pmj，否則表示未部署。

2.2 模型目標函數(shù)

在此，根據(jù)容器部署模型目標可以建立以下三個目標函數(shù)，分別為：服務間的數(shù)據(jù)傳輸開銷、執(zhí)行故障率、集群的資源率以及微服務容器聚集。

2.2.1 服務間的數(shù)據(jù)傳輸時耗函數(shù)

CDC的集群通過高速網(wǎng)絡進行連接，噪聲干擾可被忽略。那么，影響服務間的數(shù)據(jù)傳輸開銷的因素有：容器鏡像大小IMSi、部署容器的服務器間的網(wǎng)絡距離Djj′、服務間的請求次數(shù)Msreqii′和傳輸數(shù)據(jù)量TDii′。由于一個微服務的容器實例可部署到多個計算服務器中，為此，在計算服務間的數(shù)據(jù)傳輸開銷時采用服務間的多個容器對的數(shù)據(jù)傳輸時耗的平均值，如式（1）所示。

其中：X是多目標優(yōu)化問題的決策向量。式（9）～（11）是優(yōu)化目標函數(shù)。式（12）～（16）是多目標優(yōu)化問題的約束條件，分別是：a）ReqsCPUixij≤pmCPUj表示CPU資源能滿足微服務對CPU的需求約束；b）ReqsStoreixij≤pmSorej表示服務器節(jié)點的存儲或RAM能滿足微服務對存儲或RAM的需求；c）TReqsixij≤ReqThri表示確保用戶的微服務請求數(shù)量小于系統(tǒng)最大閾值，以確保請求能獲得響應；d）∑Mi=1xij=1確保至少有一個容器實例能滿足微服務的部署要求；e）∑Mj=1xij≥1是資源競爭互斥條件，確保同一微服務對應的容器只有一個且僅有一個能部署到同一個物理服務器內，避免因容器間的資源競爭而造成死鎖。

由上述的問題描述模型可知，該多目標優(yōu)化問題是一個NP-hard問題，主要以計算和存儲資源量和請求閾值作為約束，同時優(yōu)化服務間的數(shù)據(jù)傳輸開銷、容器聚集值和故障率等目標函數(shù)。由于元啟發(fā)式算法在求解多目標優(yōu)化問題的優(yōu)越性，所以本文采用加速粒子群優(yōu)化算法（APSO）來解決該多目標優(yōu)化問題。APSO主要通過對粒子的位置和速度進行改進來降低隨機性，從而實現(xiàn)Pareto解集的最優(yōu)解的快速收斂。

3 目標函數(shù)求解——加速粒子群優(yōu)化算法

3.1 APSO算法

粒子群優(yōu)化算法（PSO）是一種通過模擬鳥群覓食的智能群體優(yōu)化算法。該算法的核心思想是：在鳥群覓食過程中，個體為了尋找到食物目標需在搜索空間中不斷調整自身的飛行軌跡。改變飛行軌跡包括自身經(jīng)驗和全體經(jīng)驗兩個因素。自身經(jīng)驗是一種局部最優(yōu)（personal best，Pb），即個體最優(yōu)位置；而全體經(jīng)驗是一種全局最優(yōu)（global best，Gb），即群體中的最優(yōu)位置。然后，群體中的個體通過不斷改變自身位置和速度來逼近最優(yōu)目標，從而實現(xiàn)尋優(yōu)目標。為了提升粒子群優(yōu)化算法的全局最優(yōu)解的收斂速度，提出一種改進版的PSO，即加速粒子群優(yōu)化（APSO）算法。APSO算法是采用全局最優(yōu)來更新速度。假設在N維搜索空間中，粒子群為Pops={pi|1≤i≤P}，pi=〈Xi，Vi〉，其中，Xi={Xni|1≤n≤N}是粒子的位置向量，Vi={Vni|1≤n≤N}是粒子的速度向量。對于t（t為某一時刻或迭代次數(shù)），粒子pi的速度和位置更新公式分別如式（17）和（18）所示。

Xi（t+1）=Vi（t+1）+（1-σ）Xi（t）（18）

其中：σ∈［0.1，0.7］；ρ∈［0.1，0.5］L，L是變量刻度；ε∈rand（0，1）為隨機向量，其值為0～1；Gb*為全局最優(yōu)。

3.2 粒子編碼

APSO算法關鍵問題之一在于解決粒子編碼，每個粒子個體都傾向于實現(xiàn)優(yōu)化目標以獲得更好的值；并且在個體尋優(yōu)過程中，需不斷地調整位置和速度，以便生成新的解。根據(jù)第2章建立的優(yōu)化問題，使用字符串對個體進行編碼，即采用數(shù)組的方式來表達粒子，數(shù)組的每個元素對應一個微服務，序列號為微服務ID，粒子pi（1≤i≤P）的結構如表1所示，包含了I個微服務。在表1中，服務器節(jié)點列表是部署微服務容器的節(jié)點ID，每個節(jié)點ID只出現(xiàn)一次，這是基于式（11）的約束，主要是為了避免因爭奪資源而發(fā)生沖突，所以約定同一微服務在同一服務器只部署一個容器實例。

在服務器節(jié)點列表中，每個節(jié)點ID采用0-1編碼表示。令集群中總共有M=240個服務器節(jié)點，節(jié)點ID的編碼長度nID=［log2M］，對應的0-1編碼為［11110000］。服務器節(jié)點進行如下的設置編碼，如MS1的服務器節(jié)點列表為XMS1={［00000111］，［00001001］，［00100001］}?；诖耍琗k=（XMS1，XMS2，…，XMSI）為粒子pi的位置，即為優(yōu)化問題的一個解。

由上述粒子的位置可知，其值在0～1變動，本文使用sigmoid函數(shù)來刻畫0～1的變換速度vt。

sigmoid（vt）=11+evt（19）

x=1 若rand＜sigmoid（vt）0 else（20）

那么，對于任意t，分別對粒子pi的速度和位置更新公式進行改進，如式（21）和（22）所示。

Vi（t+1）=Vi（t）+σ（x*n（t）-xn（t））+ρ*rand（1，nID）（21）

xi（t+1）=1 若rand＜sigmoid（vt）0 else（22）

其中：n∈{nID}；x*n是全局最優(yōu)粒子的位置狀態(tài)。

3.3 適應度函數(shù)

針對第2章提出的多目標優(yōu)化問題，為了獲得問題模型的次優(yōu)解或最優(yōu)解，本文采用APSO算法來實現(xiàn)微服務的容器部署，即將微服務對應的多個容器實例部署到合適的計算服務器。在部署過程中，每個粒子pi的位置Xi都是問題的解。在此，本文采用適應度值來評估每個位置Xi，通過歸一化方法將三個優(yōu)化目標函數(shù)聚合到一個評估函數(shù)中，其公式如式（23）所示。

Fitness（X）=γ1Trans（X）-TransminTransmax-Transmin+

γ2CAV（X）-CAVminCAVmax-CAVmin+γ3MSF（X）-MSFminSEFmax-MSFmin（23）

其中：0≤γi≤1且∑3i=1γi=1，γi可根據(jù)實際業(yè)務需求進行調整；Transmin、CAVmin、MSFmin是目標值的最小值，Transmax、CAVmax、MSFmax是最大值。

在任意t，首先基于支配關系可選擇出非支配解集，即Pareto集（歸檔集）；然后采用擁擠距離計算非支配解到全局最優(yōu)之間的距離；最后從Pareto集中選出擁擠距離最小且適應度值最小的粒子更新全局最優(yōu)，使得群體不斷向最優(yōu)解逼近。

3.4 算法過程描述

APSO-CDSM算法的服務容器部署流程如圖1所示。

APSO-CDSM算法的尋優(yōu)步驟如下：

a）初始化。該算法生成粒子群Pops={pi|1≤i≤P}，包括初始位置X、速度V以及初始化參數(shù)σ、ρ。

b）迭代過程。

（a）評估每個個體pi的適應度函數(shù)值，基于擁擠距離選擇歸檔集Arc。

（b）從Arc中選擇最優(yōu)個體Gb*。

（c）個體速度Vi和位置Xi的更新。

（d）為微服務MSk尋找合適的服務器節(jié)點，若資源剩余量滿足資源請求量，則分配對應的容器coni到服務器節(jié)點pmj；否則，尋找下一節(jié)點。循環(huán)執(zhí)行Cinsk次，直到所有容器被部署。繼續(xù)迭代步驟（a）。

c）迭代結束。當所有微服務容器部署到合適的服務器節(jié)點，則完成一次迭代。

d）若達到最大迭代次數(shù)，則結束算法。

算法1 APSO-CDSM算法偽代碼

輸入：P，nID，σ，ρ，Iters;MSs={MSk|1≤k≤I};MS_Rs={（MSk，MSk′，Rs）|MSk，MSk′∈MSs，Rs∈MR};PMs={pmj|1≤j≤M}。

輸出：Ms_PMs={（Msk，PMj）|PMjPMs}。 /*為每個微服務找到合適的服務器節(jié)點集*/

t←1；

Pops←iniPops（P）;

fitness←Galfit（Pops）;

Arc←Deter min e（Pops）;

while（t≤Iters）do

Gb←ChooseGb（Arc，fitness）;

for each pi do

for MSk do

While l≤Cinsk do

While（true）do

for n≤nID do

update vcn by 式（21）;

update xcn by 式（22）;

end for

if（ReqsCPUk≤ReCPUj∧ReqsStorek≤ReStorej）

update MS_PMs by （k，j）;

break;

end if

end while

end while

end for

end for

fit←Calfit（Pops）;

Arc←Deter min e（Pops）;

end while

return Ms_PMs

4 實驗結果分析與對比

為了評估APSO-CDSM算法的性能及有效性，解決2.3節(jié)中所提出的在式（12）～（16）約束下的多目標優(yōu)化問題模型，在優(yōu)化對應的三個性能指標中體現(xiàn)出全局搜索和局部搜索的提升能力，本文實驗采用阿里云提供的跟蹤V2018［19］數(shù)據(jù)集。

4.1 實驗數(shù)據(jù)及參數(shù)設置

在實驗中，基于跟蹤V2018數(shù)據(jù)集的分析，考慮了一個應用程序，存在三個SFC（SFC1，SFC2，SFC3），包含18個微服務，每個服務的基本信息以及服務間的調用關系信息如表2和圖2所示。在表2中，SFC、ReqsCPUk、ReqsStorek分別表示微服務所在的SFC、所需的計算和存儲資源；Msreqk、ReqThrk、Cinsk分別表示請求微服務的次數(shù)、閾值以及容器實例數(shù)；IMSk、IMOk分別表示容器鏡像大小及傳輸開銷。

圖2為微服務間的調用DAG，圖中的三元組表示的權值分別是：weight表示SFC中微服務間邊的權值，weight表達了邊的不同調用關系，邊權值越大，說明兩個微服務間的數(shù)據(jù)交互越緊密；Msreqkk′、TDkk′分別表示服務間的請求次數(shù)和數(shù)據(jù)傳輸量。此外，（0，MSk）表示客戶端啟動服務MSk。

異構CDC中的集群參數(shù)設置如表3所示。

表3中，Djj′=1.0、4.0和8.0分別表示同一節(jié)點、同一CDC以及不同的CDC。表4是APSO-CDSM算法的參數(shù)設置。

實驗環(huán)境：處理器為AMD A6-6310 APU with AMD Radeon R4 Graphics 1.80 GHz， 內存為8 GB RAM。

為了驗證APSO-CDSM算法的性能和有效性，本文將其與GA-NSGAⅡ［12，20，21］、ACO-MCMSA［22］和MSG-NSGAⅢ［13，23］算法進行對比。在實驗中，采用MATLAB工具構建了測試代碼，并分別對兩種集群規(guī)模（M=［120，240］）施加六種請求數(shù)ureqs={×1.0，×2.0，×3.0，×4.0，×5.0，×6.0}。為獲得準確有效的實驗數(shù)據(jù)，每種設置下各完成20次實驗，最后對實驗結果進行統(tǒng)計分析與比較。

4.2 結果分析與對比

采用阿里云提供的V2018數(shù)據(jù)集，通過兩個模擬實驗來驗證APSO-CDSM算法的性能，并與現(xiàn)有的GA-NSGAⅡ、ACO-MCMSA和MSGA-NSGAⅢ算法進行性能比較。在實驗中，實驗1和實驗2的集群規(guī)模分別設定為M=128/256，考察的性能參數(shù)有微服務容器聚集值、服務間的數(shù)據(jù)傳輸開銷、故障率以及集群的資源利用率等。

4.2.1 微服務容器聚集度CAV

四個算法的微服務容器聚集值對比情況如圖3～5所示。通過其值范圍來考察容器聚集對服務間的數(shù)據(jù)開銷和集群資源利用率的影響。

圖3是針對實驗1（M=128）中獲得的容器聚集值的平均結果統(tǒng)計數(shù)據(jù)對比折線圖，以及在對應六種請求數(shù)情況下APSO-CDSM算法對比其他三個算法的提升百分比分布情況盒圖。由圖3可知，APSO-CDSM算法獲得的容器聚集值對應的折線是最底下的折線，是對比算法中最好的，同時其提升都大于13.4%，而且在第一種請求數(shù)情況下表現(xiàn)得最穩(wěn)定，其提升分布大于55%，最大提升相對于MSGA-NSGAⅢ達到76%以上。針對實驗1，APSO-CDSM算法整體提升平均達到42.2%。

同樣，針對實驗2的配置（M=256），驗證APSO-CDSM算法對比其他算法獲得的容器聚集值的數(shù)據(jù)情況的統(tǒng)計如圖4所示。由圖4可以看到，APSO-CDSM算法對比其他三種算法，在容器聚集的平均值上提升的百分比最少為28.4%，最大達到了82.4%，總體平均提升56.9%。

綜合針對集群規(guī)模分別為M=128和M=256的兩個實驗，各個算法獲得的容器聚集度的分布如表5所示。

對應的兩個實驗獲得的結果箱圖及對應的平均取值折線圖如圖5所示。由圖5可知，兩個不同集群規(guī)模實驗結果中，APSO-CDSM算法獲得的數(shù)據(jù)要比其他三個算法更好，特別是集群規(guī)模變大時（M=256時），其獲得容器聚集值較對比算法更好更穩(wěn)定。這點由各次實驗統(tǒng)計的容器聚集值的平均值取值區(qū)域在0.021 8～0.030 8，均小于其余算法的平均值可知。APSO-CDSM算法的整體效果也是最好的。

4.2.2 服務間的數(shù)據(jù)傳輸消耗Trans

服務間的數(shù)據(jù)傳輸開銷是指多個容器對的數(shù)據(jù)傳輸開銷的平均值。在上述兩個實驗中，統(tǒng)計兩個實驗采用不同算法得到的各個服務間數(shù)據(jù)傳輸消耗的平均值結果如圖6～8所示。

圖6、7分別是集群規(guī)模M=128和M=256環(huán)境下，APSO-CDSM算法產(chǎn)生的服務間數(shù)據(jù)傳輸時耗的平均值對比其他算法，在不同請求數(shù)下提升百分比統(tǒng)計結果箱圖。圖中的折線是不同請求數(shù)下各算法獲得的服務間數(shù)據(jù)傳輸開銷的平均值。

綜合兩個集群規(guī)模各個算法在所有實驗中得到的服務間數(shù)據(jù)傳輸開銷的平均值，其統(tǒng)計結果如圖8所示。

圖8 服務間數(shù)據(jù)傳輸開銷平均值統(tǒng)計箱圖及平均值折線圖

Fig.8 Box plot and mean line graph for average inter-service datatransmission overhead statistics

由圖8兩個子圖對應的箱圖結果可知，APSO-CDSM算法產(chǎn)生的服務間數(shù)據(jù)傳輸開銷的平均值分布明顯處于其他三個算法得到的數(shù)據(jù)分布的左邊，說明其效果是對比算法中最優(yōu)的。

4.2.3 故障率MSF

在不同環(huán)境下還需統(tǒng)計出用不同算法對資源進行調度觸及服務執(zhí)行發(fā)生的故障平均率，以反映不同算法在資源調度中的有效性。服務執(zhí)行發(fā)生故障會影響調度的整體性能，包括資源利用率、服務響應時間等。統(tǒng)計兩種集群狀態(tài)下不同算法獲得的服務執(zhí)行發(fā)生故障率的平均值，按故障率平均值的大小生成相應的熱力圖，同時將APSO-CDSM算法得到的故障率對比其他三種算法，計算其效果提升情況的百分數(shù)分布的箱圖，最后得到四個子圖的數(shù)據(jù)可視化圖，如圖9所示。熱力圖顏色越淺表示對應算法下的故障率均值越小，APSO-CDSM算法對應行所有格子的填充色是所在列中最淺的，同時由其提升百分數(shù)分布箱子可看到：在M=128情況下至少提升3%左右，最大達到 28%；M=256時，效果提升穩(wěn)定在10%～20%。其故障率也在四種算法中獲得了最好的效果。

4.2.4 集群資源利用率AR

好的調度策略和算法能充分利用集群中各類核心資源，讓資源的利用率得到更大提升。實驗統(tǒng)計了不同集群參數(shù)和不同的請求數(shù)需求下服務器中CPU和RAM兩類核心資源的利用率。圖10、11分別展示了在M=128和M=256集群規(guī)模下不同算法的CPU和RAM利用率的熱力圖。

核心資源利用是衡量調度算法的優(yōu)劣指標之一，集群內資源利用率越高，表示算法能充分利用資源，更好地提升集群的性能。圖10、11中顏色越深表示對應資源的利用率越高，觀察四個子圖，其中APSO-CDSM算法對應行的所有格子的填充色相對于同列其他算法都呈現(xiàn)出更深的顏色，表示APSO-CDSM算法對資源的利用率更高，也說明了該算法的優(yōu)越性。統(tǒng)計所有實驗中各算法在CPU和RAM上的利用率，如表6所示。

匯總所有實驗中各個算法獲得集群資源（CPU和RAM）的平均利用率得到表6的數(shù)據(jù)可知，相比其他三個算法，應用APSO-CDSM算法的微服務調度能更充分地利用集群資源，其CPU和RAM的利用率是四種算法中最高的。

通過對比四種算法的微服務調度，APSO-CDSM算法在容器聚集度CAV、數(shù)據(jù)傳輸消耗Trans、故障率MSF和集群資源利用率AR四個維度上都獲得了最優(yōu)的效果，能作為基于容器的微服務部署和資源管理管理系統(tǒng)的決策引擎，為CDC提供相應部署調度服務。

5 結束語

為解決云數(shù)據(jù)中心（CDC）中基于容器的微服務部署和資源管理，實現(xiàn)資源有效調度的優(yōu)化問題，提出一種改進的加速粒子群優(yōu)化算法，用于解決CDC集群中微服務容器部署的多目標優(yōu)化問題。該算法通過考慮微服務之間的調用關系，使得容器聚集在一起，從而降低服務的數(shù)據(jù)傳輸成本和故障率，并提高集群資源利用率。通過實驗，與當前提出的基于容器微服務的部署算法相比，實驗結果證明了本文提出的APSO-CDSM算法的有效性和優(yōu)越性。在四個重要性能指標：容器聚集度CAV，數(shù)據(jù)傳輸消耗Trans、故障率MSF和集群資源利用率AR都具有明顯的改善和提高，其中，容器聚集度CAV的提升達到40%以上，數(shù)據(jù)傳輸消耗Trans的提升平均有4%以上，故障率MSF也減少了10%～20%，利用率提升了3%左右。實驗結果表明，APSO-CDSM優(yōu)化算法能提升和改善集群容器部署的能力，為CDC在容器部署過程中提供決策支持。在今后的研究中，將進一步研究擴展粒子群加速優(yōu)化算法在CDC和云邊端資源調度的應用，為降低能耗和服務部署成本提供更有效的解決方案。

參考文獻：

［1］Hwang J， Nkenyereye L， Sung N， et al. IoT service slicing and task offloading for edge computing［J］. IEEE Internet of Things Journal， 2021，8（14）： 11526-11547.

［2］Pham V N， Hossain M D， Lee G W， et al. Efficient data delivery scheme for large-scale microservices in distributed cloud environment［J］. Applied Sciences， 2023，13（2）： 886.

［3］Liu Zheng， Yu Huiqun， Fan Guisheng， et al. Reliability modelling and optimization for microservice-based cloud application using multi-agent system［J］. IET Communications， 2022，16（10）： 1182-1199.

［4］Assun?ao W K G， Krüger J， Mosser S， et al. How do microservices evolve？An empirical analysis of changes in open-source microservice repositories［J］. Journal of Systems and Software， 2023，204：111788.

［5］Wang Xinkai， Li Chao， Zhang Lu， et al. Exploring efficient microservice level parallelism［C］//Proc of IEEE International Parallel and Distributed Processing Symposium. Piscataway，NJ：IEEE Press， 2022： 223-233.

［6］Ahmad I， AlFailakawi M G， AlMutawa A， et al. Container scheduling techniques： a survey and assessment［J］. Journal of King Saud University-Computer and Information Sciences， 2022，34（7）： 3934-3947.

［7］Valsamas P， Skaperas S， Mamatas L， et al. Virtualization technology blending for resource-efficient edge clouds［J］. Computer Networks， 2023，225：109646.

［8］Mostafavi S， Hakami V， Sanaei M. Quality of service provisioning in network function virtualization： a survey［J］. Computing， 2021，103： 917-991.

［9］Liu Dongqing， Hafid A， Khoukhi L. Workload balancing in mobile edge computing for Internet of Things： a population game approach［J］. IEEE Trans on Network Science and Engineering， 2022，9（3）： 1726-1739.

［10］Gao Yifan， Yang Bo， Wang Shilong， et al. Bi-objective service composition and optimal selection for cloud manufacturing with QoS and robustness criteria［J］. Applied Soft Computing， 2022，128： 109530.

［11］Zhao Haitong， Zhang Changsheng. An ant colony optimization algorithm with evolutionary experience-guided pheromone updating strategies for multi-objective optimization［J］. Expert Systems with Applications， 2022，201： 117151.

［12］Mousa M H， Hussein M K. Efficient UAV-based mobile edge computing using differential evolution and ant colony optimization［J］. PeerJ Computer Science， 2022， 8： e870.

［13］Ma Wubin， Wang Rui， Gu Yuanlin， et al. Multi-objective microservice deployment optimization via a knowledge-driven evolutionary algorithm［J］. Complex & Intelligent Systems， 2021，7： 1153-1171.

［14］Pradhan A， Bisoy S K， Das A. A survey on PSO based meta-heuristic scheduling mechanism in cloud computing environment［J］. Journal of King Saud University-Computer and Information Sciences， 2022，34（8）： 4888-4901.

［15］Nouri N A， Aliouat Z， Naouri A， et al. Accelerated PSO algorithm applied to clients coverage and routers connectivity in wireless mesh networks［J］. Journal of Ambient Intelligence and Humanized Computing， 2023，14（1）： 207-221.

［16］Alsaidy S A， Abbood A D， Sahib M A. Heuristic initialization of PSO task scheduling algorithm in cloud computing［J］. Journal of King Saud University-Computer and Information Sciences， 2022，34（6）： 2370-2382.

［17］Dubey K， Sharma S C. A novel multi-objective CR-PSO task scheduling algorithm with deadline constraint in cloud computing［J］. Sustainable Computing： Informatics and Systems， 2021，32： 100605.

［18］Filip I D， Pop F， Serbanescu C， et al. Microservices scheduling model over heterogeneous cloud-edge environments as support for IoT applications［J］. IEEE Internet of Things Journal， 2018，5（4）： 2672-2681.

［19］Zhu Jianyong， Lu Bin， Yu Xiaoqiang， et al. An approach to workload generation for cloud benchmarking： a view from Alibaba trace［C］//Proc of the 15th IEEE International Symposium on Autonomous Decentralized System. Piscataway，NJ：IEEE Press， 2023： 1-8.

［20］Guerrero C， Lera I， Juiz C. Genetic algorithm for multi-objective optimization of container allocation in cloud architecture［J］. Journal of Grid Computing， 2018，16： 113-135.

［21］吳祥， 董輝， 俞立，等. 多色服裝裁剪分床計劃復合優(yōu)化算法［J］. 控制與決策， 2022，37（6）： 1531-1540. （Wu Xiang， Dong Hui， Yu Li， et al. Hybrid optimization algorithm for cut order planning of multicolor garment［J］. Control and Decision， 2022，37（6）： 1531-1540.）

［22］Lin Miao， Xi Jianqing， Bai Weihua， et al. Ant colony algorithm for multi-objective optimization of container-based microservice scheduling in cloud［J］. IEEE Access， 2019，7： 83088-83100.

［23］張珊莉， 謝加良， 陳水利. 基于模糊系統(tǒng)的改進型NSGA-Ⅲ算法［J］. 模糊系統(tǒng)與數(shù)學， 2023，37（2）： 13-24. （Zhang Shanli， Xie Jialiang， Chen Shuili. Improved NSGA-Ⅲ algorithm based on fuzzy system［J］. Fuzzy Systems and Mathematics， 2023，37（2）：13-24.）