面向无线内容分发网络的树形拓扑生成算法

摘要

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