• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

A tree topology generation algorithm for
wireless content distribution networks

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

  1. (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:

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