More Web Proxy on the site http://driver.im/

article

Parameterized complexity of Max-lifetime Target Coverage in wireless sensor networks

Authors:

Jianer ChenAuthors Info & Claims

Theoretical Computer Science, Volume 518

Pages 32 - 41

https://doi.org/10.1016/j.tcs.2013.06.008

Published: 01 January 2014 Publication History

Abstract

Max-lifetime Target Coverage can be viewed as a family of problems where the task is to partition the sensors into groups and assign their time-slots such that the coverage lifetime is maximized while satisfying some coverage requirement. Unfortunately, these problems are NP-hard. To gain insight into the source of the complexity, we initiate a systematic parameterized complexity study of two types of Max-lifetime Target Coverage: Max-min Target Coverage and Max-individual Target Coverage. We first prove that both problems remain NP-hard even in the special cases where each target is covered by at most two sensors or each sensor can cover at most two targets. By contrast, restricting the number of targets reduces the complexity of the considered problems. In other words, they are both fixed parameter tractable (FPT) with respect to the parameter ''number of targets''. Moreover, we extend our studies to the structural parameter ''number k of sensors covering at least two targets''. Positively, both problems are in FPT with respect to k. Finally, we show that Max-min Target Coverage is in FPT with respect to the combined parameters ''number of groups'' and ''number of targets covered by each group''.

References

[1]

Abrams, Z., Goel, A. and Plotkin, S., Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. In: Proc. of 3rd ACM International Symposium on Information Processing in Sensor Networks (IPSN¿04), ACM. pp. 424-432.

[2]

Alon, N., Yuster, R. and Zwick, U., Color-coding. J. ACM. v42. 844-856.

[3]

Assmann, S.F., Johnson, D.S., Kleitman, D.J. and Leung, J.Y.T., On a dual version of the one-dimensional bin packing problem. J. Algorithms. v5. 502-525.

[4]

Cardei, M. and Du, D.Z., Improving wireless sensor network lifetime through power aware organization. Wirel. Netw. v11. 333-340.

[5]

Cardei, M., Thai, M.T., Li, Y. and Wu, W., Energy-efficient target coverage in wireless sensor networks. In: Proc. of 24th Annual Joint Conference of the IEEE Computer and Communications (Infocom¿05), IEEE. pp. 1976-1984.

[6]

Chen, J., Lu, S., Sze, S.H. and Zhang, F., Improved algorithms for path, matching, and packing problems. In: Proc. of 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA¿07), Society for Industrial and Applied Mathematics. pp. 298-307.

[7]

Cheng, M.X. and Gong, X., Maximum lifetime coverage preserving scheduling algorithms in sensor networks. J. Global Optim. v51. 447-462.

[8]

Cheng, M.X., Ruan, L. and Wu, W., Coverage breach problems in bandwidth-constrained sensor networks. ACM Trans. Sens. Netw. v3. 1-23.

[9]

Das, B. and Bharghavan, V., Routing in ad-hoc networks using minimum connected dominating sets. In: Proc. of IEEE International Conference on Communications (ICC¿97), IEEE. pp. 376-380.

[10]

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., Introduction to Algorithms. 2001. The MIT Press.

[11]

Damaschke, P., Multiple hypernode hitting sets and smallest two-cores with targets. J. Comb. Optim. v18. 294-306.

[12]

Deshpande, A., Khuller, S., Malekian, A. and Toossi, M., Energy efficient monitoring in sensor networks. Algorithmica. v59. 94-114.

[13]

Downey, R.G. and Fellows, M.R., Parameterized Complexity. 1999. Springer, New York.

[14]

Garey, M.R., Johnson, D.S. and Stockmeyer, L., Some simplified NP-complete graph problems. Theoret. Comput. Sci. v1. 237-267.

[15]

Guo, J., Hüffner, F. and Niedermeier, R., A structural view on parameterizing problems: distance from triviality. In: Lect. Notes Comput. Sci., vol. 3162. Springer. pp. 162-173.

[16]

Haynes, T.W., Hedetniemi, S.T. and Slater, P.J.B., Fundamentals of Domination in Graphs. 1998. Marcel Dekker Inc.

[17]

Haynes, T.W., Hedetniemi, S.T. and Slater, P.J.B., Domination in Graphs: Advanced Topics. 1998. Marcel Dekker Inc.

[18]

Holyer, I., The NP-completeness of edge-coloring. SIAM J. Comput. v10. 718-720.

[19]

Kannan, R., Minkowski's convex body theorem and integer programming. Math. Oper. Res. v12. 415-440.

[20]

Liu, Z., Wang, B. and Guo, L., A survey on connected dominating set construction algorithm for wireless sensor networks. Inf. Technol. J. v9. 1081-1092.

[21]

Niedermeier, R., Invitation to Fixed-Parameter Algorithms. 2006. Oxford University Press.

[22]

Riege, T. and Rothe, J., Complexity of the exact domatic number problem and of the exact conveyor flow shop problem. Theory Comput. Syst. v39. 635-668.

[23]

Riege, T., Rothe, J., Spakowski, H. and Yamamoto, M., An improved exact algorithm for the domatic number problem. Inform. Process. Lett. v101. 101-106.

