On the Agent Localizability of Hybrid GNSS-Terrestrial Cooperative Positioning

Abstract

Cooperative positioning is a new paradigm around how devices can cooperate with each other to improve their abilities to compute position. The problem of whether or not a device can be localized is fundamental for cooperative positioning. Many efforts have been made to solve the problem of whether or not a network or a node in the network can be localized in wireless sensor networks. Nevertheless, existing studies mainly examine the network or node localizability in 2-dimension space, yet fundamental questions in 3-dimension space remain unaddressed. In this contribution, we study the agent localizability in hybrid cooperative positioning, where GNSS information is combined with terrestrial range measurements through sharing information with other agents in a small scale group. The results provide a characterization of availability of hybrid positioning schemes, and lead to a deep understanding of the reasons for why cooperation can improve the availability.

1 Introduction

Nowadays, the most widely used positioning and navigation technology is Global Navigation Satellite System (GNSS). In GNSS, each device estimates its position individually based on pseudorange measurements taken with respect to multiple satellites with known positions. Unfortunately, because the received GNSS signal is extremely low power, the satellite signals can be easily obstructed. For instance, GNSS-based techniques fail to provide satisfactory performance due to signal blockage in many scenarios such as urban terrain, forests, or jungles. At the same time, GNSS receivers are also susceptible to jamming and unintentional interference for this same reason [1]. Driven by the success of cooperative techniques in many research areas, cooperative techniques have been introduced in the research of positioning and navigation.

Cooperative positioning methods have been recognized as part of an effort to improve the performance of GNSS receivers in hostile environments, relying on information exchange and/or direct measurements among devices (also referred to as agents hereafter). They can be used not only when GNSS is unavailable, but also in combination with GNSS, in order to improve the performance of positioning, such as accuracy, availability, time to first fix (TTFF), integrity etc. Hybrid cooperative positioning is an emerging research topic [2].

In prior work, graph rigidity is found closely related to positioning problem. Based on rigidity theory, the necessary and sufficient condition for network positioning was proposed [3], and the concept of node localizability was proposed to answer the following two questions [4]: First, given a network configuration, whether or not a specific node is localizable? Second, how many nodes in a network can be located and which are them? Unfortunately, previous works on network localizability and node localizability are both in 2-dimension and its conclusion cannot be applied to the hybrid cooperative positioning.

In this paper, we attempt to answer the question of whether or not an agent can be localized and why cooperation among nodes can improve the availability. In contrast to prior works, this paper presents an analysis on the agent localizability in scenario for small scale cooperative GNSS positioning, under different cases depending on the measurements between agents. The measurements between nodes may include one or more of the following:

• Relative position between agents, including distance between agents and relative bearing between agents.

• Distance between agents. Considering the relative bearing may not be available in practice, distance between agents is usually considered, besides, IEEE 802.11v defines a protocol to obtain this measurement between two peer WiFi devices using time-of-flight or calibrated RSS measurements.

• Difference in clock bias between agents. IEEE 802.11v also defines a protocol to obtain this measurement.

• Difference in altitude between agents. When devices are equipped with altimeters, this measurement can be obtained to improve performance. Besides, equal altitudes can be assumed between agents in some scenarios.

2 Problem Formulation

2.1 Scenario Setting

Consider a hybrid GNSS-terrestrial cooperative network including satellite nodes with known clock bias and known position, anchor nodes with known position but unknown clock bias, and agents with unknown clock bias and unknown position. Generally, bias in range measurements from satellite to terrestrial devices is considered, resulting from imperfect synchronization of device clock with respect to satellites. Nevertheless, the above bias in terrestrial range measurements is usually not considered [2]. Figure 53.1 illustrates the scenario for hybrid GNSS-terrestrial cooperative positioning.

Fig. 53.1

Scenario for hybrid GNSS-terrestrial cooperative positioning

Let ${\rm M}$ be the set of agents, $S$ the set of satellites, ${\rm A}$ the set of anchors; denote by $S_{m}$ the set of satellites agent m can see, by ${\rm A}_{m}$ the set of anchors agent m can communicate with. Positional state of satellite $s \in S$, of anchor $a \in {\rm A}$, and of agent $m \in {\rm M}$, are indicated respectively by ${\mathbf{x}}_{s} = [x_{s} \;y_{s} \;z_{s} ]$, ${\mathbf{x}}_{a} = [x_{a} \;y_{a} \;z_{a} ]$, ${\mathbf{x}}_{m} = [x_{m} \;y_{m} \;z_{m} ]$. The variable $b_{m}$ represents the clock bias of agent m, expressed in distance units. The information agent m obtained from satellites (denoted by ${\mathbf{P}}_{sm}$) and terrestrial anchors (denoted by ${\mathbf{R}}_{am}$) and from useful neighboring agents (denoted by ${\mathbf{P}}_{m}$) is denoted by ${\mathbf{M}}_{m} = {\mathbf{P}}_{sm} \cup {\mathbf{R}}_{am} \cup {\mathbf{P}}_{m}$, a set of unknowns ${\mathbf{U}}_{m} = \left[ {{\mathbf{x}}_{m} {\kern 1pt} \,b_{m} } \right]$ for agent m are to be determined.

