Power assignment for k-connectivity in wireless ad hoc networks

Abstract — The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k ≥ 3, a(k +12H (k))-approximation algorithm for k (2k − 1) ≤ n where n is the network size, a (k +2⌈(k +1)/2⌉)-approximation algorithm for 2 ≤ k ≤ 7, a6-approximation algorithm for k =3, and a 9-approximation algorithm for k =4. Index Terms — k-connectivity, power assignment, wireless ad hoc sensor networks I