基于模拟退火与网络单纯形法的通信网络中设施选址优化算法

FACILITY LOCATION OPTIMIZATION ALGORITHM IN COMMUNICATION NETWORK BASED ON SIMULATED ANNEALING AND NETWORK SIMPLEX METHOD

当用户观看视频时,影响其体验的关键在于带宽,然而视频内容服务器的硬件成本与链路带宽租赁费用相对昂贵。因此,如何在满足用户带宽需求的前提下,通过优化服务器部署与带宽租赁方案,从而降低成本成为挑战。提出基于模拟退火与网络单纯形法的优化算法。该算法根据网络结构、链路带宽与租赁费用、服务器的硬件成本与部署成本和用户带宽需求大小,通过模拟退火来迭代优化服务器部署方案,使用网络单纯形法求解部署方案的总成本,通过快速迭代计算出较优方案。仿真结果表明,模拟退火-网络单纯形方案与贪心-Dinic算法相比,能够减少10%以上的总成本,且随着数据规模的扩大,优势更加明显。

When users watch videos,the key to their experience is bandwidth.However,the hardware cost of video content servers and link bandwidth lease costs are relatively expensive.Therefore,how to reduce the cost by optimizing the server deployment and bandwidth leasing scheme under the premise of meeting user bandwidth requirements becomes a challenge.This paper proposes an optimization algorithm based on simulated annealing and network simplex method.According to the network structure,link bandwidth,lease costs,server hardware costs,deployment costs,and user bandwidth requirements,the algorithm iteratively optimized the server deployment scheme through simulated annealing.The network simplex method was used to solve the total cost of the deployment scheme,and a better scheme was calculated by rapid iteration.The simulation results show that the simulated nnnealing-network simplex scheme can reduce the total cost by more than 10%compared with the greedy-dinic algorithm,and the advantages become more obvious with the expansion of the data scale.