# Distributed Finite-Time Cooperative Localization for Three-Dimensional
Sensor Networks

Jinze Wu, Lorenzo Zino, Zhiyun Lin, and Alessandro Rizzo J. Wu, L. Zino, and
A. Rizzo are with the Department of Electronics and Telecommunications,
Politecnico di Torino, Torino, Italy. Emails:
<EMAIL_ADDRESS>J. Wu and Z. Lin are with
Shenzhen Key Laboratory of Control Theory and Intelligent Systems, School of
System Design and Intelligent Manufacturing, Southern University of Science
and Technology, Shenzhen, China. Email<EMAIL_ADDRESS>Z. Lin is also
with Peng Cheng Laboratory, Shenzhen, China. A. Rizzo is also with the
Institute for Invention, Innovation, and Entrepreneurship, New York University
Tandon School of Engineering, Brooklyn NY, US.

###### Abstract

This paper addresses the distributed localization problem for a network of
sensors placed in a three-dimensional space, in which sensors are able to
perform range measurements, i.e., measure the relative distance between them,
and exchange information on a network structure. First, we derive a necessary
and sufficient condition for node localizability using barycentric
coordinates. Then, building on this theoretical result, we design a
distributed localizability verification algorithm, in which we propose and
employ a novel distributed finite-time algorithm for sum consensus. Finally,
we develop a distributed localization algorithm based on conjugate gradient
method, and we derive a theoretical guarantee on its performance, which
ensures finite-time convergence to the exact position for all localizable
nodes. The efficiency of our algorithm compared to the existing ones from the
state-of-the-art literature is further demonstrated through numerical
simulations.

##  1 Introduction

Localization has become a critical issue as the position information of a set
of agents plays an increasingly important role in multiple applications, such
as target searching, environmental monitoring, and formation control [1, 2, 3,
4, 5]. The most common method to obtain position information is to equip all
agents with GPS, a satellite-based global positioning system that provides the
coordinates of receivers [6]. However, GPS has some drawbacks in terms of
coverage and power consumption [7]. More specifically, it may not work
properly in environments with obstructions between the GPS satellites and the
receivers, e.g., interior buildings and areas with dense vegetation or
mountains. Furthermore, a scenario in which all agents are equipped with GPS
consumes more energy than one with only a few of them equipped with GPS. Thus,
cooperative localization based on terrestrial techniques such as cellular,
WiFi, and ultra-wideband has come to the fore.

The objective of cooperative localization is to determine the Euclidean
coordinates of all agents given the Euclidean coordinates of a (small) subset
of reference agents, and assuming that the rest of the agents is able to make
local measurements (e.g., the relative distance, bearing, or angle between
them) and exchange information over a network. For this reason, in the rest of
this paper we will refer to the set of agents as a _sensor network_. Given the
importance of this problem, several approaches have been proposed in the
literature.

Since the essence of the cooperative localization problem is nonlinear (being
the relationship between Euclidean coordinates and local measurements
generally nonlinear), most authors in the literature focused on nonlinear
algorithms, formulating the cooperative localization problem as a constrained
nonlinear optimization problem [8, 9, 10, 11]. However, these approaches have
several crucial limitations. First, solvers for such nonlinear optimization
problems typically lack in theoretical guarantees to ensure global convergence
[9]. Second, as the scale of the sensor network grows, solving nonlinear
equations results in an increased number of saddle points due to iterations,
limiting the possibility to implement them in large-scale real-world
applications [12]. Third, most of the nonlinear localization algorithms
proposed in the literature need to be solved in a centralized fashion,
yielding a more complex and less robust architecture.

In order to address the limitations of nonlinear algorithms, distributed
linear cooperative localization algorithms have attracted a lot of research
interest in recent years. In particular, different algorithms have been
proposed to tackle this problem, depending on the type of local measurements
that the sensors are able to perform, including range-based [13, 14, 15, 16,
17], bearing-based [18, 19, 20, 21], relative position-based [22, 23], angle-
based [24, 25, 26] and mixed measurements-based [27, 28, 29] methods. A common
technique to represent space in these effort is the use of barycentric
coordinates [30] –a coordinate system in which the location of a point is
specified with reference to other points. Barycentric coordinate systems have
emerged as one of the most effective tools to obtain the prerequisites for
addressing the cooperative localization problem in a distributed and linear
manner.

The authors in [13] proposed a distributed localization algorithm based on
barycentric coordinates that uses range-based measurements (i.e., in which it
is assumed that sensors can measure the relative distance between them). This
algorithm is implemented by expressing the positions of the sensors as a
pseudo linear system with all nonlinearities hidden in range measurements and
relies on the assumption that each sensor requires to lie inside the convex
hull of its neighbors. To remove this assumption, [15] developed a novel
localization algorithm in a two-dimensional space. Building on this approach,
[16] presented a more robust localization algorithm in a two-dimensional
space, adopting the idea of the congruent framework. Such approach was
successfully extended to a three-dimensional space in [17]. Besides range-
based measurements, barycentric coordinates were also employed to solve
localization problems in other scenarios, with bearing [19, 21], relative
position [23], angle [24] and mixed [27] measurements. Moreover, the angle-
based localization algorithms proposed in [25, 26] can be converted into
barycentric coordinates for solution as well.

In addition to designing localization algorithms, a problem of paramount
importance is to determine which nodes are localizable, given the specific
characteristics of the sensor network setup (i.e., topology of the sensing and
communication channel, and type of measurement that sensor can perform) [31].
Most of the aforementioned works have focused on proposing localization
algorithms under the assumption that all sensor nodes can be localized in the
sensor network. In other words, these works solely address network
localizability without delving into the node localizability. However, research
on node localizability in the localization problem based on barycentric
coordinates holds significant importance. Neglecting whether a sensor node is
localizable or not can lead to errors in the localization process. For
instance, the location of a localizable sensor may be inaccurately estimated
due to the iterative propagation of wrong positions from unlocalizable
sensors. Therefore, it is crucial to identify all localizable and
unlocalizable sensor nodes before implementing a distributed localization
algorithm. Accurate identification of localizable sensors is a key step to
ensure the reliability and precision of the localization process in a sensor
network.

In this paper, we address the localization problem, without making any a
priori assumption on localizability. Specifically, we deal with the range-
based localization problem for sensor networks in a three-dimensional space.
The main contribution of this paper is threefold. First, we prove a necessary
and sufficient condition for node localizability of range-based localization
problem in a three-dimensional space using barycentric coordinates, and then
propose a distributed verification algorithm to distinguish between
localizable and unlocalizable sensor nodes in the sensor network. With this
verification and filtering process, many localization algorithms based on
barycentric coordinates can still succeed even in the presence of
unlocalizable sensor nodes, further lifting the restrictions of localization
algorithms. Second, we develop a distributed conjugate gradient localization
algorithm to efficiently solve the localization problem for the sensor network
in finite time. Its finite-time convergence is proved theoretically, and then
validated in numerical simulations. Third, in the development of our
algorithms, we propose a novel distributed algorithm, which is able to achieve
sum consensus among all nodes in the network in finite time. Such algorithm,
which is used in our localization process, is a distributed consensus
algorithm that considers the tradeoff between memory size and iteration steps,
and can be directly employed in other application fields.

The rest of the paper is organized as follows. Section 2 presents notation and
preliminaries. In Section 3, we formulate the research problem. In Section 4,
we propose a distributed algorithm to address the localizability verification
problem. Section 5 is devoted to the distributed localization algorithm and
the proof of its finite-time convergence. Numerical simulations are presented
in Section 6. Section 7 concludes the paper and outlines future research
directions.

##  2 Notation and Preliminaries

###  2.1 Notation

We use uppercase letters for matrices, bold lowercase letters for vectors, and
lowercase letters for scalars. With $\mathbf{x}\in\mathbb{R}^{n}$ we refer to
a column vector, and we use the transpose operator ($\mathbf{x}^{\top}$) to
denote row vectors. Let $\mathbb{R}^{n}$ be the $n$-dimensional real
coordinate space. $I_{n}$ denotes the identity matrix of order $n\times n$,
while $\mathbf{1}_{n}$ denotes the $n$-dimensional vector with all entries
equal to $1$ and $\mathbf{e_{i}}$ denotes a vector whose $i$th entry is $1$
and all other entries are $0$. The symbol $\|\cdot\|$ denotes the 2-norm and
$\otimes$ denotes the Kronecker product. Moreover, the symbol $\lceil x\rceil$
refers to the smallest integer that is larger than or equal to a real number
$x$. Finally, let $\textrm{diag}(\cdot)$ denote the diagonal matrix. Given a
matrix $A\in\mathbb{R}^{n\times m}$, $\textrm{rank}(A)$ and $\textrm{ker}(A)$
are its rank and kernel, respectively.

###  2.2 Graph Theory

An undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ consists of a
nonempty set $\mathcal{V}$, whose elements are called nodes or vertices, and a
set of unordered pairs of nodes
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$, whose elements are called
edges. For a node $i$, we define its neighbor set as
$\mathcal{N}_{i}:=\\{j\in\mathcal{V}:(i,j)\in\mathcal{E}\\}$. Clearly, if
$i\in\mathcal{N}_{j}$ then $j\in\mathcal{N}_{i}$. A path of length $\ell$ from
$i\in\mathcal{V}$ to $j\in\mathcal{V}$ is a sequence of $\ell$ edges of the
form $(i,v_{1}),(v_{1},v_{2}),\dots,(v_{\ell-1},j)$. A graph is said to be
_connected_ if there is a path between every pair of vertices. The diameter of
a connected graph, denoted by $\delta$, is the maximum among all the lengths
of the shortest path between any pair of vertices of the graph. A subset of
$d$ vertices such that each and every pair of them is connected through an
edge is said to be a _clique_ of order $d$. Here, we shall refer to cliques of
order $4$ as _tetrahedrons_ and use the notation
$\mathchoice{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=5.59721pt]{tetrahedron}}{\includegraphics[height=3.87495pt]{tetrahedron}}ijkl$
for a tetrahedron with vertices $i,j,k,l\in\mathcal{V}$. Note that a clique of
order $5$ is formed by $5$ tetrahedrons.

Given a set of $n$ nodes positioned in the Euclidean space $\mathbb{R}^{3}$,
we define their _configuration_ as the vector
$\mathbf{p}=[\mathbf{p}^{\top}_{1},\cdots,\mathbf{p}^{\top}_{n}]^{\top}\in\mathbb{R}^{3n}$,
where the entry $\mathbf{p_{i}}\in\mathbb{R}^{3}$ is the position of node $i$
in the three-dimensional Euclidean space. A configuration
$\mathbf{p}=[\mathbf{p}^{\top}_{1},\cdots,\mathbf{p}^{\top}_{n}]^{\top}\in\mathbb{R}^{3n}$
is said to be generic if the coordinates
$\mathbf{p_{1}},\cdots,\mathbf{p_{n}}$ do not satisfy any nonzero polynomial
equation with integer coefficients or equivalently algebraic coefficients
[32]. In other words, a generic configuration has no degeneracy, that is, no
three points staying on the same line, no three lines go through the same
point, no four points staying on the same plane, etc.

A framework $\mathcal{F}=(\mathcal{G},\mathbf{p})$ in the Euclidean space
$\mathbb{R}^{3}$ is formed by a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$
and a configuration $\mathbf{p}\in\mathbb{R}^{3n}$. Two frameworks with the
same graph $(\mathcal{G},\mathbf{p})$ and $(\mathcal{G},\mathbf{q})$ are said
to be congruent (denoted by
$(\mathcal{G},\mathbf{p})\equiv(\mathcal{G},\mathbf{q})$) if and only if (iff)
$\|\mathbf{p_{i}}-\mathbf{p_{j}}\|=\|\mathbf{q_{i}}-\mathbf{q_{j}}\|$ holds
for all pairs $i,j\in\mathcal{V}$. In other words, all nodes of two congruent
frameworks maintain the same distances between pairs. It is easy to check that
the property of being congruent is an equivalence relation. It is important to
notice that such an equivalence relation preserves volumes in the space.

