Broadcast Routing and Channel Selection in Multi-Radio Wireless Mesh Networks
Kai Han, Yuling Li, Qingyu Guo, Mingjun Xiao · 2008
In multi-radio wireless mesh networks, each node can be equipped with multiple network interface cards tuned to different channels. In this paper, we present a routing and channel selection algorithm for reducing the broadcast redundancy in multi-radio wireless mesh networks. In our approach, the concept of Relaying Channel Redundancy is proposed, which is the sum of the number of different channels selected by each forward node in a broadcast tree. Our aim is to build a broadcast tree with minimum Relaying Channel Redundancy. We prove that building such a broadcast tree is a NP-hard problem, and propose an approximate algorithm for it. Our algorithm has an approximation ratio of at most 20delta5+2, wheredeltais the number of available non-overlapping channels. Finally, the distributed implementation of our algorithm is also presented.