智慧城市中協(xié)同服務(wù)部署與任務(wù)調(diào)度的自適應(yīng)機(jī)制

摘 要：邊緣計(jì)算通過(guò)利用邊緣側(cè)的計(jì)算、存儲(chǔ)和網(wǎng)絡(luò)資源為用戶提供低時(shí)延、高響應(yīng)性的服務(wù)，但在智慧城市邊緣系統(tǒng)中仍面臨著資源有限、服務(wù)請(qǐng)求多樣性和邊緣服務(wù)器過(guò)載等挑戰(zhàn)。對(duì)此，研究了資源受限下聯(lián)合服務(wù)部署與任務(wù)調(diào)度問(wèn)題，提出了一種基于層次化時(shí)間框架的自適應(yīng)協(xié)同服務(wù)部署及任務(wù)調(diào)度方案。優(yōu)化問(wèn)題的目標(biāo)是在充分考慮任務(wù)優(yōu)先級(jí)的情況下，優(yōu)化系統(tǒng)時(shí)延和負(fù)載均衡。首先建立了系統(tǒng)時(shí)延和負(fù)載均衡的系統(tǒng)開(kāi)銷模型，并引入服務(wù)水平協(xié)議（service level agreement，SLA）提高靈活性。其次通過(guò)考慮服務(wù)優(yōu)先級(jí)與訪問(wèn)頻率構(gòu)建啟發(fā)式服務(wù)部署算法，再進(jìn)一步提出一種改進(jìn)的二元平衡優(yōu)化器（binary equilibrium optimizer，BiEO）的任務(wù)調(diào)度算法來(lái)優(yōu)化系統(tǒng)開(kāi)銷。最后，利用上海電信數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。結(jié)果表明該方法與其他方法相比，在平均加權(quán)時(shí)延（average weighted response time，AWRT）方面能降低12.35%以上，在負(fù)載均衡方面能優(yōu)化14.47%以上，實(shí)現(xiàn)了更低時(shí)延的同時(shí)，保證了邊緣服務(wù)器負(fù)載的均衡。

關(guān)鍵詞：智慧城市；多接入邊緣計(jì)算；服務(wù)部署；任務(wù)調(diào)度；平衡優(yōu)化器

中圖分類號(hào)：TP393"" 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）12-039-3814-08

doi： 10.19734/j.issn.1001-3695.2024.05.0143

Adaptive mechanism for collaborative service deployment and task scheduling in smart cities

Chen Tingtinga， b， Wang Suhonga， b， Tang Yubenb， c， Cai Zhenga， b， Qin Tuanfaa， b

（a. School of Computer amp; Electronic Information， b. Key Laboratory of Multimedia Communications amp; Network Technology， c. School of Electrical Engineering， Guangxi University， Nanning 530004， China）

Abstract：Edge computing leverages computing， storage， and networking resources at the edge to provide users with low latency and high responsiveness services. However， in smart city edge systems， challenges such as limited resources， diverse service requests， and edge server overload persist. To address these challenges， this paper investigated the problem of joint service deployment and task scheduling under resource constraints and proposed an adaptive collaborative service deployment and task scheduling scheme based on a hierarchical time frame. The method aimed to optimize system latency and load balancing while considering task priority. Firstly， this paper established a system cost model involving system latency and load ba-lancing and introduced SLAs to enhance flexibility. Secondly， by considering service priority and access frequency， it deve-loped a heuristic service deployment algorithm and proposed an improved BiEO task scheduling algorithm to optimize system costs. Finally， this paper conducted simulation experiments using the Shanghai telecom dataset. The results show that the proposed method reduces the AWRT by more than 12.35% and improves load balancing by more than 14.47% compared with other methods. This approach achieves lower latency while ensuring a balanced load on edge servers.

Key words：smart cities; multi-access edge computing（MEC）; service deployment; task scheduling; equilibrium optimizer

0 引言

隨著以5G為代表的移動(dòng)通信技術(shù)的快速發(fā)展，移動(dòng)網(wǎng)絡(luò)服務(wù)涌現(xiàn)出大量新的業(yè)務(wù)場(chǎng)景，如自動(dòng)駕駛、虛擬現(xiàn)實(shí)、增強(qiáng)現(xiàn)實(shí)（augmented reality， AR）、數(shù)字孿生及元宇宙等。由于具有計(jì)算密集和時(shí)延敏感度高的特性，這些新興服務(wù)的出現(xiàn)對(duì)未來(lái)網(wǎng)絡(luò)的質(zhì)量和性能提出了更高的要求，而傳統(tǒng)云計(jì)算處理模式的帶寬有限、時(shí)延高、能耗高，難以滿足用戶的高性能需求[1]。作為應(yīng)對(duì)此挑戰(zhàn)的創(chuàng)新方案，多接入邊緣計(jì)算（multi-access edge computing， MEC）[2]通過(guò)將計(jì)算和存儲(chǔ)資源從網(wǎng)絡(luò)的中心下沉部署到靠近終端設(shè)備的網(wǎng)絡(luò)邊緣側(cè)，并且將相應(yīng)應(yīng)用的服務(wù)部署在邊緣服務(wù)器上以滿足移動(dòng)設(shè)備的服務(wù)請(qǐng)求，實(shí)現(xiàn)了資源對(duì)需求的就近部署，有效降低了網(wǎng)絡(luò)傳輸帶來(lái)的通信時(shí)延。

在綜合性智慧城市的MEC環(huán)境中，各種類型的移動(dòng)設(shè)備和傳感器可以隨時(shí)隨地提出任務(wù)卸載請(qǐng)求。然而特定任務(wù)只能由對(duì)應(yīng)的服務(wù)處理，服務(wù)的部署會(huì)占用邊緣服務(wù)器的資源。由于資源有限，需要優(yōu)化服務(wù)布局，將最合適的服務(wù)放置在每個(gè)邊緣服務(wù)器上。在服務(wù)已經(jīng)部署的情況下，考慮到任務(wù)的時(shí)延敏感性以及不同任務(wù)的類型、優(yōu)先級(jí)、數(shù)據(jù)量等特征具有的差異性，例如通用用戶服務(wù)、AR和緊急救護(hù)車應(yīng)用中，緊急救護(hù)車應(yīng)用的優(yōu)先級(jí)應(yīng)該具有最高的優(yōu)先級(jí)，AR所需的數(shù)據(jù)量最高，需要進(jìn)一步對(duì)卸載的任務(wù)進(jìn)行實(shí)時(shí)調(diào)度并分配合理的資源。同時(shí)智慧城市中大量的任務(wù)請(qǐng)求和多樣的服務(wù)種類等因素也使這個(gè)問(wèn)題變得足夠復(fù)雜。因此如何合理地通過(guò)對(duì)服務(wù)器進(jìn)行細(xì)粒度的服務(wù)部署和任務(wù)調(diào)度，是目前面臨的主要挑戰(zhàn)之一。

為了實(shí)現(xiàn)算力的細(xì)粒度高效調(diào)度，當(dāng)前輕量級(jí)的虛擬化解決方案（如Docker容器技術(shù)[3]）正在不斷發(fā)展，這些解決方案允許在不同的環(huán)境中快速靈活地部署服務(wù)和分配資源。近年來(lái)，一些研究已經(jīng)從提高服務(wù)質(zhì)量（quality of service， QoS）或降低成本的角度出發(fā)，探討了邊緣服務(wù)部署和任務(wù)調(diào)度問(wèn)題。針對(duì)傳統(tǒng)的中心化架構(gòu)易受到單點(diǎn)故障的影響及調(diào)度效率低等問(wèn)題，彭青藍(lán)等人[4]提出了一種去中心化的在線任務(wù)調(diào)度方法，采用任務(wù)卸載的平均優(yōu)先級(jí)加權(quán)響應(yīng)時(shí)間作為調(diào)度策略的優(yōu)化目標(biāo)。Tan等人[5]研究了邊緣云系統(tǒng)中任務(wù)分派和調(diào)度問(wèn)題的在線算法，目標(biāo)是最大程度地減少總作業(yè)響應(yīng)時(shí)間。Alqahtani等人[6]在霧計(jì)算的請(qǐng)求調(diào)度中考慮了負(fù)載均衡。Meng 等人[7]考慮了每一項(xiàng)任務(wù)完成的截止時(shí)間，并提出了在帶寬和資源受限條件下的Dedas算法，盡可能按時(shí)完成更多任務(wù)。針對(duì)不同區(qū)域的任務(wù)卸載問(wèn)題，孔珊等人[8]利用任務(wù)的相似性，提出一種進(jìn)化多任務(wù)多目標(biāo)優(yōu)化算法進(jìn)行求解。然而以上的研究均假設(shè)邊緣側(cè)部署的服務(wù)是固定的，或者假設(shè)邊緣側(cè)可以執(zhí)行任何計(jì)算任務(wù)，但由于MEC環(huán)境中存在用戶的變化性，這些想法運(yùn)用在實(shí)際場(chǎng)景中有些理想化，所以必須更加重視邊緣端的服務(wù)部署，以便根據(jù)需求動(dòng)態(tài)調(diào)整和優(yōu)化服務(wù)的響應(yīng)能力。

