Broadcast Routing and Channel Selection in Multi-Radio Wireless Mesh Networks

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 20delta 5+2, where delta is the number of available non-overlapping channels. Finally, the distributed implementation of our algorithm is also presented.