A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> In many applications of computer vision, the following problem is encountered. Two point patterns (sets of points) (x/sub i/) and (x/sub i/); i=1, 2, . . ., n are given in m-dimensional space, and the similarity transformation parameters (rotation, translation, and scaling) that give the least mean squared error between these point patterns are needed. Recently, K.S. Arun et al. (1987) and B.K.P. Horn et al. (1987) presented a solution of this problem. Their solution, however, sometimes fails to give a correct rotation matrix and gives a reflection instead when the data is severely corrupted. The proposed theorem is a strict solution of the problem, and it always gives the correct transformation parameters even when the data is corrupted. > <s> BIB001 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> It is often useful to know the geographic positions of nodes in a communications network, but adding GPS receivers or other sophisticated sensors to every node can be expensive. MDS-MAP is a recent localization method based on multidimensional scaling (MDS). It uses connectivity information - who is within communications range of whom - to derive the locations of the nodes in the network, and can take advantage of additional data, such as estimated distances between neighbors or known positions for certain anchor nodes, if they are available. However, MDS-MAP is an inherently centralized algorithm and is therefore of limited utility in many applications. In this paper, we present a new variant of the MDS-MAP method, which we call MDS-MAP(P) standing for MDS-MAP using patches of relative maps, that can be executed in a distributed fashion. Using extensive simulations, we show that the new algorithm not only preserves the good performance of the original method on relatively uniform layouts, but also performs much better than the original on irregularly-shaped networks. The main idea is to build a local map at each node of the immediate vicinity and then merge these maps together to form a global map. This approach works much better for topologies in which the shortest path distance between two nodes does not correspond well to their Euclidean distance. We also discuss an optional refinement step that improves solution quality even further at the expense of additional computation. <s> BIB002 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <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> BIB003 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> This paper describes a distributed, linear-time algorithm for localizing sensor network nodes in the presence of range measurement noise and demonstrates the algorithm on a physical network. We introduce the probabilistic notion of robust quadrilaterals as a way to avoid flip ambiguities that otherwise corrupt localization computations. We formulate the localization problem as a two-dimensional graph realization problem: given a planar graph with approximately known edge lengths, recover the Euclidean position of each vertex up to a global rotation and translation. This formulation is applicable to the localization of sensor networks in which each node can estimate the distance to each of its neighbors, but no absolute position reference such as GPS or fixed anchor nodes is available. We implemented the algorithm on a physical sensor network and empirically assessed its accuracy and performance. Also, in simulation, we demonstrate that the algorithm scales to large networks and handles real-world deployment geometries. Finally, we show how the algorithm supports localization of mobile nodes. <s> BIB004 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> In many applications of wireless sensor networks, location is very important information. Conventional location information comes from manual setting or GPS device. However, manual location setting requires huge cost of human time, and GPS location setting requires expensive device cost and large device size. Furthermore, GPS can not operate in indoor environment. Both approaches are not applicable to localization task of wireless sensor networks. In this paper, an accurate and efficient localization algorithm based on multidimensional scaling (MDS) is proposed in hierarchical network environment. Through localized computation of multidimensional scaling within a cluster, the computation overhead can be distributed to each cluster. On the other hand, MDS-based localization approach requires the estimation of multihop distance. Through restricting estimation of multihop distances within a cluster, the proposed localization algorithm achieves better accuracy and can operate in non-convex network environment. Experimental results reveal that the proposed HMDS localization algorithm outperforms MDSMAP algorithm in terms of accuracy. <s> BIB005 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> A wide range of applications used on wireless sensor networks requires the location information of sensor nodes. Some conventional localization techniques employ GPS or other location-tracking devices installed on sensor nodes. On the other hand, other methods provide location information by taking into account node connectivity only. One example of such methods is a multidimensional scaling-MAP (MDS-MAP), which provides the most accurate location information to date. MDS-MAP, however, has a computational overhead of O(n^3) in a network of n nodes and also it intrinsically generates significant localization accuracy error in an environment with holes. This paper proposes a cluster-based MDS scheme for range-free localization, CMDS for short, which addresses the shortcomings of MDS-MAP and yields higher accuracy in all environments. Simulation results demonstrate that in a sensor network environment with holes, the proposed scheme gives up to 23% improvement in localization accuracy over hierarchical MDS (HMDS), which is an enhanced version of the conventional MDS-MAP. <s> BIB006 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> In wireless sensor networks, three-dimensional 3D localization is very crucial for the applications of target tracking, environmental monitoring and building inspection system, etc. This paper proposed a multi-dimensional positioning based on the method of multidimensional scaling (MDS) and wireless signal strength indicator value to locate the node, and established the dissimilarity matrix by combining the experience attenuation model of RSSI and the shortest path method, reduced the computation complexity of decomposing dissimilarity matrix by a lightweight matrix decomposition algorithm. Improved MDS-RSSI location algorithm for clustering added the idea of reducing the time complexity of the algorithm to enhance the scalability of the algorithm. <s> BIB007 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> This paper proposes a non-measurement multidimensional scaling distributed wireless sensor network localization algorithm. Firstly, clusters are created in the network. Then, each cluster uses the non-measurement multidimensional scaling technique to locate local network and the steepest descent method is used. Finally the least squares estimate is applied to merge the local network coordinate into the coordinates of the entire network. Simulation results indicate this algorithm has high localization accuracy. The localization error is 13%. <s> BIB008 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> We offer a redesigned form of the classical multidimensional scaling (C-MDS) algorithm suitable to handle the localization of multiple sources under line-of-sight (LOS) and non-line-of-sight (NLOS) conditions. To do so we propose to modify the kernel matrix used in the MDS algorithm to allow for both distance and angle information to be processed algebraically (without iteration) and simultaneously. In so doing we also show that the new formulation overcomes two well known limitations of the C-MDS approach, namely the propagation error problem and the possibility to weight the dissimilarities used as measurement information, including, for the case of binary weights, the data erasure problem. Due to the increased size of the proposed edge kernel matrix KE used in the algorithm, the Nystrom approximation is applied to reduce the overall computational complexity to few matrix multiplications. Range only scenarios are also dealt with by approximating the matrix KE. Simulations in range-angle as well as range-only scenarios demonstrate the superiority of our solution under both LOS and NLOS conditions versus semidefinite programming (SDP) formulations of the problem specifically designed to exploit the heterogeneity of the information available. <s> BIB009 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> This study is to propose a multidimensional scaling localization algorithm based on cluster structure [MDS-MAP (C, E)], and used in underwater wireless sensor networks (UWSN) node self-positioning. MDS-MAP (C, E) algorithm: First, underwater wireless sensor network is divided into more than one cluster head of the local network; Secondly, local positioning, using the Euclidean algorithm to calculate the Euclidean distance between each node and its two-hop neighbors, and then take this Euclidean distance for multidimensional scaling in each cluster, instead of the shortest distance from Dijkstra or Floyd algorithm. Simulation results show that: the localization algorithm achieves self-positioning of the whole network in the case of underwater anchor node sparse sensor nodes; the algorithm can obtain higher positioning accuracy than traditional MDS-MAP algorithm, at the same time reducing the computational overhead. <s> BIB010 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> The purpose of this paper is to present a novel localization scheme for sensor networks with large scale deployment with sparse anchor nodes. In most wireless sensor networks, sensed data are location-aware as they are only useful with the location information. However, localization is not a simple task according to the financial cost and technical limitations. The deployment environment also affect the accuracy of the localization. Many solutions have been introduced, but the performance is still not satisfactory or the cost of hardware device and computation complex are too high. In our proposed scheme, fewer anchor nodes are required to reduce the cost. With the help of modified Floyd algorithm and MDS-based Optimal Anchor Nodes Selection algorithm, good performance can be achieved in such sparse anchor situation. The analytical discussions and simulation results both prove these improvements. <s> BIB011 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> With the increasing demand of smart objects in our everyday life promotes an advance generation of communications under the umbrella of the Internet of Things (IoT). For IoT, location-based service is one of the main service, while localization accuracy is a primary problem. Rather than linearizing the nonlinear cost function, we propose a novel subspace algorithm by using the time of arrival (TOA) measurements. Our propose algorithm provide closed-form solution and is validated to be robust even for large measurement noise, as the dimension awareness and eigenstructure of scalar product matrix is used. We evaluate the proposed algorithm by comparing with Cramer-Rao Lower Bound (CRLB) and show its performance through simulation experiments using MATLAB. <s> BIB012 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> Nodes positioning has recently been of great interest in wireless networks owing to its crucial role in many applications. In wireless sensor networks WSNs, the task of localising sensor nodes with unknown position is important for efficient network configuration and operation. This challenge has stimulated research of various localisation algorithms. In this paper we propose robust localisation algorithm for large scale three-dimensional 3D WSNs based on multidimensional scaling MDS. Our approach has two main improvements over classical MDS algorithm. Firstly, it uses heuristic approach for distance matrix calculation, and secondly, it applies Levenberg-Marquardt LM method for absolute map refinement using received signal strength RSS measurements. Furthermore, the performance of the proposed approach is compared to other 3D WSN localisation techniques and it is shown that the proposed approach outperforms other techniques for 3D localisation. <s> BIB013 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> While physical coordinates are useful for IoT and sensor network operations, physical localization is not a viable option for large-scale networks of simple devices in complex or harsh environments. Topology Preserving Maps (TPM) extracted from anchor-based Virtual Coordinates (VCs) are an attractive localization free alternative for physical maps. We present an approach, based on the theory of low-rank matrix completion, to extract TPMs with only partial information about VCs. Evaluation using 2D and 3D networks with random anchors shows that accurate TPMs can be obtained even when up to 40% to 60% of random coordinates are missing. Coordinate generation and communication cost thus may be reduced significantly. TPM generation can now also be based on a different VC system as long as it characterizes each node with distances to a small set of random nodes instead of a global set of anchors. <s> BIB014 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> Nodes localization in Wireless Sensor Networks (WSN) has arisen as a very challenging problem in the research community. Most of the applications for WSN are not useful without a priori known nodes positions. One solution to the problem is by adding GPS receivers to each node. Since this is an expensive approach and inapplicable for indoor environments, we need to find an alternative intelligent mechanism for determining nodes location. In this paper, we propose our cluster-based approach of multidimensional scaling (MDS) technique. Our initial experiments show that our algorithm outperforms MDS-MAP[8], particularly for irregular topologies in terms of accuracy. <s> BIB015 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> The demand of smart objects in our life promotes an advanced generation of communications under the umbrella of Internet of Things (IoT). In IoT, location-based service is one of the most promising services, where localization accuracy is a crucial problem. Rather than linearizing a nonlinear cost function used in ordinary localization problem, we propose a novel subspace algorithm by using the time of arrival (TOA) measurements. Our algorithm provides a closed-form solution and is validated to be robust for large measurement noise, as the dimension awareness and eigen structure of scalar product matrix are used. Moreover, we develop a Cramer-Rao Lower Bound (CLB) for 3-dimensional (3D) localization by using the TOA measurements. We evaluate the proposed algorithm by comparing with CLB and show its performance through simulation experiments. <s> BIB016 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> C. Semi-Centralized MDS Based Localization <s> Creating an efficient localization algorithm for Internet of Things (IoT) and heterogeneous networks has been of the greatest challenges in the recent years for the researchers and industries. There has been significant efforts to increase the estimation accuracy and computational speed of localization algorithms either by improving the already existing ones or proposing new solutions. In this paper we propose a new algorithm, namely Cholesky MDS (CMDS) which is based on Multidimensional Scaling (MDS) and Super MDS (SMDS). Likewise SMDS, the proposed algorithm allows angle and distance information to be used simultaneously for an accurate position estimation while offering a computational speed of up to 8 times faster. This makes CMDS one of the best candidates for real-time and power-constrained scenarios especially those involving large networks and fast moving targets. <s> BIB017
The centralized MDS based localization methods generally have high computational complexity and large localization error for irregular networks. Therefore, many researchers were encouraged to develop semi-centralized (or clustered) MDS methods for WSNs-IoT localization BIB005 , BIB006 , BIB009 , BIB002 BIB003 BIB004 BIB008 BIB010 BIB007 BIB011 BIB013 BIB014 BIB015 BIB017 . Semi-centralized MDS methods are more robust and accurate with low complexity. In recent past the authors in BIB012 , BIB016 proposed three dimensional semi-centralized MDS based localization methods for IoT networks. In semi-centralized MDS based methods, initially, all the nodes in the network are divided into clusters. Different clustering algorithms such as k-means clustering, density-based clustering, or fuzzy clustering can be used for a clustering purpose. Once the network is clustered, the next step is to select a cluster head for each cluster by using various cluster head selection methods such as minimum energy consumption, large number of neighbors etc. Semi-centralized MDS based localization methods consist of following steps: • Construction of Local Distance Affinity Matrix: In this step, the cluster head of each cluster computes the shortest path distances for its every member in the cluster and defines a local distance affinity matrix. The local distance affinity matrix for cluster i is defined as , where c is the total number of nodes in cluster i. D i can be written in matrix form as where i = 1, 2, 3, . . . , c and j = 1, 2, 3, . . . , c are the number of nodes in cluster i. • Construction of Local Map for Each Cluster: MDS is applied to the local distance affinity matrix D i to get the relative position estimate of each node in cluster i. Like the centralized MDS, the first step is to double center the local distance affinity matrix, i.e., But the size of the double centered matrix is c × c instead of n × n. The local doublecentered matrix C i is then decomposed by Eigen value decomposition as where e represents the eigen-vectors and λ are the eigenvalues. Finally, the relative two dimensional positions of the nodes in cluster i are determined from the two largest eigenvalues of λ and two largest eigen-vectors in e, i.e., • Stitching of the Local Maps: In this step, the cluster heads communicate with each other to merge their local maps. The local maps are stitched together with the help of inter-cluster nodes, where each inter-cluster node belongs to at least two neighboring clusters. Two neighboring clusters should have at least three inter-cluster nodes for stitching BIB001 . The inter-cluster nodes have different relative coordinates in each cluster, therefore the position estimates of nodes in cluster i after stitching are given aŝ where A i is the alignment matrix and α i is the reconstruction error. For a fixedP i , A i =P iP + i that minimizes the reconstruction error α i 2 , whereP + i is the Moore-Penrose inverse ofP i , therefore The total reconstruction error for all the clusters is given as Let S i is a selection matrix which selects the estimated local positions for the nodes in cluster i, such that the Hadamard product ofPR i =P i and Decomposing RΘΘ T R T by Eigen value decomposition yields where T is the transpose operator. The global relative coordinates are extracted from the two largest eigenvectors Λ and the corresponding two eigenvalues λ for two-dimensional localization, i.e., As the relative global position estimates obtained by (20) are not absolute, it is required to transform these relative position estimates into absolute positions. Linear transformations such as Procrustes analysis, Helmert transformation, or principal coordinate analysis can be used to reach the global absolute position estimates.