在服務(wù)部署的研究上，Aral等人[9]提出了一種分布式數(shù)據(jù)傳播方法，根據(jù)用戶需求的大小和位置作出決策，以盡量減少延遲。Gu等人[10]通過(guò)結(jié)合服務(wù)器內(nèi)和服務(wù)器間層共享協(xié)同部署微服務(wù)，并對(duì)此提出了基于隨機(jī)舍入的啟發(fā)式算法。在用戶移動(dòng)性高（例如自動(dòng)駕駛汽車）的場(chǎng)景中，可能會(huì)導(dǎo)致其附近邊緣云的頻繁切換，進(jìn)而增加時(shí)延及成本。對(duì)此，Wang 等人[11]研究了邊緣云之間的微服務(wù)協(xié)調(diào)問(wèn)題，并提出了基于動(dòng)態(tài)規(guī)劃的離線微服務(wù)協(xié)調(diào)算法和基于強(qiáng)化學(xué)習(xí)的在線微服務(wù)協(xié)調(diào)算法。除此之外，在智慧城市等應(yīng)用場(chǎng)景中，服務(wù)具有不同的資源需求和關(guān)鍵性，對(duì)此Cabrera等人[12]使用搶占式排隊(duì)模型將關(guān)鍵應(yīng)用放在首位，進(jìn)而提出了一種移動(dòng)感知、優(yōu)先級(jí)驅(qū)動(dòng)的服務(wù)部署模型。Huang 等人[13]從分層MEC網(wǎng)絡(luò)出發(fā)，以降低成本為目標(biāo)考慮服務(wù)部署問(wèn)題，并提出基于Gibbs采樣的迭代服務(wù)部署算法，但是它將服務(wù)部署問(wèn)題和任務(wù)調(diào)度問(wèn)題解耦了，缺乏對(duì)兩者之間相互作用的考慮，可能導(dǎo)致非最優(yōu)的決策。

針對(duì)服務(wù)部署和請(qǐng)求調(diào)度兩個(gè)問(wèn)題的聯(lián)合優(yōu)化，He等人[14]首次提出了一種基于線性程序松弛和舍入的啟發(fā)式方法，旨在利用邊緣云有限的資源盡可能為更多的用戶請(qǐng)求提供服務(wù)。在支持MEC的密集蜂窩網(wǎng)絡(luò)場(chǎng)景下，Xu等人[15]提出了一種高效的在線算法OREO，聯(lián)合優(yōu)化了動(dòng)態(tài)服務(wù)緩存和任務(wù)卸載。Poularakis等人[16]針對(duì)BS存儲(chǔ)、計(jì)算和通信資源等約束，提出服務(wù)部署和請(qǐng)求路由的聯(lián)合優(yōu)化的雙準(zhǔn)則近似算法。針對(duì)能夠細(xì)粒度調(diào)度算力的新場(chǎng)景，Xu等人[17]同時(shí)考慮任務(wù)調(diào)度和算力調(diào)度，提出一種動(dòng)態(tài)協(xié)作算力和任務(wù)調(diào)度的自適應(yīng)機(jī)制。Liu等人[18]專注于請(qǐng)求調(diào)度并協(xié)助服務(wù)部署，在平衡服務(wù)器負(fù)載的同時(shí)最大限度地減少平均響應(yīng)時(shí)間。此外，韓超臣等人[19]以優(yōu)化時(shí)延和能耗為目標(biāo)，提出了聯(lián)合服務(wù)更新和云邊端協(xié)作的任務(wù)卸載方法。然而，在智慧城市MEC場(chǎng)景下，多種任務(wù)的優(yōu)先級(jí)特性沒(méi)有被考慮在內(nèi)。

綜上所述，盡管在邊緣服務(wù)部署和任務(wù)調(diào)度方面取得了進(jìn)展，但當(dāng)前的工作忽略了智慧城市新興業(yè)務(wù)場(chǎng)景的特性，因此智慧城市邊緣系統(tǒng)仍面臨一些挑戰(zhàn)：a）資源密集型任務(wù)請(qǐng)求的服務(wù)需要專用計(jì)算資源和大量服務(wù)器上的數(shù)據(jù)，需根據(jù)需求動(dòng)態(tài)調(diào)整; b）邊緣服務(wù)器數(shù)量有限且分布不均勻，可能導(dǎo)致性能下降; c）不同服務(wù)具有不同的資源需求和重要性，必須考慮這些異構(gòu)性才能及時(shí)作出響應(yīng)。因此本文從邊緣提供商的角度研究了智慧城市中聯(lián)合服務(wù)部署和任務(wù)調(diào)度問(wèn)題，提出了一種基于層次化時(shí)間框架的自適應(yīng)協(xié)同服務(wù)部署及任務(wù)調(diào)度方案。其主要貢獻(xiàn)如下：

a）將該問(wèn)題闡述為優(yōu)化系統(tǒng)時(shí)延和工作負(fù)載均衡的多目標(biāo)優(yōu)化問(wèn)題，考慮到不同任務(wù)類型引入的任務(wù)優(yōu)先級(jí)差異，模型中引入分段SLA以提高靈活性，并考慮服務(wù)器實(shí)時(shí)資源狀態(tài)以提高資源利用率。

b）提出了一種基于改進(jìn)BiEO的聯(lián)合任務(wù)調(diào)度算法HA_BiEO，通過(guò)考慮邊緣服務(wù)器資源狀態(tài)和任務(wù)優(yōu)先級(jí)，在存儲(chǔ)、計(jì)算和通信資源約束下選擇當(dāng)前狀態(tài)下最佳服務(wù)部署和任務(wù)調(diào)度決策，以滿足多種任務(wù)的時(shí)延要求，同時(shí)優(yōu)化系統(tǒng)負(fù)載均衡。

c）基于真實(shí)數(shù)據(jù)集的算法對(duì)比證明，所提算法能夠有效地減少邊緣服務(wù)器的系統(tǒng)時(shí)延和任務(wù)處理超時(shí)比例，均衡邊緣服務(wù)器負(fù)載。

1 系統(tǒng)模型和問(wèn)題定義

1.1 系統(tǒng)模型

