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

详细信息    查看全文

• 作者：Bing-Hong Liu ; ^{bhliu@kuas.edu.tw" class="auth_mail" title="E-mail the corresponding author} ; ^{bhliu@cc.kuas.edu.tw" class="auth_mail" title="E-mail the corresponding author} ; Ngoc-Tu Nguyen ^{kuastu2011@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Van-Trung Pham ^{pvtrung@pdu.edu.vn" class="auth_mail" title="E-mail the corresponding author} ; Wei-Sheng Wang ^{dj3662002@hotmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Wireless sensor network ; Coverage problem ; NP-complete problem ; Sensor deployment
• 刊名：Computer Communications
• 出版年：2016
• 出版时间：1 May 2016
• 年：2016
• 卷：81
• 期：Complete
• 页码：52-60
• 全文大小：1456 K

文摘

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.