###  2.3 Barycentric Coordinates

The barycentric coordinates were introduced by A. F. Möbius in 1827 as mass
points to define a coordinate-free geometry [30]. In fact, barycentric
coordinates characterize the relative position of a node with respect to other
nodes. Specifically, given five nodes $i,j,k,l$, and $h$ with their Euclidean
coordinates
$\mathbf{p_{i}},\mathbf{p_{j}},\mathbf{p_{k}},\mathbf{p_{l}},\mathbf{p_{h}}\in\mathbb{R}^{3}$,
the barycentric coordinates of node $i$ with respect to nodes $j,k,l$, and $h$
are equal to the quadruple $\\{a_{ij},a_{ik},a_{il},a_{ih}\\}$, solution of
the following system of equations:

$\begin{cases}\mathbf{p_{i}}=a_{ij}\mathbf{p_{j}}+a_{ik}\mathbf{p_{k}}+a_{il}\mathbf{p_{l}}+a_{ih}\mathbf{p_{h}},\\\
a_{ij}+a_{ik}+a_{il}+a_{ih}=1.\end{cases}$ (1)

In other words, using the barycentric coordinates, we represent the position
of a point in a three-dimensional space as a combination of the positions of
four other points in the space, and we use the weights of such combination to
identify the point. Fig. 1 illustrates a graphic representation of the
barycentric coordinates.

The barycentric coordinates of node $i$ can be calculated using the signed
volumes between corresponding tetrahedrons [30]. Specifically, it holds

$a_{ij}=\frac{V_{iklh}}{V_{jklh}},a_{ik}=\frac{V_{jilh}}{V_{jklh}},\\\
a_{il}=\frac{V_{jkih}}{V_{jklh}},a_{ih}=\frac{V_{jkli}}{V_{jklh}},$ (2)

where $V_{iklh},V_{jilh},V_{jkih},V_{jkli}$ and $V_{jklh}$ are the signed
volumes of the tetrahedrons
$\mathchoice{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=5.59721pt]{tetrahedron}}{\includegraphics[height=3.87495pt]{tetrahedron}}iklh$,
$\mathchoice{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=5.59721pt]{tetrahedron}}{\includegraphics[height=3.87495pt]{tetrahedron}}jilh$,
$\mathchoice{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=5.59721pt]{tetrahedron}}{\includegraphics[height=3.87495pt]{tetrahedron}}jkih$,
$\mathchoice{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=5.59721pt]{tetrahedron}}{\includegraphics[height=3.87495pt]{tetrahedron}}jkli$,
and
$\mathchoice{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=5.59721pt]{tetrahedron}}{\includegraphics[height=3.87495pt]{tetrahedron}}jklh$,
respectively. The signed volume $V_{iklh}$ is equal in modulus to the volume
of the tetrahedron
$\mathchoice{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=5.59721pt]{tetrahedron}}{\includegraphics[height=3.87495pt]{tetrahedron}}iklh$,
with positive sign if nodes $i,k,l$, and $h$ conform to the right hand
corkscrew rule, and negative otherwise. Given the coordinates of its four
vertices, the signed volume $V_{iklh}$ is equal to the following determinant
of a $4\times 4$ matrix:

$V_{iklh}=\frac{1}{6}\left|\begin{array}[]{cccc}1&1&1&1\\\
\mathbf{p_{i}}&\mathbf{p_{k}}&\mathbf{p_{l}}&\mathbf{p_{h}}\\\
\end{array}\right|.$ (3)

Note that, due to the volume conservation law under roto-translation, the
barycentric coordinates of a node are invariant with respect to congruent
frameworks.

Figure 1: Illustration of the barycentric coordinates of node $i$ with respect
to nodes $j,k,l$, and $h$ in a three-dimensional space.

##  3 Problem Setup and Statement

###  3.1 Problem Setup

Consider $n$ sensors positioned in a three-dimensional Euclidean space.
Sensors are allowed to interact with each others —measuring their relative
distance (range measurement)— and communicate, subject to some constraints.
Specifically, we define a _sensor network_ that is represented by an
undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ by associating a node
of the graph with each sensor, and edges to describe the sensing and
communication topology of the sensor network. That is, we assume that
$(i,j)\in\mathcal{E}$ iff sensors $i$ and $j$ can measure their relative
distance and communicate, i.e., we assume that the sensing and communication
graphs of the sensor network are the same and that the network is connected.

The sensor network consists of a small number of sensors with known position
and a large number of sensors with unknown position. The sensors whose
position are known (e.g., obtained through GPS or being able to self-
calibrate) are called _anchor nodes_. The rest of the sensors are called _free
nodes_. The objective of cooperative localization is to estimate the Euclidean
coordinates in the global coordinate system of the free nodes in a distributed
fashion by exchanging information on their range measurements, given the
absolute Euclidean coordinates of the anchor nodes.

We observe that a necessary condition for all free nodes to be localized in a
three-dimensional space using relative measurements is that the sensor network
has at least four anchor nodes [33]. Hence, without any loss in generality, we
assume there are four anchor nodes and $n-4$ free nodes. We denote these sets
as $\mathcal{V}=\mathcal{V}_{f}\cup\mathcal{V}_{a}$, with
$\mathcal{V}_{f}=\\{1,\cdots,n-4\\}$ and $\mathcal{V}_{a}=\\{n-3,\cdots,n\\}$
denoting the free node set and the anchor node set, respectively. If the
sensor network has the edge $(i,j)\in\mathcal{E}$, then node $i$ can measure
the range measurement $d_{ij}=\|\mathbf{p_{i}}-\mathbf{p_{j}}\|$ and exchange
such information with node $j$. Let
$\mathbf{p_{f}}=[\mathbf{p_{1}}^{\top},\cdots,\mathbf{p_{n-4}}^{\top}]^{\top}\in\mathbb{R}^{3(n-4)}$
and
$\mathbf{p_{a}}=[\mathbf{p_{n-3}}^{\top},\cdots,\mathbf{p_{n}}^{\top}]^{\top}\in\mathbb{R}^{12}$
denote the Euclidean coordinate vectors of the free nodes and of the anchor
nodes, respectively. It is clear that $\mathbf{p_{a}}$ is known, but the
Euclidean coordinates of free node set $\mathbf{p_{f}}$ needs to be estimated.

All free nodes in the network can be characterized depending on their
possibility to be localized in a distributed fashion using barycentric
coordinates. Hence, we define two different classes: _localizable_ nodes and
_unlocalizable_ nodes. According to [33], a node requires at least four
neighbors for localizability in a three-dimensional space. Moreover, in order
to use barycentric coordinates, a node $i\in\mathcal{V}$ should position
itself with respect to other $4$ nodes. Intuitively, we need these $5$ nodes
(i.e., node $i$ and the four neighbors) to be able to communicate in order to
compute the volumes of the $5$ tetrahedrons they form and, ultimately, the
barycentric coordinates of $i$. Hence, node $i$ should belong to a clique of
order $5$ to be localized. As a consequence, all nodes that do not belong to
any clique of order $5$ belong necessarily to the class of unlocalizable
nodes, which we term _scarcely connected_ nodes.

######  Remark 1.

Node $i$ has information on its neighbor set $\mathcal{N}_{i}$. Moreover, $i$
can exchange such information with its neighbors. Hence, for any
$j\in\mathcal{N}_{i}$, the neighbor set $\mathcal{N}_{j}$ can be made
available to node $i$ via communication. Thus, by comparing these sets, it is
easy for node $i$ to know whether it belongs to a clique of order $5$, without
needing centralized information.

For the sake of simplicity, we will assume that all scarcely connected nodes
are detected a priori following Remark 1 and removed from the network. Hence,
we assume that each of all the (remaining) $n-4$ free nodes belong to at least
one clique of order $5$. However, belonging to a clique of order at least $5$
is a necessary condition for localizability, but is not sufficient. Hence, we
need to determine a sufficient condition for localizability, and then design
an algorithm to classify the free nodes depending on their localizability,
before any localization algorithm can be applied.

###  3.2 Problem Statement

In view of our problem setting, the distributed cooperative localization
problem explored in this paper is described as follows. We consider a sensor
network $\mathcal{G}$ with $n$ nodes in a three-dimensional space, in which
sensors can make range measurements and communicate with their neighbors on
$\mathcal{G}$. We assume that the absolute positions of four anchor nodes
$\mathbf{p_{a}}$ are known. Our objective is twofold.

######  Problem 1 (Localizability verification).

Design a distributed localizability test scheme to determine for which of the
free nodes it is possible to determine the absolute position.

######  Problem 2 (Localization algorithm).

Design a localization algorithm to estimate $\mathbf{p_{i}}$ in finite time,
for each free node $i\in\mathcal{V}_{f}$ that is localizable.

##  4 Localizability Verification Algorithm

In this section, we address Problem 1. We start by providing a necessary and
sufficient condition for node localizability. Then, we use such condition to
build an algorithm to verify node localizability in a distributed fashion.

###  4.1 Necessary and Sufficient Node Localizability Condition

Before presenting the necessary and sufficient condition of node
localizability, we first illustrate how the problem of estimating the
Euclidean coordinates of a sensor network can be cast as a set of linear
equations that can be derived in a distributed fashion using barycentric
coordinates.

Consider a clique of order $5$ formed by nodes $i,j,k,l,h\in\mathcal{V}$, with
positions
$\mathbf{p_{i}},\mathbf{p_{j}},\mathbf{p_{k}},\mathbf{p_{l}},\mathbf{p_{h}}\in\mathbb{R}^{3}$
in a framework we denote as $\mathcal{F}_{p}$. Node $i$ can communicate with
the other four neighbors and can get access to the range measurements
$d_{ij},d_{ik},d_{il}$, and $d_{ih}$ through onboard sensing or communication
from its neighbors. Moreover, since communication and sensing networks
coincide, node $i$ can also receive direct information about measurements
$d_{jk},d_{jl},d_{jh},d_{kl},d_{kh}$, and $d_{lh}$ through communication with
nodes $j,k,l$, and $h$. These measurements can be utilized to construct a
matrix $D\in\mathbb{R}^{5\times 5}$ with its generic entry
$D_{xy}:=d_{xy}^{2}$, that is, equal to the square of the distance measured
between nodes $x$ and $y$ for $x,y\in\\{i,j,k,l,h\\}$, and we define
$J=I_{5}-\frac{1}{5}\mathbf{1}_{5}\mathbf{1}_{5}^{\top}$. Then we can apply
the Congruent Framework Construction (CFC) algorithm summarized in the
pseudocode in Algorithm 1, obtaining matrix
$Q=[\mathbf{q_{i}}\,\mathbf{q_{j}}\,\mathbf{q_{k}}\,\mathbf{q_{l}}\,\mathbf{q_{h}}]$,
to construct a congruent framework $\mathcal{F}_{q}$ for the clique.

Algorithm 1 CFC Algorithm

0: Function: $Q=\textbf{CFC}(D)$

1: Compute $X=-\frac{1}{2}JDJ$.

2: Do singular value decomposition on $X$ as $X=V\Lambda V^{\top}$, where
$V=[\mathbf{v_{1}},\mathbf{v_{2}},\mathbf{v_{3}},\mathbf{v_{4}},\mathbf{v_{5}}]$
is a $5\times 5$ unitary matrix and $\Lambda$ is a diagonal matrix whose
diagonal elements
$\lambda_{1}\geq\lambda_{2}\geq\lambda_{3}\geq\lambda_{4}\geq\lambda_{5}\geq
0$ are singular values.

3: Compute
$\Lambda_{*}=\textrm{diag}(\lambda_{1},\lambda_{2},\lambda_{3})\in\mathbb{R}^{3\times
3}$ and
$V_{*}=[\mathbf{v_{1}},\mathbf{v_{2}},\mathbf{v_{3}}]\in\mathbb{R}^{5\times
3}$.

4: Compute $Q=\Lambda_{*}^{1/2}V_{*}^{\top}$.

