T
`
`'"T‘LL'GW Vehicle Locatiog
`TRANSPORTATION
`and Navigatioxif
`SYSTEMS
`3 Systems
`
`
`
`Yilin Zhao
`
`|PR2020-01192
`Apple EX1032 Page 1
`
`IPR2020-01192
`Apple EX1032 Page 1
`
`

`

`VEHICLE LOCATION
`
`AND NAVIGATION SYSTEMS
`
`Yilin Zhao
`
`Artech House, Inc.
`Boston 0 London
`
`|PR2020-01 192
`Apple EX1032 Page 2
`
`IPR2020-01192
`Apple EX1032 Page 2
`
`

`

`taloging-in-I’ublication Data
`tion and navigation systems Nilin Zhao.
`Zhao. Y1 :n-
`-
`es and index.
`P'
`cm.
`ra hicalrefcrenc
`‘
`(alk. paper)
`IBCIUdes blbhog P
`1. Intelligent Vehicle l-lighway Systems.
`2. MOtOf “melts—Autumatic [Dear
`systems.
`3 Electronics in navigation.
`Inn
`1. Title.
`"Tl-3223.32“
`1997
`629.2’7——dc21
`
`97-4200
`
`CIP
`
`British Library Cataloguing in Publication Data
`Zhao, Yilin
`_
`.
`Vehicle location and nanganon systems
`1. Intelligent Vehicle Highway Systems
`I. Title
`625.794
`
`2. Motor vchides—Automatic:19mm0n
`
`”Slam5
`
`ISBN 0-89006-861-5
`
`Cover design by Jennifer Makower
`
`O 1997 ARTECH HOUSE, INC.
`685 Canton Street
`Norwood, MA 02062
`
`‘
`All rights reserved. Printed and bound in the United States of A
`'
`mertca. No
`'
`.
`.
`may be reprodneed or utilized in any form or by any means. electronic or mgitrain'iigitiuisnmk
`mg photocopying, recording, or by any information storage and retrieval system ,withiiui
`permission in writing from the publisher.
`All terms mentloned In this book that are known to be trademarks or service marks have
`3:11 aggrépgiagg :fliltalijzedl.‘Alitech House cannot attest to the accuracy of this informa-
`mark of “Nice mark,
`15 oo 5 ould not be regarded as affecting the validity of any trade-
`
`International Standard Book Nu
`‘
`mber: 0-89006-86 -
`Library of Congress Catalog Card Number: 97-42305
`
`109376543
`
`
`
`IPR2020-01 192
`Apple EX1032 Page 3
`
`IPR2020-01192
`Apple EX1032 Page 3
`
`

`

`TV,
`
`CONTENTS
`
`Preface
`
`Acknowledgments
`
`Introduction
`Chapter 1
`Brief History
`1.1
`1.2 Modern Vehicle Location and Navigation
`References
`
`Part I Basic Modules
`
`Chapter 2 Digital Map Database Module
`2.1
`Introduction
`2.2
`Basic Representations
`2.3
`Reference Coordinate Systems
`2.4
`Standards
`2.4.1
`Geographic Data Files
`2.4.2 Digital Road Map Association
`2.4.3
`Spatial Data Transfer Standard
`2.4.4
`Truth-in-Labeling Standard
`Proprietary Digital Map Databases
`2.5.1
`Etak
`2.5.2 Navigation Technologies
`
`2.5
`
`m'i
`
`xiii
`
`xvi i
`
`12
`
`15
`
`17
`
`17
`
`18
`20
`
`28
`
`28
`30
`
`31
`
`32
`33
`33
`35
`
`|PR2020-01192
`Apple EX1032 Page 4
`
`IPR2020-01192
`Apple EX1032 Page 4
`
`

