Stability-Oriented Heterogeneous Application Re-Deployment in Mobile Edge Computing

With the rapid development of Mobile Edge Computing (MEC), various heterogeneous applications have being deployed on edge servers in close proximity to end-users for the low-latency responses. In this circumstance, since the resources on edge servers are limited, it is critical to deploy these applications on suitable edge servers. However, due to the heterogeneity of the applications and the mobility of end-users in real MEC circumstances, the requests each edge server received may undergo temporal fluctuations in both views of quantity and type. In other words, it is crucial to re-deploy these heterogeneous applications to match these dynamic circumstances, instead of permanent deployments without adjustments. Nevertheless, frequent re-deployment causes service interruptions and resource wastage, leading to system instability. Existing approaches struggle to handle redeployment effectively in heterogeneous, dynamic, and stability-critical MEC environments. In this paper, we first formulate the Edge Application Re-Deployment problem on the basis of constrained multi-objective optimization and prove its <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {NP}$</tex-math></inline-formula>-hardness. Then we propose an optimal re-deployment approach based on the Integer Programming technique for small-scale edge application re-deployment scenarios. And we also propose a Decompose-Solve-Merge approximation approach which balances the effectiveness and efficiency with a configurable parameter for large-scale scenarios. Extensive experiments on a real-world data set evaluate our novel approaches against four existing representative approaches. Additionally, we perform the ablation experiment to validate the effectiveness of our approaches and explore the impact of configurable parameter on the performance. The results show the superior performance of our approaches on re-deployment in terms of heterogeneous, dynamic, and stability.