Optimum Selection of Mobile Edge Computing Hosts Based on Extended Balas-Geoffrion Additive Algorithm

Abstract

Multi-access edge computing (MEC) is emerging as a solution to serve offloaded tasks from mobile devices that are computing intensive and have very low latency and high bandwidth requirements. Since compute resources are limited at the MEC hosts, collaboration among hosts could enhance the capabilities of sharing limited resources while minimizing the cost of such hosts. However, the selection of optimal hosts to instantiate the user applications is a major challenge when considering the total service provisioning cost. In this paper, we formulate the MEC hosts selection problem as a binary integer problem with the objective to minimize the total cost of providing the offloading services. We extend the Balas-Geoffrion algorithm to solve the special case of binary programming problems similar to MEC host selection problem. The time complexity of the MEC host selection problem is therefore minimized. We show that our modified algorithm outperforms Balas-Geoffrion algorithm in the number of iterations required to reach the optimal solution. Then we conduct an extensive simulation to show that the overall quality of-service of the MEC system is improved by the MEC hosts collaborations in a limited bandwidth scenario by up to 13%. However, the tradeoff is an increase in the cost of provisioning the services.