Sensor network localization (SNL) is a challenging problem due to its inherent non-convexity and the effects of noise in inter-node ranging measurements and anchor node position. We formulate a non-convex SNL problem as a multi-player non-convex potential game and investigate the existence and uniqueness of a Nash equilibrium (NE) in both the ideal setting without measurement noise and the practical setting with measurement noise. We first show that the NE exists and is unique in the noiseless case, and corresponds to the precise network localization. Then, we study the SNL for the case with errors affecting the anchor node position and the inter-node distance measurements. Specifically, we establish that in case these errors are sufficiently small, the NE exists and is unique. It is shown that the NE is an approximate solution to the SNL problem, and that the position errors can be quantified accordingly. Based on these findings, we apply the results to case studies involving only inter-node distance measurement errors and only anchor position information inaccuracies.

Consider a sensor network consisting of both anchor and non-anchor nodes. We address the following sensor network localization (SNL) problem: given the physical locations of anchor nodes and relative measurements among all nodes, determine the locations of all non-anchor nodes. The solution to the SNL problem is challenging due to its inherent non-convexity. In this paper, the problem takes on the form of a multi-player non-convex potential game in which canonical duality theory is used to define a complementary dual potential function. After showing the Nash equilibrium (NE) correspondent to the SNL solution, we provide a necessary and sufficient condition for a stationary point to coincide with the NE. An algorithm is proposed to reach the NE and shown to have convergence rate $\mathcal{O}(1/\sqrt{k})$. With the aim of reducing the information exchange within a network, a distributed algorithm for NE seeking is implemented and its global convergence analysis is provided. Extensive simulations show the validity and effectiveness of the proposed approach to solve the SNL problem.

Graph neural networks (GNNs) have gained significant popularity for classification tasks in machine learning, yet their applications to regression problems remain limited. Concurrently, attention mechanisms have emerged as powerful tools in sequential learning tasks. In this paper, we employ GNNs and attention mechanisms to address a classical but challenging nonlinear regression problem: network localization. We propose a novel GNN-based network localization method that achieves exceptional stability and accuracy in the presence of severe non-line-of-sight (NLOS) propagations, while eliminating the need for laborious offline calibration or NLOS identification. Extensive experimental results validate the effectiveness and high accuracy of our GNN-based localization model, particularly in challenging NLOS scenarios. However, the proposed GNN-based model exhibits limited flexibility, and its accuracy is highly sensitive to a specific hyperparameter that determines the graph structure. To address the limitations and extend the applicability of the GNN-based model to real scenarios, we introduce two attentional graph neural networks (AGNNs) that offer enhanced flexibility and the ability to automatically learn the optimal hyperparameter for each node. Experimental results confirm that the AGNN models are able to enhance localization accuracy, providing a promising solution for real-world applications. We also provide some analyses of the improved performance achieved by the AGNN models from the perspectives of dynamic attention and signal denoising characteristics.

Sensor network localization (SNL) problems require determining the physical coordinates of all sensors in a network. This process relies on the global coordinates of anchors and the available measurements between non-anchor and anchor nodes. Attributed to the intrinsic non-convexity, obtaining a globally optimal solution to SNL is challenging, as well as implementing corresponding algorithms. In this paper, we formulate a non-convex multi-player potential game for a generic SNL problem to investigate the identification condition of the global Nash equilibrium (NE) therein, where the global NE represents the global solution of SNL. We employ canonical duality theory to transform the non-convex game into a complementary dual problem. Then we develop a conjugation-based algorithm to compute the stationary points of the complementary dual problem. On this basis, we show an identification condition of the global NE: the stationary point of the proposed algorithm satisfies a duality relation. Finally, simulation results are provided to validate the effectiveness of the theoretical results.

In the general problem known as multidimensional scaling (MDS), the primary objective is to represent a set of items as points within a Euclidean space of a specified dimension. This representation should ideally preserve the given pairwise dissimilarities as accurately as possible, by ensuring that the Euclidean distances between these points mirror the original dissimilarities. MDS is a extensively researched problem found in diverse fields such as psychometrics [16], mathematics, and computer science [9, 14, 57], engineering (where it is also known as network localization) [61], as well as statistics [3, 71] and machine learning [43, Ch 14]. Dimensionality reduction (DR) aims at embedding data points in a Euclidean space into a lower-dimensional Euclidean space while preserving, as much as possible, the geometry of the point cloud [36, 59]. When the data points are assumed to be on or near a smooth submanifold, a variant of DR known as manifold learning, this typically means preserving the pairwise intrinsic distances to the greatest extent.

