袁景凌，毛慧華，王娜娜，向堯

移動(dòng)邊緣計(jì)算中資源受限的動(dòng)態(tài)服務(wù)部署策略

袁景凌1，2，毛慧華1，2，王娜娜3，向堯2*

（1.武漢理工大學(xué) 三亞科教創(chuàng)新園，海南 三亞 572019； 2.武漢理工大學(xué) 計(jì)算機(jī)與人工智能學(xué)院，武漢 430070； 3.武漢理工大學(xué) 土木工程與建筑學(xué)院，武漢 430070）（*通信作者電子郵箱hbycxiangyao@163.com）

移動(dòng)邊緣計(jì)算（MEC）的出現(xiàn)使移動(dòng)用戶能夠以低延遲訪問部署在邊緣服務(wù)器上的服務(wù)。然而，MEC仍然存在各種挑戰(zhàn)，尤其是服務(wù)部署問題。邊緣服務(wù)器的數(shù)量和資源通常是有限的，只能部署數(shù)量有限的服務(wù)；此外，用戶的移動(dòng)性改變了不同服務(wù)在不同地區(qū)的流行度。在這種情況下，為動(dòng)態(tài)請(qǐng)求部署合適的服務(wù)就成為一個(gè)關(guān)鍵問題。針對(duì)該問題，通過了解動(dòng)態(tài)用戶請(qǐng)求來部署適當(dāng)?shù)姆?wù)以最小化交互延遲，將服務(wù)部署問題表述為一個(gè)全局優(yōu)化問題，并提出了一種基于集群劃分的資源聚合算法，從而在計(jì)算、帶寬等資源約束下初步部署合適的服務(wù)。此外，考慮動(dòng)態(tài)用戶請(qǐng)求對(duì)服務(wù)流行度及邊緣服務(wù)器負(fù)載的影響，開發(fā)了動(dòng)態(tài)調(diào)整算法來更新現(xiàn)有服務(wù)，以確保服務(wù)質(zhì)量（QoS）始終滿足用戶期望。通過一系列仿真實(shí)驗(yàn)驗(yàn)證了所提出策略的性能。仿真結(jié)果表明，與現(xiàn)有基準(zhǔn)算法相比，所提出的策略可以降低服務(wù)交互延遲并實(shí)現(xiàn)更穩(wěn)定的負(fù)載均衡。

服務(wù)部署；移動(dòng)邊緣計(jì)算；資源約束；動(dòng)態(tài)需求感知；服務(wù)流行度

0 引言

隨著互聯(lián)網(wǎng)和無線通信技術(shù)的快速發(fā)展，移動(dòng)計(jì)算已經(jīng)極大地改變了人們的日常生活；然而，許多新的服務(wù)和時(shí)延敏感的應(yīng)用不斷出現(xiàn)，如虛擬現(xiàn)實(shí)（Virtual Reality， VR）和增強(qiáng)現(xiàn)實(shí)（Augmented Reality， AR）等［1］。此外，在工程領(lǐng)域，一些現(xiàn)代化的項(xiàng)目往往結(jié)合人工智能、VR等智能化技術(shù)，通過終端來進(jìn)行管理和控制，如大壩的監(jiān)測(cè)和預(yù)警。移動(dòng)設(shè)備的資源（如計(jì)算和存儲(chǔ)）限制了這些復(fù)雜服務(wù)的普及［2］。為了克服移動(dòng)設(shè)備電池容量和計(jì)算能力的限制，一些解決方案［3］將任務(wù)卸載到云計(jì)算中心以解決資源短缺的問題。然而，由于廣域網(wǎng)通信延遲較高，將任務(wù)卸載到云端可能帶來較低的服務(wù)質(zhì)量（Quality of Service， QoS）。

移動(dòng)邊緣計(jì)算（Mobile Edge Computing， MEC）的出現(xiàn)提供了新的思路［4-5］。通過在終端用戶附近部署邊緣服務(wù)器（Edge Server）來提供服務(wù)，用戶可以直接訪問并獲得更好的QoS，而無需求助于云端，與傳統(tǒng)方案相比，可以進(jìn)一步縮短服務(wù)響應(yīng)時(shí)間。

