United States Patent c191
`Geier
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US005202829A
`5,202,829
`[I I] Patent Number:
`[45] Date of Patent: Apr. 13, 1993
`
`[54] EXPLORATION SYSTEM AND METHOD
`FOR HIGH-ACCURACY AND
`HIGH-CONFIDENCE LEVEL RELATIVE
`POSITION AND VELOCITY
`DETERMINATIONS
`Inventor: George J. Geier, Santa Clara, Calif.
`[73] Assignee: Trimble Navigation Limited,
`Sunnyvale, Calif.
`
`[75]
`
`[21] Appl. No.: 713,438
`Jun. 10, 1991
`[22] Filed:
`Int. CJ.s ................................................ GOlS 5/02
`[51]
`[52] U.S. CI •.................................... 364/449; 364/459;
`342/357; 342/457
`[58] Field of Search ............... 364/443, 449, 457, 459;
`73/178 R; 342/357, 358,457
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,445, 118 4/1984 Taylor et al. ....................... 342/357
`4,613,864 9/1986 Hofgen ................................ 342/357
`4,646,096 2/1987 Brown ................................. 342/358
`4,751,512 6/1988 Longaker ............................ 342/457
`4,814,711 3/1989 Olsen et al. ......................... 364/449
`4,894,662 1/1990 Counselman ........................ 342/357
`5,017,926 5/1991 Ames et al. ......................... 342/357
`5,099,245 3/1992 Sagey .................................. 342/357
`Primary Examiner-Gary Chin
`
`Attorney, Agent, or Firm-Thomas E. Schatzel
`[57]
`ABSTRACT
`An embodiment of the present invention is a shipboard
`GPS positioning system having data links to outlying
`tailbuoys equipped with respective GPS receivers. On
`ship, an Intel 386-based microcomputer system collects
`data from various ship's equipment including the ship's
`GPS receiver and data from the several tailbuoy units.
`A computer-implemented process located in the mi(cid:173)
`crocomputer system controls the following processes.
`Periodically each GPS receiver produces updated
`pseudo ranges (PRs) and these are time-tagged. The
`time-tagged PRs for the ship are aligned according to
`their time tags with their counterpart PRs from the
`tailbuoys. The raw PRs are then passed through a Kal(cid:173)
`man matjiematical filter to produce filtered pseudo(cid:173)
`ranges (f>Rs). A position soluti9_n is then attempted for
`each GPS receiver using the Pih. The filters provj4e
`statistical data that is used to rate the quality of each PR
`in a weighted least squares solution process. Special
`measures are included to provide quality control/qual(cid:173)
`ity assurance, including the use of error ellipses on the
`display to present a graphic indication of expected solu(cid:173)
`tion accuracy, and the use of real time fault detection,
`isolation, and correction algorithms when redundant
`satellite information is available.
`
`10 Claims, 8 Drawing Sheets
`
`r:-
`
`-
`
`-
`
`-
`
`-
`
`r--
`1
`I
`- SV MEASUfftMENTS
`~
`I
`56
`I
`I
`I
`I
`I
`I
`I
`I
`TAILBUOY SUBSYSTEM
`I
`(TBS)
`f- - - - - - - - - - - - _.J
`I
`I
`I
`I
`
`GPS
`RECEIVER
`
`WATERPROOF
`ENCLOSURE
`
`RADIO/MODEM
`
`CPU
`
`L!Hl~~R~SUBSY~EMJSBSl _______ J
`
`.:!".!=~.!=~~~~
`
`Apple Inc. Exhibit 1009 Page 1
`
`

`
`U.S. Patent
`
`Apr. 13, 1993
`
`Sheet 1of8
`
`5,202,829
`
`10
`
`/
`
`Fig .. 1
`
`- - - - SHIPBOARD
`PROCESSING
`SUBSYSTEM
`
`r:-
`
`-
`
`-
`
`54
`
`GPS
`RECEIVER
`
`-
`
`-
`
`RADIO/MODEM
`
`RADIO/MODEM
`
`r--
`1
`I
`- sv MEAsuR1MENTS
`~
`GPS
`;
`56
`SENSOR
`I
`. - - -4 - - - - ' -
`I
`I
`I
`WATERPROOF
`I
`ENCLOSURE
`I
`I TAILBUOY SUBSYSTEM
`I
`(TBS)
`t-------------.J
`I .,
`I
`I
`
`L!HIPB~R~SUBSYSTEMJSBS> _______ J
`
`~t:_::~~i.~~
`
`Fig_2
`
`Apple Inc. Exhibit 1009 Page 2
`
`

