Peer-to-Peer Cooperative Positioning
Part II: Hybrid Devices with GNSS & Terrestrial Ranging Capability
In this second part of a discussion of peer-to-peer cooperative positioning, we revisit the topic of sharing critical information across clusters of GNSS users. This article focuses on users within GNSS-challenged environments equipped with both a GNSS receiver and a terrestrial ranging system. Multiple methods for sharing position information across users are examined. The authors show that strategically sharing information can greatly enhance the availability of the position solutions to the network as a whole.
Working Papers explore the technical and scientific themes that underpin GNSS programs and applications. This regular column is coordinated by Prof. Dr.-Ing. Günter Hein, head of Europe's Galileo Operations and Evolution.
In peer-to-peer (P2P) networks, communication nodes can communicate with their neighbors without central coordination. By exchanging data, the network can perform cooperative positioning: each node is helped by its neighbors to compute its position.
If the devices contain both a GNSS receiver and a terrestrial ranging system for estimating the inter-node distances, a hybrid localization approach can be applied. The different information sources can be merged by estimation algorithms such as least square, Kalman filter, particle filter, and sum product.
Fully decentralized versions of these algorithms can be developed, where each node is able to independently process the incoming data, without depending on an external data fusion center. This approach strongly enhances the positioning performance in terms of availability and accuracy in GNSS-hostile environments.
Network nodes without enough satellite visibility may be able to compute their position without a terrestrial infrastructure or a set of beacons with a priori knowledge of their coordinates. Hybrid cooperative positioning can soon become a reality for highly connected, multi-standard devices, strongly improving their localization capability.
P2P Cooperative Positioning
In the previous article, we focused on P2P GNSS-only cooperative positioning: using the aiding data relating to the GNSS system (visible satellites, navigation messages, and so forth) or data obtained by processing GNSS signals (e.g., Doppler, carrier-to-noise ratio (C/N0), and code delay information). We showed that this approach reduces the acquisition time in many scenarios. Improvements were similar to those obtained with augmentation systems such as assisted GNSS (A-GNSS), but without requiring a fixed infrastructure.
Typical applications of P2P GNSS cooperation appear in “light indoor” scenarios, where each node has a sufficient number of satellites in view but some of which are received with very low (C/N0) due to natural or artificial blocking such as occurs due to foliage and buildings. In the absence of A-GNSS or P2P GNSS cooperation, the time needed to acquire signals becomes an issue and acquisition may even become impossible.
In this article, we focus on P2P hybrid cooperative positioning, where we assume that the nodes include both a GNSS receiver and a terrestrial ranging system to estimate the distance from their neighbors. Messages containing node position information are exchanged in the P2P network. Each node merges the satellite and the terrestrial ranging information by using a proper estimation algorithm to compute its position.
This approach can provide significant improvements in terms of availability for GNSS-denied nodes: in fact, nodes having fewer than four satellites in sight may be able to compute their position by using terrestrial ranging and neighbors’ information. Moreover, the technique may also improve the accuracy of the position of nodes tracking more than four satellites.
P2P hybrid cooperative positioning requires no infrastructure: each node performs its computation independently, starting from its pseudorange estimation, its terrestrial range measurements, and the messages received from neighboring peers. In particular, beacons are not required. (A beacon, also called an anchor, is a node with a priori knowledge of its position.) Therefore, the system can work even if none of the nodes in the network have visibility to at least four satellites.
Figure 1 depicts an example of a possible P2P hybrid cooperative positioning scenario. The blue lines represent pseudorange measurements. Because none of the nodes have visibility to at least four satellites, none of them can compute its position using only GNSS. By using terrestrial ranging measurements (red lines) and message exchange, all the nodes may become able to individually compute their position in a global coordinate system such as the WGS-84.
Ranging for P2P Hybrid Cooperative Positioning
GNSS Receiver. A mass market GNSS receiver is sufficient to implement the hybrid cooperative positioning approach. The only requirement is that the pseudorange measurements must be provided by the GNSS receiver, since they must be merged with the terrestrial ranging data in a tightly coupled approach.
Terrestrial Ranging System. The terrestrial ranging system allows us to estimate the distance from a neighboring node.
Many terrestrial ranging methods can be employed. Since we are focusing on P2P networks composed of small portable devices, we consider the following two ranging techniques, which are specifically suitable for such devices.
Received Signal Strength (RSS). The node measures the power of a signal transmitted by a neighbor. If we know the transmitted power and environmental parameters, the distance can be estimated by inverting a proper path loss model. RSS ranging is very simple but, unfortunately, it suffers from important drawbacks. The connection between the transmitted and the received power strongly depends on the environment. In general, the accuracy achieved is not very good and for some applications it may be not sufficient.
Time of Flight. The node measures the time needed to travel to/from a neighboring node. The intra-node distance is then estimated by taking into account the speed of light. To avoid the need for time synchronization between nodes, two-way time-of-arrival (TOA) ranging can be used.
Figure 2 illustrates this technique. The yellow node sends a message to the red one at time t. The red node receives the message, processes it for a time ε, and finally sends back a message containing the time delay ε. The yellow node receives the message, computes the total elapsed time (2Δ+ε), and subtracts the time delay ε introduced by the red node, obtaining an estimation of the time of flight, Δ. By using the speed of light, c, it finally computes an estimation of the ranging distance, d: dˆ=cΔ. (Note that the error due to device clock drift during ranging measurement is negligible.)
Many other techniques can be used for terrestrial ranging, including Doppler measurement (requires movement), angle of arrival (requires multiple antennas), and time difference of arrival (requires all nodes except one to be synchronized). However, such methods are less appropriate for the low-cost P2P devices considered in this article.
Concerning terrestrial ranging signals, many studies have addressed hybrid positioning that integrates GNSS with terrestrial ranging obtained from the so-called “signals of opportunity,” i.e., signals generated by wireless systems such as GSM/UMTS, DVB-T, and WiFi, which were designed for a purpose other than navigation. In fact, by computing the distance of a receiver from some fixed stations, it may be possible to integrate the GNSS pseudoranges, when their number is not sufficient to fix the position.
The latter approach has been investigated for several systems. Clearly, it relies on a terrestrial infrastructure, which may not always be available, and may also require a calibration phase (for example, to exactly compute the emitter position, when unknown).
In our framework, we are more interested in terrestrial ranging between mobile devices. In this case, short-range wireless systems like Bluetooth, Low rate WPAN (Wireless Personal Area Networks based on the 802.15.4 standard), WiFi, and ultrawideband can be employed. Among these, the last two look promising for our application.
WiFi (802.11). Different versions of WiFi systems are available with various modulation formats, including spread spectrum and orthogonal frequency-division multiplexing (OFDM). Most commercial WiFi receivers can easily provide RSS information. As an alternative, two-way TOA ranging can be obtained via WiFi signals by properly managing the node communication protocol.
As shown in the document “Peer to Peer Positioning — Final Report,” from Politecnico di Torino and others, listed in the Additional Resources near the end of this article, the reliability achieved by WiFi RSS is often poor. Thus, TOA is preferred for applications requiring high position accuracy.
UltraWideBand (UWB). With a clock resolution on the order of nanoseconds, UWB offers submeter TOA ranging accuracy, according to results described in the article by R. Cardinali et alia (see Additional Resources). UWB modules are available (even if they are currently far less popular than WiFi modules), and results from UWB ranging based on real measurements show that this technique has very good potential.
Signal propagation through most obstacles is not a big problem with UWB, though this depends on the material. UWB devices are also effective in non-line-of-sight (NLOS) conditions, propagating through two (sometimes even three) walls. The main problem with obstacles is signal attenuation, which may result in the first path not being detected, thus resulting in a positive ranging error. Multipath is also not a large factor as long as the direct-path signal is sufficiently strong.
An important note: the most significant problem for UWB ranging may be the presence of strong reflectors. In fact, these can occasionally generate large outliers. In combination with a blocked direct path, this may lead to errors that cannot be detected. Many of these problems can be taken care of through outlier detection at the PVT (position, velocity, time) level. Nevertheless, if the system is deployed in an environment with many thick walls with lots of metal, the performance of the system may deteriorate.
Addressing the two systems previously identified, WiFi is very popular and its radio interface is implemented in many portable devices. Moreover, some car companies already have prototypes for P2P car communications based on the emerging standard for Dedicated Short Range Communications (DSRC) (see ETSI in Additional Resources), which uses WiFi signals. Currently, UWB is used much less often.
Considering the current state of the art, a possible P2P hybrid cooperative positioning solution could be as follows: In cases where a very high level of accuracy is required, complex devices that incorporate UWB for TOA ranging (and UWB or WiFi or any other system for message exchanging) could be used. In cases where such a high level of accuracy is not required, simpler devices could employ WiFi for both communication and terrestrial ranging. (Whenever possible, TOA ranging should still be used: RSS WiFi ranging is suggested only when large errors — e.g., 50 meters or more — are acceptable).
Cooperative Positioning Procedure
Equation 1 (inset photo, above right)
where c is the speed of light, δm is the clock bias between the user receiver and the satellite constellation, and vi is the pseudorange noise for this measurement.
Similarly, by using its terrestrial ranging system, the node computes a set of M range measurements from its neighboring nodes. Assuming that RSS or two-way TOA is employed, no synchronization is needed, and each range measurement defines a sphere centered at the neighbor node’s coordinates (xj, yj, zj) with radius rj:
Equation 2 (inset photo, above right)
where μi is the range noise for this measurement.
To compute its position, the node must solve the (typically over-determined) set of (N+M) equations. While the satellite coordinates are accurately estimated from the ephemeris data, the other node coordinates are not. Each node only knows an estimate of its actual position, which is shared with its neighbors via the communication system.
Because this approach assumes that no fusion center is needed, each node computes its position iteratively. Figure 3 illustrates the procedure adopted by a P2P network to perform hybrid cooperative positioning in more detail. Time is slotted and within any interval each node must perform two operations: terrestrial range and pseudorange measurements, and position computation.
During the first phase, the node measures the pseudoranges of the satellites in view. Meanwhile, it uses its terrestrial ranging system for estimating the distance to its neighbors.
In Phase 2, each node computes its position by applying a given number I of iterations. For each iteration, the node (given its current position estimation, the new pseudorange measurements, the new terrestrial range measurements, and the incoming message from its neighbors containing their current position estimation) applies an algorithm to update its position values and sends a message to its neighbor nodes containing its updated position values.
These operations are performed for I iterations (in Figure 3, I=3; generally a small number I is sufficient to achieve good accuracy). At the end of the last iteration, each node has its final estimated position value.
In the following time slot, the procedure is repeated: new pseudo-range/terrestrial range measurements are taken and a new position estimation is produced. Depending on the node mobility, the time slot duration and the number of iterations can be changed by finding a proper trade-off between number of operations (and power consumption) and precision.
Fully distributed, cooperative versions of these algorithms were developed through the study described in the “Peer-to-Peer Positioning – Final Report” cited earlier. We will briefly discuss their characteristics here.
Least Squares. Least Squares (LS) is one of the most widely used deterministic techniques for solving the Position Time problem. Given the measurements, the coordinate values are chosen to minimize a given error function. Each terrestrial range measurement can be weighted by the estimated accuracy of the corresponding neighboring node position.
The main advantage of the algorithm is its simplicity. The main drawback is that it does not consider the measurement statistical model. Moreover, it does not have a prediction phase that could be leveraged to take into account mobility.
Two versions of a hybrid cooperative weighted least square algorithm were developed by Politecnico di Torino and others in the P2P positioning report. Various methods can be used to minimize the algorithm cost function (see also the articles by H. Wymeersch et alia, G. Heinrichs et alia, and M. A. Caceres listed in Additional Resources). The P2P positioning report considered an iterative linearization of the cost function to a first-order Taylor series expansion around an a priori estimate. (A damping factor was introduced in order to cope with possible divergence.)
Kalman Filter. The Kalman filter is very popular in navigation because it provides an elegant and efficient tracking solution for mobile nodes. The algorithm takes into account the statistical modeling of state and measurements, even though it relies on a Gaussian distribution assumption. Due to the non-linear nature of the observed pseudoranges and terrestrial ranges, some linearization must be performed for solving the PVT problem.
The extended Kalman filter (EKF), which linearizes both process and observation models, is widely employed for tracking in GNSS receivers, and is considered the de facto standard in non-linear state estimation. A hybrid cooperative EKF algorithm was presented in the P2P positioning report. For further details, see the articles by M. A. Caceres and M. A. Caceres et alia (2010).
To improve the performance of the Kalman filter for cooperative positioning scenarios, we also studied a different version of the algorithm, based on the unscented Kalman filter (UKF). In the UKF, the probability density is approximated by the nonlinear transformation of a random variable. This returns much more accurate results than Taylor expansions of the nonlinear functions in the EKF.
The approximation utilizes a set of sample points, which guarantees accuracy with the posterior mean and covariance to the second order for any nonlinearity. In addition, this technique removes the requirement to explicitly calculate Jacobians, which for complex functions can be a difficult task in itself. Two versions of the UKF with different complexity have been developed by Politecnico di Torino and others in the P2P positioning Report (see also the articles by M. A. Caceres and M. A. Caceres et alia ).
Particle Filter. The particle filter (PF) is a sequential Monte Carlo method based on point mass (or particle) representation of probability densities. Provided that a sufficient number of particles is employed, a PF approaches the Bayesian optimal estimate without requiring Gaussian distributions and linear systems.
A hybrid cooperative version of PF was developed in the P2P positioning report and is also described in the article by F. Sottile et alia. A common problem with the particle filter is the degeneracy phenomenon (after a few time iterations all but one particle have negligible weight). To reduce this, a resampling algorithm can be adopted, which eliminates particles that have small weights and concentrates on particles with large weights. The PF method requires a good initial position estimate. A simple Kalman filter can be used to initialize the algorithm.
Sum Product. A cooperative positioning method using belief propagation on factor graphs was originally proposed in the paper by H. Wymeersch et alia. The algorithm, called the Sum Product Algorithm over a Wireless Network (SPAWN), was shown to provide accurate position estimates even in challenged indoor environments.
In the original study, SPAWN was based on terrestrial ranging only. This algorithm was extended to a hybrid approach described in the article by M. A. Caceres et alia (2011). The new algorithm, called Hybrid Sum Product Algorithm over a Wireless Network (hSPAWN), must take into account one additional variable: the receiver clock error with respect to GNSS System Time.
hSPAWN can be implemented in a fully distributed way through local exchange of messages between pairs of neighboring nodes. Because it relies on a probabilistic, Bayesian approach, all quantities of interest (e.g., position and bias estimates, and terrestrial range/pseudorange measurements) are modeled as probability distribution functions. More details on the algorithm are provided in the sidebar, “The hSPAWN Algorithm.”
Similar to the particle filter method, hSPAWN requires a good initial position. For this, a simple Kalman filter can again be used to initialize the algorithm.
Improvements in Cooperative Algorithms
This censoring method is very useful in the presence of dense networks (i.e., P2P networks with a medium/high average number of neighbors per peer). In this case, it assures faster peers’ convergence and limits the complexity of data processing as well as the amount of exchanged data.
However, this method may be suboptimal for sparse networks (i.e., P2P networks with a low average number of neighbors per peer). In such cases, low-quality data from non-reliable peers may be useful and worth keeping in the cooperative positioning computations, as such data may improve availability (even at the price of a much longer convergence time). Therefore, the best solution would be to use an adaptive censoring approach, which adjusts the robustness thresholds according to both the number of neighbors per peer and the current position estimation availability.
Many other details on cooperative algorithms can be found in the P2P positioning report where additional results are also presented such as the effect of measurement noise and the effect of “malicious” nodes.
The environment divides the nodes into three classes: The black nodes (external region) have at least four satellites in view (for example, through windows). The blue nodes (middle region) have only one, two, or three satellites in view. The red nodes (inner region) are deep indoors and have no satellites in view.
The black nodes (Numbers 1, 3, and 5 in the figure) can compute their position independently by using GNSS only, while the blue nodes (Numbers 2, 4, and 6) and red nodes (Number 7) cannot. By applying a hybrid cooperative approach, the blue nodes and the red nodes may be able to compute their position, too.
The root mean square errors (RMSEs) of the 3D position–estimate evolution for each of the seven nodes, achieved by the hybrid cooperative particle filter, is plotted versus time in Figure 5. For the sake of simplicity, we assumed that all nodes had an indoor pseudorange standard deviation of 15 meters.
We considered a terrestrial ranging standard deviation of 20 centimeters (a value obtained from UWB TOA measurements; see the article by R. Cardinali et alia). All nodes are able to communicate with their neighbors within a distance of 35 meters.
We consider 20 time slots — for simplicity, each of these has a duration of one second. Within each time slot, every node performs terrestrial range/pseudorange measurements and I=3 iterations (position computation/message exchange), according to the scheme depicted in Figure 4. (The simulations assume that, at the beginning, the nodes have no information on their position. We then suppose that their initial estimate is uniformly distributed over the entire indoor environment.)
From the simulation results, we can see that initially only the three nodes with at least four satellites in view (Nodes 1, 3, and 5) can compute their position. Over time, however, we see that all nodes (including Node 7 which is deep indoors) are able to compute their position thanks to cooperation.
A comparison between different estimation algorithms is presented in Figure 6, where the horizontal RMSE (averaged over all nodes) is plotted versus time for all the considered algorithms, showing their difference in convergence behavior.
Scenario B — Many Peers, Static. This scenario is depicted in Figure 7 and represents a large network composed of 100 nodes, deployed in an indoor environment 50 x 50 meters in size. All nodes are static.
The position RMSE evolution for each node, achieved by the hybrid cooperative particle filter is plotted in Figure 8. After a certain period, all nodes are able to compute their position thanks to cooperation.
The position RMSE evolution for each node, achieved by the hybrid cooperative particle filter is plotted in Figure 10. Except for the first epoch, all the nodes have become able to compute their position thanks to cooperation.
Comments on Algorithm Performance
With regard to the different algorithms, the particle filter typically provides the best performance, followed by the unscented Kalman filter and hSPAWN. Least square achieves the worst performance.
An analysis of the algorithm complexity was performed by Politecnico di Torino in the P2P positioning report. The most complex algorithms turn out to be hSPAWN and the particle filter. The unscented Kalman filter and least-square algorithms are the least complex.
Thanks to its excellent trade-off between performance and complexity, the unscented Kalman filter is a very good candidate for cooperative positioning implementation on simple devices. On the other hand, hSPAWN is the most innovative algorithm and can be used for applications requiring very good accuracy, similar to particle filter which typically provides the best performance. Least squares can be used for very simple applications where a limited accuracy is sufficient.
A number of considerations for the algorithms, their complexity, and the practical feasibility of P2P hybrid algorithms were described in the P2P positioning report. Clearly, cooperative algorithms raise interesting questions concerning media access control (MAC) protocol issues, too. Cooperation leads to delays, because the nodes need to access the same channel. Hence, more peers will lead to larger delays, which is especially problematic in mobile scenarios (see, for example, the article by F. Sottile et alia).
Conclusions and Applications
The message exchange can be performed in an unstructured P2P way, without requiring any fixed infrastructure. No data fusion center is needed, since each node can perform its operation individually. No beacons with a priori knowledge of their position are required because the method can work even if none of the nodes have full satellite visibility.
The approach allows dramatic improvements in position availability in GNSS-hostile environments like buildings, urban and natural canyons, and so forth. The applications are innumerable and include indoor positioning, the “Internet of things,” tracking of moving objects in GNSS-challenged areas, and so on.
A wide range of terrestrial ranging systems and techniques and estimation algorithms are available for hybrid positioning. Ad hoc cooperative networks can be implemented today. As an example, WiFi/UWB two-way TOA ranging combined with an unscented Kalman filter could represent an interesting solution for less complex devices.
Moreover, in the future, devices will be more and more inter-connected. This will be true for both portable devices and car systems and will also include opportunistic networks formed by users connected for a limited amount of time. By including position information in the exchanged messages, cooperative positioning can become a reality and strongly improve the positioning capability of each device in GNSS-hostile environments.
Copyright © 2013 Gibbons Media & Research LLC, all rights reserved.