Particle filtering, based on a stochastic process, is another approach to the map-matching problem. Particle filters are recursive implementations of Monte Carlo-based statistical signal processing (Crisan & Doucet, 2002). Gustafsson et al. (2002) evaluate in real time a map-matching particle filter used to match a vehicle's horizontal driven path to a digital roadway map. They conclude that the particle filter converged relatively rapid after a few iterations of the algorithm. The challenge of this map-matching technique is to find nonlinear relations and non-Gaussian sensor models that provide the most information about the vehicle's position. The authors assert that research is still needed to seek a reliable way to detect divergence and to restart the filter.

Toledo-Moreo et al. (2009) present a multiple-hypothesis particle-filter based algorithm to solve the map-matching problem with integrity provision at the lane level. The proposed system joins measurements from a GPS receiver, an odometer, and a gyroscope along with road information in digital maps. A set of six experiments were conducted with real data for

a period of 30 minutes proving the feasibility of the approach for lane-level applications. The authors mention that outlier removal, multipath effect mitigation, and additional method validation are tasks that need to be addressed in the future.

## **2.6 Personal navigation assistants and map-matching**

218 Global Navigation Satellite Systems – Signal, Theory and Applications

Yet another map-matching algorithm based on fuzzy theory is proposed by Guo and Luo (2009). First, the algorithm compares the similarity degree between the trajectory curve of the road and all candidate roads to identify the road on which a vehicle is traveling. Subsequently, fuzzy preference relations are adopted to perform a multi-criteria decision and a look-ahead technique is employed to improve the matching accuracy. The algorithm

There has been abundant research on application of Kalman filters in combination with GPS and dead-reckoning signals to solve spatial mismatches. This integrated technology improves positioning accuracy by estimating white noise and error in the GPS and then correcting the vehicle's position (Jo et al., 1996; W. Kim et al., 2000; Zhao et al., 2003). For example, Quddus et al. (2003) present a general map-matching algorithm that integrates GPS and dead-reckoning sensor data (position, velocity, and time) through an extended Kalman filter and uses them as input to improve performance of the algorithm. The physical location of the vehicle on a roadway link is determined empirically from the weighted averages of two state determinations of the vehicle position based on topological

Yang et al. (2003) present an improved map-matching algorithm that employs Kalman filtering to filter unreasonable GPS data and the Dempster-Shafer (D-S) theory to correctly snap GPS vehicle coordinates to the digital roadway map. The D-S theory allows explicit representation of ignorance and combination of evidence and operates with a smaller set of uncertainties. Although the authors report satisfying results, they suggest additional

Nassreddine et al. (2009) describe a map-matching method based on D-S theory and interval analysis to compute accurate vehicle positions from an initial estimated position on a digital road network. The authors state that the proposed technique proves to be successful at junctions and parallel roads. However, real world data needs to be examined in addition to

Particle filtering, based on a stochastic process, is another approach to the map-matching problem. Particle filters are recursive implementations of Monte Carlo-based statistical signal processing (Crisan & Doucet, 2002). Gustafsson et al. (2002) evaluate in real time a map-matching particle filter used to match a vehicle's horizontal driven path to a digital roadway map. They conclude that the particle filter converged relatively rapid after a few iterations of the algorithm. The challenge of this map-matching technique is to find nonlinear relations and non-Gaussian sensor models that provide the most information about the vehicle's position. The authors assert that research is still needed to seek a reliable

Toledo-Moreo et al. (2009) present a multiple-hypothesis particle-filter based algorithm to solve the map-matching problem with integrity provision at the lane level. The proposed system joins measurements from a GPS receiver, an odometer, and a gyroscope along with road information in digital maps. A set of six experiments were conducted with real data for

requires testing and analysis with GPS data in addition to cell phone positions.

**2.4 Kalman filter approach**

information and external sensors.

**2.5 Particle filtering and map-matching**

way to detect divergence and to restart the filter.

simulated data.

research to verify the accurate performance of the algorithm.

White et al. (2000) discuss solutions to the map-matching problem for personal navigation assistants (PNA). Four different map-matching algorithms were implemented and tested: 1) use of minimum distance (point-to-curve), 2) comparison of heading information with arc and trajectory, 3) use of topology to select roads that are reachable from the current road, and 4) construction of piece-wise linear curves from different paths, followed by comparison of them to centerline curves using points (curve-to-curve matching). The authors conclude that these algorithms performed better when the distance between the GPS point and the closest road is small and that correct matches tend to occur at greater speeds on straight roadways.

Freitas et al. (2009) explain the necessity of map-matching algorithms to correctly locate GPS positions on a map when using PNA, particularly for dynamic route guidance systems. The authors describe an approach to update digital maps through the use of GPS points, in order to identify map incongruence. The proposed system was designed as a prototype and lacks of extensive testing, however, it correctly processes and implements methods for mapmatching and detecting discrepancies between the real network and digital maps.

## **2.7 Topological network-based algorithms**

Taylor et al. (2001) describe an algorithm called "Road Reduction Filter (RRF)" that uses differential corrections and height aids. RRF identifies all possible roadway candidates while systematically removing incorrect ones. RRF is improved by using shortest path network analysis and drive restriction information. A shortest path network routine calculates the distance through the roadway network from a vehicle's previous position to each potential present position offered by the algorithm. The drive restriction information routine selects roadways using direction and access information.

Greenfeld (2002) presents a map-matching procedure that consists of two algorithms. One algorithm assesses similarity between characteristics of the roadway network and the positioning pattern of the vehicle. The second algorithm performs topological analysis and applies a weighting scheme to match each GPS data point to the roadway network. The highest weighted score determines the most likely candidate for a correct match. The author indicates that further research is needed to determine the correct position of the vehicle along a roadway segment and to verify the accuracy performance of the algorithms.

Doherty et al. (2000) studied an algorithm that automatically matches GPS data points to roadway segments along a network. First, the algorithm joins GPS points to create a linear object forming the vehicle's track. Subsequently, it creates a buffer zone around the linear object, and then identifies all the roadways that are totally included within the buffer to select the correct one.

Marchal et al. (2005) presents an innovative map-matching algorithm that relies on GPS measurements and network topology. The algorithm consists of maintaining a set of

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 221

The decision-rule topological map-matching algorithm determines the correct roadway centerline for vehicle travel by obtaining feasible shortest paths between snapped GPS data points in post-processing mode. The algorithm selects all roadways within a buffer around a GPS data point and snaps the point to the closest roadway by obtaining the minimum perpendicular distance from the data point to each roadway. Figure 3 illustrates that GPS data points 1 and 2 (shown as circles) are snapped to ramp 2 because it is the closest roadway contained with the buffers around the points. Subsequently, the shortest path (displayed with a bold arrow) is obtained between the two snapped GPS data points S1 and S2 (shown as squares). Only paths that follow allowable traffic directions and allowable turns are employed. The travel speed between these two snapped GPS points is determined by the length of the shortest path and the difference in time stamps for the points. The computed speed is compared to the average of the speeds at the data points collected by the vehicle while traveling. If the computed speed is within a specified tolerance of the average recorded speed, then the obtained shortest path is viable and the snapped locations for

Fig. 3. Example of Snapping to the Correct Roadway for Two GPS Data Points Using the

The map-matching algorithm advances to GPS data point 3, snaps this point to the closest roadway centerline within its buffer, and calculates the shortest path between snapped point S2 and the newly-snapped GPS data point S3. If the path between S2 and S3 is not feasible because the speed comparison yields a large disparity, then the algorithm determines if feasible routes exist between the preceding and subsequent points bounding the GPS data points of concern, as illustrated in the example of Figure 4. This example shows that there is no feasible path between snapped points S2 and S3 when network topology and turn restrictions are employed. Therefore, the map-matching algorithm looks

GPS Data Point

Perpendicular Road

Nearest

Point

**3. Decision-rule topological map-matching algorithm**

**3.1 Description**

points 1 and 2 are accepted as correct.

Map-Matching Algorithm

candidate paths as GPS data are processed and computing matching scores for each path. The path with the best score represents the correct vehicle route. According to the authors further research is needed to improve the robustness of the algorithm.

Yet another topological map-matching algorithm is proposed by Wang and Yang (2009). The algorithm presents high accuracy and solves spatial ambiguities in complex roadway networks, specifically near intersections and parallel roads. Nevertheless, the topological algorithm was tested on only four road intersections with a 2-second sampling interval of GPS measurements.

Velaga et al (2009) describe an enhanced weight-based topological map-matching algorithm for ITS. The algorithm was tested with real data under different operational environments. However, the optimal algorithmic weights for different factors such as heading, proximity, connectivity, and turn-restriction still need to be estimated with a range of real-world field data from different road environments.

Blazquez and Vonderohe (2005) propose a topological map-matching algorithm that resolves spatial ambiguities that occur with intelligent winter maintenance vehicle data collected in Wisconsin. The algorithm computes shortest paths between snapped GPS data points using network topology and turn restrictions. If similarity exists between calculated and recorded vehicle speed values, then the path is feasible and snapped GPS locations are correct. If the path is not viable, then GPS data points are snapped to alternative roadway centerlines, shortest paths are recalculated, and speeds are again compared. The authors studied this problem further and published the effects of controlling parameters on the performance of the map-matching algorithm (Blazquez & Vonderohe, 2009). The current chapter discusses and describes in more detail the performance analysis of this mapmatching algorithm.

## **2.8 Other map-matching algorithms**

According to Zhao (1997), many pattern recognition methods (e.g., neural network) could be used for map-matching. Neural networks are dynamic systems that consist of many interconnected layered nodes (neurons). These networks need to be trained to arrange the layers and interconnections to model real-world applications. Other pattern recognition methods can be used to work with positioning sensors such as GPS. The underlying principle of these methods is that the digital map is used to filter out vehicle sensor errors and to determine the best position.

Schlingelhof et al. (2008) present a two-dimension map-matching algorithm based on a lanelevel model. The output of this algorithm is the road segment identification number, the relative vehicle position along this segment, and the relative transversal vehicle position with respect to one of the border lines. The road selection algorithm consists of extracting candidate segments, computing positioning solution residuals, and selecting the most likely segment. The authors state that the first results obtained with real measurements are encouraging. However, these should be generalized to enhanced maps.

Li et al. (2005) present a novel map-matching method using least-squares position estimation, and digital mapping and height data to augment the vehicle position calculation. Experiment results indicate that combining the algorithm with height aiding improves the vehicle position accuracy when the number of visible satellites is reduced.

## **3. Decision-rule topological map-matching algorithm**

## **3.1 Description**

220 Global Navigation Satellite Systems – Signal, Theory and Applications

candidate paths as GPS data are processed and computing matching scores for each path. The path with the best score represents the correct vehicle route. According to the authors

Yet another topological map-matching algorithm is proposed by Wang and Yang (2009). The algorithm presents high accuracy and solves spatial ambiguities in complex roadway networks, specifically near intersections and parallel roads. Nevertheless, the topological algorithm was tested on only four road intersections with a 2-second sampling interval of

Velaga et al (2009) describe an enhanced weight-based topological map-matching algorithm for ITS. The algorithm was tested with real data under different operational environments. However, the optimal algorithmic weights for different factors such as heading, proximity, connectivity, and turn-restriction still need to be estimated with a range of real-world field

Blazquez and Vonderohe (2005) propose a topological map-matching algorithm that resolves spatial ambiguities that occur with intelligent winter maintenance vehicle data collected in Wisconsin. The algorithm computes shortest paths between snapped GPS data points using network topology and turn restrictions. If similarity exists between calculated and recorded vehicle speed values, then the path is feasible and snapped GPS locations are correct. If the path is not viable, then GPS data points are snapped to alternative roadway centerlines, shortest paths are recalculated, and speeds are again compared. The authors studied this problem further and published the effects of controlling parameters on the performance of the map-matching algorithm (Blazquez & Vonderohe, 2009). The current chapter discusses and describes in more detail the performance analysis of this map-

According to Zhao (1997), many pattern recognition methods (e.g., neural network) could be used for map-matching. Neural networks are dynamic systems that consist of many interconnected layered nodes (neurons). These networks need to be trained to arrange the layers and interconnections to model real-world applications. Other pattern recognition methods can be used to work with positioning sensors such as GPS. The underlying principle of these methods is that the digital map is used to filter out vehicle sensor errors

Schlingelhof et al. (2008) present a two-dimension map-matching algorithm based on a lanelevel model. The output of this algorithm is the road segment identification number, the relative vehicle position along this segment, and the relative transversal vehicle position with respect to one of the border lines. The road selection algorithm consists of extracting candidate segments, computing positioning solution residuals, and selecting the most likely segment. The authors state that the first results obtained with real measurements are

Li et al. (2005) present a novel map-matching method using least-squares position estimation, and digital mapping and height data to augment the vehicle position calculation. Experiment results indicate that combining the algorithm with height aiding improves the

encouraging. However, these should be generalized to enhanced maps.

vehicle position accuracy when the number of visible satellites is reduced.

further research is needed to improve the robustness of the algorithm.

GPS measurements.

matching algorithm.

data from different road environments.

**2.8 Other map-matching algorithms**

and to determine the best position.

The decision-rule topological map-matching algorithm determines the correct roadway centerline for vehicle travel by obtaining feasible shortest paths between snapped GPS data points in post-processing mode. The algorithm selects all roadways within a buffer around a GPS data point and snaps the point to the closest roadway by obtaining the minimum perpendicular distance from the data point to each roadway. Figure 3 illustrates that GPS data points 1 and 2 (shown as circles) are snapped to ramp 2 because it is the closest roadway contained with the buffers around the points. Subsequently, the shortest path (displayed with a bold arrow) is obtained between the two snapped GPS data points S1 and S2 (shown as squares). Only paths that follow allowable traffic directions and allowable turns are employed. The travel speed between these two snapped GPS points is determined by the length of the shortest path and the difference in time stamps for the points. The computed speed is compared to the average of the speeds at the data points collected by the vehicle while traveling. If the computed speed is within a specified tolerance of the average recorded speed, then the obtained shortest path is viable and the snapped locations for points 1 and 2 are accepted as correct.

Fig. 3. Example of Snapping to the Correct Roadway for Two GPS Data Points Using the Map-Matching Algorithm

