Connected Vehicles: Intelligent Transportation Systems

Wireless Networks Radovan Miucic Editor Connected Vehicles Intelligent Transportation Systems

Wireless Networks Series editor Xuemin Sherman Shen University of Waterloo, Waterloo, Ontario, Canada

More information about this series at http://www.springer.com/series/14180

Radovan Miucic Editor Connected Vehicles Intelligent Transportation Systems 123

Editor Radovan Miucic Department of Electrical and Computer Engineering Wayne State University Detroit, MI, USA ISSN 2366-1186 ISSN 2366-1445 (electronic) Wireless Networks ISBN 978-3-319-94784-6 ISBN 978-3-319-94785-3 (eBook) https://doi.org/10.1007/978-3-319-94785-3 Library of Congress Control Number: 2018957111 © Springer Nature Switzerland AG 2019 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company Springer Nature Switzerland AG The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

Contents Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Radovan Miucic Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Zeljko Popovic and Radovan Miucic Human Machine Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Zeljko Medenica A Security Credential Management System for V2X Communications . . . . . 83 Benedikt Brecht and Thorsten Hehn V2V Vehicle Safety Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Shubham Shrivastava Vehicle to Infrastructure Communications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 Samer Rajab Cooperative Vehicle to Pedestrian Safety System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 Radovan Miucic and Sue Bai 5.9 GHz Spectrum Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Ehsan Moradi-Pari Efficient and High Fidelity DSRC Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Yaser P. Fallah and S. M. Osman Gani Applications of Connectivity in Automated Driving . . . . . . . . . . . . . . . . . . . . . . . . . 245 Ahmed Hamdi Sakr, Gaurav Bansal, Vladimeros Vladimerou, Kris Kusano, and Miles Johnson v

Introduction Radovan Miucic Introduction Next generation of vehicle safety applications will hinge on connectivity. It is also widely accepted notion that connectivity will be key enabling technology for autonomous driving. That connectivity may include Vehicle to Vehicle (V2V), Vehicle to Infrastructure (V2I), and Vehicle to Pedestrian (V2P) communications. One of the questions is “what technology will prevail?” Lower layers of Dedicated Short Range Communication (DSRC) are defined in IEEE 802.11. The automotive industry, academia, and government have been evaluating DSRC since late 1990s. On the other side, recently the cellular industry has taken an interest in developing standards for vehicular usage. DSRC is based on relatively old physical layer protocol. But, it has been tested and proven to meet requirements for the vast majority of the cooperative safety applications in term of range and latency. The newer 5G cellular approach is not thoroughly tested for cooperative vehicle safety. It does offer potentially better communication performance and a path for system upgradeability. Whichever technology prevails, safety communication requirements will remain unchanged: high availability and low latency. Vehicle to everything (V2X) communications needs to accommodate fast-moving vehicles. Vehicles in various traffic situations need to communicate with low latency. End to end latency should be in the order of 100 ms. It is necessary for V2X communications to be highly available. In other words, V2X is not to compete with other crowded communications networks such as WiFi and cellular networks. DSRC historically evolved from WiFi. In late 1990s, when the DSRC research was in its infancy, the best wireless technology was Wi-Fi. The researchers used R. Miucic ( ) 1 Department of Electrical and Computer Engineering, Wayne State University, Detroit, MI, USA e-mail: radovan@wayne.edu © Springer Nature Switzerland AG 2019 R. Miucic (ed.), Connected Vehicles, Wireless Networks, https://doi.org/10.1007/978-3-319-94785-3_1

2 R. Miucic Wi-Fi chipsets for the V2X communication development. More recently dedicated chipsets for DSRC started to take a foothold. IEEE task force introduced DSRC physical layer modifications in 802.11 as an 802.11p amendment. The amendment was fully integrated into 2012 version of the 802.11 standard. Aims of modifications are to reduce overhead, to limit out of band interference, and make provisions for outdoor multi-path and higher vehicle speeds. In the US, IEEE standards define lower layers of DSRC. SAE documents define the application layer. IEEE 802.11 details physical and lower Media Access Control (MAC) layers. IEEE 1609.4 describes upper MAC layer. IEEE 802.4 covers logical link control (LLC) layer. IEEE 1609.3 defines Network and Transportation layers. IEEE 1609.2 covers security. Finally, SAE J2735 and J2945 specify application layer. Federal Communications Commission (FCC) allocated 75 MHz for V2X communication in 1999. At that time FCC crafted the usage for manually driven vehicles. The main usage of V2X indents to improve travelers’ safety. Other approved usages include decreasing traffic congestion, air pollution, and fuel consumption. In the future, V2X communication may extend to include the needs of the autonomous vehicles. V2X communication is a set of communication protocols, experiments, and pilot deployments. As such, V2X communications are addressing the needs of current and future travelers. It is important that V2X is a direct communication. For example, V2V communication is the exchange of the information directly between vehicles without intermediaries such as cell-phone infrastructure or WiFi hotspot. DSRC-V2V does not require infrastructure to facilitate the communication between vehicles. Another mode of communication is Vehicle to Infrastructure (V2I). V2I communication is the exchange of information between vehicles and roadside infrastructure. For example, a RoadSide Unit (RSU) can be connected to a signal controller at an intersection. RSU sends out intersection map (MAP) message and traffic signal status message know as Signal Phase and Timing (SPaT) message. Next in line is Vehicle to Pedestrian (V2P) communication. V2P involves exchanging information between vehicles and pedestrians. For example, DSRC enabled smartphone can serve as a pedestrian communication device. Implemen- tation of the V2X in a vehicle consists of the several standard components. The components include localization device, computation platform, HMI interface and DSRC transceiver. Collection of these components is commonly called On-Board Equipment (OBE). Fully implemented OEM V2X system may include connections to the internal vehicle bus. Aftermarket devices may not have access to the internal vehicle bus. The most important message in V2V communication is Basic Safety Message (BSM). A DSRC equipped vehicle broadcasts BSMs to all other vehicles in its vicinity. BSM consists of crucial information about the vehicle such as position and vehicle dynamics. Some elements of the BSM are latitude, longitude, elevation, speed, heading, brake status, accelerations, dimensions, and path history and path prediction. Once a vehicle receives BSM from a remote vehicle it is able to compute collision probability and if needed warns the driver. V2V cooperative safety applications are addressing immediate situations. These situations include collision avoidance and traffic scene awareness. For example, a

Introduction 3 very typical V2V application is Electronic Emergency Brake Light (EEBL). EEBL informs the driver when a vehicle in front brakes hard. EEBL helps the driver by giving an early notification that the leading vehicle is braking hard. EEBL warns even in the case of limited driver’s visibility (e.g. a large truck is blocking the driver’s view, heavy fog or rain). Another V2V example is co-operative Forward Collision Warning (FCW). FCW issues a warning to the driver of the host vehicle in case of an impending front-end collision. For example, a slow-moving vehicle ahead in the same lane and direction of travel is a candidate for FCW warning. FCW helps drivers avoid a collision in the forward path of travel. Blind Spot Warning (BSW) provides a notification to the driver when a remote vehicle is in its blind spot. Left Turn Assist (LTA) warns the driver in case it is unsafe to make a left turn at an intersection. For example, a remote vehicle approaches from the opposite direction in the adjacent lane. Intersection Movement Assist (IMA) issues a warning to the driver in case of an impending side collision. A remote vehicle driving in a perpendicular direction to the ego vehicle is a candidate for IMA warning. This often happens at an intersection. Control Loss Warning (CLW) issues a warning in case of a possible collision with a remote vehicle of which the driver has lost control. CLW helps avoid or mitigate collisions in a variety of traffic scenarios. Like BSM, a Pedestrian Safety Message (PSM) is being transmitted from a smartphone. PSM consists of vital pedestrian data. The data include latitude, longitude, elevation, speed, heading, and dimensions. PSM has similar but less information than BSM. V2P collision avoidance application works in a similar fashion to V2V. An aim of V2P cooperative safety applications is an increase in driver awareness. Candidates for V2P applications are vulnerable road users (generally pedestrians and cyclists). Pedestrian collision avoidance application warns the driver of impending pedestrians. For example, a vehicle would warn the driver in case a pedestrian, crossing the street, jumps in front of the moving vehicle. V2I applications are usually local in character. An example is Cooperative Intersection Collision Avoidance Systems (CICAS). CICAS can issue traffic signal violation warning to the driver if he is about to run the red light. Pothole Detection is an example collaborative V2I application. Pothole Detection leverage collabo- ration from many vehicles and the infrastructure. Vehicles share information with infrastructure about their location and sudden events. One type of events includes maneuvers the driver is taking to avoid the pothole. Another type of events includes a sudden change in vertical acceleration of the vehicle going over a pothole. The infrastructure analyzes many such reports from vehicles. The infrastructure then sends aggregated data informing the vehicles about the existence of a pothole. A unique feature of the V2X technology is the ability to detect threats in non- line of site situations. Many safety applications such as FCW, BSW and pedestrian collision warning are implemented using a traditional line of sight sensors such as camera or radars. However, cameras and radars cannot detect vehicles and pedestrians in non line of sight scenarios such as a blind intersection or obstructed traffic. V2X is envisioned to fill “the gap” and enhance the sensing ability of the vehicle. A traditional line-of-sight sensor (e.g. camera or radar) is estimating information such as relative position, speed, direction and infer the braking status of

