Cooperative Group Localization Based on Factor Graph for Next-Generation Networks

Abstract

In ill-conditioned communication environment, multiple target localization is of important practical significance. The cooperative group localization (CGL) model was firstly put forward, which has verified the effectiveness of localization performance gain and simultaneous multiple target localization in ill conditions. However, there exist two inherent difficulties: the strict demand for CGL topology and the high complexity. By the rational use of information to relax restrictions on topology and by dividing the complex problem into some simple local ones, the factor graph (FG) together with the sum-product algorithm is a perfect candidate for the problems above. In order to solve the two problems, we propose the weighted FG-based CGL (WFG-CGL) algorithm which incorporates the optimal weights based on the information reliability. In order to further reduce the complexity, we propose the low-complexity FG-based CGL (LCFG-CGL) algorithm. The Cramer-Rao lower bound (CRLB) of the localization error in CGL is first derived. Theoretical analysis and numerical results indicate that the proposed algorithms not only perform better in relaxing CGL topology requirement, but also enjoy high localization accuracy under low complexity in comparison with the existing CGL algorithm.

1. Introduction

Wireless localization technologies, which are designated to estimate the position of a mobile terminal (MT), have drawn a lot of attention over the past few decades. Federal Communication Commission (FCC) has mandated the cellular network operators to estimate the position of emergency caller with the error of less than 100 meters in the enhanced 911 (E-911) [1]. In recent years, there are increasing demands for commercial applications to adopt the localization information within their system design, such as the navigation system, the health care system, the wireless sensor network (WSN) [2–4], and the intelligent transportation system (ITS) [5, 6]. Moreover, more and more people rely on the instant localization, which may make the communication services more user-friendly. With the emergent interests in the localization-based services (LBSs), the wireless localization with enhanced accuracy becomes necessary for the applications under different circumstances.

The research of the localization techniques is an important part of wireless localization fields [7]. A variety of wireless localization techniques have been investigated, such as basic localization algorithms and their corresponding Cramer-Rao lower bound (CRLB) analysis [8–10]. CRLB provides a useful means for the analysis of the limits of localization accuracy. CRLB results for localization, based on different types of internode measurements, can be found in [2, 3, 11–15]: the localization error is shown to depend on several elements, in particular on the measurement reliability (which may be impaired by multipath, non-line of sight, synchronization errors, etc.) and the topology of the network.

Most of current academic achievements in localization field focus on the enhancement localization techniques in the well condition. The well condition means that mobile terminal (MT) to be localized has the sufficient signal resources. For example, if one MT can be accurately located by the measurement parameters of time of arrival (TOA), time difference of arrival (TDOA), angle of arrival (AOA), or received signal strength (RSS), the MT connects well with at least three base stations (BSs) and line-of-sight (LOS) propagation paths existing between BSs and MT [16]. Nevertheless, the scenarios with sufficient signal resources do not always happen in real circumstances. Sometimes, the parameter measurements may be corrupted by non-line-of-sight (NLOS) error, or MT can not simultaneously connect with three BSs [9, 16]. These ill conditions with insufficient signal resources can make the accurate localization unrealistic.

The cooperative group localization (CGL), which can achieve the multiple target localization simultaneously, is proposed as an approach to solving the above ill-conditioned localization problem in [17, 18]. The existing research indicates that the CGL scheme not only has higher localization accuracy over the traditional methods in ill conditions, but also can effectively enhance the robustness of localization. However, there also exists two inherent difficulties: (1) the strict demand for CGL topology and (2) the high complexity. According to the rigid graph theory [19], the CGL topology must be global rigidity so as to satisfy the unique solvability. Furthermore, CGL has to face the problem of high complexity, especially with the increasing number of cooperative MTs.

In [20], factor graph (FG) theory is proposed, which can simplify a complex problem into multiple simple sub problems. The optimal or the near-optimal solution can be obtained by solving the sub problems, respectively. According to its feasibility and simplicity, it has been introduced into cellular or sensor network based on measurement parameters TOA, TDOA, AOA, and RSS [21–25] and reaches the good tradeoff between the localization accuracy and complexity. In [26], Wymeersch et al. analyzes the feasibility of FG theory applied into the cooperative localization.

In this paper, we combine FG theory with CGL. The FG-CGL graph can adapt its constitutions and architecture based on the different measurement information, considered as self-organizing. First, a weighted FG-based CGL algorithm (WFG-CGL) is proposed to effectively solve the above problems of strict demand for CGL topology and high complexity in the ill condition. It enhances the accuracy by adopting the different information reliability of BSs and MTs into its formulation. Then, a low-complexity FG-based CGL (LCFG-CGL) algorithm is proposed to further diminish the complexity. Moreover, CRLB analysis is extended to CGL scenarios. Numerical simulation results verify that compared to the existing CGL method, the proposed algorithms can relax CGL topology requirement and provide the high localization accuracy under low complexity. And the important factors for the FG-based CGL algorithms are analyzed based on the simulation results.

The paper is organized as follows. In Section 2, CGL model is introduced. In Section 3, the principles of factor graph and sum-product algorithm are presented. Section 4 proposes WFG-CGL algorithm and LCFG-CGL algorithm. Section 5 completes CRLB analysis of CGL. Section 6 evaluates the performance and the complexity of the proposed algorithms by numerical simulation. Finally, the conclusion is included in Section 7.

2. Mathematical Model of CGL

For the description convenience, take the scenario shown in Figure 1 for example, which presents the principle of CGL in the following sections. In CGL, the conception of the terminal group (TG) is firstly put forward. TG refers to a group of MTs supporting peer-to-peer communication mode in the next-generation communication networks. To represent the most general situation, all MTs are supposed to be the localization unknown nodes, and the relative distances between some certain MT pairs are known. For the next-generation communication networks, the advantages of the cooperation between MTs can be applied widely. As shown in Figure 1, each MT in TG connects with less than three BSs, which can be included in the ill conditions mentioned above.

Figure 1

CGL topology diagram.

The CGL graph $G = (V, E)$ can be divided into three sub-graphs: the first one is BS subgraph $G_{B} = (V_{B}, E_{B})$ , where $V_{B}$ represents the BSs, and $E_{B}$ represents the existing edges between any two vertices of $V_{B}$ ; the second one is TG subgraph $G_{T} = (V_{T}, E_{T})$ , where $V_{T}$ includes all the MTs in TG, and $E_{T}$ represents the distances determined by direct communication among the MTs; the third is cooperative sub-graph $G_{C} = (V_{C}, E_{C})$ , where $V_{C}$ includes the BSs or the cooperative MTs in TG, and $E_{C}$ represents the edges existing between $G_{B}$ and $G_{T}$ . The operator $| • |$ of the sets denotes the number of the elements in a set.

Given the CGL graph, the aim of CGL is to simultaneously solve the positions of all the MTs in TG. However, not all topologies of CGL have unique solvability. The unique solvability means that the positions of MTs in a TG can be located without ambiguity. It can be investigated by the rigid graph theory [19].

3. Factor Graph and Sum-Product Algorithm

3.1. Factor Graph

A factor graph [20] is a bipartite graph that illustrates how a complicated global function with many variables is simplified into the product of several simple local functions. Each local function is a function with few variables. A factor graph has the variable node for each variable, the function node for each local function, and the edge connecting variable node to factor node if and only if the variable is an argument of the function. For example, $f (x_{1}, x_{2}, x_{3}, x_{4}, x_{5})$ is a real-valued function with five variables, which is divided into the product of five local functions $f_{A}, f_{B}, f_{C}, f_{D}$ and $f_{E}$ , as is shown in Figure 2, as follows:

\begin{array}{l} f (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) \\ = f_{A} (x_{1}) \cdot f_{B} (x_{2}) \cdot f_{C} (x_{1}, x_{2}, x_{3}) \cdot f_{D} (x_{3}, x_{4}) \cdot f_{E} (x_{3}, x_{5}) . \end{array}

(1)

Figure 2

An example of factor graph.

3.2. Sum-Product Algorithm

Sum-product algorithm [20] is one of the important algorithms in graphical model, which provides the convenient solution to marginal probability. The algorithm works by the passing messages along the edges between the nodes. There are two types of messages.

With two rules above, information is passed among neighboring nodes. Each variable node modifies its own value according to the received message. After a few times, the information converges. The variable can be estimated according to the product of overall message from its neighboring nodes as follows:

\begin{matrix} SI (x) = \prod_{h \in n (x)} SI (h, x) . \end{matrix}

(2)

4. FG-Based CGL Algorithms