The map-matching algorithm advances to GPS data point 3, snaps this point to the closest roadway centerline within its buffer, and calculates the shortest path between snapped point S2 and the newly-snapped GPS data point S3. If the path between S2 and S3 is not feasible because the speed comparison yields a large disparity, then the algorithm determines if feasible routes exist between the preceding and subsequent points bounding the GPS data points of concern, as illustrated in the example of Figure 4. This example shows that there is no feasible path between snapped points S2 and S3 when network topology and turn restrictions are employed. Therefore, the map-matching algorithm looks

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 223

Fig. 5. Flow Diagram with the Step Sequence of the Map-Matching Algorithm

The example illustrated in Figure 6 includes a set of Differential GPS (DGPS) data points collected every five seconds by a winter maintenance vehicle during the 2002-2003 winter season in Columbia County, Wisconsin. The spatial mismatch, occurring at the diverging roadways in this figure, is resolved by implementing the decision-rule map-matching algorithm. Points 0, 2, 3, and 4 are snapped to the nearest roadway within their 35-foot buffers, resulting in points S0, S2, S3, and S4 (shown as rectangles). Points S0, S3, and S4 are on the Interstate 39 centerline, while point S2 is situated on the ramp centerline. Note that no roadways are contained within the buffer for GPS data point 1, thus, this point is not used in

**3.2 Example of an implementation of the algorithm**

determining the feasible path.

ahead by snapping point 4 to the nearest roadway centerline within its buffer, and determines if the shortest path between snapped points S3 and S4 is possible. Since the tested path is not feasible, the algorithm snaps point 3 to the next nearest roadway centerline within its buffer obtaining point alt3, shown as a triangle.

Fig. 4. Example of an Alternative Roadway Centerline Snapping

Subsequently, the upper part of the algorithm (shown in Figure 5) for alternative roadway centerline search and feasibility path check is initiated. This algorithm verifies if a path is feasible between the alternative snapped location for point 3 (where Ki = 3), and former and succeeding neighboring snapped points 2 and 4 (where Ki-1 = 2 and Kj = 4). If the shortest paths between these three points are not feasible because the speed comparison fails, then the algorithm searches for other roadway centerlines within the buffer around point 3 that have not already been used in a feasibility path check. When finding a new candidate, point 3 is then snapped to it and the feasibility of shortest paths between snapped points 2, 3, and 4 (Ki-1, Ki, Kj) is checked again. If these paths are feasible, then the spatial ambiguity is resolved, and the algorithm terminates. If no alternative roadway centerline exists within the buffer for GPS data point 3, then the algorithm continues by snapping data point 4 to alternative roadway candidates contained within its buffer, and the upper part of the algorithm is executed again. If no other roadway centerlines exist within the buffer of GPS data point 4 or no feasible paths are obtained, then the lower part of the algorithm is executed and feasible paths between preceding and subsequent data points are examined. If none of the consecutive data points aid in solving the spatial mismatch between the snapped points for 2 and 3, then it is likely that no roadway centerlines within their buffers yield a feasible path and larger buffers and/or more consecutive data points need to be utilized by the algorithm. Once a feasible path is obtained, the intermediate points not employed during the map-matching process are snapped to the roadway along that feasible path.

222 Global Navigation Satellite Systems – Signal, Theory and Applications

ahead by snapping point 4 to the nearest roadway centerline within its buffer, and determines if the shortest path between snapped points S3 and S4 is possible. Since the tested path is not feasible, the algorithm snaps point 3 to the next nearest roadway centerline

Subsequently, the upper part of the algorithm (shown in Figure 5) for alternative roadway centerline search and feasibility path check is initiated. This algorithm verifies if a path is feasible between the alternative snapped location for point 3 (where Ki = 3), and former and succeeding neighboring snapped points 2 and 4 (where Ki-1 = 2 and Kj = 4). If the shortest paths between these three points are not feasible because the speed comparison fails, then the algorithm searches for other roadway centerlines within the buffer around point 3 that have not already been used in a feasibility path check. When finding a new candidate, point 3 is then snapped to it and the feasibility of shortest paths between snapped points 2, 3, and 4 (Ki-1, Ki, Kj) is checked again. If these paths are feasible, then the spatial ambiguity is resolved, and the algorithm terminates. If no alternative roadway centerline exists within the buffer for GPS data point 3, then the algorithm continues by snapping data point 4 to alternative roadway candidates contained within its buffer, and the upper part of the algorithm is executed again. If no other roadway centerlines exist within the buffer of GPS data point 4 or no feasible paths are obtained, then the lower part of the algorithm is executed and feasible paths between preceding and subsequent data points are examined. If none of the consecutive data points aid in solving the spatial mismatch between the snapped points for 2 and 3, then it is likely that no roadway centerlines within their buffers yield a feasible path and larger buffers and/or more consecutive data points need to be utilized by the algorithm. Once a feasible path is obtained, the intermediate points not employed during the map-matching process are

within its buffer obtaining point alt3, shown as a triangle.

Fig. 4. Example of an Alternative Roadway Centerline Snapping

snapped to the roadway along that feasible path.

Fig. 5. Flow Diagram with the Step Sequence of the Map-Matching Algorithm

#### **3.2 Example of an implementation of the algorithm**

The example illustrated in Figure 6 includes a set of Differential GPS (DGPS) data points collected every five seconds by a winter maintenance vehicle during the 2002-2003 winter season in Columbia County, Wisconsin. The spatial mismatch, occurring at the diverging roadways in this figure, is resolved by implementing the decision-rule map-matching algorithm. Points 0, 2, 3, and 4 are snapped to the nearest roadway within their 35-foot buffers, resulting in points S0, S2, S3, and S4 (shown as rectangles). Points S0, S3, and S4 are on the Interstate 39 centerline, while point S2 is situated on the ramp centerline. Note that no roadways are contained within the buffer for GPS data point 1, thus, this point is not used in determining the feasible path.

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 225

Average Recorded Speed (mi/h)

Is Path Feasible?

Calculated Speed (mi/h)

S0 → S2 392.6 26.8 31.5 YES S2 → S3 5125.9 699 33 NO S3 → S4 213 29 35 YES S0 → alt2 392.8 26.8 31.5 YES alt2 → S3 215.7 29.4 33 YES

Table 1. Speed Comparison for Determining Feasibility of Shortest Paths

Fig. 7. DGPS Data Points Collected in Portage County Every 10 seconds

**4. Performance analysis of the decision-rule map-matching algorithm**

Success in solving spatial ambiguities depends on the values assigned to each variable of the map-matching algorithm. The analysis in this chapter examines the performance of the map-matching algorithm as values of the following parameters vary: 1) buffer size, 2) speed range, 3) number of consecutive data points, 4) temporal resolution, and 5) DGPS positional

The data employed in this study were collected by winter maintenance vehicles in Columbia and Portage Counties, Wisconsin, and Polk County, Iowa. These counties have different accuracy roadway centerline maps with 1:2,400, 1:12,000, and 1:100,000 nominal scales, respectively, and employ different AVL/DGPS systems for data collection. Selected data sets with sampling intervals of 2 and 10 seconds were collected for different storm events and vehicle operators driving through various routes over the 2000-2001, 2001-2002, and 2002-2003 winter seasons. These routes include federal, state, and interstate highways, and local roads. Figures 7, 8, and 9 display examples of data collected in Columbia, Portage, and Polk counties every 2, 10, and 10 seconds, respectively. Notice that none of the counties employed an integrated dead reckoning system and heading information was not available

Data Points

error.

**4.1 Spatial data description**

during the data collection process.

Shortest Path Distance (ft)

The shortest path between points S0 and S2 is computed using network topology and allowable turns. Consequently, the speed comparison shown in Table 1 is performed to determine if this path is feasible. In this case, the obtained path is feasible since the difference between the average calculated and recorded speeds (26.8 and 31.5 mi/h, respectively) is within tolerance (25 mi/h). Therefore, the current snapped positions for points 0 and 2 are initially assumed to be correct. The main algorithm continues by finding the shortest path between the next pair of snapped points, S2 and S3. This path is not feasible when using network topology because if the vehicle was located at S2, it would have to exit the ramp and travel approximately 5,125.9 feet in 5 seconds at an average speed of 699 mi/h to reach snapped point S3. Hence, either point S2 or S3 or both were snapped to an incorrect roadway centerline. The map-matching algorithm now obtains the shortest path between points S3 and S4 and determines that the difference between calculated and average recorded speeds with values of 29 mi/h and 35 mi/h, respectively, is within tolerance. Therefore, an alternative roadway centerline is sought within the buffer around point 2. Interstate 39 is found to be the next nearest roadway, resulting in alternative point alt2, shown as a triangle in Figure 6. Consequently, feasibility is checked for paths between the preceding points S0 and alt2, and between alt2 and its successor, snapped point S3. As indicated in Table 1, both computed shortest paths are feasible. The calculated speeds along these paths are within 25 mi/h of their respective average recorded speeds for the vehicle. Therefore, the spatial ambiguity at the diverging roadway is resolved and the correct roadway for point 2 is Interstate 39. Data point S1 is then obtained by snapping point 1 to the Interstate 39 centerline.

Fig. 6. Example of Map-Matching Algorithm at Diverging Roadways

Table 1. Speed Comparison for Determining Feasibility of Shortest Paths

## **4. Performance analysis of the decision-rule map-matching algorithm**

Success in solving spatial ambiguities depends on the values assigned to each variable of the map-matching algorithm. The analysis in this chapter examines the performance of the map-matching algorithm as values of the following parameters vary: 1) buffer size, 2) speed range, 3) number of consecutive data points, 4) temporal resolution, and 5) DGPS positional error.

### **4.1 Spatial data description**

224 Global Navigation Satellite Systems – Signal, Theory and Applications

The shortest path between points S0 and S2 is computed using network topology and allowable turns. Consequently, the speed comparison shown in Table 1 is performed to determine if this path is feasible. In this case, the obtained path is feasible since the difference between the average calculated and recorded speeds (26.8 and 31.5 mi/h, respectively) is within tolerance (25 mi/h). Therefore, the current snapped positions for points 0 and 2 are initially assumed to be correct. The main algorithm continues by finding the shortest path between the next pair of snapped points, S2 and S3. This path is not feasible when using network topology because if the vehicle was located at S2, it would have to exit the ramp and travel approximately 5,125.9 feet in 5 seconds at an average speed of 699 mi/h to reach snapped point S3. Hence, either point S2 or S3 or both were snapped to an incorrect roadway centerline. The map-matching algorithm now obtains the shortest path between points S3 and S4 and determines that the difference between calculated and average recorded speeds with values of 29 mi/h and 35 mi/h, respectively, is within tolerance. Therefore, an alternative roadway centerline is sought within the buffer around point 2. Interstate 39 is found to be the next nearest roadway, resulting in alternative point alt2, shown as a triangle in Figure 6. Consequently, feasibility is checked for paths between the preceding points S0 and alt2, and between alt2 and its successor, snapped point S3. As indicated in Table 1, both computed shortest paths are feasible. The calculated speeds along these paths are within 25 mi/h of their respective average recorded speeds for the vehicle. Therefore, the spatial ambiguity at the diverging roadway is resolved and the correct roadway for point 2 is Interstate 39. Data point S1 is then obtained by snapping point 1 to

the Interstate 39 centerline.

Fig. 6. Example of Map-Matching Algorithm at Diverging Roadways

The data employed in this study were collected by winter maintenance vehicles in Columbia and Portage Counties, Wisconsin, and Polk County, Iowa. These counties have different accuracy roadway centerline maps with 1:2,400, 1:12,000, and 1:100,000 nominal scales, respectively, and employ different AVL/DGPS systems for data collection. Selected data sets with sampling intervals of 2 and 10 seconds were collected for different storm events and vehicle operators driving through various routes over the 2000-2001, 2001-2002, and 2002-2003 winter seasons. These routes include federal, state, and interstate highways, and local roads. Figures 7, 8, and 9 display examples of data collected in Columbia, Portage, and Polk counties every 2, 10, and 10 seconds, respectively. Notice that none of the counties employed an integrated dead reckoning system and heading information was not available during the data collection process.

Fig. 7. DGPS Data Points Collected in Portage County Every 10 seconds

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 227

Correct and incorrect snaps are computed before and after applying the map-matching

Fig. 10. Example of Three Consecutive GPS Data Points Considered False Negatives

Figure 11 presents the cases of snapped and not snapped data points before and after applying the map-matching algorithm. The group of data points that does not snap to any roadway contains either FN or points that have no solution. Data points that have roadway centerlines within their buffers are either snapped correctly or incorrectly, or are FP. A data point that snaps incorrectly before applying the algorithm and snaps correctly afterwards is

**r r r**

Fig. 11. Cases for Data Points Snapped and Not Snapped Before and After Applying the

algorithm.

Algorithm

Fig. 8. DGPS Data Points Collected in Columbia County Every 2 seconds

Fig. 9. DGPS Data Points Collected in Polk County Every 10 seconds

## **4.2 DGPS data point classification**

This section identifies different cases (i.e., false negatives, false positives, no solution, incorrect and correct snap, and solved spatial ambiguities) obtained from comparing snapping results to the true roadway centerline on which a vehicle is traveling. The true vehicle path was obtained by performing a visual examination of the collected data. Data points are classified in these cases before and after applying the map-matching algorithm.

#### **4.2.1 False negatives and false positives**

False Negatives (FN) occur when data points fail to snap to any roadway centerline when they should have snapped to one. False Positives (FP) are data points that snapped to some roadway centerline when they should have not snapped to any centerline. Figure 10 shows an example of three successive GPS data points (1, 2, and 3) considered as FN. They should have snapped to Interstate 39 east bound direction, however, their buffers with radius r are too small to include any roadway centerline.

#### **4.2.2 Solved / not solved cases**

If roadway centerlines exist within the buffer of a data point, then a correct snap occurs when this point snaps along the true route of the vehicle. Conversely, an incorrect snap is obtained when a data point snaps to a roadway that is not on the true route of the vehicle. 226 Global Navigation Satellite Systems – Signal, Theory and Applications

Fig. 8. DGPS Data Points Collected in Columbia County Every 2 seconds

Fig. 9. DGPS Data Points Collected in Polk County Every 10 seconds

