含有可分解任務的邊緣運算之動態任務分配

Abstract

由於工業4.0的發展，工廠中運算密集(computation-intensive)且具有延遲敏感(delay-sensitive)特性的運算任務，如影像辨識、預防保養等運用深度學習技術的任務日益增加，需仰賴外部處理器如邊緣伺服器及雲端伺服器執行。此類任務擁有可分解(decomposable)的特性，能夠將任務分解並於不同伺服器處理。為了有效管理任務及運算資源，本研究針對含有可分解任務的邊緣運算系統，提出動態任務分配(allocation)以及任務卸載(offloading)的方法，在提升系統之運算效率的同時降低系統運算成本。 動態任務分配方法對於擁有延遲敏感特性的運算任務來說至關重要。由於運算系統狀態變化快速，若無法根據系統狀態改變任務分配方法，將使運算任務面臨等候時間過長的窘境，最終導致系統之服務品質(Quality of Service, QoS)降低。另外，適當的動態選擇任務處理模式也十分重要。若在運算需求低時使用雲端伺服器，可能會使運算成本增加；在運算需求高時使用邊緣伺服器，則可能延長任務的等候時間，進而導致任務延遲時間增加。 因此，本研究考量一個擁有多個邊緣伺服器及雲端伺服器的運算系統，運用可分解任務的特性，提出一個可以動態決定任務運算模式，以及決定優先被處理任務種類的方法。本研究採用馬可夫決策過程(Markov Decision Process, MDP)建立模型，運用混整數規劃分解模型(Mixed Integer Programming Decomposition, MILPD)分配運算資源，再利用動態規劃概念及反向歸納法(Backward Induction)求得任務分配及卸載方法的最佳解，最小化任務延遲時間所產生之時間成本與運算成本。 透過模擬證實本研究之動態任務分配與卸載方法於不同規模之運算系統中，皆能有效降低任務延遲成本以及運算成本，且優於其他任務分配與卸載方法。

With the development of Industry 4.0, demand on deep-learning related tasks that are computation-intensive and delay-sensitive in the factories such as image recognition and predictive maintenance have been increasing. Thus, external processors such as edge and cloud servers are required to successfully complete the tasks. These tasks possess a decomposable feature which can be divided and processed across different servers. To effectively manage tasks and computational resources, this study proposes methods for dynamic task allocation and offloading in edge computing systems with decomposable tasks, aiming to enhance computational efficiency while reducing system costs. In terms of tasks that are delay-sensitive, dynamic task allocation plays an important role. Due to the rapid changes in system states, failure to adapt task allocation methods can lead to excessive waiting times for computational tasks, ultimately decreasing the system's Quality of Service (QoS). Moreover, appropriately selecting the service placement is also important. If cloud servers are selected when the computational demand is low, the computational costs would increase. On the other hand, selecting edge servers when the computational demand is high would lead to great queuing time for completing tasks, which would also increase task delays. This study includes a computational system with multiple edge and a cloud servers, and proposed a model that dynamically determines the server for task computation by utilizing the decomposable feature, while the types of tasks that are required to be prioritized can also be determined. A Markov Decision Process (MDP)-based model is constructed, and the Mixed Integer Linear Programming Decomposition (MILPD) is applied to allocate computational resources. The optimal solutions for task allocation and offloading are obtained through dynamic programming and backward induction, minimizing the combined time costs resulting from task delays and computational costs. With simulations demonstrated in this work to show that he proposed dynamic task allocation and offloading methods effectively reduce the overall task delay, furthermore, computational costs in systems can also be reduced under different scales of computation systems. The results also outperform other task allocation and offloading methods.