Energy and Lifetime Efficient Connectivity in Wireless Ad-Hoc Networks
Daniel Berend, Michael Segal and Hanan Shpungin
The temporary and unfixed physical topology of a wireless ad-hoc network is determined by the distribution of the wireless nodes as well as the transmission power (range) assignment of each node. This paper studies asymmetric power assignments for which the induced communication graph is k-strongly connected, while minimizing the total energy assigned and maximizing the network lifetime.
We show that our power assignment algorithm from [9] achieves a bicriteria approximation ratio of (O(k), O(k log n k √ nϕ(n))) with high probability, where ϕ(n) is any function with limn→∞ϕ(n) = ∞, for the minimal total cost/maximal network lifetime problem in the plane, respectively, in the case of arbitrary battery charges. The same algorithm provides an (O(k),O(1))-approximation in the case of uniform batteries. To the best of our knowledge, this is the first attempt to provide a bicriteria approximation ratio for the total power assignment cost and the network lifetime under the k-fault resilience criterion. In addition, we study the special cases where the nodes are located on a torus or along a line. In the linear case with uniform batteries, we show that our algorithm from [33] obtains an (O(1),1)-approximation. For the toral case, we suggest an assignment which is simultaneously the optimum in terms of each of the criteria.
Keywords: Topology control, power assignment, connectivity, network lifetime.