This section identifies different cases (i.e., false negatives, false positives, no solution, incorrect and correct snap, and solved spatial ambiguities) obtained from comparing snapping results to the true roadway centerline on which a vehicle is traveling. The true vehicle path was obtained by performing a visual examination of the collected data. Data points are classified in these cases before and after applying the map-matching algorithm.

False Negatives (FN) occur when data points fail to snap to any roadway centerline when they should have snapped to one. False Positives (FP) are data points that snapped to some roadway centerline when they should have not snapped to any centerline. Figure 10 shows an example of three successive GPS data points (1, 2, and 3) considered as FN. They should have snapped to Interstate 39 east bound direction, however, their buffers with radius r are

If roadway centerlines exist within the buffer of a data point, then a correct snap occurs when this point snaps along the true route of the vehicle. Conversely, an incorrect snap is obtained when a data point snaps to a roadway that is not on the true route of the vehicle.

**4.2 DGPS data point classification**

**4.2.1 False negatives and false positives**

too small to include any roadway centerline.

**4.2.2 Solved / not solved cases**

Correct and incorrect snaps are computed before and after applying the map-matching algorithm.

Fig. 10. Example of Three Consecutive GPS Data Points Considered False Negatives

Figure 11 presents the cases of snapped and not snapped data points before and after applying the map-matching algorithm. The group of data points that does not snap to any roadway contains either FN or points that have no solution. Data points that have roadway centerlines within their buffers are either snapped correctly or incorrectly, or are FP. A data point that snaps incorrectly before applying the algorithm and snaps correctly afterwards is

Fig. 11. Cases for Data Points Snapped and Not Snapped Before and After Applying the Algorithm

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 229

20 30 40 50 60 **Buffer Size (ft)**

Fig. 12. FN Percentages Before and After Applying Algorithm by Buffer Size for Columbia,

Before (Columbia) After (Columbia) Before (Portage) After (Portage) Before (Polk) After (Polk)

20 30 40 50 60 **Buffer Size (ft)**

Columbia Portage Polk

Fig. 13. Percentages of Solved Cases After Applying Algorithm by Buffer Size for Columbia,

Portage, and Polk Counties

0

Portage, and Polk Counties

10

20

30

40

50

**Percentage of DGPS Data Points**

60

70

80

90

100

**Percentage of DGPS Data Points**

regarded as a solved case. If a data point is snapped incorrectly before applying the algorithm and it is snapped incorrectly after applying the algorithm, then the spatial mismatch is not solved. If this occurs, then some neighboring data points may be left incorrectly snapped. Note that FN, FP, and no solution are not included in the solved and not solved case analysis.

In the following section of this chapter, FN data points are minimized and solved spatial mismatches are maximized after applying the algorithm. Although FP and no solution cases occur due to spatial database incompleteness, they amount to less than 0.5% of the total number of data points examined in this study. Therefore, these two cases were not taken into account in the analysis.

#### **4.3 Analysis of the impact of variables on the performance of the map-matching algorithm**

This section examines each algorithmic variable independently to determine its effect on the performance of the map-matching algorithm. These variables are classified into two groups. One group consists of parameters controlled by the user (i.e., buffer size, speed range, number of consecutive data points) and the other group comprises parameters controlled through the data (i.e., temporal resolution and DGPS error).

## **4.3.1 Buffer size**

The appropriate buffer size employed during the snapping process when solving spatial ambiguities depends on the quality and geometry of the spatial data. This proximity parameter used to select roadway centerlines around data points is critical for solving the map-matching problem and, therefore, for the success of the algorithm. Buffers that are overly small in size might not include any roadways. While extremely large buffers make the algorithm less efficient since it needs to examine more roadways, many of which will not be correct.

Roadways are typically represented by centerlines that do not account for lane widths. Therefore, data points will almost always appear offset some distance from roadway centerlines in addition to being affected by errors in the DGPS measurements and digital roadway maps (Wolf & Ghilani, 1997). Hence, the buffer size parameter was tested at 10-ft increments from 20 ft to 60 ft for data collected in Columbia and Portage Counties, and at 20-ft increments from 20 to 100 ft for data collected in Polk County. The latter is due to the smaller scale of the Polk County roadway centerline map. These buffer size values were predetermined through the computation of average distance percentages between the data points and roadway centerlines. As different buffer sizes were analyzed and tested against the map-matching algorithm, the speed range tolerance and number of consecutive data points were maintained constant with values 25 mi/h and 5, respectively.

Figure 12 shows a chart with the average percentages of FN before and after applying the algorithm, as the buffer size varies for Columbia, Portage, and Polk County. This figure indicates that lower FN percentages are obtained after applying the algorithm for all three counties. Portage and Polk counties present the largest decrease of FN percentages with an average difference of 20% before and after executing the algorithm. Overall, average percentages of FN data points diminish as the buffer size increases since more data points are snapped to roadway centerlines.

228 Global Navigation Satellite Systems – Signal, Theory and Applications

regarded as a solved case. If a data point is snapped incorrectly before applying the algorithm and it is snapped incorrectly after applying the algorithm, then the spatial mismatch is not solved. If this occurs, then some neighboring data points may be left incorrectly snapped. Note that FN, FP, and no solution are not included in the solved and

In the following section of this chapter, FN data points are minimized and solved spatial mismatches are maximized after applying the algorithm. Although FP and no solution cases occur due to spatial database incompleteness, they amount to less than 0.5% of the total number of data points examined in this study. Therefore, these two cases were not taken

**4.3 Analysis of the impact of variables on the performance of the map-matching**

through the data (i.e., temporal resolution and DGPS error).

This section examines each algorithmic variable independently to determine its effect on the performance of the map-matching algorithm. These variables are classified into two groups. One group consists of parameters controlled by the user (i.e., buffer size, speed range, number of consecutive data points) and the other group comprises parameters controlled

The appropriate buffer size employed during the snapping process when solving spatial ambiguities depends on the quality and geometry of the spatial data. This proximity parameter used to select roadway centerlines around data points is critical for solving the map-matching problem and, therefore, for the success of the algorithm. Buffers that are overly small in size might not include any roadways. While extremely large buffers make the algorithm less efficient since it needs to examine more roadways, many of which will not

Roadways are typically represented by centerlines that do not account for lane widths. Therefore, data points will almost always appear offset some distance from roadway centerlines in addition to being affected by errors in the DGPS measurements and digital roadway maps (Wolf & Ghilani, 1997). Hence, the buffer size parameter was tested at 10-ft increments from 20 ft to 60 ft for data collected in Columbia and Portage Counties, and at 20-ft increments from 20 to 100 ft for data collected in Polk County. The latter is due to the smaller scale of the Polk County roadway centerline map. These buffer size values were predetermined through the computation of average distance percentages between the data points and roadway centerlines. As different buffer sizes were analyzed and tested against the map-matching algorithm, the speed range tolerance and number of consecutive data

Figure 12 shows a chart with the average percentages of FN before and after applying the algorithm, as the buffer size varies for Columbia, Portage, and Polk County. This figure indicates that lower FN percentages are obtained after applying the algorithm for all three counties. Portage and Polk counties present the largest decrease of FN percentages with an average difference of 20% before and after executing the algorithm. Overall, average percentages of FN data points diminish as the buffer size increases since more data points

points were maintained constant with values 25 mi/h and 5, respectively.

are snapped to roadway centerlines.

not solved case analysis.

into account in the analysis.

**algorithm**

**4.3.1 Buffer size**

be correct.

Fig. 12. FN Percentages Before and After Applying Algorithm by Buffer Size for Columbia, Portage, and Polk Counties

Fig. 13. Percentages of Solved Cases After Applying Algorithm by Buffer Size for Columbia, Portage, and Polk Counties

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 231

increase in the percentage of solved cases remaining at 68% for Portage County data when speed range values equal to or greater than 25 mi/h are employed. The percentage of solved cases for Polk County remained constant at 50% for speed ranges equal to or greater than 15 mi/h, independent of buffer size. Thus, the map-matching algorithm is sensitive to speed range values, particularly when small speed ranges are employed since feasible paths are

> 20 30 40 50 60 **Buffer Size (ft)**

> > 5 mi/hr 10 mi/hr 15 mi/hr 20 mi/hr

25 mi/hr 30 mi/hr 35 mi/hr

Fig. 14. FN Percentages After Applying Algorithm for Different Speed Ranges by Buffer Size

If no feasible paths are obtained between a pair of snapped data points, then the algorithm tests for viable routes between preceding and subsequent data points, as described in Figure 5. If a small buffer size is utilized, several successive data points do not snap to any roadway centerline generating FN data points. Thus, the number of consecutive data points used by the algorithm needs to be incremented to consider adjacent data points that are correctly

Although the map-matching algorithm may employ any number of consecutive data points, the performance of the map-matching algorithm was analyzed with a number of consecutive data points between three and eight. A previous test determined that this range of consecutive data points is suffice for solving spatial ambiguities with the spatial and

Similar to the FN curve behavior due to speed range variations, FN curves for different number of consecutive data points are parallel for the three counties and converge to constant values as the buffer size increases. Figure 15 shows the percentage of FN data points as the

rejected.

for Columbia County

**4.3.3 Number of consecutive GPS data points**

snapped and minimize FN percentages.

temporal data employed in this study.

**Percentage of DGPS Data Points**

Figure 13 presents the percentage of solved spatial ambiguities after applying the mapmatching algorithm for Columbia, Portage, and Polk counties. This chart indicates that over 90% of incorrectly snapped data points collected in Columbia County were solved by the algorithm when employing a 30-foot buffer size. Whereas, solved cases reached their maximum values (68% and 64%) for Portage and Polk counties with 50 and 60-foot buffers, respectively. As mentioned earlier, Polk County data was tested for buffer sizes every 20 feet, thus, there is no data for buffer sizes equal to 30 and 50 feet.

#### **4.3.2 Speed**

The map-matching algorithm determines the correct roadway centerline on which a vehicle is traveling by computing feasible shortest paths between snapped data points. This feasibility is sensitive to the allowable range utilized when comparing computed and recorded speeds. The analysis of this variable examines the effect that it has on the performance of the map-matching algorithm.

The average recorded speed (v) is computed using the recorded speeds (v1 and v2), as shown in Equation 1. Equation 2 presents the computed speed calculation (s) given the shortest distance traveled (D) and timestamps (t1 and t2) between a pair of snapped data points. Subsequently, the algorithm accepts a tested path as feasible if the average recorded speed is within the equally distributed speed range shown in Equation 3.

$$\mathbf{v} = \frac{\mathbf{v}\_1 + \mathbf{v}\_2}{2} \tag{1}$$

$$\mathbf{s} = \frac{\mathbf{D}}{\left(\mathbf{t}\_2 - \mathbf{t}\_1\right)}\tag{2}$$

$$\mathbf{v} \in \mathbf{s} \pm \frac{\text{SpeedRange}}{2} \tag{3}$$

FN curves were computed for various buffer sizes and different speed range tolerances from 5 to 35 mi/h with increments of 5 mi/h for the three counties. Analysis results for this variable show that feasible paths are rejected when small speed ranges are employed leaving FN data points not snapped to any roadway centerline. On the contrary, as speed range increases, FN percentages diminish since feasible paths are found during the speed comparison process. Figure 14 shows FN curves for Columbia County with data collected every 2 seconds. These curves are approximately parallel as the speed range varies, and stabilize for speed ranges greater than 15 mi/h. Speed ranges equal to or greater than 25 mi/h are needed to minimize FN percentages in Portage and Polk counties. Further speed range increase does not improve the results because all feasible paths are accepted. In general, FN curves are steeper for small buffer sizes, and approach near-zero slope for buffer sizes equal to or greater than 40 feet.

Analysis results for this variable indicate that the percentage of solved cases increases as speed range also increases. The percentage of solved cases has the highest value of approximately 90% when the algorithm employs speed ranges equal to or greater than 20 mi/hr and a 30-foot buffer for Columbia County data. Conversely, there is no considerable 230 Global Navigation Satellite Systems – Signal, Theory and Applications

Figure 13 presents the percentage of solved spatial ambiguities after applying the mapmatching algorithm for Columbia, Portage, and Polk counties. This chart indicates that over 90% of incorrectly snapped data points collected in Columbia County were solved by the algorithm when employing a 30-foot buffer size. Whereas, solved cases reached their maximum values (68% and 64%) for Portage and Polk counties with 50 and 60-foot buffers, respectively. As mentioned earlier, Polk County data was tested for buffer sizes every 20

The map-matching algorithm determines the correct roadway centerline on which a vehicle is traveling by computing feasible shortest paths between snapped data points. This feasibility is sensitive to the allowable range utilized when comparing computed and recorded speeds. The analysis of this variable examines the effect that it has on the

The average recorded speed (v) is computed using the recorded speeds (v1 and v2), as shown in Equation 1. Equation 2 presents the computed speed calculation (s) given the shortest distance traveled (D) and timestamps (t1 and t2) between a pair of snapped data points. Subsequently, the algorithm accepts a tested path as feasible if the average recorded

<sup>+</sup> <sup>=</sup> v v 1 2 <sup>v</sup>

s

v s

2 1 D

FN curves were computed for various buffer sizes and different speed range tolerances from 5 to 35 mi/h with increments of 5 mi/h for the three counties. Analysis results for this variable show that feasible paths are rejected when small speed ranges are employed leaving FN data points not snapped to any roadway centerline. On the contrary, as speed range increases, FN percentages diminish since feasible paths are found during the speed comparison process. Figure 14 shows FN curves for Columbia County with data collected every 2 seconds. These curves are approximately parallel as the speed range varies, and stabilize for speed ranges greater than 15 mi/h. Speed ranges equal to or greater than 25 mi/h are needed to minimize FN percentages in Portage and Polk counties. Further speed range increase does not improve the results because all feasible paths are accepted. In general, FN curves are steeper for small buffer sizes, and approach near-zero slope for

Analysis results for this variable indicate that the percentage of solved cases increases as speed range also increases. The percentage of solved cases has the highest value of approximately 90% when the algorithm employs speed ranges equal to or greater than 20 mi/hr and a 30-foot buffer for Columbia County data. Conversely, there is no considerable

SpeedRange

2

2 (1)

(t t ) <sup>=</sup> <sup>−</sup> (2)

∈ ± (3)

feet, thus, there is no data for buffer sizes equal to 30 and 50 feet.

