• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

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


Abstract

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


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Wen-Lin Yang, Chi-Chou Kao and Cheng-Huang Tung, "Heuristic Algorithms for Constructing Interference-Free and Delay-Constrained Multicast Trees for Wireless Mesh Networks," KSII Transactions on Internet and Information Systems, vol. 5, no. 2, pp. 269-286, 2011. DOI: 10.3837/tiis.2011.02.002

[ACM Style]
Yang, W., Kao, C., and Tung, C. 2011. Heuristic Algorithms for Constructing Interference-Free and Delay-Constrained Multicast Trees for Wireless Mesh Networks. KSII Transactions on Internet and Information Systems, 5, 2, (2011), 269-286. DOI: 10.3837/tiis.2011.02.002