4 R. Miucic the targets whereas V2X is actually getting this information from the best possible sensors, from the remote vehicle internal bus itself. List of Chapters This will book covers the current status and many remaining challenges that face communication for the Intelligent Transportation Systems. The material covered in the book is organized as follows. Chapter “Positioning” describes principles of localization services as a key enabler for V2X technology. Chapter “Human Machine Interface” focuses on Human Machine Interface for the cooperative safety applications. Chapter “A Security Credential Management System for V2X Communications” gives an overview of the Security Credential Management System (SCMS) for V2X communications system. Chapters “V2V Vehicle Safety Communication”, “Vehicle to Infrastructure Communications” and “Cooperative Vehicle to Pedestrian Safety System” identify V2V, V2I, and V2P applications and requirements. Chapter “5.9 GHz Spectrum Sharing” explains proposals for sharing the 5.9 GHz spectrum between Intelligent Transportation Systems (ITS) and Consumers Electronic industries. Chapter “Efficient and High Fidelity DSRC Simulation” explains the work done in simulating DSRC communication networks. Finally, Chapter “Applications of Connectivity in Automated Driving” looks into the potential future usage for the V2X technology by exploring applications of connectivity in automated driving. Positioning Benefits of connectivity in ITS, including safety and convenience, arise from information shared between connected vehicles, other connected traffic participants, and road infrastructure. An essential shared set of information includes position (location) and velocity because they allow the connected device to know the presence and predict behavior of other relevant traffic, even by relying solely on the exchanged data in absence of other sensors. This further enables an in-vehicle system to warn the human driver, or even automatically initiate corrective actions. Satellite-based positioning systems, including the American Global Positioning System (GPS) and also other such Global Navigation Satellite Systems (GNSS), provide globally referenced location and velocity that are often sufficiently accurate for many ITS applications, but their performance suffers in obstructed skies. Integration of other positioning-relevant data through sensor fusion, such as that from inertial, ranging, and vision sensors, but also from maps, improves positioning robustness across diverse environments. Application of advanced satellite-based positioning algorithms, such as Differential GPS (DGPS), Real-Time Kinematic (RTK), and precise point positioning (PPP), to data received from ground reference

Introduction 5 stations, allows decimeter-level global positioning accuracy and improved integrity measures that further extend the scope of supported ITS applications. The DSRC standards, intended for ITS applications, conveniently provide for sharing of basic position data, local high-definition map data, as well as data for enabling high accuracy positioning. Planned improvements and expansions of GNSS systems, and trends of increasing performance-to-cost ratio of positioning-aiding sensors, suggest future gains in positioning accuracy, integrity, and availability. Positioning performance of currently available and expected future positioning solutions is assessed against their cost. There are currently available automotive-grade and ITS- suitable positioning systems that achieve lane-level accuracy, conditions-dependent, with some uncertainty. More advanced systems are expected to provide within-lane positioning with tight integrity measures. Human Machine Interface The main intention of this chapter is to describe what Human Computer Interaction (HMI) is, why it is important in the automotive context and how connected vehicles can benefit from it. Every device that is meant for people to use, cars included, should provide means that enable successful interaction. This is what HMI is all about: how to design an interface that enables intuitive, simple and timely interaction with a machine. Depending on the nature of the task some of these aspects may have higher priority compared to others. However, all three are extremely important in vehicles, because driving is a complex hands-busy, eyes-busy activity that poses both physical and cognitive load on drivers. In a situation like this, it is necessary for an HMI to provide adequate information to drivers without negatively affecting their primary task of driving. Information presented to drivers can be roughly divided in two categories: infotainment and safety. Infotainment is mostly concerned with convenience features in vehicles, such as navigation, music, climate control, phone, etc. In this chapter, we are primarily concerned with HMI for safety-related applications, since this is the area where connected vehicles can contribute the most. V2X communication enables a completely new horizon of sensing that is not achievable with any of the currently available vehicle sensors, such as radar, lidar, camera, etc. This makes it possible to design completely new safety-related and Advanced Driver Assistance Systems (ADAS) compared to what was possible before. In any case, the corresponding HMI should effectively explain the situation on the road and stimulate drivers to perform adequate actions (such as avoiding an obstacle or preemptive braking). This can be achieved by using any kinds of modalities (and their combinations) that influence people’s basic senses: sight, hearing, touch, smell and taste. In this chapter, we will cover some representative safety-related applications and analyze how different modalities can be used to create a successful HMI. Finally, we will briefly explore how HMI and connected vehicles converge in the autonomous driving domain.

6 R. Miucic A Security Credential Management System for V2X Communications V2X communications system requires that users are able to trust information presented to them. To this end, each receiver must be able to tell whether messages received over the air interface come from a trustworthy source and have not been tampered with during transmission. This trust relation needs to be established as soon as two vehicles receive messages from each other. At the same time, users care about privacy and will unlikely accept the system if it allows for tracking of singular devices. Providing both security and privacy to the largest extent reasonable and possible is the major challenge and design goal of the Security SCMS presented in this chapter. It has been designed for V2V and V2I communications and has been developed by the Crash Avoidance Metrics Partnership (CAMP) under a Cooperative Agreement with the USDOT. It is based on public key infrastructure (PKI) principles and issues digital certificates to participating vehicles and infras- tructure nodes for trustworthy communications among them, which is necessary for safety and mobility applications based on V2X communications. Standard solutions from literature, such as group signature schemes and management schemes for symmetric keys, do not meet the requirements of a V2X communications system. We briefly review these well-known schemes and show where they do not meet the requirements of V2X. The SCMS supports four main use cases, namely bootstrapping, certificate provisioning, misbehavior reporting and revocation. To achieve a reasonable level of privacy, vehicles are issued pseudonym certificates, and the generation and provisioning of those certificates are divided among multiple organizations. One of the main challenges is to facilitate efficient revocation of misbehaving or malfunctioning vehicles, while at the same time preserving privacy against attacks from insiders. We present a revocation process which actively informs the fleet about misbehaving devices and is very efficient in terms of revoking a high number of pseudonym certificates with little amount of data signaled over the air. Another challenge is to handle certificate authority revocations without requiring all affected devices to come back to dealerships or some form of secure environment. We present an approach called Elector-based Root Management to minimize the impact on devices. V2V Vehicle Safety Communication National Highway Traffic Safety Administration (NTHSA) has been interested in V2V communication as the next step in addressing grooving rates of fatalities from vehicle related crashes. Today’s crash avoidance technologies depend on on-board sensors like camera and radar to provide awareness input to the safety applications. These applications are warning the driver of imminent danger or sometimes even act on the driver’s behalf. However, even technologies like those cannot “predict”

Introduction 7 a crash that might happen because of a vehicle which is not very close or not in the line of sight to the host vehicle. A technology that can “see” through another vehicle or obstacles like buildings and predict a danger can fill these gaps and reduce crashes drastically. V2V communications can provide vehicles the ability to talk to each other and therefore see around corners and through the obstacles over a longer distance compared to the current on-board sensors. It is estimated that V2X communications address up to 80% of the unimpaired crashes. By means of Notice of Proposed Rulemaking (NPRM), NHTSA is working towards standardization of V2V communications and potentially mandating the broadcast of vehicle data (e.g. GPS coordinates, speed, acceleration) over DSRC through V2V.A vehicle needs an On-Board Unit (OBU) to establish the V2V communication with other vehicles also equipped with OBUs or V2I communication with the traffic infrastructure equipped with Road-Side Units (RSUs). In general, an OBU has a DSRC radio for transmission and reception, GNSS receiver, a processor, and several interfaces (e.g. CAN, Ethernet, GPS) for obtaining the vehicle data. Essential message in V2V communication is called Basic Safety Messages (BSM). BSM is a broadcast message typically transmitted frequently up to 10 times a second. Content of BSM includes vehicle information such as vehicle speed, location, and brake status. Safety applications use the remote vehicles (RVs) data from BSM and Host Vehicle (HV) data from the OBU interfaces like CAN and GNSS to predict a potential crash and alert the driver. V2V messages could also potentially be fused with on- board sensors like Radar, LiDAR, and Camera to improve the confidence level of vehicle detection for safety applications or even for autonomous driving to some extent. Majority of the crash scenarios can be addressed by the following safety applications: (1) Forward Collision Warning (FCW), (2) Electronic Emergency Brake Light (EEBL), (3) Intersection Move Assist (IMA), (4) Left Turn Assist (LTA), (5) Do Not Pass Warning (DNPW), and (6) Blind Spot Warning/Lane Change Warning (BSW/LCW). These applications showed promise to mitigate and prevent potential crashes in recent the Connected Vehicle Safety Pilot Deployment Program conducted by University of Michigan Transportation Research Institute (UMTRI) which was launched in August 2012.This chapter will describe six primary safety applications, their requirements from the implementation point of view, and will explain how each of these applications can alert the driver of a forthcoming crash threat to help reduce the crash. Vehicle to Infrastructure Communications Vehicle to Infrastructure communications (V2I) is one of the emerging connected vehicles technologies holding a promise for significant benefits to both road users and operators. A considerable research effort has been invested in V2I communications technology leading to a number standardized messages as well as application concepts. A number of V2I deployments are currently being planned and executed around the United States taking advantage of the recent technology

8 R. Miucic maturity level. An overview of these deployment efforts will be given in this chapter. Several aspects make V2I technology attractive to the ITS industry including early deployment benefits, extended information sharing ranges and sensing capabilities afar from what a vehicle on-board sensors can offer in real-time. Such aspects may provide substantial safety, mobility and environmental value as will be discussed in this chapter. This chapter deliberates on V2I communications technology and examines additional benefits it offers beyond V2V technology. Details of V2I Over The Air (OTA) messages developed by research and standardization organizations will be provided and discussed. Such messages enable wide variety of V2I safety, mobility and environmental applications. Examples of these applications will be detailed in the chapter. Cooperative Vehicle to Pedestrian Safety System This chapter provides an overview of the V2P cooperative safety application, enabling technologies and field test results. The chapter also covers the motivation for DSRC based V2P safety application research. We continue with comparison of the DSRC and Vision V2P collision detection systems. The chapter describes implemented system architecture and basic concepts of operation. A new mes- sage Pedestrian Safety Message (PSM), similar to BSM, was invented to signal pedestrian presence to surrounding vehicles. We used both PSMs and BSMs in our implementation of the V2P system. Our work was forerunner for the development of SAE J2945/9 standard “Vulnerable Road User Safety Message Minimum Performance Requirements”. It is crucial for the V2P system to have a usable vehicle warning strategy consisting of informative and alerting modalities. We present a multi stage warning system for alerting the driver of impeding collision with the pedestrian. This is followed by a description of our test setup. Finally we present the results of communication and application performance. 5.9 GHz Spectrum Sharing The Federal Communications Commission (FCC) issued a Notice of Proposed Rulemaking (NPRM) on February 20, 2013, regarding the feasibility and potential use of the 5.9 GHz Dedicated Short Range Communications (DSRC) spectrum by Unlicensed National Information Infrastructure (U-NII) devices. FCC is inves- tigating the feasibility of sharing 5.85–5.925 GHz spectrum between DSRC and unlicensed devices such as those using 802.11-based standards. The primary spectrum allocation for DSRC use was granted to the transportation community on December 17, 2003 with a condition for the need to prove that DSRC could co-exist with the other primary uses for military radar, satellite uplinks, and indoor industrial, scientific, and medical devices. Two interference mitigation approaches