speed is within the equally distributed speed range shown in Equation 3.

performance of the map-matching algorithm.

buffer sizes equal to or greater than 40 feet.

**4.3.2 Speed**

increase in the percentage of solved cases remaining at 68% for Portage County data when speed range values equal to or greater than 25 mi/h are employed. The percentage of solved cases for Polk County remained constant at 50% for speed ranges equal to or greater than 15 mi/h, independent of buffer size. Thus, the map-matching algorithm is sensitive to speed range values, particularly when small speed ranges are employed since feasible paths are rejected.

Fig. 14. FN Percentages After Applying Algorithm for Different Speed Ranges by Buffer Size for Columbia County

## **4.3.3 Number of consecutive GPS data points**

If no feasible paths are obtained between a pair of snapped data points, then the algorithm tests for viable routes between preceding and subsequent data points, as described in Figure 5. If a small buffer size is utilized, several successive data points do not snap to any roadway centerline generating FN data points. Thus, the number of consecutive data points used by the algorithm needs to be incremented to consider adjacent data points that are correctly snapped and minimize FN percentages.

Although the map-matching algorithm may employ any number of consecutive data points, the performance of the map-matching algorithm was analyzed with a number of consecutive data points between three and eight. A previous test determined that this range of consecutive data points is suffice for solving spatial ambiguities with the spatial and temporal data employed in this study.

Similar to the FN curve behavior due to speed range variations, FN curves for different number of consecutive data points are parallel for the three counties and converge to constant values as the buffer size increases. Figure 15 shows the percentage of FN data points as the

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 233

20 40 60 80 100 **Buffer Size (ft)**

<sup>20</sup> <sup>30</sup> <sup>40</sup> <sup>50</sup> <sup>60</sup>

Fig. 17. Percentages of Solved Cases for Different Temporal Resolutions by Buffer Size for

**Buffer Size (ft)**

0

10

20

30

40

**Percentage of DGPS Data Points**

50

60

70

Fig. 16. FN Percentages Before and After Applying Algorithm for Different Temporal

10sec (FN) 20sec (FN) 30sec (FN) FN (Before)

0

Resolutions by Buffer Size for Polk County

10 20 30

**Temporal Resolution (sec)**

Portage County

10

20

30

40

**Percentage of DGPS Data Points**

50

60

70

number of consecutive data points varies by county with a 40-foot buffer size. No significant improvements are identified in the percentage of FN for the three counties as the number of consecutive data points varies, except for Portage County data that presents a decrease in the amount of FN when increasing the number of consecutive data points from three to four.

Fig. 15. Average Percentages of FN After Applying Algorithm by Number of Consecutive Data Points and County

The percentage of solved spatial mismatches increased as the number of consecutive data points increased. Eight consecutive data points solve almost 100% of initial incorrect snaps for Columbia County data when employing a 40-foot buffer. The largest percentage of solved mismatches (over 70%) after applying the algorithm occurs with a 50-foot buffer for Portage County. While the percentage of solved cases in Polk County remained constant at 50%, as the buffer size and number of consecutive data points increased. The results of this analysis show that increasing the number of consecutive data points solves a larger number of spatial ambiguities. By increasing this number, the algorithm resolves ambiguities that arise when alternative roadway centerlines are equally viable.

#### **4.3.4 Temporal resolution**

The outcome of the map-matching technique is not only affected by spatial inaccuracies, it is also influenced by the collection frequency of the data points. As temporal resolution increases, the tracking of the vehicle becomes more accurate. On the other hand, the sampling interval impacts the sizes of the data sets. Processing of large data sets takes significant CPU time, and increases storage requirements. Hence, there is a tradeoff between decreasing the sampling interval and quality of collected speed data.

Data sets collected in Columbia County with an original 2-second time interval were processed to generate data files with lower temporal resolutions varying from 2 to 30 with increments of 4 seconds. Similarly, data collected every 10 seconds in Portage and Polk counties were processed to create data files with temporal resolutions equal to 10, 20, and 30 seconds, respectively. The speed range and number of consecutive points remained constant with values 25 mi/h and 5, respectively.

232 Global Navigation Satellite Systems – Signal, Theory and Applications

number of consecutive data points varies by county with a 40-foot buffer size. No significant improvements are identified in the percentage of FN for the three counties as the number of consecutive data points varies, except for Portage County data that presents a decrease in the amount of FN when increasing the number of consecutive data points from three to four.

> 345678 **Number of Consecutive Data Points**

> > Columbia Portage Polk

Fig. 15. Average Percentages of FN After Applying Algorithm by Number of Consecutive

The percentage of solved spatial mismatches increased as the number of consecutive data points increased. Eight consecutive data points solve almost 100% of initial incorrect snaps for Columbia County data when employing a 40-foot buffer. The largest percentage of solved mismatches (over 70%) after applying the algorithm occurs with a 50-foot buffer for Portage County. While the percentage of solved cases in Polk County remained constant at 50%, as the buffer size and number of consecutive data points increased. The results of this analysis show that increasing the number of consecutive data points solves a larger number of spatial ambiguities. By increasing this number, the algorithm resolves ambiguities that

The outcome of the map-matching technique is not only affected by spatial inaccuracies, it is also influenced by the collection frequency of the data points. As temporal resolution increases, the tracking of the vehicle becomes more accurate. On the other hand, the sampling interval impacts the sizes of the data sets. Processing of large data sets takes significant CPU time, and increases storage requirements. Hence, there is a tradeoff between

Data sets collected in Columbia County with an original 2-second time interval were processed to generate data files with lower temporal resolutions varying from 2 to 30 with increments of 4 seconds. Similarly, data collected every 10 seconds in Portage and Polk counties were processed to create data files with temporal resolutions equal to 10, 20, and 30 seconds, respectively. The speed range and number of consecutive points remained constant

arise when alternative roadway centerlines are equally viable.

decreasing the sampling interval and quality of collected speed data.

0

Data Points and County

**4.3.4 Temporal resolution**

with values 25 mi/h and 5, respectively.

5

10

**Percentages of DGPS Data Points**

15

20

25

Fig. 16. FN Percentages Before and After Applying Algorithm for Different Temporal Resolutions by Buffer Size for Polk County

Fig. 17. Percentages of Solved Cases for Different Temporal Resolutions by Buffer Size for Portage County

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 235

45

24

2 meter error

Columbia (2 sec) Portage (10 sec) Polk (10 sec)

Before After

53

29

5 meter error

45

22

Original data

60

42

2 meter error

63

48

5 meter error

5

0

**Percentage of Solved Cases**

Original data

2 meter error

5 meter error

and 5 m Error by Buffer Size in Columbia County

Original data

2 meter error

5 meter error

Original data

Fig. 19. Percentage of Solved Cases After Applying the Algorithm for Original Data, 2 m,

2 meter error

20 30 40 50 60 **Buffer Size (ft)**

5 meter error

Original data

2 meter error

5 meter error

Original data

2 meter error

5 meter error

10

20

30

**Percentage of DGPS Data Points**

40

50

60

70

0,6

Original data

9

6

2 meter error

and 5 m Error with a 40-foot Buffer by County

15

10

5 meter error

32

16

Original data

Fig. 18. FN Percentages Before and After Applying the Algorithm for Original Data, 2 m,

Figure 16 illustrates FN curves before and after applying the algorithm for different temporal resolutions with data originally collected every 10 seconds in Polk County. The graph presents relatively parallel FN curves for all data collection frequencies. These curves show that as temporal resolution increases, the percentages of FN data points decreases. FN curves after applying the algorithm show lower percentages of FN data points compared to before executing the algorithm. FN curves for Columbia and Portage counties behave similarly with different sampling intervals. All county cases illustrate that larger amount of FN points occur when using smaller buffers independent of data collection frequency. Figure 17 shows the variation of solved cases as temporal resolution increases in Portage County. Percentages of solved spatial ambiguities increase as data is collected at higher frequencies, being the largest at a 50-foot buffer with 68%. This percentage decreases in average for Columbia County data from approximately 80% to 20% as sampling intervals increase from 5 to 30 second for all buffer sizes. The same behavior is apparent for solved case percentages in Polk County as data is collected more frequently.

#### **4.3.5 GPS error**

GPS measurements are affected by both systematic and random errors. Their combined magnitudes will affect the accuracy of the positioning results. Systematic errors obey physical or mathematical law, and can be computed and applied to measurements to eliminate their effects (Ghilani & Wolf, 2006). Random errors occur because of stochastic noise in the measurement process producing different coordinates each time a measurement is achieved, even during short intervals. This type of error is assumed to be Gaussian affecting both latitude and longitude or X, Y coordinates. DGPS is a method that increases the accuracy of CA code measurements by canceling some of the inherent systematic errors. Any potentially remaining systematic errors were not modeled in this study, and only the effects of random errors were examined.

Random errors were simulated by using a normal distribution random number generator (Box & Muller, 1958) for known means and different standard deviations. If U1 and U2 are a pair of independent uniformly-distributed random numbers from the rectangular density function on the interval (0, 1), then a pair of independent random numbers (*X1* and *X2*) from a normal distribution with mean zero and standard deviation σ are generated using Equations 4 and 5.

$$X\_1 = (-2\log \mathcal{U} \mathbf{1})^{1/2} \cos(2\pi \mathcal{U} \mathbf{1}\_2) \tag{4}$$

$$X\_2 = (-2\log \mathcal{U}\_1)^{1/2} \sin(2\pi \mathcal{U}\_2) \tag{5}$$

Experiments conducted by the Wisconsin Winter Maintenance Concept Vehicle project concluded that random DGPS errors were on the order of 2 to 5 meters, root-mean-square (Vonderohe et al., 2001). Therefore, a mean value of zero and standard deviations of ±2 and ±5 meters were employed in this analysis. Speed range and number of consecutive points values were held fixed as 2- and 5-meter standard deviation errors were introduced in the DGPS data points.

Percentages for FN and solved cases were computed to compare the performance of the algorithm for original and perturbed DGPS data points. Figure 18 presents variations in the percentage of FN data points for original and perturbed data by county for a 40-foot buffer 234 Global Navigation Satellite Systems – Signal, Theory and Applications

Figure 16 illustrates FN curves before and after applying the algorithm for different temporal resolutions with data originally collected every 10 seconds in Polk County. The graph presents relatively parallel FN curves for all data collection frequencies. These curves show that as temporal resolution increases, the percentages of FN data points decreases. FN curves after applying the algorithm show lower percentages of FN data points compared to before executing the algorithm. FN curves for Columbia and Portage counties behave similarly with different sampling intervals. All county cases illustrate that larger amount of FN points occur when using smaller buffers independent of data collection frequency. Figure 17 shows the variation of solved cases as temporal resolution increases in Portage County. Percentages of solved spatial ambiguities increase as data is collected at higher frequencies, being the largest at a 50-foot buffer with 68%. This percentage decreases in average for Columbia County data from approximately 80% to 20% as sampling intervals increase from 5 to 30 second for all buffer sizes. The same behavior is apparent for solved

GPS measurements are affected by both systematic and random errors. Their combined magnitudes will affect the accuracy of the positioning results. Systematic errors obey physical or mathematical law, and can be computed and applied to measurements to eliminate their effects (Ghilani & Wolf, 2006). Random errors occur because of stochastic noise in the measurement process producing different coordinates each time a measurement is achieved, even during short intervals. This type of error is assumed to be Gaussian affecting both latitude and longitude or X, Y coordinates. DGPS is a method that increases the accuracy of CA code measurements by canceling some of the inherent systematic errors. Any potentially remaining systematic errors were not modeled in this study, and only the

Random errors were simulated by using a normal distribution random number generator (Box & Muller, 1958) for known means and different standard deviations. If U1 and U2 are a pair of independent uniformly-distributed random numbers from the rectangular density function on the interval (0, 1), then a pair of independent random numbers (*X1* and *X2*) from a normal distribution with mean zero and standard deviation σ are generated using

Experiments conducted by the Wisconsin Winter Maintenance Concept Vehicle project concluded that random DGPS errors were on the order of 2 to 5 meters, root-mean-square (Vonderohe et al., 2001). Therefore, a mean value of zero and standard deviations of ±2 and ±5 meters were employed in this analysis. Speed range and number of consecutive points values were held fixed as 2- and 5-meter standard deviation errors were introduced in the

Percentages for FN and solved cases were computed to compare the performance of the algorithm for original and perturbed DGPS data points. Figure 18 presents variations in the percentage of FN data points for original and perturbed data by county for a 40-foot buffer

*X*1 *= (-2 logU*1*)*1/2 *cos(2πU*2*)* (4)

*X*2 *= (-2 logU*1*)*1/2 *sin(2πU*2*)* (5)

case percentages in Polk County as data is collected more frequently.

**4.3.5 GPS error**

Equations 4 and 5.

DGPS data points.

effects of random errors were examined.

Fig. 18. FN Percentages Before and After Applying the Algorithm for Original Data, 2 m, and 5 m Error with a 40-foot Buffer by County

Fig. 19. Percentage of Solved Cases After Applying the Algorithm for Original Data, 2 m, and 5 m Error by Buffer Size in Columbia County

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 237

The results of this study indicate that the success of the map-matching algorithm in solving spatial ambiguities depends on not only by the variables employed by the algorithm, but also by the sampling interval and the quality of the spatial measurements and roadway map scale. If lower spatial data qualities and less frequent sampling intervals are used, then the algorithm requires larger buffers and speed ranges to obtain best results. On the other hand, if GPS data points collected more frequently are snapped to higher accuracy maps, such as the Columbia County case, then larger percentages of incorrect snaps are solved and smaller buffer sizes are adequate. By increasing the number of consecutive data points, a larger number of spatial ambiguities are solved, particularly when alternative roadway centerlines are equally viable, and FN percentages are reduced since more combinations are examined between pairs of snapped DGPS data points. However, no significant variations in the solved results for Polk County are apparent as the number of consecutive data points increases since lower spatial data accuracies were used in this county. Table 2 presents the best and worst variable values encountered when solving incorrect snaps after applying the map-matching algorithm by county. This table indicates that larger speed range values, and numbers of consecutive points provide better results in maximizing solved cases. Stable percentage values are reached as both speed range and number of consecutive points reach certain values. While small speed ranges tend to reject tested paths, larger speed ranges accept most of these paths without improving the performance of the algorithm. Similarly, larger percentages of solved cases are obtained as the number of consecutive points increases since additional combinations between pairs of snapped data points are examined. Overall, higher parameter values yield better results as data are collected less frequently and