5: return Q

Once a congruent framework of the clique of order $5$ is generated using the
CFC Algorithm, we compute the volumes of the tetrahedrons in the congruent
framework using (3), and then obtain the barycentric coordinates
$\\{a_{ij},a_{ik},a_{il},a_{ih}\\}$ of node $i$ using (2).

Ultimately, using (1), we establish the following linear equation for the
Euclidean coordinates of the five nodes belonging to the clique:

$\mathbf{p_{i}}=a_{ij}\mathbf{p_{j}}+a_{ik}\mathbf{p_{k}}+a_{il}\mathbf{p_{l}}+a_{ih}\mathbf{p_{h}},$
(4)

where the constants $a_{ij}$, $a_{ik}$, $a_{il}$, and $a_{ih}$ are known, and
$\mathbf{p_{i}},\mathbf{p_{j}},\mathbf{p_{k}},\mathbf{p_{l}},\mathbf{p_{h}}$
are the unknown absolute Euclidean coordinates of nodes $i,j,k,l$, and $h$ in
the global coordinate system.

It is easy to find that a node may lie in multiple cliques. For any of them,
we can establish one linear equality. Supposing that node $i$ lies in a total
of $r_{i}$ cliques, we aggregate all the equations (4) for the free nodes in
matrix form as

$\begin{bmatrix}\underbrace{\mathbf{p_{1}}\dots\mathbf{p_{1}}}_{r_{1}}\dots\underbrace{\mathbf{p_{n-4}}\dots\mathbf{p_{n-4}}}_{r_{n-4}}\end{bmatrix}^{\top}=\left(\begin{bmatrix}C&B\\\
\end{bmatrix}\otimes I_{3}\right)\begin{bmatrix}\mathbf{p_{f}}\\\
\mathbf{p_{a}}\end{bmatrix},$ (5)

where
$C\in\mathbb{R}^{\left(\sum_{i=1}^{n-4}r_{i}\right)\times\left(n-4\right)}$
and $B\in\mathbb{R}^{\left(\sum_{i=1}^{n-4}r_{i}\right)\times 4}$ are two
matrices that collects all the barycentric coordinates of the vertices
associated with free nodes and anchor nodes, respectively. Define

$E:=[\underbrace{\mathbf{e_{1}},\cdots,\mathbf{e_{1}}}_{r_{1}},\underbrace{\mathbf{e_{2}},\cdots,\mathbf{e_{2}}}_{r_{2}},\cdots,\underbrace{\mathbf{e_{n-4}},\cdots,\mathbf{e_{n-4}}}_{r_{n-4}}]^{\top},$
(6)

as a $\left(\sum_{i=1}^{n-4}r_{i}\right)\times\left(n-4\right)$ matrix. Let
$\bar{C}=C\otimes I_{3}$, $\bar{B}=B\otimes I_{3}$ and $\bar{E}=E\otimes
I_{3}$, we can write (5) in the following compact matrix form

$\left(\bar{E}-\bar{C}\right)\mathbf{p_{f}}=\bar{B}\mathbf{p_{a}}.$ (7)

Define $M=E-C$ and $\bar{M}=\bar{E}-\bar{C}$. Then (7) becomes

$\bar{M}\mathbf{p_{f}}=\bar{B}\mathbf{p_{a}},$ (8)

where $\bar{M}\in\mathbb{R}^{\left(3\sum_{i=1}^{n-4}r_{i}\right)\times
3\left(n-4\right)}$.

Next, subject to the linear equation constrains in (8), we address the node
localizability problem and present the necessary and sufficient conditions of
node localizability.

The least squares method is considered to obtain the solution by minimizing
the sum of the squares of the residuals made in the results of each individual
equation. For the equation system (8), the least squares formula is obtained
from the problem

$\min_{\mathbf{p_{f}}}\|\bar{M}\mathbf{p_{f}}-\bar{B}\mathbf{p_{a}}\|,$ (9)

the solution of which can be written with the normal equation

$\mathbf{p_{f}}=\left(\bar{M}^{\top}\bar{M}\right)^{-1}\bar{M}^{\top}\bar{B}\mathbf{p_{a}},$
(10)

provided $\left(\bar{M}^{\top}\bar{M}\right)^{-1}$ exists, which is equivalent
to $\bar{M}$ has full column rank. Note that for (10), an approximate solution
is found when no exact solution exists. Moreover, (10) can be viewed as the
solution to the following linear equation system

$\bar{M}^{\top}\bar{M}\mathbf{p_{f}}=\bar{M}^{\top}\bar{B}\mathbf{p_{a}},$
(11)

if $\bar{M}^{\top}\bar{M}$ is invertible.

######  Remark 2.

It is easy to see that $\mathbf{p_{f}}$ in (11) can be uniquely solved iff
$\textrm{rank}(\bar{M}^{\top}\bar{M})=3\left(n-4\right)$, which is equivalent
to $\textrm{rank}(\bar{M})=3\left(n-4\right)$ and $\textrm{rank}(M)=n-4$.
Hence if the rank of the matrix $\bar{M}$ is less than $3(n-4)$, namely, the
rank of the matrix $M$ is less than $n-4$, there must exist unlocalizable
nodes in the sensor network.

By utilizing the definitions $\bar{M}=M\otimes I_{3}$ and $\bar{B}=B\otimes
I_{3}$, we can interpret the linear equation system (11) as three equivalent
linear equation systems:
$M^{\top}M\mathbf{p_{f}^{\varphi}}=M^{\top}B\mathbf{p_{a}^{\varphi}}$, where
the superscript $\varphi\in\\{x,y,z\\}$ denotes the Euclidean coordinate of
$\varphi$ axis. Here, $\mathbf{p_{f}^{\varphi}}$ is a vector comprising the
$\varphi$ axis Euclidean coordinates of all free nodes. Consequently, the
localizability test for node $i$ can be transformed into a more concise
exploration based on the aforementioned linear equations for
$\varphi\in\\{x,y,z\\}$, which share the same matrix $M^{\top}M$. This
dimension reduction also leads to a reduction in computational complexity
during the verification test. Therefore, we can conclude that a node
$i\in\mathcal{V}_{f}$ is localizable if it belongs to a clique of order $5$
and for any $\mathbf{x^{\varphi}}$ satisfying
$M^{\top}M\mathbf{x^{\varphi}}=M^{\top}B\mathbf{p_{a}^{\varphi}}$, it must
hold that $x_{i}^{\varphi}=p_{i}^{\varphi}$, where $x_{i}^{\varphi}$ and
$p_{i}^{\varphi}$ are the corresponding scalars in
$\mathbf{x_{i}}=[x_{i}^{x},x_{i}^{y},x_{i}^{z}]^{\top}$ and
$\mathbf{p_{i}}=[p_{i}^{x},p_{i}^{y},p_{i}^{z}]^{\top}$, respectively.

Now we are ready to establish the necessary and sufficient conditions for
localizability using the barycentric coordinates.

######  Theorem 1.

Supposing that node $i$ belongs to at least one clique of order $5$, then node
$i$ is localizable iff $\mathbf{e_{i}}\bot\textrm{ker}\left(M^{\top}M\right)$,
where $\textrm{ker}(M^{\top}M)$ denotes the kernel of the matrix $M^{\top}M$.

###### Proof.

We start by proving sufficiency. Suppose to the contrary that node $i$ is not
localizable, That is to say, there exists a vector $\mathbf{x^{\varphi}}$ that
satisfies $M^{\top}M\mathbf{x^{\varphi}}=M^{\top}B\mathbf{p_{a}^{\varphi}}$
but does not satisfy $x_{i}^{\varphi}=p_{i}^{\varphi}$. Then it can be
obtained that $M^{\top}M(\mathbf{x^{\varphi}}-\mathbf{p_{f}^{\varphi}})=0$.
That is,
$\mathbf{x^{\varphi}}-\mathbf{p_{f}^{\varphi}}\in\textrm{Ker}(M^{\top}M)$ but
the $i$th component is nonzero. Hence,
$\mathbf{e_{i}}^{\top}\left(\mathbf{x^{\varphi}}-\mathbf{p_{f}^{\varphi}}\right)\neq
0$, which contradicts to the condition
$\mathbf{e_{i}}^{\top}\perp\textrm{ker}(M^{\top}M)$.

Now, we prove necessity. If node $i$ is localizable, then for any vectors
$\mathbf{x^{\varphi}}$ and $\mathbf{y^{\varphi}}$ satisfying

$M^{\top}M\mathbf{x^{\varphi}}=M^{\top}B\mathbf{p_{a}^{\varphi}}$ (12)

and

$M^{\top}M\mathbf{y^{\varphi}}=M^{\top}B\mathbf{p_{a}^{\varphi}},$ (13)

it must hold that $x_{i}^{\varphi}=y_{i}^{\varphi}$, where $x_{i}^{\varphi}$
and $y_{i}^{\varphi}$ are the $i$th components of $\mathbf{x^{\varphi}}$ and
$\mathbf{y^{\varphi}}$. That is to say, for any $w\in\textrm{ker}(M^{\top}M)$,
the $i$th component of $w$ must be zero as otherwise there must exist two
different vectors $\mathbf{x^{\varphi}}$ and $\mathbf{y^{\varphi}}$ satisfying
(12) and (13) such that $x_{i}^{\varphi}\neq y_{i}^{\varphi}$. Therefore,
$\mathbf{e_{i}}\bot\textrm{ker}\left(M^{\top}M\right)$. ∎

###  4.2 Distributed Verification Algorithm for Node Localizability

Building on Theorem 1, we design a distributed algorithm to address Problem 1,
determining whether a generic node in the sensor network is localizable. In
this algorithm, we compute the eigenvalues and eigenvectors of the matrix
$M^{\top}M$ in a distributed fashion, following three steps. First, we design
a subalgorithm to compute local sum of the node based on the barycentric
coordinates only through neighbor sensing and communication. Second, we
propose a subalgorithm that achieves sum consensus among all nodes in the
sensor network within a finite number of iterations. Third, leveraging the
aforementioned algorithms, design our distributed verification algorithm that
solves Problem 1.

####  4.2.1 Local sum

Given an arbitrary matrix $X$ with appropriate dimensions, where the $i$th row
vector or column vector is denoted as $\mathbf{x_{i}}$, this Local Sum (LS)
algorithm is designed to compute $\mathbf{y_{i}}$, the corresponding row or
column vectors of the matrix products $M^{\top}MX$, $\bar{M}^{\top}\bar{M}X$,
or $\bar{M}^{\top}\bar{B}X$, in a distributed manner. A pseudocode for this
algorithm is reported in Subalgorithm 2.

In order to provide a clearer explanation of the algorithm, we recall that the
matrix $M$ is structured in such a way that each row consists of the
barycentric coordinates $a_{ij}$ of free nodes, i.e.
$j\in\mathcal{N}_{i}\cap\mathcal{V}_{f}$, with the convention that
$a_{ii}=-1$, and the remaining elements are zeros. While matrix $B$ only
comprises the barycentric coordinates $a_{ij}$ of anchor nodes, i.e.
$j\in\mathcal{N}_{i}\cap\mathcal{V}_{a}$. Note that the barycentric
coordinates $a_{ij}$ can be computed using the congruent framework by
Algorithm 1. Exploiting these structures, the computation of each row in the
matrix multiplication involving matrix $M$, $\bar{M}$, and $\bar{B}$ can be
reformulated as a calculation of sums obtained by multiplying each $a_{ij}$
with the corresponding vector $\mathbf{x_{i}}$ held by neighboring nodes. This
is possible due to the fact that the elements in each row of $M$, $\bar{M}$,
and $\bar{B}$ only involve the corresponding node and its neighbors. Hence we
name this computation as Local Sum and it can be efficiently performed by
enabling communication solely between nodes and their respective neighbors.

