Delay-aware multi-stage edge server placement and task offloading with budget constraint

This paper introduces a novel network planning problem called Multi-stage Edge Server Deployment (M-ESD). The problem calls for a solution that (i) adds fixed edge servers to an existing Multi-access Edge Computing (MEC) network incrementally over multiple stages, e.g., in years, and (ii) optimizes the offloading of tasks to installed servers. More specifically, when upgrading a network, at each stage, the problem involves the following constraints: (i) budget (in $), (ii) server deployment cost (in $) and cost depreciation rate (in %), (iii) number of tasks and their increase rate (in %), and (iv) server storage capacity. The goal of M-ESD is to ensure the resulting network maximizes the average number of tasks that meet their delay requirement. This paper presents a Mixed Integer Linear Programming (MILP) model and a heuristic approach called M-ESD/H to solve the M-ESD problem. Simulation results on small networks show that M-ESD/H produces results that are within 13.6% of the optimal MILP solution. Further, it significantly reduces runtime and produces results in less than 0.1 s as compared to MILP, which failed to produce results in some networks after running for over 48 h. For large networks, M-ESD/H is compared against two versions of M-ESD that consider arbitrary budget allocation and/or edge server placement, i.e., M-ESD/A1 and M-ESD/A2. The results show that M-ESD/H outperforms both M-ESD/A1 and M-ESD/A2 across various options with varying numbers of stages, budget allocation, and tasks. • Introduced M-ESD, an NP-hard problem to deploy edge servers in multiple stages. • Proposed a MILP model for the optimal solution of M-ESD. • Designed M-ESD/H, a heuristic solution with 13.6% MILP deviation, 99.9% faster runtime. • Demonstrated that M-ESD/H outperforms two arbitrary methods in task satisfaction.