International Journal of Information Engineering and Electronic Business (IJIEEB)
IJIEEB Vol. 1, No. 1, 8 Oct. 2009
Cover page and Table of Contents: PDF (size: 333KB)
Reducing Multicast Redundancy and Latency in Multi-Interface Multi-Channel Wireless Mesh Networks
Full Text (PDF, 333KB), PP.41-49
Views: 0 Downloads: 0
Index Terms
Multicast, broadcast, wireless mesh networks, multi-interface, multi-channel, interface redundancy, latency
Abstract
In wireless mesh networks, each node can be equipped with multiple network interface cards tuned to different channels. In this paper, we study the problem of collision-free multicast in multi-interface multi-channel wireless mesh networks. The concept of interface redundancy is proposed as a new criterion for the multicast/broadcast redundancy in wireless mesh networks, and we prove that building a multicast/broadcast tree with the minimum interface redundancy is NP-hard. We also prove that the minimum-latency multicasting problem in multi-channel wireless mesh networks is NP-hard. We present two heuristic-based algorithms which jointly reduce the interface redundancy and the multicast latency. Since broadcast can be considered as a special case of multicast, an approximate algorithm for low-redundancy broadcast tree construction is also proposed, which has a constant approximation ratio. Finally, the simulation results prove the effectiveness of our approach.
Cite This Paper
Kai Han, Yang Liu, "Reducing Multicast Redundancy and Latency in Multi-Interface Multi-Channel Wireless Mesh Networks", International Journal of Information Engineering and Electronic Business(IJIEEB), vol.1, no.1, pp.41-49, 2009. DOI:10.5815/ijieeb.2009.01.06
Reference
[1]Akyildiz, I. F., Wang, X. and Wang, W. (2005). Wireless mesh networks: a survey. Computer Networks 47,445-487.
[2]Tang, J., Xue, G. and Zhang, W. (2005). Interference-aware topology control and QoS routing in multi-channel wireless mesh networks, in Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, 68-77.
[3]Yuan, J., Li, Z., Yu, W. and Li, B. (2006). A Cross-Layer Optimization Framework for Multihop Multicast in Wireless Mesh Networks. IEEE Journal on Selected Areas in Communications 24,2092-2103.
[4]Roy, S., Koutsonikolas, D., Das, S. and Hu, Y. C. (2006). High-Throughput Multicast Routing Metrics in Wireless Mesh Networks, in Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, 48.
[5]Zeng, G. W., Ding, B., Xiao, Y. L. and Mutka, M. (2007). Multicast Algorithms for Multi-Channel Wireless Mesh Networks, in Proceedings of the IEEE International Conference on Network Protocols, 1-10.
[6]Han, K., Xiao, M.J., Huang, L.S., and Chen, S.P. (2006). Multicast in Multi-Radio Multi-Channel Wireless Mesh Networks, Journal of University of Science and Technology of China 36,902-905 (research letter)
[7]Gandhi, R., Parthasarathy, S. and Mishra, A. (2003). Minimizing broadcast latency and redundancy in ad hoc networks, in Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, 222-232.
[8]Royer, E. M. and Perkins, C. E. (1999). Multicast operation of the ad-hoc on-demand distance vector routing protocol, in Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking, 207-218.
[9]Garcia-Luna-Aceves, J. J. and Madruga, E. L. (1999). The Core-Assisted Mesh Protocol. IEEE Journal on Selected Areas in Communications 17,1380-1394.
[10]Lee, S. J., Su, W. and Gerla, M. (2002). On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks. Mobile Networks and Applications 7,441-453.
[11]Ruiz, P. M. and Gomez-Skarmeta, A. F. (2004). Mobility-Aware Mesh Construction Algorithm for Low Data-Overhead Multicast Ad hoc Routing. Journal of Communications and Networks 6,240-251.
[12]Huang, S. C. H., Wan, P. J., Jia, X., Du, H. and Shang, W. (2007). Minimum-Latency Broadcast Scheduling in Wireless Ad Hoc Networks, in Proceedings of the 26th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 733-739.
[13]Tseng, Y. C., Ni, S. Y., Chen, Y. S. and Sheu, J. P. (2002). The Broadcast Storm Problem in a Mobile Ad Hoc Network. Wireless Networks 8,153-167.
[14]Du, D. Z. and Pardalos, P. M. (1998). Handbook of Combinatorial Optimization. Springer, Berlin.
[15]Alicherry. M., Bhatia. R., and Li. L. (2005). Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, in Proceedings of the 11th Annual International Conference on Mobile Computing and Networking(MobiCom), 58-72.
[16]Clark. B. N., Colbourn. C. J. and Johnson. D. S. (1990) Unit disk graphs, Discrete Mathematics, 86, 165-177.
[17]Wu. W., Du. H., Jia. X., Li. Y., and Huang. S. C.-H. (2006). Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theoretical Computer Science, 352, 1–7.
[18]Singh. G. and Vellanki. K. (1998). A distributed protocol for constructing multicast trees, in Proceedings of IEEE International Conference on Principles of Distributed Systems, 41–48.
[19]Bauer. F. and Varma. A. (1996). Distributed algorithms for multicast path setup in data networks, IEEE/ACM Transactions on Networking, 4, 181–191.
[20]Han, K., Li Y. L., Guo, Q. Y. and Xiao M.J.(2008). Broadcast Routing and Channel Selection in Multi-Radio Wireless Mesh Networks, in Proceedings of IEEE Wireless Communications and Networking Conference, 2188-2193.