但是MEC也存在各種挑戰(zhàn)，尤其是服務(wù)部署問題［6］。與具有豐富計(jì)算資源和巨大存儲(chǔ)空間的云計(jì)算中心相比，邊緣服務(wù)器的規(guī)模更小，通常只配備輕量級(jí)的計(jì)算組件和有限的存儲(chǔ)、帶寬等資源，所以邊緣服務(wù)器只能部署數(shù)量有限的服務(wù)，因此，需要仔細(xì)選擇所要部署的服務(wù)來提高QoS［7］。此外，服務(wù)部署和任務(wù)卸載具有高度耦合性，服務(wù)部署策略會(huì)影響任務(wù)卸載決策，進(jìn)而影響MEC系統(tǒng)的性能［8］。由于用戶的移動(dòng)性，用戶需求會(huì)隨著時(shí)間的推移而動(dòng)態(tài)變化，從而影響服務(wù)的流行程度，使較早部署的服務(wù)不再適用。在這種情況下，為動(dòng)態(tài)變化的服務(wù)需求自適應(yīng)地調(diào)整服務(wù)就成為一個(gè)關(guān)鍵問題。

隨著移動(dòng)計(jì)算的發(fā)展和邊緣云的出現(xiàn)，移動(dòng)邊緣系統(tǒng)中的服務(wù)部署問題也得到了廣泛研究［9-12］。對(duì)于優(yōu)化目標(biāo)，一些研究方法側(cè)重于服務(wù)成本［9］或者服務(wù)提供商（Service Provider， SP）的利潤(rùn)［10］，而另一些研究方法則關(guān)注于減少服務(wù)部署的延遲［12］或者服務(wù)響應(yīng)時(shí)間［13-14］。例如，文獻(xiàn)［9］中考慮成本，提出了一種基于認(rèn)證的云服務(wù)組合方法，該方法同時(shí)考慮了部署和認(rèn)證/驗(yàn)證的成本；文獻(xiàn)［10］中的目標(biāo)是最大化所有服務(wù)提供商的總利潤(rùn)，提出了一種基于李雅普諾夫優(yōu)化的在線算法來研究聯(lián)合服務(wù)放置和請(qǐng)求調(diào)度問題；文獻(xiàn)［11］中主要關(guān)注跨多個(gè)軟件定義網(wǎng)絡(luò)（Software Defined Network， SDN）的動(dòng)態(tài)網(wǎng)絡(luò)服務(wù)部署問題，并利用Dijkstra算法提出了一種啟發(fā)式服務(wù)部署方法來解決這個(gè)問題；文獻(xiàn)［13］中研究了復(fù)合云服務(wù)的部署和請(qǐng)求調(diào)度問題，提出了負(fù)載感知的服務(wù)部署方法和基于任務(wù)排序機(jī)制的服務(wù)請(qǐng)求調(diào)度方法。

本文旨在根據(jù)動(dòng)態(tài)服務(wù)需求為每個(gè)邊緣服務(wù)器設(shè)計(jì)服務(wù)部署策略，以使用戶的交互延遲最小化；此外，還考慮了邊緣服務(wù)器的資源限制以及如何平衡邊緣服務(wù)器的請(qǐng)求負(fù)載。

本文主要工作總結(jié)如下：

1）提出了一種基于集群劃分的資源聚合算法，將邊緣服務(wù)器劃分成集群，在計(jì)算、存儲(chǔ)和帶寬資源的約束下初步部署合適的服務(wù)。

2）考慮了動(dòng)態(tài)用戶需求對(duì)服務(wù)流行度及邊緣服務(wù)器負(fù)載的影響，提出了一種動(dòng)態(tài)調(diào)整算法來更新現(xiàn)有服務(wù)，保持整個(gè)邊緣網(wǎng)絡(luò)的穩(wěn)定性。

3）實(shí)施了仿真實(shí)驗(yàn)來評(píng)估本文所提出策略的性能，與遺傳算法（Genetic Algorithm， GA）、模擬退火（Simulated Annealing， SA）算法、隨機(jī)算法（Random）和貪婪算法（Greedy）等基準(zhǔn)算法相比，本文的策略可以有效地減少交互延遲并實(shí)現(xiàn)更穩(wěn)定的負(fù)載均衡。

