運用MILP分解之邊緣運算動態任務分配決策研究

Abstract

因應物聯網快速發展及龐大的運算需求，雲端運算雖為終端設備帶來較佳的運算效能，但其附帶的傳輸延遲已無法滿足使用者的即時運算需求。邊緣運算伺服器容易設置的特性使其可以提供使用者較小傳輸延遲的運算服務。故本研究針對邊緣運算伺服器運算任務分配決策問題進行優化，考量真實運算系統的隨機性及多樣性，最小化邊緣伺服器的運算成本。 首先，針對伺服器內的運算任務分配決策問題，本研究透過混合整數線性規劃拆解模型(Mixed Integer Linear Programming Decomposition ，簡稱MILPD)拆解大型維度問題，再利用動態規劃方法建立應用於多任務多處理器的運算決策模型(Processing Dynamic Decision Model，簡稱PDDM)，對拆解後的子問題進行獨立求解，在保留決策模型動態特性的條件下，使系統可以在合理之運算時間內獲得近似最佳決策，找到為運算系統帶來最小運算成本的動態決策方法。 透過模擬驗證本研究開發之具擴展性動態任務分配決策方法(Dynamic processing task allocation decision approach with scalability，簡稱DPDS)在不同邊緣運算伺服器之效果。實驗結果顯示DPDS能有效降低邊緣伺服器之運算成本與運算時間，尤其在任務型態數量增加時，效果更為顯著。

In response to the rapid development of the IoT and huge computing demands, although cloud computing brings better computing performance to end-users, the accompanying transmission latency can’t meet users' real-time needs. Relatively, edge computing servers are easy to set up, which makes them can have a smaller transmission distance. Therefore, this study optimizes task allocation decision-making of edge computing servers, considering the randomness and diversity of the real computing system, and minimizing the overall computing cost of the server. For computing task allocation problems, this study uses a Mixed-Integer Linear Programming Decomposition model(MILPD) to decompose large-scale dimensional problems and solves the sub-problems by Processing Dynamic Decision Model (PDDM) independently. The model enables the system to obtain near-optimal decisions in a reasonable time with retaining the dynamic characteristics. This study verifies the effect of the Dynamic processing task allocation decision approach with scalability (DPDS) developed in this thesis on different edge computing servers through simulation. The experimental results show that DPDS can effectively reduce the computing cost and cycle time of edge computing servers, especially when the number of task types increases, the effect is more significant.