Heuristic Algorithms for Constructing Interference-Free and Delay-Constrained Multicast Trees for Wireless Mesh Networks

• Published in: KSII transactions on Internet and information systems 2011-02, Vol.5 (2), p.269-286
• Main Authors: Yang, Wen-Lin, Kao, Chi-Chou, Tung, Cheng-Huang
• Format: Article
• Language: Korean
• Subjects: channel assignment; delay-constrained multicast; multiple radios; orothgonal channels; Wireless mesh networks
• ISSN: 1976-7277; 1976-7277

In this paper, we study a problem that is concerning how to construct a delay-constrained multicast tree on a wireless mesh network (WMN) such that the number of serviced clients is maximized. In order to support high-quality and concurrent interference-free transmission streams, multiple radios are implemented in each mesh node in the WMNs. Instead of only orthogonal channels used for the multicast in the previous works, both orthogonal and partially overlapping channels are considered in this study. As a result, the number of links successfully allocated channels can be expected to be much larger than that of the approaches in which only orthogonal channels are considered. The number of serviced subscribers is then increased dramatically. Hence, the goal of this study is to find interference-free and delay-constrained multicast trees that can lead to the maximal number of serviced subscribers. This problem is referred as the MRDCM problem. Two heuristics, load-based greedy algorithm and load-based MCM algorithm, are developed for constructing multicast trees. Furthermore, two load-based channel assignment procedures are provided to allocate interference-free channels to the multicast trees. A set of experiments is designed to do performance, delay and efficiency comparisons for the multicast trees generated by all the approximation algorithms proposed in this study.