一种适用于(p+m)-中点问题的服务设施放置算法
|
摘要
针对雾计算应用中服务设施放置问题,将其建模成(p+m)-中点问题,提出了一种基于贪婪策略与禁忌搜索策略相结合的启发式服务设施放置算法.提出的算法适用于一般拓扑、任意需求分布的网络.性能分析结果表明,提出的算法是多项式时间的,在当扩展服务节点数和请求节点数相等时能够达到性能上的最优.仿真结果验证了新算法的有效性.
This service facility placement problem is investigated,which appears representatively in fog computing for the cost minimization and the optimal resource utilization. After the problem being modelled as a( p + m)-median problem,a novel heuristic placement algorithm is proposed that combines the greedy and tabu-search strategies. The proposed algorithm can be used in networks with arbitrary topology and random demand distribution. Analysis results show that it is polynomial in time complexity and can reach the optimal performance in the case that the number of the extended service nodes in the network is equal to that of the request nodes. Finally,simulations verify the advantages above.
This service facility placement problem is investigated,which appears representatively in fog computing for the cost minimization and the optimal resource utilization. After the problem being modelled as a( p + m)-median problem,a novel heuristic placement algorithm is proposed that combines the greedy and tabu-search strategies. The proposed algorithm can be used in networks with arbitrary topology and random demand distribution. Analysis results show that it is polynomial in time complexity and can reach the optimal performance in the case that the number of the extended service nodes in the network is equal to that of the request nodes. Finally,simulations verify the advantages above.
引文
[1]田辉,范绍帅,吕昕晨,等.面向5G需求的移动边缘计算[J].北京邮电大学学报,2017,40(2):1-10.Tian H,Fan S,Lv X,et al. Mobile edge computing for5G requirements[J]. Journal of Beijing University of Posts and Telecommunications,2017,40(2):1-10.
[2]Gao L,Luan T H,Yu S,et al. FogRoute:DTN-based data dissemination model in fog computing[J]. IEEE Internet of Things Journal,2017,4(1):225-235.
[3]Kariv O,Hakimi S L. An algorithmic approach to network location problems. I:the p-centers[J]. Siam Journal on Applied Mathematics,1979,37(3):513-538.
[4]Kariv O,Hakimi S L. An algorithmic approach to network location problems. II:the p-medians[J]. Siam Journal on Applied Mathematics,1979,37(3):539-560.
[5]Tamir A. An O(pn 2)algorithm for the p-median and related problems on tree graphs[J]. Operations Research Letters,1996,19(2):59-64.
[6]Rolland E,Schilling D A,Current J R. An efficient tabu search procedure for the p-median problem[J]. European Journal of Operational Research,1997,96(2):329-342.
[7]Charikar M,Guha S,Shmoys D B. A constant-factor approximation algorithm for the k-median problem[J].Journal of Algorithms,2003,65(1):129-149.
[8]Lorena L A N,Furtado J C. Constructive genetic algorithm for clustering problems[J]. Evolutionary Computation,2001,9(3):309-327.
[2]Gao L,Luan T H,Yu S,et al. FogRoute:DTN-based data dissemination model in fog computing[J]. IEEE Internet of Things Journal,2017,4(1):225-235.
[3]Kariv O,Hakimi S L. An algorithmic approach to network location problems. I:the p-centers[J]. Siam Journal on Applied Mathematics,1979,37(3):513-538.
[4]Kariv O,Hakimi S L. An algorithmic approach to network location problems. II:the p-medians[J]. Siam Journal on Applied Mathematics,1979,37(3):539-560.
[5]Tamir A. An O(pn 2)algorithm for the p-median and related problems on tree graphs[J]. Operations Research Letters,1996,19(2):59-64.
[6]Rolland E,Schilling D A,Current J R. An efficient tabu search procedure for the p-median problem[J]. European Journal of Operational Research,1997,96(2):329-342.
[7]Charikar M,Guha S,Shmoys D B. A constant-factor approximation algorithm for the k-median problem[J].Journal of Algorithms,2003,65(1):129-149.
[8]Lorena L A N,Furtado J C. Constructive genetic algorithm for clustering problems[J]. Evolutionary Computation,2001,9(3):309-327.