In this way, for each node $i$ that has the knowledge of $\mathbf{x_{i}}$,
after obtaining $\mathbf{x_{j}}$ by communicating with neighboring nodes, the
barycentric coordinates $a_{ij}$ can be utilized to calculate $\mathbf{y_{i}}$
using the LS algorithm in Subalgorithm 2.

On the one hand, the LS algorithm will be applied multiple times in the
Distributed Localizablity Verification Algorithm. Given the
$(n-4)$-dimensional row vector $\mathbf{x_{j}}$ held by neighboring nodes of
node $i$, it enables the local acquisition of $\mathbf{y_{i}}$ (the $i$th row
vector of $M^{\top}MX$) through communication with neighbors. Here, $X$ is an
arbitrary $(n-4)\times(n-4)$ matrix, with $\mathbf{x_{j}}$ as the $j$th row
vector. The whole process could be described as follows. After receiving
$\mathbf{x_{j}}$ through communication with neighbors, the algorithm computes
an intermediate result, consisting with the row vectors of $\xi=MX$. Then,
employing another round of communication through which nodes exchange this
intermediate result, nodes are finally able to compute the desired $i$th row
vector of $M^{\top}MX$, here denoted by $\mathbf{y_{i}}$. This step is key for
the distributed verification of the relation (11), as illustrated at the end
of this section.

On the other hand, the LS Algorithm will also be used later in this paper to
pursue localization. In that application, the input $\mathbf{x_{j}}$ is a
$3\times 1$ column vector denoting the coordinate estimate of node $j$. As a
result, both $\mathbf{\xi_{i}^{r}}$ and $\mathbf{y_{i}}$ are $3\times 1$
column vectors. The LS Algorithm is then used to compute the components of
$\mathbf{y}=\bar{M}^{\top}\bar{M}X$ or $\mathbf{y}=\bar{M}^{\top}\bar{B}X$,
where $X$ is an arbitrary $3(n-4)\times 1$ column vector consisting of several
$3\times 1$ vectors as its components, with the $j$th $3\times 1$ vector as
$\mathbf{x_{j}}$. Since $\bar{M}$ is composed of barycentric coordinates of
free nodes, and $\bar{B}$ consists of barycentric coordinates of anchor nodes,
we can differentiate the computation of $\bar{M}X$ or $\bar{B}X$ by selecting
only free nodes or anchor nodes during the calculation of $\xi$ in line 2.
More specifically, we compute the components of $\mathbf{\xi}=\bar{M}X$ when
$j\in\\{\mathcal{N}_{i}\cup
i\\}\cap\mathcal{V}_{f}\cap\mathchoice{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=5.59721pt]{tetrahedron}}{\includegraphics[height=3.87495pt]{tetrahedron}}_{i}^{r}$
and $\mathbf{\xi}=\bar{B}X$ when $j\in\\{\mathcal{N}_{i}\cup
i\\}\cap\mathcal{V}_{a}\cap\mathchoice{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=6.88889pt]{tetrahedron}}{\includegraphics[height=5.59721pt]{tetrahedron}}{\includegraphics[height=3.87495pt]{tetrahedron}}_{i}^{r}$,
which will be specially noted when calling this subalgorithm. Note that the
superscript $r$ indicates that node $i$ belongs to $r$th clique of order 5,
more details can be found in Section 4.1.

Subalgorithm 2 LS Algorithm

0: Function: $\mathbf{y_{i}}=\textbf{LS}(\mathbf{x_{j}},j\in\mathcal{N}_{i})$

1: Receive $\mathbf{x_{j}}$ from its neighbour $j\in\mathcal{N}_{i}$.

2: Compute  $\begin{gathered}\vdots\\\
\mathbf{\xi_{i}^{r}}=\sum_{j\in\\{\mathcal{N}_{i}\;\cup\;i\\}\;\cap\;\mathchoice{\includegraphics[height=4.82224pt]{tetrahedron}}{\includegraphics[height=4.82224pt]{tetrahedron}}{\includegraphics[height=3.91806pt]{tetrahedron}}{\includegraphics[height=2.71246pt]{tetrahedron}}_{i}^{r}}-a_{ij}^{r}\mathbf{x_{j}}\\\
\vdots\end{gathered}$

3: Receive $a_{ji}^{r}\mathbf{\xi_{j}^{r}}$ from its neighbour
$j\in\mathcal{N}_{i}$.

4: Compute
$\mathbf{y_{i}}=\sum_{j\in\\{\mathcal{N}_{i}\;\cup\;i\\}\;\cap\;\mathcal{V}_{f},\forall
r}-a_{ji}^{r}\mathbf{\xi_{j}^{r}}.$

5: Return $\mathbf{y_{i}}$.

####  4.2.2 Finite-Time K-Max-Consensus Sum

Next, we present the Finite-Time K-Max-Consensus Sum (FKMS) Algorithm, along
with its associated function, the K-Max-Consensus (KMC) Algorithm. These
algorithms are devised to achieve sum consensus among all nodes of the sensor
network. Specifically, the algorithms enable each node to obtain the sum of
all the state of the nodes in the network in a distributed fashion through
communication. In these two algorithms, $ID_{i}$ and $x_{i}$ denote the
identifier and state value of node $i$, and $\delta$ denotes the network
diameter, which we assumed to be known.

######  Remark 3.

If the diameter $\delta$ is unknown, we can calculate it in a finite number of
steps using established algorithms from the literature [34, 35, 36], which
only require an upper bound on the number of nodes that can also be computed
in a distributed fashion (see, e.g., [37, 38, 39]).

The KMC algorithm, described in the pseudocode in Subalgorithm 3, is utilized
to obtain the $K$ maximum state values among all nodes in the sensor network
and their corresponding identifiers. For each node, the entire process
involves continuous comparison between its own $K$ maximum state values and
those held by its neighbors, ultimately obtaining the $K$ maximum state values
and corresponding identifiers. The key lies in the $\text{K}_{\max}$ function,
which sorts all state values of the node and its neighbors by value first and
then by identifier if there are repeated values. Following this procedure,
since the network is connected, each node in the sensor network will finally
select the same $K$ maximum values and corresponding identifiers. This
iterative process requires $\delta$ steps, and the resulting values are stored
in a local variable for each node, denoted by $\bar{\Omega}_{i}$,
$i\in\mathcal{V}$.

Subalgorithm 3 KMC Algorithm

0: Function:
$\bar{\Omega}_{i}=\textbf{KMC}\left(\left(ID_{i},x_{i}\right),\delta\right)$

0: Initialization:

1: $\Omega_{i}(0)=\\{(ID_{i},x_{i})\\}$.

0: Iteration:

1: for $k=1,k\leq\delta,k++$ do

2: Receive $\Omega_{j}(k-1)$ from its neighbor $j\in\mathcal{N}_{i}$.

3:
$\Omega_{i}(k)=\textbf{K}_{\max}\cup_{j\in\\{\mathcal{N}_{i}\;\cup\;i\\}}\Omega_{j}(k-1)$.

4: end for

5: Return $\bar{\Omega}_{i}=\Omega_{i}(k)$.

Then, the FKMS Algorithm (whose pseudocode is reported in Subalgorithm 4) uses
the KMC Algorithm to enable each node to obtain the sum of all the state
values held by all nodes. The overall process is described in the following
three core steps of each iteration. First, each node updates its sum value by
adding the $K$ maximum values. Second, any state value that has already been
included in the sum is assigned a value equal to $-\infty$. Third, the KMC
Algorithm is executed to identify the subsequent set of $K$ maximum values.
These three steps are repeated iteratively until all state values eventually
become equal to $-\infty$. This iterative process guarantees that each node
eventually obtains the same sum value, which is referred to as sum consensus
in this paper.

In Subalgorithm 4, $x_{i}^{tmp}$ and $sum_{i}$ denote the temporary variables
of state value and sum of node $i$, respectively. The functions
$\text{Keys}(\cdot)$ and $\text{Values}(\cdot)$ refer to the sets of
identifiers and their corresponding state values. The final consensus sum
value is denoted by $\bar{sum}$. We initialize
$\bar{\Omega}=\\{(ID_{i},x_{i})\\}$ and $x_{i}^{tmp}=x_{i}$ for each node.
During the iteration, on line 2 we call the Subalgorithm 3 to get the $K$
maximum state values and their identifiers for $\delta$ steps; then, line 3
updates the sum value by adding the nonnegative infinity values of the $K$
maximum values once. In lines 4–5, we remove the nodes that have completed the
accumulation of state values. At last, when all values
$z\in\text{Values}\left(\bar{\Omega}\right)$ are $-\infty$, the algorithm
terminates and every node obtains the consensus sum result.

We want to stress that $K$ in Subalgorithm 4 and Subalgorithm 3 is a value
that considers the tradeoff between memory size and iteration steps: the
greater the value of $K$, the more memory it is used, but the less the steps
are required. Therefore, $K$ can be selected according to the specific
performance of sensors and demand of the application considered.

Subalgorithm 4 FKMS Algorithm

0: Function:
$\bar{sum}=\textbf{FKMS}\left(\left(ID_{i},x_{i}\right),\delta,K\right)$

0: Initialization:

1: $\bar{\Omega}=\\{(ID_{i},x_{i})\\}$.

2: $x_{i}^{tmp}=x_{i}$.

3: $sum_{i}=0$.

0: Iteration:

1: while $z\in\text{Values}\left(\bar{\Omega}\right)>-\infty$ do

2:
$\bar{\Omega}=\textbf{KMC}\left(\left(ID_{i},x_{i}^{tmp}\right),\delta\right)$.

3: $sum_{i}=sum_{i}+\sum_{z\in\text{Values}\left(\bar{\Omega}\right)\text{ and
}z>-\infty}z$.

4: if $ID_{i}\in\text{Keys}\left(\bar{\Omega}\right)$ or $x_{i}^{tmp}=-\infty$
then

5: $x_{i}^{tmp}=-\infty$.

6: end if

7: end while

8: Return $\bar{sum}=sum_{i}$.

######  Remark 4.

The tradeoff between memory size and iteration steps through the parameter $K$
implemented in the FKMS Subalgorithm can also be encapsulated within other
distributed consensus algorithms, including, e.g., average consensus [40].

####  4.2.3 Distributed Localizablity Verification

Finally, we present the Distributed Localizablity Verification, whose goal is
to check the localizability of each node. In accordance with Theorem 1,
considering that eigenvectors corresponding to eigenvalues equal to $0$ reside
in the kernel set of a matrix, we address this localizability verification
problem by conducting distributed computations of the matrix eigenvalues and
eigenvectors of matrix $M^{\top}M$. Specifically, our algorithm, whose
pseudocode is reported in Algorithm 5, computes for the eigenvalues of the
matrix $M^{\top}M$ and calculates the $i$th component of each eigenvector at
node $i$.

In Algorithm 5, the superscript $\top$ indicates it is a row vector and
subscript $s$ indicates the $s$th component of the vector, for example,
$v_{i,s}^{\top}$ denotes the $s$th component of the row vector
$\mathbf{v_{i}}^{\top}$. In the initialization, the initial value
$\mathbf{v_{i}}^{\top}(0)$ of each node is set randomly. During the iteration,
in line 1 we compute the components of $U=M^{\top}MV$ using the LS Algorithm,
where matrix $V=\left[\mathbf{v_{1}},\cdots,\mathbf{v_{n-4}}\right]\top$
denotes the estimate of the matrix formed by the $n-4$ eigenvectors of
$M^{\top}M$ as columns. Then, in line 2, we use the FKMS Algorithm to compute
the $n-4$ eigenvalues using the Rayleigh quotient formula [41, 42]. This step
allows each node to compute the eigenvalues through a distributed computation
process. In line 3, we obtain the consensus matrix $O=U^{\top}U$ by computing
all of its elements, using again the FKMS Algorithm. Then, in lines 4 and 5,
we perform the distributed orthonormalization of $U$, i.e.,
$U^{\top}U=(VR)^{\top}(VR)=R^{\top}R$, where $V$ and $R$ are the QR
factorization of $U$. Once the eigenvalues are deemed converged, each node $i$
has access to $\mathbf{v_{i}}^{\top}$, which represents the $i$th component of
all eigenvectors of $M^{\top}M$. This information is precisely what is needed
to check the localizability verification condition for node $i$ from Theorem
1. For practical applications, we set a maximum number of iterations ${\rm
Iter}_{\max}$ and we reformulate the conditions as $\lambda_{s}({\rm
Iter}_{\max})<\varepsilon_{1}$ and $\left|v_{i,s}^{\top}({\rm
Iter}_{\max})\right|>\varepsilon_{2}$, where $\varepsilon_{1}>0$ and
$\varepsilon_{2}>0$ are small threshold values. Fig. 2 reports a flow chart of
the algorithm.

