Academic
Publications
Approximation algorithms for multicast routing in ad hoc wireless networks

Approximation algorithms for multicast routing in ad hoc wireless networks,10.1007/s10878-009-9245-6,Journal of Combinatorial Optimization,Deying Li,Q

Approximation algorithms for multicast routing in ad hoc wireless networks   (Citations: 1)
BibTex | RIS | RefWorks Download
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.
Journal: Journal of Combinatorial Optimization - JCO , vol. 21, no. 3, pp. 293-305, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: