在无线内容分发网络中, 为减轻骨干网络的传输压力, 可将网络拓扑结构构建为以基站和Wi-Fi接入点为根的若干棵最小生成树, 并对生成树的深度和每个节点的度数进行约束.这种深度和度数约束的最小生成树问题是一个NP完全问题.针对该问题, 首先提出能够生成优质近似解的启发式算法, 该算法在不违反深度以及度数约束的情况下构建生成树, 算法思想为在服务性节点相连的边中选择与当前生成树相连且权值最小的边加入生成树.然后在生成初始近似解的基础上采用定制的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化.实验结果表明, 在给定的约束条件下, 禁忌搜索算法求得的解优于现有的遗传算法, 在深度约束为4以及度数约束为10的条件下, 解的改进幅度可达18.5％, 所提算法的运行速度比遗传算法提高了10倍.%In the wireless content distribution network, network topology can be constructed as a number of minimum spanning trees rooted at the base station and the Wi-Fi access points, and the depth of spanning trees and the degree of each node are limited to reduce the transmission pressure of the backbone network.This minimum spanning tree problem with depth and degree constraints is an NP-complete problem.Aiming ta this problem, we propose an efficient heuristic algorithm to generate highquality approximate spanning trees.The proposed heuristic algorithm constructs spanning trees by selecting edges with lowest weight and connected to the current spanning trees from the edges connected to service nodes, and adding them to the spanning trees without violating the depth and degree constraints.Then, the approximate solution is further optimized by using the customized tabu search algorithm and simulated annealing algorithm.Experimental results show that the tabu search algorithm is more efficient than existing genetic algorithms under the given constraints.For the cases that the depth constraint is 4 and the degree constraint is 10, the solution of the genetic algorithm can be improved up to18.5％.The proposed algorithms run 10 times faster than the genetic algorithm.
展开▼
