Daniel Berend

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 (which is NP-Hard) and maximizing the network lifetime. We show that our power assignment algorithm from [9] achieves a bicriteria approximation of (O(k). O(k √logn k√α(n))) with high probability for the minimal total cost/maximal network (respectively) lifetime problem in the plane in the case of arbitrary battery charges. The same algorithm is an (O(k), O(l))-approximation in the case of uniform batteries. To the best of our knowledge, this is the first attempt to provide a bicriteria approximation factor for the total power assignment cost and the network lifetime under the k-fault resilience criterion. We provide some results for the linear power assignment algorithm in [30] as well. In addition, we extend the static algorithms above to support dynamic node insert/ delete operations in O(logn) time for the linear case and an expected O(k poly log n) amortized time in the plane.