Algorithm 5 Distributed Localizablity Verification Algorithm

0: Initialization: $(\forall i=1,\cdots,n-4)$ :

1: $\mathbf{v_{i}}^{\top}(0)=$ random initial $(n-4)$ dimensional row vector.

0: Iteration: with $k$ starting at 0 :

1: $\mathbf{u_{i}}^{\top}(k)=$ LS
$\left(\mathbf{v_{j}}^{\top}(k),j\in\\{\mathcal{N}_{i}\cup
i\\}\cap\mathcal{V}_{f}\right)$.

2:
$\lambda_{s}(k)=\frac{\textbf{FKMS}\left(\left(ID_{i},v_{i,s}^{\top}(k)u_{i,s}^{\top}(k)\right),\delta,K\right)}{\textbf{FKMS}\left(\left(ID_{i},v_{i,s}^{\top}(k)v_{i,s}^{\top}(k)\right),\delta,K\right)},\forall
s=1,\cdots,n-4$.

3:
$O(k)=\textbf{FKMS}\left(\left(ID_{i},\mathbf{u_{i}}(k)\mathbf{u_{i}}^{\top}(k)\right),\delta,K\right)$.

4: Solve $R(k)$ from $R^{\top}(k)R(k)=O(k)$.

5: $\mathbf{v_{i}}^{\top}(k+1)=\mathbf{u_{i}}^{\top}(k)R^{-1}(k)$.

6: $k=k+1$.

0: Localizability verification:

1: if $\exists s$ such that $\lambda_{s}({\rm Iter}_{\max})<\varepsilon_{1}$
but $\left|v_{i,s}^{\top}({\rm Iter}_{\max})\right|>\varepsilon_{2}$, then

2: node $i$ is unlocalizable;

3: else

4: node $i$ is localizable.

5: end if

StartInitialize row vector $\mathbf{v_{i}}^{\top}(0)$Compute barycentric
coordinates $a_{ij}$ by Algorithm 1Compute $\mathbf{u_{i}}^{\top}(k)$ by
Subalgorithm 2Compute eigenvalues $\lambda_{s}$ by Subalgorithm 4Check if
$\lambda_{s}$ convergeCompute $O(k)$ by Subalgorithm 4NoSolve $R(k)$Update
$\mathbf{v_{i}}^{\top}(k+1)$Check if $\lambda_{s}<\varepsilon_{1}$
existsYesnode $i$ is localizableNoCheck if
$\mathbf{v_{i,s}}^{\top}>\varepsilon_{2}$YesYesnode $i$ is unlocalizableNo
Figure 2: Flow chart of the Distributed Localizablity Verification Algorithm.

######  Remark 5.

We want to stress that the Distributed Localizability Verification Algorithm
with the KMC and FKMS Algorithms can be used not only to solve Problem 1 in
this setting, but their applicability can also be extended to all localization
problems employing barycentric coordinates; namely, in two or three
dimensional space with various types of measurements. For instance, it can be
adopted before running the localization algorithms in [15, 16, 17] for the
sensor network with unlocalizable nodes. The key lies in modifying the LS
Algorithm according to the barycentric coordinates obtained in the specific
scenario considered. Thus, our Distributed Localizability Verification
Algorithm is a general distributed algorithm for testing the localizability of
each node in the sensor network using barycentric coordinates.

##  5 Finite-Time Localization Algorithm

###  5.1 Distributed Localization Algorithm

Using the Distributed Localizablity Verification Algorithm in Algorithm 5,
each node is able to determine whether it is localizable or not. Then, if node
$i$ is not localizable, all cliques containing node $i$ in the sensor network
are removed, as well as the corresponding linear equations. At this stage, we
define $\mathcal{V}_{z}$ as the set of $n_{z}$ localizable free nodes, forming
a sub-graph $\mathcal{G}_{z}=(\mathcal{V}_{z},\mathcal{E}_{z})$ with
$\mathcal{E}_{z}:={(i,j)\in\mathcal{E}:i,j\in\mathcal{V}_{z}}$. Additionally,
we make the following assumption.

######  Assumption 1.

The sub-graph $\mathcal{G}_{z}=(\mathcal{V}_{z},\mathcal{E}_{z})$ is
connected.

Let $\delta_{z}$ be the diameter of this sub-graph. Under Assumption 1, we
observe that the following inequalities naturally hold:

$n_{z}\leq n-4<n,\quad\delta_{z}\leq n_{z}-1<n.$ (14)

The reduced set of linear equations from (11) that involve only nodes
belonging to $\mathcal{V}_{z}$ can be written as follows:

$\bar{M}_{z}^{\top}\bar{M}_{z}\mathbf{p_{z}}=\bar{M}_{z}^{\top}\bar{B}_{z}\mathbf{p_{a}},$
(15)

where the subscript $z$ denotes the matrix or vector established by
localizable nodes and $\mathbf{p_{z}}$ denotes the Euclidean coordinate
vectors of the localizable node set $\mathcal{V}_{z}$.

Note that the matrix $\bar{M}_{z}^{\top}\bar{M}_{z}$ is symmetric and positive
definite since all unlocalizable nodes are removed from the sensor network.
Therefore, we propose our distributed localization algorithm to solve (15) by
leveraging the conjugate gradient method [43]. In our Distributed Localization
Algorithm (whose pseudocode is reported in Algorithm 6), each node obtains an
initial value $r_{i}(0)$, which is equal to the $i$th component of

$\mathbf{r}(0)\\!=\\!\bar{M}_{z}^{\top}\bar{B}_{z}\mathbf{p_{a}}\\!-\\!\bar{M}_{z}^{\top}\bar{M}_{z}\mathbf{\hat{p}_{z}}(0)\\!=\\!-\bar{M}_{z}^{\top}\begin{bmatrix}\bar{M}_{z}\\!-\\!\bar{B}_{z}\end{bmatrix}\begin{bmatrix}\mathbf{\hat{p}_{z}}(0)\\\
\mathbf{p_{a}}\end{bmatrix},$ (16)

where $\mathbf{\hat{p}_{z}}(0)$ denotes the initial estimate of the Euclidean
coordinates of localizable nodes. During the iteration, in line 1 we use the
LS Algorithm to compute $q_{i}(k)$ for node $i$, which is the $i$th components
of $\mathbf{q}(k)=\bar{M}_{z}^{\top}\bar{M}_{z}\mathbf{v}(k)$. Then, in lines
2 and 5, we update the step sizes $\alpha_{i}(k)$ and $\beta_{i}(k)$. Note
that $\alpha_{i}(k)$ and $\beta_{i}(k)$ are definitely constants consistent
for all nodes, so they can be uniformly denoted as $\alpha(k)$ and $\beta(k)$
and computed as

$\alpha(k)=\frac{\mathbf{r}^{\top}(k)\mathbf{r}(k)}{\mathbf{v}^{\top}(k)\mathbf{q}(k)},\quad\beta(k)=\frac{\mathbf{r}^{\top}(k+1)\mathbf{r}(k+1)}{\mathbf{r}^{\top}(k)\mathbf{r}(k)},$
(17)

in a distributed fashion by means of the FKMS Algorithm. Meanwhile, in lines
3, 4, and 6, we update the estimate $\mathbf{\hat{p}_{i}}(k)$ and parameters
$\mathbf{r_{i}}(k)$ and $\mathbf{v_{i}}(k)$. Note that, the first two
quantities are updated after computing the step $\alpha_{i}(k)$ since they
require the updated values of $\alpha_{i}(k)$, and before computing the step
$\beta_{i}(k)$, for which they are needed. Similar, the latter quantity
($\mathbf{v_{i}}(k)$) is updated at the end of the iteration, using the
updated value of the step $\beta_{i}(k)$, computed in line 5.

Algorithm 6 Distributed Localization Algorithm

0: Initialization: $(\forall i\in\mathcal{V}_{z})$

1: $\mathbf{\hat{p}_{i}}(0)=$ random initial $3$ dimensional column vector.

2:
$\mathbf{\hat{p}_{n-3}}(0)=\mathbf{p_{n-3}},\mathbf{\hat{p}_{n-2}}(0)=\mathbf{p_{n-2}},\mathbf{\hat{p}_{n-1}}(0)=\mathbf{p_{n-1}}$
and $\mathbf{\hat{p}_{n}}(0)=\mathbf{p_{n}}$.

3:
$\mathbf{r_{i}}(0)=-\textbf{LS}\left(\mathbf{\hat{p}_{j}}(0),j\in\\{\mathcal{N}_{i}\cup
i\\}\cap\left(\mathcal{V}_{z}\cup\mathcal{V}_{a}\right)\right)$.

4: $\mathbf{v_{i}}(0)=\mathbf{r_{i}}(0)$.

0: Iteration: with $k$ starting at $0$

1: $\mathbf{q_{i}}(k)=$ LS $\left(\mathbf{v_{j}}(k),j\in\\{\mathcal{N}_{i}\cup
i\\}\cap\mathcal{V}_{z}\right)$.

2:
$\alpha_{i}(k)=\frac{\textbf{FKMS}\left(\left(ID_{i},\mathbf{r_{i}}^{\top}(k)\mathbf{r_{i}}(k)\right),\delta_{z},K\right)}{\textbf{FKMS}\left(\left(ID_{i},\mathbf{v_{i}}^{\top}(k)\mathbf{q_{i}}(k)\right),\delta_{z},K\right)}$.

3:
$\mathbf{\hat{p}_{i}}(k+1)=\mathbf{\hat{p}_{i}}(k)+\alpha_{i}(k)\mathbf{v_{i}}(k)$.

4: $\mathbf{r_{i}}(k+1)=\mathbf{r_{i}}(k)-\alpha_{i}(k)\mathbf{q_{i}}(k)$.

5:
$\beta_{i}(k)=\frac{\textbf{FKMS}\left(\left(ID_{i},\mathbf{r_{i}}^{\top}(k+1)\mathbf{r_{i}}(k+1)\right),\delta_{z},K\right)}{\textbf{FKMS}\left(\left(ID_{i},\mathbf{r_{i}}^{\top}(k)\mathbf{r_{i}}(k)\right),\delta_{z},K\right)}$.

6: $\mathbf{v_{i}}(k+1)=\mathbf{r_{i}}(k+1)+\beta_{i}(k)\mathbf{v_{i}}(k)$.

7: $k=k+1$.

###  5.2 Finite-Time Convergence Analysis

We prove that the Distributed Localization Algorithm in Algorithm 6 solves
Problem 2, i.e., that the positions estimated by the algorithm converge to the
real positions in a finite number of steps. The analysis consists of two
parts. First, we prove that the FKMS Algorithm can obtain the step sizes
$\alpha$ and $\beta$ in finite time. Second, using this result, we prove
finite-time convergence of Algorithm 6.

####  5.2.1 Finite-time computation of the step size

We start by proving the following lemma.

######  Lemma 1.

Under Assumption 1, for any $i\in\mathcal{V}_{z}$ in the sensor network,
$\bar{sum}_{i}$ generated by the FKMS Algorithm in Subalgorithm 4 converges to
the sum of the state values in finite time. Precisely, the algorithm takes no
more than $\delta_{z}\left(\left\lceil\frac{n_{z}}{K}\right\rceil+1\right)$
steps to converge.

###### Proof.

