Sampling-based selection-decimation deployment approach for large-scale wireless sensor networks

Large-scale is one of the main tendencies for future wireless sensor networks. This paper considers the problem of deploying (very) large-scale wireless sensor networks in a way that guarantees preferential coverage of a region of interest. As this deployment problem is NP-complete, a weighted sampling scheme matching the requested detection probabilities is adopted in order to reduce the computation workload. The problem is then solved using a practical deployment approach based on a fast selection-decimation process that is easy to implement. The performance of the proposed approach is evaluated through extensive simulations and compared to several other deployment strategies. Results show that the proposed approach fully satisfies the user requirements, outperforms existing algorithms in terms of deployment cost while reducing dramatically the computation time. This reduction, which is scenario-dependent, is at least one order of magnitude but may exceed four orders of magnitude in large-scale scenarios.