Buffer Size (ft) Speed Range (mi/hr) Number of Consecutive Points County Best Worst Best Worst Best Worst

Introducing positional error in the DGPS data points decreases the percentage of solved incorrect snaps and total number of snapped data points obtained before and after applying the algorithm. As the positional error increments from 2 to 5 meters in standard deviation, the percentage of solved cases decrease and FN percentages increase for all counties. Thus, larger buffer sizes and speed ranges are needed for lower quality data. Future research is required to explore these parameter values against additional spatial data qualities derived from multiple ITS applications. Further research may involve online implementation of the map-matching algorithm, in which spatial ambiguities are solved as GPS measurements are

Blazquez, C., & Vonderohe, A. (2005). Simple Map-Matching Algorithm Applied to

Intelligent Winter Maintenance Vehicle Data. *Journal of Transportation Research*

Columbia 30 ≥50 35 5 8 3 Portage 50 20 ≥25 5 8 3 Polk 40 20 ≥15 5 ≥3 ≥3

Table 2. Best and Worst Variable Values for Solved Cases by County

snapped to lower quality roadway maps.

collected in real-time.

*Board*, Vol. 1935, pp. 68-76.

**6. References**

before and after applying the algorithm. All FN percentages decrease after executing the algorithm, independent from the spatial data quality. Average FN percentages computed with original data present smaller values than data perturbed with 2- and 5-m error before and after applying the algorithm. For example, FN percentages increase from 22% to 48% for Polk County after executing the algorithm when introducing a 5-m error. In general, the percentage of data points that should snap to a roadway centerline increases when there is larger error in the DGPS data points.

Figure 19 presents the percentages of solved spatial ambiguities by the algorithm before and after perturbing the DGPS data points with original and simulated random errors (2-and 5 meter standard deviation) for Columbia County. This figure shows that the percentage of incorrect snaps solved after applying the algorithm for original Columbia County data are larger than those computed with perturbed data. On average, the percentage of solved cases decreases approximately 20% and 40% for data with 2- and 5-meter error for all buffer sizes, except for the 20-foot buffer. This small buffer is not able to accommodate the spatial ambiguities that arise with simulated data. Similarly, Portage and Polk counties present a drop in the percentages of solved data points from approximately 68% and 50% for original data to approximately 10% and 15%, respectively, for 5 m perturbed data.

## **5. Summary and conclusions**

Transportation applications employ AVL/DGPS technology to collect vehicle positions and other sensor data. Normally, DGPS data points are associated with roadways by snapping to the nearest centerline in a GIS environment. The map-matching problem or spatial ambiguities arise during this association due to errors in DGPS measurements and digital cartography. Such ambiguities are common at underpasses and converging or diverging roadways. These can result in DGPS data points being snapped to incorrect roadway centerlines affecting the calculation of cumulative distance traveled by the vehicles along a roadway network, or the allocation of non-spatial data collected from vehicle sensors to incorrect roadways. Thus, this problem propagates to the computation of performance measures or decision management tools.

This study contributes with the development and implementation of a post-processing decision-rule map-matching algorithm that resolves many of these spatial ambiguities by examining the feasibility of paths between pairs of snapped data points. A viable path is the shortest-distance path between two snapped points that a vehicle can travel, while following network topology and turn restrictions, at a speed comparable to its average recorded speed. If a given shortest path is not feasible, then DGPS data points are related to other roadway centerlines within their buffers and new shortest paths are calculated; or adjacent DGPS data points are used to determine feasible paths. Examples were presented to describe the step-by-step process of the map-matching algorithm. Five variables were studied independently to analyze the performance of the map-matching algorithm. These variables are buffer size, speed range tolerance, number of consecutive points, temporal resolution, and positional error in the DGPS data points. Data collection frequency and DGPS error are variables controlled externally through the data, while buffer size, speed range, and number of consecutive data points are algorithm parameters are controlled by the user.

The results of this study indicate that the success of the map-matching algorithm in solving spatial ambiguities depends on not only by the variables employed by the algorithm, but also by the sampling interval and the quality of the spatial measurements and roadway map scale. If lower spatial data qualities and less frequent sampling intervals are used, then the algorithm requires larger buffers and speed ranges to obtain best results. On the other hand, if GPS data points collected more frequently are snapped to higher accuracy maps, such as the Columbia County case, then larger percentages of incorrect snaps are solved and smaller buffer sizes are adequate. By increasing the number of consecutive data points, a larger number of spatial ambiguities are solved, particularly when alternative roadway centerlines are equally viable, and FN percentages are reduced since more combinations are examined between pairs of snapped DGPS data points. However, no significant variations in the solved results for Polk County are apparent as the number of consecutive data points increases since lower spatial data accuracies were used in this county. Table 2 presents the best and worst variable values encountered when solving incorrect snaps after applying the map-matching algorithm by county. This table indicates that larger speed range values, and numbers of consecutive points provide better results in maximizing solved cases. Stable percentage values are reached as both speed range and number of consecutive points reach certain values. While small speed ranges tend to reject tested paths, larger speed ranges accept most of these paths without improving the performance of the algorithm. Similarly, larger percentages of solved cases are obtained as the number of consecutive points increases since additional combinations between pairs of snapped data points are examined. Overall, higher parameter values yield better results as data are collected less frequently and snapped to lower quality roadway maps.

Table 2. Best and Worst Variable Values for Solved Cases by County

Introducing positional error in the DGPS data points decreases the percentage of solved incorrect snaps and total number of snapped data points obtained before and after applying the algorithm. As the positional error increments from 2 to 5 meters in standard deviation, the percentage of solved cases decrease and FN percentages increase for all counties. Thus, larger buffer sizes and speed ranges are needed for lower quality data. Future research is required to explore these parameter values against additional spatial data qualities derived from multiple ITS applications. Further research may involve online implementation of the map-matching algorithm, in which spatial ambiguities are solved as GPS measurements are collected in real-time.

### **6. References**

236 Global Navigation Satellite Systems – Signal, Theory and Applications

before and after applying the algorithm. All FN percentages decrease after executing the algorithm, independent from the spatial data quality. Average FN percentages computed with original data present smaller values than data perturbed with 2- and 5-m error before and after applying the algorithm. For example, FN percentages increase from 22% to 48% for Polk County after executing the algorithm when introducing a 5-m error. In general, the percentage of data points that should snap to a roadway centerline increases when there is

Figure 19 presents the percentages of solved spatial ambiguities by the algorithm before and after perturbing the DGPS data points with original and simulated random errors (2-and 5 meter standard deviation) for Columbia County. This figure shows that the percentage of incorrect snaps solved after applying the algorithm for original Columbia County data are larger than those computed with perturbed data. On average, the percentage of solved cases decreases approximately 20% and 40% for data with 2- and 5-meter error for all buffer sizes, except for the 20-foot buffer. This small buffer is not able to accommodate the spatial ambiguities that arise with simulated data. Similarly, Portage and Polk counties present a drop in the percentages of solved data points from approximately 68% and 50% for original

Transportation applications employ AVL/DGPS technology to collect vehicle positions and other sensor data. Normally, DGPS data points are associated with roadways by snapping to the nearest centerline in a GIS environment. The map-matching problem or spatial ambiguities arise during this association due to errors in DGPS measurements and digital cartography. Such ambiguities are common at underpasses and converging or diverging roadways. These can result in DGPS data points being snapped to incorrect roadway centerlines affecting the calculation of cumulative distance traveled by the vehicles along a roadway network, or the allocation of non-spatial data collected from vehicle sensors to incorrect roadways. Thus, this problem propagates to the computation of performance

This study contributes with the development and implementation of a post-processing decision-rule map-matching algorithm that resolves many of these spatial ambiguities by examining the feasibility of paths between pairs of snapped data points. A viable path is the shortest-distance path between two snapped points that a vehicle can travel, while following network topology and turn restrictions, at a speed comparable to its average recorded speed. If a given shortest path is not feasible, then DGPS data points are related to other roadway centerlines within their buffers and new shortest paths are calculated; or adjacent DGPS data points are used to determine feasible paths. Examples were presented to describe the step-by-step process of the map-matching algorithm. Five variables were studied independently to analyze the performance of the map-matching algorithm. These variables are buffer size, speed range tolerance, number of consecutive points, temporal resolution, and positional error in the DGPS data points. Data collection frequency and DGPS error are variables controlled externally through the data, while buffer size, speed range, and number of consecutive data points are algorithm parameters are controlled by

data to approximately 10% and 15%, respectively, for 5 m perturbed data.

larger error in the DGPS data points.

**5. Summary and conclusions**

measures or decision management tools.

the user.

Blazquez, C., & Vonderohe, A. (2005). Simple Map-Matching Algorithm Applied to Intelligent Winter Maintenance Vehicle Data. *Journal of Transportation Research Board*, Vol. 1935, pp. 68-76.

A Decision-Rule Topological Map-Matching Algorithm with Multiple Spatial Data 239

Kim, W., Lee, G.I., & Lee, J.G. (2000). Efficient Use of Digital Road Map in Various

Li, J., Taylor, G., & Kidner, D. (2005) Accuracy and Reliability of Map-Matched GPS

Marchal, F., Hackney, J., & Axhausen, K.W. (2005). Efficient Map-Matching of Large GPS

Nassreddine, G., Abdallah, F., & Denoeux, T. (2009) Map Matching Algorithm Using

Quddus, M., Ochieng, W., Zhao, L., & Noland, R. (2003). A General Map Matching

Quddus, M., Noland, R., & Ochieng, W. (2006). A High Accuracy Fuzzy Logic Based Map

Schlingelhof, M., Betaille, D., Bonnifait, P., and Demaseure, K. (2008) Advanced Positioning

Sheridan, K., T. Dyjas, C. Botteron, J. Leclere, F. Dominic, and G. Marucco (2011) Demands

Taylor, G., Blewitt, G., Steup, D., Corbett, S., & Car, A. (2001). Road Reduction Filtering for GPS-GIS Navigation. *Transactions in GIS*, Volume 5, No. 3, pp. 193-207. Toledo-Moreo, R., Betaille, D., & Peyret, F. (2010) Lane-Level Integrity Provision For

Velaga, N., Quddus, M., & Bristow, A. (2009). Developing an Enhanced Weight-Based

and Environmental Engineering, University of Wisconsin-Madison. Wang, Z., & Yang, Z. (2009) Research on the Map Matching of Typical Region Based on the

*Computation Technology and Automation*, Zhangjiajie, China October 2009. White, C., Bernstein, D., & KornHauser, A. (2000). Some Map Matching Algorithms for

*Symposium*, San Diego, California, March 2000.

September 1989.

pp. 157-167.

2, pp. 81-91.

113.

*World*, Vol. 22, No. 3.

*Technologies*, Vol. 8, No. 1, pp. 91-108.

Vol. 10, No. 3, pp. 103-115.

Algorithm. *Computers & Geosciences*, Vol. 31, pp. 241-251.

