Approximation algorithms for multicast routing in ad hoc wireless networks

Approximation algorithms for multicast routing in ad hoc wireless networks

0.00 Avg rating0 Votes
Article ID: iaor20114160
Volume: 21
Issue: 3
Start Page Number: 293
End Page Number: 305
Publication Date: Apr 2011
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: heuristics, engineering
Abstract:

Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2‐D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is V∖{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP‐hard and it is unlikely to have an approximation algorithm with performance ratio ρlnn(ρ<1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic for broadcast tree problem. Simulations ensure our algorithms are efficient.

Reviews

Required fields are marked *. Your email address will not be published.