Introduction 9 are introduced as candidates for spectrum sharing solution: (1) Detect and Avoid (DAA) and (2) modified DSRC channelization (re-channelization). This chapter explains current spectrum allocation as well as the impact the two proposals would have on the DSRC. Efficient and High Fidelity DSRC Simulation Vehicular communication is the backbone of connected vehicle (CV) technology. As a result, evaluation of the performance of vehicular wireless networks becomes a necessary part of designing CV applications. Given the complexities of channel and network situations it is not practical to test applications in field trials. In particular, when networks of thousands of vehicles within vicinity of each other is considered, it becomes prohibitively expensive and complex to setup tests in which a meaningful set of network and applications conditions are considered. As a result, simulation studies, in particular with respect to the DSRC component of the CV systems becomes necessary. Simulating DSRC networks can be done at many different levels, resolutions and fidelities. In this chapter we discuss different components of a DSRC network, and identify features and characteristics that impact CV application behavior, and thus require special attention in simulator design. We then identify modeling schemes and simulator design approaches that allow capturing the major and important features of DSRC networks. In particular, recent efforts in designing simulation models based on simulators such as ns-3 and OPNET will be discussed. Mathematical models that can further abstract network and communication link behaviors will also be discussed. The general modeling approach is discussed at three levels (layers) of channels, transceivers and networks. We explore the diversity of vehicular communication channels and determine the issues that arise when different channel models are considered for evaluation of CV applications. Transmitter/Receiver models are also discussed and presented at different levels of fidelity. Network models are shown to be generally dependent on road topology and vehicle density; though it is possible to find several general models for network behavior. The chapter is concluded with a study of the impact of simplification of models in each of the above three layers. Applications of Connectivity in Automated Driving Vehicles in the near future will be equipped with DSRC transceiver which holds great promise of significantly reducing vehicle collisions by enabling V2V and V2I communications. In addition, modern vehicles will be equipped with different on- board sensors such as GPS receivers, cameras, radars, LiDARs, etc. Using these technologies, we propose two applications to improve the driving experience and enable future advanced driver assistance systems (ADAS). In the first application,

10 R. Miucic we propose a comprehensive system design to improve the positioning of an ego vehicle based on Kalman filters. In this approach, the ego vehicle fuses its own position information obtained by the on-board GPS receiver with position information of nearby vehicles collected by the on-board ranging sensor(s) and the messages received via the DSRC transceiver from other equipped vehicles. This process also involves performing track matching using a multi-sensor multi-target track association algorithm. On the other hand, the second application aims at road geometry estimation as an essential step in ADAS applications where an ego vehicle builds a local map of the road ahead using its on-board sensors. We propose a novel design for road geometry estimation by fusing on-board sensor (camera and radar) data with the standard V2V messages received from remote vehicles via DSRC. Our Kalman Filter-based methods fuse measurements by on-board sensors with information from V2V messages to produce a long-range estimate for the road geometry ahead of the ego vehicle. For the localization application, we provide insights on the system design and present simulation and experimental results that show significant performance gains of the proposed methods in terms of localization accuracy and matching accuracy. For the road geometry estimation application, we show by experimental data that the proposed method achieves more than 7× the accuracy of current state-of-the-art camera-radar fusion methods.

Positioning Zeljko Popovic and Radovan Miucic Introduction Motivation Ubiquity of devices with satellite location technology, and their usefulness, has made the location technology familiar to the masses. There is almost a dependence on it for achieving efficient everyday mobility. However, it is the promise of sharing the location data among traffic participants that elevates its significance from providing universal navigation convenience to helping bring provide traffic safety for all. V2X communication technology, that is, the communication technology that allows vehicles to communicate with all other traffic participants (vehicle, V2V; pedestrians, V2P), as well as to traffic control infrastructure (V2I), promises a new, cost-effective, layer of safety. The primary mechanism for this is sharing of location data. Location shared among surrounding traffic and infrastructure allows all to be aware of all others, even when other forms of sensing fail due to sight-line obstructions. On-board computers could even use this awareness to automatically initiate defensive actions to reduce the risk of collisions. Furthermore, the communication and positioning technologies that are required to support this are less expensive to add than sensors used so far in avoiding collisions—such as lidars, radars, and cameras—thus allowing V2X technology to bring automatic collision avoidance, and conveniences, beyond luxury vehicles to all road users. Z. Popovic ( ) San Francisco, CA, USA R. Miucic Department of Electrical and Computer Engineering, Wayne State University, Detroit, MI, USA e-mail: radovan@wayne.edu © Springer Nature Switzerland AG 2019 11 R. Miucic (ed.), Connected Vehicles, Wireless Networks, https://doi.org/10.1007/978-3-319-94785-3_2

12 Z. Popovic and R. Miucic Positioning Requirements for Intelligent Transportation Systems For sharing of position data to be effective in improving safety, it needs to be of certain accuracy and reliability. There are some traffic scenarios in which road-level positioning accuracy—knowing which road we are on—can be sufficient to provide assessments needed for issuing warnings and corrective actions that can improve safety. Examples include dealing with oncoming traffic in making unprotected turns through intersections and slowing down for road conditions ahead (tight turns seen in maps, icy spots reported by other vehicles, . . . ). Beyond that, there is a significant portion of traffic scenarios in which reliably knowing positions of traffic participants down to the lane of travel is needed (and sufficient) to prevent collisions or road excursions. Among others these include: anticipating sudden traffic slow-downs in our own lane, preventing unintended lane or road departures, and reacting to traffic controls applicable only to our lane, where the latter can depend on similarly accurate maps of intersection zones. With the aim of quantifying the required positioning accuracy levels, road-level accuracy values are derived from the need to distinguish between nearby or adjacent roads that have similar directions of travel but are not physically or topologically connected and thus can’t influence each other’s traffic. This distinction is needed to prevent false warnings and reactions. In the most stringent and ambiguous cases, for example adjacent lanes separated by a barrier, this requirement reduces to the requirement of lane-level accuracy, but often 5 or 10 m of accuracy is sufficient. Setting a number for lane-level accuracy also does not have a definite anchor, but 1.5 m is suggested here because for a vehicle travelling down the middle of a 3 m lane any larger error would place it in another (and thus wrong) lane. A 3 m lane, which is an unusually narrow lane in the United State, is used here in order to cover most of the lane width diversity: In the US, lanes with widths of 3 m or more are used about 90% of the time [1]. The main source of positioning information in V2X systems, and the only source of absolute positioning information, has been GPS (Global Positioning System, maintained by the United States government) and similar systems maintained by other governments, where any such system is known as a GNSS system (Global Navigation Satellite System). GNSS can provide adequate positioning performance for V2X in most cases, but to make a positioning system sufficiently robust for safety applications it needs to be combined with other information, typically from sensors that reliably relate a vehicle’s change of position over time (such as inertial sensors), but can’t provide absolute position coordinates (which are required for seamless sharing of location with other vehicles and for use of maps). The aims of this chapter are to introduce: operation of GNSS systems while using GPS as the main example (Section “GNSS Principles”), use of GNSS positioning in V2X systems (Section “Basic GNSS Positioning in Cooperative Vehicles”), GNSS sources of errors and ways of limiting those errors, including advanced techniques for achieving centimeter-level accuracy (Section “GNSS Performance

Positioning 13 and High-Accuracy Methods”), and ways of combing GNSS data with other sensing for achieving a robust position solution (Section “Multi-Sensor Fusion for Robust and Accurate Positioning”). The goal of covering this broad scope in a single introductory chapter does not allow room for getting into the depth of theoretical derivations and implementation details, but those are already well covered in existing dedicated publications and the value of this chapter instead lies in enabling those new to these fields to quickly become familiar with numerous key concepts through an intuitively developed understanding. This serves to allow effective initial consideration of the technologies involved and can efficiently direct further independent study. GNSS Principles What Is GPS? GPS, strictly speaking, stands for Global Positioning System. It is the United States maintained system that consists of a set of Earth-orbiting satellites. The satellites continually broadcast signals that allow an Earth-based user with a suitable device (a GPS receiver) to determine the user location coordinates on Earth typically to an accuracy in the order of meters, and down to centimeters when locally- specific corrective data is available. In this proper sense, which will be used in this chapter, a GPS receiver that does not contain maps and does not provide navigation direction. In popular use however, in particular in the United States, the meaning of “GPS” has been extended to refer to any device that provides displays of user’s global location on a map and that might also provide turn-by-turn directions, which elsewhere in the world is more tellingly referred to as “satellite navigation” or “sat-nav”. There are similar systems maintained, or in process of development, by other countries. Such a system is generically referred to as a Global Navigation Satellite System (GNSS). Characteristics of other GNSS systems are presented in Section “Other GNSS Systems”. The discussion that follows is presented as GPS specific, but in most cases, it applies to all other GNSS systems. Any important differences will be specifically noted. Trilateration and Triangulation Concepts The method that underlies GPS (and GNSS) location determination is trilateration, which is an estimation of user position based on user measurements of distances to objects with known locations. Sometimes this estimation is mistakenly referred

