A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. 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. We present an algorithm that uses connectivity information who is within communications range of whom to derive the locations of the nodes in the network. The method can take advantage of additional information, such as estimated distances between neighbors or known positions for certain anchor nodes, if it is available. The algorithm is based on multidimensional scaling, a data analysis technique that takes O(n3) time for a network of n nodes. Through simulation studies, we demonstrate that the algorithm is more robust to measurement error than previous proposals, especially when nodes are positioned relatively uniformly throughout the plane. Furthermore, it can achieve comparable results using many fewer anchor nodes than previous methods, and even yields relative coordinates when no anchor nodes are available. <s> BIB001 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. Centralized MDS Based Localization <s> There are various applications in wireless sensor networks which require knowing the relative or actual position of the sensor nodes. Recently, there have been different localization algorithms proposed in the literature. The algorithms based on classical Multidimensional Scaling (MDS) only require 3 or 4 anchor nodes and can provide higher accuracy than some other schemes. In this paper, we propose and analyze another type of MDS (called ordinal MDS) for localization in wireless sensor networks. Ordinal MDS differs from classical MDS by that it only requires a monotonicity constraint between the shortest path distance and the Euclidean distance for each pair of nodes. We conduct simulation studies under square and C-shaped topologies with different connectivity levels and number of anchors. Results show that ordinal MDS provides a lower position estimation error than classical MDS. <s> BIB002 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. Centralized MDS Based Localization <s> In this paper, we proposed a localization algorithm in wireless sensor networks based on MDS combined with weight. The way of determining weight is according to RSSI which is classified by an experiential method. In the new method, the shortest path matrix could be modified in order to obtain better accuracy. Although without range measuring, it is proved that a better accuracy could be obtained in the new algorithm. <s> BIB003 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. Centralized MDS Based Localization <s> In radio frequency identification (RFID) systems, location information is of great importance to provide location-aware services combined with identification. Conventional RFID systems can only provide coarse localization information. In this paper, we propose a novel approach named MDS-RFID to locate active RFID tags based on multidimensional scaling (MDS), an efficient data analysis technique. The approach has the advantage of fully utilizing the distance information in the network simultaneously, and thus can achieve better localization results than previous multilateration-based methods. The MDS-RFID algorithm first infers the tag-to-reader distances from the received signal strength (RSS). To obtain the distance matrix, the inter-tag distances are estimated using triangular inequalities. Then, classical MDS algorithms can be applied to determine the estimated locations of the tags. An optional refinement step can be added to further improve the accuracy using maximum likelihood estimate (MLE) when enough readers are deployed at the expense of additional computation costs. Simulation results show that the MDS-RFID algorithm can achieve a significant gain in accuracy over the previous localization schemes based on multilateration. <s> BIB004 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. Centralized MDS Based Localization <s> We consider problems of wireless sensor network (WSN) — based localisation as a promising technology for highly accurate positioning solutions. Hence, this paper provides an overview on the results of synthetic data testing of an iterative positioning approach. Position estimation in WSNs is based on distance measuring by means of time-of-flight (TOF) ranging techniques. To employ radio frequency (RF) — based positioning here an iterative classical multidimensional scaling (C-MDS) approach is used for computing position estimates by applying the eigen-decomposition of an Eucledian kernel. The iterative process enables coping with not RF connected sensor nodes. Based on various simulations, we investigate this approach in terms of performance and especially convergence speed. <s> BIB005 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. Centralized MDS Based Localization <s> To improve the feasibility and the convenience of localization methods for wireless sensor networks, a localization algorithm RI-MDS (RSSI-based Iterative-Multidimensional Scaling) is proposed. The RI-MDS method is centralized, and mainly focuses on improving localization accuracy. It collects RSSI vectors as ranging basis, and combines the metric-MDS method and the nonmetric MDS method to accomplish the relative localization. Then it uses the maximum likelihood method in affine transformation to transform the relative coordinates to absolute ones. Our method has no need for additional equipment on the WSN nodes. Simulation and field experiments show that the average localization error and the localization error ratio of the RI-MDS method is relatively lower, thus it is more feasible. <s> BIB006 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. Centralized MDS Based Localization <s> Traditional localization algorithms are vulnerable in multipath environment for passive UHF RFID tag localization. To improve the localization accuracy, this letter proposes a robust algorithm named residual weighted multidimensional scaling (RWMDS) based on the multipath channel model. The RWMDS algorithm first utilizes reader-to-tag distances derived from received signal phase. To obtain the squared distance matrix required in the algorithm, the inter-tag distances are estimated using a few reference tags by establishing the relationship between inter-tag distance and phase information vectors measurement. Based on the modeling of ranging error in multipath environment, the RWMDS lgorithm can be applied to determine the estimated locations of the tags through a few iterations. Simulation results show that the RWMDS algorithm achieves higher localization accuracy than traditional algorithms in multipath environment. <s> BIB007 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. Centralized MDS Based Localization <s> Recently, multidimensional scaling (MDS) algorithms have been verified to be robust for the emitter localization. However, the traditional MDS algorithms are based on single one kind of measurement. In this paper, a novel hybrid MDS localization algorithm based on both angle-of-arrival (AOA) and time-of-arrival (TOA) measurements is proposed. In the condition that one of the sensors can obtain the AOA of the emitter, this algorithm utilizes AOA measurement to improve the traditional MDS localization based on TOA measurements. The simulation results demonstrated the improvement of this algorithm. <s> BIB008 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. Centralized MDS Based Localization <s> For radio frequency identification (RFID) system, the location information is very important in many applications, such as Internet of Things, logistics, library management, and so on. Most of traditional RFID localization algorithms can only locate one tag at a time. However, multitag localization is desired in many RFID applications. In this paper, we propose a novel range-free algorithm named nonmetric multidimensional scaling (NMDS)-RFID(F), which combines NMDS algorithm and the fingerprinting localization algorithm to achieve indoor RFID multitag cooperative localization. The NMDS-RFID(F) algorithm firstly uses received signal strength Euclidean distance based on fingerprinting method to get the rank order of the distance for all pairs of tags, and then NMDS algorithm is used to generate the relative coordinates of tags. Finally, due to the coordinates of reference tags are known, we can use the coordinate system registration algorithm to get the absolute coordinates of tags. Simulation results show that the NMDS-RFID(F) algorithm outperforms some previous RFID localization algorithms. <s> BIB009 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> B. Centralized MDS Based Localization <s> Multidimensional Scaling (MDS) is a widely used technique for visualizing a set of objects in an n-dimensional space. It has been extensively applied in wireless sensor networks for deriving the coordinates of a set of nodes in distance-based Localization. Many variants of MDS have been proposed to overcome issues such as partial connectivity and different types of noise in the measurements. In particular, some works adapted and modified the MDS technique to include the notion of anchors. However, in order to maintain the original formulation of MDS, the algorithm was twisted by adding constraints to the minimization function or adapting the final result through roto-translations. Unfortunately, however, these adaptions do not fully solve the problem, because they try to align the relative positions of the nodes to the global reference system provided by the anchors only after the MDS algorithm. This paper provides a theoretical generalization of the classical MDS algorithm when some of the coordinates of some elements (e.g., anchors in the case of localization) are known. The proposed generalization can be applied to any of the many MDS variants (e.g., classical MDS, ordinal MDS, MDS-MAP, GM-MDS) that minimize the stress function with the SMACOF technique. The formulation is proved to be correct and does not add any constraints to MDS. <s> BIB010
Assume that there are n nodes in the network and the pairwise range measurements between the nodes are noisy, the centralized MDS based localization consists of the following steps  . • The shortest path distances are estimated between each pair of all nodes by using shortest path algorithms (Dijkstra or Floyd Warshall algorithms  ) to construct the distance affinity matrix D = {d 2 ij } n i,j =1 which can be written in matrix form as where the direct neighborhood distance is the Euclidean distance between node i and j, ij represents the ranging error which is modeled as zero-mean Gaussian random variable with variance d ij η 2 ij where η 2 ij = μd , μ is scalar constant related to the receiver, and β ij is the path loss exponent. As the matrix D is square symmetric witĥ d ii = 0 andd ij =d ji , therefore, simplifying (7) yields • The MDS method is applied to the distance affinity matrix D to minimize the discrepancies between the actual Euclidean distances and estimated distances. The normalized loss function or stress function for the MDS method is defined as The stress function defined in (9) is nonlinear and nonconvex, therefore to get the close form solution for this function, the distance affinity matrix D is double centered by using the double centering operator H = I − 1 n ee T , given as which is then decomposed by using Eigen value decomposition given as where e represents the eigen-vectors and λ are the eigenvalues. Finally, the relative two dimensional positions of the nodes are determined from the two largest eigenvalues of λ and two largest eigen-vectors in e, i.e., Since the position estimates obtained in (12) are not absolute, it is required to transform these relative position estimates into absolute (global) positions. Linear transformations such as Procrustes analysis, Helmert transformation, or principal coordinate analysis can be used to get the global position estimates. Centralized MDS based localization method was first proposed by Shang et al. in BIB001 . The proposed method in BIB001 is applicable to both range based and range free conditions. The benefit of using centralized MDS is that it can work with few number of anchors with high accuracy. But the problems with this approach are high computational overhead and large localization error for irregular networks. An ordinal MDS based centralized localization method is proposed in BIB002 which requires only the relationship between the shortest path distances and the Euclidean distances. Classical centralized MDS based localization is proposed in BIB004 for RFID systems. Centralized RSS based non-metric MDS is used in BIB009 to find the location of RFID tags. Small scale WSNs localization is investigated in BIB005 , BIB006 by using centralized MDS method. A centralized cooperative MDS based localization method is proposed in  for WLANs. Authors in BIB007 have investigated the multipath propagation ranging error for MDS based localization method. In BIB003 a weighted MDS is proposed for WSNs localization where the accurate range measurements are given more weight, and the noisy ranges are down-weighted. A hybrid ToA and AoA based centralized MDS method is presented in BIB008 for WSNs localization. In BIB010 a theoretical generalization for centralized MDS based localization is provided in the presence of few anchors.