`

`viii VEHICLE LOCATI
`
`ON AND NAVIGATION SYSTEMS
`
`2.6 Digital Map Compilation
`2.6.1 Data Structures
`2.6.2
`Compiler Structure
`2.6.3 Hierarchical Maps
`References
`
`Chapter 3
`3.1
`3.2
`3.3
`
`Positioning Module
`Introduction
`Dead Reckoning
`Relative Sensors
`3.3.1
`Transmission Pickups
`3.3.2 Wheel Sensors
`3.3.3 Gyroscopes
`3.4 Absolute Sensors
`3.4.] Magnetic Compasses
`3.4.2 Global Positioning System
`Sensor Fusion
`3.5.1
`Simple Filters
`3.5.2 Kalman Filters
`3.5 .3 Other Fusion Methods
`ReferenCes
`
`3.5
`
`Chapter 4 Map—Matching Module
`4.1 .
`Introduction
`4.2
`Conventional Map Matching
`4.2.1
`Semi-Deterministic Algorithms
`4.2.2
`Probabilistic Algorithms
`Fuzzy-Logic-Based Map Matching
`4.3.1
`Fuzzy-Logic-Based Algorithms
`4.4 Other Map-Marching Algorithms
`4.5 Map-Aided Sensor Calibration
`References
`
`4.3
`
`Chapter 5 Route—Planning Module
`5.1
`Introduction
`5.2
`Shortest Path
`5.2.1 Dijkstra's Shortest Path Algorithm
`5.2.2. Modified Shortest Path Algorithm
`5.3 Heuristic Search
`5.3.1
`A” Algorithm
`Bidirectional Search
`5.4
`5.5 Hierarchical Search
`
`|PR2020—01 192
`Apple EX1032 Page 5
`
`IPR2020-01192
`Apple EX1032 Page 5
`
`

`

`
`
`Contents ix
`
`5.6 Other Algorithms
`References
`
`Chapter 6 Route Guidance Module
`6.1
`Introduction
`
`L
`
`6.2 Guidance While En Route
`6.2.1 Maneuver Generation
`6.2.2
`Route Following
`6.3 Guidance While Off-Route
`6.4 Guidance With Dynamic Information
`References
`
`Chapter 7 Human-Machine Interface Module
`7.1
`Introduction
`
`7.2 Visual-Display-Based Interfaces
`7.2.1
`Display Technologies
`7.2.2
`Touch Screens
`7.2.3 Additional Design Considerations
`Voice-Based Interfaces
`7.3.1
`Speech Recognition
`7.3.2
`Speech Synthesis
`
`7.3
`
`References
`
`Chapter 8 Wireless Communications Module
`8 .1
`Introduction
`
`8.2
`
`8.3
`
`Communications Subsystem Attributes
`8.2.1
`Coverage
`Capacity
`Cost
`
`8.2.2
`8.2.3
`
`Connectivity
`8.2.4
`Existing Communications Technologies
`8.3.1
`Paging
`8.3.2
`Cellular
`
`8.3.3
`
`8.3.4
`
`8.3.5
`8.3.6
`
`8.3.7
`8.3.8
`
`Personal Communications Services
`
`Private Land Mobile Radio Systems
`Radio Data Networks
`Broadcast Subcarriers
`
`Short-Range Beacons
`Satellites
`
`Communications Subsystem Integration
`8.4
`References
`
`123
`
`125
`
`129
`129
`
`130
`131
`133
`
`135
`
`136
`141
`
`143
`
`143
`
`145
`
`146
`151
`
`156
`
`158
`
`160
`
`164
`166
`
`169
`
`169
`170
`
`171
`174
`
`17.5
`175
`
`175
`
`178
`
`180
`183
`185
`191
`
`196
`
`202
`
`205
`
`207
`
`212
`
`
`|PR2020-01192
`Apple EX1032 Page 6
`
`IPR2020-01192
`Apple EX1032 Page 6
`
`

`

`
`
`l
`l
`
`.
`I
`
`x VEHICLE LOCATION AND NAVIGATION SYSTEMS
`
`—_~fi\
`
`Systems
`Part 11
`Chapter 9 Autonomous Location and Navigation
`9.1
`Introduction
`9.2
`Vehicle Location
`9_2,1
`Stand—Alone Technologies
`9.2.2
`Terrestrial Radio Technologies
`9.2.3
`Satellite Technologies
`9.2.4
`Interface Technologies
`Vehicle Navigation
`9.3.1
`Coping With Complex Requirements
`9.3.2 Dual-Use Navigation and Entertainment
`Components
`
`93
`
`References
`
`Chapter 10 Centralized Location and Navigation
`10.1
`Introduction
`10.2 Automatic Vehicle Location
`10.2.1 Centralized Approach
`10.2.2 Distributed Approach
`10.3 Dynamic Navigation
`10.3.1 Centralized Approach
`10.3.2 Distributed Approach
`10.4 Applications: Mayday
`References
`
`Chapter 11 A Case Study: ADVANCE
`11.1
`Introduction
`11.2 Traffic Information Center
`11.3 Mobile Navigation Assistant
`11.3.1 Hardware
`11.3.2 Software
`11.4 Communications Network
`11.5 Initial Evaluation Results
`References
`Chapter 12 Conclusions
`12.] Past Lessons
`12,2 Future Directions
`References
`
`Appendix A Transformation Between Cartesian and Ellipsoidal
`Coordinates
`
`References
`
`215
`2
`2'7
`217
`Zia
`229
`22;
`229
`229
`229
`
`236
`237
`
`239
`239
`242
`243
`24-;
`253
`2-54
`256
`259
`263
`
`265
`265
`265
`274
`275
`231
`236
`239
`293
`295
`295
`299
`303
`
`5
`337
`
`'._______J
`
`|PR2020-01192
`Apple EX1032 Page 7
`
`IPR2020-01192
`Apple EX1032 Page 7
`
`

`