14 Z. Popovic and R. Miucic to as triangulation, which is a different method that relies on the use of angle measurements. In the case of GPS, the objects with known locations are the GPS satellites. The satellites make their locations known to the user’s device via messages carried on signals that they transmit. The user’s receiver measures the distances to each visible satellite by converting to distance the time delay in getting the signal, using the speed of light (Eq. (1)): (distance to satellite) = (signal speed)∗ (signal arrival time–signal sending time) (1) The signal sending time is encoded in the message, while the determination of the signal arrival time will be explained in the next section. Given the satellite locations and distances to at least four satellites, the user location estimate can be visualized as the intersection of spheres (circles in 2D). The spheres are centered at the satellites locations and with radii equal to the distances to the satellites (Fig. 1). Spheres from three satellites are needed to narrow down their intersection to a point (in the case of perfect measurements). The fourth satellite is needed because there is drift between the receiver and satellite clocks that converts into position uncertainty and thus also needs to be estimated. Using more than four satellites reduces the estimate error, as further discussed in Section “Calculation of Position and Time” on position, velocity, and time calculations. Fig. 1 Trilateration using three satellite locations and distances

Positioning 15 Basic Operation of GPS Positioning Keeping the concept of trilateration in mind, here is a more extended, but still simplified, outline of how various quantities are extracted from GPS signals and combined into a position estimate (Fig. 2). The actual specification of GPS signals and data described below is given by the Interface Control Document IS-GPS-200. Is latest version is H-003 [2]. 1. Each satellite sends a unique but known signal which is received by the receiver. (Signals from all satellites arrive combined to the receiver, but can be separated using signal processing techniques to be discussed later.) 2. The parameters of orbits of all satellites (and thus their locations at any time) are known and transmitted in the message from each satellite. This data is known as ephemeris. The GPS receiver decodes the ephemeris to know which satellites are visible to it (that is, which are above the horizon, so that their signals are expected to reach the receiver when there are no obstructions). 3. There are GPS time timestamps periodically embedded in a message carried by the signal that is known as the navigation message. The GPS receiver uses these timestamps to internally generate the expected signal (unique for each satellite) at the expected time for each visible satellite. (Synchronization of the receiver to the globally maintained GPS time is a challenge that will be addressed later.) 4. There is a difference between the receiver-generated signal and the receiver- received signal, for each satellite, because of the time it takes the signal to arrive from the satellite to the receiver. The receiver can measure this time difference, Fig. 2 Approach to measuring the pseudorange to a GPS satellite

16 Z. Popovic and R. Miucic t, by delay-shifting the generated signal until it lines up in time with the received signal. 5. This time difference is converted to a distance (known as the pseudorange, ρ, because it is corrupted by errors) by multiplying the time difference with the speed of the signal, which is the speed of light, c. 6. The pseudorange to a satellite, the location of which is known, constrains the receiver location to a sphere. The intersection of such spheres based on signals from multiple satellites is the receiver location. This intersection can be found by solving a simultaneous set of equations, as discussed in Section “Calculation of Position and Time”. GPS Architecture The GPS system was developed and is maintained by the US Department of Defense. Its architecture was approved in 1973. The first satellite was launched in 1978, but it took years to get in orbit all 24 satellites required for the intended global coverage and to prove the system out through testing. The system was declared operational in 1995. The GPS system consists of three segments: the space segment, the control segment, and the user segment. The space segment nominally consists of 24 satellites orbiting Earth in Medium Earth Orbit at the height of about 21,000 km. The satellites are allocated across six orbital planes, each inclined at 55◦ to the Equator, with four satellites in a plane (Fig. 4). Each satellite (Fig. 3) is continually broadcasting a unique signal at known periodic times. The satellites are not stationary above a point on Earth but instead traverse a trajectory above ground that repeats about once every 12 h. However, due to the arrangement of all satellite orbits, the exact same arrangement of all satellites above a particular point on Earth repeats only about once every 24 h. That is, over each period of about 24 h, a user on Earth will be experiencing a constantly changing satellite coverage, even when completely at rest and without any sky obstructions. The constellation of 24 satellites is needed to provide the minimum designed global coverage where at least 6 satellites are visible from any unobstructed point on Earth at any time. Note that at any one place the number of visible satellites changes over times as satellites orbit the Earth (Fig. 5). The number of satellites in the constellation changes as old satellites are decommissioned and new added to replace them. In recent years usually, there have been more than 24, in order to improve the number of satellites visible from any one place and time and to provide for some robustness against temporary satellite outages. For example, there were 31 satellites in orbit in March of 2016. The control segment consists of monitor stations, the master control station (MCS), and ground antennas. The monitor stations consist of GPS receivers with atomic clocks, weather instruments, and communications equipment. They are unmanned, receive GPS signals, and send data to MCS (Figs. 6 and 7).

Positioning 17 Fig. 3 GPS satellite, an illustration in space and a close-up photograph on the ground Orbital z plane Equatorial plane y x Fig. 4 GPS orbital plane The MCS maintains GPS time that is used to synchronize time across the entire GPS system. It also monitors and predicts orbits. Based on the orbit predictions, it updates the messages from satellites containing the orbit parameters. Another key role of the MCS is to generate commands to satellites to perform corrective moves in order to stay in the desired orbit. The unmanned ground antennas upload to satellites the motion commands and the messages to be sent by the satellites.

18 Z. Popovic and R. Miucic 8 Visible Satellites 5 Visible Satellites Fig. 5 GPS constellation as seen from one place at two different times Fig. 6 GPS control segment ground stations

Positioning 19 Fig. 7 GPS monitoring station in Hawaii Fig. 8 An early GPS receiver on the back of a soldier The user segment consists of all devices capable of receiving the GPS signals and using them to determine position, velocity, and time (GPS receivers) (Figs. 8 and 9). Other GNSS Systems Besides GPS, there are other GNSS systems, which are currently either partially or fully operational. Nations develop their own systems in order to be able to control their location service in a time of war where other nations might deny the use of their systems. From the user point of view, having access to multiple systems provides benefits in terms of increased satellite visibility, which is particularly important in

20 Z. Popovic and R. Miucic Fig. 9 Modern GPS receiver obstructed sky conditions (such as in densely urban or mountainous areas) where only a small portion of the sky is open to allow signal reception. The downside is that multi-GNSS capability increases the complexity and cost of location device hardware and software. Here is a brief look at GNSS systems that are at least partially operational. GLONASS is the Russian system and is the only other system besides GPS that is currently fully operational. Its first satellite was launched in 1982. It had troubles obtaining funding in the 1990s leading to its constellation dropping to only 6 satellites in 2001, but it has recovered since and it had 29 satellites in orbit in 2016. GLONASS is commonly supported on scientific GPS receivers and becomes more so on automotive receivers as well, but it is not common on mobile phones. Galileo is the European system. It is the most recent fully global development that includes improved signal design based on what has been learned about GNSS technology from decades of GPS use. Its first satellite was launched in 2011 and it had 11 satellites in 2016. It will not be fully operational until 2019. BeiDou is the Chinese system. It was originally limited to regional use around China but it is planned to have a global reach from 2020. Its first satellite launch was in 2000 and it had 20 satellites in 2016. QZNSS is Japanese system that is designed for regional use. It can provide benefits in an area of Pacific ocean that includes Japan and spans down to Indonesia. Its first launch was in 2010 and it had one satellite in 2016.

Positioning 21 IRNSS or NAVIC is Indian regional satellite navigation system. It provides positioning services in the area that includes India, Indian Ocean, and South Asia. Its first launch was in 2013 and it had seven satellites in 2017. Performance The achievable GNSS accuracy is subject to a number of error sources but there are methods for constraining the errors. Section “GNSS Performance and High- Accuracy Methods” will address those topics after the immediately following Section “Basic GNSS Positioning in Cooperative Vehicles” with introduction to how basic GNSS position data is used in V2X. Further Resources For more in-depth coverage of the topics in Section “GNSS Principles”, and for other related topics, consult the excellent introductory but comprehensive texts [3, 4]. Basic GNSS Positioning in Cooperative Vehicles Accurate positioning is essential for proper functioning of V2V safety applications. Most V2V safety applications require relative lane-level positioning of the HV and RVs. For example, a safety application has to be able to determine if the Host Vehicle (HV) and a Remote Vehicle (RV) are in the same lane. V2X system includes GNSS receiver providing the system with its own position and accurate time. The onboard system retains path history and calculates path prediction. Each vehicle broadcasts BSMs containing motion data: time-stamped speed, acceleration, position, heading, path history and path prediction. Given HV and RV information, the system calculates range, the difference in heading, and the relative position between vehicles. The path history and path prediction are used to aid in lane level target classification of the remote vehicle. Industry consensus is that vehicle has to localize its self within a lane. Therefore, minimum performance requirement for vehicle positioning is 1.5 m in absolute terms [6]. The effectiveness of cooperative applications degrades gracefully when subject to reduced GNSS availability. Urban canyons, tunnels or dense foliage significantly reduce satellite signal quality. Positioning then can depend on dead reckoning using other vehicle sensors such as IMU, camera or odometer. The reference system is relatively immune to the sporadic outages (less than 1 s). Outages of less than 1 s in duration accounted for the majority (93%) observed during the 20,000 miles of data

22 Z. Popovic and R. Miucic Fig. 10 Overview of OBE DSRC GPS OBE functional blocks Antenna Antenna GPS Receiver Computing Unit To HMI DSRC Vehicle CAN Transceiver collected in the DOT-CAMP system performance testing [5]. Prolonged outages (2–5 s) typically result in degrading of the V2V functionality. Applications that require lane-level accuracy would be disabled (e.g. EEBL). However, applications needing road level (e.g. IMA) would still be operational. Road Side equipment (RSE) devices are sending differential corrections that will improve localization of the connected vehicles at the equipped intersections. According to SAE J2945/1 [31] V2X positioning subsystem shall use WAAS corrections when the WAAS signal is available; in order to improve the position accuracy. SAE J2945/1 standard also requires the position to be acquired 10 times a second. There are many national or state agencies providing correction data as well. For example, state of Michigan is running a network of Continuously Operating Reference Stations (CORS) and providing updates over the internet free of charge [7]. Positioning Device in Vehicle Architecture To describe the place of a positioning device in a typical vehicle connected architecture (probably needs to refer to “Vehicle Architecture” chapter). A typical implementation of the DSRC system in vehicles is enclosed within On Board Equipment OBE device [8, 9]. Figure 10 shows logical links between major functional components in an OBE. Computing Unit reads vehicle information data from the vehicle CAN bus. GPS receiver supplies current vehicle position information. From these two data sources Computing Unit composes and transmits messages via DSRC transceiver. At the same time, any computed collision warning is further passed to the HMI link. Positioning Provisions of Communication Protocol In the most typical configuration, a DSRC equipped vehicle will have one or two channel configuration setup. At least one channel will be tuned to Channel 172

