Before giving the details of the proposed optimal flat metric-based localization algorithms in
Section 4 and
Section 5, we introduce briefly the concepts of metric and Gaussian curvature in
Section 3.1, which provide the necessary background knowledge of the algorithms. Specifically, we introduce discrete surface Ricci flow in
Section 3.2, a tool we apply to compute the optimal flat metric that induces a planar localization of a given sensor network with a minimal localization error. We then discuss the condition to find the optimal flat metric and give the optimal flat metric theorem, which serves as the foundation of the proposed algorithms in
Section 3.3.
Table 1 summaries the symbols we use in the paper.
3.1. Discrete Metric and Gaussian Curvature
In the discrete setting, we denote a triangulated surface (or mesh in short) embedded in , consisting of vertices (V), edges (E) and triangle faces (F). Specifically, we denote a vertex with id i; an edge with two ending vertices and ; a triangle face with vertices , and .
Definition 1 (Discrete metric)
. A discrete metric on M is a function on the set of edges, assigning to each edge a positive number , such that all triangles satisfy the triangle inequalities : .
Edge lengths of M define a discrete metric. If M can be embedded in the Euclidean plane , we call its metric a flat metric.
Definition 2 (Discrete Gaussian curvature)
. Denote the corner angle attached to vertex in face and the boundary of M; the discrete Gaussian curvature on is defined as the angle deficit at : We can compute corner angles directly from edge lengths, so the discrete metric solely determines the discrete Gaussian curvature of
M. If
M can be embedded in the plane, it is intuitive and also obvious from Equation (
1) that the flat metric induces zero Gaussian curvatures for all non-boundary vertices.
The well-known Gauss–Bonnet theorem says that the total Gaussian curvature of M is solely determined by its topology:
Theorem 1 (Discrete Gauss–Bonnet theorem)
. Denote b the number of boundaries. Denote the Euler characteristic number of M and . The total Gaussian curvature of M is a topological invariant. It holds as follows: 3.2. Discrete Surface Ricci Flow
Ricci flow was first introduced by Richard Hamilton in his seminal work [
6] in 1982. Suppose
S is a smooth surface with a Riemannian metric
. The Ricci flow deforms the metric
according to the Gaussian curvature
(induced by itself), where
t is the time parameter:
If we replace the metric in Equation (
3) with
, then the Ricci flow can be simplified as:
which states that the metric should change according to the curvature.
The Ricci flow can be easily modified to compute a metric with a user-defined curvature
as the following,
With this modification, the solution metric
can be computed, which induces the curvature
.
Conformal metric deformation preserves infinitesimal circles and the intersection angles among them. Ricci flow defined in Equation (
3) is proven in [
16,
17] to be convergent. The final metric is conformal to the original one. Moreover, at any time
t, the metric
is conformal to the original one
.
Later, Chow and Luo [
18] proved a general existence and convergence theorem for discrete Ricci flow on surfaces.
To briefly introduce the concept of discrete surface Ricci flow, we start from the concept of the circle packing metric given by Thurston in [
19] as shown in
Figure 1. We assign each
a circle and denote
its radius. The radius function is
. The two circles at
and
of edge
intersect with an acute angle, denoted as
and called the weight of
. The edge weight function is then
.
The length
of
can be computed from the circle radii of its two ending vertices
and its weight
from the cosine law:
Definition 3 (Circle packing metric)
. A circle packing metric of a mesh M includes the circle radius function and the edge weight function.
Given a discrete surface, we use circles with finite radii to approximate the infinitesimal circles; conformal deformation of a circle packing metric to approximate continuous metric deformation. Since two circle packing metrics and on the same mesh are conformally equivalent if , a conformal deformation of a circle packing metric only modifies the vertex radii and preserves the intersection angles on the edges.
Denote
,
and
the target and current Gaussian curvatures of
, respectively, and
t the time. The discrete Ricci flow is defined as follows:
Discrete Ricci flow continuously deforms the circle packing metric according to the difference between the current and target Gaussian curvatures in a heat-like diffusion process. Convergence of discrete surface Ricci flow is proven in [
18]. The final circle packing metric induces the one that satisfies the target Gaussian curvatures.
Discrete Ricci flow can be formulated in a variational setting, namely it is a negative gradient flow of a special energy form. We define a mesh
M with edge weight
a weighted mesh, denoted as
. We represent a circle packing metric on
by a vector
and Gaussian curvatures at vertices by the curvature vector
, where
n is the number of vertices. For two arbitrary vertices
and
, the following symmetric relation holds:
Let
be a differential one-form [
20]. The symmetric relation guarantees that the one-form is closed (curl free) in the metric space.
By Stokes theorem, the following integration is path independent and called discrete Ricci energy.
where
is an initial circle packing metric that induces the surface original metric. The discrete Ricci energy has been proven to be strictly convex in [
18]. The global minimum uniquely exists, corresponding to the desired metric
that induces user-defined curvature
. The discrete Ricci flow is a negative gradient flow of the discrete Ricci energy, converging to the global minimum.
Furthermore, the speed of convergence can be estimated by the following formula [
18]:
where
and
are constant; namely, the convergence is exponentially fast.
3.3. Optimal Flat Metric
Analytically, the distortion of the metric at each vertex is given by
. This motivates us to define the total distortion energy as:
where
and
represent the set of target and initial vertex Gaussian curvatures, respectively. The integration is along an arbitrary path from
to the target curvature
. This energy is the Legendre dual to the Ricci energy given in Equation (
8). Therefore, it is also convex, and it has a unique global minimum for a given
.
All of the possible
’s form the admissible metric space, and all of the possible
’s form the admissible curvature space. According to the Gauss–Bonnet theory (Equation (
2)), the total Gaussian curvatures of
M must be
. A curvature vector
is admissible if there exists a metric vector
on
M, which induces
.
Define:
the set of
’s such that the sum of Gaussian curvatures of vertices satisfies the Gauss–Bonnet theorem, and the Gaussian curvature of all interior vertices is zero.
induces the set of all possible flat metrics of
M.
We formulate our problem as:
Among all possible flat metrics of M induced from the set of ’s, we want to find the one introducing the least distortion from the initially estimated curved metric of M.
Theorem 2 (Optimal flat metric theorem)
. The solution to the optimization problem (9) is unique and satisfies: Proof. The distortion energy
is convex. The domain
is a linear subspace of the original domain
. Therefore, the restriction of
on
is still convex; it has a unique global optimum at an interior point. The gradient of the energy is
. At the optimal point, the gradient is orthogonal to
. Assume
, then the normal vector to
is given by
. Therefore, the gradient is along the normal vector. Therefore, Equation (
10) holds. ☐
We set the constant in Equation (
10) as one. We also set the following two conditions for the target metric of discrete Ricci flow: set the target Gaussian curvatures of all interior vertices to zero so that the final metric is a flat one; deform only the metrics of interior vertices during the process of deforming the estimated metric so that the final flat metric is an optimal flat one. We apply discrete Ricci flow to find the target metric. Since discrete Ricci flow is proven in [
18] as a negative gradient flow of a convex shape energy, it is guaranteed to find the optimal flat metric regardless of the step length or initial values.