loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2008 11th IEEE International Conference on Computational Science and Engineering
Energy Efficient Broadcast in Distributed Ad Hoc Wireless Networks
July 16-July 18
ISBN: 978-0-7695-3193-9
In this work we present algorithms for Minimum Energy Consumption Broadcast Subgraph (MECBS) problem. First, we focus on designing distributed algorithms for MECBS. To our knowledge, this is the first work looking into the aspects of designing a distributed approximation algorithm for the MECBS. Given input graph G = (V,E) with |V| = n, our algorithm has approximation ratio of $2 H_{n-1}$ with time complexity ${\mathcal O}(n \cdot \Lambda(G))$, where $H_{n}$ is the $n$th Harmonic Number, and $\Lambda(G)$ denotes the diameter of the graph $G$. Second, we present an improved sequential approximation algorithm for the MECBS problem with arbitrary asymmetric power requirement having performance ratio $1.5\left(\ln{\left(n-1\right)} + 1\right)$, hence improving all known results for MECBS problem in most general case. Our improvement in MECBS problem also implies that there is a $1.5\ln{\left(n-1\right)} + 2.5$ -- approximation algorithm for strong connectivity with asymmetric power requirements.
Index Terms:
approximation algorithm, distributed algorithm, Minimum Energy Broadcast
Citation:
Subhas Kumar Ghosh, "Energy Efficient Broadcast in Distributed Ad Hoc Wireless Networks," cse, pp.394-401, 2008 11th IEEE International Conference on Computational Science and Engineering, 2008
Usage of this product signifies your acceptance of the Terms of Use.