Positioning 23 (CH172). CH172 will mainly be used for sending V2V messages (BSMs), SPaT and MAP, and security service messages. V2V traffic will occupy the majority of the channel load. There will be limited opportunity to exchange large content such as regional maps, with the exception of MAP messages. MAP message is transmitted from RSE. The MAP contains detailed lane and available approaches information of the intersection the RSE is placed to. The most common implementation of Traffic Sign Violation application is described in CICAS-V project [22]. A vehicle, using its ego position information, locates itself in a particular approach. The system then listens for a SPaT message that contains the state of the traffic light for that approach. If the system determines the speed is not adequate for the vehicle to safely stop at the red light, it will warn the driver of impending traffic light violation. Positioning Data Flow in a Connected Vehicle Most common wired communication links between GPS receiver and Computing Unit in a typical embedded solution include I2C, SPI, USB and UART [9, 12, 21]. Another important physical signal from GPS receiver is Pulse per Second (PPS). PPS signal is used for synchronizing OBEs between vehicles. To communicate actual positioning information GPS receiver is using NMEA messages. NMEA 0183 is a combined electrical and data specification for communication standards over a serial connection. Most useful NMEA messages for V2X/OBE are GPGGA and GPRMC [10]. Figure 11 shows a sample of NMEA stream with GPGGA and GPRMC messages highlighted. GGA message contains essential fix data which provide 3D location and accuracy data. The following NMEA string: “$GPGGA,171546.0,4228.594269,N,08306. 957771,W,1,09,0.7,186.1,M,-34.0,M,*6A” is dissected and explained in Table 1. RMC (Recommended Minimum C) message contains essential GPS (position, velocity, time) data. The following NMEA string: “$GPRMC,171546.0,A,4228.594269,N,08306. 957771,W,44.7,255.9,290315,0.0,E,A*29” is dissected and explained in Table 2. Fig. 11 A sample NMEA file

24 Z. Popovic and R. Miucic Table 1 GPGGA message $GPGGA – $ indicates start of the sentence. – GP indicates that fix came from a GPS device (other possible values are GA-Galileo, GL-Glonass, GN-combined GNSS systems) – GGA-global positioning system fix data 171546.0 Fix taken at 17:15:46 UTC 4228.594269,N Latitude 42 deg. 28.594269 N 08306.957771,W Longitude 83 deg. 06.957771 E 1 Fix quality: 0 = invalid 1 = GPS fix (SPS) 2 = DGPS fix 3 = PPS fix 4 = real time kinematic 5 = float RTK 6 = estimated (dead reckoning) 7 = manual input mode 8 = simulation mode 09 Number of satellites being tracked 0.7 Horizontal dilution of position 186.1,M Altitude, meters, above mean sea level 34.0,M Height of geoid (mean sea level) above WGS84 ellipsoid *6A The checksum data always begins with * Table 2 GPRMC message $GPRMC – $ indicates start of the sentence. – GP indicates that fix came from a GPS device (other possible values are 171546.0 GA-Galileo, GL-Glonass, GN-combined GNSS systems) A – RMC-Recommended Minimum sentence C 4228.594269,N 08306.957771,W Fix taken at 17:54:46 UTC 44.7 Status A = active or V = void 255.9 Latitude 42◦ 28.594269 N 290,315 Longitude 83◦ 6.957771 W 0.0,E A Speed over the ground in knots *29 Track angle in degrees true (course made good, true) Date—29th of March 2015 Magnetic variation Kind of fix the receiver currently has. The value can be A = autonomous, D = differential, E = estimated, N = not valid, S = simulator The checksum data always begins with * For a good overview of the NMEA 183 standard please see [10, 11]. As it can be seen from the above tables, GPGGA and GPRMC messages provide all essential positioning data: latitude, longitude, heading (Course Made Good), exact time (UTC), date, speed, and altitude. The information from the two messages is sync into OBE with help from PPS signal. Computing unit synchronizes internal clock every time PPS signal is received. Time information extracted from $GPRMC

Positioning 25 message, closest in time to received PPS signal, is used to update Computing Unit system clock. Positioning Data in DSRC Message Set In DSRC message set defined in SAE J2735 [31], the following data elements are directly read from GPS receiver: DE_Latitude, DE_Longitude, DE_Second, DE_Elevation, and DE_Heading. DF_PathHistory frame is derived from position information in the OBE. Some frames such as DF_PositionalAccuracy are either derived or read from the GNSS receiver. The OBE can be fully integrated in the vehicle or installed as Aftermarket Safety Device (ASD). In fully integrated solution OBE reads vehicle CAN data. In the case of ASD, the OBE does not have access to vehicle CAN. For ASD the following elements are derived from GNSS data: DE_Speed, DF_AccelerationSet4Way, DE_TransmissionState, and DF_BrakeSystemStatus. Fully integrated OBE extracts these elements from vehicle CAN. The quality of the data coming from the vehicle CAN bus are much more reliable and accurate than the ones derived in ASD. Path History Path history (PH) is a set of timestamped positional points (latitude, longitude, and heading) that subject vehicle traveled. PH data is used to reconstruct the remote vehicle trajectory. The number of path history points in a given BSM are limited by two conditions. First, the total distance of the PH data is limited to 300 m. Second, a number of path history points does not exceed 23. PH data in a BSM is condensed using concise representation algorithm. The goal of the algorithm is to produce a concise representation of the path history such that reconstructed trajectory does not exceed a given error threshold, typically 1 m. If a vehicle is traveling in a straight path, the past trajectory is concisely represented with two points: the current position and the position 300 meters behind, as shown in Fig. 12. If a vehicle is traveling in a curved path, there will be many more points representing traveled trajectory, as shown in Fig. 13. GNSS Performance and High-Accuracy Methods Concepts Representing Earth: Ellipsoid, Geoid, Terrain, and Heights In order to quantify a location on Earth, or near Earth, we need a mathematical model of Earth. This comes in the form of an ellipsoid, which is an ideal three- dimensional body defined from the swept volume of an ellipse rotated along its

26 Z. Popovic and R. Miucic Fig. 12 Concise representation of the PH points for straight line trajectory Fig. 13 Concise representation of the PH points for curved line trajectory longer axis. The ellipsoid is used instead of a sphere to better match Earth’s actual shape, which, on large scale, slightly deviates from a sphere due to the elongation at the Equator. Nearer the surface, at the scale of kilometers and meters, the real shape of the Earth is much more complex, with mountains and valleys that deviate from the geometric concept of the ellipsoid. However, the geometric concept is still useful to constrain the number of parameters required to define the gross shape of the Earth to two (major radius and flattening), while the complexity of real surface can be captured in the third parameter of the height of the terrain above the ellipsoid.

Positioning 27 There is no one obvious way to fit the ellipsoid to Earth, but one approach is to make it match as closely as possible. The geoid is the surface defined by points of gravitational potential equal to that of the mean sea level. On the sea, this surface coincides with the mean sea, and on land, it is a theoretical surface that would experience the gravitational potential of the mean sea level in a hypothetical canal. Since the density of Earth is not uniform, the geoid is not a uniform shape but itself has peaks and valleys. The motivation of using the geoid as the target for ellipsoid parameterization is that traditional instruments naturally provide measurements with respect to it: plumb lines point down perpendicular to the geoid surface, water levels itself parallel to it, and barometric altimeters report heights (which are orthometric heights) with respect to it (Fig. 14). The specific ellipsoid used as a reference for GPS coordinates is known as World Geodetic System 1984 (WGS 84) maintained by National Geospatial Intelligence Agency (NGA) and established for supporting the U.S. Department of Defense (DoD) in 1984 [13] and periodically updated and aligned with international systems. It is an Earth-centered, Earth-fixed reference system that defines the ellipsoid parameters and the geoid surface. This collection of parameters that define a reference frame is known as the datum. The latest versions of WGS84, the one that is currently used by the GPS system, is WGS84 (G1674) [14]. Its key parameters are shown in Table 3 [13]. Fig. 14 Ellipsoid, geoid, ε Deflection of the vertical terrain, and heights Ellipsoidal height Table 3 WGS84 (G1674) parameters [13] Terrain H Orthometric height Geoid h N Geoidal height Ellipsoid Parameter Symbol Value a 6378137.0 m Semi-major 1/f 298.257223563 axis GM 3986004.418 × 108 m3/s2 Flattening factor of the ω 7292115 × 10−11 rad/s earth Geocentric gravitational constant Angular velocity of earth

28 Z. Popovic and R. Miucic Latitude, Longitude, Ellipsoidal Height The essential output of a GNSS-based device is the global location, which is typically expressed as a triple of values: latitude, longitude, and height. Latitude (φ in Fig. 15) is the angle between equatorial plane (x-y) and the normal to the ellipsoid that passes through the location point (P). Longitude (λ in Fig. 15) is the angle between the reference meridian plane (passing through Greenwich near London, UK) and the meridian plane of position P. Height (h in Fig. 15) typically reported by GPS receivers is the height above ellipsoid, that is, the distance from the location P to the ellipsoid surface along the normal to the ellipsoid. Different Datums Before GPS, representing locations as coordinates, and producing the resulting maps, were often limited to a region of the world, such as a country or a continent. As such, the optimal datums (the reference frames in terms of calculated geoids and the chosen ellipsoids) were derived and optimized locally and thus can differ from region to region. This demands caution as different datums gives different meanings to latitude, longitude, and height (Fig. 16). For example, most maps in the US are based on North American Datum of 1983 (NAD 83), which is slightly (a meter or two, depending on location and time) different from GPS’s WGS 84 (the latest version of which is G1674 [14]). There are equations and software applications for converting between the two systems, but they are complicated by the need to account for time of the location measurement. This is because NAD 83 is defined based on reference points on the surface of the North American continent while WGS 84 is Reference z (x, y, z) meridian Height Latitude Longitude x y Fig. 15 Latitude, longitude, and height

