移動邊緣計算中資源受限的動態服務部署策略

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

移動邊緣計算中資源受限的動態服務部署策略

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

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

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

服務部署；移動邊緣計算；資源約束；動態需求感知；服務流行度

0 引言

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

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

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

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

本文旨在根據動態服務需求為每個邊緣服務器設計服務部署策略，以使用戶的交互延遲最小化；此外，還考慮了邊緣服務器的資源限制以及如何平衡邊緣服務器的請求負載。

本文主要工作總結如下：

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

2）考慮了動態用戶需求對服務流行度及邊緣服務器負載的影響，提出了一種動態調整算法來更新現有服務，保持整個邊緣網絡的穩定性。

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

1 問題描述與建模

本章詳細闡述服務部署問題和系統模型。

圖1 邊緣服務器上的服務部署示例

2 動態服務部署策略

對于第一章中描述的問題，本文提出了一種動態需求感知和負載均衡（Dynamic Requirement Awareness and Load Balance， DRLB）的策略來動態更新服務。該策略包括初始服務部署和動態調整兩個階段。

2.1 初始服務部署階段

在部署服務之前，一般需花費巨大的成本收集所有邊緣服務器的狀態。為了使服務部署和動態調整更容易，將邊緣服務器劃分為多個集群。

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

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

算法1 集群劃分算法。

算法2 服務部署算法。

6） 根據式（3）～（5）計算約束條件；

7） If 不滿足約束條件 then

8） 按照排序次序補選；

9） End If

10） End For

2.2 動態服務調整階段

算法3 服務動態更新算法。

輸出 該集群調整后的服務部署方案。

4） End For

9） End If

12） End If

15） End If

16） End For

17） End For

3 仿真與分析

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

表1 實驗參數設置

如第2章所述，問題的規模主要與集群、服務和邊緣服務器的數量。本文參考了文獻［6］中的實驗方法來測試這三個參數對本文策略DRLB性能的影響。考慮了三組參數，如表2所示。在每組參數中，其中一個參數是變化的，另外兩個參數保持不變。所有實驗均重復10次，使用平均值作為結果。

表2 變量設置

圖2 集群數量對平均交互延遲的影響

圖3 集群數量對負載均衡的影響

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

不同數量的邊緣服務器對平均交互延遲的影響如圖6所示，可以看出所有方法的平均交互延遲隨著邊緣服務器數量的增加而增加，這是因為邊緣服務器的數量對優化空間有影響，會增加問題解決的復雜性。邊緣服務器數量對負載均衡的影響如圖7所示，可以看出本文策略DRLB的服務請求量的方差更小，明顯優于其他基準算法，圖5中也體現了這一點。綜上所述，可以得出結論，本文策略能夠解決不同規模的服務部署問題，具有良好的可擴展性；此外，該策略的動態調整算法還具有提高邊緣服務器負載均衡的能力。。

圖4 服務數量對平均交互延遲的影響

圖5 服務數量對負載均衡的影響

圖6 邊緣服務器數量對平均交互延遲的影響

圖7 邊緣服務器數量對負載均衡的影響

4 結語

本文重點研究了邊緣計算系統中的服務部署和更新機制，提出了資源受限的動態服務部署策略DRLB。借助服務流行度來動態調整服務的部署，本文策略可以實現更穩定的負載均衡。實驗結果表明，與傳統方法相比，本文策略可以實現更低的平均交互延遲。未來將會在更實際的場景中考慮這個問題，比如預測用戶的路徑以及邊緣之間的服務協作，以進一步提高部署質量。

[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] 陳玉平，劉波，林偉偉，等. 云邊協同綜述［J］. 計算機科學， 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。

國家自然科學基金資助項目（61303029）；三亞崖州灣科技城管理局重大科技項目（SKJC?KJ?2019KY02）。

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