2.2 Different Models Between Agents

In this subsection, we describe the measurements models among agents in different cases. In all the cases, the following two types of measurements always exist:

• 1. Range measurements, i.e., distance between agents and anchors $r_{am} = \left\| {{\mathbf{x}}_{a} - {\mathbf{x}}_{m} } \right\| + v_{am} .$

• 2. Pseudorange measurements, i.e., distance between agents and satellites $\rho_{sm} = \left\| {{\mathbf{x}}_{s} - {\mathbf{x}}_{m} } \right\| + b_{m} + v_{sm}$.

where the symbol $\left\| \cdot \right\|$ denotes Euclidean distance, $m \in {\rm M},\,a \in {\rm A},\,s \in S,\,v_{am} ,\,v_{sm}$ are measurement noise. Without loss of generality, in the following of this paper, we only discuss on the situation when distance between agents and satellites is available, and the measurements between agents and anchors will not be considered.

Based on different intra- and inter-node measurement sensors that agents equipped, there are several measurement models in accordance with the description in Sect. 53.1.

• Case 1: the relative position ${\mathbf{p}}_{mn}$ between agent n and a neighbour agent m can be measured, ${\mathbf{p}}_{mn} = {\mathbf{x}}_{m} - {\mathbf{x}}_{n}$.

• Case 2: the distance between agent n and a neighbour agent m can be measured. $r_{nm} = \left\| {{\mathbf{x}}_{n} - {\mathbf{x}}_{m} } \right\| + v_{nm}$, where $v_{nm}$ is measurement noise.

• Case 3: the difference in clock bias between agent n and a neighbour agent m can be measured, $\Updelta b_{mn} = b_{m} - b_{n}$.

• Case 4: the difference in altitude between agent n and a neighbour agent m can be measured, $\Updelta z_{mn} = z_{m} - z_{n}$. Besides, it can be supposed that all the agents work on the same altitude, $z_{m} = z_{n}$.

3 Conditions for Agent Localizability

To determine the solution of unknowns, a well-determined or preferably over-determined set of equations must be obtained, that is, the set of independent measurements ${\mathbf{M}}_{m}$ in the agent m must have greater cardinality than or equal to the set of unkowns ${\mathbf{U}}_{m}$ in the same agent.

3.1 Conventional GNSS Positioning Requirements

In order to determine agent position in the conventional satellite positioning as shown in Fig. 53.2, pseudorange measurements are made to at least four satellites resulting in the system of equations $\rho_{sm} = \left\| {{\mathbf{x}}_{s} - {\mathbf{x}}_{m} } \right\| + b_{m} + v_{sm}$.

Fig. 53.2

Conventional positioning: an agent can be located by no less than four satellites

There are three methods to solve the nonlinear equations, i.e., closed-form solutions, iterative techniques based on linearization and kalman filtering [5]. Given four measured pseudoranges, a position-bias pair almost always exists which exactly satisfies all four pseudorange equations. There are many previous works focusing on the exact solutions and the question of solution uniqueness. In the following of this paper, we discuss whether or not the unknowns can be resolved, and the uniqueness of the solutions will be our focal point in future works.

3.2 Cooperative Positioning Requirements for Two Agents

Using the conventional multilateration requirements as a starting point, the corresponding set of requirements for cooperative positioning between two agents can be established. Cooperative positioning between two agents represents the situation where one or both of the agents cannot see at least four satellites and then cannot obtain its position state individually. In this situation, the two agents can cooperate with each other, including the several cases in Sect. 53.2.2 to jointly solve the unknowns. In practice, the relative bearing may not be available, thus we only discuss on situations from the later three cases in the following.

Scenario 1, that case 2 and case 3 in Sect. 53.2.2 are satisfied. In this scenario, distance and difference in clock bias between the two agents can be measured, thus there are 7 parameters in the set of unknowns for the system. From this perspective, a condition for agent localizability in this scenario can be set.

Condition 1: To obtain the positional state of the two agents in this scenario, it is necessary that at least 7 measurements can be obtained in the system.

Unfortunately, this condition is necessary but not sufficient to guarantee that there is only one possible agent position estimate. Just as illustrated in Fig. 53.3c and d, both of the two cases have 7 measurements, but never of them can be localized. That is because each agent have 4 unknowns to be solved, only one of them can be shared by the two agents, still 3 unknowns are remaining and should be solved depend on its own measurements from satellites and the other agents. Actually, in the two cases, the measurements are not independent so that independent measurements are less than 7. To avoid the above problem, an additional condition is set.

Fig. 53.3

Four basic cases (as shown in a, b, c and d) in scenario 1

