Dual power assignment optimization and fault tolerance in WSNs

Because of limited battery equipped on each sensor, power consumption is one of the crucial issues in wireless sensor networks (WSNs). It therefore has been the focus of many researchers. An important problem concerning power consumption is to minimize the number of maximum‐power nodes while maintaining a desired network topology. As fault tolerance is vitally important in practice, it is desirable that the constructed network topology is $k$ ‐edge‐connected or $k$ ‐connected. In this paper, we study the dual power assignment problem for $k$ ‐edge connectivity $(kEDP)$ and biconnectivity in WSNs. While other studies consider only the special case $k=2$ , our goal is to address the general problem. In addition to showing the APX‐completeness of biconnectivity problem in the metric model, we also prove the NP‐completeness of the $kEDP$ problem in the geometric case and provide a 2‐approximation algorithm using linear programming techniques. To the best of our knowledge, this approximation ratio is currently the best one. We also introduce a heuristic whose performance is better compared with an approximation algorithm in Wang et al. (J Comb Optim 19:174–183, 2010).