*Vehicles Symposium (IV'09*), Xi'an ,China, June 2009.

Positioning for ITS. *Proceedings of IEEE PLANS, Position Location and Navigation*

Coordinates: The Dependence on Terrain Model Resolution and Interpolation

Data Set – Tests on a Speed Monitoring Experiment in Zurich. *Proceeding of 84th Annual Meeting Transportation Research Board*, Washington, DC., January 2005. Morisue, F., & Ikeda, K. (1989). Evaluation of Map-Matching Techniques. *Proceedings of*

*Vehicle Navigation and Information Systems Conference Record*, Toronto, Canada,

Interval Analysis and Dempster-Shafer Theory. *Proceedings of IEEE Intelligent*

Algorithm for Transportation Telematics Applications. *GPS Solutions*, Vol. 7, No. 3,

Matching Algorithm for Road Transport. *Journal of Intelligent Transportation Systems*,

Technologies for Co-operative Systems*. IET Intelligent Transport Systems*, Vol. 2, No.

of Roads. An Assisted-GNSS Solution Uses the EGNOS Data Access Service. *GPS*

Navigation And Map Matching With GNSS, Dead Reckoning, And Enhanced Maps. *IEEE Transactions on Intelligent Transportation Systems*. Vol. 11, No. 1, pp. 100-

Topological Map-Matching Algorithm for Intelligent Transport Systems. *Transportation Research Part C: Emerging Technologies*, Vol. 17, No. 6, pp. 672-683. Vonderohe, A., Malhotra, A., Sheth, V., Mezera, D., & Adams, A. (2001). *Report Wisconsin*

*Winter Maintenance Concept Vehicle: Data Management Year 1.* Department of Civil

Topological Analysis. *Proceedings of 2nd International Conference on Intelligent*

Personal Navigation Assistants. *Transportation Research Part C: Emerging*

238 Global Navigation Satellite Systems – Signal, Theory and Applications

Blazquez, C., & Vonderohe, A. (2009). Effects of Controlling Parameters on Performance of a

Box, G. & Muller, M. (1958) A Note on the Generation of Random Normal Deviates. *Annals*

Chen, W., Li, Z., Yu, M., & Chen, Y. (2005). Effects of sensor errors on the performance of

Crisan, D., & Doucet A. (2002). A Survey of Convergence Results on Particle Filtering

Czerniak R. (2002). Collecting, Processing, and Integrating GPS Data into GIS. In

Freitas, T., Coelho, A., & Rossetti, R. (2009) Improving digital maps through GPS data

French, R. (1989). Map Matching Origins, Approaches and Applications. *Proceedings of the*

Ghilani, C., & Wolf, P. (2006). *Adjustment Computations-Spatial Data Analysis*, John Wiley &

Greenfeld, J.S. (2002). Matching GPS Observations to Location on a Digital Map. *Proceedings*

Guo, L. & Luo, D. Y. (2009) Development of an Integrated Map Matching Algorithm Based

*Computation Technology and Automation*, Zhangjiajie, China, October 2009. Gustafsson, F., Gunnarsson, F., Bergman, N., Forssell, U., Jansson, J., Karlsson, R., &

Jagadeesh, G., Srikanthan, T., & Zhang, X. (2004) A Map Matching Method for GPS Based Real-Time Vehicle Location. *The Journal of Navigation*, Vol. 54, pp. 429-440 Jo, T., Haseyama, M., & Kitajima, H. (1996). A Map Matching Method with the Innovation of

Kim, S., & Kim, J.H. (2001). Adaptive Fuzzy-Network-Based C-Measure Map-Matching

*Transportation Systems, ITSC*, St. Louis, Missouri., October 2009.

Sons, Inc., ISBN<PHONE_NUMBER>282, Hoboken, New Jersey.

*Transactions on Signal Processing*, Vol. 50, No. 2, pp. 425-437.

Cozzens, T. (2009) Mileage-Based Road Tax Gets Pumped. *GPS World*, Vol. 20, No. 5.

*Engineering*, Vol. 135, No. 12, (December, 2009), pp. 966-973.

map-matching. *Journal of Navigation*, Vol. 58, pp. 273-282.

*of Mathematical Statistics*, Vol. 29, No. 2, pp. 610-611.

Research Council, Washington, D.C.

Board, Washington, D.C., January 2002.

*and Computer Sciences*, Vol. 79-A, No. 11.

Vol. 48, No. 2, pp.432-441.

736-746.

1989.

Decision-Rule Map-Matching Algorithm. *ASCE Journal of Transportation*

Methods for Practitioners. *IEEE Transactions on Signal Processing*, Vol. 50, No. 3, pp.

*Transportation Research Board: NCHRP Synthesis of Highway Practice 301*, Transportation Research Board, National Research Council, Washington, D.C. Doherty, S.T., Noel, N., Gosselin, M.L., Sirois, C., and Ueno, M. (2000). Moving Beyond

Observed Outcomes: Integrating Global Positioning Systems and Interactive Computer-Based Travel Behavior Surveys. *Transportation Research Circular E-C026, Personal Travel: The Long and Short of It*, Transportation Research Board, National

processing. *Proceedings of the 12th International IEEE Conference on Intelligent*

*Second International Symposium on Land Vehicle Navigation*, Munster, Germany, July

*of Transportation Research Board 81st Annual Meeting*, Transportation Research

on Fuzzy Theory. *Proceedings of Second International Conference on Intelligent*

Nordlund, P. (2002). Particle Filters for Positioning, Navigation, and Tracking. *IEEE*

the Kalman Filter. *IEICE Transactions on Fundamentals of Electronics, Communications*

Algorithm for Car Navigation System. *IEEE Transactions on Industrial Electronics*,

**0**

**10**

**Beyond Trilateration: GPS Positioning Geometry**

Trilateration/multilateration is the fundamental basis for most GPS positioning algorithms. It begins by finding range estimates to known satellite positions which provides a spherical Locus of Position (LOP) for the receiver. Ideally four such spherical LOPs can be solved to precisely determine the receiver position. Thus, it is an analytical approach that finds receiver position by solving required number of linear/quadratic equations. This method can determine the receiver position precisely when the equations are perfectly formulated. However, determining the exact range is nearly impossible in real-life due to many external factors such as noise interference, signal fading, multi-path propagation, weather condition, clock synchronization problem etc (Strang & Borre, 1997). Hence, trilateration fails to achieve sufficient accuracy under real world conditions. It is also argued that GPS algorithms are not at all tri/multi-lateration rather they are difference of measurement (time-difference or second order difference of two ranges) based hyperbolic formulations (Chaffee & Abel, 1994). However, there are widely used useful range-based algorithms such as Bancroft (1985) method. Therefore, trilateration is still predominantly associated with positioning (Bajaj et al., 2002). In this chapter, we first discuss about the analytical accuracy of trilateration based positioning algorithms. Subsequently, we show how noise can impact positioning accuracy in real world. In Section 3, we present existing analytical algorithms for GPS along with two new analytical approaches using Paired Measurement Localization (PML) of (Rahman & Kleeman, 2009). PML approaches can cope up with practical improper range based equations and are computationally efficient for implementation by conventional and resource constraint GPS

As alluded before, analytical approaches of positioning are based on accurate distance measurement from geo-stationary satellites. Trilateration is the basis of these techniques where the range measurements from *n* + 1 satellites are used for an *n*-dimensional position

In the ideal scenario when we can measure the precise range estimates of the GPS receiver, we can formulate a spherical locus of position for the receiver. The fundamental positioning geometry using three satellites placed in a hypothetical 2-Dimensional space is shown in

receivers. Section 4 draws some conclusions for this chapter.

estimation (Caffery, 2000).

Fig. 1(a).

**2. Trilateration: its problems and alternative approaches**

**1. Introduction**

**and Analytical Accuracy**

Mohammed Ziaur Rahman

*University of Malaya*

*Malaysia*

## **Beyond Trilateration: GPS Positioning Geometry and Analytical Accuracy**

Mohammed Ziaur Rahman *University of Malaya Malaysia*

### **1. Introduction**

240 Global Navigation Satellite Systems – Signal, Theory and Applications

Wolf, P. & Ghilani, C. (1997). *Adjustment Computations-Statistics and Least Squares in Surveying and GIS*, John Wiley & Sons, ISBN 0-471-16833-5, New York. Yang, D., Cai, B., & Yuan, Y. (2003). An Improved Map-Matching Algorithm Used in Vehicle

Zhao, Y. (1997). *Vehicle location and navigation systems*, Artech House, Inc., ISBN 0-89006-861-

Zhao, L., Ochieng, W., Quddus, M., & Noland, R. (2003). An Extended Kalman Filter

*Transportation Systems*, Vol. 2, Shanghai, China, October 2003.

5, Norwood, MA.

257-275.

Navigation System. *Proceedings of IEEE International Conference on Intelligent*

Algorithm for Integrating GPS and Low Cost Dead Reckoning System Data for Vehicle Performance and Emissions Monitoring. *Journal of Navigation*, Vol. 56, pp.

> Trilateration/multilateration is the fundamental basis for most GPS positioning algorithms. It begins by finding range estimates to known satellite positions which provides a spherical Locus of Position (LOP) for the receiver. Ideally four such spherical LOPs can be solved to precisely determine the receiver position. Thus, it is an analytical approach that finds receiver position by solving required number of linear/quadratic equations. This method can determine the receiver position precisely when the equations are perfectly formulated. However, determining the exact range is nearly impossible in real-life due to many external factors such as noise interference, signal fading, multi-path propagation, weather condition, clock synchronization problem etc (Strang & Borre, 1997). Hence, trilateration fails to achieve sufficient accuracy under real world conditions. It is also argued that GPS algorithms are not at all tri/multi-lateration rather they are difference of measurement (time-difference or second order difference of two ranges) based hyperbolic formulations (Chaffee & Abel, 1994). However, there are widely used useful range-based algorithms such as Bancroft (1985) method. Therefore, trilateration is still predominantly associated with positioning (Bajaj et al., 2002).

> In this chapter, we first discuss about the analytical accuracy of trilateration based positioning algorithms. Subsequently, we show how noise can impact positioning accuracy in real world. In Section 3, we present existing analytical algorithms for GPS along with two new analytical approaches using Paired Measurement Localization (PML) of (Rahman & Kleeman, 2009). PML approaches can cope up with practical improper range based equations and are computationally efficient for implementation by conventional and resource constraint GPS receivers. Section 4 draws some conclusions for this chapter.

## **2. Trilateration: its problems and alternative approaches**

As alluded before, analytical approaches of positioning are based on accurate distance measurement from geo-stationary satellites. Trilateration is the basis of these techniques where the range measurements from *n* + 1 satellites are used for an *n*-dimensional position estimation (Caffery, 2000).

In the ideal scenario when we can measure the precise range estimates of the GPS receiver, we can formulate a spherical locus of position for the receiver. The fundamental positioning geometry using three satellites placed in a hypothetical 2-Dimensional space is shown in Fig. 1(a).

(a) Ideal 2-D trilateration scenario where linear form LOPs are found from the corresponding two circular LOPs (Caffery, 2000).

(b) LOP from equidistant satellites in presense of equal noise.

**0 5 10 15 20 25 30 35**

(a)

**Anchor node Regular node Observed range Actual range Linear Form LOP Hyperbolic LOP**

Beyond Trilateration: GPS Positioning Geometry and Analytical Accuracy 243

Fig. 2. The hyperbolic and linear form LOP of a receiver from range estimates by a pair of satellites under equal noise assumption. (a) The general case when two observed circular LOPs physically intersect. (b) The case when circular LOPs do not intersect due to noise and

At first, we present the following observation that identifies the case when the conventional

**Observation 1.** *Assuming a receiver uses range estimates from two satellites that are located at the same distance from the receiver and have equal noise components, it is shown below that the locus of positions for that receiver (as the error components vary) is a straight line whose equation is independent*

Assume that due to noise, the range measurements for **p1** (*x*1, *y*1), **p2** (*x*2, *y*2) and **p3** (*x*3, *y*3) are corrupted to give respective LOPs of radii *r*˜1 = *r*<sup>1</sup> + ξ1, *r*˜2 = *r*<sup>2</sup> + ξ<sup>2</sup> and *r*˜3 = *r*<sup>3</sup> + ξ3, where *r*˜*i*, *ri* represent the observed and actual distance (pseudorange and actual range respectively)

receiver corresponding to the measurement. The circular LOP can then be expressed as:

(*x*<sup>2</sup> − *x*1) *x* + (*y*<sup>2</sup> − *y*1) *y* =

�**p**2�<sup>2</sup> − �**p**1�<sup>2</sup> <sup>+</sup> (*r*<sup>1</sup> <sup>+</sup> <sup>ξ</sup>1)

where the right hand side becomes independent of range parameters, *i.e.*, measurement values

and equal noise presence when the above condition is fulfilled. The importance of this observation lies in the fact that it eliminates the signal propagation dependent parameters and receiver clock bias under assumed conditions completely. GPS measurements are mostly susceptible to these errors which are both device and

*th* satellite and receiver respectively and ξ*<sup>i</sup>* is the measurement noise at the

(*ri* <sup>+</sup> <sup>ξ</sup>*i*)<sup>2</sup> <sup>=</sup> �**p***<sup>i</sup>* <sup>−</sup> <sup>ρ</sup>�<sup>2</sup> (2)

2

(3)

<sup>2</sup> <sup>−</sup> (*r*<sup>2</sup> <sup>+</sup> <sup>ξ</sup>2)

<sup>2</sup> ⇒ *r*<sup>1</sup> + ξ<sup>1</sup> = *r*<sup>2</sup> + ξ2. One particular case is equidistant satellites

**5 10 15 20 25 30**

**X**

(b)

**Anchor node Regular node Observed range Actual range Linear Form LOP Hyperbolic LOP**

**Y**

**X**

trilateration works in consideration of noise.

where ρ = (*x*, *y*) is the receiver position to be determined.

1 2

<sup>1</sup> = *r*˜

Equating the circular LOPs for **p**<sup>1</sup> and **p**<sup>2</sup> using (2), *L*<sup>1</sup> becomes:

*of range estimates.*

between the *i*

*r*˜ <sup>1</sup> and *r*˜

<sup>2</sup> whenever *r*˜

environmentally dependent.

underestimation of the ranges.

**Y**

Fig. 1. Depiction of observation 1.

The circles surrounding the satellites with known positions **p1** (*x*1, *y*1), **p2** (*x*2, *y*2) and **p3** (*x*3, *y*3), denote the LOPs obtained from the individual range measurements for each satellite. Ideally, the LOPs surrounding satellite *i* is given by,

$$r\_i^2 = \|\mathbf{p}\_i - \rho\|^2 = \left( (\mathbf{x} - \mathbf{x}\_i)^2 + (y - y\_i)^2 \right) \tag{1}$$

In 2-D, it is feasible to calculate the exact receiver position using only three range measurements. Two range measurements can result in two solutions corresponding to the intersection of two circular LOPs. The third measurement resolves this ambiguity.

However, equating two circular LOPs will result in a straight line equation (in case of 3-D, it will be planar equation) passing through two intersecting points of the circular LOPs. This line does not represent the actual locus of the receiver position as it will be clarified later. However, following (Caffery, 2000) this line is referred as *Linear Form LOP* in the subsequent discussions. In Fig. 1, *L*<sup>1</sup> and *L*<sup>2</sup> are determined from the circular LOPs corresponding to satellite pairs (**p1**, **p2**) and (**p1**, **p3**) respectively, with the intersection point (*x*, *y*) of *L*<sup>1</sup> and *L*<sup>2</sup> denoting the actual position of the receiver.

As shown in Fig. 1,the positioning geometry works correctly for ideal case of exact range estimates being measured by the positioning devices. However, in reality it is quite difficult to measure the exact range both for external noise impact and internal errors such as receiver clock bias and satellite clock skews. However, we also showed the fact that accurate positioning can be obtained if the noise effect is exactly the same for two satellites. However, in case of variable noise presence for two satellite range estimates usual linear form LOP obtained from circular LOPs deviates significantly from the true position of the receiver and leads to a bad positioning geometry. This is further explained as follows.

As it is clarified before that the range equations are mostly not accurate in practical scenario. Though trilateration is a mathematical approach and ideally it can find the exact receiver position, however it cannot find the position very well when the range estimates are perturbed by noise. In this section we will specifically identify the problems of trilateration for inaccurate range equations. For the ease of understanding we still limit this discussion for 2-dimensions only.

2 Will-be-set-by-IN-TECH

The circles surrounding the satellites with known positions **p1** (*x*1, *y*1), **p2** (*x*2, *y*2) and **p3** (*x*3, *y*3), denote the LOPs obtained from the individual range measurements for each

In 2-D, it is feasible to calculate the exact receiver position using only three range measurements. Two range measurements can result in two solutions corresponding to the

However, equating two circular LOPs will result in a straight line equation (in case of 3-D, it will be planar equation) passing through two intersecting points of the circular LOPs. This line does not represent the actual locus of the receiver position as it will be clarified later. However, following (Caffery, 2000) this line is referred as *Linear Form LOP* in the subsequent discussions. In Fig. 1, *L*<sup>1</sup> and *L*<sup>2</sup> are determined from the circular LOPs corresponding to satellite pairs (**p1**, **p2**) and (**p1**, **p3**) respectively, with the intersection point (*x*, *y*) of *L*<sup>1</sup> and *L*<sup>2</sup> denoting the actual

As shown in Fig. 1,the positioning geometry works correctly for ideal case of exact range estimates being measured by the positioning devices. However, in reality it is quite difficult to measure the exact range both for external noise impact and internal errors such as receiver clock bias and satellite clock skews. However, we also showed the fact that accurate positioning can be obtained if the noise effect is exactly the same for two satellites. However, in case of variable noise presence for two satellite range estimates usual linear form LOP obtained from circular LOPs deviates significantly from the true position of the receiver and leads to a bad

As it is clarified before that the range equations are mostly not accurate in practical scenario. Though trilateration is a mathematical approach and ideally it can find the exact receiver position, however it cannot find the position very well when the range estimates are perturbed by noise. In this section we will specifically identify the problems of trilateration for inaccurate range equations. For the ease of understanding we still limit this discussion for 2-dimensions

(*<sup>x</sup>* <sup>−</sup> *xi*)<sup>2</sup> + (*<sup>y</sup>* <sup>−</sup> *yi*)<sup>2</sup>

*L*1

**P**<sup>1</sup> **P**<sup>2</sup>

(b) LOP from equidistant satellites in presense of equal noise.

*r*1

ξ1 Same Linear LOP

*r*2 ξ2

(1)

(a) Ideal 2-D trilateration scenario where linear form LOPs are found from the corresponding two circular LOPs (Caffery, 2000).

satellite. Ideally, the LOPs surrounding satellite *i* is given by,

*<sup>i</sup>* <sup>=</sup> �**p***<sup>i</sup>* <sup>−</sup> <sup>ρ</sup>�<sup>2</sup> <sup>=</sup>

intersection of two circular LOPs. The third measurement resolves this ambiguity.

*r* 2

positioning geometry. This is further explained as follows.

Fig. 1. Depiction of observation 1.

position of the receiver.

only.

Fig. 2. The hyperbolic and linear form LOP of a receiver from range estimates by a pair of satellites under equal noise assumption. (a) The general case when two observed circular LOPs physically intersect. (b) The case when circular LOPs do not intersect due to noise and underestimation of the ranges.

At first, we present the following observation that identifies the case when the conventional trilateration works in consideration of noise.

**Observation 1.** *Assuming a receiver uses range estimates from two satellites that are located at the same distance from the receiver and have equal noise components, it is shown below that the locus of positions for that receiver (as the error components vary) is a straight line whose equation is independent of range estimates.*

Assume that due to noise, the range measurements for **p1** (*x*1, *y*1), **p2** (*x*2, *y*2) and **p3** (*x*3, *y*3) are corrupted to give respective LOPs of radii *r*˜1 = *r*<sup>1</sup> + ξ1, *r*˜2 = *r*<sup>2</sup> + ξ<sup>2</sup> and *r*˜3 = *r*<sup>3</sup> + ξ3, where *r*˜*i*, *ri* represent the observed and actual distance (pseudorange and actual range respectively) between the *i th* satellite and receiver respectively and ξ*<sup>i</sup>* is the measurement noise at the receiver corresponding to the measurement. The circular LOP can then be expressed as:

$$((r\_i + \xi\_i)^2 = \|\mathbf{p}\_i - \rho\|^2 \tag{2}$$

where ρ = (*x*, *y*) is the receiver position to be determined.

Equating the circular LOPs for **p**<sup>1</sup> and **p**<sup>2</sup> using (2), *L*<sup>1</sup> becomes:

$$\begin{aligned} \left( \left( \mathbf{x}\_2 - \mathbf{x}\_1 \right) \mathbf{x} + \left( y\_2 - y\_1 \right) \right) \mathbf{y} &= \\ \frac{1}{2} \left( \| \mathbf{p}\_2 \| ^2 - \| \mathbf{p}\_1 \| ^2 + \left( r\_1 + \xi\_1 \right)^2 - \left( r\_2 + \xi\_2 \right)^2 \right) &\tag{3} \end{aligned}$$

where the right hand side becomes independent of range parameters, *i.e.*, measurement values *r*˜ <sup>1</sup> and *r*˜ <sup>2</sup> whenever *r*˜ <sup>1</sup> = *r*˜ <sup>2</sup> ⇒ *r*<sup>1</sup> + ξ<sup>1</sup> = *r*<sup>2</sup> + ξ2. One particular case is equidistant satellites and equal noise presence when the above condition is fulfilled.

The importance of this observation lies in the fact that it eliminates the signal propagation dependent parameters and receiver clock bias under assumed conditions completely. GPS measurements are mostly susceptible to these errors which are both device and environmentally dependent.

The hyperbolic LOP represents the actual LOP for a pair of satellites under the equal noise assumption. The linear form LOP does not truly represent the locus of the receiver in presence of noise unless both ranges to the satellites are equal as clarified in Fig. 2. Two possible cases could arise due to equal noise presence: *a*) the circular ranges have a physical intersection and *b*) the circular ranges do not have any physical intersection. In both cases, the hyperbolic LOP is able to represent the original receiver position whereas linear form LOP deviates from receiver position significantly. As establishing the LOP is the first step in positioning, any error present at this step could aggravate the result significantly and hence finding a LOP closer to