智慧城市MEC應(yīng)用場(chǎng)景中，主要的邊緣網(wǎng)絡(luò)如圖1所示，網(wǎng)絡(luò)架構(gòu)一共有云數(shù)據(jù)中心層、邊緣層和用戶設(shè)備層三層。邊緣層由一組邊緣服務(wù)器組成，表示為E={1，2，…，j，…，n}，它們之間的網(wǎng)絡(luò)拓?fù)淇梢钥闯梢粋€(gè)無(wú)向圖G=（E，L），其中L={ b（jj′） | j， j′∈[1，n]， j≠j′}，b（jj′）≠0表示邊緣服務(wù)器j和j′之間存在直接通信鏈路且?guī)挒閎（jj′）。每個(gè)邊緣服務(wù)器都配備了計(jì)算資源Fj和存儲(chǔ)資源Aj，系統(tǒng)提供了多種用戶需求和應(yīng)用，例如通用用戶服務(wù)、監(jiān)控系統(tǒng)的人臉識(shí)別、電網(wǎng)傳感器監(jiān)測(cè)、增強(qiáng)現(xiàn)實(shí)體驗(yàn)和緊急救護(hù)車應(yīng)用等，服務(wù)集表示為S={1，2，…，i，…，k}，在邊緣服務(wù)器上部署服務(wù)i時(shí)，會(huì)占用一定的內(nèi)存和存儲(chǔ)資源，服務(wù)i的副本存儲(chǔ)大小為ci。為了更貼合真實(shí)情況，該系統(tǒng)以隨機(jī)方式接受用戶的任務(wù)處理請(qǐng)求，其中任務(wù)屬性{ri， dr， fr， ωr}包括請(qǐng)求的服務(wù)i、任務(wù)傳輸時(shí)的數(shù)據(jù)大小dr、任務(wù)的計(jì)算量fr和優(yōu)先級(jí)ωr。如圖1所示，通過(guò)邊緣服務(wù)器之間的協(xié)作，用戶的請(qǐng)求可以被調(diào)度到邊緣服務(wù)器上處理，前提是該邊緣服務(wù)器上已經(jīng)部署了相應(yīng)的服務(wù)，并且該時(shí)刻邊緣服務(wù)器有足夠的計(jì)算和存儲(chǔ)資源。因此需要決定將服務(wù)放置在哪些邊緣服務(wù)器中，以及如何將用戶請(qǐng)求調(diào)度到最合適的邊緣服務(wù)器上處理。為了對(duì)這些決策進(jìn)行建模，引入了兩組優(yōu)化變量：xij={0，1}和yjr={0，1}，分別表示服務(wù)i是否在邊緣服務(wù)器j上部署和任務(wù)r是否在邊緣服務(wù)器j上部署。文中符號(hào)變量及定義如表1所示。

1.2 服務(wù)部署模型

用xij=1表示服務(wù)i在邊緣服務(wù)器上部署，由于每個(gè)服務(wù)應(yīng)該至少部署一次：

∑j∈Exij≥1，i∈S（1）

要在網(wǎng)絡(luò)邊緣處理某種類型的任務(wù)，邊緣服務(wù)器應(yīng)預(yù)置一定的存儲(chǔ)容量來(lái)緩存相應(yīng)的服務(wù)，服務(wù)器存儲(chǔ)資源受限制：

∑i∈Sxijci≤Aj（2）

任務(wù)r由服務(wù)器j處理的條件是j必須部署了與任務(wù)r對(duì)應(yīng)的服務(wù)i，用Poolr（j）表示可以供任務(wù)r卸載的邊緣服務(wù)器構(gòu)成的資源池：

Poolr（i）={j|xij=1，j∈E}（3）

1.3 任務(wù)處理模型

對(duì)于一個(gè)任務(wù)r，任務(wù)數(shù)據(jù)從用戶設(shè)備至邊緣服務(wù)器j的上行傳輸時(shí)間為

Tupr=drβlog2［1+ρrτrj/λ2］（4）

由調(diào)度造成的任務(wù)數(shù)據(jù)在邊緣服務(wù)器j和j′之間的傳輸時(shí)間為

Tdispr=∑（j，j′）∈Ordr+d′rbjj′（5）

最終計(jì)算結(jié)果由邊緣服務(wù)器j返回用戶設(shè)備的下行傳輸時(shí)間為

Tdownr=d′rβlog2［1+ρrτr′j/λ2］（6）

其中：dr和d′ r分別表示傳輸上行和下行數(shù)據(jù)量；β為用戶設(shè)備到基站的信道帶寬；ρr為移動(dòng)設(shè)備的信號(hào)傳輸功率；τrj和τr′j分別表示任務(wù)r的請(qǐng)求設(shè)備首次到達(dá)和經(jīng)由邊緣服務(wù)器之間的信道增益，由τrj=［D（r，j）］－ξ計(jì)算，其中定義ξ=4為用戶設(shè)備與基站之間的路徑損耗因子[20]；λ2為設(shè)備高斯噪聲功率；Or為任務(wù)r的所有調(diào)度記錄；（j，j′）∈Or表示任務(wù)r一次經(jīng)由服務(wù)器j到達(dá)服務(wù)器j′的記錄。

因此總傳輸時(shí)延表示為

Ttranr=Tupr+Tdispr+Tdownr（7）

本文假設(shè)服務(wù)器使用當(dāng)前可以分配的最大頻率來(lái)處理傳入的任務(wù)，表示為Fj×（1-Utj），其中Utj為服務(wù)器在時(shí)隙t中的CPU利用率，使用yjr表示任務(wù)r由服務(wù)器j處理，處理時(shí)延如式（8）所示。

Tcompr=frFj×（1－Utj）×yjr（8）

任務(wù)r被服務(wù)器j處理占用服務(wù)器內(nèi)存mr，服務(wù)器j在時(shí)隙t的內(nèi)存利用率為m tj，為分配給所有任務(wù)的內(nèi)存不能超過(guò)服務(wù)器j的內(nèi)存資源：

∑r∈Rmryjr+mtjMj≤Mj（9）

令Q為任務(wù)r之前的任務(wù)集，排隊(duì)時(shí)延為在此之前任務(wù)的處理時(shí)間，表示為

Tqueuejr=∑r′∈QTcompjr′（10）

任務(wù)處理總時(shí)延為

Ttal=Ttranij+Tcompjr+Tqueuejr（11）

因此系統(tǒng)的加權(quán)平均時(shí)延為

w=∑mr=0ωr·Ttalr∑mr=0ωr（12）

在現(xiàn)有研究[12，18]中，直接使用平均時(shí)延易受到極端取值的影響，導(dǎo)致優(yōu)化結(jié)果偏向于少數(shù)幾個(gè)高時(shí)延任務(wù)。除此之外，當(dāng)一個(gè)系統(tǒng)的時(shí)延已經(jīng)滿足某個(gè)閾值之后，繼續(xù)降低時(shí)延并不一定帶來(lái)服務(wù)質(zhì)量上的提升。本文采用優(yōu)先級(jí)感知的線性懲罰SLA，由式（13）對(duì)時(shí)延進(jìn)行映射，引入?yún)?shù)Tidealr和Tdlr，分別表示理想時(shí)延和最大容忍時(shí)延，當(dāng)任務(wù)處理總時(shí)延小于Tidealr時(shí)，服務(wù)質(zhì)量良好，此時(shí)不會(huì)受到懲罰，但如果任務(wù)處理總時(shí)延大于Tidealr，服務(wù)質(zhì)量會(huì)開(kāi)始下降，因此作為懲罰，Pr會(huì)線性增大，如果超過(guò)Tdlr，則服務(wù)質(zhì)量不可接受，此時(shí)施加最大的懲罰。對(duì)于不同優(yōu)先級(jí)的任務(wù)，系數(shù)Tidealr和Tdlr不同：

