An Effective Algorithm to Find a Cost Minimizing Gateway Deployment for Node-Replaceable Wireless Sensor Networks

In this paper, we present an efficient way to find a gateway deployment for a given sensor network topology. We assume that the expired sensors and gateways can be replaced and the locations of the gateways are chosen among the given sensor nodes. The objective is to find a gateway deployment that minimizes the cost per unit time, which consists of the maintenance and installation costs. The proposed algorithm creates a cost reference and uses it to find the optimal deployment via a divide and conquer algorithm. Comparing all cases is the most reliable way to find the optimal gateway deployment, but this is practically impossible to calculate, since its computation time increases exponentially as the number of nodes increases. The method we propose increases linearly, and so is suitable for large scale networks. Additionally, compared to stochastic algorithms such as the genetic algorithm, this methodology has advantages in computational speed and accuracy for a large number of nodes. We also verify our methodology through several numerical experiments.