A Modified Differential Evolution With Heuristic Algorithm for Nonconvex Optimization on Sensor Network Localization

Sensor network localization based on connectivity can be modeled as a nonconvex optimization problem. However, current models only consider the convex constraints, i.e., connections among the nodes. The proposed method considers not only the connection constraints but the disconnection constraints, which are nonconvex in nature, as well. It is argued that the connectivity-based localization problem should be represented as an optimization problem with both convex and nonconvex constraints. In this paper, an algorithm combining a modified differential evolution (DE) algorithm and heuristics is presented for the situation in which the communication range value is unknown. The developed algorithm has a new crossover procedure, with refined procedures to produce a new generation of individuals/candidates. A “single node treatment” procedure is also designed for the search procedure to formulate a new set of coordinate locations to jump out from the local minimum. The final solution can reach the most suitable configuration of the unknown nodes (nodes without knowing their location) because all the information on the constraints has been used. Simulation results have shown that better solutions can be obtained when compared with other convex-constraint methods. The proposed method also gets better results than other general nonconvex optimization methods.

I. Introduction

Position estimation is necessary in many applications such as remote patient monitoring, package and person tracking, environment monitoring, and wildlife habitat monitoring. In these systems, there could be hundreds of low-cost sensor nodes, which can take some simple measurements. Based on either the distances or the connectivity among the nodes, we would like to estimate the location of these nodes in the sensor network. It is necessary to accurately localize the sensors to measure data, which is geographically meaningful.