Communications of the ACM

Last byte

Orbit Design

By Dennis Shasha
Communications of the ACM, January 2022, Vol. 65 No. 1, Pages 120-ff
10.1145/3498585
Comments

A satellite on a "Repeat Ground Track Orbit" (Repeat Orbit for short) passes the same points on earth on every orbit at a known repeat period. Equatorial orbits (satellites that orbit the equator) are obviously Repeat Orbit but others can be too if they are timed just right. For example, if an orbit took 24 hours (well, 23 hours, 56 minutes and a little over 4 seconds) then a polar orbit would be a Repeat Orbit.

Satellites can be characterized by the intervals within their orbital period during which they are in line-of-sight communication with at least some ground station. Those intervals will not generally cover the whole orbital period, because some ground station may be out of order or because the satellite is flying over an area without ground stations (for example, over an ocean).

So, if the orbit period is T, the coverage times of a single satellite is a sequence of disjoint begin-end times bi, ei.

[b1…e1], [b2..e2], …

where e1 < b2, e2 < b3, …

The orbit designer can specify that satellites are placed in orbit at certain time differences between them, for example, satellite A may be m1 minutes before satellite B in the orbit and B may be m2 minutes before C, and so forth.

An easy lower bound on the required number of satellites so that at least one satellite is in contact with at least one ground station at all times is:

ceiling(T/((e1-b1)+ (e2-b2) + …)

Figure. If the coverage map is 10..60 for a 90-minute orbit, when in the orbit should each of two satellites start in order to give full coverage?

This expression is the orbit time T divided by the total coverage times during an orbit. Note that because the last interval must begin before T but might end in the next orbit, we allow the last end point to have a value greater than T.

An optimal design (one requiring the fewest satellites) may have no satellite starting at time 0 in the period.

Warm-Up: Suppose the coverage map is just the single interval 10..60 for a 90-minute orbit. When in the period should the satellites begin?

---

Satellites can be characterized by the intervals within their orbital periods during which they are in line-of-site communication with at least some ground station.

---

Solution to Warm-Up: One satellite starts at time 80, so it covers time 0 to 50 in each period. The other starts at time 40 covering 50 to 90.

---

Achieving the optimal bound may not always be possible though.

---

Achieving the optimal bound may not always be possible though. Keeping the orbit at T = 90 minutes, suppose the coverage map is 0..30 and 41..56. The total coverage time is (30 - 0) + (56-41) = 45. Therefore ceiling(T/(sum over (ei - bi))) = 2. Let's see whether two satellites are enough.

Warm-Up 2: Suppose satellite A starts the orbit at time 0. Suppose further that the second satellite B starts at time 31 in order to cover minutes 31 to 46. Would there be gaps in coverage?

Solution to Warm-up 2: In that case, A would cover 0..30 and 41..56, B would cover 31..61 and 72..87, but there would be no coverage in the ranges 62..71 or 88..90.

That particular schedule did not work, but might another one work better?

Question 1: Given a period T = 90 and a coverage map of 0..30 and 41..56, is there any two satellite combination that would have no gaps in coverage?

Solution to Question 1: After deploying satellite A, there is an 11-minute gap and a 24-minute gap. For satellite B to cover the 11-minute gap, satellite B must use either its 30-minute coverage interval or its 15-minute coverage interval. Regardless of which one B uses, B's coverage time will overlap time that satellite A already covers. Those "wasted" minutes mean satellite B will not be able to cover both gaps, because, well, B has no minutes to waste.

Question 2: Can you add a third satellite to achieve full coverage?

Solution to Question 2: With respect to the design of Warm-Up 2, adding a satellite C that starts at 61 is one of many solutions.

Now that you understand the problem, here are some upstart questions, some of which might be NP-complete.

Upstart 1: Given a coverage map, can you find a minimal set of satellites and their time offsets allowing no gaps.

Upstart 2: Given a coverage map, can you find a minimal set of satellites and their time offsets allowing k gaps of up to p minutes each.

Upstart 3: Given a coverage map and a satellite budget of s satellites at most and the knowledge that each additional ground station is in line-of-sight communication with a satellite for m minutes, where in the orbit would you place the ground stations to stay within the satellite budget?

My NYU colleague Ernest Davis pointed out the simplest greedy algorithm—choose the offset that covers the most uncovered time—is in fact a (very) special case of the greedy algorithm for the set-cover problem, which is known to be within a log factor of optimal. It is easy to construct examples where the greedy algorithm gives a solution that is close to twice optimal, but we do not know of anything between those two bounds.

Davis and Scott Aaronson of the University of Texas, Austin, TX, also looked into the specific solution where, at every time, exactly one satellite can communicate with the ground. It turns out this is a difficult problem that has been extensively studied and not entirely solved; it is called the problem of "translational tiling."

 Further Reading

Kolountzakis, M.N. and Matolcsi, M.
Algorithms for translational tiling. Journal of Mathematics and Music 3, 2 (2009), 85–97; https://doi.org/10.1080/17459730903040899

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2022 ACM, Inc.

---

No entries found