1 Introduction

In recent years, network localization [1, 2] has become more and more important in a great number of applications emerging from the fields such as mobile ad hoc networking (MANET) [3], wireless sensor networks (WSN) [4], internet of things (IoT) [5] and vehicular communication networks [6]. In the case of collecting data (e.g., temperature levels) from a forest using a WSN, the data could be useless if the accurate locations where they are gathered are not known [7]. Although the global positioning system (GPS) is a popular technique that is widely used in navigation in our daily life, typically its localization accuracy is about 6–10 m [8] and it does not work well in indoor environments or those WSN applications that need higher location accuracy. In fact, even in outdoor applications, since some of the intelligent transportation systems (ITS) services have relatively demanding positioning requirements of 2 m or less, an efficient location information service (LIS) is necessary to get more precise location information [6].

To improve localization accuracy, one efficient way is to deploy as many beacons as needed, whose locations are highly accurate. In this case the first stage of the deployment of a localization systems would involve beacon deployments to provide a network infrastructure for localization of non-beacon-nodes. For example, Apple iBeacons have a range of half a meter. If the deployment of iBeacons can guarantee that there is an iBeacon within half a meter of any point in the scenario, then after the deployment the localization accuracy of mobile nodes can be within a meter.

However, with the number of beacons to be deployed getting bigger and bigger, the deployment of these nodes becomes labor intensive [9, 10], which means the positions of beacons should precisely located first and then configured one by one. Although there are multi-target localization algorithms such as multidimensional scaling (MDS) [11–13] and curvilinear component analysis (CCA) [14, 15], which can be used for beacon deployment, the prerequisite is that the nodes must be uniquely localizable. If the unique network localization cannot be determined, multiple localization solutions may exist. In graph theory, this is a problem of unique realization in which the positions of vertices are determined by edges between them. As shown in Fig. 1, the measured distances between nodes A, B, C, D and D′ are presented as solid lines. The dash line between A and D′ means the distance is within the transmission range of the nodes, and no line between A and D means their distance is beyond the transmission range. According to these constraints of solid lines, D and D′ are two possible solutions and the position of D cannot be determined with only these constraints. This example give a concrete explanation that if the unique network localization cannot be determined, all the localization schemes cannot guarantee the accuracy they claimed and will even lose the feasibility of localization. Therefore the problem of beacon deployment with position auto-configured can be divided into two parts; one is to determine whether a deployment is uniquely localizable, and the other is to use existing schemes to locate all the nodes. The former can be used to determine when the deployment should be finished, and the localization accuracy of the latter has an important impact on further localizations.

Fig. 1
figure 1

D and its mirroring vertex D′ both satisfy the distances constraint denoted by solid lines

Full size image

For the first part of beacon deployment, according to the literature [1, 16], the network should satisfy the constraint of generic global rigidity to guarantee unique localization, which is NP-hard. In graph theory, the problem of finding Euclidean positions for the vertices of a graph is known as the graph realization problem. Saxe showed that finding a realization is strongly NP-hard for the two-dimensional case or higher [17].

In spite of this, Goldenberg et al. [18] found that there may exist uniquely localizable nodes even in networks with non-global rigid grounded graphs. Jackson et al. [19] presented a theoretical investigation of this phenomenon of global linked nodes. Hendrickson [20] reported in his work that in d-dimensional space with a set of n vertices, a framework is rigid if and only if its rigidity matrix has rank exactly equal to S(n, d) where