Positioning 29 Regional Reference ellipsoid point Geocentric ellipsoid Geoid Fig. 16 Differences in latitude due to differences in ellipsoids defined using global averaging. Since the North American continent is moving with respect to other continents (and some parts of it faster than others), then there is a difference between NAD 83 and WGS 84 that changes over time (and in some locations more than in others). Note that for most practical purposes, including the accuracies relevant to cooperative vehicles, WGS84 (G1674) frame is the same as International Terrestrial Reference Frame of year 2008 (ITRF2008). This can be useful as coordinates of base stations used in higher accuracy methods discussed later may be expressed in ITRF2008. Map Projections The spherical coordinates of latitude and longitude allow succinctly and accurately specifying a location on the ellipsoidal shape of the Earth (with heights used to account for real surface irregularities), but often it is more convenient to use flat two-dimensional representations, such as those of maps on paper or screen. In that case, the points on the ellipsoid of the Earth, defined using the spherical coordinates (typically in units of degrees), need to be flattened into a two-dimensional rectilinear Cartesian coordinates (typically in units of meters). There are a number different ways of projecting points from a sphere (or ellipsoid) onto a plane, but each necessarily introduces some kind of distortion of the spatial relationship of points on the original curved surface. The most widely used projection is Universal Transverse Mercator (UTM) [15–17], which, like the Mercator projection it is based on, projects the points on the Earth onto a hypothetical Earth-enveloping cylinder, which is then conceptually unfolded into a two-dimensional plane, see Fig. 17. The advantage of the Mercator projection is that, within a few degrees from the parallel or meridian that is tangent to the cylinder, it keeps the directions, distances

30 Z. Popovic and R. Miucic Fig. 17 UTM cylinder and areas accurate. Normal Mercator’s cylinder is tangent to the equator, while Transverse Mercator (TM) is tangent to a selected meridian, known as the central meridian. To maintain the representational accuracy, UTM divides the Earth into 60 bands of 6◦ of longitude each, where each band (zone) is a separate TM projection around a different central meridian. UTM is accurate to better then 0.04% of distance error within the zone, but the conversion from spherical to UTM coordinates does require extensive computations. For more efficient computer implementation in applications that only deal with maps of local areas of about 1 km2 of less, a simple projection onto a tangent plane can give accuracies in the order of centimeters. Regardless of what projection is used to create a planner map, it is important to keep in mind that the projection method matters in interpreting what the map coordinates mean and that it should be considered as a source of error. Time Since user position and velocity estimates depend on accurate knowledge of synchronized time, and since there are various common notions of time, it is worth discussing how time is defined for GPS. It helps that understanding, and is curious to know, how historically that definition was approached. Note also that globally synchronized, nanosecond-accurate time is a valuable output of a GPS receiver in its own right for various important applications ranging from scientific to financial. A simple and ancient reference for time measurement is the solar day—the time it takes Earth to rotate around itself, seen as the time between the moments at which the Sun repeats its highest point in the sky. Our notions of hour, minute, and second derive from the division of solar day. The problem with using the solar day as the source of time unit definitions is that it varies by about 16 min due to Earth’s tilted axis of rotation and the shape of the Earth orbit around Sun. Still, it stayed in use as the official time interval reference until 1960, through the definition of 1 s as the mean solar day divided by 86,400 (the number of seconds in a day). Since solar day is variable, in search of a constant definition of time, a particular solar year was chosen by convention, that of 1900, to derive 1 s as 1/31556925.9747 of that solar year.

Positioning 31 Fig. 18 Leap second insertion Not only is duration of a day variable, but a day in one part of the globe is night in another. In order to have one common reference time, one reference location was selected by convention: the location of the Greenwich observatory in the United Kingdom. The mean solar time at that location is known as GMT. Duration of a solar day varies due to polar axis motion and variations in Earth’s spin rate. It is overall slowing down by about 1 s a year. Applying corrections for polar motion (but not spin rate) results in time scale known as UT1 (where UT0 = GMT). Starting in 1967, a very stable and precise reference to a property of an atom has become the definition of 1 s: 9,192,631,770 periods of the radiation corresponding to the transition between two hyperfine levels of the ground state of the cesium-133 atom. This time scale is known as International Atomic Time (TAI, for its French acronym). It is not affected by variations in Earth’s orbit, however, it slowly diverges from natural cycles of solar days and years, so that over 4000 years, it accumulates 12 h of delay: In that future, TAI noon in Greenwich will be solar midnight, thus actual night. To deal with this downside, yet another time scale was invented: Coordinated Universal Time (UTC). This is continually updated from TAI time by inserting seconds to slow it down to remain close to the more-natural UT1. These inserted seconds are known as leap seconds [19]. They are added at a decision of a committee that tries to keep UTC close to UT1. The insertions have been happening recently every 1 or 2 years. The last leap second insertion occurred on December 31, 2016 and the current difference is TAI − UTC = 37 s [18–19]. A leap second is inserted at midnight of the last day of the chosen year as the 60th second (normally second count rolls over from 59 to 0) (Fig. 18). So leap seconds prevent UTC noon hour occurring in the middle of a night in the far future, but they are messy because they introduce a discontinuity in UTC time every couple of years (at leap second insertion) and require keeping track of leap seconds difference accumulated between TAI and UTC times. As a curiosity, note that it takes a month to calculate UTC in a laboratory near Paris from about 250 atomic clocks around the world. Each country has its own estimates of UTC. In the US, there are two versions: one done by the US Naval Observatory UTC (UNSO) and another by the National Institutes of Standard and Technology UTC (NIST). UTC time is the primary time standard of the world. Finally we arrive at the definition of GPS time (GPST). GPST is effectively UTC time derived by combining data from atomic clocks on GPS satellites and at GPS monitoring stations, but without use of leap seconds. Since GPST does not use leap seconds but UTC does, over time the difference between them grows as

32 Z. Popovic and R. Miucic leap seconds are added to UTC. Currently, GPST − UTC = 18. Being aware of that difference, and keep track of how it changes over time, is important in avoiding mistakes in converting between GPS time (given by the GPS devices) and UTC time (the universal civil time standard). Since at the time GPST was established from UTC the difference between TAI and UTC was 19 s, and the GPST does not get leap seconds added, the difference TAI − GPS remains constant at 19 s. GPS time is often expressed in GPS data messages as “Seconds into Week” since Sunday along with a “Week Number”, where the week count started at 1 on January 7, 1980 and rolls over at 1024. This allows representing time as smaller float values which are convenient for storage, operations, and plotting, as opposed to dealing with cumbersome calendar representations or an always growing accumulation. Signals Each GNSS system has a different set of signals which are sent from the satellites and processed by a GNSS receiver to extract the position, velocity, and time information. However, most of them employ the same operational principles and can be described using the same parameters. In this and the coming sections the details of GPS system signals, which employ Code Division Multiple Access (CDMA) modulation technique, are used as an example to illustrate the operation of other GNSS systems. The Galileo system, which also uses CDMA, differs mainly in frequencies used. GLONASS is the only GNSS system that is funda- mentally different because it uses Frequency Division Multiple Access (FDMA) modulation. Each satellite in the GPS system transmits signals on either two radio frequencies (older satellites, before IIF and IIR-M satellite generations) or three (with newer satellites), known as L1 (at about 1.6 GHz), L2 ( 1.2 GHz), and L5 ( 1.1 GHz). There are two signals on L1: one civilian (known as “C/A”, from “course/acquisition”) and one military (known as “P(Y)”, where “P” is from “precision” and “Y” signifies that encryption is used). There is one military signal on L2, and one civilian signal on L5. Each signal is a combination of three components: a simple sinusoid carrier signal, a unique pulsetrain called “code”, and also a slower pulsetrain of navigation data (Fig. 19). The carrier component is a simple sinusoid with the period determined by the radio channel frequency: L1 signal at 1575.42 MHz frequency (63.5 ns period), L2 signals at 1227.60 MHz (81.5 ns), and L5 at 1176.45 MHz (85.0 ns). The code is a binary pulsetrain that is composed of a sequence of 0 and 1 values represented as low and high voltage levels. Each satellites transmits unique known codes (the C/A code in the civil L1 signal, and P(Y) code in the military signals on both L1 and L2), so that deciphering the code reveals the sending satellite’s identity. The C/A code is 1023 values long (each value duration known as a “chip”), sent at the rate of 1023 chips per second (1.023 Mcps), with each value lasting about 1 μs. Thus the equivalent distance covered at light speed by chip duration is about

Positioning 33 Carrier at L1/L2 19 cm (L1) Code at 1.023 Mcps (C/A) 10.23 Mcps (P(Y)) 300 m (CA) Navigation Data at 50 bps 6000 km Fig. 19 Components of a GPS signal: carrier (top), code (middle), navigation data (bottom) 300 m and the C/A code repeats about once every millisecond. The P(Y) code is in comparison much longer at about 1014 chips, sent 10 times faster at 10.23 Mcps, is about 100 ns (30 m) wide, and repeats after 1 week. The shorter P(Y) allows greater positioning precision, but it cannot be directly used for civilian purposes due to its military encryption. The code (both C/A and P(Y)) is generated in such a way that, although it is predetermined, constant, and known, it appears as random (to a human eye, but more importantly, also to signal processing techniques that apply to random signals). This is why the code is known as pseudo-random noise (PRN) code. One useful property of such codes is that they don’t interfere with each other: All satellites can transmit their different unique PRN code simultaneously without preventing receiver’s ability to separate them all out. The length and rate of the code determine its robustness to noise and interference (to be revisited in a later section). Another benefit of using PRN codes is that they spread the signal energy over a wider frequency band centered at the signal normal frequency thus making their power undetectable in normally present background radio noise unless the code (which could be kept secret) is applied to re-focus the signal power. This is why they are known as direct sequence spread spectrum signals. Most importantly, PRN code’s autocorrelation function (the result of multiplying variously shifted code copies) is nearly zero for all shifts except the zero (exact alignment) shift, which, as will