In the following analysis, the positions of several MTs are estimated simultaneously based on TOA measurements. In order to reduce the complexity of the two-dimensional (2D) problem, the problem is divided into two one-dimensional (1D) problems [21], x-coordinate group and y-coordinate group, as illustrated in Figure 3. In Figure 3, $x_{i}$ and $y_{i}$ represent the coordinates for the ith MT; $Δ x_{i, j}$ and $Δ y_{i, j}$ represent the relative distances between the ith MT and the jth BS; $Δ x_{i, j}^{β}$ and $Δ y_{i, j}^{β}$ represent the relative distances between the ith MT and the jth BS after the weight adaptation; $Δ x x_{i, t}$ and $Δ y y_{i, t}$ represent relative distances between the ith MT and the tth cooperative MT; $Δ x x_{i, t}^{β}$ and $Δ y y_{i, t}^{β}$ represent relative distances between the ith MT and the tth cooperative MT after the weight adaptation; ${\hat{d}}_{i, j}$ and ${\hat{l}}_{i, t}$ are the measurement distance from the jth BS to the ith MT, and the distance from the tth cooperative MT to the ith MT; $d_{i, j}$ and $l_{i, t}$ are produced by the Gaussian distribution with the means ${\hat{d}}_{i, j}$ and ${\hat{l}}_{i, t}$ , and with their corresponding variances. The meanings of function nodes are described below. The messages are processed and passed between variable nodes and function nodes.

Figure 3

FG in CGL (take one of the MT as an example).

4.1. The Functions of All Nodes in FG-Based CGL

(1) Variable $x_{i}$ and $y_{i}$ (in the kth iteration)

The message from variable node $x_{i}^{k}$ to function node $A_{i, j}^{k}$ or $M_{i, t}^{k}$ is a Gaussian probability density function (PDF) of $x_{i}^{k}$ and can be expressed as

\begin{matrix} SI (x_{i}^{k}, A_{i, j}^{k}) = \prod_{u = 1, u \neq j}^{| V_{B, i} |} SI (A_{i, u}^{k}, x_{i}^{k}) \prod_{v = 1}^{| V_{T, i} |} SI (M_{i, v}^{k}, x_{i}^{k}), \\ SI (x_{i}^{k}, M_{i, t}^{k}) = \prod_{u = 1}^{| V_{B, i} |} SI (A_{i, u}^{k}, x_{i}^{k}) \prod_{v = 1, v \neq t}^{| V_{T, i} |} SI (M_{i, v}^{k}, x_{i}^{k}), \end{matrix}

(3)

where

i = 1,2, \dots, | V_{T} |

j = 1,2, \dots, | V_{B, i} |

t = 1,2, \dots, | V_{T, i} |

t \neq i

| V_{T} |

is the number of whole MTs to be located simultaneously.

| V_{B, i} |

and

| V_{T, i} |

represent the number of BSs and other cooperative MTs connecting to the ith MT, respectively.

SI (A_{i, u}^{k}, x_{i}^{k})

and

SI (M_{i, v}^{k}, x_{i}^{k})

are Gaussian PDF of

x_{i}^{k}

. Note that the product of any U Gaussian pdf is also Gaussian and can be derived as [20]

\begin{matrix} \prod_{u = 1}^{U} N (x, m_{u}, σ_{u}^{2}) \propto N (x, m_{Λ}, σ_{Λ}^{2}), \end{matrix}

(4)

where

N (x, m, σ^{2}) \propto \exp [- {(x - m)}^{2} / 2 σ^{2}]

σ_{Λ}^{2} = 1 / (\sum_{u = 1}^{U} 1 / σ_{u}^{2})

, and

m_{Λ} = σ_{Λ}^{2} \sum_{u = 1}^{U} (m_{u} / σ_{u}^{2})

. Similarly, variable node

y_{i}

can be calculated.

(2) Variable Nodes $Δ x_{i, j}$ , $Δ y_{i, j}$ , $Δ x x_{i, t}$ , $Δ y y_{i, t}$ , $Δ x_{i, j}^{β}$ , $Δ y_{i, j}^{β}$ , $Δ x x_{i, t}^{β}$ , $Δ y y_{i, t}^{β}$ , $d_{i, j}$ , and $l_{i, t}$

Variable node $Δ x_{i, j}$ and $Δ x x_{i, t}$ can transmit the receiving message directly as follows:

\begin{matrix} SI (Δ x_{i, j}^{k}, R_{i, j}^{k}) = SI (C_{i, j}^{k}, Δ x_{i, j}^{k}), \end{matrix}

(5)

\begin{matrix} SI (Δ x_{i, j}^{k}, C_{i, j}^{k}) = SI (R_{i, j}^{k}, Δ x_{i, j}^{k}), \end{matrix}

(6)

\begin{matrix} SI (Δ x x_{i, t}^{k}, R R_{i, t}^{k}) = SI (C C_{i, t}^{k}, Δ x x_{i, t}^{k}), \end{matrix}

(7)

\begin{matrix} SI (Δ x x_{i, t}^{k}, C C_{i, t}^{k}) = SI (R R_{i, t}^{k}, Δ x x_{i, t}^{k}) . \end{matrix}

(8)

Similarly, variable node

Δ y_{i, j}

Δ y y_{i, t}

Δ x_{i, j}^{β}

Δ x x_{i, t}^{β}

Δ y_{i, j}^{β}

Δ y y_{i, t}^{β}

d_{i, j}

, and

l_{i, t}

all play the role as a message transfer between the corresponding two function nodes.

(3) Function Nodes $A_{i, j}$ , $B_{i, j}$ , $M_{i, t}$ , and $N_{i, t}$

The function of these nodes is to convert the relative position information into the absolute position information, and vice versa

\begin{matrix} Δ x_{i, j}^{β} = X_{i, j} - x_{i}, \\ Δ y_{i, j}^{β} = Y_{i, j} - y_{i}, \end{matrix}

(9)

where

X_{i, j}

and

Y_{i, j}

represent the position of the jth BS connecting to the ith MT.

\begin{matrix} \begin{matrix} Δ x x_{i, t}^{β} = x_{t} - x_{i}, \\ Δ y y_{i, t}^{β} = y_{t} - y_{i}, \end{matrix} t = 1,2, \dots, | V_{T, i} |, \end{matrix}

(10)

\begin{matrix} SI (A_{i, j}^{k}, Δ x_{i, j}^{β, k}) = N (Δ x_{i, j}^{β, k}, X_{i, j} - x_{i}^{k}, σ_{x_{i}^{k}}^{2}), \end{matrix}

(11)

\begin{matrix} SI (A_{i, j}^{k}, x_{i}^{k}) = N (x_{i}^{k}, X_{i, j} - Δ x_{i, j}^{β, k}, σ_{Δ x_{i, j}^{β, k}}^{2}), \end{matrix}

(12)

where

σ_{x_{i}^{k}}^{2}

and

σ_{Δ x_{i, j}^{β, k}}^{2}

are the variance of the Gaussian soft information from

x_{i}^{k}

and

Δ x_{i, j}^{β, k}

. Similarly, the message from

B_{i, j}

M_{i, t}

, and

N_{i, t}

can be calculated.

(4) Function Nodes $C_{i, j}$ and $C C_{i, t}$

The function of these nodes is to merge the separate information from x-coordinate group and the y-coordinate group and then compare it with real measurement data as follows:

\begin{matrix} {(Δ x_{i, j})}^{2} + {(Δ y_{i, j})}^{2} = d_{i, j}^{2}, \\ {(Δ x x_{i, t})}^{2} + {(Δ y y_{i, t})}^{2} = l_{i, t}^{2} . \end{matrix}

(13)

Δ y_{i, j}

updates itself according to the messages from

Δ x_{i, j}

and

d_{i, j}

;

Δ x_{i, j}

updates itself according to the messages from

Δ y_{i, j}

and

d_{i, j}

\begin{array}{l} SI (C_{i, j}^{k}, Δ y_{i, j}^{k + 1}) = N (Δ y_{i, j}^{k + 1}, \pm \sqrt{{({\hat{d}}_{i, j}^{k})}^{2} - {(Δ x_{i, j}^{k})}^{2}}, \\ \frac{{(Δ x_{i, j}^{k})}^{2} {(σ_{Δ x_{i, j}}^{k})}^{2} + {({\hat{d}}_{i, j}^{k})}^{2} {(σ_{d_{i, j}}^{k})}^{2}}{{({\hat{d}}_{i, j}^{k})}^{2} - {({Δ x}_{i, j}^{k})}^{2}}), \end{array}

(14)

\begin{array}{l} SI (C_{i, j}^{k}, Δ x_{i, j}^{k + 1}) = N (Δ x_{i, j}^{k + 1}, \pm \sqrt{{({\hat{d}}_{i, j}^{k})}^{2} - {(Δ y_{i, j}^{k})}^{2}}, \\ \frac{{(Δ y_{i, j}^{k})}^{2} {(σ_{Δ y_{i, j}}^{k})}^{2} + {({\hat{d}}_{i, j}^{k})}^{2} {(σ_{d_{i, j}}^{k})}^{2}}{{({\hat{d}}_{i, j}^{k})}^{2} - {({Δ y}_{i, j}^{k})}^{2}}), \end{array}

(15)

where

{\hat{d}}_{i, j}

and

{\hat{l}}_{i, t}

are the measurement information between BSs and MTs, and between MTs. Similarly,

SI (C C_{i, t}^{k}, Δ x x_{i, t}^{k + 1})

and

SI (C C_{i, t}^{k}, Δ y y_{i, t}^{k + 1})

can be calculated.

(5) Function Nodes $R_{i, j}$ and $R R_{i, t}$

The function of these nodes is to perform the weighting process based on information reliability as follows:

\begin{array}{l} SI (Δ x_{i, j}^{k}, R_{i, j}^{k}) = N (Δ x_{i, j}^{k}, \pm \sqrt{{({\hat{d}}_{i, j}^{k})}^{2} - {(Δ y_{i, j}^{k})}^{2}}, \\ \frac{{(Δ y_{i, j}^{k})}^{2} {(σ_{Δ y_{i, j}}^{k})}^{2} + {({\hat{d}}_{i, j}^{k})}^{2} {(σ_{d_{i, j}}^{k})}^{2}}{{({\hat{d}}_{i, j}^{k})}^{2} - {({Δ y}_{i, j}^{k})}^{2}}), \end{array}

(16)

\begin{array}{l} SI (Δ y_{i, j}^{k}, R_{i, j}^{k}) = N (Δ y_{i, j}^{k}, \pm \sqrt{{({\hat{d}}_{i, j}^{k})}^{2} - {(Δ x_{i, j}^{k})}^{2}}, \\ \frac{{(Δ x_{i, j}^{k})}^{2} {(σ_{Δ x_{i, j}}^{k})}^{2} + {({\hat{d}}_{i, j}^{k})}^{2} {(σ_{d_{i, j}}^{k})}^{2}}{{({\hat{d}}_{i, j}^{k})}^{2} - {({Δ x}_{i, j}^{k})}^{2}}), \end{array}

(17)

\begin{array}{l} SI (R_{i, j}^{k}, Δ x_{i, j}^{β, k}) \\ = N (Δ x_{i, j}^{k}, \pm \sqrt{{({\hat{d}}_{i, j}^{k})}^{2} - {(Δ y_{i, j}^{k})}^{2}}, \\ β_{i} \cdot \frac{{(Δ y_{i, j}^{k})}^{2} {(σ_{Δ y_{i, j}}^{k})}^{2} + {({\hat{d}}_{i, j}^{k})}^{2} {(σ_{d_{i, j}}^{k})}^{2}}{{({\hat{d}}_{i, j}^{k})}^{2} - {({Δ y}_{i, j}^{k})}^{2}}), \end{array}

(18)

\begin{array}{l} SI (R_{i, j}^{k}, Δ y_{i, j}^{β, k}) \\ = N (Δ y_{i, j}^{k}, \pm \sqrt{{({\hat{d}}_{i, j}^{k})}^{2} - {(Δ x_{i, j}^{k})}^{2}}, \\ β_{i} \cdot \frac{{(Δ x_{i, j}^{k})}^{2} {(σ_{Δ x_{i, j}}^{k})}^{2} + {({\hat{d}}_{i, j}^{k})}^{2} {(σ_{d_{i, j}}^{k})}^{2}}{{({\hat{d}}_{i, j}^{k})}^{2} - {({Δ x}_{i, j}^{k})}^{2}}), \end{array}

(19)

\begin{array}{l} SI (Δ x_{i, j}^{β, k}, R_{i, j}^{k}) = SI (A_{i, j}^{k}, Δ x_{i, j}^{β, k}), \end{array}

(20)

\begin{array}{l} SI (Δ y_{i, j}^{β, k}, R_{i, j}^{k}) = SI (B_{i, j}^{k}, Δ y_{i, j}^{β, k}), \end{array}

(21)

\begin{array}{l} SI (R_{i, j}^{k}, Δ x_{i, j}^{k}) = SI (Δ x_{i, j}^{β, k}, R_{i, j}^{k}), \end{array}

(22)

\begin{array}{l} SI (R_{i, j}^{k}, Δ y_{i, j}^{k}) = SI (Δ y_{i, j}^{β, k}, R_{i, j}^{k}), \end{array}

(23)

where

β_{i}

is the weighting coefficient and

β_{i} = 1

(without weighing) is for the information from BS. Similarly,

SI (Δ x x_{i, t}^{k}, R R_{i, t}^{k})

SI (Δ y y_{i, t}^{k}, R R_{i, t}^{k})

SI (R R_{i, t}^{k}, Δ x x_{i, t}^{β, k})

SI (R R_{i, t}^{k}, Δ y y_{i, t}^{β, k})

SI (R R_{i, t}^{k}, Δ x x_{i, t}^{k})

, and

SI (R R_{i, t}^{k}, Δ y y_{i, t}^{k})

can be calculated.

(6) Function Nodes $D_{i, j}$ and $L_{i, t}$

The measurement information ${\hat{d}}_{i, j}$ and ${\hat{l}}_{i, t}$ enter FG through the function node $D_{i, j}$ and $L_{i, t}$ as follows:

\begin{matrix} SI (D_{i, j}^{k}, d_{i, j}^{k}) = N (d_{i, j}, {\hat{d}}_{i, j}, σ_{d_{i, j}}^{2}), \\ SI (L_{i, t}^{k}, l_{i, t}^{k}) = N (l_{i, t}, {\hat{l}}_{i, t}, σ_{l_{i, t}}^{2}) . \end{matrix}

(24)

After K iterations, information in variable nodes

x_{i}

and

y_{i}

converges.

x_{i}

and

y_{i}

can be estimated.

\begin{matrix} SI (x_{i}^{k}) = \prod_{u = 1}^{| V_{B, i} |} SI (A_{i, u}^{k}, x_{i}^{k}) \prod_{v = 1}^{| V_{T, i} |} SI (M_{i, v}^{k}, x_{i}^{k}), \\ SI (y_{i}^{k}) = \prod_{u = 1}^{| V_{B, i} |} SI (B_{i, u}^{k}, y_{i}^{k}) \prod_{v = 1}^{| V_{T, i} |} SI (N_{i, v}^{k}, y_{i}^{k}) . \end{matrix}

(25)

4.2. The Characteristics of FG-Based CGL

From Figure 3, it can be concluded that the passing messages from BSs or cooperative MTs only merge in variable nodes $x_{i}$ and $y_{i}$ , while the passing message in other variable nodes is just related with the information in their local branches. The estimation for $x_{i}$ (or $y_{i}$ ) is $m_{Λ, i} = σ_{Λ, i}^{2} \sum_{u = 1}^{U} (m_{i, u} / σ_{i, u}^{2})$ , where $σ_{Λ, i}^{2} = 1 / (\sum_{u = 1}^{U} 1 / σ_{i, u}^{2})$ . $m_{i, u}$ represents the mean of the information in the $u th$ branch (no matter the BS branch or the MT branch) connecting to the ith MT, and, $σ_{i, u}^{2}$ represents the variance of the information in the $u th$ branch connecting to the ith MT. Moreover, it is supposed that the variances of the information from BSs are the same (denoted as $C = 1 / σ_{i, j}^{2})$ , and the variances of the information from cooperative MTs are the same as well (denoted as $D = 1 / σ_{i, t}^{' 2})$ . Therefore, $m_{Λ, i} = σ_{Λ, i}^{2} \sum_{u = 1}^{U} (m_{i, u} / σ_{i, u}^{2})$ can be written as $m_{Λ, i} = (C \sum_{j = 1}^{| V_{B, i} |} m_{i, j} + D \sum_{t = 1}^{| V_{T, i} |} m_{i, t}^{'}) / (C | V_{B, i} | + D | V_{T, i} |)$ , where $| V_{B, i} |$ denotes the number of BSs connecting to the ith MT, and $| V_{T, i} |$ denotes the number of cooperative MTs connecting to the ith MT. The estimated localization error is

