Introduction to
Global Navigation Satellite System (GNSS)
Position Computation
Dinesh ManandharCenter for Spatial Information Science
The University of Tokyo
Contact Information: dinesh@iis.u-Tokyo.ac.jp

Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 1

Pseudorange equation
Perfect World:r  ct  t SRReal World:
Receiver clock error

Tropospheric delayMultipath  r  ct  t   I  T  M  SRSatellite clock error

Simplify…

Ionospheric delay Thermal noise  r  ct R  t S   Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 2

Range Equation
Satellite position at signal transmission time:x , y , z Receiver position at signal reception time:

x, y, z r

SSSx  x   y  y   z  z S 2

S 2

S 2

x , y , z SSS

x, y, z 
Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 3

Pseudorange modelx  x   y  y   z  z   ct  t  S 2

S 2

S 2

SRr
Given satellite position & clock in navigation message
Unknown receiver position & clock
Estimate optimal solution to minimize the error

Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 4

Nonlinear Optimization Problem• We have n simultaneous nonlinear equations from n
pseudorange observations.
• We need at least 4 independent observations in order todetermine 4 unknown parameters.
• In general, even a single nonlinear equation cannot be
solved without some iterative method by generating asequence of approximate solutions.

Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 5

Newton-Raphson Method
Find successively better approximation x  x0satisfyingy  y0of a nonlinear equation y  f (x. )yy0  f x0   f x0  xy  f (x)

y

yy0

xxx xx0 The0 University
0 of Tokyo, dinesh@iis.u-tokyo.ac.jp
Dinesh Manandhar, CSIS,

Slide : 6

Newton-Raphson Algorithm
Initial Guess x  x0
Solve the equation for xy  f x0   f x0  x

yUpdate x0x0  x0  x

y : Residual
Repeat until a sufficiently
small value x is reached.

Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 7

Pseudorange Equation
x  x   y  y   z  z   ct  ct
S 2S 2r

 f x, y, z, b

S 2

Sb

For given observation   0
Linearize around the initial solution x0 , y0 , z0 , b0 
Obtain the update x, y, z, b

Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 8

Linearization
Partial derivatives with respect to each unknown parameter:f x  x,xrSfy  yS,yr

f z  z S,zrf
1
bLinearized pseudorange residual equation:

x0  x Sy0  y Sz0  z S
 0  f x0 , y0 , z0 , b0  
x y z  br0r0r0


Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 9Vector Description
 x0  x S  
 r0y0  y Sr0z0  z Sr0x y  1 z  bhx

We need at least 4 linearly independent equations
in order to determine 4 unknown parameters.
Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 10

Simultaneous equations 1   h1    1  2  2  2     h  x          
 N  N  N  h   yN 1
Residual vector

N 4e
N  4 41 N 1

Hy  Hx  e

Observation
matrix State vector
Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 11

Least squares problem
For given y  Hx ,efindx toxˆ minimize.eT ePerformance Index:

J  eT e y  Hx y  Hx
T yT y  yT Hx  xT HT y  xT HT Hx
 y y  2x H y  x H Hx
TTT

TT

J
0Find x  xˆto minimize J x x xˆ
Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 12

Least squares solution
Partial derivatives of a scalar function w.r.t the state vector:

fa(1) f x  a x  x a thenx
fT
 2Ax
(2) f x  x Ax thenx
for all symmetric matrix ATFind x  xˆto satisfy

TJ 2HT y  2HT Hx  0x

xˆ  H HTHy
1TDinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 13

GNSS Positioning Calculation
Initial Guess x 0

Even the north pole isa good initial guess!

Solve the equation for x̂

Pseudorange xˆ  H HTHy
1

TSatellite position x , y , z SSS

Satellite clock t S

Update x 0x0  x0  xˆGenerally takes a few iterations.

Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 14

Error Budget• The positioning accuracy depends on the magnitude of error
in the individual pseudorange measurement.
Source

Error

DGPS

Satellite orbit error

1 ~2m

0

Satellite clock error

1m0

Ionospheric delay

4~10 mTropospheric delay

1~2 m

Can be minimized to<1mThermal noise

1mMultipath

1m or more

Can’t be removed

Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 15

Error sources
V = 4km/s

Satellite position error
Ephemeris

Ionospheric delay
200km

Tropospheric delay

Satellite clock error

50km

10km

Thermal noise
Multipath
Receiver clock error
Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 16

Satellite geometry and positioning error• The positioning accuracy also depends on the geometricconfiguration of the satellites.
Badgeometry

Goodgeometry

Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 17

Dilution of precision (DOP)gx
1TG H H 

Position DOP:
Time DOP:
Geometric DOP:

gy

gz


 gb 

PDOP  g x  g y  g z
TDOP  g b

GDOP  g x  g y  g z  g b

Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 18

DOP and positioning accuracy
Accuracy of any measurement is proportionately dependent
on the DOP value. This means that if DOP value doubles, theresulting position error increases by a factor of two.
ys

sy=s×YDOPx

sx=s×XDOP
Dinesh Manandhar, CSIS, The University of Tokyo, dinesh@iis.u-tokyo.ac.jp

Slide : 19