摘要：在无线内容分发网络中,为减轻骨干网络的传输压力,可将网络拓扑结构构建为以基站和Wi-Fi接入点为根的若干棵最小生成树,并对生成树的深度和每个节点的度数进行约束。这种深度和度数约束的最小生成树问题是一个NP完全问题。针对该问题,首先提出能够生成优质近似解的启发式算法,该算法在不违反深度以及度数约束的情况下构建生成树,算法思想为在服务性节点相连的边中选择与当前生成树相连且权值最小的边加入生成树。然后在生成初始近似解的基础上采用定制的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化。实验结果表明,在给定的约束条件下,禁忌搜索算法求得的解优于现有的遗传算法,在深度约束为4以及度数约束为10的条件下,解的改进幅度可达18.5%,所提算法的运行速度比遗传算法提高了10倍。

关键词：无线内容分发网络 生成树 启发式算法 禁忌搜索算法 模拟退火算法 

单位：广东工业大学计算机学院; 广东广州510006; 桂林电子科技大学广西高校图像图形智能处理重点实验室; 广西桂林541004