`
`U.S. Patent
`
`Apr. 13, 1993
`
`Sheet 2 of 8
`
`5,202,829
`
`r 54
`
`·SHIP CMR
`·EPHEMERIS
`• IONO
`• DIF'L DATA
`• BINPOS
`
`COM I
`
`SPARE COM2
`
`I" 58
`
`l/03
`
`BINPOS
`
`TAI LB UOY
`I/04 SOLUTION_
`-
`DATA
`
`PS/2 MOUSE
`
`I
`I
`
`SPARE
`
`DEDICATED
`MOUSE PORT
`l/01
`
`TAILBUOY CMR:
`
`1/02
`
`l/05
`
`RAW DATA
`
`SELECTED
`SOLUTION
`
`QC/QA DATA
`
`8 CHGPS
`
`1PPS
`
`SHOT POINT
`CONTACT
`CLOSURE
`
`,_§0
`
`i"\68
`
`SHOT
`POINT
`BOARD
`
`SHIP NAV.
`COMPUTER
`
`USER
`SUPPLIED
`RECORDING
`SYSTEM
`
`SHIP DATA
`ACQUISITION
`SYSTEM
`
`\60
`
`RECEIVER ~ DATA SELECTED
`10 Volo
`
`I/06
`I/07
`I/08
`
`}SPARES
`
`Fig_3
`
`« TBTRACK GPS Toilbuoy Trockino System»
`
`I
`Om
`
`I
`5
`
`I
`
`...-Error Elli~se Of Toil buoy
`Relative o Ship
`Toilbuoy Position
`
`II
`11 05/29 21:56:16
`~[f!ill D
`Lal
`Lon
`ASll
`COG
`SOG
`lFlndllTrackl~O
`
`j
`
`Absolute Ship Position
`
`Error Ellipse Of Absolute
`Ship Position
`
`J
`
`I
`18
`I 1 Filter Reset
`101
`illlVsl llMrklliU) 8
`To
`f Buoy I
`Lat 3723.65531N
`Lon 122 02.2932W
`Alt
`·32m
`Rng Sm
`Brg 21T
`D ADF 0111
`0 21:54:5f>Of: No Time-Aligned Ship Doto Available
`D 21: 54: 51>01: No Time-A~g~ed Ship Dato Available D I IPau1lllE1it I lilJDO I
`21:55:21>0f:SVt5 SV
`AVAIL TO SHIP
`II Refresh 1II001 Colors
`j [zoomlnllZoomoutlD DD DD DI Monitor
`II
`Fig_l4
`
`Apple Inc. Exhibit 1009 Page 3
`
`

`
`U.S. Patent
`
`Apr. 13, 1993
`
`Sheet 3 of 8
`
`5,202,829
`
`RE-INIT
`
`BEGIN
`
`102
`INPUT INITIAL
`SHIP POSITION
`
`FILL USER_CTL
`WITH PARAMETERS
`
`LOOP
`
`FILL SHIP_IN WITH
`MEASUREMENT DATA
`108
`
`106
`
`GPS_SHIP_CALC
`
`110
`MAINTAIN STACK
`OF SHIP_OUTs
`
`FILL BUOY_IN WITH
`MEASUREMENTS DATA
`
`112
`
`SYNCHRONIZE BUOY_IN
`WITH SHIP_OUT DATA
`
`114
`
`119
`
`y
`
`SYNC SHIP POSITION
`AND SEPARATION
`VECTOR TO SHOT
`
`DRIVE TBTRACK DISPLAY
`
`y
`
`N
`
`Fig_4
`
`Apple Inc. Exhibit 1009 Page 4
`
`

`
`U.S. Patent
`
`Apr. 13, 1993
`
`Sheet 4 of 8
`
`5,202,829
`
`108
`
`\
`
`GPS_SHIP_CALC
`210
`COLLECT SV DATA
`
`280
`
`\
`
`POSITION/VELOCITY UPDATE
`
`TEST FOR DIFFERENTIAL
`CORRECTIONS
`
`220
`CORRECT AND SYNC
`MEASUREMENT DATA
`230
`SV CODE/CARRIER
`FILTERING
`
`250
`
`COMPENSATE
`
`PROPOGATE PRIOR
`SOLUTION AND COFACTOR
`TO REFERENCE TIME
`270
`TEST D.O. P. HOLE
`280
`
`POSITION AND
`VELOCITY UPDATE
`
`RETURN
`Fig_5
`
`COMPUTE COFACTOR MATRIX
`FOR SOLUTION UPDATES.
`INCLUDE CONSTRAINED
`ALTITUDE, IF APPLICABLE
`
`282
`
`283'
`COMPUTE FDIC
`---- COFACTOR
`MATRIX
`
`285
`PERFORM
`FDIC TESTS
`
`PERFORM NAVIGATION
`UPDATE IF APPROPRIATE
`
`RETURN
`Fig_6
`
`Apple Inc. Exhibit 1009 Page 5
`
`

`
`U.S. Patent
`
`Apr. 13, 1993
`
`Sheet 5 of 8
`
`5,202,829
`
`116
`
`\
`
`GPS_BUOY_CALC
`
`CORRECT SV DATA
`AND SCREEN BAD
`DATA OUT
`
`CORRECT
`MEASUREMENT DATA
`(330
`SYNC MEASUREMENT
`DATA TO REF. TIME
`
`SV CODE/CARRIER
`FILTERING
`
`PROPOGATE
`COFACTOR MATRIX
`
`' r310
`' r320
`'
`• (340
`• r350
`' r360
`
`TEST FOR
`D.O.P. HOLE
`
`t370
`•
`COMPUTE
`SEPARATION
`VECTOR
`SOLUTION
`
`r375
`'
`NON-LINEAR
`CORRECTION
`
`+
`RETURN
`Fig_7
`
`375
`
`\
`
`NON-LINEAR CORRECTION
`SUB-ROUTINE
`
`FIND ~ IN ECEF FRAME
`d ECEF _ CECEF d ENV
`-
`-
`ENV
`-
`ENVT
`ECEF
`WHERE: CENV =CECEF
`
`' r402
`'
`
`r404
`FORM LOS VECTOR BUOY-+SAT
`
`Rbi =l~i - ~s + !ti
`Ubi ·l~i -~s + ~J/Rbi
`COS<ri •~bi• ~si
`
`' r406
`
`-
`-
`CORRECTED PR DIFFS
`U-COSCXt) Rbt
`u-cosa:2> Rb2
`- - •
`•
`•
`...
`-
`u-cosa" > RbN
`
`APR'•APR-
`
`'
`
`RETURN
`Fig_B
`
`Apple Inc. Exhibit 1009 Page 6
`
`

`
`U.S. Patent
`
`-
`Apr. 13, 1993
`
`Sheet 6 of 8
`
`5,202,829
`
`230' CODE/CARRIER FILTER
`~ (THIRD ORDER TYPE}
`
`PROPAGATE FILTERED
`PSEUDO RANGE
`
`PROPAGATE
`MULTI PATH STATE
`
`DO STATE TRANSITION
`MATRIX
`
`PROCESS NOISE
`COVARIANCE MATRIX
`
`' r4IO'
`• r411'
`' c412'
`' t414'
`• c416'
`
`............
`'
`TEST FOR FAILED PR
`MEASUREMENT
`
`(SECOND ORDER TYPEJ
`
`230 ' CODE/CARRIER FILTER
`• r410
`
`PROPAGATE FILTERED
`PSEUDO RANGE
`t
`(412
`DO STATE TRANSITION
`MATRIX
`
`+
`
`(414
`
`r416
`
`PROCESS NOISE
`COVARIANCE MATRIX
`t
`PROPAGATE
`COVARIANCE MATRIX
`
`FORM RESIDUAL WITH
`MEASURED PR
`
`4201 , _______
`' (418
`' r422
`MULTIPATH •
`
`TEST FOR EXCESSIVE
`
`r424
`COMPUTE MEASUREMENT
`GRADIENT VECTOR
`
`t
`
`(426
`COMPUTE STATE
`CORRECTIONS
`
`' r428
`' ,430
`
`CORRECT TERMS
`
`UPDATE COVARIANCE
`MATRIX
`
`~
`RETURN
`Fig_9
`
`PROPAGATE
`COVARIANCE MATRIX
`~
`,418'
`FORM RESIDUAL WITH
`
`',, ____ ,,, Fig_JQ
`
`MEASURED PR '
`
`' ' ' ' ' ' '
`
`Apple Inc. Exhibit 1009 Page 7
`
`

`
`U.S. Patent
`
`Apr. 13, 1993
`
`Sheet 7 of 8
`
`5,202,829
`
`250
`
`\
`
`FIND SOLUTION
`REFERENCE TIME
`r4BO
`•
`COMPUTE REFERENCE TIME
`AS AVERAGE OF AVAILABLE
`MEASUREMENT TESTS
`t REF= - L ti
`I M
`M •
`I= I
`
`r4B2
`
`TEST THAT SUFFICIENT NUMBER
`OF MEASUREMENTS AVAILABLE
`M<3, BYPASS UPDATE
`M<4, SET ALTITUDE HOLD FLAG
`
`r4B4
`
`"'
`SYNCH EACH PR TO REF. Tl ME
`At= t~- tREF
`PRi = PRi + PRRi • 6t
`
`r486
`TEST IF DIFFERENTIAL CORRECTION SELECTED
`TEST IF CORRECTION DATA AVAILABLE
`FOR MINIMUM NUMBER OF SV APPLY
`DIFFERENTIAL CORRECTIONS TO AVAILABLE
`MEASUREMENTS
`
`~
`RETURN
`
`Fig_tl
`
`Apple Inc. Exhibit 1009 Page 8
`
`

`
`U.S. Patent
`
`Apr. 13, 1993
`
`Sheet 8 of 8
`
`5,202,829
`
`COMPUTE COFACTOR MATRIX
`
`282 ""'
`
`504
`
`COMPUTE RESIDUALS
`
`FDIC
`
`285
`550
`~
`COMPUTE NORMALIZED
`FAULT VECTOR
`
`552
`DO FAULT DETECTION
`554
`
`DETERMINE
`THRESHOLD FOR D
`556
`COMPUTE m VALUES
`
`558
`
`y
`
`509'
`
`DO ISOLATION/
`RELIABILITY TESTS
`
`RECOMPUTE f
`
`y
`
`564
`
`512
`
`SET FLAG
`
`DO UPDATE
`
`RETURN
`Fig_13
`
`521'
`
`COLLECT RESIDUALS
`
`COMPUTE VELOCITY
`
`CORRECT CURRENT
`ESTIMATES
`
`526
`
`RETURN Fig_12
`
`Apple Inc. Exhibit 1009 Page 9
`
`

`
`1
`
`5,202,829
`
`EXPLORATION SYSTEM AND METHOD FOR
`HIGH-ACCURACY AND HIGH-CONFIDENCE
`LEVEL RELATIVE POSITION AND VELOCITY
`DETERMINATIONS
`
`2
`SUMMARY OF THE PRESENT INVENTION
`It is therefore an object of the present invention to
`improve systems and methods for the simultaneous
`5 position and/or velocity determinations of a plurality of
`ground-based units where the ground-based units' posi-
`tions relative to one another and their absolute positions
`BACKGROUND OF THE INVENTION
`l. Field of the Invention
`need to be determined for the same instant, and where
`the ground-based units have signal acquisition of a com-
`The invention relates generally to global positioning
`system (GPS) devices and more particularly to systems 10 mon set of GPS satellites.
`and methods for the simultaneous position and/or ve-
`Briefly, a preferred embodiment of the present inven-
`locity determinations of a plurality of ground-based
`tion is a shipboard system with data links to outlying
`units where the ground-based units' positions relative to
`tailbuoys equipped with respective GPS receivers. On
`one another and their absolute positions need to be
`ship, an Intel 386-based microcomputer system collects
`determined for the same instant, and where the ground-
`data from various ship's equipment including the ship's
`based units have signal acquisition of a common set of
`GPS receiver and data from the several tailbuoy units.
`GPS satellites. (The term "ground-based" includes any-
`A computer-implemented process located in the mi-
`where on Earth, e.g., undersea, on-the-sea, on-the-land,
`crocomputer system controls the following processes.
`and in-the-air.)
`20 Periodically each GPS receiver produces updated
`2. Description of the Prior Art
`pseudo ranges (PRs) and these are time-tagged. The
`time-tagged PRs for the ship are aligned according to
`The United States of America Department of De-
`fense has placed in orbit a group of satellites, as part of
`their time tags with their counterpart PRs from the
`a global positioning system (GPS), that can be used by
`tailbuoys. The raw PRs are then passed through a Kal-
`civilians and the military alike to get automated and 25 man mathematical filter to produce filtered pseudo-
`highly-accurate earth position coordinates on easy to
`ranges (PRs). A position solution is then attempted for
`read digital displays. Determining where you are has
`each GPS receiver using the PRs. The filters provide
`been a particular problem for seafarers for thousands of
`statistical data that is used to rate the quality of each PR
`years. Now, GPS_ enables small_ sailb~~t owners. a~d
`in a weighted least squares solution process.
`even combat sol~1ers to get their pos1t10n~ to w1thm 30 An advantage of the present invention is that it pro-
`several meters usmg handheld i:iortabl~ equipment_.
`vides an improved system and method of positioning.
`Ocean and _s7a-bottom surveymg eq~1pme~t routmely
`Another advantage of the present invention is that
`use earth pos~t1ons to ge~erate geologic stu_d1es of earth
`error ellipses on computer displays rapidly convey sta-
`s~rata. A typical ~eolog1c survey method mvolves set-
`tistical information to users about the quality of the
`tmg off an explosive charge. that creates. a shockwave 35 position information being viewed.
`and t_hen :ecords the reflection~ that arnve at several
`Another advantage of the present invention is that
`locat1~ms m the general area. U~mg well~known survey
`statistical error information on each satellite's pseudo-
`techmques, the refl_ected_soun~ mformation can be ana-
`range data is weighed into a final position solution.
`lyzed, and three-dimensional images of t_he structures
`Another advantage of the present invention is that
`can be rec_o_nstructed by computer and displa~ed on a 40 pseudo-ranges from one or more satellites having the
`~reen. Cnucal to the analyses are the respective l~a-
`least statistical confidence level can be isolated and
`t1ons of the source of the shockwave and the locat10ns
`. .
`.
`.
`.
`·
`·
`· d" "d 1 1.
`Th
`t
`d
`removed from a final position solution 1f sufficient satel-
`f h
`o t e m 1v1 _ua 1stenmg stations.
`e c?mpu ~r. e-
`lites are tracked.
`pends on havmg extremely accurate relative pos1t1ons
`A
`th
`d
`t
`f th
`t ·
`·
`· h
`· ·
`f
`h
`.
`no er a van age o
`e presen mvent1on 1s t at
`for the above. The absolute pos1t1on o sue a group 1s 45
`1 .
`fli
`· 1 "d
`th
`·
`be
`"fi d
`h
`1
`mudtfi1·
`e ective Y 1 ent1 ie as sue
`more important to the users, rather than the computer.
`a dsigna s can
`· ·
`an 1 tere out.
`d
`·
`·
`1
`The abso ute pos1t1ons are use
`to pmpomt structures
`.
`J?iese a_nd ot~er objects and advanta~es of the pres-
`on the map, so that they may be visited again.
`en~~nvent~~ ~dlhno dou~t ~cOI_ne obv~ouhs tofi t
`os~ of
`Previous systems have made absolute determinations
`1? t. e art a ter avmg rea
`of where the respective groups members are, and then 50 or 1?ary s
`
`t e o ?wmg
`de~led d~scnption . of the !?referred . embodtments
`solved from that what the relative orientations are.
`Each GPS receiver is usually able to acquire the signal
`which are Illustrated m the vanous drawmg figures.
`of several GPS satellites at once. Normally three range
`IN THE DRAWINGS
`measurements are required to triangulate a location, but
`four are actually needed with GPS to correct local 55
`clocks to GPS system time. The individual distance legs
`from each GPS satellite to each GPS receiver are there(cid:173)
`fore called pseudo ranges (PR). Therefore, for four SVs
`and two GPS receivers, eight PRs will be generated.
`The present invention solves the problem of fmding 60
`the relative distance between GPS receivers by time(cid:173)
`tagging candidate PRs, aligning like tagged PRs from
`respective GPS receivers, and subtracting the differ(cid:173)
`ence between corresponding PRs to arrive at highly
`accurate relative position determinations. This is a so- 65
`called "range-domain" approach, rather than the more
`conventional "position-domain" approach referenced in
`the previous paragraph.
`
`FIG. 1 is a GPS positioning system for a ship and
`several tailbuoys according to the present invention;
`FIG. 2 is a block diagram of several of the major
`elements of the system of FIG. 1;
`FIG. 3 is a block diagram of the inputs and outputs
`for the ship board CPU of the system of FIG. 1;
`FIG. 4 is a top level flowchart for a computer-imple(cid:173)
`mented process that runs on the CPU of FIG. 3;
`FIG. 5 is a flowchart of the GPS SHIP CALC sub(cid:173)
`routine of the computer-implemented process of FIG.
`4·
`' FIG. 6 is a flowchart of the position & velocity up-
`date subroutine of the computer-implemented process
`of FIG. 4;
`
`1h1
`
`1p
`
`15
`
`Apple Inc. Exhibit 1009 Page 10
`
`

`
`5,202,829
`
`4
`this can alternatively be a trackball. A trackball may be
`preferred for use on ships that roll at sea. A shot-point
`board is in add-on board that plugs into CPU 58. Prefer(cid:173)
`ably, CPU 58 is an "IBM-compatible" personal com(cid:173)
`puter having an Intel 80386 microprocessor and the
`Microsoft MS-DOS or IBM PS/2 operating system. A
`Compaq Computer model 386 gives acceptable results.
`The shot-point board provides 1/0 interfacing for GPS
`receiver 50 and a shot-point contact closure 68 ulti(cid:173)
`mately sourced from tailbuoy 18. Outputs from CPU 58
`I/O ports 3-5 arc BINPOS to the ship's navigational
`computer, tailbuoy solution data for user equipment,
`and raw measurement data for recording on a ship data
`acquisition system. Selected solution data and quality
`control/quality assurance (QC/QA) data is also avail(cid:173)
`able.
`
`3
`FIG. 7 is a flowchart of the GPS BUOY CALC
`subroutine of the computer-implemented process of
`FIG. 4;
`FIG. 8 is a flowchart of the nonlinear-correction
`subroutine of the computer-implemented process of 5
`FIG. 4;
`FIG. 9 is a flowchart of the second-order space vehi(cid:173)
`cle (SV) code/carrier filtering correction subroutine of
`the computer-implemented process of FIG. 4;
`FIG. 10 is a flowchart of the alternative third-order 10
`space vehicle (SV) code/carrier filtering correction
`subroutine of the computer-implemented process of
`FIG.4;
`FIG. 11 is a flowchart of the solution reference-time
`finding subroutine of the computer-implemented pro- 15
`ccss of FIG. 4;
`FIG. 12 is a flowchart of the subroutine for comput(cid:173)
`ing the cofactor-matrix and solution update in the com(cid:173)
`puter-implemented process of FIG. 4;
`FIG. 13 is a flowchart of the fault detection isolation 20
`& correction (FDIC) subroutine of the computer-imple(cid:173)
`mented process of FIG. 4; and
`FIG. 14 is an illustration of a typical screen display
`presented to a user of the system of FIG. 1.
`
`System Overview
`CPU 58 calculates real-time range domain based sep(cid:173)
`aration vectors between the tailbuoys and ship. Pscudo(cid:173)
`ranges (PRs) arc optimally filtered using integrated
`Doppler. A computed weighted-least-squares solution
`is based on measured signal-to-noise-ratio (SNR), the
`duration of continuous tracking on each satellite, satel-
`25 lite geometry, and the expected level of correlated er(cid:173)
`rors in each pseudo range. System 10 has a basic five
`meter relative position accuracy. Three tailbuoys can be
`processed per six second epoch. The radio communica-
`tions link has a six kilometer range. The tailbuoy CPS
`receiver collects raw SV data and, compresses it into
`the CMR to reduce data packet length. All calculations
`arc performed on the shipboard CPU. This provides for
`high accuracy calculations, and allows for quality con(cid:173)
`trol/ quality assurance measure calculations and display.
`All raw data is stored for post mission analysis.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`FIG. 1 shows an offshore oil exploration system 10
`for providing two to five meter location accuracy for
`hydrophone streamer tailbuoys. System 10 is a first 30
`embodiment of the present invention, and comprises a
`main system 12 onboard a ship, an optional reference
`station 14, a satellite (SV) 16, a group of tailbouys 18,
`20, 22, and 24, a reference link 26, a reference GPS
`downlink 28, a ship GPS downlink 30, a tailbuoy GPS 35
`downlink 32, and a group of tailbuoy VHF radio links
`Quality Control/Quality Assurance
`34,36, 38, and 40. Tailbuoy 18 has a sonic cannon that
`Real-time visual indicators to operators show the
`emits a shockwave 42 that impacts on seafloor bottom
`approximate quality of satellite data used in the position
`44. Reflected sound waves 46 are recorded by the tail-
`buoys 18, 20, 22, and 24. Data collected from reflected 40 solutions. The nature of this display allows a user to
`sound waves 46 and raw pseudo-range (PR) informa-
`immediately determine if data should be recollected.
`tion is reported back to main system 12, together with a
`The indicators arc ellipses drawn around each tailbuoy
`signal time-marking when the sonic cannon fired, over
`and ship icon on a user display (sec FIG. 14). The cllip-
`radio link 34. A compact message record (CMR) format
`ses are referred to as "error ellipses", since they provide
`is used by the tailbuoys to efficiently communicate data 45 a statistical indication of the expected solution error.
`in the speed restricted and time competitive environ-
`System 10 tracks the real-time positions and velocities
`mcnt created here. The CMR is detailed below.
`of the ship and the three tailbuoys using the range do-
`FIG. 2 shows that main system 12 comprises a data
`main DGPS technique. Five meter, one sigma (o-),
`receiver modem 50, an antenna 52, a GPS receiver 54, a
`accuracy of the relative solution between the ship and
`radio/modem 56, and a microcomputer system (CPU) SO tailbuoy is possible, assuming an HOOP of 2.S or less.
`58. Tailbuoy 20, which is representative of all the tail-
`Ten kilometer radio range from tailbuoy to ship is prac-
`buoys, has a GPS sensor 60, a radio/modem 62, and a
`tical, assuming 20 meter antenna height on ship and
`tailbuoy antenna 63. Since the tailbuoys are typically
`three meter antenna heights on the tailbuoys. System 10
`calculates an overdetermined solution when more than
`subjected to rough seas that can cause them to roll, a
`gimbal is provided on antenna 63 to keep the main re- SS four healthy satellites arc co-visible between the tail-
`buoy and ship, or three if a constrained altitude solution
`ception lobe pointing in a consistent direction. Weather
`and corrosion are a major problem at sea too, so the
`is selected. Update rates do not usually exceed six sec-
`onds for three tailbuoys with a 1200 baud radio commu-
`gimbal mechanism, at least, will have a longer life and
`bettcr operation if the entire antenna is covered by a
`nication link, assuming a worst case 1400-bit long mes-
`radome. The construction of gimbals compatible with 60 sage with eight satellites. The capture of a contact cla-
`use at sea and radomes for satellite antennas are well-
`sure (shot point firing) is typically better than one milli-
`known, so further explanation here is not necessary.
`second UTC. Solution data is preferably de-skewed to
`FIG. 3 diagrams the data 1/0 for CPU 58. GPS re-
`the contact closure event. The following data is output
`ceiver 54 outputs a ship CMR (Compact Measurement
`to the ship's data acquisition system: receiver-generated
`Record), ephemeris data, ionospheric correction data, 65 BINary POSition data (BINPOS);
`tailbuoy solu-
`tion-relative position to ship at shot point time; ship
`diffcrential correction data (if supplied), and BINPOS
`position; all raw data used in computation of ship and
`(BINary POSition) data from GPS receiver itself, to
`port COM-1. A mouse connects to a dedicated port, and
`tailbuoy position including; compact measurement re-
`
`Apple Inc. Exhibit 1009 Page 11
`
`

`
`5,202,829
`
`5
`cords for the tailbuoys; compact measurement records
`for the ship; ephemeris and ionospheric correction data
`for the ship; differential correction data for the ship;
`selected solution outputs; ship and tailbuoy solution,
`quality control and quality assurance measures. (statis(cid:173)
`tics and over-determined solution data);
`
`(C:
`
`TBTRACK
`TBTRACK is an application program that preferably
`installs itself on an "IBM-compatible" personal mi(cid:173)
`crocomputer's "C:" drive (hard disk). TBTRACK cre(cid:173)
`ates a directory tree (these terms will be familiar to IBM
`PC and Microsoft MSDOS users) that starts at the root
`directory
`
`6
`its CPU 58 filename, TBTRACK. Step 102 allows a
`user to input basic information via the mouse and key(cid:173)
`board. Basic operating parameters are loaded in file
`USER_CTL in step 104. Raw data measurements from
`5 various GPS and radio receivers fill the data input re(cid:173)
`quirements for the display and position/velocity solu(cid:173)
`tions in step 106. Step 106 calls GPS_SHIP -CALC as
`a subroutine to compute the ship's position and velocity
`using the data made available in SHIP _JN (step 106). A
`10 queue, or stack, of time-tagged ship GPS data and solu(cid:173)
`tions are assembled in step 110. Twelve distinct periods
`are maintained. Similar to step 106, BUOY _JN collects
`data necessary for the tailbuoy GPS solutions and dis(cid:173)
`play in step 112. The available tailbuoy raw data are
`15 then matched, using time-tags, with available ship solu(cid:173)
`),e.g.,:
`tions in step 114. In step 115, a test is made to see if a
`TBTRACK
`match can be found, if not, step 115' decides if the cur(cid:173)
`CHARTS
`rent tailbuoy and ship solution stet will provide a match,
`MWORLDSO
`or if a whole new set is collected. If a match is found,
`MWORLDSSO.AOI
`20 the time is spent to convert the raw tailbuoy data into
`CHARTHDR
`MWORLDSO.HDR
`final solutions in step 116. Step 118 checks to see if a
`DCCHARTS
`sonic canon has been fired (shot event). If yes, step 119
`ARCHIVE
`synchronizes ship position and separation vectors (to
`TEXT
`the tailbuoys) to the shot. In any event, step 120 updates
`the directory that contains the 25 (drives) the TBTRACK display on the user screen of
`TBTRACK is
`TBTRACK program itself and its support files. It is
`CPU 58. Step 122 tests whether or not a user has input
`a reset via the mouse of CPU 58. If so, control flow
`from this directory that TBTRACK is executed. The
`returns to step 102. Step 124 decides whether or not to
`CHARTS directory contains sub-directories that con-
`tain chart files. A program disk for TBTRACK pref era-
`loop to step 106 to repeat the above sequence, or to end.
`
`bly installs a chart file for the entire world in a sub- 3° FIG. S flowcharts the GPS_SHIP _CALC subrou-
`
`35
`
`tine called in step 108 of FIG. 4. Step 210 collects space
`directory under CHARTS, called MWORLDSSO. Any
`additional charts installed in the system must have a
`vehicle (SV) data in the form of raw pseudo-ranges.
`This measurement data is corrected and time synchro-
`directory created for them here.
`MWORLDSO is a chart directory that TBTRACK
`nized in step 220. The raw data is filtered in step 230 and
`.
`II .
`statistical information about the quality of the data is
`creates at system msta at1on.
`obtained. A solution reference time is selected in step
`The CHARTHDR directory contains "header" files
`for all of the charts that have a directory under
`250. The previous solution is carried-forward (propa-
`gated) with its associated cofactor matrix to the selected
`CHAR TS. These "header" files contain information
`about the charts in the CHARTS directory. A single
`reference time in step 260. Propagated solutions are
`header file for the MWORLDSO world chart is pro- 40 used to provide information bridging across time peri-
`vided and installed by TBTRACK at install time. Any
`ods that would otherwise have missing solutions be-
`additional charts installed in the system have their cor-
`cause the current raw data input has been judged to be
`responding header files placed here.
`insufficient or unreliable. In step 360, which is not used
`DCCHARTS is a directory that is used as a scanned
`chart disk file cache. As sections of a chart are decom- 45 in an alternative embodiment, a test is made using the
`propagated cofactor matrix for solution degradation
`caused by the loss of contact with one or more SVs.
`pressed, they are typically stored in this directory. The
`maximum amount of disk space that is taken by this
`(Such a loss can occur on individual tailbuoys or the
`cache is specified when running an initial setup pro-
`gram, VSETUp. A CaChe level is used such that when
`ship itself as the sea rolls and the respective GPS receiv(cid:173)
`TBTRACK is requested to display a section of a chart 50 ing antennas swing around, for example.) DOP holes
`are SV configurations (positions in the sky) that create
`it checks in the cache first, to see if a chart section exists
`in a decompressed form. If it does, it is simply read from
`problems in SV navigation systems. These problems
`the cache and displayed. If it does not exist, a com-
`occur because of poor geometric SV locations (referred
`pressed file is retrieved, decompressed, stored in a
`to also as bad geometry). Step 280 updates the position
`cache directory, and then displayed. If the cache direc- 55 and velocity solutions and makes them available.
`tory becomes full, TBTRACK will erase the oldest
`GPS-SHIP _CALC 108 then returns.
`chart section from the cache. It then saves the new
`FIG. 6 flowcharts position and velocity update sub-
`chart section in the cache. If the disk space taken by this
`routine 280. The ionosphere and troposphere can dis-
`"cache"
`is needed
`for any
`reason other
`than
`turb raw pseudo-range information, and step 281 uses
`TBTRACK's use, the contents may simply be deleted. 60 the elevation, azimuth, and other data about each SV to
`TBTRACK will recreate cache files when necessary.
`compute and apply a correction factor to each measure-
`The ARCHIVE directory allows TBTRACK to
`ment. The cofactor matrix is then computed in step 282.
`If n:iore th~n four or more than ~hree SVs in a. con-
`archive ship position solution data. This data is used for
`tracking session reruns.
`stramed altitude mode are supplymg acceptable mfor-
`The TEXT directory archives ship report data in a 65 mation, then step 283 will branch to step 283' to com-
`pute a separate cofactor matrix for FDIC. When three
`text format that is easily readable.
`FIG. 4 is a top level flowchart for a computer-imple-
`SVs only are supplying acceptable data, the fact that the
`mented process 100. Process 100 is referred to herein by
`ship and tailbuo:1$ must have altitudes approximating
`
`Apple Inc. Exhibit 1009 Page 12
`
`

`
`5,202,829
`
`8
`
`ECEF
`dECEF = C ENV • dENU;
`Rb; = Ix; - Xs + d I ;
`ub; = Ix; - Xs + d I I Rb; ; and
`cosa; = ub; . ub, .
`
`25
`
`7
`mean sea level (MSL) is used in a constrained altitude
`solution in step 284. Fault detection, isolation, and cor(cid:173)
`rection (FDIC) tests are run in step 285 and the subrou(cid:173)
`tine 280 returns.
`The advantages of a navigation system that can moni- 5
`tor its own integrity are obvious. (See, Mark A. Sturza,
`"Navigation System Integrity Monitoring Using Re(cid:173)
`dundant Measurements," NAVIGATION: Journal of
`The Institute of Navigation", Vol. 35, No. 4, Winter
`1988-89.) Redundant measurements allow fault detec- 10
`tion that stops errors before they have a chance to cor(cid:173)
`rupt the outputs. Sturza presents an excellent back(cid:173)
`ground for the reader and gives two examples of sys(cid:173)
`tems with fault detection, 1) a skewed axis strapdown
`inertial navigation system, and 2) a GPS navigation set. 15
`Sturza also discloses a fault identification algorithm.
`The present invention not only detects and isolates
`faults, but makes use of an isolation reliability test, and
`then corrects input sources. In addition, the statistical
`weightings given to the measurement data are com- 20
`puted dynamically, while Sturza makes use of fixed
`weightings.
`FIG. 7 flowcharts the GPS_BUOY _CALC subrou(cid:173)
`tine. In step 310, SV measurement data is collected and
`tested to see if the data is acceptable. In step 320, SV
`measurement data is corrected for receiver clock roll(cid:173)
`over and SV clock error. In step 330, buoy measure(cid:173)
`ments are synchronized to the reference time, calcu(cid:173)
`lated by GPS_SHIP -CALC. In step 340, SV Code/- 30
`Carrier Filtering is used to produce a current, optimally
`smoothed pseudo-range (PR) for each SV. The filtering
`is designed to access stored measurement ionospheric
`correction data from each SV. This data is used to com(cid:173)
`pensate for the ionospheric dispersion between the code 35
`and carrier information. In step 350, the cofactor matrix
`is propagated to the reference time. The purpose of the
`position and velocity cofactor matrices is to measure
`the amount of uncertainty in the previous calculations.
`In step 360, which is not used in an alternative embodi- 40
`ment, a test for DOP holes is initialized. DOP holes are
`SV configurations (positions in the sky) that create
`problems in SV navigation systems. These problems
`occur because of poor geometric SV locations (referred
`to also as bad geometry). The advantage of computing 45
`a cofactor matrix is that it identifies and screens out
`DOP holes which can create problems to navigators.
`Once a DOP hole is identified, the operator is informed
`of this by the lack of new position updates. In step 370,
`after the ship's position is updated, a computation of so
`separation vectors is performed. Separation vectors
`represent the vectors from buoy to ship. In step 375,
`since the lines-of-sight from the ship and buoy to each
`SV are not tr