Pr=Pm""""" Ttalr≥Tdlrγ×（Ttalr－Tidealr）"" "Tidealr＜Ttalr≤Tdlr 0"""""" Ttalr＜Tidealr（13）

其中：

γ=PmTdlr－Tidealr（14）

通過(guò)Tidealr和Tdlr的靈活性設(shè)置，在構(gòu)建目標(biāo)函數(shù)時(shí)考慮到任務(wù)的各種重要性，有效避免了SLA的潛在違約風(fēng)險(xiǎn)，使得優(yōu)化算法能夠針對(duì)不同的應(yīng)用場(chǎng)景和需求進(jìn)行精準(zhǔn)調(diào)整。因此設(shè)定系統(tǒng)時(shí)延為

Ptal=∑mr=0Prm（15）

在對(duì)邊緣服務(wù)器負(fù)載均衡的衡量上，方差和標(biāo)準(zhǔn)差對(duì)極端值較為敏感，而吉尼系數(shù)相對(duì)更為魯棒，并且無(wú)量綱，通常在0～1，使得邊緣服務(wù)器負(fù)載的不平等情況更容易比較[21]。因此引入吉尼系數(shù)對(duì)邊緣服務(wù)器的負(fù)載均衡程度進(jìn)行評(píng)估，并定義為BL：

BL=1－1n（2∑n－1j=1wlj+1）（16）

其中：wlj是按升序排列的各服務(wù)器的負(fù)載值，將服務(wù)器按照負(fù)載排序，然后計(jì)算洛倫茨曲線下的面積與45 °線下的面積之比，得到一個(gè)吉尼系數(shù)。這個(gè)吉尼系數(shù)可以反映出邊緣服務(wù)器負(fù)載的不平等程度，即是否存在少數(shù)服務(wù)器承擔(dān)了大部分負(fù)載，而大多數(shù)服務(wù)器負(fù)載較輕的情況。

1.4 問(wèn)題描述

本文的優(yōu)化目標(biāo)是在確保任務(wù)優(yōu)先級(jí)得到充分考慮的同時(shí)，優(yōu)化系統(tǒng)時(shí)延和負(fù)載均衡。為了獲得整體優(yōu)化指標(biāo)，采用加性加權(quán)模型將服務(wù)部署聯(lián)合任務(wù)調(diào)度多目標(biāo)問(wèn)題轉(zhuǎn)換為單目標(biāo)優(yōu)化問(wèn)題。將系統(tǒng)開(kāi)銷Sod定義為系統(tǒng)時(shí)延Ptal和負(fù)載均衡BL的加權(quán)和，如下所示。

Sod=η×Ptal+（1－η）×BL（17）

根據(jù)上述內(nèi)容，問(wèn)題可被描述為

min"""""" Sod

s.t.

C1：xij∈{0，1} i∈S，j∈EC2：yjr∈{0，1} r∈R，j∈EC3：∑j∈Exij≥1i∈S，j∈EC4：∑j∈Eyrj=1r∈R，j∈EC5：∑i∈Sxijci≤Aj j∈EC6：∑r∈Rmryjr+mtjMj≤Mji∈S，j∈E（18）

其中：約束C1和C2中的xij和yjr分別表示服務(wù)i是否部署在服務(wù)器j上和任務(wù)r是否由服務(wù)器j處理，其值用二進(jìn)制表示；約束C3確保所有服務(wù)均被部署；約束C4確保任務(wù)i被且僅被一個(gè)服務(wù)器處理；約束C5是服務(wù)器存儲(chǔ)容量限制；約束C6是內(nèi)存限制，確保處理任務(wù)時(shí)邊緣服務(wù)器上有足夠的內(nèi)存空間。

2 HA_IBiEO算法

基于1.4節(jié)的目標(biāo)函數(shù)， 本文提出的HA_IBiEO算法旨在根據(jù)每臺(tái)邊緣服務(wù)器的資源狀態(tài)進(jìn)行服務(wù)部署和任務(wù)調(diào)度，并采用一種層次化時(shí)間框架，將這兩個(gè)決策的時(shí)間尺度分開(kāi)：為了避免發(fā)生系統(tǒng)不穩(wěn)定的情況，服務(wù)部署的決策周期較長(zhǎng)，設(shè)為τ；同時(shí)為了保證服務(wù)質(zhì)量，任務(wù)調(diào)度在每一個(gè)時(shí)隙t都進(jìn)行決策。

2.1 編碼方案

考慮到服務(wù)部署和將任務(wù)調(diào)度到服務(wù)器是多對(duì)一的映射關(guān)系，本文采用一種基于二維矩陣的編碼方案，此方案可以很清楚地展示每一個(gè)服務(wù)與服務(wù)器、任務(wù)與服務(wù)器之間的關(guān)系。

對(duì)于某個(gè)服務(wù)i，定義其部署方案為vi，為1×n矩陣，所以全部服務(wù)的部署策略為k×n矩陣：

V=v1，…，vkT（19）

對(duì)于某個(gè)任務(wù)r，其調(diào)度方案為hr，為1×n矩陣，所以全部任務(wù)的調(diào)度方案為m×n矩陣：

H=h1，…，hmT（20）

對(duì)于調(diào)度方案H，編碼規(guī)則是：a）只有V中與任務(wù)r對(duì)應(yīng)服務(wù)的vk，n為1，且該服務(wù)器滿足約束C6，H中的hr，n才能為1；b）矩陣H的每一行有且僅有一個(gè)1。

2.2 方法概覽

HA_IBiEO算法由四部分組成，如圖2所示。

圖2 HA_IBiEO算法流程

Fig.2 Flowchart of HA_IBiEo algorithm

a）判斷時(shí)隙t所在周期τ，如果都在同一周期τ，則執(zhí)行任務(wù)調(diào)度算法IBiEO；如果進(jìn)入下一周期，則先執(zhí)行服務(wù)部署算法HA，再執(zhí)行任務(wù)調(diào)度算法IBiEO。

b）通過(guò)調(diào)用IBiEO算法獲得每一個(gè)時(shí)隙t內(nèi)的調(diào)度策略Ht，此部分必須根據(jù)HA算法已經(jīng)得到的服務(wù)部署策略Vτ進(jìn)行考慮，并將周期內(nèi)全部調(diào)度記錄存儲(chǔ)在H中。

c）進(jìn)入下一周期便調(diào)用HA服務(wù)部署算法，通過(guò)H記錄的數(shù)據(jù)獲得此周期內(nèi)的Vτ。

d）輸出結(jié)果并進(jìn)入下一時(shí)隙t。

2.3 IBiEO任務(wù)調(diào)度算法

BiEO算法是一種元啟發(fā)式算法，其靈感來(lái)自用于估計(jì)動(dòng)態(tài)和平衡狀態(tài)的控制體積質(zhì)量平衡模型。由于BiEO具有快速的收斂速率、參數(shù)少、簡(jiǎn)單性和多維適用性等優(yōu)點(diǎn)[22]，故本文采用基于BiEO的任務(wù)調(diào)度算法。在BiEO中，每個(gè)粒子都是一個(gè)搜索代理，其位置編碼代表一個(gè)解決方案。搜索代理根據(jù)迄今為止的最佳解決方案（即平衡候選粒子）更新其濃度，最終達(dá)到平衡狀態(tài)，即獲得最優(yōu)解。

平衡狀態(tài)是算法的最終收斂狀態(tài)，但在初始迭代中，系統(tǒng)對(duì)平衡狀態(tài)掌握的信息不足。因此，算法利用平衡候選粒子的信息來(lái)引導(dǎo)其他粒子朝著搜索空間中的最佳點(diǎn)前進(jìn)。如式（21）所示，平衡候選粒子是在每次優(yōu)化迭代期間確定的四個(gè)迄今為止最好的粒子加上一個(gè)位置是這四個(gè)粒子的算術(shù)平均值的粒子。這些粒子形成了一個(gè)稱為平衡池的向量Ceq，pool，每次迭代中的每個(gè)粒子從Ceq，pool中隨機(jī)選擇一個(gè)來(lái)更新其位置。例如，某個(gè)粒子在第一次迭代中選擇根據(jù)Ceq（1）更新位置，在第二次迭代中可能會(huì)根據(jù)Ceq（4）更新位置，直到優(yōu)化過(guò)程結(jié)束。

Ceq，pool=Ceq（1），Ceq（2），Ceq（3），Ceq（4），Ceq（ave）（21）

令每一個(gè)粒子的狀態(tài)編碼為一個(gè)任務(wù)調(diào)度方案，其中i表示第i個(gè)粒子，而k表示該粒子的狀態(tài)編碼中的第k個(gè)任務(wù)，t表示第t次迭代。這里均勻地生成隨機(jī)數(shù)r1和r2，粒子根據(jù)式（22）更新?tīng)顟B(tài)編碼：

Cki（t+1）=（Cki（t））－1r2lt;Pki（ΔC）Cki（t）" ""r2≥Pki（ΔC） r1 lt;0.5" round（r）" r2lt;Pki（ΔC）Cki（t）"" r2≥Pki（ΔC） r1≥0.5" （22）

C中狀態(tài)編碼更新的概率P（ΔC）計(jì)算如式（23）所示，這里使用的是V型的傳遞函數(shù)：

P（ΔC）=arctan（2πΔC）/arctan（2π）（23）

其中：ΔC表示粒子位置變化的向量。

ΔC=（α+C－Ceq）·F+CλV（1－F）（24）

α=GP×（randgt;0.5）（25）

在粒子狀態(tài)編碼更新過(guò)程中，式（24）的向量F有助于算法在探索和開(kāi)發(fā)之間取得合理的平衡，其中a1和a2分別是控制探索和開(kāi)發(fā)能力的常量值：

F=a1sign（r－0.5）e－λt－1（26）

t=（1－IterMax_iter）（a2 IterMax_iter）（27）

同時(shí)，在式（24）后半部分中，G通過(guò)增強(qiáng)開(kāi)發(fā)能力來(lái)提供更精確的解決方案，防止陷入局部最小值中。

G=G0F（28）

其中G0定義如下：

G0=GCP（Geq-λC）（29）

其中：GCP被定義為生成率控制參數(shù)，它包括生成項(xiàng)對(duì)更新過(guò)程的貢獻(xiàn)概率。這種貢獻(xiàn)的概率規(guī)定了有多少粒子使用生成項(xiàng)更新其狀態(tài)，由另一個(gè)生成概率（GP）的項(xiàng)決定。r1和r2是[0，1]中的均勻隨機(jī)數(shù)：

GCP=0.5r1"""" "r2≥GP0"" r2lt;GP（30）