[24]

Slijepcevic, S. and Potkonjak, M., Power efficient organization of wireless sensor networks. In: Proc. of IEEE International Conference on Communications (ICC¿01), IEEE. pp. 472-476.

[25]

Telle, J.A., Complexity of domination-type problems in graphs. Nordic J. Comput. v1. 157-171.

Digital Library

[26]

Telle, J.A., Vertex partition problems: characterization, complexity and algorithms on partial k-trees. 1994. Department of Computer and Information Science, University of Oregon, USA.

[27]

Thai, M.T., Wang, F., Du, H. and Jia, X., Coverage problems in wireless sensor networks: designs and analysis. Int. J. Sens. Netw. v3. 191-200.

Digital Library

[28]

Wang, C., Thai, M.T., Li, Y., Wang, F. and Wu, W., Minimum coverage breach and maximum network lifetime in wireless sensor networks. In: Proc. of 50th IEEE Global Telecommunications Conference (Globecom¿07), IEEE. pp. 1-6.

[29]

Wu, J., Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links. IEEE Trans. Parallel Distrib. Syst. v9. 866-881.

[30]

Zorbas, D., Glynos, D., Kotzanikolaou, P. and Douligeris, C., Solving coverage problems in wireless sensor networks using cover sets. Ad Hoc Netw. v8. 400-415.

Cited By

Jagtap AGomathi N. (2020)Energy Efficient Sensor Deployment with TCOV and NCON in Wireless Sensor NetworksInternational Journal of Embedded and Real-Time Communication Systems10.4018/IJERTCS.202001010111:1(1-22)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.4018/IJERTCS.2020010101
(2019)Target coverage algorithm with energy constraint for wireless sensor networksInternational Journal of Information and Communication Technology10.5555/3319273.331928114:2(236-250)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3319273.3319281
Jagtap AGomathi N(2019)Minimizing movement for network connectivity in mobile sensor networks: an adaptive approachCluster Computing10.1007/s10586-017-1660-322:1(1373-1383)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10586-017-1660-3
Show More Cited By

Parameterized complexity of Max-lifetime Target Coverage in wireless sensor networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Parameterized complexity of the k-arc Chinese Postman Problem

In the Mixed Chinese Postman Problem (MCPP), given an edge-weighted mixed graph G (G may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges ...
Prolonging network lifetime under probabilistic target coverage in wireless mobile sensor networks

One of the main operations in wireless sensor networks is the surveillance of a set of events (targets) that occur in the field. In practice, a node monitors an event accurately when it is located closer to it, while the opposite happens when the node ...
Polynomial Turing Compressions for Some Graph Problems Parameterized by Modular-Width
Computing and Combinatorics
Abstract
A polynomial Turing compression (PTC) for a parameterized problem L is a polynomial-time Turing machine that has access to an oracle for a problem $L^{'}$ such that a polynomial in the input parameter bounds each query. Meanwhile, a polynomial (many-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 518, Issue

January, 2014

140 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2013.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 January 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jagtap AGomathi N. (2020)Energy Efficient Sensor Deployment with TCOV and NCON in Wireless Sensor NetworksInternational Journal of Embedded and Real-Time Communication Systems10.4018/IJERTCS.202001010111:1(1-22)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.4018/IJERTCS.2020010101
(2019)Target coverage algorithm with energy constraint for wireless sensor networksInternational Journal of Information and Communication Technology10.5555/3319273.331928114:2(236-250)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3319273.3319281
Jagtap AGomathi N(2019)Minimizing movement for network connectivity in mobile sensor networks: an adaptive approachCluster Computing10.1007/s10586-017-1660-322:1(1373-1383)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10586-017-1660-3
(2018)An optimal algorithm for small group multicast in wireless sensor networksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2018.09288328:3(168-179)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1504/IJAHUC.2018.092883
Liu YLiu ALi YLi ZChoi YSekiya HLi J(2017)APMDPervasive and Mobile Computing10.1016/j.pmcj.2017.03.01241:C(413-435)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1016/j.pmcj.2017.03.012
Liu AHu YChen Z(2016)An energy-efficient mobile target detection scheme with adjustable duty cycles in wireless sensor networksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2016.07811222:4(203-225)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1504/IJAHUC.2016.078112
Yi CYang GDai HLiu LLi N(2016)Switching algorithm with prediction strategy for maximizing lifetime in wireless sensor networkInternational Journal of Distributed Sensor Networks10.1155/2015/5920932015(230-230)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1155/2015/592093
Zhang SLiu XWang JCao JMin G(2015)Accurate Range-Free Localization for Anisotropic Wireless Sensor NetworksACM Transactions on Sensor Networks10.1145/274634311:3(1-28)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2746343
Feng QWang JXu CYao JChen J(2014)Improved parameterized algorithms for minimum link-length rectilinear spanning path problemTheoretical Computer Science10.1016/j.tcs.2014.07.021560:P2(158-171)Online publication date: 4-Dec-2014
https://dl.acm.org/doi/10.1016/j.tcs.2014.07.021

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents