Constrained node-weighted Steiner tree based algorithms for constructing a wireless sensor network to cover maximum weighted critical square grids

Bing Hong Liu, Ngoc Tu Nguyen, Van Trung Pham, Wei Sheng Wang

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Deploying minimum sensors to construct a wireless sensor network such that critical areas in a sensing field can be fully covered has received much attention recently. In previous studies, a sensing field is divided into square grids, and the sensors can be deployed only in the center of the grids. However, in reality, it is more practical to deploy sensors in any position in a sensing field. Moreover, the number of sensors may be limited due to a limited budget. This motivates us to study the problem of using limited sensors to construct a wireless sensor network such that the total weight of the covered critical square grids is maximized, termed the weighted-critical-square-grid coverage problem, where the critical grids are weighted by their importance. A reduction, which transforms our problem into a graph problem, termed the constrained node-weighted Steiner tree problem, is proposed and used to solve our problem. In addition, three heuristics, including the greedy algorithm (GA), the group-based algorithm (GBA), and the profit-based algorithm (PBA), are proposed for the constrained node-weighted Steiner tree problem. Simulation results show that the proposed reduction with the PBA provides better performance than the others.

Original languageEnglish (US)
Pages (from-to)52-60
Number of pages9
JournalComputer Communications
Volume81
DOIs
StatePublished - May 1 2016

Bibliographical note

Funding Information:
This work was supported by the Ministry of Science and Technology under Grant MOST 103-2221-E-151-002.

Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.

Keywords

  • Coverage problem
  • NP-complete problem
  • Sensor deployment
  • Wireless sensor network

Fingerprint Dive into the research topics of 'Constrained node-weighted Steiner tree based algorithms for constructing a wireless sensor network to cover maximum weighted critical square grids'. Together they form a unique fingerprint.

Cite this