1 問題描述與建模

本章詳細(xì)闡述服務(wù)部署問題和系統(tǒng)模型。

圖1 邊緣服務(wù)器上的服務(wù)部署示例

2 動(dòng)態(tài)服務(wù)部署策略

對(duì)于第一章中描述的問題，本文提出了一種動(dòng)態(tài)需求感知和負(fù)載均衡（Dynamic Requirement Awareness and Load Balance， DRLB）的策略來動(dòng)態(tài)更新服務(wù)。該策略包括初始服務(wù)部署和動(dòng)態(tài)調(diào)整兩個(gè)階段。

2.1 初始服務(wù)部署階段

在部署服務(wù)之前，一般需花費(fèi)巨大的成本收集所有邊緣服務(wù)器的狀態(tài)。為了使服務(wù)部署和動(dòng)態(tài)調(diào)整更容易，將邊緣服務(wù)器劃分為多個(gè)集群。

集群劃分過程如算法1所示，主要包括三個(gè)步驟：

3）對(duì)于剩下未分配到集群中的邊緣服務(wù)器，將其劃分到最近的中心邊緣服務(wù)器所在的集群。

算法1 集群劃分算法。

算法2 服務(wù)部署算法。

6） 根據(jù)式（3）～（5）計(jì)算約束條件；

7） If 不滿足約束條件 then

8） 按照排序次序補(bǔ)選；

9） End If

10） End For

2.2 動(dòng)態(tài)服務(wù)調(diào)整階段

算法3 服務(wù)動(dòng)態(tài)更新算法。

輸出 該集群調(diào)整后的服務(wù)部署方案。

4） End For

9） End If

12） End If

15） End If

16） End For

17） End For

3 仿真與分析

本文將遺傳算法（GA）、模擬退火（SA）算法、隨機(jī)算法（Random）和貪婪算法（Greedy）作為基準(zhǔn)算法。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

如第2章所述，問題的規(guī)模主要與集群、服務(wù)和邊緣服務(wù)器的數(shù)量。本文參考了文獻(xiàn)［6］中的實(shí)驗(yàn)方法來測(cè)試這三個(gè)參數(shù)對(duì)本文策略DRLB性能的影響?？紤]了三組參數(shù)，如表2所示。在每組參數(shù)中，其中一個(gè)參數(shù)是變化的，另外兩個(gè)參數(shù)保持不變。所有實(shí)驗(yàn)均重復(fù)10次，使用平均值作為結(jié)果。

表2 變量設(shè)置

圖2 集群數(shù)量對(duì)平均交互延遲的影響

圖3 集群數(shù)量對(duì)負(fù)載均衡的影響

圖4、5顯示了不同服務(wù)數(shù)量對(duì)平均交互延遲和負(fù)載均衡的影響。從圖4中可以看出，本文策略DRLB在所有情況下的平均交互延遲均最小。從圖5中還可以發(fā)現(xiàn)，本文策略DRLB的服務(wù)請(qǐng)求量的方差均值也是對(duì)比算法中最小的，這表明本文策略在面對(duì)更復(fù)雜的用戶請(qǐng)求時(shí)保證了更穩(wěn)定的QoS。

不同數(shù)量的邊緣服務(wù)器對(duì)平均交互延遲的影響如圖6所示，可以看出所有方法的平均交互延遲隨著邊緣服務(wù)器數(shù)量的增加而增加，這是因?yàn)檫吘壏?wù)器的數(shù)量對(duì)優(yōu)化空間有影響，會(huì)增加問題解決的復(fù)雜性。邊緣服務(wù)器數(shù)量對(duì)負(fù)載均衡的影響如圖7所示，可以看出本文策略DRLB的服務(wù)請(qǐng)求量的方差更小，明顯優(yōu)于其他基準(zhǔn)算法，圖5中也體現(xiàn)了這一點(diǎn)。綜上所述，可以得出結(jié)論，本文策略能夠解決不同規(guī)模的服務(wù)部署問題，具有良好的可擴(kuò)展性；此外，該策略的動(dòng)態(tài)調(diào)整算法還具有提高邊緣服務(wù)器負(fù)載均衡的能力。。

