Celestial Synchronization (Part 1 of 2): An Optimization Based Approach to Maximize Satellite-Ground Station Interactions
Introduction
In the boundless expanse of space, a captivating dance unfolds — a synchronization of satellites and ground stations, each playing a vital role in the transmission of data. It’s a scene that blends science fiction with mathematical precision, where optimization becomes the guiding star. Welcome to the realm where Python’s PuLP package transforms complex equations into seamless interactions.
Addressing Critical Gaps
Amidst the marvels of modern technology, significant gaps persist in the optimization landscape:
- Limited Consideration of Constraints: Existing studies often overlook crucial constraints such as energy and data limitations, leading to suboptimal solutions that fail to reflect real-world operational constraints.
- Single-Satellite Focus: The focus on single-satellite optimization leaves the complexity of multi-satellite constellations, including inter-satellite communication, unaddressed.
- Scalability Challenges: Efficiency and effectiveness of scheduling algorithms for large-scale satellite constellations pose significant scalability challenges.
- Absence of Agile Satellite Constellation Studies: The absence of agile satellite constellation studies neglects the unique operational challenges associated with a cluster of multiple coordinated satellites.
As we venture deeper into the intricacies of satellite-ground station interactions, these gaps serve as beacons, guiding our quest for comprehensive optimization solutions.
Understanding the Problem
Imagine a scenario where multiple satellites need to communicate with a network of ground stations within predefined time windows. Each satellite has its own download time requirements, and there are setup times involved when transitioning between different satellites and ground stations. For simplicity, we’ve demonstrated the above problem for just 2 satellites and 2 ground stations in Fig 2. Our objective is to maximize processing time while adhering to constraints such as download time limits and setup time intervals. The following approach is inspired by existing research in the field, particularly the mathematical optimization model proposed in a relevant research paper [1].
Optimization Model
To tackle this optimization problem, we’ve developed a Python function leveraging the power of PuLP, a linear programming package. The optimization model serves as the foundation of our solution and is based on prior research findings. It is designed to maximize processing time while considering download times for each satellite and adhering to various constraints.
Objective Function
Maximize [W1∑(s, g, k)p(s, g, k) + (1-W1)Zs]
where:
- p(s, g, k) represents the processing time for satellite s interacting with ground station g. within time window k belongs to set of satellite-ground station time windows i.e. {TW(1, 1), TW(1, 2), TW(2, 1), TW(2, 2)}
- Zs denotes the download time for satellite s.
- W1 is the weight of the objective function coefficients between 0 and 1
# Set of all Satellites
S = ["s1", "s2"]
# Set of all Ground Stations
G = ["g1", "g2"]
# Set of all Time Windows in 'minutes' assuming evenly spaced from TW1 to TW8
TW = {
("s1", "g1", "s1g1") : (1, 4),
("s1", "g2", "s1g2") : (3, 5),
("s2", "g1", "s2g1") : (2, 7),
("s2", "g2", "s2g2") : (6, 8)
}
# Set of all downloading times in 'minutes' for each satellite (Assumed values)
Z = {
"s1" : 1.8,
"s2" : 2.7
}
# Objective function weights
W1 = 0.5
# Decision Variables
assignment = LpVariable.dicts(
"x",
[(s, g, s+g) for s in S for g in G],
lowBound=0,
cat="Binary"
)
processing_times = LpVariable.dicts(
"p",
[(s, g, s+g) for s in S for g in G],
lowBound=0,
cat="Continuous"
)
satellite_setup_times = LpVariable.dicts(
"Tau_s",
[(s, g1, g2) for s in S for g1, g2 in zip(G, G[1:])],
lowBound=1,
cat="Continuous"
)
ground_station_setup_times = LpVariable.dicts(
"Tau_g",
[(g, s1, s2) for g in G for s1, s2 in zip(S, S[1:])],
lowBound=1,
cat="Continuous"
)
# Define the model objective functions
model = LpProblem("Maximize Processing Time", LpMaximize)
model += (
W1*(lpSum(processing_times)) +
(1-W1)*round(sum([Z[s] for s in S]), 1)
)Constraints
The download time for each satellite must be within the set time windows i.e Z ≤ ∑(g,k)p(s, g, k) ∀ s ∈ {s1, s2}
for s in S:
model+= Z[s] <= lpSum(
[processing_times[(s, g, s+g)] for g in G]
)Next, we add the lower and upper bounds of the start and download processing times for each time window if the corresponding binary decision variable x(s, g, k) equals 1: 0 ≤ p(s, g, k) ≤ δ(s, g, k) − t(s, g, k)
for i in assignment.keys():
model += processing_times[i] <= (
assignment[i] * (max(TW[i]) - min(TW[i]))
)Next, a satellite can interact with only 1 ground station at a time:
∑(g, k)x(s, g, k) ∀ s ∈ {s1, s2}
for s in S:
model += lpSum([assignment[(s, g, s+g)] for g in G]) == 1Similarly, a ground station can interact with only 1 satellite at a time:
∑(s, k)x(s, g, k) ∀ g∈ {g1, g2}
for g in G:
model += lpSum([assignment[(s, g, s+g)] for s in S]) == 1A satellite interacting can start its task in the next time window only after completing its task in the previous time window:
min(TW(s, g1,k)) + p(s, g1, k) + τ(s, (g1, k), (g2, k)) ≤ min(TW(s, g2,k))
∀ s ∈ {s1, s2}. Here τ(s, (g1, k), (g2, k)) is the setup time for satellite when switching from one ground station to the next.
for s in S:
for g in G:
kes = (s, g, s+g)
next_gs = kes[1][0] + str(int(kes[1][1])+1)
if next_gs in G:
kes_2 = kes[0], next_gs, kes[0]+next_gs
model += (
(
min(TW[kes]) +
processing_times[kes] +
satellite_setup_times[kes[0], kes[1], next_gs]
) <= min(TW[kes_2])
)Similarly, a ground station can start its task in the next time window only after completing its task in the previous time window:
min(TW(s1, g, k)) + p(s1, g, k) + τ(g, (s1, k), (s2, k)) ≤ min(TW(s2, g, k))
∀ g ∈ {g1, g2}. Here τ(g, (s1, k), (s2, k)) is the setup time for ground station’s antenna when switching from one satellite to the next.
for g in G:
for s in S:
kes = (s, g, s+g)
next_sat = kes[0][0] + str(int(kes[0][1])+1)
if next_sat in S:
kes_2 = next_sat, kes[1], next_sat+kes[1]
model += (
min(TW[kes]) +
processing_times[kes] +
ground_station_setup_times[kes[1], kes[0], next_sat]
) <= max(TW[next_sat, kes[1], next_sat+kes[1]])Optimal Solution
Now that we have defined the decision variables, formulated the objective function along with the constraints, we can obtain the optimal solution as follows. The code below outputs the most mathematically efficient schedule for satellite and ground station interaction within set time windows!
model = download_interval_schedule(
S=["s1", "s2"],
G=["g1", "g2"],
TW={
("s1", "g1", "s1g1") : (1, 4),
("s1", "g2", "s1g2") : (3, 5),
("s2", "g1", "s2g1") : (2, 7),
("s2", "g2", "s2g2") : (6, 8)
},
Z={
"s1": 2.0,
"s2": 3.0
},
W1=0.5
)
print("Model Status:", "\n",LpStatus[model.status], "Solution")
print(
"\nMaximum task completion time (Processing + Download):", "\n",
value(model.objective),
"minutes"
)
print("\nAssignment Variables:")
for v in model.variablesDict():
if "x_"in v and model.variablesDict()[v].varValue>0:
print(" ", v, "=", model.variablesDict()[v].varValue)
print("\nProcessing Times:")
for v in model.variablesDict():
if "p_"in v and model.variablesDict()[v].varValue>0:
print(
" ", v, "=",
model.variablesDict()[v].varValue,
"minutes"
)
print("\nSatellite-Ground Station Setup Times:")
for v in model.variablesDict():
if "Tau_s"in v and model.variablesDict()[v].varValue>0:
print(
" ", v, "=",
model.variablesDict()[v].varValue,
"minutes"
)
print("\nGround Station-Satellite Setup Times:")
for v in model.variablesDict():
if "Tau_g"in v and model.variablesDict()[v].varValue>0:
print(
" ", v, "=",
model.variablesDict()[v].varValue,
"minutes"
)
print("\nProposed Optimal Schedule:")
for s in S:
for g in G:
if model.variablesDict()[
"x_('{}',_'{}',_'{}')".format(s, g, s+g)
].varValue==1:
print(
" Satellite '{}' to interact with Ground Station '{}'".format(s, g),
"within Time Window",
TW[(s, g, s+g)],
"with a processing time of {} minutes".format(
model.variablesDict()[
"p_('{}',_'{}',_'{}')".format(s, g, s+g)
].varValue
)
)
Conclusion
By integrating the mathematical optimization model from existing research with Python implementation using PuLP, we can efficiently schedule interactions between satellites and ground stations while maximizing processing time and adhering to constraints. This approach not only streamlines communication operations but also lays the groundwork for further enhancements in satellite network management.
In the dynamic landscape of satellite communication, leveraging existing research insights alongside computational tools like PuLP is crucial for advancing optimization solutions. By building upon prior knowledge and utilizing modern optimization techniques, we can drive innovation and efficiency in satellite system management.
GitHub Link to the entire code can be found here:
https://github.com/mohiteprathamesh1996/satellite-interval-scheduling.git
References
1. Cho, D.H., Kim, J.H., Choi, H.L. and Ahn, J., 2018. Optimization-based scheduling method for agile earth-observing satellite constellation. Journal of Aerospace Information Systems, 15(11), pp.611–626
