Decentralized Scheduling and Dynamic Pricing for Edge Computing: A Mean Field Game Approach
Xiong Wang, Jiancheng Ye, John C. S. Lui
Abstract
Edge computing provides a platform facilitating edge servers to contribute to computation offloading while economizing their resources. Traditional offloading solutions are mostly centralized, which are unscalable for large-scale edge computing networks due to complex interactions among many edge servers. Meanwhile, dynamic pricing for an operator is equally, if not more, important to accommodate users’ time-varying demands for computing services. In this paper, we develop a decentralized online optimization framework to jointly minimize the server’s cost of workload scheduling while maximizing the operator’s utility of service pricing. Specifically, we employ the mean field game to model the collective scheduling behavior of all edge servers, thereby enabling optimal decision making only based on the server’s local information. Considering the service price in practice is not adjusted as frequently as the scheduling process, we establish a two-timescale optimization framework, where workload scheduling at a small timescale is tightly embedded into service pricing at a large timescale. Using mean field approximation, we derive the closed-form expression for the minimum scheduling cost, and the approximation error is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O\left ({\frac {1}{\sqrt {M}}}\right)$ </tex-math></inline-formula> which declines as the number of edge servers <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$M$ </tex-math></inline-formula> increases. By characterizing the influence of workload scheduling on dynamic pricing, we transform the complex service utility maximization into a succinct but equivalent problem, and thus we can make use of Lyapunov optimization to determine the optimal price over time. Extensive evaluations validate the effectiveness and optimality of our scheduling and pricing schemes.