Beyond Trilateration: GPS Positioning Geometry and Analytical Accuracy 245

the original receiver position is fundamental to achieving high accuracy positioning.

linear form LOPs.

analytical algorithms for GPS.

*r*˜*i*

(Strang & Borre, 1997).

<sup>2</sup> = (*ri* + ξ*i*)

**3. Analytical approaches for global positioning**

It is also crucial to compare the hyperbolic and linear form LOPs for unequal noise components in individual measurements as in reality this assumption can be void. In these general situations three possible cases could arise. *a*) the observed circular ranges have a physical intersection; *b*) the observed circular ranges do not have any common intersection region; and *c*) One of the observed circular ranges overlap completely within the other circular region. These three cases are shown in Fig. 3 where Fig. 3(a), (b) shows the hyperbolic and linear form LOPs for noise ratio (ξ1/ξ2) of 2 while Fig. 3(c) shows the LOPs for noise ratio of 4. Fig. 3(c) also shows that for completely overlapped ranges the hyperbolic formulation turns into elliptic formulation. This is the case when coefficient of *y*<sup>2</sup> in (5) changes sign as the range difference becomes greater than distance between the satellites (*c* > *a*). The noise presence generally attenuates the signal more than that of ideal propagation scenario causing overestimation of the range. However, it is theoretically possible to imagine the case where range is underestimated due to noise. The simultaneous overestimation and underestimation of ranges is supposed to be the most detrimental for LOP estimation and hence this case is shown in Fig. 3(d). It is evident from the figures that for all the three cases of unequal noise presence as well as for noise having different signs, hyperbolic formulation is better suited than linear form and the impact of noise is less detrimental on hyperbolic LOPs than it is on

We have discussed about the mathematical basis for positioning and presented the problems of regular trilateration from the viewpoint of noisy measurements. The positioning algorithms for GPS need greater care for noise and often augmented by filtering process to mitigate the effect of noise. However, they still largely depend on basic analytical positioning both for initial estimation and for error correcting/filtering phase. In this chapter, we present the different

A generally acceptable modeling of the ranging error ξ*<sup>i</sup>* is described by the following equation

where *Ii* is the ionospheric error, *Ti* is the tropospheric error, *c* is the speed of light, *dti* is the satellite clock offset, *dt* is the receiver clock offset, *t* is the receiver time and τ*<sup>i</sup>* is the signal

(*<sup>x</sup>* <sup>−</sup> *xi*)<sup>2</sup> + (*<sup>y</sup>* <sup>−</sup> *yi*)<sup>2</sup> + (*<sup>z</sup>* <sup>−</sup> *zi*)<sup>2</sup>

ξ*<sup>i</sup>* = *Ii* + *Ti* + *c* (*dti*(*t* − τ*i*) − *dt*(*t*)) − *ei* (7)

(6)

We begin with the 3-D analogous formula for equation 2 which represents a sphere.

<sup>2</sup> <sup>=</sup> �**p***<sup>i</sup>* <sup>−</sup> <sup>ρ</sup>�<sup>2</sup> <sup>=</sup>

propagation time and *ei* represents all other unmodelled error terms.

Fig. 3. The hyperbolic and linear form LOPs for unequal noise presence. (a) The general case when two observed circular LOPs physically intersect. (b) The case when observed circular LOPs do not intersect due to underestimation of the ranges. (c) The case when observed circular LOPs do not intersect but overlap completely due to overestimation of the ranges.(d) The case when ranging errors are of opposite signs.

Assuming equal noise presence, it is useful to explore paired measurements rather than individual ranges to mitigate the effect of noise. As the difference of the range estimates equate to actual difference for equal noise presence (*e.g.*, *r*˜ <sup>2</sup> − *r*˜ <sup>1</sup> = *r*<sup>2</sup> − *r*1), the LOP for the receiver position is found by the locus of positions maintaining constant difference from the pair of satellites. Hence, the hyperbolic LOP of the receiver can be found independent of the noise parameters as shown in Fig. 2 and formulated below:

$$\sqrt{(\mathbf{x} - \mathbf{x}\_2)^2 + (y - y\_2)^2} \quad \text{---} \quad \sqrt{(\mathbf{x} - \mathbf{x}\_1)^2 + (y - y\_1)^2} \quad \text{---} \quad \qquad \qquad (\mathbf{r}\_2 - \mathbf{r}\_1) \tag{4}$$

After algebraic manipulations, it takes the general hyperbolic form as follows for **p**<sup>1</sup> = (0, 0), **p**<sup>2</sup> = (*a*, 0), and *r*˜ <sup>1</sup> − *r*˜ <sup>2</sup> = *c*.

$$
\left(\mathbf{x} - \frac{a}{2}\right)^2 - \frac{y^2}{\left(\frac{a^2}{c^2} - 1\right)} = \frac{c^2}{4} \tag{5}
$$

4 Will-be-set-by-IN-TECH

Fig. 3. The hyperbolic and linear form LOPs for unequal noise presence. (a) The general case when two observed circular LOPs physically intersect. (b) The case when observed circular LOPs do not intersect due to underestimation of the ranges. (c) The case when observed circular LOPs do not intersect but overlap completely due to overestimation of the ranges.(d)

Assuming equal noise presence, it is useful to explore paired measurements rather than individual ranges to mitigate the effect of noise. As the difference of the range estimates

receiver position is found by the locus of positions maintaining constant difference from the pair of satellites. Hence, the hyperbolic LOP of the receiver can be found independent of the

<sup>2</sup> <sup>+</sup> (*<sup>y</sup>* <sup>−</sup> *<sup>y</sup>*1)

After algebraic manipulations, it takes the general hyperbolic form as follows for **p**<sup>1</sup> =

<sup>−</sup> *<sup>y</sup>*<sup>2</sup> *a*2 *<sup>c</sup>*<sup>2</sup> − 1

<sup>=</sup> *<sup>c</sup>*<sup>2</sup>

**Y**

**Y**

**−20 0 20 40 60 80 100**

**X**

(b)

**−5 0 5 10 15 20 25 30**

**X**

(d)

<sup>2</sup> − *r*˜

<sup>2</sup> = (*r*˜

<sup>1</sup> = *r*<sup>2</sup> − *r*1), the LOP for the

<sup>4</sup> (5)

<sup>2</sup> − *r*˜

<sup>1</sup>) (4)

**Anchor node Regular node Observed range Actual range Linear Form LOP Hyperbolic LOP**

**Anchor node Regular node Observed range Actual range Linear Form LOP Hyperbolic LOP**

**Anchor node Regular node Observed range Actual range Linear Form LOP Hyperbolic LOP**

**Anchor node Regular node Observed range Actual range Linear Form LOP Hyperbolic LOP**

**−20 0 20 40 60 80 100 120**

(a)

**−50 0 50 100 150 200**

(c)

equate to actual difference for equal noise presence (*e.g.*, *r*˜

noise parameters as shown in Fig. 2 and formulated below:

 *<sup>x</sup>* <sup>−</sup> *<sup>a</sup>* 2 2

(*x* − *x*1)

<sup>2</sup> <sup>−</sup>

<sup>1</sup> − *r*˜ <sup>2</sup> = *c*.

**X**

The case when ranging errors are of opposite signs.

**X**

(*x* − *x*2)

(0, 0), **p**<sup>2</sup> = (*a*, 0), and *r*˜

<sup>2</sup> <sup>+</sup> (*<sup>y</sup>* <sup>−</sup> *<sup>y</sup>*2)

**Y**

**Y**

The hyperbolic LOP represents the actual LOP for a pair of satellites under the equal noise assumption. The linear form LOP does not truly represent the locus of the receiver in presence of noise unless both ranges to the satellites are equal as clarified in Fig. 2. Two possible cases could arise due to equal noise presence: *a*) the circular ranges have a physical intersection and *b*) the circular ranges do not have any physical intersection. In both cases, the hyperbolic LOP is able to represent the original receiver position whereas linear form LOP deviates from receiver position significantly. As establishing the LOP is the first step in positioning, any error present at this step could aggravate the result significantly and hence finding a LOP closer to the original receiver position is fundamental to achieving high accuracy positioning.

It is also crucial to compare the hyperbolic and linear form LOPs for unequal noise components in individual measurements as in reality this assumption can be void. In these general situations three possible cases could arise. *a*) the observed circular ranges have a physical intersection; *b*) the observed circular ranges do not have any common intersection region; and *c*) One of the observed circular ranges overlap completely within the other circular region.

These three cases are shown in Fig. 3 where Fig. 3(a), (b) shows the hyperbolic and linear form LOPs for noise ratio (ξ1/ξ2) of 2 while Fig. 3(c) shows the LOPs for noise ratio of 4. Fig. 3(c) also shows that for completely overlapped ranges the hyperbolic formulation turns into elliptic formulation. This is the case when coefficient of *y*<sup>2</sup> in (5) changes sign as the range difference becomes greater than distance between the satellites (*c* > *a*). The noise presence generally attenuates the signal more than that of ideal propagation scenario causing overestimation of the range. However, it is theoretically possible to imagine the case where range is underestimated due to noise. The simultaneous overestimation and underestimation of ranges is supposed to be the most detrimental for LOP estimation and hence this case is shown in Fig. 3(d). It is evident from the figures that for all the three cases of unequal noise presence as well as for noise having different signs, hyperbolic formulation is better suited than linear form and the impact of noise is less detrimental on hyperbolic LOPs than it is on linear form LOPs.

