Multichoice Games for Optimizing Task Assignment in Edge Computing
Yongbo Li, Tian Lan · 2018
Mobile Edge Computing has quickly become a promising paradigm to meet the ever-increasing data-processing demands imposed by emerging applications, by shifting computations to network edge. In this paper, we address two problems unique in edge computing: How to determine the execution cost contributed by each computing task in an edge environment, and how to distributively assign tasks to heterogeneous edge nodes to minimize total execution cost? Cost accounting is a long-standing hard problem for multiprocessing systems, e.g., when edge nodes jointly process tasks from different users. We propose a new framework that models the problem as a multichoice cooperative game, and use Shapley Value for cost accounting. The result enables us to decouple the cost of concurrent task executions and to efficiently solve the task assignment problem through a distributive Hungarian algorithm. To evaluate the performance, we conduct hybrid experiments by collecting trace from a fully implemented edge testbed and generating cost profiles to drive extensive simulations. Numerical results show that our solution guided by multichoice Shapley value is able to consistently outperform two baseline strategies using oblivious cost accounting policies, for task assignment in heterogeneous edge networks. Our solution's advantages become more significant for edge networks with higher levels of heterogeneity (either computation- or network-wise).