由于V形函數(shù)的性質(zhì)，當(dāng)大部分種群成員都聚集在某局部最優(yōu)解附近，種群整體將陷入該局部最優(yōu)，限制了對(duì)更廣闊解空間的探索[23]。為了更好地控制算法的探索和利用，本文將V型與U型傳遞函數(shù)相結(jié)合，如式（31）所示。

P（ΔC）=2πarctan（（ΔC）2）（31）

在迭代的早期階段，位置能夠在 0 ～ 1 快速切換以搜索更多空間。而在后期階段，位置切換速度較慢，以增加尋找最佳解決方案的能力。

此傳遞函數(shù)的優(yōu)點(diǎn)在于：具有更大的搜索空間，并且可以同時(shí)處理低維和高維問(wèn)題。

算法1 IBiEO算法

輸入：時(shí)隙t的任務(wù)請(qǐng)求集R;基站數(shù)據(jù)集;種群大小N;迭代次數(shù)Imax;當(dāng)前服務(wù)部署方案V。

輸出：最優(yōu)任務(wù)調(diào)度策略Ht;系統(tǒng)開(kāi)銷Sod。

初始化N個(gè)粒子的編碼M

while Iter≤Imax do

檢測(cè)平衡候選粒子并構(gòu)建平衡庫(kù)

實(shí)現(xiàn)內(nèi)存保存（if Iter＞1）

for 每個(gè)粒子 do

從平衡庫(kù)中隨機(jī)選擇一個(gè)候選粒子

根據(jù)式（26）生成隨機(jī)向量λ和r

根據(jù)式（26）（28）構(gòu)造F和G

根據(jù)式（24）（25）計(jì)算△C

由式（23）計(jì)算概率P（△C）

根據(jù)式（22）更新粒子位置C

檢查每一個(gè)粒子的狀態(tài)矩陣是否符合條件，若不符合則進(jìn)行刪除和回填操作

end （for）

end （while）

return Ht，Sod

在算法迭代過(guò)程中，粒子位置更新操作可能會(huì)使編碼不滿足約束條件，因此需要通過(guò)刪除和回填消除約束沖突：

a）刪除：逐行檢查狀態(tài)編碼，若編碼Ht中不符合規(guī)則，則將一整行編碼全部置為0。

b）回填：根據(jù)矩陣V搜索此任務(wù)的資源池，存在兩種情況。只有一個(gè)邊緣服務(wù)器能處理，此時(shí)只需要將此任務(wù)調(diào)度到這個(gè)邊緣服務(wù)器即可；若有多臺(tái)邊緣服務(wù)器能處理，則根據(jù)式（8）和（10）計(jì)算需要等待的時(shí)間并進(jìn)行排序，選擇需等待時(shí)間最小的邊緣服務(wù)器進(jìn)行處理。

在任務(wù)調(diào)度的過(guò)程中，需要考慮任務(wù)隊(duì)列的動(dòng)態(tài)調(diào)整以確定任務(wù)處理的順序，按式（32）的規(guī)則使較高優(yōu)先級(jí)的任務(wù)具有較高的權(quán)值：

υr（t）=［wr（t）+ωr］ε+1－wr（t）ε+1Wr（t）ε+1（32）

wr（t）代表隊(duì)列Lj（t）中排在任務(wù)r之前所有任務(wù)的優(yōu)先級(jí)之和：

wr（t）=∑r′∈Lj（t）ωr·z（r，r′）（33）

其中：Lj（t）表示t時(shí)刻邊緣服務(wù)器j的任務(wù)隊(duì)列；z（r，r′）∈{0，1}表示在隊(duì)列Lj（t）中任務(wù)r是否排在r′前。Wj（t）表示邊緣服務(wù)器j的任務(wù)隊(duì)列Lj（t）中所有任務(wù)的優(yōu)先級(jí)之和，計(jì)算如下：

Wj（t）=∑r∈Lj（t）ωr（34）

其中：ε∈N+，隨著ε的增大，隊(duì)列尾部具有較高優(yōu)先級(jí)wr的任務(wù)r會(huì)獲得更大的排隊(duì)權(quán)值，這個(gè)特性確保了排在隊(duì)列尾部但具有較高優(yōu)先級(jí)的任務(wù)可以得到及時(shí)的執(zhí)行。

經(jīng)過(guò)上述階段，IBiEO算法的復(fù)雜度分析如下：a）初始化復(fù)雜度為O（N×m），其中N為粒子數(shù)，m為任務(wù)數(shù)（即維數(shù)）；b）計(jì)算適應(yīng)度復(fù)雜度為O（N×m×n），其中n為邊緣服務(wù)器數(shù)；c）保存機(jī)制復(fù)雜度為O（N）；d）位置更新復(fù)雜度為O（N×m×n）；e）刪除回填復(fù)雜度為O（N×m×n）；f）二進(jìn)制轉(zhuǎn)換復(fù)雜度為O（N×m）；g）隊(duì)列調(diào)整復(fù)雜度為O（N×m）。因此IBiEO的總復(fù)雜度為O（N×m×n×Imax），其中Imax為最大迭代數(shù)。

2.4 HA服務(wù)部署算法

HA算法先根據(jù)服務(wù)的全局訪問(wèn)情況作出決策。通過(guò)計(jì)算式（35），全局訪問(wèn)率超過(guò)40%的服務(wù)，因其高頻訪問(wèn)的特性，應(yīng)在所有服務(wù)器上進(jìn)行部署，以確保廣泛的可用性。對(duì)于剩余服務(wù)，則在確保滿足約束C1和C5的前提下，根據(jù)每個(gè)服務(wù)器上的訪問(wèn)模式和優(yōu)先級(jí)特性，以及式（36）計(jì)算其局部訪問(wèn)率，并按照排序?qū)γ恳粋€(gè)服務(wù)進(jìn)行部署。

算法2 HA算法

輸入：當(dāng)前時(shí)間片τ；τ-1的服務(wù)訪問(wèn)記錄。

輸出：系統(tǒng)服務(wù)部署策略Yτ。

1" if" τ是初始周期

2"" 隨機(jī)初始化Yτ

3" else

4"" for i∈S do

5""" 根據(jù)式（35）計(jì)算AGτi并排序

6""" for AGτi＞0.4 do

7"""" for j∈E do

8""""" add i" to" Y jτ， add i to EXI， Cjτ←Cjτ+ci

9""""" for iEXI do

10"""""" 根據(jù)式（36）計(jì)算ALτ i，j并排序

11"""""" if Cjτ＜Aj

12""""" add i to Yjτ， Cjτ←Cjτ+ci

13"" end

