Algorithms for global positioning

Publication date 15 June 2012

Accurate time keeping was a problem for centuries. Now, this picture has totally changed because of new technological developments, electronics and artificial satellites. Today, atomic clocks tell the time with an accuracy better than \(10^{-11}\) seconds. Satellite positioning, a combination of engineering tools, mathematics of coordinate mapping and numerical calculations, influences the life of many people. NEWLINENEWLINENEWLINE NEWLINEThe present book is an extension of the authors' text from 1997 ``Linear Algebra, Geodesy, and GPS [Wellesley, MA: Wellesley-Cambridge Press. xvi, 624 p. (1997; Zbl 1007.86001)]. It describes the linear algebra and the specialised algorithms for receivers to compute their positions. Thus it starts with a section on the fundamental theorem of linear algebra. As the Global Positioning System (GPS) is used as an example of the central ideas of global satellite navigation technology, a detailed discussion of a GPS software receiver follows. From coordinates of at least four satellites and their four pseudoranges (distances between satellite and receiver, calculated as traveltime of the signal times speed of light), the receiver can compute its own position as well as the offset between GPS time and the local time in the receiver. The accuracy of the computed position is recently usually a few meters. The examples and data sets presented in the book come from the GPS Center in Aalborg. The book provides, besides GPS data, also information on other used and planned global positioning systems like Galileo, GLONASS, Compass, and QZSS. Chapter 1 contains a survey of important civilian GPS applications. It considers essential ideas and applications of ``Global Navigation Satellite Systems (GNSS) including satellite based augmentation to compensate ionospheric time delay (WAAS in USA, EGNOS in Europe, GAGAN in India, and QZSS in Japan). When the algorithm level is presented, using pseudoranges and carrier ranges and corrections, one sees only small differences in these systems. Accuracy of a few centimeters can be obtained by using dual frequency receivers which observe both pseudoranges and carrier phases (chapter 10).NEWLINENEWLINEChapter 2 explains in detail features of the ``Gold Code which is used as the basic spreading code for GNSS signals. Wave forms, power spectral densities, and autocorrelation functions of the modulated waveforms are discussed. Unfortunately, the Earth is not a sphere. It is flattened at the poles by a factor close to \(1/297\). Thus GPS needs to convert latitude and longitude on the Earth to and from x-y-z Cartesian coordinates in space. Therefore, chapter 3 focuses on coordinates and changes of coordinates. The World Geodetic System (WGS84), a global datum, which provides accurate parameters for positioning is discussed. It is explained how coordinate changes may be found from datum changes.NEWLINENEWLINEChapters 4 to 8 describe the mathematics one needs for GNSS. Global positioning gives more data than the minimum needed to determine a position. But these measurements contain errors. Thus least squares algorithms are applied to find the best solution. Chapter 4 establishes the equations that determine a position when the noise vector is taken to be a random variable. That means, here the two starting points of the calculations are: (1) noise in a signal is modeled as a random process. (2) The best estimate of a position is based on ``weighted least squares. ``The crucial link between the two ideas is that the optimal weights in least squares are the inverses of the covariance matrices for the random variables. These variances and covariances must be estimated. This is not easy. The covariances go into the least squares algorithms. The output must include an estimate (of position or velocity) and also a measure of convidence in that estimate [preface and outline, p. X].NEWLINENEWLINEThe Kalman filter is created to produce this output: estimate plus covariance. The key to the Kalman filter is the idea of updating: ``The algorithm is recursive least squares, in which the output at time epoch \(k\) is combined with new observations to produce an estimate at epoch \(k+1\) (with covariance). Recursive means, that the observations prior to \(k\) are not used again, their contribution is made in estimating the state at time \(k\). The update multiplies by the gain matrix. [preface and outline, p. X].NEWLINENEWLINE``A second feature of the Kalman filter is equally valuable. It can estimate a state that is changing. The receiver can move, and that movement is given by the state equation. The update has to account for change in the state as well as new observations. The steps are conceptually simple but the algebra is notoriously painful (in comparison with the basic normal equation \(A^TAx=A^Tb\) for the unweighted least squares solution of \(Ax=b\) [preface and outline, p. X].NEWLINENEWLINEThe authors do their best with that algebra. Chapter 5 deals with random processes in continuous and discrete times, chapter 6 explains linear algebra for weigted least squares, and chapter 7 discusses singular normal equations and networks (least-squares problems with dependent columns in the matrices). Chapter 8 concerning Kalman filters is written on the basis of chapter 17 of the previous book of the authors on ``Linear algebra, geodesy, and GPS, which has been accepted as a clear and self-contained reference to Kalman filters.NEWLINENEWLINEChapters 9 and 10 explain the positioning algorithms which are at the heart of the subject. For GPS one needs data of at least four satellites, thus four ``one-ways are needed to compute the position of a stand-alone receiver. Usually more than four satellites (or ``one-ways) are in view. One uses least squares to estimate the position and the clock error. Chapter 9 deals with receiver positions from one-way pseudoranges. The discussion starts with inexpensive receivers and limited accuracy of meters, and it comes to high-quality receivers and networks of receivers that allow code and phase measurements, and have a resolution of millimeters. The ideas are straightforward, but the details are more involved. The reader gets information about 18 so-called ``Easy Codes of MATLAB to compute positions, which are collected in two ``Easy Suites. The topics in the first ``Easy Suite (codes 1-10) are selected to establish an increase of the complexity of the codes. The second ``Suite (codes 11-18) contains specialist topics of growing importance.NEWLINENEWLINEEach satellite sends signals on more than one frequency. Chapter 10 shows how a more precise receiver can use phase observations for high accuracy. Signals are delayed in the ionosphere (light travels more slowly) in dependence on the frequency. Thus with two frequencies one can delete the related delay of the data. A key idea of chapter 10 is therefore to work with differences in the observations of nearby receivers, that means with differences of one-way observations. Chapter 10 handles major error sources of positioning. It ends with real-time kinematic positioning, including codes.NEWLINENEWLINEChapters 11 and 12 return to fundamental questions of geometry. The positioning computing is performed on an ellipsoid. The geodesics are no longer great circles on a sphere. A whole succession of famous geometers has worked with formulas on the ellipsoid and conformal mappings onto the plane. In presenting these fundamental issues of geodesy (Earth measurement), it is reported on the achievements of the past. In a wonderful way, the new technology of satellite positioning has brought incredible accuracy to this classical science.

Recommendations

Cited in

(28)

Describes a project that uses

Uses Software

Matlab

This page was built for publication: Algorithms for global positioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891514)