Heuristic Algorithms for Minimum Bandwidth Consumption Multicast Routing in Wireless Mesh Networks
Pedro M. Ruiz
We study the problem of computing minimal cost multicast trees in multi-hop wireless mesh networks. This problem is known as the Steiner tree problem, and it has been widely studied in fixed networks. However, we show in this paper that in multi-hop wireless networks, a Steiner tree is no an optimal solution to the lowest bandwidth consumption. So, we re-formulate the problem in terms of minimizing the number of transmissions rather than the edge cost. We show that the new problem is also NP-complete and propose heuristics to approximate such trees. Our simulations results show that the proposed heuristics offer a lower cost than Steiner trees over a variety of scenarios and network densities.
|
