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

计算机工程与科学

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

黄洪涛1，武继刚1，郑露露1，缪裕青2

（1.广东工业大学计算机学院,广东广州 510006;

2.桂林电子科技大学广西高校图像图形智能处理重点实验室，广西桂林 541004）

收稿日期:2018-07-10 修回日期:2018-09-15 出版日期:2018-12-25 发布日期:2018-12-25
基金资助:
国家自然科学基金（61672171,61702115,61702114）;广东省科技研发计划（2017B030305003）;广西高校图像图形智能处理重点实验室项目（GIIP201706）

A tree topology generation algorithm for

wireless content distribution networks

HUANG Hongtao1,WU Jigang1,ZHENG Lulu1,MIAO Yuqing2

（1.School of Computers,Guangdong University of Technology,Guangzhou 510006;

2.Guangxi College and University Key Laboratory of Intelligent Processing

of Computer Images and Graphics,Guilin 541004,China）

Received:2018-07-10 Revised:2018-09-15 Online:2018-12-25 Published:2018-12-25

摘要/Abstract

摘要：

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

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

Abstract:

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 high-quality 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 to 18.5%. The proposed algorithms run 10 times faster than the genetic algorithm.

Key words: wireless content distribution network, spanning trees, heuristic algorithm, tabu search algorithm, simulated annealing algorithm

黄洪涛1，武继刚1，郑露露1，缪裕青2. 面向无线内容分发网络的树形拓扑生成算法[J]. 计算机工程与科学.

HUANG Hongtao1,WU Jigang1,ZHENG Lulu1,MIAO Yuqing2.

A tree topology generation algorithm for

wireless content distribution networks

[J]. Computer Engineering & Science.

[1]	张贝, 闵华松, 张新明. 差分变异和领地搜索的平衡优化算法及其机器人路径规划[J]. 计算机工程与科学, 2023, 45(11): 2078-2090.
[2]	赵炳巍, 贾峰, 曹岩, 孙瑜, 刘一鸿. 基于模拟退火算法的人工势场法路径规划研究[J]. 计算机工程与科学, 2022, 44(04): 746-752.
[3]	袁也, 王刚, 刘晓光, 李雨森. 新型电路版图布局布线算法设计[J]. 计算机工程与科学, 2021, 43(07): 1185-1191.
[4]	欧永东，谢小鹏. 基于改进Census变换的多特性立体匹配算法[J]. 计算机工程与科学, 2020, 42(06): 1030-1036.
[5]	包敏泽, 胡秀婷, 谢玉莹, 蒋波. 基于人工蜂群算法的p-center问题求解算法[J]. 计算机工程与科学, 2020, 42(06): 1127-1133.
[6]	马晗，常安定，陈童，李江杰. 基于文化混合优化算法的旅行商问题求解[J]. 计算机工程与科学, 2019, 41(07): 1273-1278.
[7]	陈秀兰，刘婷. 基于动态奖惩的CDCL SAT求解器分支启发式算法[J]. 计算机工程与科学, 2019, 41(03): 490-497.
[8]	李永伟1,2，刘树安3，郭晋秦1. 普通立体仓库的货位优化模型与算法研究[J]. 计算机工程与科学, 2019, 41(02): 321-327.
[9]	罗裕春,武继刚,史雯隽,贺子楠. 移动云计算中的任务调度与计算迁移算法[J]. 计算机工程与科学, 2018, 40(11): 1915-1924.
[10]	郑露露,武继刚,陈辉. 网络可存活生成树的快速恢复算法[J]. 计算机工程与科学, 2018, 40(11): 1967-1973.
[11]	吉慧，周磊. 面向温度优化的片上网络任务调度方法[J]. 计算机工程与科学, 2018, 40(09): 1527-1533.
[12]	骆伟忠，蔡昭权. 基于核心化技术的点覆盖改进算法[J]. 计算机工程与科学, 2018, 40(08): 1405-1411.
[13]	张耀国1，武继刚2，高任飞1. 具有可控冗余度的虚拟机容错分配算法[J]. 计算机工程与科学, 2017, 39(09): 1617-1626.
[14]	朱康宁，谢政，戴丽. 基于自适应邻域模拟退火算法的非合作对策求解[J]. 计算机工程与科学, 2016, 38(12): 2560-2566.
[15]	汤强，谢明中，罗元盛. 基于多生成树和子网-节点度联合权重的MCDS构造算法[J]. J4, 2016, 38(06): 1103-1110.