دانلود رایگان مقاله درخت گره اشتاینر مبتنی بر الگوریتم برای ساخت شبکه حسگر بی سیم

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.

6. Conclusion

In the paper, we investigated the weighted-critical-square-grid coverage problem, which is 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. The problem was shown to be NP-complete. In addition, a reduction that transforms the weighted-critical-square-grid coverage problem into the constrained node-weighted Steiner tree problem was proposed. Once a solution to the constrained node-weighted Steiner tree problem is obtained, the solution can be used to select the points that are allowed to deploy sensors for the weighted-critical-square-grid coverage problem. We also showed that the constrained node-weighted Steiner tree problem is NP-complete. In addition, the greedy algorithm (GA), the group-based algorithm (GBA), and the profit-based algorithm (PBA), were proposed for the constrained node-weighted Steiner tree problem. In the simulation, we evaluated the performance with our proposed methods, including Reduction+GA, Reduction+GBA, and Reduction+PBA, in terms of the total weight of the critical grids covered by deployed sensors, where the Reduction+GA, the Reduction+GBA, and the Reduction+PBA denoted the proposed reductions by applying the greedy algorithm, the group-based algorithm, and the profitbased algorithm, respectively. The simulation results showed that the Reduction+PBA had a higher total weight than the others. We also evaluated the performance with the proposed methods in terms of the number of deployed sensors if the number of sensors was large enough to cover all critical grids. The simulation results showed that the Reduction+PBA used fewer sensors than the others for deployment.