Flipping Free Conditions and Their Application in Sparse Network Localization

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 21, NO. 3, MARCH 2022

Haodi Ping, Yongcai Wang*, Deying Li and Tianyuan Sun

School of Information, Renmin University of China, Beijing, 100872

Overview

Inferring network topology via inter-node distance measurements is an important problem. It is challenging when the distance measurements are sparse because the lack of edge constraints may lead to ambiguous realizations that differ greatly from the ground truth. The flipping ambiguities are caused by binary vertex cut sets in 2D and triple vertex cut sets in 3D, which are called separators. This paper investigates conditions on whether the flipping ambiguities caused by these separators can be disambiguated using neighborhood, full graph, and component-level conditions. Accordingly, local flipping-free condition (LFFC), global flipping-free condition (GFFC), and component-based flipping free condition (CFFC) are proposed. Then a disambiguating framework based on a combinatorial application of these conditions is proposed. It detects separators and first disambiguate separators locally by LFFC, which converts the graph to a binary tree, whose leaf nodes are flipping-free components and edges are LFFC unsolvable separators. Then the CFFC condition is further applied to disambiguate LFFC unsolvable separators between components. If k and g separators are disambiguated by LFFC and CFFC respectively, the number of ambiguous solutions for network localization will be reduced by 2kþg times. Finally, the flipping-free components realize node coordinates in their local coordinate systems and a residue- based weighted component stitching algorithm (RWCS) is proposed to iteratively synchronize components’ local coordinates to generate global coordinates of the network. Extensive simulations show the LFFC, CFFC and RWCS frameworks are efficient, which resolve a major portion of flipping ambiguities and greatly improve the localization accuracy than the state of art algorithms in various sparse network settings.

Motivation

This paper studies the disambiguation problem, which is a key challenge in both network localization and graph realization. Localization and realization will be used inter- changeably since the realized structure can be transformed into the global coordinate system by selecting not less than $d-1$$d- 1$ non-collinear nodes as anchors, where $d$$d$ is the space dimension.

Solution uniqueness is a key challenge in graph realization, which requires the graph hasn’t other ambiguous realizations that also satisfy $D$$D$. Note that rigid transformations, i.e., the global rotation, translation, and reflection don’t change the inner structure of a realization. Two realizations $P$$P$ and $P_0$$P_0$ of a graph are said ambiguous if their inter-node distances both satisfy $D$$D$, but $P_0$$P_0$ cannot be rigidly transformed to $P$$P$.

Contributions

• We first propose basic flipping graphs (BFG) in 2D and 3D, which are the minimum size graphs in which flip- ping ambiguity may happen. Then a local flipping free condition (LFFC) in BFGs is proposed, which can infer the exact length of the negative edge in the BFG, so that the flipping ambiguity of the BFG can be disambiguated with high probability. LFFC is a local condi- tion using one-hop neighborhood information. We show the advantages of LFFC than the traditional triangle inequality (TI) condition in resolving more flip- ping cases.

• Then we prove a global flipping free condition (GFFC) in the graph level. It proves that the $d-1$$d-1$ connected generic graphs in ${\mathrm{\Re }}^d$$\Re^d$ are flipping-free for $d\in \{2,3\}$$d\in \{2,3\}$. So in a rigid graph, each $(d+1)$$(d+1)$-connected component is flipping free. Flipping may happen only at the $d$$d$​-vertex cut sets, which are called flipping separators. We further propose a Component-based Flipping Free Condition (CFFC) to determine whether flipping ambiguity may happen at a flipping separator.

• By utilizing CFFC and LFFC in combination, a flipping separator detection, LFFC checking, and non-flipping tree (NC-Tree) construction method is proposed. The algo- rithm starts by finding a flipping separator and checks LFFC on it. If LFFC is TRUE, the flipping ambiguity is eliminated and another flipping separator will be found and be checked. If LFFC is FALSE, the graph is separated into two sub-graphs by the flipping separator. The result of the algorithm partitions the network into a binary tree, called NC-Tree, whose leaf nodes are $(d+1)$$(d+1)$​-connected non-flipping components and edges are unresolvable flipping separators.

• CFFC condition is further applied on the NC-Tree to resolve LFFC unsolvable separators using the multi- hop geometrical condition. If $k$$k$ and $g$$g$ separators are resolved by LFFC and CFFC respectively, the number of ambiguous realizations of the network will be reduced by $2^{k+g}$$2^{k+g}$ times. All feasible realizations can be inferred from the NC-Tree.

• At last, to generate a realization with better tolerance to ranging noises, a Residue-based Weighted Component Stitching (RWCS) algorithm is developed. It first calculates the local coordinates of each non-flipping components in their local coordinate frames. Then the local coordinates are synchronized by iterative rotation and transition until convergence to produce the global coordinates of the graph. We show by extensive simulations that the proposed LFFC, CFFC and RWCS framework resolves flipping ambiguities efficiently and improves the network realization accuracy greatly in sparse networks than the state of art algorithms in various network settings.

Main Algorithms

1. Proposition 1 (Basic Flipping Graph: BFG). A four vertex, five edge component containing a flipping edge as shown in Fig. 2a, and five vertexes, nine-edge component containing a flipping face as shown in Fig. 2b are the simplest rigid graphs that may have flipping ambiguity, i.e., rigid graphs having the least number of vertices and edges that may have flipping ambiguity in ${\mathrm{\Re }}^2$$\Re^2$ and ${\mathrm{\Re }}^3$$\Re^3$ respectively.

2. Main Theories:

3. System Architecture

   An overview of the proposed scheme using a graph of three separators as an instance.

Evaluations

BibTex

xxxxxxxxxx
1
@ARTICLE{PingTMC2022,
2
  author={Ping, Haodi and Wang, Yongcai and Li, Deying and Sun, Tianyuan},
3
  journal={IEEE Transactions on Mobile Computing}, 
4
  title={Flipping Free Conditions and Their Application in Sparse Network Localization}, 
5
  year={2022},
6
  volume={21},
7
  number={3},
8
  pages={986-1003},
9
  keywords={Particle separators;Distance measurement;Mobile computing;Network topology;Synchronization;Optimization;Two dimensional displays;Network localization;negative edges;sparse networks;flipping free condition;tree of non-flipping components;component synchronization},
10
  doi={10.1109/TMC.2020.3015480}}

Acknowledgment

This work was supported in part by the National Natural Science Foundation of China Grant No. 61972404, 61672524, 11671400. The Fundamental Research Funds for the Central University, and the Research Funds of Renmin University of China, 2015030273.