IMF: Iterative Max-Flow for Node Localizability Detection in Barycentric Linear Localization

For a network $\mathcal{G=\{V,E,\mathbf{d}\}}$, let $\mathcal{V}$ = $\mathcal{A}\cup\mathcal{F}$ denote the node set, which is composed of $m$ anchor nodes (i.e., $\mathcal{A}=\{v_{m+1},\cdots,v_{m+n}\}$) and $n$ free nodes (i.e., $\mathcal{F}=\{v_{1},\cdots,v_{m}\}$). Locations of anchors are known, denoted by $\mathbf{P}_{\mathcal{A}}=\{\mathbf{p}_{1},\cdots,\mathbf{p}_{m}\}$ while locations of free nodes are unknown, denoted by $\mathbf{P}_{\mathcal{F}}=\{\mathbf{p}_{m+1},\cdots,\mathbf{p}_{m+n}\}$. $\mathbf{d}$ represents the distance matrix among nodes. For a node $v_{i}$, it can obtain the distance $d_{ij}$ to another node $v_{j}$ if $||\mathbf{p}_{i}-\mathbf{p}_{i}||_{2}\leq R$, where $R$ is the perception radius. $(i,j)\in\mathcal{E}$ if $d_{ij}$ can be obtained. The neighbors of $v_{i}$ is represented as $\mathcal{N}_{i}$, $v_{j}\in\mathcal{N}_{i}$ if $(i,j)\in\mathcal{E}$. The problem is to detect which free nodes can be uniquely localized using the anchor and distance constraints when BLL methods are adopted.

Range-based NL algorithms fall into two categories, i.e., NLL and BLL. In NLL, there are a wide range of algorithms to solve $\mathbf{P}_{\mathcal{F}}$ from the model of minimizing the sum square errors[29, 11, 30, 31, 15, 32, 12, 14]. The main defect of NLL is that it does not guarantee global optimality since the optimization model is quadratic. For a detailed introduction to NLL, please refer to reference [14]. In this paper, we focus on BLL algorithms.

An overview of the state-of-the-art for network localizability, node localizability detection conditions and algorithms is summarized in Table I. Overall, the localizability problem has been well researched in NLL except for a necessary and sufficient node localizability condition and the corresponding detection algorithm that guarantee to detect all localizable nodes. The research on localizability in BLL is much lacked. Only the necessary and sufficient condition for BLL network localizability is given in [19]. The testing algorithm for BLL network localizability, conditions and algorithm for BLL node localizability are still open.

To fill the knowledge gap in BLL, this paper proposes:

1) A necessary condition for BLL node localizability.

2) A sufficient condition for BLL node localizability.

3) A testing algorithm for BLL network localizability, and

4) A detection algorithm for BLL localizable nodes.

The necessary and sufficient condition for node localizability is still left as an open problem.

From Lemma 2, a node should have three node-disjoint paths (3P) to anchors in $\mathcal{G^{A}}$ to be BLL-localizable. To make a certain node has 3P to anchors, it is straightforward that it must have at least 3 neighbors in $\mathcal{G^{A}}$. From the perspective of the original graph $\mathcal{G}$, this necessary condition is formulated as follows.

Theorem 1 implies that BLL node localizability requires stronger connectivity for each node. Neighbors in $\mathcal{N}_{i}$ need to be mutually connected to contribute to the BLL-localizability of $v_{i}$. That is, BLL-localizability is theoretically more difficult to be satisfied than NLL-localizability. For example, Yang et. al. have proved that a wheel graph like Fig. 2(a) is global rigid (i.e., NLL-localizable)[27]. But none of these nodes are BLL-localizable since each node’s neighbors are not mutually connected.

From Lemma 2, we derive a sufficient condition for BLL node localizability by recursion.

Theorem 2 implies that the set of BLL-localizable nodes and the set of BLL-unlocalizable nodes should be edge-independent, i.e., the BLL-localizable nodes should have no edge connecting BLL-unlocalizable nodes. Thus, the BLL-localizable nodes can be found by iteratively removing nodes without 3P.

