Reducing Multicast Redundancy and Latency in Multi-Interface Multi-Channel Wireless Mesh Networks
Kai Han, Yang Liu · International Journal of Information Engineering and Electronic Business · 2009
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.