#### **3. Analytical approaches for global positioning**

We have discussed about the mathematical basis for positioning and presented the problems of regular trilateration from the viewpoint of noisy measurements. The positioning algorithms for GPS need greater care for noise and often augmented by filtering process to mitigate the effect of noise. However, they still largely depend on basic analytical positioning both for initial estimation and for error correcting/filtering phase. In this chapter, we present the different analytical algorithms for GPS.

We begin with the 3-D analogous formula for equation 2 which represents a sphere.

$$\left|\tilde{r}\_i^2 = (r\_i + \xi\_i)^2 = \|\mathbf{p}\_i - \rho\|^2 = \left( (\mathbf{x} - \mathbf{x}\_i)^2 + (y - y\_i)^2 + (z - z\_i)^2 \right) \tag{6}$$

A generally acceptable modeling of the ranging error ξ*<sup>i</sup>* is described by the following equation (Strang & Borre, 1997).

$$\xi\_{i} = I\_{i} + T\_{i} + c \left( dt\_{i}(t - \tau\_{i}) - dt(t) \right) - e\_{i} \tag{7}$$

where *Ii* is the ionospheric error, *Ti* is the tropospheric error, *c* is the speed of light, *dti* is the satellite clock offset, *dt* is the receiver clock offset, *t* is the receiver time and τ*<sup>i</sup>* is the signal propagation time and *ei* represents all other unmodelled error terms.

When more than four observations are available we can compute the correction values

Beyond Trilateration: GPS Positioning Geometry and Analytical Accuracy 247

*<sup>r</sup>*<sup>1</sup> <sup>−</sup>*z*1−*z*<sup>0</sup>

*<sup>r</sup>*<sup>2</sup> <sup>−</sup>*z*2−*z*<sup>0</sup>

*rm* <sup>−</sup>*zm*−*z*<sup>0</sup>

If the code observations are independent and assumed to have equal variance, then the above

We want to turn positioning into a linear algebra problem. Here is a clever method due to Bancroft (1985) that does some algbraic manipulations to reduce the equations to a least-squares problem. Multiplying things out in equation 6 and using the receiver clock bias −*b* = ξ�

� for the preliminary estimate. The least squares formulation can be concisely

⎤

⎡

δ*x* δ*y* δ*z* δ*c dt*

⎤

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

= (*AT*Σ−1*A*)−<sup>1</sup>*AT*Σ−1**b** (13)

= (*ATA*)−<sup>1</sup>*AT***b** (14)

2

*<sup>x</sup>*<sup>2</sup> <sup>+</sup> *<sup>y</sup>*<sup>2</sup> <sup>+</sup> *<sup>z</sup>*<sup>2</sup> <sup>−</sup> *<sup>r</sup>*

�*T* .

*<sup>i</sup>* <sup>−</sup> <sup>2</sup>*rib* <sup>+</sup> *<sup>b</sup>*<sup>2</sup> (15)

2 �

�ρ, ρ� = 0; (17)

*<sup>T</sup>* denote the *i*

*i s* as

= 0 (16)

*th* satellite

*x*<sup>0</sup> + δ*x y*<sup>0</sup> + δ*y z*<sup>0</sup> + δ*z*

*<sup>i</sup>* <sup>−</sup> <sup>2</sup>*ziz* <sup>+</sup> *<sup>z</sup>*<sup>2</sup> <sup>=</sup> *<sup>r</sup>*

= **b** − � (12)

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

*<sup>r</sup>*<sup>1</sup> 1

*<sup>r</sup>*<sup>2</sup> 1

*rm* 1

�

δ *x*, δ *y*, δ *z*

written as follows.

The least squares solution is

can be simplified to

**Ax** =

The final position vector can be estimated by <sup>ρ</sup> = �

*<sup>i</sup>* <sup>−</sup> <sup>2</sup>*xix* <sup>+</sup> *<sup>x</sup>*<sup>2</sup> <sup>+</sup> *<sup>y</sup>*<sup>2</sup>

*<sup>i</sup>* <sup>+</sup> *<sup>z</sup>*<sup>2</sup> *<sup>i</sup>* − *r* 2 *i* �

Using *Lorentz inner product* for 4-space defined by:

1 2

**3.3 Bancroft's method (least squares solution)**

the only noise parameter, we get

*x*2

� *x*2 *<sup>i</sup>* <sup>+</sup> *<sup>y</sup>*<sup>2</sup>

position and range vectors.

 However, the iterative approach will be computationally expensive. Moreover, the positioning accuracy will be poor as there is no proper formalism to identify and mitigate the error components.

#### **3.1 Ordinary trilateration for positioning**

Let **<sup>P</sup>***<sup>i</sup>* <sup>=</sup> � **p***i* <sup>1</sup>, **<sup>p</sup>***<sup>i</sup>* 2 � be an arbitrary satellite pair, where **p***<sup>i</sup>* <sup>1</sup> <sup>=</sup> � *xi* <sup>1</sup>, *yi* 1, *zi* 1 � and **p***<sup>i</sup>* <sup>2</sup> <sup>=</sup> � *xi* <sup>2</sup>, *yi* 2, *zi* 2 � represent satellite positions of the *i th* pair. Analogous to 2-D linear form LOP of equation 3, a 3-D planar form LOP is found as follows.

$$\begin{aligned} \left(\mathbf{x}\_2^i - \mathbf{x}\_1^i\right)\mathbf{x} + \left(y\_2^i - y\_1^i\right)\mathbf{y} + \left(z\_2^i - z\_1^i\right)\mathbf{z} &= \\ \frac{1}{2}\left(\|\mathbf{p}\_2^i\|^2 - \|\mathbf{p}\_1^i\|^2 + \left(r\_1^i\right)^2 - \left(r\_2^i\right)^2 + 2\xi\left(r\_1^i - r\_2^i\right)\right) &\tag{8} \end{aligned} \tag{9}$$

Where it is assumed that the noise are equal and constant for a particular satellite pair *i.e.*, ξ<sup>1</sup> = ξ<sup>2</sup> = ξ.

The equation becomes linear in terms of *x*, *y*, *z* and ξ if the noise is represented by a single parameter ξ for all pairs. In that case there are four unknowns in this equation and therefore four equations will be required to solve them. In practicality, the assumption is susceptible for large positioning error and hence iterative refinement approach of the following is rather adopted for real implementations.

#### **3.2 Iterative least squares estimate**

The iterative approach works by having a preliminary estimate of the receiver position (ρ<sup>0</sup> = [*x*<sup>0</sup> *y*0*z*0] *<sup>T</sup>*). Let the rotation rate of the earth be ω. The position vectors in the earth centered earth fixed (ECEF) system of the receiver be donated by ρ(*t*)*ECEF* and geo-stationary position vector for satellite *i* be denoted by **p***i*(*t*)*geo* where the argument *t* denotes the dependence on time. The range equation can be written as:

$$r\_i = \|R\_3(\omega \tau\_i) \mathbf{p}\_i(t - \tau\_i)\_{\text{geo}} - \rho(t)\_{\text{ECEF}}\|\tag{9}$$

Where *R*<sup>3</sup> is the earth's rotation matrix as defined below.

$$R\_3(\omega \tau\_i) = \begin{bmatrix} \cos(\omega \tau\_i) & \sin(\omega \tau\_i) & 0\\ -\sin(\omega \tau\_i) & \cos(\omega \tau\_i) & 0\\ 0 & 0 & 1 \end{bmatrix}$$

Let

$$
\begin{bmatrix} x\_i \\ y\_i \\ z\_i \end{bmatrix} = \mathcal{R}\_3(\omega \tau\_i) \mathbf{p}\_i(t - \tau\_i)\_{\mathcal{G}^{\otimes 0}} \quad \text{and} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \rho(t)\_{\text{ECEF}} \tag{10}
$$

Now, omitting the refraction terms *Ii* and *Ti* and linearizing the equation 6, we get

$$-\frac{\mathbf{x}\_{i}-\mathbf{x}^{0}}{(\tilde{r}\_{i})^{0}}\delta\mathbf{x}-\frac{y\_{i}-y^{0}}{(\tilde{r}\_{i})^{0}}\delta y-\frac{z\_{k}-z^{0}}{(\tilde{r}\_{i})^{0}}\delta z+(\mathbf{c}\,dt)=\tilde{r}\_{i}-(\tilde{r}\_{i})^{0}-\mathbf{c}\_{i}=b\_{i}-\mathbf{c}\_{i}\tag{11}$$

where *bi* denotes the correction to the preliminary range estimate.

When more than four observations are available we can compute the correction values � δ *x*, δ *y*, δ *z* � for the preliminary estimate. The least squares formulation can be concisely written as follows.

$$\mathbf{A}\mathbf{x} = \begin{bmatrix} -\frac{\underline{x}\_1 - \underline{x}^0}{r\_1} - \frac{y\_1 - \underline{y}^0}{r\_1} & -\frac{z\_1 - \underline{z}^0}{r\_1} & 1\\ -\frac{\underline{x}\_2 - \underline{x}^0}{r\_2} & -\frac{y\_2 - \underline{y}^0}{r\_2} & -\frac{z\_2 - \underline{z}^0}{r\_2} & 1\\ \vdots & \vdots & \vdots & \vdots\\ -\frac{\underline{x}\_m - \underline{x}^0}{r\_m} & -\frac{y\_m - \underline{y}^0}{r\_m} & -\frac{z\_m - \underline{z}^0}{r\_m} & 1 \end{bmatrix} \begin{bmatrix} \delta x\\ \delta y\\ \delta z\\ \delta c \, dt \end{bmatrix} = \mathbf{b} - \boldsymbol{\varepsilon} \tag{12}$$

The least squares solution is

6 Will-be-set-by-IN-TECH

The equation 6 can be iteratively solved using Newton's method. However, the iterative approach will be computationally expensive. Moreover, the positioning accuracy will be poor

> <sup>1</sup> <sup>=</sup> � *xi* <sup>1</sup>, *yi* 1, *zi* 1 � and **p***<sup>i</sup>*

*th* pair. Analogous to 2-D linear form LOP of equation 3, a

<sup>2</sup> <sup>=</sup> � *xi* <sup>2</sup>, *yi* 2, *zi* 2 �

�� (8)

as there is no proper formalism to identify and mitigate the error components.

be an arbitrary satellite pair, where **p***<sup>i</sup>*

2�<sup>2</sup> − �**p***<sup>i</sup>*

<sup>1</sup>�<sup>2</sup> <sup>+</sup> � *r i* 1 �2 − � *r i* 2 �2 + 2ξ � *r i* <sup>1</sup> − *r i* 2

Where it is assumed that the noise are equal and constant for a particular satellite pair *i.e.*,

The equation becomes linear in terms of *x*, *y*, *z* and ξ if the noise is represented by a single parameter ξ for all pairs. In that case there are four unknowns in this equation and therefore four equations will be required to solve them. In practicality, the assumption is susceptible for large positioning error and hence iterative refinement approach of the following is rather

The iterative approach works by having a preliminary estimate of the receiver position (ρ<sup>0</sup> =

earth fixed (ECEF) system of the receiver be donated by ρ(*t*)*ECEF* and geo-stationary position vector for satellite *i* be denoted by **p***i*(*t*)*geo* where the argument *t* denotes the dependence on

*<sup>T</sup>*). Let the rotation rate of the earth be ω. The position vectors in the earth centered

cos(ωτ*i*) sin(ωτ*i*) 0 −sin(ωτ*i*) cos(ωτ*i*) 0 0 01

> ⎡ ⎢⎢⎢⎢⎢⎢⎣ *x y z*

⎤

*ri* = �*R*3(ωτ*i*)**p***i*(*t* − τ*i*)*geo* − ρ(*t*)*ECEF*� (9)

⎤ ⎥⎥⎥⎥⎥⎥⎦

(*r*˜*i*)<sup>0</sup> <sup>δ</sup>*<sup>z</sup>* + (*c dt*) = *<sup>r</sup>*˜*<sup>i</sup>* <sup>−</sup> (*r*˜*i*)<sup>0</sup> <sup>−</sup> �*<sup>i</sup>* <sup>=</sup> *bi* <sup>−</sup> �*<sup>i</sup>* (11)

⎥⎥⎥⎥⎥⎥⎦ <sup>=</sup> <sup>ρ</sup>(*t*)*ECEF* (10)

**3.1 Ordinary trilateration for positioning**

3-D planar form LOP is found as follows.

� *xi* <sup>2</sup> <sup>−</sup> *<sup>x</sup><sup>i</sup>* 1 � *<sup>x</sup>* + � *yi* <sup>2</sup> <sup>−</sup> *<sup>y</sup><sup>i</sup>* 1 � *<sup>y</sup>* + � *zi* <sup>2</sup> <sup>−</sup> *<sup>z</sup><sup>i</sup>* 1 � *z* =

1 2 � �**p***i*

represent satellite positions of the *i*

adopted for real implementations.

**3.2 Iterative least squares estimate**

time. The range equation can be written as:

Where *R*<sup>3</sup> is the earth's rotation matrix as defined below.

⎡ ⎢⎢⎢⎢⎢⎢⎣ *xi yi zi*

(*r*˜*i*)<sup>0</sup> <sup>δ</sup>*<sup>x</sup>* <sup>−</sup> *yi* <sup>−</sup> *<sup>y</sup>*<sup>0</sup>

<sup>−</sup> *xi* <sup>−</sup> *<sup>x</sup>*<sup>0</sup>

⎤

*R*3(ωτ*i*) =

⎡ ⎢⎢⎢⎢⎢⎢⎣

⎥⎥⎥⎥⎥⎥⎦ <sup>=</sup> *<sup>R</sup>*3(ωτ*i*)**p***i*(*<sup>t</sup>* <sup>−</sup> <sup>τ</sup>*i*)*geo and*

Now, omitting the refraction terms *Ii* and *Ti* and linearizing the equation 6, we get

(*r*˜*i*)<sup>0</sup> <sup>δ</sup>*<sup>y</sup>* <sup>−</sup> *zk* <sup>−</sup> *<sup>z</sup>*<sup>0</sup>