Localization Algorithm Based On Distributed MDS In Wireless Sensor Network

In wireless sensor networks, node localization technology based on multi-dimensional scaling can generally be divided into two categories: the classical MDS method and the iterative MDS method. They all use the similar information such as the distance information between the unknown nodes to execute the localization, therefore both belong to localization method based on measured distances. The classical MDS transforms the matrix derived from distances between unknown nodes so as to localize them. It's a simple coarse-grained algorithm but executed by centralized program which would lead a high volume of communication. The iterative MDS in fact is one kind refinement algorithm, and it makes use of the initial position information of nodes to refine the unknown nodes position iteratively, and often can achieve higher precision compared to the classical MDS algorithm, but also would bring a higher amount of computation because of the iterative computation. The distributed multi-dimensional scaling technology is a method which applies the iterative MDS to localization in a distributed form. The distributed weighted-multidimensional scaling (dwMDS) algorithm raised by Jose A. Costa et al. is a better algorithm presently, but its accuracy should be enhanced further. This article studied and studies some kinds of iterative refinement algorithms and applies them to the distributed localization simulation. This is a significance work. The primary works are as follows:1. This paper has been focusing on the types of MDS algorithm and has analyzed the implementation process of classical MDS. About the iterative MDS algorithm, here focuses on the principle of dwMDS algorithm and observes the negative bias effect which is caused by the RSSI model, then discusses a measure of two-step neighbor option which can resists the negative bias effect to some extent. Both the negative bias effect and the affect of the two-step neighbor option to results will be observed in simulation. The two MDS algorithms are simulated in different experimental scenario and different connectivity, and the dwMDS is exampled as one of the iterative MDS and simulated based on the initial location derived from classical MDS. The simulation turns out that the dwMDS algorithm can achieve convergence but the accuracy of the result is not satisfactory compared to the initial location.2. Several classical iterative optimization algorithms have been studied in this paper, such as the steepest descent method, the Newton method and the relaxation iteration method. And the advantages and weaknesses of each algorithm are also analyzed. The simulations of theses algorithms show that the localization algorithm based on relaxation iteration method has a faster localization speed and is more suitable to low connective networks compared to the dwMDS, and the localization algorithm based on the steepest descent method can achieve a higher accuracy than the dwMDS.3. Improvement scheme for the iterative step size of the steepest descent algorithm has been studied. Based on the experiment data, a function between connectivity and step size is constructed through data fitting. And the values of step size in different network environments can be obtained according this function. Though theses values aren't necessarily precise, the simulations show that this scheme can achieve a slightly lower accuracy but with smaller computation than the one based on steepest descent algorithm.