# Why does GPS require a minimum of 24 satellites?

From Wikipedia,

The GPS design originally called for 24 SVs, eight each in three approximately circular orbits, but this was modified to six orbital planes with four satellites each. [...] The orbits are arranged so that at least six satellites are always within line of sight from almost everywhere on Earth's surface.

I understand that we need 4 satellites within line of sight in order to solve for position and time. Let's accept that for fail-safe reasons, we require that 6 satellites are always within line of sight, everywhere on Earth.

Here is my question: why do we need to a minimum of 24 satellites in order to have 6 of them within line of sight?

Let $r$ be Earth's radius and $R$ be the orbital radius of the satellites, the area of the orbital sphere visible at any place on Earth's surface is

$A=\int R^2 \sin\theta\,\mathrm d\theta\,\mathrm d\phi = -2\pi R^2\int_1^{r/R} \mathrm d\cos\theta = 2\pi R^2(1-r/R)$

The fraction of solid angle visible is

$x = 2\pi R^2(1-r/R)/(4\pi R^2) = (1-r/R)/2$

Substituting $R =$ 26,600 km and $r =$ 6,370 km (values from Wikipedia), we get $x =$ 38.0%. With 24 satellites, we should be able to see about 9 of them most of the time, which is ~50% above the requirement.

Is the discrepancy because we cannot uniformly distribute the satellites in a sphere? If so, how can we derive the minimum number of satellites needed?

-
As far as I know, it is not just requirement. There is also redundancy and accuracy reasons for "the more the merrier" solution. – user13838 Sep 10 '11 at 10:14
One thing you also have to consider is that line of sight depends a lot on terrain and the presence or absence of buildings. You won't be able to see satellites that are too close to the horizon. Modeling the earth as a sphere misses this aspect. – Tim Seguine Sep 10 '11 at 12:56
Also, even if you could distribute the satellites "optimally" in a single moment of time, this optimal configuration cannot be preserved when the satellites need to move in their orbits in order to stay up. You can't just rotate the entire shell of satellites rigidly, because each satellite must stay within a single geometric plane through the Earth's center. – Henning Makholm Sep 10 '11 at 15:07
@Henning: It looks like I nabbed this idea from you, but I was actually adding it to my answer while you posted this comment... – joriki Sep 10 '11 at 15:14
@joriki, it's OK; it's not as if I could claim originality anyway. – Henning Makholm Sep 10 '11 at 15:18

I see six potential reasons for this. You've already mentioned one, the impossibility of "uniformly" distributing the satellites over a sphere, in the question, and percusse and Tim mentioned three more in comments, redundancy, accuracy and visibility on the horizon. Two further aspects are that even with "uniform" distribution over the sphere your averaging doesn't guarantee complete coverage, and the fact that the satellites can't stay in a fixed constellation without being in geostationary orbits.

Accuracy

The accuracy of GPS is higher when the satellites being used are spaced further apart (angularly). One might at first think that that means the accuracy would increase if there are fewer and they're spaced further apart; however, if there are more than the minimum number of satellites in sight, you can choose the outermost ones and get a better angle than if they were all spaced slightly further apart but you had to use the inner ones. Which of these two effects dominates might depend on the details of the configuration.

Horizon

People are usually surrounded by houses or hills or forests; you rarely have a line of sight to the horizon. This post says:

I’m also going to constrain the DOP calculations by requiring that each point on Earth not be able to see any GPS satellite below 10 degrees from the horizon. This is a typical mask angle used for these types of analysis.

To perform your analysis with this constraint, we need to find the value of $\theta$ corresponding to an angle of $\alpha=100^\circ$ between the directions to the centre of the Earth and to a satellite at $\theta$. Applying the law of cosines twice,

$$x^2=r^2+R^2-2rR\cos\theta\;,$$ $$R^2=r^2+x^2-2rx\cos\alpha\;,$$

subtracting to get rid of $x^2$,

$$r-R\cos\theta+x\cos\alpha=0\;,$$

solving for $x$ and substituting it into the first equation,

$$(r-R\cos\theta)^2=\cos^2\alpha(r^2+R^2-2rR\cos\theta)$$

and solving for $\cos\theta$ yields

$$\cos\theta=\lambda\sin^2\alpha-\cos\alpha\sqrt{1-\lambda^2\sin^2\alpha}$$

with $\lambda=r/R$. Substituting $\alpha=100^\circ$ and $\lambda=6370/26600\approx0.24$ yields $\cos\theta\approx0.4$, so $(1-\cos\theta)/2\approx0.3$, so the visible fraction of solid angle would be about $30\%$.

Uniformity

We should first think about what it means for points to be "uniformly" distributed over the sphere. We could try to make the polyhedron formed by the satellites isohedral, isotoxal and/or isogonal. We get the most stringent condition by requiring all three of these properties, which means that the polyhedron is regular, and since it's convex (assuming the satellites are on a sphere), it must be one of the Platonic solids. Obviously there are only five numbers of satellites for which this is possible, but since one of them, $20$, is close to the actual number, $24$, it makes sense to look at this case.

Even if the satellites form a Platonic solid, and are thus as "uniformly" distributed as possible, your consideration of the average doesn't quite give the right number of satellites. This is perhaps easiest to see for the regular tetrahedron. Say our requirement were to always have two satellites in sight, and for simplicity let's assume that we can always see the horizon and the satellites are very far away, so we can see them in exactly half of the solid angle. Then your approach would say that we should need about four satellites "uniformly" distributed at the vertices of a regular tetrahedron to always have two in sight. This is obviously not the case, since three of them can be concentrated in the lower $((-1/3)-(-1))/2=1/3$ of the full solid angle. A numerical simulation shows that in this scenario, about $17.5\%$ of the Earth would only see one satellite, $65\%$ would see two, and $17.5\%$ would see three.

In this simplified scenario, the problem wouldn't occur with any of the other Platonic solids, since they all have opposing vertices so exactly half of them would always be in view. However, going back to the realistic case where we see about $30\%$ of the solid angle, it just so happens that your approach would predict $20$ satellites to be enough to see $6$ of them all the time, so we could try using a regular icosahedron for this case. A numerical simulation shows that in this case $3\%$ of the Earth would see only $4$ satellites, $20\%$ would see $5$, $51\%$ would see $6$, and $26\%$ would see $7$.

So even if we put the satellites on the vertices of a Platonic solid, and even if we could fix them in place (which we can't in these orbits), $20$ satellites would already be cutting it pretty close. If you now take into account that the configuration has to make up for the shifts caused by the movements of the satellites, $24$ is beginning to appear less redundant than it seems at first sight.

-
Thank you very much. Your tetrahedron counter-example and the numerical simulations are really helpful. – netvope Sep 12 '11 at 2:37
Furthering your point about the horizon -- in the western US, it's very common for people to hike through steep-sided canyons. Imagine the Grand Canyon as an extreme example. From such a location, very little of the sky is visible. You get a similar situation in places like Manhattan or downtown San Francisco. – Ben Crowell Jul 24 '12 at 0:24