Dual power assignment optimization and fault tolerance in WSNs

Nhat X. Lam, Trac N. Nguyen, Min Kyung An and Dung T. Huynh ()
Additional contact information
Nhat X. Lam: University of Texas at Dallas
Trac N. Nguyen: University of Texas at Dallas
Min Kyung An: University of Texas at Dallas
Dung T. Huynh: University of Texas at Dallas

Journal of Combinatorial Optimization, 2015, vol. 30, issue 1, No 10, 120-138

Abstract: Abstract 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$$ k -edge-connected or $$k$$ k -connected. In this paper, we study the dual power assignment problem for $$k$$ k -edge connectivity $$(kEDP)$$ ( k E D P ) and biconnectivity in WSNs. While other studies consider only the special case $$k=2$$ 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$$ k E D P 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).

Keywords: NP-completeness; Dual power; Connectivity; Approximation; Heuristic; Wireless sensor network (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9637-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:1:d:10.1007_s10878-013-9637-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9637-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().