Distance measurements demonstrate distinctive scalability when used for relative state estimation in large-scale multi-robot systems. Despite the attractiveness of distance measurements, multi-robot relative state estimation based on distance measurements raises a tricky optimization problem, especially in the context of large-scale systems. Motivated by this, we aim to develop specialized computational techniques that enable robust and efficient estimation when deploying distance measurements at scale. We first reveal the commonality between the estimation problem and the one that finds realization of a sensor network, from which we draw crucial lesson to inspire the proposed methods. However, solving the latter problem in large-scale (still) requires distributed optimization schemes with scalability natures, efficient computational procedures, and fast convergence rates. Towards this goal, we propose a complementary pair of distributed computational techniques with the classical block coordinate descent (BCD) algorithm as a unified backbone. In the first method, we treat Burer-Monteiro factorization as a rank-restricted heuristic for rank-constrained semidefinite programming (SDP), where a specialized BCD-type algorithm that analytically solve each block update subproblem is employed. Although this method enables robust and (extremely) fast recovery of estimates from initial guesses, it inevitably fails as the initialization becomes disorganized. We therefore propose the second method, derived from a convex formulation named anchored edge-based semidefinite programming} (ESDP), to complement it, at the expense of a certain loss of efficiency. This formulation is structurally decomposable so that BCD can be naturally employed, where each subproblem is convex and (again) solved exactly...

We present a novel initialization technique for the range-aided simultaneous localization and mapping (RA-SLAM) problem. In RA-SLAM we consider measurements of point-to-point distances in addition to measurements of rigid transformations to landmark or pose variables. Standard formulations of RA-SLAM approach the problem as non-convex optimization, which requires a good initialization to obtain quality results. The initialization technique proposed here relaxes the RA-SLAM problem to a convex problem which is then solved to determine an initialization for the original, non-convex problem. The relaxation is a second-order cone program (SOCP), which is derived from a quadratically constrained quadratic program (QCQP) formulation of the RA-SLAM problem. As a SOCP, the method is highly scalable. We name this relaxation Second-order COnic RElaxation for RA-SLAM (SCORE). To our knowledge, this work represents the first convex relaxation for RA-SLAM. We present real-world and simulated experiments which show SCORE initialization permits the efficient recovery of quality solutions for a variety of challenging single- and multi-robot RA-SLAM problems with thousands of poses and range measurements.

Graph neural networks (GNNs) are popular to use for classifying structured data in the context of machine learning. But surprisingly, they are rarely applied to regression problems. In this work, we adopt GNN for a classic but challenging nonlinear regression problem, namely the network localization. Our main findings are in order. First, GNN is potentially the best solution to large-scale network localization in terms of accuracy, robustness and computational time. Second, thresholding of the communication range is essential to its superior performance. Simulation results corroborate that the proposed GNN based method outperforms all benchmarks by far. Such inspiring results are further justified theoretically in terms of data aggregation, non-line-of-sight (NLOS) noise removal and lowpass filtering effect, all affected by the threshold for neighbor selection. Code is available at https://github.com/Yanzongzi/GNN-For-localization.

A reliable, accurate, and affordable positioning service is highly required in wireless networks. In this paper, the novel Message Passing Hybrid Localization (MPHL) algorithm is proposed to solve the problem of cooperative distributed localization using distance and direction estimates. This hybrid approach combines two sensing modalities to reduce the uncertainty in localizing the network nodes. A statistical model is formulated for the problem, and approximate minimum mean square error (MMSE) estimates of the node locations are computed. The proposed MPHL is a distributed algorithm based on belief propagation (BP) and Markov chain Monte Carlo (MCMC) sampling. It improves the identifiability of the localization problem and reduces its sensitivity to the anchor node geometry, compared to distance-only or direction-only localization techniques. For example, the unknown location of a node can be found if it has only a single neighbor; and a whole network can be localized using only a single anchor node. Numerical results are presented showing that the average localization error is significantly reduced in almost every simulation scenario, about 50% in most cases, compared to the competing algorithms.

How to self-localize large teams of underwater nodes using only noisy range measurements? How to do it in a distributed way, and incorporating dynamics into the problem? How to reject outliers and produce trustworthy position estimates? The stringent acoustic communication channel and the accuracy needs of our geophysical survey application demand faster and more accurate localization methods. We approach dynamic localization as a MAP estimation problem where the prior encodes dynamics, and we devise a convex relaxation method that takes advantage of previous estimates at each measurement acquisition step; The algorithm converges at an optimal rate for first order methods. LocDyn is distributed: there is no fusion center responsible for processing acquired data and the same simple computations are performed for each node. LocDyn is accurate: experiments attest to a smaller positioning error than a comparable Kalman filter. LocDyn is robust: it rejects outlier noise, while the comparing methods succumb in terms of positioning error.