DocumentCode
761373
Title
Constructing a Wireless Sensor Network to Fully Cover Critical Grids by Deploying Minimum Sensors on Grid Points Is NP-Complete
Author
Ke, Wei-Chieh ; Liu, Bing-Hong ; Tsai, Ming-Jer
Author_Institution
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu
Volume
56
Issue
5
fYear
2007
fDate
5/1/2007 12:00:00 AM
Firstpage
710
Lastpage
715
Abstract
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
Keywords
computational complexity; geometry; wireless sensor networks; NP-complete problem; critical-grid coverage problem; grid points; weighted-grid coverage problem; wireless sensor network; Base stations; Biosensors; Chemical and biological sensors; Chemical technology; Communication system control; Fires; Sensor phenomena and characterization; Weapons; Wireless communication; Wireless sensor networks; NP-Complete; coverage problem.; wireless sensor networks;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/TC.2007.1019
Filename
4141243
Link To Document