Since the sub-graph is connected by Assumption 1, it is easy to observe that
the KMC Algorithm succeeds within $\delta_{z}$ steps during the first
iteration and the $K$ maximum initial state values and their corresponding
identifiers are obtained by all nodes. We denote them as
$\bar{\Omega}=\textbf{KMC}\left(\left(ID_{i},x_{i}(0)\right),\delta_{z}\right)$.
Note that if state values are repeated, the largest identifiers are selected.
After adding the $K$ maximum initial state values to $sum_{i}$, the algorithm
sets the temporary state values $x_{i}^{tmp}$ of all nodes whose identifier is
contained in $\text{Keys}\left(\bar{\Omega}\right)$ to $-\infty$, aiming to
eliminate their value from subsequent KMC computations. Similar, in the
following iterations, the sets
$\bar{\Omega}=\textbf{KMC}\left(\left(ID_{i},x_{i}^{tmp}\right),\delta_{z}\right)$
are computed within $\delta_{z}$ steps each, where
$\text{Values}\left(\bar{\Omega}\right)$ are the $K$ maximum values of the
initial state values except previous sets of $K$ maximum values and
$\text{Keys}\left(\bar{\Omega}\right)$ are their identifiers.

Hence, in each iteration, each node adds $K$ maximum initial state values to
$sum_{i}$. Once all initial state values have been accumulated, we have
$x_{i}^{tmp}=-\infty$ for all nodes and
$\text{Values}\left(\bar{\Omega}\right)=\\{-\infty,\cdots,-\infty\\}$. At this
time, the algorithm terminates simultaneously for all nodes. This requires a
number of iterations equal to the smallest integer that is larger than or
equal to $\frac{n_{z}}{K}$. Furthermore, an additional step is needed to
ensure that all the $x_{i}^{tmp}$ values are equal to $-\infty$. Therefore, a
total of $\left\lceil\frac{n_{z}}{K}\right\rceil+1$ steps of the main routine
of Subalgorithm 4 are required. Moreover, it should be noted that every node
has the same value for $sum_{i}$ at each step due to the consensus properties.

In conclusion, the KMC Algorithm requires $\delta_{z}$ steps for each
iteration and the FKMS Algorithm needs to be executed no more than
$\left\lceil\frac{n_{z}}{K}\right\rceil+1$ times, yielding the claim. ∎

In the light of Lemma 1, we can draw a conclusion that for any node
$i\in\mathcal{V}_{z}$, the numerator and denominator of $\alpha_{i}$ and
$\beta_{i}$ can be calculated simultaneously in at most
$\delta_{z}\left(\left\lceil\frac{n_{z}}{K}\right\rceil+1\right)$ steps.
Therefore, the step sizes $\alpha$ and $\beta$ can be obtained in a finite
number of steps, and the final results are shown as (17).

####  5.2.2 Finite-time convergence of Algorithm 6

After ensuring that the step size is obtained within a finite number of steps,
we show that the Distributed Localization Algorithm converges in a finite
number of iterations.

First, for all nodes $i$, $i\in\mathcal{V}_{z}$, the discrete-time system in
Algorithm 6 can be written in the following compact matrix

$\displaystyle\mathbf{\hat{p}_{z}}(k+1)=\mathbf{\hat{p}_{z}}(k)+\alpha(k)\mathbf{v}(k),$
(18a)
$\displaystyle\mathbf{r}(k+1)=\mathbf{r}(k)-\alpha(k)\bar{M}_{z}^{\top}\bar{M}_{z}\mathbf{v}(k),$
(18b) $\displaystyle\mathbf{v}(k+1)=\mathbf{r}(k+1)+\beta(k)\mathbf{v}(k),$
(18c) with step sizes
$\displaystyle\alpha(k)=\frac{\mathbf{r}^{\top}(k)\mathbf{r}(k)}{\mathbf{v}^{\top}(k)\bar{M}_{z}^{\top}\bar{M}_{z}\mathbf{v}(k)},$
(18d)
$\displaystyle\beta(k)=\frac{\mathbf{r}^{\top}(k+1)\mathbf{r}(k+1)}{\mathbf{r}^{\top}(k)\mathbf{r}(k)},$
(18e)

by substituting $\mathbf{q}(k)=\bar{M}_{z}^{\top}\bar{M}_{z}\mathbf{v}(k)$
into (17). In the sequel, we denote $A=\bar{M}_{z}^{\top}\bar{M}_{z}$.

Then, before providing the proof, we present a lemma that demonstrates the
orthogonality of the residuals and conjugacy of the search direction,
considering [43].

######  Lemma 2.

The residuals $\mathbf{r}(0),\mathbf{r}(1),\dots$ generated by (18b) are
mutually orthogonal and the direction vectors
$\mathbf{v}(0),\mathbf{v}(1),\dots$ generated by (18c) are mutually conjugate
with respect to the matrix $A=\bar{M}_{z}^{\top}\bar{M}_{z}$.

###### Proof.

The proof of the lemma is equivalent to prove that the following relations
hold

$\displaystyle\mathbf{r}^{\top}(g)\mathbf{r}(f)$ $\displaystyle=0\;(g\neq f),$
(19a) $\displaystyle\mathbf{v}^{\top}(g)A\mathbf{v}(f)$
$\displaystyle=0\;(g\neq f),$ (19b)
$\displaystyle\mathbf{v}^{\top}(g)\mathbf{r}(f)=0\;(g<f),$
$\displaystyle\;\mathbf{v}^{\top}(g)\mathbf{r}(f)=\mathbf{r}^{\top}(g)\mathbf{r}(g),$
(19c)
$\displaystyle\mathbf{r}^{\top}\\!(g)A\mathbf{v}(g)\\!=\\!\mathbf{v}^{\top}\\!(g)A\mathbf{v}(g),$
$\displaystyle\;\mathbf{r}^{\top}\\!(g)A\mathbf{v}(f)\\!=\\!0\;(\\!g\\!\neq\\!l,g\\!\neq\\!f\\!+\\!1\\!),$
(19d)

which could be made by induction. First, it easy to get that the vectors
$\mathbf{r}(0),\mathbf{v}(0)$ and $\mathbf{r}(1)$ satisfy relations (19) due
to

$\displaystyle\mathbf{r}$
$\displaystyle{}^{\top}(0)\mathbf{r}(1)=\mathbf{v}^{\top}(0)\mathbf{r}(1)=\mathbf{v}^{\top}(0)\left(\mathbf{r}(0)-\alpha(0)A\mathbf{v}(0)\right)$
(20)
$\displaystyle=\mathbf{r}^{\top}(0)\mathbf{r}(0)-\alpha(0)\mathbf{v}^{\top}(0)A\mathbf{v}(0)$
$\displaystyle=\mathbf{r}^{\top}(0)\mathbf{r}(0)-\frac{\mathbf{r}^{\top}(0)\mathbf{r}(0)}{\mathbf{v}^{\top}(0)A\mathbf{v}(0)}\left(\mathbf{v}^{\top}(0)A\mathbf{v}(0)\right)=0,$

by (18b) and (18d).

Second, supposing that relations (19) hold for the vectors
$\mathbf{r}(0),\cdots,\mathbf{r}(k)$ and
$\mathbf{v}(0),\cdots,\mathbf{v}(k-1)$, we prove that $\mathbf{v}(k)$
satisfies relations (19). To verify that $\mathbf{v}(k)$ can be adjoined to
this set, it is necessary to show that

$\displaystyle\mathbf{r}^{\top}(g)\mathbf{v}(k)=\mathbf{r}^{\top}(k)\mathbf{r}(k)$
$\displaystyle\quad(g\leq k),$ (21a)
$\displaystyle\mathbf{v}^{\top}(g)A\mathbf{v}(k)=0$ $\displaystyle\quad(g<k),$
(21b)
$\displaystyle\mathbf{r}^{\top}(k)A\mathbf{v}(g)=\mathbf{v}^{\top}(k)A\mathbf{v}(g)$
$\displaystyle\quad(g\leq k,g\neq k-1).$ (21c)

It can be verified that (18e) and (18c) hold for any $k$ iff

$\mathbf{v}(k)=\left(\mathbf{r}^{\top}(k)\mathbf{r}(k)\right)\sum\nolimits_{f=0}^{k}\frac{\mathbf{r}(f)}{\mathbf{r}^{\top}(f)\mathbf{r}(f)}.$
(22)

Then for formula 21, (21a) can be derived at once from (22) and (19a) as
follows

$\begin{array}[]{l}\mathbf{r}^{\top}(g)\mathbf{v}(k)=\mathbf{r}^{\top}(g)\left(\mathbf{r}^{\top}(k)\mathbf{r}(k)\sum_{l=0}^{k}\frac{\mathbf{r}(f)}{\mathbf{r}^{\top}(f)\mathbf{r}(f)}\right)\\\
\,\,\,=\mathbf{r}^{\top}(g)\left(\mathbf{r}^{\top}(k)\mathbf{r}(k)\frac{\mathbf{r}(g)}{\mathbf{r}^{\top}(g)\mathbf{r}(g)}\right)=\mathbf{r}^{\top}(k)\mathbf{r}(k).\end{array}$
(23)

To prove (21b), we use (18b) and find that

$\begin{array}[]{l}\mathbf{r}^{\top}(g+1)\mathbf{v}(k)=\left(\mathbf{r}(g)-\alpha(g)A\mathbf{v}(g)\right)^{\top}\mathbf{v}(k)\\\
\qquad=\mathbf{r}^{\top}(g)\mathbf{v}(k)-\alpha(g)\mathbf{v}^{\top}(g)A^{\top}\mathbf{v}(k),\end{array}$
(24)

which becomes

$\mathbf{r}^{\top}(k)\mathbf{r}(k)=\mathbf{r}^{\top}(k)\mathbf{r}(k)-\alpha(g)\mathbf{v}^{\top}(g)A\mathbf{v}(k)$
(25)

by (21a) when $g<k$, then (21b) holds since $\alpha(g)>0$. In order to
establish (21c), we use (18c) and (21b) to obtain

$\begin{array}[]{l}\mathbf{v}^{\top}(k)A\mathbf{v}(g)=\left(\mathbf{r}(k)+\beta(k-1)\mathbf{v}(k-1)\right)^{\top}A\mathbf{v}(g)\\\
\qquad=\mathbf{r}^{\top}(k)A\mathbf{v}(g)+\beta(k-1)\mathbf{v}^{\top}(k-1)A\mathbf{v}(g)\\\
\qquad=\mathbf{r}^{\top}(k)A\mathbf{v}(g),\end{array}$ (26)

when $g\neq k-1$, which follows that (21c) holds. Therefore, relations (19)
holds for the vectors $\mathbf{r}(0),\mathbf{r}(1),\cdots,\mathbf{r}(k)$ and
$\mathbf{v}(0),\mathbf{v}(1),\cdots,\mathbf{v}(k)$.

Finally, supposing that relations (19) holds for the vectors
$\mathbf{r}(0),\cdots,\mathbf{r}(k)$ and
$\mathbf{v}(0),\cdots,\mathbf{v}(k-1)$, we prove $\mathbf{r}(k+1)$ satisfies
relations (19). With the above results, proving that $\mathbf{r}(k+1)$ can be
adjoined to this set is done by showing that

$\displaystyle\mathbf{r}^{\top}(g)\mathbf{r}(k+1)$ $\displaystyle=0\quad(g\leq
k),$ (27a) $\displaystyle\mathbf{v}^{\top}(g)A^{\top}\mathbf{r}(k+1)$
$\displaystyle=0\quad(g<k),$ (27b)
$\displaystyle\mathbf{v}^{\top}(g)\mathbf{r}(k+1)$ $\displaystyle=0\quad(g\leq
k).$ (27c)

By (18b), we have

$\mathbf{r}^{\top}(g)\mathbf{r}(k+1)=\mathbf{r}^{\top}(g)\mathbf{r}(k)-\alpha(k)\mathbf{r}^{\top}(g)A\mathbf{v}(k).$
(28)

