Dual power assignment optimization for k-edge connectivity in WSNs
Nhat X. Lam, Trac N. Nguyen, Min Kyung An, D.T. Huynh · 2011
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 how 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) in WSNs. While other studies consider only the special case k=2, our goal is to address the general problem. We prove the NP-completeness of kEDP problem in the geometric case and provide a 2-approximation algorithm using linear programming techniques. To 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 [1].