INFORMATION CHANGE THE WORLD

International Journal of Information Engineering and Electronic Business(IJIEEB)

ISSN: 2074-9023 (Print), ISSN: 2074-9031 (Online)

Published By: MECS Press

IJIEEB Vol.1, No.1, Oct. 2009

Reducing Multicast Redundancy and Latency in Multi-Interface Multi-Channel Wireless Mesh Networks

Full Text (PDF, 333KB), PP.41-49


Views:71   Downloads:1

Author(s)

Kai Han,Yang Liu

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", IJIEEB, vol.1, no.1, pp.41-49, 2009.

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.