Monday, September 15, 2008

Before providing a more mathematical description of position calculation, the introductory material on this topics is reviewed. To describe the basic concept of how a GPS receiver works, the errors are at first ignored. Using messages received from four satellites, the GPS receiver is able to determine the satellite positions and time sent. The x, y, and z components of position and the time sent are designated as $\left [x_i, y_i, z_i, t_i\right ]$ where the subscript i denotes which satellite and has the value 1, 2, 3, or 4. Knowing the indicated time the message was received $\ tr_i$, the GPS receiver can compute the indicated transit time, $\left (tr_i-t_i\right )$. of the message. Assuming the message traveled at the speed of light, c, the distance traveled, $\ p_i$ can be computed as $\left (tr_i-t_i\right )c$. Knowing the distance from GPS receiver to a satellite and the position of a satellite implies that the GPS receiver is on the surface of a sphere centered at the position of a satellite. Thus we know that the indicated position of the GPS receiver is at or near the intersection of the surfaces of four spheres. In the ideal case of no errors, the GPS receiver will be at an intersection of the surfaces of four spheres. The surfaces of two spheres if they intersect in more than one point intersect in a circle. A figure, Two Sphere Surfaces Intersecting in a Circle, is shown below depicting this which hopefully will aid the reader in visualizing this intersection.

The article, trilateration, shows mathematically how the equation for a circle is determined. A circle and sphere surface in most cases of practical interest intersect at two points, although it is conceivable that they could intersect in 0, 1 or infinite points. Another figure, Surface of Sphere Intersecting a Circle (not disk) at Two Points, is shown below to aid in visualizing this intersection. Again trilateration clearly show this mathematically. The correct position of the GPS receiver is the one that is closest to the fourth sphere. This paragraph has described the basic concept of GPS while ignoring errors. The next problem is how to process the messages when errors are present.

Let $\ b$ denote the clock error or bias, the amount by which the receiver's clock is slow. The GPS receiver has four unknowns, the three components of GPS receiver position and the clock bias $\left [x, y, z, b\right ]$. The equation of the sphere surfaces are given by

$(x-x_i)^2 + (y-y_i)^2 + (z-z_i)^2 = \bigl((tr_i + b - t_i)c\bigr)^2$,$\;i=1,2,3,4.$ Another useful form of these equations is in terms of the pseudoranges, which are simply the ranges approximated based on GPS receiver clock's indicated (i.e. uncorrected) time so that $p_i = \left (tr_i - t_i \right )c$. Then the equations becomes:

$p_i = \sqrt{(x-x_i)^2 + (y-y_i)^2 + (z-z_i)^2)}- bc,\;i=1,2,3,4.$. Two of the most important methods of computing GPS receiver position and clock bias are (1) trilateration followed by one dimensional numerical root finding and (2) multidimensional Newton-Raphson calculations. These two methods along with their advantages are discussed.

• The receiver can solve by trilateration followed by one dimensional numerical root finding[. This method involves using Trilateration to determine the intersection of the surfaces of three spheres. It is clearly shown in trilateration that the surfaces of three spheres intersect in 0, 1, or 2 points. In the usual case of two intersections, the solution which is nearest the surface of the sphere corresponding to the fourth satellite is chosen. The surface of the earth can also sometimes be used instead, especially in the case of civilian GPS receivers since it is illegal in the United States to track vehicles of more than 60,000 feet in altitude. The bias, $\ b$ is then computed based on the distance from the solution to the surface of the sphere corresponding to the fourth satellite. Using an updated received time based on this bias, new spheres are computed and the process is repeated. One advantage of this method is that it involves one dimensional as opposed to multidimensional numerical root finding.
• The receiver can utilize multidimensional Newton-Raphson calculations. Linearize around an approximate solution, say $\left [x^{(k)}, y^{(k)}, z^{(k)}, b^{(k)}\right ]$ from iteration k, then solve four linear equations derived from the quadratic equations above to obtain $\left [x^{(k+1)}, y^{(k+1)}, z^{(k+1)}, b^{(k+1)}\right ]$. The radii are large and so the sphere surfaces are close to flat.[28][29] This near flatness may cause the iterative procedure to converge rapidly in the case where $\ b$ is near the correct value and the primary change is in the values of $x, y,\; and\; z$, since in this case the problem is merely to find the intersection of nearly flat surfaces and thus close to a linear problem. However when $\ b$ is changing significantly, this near flatness does not appear to be advantageous in producing rapid convergence, since in this case these near flat surfaces will be moving as the spheres expand and contract. This possible fast convergence is an advantage of this method. Also it has been claimed that this method is the "typical" method used by GPS receivers. A disadvantage of this method is that according to , "There are no good general methods for solving systems of more than one nonlinear equations." For a more detailed description of the mathematics see Multidimensional Newton Raphson.
• Other methods include:
1. Solving for the intersection of the expanding signals form light cones in 4-space cones
2. Solving for the intersection of hyperboloids determined by the time difference of signals received from satellites utilizing multilateration,
3. Solving the equations in accordance with.

• More than four satellites should be used, if available. This results in an over-determined system of equations with no unique solution, which must be solved by least-squares or a similar technique. If all visible satellites are used, the results are always at least as good as using the four best, and usually better. Also the errors in results can be estimated through the residuals. With each combination of four or more satellites, a geometric dilution of precision (GDOP) vector can be calculated, based on the relative sky positions of the satellites used. As more satellites are picked up, pseudoranges from more combinations of four satellites can be processed to add more estimates to the location and clock offset. The receiver then determines which combinations to use and how to calculate the estimated position by determining the weighted average of these positions and clock offsets. After the final location and time are calculated, the location is expressed in a specific coordinate system such as latitude and longitude, using the WGS 84 geodetic datum or a local system specific to a country.

Finally, results from other positioning systems such as GLONASS or the upcoming Galileo can be used in the fit, or used to double check the result. (By design, these systems use the same bands, so much of the receiver circuitry can be shared, though the decoding is different.)

Chirag K. Shah said...

Good work..But have no idea what you wanted to show in this....I have done project on GPS from DRDO..SO i guess do you want some suggestions or advice??

Anonymous said...