To proceed, we introduce a flow graph $\mathcal{G^{F}}=(\mathcal{V^{F}},\mathcal{E^{F}},\mathcal{C})$ constructed from $\mathcal{G=\{V,E\}}$, where $\mathcal{V}=\mathcal{A}\cup\mathcal{F}$.

• •

  Divide each free node $v_{i}\in\mathcal{F}$ into two copies $\{v_{i}^{in},v_{i}^{out}\}$ and add them to $\mathcal{V^{F}}$. Then, add anchor nodes in $\mathcal{A}$ and an virtual target node $\Omega$ to $\mathcal{V^{F}}$.

• •

  For each $v_{i}\in\mathcal{F}$, add $(v_{i}^{in},v_{i}^{out})$ to $\mathcal{E^{F}}$. For each neighbor $v_{j}\in\mathcal{N}_{i}$, add $(v_{i}^{out},v_{j})$ to $\mathcal{E^{F}}$ if $v_{j}$ is an anchor, add $(v_{i}^{out},v_{j}^{in})$ to $\mathcal{E^{F}}$, otherwise; For each anchor node $v_{i}\in\mathcal{A}$, add $(v_{i},\Omega)$ to $\mathcal{E^{F}}$.

• •

  Assign $\mathcal{C}_{ij}=1$ in the capacity matrix $\mathcal{C}$ if $(v_{i},v_{j})\in\mathcal{E^{F}}$.

Then, we show the equality between the number of disjoint paths (DP) in $\mathcal{G}$ and the Max-Flow in $\mathcal{G^{F}}$.

A case study is shown in Fig. 3. The generated graph $\mathcal{G^{A}}$ of a network $\mathcal{G}$ of 5 nodes is given in Figure 3(a). Its corresponding $\mathcal{G^{F}}$ is in Figure 3(b). The constructed capacity matrix $\mathcal{C}$ is shown in Table II. It is easy to verify the equivalence between the number of disjoint paths in $\mathcal{G^{A}}$ and the max flow in $\mathcal{G^{F}}$. For example, there are five paths from $v_{4}$ to anchors, i.e., $v_{4}\rightarrow v_{1},v_{4}\rightarrow v_{5}\rightarrow v_{1},v_{4}\rightarrow v_{5}\rightarrow v_{2},v_{4}\rightarrow v_{5}\rightarrow v_{3},v_{4}\rightarrow v_{6}\rightarrow v_{3}$. Three of them are node disjoint, i.e., $v_{4}\rightarrow v_{1},v_{4}\rightarrow v_{5}\rightarrow v_{2},v_{4}\rightarrow v_{6}\rightarrow v_{3}$. Using Orlin’s method [40], we can obtain that the max-flow from $v_{4}$ to $\Omega$ in $\mathcal{G^{F}}$ is also three.

Now, whether a network $\mathcal{G}$ is BLL-localizable can be tested by checking $\mathcal{G^{A}}$ using Lemma 3. Algorithm 1 shows the routine. Recall that a network is BLL-localizable means that all the nodes are BLL-localizable. So if any node does not meet the necessary condition in Theorem 1, the network is not BLL-localizable (Line 1-Line 1). Then, if all nodes meet the necessary condition, we construct the generated graph $\mathcal{G^{A}}$ shown as Function construct_generated_graph($\mathcal{G}$) (Line 1-Line 1). Then the flow graph $\mathcal{G^{F}}$ of $\mathcal{G^{A}}$ is constructed using the method in Section IV-A. The max flow is calculated using Orlin’s method [40] (Line 1). In Lemma 2, the BLL network localizability condition requires that each free node should have 3P to anchors in $\mathcal{G^{A}}$, so $\mathcal{G}$ is BLL-localizable if the max-flow from each $v_{i}\in\mathcal{F}$ to $\Omega$ is not less than 3 in $\mathcal{G^{F}}$, BLL-unlocalizable, otherwise (Line 1-Line 1).

Use the graph in Fig. 3 for instance. Let $\bf{DP}^{\mathcal{G_{A}}}_{i\rightarrow\mathcal{A}}$ be the number of disjoint paths from $v_{i}$ to nodes in $\mathcal{A}$ in $\mathcal{G_{A}}$, and $\bf{Max\_Flow}_{i\rightarrow\Omega}^{\mathcal{G^{F}}}$ be the max flow from $v_{i}$ to the virtual node $\Omega$. We can obtain:

Thus, through Algorithm 1, we can conclude that the network in Fig. 3 is not BLL-localizable due to the existence of $v_{6}$.

Detecting the BLL-localizable nodes in a partial localizable network is conducted through Theorem 2, i.e., detecting the nodes that satisfy the Recursive-3DP condition. The routine is shown as the IMF algorithm in Algorithm 2. IMF iteratively removes nodes not having 3P and the corresponding capacities of these nodes in each round. In each round, only the nodes having 3P and the edges among them (denoted by Edge($\cdot$)) are left (Line 2-Line 2). Finally, IMF terminates when no more nodes can be removed (Line 2).

Take Fig. 3 as an example to show the process of IMF. In the first round, $v_{6}$ is removed since $\mathbf{Max\_Flow}_{6\rightarrow\Omega}^{\mathcal{G^{F}}}=2$, then $\mathcal{F}^{*}=\{v_{4},v_{5}\}$; In the second round, $\mathbf{Max\_Flow}_{4\rightarrow\Omega}^{\mathcal{G^{F}}}$ becomes 2 since $v_{6}$ and its corresponding edges are removed. Then, $\mathcal{F}^{*}$ becomes $\{v_{5}\}$; In the third round, $\mathcal{F}^{*}$ does not change since the 3P of $v_{5}$ does not pass through nodes without 3P. So IMF terminates and outputs $\{v_{5}\}$ as the BLL-localizable node set.

In this section, the perception radius $R$ is varied to control the network density (assessed by average node degree). The percentage of anchor nodes (i.e., $|\mathcal{A}|/|\mathcal{V}|$) is also varied. The detection capacity of a certain algorithm is assessed by the percentage of detected localizable nodes $|\hat{\mathcal{F}}^{*}|/|\mathcal{V}|$ (called $\%$ of localizable for brief), where $\hat{\mathcal{F}}^{*}$ is the detected localizable nodes by a certain algorithm.

Fig. 4 shows the percentage of detected localizable nodes of different algorithms under different average degrees and anchor densities. We can obtain the following observations:

• •

  IMF outperforms the other two algorithms in detection capacity under all settings, especially in sparse and anchor-lacking networks.

• •

  It is straightforward that detection algorithms are expected to detect more localizable nodes when there are more anchors. However, only the localizable nodes detected by IMF increase monotonically with the increase of anchor nodes under fixed network density. That is, the detection capacities of TP and TE are additionally affected by the distribution of anchors.

To further show the stable performance of IMF, we visualize the detection result of different algorithms in harsh scenarios, i.e., networks with irregular anchor distribution or networks with holes.

Fig. 5 shows the impact of anchor distribution. It can be seen that TP requires at least three anchors having common neighbors as in Fig. 5 to startup and TE needs at least two anchors having common neighbors as in Fig. 5 to startup. If the startup condition is not satisfied as in Fig. 5, TP and TE fail and detect no localizable nodes. However, IMF can detect most of the localizable nodes, even when anchors do not have any common neighbor.

In some applications, networks may be deployed with holes due to geographical obstacles or deployment requirements. To clarify the effect of holes, we first adjust the anchor distribution to ensure TP and TE can startup as in Fig. 5 and Fig. 5. The results show that even when the startup conditions are met, TP and TE detect fewer localizable nodes than IMF. When anchors have no common neighbors, only IMF works as in Fig. 5. The detailed detection results are given in Table III.

Moreover, Fig. 6 shows the statistical results of repeated experiments. The five figures are statistical results for networks with average degrees {8, 10, 12, 14, 16} respectively. In each figure, 1000 networks are generated randomly following the average node degree and run TP, TE, and IMF respectively. Each network contains 100 nodes and the distributions of the number of detected localizable nodes for TP, TE and IMF are compared using box graph. It can be observed that:

• •

  IMF always detects more localizable nodes than TP and TE, especially in sparse networks. When the average degree is 16, the median value of IMF reaches 97%.

• •

  The median value of TP is 0 under each degree, which means that its startup condition is hard to be satisfied in random networks.