When $g<k$, the terms on the right of (28) are both $0$ and then (27a) holds.
When $g=k$, the right member is still zero

$\begin{array}[]{l}\mathbf{r}^{\top}(k)\mathbf{r}(k)-\alpha(k)\mathbf{r}^{\top}(k)A\mathbf{v}(k)\\\
\quad=\mathbf{r}^{\top}(k)\mathbf{r}(k)-\frac{\mathbf{r}^{\top}(k)\mathbf{r}(k)}{\mathbf{v}^{\top}(k)A\mathbf{v}(k)}\left(\mathbf{r}^{\top}(k)A\mathbf{v}(k)\right)\\\
\quad=\mathbf{r}^{\top}(k)\mathbf{r}(k)-\mathbf{r}^{\top}(k)\mathbf{r}(k)=0,\end{array}$
(29)

by (18d) and (19d). Therefore, (27a) holds. Besides, when $g<k$, using (18b)
again, we have

$\begin{array}[]{l}0=\mathbf{r}^{\top}(k+1)\mathbf{r}(g+1)=\mathbf{r}^{\top}(k+1)\mathbf{r}(g)-\\\
\quad\alpha(g)\mathbf{r}^{\top}(k+1)A\mathbf{v}(g)=-\alpha(g)\mathbf{r}^{\top}(k+1)A\mathbf{v}(g),\end{array}$
(30)

hence (27b) holds. The equation (27c) follows from (27a) and the formula (22)
for $v(g)$, if $g\leq k$, we have

$\mathbf{v}^{\top}(g)\mathbf{r}(k+1)\\!=\\!\Bigg{(}\\!\left(\mathbf{r}^{\top}(g)\mathbf{r}(g)\right)\\!\sum_{f=0}^{g}\frac{\mathbf{r}(f)}{\mathbf{r}^{\top}(f)\mathbf{r}(f)}\Bigg{)}^{\top}\\!\mathbf{r}(k+1)\\!=\\!0.$
(31)

Therefore, (19) hold for the vectors
$\mathbf{r}(0),\mathbf{r}(1),\cdots,\mathbf{r}(k),\mathbf{r}(k+1)$ and
$\mathbf{v}(0),\mathbf{v}(1),\cdots,\mathbf{v}(k)$. ∎

Now, based on Lemma 2, we prove that the system (18) converges in $m$
iterations, in the sense that the estimate $\mathbf{\hat{p}_{z}}$ coincides
with the exact solution $\mathbf{p_{z}}$ of the system of linear equations
(15) after a finite number of iterations.

######  Lemma 3.

For any $\mathbf{\hat{p}_{z}}(0)\in\mathbb{R}^{3n_{z}}$, consider the sequence
$\left\\{\mathbf{\hat{p}_{z}}(k)\right\\}$, $k=1,2,\dots$ generated by (18).
Then, there exists a constant $m\leq 3n_{z}$ such that
$\hat{p}_{z}(k)=\mathbf{p_{z}}$, solution of the linear equation system (15),
for any $k\geq m$.

###### Proof.

Let $m$ be the smallest integer such that the difference between
$\mathbf{\hat{p}_{z}}(0)$ and the solution $\mathbf{p_{z}}$ is in the subspace
spanned by $\mathbf{v}(0),\mathbf{v}(1),\cdots,\mathbf{v}(m-1)$. Due to the
fact that $A=\bar{M}_{z}^{\top}\bar{M}_{z}\in\mathbb{R}^{3n_{z}\times 3n_{z}}$
and $\mathbf{\hat{p}_{z}}\in\mathbb{R}^{3n_{z}}$, the dimension of the
subspace must be less than or equal to $3n_{z}$. Hence, $m\leq 3n_{z}$. Since
the vectors $\mathbf{v}(0),\mathbf{v}(1),\cdots,\mathbf{v}(m-1)$ are linearly
independent according to Lemma 2, we choose scalars $\mu(0),\cdots,\mu(m-1)$
such that we can write

$\mathbf{p_{z}}=\mathbf{\hat{p}_{z}}(0)+\mu(0)\mathbf{v}(0)+\cdots+\mu(m-1)\mathbf{v}(m-1).$
(32)

Then, by substituting (32) into (16), we get

$\begin{array}[]{lll}\mathbf{r}(0)&=&b-A\mathbf{\hat{p}_{z}}(0)=A(\mathbf{p_{z}}-\mathbf{\hat{p}_{z}}(0))\\\
&=&\mu(0)A\mathbf{v}(0)+\cdots+\mu(m-1)A\mathbf{v}(m-1),\end{array}$ (33)

with $b=\bar{M}_{z}^{\top}\bar{B}_{z}\mathbf{p_{a}}$. Next, using Lemma 2, we
compute

$\begin{array}[]{l}\mathbf{v}^{\top}(k)\mathbf{r}(0)=\mathbf{v}^{\top}(k)\big{(}\mu(0)A\mathbf{v}(0)+\cdots+\mu(m-1)\cdot\\\
\qquad
A\mathbf{v}(m-1)\big{)}=\mu(k)\mathbf{v}^{\top}(k)A\mathbf{v}(k),\end{array}$
(34)

and then obtain

$\mu(k)=\frac{\mathbf{v}^{\top}(k)\mathbf{r}(0)}{\mathbf{v}^{\top}(k)A\mathbf{v}(k)}=\frac{\mathbf{r}^{\top}(k)\mathbf{r}(k)}{\mathbf{v}^{\top}(k)A\mathbf{v}(k)}.$
(35)

So far, we find that $\alpha(k)=\mu(k)$, and hence that
$\mathbf{p_{z}}=\mathbf{\hat{p}_{m}}$, which yields the claim. ∎

Finally, we prove that Algorithm 6 solves Problem 2.

######  Theorem 2.

For any $\mathbf{\hat{p}_{i}}(0)\in\mathbb{R}^{3}$, $i\in\mathcal{V}_{z}$, the
estimate $\mathbf{\hat{p}_{i}}(k)$ generated by the Distributed Localization
Algorithm in Algorithm 6 converges to the absolute position $\mathbf{p_{i}}$
in finite time. Specifically, it takes no more than
$3n_{z}\left(2\delta_{z}\left(\left\lceil\frac{n_{z}}{K}\right\rceil+1\right)\right)$
iterations to converge.

###### Proof.

According to Lemma 1, the step sizes $\alpha_{i}$ and $\beta_{i}$ can be
obtained in at most
$\delta_{z}\left(\left\lceil\frac{n_{z}}{K}\right\rceil+1\right)$ iterations,
Therefore, running the iteration in Algorithm 6 once requires a total of
$2\delta_{z}\left(\left\lceil\frac{n_{z}}{K}\right\rceil+1\right)$ iterations.
Then, by applying the results of Lemma 3, we conclude that the bound on the
convergence of Algorithm 6 is given by
$3n_{z}\left(2\delta_{z}\left(\left\lceil\frac{n_{z}}{K}\right\rceil+1\right)\right)$
iterations. ∎

######  Corollary 1.

We can establish a conservative bound on the number of steps needed for
convergence of the Distributed Localization Algorithm in terms of the total
number of nodes of the network $n$, as being less than
$3n\left(2n\left(\left\lceil\frac{n}{K}\right\rceil+1\right)\right)$.

###### Proof.

This comes directly from Theorem 2 and (14). ∎

######  Remark 6.

Here, we provide a theoretical bound on the number of steps in Algorithm 6.
However, in practical scenarios, due to the presence of the rounding errors,
it is possible that a few additional steps may be needed.

##  6 Simulations

To validate our algorithms and test their effectiveness, we present a set of
numerical simulations performed on two case studies of sensor networks of
different size.

###  6.1 Case Study I

In the first case study, we consider a sensor network with $n=50$ nodes
consisting of four anchor nodes (selected at random) and $46$ free nodes. Each
node of the network is located in the three-dimensional space with each side
of length $100$m. Inspired by practical implementations [44, 45, 46], we
establish that sensors can communicate and take relative measurements if they
are within a certain radius. Here, we set such a critical radius at the value
of $50$m. Hence we generate the edges of the sensing and communication
topology according to this rule, that is,
$(i,j)\in\mathcal{E}\iff\|\mathbf{p_{i}}-\mathbf{p_{j}}\|\leq 50$m.

The configuration and the sensing and communication topology of the sensor
network are shown in Fig. 3. Using the filtering process designed in Algorithm
5, we identified three unlocalizable nodes in the sensor network (in red in
Fig. 3), which are excluded from the localization process.

Figure 3: Configuration and topology of the sensor network for Case Study I.
Anchor nodes are denoted in green, unlocalizable nodes (detected by Algorithm
5) are in red, and localizable nodes in blue.

Then, we run Algorithm 6 to estimate the positions of the remaining $43$
localizable free nodes, starting from initial estimates picked uniformly at
random in the domain $100\text{m}\times 100\text{m}\times 100$m. Fig. 4
illustrates the estimated positions at the end of the iterations (in red),
i.e., after 5,369 steps (performed in approximately 18s on a 2.5 GHz 8-Core
Intel Core i7-11700 computer), compared to the exact positions (in blue).
Consistent with our theoretical guarantees, the estimates for all localizable
nodes converge to their real positions. We also illustrate a sample trajectory
of coordinate estimates for a single node in Fig. 4. The trajectory shows how
the estimate rapidly converges to the real position of the node, demonstrating
the performance of our algorithm.

Figure 4: Output of our localization algorithm compared to the absolute
positions for Case Study I. The blue circles denote the real absolute position
and the red asterisks denote the final estimated position. The plot also
depicts a sample trajectory: the initial estimate is represented by a grey
square, the estimates at each 5 iterations by orange triangles.

Now, we perform a comparison of our distributed localization algorithm
(Algorithm 6) with the state-of-the-art algorithms proposed in the literature.
In particular, we consider the Jacobi Under Relaxation Iteration algorithm
(JU) from [47] and the Richardson Iteration algorithm (RI), proposed in [15,
16, 17]. In Fig. 5, we report the results of our comparison. In particular,
the plot shows how the estimation error ratio
$\|\mathbf{\hat{p}_{z}}(k)-\mathbf{p_{z}}\|/\|\mathbf{\hat{p}_{z}}(0)-\mathbf{p_{z}}\|$
obtained using our Algorithm 6 (denoted as CG) compared to the same quantity
computed for the other two algorithms under the same settings (real positions
and initial estimates). From this comparison, we note that, after a short
transient, the distributed localization algorithm proposed in this paper
outperforms the other two, making a significant enhancement in the convergence
rate. Moreover, it eventually allows to determine the exact locations of all
nodes in a finite number of steps as guaranteed by Theorem 2.

Figure 5: Evolution of the estimation error ratio using Algorithm 6 (red),
compared to JU [47] (blue) and RI algorithms [17] (green) for Case Study I.

###  6.2 Case Study II

Finally, we perform a set of simulations on a larger-scale network to verify
the scalability of our algorithms. Specifically, we consider a scenario in
which $n=1,000$ sensors are placed in the same $100\text{m}\times
100\text{m}\times 100$m three-dimensional space, with their positions set at
random, and edges added if two sensors are within $20$m of radius. As shown in
Fig. 6, Algorithm 5 can successfully identify $2$ unlocalizable nodes and,
then, Algorithm 6 allows to exactly determine the absolute positions of all
the remaining $994$ free nodes in finite time.

Figure 6: Output of our localization algorithm compared to the absolute
positions for Case Study II. The blue circles denote the real absolute
position and the red asterisks denote the final estimated position.

Similar to the previous case study, we compared the estimation error ratio of
our algorithm with the other two algorithms from the state-of-the-art
literature. The results, reported in Fig. 7, show that as the number of nodes
and network diameter increase, the performances of Algorithm 6 scales well. In
fact, even though computational effort needed to estimate the exact positions
increases, we observe that the convergence steps remain order of magnitude
smaller than the one needed for the other two algorithms. In addition, the
number of steps can also be reduced at the cost of allocating more memory to
the solver by increasing the value of the parameter $K$ in the FKMS Algorithm,
through the tradeoff between memory size and iteration steps discussed at the
end of Section 5.

