Mobile micro-clouds are promising for enabling performance-critical cloud
applications. However, one challenge therein is the dynamics at the network
edge. In this paper, we study how to place service instances to cope with these
dynamics, where multiple users and service instances coexist in the system. Our
goal is to find the optimal placement (configuration) of instances to minimize
the average cost over time, leveraging the ability of predicting future cost
parameters with known accuracy. We first propose an offline algorithm that
solves for the optimal configuration in a specific look-ahead time-window.
Then, we propose an online approximation algorithm with polynomial
time-complexity to find the placement in real-time whenever an instance
arrives. We analytically show that the online algorithm is $O(1)$-competitive
for a broad family of cost functions. Afterwards, the impact of prediction
errors is considered and a method for finding the optimal look-ahead window
size is proposed, which minimizes an upper bound of the average actual cost.
The effectiveness of the proposed approach is evaluated by simulations with
both synthetic and real-world (San Francisco taxi) user-mobility traces. The
theoretical methodology used in this paper can potentially be applied to a
larger class of dynamic resource allocation problems.

本研究探讨了移动微云网络中服务实例的部署及动态资源分配问题。通过提出离线及在线算法并考虑成本参数的预测和实际误差，发现在线算法具有高效、低成本和预测准确的优势，可应用在更广泛的动态资源分配问题中。