Condition 2: To obtain the positional state of the two agents in this scenario, it is necessary that each agent can obtain at least 3 measurements.

Figure 53.3a and b satisfy both condition 1 and condition 2, and they can be localized. Condition 1 and condition 2 are individually necessary but jointly sufficient to guarantee that the two agents in scenario 1 can be localized. It is noted that the satellites observed by the two agents can be the same. Here is an example for Fig. 53.3a, when the two agents are in a canyon, they observe the same three satellites, and then they can cooperate to obtain their position state. The other example for Fig. 53.3b, one agent is outdoors with four satellite measurements to obtain its position, while the other agent who is nearby indoors can only observe two satellites, then the indoor agent can cooperate with the outdoor agent to compute its own position.

Scenario 2, that case 2, case 3 and case 4 in Sect. 1.2 are satisfied. In this scenario, distance, difference in clock bias and altitude between the two agents can be measured, thus there are 6 parameters in the set of unknowns for the system. Similar to scenario 1, two conditions agent localizability in this scenario can be set.

Condition 1: To obtain the positional state of the two agents in this scenario, it is necessary that at least 6 measurements can be obtained in the system.

Condition 2: To obtain the positional state of the two agents in this scenario, it is necessary that each agent can obtain at least 2 measurements.

Figure 53.4a and b satisfy both condition 1 and condition 2, and they can be localized while Fig. 53.4c cannot be localized since it doesn’t satisfy condition 2. Condition 1 and condition 2 are individually necessary but jointly sufficient to guarantee that the two agents in scenario 2 can be localized.

Fig. 53.4

Four basic cases (as shown in a, b, c and d) in scenario 2

3.3 Cooperative Positioning Requirements for Three Agents

Due to the generality between scenario 1 and scenario 2 in Sect. 3.2, we only focus on scenario 1 (distance and difference in clock bias between the two agents can be measured) in this section. It is supposed that there are 3 agents in a group that participate in the cooperative positioning. In this case, there are 3 measurements among the 3 agents, and 10 unknowns in the system. Thus to solve the position of the agents, it is necessary that the cardinality of the set of independent measurements combining of the measurements among agents and from satellites is larger than 10. In the following cases, we only discuss the well-determined case, i.e. the cardinality of the set of independent measurements is 10.

Figure 53.5 illustrates the four cases that all the agents have no more than 4 satellites. We can declare that in the four cases, the positional state of the system in Fig. 53.5d cannot be solved, while the other three can be solved. However, like the two-agent case, the uniqueness of the solutions should be further discussed.

Fig. 53.5

Cases (as shown in a, b, c and d) that no agent can observe more than 4 satellites

Besides, there are several cases that one agent can observe more than 4 satellites. For example, Fig. 53.6a illustrates one case that one agent observe 5 satellites while the other two agents both observe 1 satellites. In this case, the positional state cannot be solved, and the reason can be found in Fig. 53.6b, which is derived from Fig. 53.6a. In Fig. 53.6b, there are 6 unknowns to be solved, unfortunately, there are only 5 measurements in the system.

Fig. 53.6

Cases that one agent can observe more than 4 satellites: (a) can be converted to (b)

In a group consisting of m agents, there are $m(m - 1)/2$ measurements among agents in total, and $3m + 1$ unknowns in the system. Thus to solve the position of the agents, it is necessary that the cardinality of the set of independent measurements combining of the measurements among agents and from satellites is larger than $3m + 1$. Then two fundamental questions must be addressed. First, are the $m(m - 1)/2$ measurements referred above independent? Second, if the $m(m - 1)/2$ measurements are not independent, then how many independent measurements can we get from them? To answer the first question, we propose Lemma l.

Lemma 1

In a group consisting of m agents, the $m(m - 1)/2$ measurements among them are not independent when m is larger than some value.

Proof

Since difference in clock bias between agents can be obtained, there are 3 m + 1 unknowns to be solved. Suppose the $m(m - 1)/2$ measurements are independent, then when $m(m - 1)/2\, \ge \,3m + 1$, i.e., $m \, \ge \, 8$, the unknowns can be solved even there is no beacon. This is in conflict with the fact. Therefore, the $m(m - 1)/2$ measurements among agents are not independent.

Inspired by Lemma 1, the answer to the second question should be further explored, and this will be our focal points in the future work.

4 Conclusion and Future Works

In this paper, we described the scenario setting and measurement model for the hybrid GNSS-terrestrial cooperative positioning. Cooperation enables agents that cannot compute positions on their own to compute their positions through sharing information with other agents. It also allows an agent that does not need cooperation to aid another agent that has insufficient measurements to compute its position alone. We analyzed agent localizability in small scale networks and explained the reason why cooperation can improve the performance of availability. Our results provide a characterization of availability of hybrid positioning schemes, and lead to a deep understanding of the reasons for why cooperation can improve the availability.

Several issues we plan to address in future mainly include the uniqueness of solutions, the localizability for a number of m agents, and simulations or experiments from live data.