\begin{matrix} Δ_{i} = m_{Λ, i} - {\bar{m}}_{i} = \frac{C \sum_{j = 1}^{| V_{B, i} |} m_{i, j} + D \sum_{t = 1}^{| V_{T, i} |} m_{i, t}^{'}}{C | V_{B, i} | + D | V_{T, i} |} - {\bar{m}}_{i}, \end{matrix}

(26)

where

{\bar{m}}_{i}

is the real value.

According to the form of (26), the localization error does not decrease linearly with the growing number of BSs or the number of cooperative MTs, and it is affected by the value of $C / D$ . When the number of BSs and MTs is definite, the localization error can reduce with the increasing value of $C / D$ . Moreover, the influence of $| V_{B, i} |$ and $| V_{T, i} |$ on localization accuracy weakens with the increasing value of $C / D$ . Therefore, the strict demand for topology is relieved which embodies the robustness of the algorithms.

4.3. The Formulation of WFG-CGL Algorithm

Obviously, the information provided by the cooperative MT is less reliable than that of BS. Generally, the variances information represents the reliability. The information reliability lowers with the larger variance. If the variance information is multiplied by a weighted coefficient based on its reliability before performing the position estimation, the higher localization accuracy can be obtained. Considering the influence from the weighted coefficient, a weights optimization method is proposed, which can calculate the optimal weights for multiple MTs, respectively.

Denote the localization error as e and

\begin{matrix} e = [\begin{bmatrix} {(x_{1} - {\bar{x}}_{1})}^{2} + {(y_{1} - {\bar{y}}_{1})}^{2} \\ \dots \\ {(x_{| V_{T} |} - {\bar{x}}_{| V_{T} |})}^{2} + {(y_{| V_{T} |} - {\bar{y}}_{| V_{T} |})}^{2} \end{bmatrix}], \end{matrix}

(27)

where

x_{i}

and

y_{i}

are the functions of

β_{i}

;

{\bar{x}}_{i}

and

{\bar{y}}_{i}

are the real position for the ith MT.

Take one element of the matrix in (27) as an example to calculate the corresponding weight.

Denote $μ_{x, i}$ and $σ_{x, i}^{2}$ represent the mean and variance of the Gaussian variable $x_{i}$ , $μ_{y, i}$ , and $σ_{y, i}^{2}$ represent the mean and variance of the Gaussian variable $y_{i}$ ; ${\bar{x}}_{i}$ and ${\bar{y}}_{i}$ are the constants.

\begin{matrix} ε_{x, i} = x_{i} - {\bar{x}}_{i} ~ N (x_{i} - {\bar{x}}_{i}, μ_{e, x, i}, σ_{x, i}^{2}), \end{matrix}

(28)

\begin{matrix} ε_{y, i} = y_{i} - {\bar{y}}_{i} ~ N (y_{i} - {\bar{y}}_{i}, μ_{e, y, i}, σ_{y, i}^{2}), \end{matrix}

(29)

\begin{matrix} μ_{e, x, i} = E [x_{i} - {\bar{x}}_{i}] = μ_{x, i} - {\bar{x}}_{i}, \end{matrix}

(30)

\begin{matrix} μ_{e, y, i} = E [y_{i} - {\bar{y}}_{i}] = μ_{y, i} - {\bar{y}}_{i} . \end{matrix}

(31)

Therefore,

ε_{x, i}^{2}

and

ε_{y, i}^{2}

follow the noncentral Chi-squared distribution.

E (ε_{x, i}^{2}) = n_{x} σ_{x, i}^{2} + s_{x}^{2}

, where

n_{x}

is the freedom degrees of the ith MT in x-coordinate and

s_{x}^{2} = \sum_{i = 1}^{n_{x}} μ_{e, x, i}^{2}

. Due to the fact that

ε_{x, i}^{2}

is independent of

ε_{y, i}^{2}

as follows:

\begin{array}{l} E (ε_{x, i}^{2} + ε_{y, i}^{2}) = E (ε_{x, i}^{2}) + E (ε_{y, i}^{2}) \\ = σ_{x, i}^{2} + s_{x}^{2} + σ_{y, i}^{2} + s_{y}^{2} \\ = σ_{x, i}^{2} + μ_{e, x, i}^{2} + σ_{y, i}^{2} + μ_{e, y, i}^{2}, \end{array}

(32)

where

σ_{x, i}^{2}

μ_{e, x, i}^{2}

σ_{y, i}^{2}

, and

μ_{e, y, i}^{2}

are the functions of

β_{i}

The optimal weight adaptation achieves minimum localization error for multiple MTs, respectively,

\begin{matrix} \min_{β_{i}} \arg E (ε_{x, i}^{2} + ε_{y, i}^{2}), \end{matrix}

(33)

\begin{matrix} \frac{\partial E (ε_{x, i}^{2} + ε_{y, i}^{2})}{\partial β_{i}} = 0, \end{matrix}

(34)

\begin{matrix} \frac{\partial σ_{x, i}^{2}}{\partial β_{i}} + 2 μ_{e, x, i} \frac{\partial μ_{e, x, i}}{\partial β_{i}} + \frac{\partial σ_{y, i}^{2}}{\partial β_{i}} + 2 μ_{e, y, i} \frac{\partial μ_{e, y, i}}{\partial β_{i}} = 0, \end{matrix}

(35)

where

σ_{x, i}^{2}

and

μ_{e, x, i}

are based on (15) and (30).

\begin{array}{l} \frac{\partial σ_{x, i}^{2}}{\partial β_{i}} = \frac{\sum_{j = 1}^{| V_{T, i} |} (1 / σ_{Δ x x, i, j}^{2})}{{(\sum_{j = 1}^{| V_{B, i} |} (1 / σ_{Δ x, i, j}^{2}) + \sum_{j = 1}^{| V_{T, i} |} (1 / σ_{Δ x x, i, j}^{2}))}^{2}}, \end{array}

(36)

\begin{array}{l} \frac{\partial μ_{e, x, i}}{\partial β_{i}} = \frac{\partial σ_{x, i}^{2}}{\partial β_{i}} (\sum_{j = 1}^{| V_{B, i} |} \frac{μ_{Δ x, j}}{σ_{Δ x, i, j}^{2}} + \sum_{j = 1}^{| V_{T, i} |} \frac{μ_{Δ x x, j}}{σ_{Δ x x, i, j}^{2}}) \\ - σ_{x, i}^{2} \cdot \sum_{j = 1}^{| V_{T, i} |} \frac{μ_{Δ x x, j}}{σ_{Δ x x, i, j}^{2}}, \end{array}

(37)

where only

μ_{Δ x x, j}

and

σ_{Δ x x, i, j}^{2}

are the functions of

β_{i}

. Numerical methods can be utilized to obtain

β_{i}

estimation.

According to the above analysis, the procedures of WFG-CGL algorithm are described as follows.

Step 1 (initialization).

All variable nodes need deterministic initial values, except $d_{i, j}$ and $l_{i, t}$ . Initial values can be made at random or by some specific algorithms, not detailed here. Set $k = 0$ .

Step 2 (entrance of measurement information in the kth iteration).

The measurement information ${\hat{d}}_{i, j}^{k}$ and ${\hat{l}}_{i, t}^{k}$ from TOA measurement enter FG through function nodes $D_{i, j}^{k}$ and $L_{i, t}^{k}$ , according to (24).

Step 3 (uplink calculation in the kth iteration).

Function node $C_{i, j}$ updates $Δ y_{i, j}$ and $Δ x_{i, j}$ according to (14), and (15). Similarly, function node $C C_{i, t}$ updates $Δ x x_{i, t}$ and $Δ y y_{i, t}$ . $β_{i}$ is calculated in (35), and function nodes $R_{i, j}$ and $R R_{i, t}$ update $Δ x_{i, j}^{β}$ , $Δ y_{i, j}^{β}$ , $Δ x x_{i, t}^{β}$ , and $Δ y y_{i . t}^{β}$ according to (18) and other similar formulae. Function nodes $A_{i, j}$ , $B_{i, j}$ , $M_{i, t}$ , and $N_{i, t}$ update the messages for $x_{i}$ and $y_{i}$ according to (12) and other similar formulae.

Step 4 (downlink calculation in the kth iteration).

Variable nodes $x_{i}$ transmit message to $A_{i, j}$ and $M_{i, t}$ according to (3). Similarly, $y_{i}$ transmits message to $B_{i, j}$ and $N_{i, t}$ . Function node $A_{i, j}$ updates $Δ x_{i, j}^{β}$ according to (11). Similarly, function nodes $B_{i, j}$ , $M_{i, t}$ , and $N_{i, t}$ update $Δ y_{i, j}^{β}$ , $Δ x x_{i, t}^{β}$ , and $Δ y y_{i, t}^{β}$ . Function node $R_{i, j}$ updates $Δ x_{i, j}$ and $Δ y_{i, j}$ according to (22) and (23). Similarly, function node $R R_{i, t}$ updates $Δ x x_{i, t}$ and $Δ y y_{i, t}$ .

Step 5.

In the kth iteration, Variable nodes $x_{i}$ and $y_{i}$ are updated and estimate the position of the ith MT according to (25).

Step 6.

Targeting for the mth MT who has not updated the position in the kth iteration, we make $i = m$ , return to Step 2. Else, when all of the cooperative MTs in a TG have completed the position updating in the kth iteration, we make $k \leftarrow k + 1$ .

Step 7.

If $k < K$ , return to Step 2. Else, $x_{i} = x_{i}^{k}$ and $y_{i} = y_{i}^{k}$ , the algorithm stops.

4.4. The Formulation of LCFG-CGL Algorithm

In WFG-CGL algorithm, the solution to the weights increases the calculation complexity. In order to further diminish the complexity, the weights for all MTs in TG are not differentiated, leading to the fact that all weights are considered as 1. Therefore, we propose LCFG-CGL algorithm to solve the problem, and the procedures of LCFG-CGL algorithm are described as follows.

Step 1 (initialization).

All variable nodes need deterministic initial values, except $d_{i, j}$ and $l_{i, t}$ . Initial values can be made at random or by some specific algorithms, not detailed here. Set $k = 0$ .

Step 2 (entrance of measurement information in the kth iteration).

The measurement information ${\hat{d}}_{i, j}^{k}$ and ${\hat{l}}_{i, t}^{k}$ from TOA measurement enter FG through function nodes $D_{i, j}^{k}$ and $L_{i, t}^{k}$ , according to (24).

Step 3 (uplink calculation in the kth iteration).

Function node $C_{i, j}$ updates $Δ y_{i, j}$ and $Δ x_{i, j}$ according to (14) and (15). Similarly, function node $C C_{i, t}$ updates $Δ x x_{i, t}$ and $Δ y y_{i, t}$ . All $β_{i}$ are set as 1, and function nodes $R_{i, j}$ , and $R R_{i, t}$ work as transfers to $Δ x_{i, j}^{β}$ , $Δ y_{i, j}^{β}$ , $Δ x x_{i, t}^{β}$ , and $Δ y y_{i, t}^{β}$ . Function nodes $A_{i, j}$ , $B_{i, j}$ , $M_{i, t}$ , and $N_{i, t}$ update the messages for $x_{i}$ and $y_{i}$ according to (12) and other similar formulae.

Step 4 4 (downlink calculation in the kth iteration).

Variable nodes $x_{i}$ transmits message to $A_{i, j}$ and $M_{i, t}$ according to (3). Similarly, $y_{i}$ transmits message to $B_{i, j}$ and $N_{i, t}$ . Function node $A_{i, j}$ updates $Δ x_{i, j}^{β}$ according to (11). Similarly, function nodes $B_{i, j}$ , $M_{i, t}$ , and $N_{i, t}$ update $Δ y_{i, j}^{β}$ , $Δ x x_{i, t}^{β}$ , and $Δ y y_{i, t}^{β}$ ; Function node $R_{i, j}$ updates $Δ x_{i, j}$ and $Δ y_{i, j}$ according to (22)and (23). Similarly, function node $R R_{i, t}$ updates $Δ x x_{i, t}$ and $Δ y y_{i, t}$ .

Step 5.

In the kth iteration, variable nodes $x_{i}$ and $y_{i}$ are updated and estimate the position of the ith MT according to (25).

Step 6.

Step 7.

If $k < K$ , return to Step 2. Else, $x_{i} = x_{i}^{k}$ and $y_{i} = y_{i}^{k}$ , the algorithm stops.

5. CRLB Analysis

The CRLB is commonly used as a performance benchmark of an estimator because it gives the lowest possible variance [27]. Although the CRLB analysis is a classical localization metric, the CRLB analysis targeting CGL has not been performed in detail. Here, we make the CRLB analysis of CGL firstly.

Considering a vector of all nodes parameters $γ = [γ_{1}, γ_{2} \dots, γ_{| V |}]$ in CGL, nodes $1,2, \dots, | V_{T} |$ represent the blindfolded MTs, and nodes $| V_{T} | + 1, | V_{T} | + 2, \dots, | V_{T} | + | V_{B} |$ represent the BSs. The unknown MT parameter vector is $θ = [θ_{1}, θ_{2}, \dots, θ_{| V_{T} |}]$ , where $θ_{i} = γ_{i}$ for $i = 1,2, \dots, | V_{T} |$ . Note that the BS parameter vector ${γ_{i}, i = | V_{T} | + 1, M + 2, \dots, | V_{T} | + | V_{B} |}$ is known. Nodes i and j make pair-wise observations $Z_{i, j}$ with density $p_{Z ∣ γ} (Z_{i, j} ∣ γ_{i}, γ_{j})$ . Let $H (i)$ = $j$ : node j makes pair-wise observations with node i. By convention, a node cannot make pair-wise observation with itself, so that $i \notin H (i)$ . By symmetry, if $j \in H (i)$ , then $i \in H (j)$ .

It is assumed by reciprocity that $Z_{i, j} = Z_{j, i}$ . Thus, it is sufficient to consider only the lower triangle of the observation matrix $Z = ((Z_{i, j}))_{i, j}$ when formulating the joint likelihood function. We assume that ${Z_{i, j}}$ are statistically independent for $j < i$ . This assumption can be somewhat oversimplified but necessary for analysis. The log of the joint conditional PDF is

\begin{matrix} l (Z ∣ γ) = \sum_{i = 1}^{| V |} \sum_{j \in H (i), j < i}^{} l_{i, j}, l_{i, j} = \ln p_{Z ∣ γ} (Z_{i, j} ∣ γ_{i}, γ_{j}) . \end{matrix}

(38)

The CRLB on the covariance matrix of any unbiased estimator $\hat{θ}$ is cov $(\hat{θ}) \geq F_{θ}^{- 1}$ , where the Fisher information matrix (FIM) $F_{θ}$ is defined as

\begin{matrix} F_{θ} = - E \nabla_{θ} {(\nabla_{θ} l (Z ∣ γ))}^{T} = [\begin{bmatrix} f_{1,1} & \dots & f_{1, | V |} \\ ⋮ & ⋱ & ⋮ \\ f_{| V |, 1} & \dots & f_{| V |, | V |} \end{bmatrix}], \end{matrix}

(39)

where the diagonal elements

f_{k, k}

for

k = 1,2, \dots, | V |

F_{θ}

can be simplified to a single sum over

H (k)

since there are

H (k)

term in (38) that depend on

θ_{k} = γ_{k}

. The off-diagonal elements can be further reduced: when

k \neq l

for

k = 1,2, \dots, | V_{T} |

;

l = 1,2, \dots, | V_{T} |

, there is at most one summand in (38) that is a function of both k and l.

\begin{matrix} f_{k, l} = {\begin{cases} - \sum_{j \notin H (k)} ‍ E [\frac{\partial^{2}}{\partial {θ_{k}}^{2}} l_{k, j}], & k = l, \\ - I_{H (k)} (l) E [\frac{\partial^{2}}{\partial θ_{k} θ_{l}} l_{k, l}], & k \neq l, \end{cases} \end{matrix}

(40)

where

I_{H (k)} (l)

is an indicator function: 1 if

l \in H (k)

or 0 otherwise.

For a 2D system, $γ = [γ_{1}, γ_{2} \dots, γ_{| V |}]$ , where $γ_{i} = {[x_{i}, y_{i}]}^{T}$ . The relative localization problem corresponds to the estimation of blindfolded device coordinates $θ = [θ_{x}, θ_{y}]$ , where $θ_{x} = [x_{1}, x_{2}, \dots, x_{| V_{T} |}]$ , $θ_{y} = [y_{1}, y_{2}, \dots, y_{| V_{T} |}]$ , and the known BSs coordinates are $[x_{| V_{T} | + 1}, \dots, x_{| V_{T} | + | V_{B} |}, y_{| V_{T} | + 1}, \dots, y_{| V_{T} | + | V_{B} |}]$ . In the cellular network, $T_{i, j}$ , $i = 1, \dots, | V_{T} |$ ; $j = | V_{T} | + 1, \dots, | V_{T} | + | V_{B} |$ is the measured TOA between BSs and MTs. $T_{i, i^{'}}$ , $i = 1, \dots, | V_{T} |$ ; $i^{'} = 1, \dots, | V_{T} |$ ; $i \neq i^{'}$ is the measured TOA between MTs. Assuming that both $T_{i, j}$ and $T_{i, i^{'}}$ are independent Gaussian distributed, which is denoted as

\begin{matrix} T_{i, j} ~ N (\frac{d_{i, j}}{c}, δ_{MB}^{2}), \end{matrix}

(41)

where

i = 1, \dots, | V_{T} |

;

j = | V_{T} | + 1, \dots, | V_{T} | + | V_{B} |

\begin{matrix} T_{i, i^{'}} ~ N (\frac{d_{i, i^{'}}}{c}, δ_{MT}^{2}), \end{matrix}

(42)

where

i = 1, \dots, | V_{T} |

;

i^{'} = 1, \dots, | V_{T} |

;

i \neq i^{'}

\begin{matrix} d_{i, j} = d (γ_{i}, γ_{j}) = ∥ γ_{i} - γ_{j} ∥, \end{matrix}

(43)

\begin{matrix} d_{i, i^{'}} = d (γ_{i}, γ_{i^{'}}) = ∥ γ_{i} - γ_{i^{'}} ∥, \end{matrix}

(44)

\begin{matrix} f_{MB} (\frac{T_{i, j}}{γ}) = \frac{1}{\sqrt{2 π δ_{MB}^{2}}} e^{- (T_{i, j} - d_{i, j} / c)^{2} / 2 δ_{MB}^{2}}, \end{matrix}

(45)

\begin{matrix} f_{MT} (\frac{T_{i, i^{'}}}{γ}) = \frac{1}{\sqrt{2 π δ_{MT}^{2}}} e^{- (T_{i, i^{'}} - d_{i, i^{'}} / c)^{2} / 2 δ_{MT}^{2}}, \end{matrix}

(46)

where c is the speed of light propagation,

δ_{MB}^{2}

and

δ_{MT}^{2}

denote the variance of TOA measurements between BSs and MTs, and between MTs, respectively.

For simplification, the FIM will have a similar form to (39) if partitioned into blocks

\begin{matrix} F = [\begin{bmatrix} F_{x x} & F_{x y} \\ F_{y x} & F_{y y} \end{bmatrix}], \end{matrix}

(47)

where

F_{x x}

is given by (39) using only the x parameter vector

θ = θ_{x}

, and

F_{y y}

is given by (39) using only

θ = θ_{y}

. The off-diagonal blocks

F_{x y}

and

F_{y x}

are similarly derived. According to this cooperative structure, the elements of the submatrics of (47) are derived as follows:

\begin{array}{l} l (\frac{X}{γ}) = \sum_{i = 1}^{| V_{T} |} \sum_{j = M + 1}^{| V_{T} | + | V_{B} |} \ln {f_{MB} (\frac{T_{i, j}}{γ})} \\ + \sum_{i = 1}^{| V_{T} |} \sum_{\begin{array}{l} i^{'} = 1 \\ i^{'} \neq i \end{array}}^{| V_{T} |} \ln {f_{MT} (\frac{T_{i, i^{'}}}{γ})} . \end{array}

(48)

And the FIM is for

k = l

\begin{array}{l} {[F_{x x}]}_{k, l} = \frac{1}{c^{2} δ_{MB}^{2}} \sum_{j \in H (k)} \frac{{(x_{k} - x_{j})}^{2}}{{∥ γ_{k} - γ_{j} ∥}^{2}} \\ + \frac{1}{c^{2} δ_{MT}^{2}} \sum_{i \in H (k)} \frac{{(x_{k} - x_{i})}^{2}}{{∥ γ_{k} - γ_{i} ∥}^{2}}, \end{array}

(49)

\begin{array}{l} {[F_{y y}]}_{k, l} = \frac{1}{c^{2} δ_{MB}^{2}} \sum_{j \in H (k)} \frac{{(y_{k} - y_{j})}^{2}}{{∥ γ_{k} - γ_{j} ∥}^{2}} \\ + \frac{1}{c^{2} δ_{MT}^{2}} \sum_{i \in H (k)} \frac{{(y_{k} - y_{i})}^{2}}{{∥ γ_{k} - γ_{i} ∥}^{2}}, \end{array}

(50)

\begin{array}{l} {[F_{x y}]}_{k, l} = \frac{1}{c^{2} δ_{MB}^{2}} \sum_{j \in H (k)} \frac{(x_{k} - x_{j}) (y_{k} - y_{j})}{{∥ γ_{k} - γ_{j} ∥}^{2}} \\ + \frac{1}{c^{2} δ_{MT}^{2}} \sum_{i \in H (k)} \frac{(x_{k} - x_{i}) (y_{k} - y_{i})}{{∥ γ_{k} - γ_{i} ∥}^{2}}, \end{array}

(51)

for

k \neq l

\begin{array}{l} {[F_{x x}]}_{k, l} = \frac{- I_{H (k)} (l)}{c^{2} (J_{MB} (k, l) δ_{MB}^{2} + J_{MT} (k, l) δ_{MT}^{2})} \\ \cdot \frac{{(x_{k} - x_{l})}^{2}}{{∥ γ_{k} - γ_{l} ∥}^{2}}, \end{array}

(52)

\begin{array}{l} {[F_{y y}]}_{k, l} = \frac{- I_{H (k)} (l)}{c^{2} (J_{MB} (k, l) δ_{MB}^{2} + J_{MT} (k, l) δ_{MT}^{2})} \\ \cdot \frac{{(y_{k} - y_{l})}^{2}}{{∥ γ_{k} - γ_{l} ∥}^{2}}, \end{array}

(53)

\begin{array}{l} {[F_{x y}]}_{k, l} = \frac{- I_{H (k)} (l)}{c^{2} (J_{MB} (k, l) δ_{MB}^{2} + J_{MT} (k, l) δ_{MT}^{2})} \\ \cdot \frac{(x_{k} - x_{l}) (y_{k} - y_{l})}{{∥ γ_{k} - γ_{l} ∥}^{2}}, \end{array}

(54)

where

I_{H (k)} (l)

is 1 when node k and node l can make pair-wise measurements, else

I_{H (k)} (l)

is zero.

J_{MB}

is 0 when

k, l = 1,2, \dots, | V_{T} |

k, l = | V_{T} | + 1, \dots, | V_{T} | + | V_{B} |

, else

J_{MB}

is 1.

J_{MT}

is 1 when

k, l = 1,2, \dots, | V_{T} |

, else

J_{MT}

is 0.

The formula derivation of FIM has been completed in (47)~(52), (53) and (54). Then, the trace ${\hat{θ}}_{CRLB}$ of the covariance for the ith blind MT satisfies

\begin{array}{l} {\hat{θ}}_{CRLB, i} = tr ({\underset{}{cov}}_{\hat{θ}} ({\hat{x}}_{i}, {\hat{y}}_{i})) \geq {({[F_{x x} - F_{x y} F_{y y}^{- 1} F_{x y}^{T}]}^{- 1})}_{i, i} \\ + {({[F_{y y} - F_{x y} F_{x x}^{- 1} F_{x y}^{T}]}^{- 1})}_{i, i}, \end{array}

(55)

\begin{array}{l} {\hat{θ}}_{CRLB} = \sum_{i = 1}^{| V_{T} |} \frac{{\hat{θ}}_{CRLB, i}}{| V_{T} |} . \end{array}

(56)

6. Simulation Results

In this section, numerical simulations include two parts. Part I is the research on important factors for the proposed algorithms. Part II is performed to show the effectiveness of the proposed WFG-CGL and LCFG-CGL algorithms under two typical topologies for localization research, including global rigidity which has the unique solvability shown in Figure 4(a), and rigidity which has no unique solvability and converges in the finite positions shown in Figure 4(b). The topologies with three MTs are taken as examples due to the fact that the simple and specific topologies are easy to follow. The comparison of localization accuracy and complexity between the proposed algorithms and the existing Taylor-series-based CGL algorithm [18] is performed. Moreover, CRLB analysis is conducted.

Figure 4

CGL topology.

Any topology scenario is constructed by the random birth of MTs in the efficient range of BSs. The average error is evaluated over 10,000 independent trials. While in the different scenarios with the same number of MTs, the positions of MTs and BSs are the same. First, we consider the edges existing between BSs and MTs or between MTs LOS paths. The distance measurements derived from TOA between MTs and BSs are $d = d_{0} + n$ , the distance measurements between MTs are $l = l_{0} + q$ , where $d_{0}$ denotes the real distance between BS and MT, $l_{0}$ denotes the real distance between MTs, and n and q denote the corresponding measurement error and follow the Gaussian distribution with zero mean value. Moreover, in urban environment, we consider NLOS propagation case. The NLOS error was modeled as the exponential distribution random variable in the literatures [28, 29]. The probability density function (PDF) of NLOS error k follows

\begin{matrix} p (k) = {\begin{cases} \frac{1}{K_{rms}} e^{- k / K_{rms}} & k > 0 \\ 0 & otherwise \end{cases} \end{matrix}

(57)

where

K_{rms}

denotes the mean of k. Referring to the literature [29],

K_{rms}

is set as 100 m.

The basic parameter configuration is listed in Table 1. The localization accuracy is analyzed by means of root mean square error (RMSE) between the real MTs' position $p_{MT} (i)$ and the estimated location $p_{MT}^{'} (i)$ , that is,

\begin{matrix} E_{RMSE} = \frac{\sum_{i = 1}^{| V_{T} |} {∥ p_{MT} (i) - p_{MT}^{'} (i) ∥}_{2}}{| V_{T} |} . \end{matrix}

(58)

Table 1

Parameters configuration.

The number of BSs ( $\| V_{B} \|$ )	3
The number of MTs in a TG ( $\| V_{T} \|$ )	3
Cell radius (m)	3000
TG radius (m)	750

6.1. The Important Factors for FG-Based CGL

(1) The Iteration Times

for the FG-based localization, the iteration times is predefined and has strong influence on the localization accuracy. Apparently, more iteration times can make the localization more precise. However, excessive iterations will lead to the increasing complexity. Therefore, the reasonable value of K should be investigated.

The intuitive results can be obtained from Figures 5 and 6 which shows the localization error in terms of the iteration times from $K = 1$ to $K = 15$ with the topologies of Figures 4(a) and 4(b) in LOS and NLOS scenarios. It can be observed from Figures 5 and 6 that no matter LOS or NLOS scenario, the performance has no significant improvement with the growth of K after $K = 7$ in both the rigidity and the global rigidity. Considering the high accuracy and low complexity simultaneously, $K = 7$ is adopted in the following simulations.

Figure 5

The influence of iteration times in LOS.

Figure 6

The influence of iteration times in NLOS.

(2) The Influence of $σ_{n}$ and $σ_{q}$

Figures 7 and 8 indicate the localization error of LOS and NLOS paths between MTs and BSs, respectively. As shown in Figure 7(a) and Figure 8(a) where $σ_{q}^{2} = 10$ m² in LOS and NLOS scenarios, and Figure 7(b) and Figure 8(b), where $σ_{q}^{2} = 100$ m² in LOS and NLOS scenarios, they indicate that the standard deviation between MT and BS $σ_{n}$ has stronger effects on the localization accuracy than the standard deviation between MTs $σ_{q}$ for the proposed algorithms in both LOS and NLOS scenarios. The main reason is attributive to the fact that BS can provide the information of higher accuracy, compared to the cooperative MT. However, the information in NLOS scenario is more inaccurate than that in LOS scenario due to the fact the influence of $σ_{n}$ in NLOS is slighter than that in LOS. This can be illustrated in Table 2.

Table 2

Statistics analysis for difference $σ_{q}^{2}$ .

		G: $(μ, σ^{2})$
		Global rigidity	Rigidity
LCFG	LOS	(0.134, 0.143)	(0.200, 0.162)
LCFG	NLOS	(0.131, 0.002)	(0.198, 0.002)

WFG	LOS	(0.219, 0.057)	(0.175, 0.101)
WFG	NLOS	(0.159, 0.002)	(0.167, 0.001)

Figure 7

RMSE of difference $σ_{q}^{2}$ in LOS.

Figure 8

RMSE of difference $σ_{q}^{2}$ in NLOS.

Denote $G = ({RMSE}_{100} - {RMSE}_{10}) / {RMSE}_{100}$ , where ${RMSE}_{100}$ represents the RMSE in $σ_{q}^{2} = 100 m^{2}$ , and ${RMSE}_{10}$ represents the RMSE in $σ_{q}^{2} = 10 m^{2}$ . $μ_{G}$ and $σ_{G}^{2}$ represent the mean and variance of G.

The statistic data can be obtained from Table 2 which shows $μ_{G}$ and $σ_{G}^{2}$ in terms of $σ_{n}$ from $σ_{n} = 5$ m to $σ_{n} = 45$ m for the two proposed algorithms in different scenarios. No matter the LCFG-CGL algorithm or the WFG-CGL algorithm, no matter the global rigidity topology or the rigidity topology, and no matter the LOS or NLOS, the values of $μ_{G}$ and $σ_{G}^{2}$ are all small which verifies the little performance difference between $σ_{q}^{2} = 10$ m² and $σ_{q}^{2} = 100$ m². Thereinto, we just take $σ_{q}^{2} = 10$ m² as an example in the following simulations.

(3) The Influence of $| V_{B} |$

According to the analysis in Section 4.2 and the simulation results in Figure 9, the localization error decreases with the growing number of the cooperative BSs, while the decline rate of the localization error becomes smaller with the growing number of the cooperative BSs. It is assumed that the variance of the measurement error between MTs $σ_{q}^{2}$ is definite. Figure 9 illustrates that the value of $C / D$ reduces with the rising of $σ_{n}^{2}$ , and the influence of $| V_{B} |$ on localization accuracy weakens with the increasing value of $C / D$ , no matter in LOS and NLOS scenarios. The simulation results consist with the analysis in Section 4.3, which can verify the robustness of our algorithms for the topology of CGL graph. It also clarifies the localization accuracy cannot be reduced through increasing the amount of measurement information (the number of BSs) when the measurement information is inaccurate. Therefore, the localization accuracy can be improved, only through optimizing the algorithm. Fortunately, our proposed algorithms can achieve this.

Figure 9

RMSE of difference $| V_{B} |$ .

6.2. The Localization Accuracy Analysis

The simulation results are shown in Figures 10 and 11, where the average localization errors versus $σ_{n}$ of the range measurement errors are compared in LOS and NLOS scenarios. The comparison is made among the Taylor-series-based CGL algorithm, the LCFG-CGL algorithm, the WFG-CGL algorithm and CRLB in the same scenario, where the Taylor-series-based CGL algorithm is analyzed in [18]. As expected, no matter the global rigidity or the rigidity, (1) the average localization errors increase when the range measurement error increases, (2) the proposed algorithms are superior to the traditional Taylor series CGL algorithm, (3) the WFG-CGL algorithm has higher localization accuracy than LCFG-CGL algorithm primarily due to its exploitation of the information reliability as the weights, (4) in NLOS scenario, LCFG-CGL algorithm and WFG-CGL algorithm perform far well than the traditional Taylor-series CGL algorithm, and (5) especially, the WFG-CGL algorithm is approximate to CRLB results in both global rigidity and rigidity regarding the LOS scenario.

Figure 10

RMSE of different topologies in LOS.

Figure 11

RMSE of different topologies in NLOS.

Denote $G_{t p} = ({RMSE}_{R} - {RMSE}_{G}) / {RMSE}_{R}$ , where ${RMSE}_{R}$ represents the RMSE in rigidity topology, and ${RMSE}_{G}$ represents the RMSE in global rigidity topology. $μ_{G_{t p}}$ and $σ_{G_{t p}}^{2}$ represent the mean and variance of $G_{t p}$ .

Remarkably, Taylor-series-based CGL algorithm performs better in global rigidity topology than in rigidity topology. It is obvious that the global rigidity topology can provide more localization information. However, the two proposed algorithms in rigidity have the similar localization accuracy in global rigidity, as shown in Figures 10 and 11. Table 3 derived from Figures 10 and 11 which shows the $μ_{G_{t p}}$ and $σ_{G_{t p}}^{2}$ in terms of $σ_{n}$ from $σ_{n} = 5$ m to $σ_{n} = 45$ m in different scenarios and different algorithms. It denotes that the two proposed algorithms in rigidity have the similar localization accuracy in global rigidity, which demonstrates the strong robustness of the proposed algorithms for different CGL topologies.

Table 3

Statistics analysis for different topologies.

		$μ_{G_{t p}}$	$σ_{G_{t p}}^{2}$
Taylor series	LOS	0.41	0.0021
Taylor series	NLOS	0.409	0.002
LCFG	LOS	0.12	0.0002
LCFG	NLOS	0.11	0
WFG	LOS	0.09	0.0002
WFG	NLOS	0.10	0
CRLB	LOS	0.08	0
CRLB	NLOS	0.002	0

The localization accuracy depends on how to utilize the available information. Generally, the variances can represent the practical environment effectively. The proposed algorithms make full use of the variances in nearly each node of FG, which is considered as a great help for performance upgrade in rigidity topology, even with less information than global rigidity. Furthermore, the power of the proposed algorithms lies in the ability to distributively process the problem and to provide the optimum or near-optimum solutions, which makes it a good approach to solving distributed problem. On the other hand, CGL is a distributed problem, that is, measurement parameters are only locally related. Therefore, the excellent combination between FG and CGL can relax the CGL topology requirement under ensuring the localization accuracy to some extent.

6.3. Complexity Analysis

This section analyzes the computation complexity of the proposed algorithms and Taylor-series-based algorithm, respectively.

(1) Complexity Analysis of Taylor-Series-Based CGL Algorithm

In Taylor-series-based CGL algorithm [18], the most complex step is the solution to pseudoinverse of large scale matrix. In each iteration, the computation complexity is $O (N^{3})$ , where N is the number of edges in CGL topology. Moreover, the iteration number is not definite, because it is determined by the tolerable localization error and the distance measurement error. Especially when the TG includes more cooperative MTs, the complexity of CGL-based Taylorseries localization algorithm increases sharply.

(2) Complexity Analysis of WFG-CGL Algorithm and LCFG-CGL Algorithm

In the two proposed FG-based CGL algorithms, the amount of messages passed between nodes is limited. And the iteration times is pre-defined, commonly $K = 7$ . Because after $K = 7$ , the performance has no significant improvement with the growth of K. The performance of the proposed algorithms approaches high accuracy after 7 iterations, which shows that the convergence speeds of the two proposed algorithms are reasonably high.

Although the solution of the weights in WFG-CGL algorithm results in the increasing calculation complexity to some extent, they can be calculated distributively, which means that it just solves multiple equations, respectively, instead of the solution to pseudo-inverse of large scale matrix. The computation complexity of weights solution is $O (N)$ , which is less than the Taylor-series-based CGL algorithm.

On the other hand, the convergence probabilities of the two proposed algorithms are shown in Figure 12. The proposed algorithms have very high convergence probabilities in both LOS and NLOS scenarios. Even when the standard derivation is big or the topology is not a unique solvability, the convergence probabilities of the two proposed algorithms are still acceptable. Those all lead to the low computational complexity and transmission loads while ensuring the localization accuracy.

From the above analysis and simulation results, it can be concluded that (1) both of the proposed algorithms can relax the CGL topology requirement and provide high localization accuracy. (2) WFG-CGL algorithm possesses higher accuracy than LCFG-CGL algorithm while LCFG-CGL algorithm possesses lower complexity than WFG-CGL algorithm. Although the complexity of WFG-CGL algorithm increases to some extent, it still performs with lower complexity than the traditional Taylor-series-based CGL algorithm.

Figure 12

Convergence probability of FG-based CGL.

7. Conclusion

In this paper, the WFG-CGL algorithm and the LCFG-CGL algorithm are proposed in ill conditions. Especially for WFG-CGL algorithm, the weights based on the information reliability are incorporated into the algorithm in order to obtain higher localization accuracy. The corresponding analysis and simulations show that the proposed algorithms can relax the demand for CGL topology and provide high localization accuracy under low complexity in comparison with the existing CGL algorithm. Moreover, the important factors and CRLB for FG-based localization are analyzed.

Footnotes

Acknowledgments

This work is supported by the National Nature Science Foundation of China Project (Grant 61001119) and Fundamental Research Funds for the Central Universities (G470712).

References

Commission

F. C.

Revision of the Commissions Rules to Insure Compatibility with Enhanced 911 Emergency Calling Systems, 1996

Patwari

Ash

J. N.

Kyperountas

Hero

A. O.

III Moses

R. L.

Correal

N. S.

Locating the nodes: cooperative localization in wireless sensor networks

IEEE Signal Processing Magazine 2005 22 4 54 69

2-s2.0-22544472158

10.1109/MSP.2005.1458287

Gezici

Tian

Giannakis

G. B.

Kobayashi

Molisch

A. F.

Poor

H. V.

Sahinoglu

Localization via ultra-wideband radios: a look at positioning aspects of future sensor networks

IEEE Signal Processing Magazine 2005 22 4 70 84

2-s2.0-22544486275

10.1109/MSP.2005.1458289

Hara

Zhao

Yanagihara

Taketsugu

Fukui

Fukunaga

Kitayama

K. I.

Propagation characteristics of IEEE 802.15.4 radio signal and their application for location estimation

Proceedings of the IEEE 61st Vehicular Technology Conference (VTC '05)

June 2005

97 101

2-s2.0-26444560138

Feng

Law

C. L.

Assisted GPS and its impact on navigation in intelligent transportation systems

Proceedings of the IEEE International Conference on Intelligent Transportation Systems

June 2002

926 931

Farradyne

Vehicle Infrastructure Integration (VII) Architecture and Functional Requirements, draft, version 1.0, 2005

Shafl

Aamer

Butterworth

Next generation wireless networks

Proceedings of the The IEEE International Symposium on Circuits and Systems (ISCAS '01)

May 2001

Sydney, Australia

721 729

Zhao

Standardization of mobile phone positioning for 3G systems

IEEE Communications Magazine 2002 40 7 108 116

2-s2.0-0036646445

10.1109/MCOM.2002.1018015

Sayed

A. H.

Tarighat

Khajehnouri

Network-based wireless location: challenges faced in developing techniques for accurate wireless location information

IEEE Signal Processing Magazine 2005 22 4 24 40

2-s2.0-22544485079

10.1109/MSP.2005.1458275

10.

Chaffee

Abel

GDOP and the Cramer-Rao bound

Proceedings of the IEEE Position Location and Navigation Symposium

April 1994

Las Vegas, Nev, USA

663 668

2-s2.0-0028060693

11.

Larsson

E. G.

Cramér-rao bound analysis of distributed positioning in sensor networks

IEEE Signal Processing Letters 2004 11 3 334 337

2-s2.0-1642365724

10.1109/LSP.2003.822899

12.

Shen

Wymeersch

Win

M. Z.

Fundamental limits of wideband cooperative localization via fisher information

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '07)

March 2007

3951 3955

2-s2.0-36348941872

10.1109/WCNC.2007.722

13.

Kobayashi

Suda

On time-of-arrival positioning in a multipath environment

IEEE Transactions on Vehicular Technology 2006 55 5 1516 1526

14.

Jourdan

D. B.

Dardari

Win

M. Z.

Position error bound and localization accuracy outage in dense cluttered environments

Proceedings of the IEEE International Conference on Ultra-Wideband (ICUWB '06)

September 2006

519 524

2-s2.0-41649118826

10.1109/ICU.2006.281603

15.

Ash

J. N.

Moses

R. L.

On the relative and absolute positioning errors in self-localization systems

IEEE Transactions on Signal Processing 2008 56 11 5668 5679

2-s2.0-54949102789

10.1109/TSP.2008.927072

16.

Zhao

Standardization of mobile phone positioning for 3G systems

IEEE Communications Magazine 2002 40 7 108 116

2-s2.0-0036646445

10.1109/MCOM.2002.1018015

17.

Zhang

Cui

Tao

Cooperative group localization for 4G wireless networks

Proceedings of the IEEE 70th Vehicular Technology Conference Fall (VTC '09)

September 2009

Anchorage, Alaska

2-s2.0-77951490194

10.1109/VETECF.2009.5379020

18.

Cui

Zhang

CGL-based modified taylor-series localization algorithms for future wireless networks

Proceedings of the IEEE International Conference on Communication Technology (ICCT '11)

September 2011

Jinan, China

19.

Aspnes

Eren

Goldenberg

D. K.

Morse

A. S.

Whiteley

Yang

Anderson

B. D. O.

Belhumeur

P. N.

A theory of network localization

IEEE Transactions on Mobile Computing 2006 5 12 1663 1678

2-s2.0-33750831866

10.1109/TMC.2006.174

20.

Kschischang

F. R.

Frey

B. J.

Loeliger

H. A.

Factor graphs and the sum-product algorithm

IEEE Transactions on Information Theory 2001 47 2 498 519

2-s2.0-0035246564

10.1109/18.910572

21.

Chen

J. C.

Wang

Y. C.

Maa

C. S.

Chen

J. T.

Network-side mobile position location using factor graphs

IEEE Transactions on Wireless Communications 2006 5 10 2696 2704

2-s2.0-33750057020

10.1109/TWC.2006.03401

22.

Mensing

Plass

TDoA positioning based on factor graphs

Proceedings of the IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC '06)

September 2006

1 5

2-s2.0-44949098126

10.1109/PIMRC.2006.254058

23.

Omidali

Shirazi

S. A. A. B.

Performance improvement of AOA positioning using a two-step plan based on factor graphs and the Gauss-Newton method

Proceedings of the 14th International CSI Computer Conference (CSICC '09)

October 2009

305 309

2-s2.0-74549163691

10.1109/CSICC.2009.5349365

24.

Huang

C. T.

C. H.

Lee

Y. N.

Chen

J. T.

A novel indoor RSS-based position location algorithm using factor graphs

IEEE Transactions on Wireless Communications 2009 8 6 3050 3058

2-s2.0-67651146653

10.1109/TWC.2009.080452

25.

Üney

Çetin

Target localization in acoustic sensor networks using factor graphs

Proceedings of the IEEE 16th Signal Processing, Communication and Applications Conference (SIU '08)

April 2008

1 4

2-s2.0-56449091622

10.1109/SIU.2008.4632715

26.

Wymeersch

Lien

Win

M. Z.

Cooperative localization in wireless networks

Proceedings of the IEEE 2009 97 2 427 450

2-s2.0-62949121723

10.1109/JPROC.2008.2008853

27.

Patwari

Hero

A. O.

Perkins

Correal

N. S.

O'Dea

R. J.

Relative location estimation in wireless sensor networks

IEEE Transactions on Signal Processing 2003 51 8 2137 2148

2-s2.0-0042665374

10.1109/TSP.2003.814469

28.

Sharp

Guo

Y. J.

Non-Line-of-Sight Identification, Ground-Based Wireless Positioning 2009

Chichester, UK

John Wiley & Sons

29.

Chen

P. C.

A non-line-of-sight error mitigation algorithm in location estimation

Proceedings of the IEEE Wireless Communications and Networking Conference

September 1999

New Orleans, La, USA

316 320

Cooperative Group Localization Based on Factor Graph for Next-Generation Networks

Abstract

1. Introduction

2. Mathematical Model of CGL

3. Factor Graph and Sum-Product Algorithm

3.1. Factor Graph

3.2. Sum-Product Algorithm

4. FG-Based CGL Algorithms

4.1. The Functions of All Nodes in FG-Based CGL

(1) Variable x i and y i (in the kth iteration)

(2) Variable Nodes Δ x i , j , Δ y i , j , Δ x x i , t , Δ y y i , t , Δ x i , j β , Δ y i , j β , Δ x x i , t β , Δ y y i , t β , d i , j , and l i , t

(3) Function Nodes A i , j , B i , j , M i , t , and N i , t

(4) Function Nodes C i , j and C C i , t

(5) Function Nodes R i , j and R R i , t

(6) Function Nodes D i , j and L i , t

4.2. The Characteristics of FG-Based CGL

4.3. The Formulation of WFG-CGL Algorithm

Step 1 (initialization).

Step 2 (entrance of measurement information in the kth iteration).

Step 3 (uplink calculation in the kth iteration).

Step 4 (downlink calculation in the kth iteration).

Step 5.

Step 6.

Step 7.

4.4. The Formulation of LCFG-CGL Algorithm

Step 1 (initialization).

Step 2 (entrance of measurement information in the kth iteration).

Step 3 (uplink calculation in the kth iteration).

Step 4 4 (downlink calculation in the kth iteration).

Step 5.

Step 6.

Step 7.

5. CRLB Analysis

6. Simulation Results

6.1. The Important Factors for FG-Based CGL

(1) The Iteration Times

(2) The Influence of σ n and σ q

(3) The Influence of | V B |

6.2. The Localization Accuracy Analysis

6.3. Complexity Analysis

(1) Complexity Analysis of Taylor-Series-Based CGL Algorithm

(2) Complexity Analysis of WFG-CGL Algorithm and LCFG-CGL Algorithm

7. Conclusion

Footnotes

Acknowledgments

References

(1) Variable $x_{i}$ and $y_{i}$ (in the kth iteration)

(2) Variable Nodes $Δ x_{i, j}$ , $Δ y_{i, j}$ , $Δ x x_{i, t}$ , $Δ y y_{i, t}$ , $Δ x_{i, j}^{β}$ , $Δ y_{i, j}^{β}$ , $Δ x x_{i, t}^{β}$ , $Δ y y_{i, t}^{β}$ , $d_{i, j}$ , and $l_{i, t}$

(3) Function Nodes $A_{i, j}$ , $B_{i, j}$ , $M_{i, t}$ , and $N_{i, t}$

(4) Function Nodes $C_{i, j}$ and $C C_{i, t}$

(5) Function Nodes $R_{i, j}$ and $R R_{i, t}$

(6) Function Nodes $D_{i, j}$ and $L_{i, t}$

(2) The Influence of $σ_{n}$ and $σ_{q}$

(3) The Influence of $| V_{B} |$