Constructing a wireless sensor network to fully cover critical grids by deploying minimum sensors on grid points is NP-Complete

Wei-Chieh Ke; Bing-Hong Liu; Ming-Jer Tsai

doi:10.1109/TC.2007.1019

Back

Constructing a wireless sensor network to fully cover critical grids by deploying minimum sensors on grid points is NP-Complete

Journal article

Peer reviewed

Constructing a wireless sensor network to fully cover critical grids by deploying minimum sensors on grid points is NP-Complete

Wei-Chieh Ke, Bing-Hong Liu and Ming-Jer Tsai

IEEE Transactions on Computers, Vol.56(5), pp.710-715

05/2007

DOI: https://doi.org/10.1109/TC.2007.1019

Abstract

Coverage problem

NP-Complete

Wireless sensor networks

This paper proves that deploying sensors on grid points to construct a wireless sensor network that fully covers critical grids using minimum sensors (Critical-Grid Coverage Problem) and that fully covers a maximum total weight of grids using a given number of sensors (Weighted-Grid Coverage Problem) are each NP-Complete. © 2007 IEEE.

Metrics

1 Record Views

Details

Title: Constructing a wireless sensor network to fully cover critical grids by deploying minimum sensors on grid points is NP-Complete
Creators - without role: Wei-Chieh Ke - National Tsing Hua University
Bing-Hong Liu - National Tsing Hua University
Ming-Jer Tsai - Department of Computer Science , National Tsing Hua University
Publication Details: IEEE Transactions on Computers, Vol.56(5), pp.710-715
Identifiers: 9957769176306774
Academic Unit: Department of Computer Science, College of Electrical Engineering and Computer Science, National Tsing Hua University
Language: English
Resource Type: Journal article

Constructing a wireless sensor network to fully cover critical grids by deploying minimum sensors on grid points is NP-Complete

Abstract

Related links

Metrics

Details

National Tsing Hua University Social media