`Contents xi
`
`
`Appendix B Transformation Between UTM and Ellipsoidal Coordinates
`References
`
`Appendix C Positioning Sensor Technologies
`
`Appendix D Least Squares Aigorithm
`References
`
`Appendix E Kalman Filter Algorithm
`References
`
`Fuzzy Logic Background
`Appendix F
`References
`
`About the Author
`
`Index
`
`309
`312
`
`313
`
`317
`318
`
`319
`320
`
`321
`326
`
`327
`
`329
`
`|PR2020-01192
`Apple EX1032 Page 8
`
`IPR2020-01192
`Apple EX1032 Page 8
`
`

`

`CHAPTER 3
`'1'?
`
`POSITIONING MODULE
`
`3.1 INTRODUCTION
`
`The positioning module is a vital component of any vehicle location and navigation
`system. To either help users obtain vehicle location or provide users with proper
`maneuver instructions, the vehicle location must be determined precisely. Therefore,
`accurate and reliable vehicle positioning is an essential prerequisite for any good
`vehicle location and navigation system.
`Positioning involves determination of the coordinates of a vehicle on the surface
`of the Earth. Location involves the placement of the vehicle relative to landmarks or
`other terrain features such as roads. These tasks are accomplished by the positioning
`module in conjunction with other modules. In this chapter, we introduce the basic
`positioning technologies and sensors and then study sensor fusion technologies for
`integrating the sensor inputs used to estimate position and location.
`Three positioning technologies are most commonly used: stand-alone, satellite
`based; and terrestrial radio based. Dead reckoning is a typical stand-alone technology.
`A common satellite-based technology involves equipping a vehicle with a global
`positioning system (GPS) receiver. Dead reckoning and CPS technologies have been
`used widely in vehicles. Therefore, we will concentrate on these two commonly
`used and easily accessed technologies in this chapter and leave the terrestrial radio
`titchnology to a later section (Sccrion 9.2)
`following our discussion of radio
`
`43
`
`|PR2020-01192
`Apple EX1032 Page 9
`
`IPR2020-01192
`Apple EX1032 Page 9
`
`

`

`44 VEHICLE LOCATION AND NAVIGATION SYSTEMS
`
`communications in Chapter 8. Although some of these radio technologies, like GPS,
`do not require users to construct central host facilities or complicated communica-
`tions systems and infrastructures, this arrangement will quickly direct readers’ atten»
`tions to the more popular technologies first. Readers may refer to Table 10.1 for a
`performance comparison of the main positioning technologies discussed in the book.
`As we will learn shortly, no single sensor is adequate to provide position and
`location information to the accuracy often required by a location and navigation
`system. The common solution [frequently the only way of obtaining the required
`levels of reliability and accuracy) is to fuse information from a number of different
`sensors, each with different capabilities and independent failure modes. Therefore,
`a positioning module typically integrates multiple sensors, which compensate for
`one another to meet overall system requirements. This in turn requires that we study
`a variety of sensors {Figure 3.1), fusion methods, and algorithms. Because a GPS
`receiver functions like an absolute sensor, for convenience of study we discuss it
`together with the compass. Bear in mind that this is a satellite—based technology and
`is based on an operating principle quite different from that of other sensors (as we
`will learn shortly).
`The positioning module is the most fundamental of the various modules needed
`for vehicle location and navigation. As seen from Figure 3.1, it is based on a variety
`of different positiouing sensors. Because of the key roles played by these sensors,
`we will discuss commonly used low-cost sensors in depth. Readers who are not
`interested in the details can skip the in-depth discussions but still should be able to
`grasp the basic concepts in this chapter. We do not pretend to cover all possible
`sensors in this chapter. With the rapid advances of technology, it is difficult to cover
`even a particular type of sensor completely in a limited space since a variety of
`implementation methods can be used to manufacture a sensor based on the same
`theoretical principle. A similar difficulty also occm-s with sensor integration and
`fusion technologies. However, the emphasis placed on sensors in current use and
`
`Transmission Pickup
`;‘ Wheel Sensors
`
`GPS
`Receiver
`
`.
`
`Distance 1Q
`
`Gyroscope
`Direction g
`
`Latitude, Longitude.
`
`Compass
`Q
`
`Direction
`
` [El Velocity, Time. etc-
`
`
`
`
`
`
`
`Fieiaiive Sensors
`
`Absolute Sensors
`
`Vehicle Position
`
`Figure 3.1 A generic positioning module.
`
`|PR2020-01192
`Apple EX1032 Page 10
`
`IPR2020-01192
`Apple EX1032 Page 10
`
`

`

