Given a small percentage of nodes whose actual positions are known, the problem of estimating the locations of the remaining nodes of a wireless sensor network has attracted a large interest in the last years. The localization task is based on the noisy estimates of the distances between pairs of nodes in range of each other. The problem is particularly hard when the network connectivity is not sufficiently high, the most attractive case in real applications. In this paper, we propose to solve the localization problem by using a two-objective evolutionary algorithm which takes concurrently into account during the evolutionary process both the localization accuracy and certain topological constraints induced by the network connectivity. The solutions generated by the evolutionary algorithm are therefore refined by a gradient-based technique which further reduces the localization error. The proposed approach is tested with different network configurations and sensor setups, and compared in terms of normalized localization error with a state-of-the-art approach based on a regularized semi-definite programming technique. The results show that, in all the experiments, our approach achieves considerable accuracies, thus manifesting its effectiveness and stability, and outperforms the compared approach.
Solving the Node Localization Problem in WSNs by a Two-objective Evolutionary Algorithm and Gradient Descent
VECCHIO, MASSIMO;
2011-01-01
Abstract
Given a small percentage of nodes whose actual positions are known, the problem of estimating the locations of the remaining nodes of a wireless sensor network has attracted a large interest in the last years. The localization task is based on the noisy estimates of the distances between pairs of nodes in range of each other. The problem is particularly hard when the network connectivity is not sufficiently high, the most attractive case in real applications. In this paper, we propose to solve the localization problem by using a two-objective evolutionary algorithm which takes concurrently into account during the evolutionary process both the localization accuracy and certain topological constraints induced by the network connectivity. The solutions generated by the evolutionary algorithm are therefore refined by a gradient-based technique which further reduces the localization error. The proposed approach is tested with different network configurations and sensor setups, and compared in terms of normalized localization error with a state-of-the-art approach based on a regularized semi-definite programming technique. The results show that, in all the experiments, our approach achieves considerable accuracies, thus manifesting its effectiveness and stability, and outperforms the compared approach.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.