其中在τ周期內(nèi)，對(duì)于服務(wù)i，全局訪問(wèn)次數(shù)為χi，帶有優(yōu)先級(jí)的全局訪問(wèn)比例：

AGτi=χi·ωi∑nk=1χk·ωk（35）

在服務(wù)器j的訪問(wèn)次數(shù)為φj，因此局部訪問(wèn)比例為

ALτi，j=φi·ωi∑njk=1φk·ωk（36）

其中：n和nj分別表示系統(tǒng)和服務(wù)器j處理的任務(wù)數(shù)。

HA算法的復(fù)雜度分析如下：a）初始化復(fù)雜度為O（n×k），其中n為邊緣服務(wù)器數(shù)，k為服務(wù)數(shù)；b）計(jì)算訪問(wèn)比例復(fù)雜度O（n）；c）添加服務(wù)復(fù)雜度為O（n×k）。因此HA算法總復(fù)雜度為O（n×k）。

HA_IBiEO算法首先使用HA算法生成服務(wù)部署策略，再調(diào)用IBiEO算法得到目前最佳調(diào)度方案，因此HA_IBiEO算法總體復(fù)雜度為O（N×m×n×Imax+n×k）=O（N×m×n×Imax）。此復(fù)雜度為多項(xiàng)式量級(jí)，因此可以認(rèn)為是一種有效的算法。

3 實(shí)驗(yàn)結(jié)果及評(píng)估

3.1 實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)采用上海電信數(shù)據(jù)集[8，17]和上海用戶訪問(wèn)數(shù)據(jù)集[18]進(jìn)行仿真，前者記錄了上海市區(qū)范圍內(nèi)基站的位置，以及用戶的互聯(lián)網(wǎng)訪問(wèn)日志，日志內(nèi)容包括用戶訪問(wèn)連接的基站，以及開(kāi)始和結(jié)束時(shí)間。但是其沒(méi)有包含與用戶訪問(wèn)內(nèi)容相關(guān)的信息，為了獲得更真實(shí)的用戶訪問(wèn)服務(wù)信息，同時(shí)使用上海用戶訪問(wèn)數(shù)據(jù)集的數(shù)據(jù)進(jìn)行模擬，具體操作如下：

a）根據(jù)其目標(biāo)訪問(wèn)的域名，將目標(biāo)劃分為不同的服務(wù)；

b）統(tǒng)計(jì)不同服務(wù)類型的請(qǐng)求頻率，按照請(qǐng)求頻率排序；

c）對(duì)服務(wù)進(jìn)行擬合，冪律分布參數(shù)0.84;擬合的冪律分布的均方誤差為7.26E－05。擬合服務(wù)分布結(jié)果如圖3所示。

本實(shí)驗(yàn)使用數(shù)據(jù)集中500個(gè)基站的用戶請(qǐng)求數(shù)據(jù)作為輸入，在10個(gè)基站上部署了邊緣服務(wù)器，并使用了2018年阿里巴巴的開(kāi)源數(shù)據(jù)集對(duì)每一個(gè)時(shí)隙內(nèi)邊緣服務(wù)器的CPU利用率和內(nèi)存利用率進(jìn)行模擬。任務(wù)優(yōu)先級(jí)服從1～5的均勻分布。實(shí)驗(yàn)中其他默認(rèn)數(shù)據(jù)參考文獻(xiàn)[24]，具體參數(shù)設(shè)置如表2所示。

本實(shí)驗(yàn)使用臺(tái)式電腦在Python3.9環(huán)境中仿真，配置為IntelCoreTM i5-9400 CPU @ 2.90 GHz，Windows 11專業(yè)版 64位。

本實(shí)驗(yàn)將HA_IBiEO算法與其他算法在系統(tǒng)開(kāi)銷、負(fù)載均衡BL、加權(quán)平均時(shí)延AWRT和超時(shí)比例四個(gè)方面進(jìn)行了比較，對(duì)比的算法如下：

a）LFU_IBiEO：經(jīng)典LFU算法+IBiEO請(qǐng)求調(diào)度算法。

b）HA_BiEO：提出的算法部署服務(wù)+BiEO請(qǐng)求調(diào)度算法[22]。

c）Greedy[16]：基于容量的服務(wù)部署貪婪算法+基于邊緣服務(wù)器間短距離的任務(wù)調(diào)度貪婪算法。

d）Pheu _SA[18]：基于訪問(wèn)量的服務(wù)部署和基于模擬退火的請(qǐng)求調(diào)度算法。

3.2 最大容忍時(shí)延影響

本實(shí)驗(yàn)設(shè)置ωr=1，2，3，4，5時(shí)默認(rèn)的最大容忍時(shí)延Tddlr=500，400，300，200，100 ms，圖4～7展示了當(dāng)最大容忍時(shí)延設(shè)置為Tddlr的0.4，0.6，0.8，1.0，1.2，1.4倍時(shí)算法的性能。

如圖4所示，HA_IBiEO算法在全部情況下都能取得最低的系統(tǒng)開(kāi)銷，LFU_IBiEO次之，這表明了HA_IBiEO算法通過(guò)考慮服務(wù)等級(jí)更有效地將服務(wù)部署在邊緣服務(wù)器上，使得服務(wù)更接近用戶，從而降低了用戶請(qǐng)求的延遲，并且能夠更好地均衡服務(wù)器的負(fù)載。隨著Tdl的增加，所有算法的系統(tǒng)開(kāi)銷均快速下降，直到倍數(shù)大于1（即為默認(rèn)值）時(shí)，系統(tǒng)開(kāi)銷幾乎停止下降，這是因?yàn)榇藭r(shí)已經(jīng)接近系統(tǒng)性能極限了。

圖5顯示了隨著最大容忍時(shí)延的增加所有算法的負(fù)載均衡性能。在這個(gè)過(guò)程中，HA_IBiEO算法均實(shí)現(xiàn)了最低的BL值。此外，隨著Tdl的增大， HA_IBiEO、LFU_IBiEO和HA_BiEO均是下降的趨勢(shì)，而Greedy呈波動(dòng)的趨勢(shì)并且一直居于最高，Pheu _SA幾乎不變。這是因?yàn)殡S著時(shí)延限制變得寬松，前三種算法能較靈活地對(duì)任務(wù)進(jìn)行調(diào)度，進(jìn)而更好地平衡負(fù)載；Pheu _SA雖然選擇了處理請(qǐng)求數(shù)量最少且性能最好的服務(wù)器來(lái)處理請(qǐng)求，但這種選擇是基于局部信息的，可能導(dǎo)致某些服務(wù)器負(fù)載過(guò)重，而其他服務(wù)器處于空閑狀態(tài)的情況，從而不能實(shí)現(xiàn)整體負(fù)載均衡。Greedy只考慮到了任務(wù)與節(jié)點(diǎn)之間的距離，而忽略了任務(wù)的執(zhí)行時(shí)間、資源需求以及節(jié)點(diǎn)的負(fù)載情況等因素，這會(huì)導(dǎo)致任務(wù)分配不合理，出現(xiàn)負(fù)載不均衡的情況。

如圖6所示，隨著最大容忍時(shí)延的增加，所有算法的AWRT呈現(xiàn)不同趨勢(shì)。其中，由于Greedy遵循短距離優(yōu)先策略，所以其AWRT一直居于最高，并且變化不大；Pheu _SA在選擇最優(yōu)服務(wù)器時(shí)主要考慮了服務(wù)器的處理數(shù)量和性能度量，并沒(méi)有直接考慮時(shí)延因素。因此，即使存在最大容忍時(shí)延，也不會(huì)直接影響算法選擇服務(wù)器的決策過(guò)程。因此Pheu _SA也是整體變化不大；HA_IBiEO、LFU_IBiEO和HA_BiEO均是上升的趨勢(shì)，這是因?yàn)殡S著Tdl的增加，系統(tǒng)更容易接受較長(zhǎng)的響應(yīng)時(shí)間而不會(huì)嚴(yán)格懲罰。這可能導(dǎo)致算法在目標(biāo)函數(shù)中更多地考慮了負(fù)載均衡優(yōu)化，而對(duì)時(shí)延的影響較少，從而導(dǎo)致AWRT的上升。