`
`
`Positioning Modnie 45
`
`the fundamental fusion technologies available should be sufficient for anyone inter-
`ested in vehicle location and navigation to have a basic understanding of this particu-
`[at area. For available linear and angular automotive sensor technologies, see the
`two tables summarized in Appendix C. Reviews of the latest automotive sensor
`development and automotive sensor technologies can be found in [1—4]. A detailed
`discussion of sensor technologies, Sensor principles, and sensor interface circuits can
`be foond in [5,6].
`ln-depth coverage of sensor integration and fusion can be
`found in [7].
`
`3.2 DEAD RECKONING
`
`A very primitive positioning technique is dead reckoning. For vehicles traveling in
`a two-dimensional planar space, it is possible to calculate the vehicle position at
`any instance provided that starting location and all previous displacements are
`known. Dead reckoning incrementally integrates the distance traveled and direction
`of travel relative to a known location. In short, it is a technique that determines the
`vehicle location (or coordinates) relative to a reference point.
`The sensors discussed in the following sections can be used to measure the
`direction of the vehicle 6 and the distance traveled d. After the sensor data have
`
`been sampled and integrated and sensor fusion has been performed, the vehicle
`position (x,,, y") and orientation (9,) at time 1;, can be calculated from the equation
`n—l
`
`x,, = x0 + Z dicosfi;
`i=0
`n—l
`
`y” .2: 3’0 + z dismfi‘,
`i=0
`
`n—I
`
`6?! z 2 fit!“
`i=0
`
`where (x0, yo) is the initial vehicle position at time to, d,- is the distance traveled or
`the magnitude of the displacement between time t,,_1 and time tn, 3,- is the direction
`(heading) of the displacement vector, and a), is the angular velocity for the same
`time period. A drawing outlining this method is shown in Figure 3.2-
`When the sampling period is constant (and short relative to the time scale for
`changes in vehicle velocity}, the above equation can be written as
`n—l
`
`xi: = x0 + 2 Uchoslag + (:1ng
`i=0
`rI—1
`
`3’»:
`
`'= yo + 2 u,Tsin(0,- + thl
`i=0
`
`|PR2020-01192
`Apple EX1032 Page 11
`
`IPR2020-01192
`Apple EX1032 Page 11
`
`

`

`46 VEHICLE LOCATION AND NAVIGATION SYSTEMS
`
`
`
`Figure 3.2 Dead-reckoning method.
`
`where v.- is the velocity measured over the sampling period T. During each sampling
`period, u,- and w, are essentially constant. Mathematically speaking, this method
`basically amounts to a continuous integration of successive displacement vectors.
`As seen from the preceding equations, the current calculated vehicle position
`during each sampling period (cycle) depends on the previous calculation cycle. It
`is difficult to eliminate errors associated with the previous cycle or the current
`measurement (due to sensor inaccuracy and the assumption that the heading remains
`constant over the sampling period). if not compensated or not properly compensated,
`these errors will generally accumulate as the vehicle continues to travel, and the
`calculated position of the vehicle will become less and less accurate. We will discuss
`algorithms (Chapter 4), short-range beacon networks (Section 8.3.7), and other
`technologies (Section 9.2) for eliminating these cumulative errors.
`Position sensors can be designed to detect various components (distance, direc-
`tion, or angular velocity) of the position of vehicular mechanical systems. They are
`either directly coupled to a shaft or linkage, or indirectly coupled to these or other
`vehicle parts in the case of a noncontact or proximity sensor. Many factors affect
`the choice of a sensor for a particular situation in the vehicle design, such as frequency
`of vibrations, temperature range, or the presence of dirt and grease. For a designer
`of a location and navigation system, position sensors and their output signals are
`often already given. The task is to make them function as an integral part of the
`positioning module. Therefore, a basic understanding of common sensor technologies
`hecumes necessary.
`
`l.1
`
`3.3 RELATIVE SENSORS
`
`A relative sensor is a device that can measure the change in distance, position, or
`heading based on a predetermined or previous measurement. Without knowing an
`initial position (or previous reference) or heading, this sensor cannot be used to
`determine absolute position or heading with respect to the Earth.
`
`|PR2020-01192
`Apple EX1032 Page 12
`
`IPR2020-01192
`Apple EX1032 Page 12
`
`

`

