I 1111111111111111 11111 lllll lllll lllll 111111111111111 lllll 111111111111111111
`5,774,829
`[11]Patent Number:
`United States Patent
`[19J
`Cisneros et al.
`Jun.30, 1998
`[45] Date of Patent:
`
`US005774829A
`
`
`
`
`
`(List continued on next page.)
`
`"A Novel Procedure for Assessing the Accuracy of Hyper­
`
`
`
`[54] NAVIGATION
`AND POSITIONING SYSTEM
`
`
`bolic Multilateration Systems"; H.B. Lee; IEEE, Vo.
`
`AND METHOD USING UNCOORDINATED
`
`
`AES-11, No. 1, Jan. 1975; pp. 2-14.
`
`BEACON SIGNALS IN CONJUNCTION
`"Accuracy Limitations of Hyperbolic Multilateration Sys­
`
`
`
`
`WITH AN ABSOLUTE POSITIONING
`
`
`tems"; H.B. Lee; IEEE, Vol. AES-11, No. 1, Jan. 1975; pp.
`SYSTEM
`16-29.
`Joseph S. Cisneros, San Dimas; David[75]Inventors:
`
`
`
`
`
`
`C. Kelley, Covina; Michael Kiang,
`
`Allso Viejo; Louis A. Greenbaum,
`Primary Examiner-Michael Zanelli
`
`
`
`Redondo Beach, all of Calif.
`
`
`Attorney, Agent, or Firm-Gary S. Williams; Flehr Hohbach
`
`
`Test Albritton & Herbert LLP
`
`
`Pinterra Corporation, Garden Grove,[73] Assignee:
`
`[57]
`Calif.
`
`ABSTRACT
`
`[21] Appl. No.: 570,747
`
`[22] Filed:Dec. 12, 1995
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`[56]
`
`
`
`References Cited
`
`
`
`U.S. PATENT DOCUMENTS
`
`A navigation system in which an uncoordinated beacon
`
`
`
`
`
`
`positioning system (UBS) is used in conjunction with an
`
`
`
`
`absolute positioning system (APS) is described herein. The
`
`
`
`UBS employs a multiplicity of transmitters, at known
`G0lS 5/02; H04B 7/185
`
`[51] Int. Cl.6
`
`
`
`locations, each of which transmits a beacon signal having a
`701/213; [52] U.S. Cl. ........................... 342/457; 701/214
`
`
`
`
`phase that is at least partially un-synchronized with the
`
`
`
`
`
`phases of the beacon signals of the other transmitters. Within
`[58] Field of Search ............................ 364/449.8, 449.95,
`
`
`
`
`a mobile unit, separate receivers are provided for receiving
`
`
`364/449.1, 460, 452; 342/357, 457; 340/995;
`
`
`these beacon signals and for receiving APS signals. The
`
`
`701/214, 216, 207, 300, 219
`
`
`
`
`absolute positioning system (APS) receiver is disposed to
`
`
`
`
`
`receive the APS signals, and to estimate an initial position of
`
`
`
`the mobile unit therefrom. The mobile unit processor is
`
`
`
`
`
`disposed to modify the estimated mobile unit position on the
`
`
`
`basis of the detected beacon signal phases. The mobile unit
`3,774,215 11/1973 Reed ................................... 343/112 D
`
`
`
`
`
`
`
`processor may also be programmed to determine the uncer­
`
`
`
`4,506,228 3/1985 Kammeyer .............................. 329/107
`
`
`
`5,173,710 12/1992 Kelly et al. ............................. 342/463
`
`
`
`
`tainty of location information provided by the beacon signal
`
`
`
`5,280,295 1/1994 Kelly et al. ............................. 342/463
`
`
`
`
`receiver and by the APS receiver. This allows the current
`
`
`
`5,311,195 5/1994 Mathis et. ............................... 342/357
`
`
`
`
`location of the mobile unit to be updated by selecting the
`
`
`5,323,163 6/1994 Maki ....................................... 342/357
`
`
`
`
`location estimate having associated therewith the least
`
`
`
`5,355,526 10/1994 Berninger ............................. 455/161.2
`
`
`
`amount of location uncertainty, or by weighting each esti­
`
`
`
`
`
`5,365,450 11/1994 Schuchman et al. ................... 364/449
`
`
`mate based on its uncertainty and combining the two
`
`
`
`5,406,490 4/1995 Braegas ................................... 364/449
`
`
`
`
`
`weighted location estimates. In another implementation, the
`
`
`
`
`5,422,813 6/1995 Schuchman et al. ................... 364/449
`
`
`
`mobile unit includes an estimator operative to compute an
`
`
`
`5,499,032 3/1996 Kelly et al. ............................. 342/357
`
`
`
`estimate of mobile unit position on the basis of selected
`
`
`
`5,510,801 4/1996 Engelbrecht et al. .................. 342/457
`
`
`
`5,552,772 9/1996 Janky et al. ............................ 340/573
`
`
`
`pseudorange measurements from the UBS and APS receiv­
`
`
`
`
`ers. The estimator may include a Kalman filter configured to
`
`
`
`
`
`process residual pseudorange information provided by the
`
`UBS and APS receivers.
`
`
`
`"A New Approach to Geometry of Range Difference Loca­
`
`
`
`tion"; R.O. Schmidt; IEEE, vol. AES-8, No. 6, Nov. 1972;
`pp. 821-835.
`
`OTHER PUBLICATIONS
`
`
`
`36 Claims, 16 Drawing Sheets
`
`c 120-2
`) MOBILE UNIT I
`
`c 120.3
`..--l MOBILE UNIT!
`
`c 120.1
`) MOBILE UNIT I
`
`110
`
`...........•... r:••••• ,
`
`! FIXED POSITION 1--------A 102.5
`'
`✓: OBSERVER
`K
`
`100 ,,,....,.._.,;r
`
`Cisco v. TracBeam / CSCO-1006
`Page 1 of 39
`
`

`

`5,774,829
`Page 2
`
`OIBER PUBLICATIONS
`
`"A Direct Solution to GPS-Type Navigation Equations";
`
`
`
`
`
`Lloyd 0. Krause; IEEE vol. AES-23, No. 2; Mar. 1987; pp.
`"The Theory of Loran-C Ground Wave Propagation-A
`
`
`225-232.
`
`
`
`
`Review"; S.N. Samaddar; Navigation, vol. 26, No. 3, Fall,
`"Passive Source Localization Employing Intersecting
`
`
`
`1979; pp. 173-187.
`
`
`
`Spherical Surfaces from Time-of-Arrival Differences";
`
`
`"Omega Possibilities: Limitations, Options, and Opportuni­
`
`
`
`H.C. Schau et al.; IEEE vol. ASSP35, No. 8, Aug. 1987; pp.
`
`
`
`ties"; E.R. Swanson; Navigation, vol. 26, No. 3, Fall 1979;
`1223-1225.
`pp. 188-202.
`"Sensitivity of GPS Acquisition to Initial Data Uncertain­
`
`
`
`"Aircraft Experiences with a Hybrid Loran-GPS"; Ralph
`
`
`
`
`ties"; C.A. Smith et al.; Inst. of Navigation, Papers Pub­
`
`
`
`Eschenbach et al.; Navigation, vol. 35, No. 4; Winter
`
`
`
`lished in Navigation, vol. 1, copyright 1980; pp. 31-43.
`
`1988-89; pp. 459-468.
`
`
`"Operational Benefits and Design Approaches for Combin­
`"Aiding GPS with Calibrated Loran-C"; Per K. Enge et al.;
`
`
`
`
`
`
`
`ing JTIDS and GPS Navigation"; Walter R. Fried; Inst. of
`
`
`
`
`Navigation, vol. 35, No. 4; Winter 1988-89; pp. 469-482.
`
`
`
`Navigation, Papers Published in Navigation, vol. ,; Jan.
`"Cost Effective, High-Accuracy Inertial Navigation"; A
`
`
`
`1984; pp. 209-225.
`
`
`Matthews et al.; Navigation, vol. 36, No. 2; Summer 1989;
`
`
`
`"The Impact of Cross-Rate Interference on LORAN-C
`pp. 157-172.
`
`
`Receivers"; M.J. Zeltser et al.; IEEE vol. AES-21, No. 7,
`Jan. 1985; pp. 36-46.
`"A Divide and Conquer Approach to Least-Squares Esti­
`
`
`
`
`
`
`
`"An Algebraic Solution of the GPS Equations"; Stephen
`
`
`
`
`mation"; IEEE Transactions Aerospace & Electronic Syst. ,
`
`
`Bancroft; IEEE, vol. AES-21, No. 7, Jan. 1985; pp. 56-59.
`
`vol. 26, No. 2; Mar. 1990; pp. 423-426.
`
`
`
`"Navigational Coordinate Systems: How To Get Your Sur­
`"Synergistic Integration of GPS and INS for Civil Aviation";
`
`
`
`
`face and Air Positioning Very Precise and Still Be Off By 20
`
`
`
`John Diesel et al.; GPS World; May 1991; pp. 41-45.
`
`
`
`
`
`Nautical Miles"; Stephen B. Richter et al.; IEEE 1986; pp.
`
`
`268-272.
`
`
`No. 4; Winter 1991-92; pp. 341-353.
`
`"Combining LORAN and GPS-The Best of Both Worlds";
`
`
`
`
`Paul Raisted et al.; Inst. of Navigation, Papers Published in
`"Urban Positioning with GPS: A Mobile Communications
`
`
`
`
`Navigation, vol. III; copyright 1986; pp. 235-240.
`
`
`
`Field Measurement Application"; Jean-Claude Fanton; GPS
`
`
`
`"Terrestrial Evaluation of the GPS Standard Positioning
`World; Jul. 1993; pp. 28-39.
`
`
`
`Service"; Francis W. Mooney; Inst. of Navigation, Papers
`"Integration of GPS with Inertial Navigation Systems"; D.B.
`
`
`
`
`
`
`Published in Navigation, vol. III,; copyright 1986; pp.
`
`Cox, Jr.; Inst. of Navigation, Papers Published in Naviga­
`275-293.
`
`tion, vol. III, copyright 1986; pp. 144-153.
`"Telenav: A Precision Navigation System Based Upon Tele­
`
`
`
`
`
`
`
`vision Signal Reception"; Will Connelly; Navigation, vol.
`"Integration of GPS and Dead-Reckoning Navigation Sys­
`
`
`
`
`33, No. 2, Summer 1986; pp. 109-122.
`
`tems"; Wei-Wen Kao; pp. 1-9. No Date.
`
`"A Rate Integrating Fiber Optic Gyro"; Navigation, vol. 38,
`
`Cisco v. TracBeam / CSCO-1006
`Page 2 of 39
`
`

`

`U.S. Patent Jun.30, 1998
`
`5,774,829
`Sheet 1 of 16
`
`�
`
`0
`z
`::::,
`C\J
`.....
`w
`...J
`ca
`0
`�
`
`C\J
`
`I
`
`0
`t::
`C\J
`.....
`z
`::::,
`w
`...J
`ca
`0
`�
`
`I
`
`t::
`.....
`z
`0
`::::,
`C\J
`.....
`
`ca
`0
`�
`
`.....
`
`I
`
`.....
`
`0
`0
`.....
`
`Cisco v. TracBeam / CSCO-1006
`Page 3 of 39
`
`

`

`Sheet 2 of 16 5,774,829
`U.S. Patent
`Jun.30, 1998
`
`er:
`w
`
`Cl) 2= rela.w �I
`<t:
`uw
`cc-
`
`Cisco v. TracBeam / CSCO-1006
`Page 4 of 39
`
`

`

`DETECTOR
`
`PHASE
`
`144
`
`SIGNAL
`PILOT
`
`140
`
`•
`
`•
`
`CPU
`
`162
`160 MAIN CONTROL ROUTINE
`
`LOOP FILTER ROUTINE
`
`180
`
`150
`
`120
`
`182
`
`BEACON DATA TABLE
`
`170
`
`ROUTINES
`
`NAVIGATION
`
`168
`
`LOW PASS FILTER
`
`166
`
`ACCUMULATOR
`PHASE MASTER
`
`164
`
`FIGURE2B
`
`CLOCK GEN
`
`CLK MTM
`
`o____,
`
`184 146
`
`M-----t E
`M-----t "OVER"
`te-----t
`
`POWER
`
`ERROR
`PHASE
`
`�<I> ------91
`
`<1>1----.i
`
`Cisco v. TracBeam / CSCO-1006
`Page 5 of 39
`
`

`

`Sheet 4 of 16 5,774,829
`U.S. Patent
`Jun.30, 1998
`
`160
`�
`
`200
`
`UPDATE TRANSMITTER TABLE WITH DATA
`FROM FIXED POSITION OBSERVER UNIT
`
`
`202
`SCAN ALL FM STATIONS FOR SIGNAL QUALITY
`
`
`
`SEND
`ERROR.._�
`MSG
`
`SELECT UP TO FIVE STATIONS WITH BEST (A) SIGNAL
`
`
`STRENGTH, AND (8) TRANSMITTER POSITIONS FOR
`
`
`ACCURATELY COMPUTING MOBILE UNIT'S POSITION.
`
`216
`SEQUENTIALLY TUNE PLL TO EACH SELECTED STATION.
`
`AT EACH SELECTED STATION WAIT 50 MILLISECONDS FOR
`TUNER TO SETTLE, MEASURE PHASE ERROR FOR 50
`
`
`MILLISECONDS, AND THEN DETERMINE ITS CURRENT
`PHASE AND DRIFT FREQUENCY.
`
`PERIODICALLY COMPUTE AND UPDATE ALL PHASE VALUES,
`USING DETECTED BEACON FREQUENCY VALUES.
`
`218
`
`
`EXECUTE NAVIGATION COMPUTATION ROUTINE
`TO DETERMINE CURRENT POSITION
`
`FIGURE3
`
`Cisco v. TracBeam / CSCO-1006
`Page 6 of 39
`
`

`

`U.S. Patent
`5,774,829
`Sheet 5 of 16
`Jun.30, 1998
`
`144
`
`<l>(H)
`
`�<l>(H)
`
`60
`PHASE
`-----'SIN()
`16 PROM
`----PCLK
`146
`
`268
`
`ACCUMU­
`LATOR
`
`OVER(M)
`E(M)
`
`BASEBAND
`BEACON ADC
`L-----.i POWER
`16
`SIGNAL
`SAMPLES ESTIMATOR
`
`P(M)
`
`MTM MTM CLK 270
`
`CLK
`
`L.__ ____
`,.__ ______
`L------�------.-___.MTM
`CLK
`
`250 252
`
`254
`
`9.728 MHZ
`+64 ---+152
`
`osc
`
`_ MTM CLK
`
`146
`
`----MTM+
`
`FIGURE4
`
`270
`
`16
`
`----�-----I
`
`282
`
`r--,_...-� MTM
`16
`
`280
`+
`o-�B-MSB
`SAMPLES
`8
`() 2
`s--.,c-..i 8-LSB
`PROM
`CLK
`
`EN
`
`MTM
`
`FIGURES
`
`Cisco v. TracBeam / CSCO-1006
`Page 7 of 39
`
`

`

`16
`
`32
`
`312
`
`•
`
`•
`
`FIGURE6
`
`32
`
`MTM+
`
`32
`+ Q-t-�-tD
`
`CLK
`
`16
`
`(�9)
`
`45
`
`°
`
`NCO
`
`DIGITAL260 /
`
`MTM
`
`.__ __ --,,,C.-----1A-LSB
`
`32
`
`16
`
`+
`
`A-MSB
`
`308
`
`8
`
`16
`
`MUX
`
`306
`
`301 304
`
`MTM
`
`314
`
`MTM
`
`16
`
`a a
`
`0 302
`
`30
`
`LOAD
`CPU
`
`L\.<l>(M)
`
`LOAD
`CPU
`
`<l>(M)
`
`Cisco v. TracBeam / CSCO-1006
`Page 8 of 39
`
`

`

`��
`
`E(M)
`
`FIGURE7
`
`MTM EN
`
`35 CLK--. ...
`
`CLK
`
`+
`
`32
`
`A
`
`266
`MULTIPLIER
`FROM -+��...1..-------:�-� B
`OUTPUT
`
`
`32
`
`32
`
`1
`SIGN
`
`MTM
`
`SIGN 1
`
`CIRCUIT �
`ACCUMULATOR
`MAIN
`CIRCUIT
`OVERFLOW
`
`�
`
`OVER(M)
`
`• •
`
`CLK � ·­
`Q
`
`D Q1-a----..,
`
`CLR MTM EN
`
`
`366
`
`268 �
`
`Cisco v. TracBeam / CSCO-1006
`Page 9 of 39
`
`

`

`5,774,829
`U.S. Patent
`Sheet 8 of 16
`Jun.30, 1998
`
`404
`38 KHZ
`COMP
`
`(400
`G(Ol',<l>)
`r - --,
`AGC
`409
`
`E(M)
`
`P(M)
`
`406
`
`Ol'(H)
`
`408
`PHASE
`<l>(H)
`MASTER
`PMA(H)
`ACCMLTR
`
`Ll<l>(H)
`
`406
`LOOP
`1 50
`I<-)
`FILTER
`50
`1
`£11 (H)
`
`FIGURES
`
`.------+-- ---. Ol'(H)
`
`FIGURE9
`
`Cisco v. TracBeam / CSCO-1006
`Page 10 of 39
`
`

`

`Sheet 9 of 16 5,774,829
`U.S. Patent
`Jun.30, 1998
`
`408
`
`Li<l>(H)
`
`152
`
`L---------...i
`
`MODULO
`2TI --<l>(H)
`
`'--- - ----�
`
`PMA(H)
`
`FIGURElO
`
`402
`
`1-K
`
`K
`
`P(M)
`
`A'(M)
`
`FIGURE 11
`
`Cisco v. TracBeam / CSCO-1006
`Page 11 of 39
`
`

`

`U.S. Patent
`Sheet 10 of 16 5,774,829
`Jun.30, 1998
`
`450
`�
`
`452
`TUNE TO NEXT FM STATION
`
`DETERMINE CURRENT PHASE OF PILOT SIGNAL AT
`
`
`FIXED OBSERVER'S POSITION.
`
`56
`
`DETERMINE CURRENT PHASE OF PILOT SIGNAL
`
`
`AT TRANSMITTER'S POSITION.
`
`ADJUST PHASE FOR COMMON TIME VALUE, AND STORE
`
`ADJUSTED PHASE VALUE IN TRANSMITTER DATA TABLE.
`
`60
`
`462
`
`CONTINUOUSLY TRANSMIT THE TRANSMITTER DATA TABLE
`
`
`
`FIGURE 12
`
`Cisco v. TracBeam / CSCO-1006
`Page 12 of 39
`
`

`

`U.S. Patent
`5,774,829
`Sheet 11 of 16
`Jun.30, 1998
`
`430
`
`FIXED
`OBSERVER
`UNIT
`FM Radio
`Receiver
`
`436
`
`�
`
`GPS
`SYSTEM
`
`432
`
`MOBILE
`UNIT
`
`FM Radio
`Receiver
`
`434
`
`GPS
`CPU
`�-------1 Receiver
`1.5Q Time Value
`Msg
`
`FIGURE 13
`
`Cisco v. TracBeam / CSCO-1006
`Page 13 of 39
`
`

`

`Sheet 12 of 16 5,774,829
`U.S. Patent
`Jun.30, 1998
`
`0
`0
`If)
`
`\ ........................................... ._ .... ,
`
`>-u
`
`
` <C 0::::
`er:_w
`en en > col
`::::> u
`a. a. w C'\I
`z
`<( (!) (.) ,...
`u <C
`-w
`� I- 0
`er:
`0 (/)
`0..
`(.!) z £Il Z -
`- - I-
`CJ)
`0 ::::>
`a.
`0 � 0
`<C
`I-
`z
`�
`0:::: LlJ
`'q" I-LlJ
`..- 0
`If)
`z
`
`'q"
`0
`If)
`
`""1'
`
`�
`�
`�
`�
`C,
`�
`�
`
`0
`I-
`(/)
`0
`
`0 w
`I-<( z er:
`zow
`0 (.) � -q-1
`ow ,...
`er: <( (.) C'\I
`om w
`(.) a:
`::::)
`
`N
`
`u
`
`..- >-If)
`<C
`::::>
`u
`u <(
`al
`::::)
`.................................................
`
`f""\
`(!)
`..-
`(V')
`
`.
`
`Cisco v. TracBeam / CSCO-1006
`Page 14 of 39
`
`

`

`5,774,829
`U.S. Patent
`Sheet 13 of 16
`Jun.30, 1998
`
`512
`
`�
`
`520
`SELECT INTITAL SET OF UNCOORDINATED
`
`
`BEACONS PROVIDING SIGNALS OF
`
`ACCEPTABLE QUALITY
`
`522
`MEASURE PHASE OF EACH SIGNAL RECEIVED FROM
`.------- BEACONS IN SELECTED SET
`
`DETERMINE
`"DOP" OF
`UBS
`
`527
`
`MEASURE
`NON-COHERENT 528
`PILOT TONE
`NOISE
`
`DETERMINE
`BEACON
`CORRELATION
`
`COMPUTE QUALITY FACTOR
`
`529
`
`534
`
`WAIT FOR
`
`EXPIRATION OF
`UPDATE INTERVAL
`
`538
`
`N
`
`ADD OTHER BEACONS TO SELECTED SET
`
`540
`
`FIGURE 15
`
`Cisco v. TracBeam / CSCO-1006
`Page 15 of 39
`
`

`

`•
`•
`
`t
`
`_
`
`I
`I
`I r--__ ....,_____
`:
`
`>--------------··
`
`I
`•
`•
`
`I
`I
`I
`
`
`••
`
`600
`
`�
`
`130
`
`602
`
`'
`.
`.
`.
`.
`. '----------------
`·--------··-········---·-·
`604
`
`.
`.
`
`.
`
`
`
`...
`
`( PGPS -PGPS)
`I
`CONTROL
`NTROL :
`RESIDUALS
`PHASE :
`DE :
`PSEUDORANGE
`UBS I
`GPS 1
`GPS
`1 •••••••••••••••••••••
`.J CORR���IONS L......
`.............
`················__j
`: •••••••••••••••••••
`fil..Q
`fil.1
`: DIFFERENTIAL :
`CPU
`CPU
`RECEIVERL--��L_!:l�--�--RECEIV ER . .
`:
`GPS
`UBS
`i TIME
`:.-----'-----
`: GPS
`:
`l
`:
`:
`:
`:
`filJi
`CORRELATOR
`: SPECTRUM i,:
`:
`i PHASE SENSOR i
`:
`SPREAD
`tUBS RECEIVER�
`GPS
`:
`: ,--------'------
`-----------------------
`
`FIGURE 16
`
`POSITION
`MOBILE
`
`UNIT
`
`601
`
`ESTIMATOR
`
`I
`
`I
`
`CO
`CO
`
` _____ ____ i
`
`_J
`
`( PUBS -PUBS)
`RESIDUALS
`PSEUDORANGE
`UBS
`
`_______
`
`.
`
`.
`.
`.
`.
`.
`
`.....
`
`'
`
`•
`
`.
`
`filIB
`
`'
`.
`.
`'
`'
`'
`
`I
`
`.
`
`t
`
`.
`
`:
`!
`
`Cisco v. TracBeam / CSCO-1006
`Page 16 of 39
`
`

`

`Sheet 15
`of 16
`U.S. Patent Jun.30, 1998
`
`5,774,829
`
`w z
`.... q .... 0
`-- I--al z-0 ::::> Cl}
`� 0
`a. j
`
`r••••••••••••••••••••••
`
`' '
`
`..... 0
`
`<O
`
`_s1 ',,
`,,,,,,,,'', , , ,
`
`z cc
`<w� 1-­....J ....J
`�u:
`
`j ' I
`
`..._
`
`(I'.
`
`I
`
`I
`I
`
`:
`
`-51
`
`ro
`
`�
`
`:
`w
`CJ cc Cl) !
`CD :
`Z W
`a: - :
`<> <o:':
`ow I
`:
`cu Cl) :
`::::, W CD :
`w cc a..-:;) !
`C/}Cl} ___ �• f-- --1-... --.......
`a. al :
`:
`....J ::::>
`<� l
`:::> 0 t ____________________
`_
`'
`Q cc
`,
`---·······························
`r·······--------------
`----------
`Cl} LLw
`�
`:
`�--•-➔�
`-
`:
`cc
`I
`I
`�
`x., -
`I
`-�
`:
`I
`,, !
`,
`l <a..(!)
`'
`:
`:
`I
`wa.o :
`:
`a.
`C Ou� :
`sgz� I
`a..C::.
`
`I
`
`I
`
`I
`
`I
`I
`
`:
`
`!
`,
`:
`i
`:
`i
`I 'I
`I '
`: I :I
`
`'
`
`!
`'
`:
`!
`
`a:
`Cl)
`0
`Cl.
`wa.1--
`c OU gi (a..(!)
`0 0 w <cl ��--------1
`u ....J 1--
`w
`C
`
`:
`
`�
`••••••••••••• J
`•••••••••••••••••••••• •••••••••••••••••••••••••••••••
`
`Cisco v. TracBeam / CSCO-1006
`Page 17 of 39
`
`

`

`FIGURE 18
`
`'
`
`•
`
`•
`
`
`
`
`
`•'•
`
`.6P
`
`-
`
`V
`A
`
`�
`
`film
`
`VELOCITY
`
`f?OSITION
`
`UNIT
`MOBILE
`
`--
`
`'
`
`filQ
`
`FILTER
`KALMAN
`
`-
`
`-
`
`-
`
`................................
`
`�
`
`'
`
`�
`
`'
`'
`'
`•
`•
`RESOLUTION -•
`•
`•
`LINE OF SIGHT
`•
`•
`A •
`•
`POSITION
`•
`•
`•
`•
`•
`•
`•
`•
`•
`'
`•
`•
`'
`RESOLUTION '
`'
`'
`LINE OF SIGHT
`'
`'
`'
`'
`'
`'
`'
`'
`'
`'
`'
`'
`'
`•
`•
`'
`'
`'
`'
`'
`'
`'
`'
`• •
`'
`'
`•
`'
`•
`'
`'
`'
`'
`'
`'
`'
`'
`•
`'
`'
`'
`•
`
`..........................................................................................
`
`........................................
`
`'
`
`�
`
`
`• •
`
`601
`
`RESIDUAL PSEUDORANGE
`
`FROM UBS RECEIVER
`
`PUBS-A PUBS
`
`_ ........................................................
`
`'
`•
`•
`•
`•
`l
`•
`•
`•
`•
`'
`• •
`I •
`' •
`' •
`' • , I
`' •
`' •
`' '
`' '
`' '
`' '
`
`.
`
`'
`
`NCO
`LOOP
`CODE .
`
`&
`�
`
`-
`
`j I
`
`658
`
`.
`
`' •
`' •
`' •
`' '
`' •
`' '
`•
`' •
`' •
`' •
`• •
`• '
`' •
`' '
`' '
`' '
`' '
`' '
`• •
`• •
`• •
`• •
`• •
`• •
`• •
`•
`•
`.l !
`• '
`' '
`' '
`' '
`' '
`•'
`'
`' '
`' '
`' '
`' '
`' '
`' '
`' '
`' '
`• •
`• •
`• '
`
`
`
`
`
`''•
`
`pGPS
`
`"'
`
`I
`
`250
`
`DETECTOR
`
`'
`
`•
`
`
`
`''
`
`•
`
`•
`
`I
`I
`
`CODE
`GPS
`
`I
`I
`I
`
`pGPS-'hes
`
`A
`
`..LOOP
`CODE
`
`'
`
`RECEIVED
`
`'
`'
`•
`•
`•
`•
`'
`•
`'
`'
`•
`'
`'
`•
`•
`•
`•
`•
`•
`•
`•
`'
`•
`•
`•
`•
`•
`•
`•
`•
`•
`'
`'
`'
`'
`'
`'
`•
`'
`'
`•
`•
`•
`•
`•
`•
`•
`l
`'
`•
`'
`•
`'
`•
`'
`•
`•
`•
`•
`•
`•
`•
`•
`•
`•
`•
`•
`........
`
`�
`
`648
`
`I
`
`_ ........
`
`Cisco v. TracBeam / CSCO-1006
`Page 18 of 39
`
`

`

`1
`
`5,774,829
`
`BACKGROUND OF THE INVENTION
`
`
`
`2
`RF-based system intermittently "resets" the current position
`
`
`
`NAVIGATION AND POSITIONING SYSTEM
`
`
`
`
`estimate in order to eliminate the positional bias internally
`AND METHOD USING UNCOORDINATED
`
`
`
`
`accumulated by all dead-reckoning systems. The interval
`
`BEACON SIGNALS IN CONJUNCTION
`
`
`between successive resets of position depends upon the
`WITH AN ABSOLUTE POSITIONING
`
`
`"fix" the 5 capability of the RF-based system to accurately
`
`SYSTEM
`
`
`
`
`position of the mobile unit, and may vary from a number of
`
`
`
`seconds to tens of minutes. As the period between each such
`The present invention relates generally to navigation and
`
`
`
`
`
`
`
`
`position fix becomes longer, as often occurs upon entering
`
`
`
`positioning systems in which an object or user at an
`
`
`
`dense metropolitan areas, the mean accuracy of the position
`
`
`
`
`unknown location receives broadcast signals from several
`
`
`
`
`system is corre­dead reckoning 10 estimate produced by the
`
`
`sources and uses information derived therefrom to determine
`
`spondingly degraded.
`
`
`
`
`the object's or user's current position. More particularly, the
`In one aspect of the present invention, an RF-based
`
`
`
`
`
`
`
`present invention relates to a positioning system which uses
`
`
`
`positioning system is combined with a positioning system
`
`
`
`uncoordinated beacon signals from commercial radio broad­
`
`
`
`
`reliant upon the 19 KHz pilot signals transmitted by com-
`
`
`
`casts in conjunction with synchronized signals from an
`
`
`
`
`Unlike GPS signals FM stations. 15 mercial broadcast stereo
`
`
`
`absolute positioning system to enable a highly accurate
`
`and other RF positioning signals of relatively high carrier
`
`position determination.
`
`
`
`frequency, FM pilot signals are generally not significantly
`
`
`
`impeded by the nearby presence of building or other large
`
`
`obstructions. This makes such FM pilot signals ideal can-
`
`
`
`Most of the well known prior art radio frequency (RF)
`
`
`
`
`inwithin urban environments, 20 didates for use in navigation
`
`
`
`navigation and positioning system, such as LORAN,
`
`
`
`
`which the performance of conventional RF-based systems
`
`
`
`GLONASS, TRANSIT, and GPS use special transmitters,
`
`
`
`tends to be degraded. In the United States, there are nearly
`
`
`
`
`
`
`either orbiting the earth or land-based, dedicated solely to
`
`
`
`
`5000 Commercial Broadcast FM radio stations configured to
`
`
`
`the positioning system. Great efforts are made in such
`
`
`
`broadcast in Stereo, and the FCC requires all stations so
`
`
`
`
`
`systems to synchronize the transmitters in these systems so
`
`
`
`
`signal. pilot sub-carrier 25 configu red to broadcast a 19 KHz
`
`
`
`
`
`that the timing of the signals reaching a user at any location
`
`
`
`
`The maximum allowed deviation is ±2 hertz. Generally the
`
`
`
`
`on the earth's surface can be calculated with a known level
`
`
`
`
`
`rate of frequency drift has been found to be much less than
`
`
`
`of accuracy. These types of prior art systems generally
`
`
`0.1 hertz per day. In any case, the transmitters used by the
`
`
`
`require huge capital investments, often government
`
`
`present invention are free, which makes the positioning
`
`
`
`
`subsidized, because the transmitters and their control sys­
`
`
`
`
`
`to inexpensive relatively 30 system of the present invention
`
`
`tems are very complex and expensive.
`implement.
`
`
`
`
`The performance of existing RF navigation systems, such
`Two U.S. patents which describe "delta-position" systems
`
`
`
`as GPS and LORAN, can be significantly compromised in
`
`
`
`using commercial radio broadcast transmissions are U.S.
`
`
`
`
`terrestrial environments due when local obstructions (e.g.,
`
`
`Pat. Nos. 4,054,880 (Dalabakis et al.) and 3,889,264
`
`
`
`large buildings) disrupt signal reception. These so-called
`
`
`
`
`using describe systems 35 (Fletcher). These prior art patents
`
`
`
`"urban canyon" difficulties associated with using GPS,
`
`
`
`three spaced-apart radio signals, each of which is an inde­
`
`
`LORAN and other absolute positioning systems within
`
`
`
`
`pendent AM radio signal. The systems typically have a
`
`
`metropolitan environments have been described elsewhere.
`
`
`
`
`vehicle carried mobile receiver, with a separate tuner for
`
`
`See, for example, the paper by W. Kao, Integration
`
`
`each station, and a second receiver at a fixed, known
`of GPS
`
`Proceedings of
`
`
`
`
`of count "zero crossings" 40 position. Basically, these systems
`
`
`and Dead Reckoning Navigation Systems;
`
`
`the 1991 Vehicle Navigation and Information Conference
`
`
`
`
`timing signals, each of which indicates that the user has
`
`
`(YINS 1991). See also the article by J. Fanton,
`
`
`
`
`
`moved a certain distance from his previous location. Thus,
`Urban
`
`
`
`
`Positioning with GPS: A mobile communications field mea­
`
`
`
`if the user needs to know his current position, the user needs
`
`GPS World; Vol. 4, No. 7 (July 1993).
`
`
`
`
`
`to first specify his starting position. A fixed position receiver
`
`surement application;
`
`
`
`
`and that drift the transmitters, 45 detects frequency drift of
`
`
`
`
`In an attempt to overcome these difficulties, hybrid sys­
`
`
`
`information is used to adjust and coordinate the zero cross­
`
`
`tems have been developed which incorporate both an
`
`
`ing counts made by the mobile receivers.
`
`
`
`
`RF-based, absolute positioning system (e.g., GPS) and a
`
`
`
`
`relative positioning system. The relative, or "dead­
`
`
`
`These are "delta-position" systems because they deter­
`
`
`
`reckoning", positioning system may be comprised of an
`
`
`
`mine only the distance and direction traveled by a mobile
`
`
`
`
`
`inertial sensor unit which includes, for example, a rate gyro,
`
`50 user from any particular starting point. Neither Dalabakis
`
`
`
`
`one or more multiple axis accelerometers, an odometer, and
`
`
`
`
`nor Fletcher actually determines the position of the mobile
`
`an inclinometer. Unfortunately, inertial units of this type
`
`
`
`
`user, and in fact such a determination is not possible using
`
`
`
`tend to become less accurate with extended use. Moreover,
`
`
`
`
`the Dalabakis or Fletcher systems because these systems do
`
`
`
`
`such inertial units are subject to disorientation upon expe­
`
`
`
`not have the ability to determine the phases of the transmit-
`
`
`
`riencing arbitrary rotation of the type which frequently
`
`
`
`
`since only zero crossings are 55 ted radio signals. Furthermore,
`
`
`
`
`occurs during normal handling of portable units. The dead­
`
`
`
`counted, the positioning accomplished by these systems
`
`
`
`
`reckoning system may further include a database of local
`
`
`
`
`have "granularity", which in the case of the systems dis­
`
`
`
`
`
`streets, which serves to constrain the positional estimate to
`
`
`
`
`closed in these two patents is on the order of thirty meters.
`
`
`
`
`navigable thoroughfares. By monitoring the outputs of the
`
`
`
`
`Like Dalabakis and Fletcher, the present invention uses
`
`
`
`
`
`devices within the inertial sensor unit, the system processor
`
`
`
`
`60 spaced apart, commercial radio signals. The present inven­
`
`
`
`
`functions in a "dead-reckoning" mode to produce estimates
`
`
`
`tion may also use a fixed position receiver to help the mobile
`
`
`
`of position and velocity. An exemplary hybrid navigation
`
`
`
`units determine their position. However, the present
`
`
`
`system of this type is described in, for example, U.S. Pat.
`
`
`
`
`
`invention, unlike Dalabakis and Fletcher, determines the
`
`
`
`
`No. 5,311,195, entitled Combined Relative and Absolute
`
`
`
`
`user's position without need for any starting point
`
`
`
`Positioning Method and Apparatus, issued May 10, 1994.
`
`
`
`65 information, and determines such positions with a high
`
`
`
`
`degree of accuracy. To do this, the fixed position receiver not
`
`
`
`During operation, the dead-reckoning system produces a
`
`
`
`
`
`
`short term estimate of position, while the GPS or other only determines frequency drift, it also determines the
`
`Cisco v. TracBeam / CSCO-1006
`Page 19 of 39
`
`

`

`5,774,829
`
`4
`3
`the beacon signals, determines the relative phases of the
`
`
`
`
`
`
`
`relative phases of the various beacons with a very high
`
`
`
`beacon signals, and broadcasts data representing these rela­
`
`
`
`degree of accuracy (e.g., within about 0.02 degrees, or
`
`
`
`tive phases. The uncoordinated beacon signal receivers
`equivalently, within about 0.00035 radians) using a digital
`
`
`
`
`
`
`
`
`within each mobile unit recover these broadcast values, and
`
`phase-locked loop. Using this relative phase information, the
`
`
`
`
`
`5 receive beacon signals from at least three radio transmitters
`
`commercial radio signal beacons are transformed, in
`
`
`as described above.
`
`essence, into coordinated beacon signals with well defined
`
`
`
`
`phase relationships. As a result, the position of the mobile
`
`
`In embodiments including a fixed position observer, each
`
`
`
`
`
`users can be computed from the radio signals received by the
`
`
`
`uncoordinated beacon signal receiver computes the location
`
`mobile user with an accuracy of about ±10 meters in the
`
`
`of the mobile unit in which it is disposed based on (A) the
`
`
`
`general case, and with appreciably greater accuracy in the 10
`
`
`
`relative phase and frequency data broadcast by the fixed
`
`absence of multipath.
`
`
`
`
`
`
`position observer, (B) the detected beacon signal phases, and
`
`
`
`(C)the known positions of the beacon signal transmitters
`SUMMARY OF THE INVENTION
`
`
`and the fixed observer. In other embodiments, the phase
`
`
`
`
`information generated by each uncoordinated beacon signal
`
`
`In summary, the present invention is a navigation system
`
`
`in which an uncoordinated beacon positioning system (UBS) 15 receiver
`
`
`could be transmitted to a computer at a remote
`
`
`
`
`location, so that the position computations for many mobile
`
`
`
`is used in conjunction with an absolute positioning system
`
`(APS). The uncoordinated beacon positioning system
`
`
`units could be performed at a central data processing station.
`
`
`
`The position computations may occur in a timely manner, or
`employs a multiplicity of transmitters, at known or other­
`
`
`
`
`they may be deferred and stored.
`
`
`
`
`wise discernible locations, at least some of which transmit a
`
`beacon signal of approximately the same frequency or 20
`
`
`Even though the uncoordinated beacon positioning sys­
`
`
`
`
`
`
`
`repetition rate. The phases of the beacon signals are at least
`
`
`
`
`tem determines the mobile receiver's absolute position with
`
`
`partially un-synchronized with the phases of the beacon
`
`
`
`
`respect to a defined coordinate system, this uncoordinated
`
`
`signals of the other transmitters.
`
`
`system does not require synchronization of clocks or time
`
`
`
`
`values between the mobile receivers and the fixed observer
`
`
`
`Within each mobile unit, separate receivers are provided
`APS 25
`
`
`
`or any other time base. Rather, time is treated by the mobile
`
`
`for receiving these beacon signals and for receiving
`
`
`receiver as an independent variable, much like the mobile
`
`
`
`signals. At least three of the beacon signals are received by
`
`
`
`unit's spatial coordinates (e.g., x, y, and z). Using the
`
`
`
`
`the UBS receiver, which includes phase detection circuitry
`
`
`
`method of the present invention, relative time offsets
`
`
`
`for detecting beacon signal phase. The absolute positioning
`
`
`
`system (APS) receiver is disposed to receive the APS
`
`
`
`
`between the fixed observer and the mobile receiver, as well
`30
`
`
`as the mobile receiver's absolute position, are determined
`
`
`
`
`signals, and to estimate an initial position of the mobile unit
`
`
`and maintained by the mobile receiver at a high level of
`
`
`
`therefrom. In a preferred embodiment, a mobile unit pro­
`accuracy.
`
`
`
`
`cessor computes a current location of the mobile unit based
`
`
`on: (i) the detected phases of at least three of said beacon
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`signals, and (ii) the estimate of mobile unit initial position.
`35
`
`
`
`In another aspect of the invention, the mobile unit pro-
`Additional objects and features of the invention will be
`
`
`
`
`
`
`
`
`cessor is programmed to determine the uncertainty of loca­
`
`
`
`
`more readily apparent from the following detailed descrip­
`
`
`
`tion information provided by the UBS and APS receivers. In
`
`
`
`tion and appended claims when taken in conjunction with
`
`
`
`
`this embodiment the current location of the mobile unit may
`
`the drawings, in which:
`
`
`
`
`be updated by selecting the location estimate having asso-40
`FIG. 1 schematically depicts a positioning system in
`
`
`
`
`ciated therewith the least amount of location uncertainty.
`
`
`accordance with the present invention.
`
`
`
`Alternately, each location estimate may be weighted based
`
`
`FIG. 2A is a block diagram of a mobile unit which
`
`
`
`on its uncertainty, and the two weighted location estimates
`
`
`
`includes an uncoordinated beacon receiver and an absolute
`
`combined to yield a composite estimate.
`
`positioning system receiver.
`
`
`In yet another embodiment of the present invention,
`45
`FIG. 2B is a more detailed block diagram of the uncoor­
`
`
`
`
`
`certain correction information is exchanged between the
`
`
`
`
`
`
`dinated beacon receiver within the mobile unit.
`
`UBS and APS receivers as a means of improving position
`
`
`
`
`
`
`
`FIG. 3 is a flowchart of the main control routine of a
`estimation accuracy. In this embodiment the mobile unit
`
`
`
`mobile receiver unit.
`
`includes an estimator operative to compute an estimate of
`
`
`
`
`mobile unit position on the basis of selected pseudorange
`
`
`
`
`
`FIG. 4 is a block diagram of a digital phase detector for
`50
`
`measurements from the UBS and APS receivers. In a par­
`
`
`
`use in both mobile receiver units and a fixed position
`ticular implementation, the estimator includes a Kalman
`
`
`
`
`observer unit.
`
`filter configured to process residual pseudorange informa­
`
`
`
`FIG. 5 is a circuit diagram of a power estimator circuit.
`
`
`
`
`tion provided by the UBS and APS receivers.
`
`
`
`FIG. 6 is a circuit diagram of a numerically controller
`
`
`
`The beacon signal transmitters may comprise, for
`55 oscillator (NCO).
`
`
`
`example, a multiplicity of commercial radio signal
`
`
`
`FIG. 7 is a circuit diagram of a phase error accumulator
`
`
`
`transmitters, at known fixed locations, each of which trans­
`circuit.
`
`
`mits a beacon signal having a phase that is unsynchronized
`FIG. 8 is a block diagram of a loop filter routine executed
`
`
`
`with the phases of the beacon signals of the other transmit­
`
`by the CPU in mobile receiver units, and also by the CPU
`
`
`
`ters. All of the beacon signals have a frequency which is 60
`in a fixed position observer unit.
`
`
`
`
`approximately equal to a predetermined target frequency. In
`
`
`
`FIG. 9 is a block diagram of a loop filter subroutine.
`
`the preferred embodiment, the beacon signals are 19 KHz
`
`
`FM
`
`
`
`FIG. 10 is a block diagram of the phase master accumu­
`
`
`
`
`pilot tones generated by Commercial Broadcast stereo
`lator software routine.
`stations.
`
`
`
`FIG. 11 is a block diagram of a low pass filter routine.
`
`
`The uncoordinated beacon positioning system may also
`65
`
`
`
`
`include a first receiver, known as the fixed position observer,
`
`FIG. 12 is a flow chart of the main routine for the fixed
`
`
`
`positioned at a known location. The fixed observer receives
`
`observer unit.
`
`Cisco v. TracBeam / CSCO-1006
`Page 20 of 39
`
`

`

`5,774,829
`
`6
`5
`FIG. 13 is a block diagram of a mobile unit, a fixed
`
`
`signal. Under certain conditions, the GPS signals from the
`
`
`
`
`
`
`satellites 10 may be used for determining the position of a
`
`
`
`position observer unit, and an exemplary GPS system in
`
`mobile unit on or near the earth. The orbits of the GPS
`
`
`which an initial time bias between the mobile and fixed
`
`
`
`
`
`satellites are arranged in multiple planes, in order to maxi-
`
`
`
`
`observer units is established on the basis of timing pulses
`
`
`
`
`from at least be received s mize the likelihood that signals can
`
`provided by the GPS system.
`
`
`
`four GPS satellites at any arbitrary point on or near the earth.
`
`
`FIG. 14 is a block diagram of a mobile unit which
`
`
`
`It is known, however, that the capability of the GPS system
`
`
`
`
`
`includes a navigation processor configured to provide an
`
`to provide accurate position informat