圖4 服務(wù)數(shù)量對(duì)平均交互延遲的影響

圖5 服務(wù)數(shù)量對(duì)負(fù)載均衡的影響

圖6 邊緣服務(wù)器數(shù)量對(duì)平均交互延遲的影響

圖7 邊緣服務(wù)器數(shù)量對(duì)負(fù)載均衡的影響

4 結(jié)語

本文重點(diǎn)研究了邊緣計(jì)算系統(tǒng)中的服務(wù)部署和更新機(jī)制，提出了資源受限的動(dòng)態(tài)服務(wù)部署策略DRLB。借助服務(wù)流行度來動(dòng)態(tài)調(diào)整服務(wù)的部署，本文策略可以實(shí)現(xiàn)更穩(wěn)定的負(fù)載均衡。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)方法相比，本文策略可以實(shí)現(xiàn)更低的平均交互延遲。未來將會(huì)在更實(shí)際的場(chǎng)景中考慮這個(gè)問題，比如預(yù)測(cè)用戶的路徑以及邊緣之間的服務(wù)協(xié)作，以進(jìn)一步提高部署質(zhì)量。

[1] REN J， ZHANG D Y， HE S W， et al. A survey on end-edge-cloud orchestrated network computing paradigms： transparent computing， mobile edge computing， fog computing， and cloudlet［J］. ACM Computing Surveys， 2020， 52（6）： No.125.

[2] XIANG Z， DENG S， TAHERI J， et al. Dynamical service deployment and replacement in resource-constrained edges［J］. Mobile Networks and Applications， 2020， 25（2）： 674-689.

[3] GUO S T， XIAO B， YANG Y Y， et al. Energy-efficient dynamic offloading and resource scheduling in mobile cloud computing［C］// Proceedings of the 35th Annual IEEE International Conference on Computer Communications. Piscataway： IEEE， 2016： 1-9.

[4] FERRER A J， MARQUèS J M， JORBA J. Towards the decentralised cloud： survey on approaches and challenges for mobile， ad hoc， and edge computing［J］. ACM Computing Surveys， 2019， 51（6）： No.111.

[5] YIN J W， ZHENG B P， DENG S G， et al. Crossover service： deep convergence for pattern， ecosystem， environment， quality and value［C］// Proceedings of the IEEE 38th International Conference on Distributed Computing Systems. Piscataway： IEEE， 2018： 1250-1257.

[6] PENG Q L， XIA Y N， FENG Z， et al. Mobility-aware and migration-enabled online edge user allocation in mobile edge computing［C］// Proceedings of the 2019 IEEE International Conference on Web Services. Piscataway： IEEE， 2019： 91-98.

[7] WU H Y， DENG S G， LI W， et al. Mobility-aware service selection in mobile edge computing systems［C］// Proceedings of the 2019 IEEE International Conference on Web Services. Piscataway： IEEE， 2019： 201-208.

[8] LI X， ZHANG X L， HUANG T S. Asynchronous online service placement and task offloading for mobile edge computing［C］// Proceedings of the 18th Annual IEEE International Conference on Sensing， Communication， and Networking. Piscataway： IEEE， 2021： 1-9.

[9] ANISETTI M，ARDAGNA C A， DAMIANI E， et al. Cost-effective deployment of certified cloud composite services［J］. Journal of Parallel and Distributed Computing， 2020， 135： 203-218.

[10] LEI Z， XU H， HUANG L， et al. Joint service placement and request scheduling for multi-SP mobile edge computing network［C］// Proceedings of the IEEE 26th International Conference on Parallel and Distributed Systems. Piscataway： IEEE， 2020： 27-34.

[11] ZHANG C C， WANG X W， DONG A W， et al. Dynamic network service deployment across multiple SDN domains［J］. Transactions on Emerging Telecommunications Technologies， 2020， 31（2）： No.e3709.