如圖7所示，當(dāng)Tdl很小時(shí)，所有的算法超時(shí)比例均很高，只有HA_IBiEO和LFU_IBiEO超時(shí)比例低于30%，隨著Tdl的增大，各個(gè)算法的超時(shí)比例快速下降，這是因?yàn)橄到y(tǒng)更容易將任務(wù)分配到負(fù)載較輕的服務(wù)器上，以改善負(fù)載均衡。這會(huì)導(dǎo)致任務(wù)的響應(yīng)時(shí)間更短，從而減少了出現(xiàn)超時(shí)的可能性，使超時(shí)比例迅速下降。當(dāng)Tdl超過(guò)默認(rèn)值后，系統(tǒng)可能會(huì)遇到負(fù)載均衡優(yōu)化的局限性。已經(jīng)分配到負(fù)載較輕的服務(wù)器上的請(qǐng)求已經(jīng)盡可能地減少了響應(yīng)時(shí)間，因此進(jìn)一步的負(fù)載均衡優(yōu)化效果減弱。同時(shí)由于系統(tǒng)對(duì)時(shí)延的容忍度也增加，即使任務(wù)被分配到了響應(yīng)時(shí)間較長(zhǎng)的服務(wù)器上，系統(tǒng)也不會(huì)立即認(rèn)為這是一個(gè)超時(shí)情況，從而使超時(shí)比例的下降速度減緩。因此繼續(xù)增加Tdl不會(huì)帶來(lái)額外的超時(shí)比例下降。

總體而言，通過(guò)比較HA_IBiEO和基準(zhǔn)算法，可以看出HA_IBiEO由于服務(wù)部署時(shí)考慮優(yōu)先級(jí)權(quán)重，并在任務(wù)調(diào)度時(shí)能夠根據(jù)資源狀態(tài)選擇最佳的服務(wù)器進(jìn)行處理，從而在時(shí)延和負(fù)載均衡方面均表現(xiàn)得較好。同時(shí)通過(guò)對(duì)圖4的分析得知，此系統(tǒng)在ωr=1，2，3，4，5時(shí)Tddlr分別取值500， 400， 300， 200， 100 ms較為合適。此時(shí)HA_IBiEO系統(tǒng)開(kāi)銷比LFU_IBiEO低6.94%，比HA_BiEO低17.03%，比Pheu _SA低20.78%，比Greedy低25.96%。

3.3 邊緣服務(wù)器計(jì)算資源影響

如圖8所示，在不同的計(jì)算資源條件下，HA_IBiEO性能均表現(xiàn)得最好，隨著計(jì)算資源的升高，各個(gè)算法的系統(tǒng)開(kāi)銷均降低，主要原因是計(jì)算資源的提高有效降低了任務(wù)的處理時(shí)延。當(dāng)從5到20增加計(jì)算資源時(shí)，系統(tǒng)開(kāi)銷下降速度很快，而當(dāng)計(jì)算資源提高至20后，系統(tǒng)開(kāi)銷的降速減緩，圖9和10也出現(xiàn)類似的趨勢(shì)，這是因?yàn)樵鹊挠?jì)算資源較少，導(dǎo)致系統(tǒng)處于高負(fù)載狀態(tài)，任務(wù)排隊(duì)等待執(zhí)行，造成了較長(zhǎng)的響應(yīng)時(shí)間。而增加了計(jì)算資源后，系統(tǒng)可以更快地響應(yīng)任務(wù)，減少了排隊(duì)等待的時(shí)間；然而，當(dāng)從20到30增加計(jì)算資源時(shí)，增加的資源對(duì)性能改善的貢獻(xiàn)逐漸減小，因此AWRT的改善速度也會(huì)相應(yīng)減緩。

圖11顯示了隨著計(jì)算資源增加所有算法的負(fù)載均衡性能。在這個(gè)過(guò)程中，HA_IBiEO算法均實(shí)現(xiàn)了最低的BL值。隨著計(jì)算資源的升高，各個(gè)算法的負(fù)載均衡均表現(xiàn)得更好，這是因?yàn)楦嗟娜蝿?wù)可以在邊緣服務(wù)器上處理，算法可以更有效地將任務(wù)分配到不同的服務(wù)器上，以確保各個(gè)服務(wù)器的負(fù)載更均衡。這樣可以避免某些服務(wù)器負(fù)載過(guò)重，而其他服務(wù)器處于空閑狀態(tài)的情況，從而提升了負(fù)載均衡的效果。

在邊緣服務(wù)器計(jì)算資源不同的情況下，HA_IBiEO均保持了較低的系統(tǒng)開(kāi)銷，且在減少時(shí)延的同時(shí)也保證了系統(tǒng)的負(fù)載均衡。同時(shí)結(jié)合圖8各性能的分析可知，系統(tǒng)應(yīng)設(shè)計(jì)算資源為20最佳。

3.4 任務(wù)到達(dá)率影響

圖12～15統(tǒng)計(jì)了任務(wù)到達(dá)率改變時(shí)，算法在不同負(fù)載強(qiáng)度下的性能。

如圖12所示，在全部情況下，HA_IBiEO均能取得較低的系統(tǒng)開(kāi)銷。隨著任務(wù)到達(dá)率的升高，各個(gè)算法的系統(tǒng)開(kāi)銷均升高，圖14和15也呈現(xiàn)相似的趨勢(shì)，這是因?yàn)檫吘壏?wù)器的負(fù)載隨著任務(wù)到達(dá)率的增加而不斷上升，系統(tǒng)中同時(shí)存在大量的待處理任務(wù)，導(dǎo)致任務(wù)排隊(duì)等待時(shí)間增加，因此任務(wù)的響應(yīng)時(shí)間增加，從而影響AWRT和超時(shí)比例。同時(shí)，從圖15可以看出，HA_IBiEO的超時(shí)比例是唯一一個(gè)在所有的情況下低于50%的，甚至在較低的任務(wù)到達(dá)率時(shí)超時(shí)比例幾乎接近0。而Greedy由于遵循短距離優(yōu)先策略而忽略了任務(wù)的特性，導(dǎo)致任務(wù)排隊(duì)時(shí)延過(guò)高，所以超時(shí)比例一直居于高位。如圖14所示，HA_IBiEO平均AWRT比LFU_IBiEO低20.05%，比HA_BiEO低30.45%，比Pheu _SA低30.45%，比Greedy低69.43%。

如圖13所示，隨著任務(wù)到達(dá)率的增加，各個(gè)算法的BL都在上升，這是因?yàn)橄到y(tǒng)中的任務(wù)數(shù)量增加，導(dǎo)致各個(gè)服務(wù)器的負(fù)載逐漸增加。在任務(wù)到達(dá)率大于105后，各個(gè)算法的BL均緩慢上升，這是因?yàn)槊總€(gè)服務(wù)器受限于當(dāng)前的服務(wù)部署策略，導(dǎo)致能夠處理的任務(wù)受到限制，從而使負(fù)載均衡的上升速度變得緩慢。總體而言，HA_IBiEO系統(tǒng)負(fù)載均衡BL比LFU_IBiEO低17.02%，比HA_BiEO低15.47%，比Pheu _SA低17.32%，比Greedy低39.19%。

圖12～15均表明，HA_IBiEO優(yōu)于其他算法。在所有的任務(wù)到達(dá)率情況下，HA_IBiEO系統(tǒng)開(kāi)銷平均比LFU_IBiEO低8.42%，比HA_BiEO低11.32%，比Pheu _SA低18.80%，比Greedy低23.73%。

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