34 Z. Popovic and R. Miucic Fig. 20 GPS signal after combining code and navigation data with the carrier be described later, is essential in being able to measure signal travel time and thus distance to satellite and user position. It is interesting to note that satellite antenna power is only 50 W, which is less than that of a microwave. By the time the signal travels 26,000 km to reach a receiver, the signal power is down to 10–16 W, but the autocorrelation properties of the PRN code allow them to be extracted below the radio noise floor. The navigation data is a binary code message that carries information necessary for the use of the signals for navigation (although it is not sufficient itself for positioning; analysis of signal travel times is also required): timestamps, satellite status, ephemeris (satellite position and velocity), clock bias parameters, and almanac (approximate orbit data for all satellites). The data is transmitted at relative slow rate of 50 bps (20 ms per bit) and takes about 12.5 min to transmit. Due to low GPS signal power, faster rates would result in more bit errors on demodulation in a receiver. For each signal, in the process of combining the three signal components, the code and navigation binary data are first combined by modulo-2 addition, which has the same effect as exclusive-or logical operation. That is, when both signals getting combined are carrying the same value (both are 0 or both are 1), then the result is 0; when they are carrying different values (one is 0 and the other 1, or vice-versa), then the result is 1. The resulting composite signal, which is still binary, is then combined with the carrier sinusoid using binary phase shift keying (BPSK) modulation, where 0 in the composite has no effect on the carrier but 1 in the binary signal shifts carrier phase by 180◦. This shift can be imagined as causing a rising sinusoid to start falling and causing a falling sinusoid to start rising. The overall combination of the three signals then produces a waveform such as in Fig. 20, where each 0-1 and 1-0 transition in the composite binary signal appears as a glitch in the carrier sinusoid. Recall that on L1 frequency, two different signals are sent simultaneously: C/A and P(Y), each with its own combination of three components described. They are prevented from interfering from each other on the receiving side by sending the P(Y) carrier phase-delayed by 90◦ to the C/A carrier. The phase-delayed carrier component of a signal is known as the quadrature carrier component. Code Measurement Code measurement refers to measuring the travel time of a particular satellite’s PRN code by detecting how much it is shifted from the same code that was generated on

Positioning 35 t1 Satellite generated t2 Code phase generated by satellite at t1 arrives Δt seconds later code Δt Code arriving t1 from satellite Receivers generated replica code Receivers generated replica code shifted Δt seconds t2 A2 R(τ ) -Tc 0 Tc τ Fig. 21 Code measurement the receiver at the time when the satellite-generated code was expected to have been sent by the satellite (Fig. 21). Then this delay time is converted to distance to the satellite by multiplying it by the speed of light. Using multiple such distances allows trilaterating user’s position estimate. More specifically, the receiver starts the PRN sequence generation for a particular satellite at the time at which the satellite is expected to have started it and then passes this generated signal (for a particular satellite, frequency, and code type) together with the actually received signal (for a particular frequency, but all of its components from all satellites still combined) through a correlator. The correlator is either an electronic component (traditionally) or a software component (in some recent devices) that derives the similarity metric between two signals by multiplying their amplitudes. Due to the delay of the received signal compared to the generated signal (keep in mind low autocorrelation of PRN codes) the correlator output will be near zero. However, the receiver continually increases the delay in its signal generation and when the delay is sufficient for the generated and received signals to start lining up, the correlator output starts increasing. The correlator output is at its maximum when the two signals line up and then any further generation delay starts

36 Z. Popovic and R. Miucic reducing the output. Thus the generation delay used to produce the correlator peak is the code (delay) measurement. Carrier Phase Measurement The GPS system was originally envisioned to provide all of its functionality based on the code measurement just described. However, since the frequency of the carrier phase (and thus the corresponding position resolution) is much higher (and thus better) than that of the C/A code (the only code available to civilians), enterprising engineers have developed an originally unintended way of deriving measurements from GPS signals by taking advantage of the higher carrier frequency through what is known as the carrier phase measurement. The carrier phase measurement is the measurement of the carrier signal delay due to travel from the satellite to the receiver, in terms of carrier signal phase shift expressed as the number of carrier’s sinusoid cycles (Fig. 22). In order to isolate the carrier signal component (a sinusoid), the PRN code tracked through code measurement is first removed. Then a carrier component is generated by the receiver, which is varied in both frequency and phase, until its correlation with the received signal peaks, as part of the process (and usually hardware) that is known as the phase lock loop. The phase offset from the nominal timing is then the carrier phase measurement (as a fraction of a sinusoid cycle). In addition to phase, the frequency must be varied because it changes in travel due to the Doppler effect. Integrating the change in carrier phase measurement over time (with increases and decreases in phase as a result of satellite and receiver motion) gives what is known as Doppler count (or delta pseudorange). The frequency used to achieve the correlation peak is then, except for ionospheric effects, a measure of Doppler shift. Since the Doppler shift is directly related to velocity (as discussed earlier), it can be used to estimate receiver velocity. Unlike a measurement based on code, where the code sequence has a well- defined start rooted in absolute time, a carrier phase measurement, as Fig. 22 shows, only provides the fractional offset between any two carrier peaks (of generated and received signals) and is thus ambiguous in the number of whole cycles that the signal was delayed in its travel, and thus alone is not sufficient for solving the absolute position, velocity, or time. However, tracking phase measurement changes over time allows more precise relative motion tracking, which then provides more precise velocity estimation, also allows smoothing of code-derived positions, and in combination with data from another receiver with a known location, as will be described later, can be used for more precise absolute location. Calculation of Position and Time As revealed as far, the distance from a GPS receiver to a satellite is estimated (with the estimate known as pseudorange) based on the time it takes for the GPS signal

Positioning 37 transit time phase measurement 1 0.5 amplitude 0 -0.5 -1 -1.5 12345678 0 receiver generated carrier carrier received from satellite at t1 1 carrier received from satellite at t2 carrier phase change in Δt 0.5 amplitude 0 -0.5 -1 -1.5 012345678 cycle Fig. 22 Carrier phase measurements illustration to arrive from the satellite to the receiver. This time is converted to distance by multiplying it by the signal speed, which is the speed of light. So it is clear that time plays a crucial role in this estimate and thus any difference in clocks used by the satellite and the receiver appears directly as pseudorange error. Since pseudoranges to multiple satellites are used to estimate the receiver position, those time errors also appear as receiver position errors. Although the satellite clock drift is minimized by satellites’ use of highly accurate atomic clocks, and although the satellite clock drift is tracked and modeled by the GPS ground-based control station with the model parameters sent in the GPS navigation message, the same cannot be done for the receiver clock. In order to account for this, time bias of the receiver with respect to common GPS time is treated as an unknown and estimated using pseudoranges. This means that in the GPS positioning problem there are four unknowns: three position coordinates and time. The expression for each pseudorange (Eq 2) involves those four unknowns and thus at least four pseudoranges are needed to simultaneously estimate the receiver position and its time bias.

38 Z. Popovic and R. Miucic ρ(k) = x(k) − x 2 + y(k) − y 2 + z(k) − z 2 + b + ε(k) (2) Eq. (2): Pseudorange for one satellite k, where (x, y, z)k is the known satellite location, (x, y, z) is the receiver unknown location, b is unknown clock bias, and ε is unmodeled errors. Having more than four pseudorange measurements, and the corresponding equations, allows improving the accuracy of the position and time solution by solving for the solution that minimizes the discrepancy across all equations using a technique such as weighted least squares with Taylor series linearization [20]. Starting from a prior good solution and making assumptions about clock drift and the constraints of receiver motion can be used to continue producing useful but degraded estimates for a brief time even when only 2 pseudoranges are available of sufficient geometric diversity. Note that before use in estimation, pseudoranges are adjusted for modeled errors in their measurement although significant unmodeled errors can still remain (to be discussed later). Ways of calculating velocity are discussed next. Doppler Effect and Velocity Calculation The Doppler effect (also called Doppler shift) is the difference between the frequency of a waveform (including wireless signals such as a those of GPS) as generated by the source and as measured at the receiver, due to the relative motion, along the line of sight to sender, between the source and the receiver. The trends are (Fig. 23): When the source is approaching, the received frequency is higher than sent (Doppler shift is positive) and when the source is going away, it is lower (Doppler shift is negative). At the point of transition from approaching to receding (which is the closest point of the relative trajectory, at which the relative line-of-sight speed is zero), the sent and received frequencies are equal and the shift is zero. For an intuitive explanation of how this happens, think of a wave on a string with its ends held by two people: One person (the sender) generates the wave by up-and-down hand motion of constant frequency while the other person (the receiver) feels the pulses. As the sender starts walking towards the receiver, without changing the frequency of string’s up-down motion, the sender will be compressing the distance between the wave crests, and since the waves are still going at the same speed, increase the frequency at which they arrive to sender’s hands. The opposite is true when the distance between the sender and receiver is increasing: as the distances between crests increase, for a given wave speed, the received frequency decreases. When the relative motion between the receiver and sender stops, the received frequency is the same as sent. Since the Doppler shift is related to velocity between the sender and the receiver, when the sending and receiving frequencies, the direction of the line of sight between the sender and receiver, and the sender velocity are known, then the receiver

Positioning 39 Same wavelength (no Doppler effect) Increased Traveling Decreased wavelength source wavelength t-3 t-2 t-1 t Fig. 23 The Doppler effect velocity can be calculated. The expression that relates them, in the case of the sender being a satellite and a receiver being a GPS user’s GPS receiver, is: fRj = fTj 1 − vj − u · aj c where fRj = received frequency from satellite j fTj = transmitted frequency by satellite j vj = velocity of satellite j u = user velocity aj = unit vector along the line of sight from satellite j to user c = speed of light Except for the user velocity, all of the other variables are known: the received frequency is measured by the receiver, the transmitted frequency is known and corrections for it are sent by the satellite in its navigation message, satellite velocity can be determined from orbital parameters sent by the satellite in its navigation message, the unit vector can be determined from earlier estimated receiver position