[12] ZHANG S L， LIU C， WANG J W， et al. Latency-aware deployment of IoT services in a cloud-edge environment［C］// Proceedings of the 2019 International Conference on Service-Oriented Computing. Cham： Springer， 2019： 231-236.

[13] ZHOU J Y， FAN J X， WANG J， et al. Dynamic service deployment for budget-constrained mobile edge computing［J］. Concurrency and Computation： Practice and Experience， 2019， 31（24）： No. e5436.

[14] LU Y C， LIN C K， LAI K C， et al. Service deployment and scheduling for improving performance of composite cloud services［J］. Computers and Electrical Engineering， 2019， 74： 616-634.

[15] 陳玉平，劉波，林偉偉，等. 云邊協(xié)同綜述［J］. 計(jì)算機(jī)科學(xué)， 2021， 48（3）： 259-268.（CHEN Y P， LIU B， LIN W W， et al. Survey of cloud-edge collaboration［J］. Computer Science， 2021， 48（3）： 259-268.）

[16] NEWMAN M E J. Power laws， Pareto distributions and Zipf’s law［J］. Contemporary Physics， 2005， 46（5）： 323-351.

Dynamic service deployment strategy in resource constrained mobile edge computing

YUAN Jingling1，2， MAO Huihua1，2， WANG Nana3， XIANG Yao2*

（1，，572019，；2，，430070，；3，，430070，）

The emergence of Mobile Edge Computing （MEC） enables mobile users to easily access services deployed on edge servers with low latency. However， there are various challenges in MEC， especially service deployment issues. The number and resources of edge servers are usually limited and only a limited number of services can be deployed on the edge servers； in addition， the mobility of users changes the popularities of different services in different regions. In this context， deploying suitable services for dynamic service requests becomes a critical problem. To address this problem， by deploying appropriate services by awareness of the dynamic user requirements to minimize interaction delay， the service deployment problem was formulated as a global optimization problem， and a cluster-based resource aggregation algorithm was proposed， which initially deployed suitable services under the resource constraints such as computing and bandwidth. Moreover， considering the influence of dynamic user requests on service popularity and edge server load， a dynamic adjustment algorithm was developed to update the existing services to ensure that the Quality of Service （QoS） always met user expectations. The performance of this deployment strategy was verified through a series of simulation experiments. Simulation results show that compared with the existing benchmark algorithms， the proposed strategy can reduce service interaction delay and achieve a more stable load balance.

service deployment; Mobile Edge Computing (MEC); resource constraint; dynamic requirement awareness; service popularity

This work is partially supported by National Natural Science Foundation of China （61303029）， Major Science and Technology Project of Sanya Yazhou Bay Science and Technology City Administration （SKJC-KJ-2019KY02）.

YUAN Jingling， born in 1975， Ph. D.， professor. Her research interests include machine learning， distributed parallel processing， intelligent analysis.

MAO Huihua， born in 1996， M. S. candidate. His research interests include edge intelligence， edge computing.

WANG Nana， born in 1978， Ph. D. Her research interests include intelligent method， safety monitoring.

XIANG Yao， born in 1989， Ph. D. His research interests include mobile edge computing， intelligent computing.

TP393

A

1001-9081（2022）06-1662-06

10.11772/j.issn.1001-9081.2021061615

2021?09?13；

2021?11?19；

2021?11?24。

國(guó)家自然科學(xué)基金資助項(xiàng)目（61303029）；三亞崖州灣科技城管理局重大科技項(xiàng)目（SKJC?KJ?2019KY02）。

袁景凌（1975—），女，湖北武漢人，教授，博士，CCF會(huì)員，主要研究方向：機(jī)器學(xué)習(xí)、分布式并行處理、智能分析；毛慧華（1996—），男，江西宜春人，碩士研究生，CCF會(huì)員，主要研究方向：邊緣智能、邊緣計(jì)算；王娜娜（1978—），女，山東青島人，博士，主要研究方向：智能方法、安全監(jiān)測(cè)；向堯（1989—），男，湖北宜昌人，博士，CCF會(huì)員，主要研究方向：邊緣計(jì)算、智能計(jì)算。