A Heuristic Algorithm for Optimal Facility Placement in Mobile Edge Networks

作者：Jiao, Jiping; Chen, Lingyu^*; Hong, Xuemin; Shi, Jianghong

来源：KSII Transactions on Internet and Information Systems, 2017, 11(7): 3329-3350.

DOI：10.3837/tiis.2017.07.002

• Facility placement
• mobile edge network
• heuristic algorithm

Installing caching and computing facilities in mobile edge networks is a promising solution to cope with the challenging capacity and delay requirements imposed on future mobile communication systems. The problem of optimal facility placement in mobile edge networks has not been fully studied in the literature. This is a non-trivial problem because the mobile edge network has a unidirectional topology, making existing solutions inapplicable. This paper considers the problem of optimal placement of a fixed number of facilities in a mobile edge network with an arbitrary tree topology and an arbitrary demand distribution. A low-complexity sequential algorithm is proposed and proved to be convergent and optimal in some cases. The complexity of the algorithm is shown to be O(H-2 gamma), where H is the height of the tree and gamma is the number of facilities. Simulation results confirm that the proposed algorithm is effective in producing near-optimal solutions.

• 出版日期2017-7-31
• 单位厦门大学