40 Z. Popovic and R. Miucic and knowing the satellite location from orbital parameters sent by the satellite in its navigation message. The above-described Doppler effect equation is one of the ways that receivers calculate their velocity. For receivers that track measure carrier phase changes over time, that is another way. Differentiating position estimates can also provide velocity, but that is less desirable because other approaches are more accurate and based on independent measurements (Doppler or carrier phase vs. pseudorange). Errors This section introduces various sources of error in GNSS measurements. The effectiveness of methods for error reduction will be noted, but the techniques themselves will only be explained later. Satellite Clock As demonstrated earlier, the estimate of position and velocity using GPS are based on converting the GPS signal’s duration of travel into distance, and thus any misalignment between receiver clock and the synchronizing GPS time translates directly into positioning errors. Recall that 1 ns of time is 0.3 m of distance at speed of light. There is typically 1.5 m of error in range to one satellite as a result of time errors. To minimize the errors in normal GPS receiver operation, the offset between the receiver clock and GPS time is solved (estimated) as an unknown in positioning equations. Also, the offset between the satellite clock and the GPS time is estimated using equations whose parameters are calculated and sent periodically from ground control stations to satellites, and then from the satellites to the receiver. Satellite Orbit Satellite locations are assumed to be known in positioning equations because they are obtained from satellite orbit equations. The parameters needed for the equations (known as the “ephemeris”) are calculated and sent periodically from ground control stations to satellites and then from there to the receiver. The difference between actual and predicted orbits, due to fidelity of equations and latency of parameter applicability, becomes range error when projected onto line of sight to the receiver. Typical contribution of satellite orbit error to the satellite range estimate error is about 1.5 m (RMS).

Positioning 41 Ionospheric Delay Ionoshpere is an atmosphere layer of ionized gases (gases that contain charged particles) that extends from 50 to 1000 km above ground. Ionization is caused by sun’s radiation. The radiation is an order of magnitude more at middle of day then near the end of night. Occasional phenomena on the sun that cause radiation bursts, such as solar flares, can cause extreme spikes in ionization, and in the corresponding estimation errors. In general, ionospheric activity can vary widely over globe and day-to-day. The effect of ionization is dispersive, that is, its effect depends on signal frequency. The error is related to the refraction of GPS signals as they pass through the ionosphere. The refraction bends the signals. The resulting curved signal path is longer than the normal direct path and so the signals take longer to arrive to the receiver. This is known as ionospheric delay. Then the approach of converting the transit time to signal distance travelled provides a distance that is longer than the true straight-line distance to a satellite that is used in estimation equations. Typical range error contribution magnitude (in RMS sense for a single satellite), without any countermeasures, is about 2–10 m, and even more for satellites appearing low in the sky (which travel through more ionoshpere). Apply theoretical models of ionospheric effects, using only L1 measurements, can reduce this error to 1–5 m. Since ionospheric delay is relatable to signal frequency, using measurements from multiple signal frequencies, for example L1 and L2, allows more accurate modelling of the ionospheric delay. This can reduce the ionospheric error to about 1 m. With differential corrections, ionospheric errors can be reduced further. With a base station 25 km away, the error comes down to about 0.1–0.2 m. Tropospheric Delay Troposphere is an atmosphere layer of dry gases and water vapor that extends from 0 to 50 km above ground. Just like in the case of ionosphere, passing through troposphere causes refraction of GPS signals and through the same mechanism causes ranging errors. Unlike in the case of ionosphere, the effect of troposphere is non-dispersive—it does not depend on signal frequency. The effect can still be model well for reducing the corresponding errors. Typical range contribution error (RMS) without modeling is 2.3–2.5 m (even more for low satellites), but modelling, which is performed by modern receivers, reduces this to 0.1–1 m. Applying differentials techniques, with a base station 10 km away, can reduce this to about 0.2 m plus any altitude effects. Multipath GPS signals reflect off obstructions such as buildings. The reflected signals are longer-path (delayed) and weaker than the direct signal. GPS receiver can happen

42 Z. Popovic and R. Miucic to receive both the direct line-of-sight (LOS) signal and the reflections, or just one or the other. When the LOS signal is still present and the delayed multipath signals are weak with large delays, receiver can identify and ignore them. When both are present, but not separable, multipath contributes to shift the LOS signal (the true signal) sometimes producing only small errors. When multipath is the only signal received from a satellite, then resulting errors are large. The multipath-caused transit delay translates into range error through speed of light, similar to atmospheric effects. Typical errors in benign (low multipath) conditions are 0.5–1 m. In urban canyons, where tall building cause long reflections, 10s or even 100s of meters of error can happen. Differential correction cannot be used to reduce multipath errors because multi- path is an entirely local effect (different for each receiver position and orientation) while differential corrections rely on common errors between multiple receivers, which are usually separated by kilometers or more. However, employing carrier phase measurements can reduce multipath error by two orders of magnitude in good conditions. Receiver and antenna hardware design are important for multipath mitigation. Receiver Noise There are errors that are collectively known as random measurement noise are mainly due to electrical noise from antenna, amplifiers, cables, and receiver electronics. This also includes interference between GPS signals and other signals in the frequency band, as well as signal quantization effects. Receiver noise error increase with lower signal strength which happens at lower satellite elevation angles. Typical error contributions are 0.2–0.5 m. Similar to multipath errors, since receiver noise errors are specific to each particular receiver, differential correction cannot help. Employing carrier phase measurements can reduce receiver noise effects by three orders of magnitude in good conditions, down to 0.01 m. Error Corrections Through High Accuracy Methods Some common GPS errors can be greatly reduced using one of a number approaches collectively loosely referred to as differential GPS. They all have in common employing GPS data from one or more base stations (which are basically static GPS receivers) to construct data that is sent to the user’s receiver to reduce receiver errors. The errors that can be reduced this way, to a varying degree, are clock, orbit, ionospheric, and tropospheric errors. Errors due to multipath and receiver noise cannot be helped with differential corrections. Receiver and antenna design are important for reducing multipath and

Positioning 43 noise errors. Multipath can be reduced through correlator design and use of newer signals with faster chipping rates. The following sections describe the key specific variants of differential correc- tions methods. Differential GPS (DGPS) In the narrow sense of “differential GPS” (DGPS), it is the simplest subset of the specific differential approaches. In that subset of approaches, there is a base station, consisting of a GPS receiver at a known location, which calculates the GPS errors at its location as the difference between its ranges to each satellite calculated based on its already-known static location, and those ranges calculated using just the GPS data received from the satellites. The base station location is known prior to its operation either from long-term (24 h or more) averaging of its GPS data, or using traditional geodetic surveys based on distance measurements to geodetic landmarks. The range errors calculated for the base station are broadcasts to other GPS receivers in the vicinity via radio, cell, or internet to be used as corrections by subtracting them from ranges to satellites measured by the receiver. The corrections are effective as long as the errors are common to the base station and the receivers that use them, which is typically the case for short distances to the base stations (known as baselines). In Local Area DGPS, a user’s GPS receiver gets correction data from one base station that is less than about 25–100 km away, typically the closest base station to the receiver. In Wide Area DGPS, there is a regional network of base stations (or even continent-wide network), with errors applicable to a region calculated by interpolat- ing between errors calculated at individual base stations in that region. A Satellites-Based Augmentation System (SBAS) is a GPS corrections system where corrections resulting from a wide area DGPS network, with continental or global coverage, are broadcast over communication satellites for a wider reach. The American SBAS system is known as WAAS (Wide Area Augmentation System) while the European system is EGNOS (European Geostationary Navigation Overlay Service) and Japanese is QZNSS (Quasi-Zenith Satellite System). WAAS, which is freely and generally available, reduces errors by about 0.5 m and can provide sub- meter accuracy in scientific-grade receivers. Real-Time Kinematic (RTK) GPS Real-Time Kinematic (RTK) GPS, is a differential GPS approach where both the base station and the user receiver measure pseudoranges and carrier phase, the base stations communicates its measurements with the user receiver, and the receiver performs differencing of base station and user receiver measurements to eliminate the errors common between the two.

44 Z. Popovic and R. Miucic RTK is distinguished from the previously described DGPS approaches by the use of carrier phase measurements in differencing. Error varies with baseline with 1 ppm error, until the base station is so far away that the full solution cannot be achieved anymore, which happens under 100 km. Correspondingly, when baseline is under 10–20 km, the error is at cm level. For baselines under 100 km, the error is at dm level. Interpolation between base stations (known as Network RTK) allows dm level performance with sparser base stations. The RTK approach with short baselines provides best achievable performance from GPS technology, down to 1 cm with good conditions and scientific-grade equipment. It is used as reference (ground-truth) in testing of other positioning technologies. The naming Real-Time Kinematic is somewhat a misnomer because sometimes the same approach is applied in post-processing (thus not in real-time), and it also applies to receivers that are not moving (so not kinematic), but the name stems from history where it was the first approach of its kind to allow carrier phase integer ambiguity resolution for moving platforms in real time. Precise Point Positioning (PPP) Precise Point Positioning (PPP) relies on network of GPS satellite monitoring stations (typically run by a commercial entity, not a government) that calculate improved satellite clock and orbit parameters. These parameters are transmitted to receivers over communication satellites or cellular or internet connections. PPP sometimes involves RTK-like use of carrier phase and differencing over time. Currently implementation suffer from long ( 10 min) solution convergence time when only L1 frequency is used. Accuracy is typically much better than SBAS but not quite as good as RTK and in the order of several decimeters. So PPP has the disadvantage of poorer accuracy but its advantage is that it can be achieved with a relatively sparse network of base stations: for PPP, an entire continent can be covered with several hundred base stations while RTK requires a base station every 20–100 km. Performance Comparison Table 4 summarizes error sources and methods for reducing errors. Further Resources For more in-depth coverage of the topics in Section “GNSS Performance and High- Accuracy Methods”, and for other related topics, consult the excellent introductory but comprehensive texts [3, 4].