Figure 7: Evolution of the estimation error ratio using our algorithm (red),
compared to JU [47] (blue) and RI algorithms [17] (green) for Case Study II.

##  7 Conclusion

We studied the distributed localization problem for three-dimensional sensor
networks with range measurements. First, utilizing barycentric coordinates, we
proposed a distributed localizability verification algorithm to identify which
nodes are unlocalizable. Second, building on a conjugate gradient method, we
proposed an efficient distributed localization algorithm, which is able to
determine the location of all localizable nodes in finite time. Third,
numerical simulations were offered to demonstrate the performance of our
algorithm compared to the state-of-the-art.

The results presented in this paper pave the way for several avenues of future
research. First, real-world measurements and information exchange are often
subject to noises. The study of the performance of our distributed algorithms
in the presence of noises is of paramount importance for assessing their
applicability in real-world scenarios. Second, an interesting future research
direction is to improve the performance of our algorithm, designing
simultaneous localizability verification and localization. Third, to extend
the applicability of our methods, our algorithms should be augmented with the
design of ad-hoc methods to determine the positions of unlocalizable sensors.
Fourth, the methodologies presented in this paper can be extended to different
localization settings. In particular, in the process of solving the
localization problem we designed a general finite-time sum consensus
algorithm. Such an algorithm can be employed to effectively solve other
problems, in which a consensus output should be computed in finite time.

## Acknowledgment

This work was partially supported by National Natural Science Foundation of
China, under Grant No. 62173118; Shenzhen Key Laboratory of Control Theory and
Intelligent Systems, under grant No. ZDSYS20220330161800001; and FAIR — Future
Artificial Intelligence Research, and received funding from the European Union
Next-GenerationEU (PIANO NAZIONALE DI RIPRESA E RESILIENZA (PNRR) — MISSIONE 4
COMPONENTE 2, INVESTIMENTO 1.3 – D.D. 1555 11/10/2022, PE00000013).

## References

  * [1] N. Patwari, J. N. Ash, S. Kyperountas, A. O. Hero, R. L. Moses, and N. S. Correal, “Locating the nodes: Cooperative localization in wireless sensor networks,” _IEEE Signal Process. Mag._ , vol. 22, no. 4, pp. 54–69, 2005\.
  * [2] A. H. Sayed, A. Tarighat, and N. Khajehnouri, “Network-based wireless location: Challenges faced in developing techniques for accurate wireless location information,” _IEEE Signal Process. Mag._ , vol. 22, no. 4, pp. 24–40, 2005.
  * [3] J. R. Lowell, “Military applications of localization, tracking, and targeting,” _IEEE Wirel. Commun._ , vol. 18, no. 2, pp. 60–65, 2011.
  * [4] B. Bayat, N. Crasta, A. Crespi, A. M. Pascoal, and A. Ijspeert, “Environmental monitoring using autonomous vehicles: a survey of recent searching techniques,” _Curr. Opin. Biotechnol._ , vol. 45, pp. 76–84, 2017.
  * [5] Z. Lin, L. Wang, Z. Han, and M. Fu, “Distributed formation control of multi-agent systems using complex laplacian,” _IEEE Trans. Autom. Control_ , vol. 59, no. 7, pp. 1765–1777, 2014.
  * [6] A. El-Rabbany, _Introduction to GPS: The Global Positioning System_. Artech House, 2002.
  * [7] R. M. Buehrer, H. Wymeersch, and R. M. Vaghefi, “Collaborative sensor network localization: Algorithms and practical issues,” _Proc. IEEE_ , vol. 106, no. 6, pp. 1089–1114, 2018.
  * [8] B. Hendrickson, “The molecule problem: Exploiting structure in global optimization,” _SIAM J. Optim._ , vol. 5, no. 4, pp. 835–857, 1995.
  * [9] J. Aspnes, T. Eren, D. K. Goldenberg, A. S. Morse, W. Whiteley, Y. R. Yang, B. D. Anderson, and P. N. Belhumeur, “A theory of network localization,” _IEEE Trans. Mob. Comput._ , vol. 5, no. 12, pp. 1663–1678, 2006.
  * [10] G. Mao, B. Fidan, and B. D. Anderson, “Wireless sensor network localization techniques,” _Comput. Netw._ , vol. 51, no. 10, pp. 2529–2553, 2007.
  * [11] G. Jing, C. Wan, and R. Dai, “Angle-based sensor network localization,” _IEEE Trans. Autom. Control_ , vol. 67, no. 2, pp. 840–855, 2021.
  * [12] U. Helmke and B. D. Anderson, “Equivariant morse theory and formation control,” in _51st Annu. Allerton Conf. Commun. Control Comput._ , 2013, pp. 1576–1583.
  * [13] U. A. Khan, S. Kar, and J. M. Moura, “Distributed sensor localization in random environments using minimal number of anchor nodes,” _IEEE Trans. Signal Process._ , vol. 57, no. 5, pp. 2000–2016, 2009.
  * [14] Y. Diao, M. Fu, Z. Lin, and H. Zhang, “A sequential cluster-based approach to node localizability of sensor networks,” _IEEE Trans. Control Netw. Syst._ , vol. 2, no. 4, pp. 358–369, 2015.
  * [15] Y. Diao, Z. Lin, and M. Fu, “A barycentric coordinate based distributed localization algorithm for sensor networks,” _IEEE Trans. Signal Process._ , vol. 62, no. 18, pp. 4760–4771, 2014.
  * [16] P. Cheng, T. Han, X. Zhang, R. Zheng, and Z. Lin, “A single-mobile-anchor based distributed localization scheme for sensor networks,” in _35th Chin. Control Conf._ , 2016, pp. 8026–8031.
  * [17] T. Han, Z. Lin, R. Zheng, Z. Han, and H. Zhang, “A barycentric coordinate based approach to three-dimensional distributed localization for wireless sensor networks,” in _13th IEEE Int. Conf. Control Autom._ , 2017, pp. 600–605.
  * [18] S. Zhao and D. Zelazo, “Localizability and distributed protocols for bearing-based network localization in arbitrary dimensions,” _Automatica_ , vol. 69, pp. 334–341, 2016.
  * [19] Z. Lin, T. Han, R. Zheng, and M. Fu, “Distributed localization for 2-D sensor networks with bearing-only measurements under switching topologies,” _IEEE Trans. Signal Process._ , vol. 64, no. 23, pp. 6345–6359, 2016.
  * [20] X. Li, X. Luo, and S. Zhao, “Globally convergent distributed network localization using locally measured bearings,” _IEEE Trans. Control Netw. Syst._ , vol. 7, no. 1, pp. 245–253, 2019.
  * [21] K. Cao, Z. Han, Z. Lin, and L. Xie, “Bearing-only distributed localization: A unified barycentric approach,” _Automatica_ , vol. 133, p. 109834, 2021.
  * [22] P. Barooah and J. P. Hespanha, “Estimation on graphs from relative measurements,” _IEEE Control Syst._ , vol. 27, no. 4, pp. 57–74, 2007.
  * [23] Z. Lin, M. Fu, and Y. Diao, “Distributed self localization for relative position sensing networks in 2-D space,” _IEEE Trans. Signal Process._ , vol. 63, no. 14, pp. 3751–3761, 2015.
  * [24] Z. Lin, Z. Han, and M. Cao, “Distributed localization for multi-robot systems in presence of unlocalizable robots,” in _59th IEEE Conf. Decis. Control._ , 2020, pp. 1550–1555.
  * [25] L. Chen, “Triangular angle rigidity for distributed localization in 2D,” _Automatica_ , vol. 143, p. 110414, 2022.
  * [26] L. Chen, K. Cao, L. Xie, X. Li, and M. Feroskhan, “3-D network localization using angle measurements and reduced communication,” _IEEE Trans. Signal Process._ , vol. 70, pp. 2402–2415, 2022.
  * [27] Z. Lin, T. Han, R. Zheng, and C. Yu, “Distributed localization with mixed measurements under switching topologies,” _Automatica_ , vol. 76, pp. 251–257, 2017.
  * [28] X. Fang, X. Li, and L. Xie, “3-D distributed localization with mixed local relative measurements,” _IEEE Trans. Signal Process._ , vol. 68, pp. 5869–5881, 2020.
  * [29] ——, “Angle-displacement rigidity theory with application to distributed network localization,” _IEEE Trans. Autom. Control_ , vol. 66, no. 6, pp. 2574–2587, 2021.
  * [30] A. F. Möbius, _Der Barycentrische Calcul_. Verlag von Johann Ambrosius Barth, 1827.
  * [31] H. Ping, Y. Wang, X. Shen, D. Li, and W. Chen, “On node localizability identification in barycentric linear localization,” _ACM Trans. Sens. Netw._ , 2022.
  * [32] A. Singer and M. Cucuringu, “Uniqueness of low-rank matrix completion by rigidity theory,” _SIAM J. Matrix Anal. Appl._ , vol. 31, no. 4, pp. 1621–1641, 2010.
  * [33] T. Eren, O. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. Anderson, and P. N. Belhumeur, “Rigidity, computation, and randomization in network localization,” in _IEEE 23rd INFOCOM_ , vol. 4, 2004, pp. 2673–2684.
  * [34] P. S. Almeida, C. Baquero, and A. Cunha, “Fast distributed computation of distances in networks,” in _51st IEEE Conf. Decis. Control._ , 2012, pp. 5215–5220.
  * [35] D. Peleg, L. Roditty, and E. Tal, “Distributed algorithms for network diameter and girth,” in _Automata, Languages, and Programming_ , 2012, pp. 660–672.
  * [36] G. Oliva, R. Setola, and C. N. Hadjicostis, “Distributed finite-time calculation of node eccentricities, graph radius and graph diameter,” _Syst. Control Lett._ , vol. 92, pp. 20–27, 2016.
  * [37] D. Varagnolo, G. Pillonetto, and L. Schenato, “Distributed statistical estimation of the number of nodes in sensor networks,” in _49th IEEE Conf. Decis. Control._ , 2010, pp. 1498–1503.
  * [38] ——, “Distributed cardinality estimation in anonymous networks,” _IEEE Trans. Autom. Control_ , vol. 59, no. 3, pp. 645–659, 2013.
  * [39] S. Zhang, C. Tepedelenlioğlu, M. K. Banavar, and A. Spanias, “Distributed node counting in wireless sensor networks in the presence of communication noise,” _IEEE Sens. J._ , vol. 17, no. 4, pp. 1175–1186, 2016\.
  * [40] L. Zino, B. Barzel, and A. Rizzo, “Network science and automation,” in _Springer Handbook of Automation_ , S. Y. Nof, Ed. Cham: Springer International Publishing, 2023, pp. 251–274.
  * [41] R. A. Horn and C. R. Johnson, _Matrix Analysis_. Cambridge University Press, 1985.
  * [42] B. N. Parlett, _The Symmetric Eigenvalue Problem_. SIAM, 1998.
  * [43] M. R. Hestenes and E. Stiefel, “Methods of conjugate gradients for solving linear systems,” _J. Res. Natl. Bur. Stand._ , vol. 49, no. 6, p. 409, 1952\.
  * [44] D. Niculescu and B. Nath, “Ad Hoc positioning system (APS) using AOA,” in _22nd IEEE INFOCOM_ , vol. 3, 2003, pp. 1734–1743.
  * [45] Y. Zhang, W. Liu, Y. Fang, and D. Wu, “Secure localization and authentication in ultra-wideband sensor networks,” _IEEE J. Sel. Areas Commun._ , vol. 24, no. 4, pp. 829–835, 2006.
  * [46] J. Vetelino and A. Reghu, _Introduction to Sensors_. CRC Press, 2017.
  * [47] Y. Xia, C. Yu, and C. He, “An exploratory distributed localization algorithm based on 3D barycentric coordinates,” _IEEE Trans. Signal Inf. Process. Netw._ , vol. 8, pp. 702–712, 2022.