Heuristic methods for solving the sensor network localization problem

Abstract

Location information in sensor networks is necessary for some applications. When this information is not present, the locations of the sensors can be obtained by using the distance measurements among sensor nodes. However, it must be considered that due to the measurement errors and other constraints, there can be a noise in the distance data. Existing methods aim to determine the sensor locations by minimizing the di erence between resulting and real distances. We investigate most frequently used solution methods for di erent problem instances. We classify these methods as the force directed method continued with the conjugate gradient method, the gradient descent method, Sammon's mapping, the Attraction-Repulsion Method and Stochastic Proximity Embedding. As the performance measure, we use stress-based errors and location-based errors. Stress values are used to determine how close the resulting intersensor distances are to the real inter-sensor distances. Location-based errors are used to compare the resulting coordinates obtained by the methods to the real coordinates. Prior to computing the location-based errors, we perform the Procrustes Analysis to make a more qualiffed comparison. In our experimental setting, we also consider two extensions. In the first one, there are missing entries in the actual distance matrix. The second extension involves the case where locations of some sensors are already known. We find out that the Attraction-Repulsion Method and Stochastic Proximity Embedding bene t more from the known location information of the sensors and are also robust when there are missing entries in the distance matrix.