適用於協同式邊緣運算之動態任務分配與遷移

Abstract

隨著AIoT和5G技術的迅速發展，大量異質設備的接入帶動密集型運算(computation-intensive)需求急遽增加，如基於機器學習技術的智慧排程與自動化品質檢測中的影像辨識等應用，皆需仰賴外部運算資源協助處理。此類大型且複雜的任務具備模組化與輕量化特性，可轉化為顆粒度更小的微服務應用(microservice)分配至鄰近裝置的邊緣端進行運算，使得運算資源的分配面臨高度動態變化與延遲控制等挑戰。在此背景下，如何有效調度任務並動態配置資源，以兼顧即時性、負載均衡(load balancing)與系統穩定性，已成為影響邊緣運算系統服務品質(Quality of Service, QoS)核心挑戰之一。 其中，考量伺服器異質運算特性將任務分配給最適的邊緣節點為常見的負載平衡策略，可有效降低因局部過載或閒置所造成的系統效能損耗。鑒於各邊緣伺服器之任務到達率具高度隨機性，而隊列過長將導致運算延遲(delay)和吞吐量(throughput)下降，進而影響整體任務執行效率。因此，如何在初始任務分配後，持續維持系統於瞬時高變負載下的運行平衡並最小化系統週期時間(cycle time)，成為系統設計上的關鍵挑戰。在此條件下，任務遷移機制(task migration)被視為實現系統穩定運作的重要手段。 因此，本研究提出一套動態任務分配與遷移(Dynamic Task Allocation and Migration, DTAM)方法，應用於協同式邊緣運算(Cooperative Edge Computing)系統。欲整合以上方法，先透過線性規劃拆解模型(Linear Programming Decomposition, LPD)，將複雜的系統問題拆解為多個子問題，並以馬可夫決策過程(Markov Decision Process, MDP)建立單伺服器多任務分配模型，決定在不同狀態下優先運算的任務種類。之後，透過協調子問題解找出最佳任務分配，並在伺服器閒置時啟動任務遷移機制，伺服器將各自求解每期遷移的任務種類及來源伺服器，以滿足最大化系統產能利用率和任務等候成本最小化等目標。

With the rapid advancement of AIoT and 5G technologies, the emergence of numerous heterogeneous devices has led to a sharp increase in computation-intensive demands. Applications such as intelligent scheduling based on machine learning and image recognition in automated quality inspection rely heavily on external computing resources. These large and complex tasks are often modularized and lightweight, allowing them to be transformed into smaller granularity microservice applications, which can then be distributed to edge devices for processing. However, this introduces challenges in managing highly dynamic resource allocation and delay control. In this context, how to effectively schedule tasks and dynamically allocate resources, while ensuring real-time responsiveness, load balancing, and system stability, has become one of the core challenges affecting the Quality of Service (QoS) in edge computing systems. Among the common strategies for load balancing, balanced task distribution can effectively reduce performance degradation caused by local overloads or idleness. Given the highly stochastic and variable nature of task arrival rates at different edge servers, excessively long queues can lead to increased computational delays and reduced throughput, ultimately affecting overall task execution efficiency. To address this, this study proposes a dynamic task allocation method that integrates task allocation and migration mechanisms within a Cooperative Edge Computing (CEC) System. The approach first applies to a Linear Programming Decomposition (LPD) method to break down complex system problems into multiple single server subproblems. A Markov Decision Process (MDP) is then used to model multi-task allocation for each server, determining the priority of tasks to be processed under different system states. Through coordination of the subproblem solutions, the optimal task allocation is derived. Additionally, when a server is idle, the task migration mechanism is activated, allowing each server to determine which tasks to migrate and from which source servers, with the aim of maximizing system resource utilization and minimizing task waiting costs.