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

• 作者: 武继刚 缪裕青 郑露露 黄洪涛
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 无线内容分发网络 生成树 启发式算法 禁忌搜索算法 模拟退火算法
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 高性能计算
• 页码范围: 2133-2140
• 页数: 8页
• 分类号: TP393.022
• 字数: 5878字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2018.12.006

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	缪裕青	桂林电子科技大学广西高校图像图形智能处理重点实验室	31	140	8.0	10.0
2	武继刚	广东工业大学计算机学院	29	46	3.0	4.0
3	黄洪涛	广东工业大学计算机学院	1	3	1.0	1.0
4	郑露露	广东工业大学计算机学院	2	4	1.0	2.0