A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Refinement <s> The recent advances in MEMS, embedded systems and wireless communication technologies are making the realization and deployment of networked wireless microsensors a tangible task. In this paper we study node localization, a component technology that would enhance the effectiveness and capabilities of this new class of networks. The n-hop multilateration primitive presented here, enables ad-hoc deployed sensor nodes to accurately estimate their locations by using known beacon locations that are several hops away and distance measurements to neighboring nodes. To prevent error accumulation in the network, node locations are computed by setting up and solving a global non-linear optimization problem. The solution is presented in two computation models, centralized and a fully distributed approximation of the centralized model. Our simulation results show that using the fully distributed model, resource constrained sensor nodes can collectively solve a large non-linear optimization problem that none of the nodes can solve individually. This approach results in significant savings in computation and communication, that allows fine-grained localization to run on a low cost sensor node we have developed. <s> BIB001 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Refinement <s> Sensor Positioning is a fundamental and crucial issue for sensor network operation and management. In the paper, we first study some situations where most existing sensor positioning methods tend to fail to perform well, an example being when the topology of a sensor network is anisotropic. Then, we explore the idea of using dimensionality reduction techniques to estimate sensors coordinates in two (or three) dimensional space, and we propose a distributed sensor positioning method based on multidimensional scaling technique to deal with these challenging conditions. Multidimensional scaling and coordinate alignment techniques are applied to recover positions of adjacent sensors. The estimated positions of the anchors are compared with their true physical positions and corrected. The positions of other sensors are corrected accordingly. With iterative adjustment, our method can overcome adverse network and terrain conditions, and generate accurate sensor position. We also propose an on demand sensor positioning method based on the above method. <s> BIB002 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Refinement <s> We propose reliable and precise distributed localization algorithms for wireless networks, iterative multidimensional scaling (IT-MDS) and simulated annealing multidimensional scaling (SA-MDS). We use only radio communication constraints to infer a node's distances, and uniquely combine a multidimensional scaling algorithm (MDS) with a lateration algorithm. We analytically establish the upperbound on the estimation error. The proposed techniques can estimate all nodes' positions, even with limited and imprecise network knowledge. Analysis and test runs show that the proposed methods are independent of the topology randomness and the range measurement errors. We attempt to bound the localization imprecision. Simulation results yield an average estimation error of about 25% of radio transmission range. The highest estimation error observed is 40% radio range for most networks. <s> BIB003
The purpose of the refinement process is to adjust the estimated position in the previous step. When one normal node estimates its own position, it informs its neighbors about its possible position. According to the radio communication constraints in section 2.2, the neighboring nodes can adjust their estimates accordingly. After a number of iterations, the position updating becomes small. Then the nodes can stop the refinement procedure and report the final position. Convex positioning algorithm applies a central unit to process the position constraints for the whole network. Because of the global information, the refinement is obtained by simply executing the same algorithms multiple times. For each iteration procedure, a possible smaller rectangle bounding-box (see section 2.4.2) will be defined for each normal node. The narrowing procedure continues until predetermined precision is achieved. Probability positioning algorithm measures the signal strength multiple times and uses a weighted formula to obtain the probability parameters (mean and standard deviation) corresponding to that position. During each advertisement phase, each node estimates and triggers an update only if the new prediction area is considerably smaller than the current. Ad-hoc positioning algorithm extends the capabilities of GPS to non-GPS enabled nodes in a hop-by-hop fashion for an ad hoc network. The GPS triangulation method is executed iteratively upon each new advertised estimation, and the iteration process stops when the corrections are below a chosen threshold. N-hop positioning algorithm groups all normal nodes into computation subtree, and executes multilateration process at each node in a consistent sequence. The computation subtree is a small set of collaborative nodes in which all nodes are over-constrained and each of them can only have one possible position. A simple example is one normal node connecting with three (or more) anchors (not collinear), in which the position of the normal node can be uniquely determined. The computation sequence does not need to be specified but it needs to be consistent for all iterations. This assures the order of the position updating sequence, and minimizes the local oscillation (local convergence without complying global optimization) and erroneous estimates BIB001 . Robust positioning algorithm includes a confidence metric with each node's position. The confidence weights are used to solve a weighted least-squares equation wAx=wb instead of Ax=b, where w is the vector of confidence weights, with anchors have highest confidence of 1, and normal nodes have lower confidence associate with their observation conditions. Also, this algorithm detects ill-connected groups, i.e. the number of neighbors is less than 3 for a 2-dimensional space with the idea similar to the concept of computation subtree in N-hop algorithm. The refinement continues until desired precision is obtained. Classical multidimensional scaling algorithm in BIB002 doesn't specifically address a refinement procedure. However, it also includes an iterative mechanism. To estimate all nodes position, it uses the newly updated positions from previous estimated nodes for the next iteration round. The advanced MDS algorithms (SA-MDS and IT-MDS) presented in BIB003 improve the classical MDS. Both algorithms can provide better estimations even with approximate pair-wise distance between nodes along the routing path. As with many other algorithms, the refinement procedure of advanced MDS also relies on the neighbors' information. However, the authors found that the refinement may deviate a lot from the estimates by localization algorithms (IT/SA-MDS). The reason is that the refinement procedure is based on the imprecise estimates. Consequently, BIB003 associates a confidence factor with the refinement procedure, such that each refinement only updates, according to the confidence, specific values to the real positions. The GGO algorithm uses on-hop neighborhood information to reduce the estimated regions. This is achieved by advertising the region estimates to all the intermediate neighbors. Upon getting information from its neighbor, each normal node adjusts its position by intersecting the previous estimates with neighborhood constraints. This process is repeated until no further improvement can be achieved. The APIT method does not specifically provide a refinement procedure. However, it gives one approach to obtain high redundancy anchor information. The mechanism uses a single moving anchor to send out location information at various positions in network. By aggregating an additional set of triangles, a possible minimal region will be obtained. APIT uses the center of the gravity of the final region as the position for the node.