本文針對(duì)智慧城市中多服務(wù)場(chǎng)景下邊緣協(xié)作的聯(lián)合服務(wù)部署與任務(wù)調(diào)度問(wèn)題進(jìn)行了研究。首先將此問(wèn)題建模為優(yōu)化系統(tǒng)時(shí)延和負(fù)載均衡的多目標(biāo)優(yōu)化問(wèn)題，模型中引入分段SLA以提高靈活性；然后提出一種基于HA_IBiEO的聯(lián)合服務(wù)部署和任務(wù)調(diào)度算法來(lái)解決這個(gè)問(wèn)題；最后通過(guò)一系列基于上海電信基站數(shù)據(jù)集的對(duì)比實(shí)驗(yàn)來(lái)評(píng)估算法的性能。實(shí)驗(yàn)結(jié)果表明，提出的聯(lián)合算法實(shí)現(xiàn)了更低系統(tǒng)時(shí)延的同時(shí)，保證了邊緣服務(wù)器負(fù)載的均衡。

對(duì)于未來(lái)的工作，筆者將考慮針對(duì)用戶移動(dòng)軌跡和任務(wù)請(qǐng)求趨勢(shì)的時(shí)空預(yù)測(cè)研究，以適應(yīng)更普遍的MEC場(chǎng)景；此外，未來(lái)將會(huì)在系統(tǒng)建模時(shí)考慮更多的QoS指標(biāo)，如能耗、成本等。

參考文獻(xiàn)：

[1]Luo Quyuan， Hu Shihong， Li Changle， et al. Resource scheduling in edge computing： a survey [J]. IEEE Communications Surveys amp; Tutorials， 2021， 23 （4）： 2131-2165.

[2]Taleb T， Samdanis K， Mada B， et al. On multi-access edge computing： a survey of the emerging 5G network edge cloud architecture and orchestration [J]. IEEE Communications Surveys amp; Tutorials， 2017， 19 （3）： 1657-1681.

[3]Anderson C. Docker [software engineering] [J]. IEEE Software， 2015， 32 （3）： 102-c3.

[4]彭青藍(lán)， 夏云霓， 鄭萬(wàn)波， 等. 一種去中心化的在線邊緣任務(wù)調(diào)度與資源分配方法 [J]. 計(jì)算機(jī)學(xué)報(bào)， 2022， 45 （7）： 1462-1477. （Peng Qinglan， Xia Yunni， Zheng Wanbo， et al. A decentralized online edge task scheduling and resource allocation method [J]. Journal of Computing， 2022， 45 （7）： 1462-1477.）

[5]Tan Haisheng， Han Zhenhua， Li Xiangyang， et al. Online job dispatching and scheduling in edge-clouds [C]// Proc of IEEE INFOCOM-IEEE Conference on Computer Communications. Piscataway， NJ： IEEE Press， 2017： 1-9.

[6]Alqahtani F，Amoon M， Nasr A A. Reliable scheduling and load ba-lancing for requests in cloud-fog computing [J]. Peer-to-Peer Networking and Applications， 2021， 14 （4）： 1905-1916.

[7]Meng Jiaying， Tan Haisheng， Xu Chao， et al. Dedas： online task dispatching and scheduling with bandwidth constraint in edge computing [C]// Proc of IEEE INFOCOM-IEEE Conference on Computer Communications." Piscataway， NJ： IEEE Press， 2019： 2287-2295.

[8]孔珊， 鄭玉琦. 基于進(jìn)化多任務(wù)多目標(biāo)優(yōu)化的邊緣計(jì)算任務(wù)卸載 [J]. 計(jì)算機(jī)應(yīng)用研究， 2024， 41 （4）： 1164-1170. （Kong Shan， Zheng Yuqi. Edge computing task offloading based on evolutionary multi-task multi-objective optimization [J]. Applications Research of Computers， 2024， 41 （4）： 1164-1170.）

[9]Aral A，Ovatman T. A decentralized replica placement algorithm for edge computing [J]. IEEE Trans on Network and Service Mana-gement， 2018， 15 （2）： 516-529.

[10]Gu Lin， Chen Zirui， Xu Honghao， et al. Layer-aware collaborative microservice deployment toward maximal edge throughput [C]// Proc of IEEE INFOCOM-IEEE Conference on Computer Communications." Piscataway， NJ： IEEE Press，" 2022： 71-79.

[11]Wang Shangguang， Guo Yan， Zhang Ning， et al. Delay-aware microservice coordination in mobile edge computing： a reinforcement learning approach [J]. IEEE Trans on Mobile Computing， 2021， 20 （3）： 939-951.

[12]Cabrera C， Svorobej S， Palade A， et al. MAACO： a dynamic service placement model for smart cities [J]. IEEE Trans on Services Computing， 2023， 16 （1）： 424-437.

[13]Huang Jie， Zhou Ao， Wang Shangguang. price-aware service deployment in hierarchical mobile-edge computing [J]. IEEE Internet of Things Journal， 2022， 9 （13）： 11533-11541.

[14]He Ting， Khamfroush H， Wang Shiqiang， et al. It’s hard to share： joint service placement and request scheduling in edge clouds with sharable and non-sharable resources [C]// Proc of the 38th IEEE International Conference on Distributed Computing Systems." Piscataway， NJ： IEEE Press，" 2018： 365-375.

[15]Xu Jie， Chen Lixing， Zhou Pan. Joint service caching and task offloading for mobile edge computing in dense networks [C]// Proc of IEEE INFOCOM-IEEE Conference on Computer Communications." Piscataway， NJ： IEEE Press，" 2018： 207-215.

[16]Poularakis K， Llorca J， Tulino A M， et al. Joint service placement and request routing in multi-cell mobile edge computing networks [C]// Proc of IEEE INFOCOM-IEEE Conference on Computer Communications." Piscataway， NJ： IEEE Press，" 2019： 10-18.

[17]Xu Yangchuan， Chen Lulu， Lu Zhihui， et al. An adaptive mechanism for dynamically collaborative computing power and task scheduling in edge environment [J]. IEEE Internet of Things Journal， 2023， 10 （4）： 3118-3129.

[18]Liu Haojiang， Li Yuanzhe， Wang Shangguang. Request scheduling combined with load balancing in mobile-edge computing [J]. IEEE Internet of Things Journal， 2022， 9 （21）： 20841-20852.

[19]韓超臣， 張俊娜， 王欣新， 等. 基于服務(wù)更新的異構(gòu)任務(wù)卸載方法 [J]. 計(jì)算機(jī)應(yīng)用研究，2024，41（8）：2481-2488. （Han Chao-chen， Zhang Junna， Wang Xinxin， et al. A heterogeneous task offloading method based on service update [J]. Applications Research of Computers，2024，41（8）：2481-2488.）

[20]Yang Lichao， Zhang Heli， Li Xi， et al. A distributed computation offloading strategy in small-cell networks integrated with mobile edge computing [J]. IEEE/ACM Trans on Networking， 2018， 26 （6）： 2762-2773.

[21]Zhao Xingbing， Zeng Yu， Ding Hongwei， et al. Optimize the placement of edge server between workload balancing and system delay in smart city [J]. Peer-to-Peer Networking and Applications， 2021， 14 （6）： 3778-3792.

[22]Faramarzi A， Mirjalili S， Heidarinejad M. Binary equilibrium optimizer： theory and application in building optimal control problems [J]. Energy and Buildings， 2022， 277： 112503.

[23]Chen Yuxiang， Liu Jianhua， Zhu Jian， et al. An improved binary particle swarm optimization combing V-shaped and U-shaped transfer function [J]. Evolutionary Intelligence， 2023， 16 （5）： 1653-1666.

[24]Poularakis K， Llorca J， Tulino A M， et al. Service placement and request routing in MEC networks with storage， computation， and communication constraints [J]. IEEE/ACM Trans on Networking， 2020， 28 （3）： 1047-1060.

[25]Al Ridhawi I， Otoum S， Aloqaily M， et al. Providing secure and relia-ble communication for next generation networks in smart cities [J]. Sustainable Cities and Society， 2020， 56： 102080.

[26]Li Yuanzhe， Zhou Ao， Ma Xiao， et al. Profit-aware edge server placement [J]. IEEE Internet of Things Journal， 2022， 9 （1）： 55-67.

[27]Guo Yan， Wang Shangguang， Zhou Ao， et al. User allocation-aware edge cloud placement in mobile edge computing [J]. Software： Practice and Experience， 2020， 50 （5）： 489-502.