Model and Problem Formulation¶
A. Network model¶
Definition 1: To tackle the temporal variations in the ISTN, we denote an ordered time set as \(\mathcal{T} = \{t_1, t_2, \dots\}\). The elements of the set \(\mathcal{T}\) are called time points, where \(t_c < t_{c+1}\). The network topology can be considered unchanged between adjacent time points. \((t_{c+1} - t_c)\) represents the minimum time granularity of network topology change. In practice a space-ground connection lasts for minutes at most. Thus we set the time granularity to one second and simply describe the time set as \(\mathcal{T} = \{1, 2, \dots, T\}\). The dynamic network topology model can then be characterized by introducing the time set \(\mathcal{T}\).
Definition 2: The network topology at each time point \(t \in \mathcal{T}\) can be formulated as an undirected graph \(G^t = (\mathcal{V}, \mathcal{E}^t)\), where \(\mathcal{V}\) is the set of network nodes and \(\mathcal{E}^t\) is the set of active communication links.
Specifically, assume \(\mathcal{V}\) is the set of all network nodes such that \(\mathcal{V} = \mathcal{V}_S \cup \mathcal{V}_G\), where \(\mathcal{V}_S = \{s_1, \dots, s_i, \dots, s_{N_S}\}\) and \(\mathcal{V}_G = \{g_1, \dots, g_{N_G}\}\) represent the node sets of satellites and GSes respectively. The LEO constellation consists of \(N\) orbital planes, with \(M\) satellites in each plane. The total number of satellites is \(N_S = |\mathcal{V}_S| = N \cdot M\). Assume \(s_i = s^{(p,q)}\) (\(\forall 1 \le q \le M, 1 \le p \le N\)) represents the \(i^{th}\) satellite, where \(i^p\) is the plane number, \(i^q\) is the index number in its orbit and \(i = i^p M + i^q\). The total number of GSes is \(N_G = |\mathcal{V}_G|\).
Definition 3: The connectivity between satellites and GSes describes whether a GSL can be established between them. The connectivity at time \(t\) is constrained by their relative position and antenna's minimum elevation angle. Based on the predictability of the satellites' position, the connectivity between the satellite \(s_i\) and the GS \(g_j\) at any time \(t\) can be calculated in advance, denoted by \(L = (\ell_{ij}^t)_{T \times |N_S| \times |N_G|}\)
\(\mathcal{E}^t\) is the set of active communication links, including ISLs and GSLs. \(\forall 1 < t < T\), the ISLs in \(\mathcal{E}^t\) are the same. The GSLs will change over time \(t\) which are decided by satellite-ground interconnection scheme, denoted by \(\tilde{L} = (\tilde{\ell}_{ij}^t)_{T \times |N_S| \times |N_G|}\) such that:
For the GSes, their locations are carefully selected, so the non-line-of-sight probability of their GSLs is small [9]. The high hardware configuration of the GS antennas (e.g., EIRP, G/T) also makes the signal strength less affected by the elevation angle. Therefore, we omit the influence of elevation angle on the signal strength and assume GSLs can be set up as long as the satellite elevation angle reaches the minimum elevation angle, i.e., the satellite is visible to the GS.
Definition 4: The hop count between GS pairs, e.g., \(g_j\) and \(g_{j'}\), at time \(t\) is the number of hops of the shortest path between them by using Dijkstra algorithm under graph \(G^t\) (only \(\mathcal{L}^t\) will change with \(t\)), which is described by a matrix \(H^t = \text{Dijkstra}(\mathcal{L}^t) = (h_{jj'}^t)_{|N_G| \times |N_G|}\).
As the cost of SN is higher than that of terrestrial network, and SN is more advantageous under long-distance transmission, it is not necessary for all GS pairs to transmit through SN. We introduce a 0-1 matrix \(D=(d_{jj'})_ {|N_G| \times |N_G|}\) to represent the communication requirements of GS pairs.
Since each GS will not have communication requirements with all other GSes, the handover of one GS will only affect the stations with communication requirements. For example, a GSL change of GS \(g_j\) will not affect the reachability between the GS \(g_{j'}\) and \(g_{j''}\). We define the satellite-ground topology change between GS pair as follows.
Definition 5: The (satellite-ground) topology change between GS pair, \(g_j\) and \(g_{j'}\), happens at time \(t\) if any GSL of \(g_j\) or \(g_{j'}\) is connected or disconnected at time \(t\). Further, the average topology change interval in \(\mathcal{T}\) between GS pair \(g_j\) and \(g_{j'}\), denoted by \(\Delta_{jj'}^{\mathcal{T}}\), can be computed using Algorithm 1.
| 符号 (Symbol) | 名称 (Name) | 定义与解释 (Definition & Explanation) |
|---|---|---|
| \(\mathcal{T}\) | 有序时间集 (Ordered Time Set) | 将连续时间离散化得到的一系列有序时间点，如 \(\{1, 2, ..., T\}\)。模型在此基础上分析网络动态。 |
| \(G^t = (\mathcal{V}, \mathcal{E}^t)\) | 网络拓扑图 (Network Topology Graph) | 在特定时间点 \(t\) 的网络快照，由节点 (\(\mathcal{V}\)) 和该时刻的活动链路 (\(\mathcal{E}^t\)) 构成。 |
| \(\mathcal{V}_S, \mathcal{V}_G\) | 节点集 (Node Sets) | 分别代表网络中所有卫星节点和地面站节点的集合。 |
| \(\ell_{ij}^t\) | 潜在地星连接 (Potential GSL Connectivity) | 二元变量 (0或1)，表示在时间 \(t\) 卫星 \(s_i\) 和地面站 \(g_j\) 是否因物理可见（满足最小仰角）而可能建立连接。 |
| \(\tilde{\ell}_{ij}^t\) | 实际地星连接 (Actual GSL Connectivity) | 二元变量 (0或1)，表示在时间 \(t\) 卫星 \(s_i\) 和地面站 \(g_j\) 是否根据某个互联方案实际建立了连接。 |
| \(H^t = (h_{jj'}^t)\) | 跳数 (Hop Count) | 性能指标。在时间 \(t\)，地面站 \(g_j\) 和 \(g_{j'}\) 之间最短路径的跳数。用于衡量路径性能或时延。 |
| \(D = (d_{jj'})\) | 通信需求矩阵 (Communication Requirements Matrix) | 二元矩阵 (0或1)，用于标识哪些地面站对之间有实际的通信需求，从而让分析更有针对性。 |
| \(\Delta_{jj'}^{\mathcal{T}}\) | 平均拓扑变化间隔 (Average Topology Change Interval) | 核心稳定性指标。衡量有通信需求的地面站对 (\(g_j, g_{j'}\)) 的拓扑平均多久变化一次。间隔越长，路径越稳定。 |
B. Problem formulation¶
As shown in Figure 3, high network reachability can be guaranteed when the topology change interval is reduced to a certain threshold by optimizing the routing protocol, such as adjusting the HELLO_INTERVAL in OSPF. Therefore, while assuring the average topology change interval between GSes exceeds a certain threshold, the goal of this work is to minimize the average maximum latency between the GS pairs which have communication requirements to achieve low latency and jitter at the same time. We formulate the Low-latency Satellite-Ground Interconnecting (LSGI) problem as follows.
Subject to
Variables: \(\tilde{L} = (\tilde{\ell}_{ij}^t)_{T \times |N_S| \times |N_G|}; g_j, g_{j'} \in \mathcal{V}_G; s_i \in \mathcal{V}_S\)
The objective function (1) indicates that the optimization goal is to minimize the average maximum hops between all GS pairs which have communication requirements during time \(\mathcal{T}\), where we use hops to approximate the latency. By computing the GSL establishment \(\tilde{\ell}_{ij}^t\) between satellite \(s_i\) and GS \(g_j\) at each time \(t\), the minimum hop count between any GS pair is updated using the Dijkstra algorithm, as shown in constraint (2). Constraint (3) describes that \(s_i\) and \(g_j\) can establish a GSL only when they are visible. Constraint (4) limits the number of GSLs that a GS can establish. Constraint (5) limits the average topology change interval between all the GS pairs which have communication requirements to no less than a certain threshold, denoted as \(\theta_T\).
Fact: 网络的稳定性（通过“拓扑变化间隔”来衡量）和性能（通过“时延”来衡量）之间存在一种权衡关系。过于追求瞬时的最低时延可能会导致连接频繁切换，破坏稳定性
Aim: 在一个预设的“网络稳定性”门槛之上，去最小化所有通信路径的“平均最大时延”
| Item | Definition & Explanation |
|---|---|
| 问题名称 | 低时延星地互联问题 (Low-latency Satellite-Ground Interconnecting, LSGI) |
| 核心目标 | 在保证网络连接稳定性（即拓扑变化不能过于频繁）的前提下，寻找一个最优的星地连接调度方案，以最小化网络传输的平均最大时延（及抖动）。 |
| 目标函数 (Formula 1) | \(\min \frac{\sum \sum \max d_{jj'} h_{jj'}^t}{\sum \sum d_{jj'}}\) \<br>\<br> 解释: 最小化所有“有通信需求的地面站对”的平均最大跳数。此处用跳数近似时延。关注“最大值”是为了抑制时延抖动(jitter)，提升路径性能的稳定性与可预测性。 |
| 决策变量 | \(\tilde{L} = (\tilde{\ell}_{ij}^t)\) \<br>\<br> 解释: 一个三维0-1矩阵 ，是整个问题的求解目标。 它代表了在整个时间周期内，完整的星地连接调度方案。即在每个时间点 \(t\)，每个地面站 \(j\) 应该连接到哪个卫星 \(i\). |
| 约束条件 | 一个可行的连接方案 \(\tilde{L}\) 必须满足以下所有条件： |
| 约束 (2): 路径计算 | \((h_{jj'}^t) = \text{Dijkstra}(\tilde{L}^t)\) \<br>\<br> 解释: 任意时刻的跳数(\(h\))由当前实际连接图(\(\\tilde{L}^t\))通过Dijkstra最短路径算法决定。 |
| 约束 (3): 物理可行性 | \(\tilde{\ell}_{ij}^t \le \ell_{ij}^t\) \<br>\<br> 解释: 实际连接(\(\\tilde{\\ell}\))不能凭空建立，必须基于物理上的可见性(潜在连接, \(\\ell\))。 |
| 约束 (4): 唯一连接 | \(\sum_{i=1}^{N_S} \tilde{\ell}_{ij}^t = 1\) \<br>\<br> 解释: 在任意时刻，每个地面站必须且只能连接到一个接入卫星。 |
| 约束 (5): 核心稳定性 | \(\Delta_{jj'}^{\mathcal{T}} \ge \theta_T\) \<br>\<br> 解释: 所有通信地面站对的平均拓扑变化间隔(\(\\Delta\))必须不小于一个预设的稳定性阈值(\(\\theta\_T\))。此约束是保证网络稳定、避免频繁切换的关键。 |
C. Complexity analysis¶
If a GS can see at least \(\psi\) satellites at time t, the GS will have \(\psi\)(may exceed 20) choices for access satellite. Then there will be up to \(\psi^{N_G}\) possible topologies, which is impossible to search in a limited time with the increase of GSes. However, even if the number of GSes is very small and LSGI at a single time point can be completed in a short time, LSGI on time set \(\mathcal{T}\) cannot be completed in a limited time. This is because LSGI of multiple time points cannot be directly transformed into that of each single time point. Therefore, the total time complexity will be as high as \(\psi^{N_G \cdot T}\). We will decompose the problem and introduce an approximate algorithm in the next section.
如果在时间点 \(t\)，一个地面站（GS）至少可以看到 \(\psi\) 颗卫星，那么该地面站将有 \(\psi\) 个（可能超过20个）接入卫星的选择。因此，随着地面站数量（\(N_G\)）的增加，将存在多达 \(\psi^{N_G}\) 种可能的拓扑结构，在有限时间内完成搜索是不可能的。
然而， 即便地面站数量很少，且在单一时间点上的LSGI问题可以在短时间内完成，在整个时间集 \(\mathcal{T}\) 上的LSGI问题也无法在有限时间内解决。
这是因为 多个时间点的LSGI问题不能被直接分解为每个单一时间点问题的简单组合（注：由于存在跨时间的稳定性约束，各时间点的决策相互依赖） 因此，总的时间复杂度将高达 \(\psi^{N_G \cdot T}\)。我们将在下一章节中对该问题进行分解，并引入一个近似算法。