A Demand-Driven Incremental Deployment Strategy for Edge Computing in IoT Network

Edge Computing brings great opportunities to enable the Internet of Things (IoT) vision. But the physical edge server deployment problem still poses a major challenge, which dramatically affects the service ability and service cost of edge computing. Previous work mostly assume that the edge servers are installed at one time. However, due to ever-increasing services, limited budget and evolving techniques, it is more reasonable to deploy edge servers in a gradual fashion. In this paper, we propose a demand-driven incremental deployment strategy (DDID) to resolve this problem. First, a novel demand model is designed to quantify the rigid and non-rigid demand of IoT services for edge computing. Then, we formulate the edge server multi-period deployment problem as a bi-level integer linear program model. The lower-level placement is to minimize the overall deployment cost throughout a planning horizon. We adopt a subgradient optimization with Lagrangian dual to solve this subproblem. In the upper-level allocation, due to the capacity limitation, we adopt a best-effort tuning scheme to prioritize the high demand services with multiple objectives. This subproblem is addressed by an improved MOEA/D (Multi-objective Evolutionary Algorithm Based on Decomposition). Finally, we evaluate the DDID in synthetic topologies. Experimental results show that, compared to the one-time deployment method, it reduces the deployment cost by 18% on average with acceptable service ability loss for edge computing.This work was supported in part by the National Key R&D Program of China under Grant 2018YFB2100300, National Natural Science Foundation of China under Grants 61877005, 62172051, and 61772085, and in part BUPT Excellent Ph.D. Students Foundation under Grant CX2019228