`
`
`Positioning Module 47
`
`:3"
`
`3.3.1 Transmission Pickups
`
`Transmission pickup sensors are used to measure the angular position of the transmis-
`sion shaft. Different technologies, such as variable reluctance, the Hall effect, magne-
`toresistance, and optically based technologies, are used to convert the mechanical
`motion into electronic signals. Although some transmission pickup sensors may have
`analog output, it is not difficult to design an interface to convert the signal to pulses
`indicating fractional revolution. Knowing the number of pulse counts per revolution
`and a proper conversion scale factor, one can convert the output of the sensor into
`distance traveled. To avoid mechanical wear and corresponding changes in accuracy
`of the measurement, it is desirable to measure the angular position of the shaft with
`a noncontact sensor. Because there is always an air gap between the sensor and the
`component being monitored, a noncontact sensor is not subject to friction wear.
`Magnetic fields and optical methods are the two most common methods used for
`noncontact coupling to a rotating shaft. In this section, we discuss only the magnetic
`field method.
`
`There are two common places in the vehicle where the signal from the transmis-
`sion pickup sensor can be obtained. One is from a connector behind the speedometer.
`The orher is from a connector on the transmission housing. In general, a two-wire
`connector indicates a variable~teluctance position sensor and a three-wire connection
`indicates a Hall—effect position sensor.
`These variable-reluctance and Hall-effect sensors are not limited to transmission
`pickups. They can be used to detect the position and speed of rotating toothed or
`notched wheels in crankshaft-, camshaft-, and wheel-monitoring applications. Some
`of these applications are discussed in the next section.
`
`Variable-Reluctance Position Sensor
`
`The principle of the variable-reluctance sensor is that the total electromagnetic force
`(emf) induced in a closed circuit is equal to the time rate of decrease in the total
`magnetic flux linking the circuit. The total magnetic flux (number of lines of magnetic
`force) is inversely proportional to total reluctance. Any change in the reluctance of
`the magnetic circuit will cause a change in the magnetic flux. If the changing flux
`lines pass through a coil, the change in flux will induce an emf on the coil. The
`output emf is measured as a voltage proportional to the rate of change of the
`reluctance for the path as shown in the following equation:
`
`where dtwdt is the rate of change in the magnetic flux in webers per sec0nd, and e
`is the emf in volts. As a result, the output voltage goes to zero as the rate of change
`
`|PR2020-01192
`Apple EX1032 Page 13
`
`IPR2020-01192
`Apple EX1032 Page 13
`
`

`

`#7
`
`48 VEHICLE LOCATION AND NAVIGATION SYSTEMS
`
`approaches zero. Therefore, variable-reluctance sensors cannot be used at speed;
`near zero. Additional detail on magnetic field measurements and magnetic fluxj,
`provided in Section 3.4.1.
`The variable-reluctance position sensor censists of a permanent magnet with
`a coil of wire wound around it (Figure 3.3). A ferrous wheel or ironlsteel dislr
`mounted on the rotating shaft has teeth or tabs that pass between the pole piece
`of this magnet. The voltage output from the sensor is typically a sine wave. When
`a tooth on the ferrous wheel begins to pass between the magnet pole pieces, the coil
`voltage starts increasing from zero, reaches a maximum, and fails to zero again
`when the tooth is exacrly between the pole pieces. At this point the rate of change
`in the magnetic flux is zero (even though the magnetic flux is at its maximum value).
`Therefore, the induced voltage across the sensing coil goes to zero. As the toad:
`continues its movement, the voltage output from the coil once again increases from
`zero, reaches a maximum, and falls to zero again as the tooth passes out of the gap
`between the pole pieces, and thus finishes a complete sine cycle.
`Despite their simple, rugged construction and low cost, variable-reluctance
`sensors do have drawbacks [2,8]. First, it is difficult to output a constant voltage
`envelope. As the speed of the ferrous wheel changes, the voltage level and frequency
`change as well. Second, the signal-to-noise ratio can be seriously degraded by vibra-
`tions or resonance. Third, the Output of the sensor is sensitive to the gap between
`the sensor and the disk. In other words, the output is inversely proportional to the
`gap size. Proper alignment and a rigid sensor mounting are required. Fourth, there
`is no sensor output when the disk rotation speed is below a certain threshold. This
`means that no output is available at very low speeds. Fifth, the range of this sensor
`tends to flatten at high speeds. The extent of this effect varies based on the sensor
`design. Finally, elecrromagneric interference or radio-frequency interference tan
`
`Side
`View
`
`Front View of
`Ferrous Wheel
`
`iii
`
`Figure 3.3 Verinhlcqeluerance position sensor.
`
`|PR2020-01 192
`Apple EX1032 Page 14
`
`
`
`IPR2020-01192
`Apple EX1032 Page 14
`
`

`

`
`
`Positioning Module 49
`
`introduce false signals if the sensor is not properly shielded or packaged, since the
`coil in the reluctance sensor has a rather high impedance. Signal processing circuitry
`can be added to the sensor package to obtain a high signal level and to minimize
`the interference.
`
`HalLEffect Position Sensor
`
`The Hall effect is the effect by which a voltage is generated in a conductor moving
`in a magnetic field. It is based on the interaction between moving electric carriers
`in a conductor and an external magnetic field. As a conductor is moved through a
`magnetic field, the current (which consists of moving electric charges) generated in
`the conductor will experience a force in a direction perpendicular to both the direction
`of motion and the magnetic field. A voltage due to the movement of these charges
`can be detected. Hall-effect devices can be manufactured in silicon or semiconductor
`materials.
`
`A Hall-effect position sensor with a ferrous wheel or ironlsteel disks is shown
`in Figure 3.4. The Hall-effect device is assembled into a probe with a biasing magnet
`and a circuit board. Figures 3.4 does not show the configuration inside the probe.
`The Hall-effecr device actually lies at the end of the probe, close to the wheel, so
`that it always lies between the magnet and the wheel. When an external Current is
`passed through this device, a voltage develops across the device perpendicular to
`the direction of current flow and to the direction of magnetic flux. As the ferrous
`wheel rotates, the reluctance of the magnetic field changes as the teeth or tabs pass
`the probe.
`
`Side
`View
`
`Front View of
`Ferrous Wheel
`
`s
`
`Figure 3.4 Hall-effect position sensor.
`
`|PR2020-01192
`Apple EX1032 Page 15
`
`IPR2020-01192
`Apple EX1032 Page 15
`
`

`

`50 VEHICLE LOCATION AND NAVIGATION SYSTEMS
`WEE—“5‘
`
`Unlike the variable-reluctance sensor, the Hall-effect sensor is a zerosmg
`sensor. No matter what the velocity, once the Hall~effect device lines up with the
`strongest magnetic field, there will be a maximum waveform output. Therefore, the
`voltage output (square wave) from this sensor is independent of the speed of the
`rotating shaft.
`Sensors that utilize Hall-effect technology also have some limitations. The
`response degrades as the upper and lower limits of operating temperature an:
`approached. They cannot be used in severe temperatures, lower than -40°C (—40%)
`or higher than 656°C (150°F). The presence of other close, strong magnetic field;
`can cause errors. As in the case of the reluctance sensor, Hall-effect sensors require
`careful alignment and mounting because of sensitivity to the gap size between sensor
`and disk. Unlike the passive reluctance Sensor, the Hall-effect sensor is an active
`sensor which requires an external electrical input. In addition, unlike the variable
`reluctance sensor, the output voltage of the Hall-effecr sensor remains constant as
`the disk rotation frequency is varied. This sensor can easily be combined with a
`signal processing circuit to output a high-level voltage. In general, it is more desirable
`to use a Hall-effect sensor than a variable-reluctance sensor for transmission pickup
`sensors or Other position sensors used in vehicle location and navigation systems.
`Further discussion of these and other automotive sensors can be found in [2.4].
`
`3.3.2 Wheel Sensors
`
`Wheel Sensors for Anti-Lock Braking Systems
`
`A typical anti-lock braking system (ABS) consists of wheel speed sensors, an electronic
`control unit, a brake pI‘eSsure modulator, wiring, relays, hydraulic tubing, and
`connectors to link the whole system together. Most ABS systems currently in use
`offer four-wheel control. The basic components used for the wheel speed measuring
`systems include a sensing element, a ferrous wheel (exciter wheel, target wheel, tone
`wheel, or ironlsteel disk), and the mechanical hardware required to mount the above
`elements with the appropriate spacings to ensure correct operation.
`The variable-reluctance sensor is still the most popular for ABSs because of
`its low cost and relative reliability. As discussed earlier, this sensor is not reliable
`at low speeds, especially below 0.45 to 1.34 mfs (1 to 3 milesfhr); this makes accurate
`vehicle positioning very difficult when using these sensors for input to a positioning
`module. Hall-effect position sensors can also be used as ABS speed sensors. We have
`learned that borh sensors are electromagnetic pulse pickups using toothed wheels
`{exciter rings) mounted directly on the rotating components of the drive train, shaft.
`or wheel hubs. They provide a digital signal whose frequency is proportional to the
`rotational velocity of the wheel. Furthermore, any technology with a sensing element
`that converts mechanical motion into an electrical signal can also be used as a wheel
`
`r
`
`L_—__________.
`
`lPR2020-01 192
`Apple EX1032 Page 16
`
`IPR2020-01192
`Apple EX1032 Page 16
`
`

`

`
`
`Positioning Module 51
`
`sensor. Table 3.1 compares several different wheel sensor technologies (most of the
`items in this table are from [9]). From this table we notice that only the variable-
`reluctance sensor is fundamentally incapable of measuring at zero speed (another
`exception is that a Hall-effect sensor cannot function as a zero-speed sensor if its
`feedback circuit has a capacitor).
`
`Differential Odometer
`
`Differential odometry is a technique to provide both distance traveled and heading
`change information by integrating the outputs from two odometers, one each for a
`pair of front or rear wheels. An odometer is a relative sensor that measures distance
`traveled with respect to an initial position. A wheel odometer typically measures
`the number of rotation counts (pulses) generated by a rotating wheel. Averaging the
`left and right wheel rotation counts and multiplying by a proper scale facmr enables
`the distance traveled by the vehicle to be determined. The difference between the
`counts for the left and right wheels multiplied by the same scale factor and divided
`by the axle length can be used to obtain the change in the heading of the vehicle.
`Both the distance traveled and the heading change can be used in calculating the
`vehicle position.
`One example of a differential odometer is shown in Figure 3.5. A ferrous wheel
`or ironfsteel disk (toothed gear) is attached to each of the nondriven wheels of the
`vehicle (because acceleration and deceleration have less effect on the output of sensors
`on nondriven wheels). A Hall-effect sensor is located close to the toothed gear. This
`sensor outputs a pulse for each tooth that passes across its sensing tip. Two counters,
`one for the left wheel and one for the right wheel, count these pulses. This left or
`right tooth count can be translated to the distance each wheel has traveled by
`multiplying the count by the scale factor (which is a predetermined value for the
`distance per count}.
`
`Table 3.1
`
`Wheel Speed Sensor Comparison
`
`
`Sensor
`
`Frequency Range
`
`Magnet
`
`Ferrous Wheel
`
`SignaIINoise
`
`High
`No
`No
`0-500 RH:
`Eddy current
`Moderate
`Yes
`Yes
`0—1 MHz'
`Hall effect
`Moderateihigh
`Yes
`Yes
`0-500 kHz
`Magnetic transistor
`Moderate
`Yes
`Yes
`0—5 MHz
`Magnetoresistive
`Very high
`No
`No-
`0-10 MHz
`Optical
`High
`Yes
`Yes
`0-600 Hz
`Reed switch
`Variable relUCEEnCE
`1—100 kHz
`Yes
`Yes
`Low
`
`Wiegand effect
`0-20 kHz
`Yes
`Yes
`High
`
`|PR2020-01 192
`Apple EX1032 Page 17
`
`IPR2020-01192
`Apple EX1032 Page 17
`
`

`

`$2 VEHICLE LOCATlON AND NAVIGATION SYSTEMS
`
`Hall-Ettect Sensors
`
`\
`
`
`
`Ferrous Wheels
`
`Figure 3.5 Differential odometer.
`
`After resetting the counters and driving the vehicle along a known Strait}-
`distance D while recording the counter numbers, the left and right scale lemma.-
`be calculated from
`
`D
`KL=—CL
`D
`KR=EE
`
`where C; and C3 are the number of counts for the left wheel and right what
`respectively. Knowing the scale factor for each wheel and the previous measuttme
`at t - 1, we can easily derive the distance traveled up to time t as follows:
`
`do) = d{;-1] +w
`
`K
`
`K C
`
`When the vehicle heading is changed. the outer wheel travels farther than [[1th
`wheel by IKLCL - KRCRI. Knowing the distance L between the left and rightwlltfl‘
`[axle length), the vehicle heading can be obtained from this equation:
`
`IKLCL ‘- KRCRI
`em = alt ” 1’ + —“——L
`
`Note that as long as the ratio KL/KR 5 1, We know that the Vehicle is travelingi‘
`a straight—line segment road {provided KL and K3 are accurate). 0n the other haf‘l
`if we know that the vehicle is traveling on a straight-line segment based onI
`given digital map, we can use this information to calibrate these two scale latterl
`
`
`
`|PR2020-01192
`Apple EX1032 Page 18
`
`IPR2020-01192
`Apple EX1032 Page 18
`
`

`

`
`
`1.
`
`52 VEHICLE LOCATION AND NAVIGATION SYSTEMS
`
`
`Hall—Ellecl Sensors
`
`
`
`Ferrous Wheels
`
`Figure 3.5 Differential odometer.
`
`After resetting the counters and driving the vehicle along a known straight
`disrance D while recording the counter numbers, the left and right scale factors can
`be calculated from
`
`D
`“=32";
`D
`“For
`
`where CL and C3 are the number of counts for the left wheel and right wheel,
`respectively. Knowing the scale factor for each wheel and the previous measurement
`at t — 1, we can easily derive the distance traveled up to time t as follows:
`
`do} = dlt~1l+w
`
`When the vehicle heading is changed, the outer wheel travels farther than the inner
`wheel by [KLCL — KRCRI. Knowing the distance L between the left and right wheels
`(axle length), the vehicle heading can be obtained from this equation:
`
`L
`
`iKLCL " KRCRI
`
`Bu):fl(t-l)+
`
`Note that as long as the ratio KLIKR = l, we know that the vehicle is traveling on
`a straight-line segment road {provided KL and K3 are accurate). 0n the other hand!
`if we know that the vehicle is traveling on a straight-line segment based on!
`given digital map, we can use this information to calibrate these two scale factors
`
`|PR2020-01192
`Apple EX1032 Page 19
`
`IPR2020-01192
`Apple EX1032 Page 19
`
`

`

`
`
`Positioning Module 53
`
`see
`(such as GPS,
`the outputs from other sensors
`dynamically. Moreover,
`Section 3.4.2) can be used to calibrate the scale factor. For instance, when the vehicle
`travels above a certain speed and the tracked satellite geometry used for the position
`fix is good, the velocity and heading information received from the GPS sensor is
`very good. The travel distance extracted from the velocity can then be used to
`calibrate the scale factor. Now we can see the benefit of using multiple positioning
`sensors in a location and navigation system.
`Depending on the technology used, an odometer or differential odometer often
`has an operational error similar to that experienced by varia hie-reluctance and Hall-
`effect sensors in general. In addition, the differential odometer is subjecr to systematic
`and nonsystematic errors such as unequal wheel diameter, misalignment of wheels,
`the finite sampling rate and count resolution, running over objects on road, slips or
`skids involving one or more wheels, etc. A slip or skid occurs if the vehicle accelerates
`or decelerates too rapidly or travels on a snowyficyi'wet road. These errors may lead
`to incorrect calculated disrance and heading data. Furthermore, in sharp turns, the
`contact point between each wheel and the road can change, so that the actual disrance
`L between the left and right wheels will be different from the one used in the
`preceding equation to derive the heading. The tire pressure in each wheel may
`change over time, as may the wheel diameter due to the tire conditions or change
`in temperature. Therefore, the scale factors used to calculate position may change
`after initial calibration. These factors contribute to the error sources of the differential
`odometer, which lead to accumulative errors discussed in Section 3.2.
`
`3.3.3 Gyroscopes
`
`Rate—sensing gyroscopes measure angular rate, and rate-integrating gyroscopes mea-
`sure attitude. At the present time, most location and navigation systems use gyro-
`scopcs to measure the angular rate.
`Gyroscopes include mechanical, optical, pneumatic, and vibration devices. A
`comparison of these gyroscope types is presented in Table 3.2. (The gas-rate gyro~
`scope is classified as a pneumatic gyroscope for lack of a better word.) As the
`explosive development of design and manufacturing technologies continues, the
`
`Table 3.2
`
`Gyroscope Comparison
`
`Type
`
`
`Performance
`Cost
`
`Mechanical
`Optical
`Pneumatic
`Vibration
`
`Very good
`Very good
`Good
`Good
`
`Expensive
`Moderate
`Moderate
`Cheap
`
`Size
`
`Large
`Moderate
`Moderate
`Small
`
`|PR2020-01 192
`Apple EX1032 Page 20
`
`IPR2020-01192
`Apple EX1032 Page 20
`
`

`

`S4 VEHICLE LOCATI