Energy Efficient Broadcast in Distributed Ad Hoc Wireless Networks
Subhas Kumar Ghosh · 2008
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 of2Hn-1with time complexity O(n ldrlambda(G)), where Hnis the nth 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 (ln(n-1) + 1t), 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(n-1) + 2.5 - approximation algorithm for strong connectivity with asymmetric power requirements.