Optimal Cluster-head Deployment in Wireless Sensor Networks with Redundant Link Requirements

In this paper, a Wireless Sensor Network (WSN) deployment problem is posed: in a two-level heterogeneous WSN, we need to optimally determine the location of cluster-heads in order to minimize communication power. We require that each sensor node connects to at least p cluster-heads for reliability, and each cluster-head can accept at most q connections. The optimization problem in formulated as a Mixed Integer Nonlinear Programming (MINLP) problem. To overcome the fact that a MINLP solver fails to solve large-scale cases or obtain a global optimum, we propose an iterative decomposition algorithm and use a randomized multi-start technique for global optimization. We also propose an incremental deployment approach and use it to solve the original problem as if the WSN is built incrementally. Numerical results show that the decomposition algorithm is very efficient. While the incremental deployment method is slower in each run, it produces a better solution distribution compared to the pure multi-start approach. Both, however, are capable of solving large-scale problems.