User-delay-tolerance-aware edge node placement: optimization for cost minimization
Creators: name: Zhang, Xiaoyu
Publisher: name: RMIT University
Year: 2024
Subjects: classificationCode: 460502
subject: Data mining and knowledge discovery
classificationCode: 460505
subject: Database systems

description: With the prosperity of 5G technologies, Mobile (or Multi-Access) edge computing (MEC) has emerged as the next generation of network architecture. Compared with the previous Mobile Cloud Computing (MCC) architecture, MEC’s decentralising network architecture empowered it amplify user accessible resource and low-latency access. Investigating how to effectively place edge nodes, which are also known as edge servers, has become a trendy research topic and attracted wide attention among researchers. Among existing studies in this research field, most of the works aim to minimize delays experienced by mobile users, which can be achieved by reaching a workload balance between edge nodes, such that the computation capacity from edge nodes can be fully used. However, considering the real use cases, cost-saving, rather than the extremely low network latency, is the prime goal that a service provider (i.e. the telecom companies) pursue when deploying edge nodes to a network as users have their delay tolerance within a threshold rather than pursuing a zero-latency network. Therefore, how to place edge nodes with the minimum cost, including the construction cost for setting up the edge nodes and the server cost for adding server units to the sites, is still worth further study. Although extensive studies have been conducted to find the optimal edge node deployment strategies with the objective of cost minimization, the formulation of such a problem is not close enough to the real-world cases. First, they barely take into account the relationship between the allocation of corresponding computation resources and users’ delay tolerance. To be more specific, instead of achieving a workload balance on each homogeneous capacitated edge node, the edge nodes can have the heterogeneous capacity, depending on the number of users they would serve and the corresponding workload. Second, the delay has not been addressed precisely enough, as most of the existing work only considers the transmission delay while ignoring the computation delay which is decided by the edge node capacity and the workload together. In our work, we define a Cost Minimization in MEC Edge Node Placement (CMMENP) problem to find an optimal edge node deployment strategy such that the cost can be minimized without exceeding users’ delay tolerance. We precisely define the delay with both transmission delay and computation delay. We prove the NP-hardness of this problem and propose a series of solutions, including Cluster based Mixed Integer Programming, Coverage First Search, and Distance-Aware Coverage First Search. Intuitively, the Cluster-based Mixed Integer Programming solves the efficiency issue in the pure MIP solution by sacrificing some degree of accuracy, while the Coverage First Search is an efficiency prioritized solution with Distance-Aware Coverage First Search to further improve its effectiveness without loss of efficiency. In addition, we propose a fine-grained optimization strategy to delicately allocate computation resources to edge nodes at the user service request level, which can remarkably decrease the deployment cost. Comprehensive experiments have been conducted on a large-scale real-world dataset, which demonstrates the competitiveness of our solutions in terms of efficiency, effectiveness and scalability compared with the state-of-art work.