Research On Localization Algorithms For Wireless Sensor Networks

This paper studied the distributed range-free localization algorithms for WSN (Wireless Sensor Networks).WSN is an ad hoc network composed of many cheap nodes with capability of detections, calculations and wireless communications. Nodes' locations are usually random and unknown. Unfortunately, observation informations without location parameters are mostly useless. Therefore, node self-localization algorithm, especially distributed range-free one leading to low cost and well robustness, is one of WSN's key techniques. There are four major algorithms. DV-Hop has the best performance with precision 33% and traffic twice floods.This paper discussed the localization principle and quantization error, proposed four new algorithms. Simulations by OPNET showed that the precisions are 16-20 percentages higher than DV-Hop's and the traffics are near once flood.The main research results are as follows:1. From analysis of distributed range-free localization algorithms' principle, the paper constructed theoretical models, and derived average connectivity formula and traffic estimate formula.Theoretical research showed that quantization error, which comes from using the radio range to quantize the distance, is the fundamental reason for localization error.2. LSHop has the good integrated performance and may instead of DV-Hop. Equivalent hop counts and AHS (Average Hop Size) can reduce the impact of quantization error. Iterative Positioning strategy promotes precision by redundant informations. Memorial Flood avoids forwarding useless packets. Simulations showed that precision can be increased to approach to 15% and traffic can be decreased to 52.0% of DV-Hop's.3. Cluster can self-exclude unreliable anchors or paths. Trilateral Proportion strategy calculates a pair of conjugate candidate positions from two points'positions and trilateral proportions. Simple Density Clustering strategy defines the number of candidates located within the clustering radius as density and uses centroid of the densest cluster as the node's location. Vote Flood avoids twice floods by the shortest path tree. Precision can be increased to close to 17% with 52.3% traffic of DV-Hop's, from the simulations.4. HopScale has only one communication stage and adapts to the mobile anchors scenarios. Proportion Localization strategy can locate nodes without AHS calculation needed. Neighborhood Flood can keep the same process of a normal flood and obtain the Neighborhood Value. Gradient is a better distance proportion and may be calculated from Neighborhood Value by BinarySearch. Simulation showed that precision can be increased to about 16% with once flood traffic.5. Fuzzy has the highest precision. Using the result of other existing algorithms as the clustering core and the statistics of distribution as the fuzzy membership grades, nodes may localize bypassing clustering. Gradient Flood simplifies the gradient calculation by Fitting Curve and avoids big changes to existing algorithms. Simulation showed that precision can be increased to near 13%, higher than that of all similar algorithms including the others put forward in this paper.