A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Given a set of pairwise distance estimates between nodes, it is often of interest to generate a map of node locations. This is an old problem that has attracted renewed interest in the signal processing community, due to the recent emergence of wireless sensor networks and ad-hoc networks. Sensor maps are useful for estimating the spatial distribution of measured phenomena, as well as for routing purposes. Both centralized and decentralized solutions have been developed, along with ways to cope with missing data, accounting for the reliability of individual measurements, etc. We revisit the basic version of the problem, and propose a two-stage algorithm that combines algebraic initialization and gradient descent. In particular, we borrow an algebraic solution from the database literature and adapt it to the sensor network context, using a specific choice of anchor/pivot nodes. The resulting estimates are fed to gradient descent iteration. The overall algorithm offers better performance at lower complexity than existing centralized full-connectivity solutions. Also, its performance is relatively close to the corresponding Cramer-Rao bound, especially for small values of range error variance. <s> BIB001 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Accurate, distributed localization algorithms are needed for a wide variety of wireless sensor network applications. This article introduces a scalable, distributed weighted-multidimensional scaling (dwMDS) algorithm that adaptively emphasizes the most accurate range measurements and naturally accounts for communication constraints within the sensor network. Each node adaptively chooses a neighborhood of sensors, updates its position estimate by minimizing a local cost function and then passes this update to neighboring sensors. Derived bounds on communication requirements provide insight on the energy efficiency of the proposed distributed method versus a centralized approach. For received signal-strength (RSS) based range measurements, we demonstrate via simulation that location estimates are nearly unbiased with variance close to the Cramer-Rao lower bound. Further, RSS and time-of-arrival (TOA) channel measurements are used to demonstrate performance as good as the centralized maximum-likelihood estimator (MLE) in a real-world sensor network. <s> BIB002 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Refinement is a necessary and effective step in some node localization schemes of wireless sensor networks (WSN). Suitable refinement procedure can improve the node localization accuracy and raise the robustness of the localization algorithm. However, most existing refinement algorithms are costly duo to complex computation and frequent communication, and may induce serious coverage problem duo to nonconvergent iterations. In view of above facts, Steepest descent method is proposed to be used as the refinement algorithm in this paper, and corresponding simulation experiments are done to testify its feasibility and validity. The results show that steepest descent method can optimize the node positions to a fairish accuracy extent, and compared with existing refinement methods, it outperforms in communication cost, computation cost, and coverage rate. <s> BIB003 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Multidimensional Scaling (MDS) has been recently applied to node localization in sensor networks and gained some very impressive performance. MDS treats dissimilarities of pair-wise nodes directly as Euclidean distances and then makes use of the spectral decomposition of a doubly centered matrix of dissimilarities. However dissimilarities mainly estimated by Received Signal Strength (RSS) or by the Time of Arrival (TOA) of communication signal from the sender to the receiver used to suffer much errors when the distances between nodes are far. From this observation, Weighted Multidimensional Scaling (WMDS) is proposed in this paper. Different from MDS, WMDS incorporates weighting factors to account for the impact of pair-wise estimated dissimilarities in MDS framework. The further distance between two nodes is, the less "impact" weight should be considered. The experiment on real sensor network measurements of RSS and TOA shows the efficiency and novelty of WMDS for sensor localization problem in term of sensor location-estimated error. <s> BIB004 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Localization of sensor nodes is a fundamental and important problem in wireless sensor networks. Although classical multidimensional scaling (MDS) is a computationally attractive positioning method, it is statistically inefficient and cannot be applied in partially-connected sensor networks. In this correspondence, a weighted MDS algorithm is devised to circumvent these limitations. It is proved that the estimation performance of the proposed algorithm can attain Cramer-Rao lower bound (CRLB) for sufficiently small noise conditions. Computer simulations are included to contrast the performance of the proposed algorithm with the classical MDS and distributed weighted MDS algorithms as well as CRLB. <s> BIB005 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Sensory systems for localization and mapping based on ranging allows to obtain not only the position of a mobile object but also the position of the beacons or landmarks. Using only ranging, the beacon positions are often calculated without needing to compute all the spatial relations among them. In this work, a preliminary study about the use of relative positioning algorithm to obtain a map of active landmarks or beacon is described. The used architecture is able to easily compute spatial relations with beacons without increasing the hardware architecture. The used algorithm is based on a first position approximation by multidimensional scaling techniques; then, an optimization, using Levenberg-Marquardt algorithm, is applied to the non-linear equations, which involves the observations carried out between beacons and mobile objects. <s> BIB006 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> This paper presents a hybrid localization algorithm for a Peer-to-Peer (P2P)-Positioning scenario, where “peers” are devices equipped with both a GNSS (Global Navigation Satellite System) receiver and a wireless communications interface. Through their GNSS receiver, peers obtain pseudorange estimates from satellites while they use their wireless interface both to communicate with each other and to obtain terrestrial range estimates. The proposed algorithm is an extended version of the distributed-weighted multidimensional scaling (dwMDS) [1] algorithm to be compatible with the hybrid P2P scenario where unknown peers infer their own positions by fusing both GNSS pseudorange and terrestrial range estimates. Simulation results show that the proposed hybrid dwMDS (hdwMDS) algorithm out-performs the cooperative version of the least squares algorithm. Moreover, they show the related benefits in term of positioning performance in a cooperative scenario in comparison to a non cooperative one based on GNSS-only positioning. <s> BIB007 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Cooperative localization of mobile sensor networks is a fundamental problem which becomes challenging for anchorless networks where there is no pre-existing infrastructure to rely on. Two cooperative mobile network tracking algorithms based on novel dynamic multidimensional scaling (MDS) ideas are proposed. The algorithms are also extended to operate in partially connected networks. Compared with recently proposed algorithms based on the extended and unscented Kalman filter (EKF and UKF), the proposed algorithms have a considerably lower computational complexity. Furthermore, model-independence, scalability, as well as an acceptable accuracy make our proposed algorithms a good choice for practical mobile network tracking. <s> BIB008 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> This study deals with the localisation of all nodes in a network, also called as network localisation, based on pairwise distance measurements. The case of a fully connected network is considered, where ‘fully connected’ refers to that within the whole network every pair of nodes directly connect to each other, thus their pairwise distance can be measured and available. For the localisation of such a network, the multi-dimensional scaling (MDS) algorithm can provide a relative localisation solution, but only a coarse solution when there are measurement errors. To bridge the gap in the localisation performance between the MDS-based and optimum network localisation, the authors propose an efficient subsequent refinement, that is, the iterative least square (LS)/weighted least square (WLS) refinement for the widely existing independent zero-mean Gaussian measurement errors. Analysis and simulation study show that with sufficiently small measurement errors the proposed improved network localisation scheme can achieve, in very limited iterations, the LS/WLS solution, which exhibits the localisation performance the same as the Cramer–Rao lower bound. The authors also extend the proposed refinement to the absolute localisation case with sufficient position-known anchors that are fully and directly connected to all sensors of the network. <s> BIB009 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> The present work considers the localization problem in wireless sensor networks formed by fixed nodes. Each node seeks to estimate its own position based on noisy measurements of the relative distance to other nodes. In a centralized batch mode, positions can be retrieved (up to a rigid transformation) by applying an eigenvalue decomposition on a so-called similarity matrix built from the relative distances. In this paper, we propose a distributed on-line algorithm allowing each node to estimate its own position based on limited exchange of information in the network. Our framework encompasses the case of sporadic measurements and random transmissions. We prove the consistency of our algorithm in the case of fixed sensors. Finally, we provide numerical and experimental results from both simulated and real data. Simulations issued to real data are conducted on a wireless sensor network testbed. HighlightsWe design an on-line and asynchronous distributed algorithm for the WSN localization problem.We prove almost sure (a.s.) convergence of the proposed distributed.We include a distributed refinement phase in order to improve the position accuracy.We provide numerical results on the position accuracy in a real testbed in an indoor scenario. <s> BIB010 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Recent advancements in micro electro mechanical system and wireless communication have made it possible to use wireless sensor nodes for many real world applications. Wireless sensor nodes are widely been used now a days in many tracking and monitoring problems such as vehicle tracking, environmental and health monitoring. It is one of the most challenging problems to find the geographic locations of nodes given that proximity information only between the nodes. There are large number of localization algorithms, each having different approach to find the final location. Multidimensional Scaling (MDS) is one of that technique which works in more robust fashion for noise sparse networks, even with less number of anchor nodes. The proposed work addresses the problem of location discovery of nodes based on MDS and Levenberg-Maurquardt (LM) method. In this paper we used MDS to find the initial estimated position of nodes and proposed Levenberg-Maurquardt as a refinement algorithm for final position. Our simulation results show that the proposed scheme is very competitive compared to other common schemes. <s> BIB011 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> This paper considers the problem of cooperative ocalization in mobile networks. In static networks, node locations can be obtained from pairwise distance measurements using the classical multidimensional scaling (MDS) approach. This paper introduces a modified MDS framework that also incorporates relative velocity measurements available in mobile networks. The proposed cost function is minimized via a provably convergent, low complexity majorization algorithm similar to SMACOF. The ailgorithm incurs low computational and communication cost, and allows practical constraints such as missing measurements and variable node velocities. Simulation results corroborate the performance gains obtained by the proposed algorithm over state-of-the-art localization algorithms. <s> BIB012 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> This paper considers the noisy range-only network localization problem in which measurements of relative distances between agents are used to estimate their positions in networked systems. When distance information is noisy, existence and uniqueness of location solution are usually not guaranteed. It is well known that in presence of distance measurement noise, a node may have discontinuous deformations (e.g., flip ambiguities and discontinuous flex ambiguities). Thus, there are two issues that we consider in the noisy localization problem. The first one is the location estimate error propagated from distance measurement noise. We compare two kinds of analytical location error computation methods by assuming that each distance is corrupted with independent Gaussian random noise. These analytical results help us to understand effects of the measurement noises on the position estimation accuracy. After that, based on multidimensional scaling theory, we propose a distributed localization algorithm to solve the noisy range network localization problem. Our approach is robust to distance measurement noise, and it can be implemented in any random case without considering the network setup constraints. Moreover, a refined version of distributed noisy range localization method is developed, which achieves a good tradeoff between computational effort and global convergence especially in large-scale networks. <s> BIB013 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> This work deals with source localization with time-difference-of-arrival (TDOA) measurements in two-dimensional (2-D) scenarios. Although the celebrated two-step weighted least squares (2WLS) method is quite successful, its drawback lies in an ill-conditioning problem when the sensor array is quasi-linear. This work presents a multidimensional scaling (MDS)-based localization scheme. Based on the subspace analysis of the scalar product matrix, an auxiliary line is defined in the plane, close to the global minimizer of the cost function. Then, the minimizer on the auxiliary line is found as the estimation of the source position. Simulations show that the proposed scheme achieves high localization accuracy for all kinds of sensor arrays including quasi-linear arrays. <s> BIB014 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> This paper considers the problem of cooperative localization in mobile networks. In static networks, node locations can be obtained from pairwise distance measurements using the classical multidimensional scaling (MDS) approach. This paper introduces a modified MDS framework that also incorporates relative velocity measurements if available in mobile networks. The proposed cost function is minimized via a low complexity majorization algorithm. A distributed variant of the proposed algorithm is also outlined for use in large resource-constrained multi-hop networks. The proposed algorithm incurs low computational and communication cost, and handles practical constraints such as missing measurements and variable node velocities. Simulation results corroborate the performance gains obtained by the proposed algorithm over state-of-the-art localization algorithms. <s> BIB015 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Localization in wireless sensor networks (WSNs) is one of the primary functions of the intelligent Internet of Things (IoT) that offers automatically discoverable services, while the localization accuracy is a key issue to evaluate the quality of those services. In this paper, we develop a framework to solve the Euclidean distance matrix completion problem, which is an important technical problem for distance-based localization in WSNs. The sensor network localization problem is described as a low-rank dimensional Euclidean distance completion problem with known nodes. The task is to find the sensor locations through recovery of missing entries of a squared distance matrix when the dimension of the data is small compared to the number of data points. We solve a relaxation optimization problem using a modification of Newton’s method, where the cost function depends on the squared distance matrix. The solution obtained in our scheme achieves a lower complexity and can perform better if we use it as an initial guess for an interactive local search of other higher precision localization scheme. Simulation results show the effectiveness of our approach. <s> BIB016 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> In this paper, we propose a matrix completion algorithm for Internet of Things (IoT) localization. In the proposed algorithm, we recast Euclidean distance matrix completion problem as an unconstrained optimization in smooth Riemannian manifold and then propose a nonlinear conjugate gradient method on this manifold to reconstruct Euclidean distance matrix. The empirical results show that the proposed algorithm is effective and also outperforms state-of-the-art matrix completion algorithms both in noise and noiseless scenarios. <s> BIB017 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> D. Distributed MDS Based Localization <s> Nowadays, finding the Unmanned Aerial Vehicle (UAV) position in the absence of GPS is attractive and challenging problem in the research community. In this paper, we present a novel algorithm for mini UAV indoor localization based on distance measurements between the UAV and the existing infrastructure consisting of WiFi Access Points. Our algorithm uses two well-known techniques from the literature: Multi-dimensional Scaling (MDS) and Weighted Centroid Localization (WCL). Through extensive simulations we have shown that our algorithm is very suitable for indoor localization of mini UAVs. For small radio-range error, our algorithm exhibits a small localization error of less than 5% of the radio range. <s> BIB018
Distributed localization methods are required for a wide range of applications. Therefore, fully distributed MDS based localization methods have been recently developed BIB014 BIB018 BIB010 . In distributed MDS based localization methods every node calculates range measurements to its neighbors and updates its location estimate by minimizing a local cost function BIB002 BIB004 BIB005 BIB007 . The steps involved in common distributed MDS based localization are similar to centralized and semi-centralized schemes, but after getting the relative position estimates, the central station sends the relative position estimates to each node, and then each node refine its own position estimate by using iterative position estimators. For example in BIB003 and BIB011 the authors used the steepest descent and Levenberg Marquardt method, respectively, to refine the MDS based relative position estimations. The update rule for position estimation in BIB011 is defined aŝ where J k is the Jacobian matrix given by λ is the step length, and f (P k i ) is the error function given as L is the total number of anchors andd il is the estimated distance between node i and anchor l. In addition to the low complexity and better accuracy, distributed MDS based methods can also support mobility. Since, in centralized MDS techniques, all the ranging information is collected at the central node which is the bottleneck of the network. In case of mobility, the network topology changes which require the minimization of a new global cost function in real time and therefore, the centralized MDS may not be a practical solution. However, in distributed MDS a local cost function is minimized which does not depend on the global topology of the network and therefore can support mobility. A number of distributed MDS based localization have been developed to determine the location of a moving user/node using different tracking filters. For example, in BIB008 the authors used extended Kalman filter and unscented Kalman filter with MDS to track mobile sensors. A low complexity majorization function with MDS is used in BIB012 , BIB015 to track mobile sensor nodes. Distributed MDS based localization algorithm is proposed in BIB013 with noisy range measurements, where the authors assume that the distances are corrupted with independent Gaussian random noise. MDS with different refinement schemes to get better localization accuracy for the sensor nodes location in WSNs has also been proposed in literature BIB001 BIB009 BIB011 , BIB003 , BIB006 . Recently a Euclidean distance matrix completion method is proposed for MDS in BIB016 , BIB017 to find the map of an IoT network. Different heuristic methods such as particle swarm optimization, simulated annealing, and genetic algorithms are applied with MDS to determine the location of mobile nodes  .