计算机工程与科学2018，Vol.40Issue(12)：2133-2140,8.DOI:10.3969/j.issn.1007-130X.2018.12.006
面向无线内容分发网络的树形拓扑生成算法
A tree topology generation algorithm for wireless content distribution networks
摘要
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 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.关键词
无线内容分发网络/生成树/启发式算法/禁忌搜索算法/模拟退火算法Key words
wireless content distribution network/spanning trees/heuristic algorithm/tabu search algorithm/simulated annealing algorithm分类
信息技术与安全科学引用本文复制引用
黄洪涛,武继刚,郑露露,缪裕青..面向无线内容分发网络的树形拓扑生成算法[J].计算机工程与科学,2018,40(12):2133-2140,8.基金项目
国家自然科学基金(61672171,61702115,61702114) （61672171,61702115,61702114）
广东省科技研发计划(2017B030305003) （2017B030305003）
广西高校图像图形智能处理重点实验室项目(GIIP201706) （GIIP201706）