$$\begin{aligned} S(n,d)=\left\{ \begin{array}{lll} nd-d(d+1)/2 &{}\quad if\,n\ge d\\ n(n-1)/2 &{}\quad otherwise. \end{array}\right. \end{aligned}$$

Trilateration [21] and Wheel [1, 22] are two special categories that can guarantee a network to be uniquely localizable, but the constraints are somewhat strict. The constraints of Bilateration [23] is less strict, but unique localization of Bilateration cannot be guaranteed.

All these studies imply that the generic global rigid constraint can be made less strict, which inspires the idea of this paper. If a special category of topology can be formed with ranging information used effectively, the computational complexity of determining unique localization for beacon deployment could be reduced. We call this class of topology Uniquely Determined Topology, which is shown in Fig. 2. If a deployment is a Uniquely Determined Topology, it should be uniquely localizable. For those deployments which are not within this special category, we can adjust the network topology to comply with a Uniquely Determined Topology using techniques such as extending the transmission range or deploying more nodes in a given area. In the scenarios that beacon deployment can be controlled to some extent, this will be helpful before localization schemes are taken.

Fig. 2
figure 2

New topology category for beacon deployment

Full size image

To achieve this goal, whether a node is within the transmission range of another is useful information that should be taken advantage of. If there is a measurement between two nodes, which means we can use techniques such as TDoA [24–26] to measure the distances between two nodes, they are supposed to be within their transmission range. If there is no measurement between them, then these two nodes are considered to be beyond the transmission range of each other. Here we make the assumption that none of the measurements are Non-Line-of-Sight (NLoS) [27] ones and all the nodes have the same transmission range lower bound. We focus on the transmission range lower bound because in real scenarios the transmission range will not be a idealistic circle, but we can use the lower bound of the transmission range to tell whether a node is within the transmission range of another. For those networks that NLoS should be considered, the goal can be achieved by deploying local maps and then merge them together to form the global one as mentioned in [13].

For the second part of beacon deployment, another contribution of this paper is that using the deployment method proposed in this paper more accurate localization results can be achieved. This is because compared to MDS that uses the shortest path between each two nodes to approximately reconstruct the distance matrix, Uniquely Determined Topology has a feature that distances between multi-hop nodes can be calculated accurately using a simple calculation model as long as the ranging between neighbor nodes is accurate.

The rest of this paper is organized as follows. In Sect. 2, the definition of Uniquely Determined Topology is proposed and detailed constraints are given on how to construct a network to satisfy unique localizability given the transmission range. This lays a solid theoretical foundation on whether a Uniquely Determined Topology is uniquely localizable. Then, the analysis of Uniquely Determined Topology is presented in Sect. 3. In Sect. 4, the determinacy scheme of Uniquely Determined Topology is proposed, which is the core function to determine when the network is uniquely localizable and the deployment should terminate. The computational complexity of the determinacy scheme is also analyzed in this section. The distance calculation model of a Uniquely Determined Topology is proposed in Sect. 5, which contributes to accuracy improvement of the final localization. Section 6 shows the simulation results in 2-dimensional space and Sect. 7 concludes the paper.

2 Uniquely Determined Topology

As mentioned above, one problem addressed in this paper is what constraint should be proposed to form an easily determined network. This section begins with a simple example to give the constraints and then prove the uniqueness theoretically so that the constraints can be extended to the whole network to guarantee unique localizability.

As shown in Fig. 1, there are two possible realizations for the graph, but if we use a constraint to exclude one possibility, then the graph is unique realization under this constraint. Clearly, whether D and A are within the transmission range of each other is such a constraint. In the scenario of LoS, we can conclude that D′ could not be a possible solution because A and D′ is within their transmission range. However, the example of Fig. 3 shows a mirroring vertex D′ for D that both satisfies the distance condition and the transmission range constraint. In the shadowed region there are innumerable examples of such mirroring vertices. Therefore, only the constraint of transmission range is not enough for unique realization.

Fig. 3
figure 3

Only transmission range constraint is not enough for unique localization

Full size image

Therefore, we focus on the constraints in addition to the transmission range. To give concrete definitions and proofs, we use the theory of unique realization as the foundation theory [16, 19, 28].

2.1 Unique realization

Let \(G=(V,E)\) be an undirected graph with the set of vertices V and the set of edges E. A framework in d-dimensional Euclidean space is denoted by (G, p), where p is a function mapping the vertices V into d-dimensional Euclidean space \(p{:}\,V\rightarrow R^{d}.\)

Definition 1

Given the frameworks (G, p) and (G, q) in d-dimensional Euclidean space X, (G, p) and (G, q) are called equivalent in X if the following condition holds:

$$\begin{aligned} \Vert p(u)-p(v)\Vert =\Vert q(u)-q(v)\Vert ,\,\,\forall uv\in E, \end{aligned}$$

where \(\Vert \cdot \Vert\) is the Euclidean Norm.

Definition 2

Given the frameworks (G, p) and (G, q) in d-dimensional Euclidean space X, (G, p) and (G, q) are called congruent in X if the following condition holds:

$$\begin{aligned} \Vert p(u)-p(v)\Vert =\Vert q(u)-q(v)\Vert ,\,\,\forall u,\,\forall v\in V \end{aligned}$$

Definition 3

The framework (G, p) is called a unique realization of G in d-dimensional Euclidean space X if every framework that is equivalent to (G, p) is congruent to (G, p).

Obviously, if a framework (G, p) is a unique realization in X, the relative positions of all the points denoted by \(p(u),u\in V\) can be determined, which means that in d-dimensional Euclidean space X, given beacons that are algebraically independent over the rationals, the network localization problem has a unique solution [28]. A sequence of trilateration extension can be carried out to obtain the generic global rigid graph, and thus can be used to solve the network localization problem [1]. However, the method demands that for each new node added to the graph, there are at least \(d+1\) edges to the vertices earlier in the sequence, which is relatively strict. The following theories show that the number of the edges can be reduced from \(d+1\) to d with the constraint of the transmission range.

2.2 Deployment constraint for unique realization

Whether a node is within the transmission range of another can be sufficiently used to reduce the number of edges added in the sequence of trilateration extension. Before we prove this reduction, the following definitions are predefined.

Definition 4

In a given undirected graph \(G=(V,E)\), the mirroring factor h of G is defined by:

$$\begin{aligned} h(G)=\sum _{u,v\in V}{H(u,v)},H(u,v)=\left\{ \begin{array}{ll} 1,&\quad uv\not \in E \\ 0,& \quad uv\in E \vee u=v \\ \end{array} \right. \end{aligned}$$

Definition 5

Let \(G=(V,E)\) be an undirected graph with \(d+2\) vertices in d-dimensional Euclidean space X. The framework (G, p) is called a unit triangle framework in X if \(h(G)\le 1\) and the coordinates of any \(d+1\) points are algebraically independent over the rationals.

Figure 4 shows two examples of unit triangle frameworks in 2-dimensional Euclidean space. Definition 5 means that in a unit triangle framework, there is at most one edge missing for a complete graph.

Fig. 4
figure 4

Examples of unit triangle frameworks in 2-dimensional Euclidean space

Full size image

Definition 6

In d-dimensional Euclidean space X, a quasi trilateration extension of a graph \(G=(V,E)\) where \(|V|>d\) produces a new graph \(G'\), which is the merging of G and \(\tilde{G}=(\{v,u,w_1,w_2,\ldots , w_d\},\{vw_1,vw_2,\ldots ,vw_d\}\cup \{mn|m,n\in \{u,w_1,w_2,\ldots ,w_d\}\wedge mn\in E\})\), where \(v \not \in V,u,w_i\in V\), and (\(\tilde{G}\), p) is a unit triangle framework in X. \(\tilde{G}\) is called the merging graph.

With Definition 6, a quasi trilateration extension of a graph can be formed by a sequence of extensions as long as the merging graph is a unit triangle framework in X. Figure 5 shows an example in 2-dimensional Euclidean space where the graph formed by vertices ABCE and the corresponding edges is the merging graph.

Fig. 5
figure 5

Quasi trilateration extension of a graph in 2-dimensional Euclidean space

Full size image

Definition 7

In d-dimensional Euclidean space X, the framework (G, p) is called a Uniquely Determined Topology of G in X under condition C, if (G, p) satisfies either of the following conditions:

  1. (1)

    G is a complete graph.

  2. (2)

    (G, p) is a unit triangle framework and a unique realization under the condition C in X.

  3. (3)

    (G, p) is a quasi trilateration extension of \((G',p)\) with the merging graph \((\tilde{G},p),\,(G',p)\) and \((\tilde{G},p)\) are both Uniquely Determined Topologies under condition C.

According to Definition 7, if in every sequential extension of graph G, there is a condition that can determine the merging graph is a unique realization, then (G, p) is a unique realization of G in X under condition C. And if we can find such constraints, the number of the edges can be reduced in each sequential extension of graph G. The reduction can be guaranteed by the following theorem.

Theorem 1

In d-dimensional Euclidean space X, if a framework (G, p) can be produced by a sequence of quasi trilateration extensions from a framework \((G_0,p)\) in which \(G_0\) is a complete graph with \(d+1\) vertices, and in each quasi trilateration extension the merging graph is a Uniquely Determined Topology under a condition C in X, then (G, p) is a unique realization of G under condition C in X.

Proof

  1. (1)

    Since \(G_0\) is a complete graph with d vertices, the framework \((G_0,p)\) is a unique realization of \(G_0\) in X, therefore, the first quasi trilateration extension \((G_1,p)\) is a unit triangle framework and is a unique realization under condition C in X.

  2. (2)

    Suppose \((G_n(V_n,E_n),p)\) denotes the nth quasi trilateration extension and is a unique realization under condition C in X. In the next quasi trilateration extension, let the merging graph be \(\tilde{G}(\tilde{V},\tilde{E}).\) \((\tilde{G},p)\) is also a unique realization of \(\tilde{G}\) under the condition of C, therefore for any framework \((G_{n+1},q)\) that is equivalent to \((G_{n+1},p)\), we have:

    $$\begin{aligned} \Vert p(m)-p(n)\Vert =\Vert q(m)-q(n)\Vert ,\forall mn\in E_n\cup \tilde{E} \end{aligned}$$
    (1)

    Therefore, \((G_{n+1},q)\) is equivalent to \((G_{n+1},p).\)

For the unique realization framework \((\tilde{G},p)\), \((\tilde{G},p)\) is congruent to \((\tilde{G},q)\) under the condition of C, that is:

$$\begin{aligned} \Vert p(m)-p(n)\Vert =\Vert q(m)-q(n)\Vert ,\forall m \forall n\in \tilde{V} \end{aligned}$$

In unit triangle framework \((\tilde{G},p)\), the coordinates of any \(d+1\) points are algebraically independent over the rationals, therefore there exists a unique orthogonal transformation T that satisfies:

$$\begin{aligned} P_1T=Q_1 \end{aligned}$$

in which

$$\begin{aligned} P_1& = \left( p(v)\quad p(w_1)\quad p(w_2) \ldots p(w_{d+1})\right) \\ Q_1& = \left( q(v)\quad q(w_1)\quad q(w_2) \ldots q(w_{d+1})\right) \end{aligned}$$

Here \(v\in \tilde{E}\wedge v\not \in E_n,w_i(i=1,2,\ldots ,d+1)\in E_n.\)

For any vertex \(x(x\ne w_i,i=1,2,\ldots , d+1)\) in \(G_n\), let \(G^*=(V^*,E^*)\), where \(E^*=\{mn|m,n\in V^* \wedge mn\in E_n\}\) and \(V^*=\{x,w_1,w_2,\ldots ,w_{d+1}\}.\) The framework \((G_n,p)\) is a unique realization of G in X concludes that the framework \((G^*,p)\) is congruent to \((G^*,p)\) thus there exists a unique orthogonal transformation \(\tilde{T}\) that satisfies:

$$\begin{aligned} P_2\tilde{T}=Q_2 \end{aligned}$$

where

$$\begin{aligned} P_2& = \left( p(x)\quad p(w_1)\quad p(w_2) \ldots p(w_{d+1})\right) \\ Q_2& = \left( q(x)\quad q(w_1)\quad q(w_2) \ldots q(w_{d+1})\right) \end{aligned}$$

Consider the following two matrices:

$$\begin{aligned} P_0& = \left( p(w_1)\quad p(w_2) \ldots p(w_{d+1})\right) \\ Q_0& = \left( q(w_1)\quad q(w_2) \ldots q(w_{d+1})\right) \end{aligned}$$

Since these \(d+1\) points are algebraically independent over the rationals, the orthogonal transformation is unique, which means \(T=\tilde{T}.\) Hence,

$$\begin{aligned} PT=Q \end{aligned}$$

where

$$\begin{aligned} P& = \left( p(v)\quad p(x)\quad p(w_1)\quad p(w_2) \ldots p(w_{d+1})\right) \\ Q& = \left( q(v)\quad q(x)\quad q(w_1)\quad q(w_2) \ldots q(w_{d+1})\right) \end{aligned}$$

Since orthogonal transformation is isometric, the following can be obtained:

$$\begin{aligned} \Vert p(x)-p(v)\Vert =\Vert q(x)-q(v)\Vert \end{aligned}$$

Hence,

$$\begin{aligned} \Vert p(m)-p(n)\Vert =\Vert q(m)-q(n)\Vert ,\,\,\forall m \forall n\in V_n\cup \tilde{V} \end{aligned}$$
(2)

Notice that \(E_{n+1}=E_n\cup \tilde{E}\) and \(V_{n+1}=V_n\cup \tilde{V}\), therefore by (1), (2), \((G_{n+1},p)\) is a unique realization of \(G_{n+1}\) in X under condition C. The result follows.

Theorem 1 implies that in each quasi trilateration extension, it is not necessarily \(d+1\) edges if the framework (G, p) is a Uniquely Determined Topology of G in X under condition C.

Let (G, p) be a framework in 2-dimensional Euclidean space X and can be produced by a sequence of quasi trilateration extensions from a framework \((G_0,p)\) in which \(G_0\) is a complete graph with 3 vertices. For each merging graph \(\tilde{G}(\tilde{V},\tilde{E})\), in which \(\tilde{V}=\{u,v,w,k\}\) and \(\tilde{E}=\{mn|m,n\in \tilde{V}\wedge mn\in E\}\), denote \(d_{uv}=\Vert p(u)-p(v)\Vert\) and \(r=max(d_{uv},d_{uw},d_{vw},d_{uk},d_{vk})\), constraints that can be adopted for Uniquely Determined Topology are shown in Corollary 1–3.

Corollary 1

(G, p) is a unique realization if for each merging graph \(\tilde{G}(\tilde{V},\tilde{E})\), we have \(\tilde{d}_{kw}\le r\) and \(d_{kw}>r\) where

$$\begin{aligned} \left\{ \begin{array}{l} \tilde{d}_{kw}^2=d_{wu}^2+d_{uk}^2-2d_{wu}d_{wk}\left( cos(\angle wuv)cos(\angle kuv)+sin(\angle wuv)sin(\angle kuv)\right) \\ cos(\angle wuv)=\frac{d_{wu}^2+d_{uv}^2-d_{wv}^2}{2d_{wu}d_{uv}}\\ cos(\angle kuv)=\frac{d_{ku}^2+d_{uv}^2-d_{kv}^2}{2d_{ku}d_{uv}} \end{array}\right. \end{aligned}$$

Proof

In X, for each merging graph \(\tilde{G}(\tilde{V},\tilde{E})\), \((\tilde{G},p)\) is a unit triangle framework, therefore for any framework \((\tilde{G},q)\) that is equivalent to \((\tilde{G},p)\), we have:

$$\begin{aligned} \Vert p(m)-p(n)\Vert =\Vert q(m)-q(n)\Vert ,\,\,\forall mn\in \tilde{E} \end{aligned}$$

If \(kw\not \in \tilde{E}\), there are two possible solutions \(\tilde{d}_{kw}\) and \({d'}_{kw}\) for \(\Vert p(w)-p(k)\Vert\) which are shown in Fig. 6. Here,

$$\begin{aligned} {d'}_{kw}^2=d_{wu}^2+d_{uk}^2-2d_{wu}d_{wk}\left( cos(\angle wuv)cos(\angle kuv)-sin(\angle wuv)sin(\angle kuv)\right) \end{aligned}$$

Recall that \(\tilde{d}_{kw}\le r\) and \(d_{kw}>r\), thus \(d_{kw}\) has a unique solution \({d'}_{kw}>r\), which implies:

$$\begin{aligned} \Vert p(k)-p(w)\Vert =\Vert q(k)-q(w)\Vert \end{aligned}$$

Thus any quasi trilateration extension will produce a Uniquely Determined Topology. Therefore, by Theorem 1 (G, p) is a unique realization of G in X under the given conditions.

Specifically, in 2-dimensional Euclidean space the following corollaries can be proved:

Fig. 6
figure 6

Different solutions of vertex k’s position denoted by p(k) and p′(k)

Full size image

Corollary 2

(G, p) is a unique realization if for each merging graph \(\tilde{G}(\tilde{V},\tilde{E})\), we have:if \(kw\not \in \tilde{E}\), then \(\Delta uvw\) and \(\Delta uvk\) are both acute triangles and \(d_{kw}>r.\)

Proof

In X, if \(kw\not \in \tilde{E}\), for each merging graph \(\tilde{G}(\tilde{V},\tilde{E})\) where \(\tilde{V}=\{u,v,w,k\}\) shown in Fig. 6, suppose w, k are on the same side of line uv. Recall that \(\Delta uvw\) and \(\Delta uvk\) are both acute triangles, by Principle Ramsey, there is at least one obtuse angle in \(\angle ukw\) and \(\angle vwk.\) If \(\angle ukw>\pi /2\), then \(d_{kw}<d_{uw}.\) And if \(\angle vwk>\pi /2\), then \(d_{kw}<d_{vk}.\) The two hypothesis both disagree with the conditions Corollary 2 demands, therefore w, k can only be on the different side of uv, thus \(\tilde{G}\) is a Uniquely Determined Topology and by Theorem 1 (G, p) is a unique realization.

Corollary 3

(G, p) is a unique realization if for each merging graph \(\tilde{G}(\tilde{V},\tilde{E})\), we have:if \(kw\not \in \tilde{E}\), then \(d_{kw}>r\) and \(\angle uwv\ge \pi /2\vee \angle ukv\ge \pi /2.\)

Proof

In X, if \(kw\not \in \tilde{E}\), for each merging graph \(\tilde{G}(\tilde{V},\tilde{E})\) where shown in Fig. 6, suppose w, k are on the same side of line uv. If \(\angle uwv\ge \pi /2\), then:

  1. (1)

    If w is inside \(\Delta uvk\) or k is inside \(\Delta uvw\), then obviously \(d_{kw}<r.\)

  2. (2)

    If w is outside \(\Delta uvk\) and k is outside \(\Delta uvw\) then \(\angle kwv\ge \pi /2\) or \(\angle kwu\ge \pi /2\) which implies \(d_{kw}<d_{vk}\) or \(d_{kw}<d_{uk}\) respectively and further \(d_{kw}<r.\)

The same disagreement appears if \(\angle uwv\ge \pi /2.\) Therefore w, k can only be on the different side of uv, thus \(\tilde{G}\) is a Uniquely Determined Topology and by Theorem 1 (G, p) is a unique realization.

Explanation: In 2-dimensional Euclidean space, there does exist a counter-example scenario which satisfies \(d_{kw}>r\) but fails to guarantee a unique solution of a node’s position. Figure 3 shows such a scenario in which D and its mirroring vertex D′ both satisfy the distance condition and in the filled region there are innumerable examples of such mirroring vertices. Therefore the constraints in Corollary 1–3 are necessary.

3 Analysis of Uniquely Determined Topology

The constraint that Theorem 1 demands can be achieved by means such as adjusting the transmission range of the nodes, deploying redundant nodes and giving a secondary deployment. All these methods will increase the connectivity level of the network, thus raising a problem on whether the constraint is hard to satisfy. The following theorem shows that our constraint is indeed less strict.

Theorem 2

In d-dimensional space (\(d=2,3\)), the connectivity lower bound of a Uniquely Determined Topology with \(n(n>d)\) nodes is:

$$\begin{aligned} \frac{2nd-d^2-d}{n} \end{aligned}$$

Proof

In d-dimensional space (\(d=2,3\)), a Uniquely Determined Topology can be produced by a sequence of quasi trilateration extensions from an initial unit triangle framework. In the initial unit triangle framework, there are \(d+2\) vertices and at least \((d+1)(d+2)/2-1=d(d+3)/2\) edges. During each quasi trilateration extension, at least d edges will be added to the graph, which will totally produce \(d(n-d-2)\) edges. Therefore the average edges of each node is:

$$\begin{aligned} \frac{d(d+3)+2d(n-d-2)}{n} \end{aligned}$$

which implies \((2nd-d^2-d)/n.\)

Theorem 2 reveals that connectivity can be controlled lower than 4 in 2-dimensional space, which is not a strict constraint for the network. Later experiments will show that this connectivity level has no essential impact on the accuracy of localization.

4 Uniquely Determined Topology decision algorithm

With Theorem 1, whether a network has a unique localization can be judged in a computational complexity of polynomial time, which can be adopted easily in deploying beacons in a large wireless sensor network. It gives a feasibility guarantee of all the localization schemes. The following algorithm named Deployment Conditioned Localizable (DCL) is to determine unique localizability of a Uniquely Determined Topology. DCL returns the result whether a network is uniquely localizable in 2-dimensional space.

Deployment Conditioned Localizable (DCL):

Input: edges with the distance measurements of the network.

Output: the boolean result of whether the network is Uniquely Determined Topology or not.

Steps:

  1. (1)

    Make two sets TopologySet and VertexSet. Set TopologySet NULL and let VertexSet be the set of all the vertices of the network. Choose a node A as the starting node.

  2. (2)

    For any triangle with starting node A as one of its vertex, mark the opposite edge of A as extending edge, add the extending edge and the other two edges of the triangle into TopologySet. Delete all the vertices of the edges in TopologySet from VertexSet.

  3. (3)

    While VertexSet is not NULL, choose an extending edge T using breadth-first-search, find every vertex w in VertexSet that is the neighbor vertex of both the vertices of the marked edge of T, if there is a vertex t that is the vertex of some edge in TopologySet, and makes uvwt a Uniquely Determined Topology, then unmark the extending edge of T, add uw and vw as marked edges into TopologySet. Add tw into TopologySet if it is an edge in the input. Delete w from VertexSet. If there is no vertex that can be added into TopologySet, return false.

  4. (4)

    Return true.

In step 2, the time complexity of finding all the triangles is O(n), where n is the number of nodes. In each loop of step 3, at least 1 vertex is deleted from VertexSet, therefore the loop has at most n rounds. In each loop, finding the added vertex will take time complexity of O(n), therefore in step 3, the algorithm has complexity of \(O(n^2).\) Therefore, the total time complexity of DCL is \(O(n^2).\)

Although a network could be uniquely localizable even when DCL returns false, we can focus more on the cases where DCL returns true. With the constraint of network topology, Uniquely Determined Topology can be determined in polynomial time, this can improve the feasibility of most localization schemes. For those cases where DCL returns false, techniques such as enlarging nodes’ transmission range or deploying new nodes in a given area can be adopted to make the networks become Uniquely Determined Topology, avoiding the NP hard problem to determine unique localizability.

5 Distance calculation model of Uniquely Determined Topology

Theorem 1 and its corollaries can be helpful to determine unique localizability before the localization schemes are deployed. Under such circumstances, the nodes’ positions are fixed if there are enough beacons provided. Another feature of such Uniquely Determined Topology is that it provides a way to calculate distances between multi-hop nodes with geometry relations.

Such calculations can be performed during the quasi trilateration extensions. In this process, the network is supposed to meet the conditions of Theorem 1 and distances between multi-hop nodes can be calculated simply by the Law of cosines. In MDS-MAP(p), it is only needed to calculate two-hop distances. The process of the calculation model is shown in Fig. 7.

Fig. 7
figure 7

Distance calculation model

Full size image

In Fig. 7, the distance between A and F can be calculated step by step. The distance AD can be calculated from \(\Delta\)ABC and \(\Delta\)BCD under the condition that whether the value of AD has a unique solution is determined, which is shown in Fig. 7(a). In Fig. 7(b), AE can be calculated from \(\Delta\)ABD and \(\Delta\)BDE, and finally in Fig. 7(c) the distance of AF is calculated. It can also be noticed that using this calculation model, the distance between each pair of nodes can be ultimately obtained, which is helpful to reconstruct distance matrix used in [13] or [15].

6 Simulation results

One core contribution of this paper is to propose a new category of Uniquely Determined Topology, which can be used easily for beacon-node deployment. One important thing for beacon-node deployment is that it should take less computational time complexity to determine whether a network is uniquely localizable or not, this can be achieved by DCL mentioned above. The other is to get accurate locations for beacons. In this section, we will show that using Uniquely Determined Topology and CL-based schemes, the locations of deployed beacons can be more accurate.

An advantage of Uniquely Determined Topology is that distances between multi-hop nodes can be calculated accurately using its distance calculation model. The distance calculation model can be used for trilateration or local distance matrix in MDS-MAP(p). If such calculations is performed during the quasi trilateration extensions, we call this scheme Trilateration with Conditional Localization (TCL). If the distance calculation model is used to reconstruct the local distance matrix in MDS-MAP(P) and CCA using distance calculation model instead of the shortest path, we call the improved schemes Conditional Localization Based Improved schemes [MDS-MAP(P)-CL and CCA-CL for short].

Simulations are carried out in Matlab 7. To further simplify the problem, all the simulations are performed in 2-dimensional space. 5 topologies are deployed in a 500 m \(\times\) 500 m square region, which are shown in Fig. 8.

Fig. 8
figure 8

Five deployments and their localization result with no ranging error

Full size image

In Fig. 8, in order to study the impact of different network shapes, the topologies are deployed as net-shape, O-shape and C-shape, which is shown in Fig. 8(a–c) with 70, 68, 67 nodes and connectivity level 5.11, 5.35, 4.57 respectively. The transmission ranges of these three deployments are set to 70, 70, 60 m. To demonstrate the generality of our algorithm, a random topology with a uniform distribution is deployed which is shown in Fig. 8(d) with 100 nodes, transmission range 80 and connectivity level 6.5. In each of these four deployments, 4 beacons are deployed at the corners of the topology denoted by a triangle. Figure 8(e) illustrates a scenario with 3 beacons deployed inside the topology. In this deployment, there are totally 100 nodes, the transmission range is set to 70 m, and the connectivity level is 5.29. All the to-be-located nodes are denoted by black dots.

6.1 Results on accuracy affected by shapes

Simulations are first carried out by TCL based on the assumption that there should be no ranging errors of estimated distances between neighbor nodes. The results are shown in Fig. 8 with circles representing the estimated localizations. In Fig. 8(a) the node with the id number 57 happens to hold the largest absolute error between the estimated position and the true position, which is \(3.595 \times 10^{-13}\,\hbox {m}\), and the average error of all the nodes is \(1.0003 \times 10^{-13}\,\hbox {m}.\) Absolute errors are the distances between the calculated positions of to-be-located nodes and their true positions, average error is the average of all absolute errors of to-be-located nodes. The localization error of other topologies is in the same level.

All these simulations indicate that the localization accuracy is nearly not affected by the shape of the network or the location of the beacons. Such a result is coherent with our theories on unique realization with Uniquely Determined Topology constraint. It means that as long as the network is a Uniquely Determined Topology, the positions of the to-be-located nodes are definite and the estimations will be accurate. Therefore it is significantly helpful to deploy beacons that can form a Uniquely Determined Topology.

6.2 Results on accuracy impacted by connectivity level

Many localization algorithms such as DVhop and MDS suggest that the accuracy of localization has something to do with the connectivity of the network. That is, the accuracy will apparently improve with the enhancement of connectivity level. In order to illustrate the relationship between accuracy and connectivity level in TCL, we make a comparison through simulations in which the transmission range is altered to generate various connectivity levels. The result is shown in Fig. 9 based on Fig. 8(a).

Fig. 9
figure 9

Accuracy changes little with different connectivity levels

Full size image

It is implied in this simulation that the changes of accuracy are minute when connectivity is above 5.11. Here the connectivity level does not represent the lower bound of connectivity; it is calculated when the transmission range is 70 m. In the topology of Fig. 8(a), when connectivity is smaller than 5, it is not a Uniquely Determined Topology any more. At this point, most localization algorithms will fail or their localization accuracy cannot be guaranteed. Therefore a good way is to enlarge the transmission range or deploy more nodes to make the topology comply with a Uniquely Determined Topology.

6.3 Results on accuracy influenced by estimating errors of distances

It is a fact that estimated distances are not accurate, therefore we model the distance measure as the true distance blurred with Gaussian noise. Assume the true distance is d and range error is \(E_r\), the measured distance is a random value drawing from a normal distribution \(\tilde{d}=d\times (1+N(0,E_r)).\) Here we use calculation model to construct the local distance matrix instead of the shortest path to improve MDS-MAP(P) and CCA.

In this simulation, MDS-MAP(P) is performed without refinements because of two reasons. First, the refinements can also be conducted based on our results, and second, the refinements are more computational expensive. Figure 10 shows the different localization accuracy of the performed schemes based on Fig. 8(a).

Fig. 10
figure 10

Location error affected by estimated error

Full size image

In Fig. 10, when the error of estimated distances is below 5 %, MDS-MAP(P)-CL outperforms the other schemes. Due to the shortest paths adopted, MDS-MAP(P) and CCA cannot get accurate results when estimating distances are accurate, while using distance calculation model, the local distance matrix can be accurately calculated, which will always work when a network is a Uniquely Determined Topology. Given accurate distance matrix, MDS-MAP(P) will get accurate results. Therefore in the scenarios where high location accuracy is required, MDS-MAP(P)-CL is very competitive and techniques such as TDoA [24–26] and magnetic position [29] are all optional ranging techniques.

However, it is very strange that when we use a more accurate calculation model instead of the shortest path in MDS-MAP(P) and CCA, CL-schemes do not perform better when estimated error is above 5 %. This can be explained by the following analysis.

Although we can use calculation model to reconstruct local distance matrix accurately, when we use estimated distances to do the localization, we know nothing of the details of the estimated error and try to minimize the least square distance error:

$$\begin{aligned} \sum _{i,j}{\left( l_{ij}-d_{ij}\right) ^2} \end{aligned}$$
(3)

where \(l_{ij}\) is the estimated distance between node i and j, and \(d_{ij}\) is the true distance.

However, the location error is formulated by the following:

$$\begin{aligned} \sum _i{\sqrt{\sum _j{\left( \tilde{x}_{ij}-x_{ij}\right) ^2}}} \end{aligned}$$
(4)

where \(\tilde{x}_{i}\) is the estimated coordinates of node i, \(x_i\) is the true coordinates.

When estimated error is 10 %, we have performed the simulation for 5 times, the mean result of (3) is 1765 with MDS-MAP(P)-CL and 3958 with MDS-MAP(P). This means that MDS-MAP(P)-CL can get better results to satisfy the distances. But when there is estimate error of these distances, the coordinates that can achieve a minimum of (3) may not necessarily achieve a minimum of (4).

7 Conclusion

In the scenarios such as indoor localization or those WSN applications that need higher location accuracy, deploying more beacons is one efficient way to improve the localization accuracy. The new category of topology named Uniquely Determined Topology proposed in this paper has revealed that a lot of deploying efforts can be saved when ranging information can be used efficiently. One contribution of this paper is that by Theorem 1 and its corollaries the topology of a network can be guaranteed to be a unique realization if it can be formed by a series of quasi trilateration extensions, which means that in d-dimensional space in some cases edges can be reduced from \(d+1\) to d in each extension. This not only means the constraints of determining whether a topology is a unique realization can be made less strict, but also lowers the connectivity lower bound of a unique realization topology in d-dimensional space to \((2nd-d^2-d)/n.\) We also give a judging method DCL to determine whether a deployment is a Uniquely Determined Topology and can be finished, which is efficient enough for deployment because the computational time complexity of DCL is \(O(n^2).\) The other contribution of this paper is that distances between multi-hop nodes can be calculated accurately using distance calculation model of Uniquely Determined Topology, due to their topology feature. Therefore using the distance calculation model instead of the shortest path in MDS or CCA, a more accurate distance matrix can be reconstructed, which makes CL-schemes outperform the other schemes when the error of estimated distances is below 5 %. That means in the scenarios where high location accuracy is required, CL-schemes are very competitive. The analysis is given to explain why CL-schemes do not perform better when estimated error is above 5 %, and a more detailed assessment will be in future work.