BeiDou satellites cross-regional communication path assignment model and resource management

Abstract

Time division inter-satellite communication and ranging link assignment of BeiDou satellites have made important progress; however, there is still the unsolved issue of integrated communication between ground gateway, aircraft, or even ship, and the BeiDou satellites. Therefore, in this study, we develop a path assignment model based on the idea of clustering and Markov chain. The optimal path is determined by the objective function based on the maximum transition probability. The transition probability takes into account the communication environment, congestion status, aircraft mobility, and reduces the complexity of path assignment by hiding the topology in the region. At the same time, due to the limited resources of onboard computing, storage and bandwidth, we also design a resource management strategy based on task urgency, aimed at minimizing the unreasonable allocation index, to enable the readjustment of link application resources. Finally, the performance of the model and the strategy in average link handover times, link reliability, resource allocation fairness, and network quality of service is determined by simulation.

Introduction

The BeiDou-3 (BD3) global navigation satellite system announced the completion of networking in June 2020. BD3 inter-satellite link (ISL) allocation technology enables the integration of communication and navigation functions, and the short message function provides support for the integrated communication between satellites and earth. ¹ However, existing research mainly focuses on the satellite layer, such as timeslot division based on time division multiple access (TDMA), ISL assignment.^2,3 There are few studies that consider the cross-regional communication of the ground gateway, ship, and aircraft. Therefore, when the ground or ocean nodes establish communication links with BD3, the development of a path assignment model to obtain lower link handover times, improve the fairness of BD3 resources, and improve network service quality is the main research of this article.

With the rapid development of cross-regional communication, it is necessary to improve communication capabilities across network areas and facilitate the construction of comprehensively integrated space, land, air, and ocean systems. ⁴ Satellite and fifth generation (5G) communication technologies have ensured seamless network access from urban to rural areas; ⁵ furthermore, cloud and edge computing has been widely used in the network, and the integration of ground Internet of Things (IoT) and satellite network is a hot research topic. ⁶ However, geographic factors have led to a relative lack of awareness of ocean and stratospheric information. Especially in the marine domain, although the oceans occupy 71% of the total surface area of the Earth, related cross-regional communication technology has not received sufficient attention. ⁷ At the same time, marine equipment tends to form cluster communication networks. ⁸ However, due to severe weather in long-distance sailing areas, the stability of the radio communication between ships and satellites is often poor, and deterioration of the link quality often occurs. Since a common solution for ensuring the efficient transmission of data is by means of aircraft or ground gateway relays, ⁹ the problem of cross-regional communication path assignment emerges.

Cross-regional communication is an advanced concept, and it still faces many challenges, such as complex candidate paths and unreasonable resource allocation. ¹⁰ The first challenge is the path assignment problem. Cross-regional communication requires the consideration of all network nodes in the space, sky, ground, and ocean, meaning that the number of nodes is extremely large and the factors affecting the link reliability are complex. Therefore, it is necessary to establish an efficient cross-regional communication model and design a stable path assignment strategy. Next, once the optimal path has been found, multiple links often need to connect to the same satellite simultaneously, which requires a reasonable resource management mechanism to maximize allocation capacity. ¹¹ When the resource demand reaches the upper limit of satellite capacity, the resources must be reasonably allocated to ensure fairness for all links.

The remainder of the article is organized as follows. The section “Related work” discusses the existing research. The section “Cross-regional Communication Model for the BDS” designs the cross-regional communication model, Markov transition probability model (MTPM), based on Markov chain with the ideal of clustering. In the section “Parameter determination of the MTPM,” the parameter determination method of MTPM is described. In the section “Onboard resource management strategy based on MTPM,” three types of resources are proposed, and the resource allocation strategy based on fairness is presented. The section “Simulation” verifies the effectiveness of the proposed model and strategy through simulations, and the section “Conclusion” summarizes the entire study.

Related work

Data transmission between the BeiDou satellite (BDS) and the ground, the sky, and the ocean is known as integrated communication technology, in which multidomain information sharing and situation awareness have always been the research hotspots. Furthermore, two important issues are path assignment and resource management, and the latter needs to be built on the former. The existing research is as follows.

First, the problem of timeslot link allocation of the BDS is studied by Yan et al. ² To minimize communication delays, a multi-objective optimization model is adopted to enable the ISL planning of global navigation satellite system (GNSS). In the study by Zhang et al., ³ the real orbit model of BD3 satellite is proposed, and the bidirectional ranging of BD3 satellite is studied based on the concept of ground station tracking. Sun et al. ¹² uses the anchor satellite model and replaces the objective function with PDOP minimization, which verified the feasibility of a genetic algorithm (GA) to solve the problem. In the study by Liu et al., ¹³ a laser/radio hybrid network based on BDS was developed to balance the problems of slow antenna alignment time and difficult change of laser transmission direction. The multiobjective simulated annealing algorithm (MSAA) was used to solve the problem. Sun et al. ¹⁴ combined aircraft with the BDS, considered the dynamic attitude changes of the aircraft, and realized the integrated air–space–ground communication. Zhao et al. ¹⁵ adopted the integration between the BDS and the ground gateway, which is usually called the heaven and earth integration communication. The strategic objectives are to minimize the number of link handoffs with the minimum number of route updates and the maximum throughput. Ocean vessels carrying a large number of deep-sea exploration data have not been considered in the integrated communication network model based on the BDS.

Network quality of service (QoS) and resource allocation are also concerns in integrated communication. QoS includes congestion avoidance, load balancing, QoS guarantees, and other technologies. ¹⁶ Li et al. ¹⁷ established a low earth orbit (LEO) satellite model and designed a QoS routing (QSR) strategy with the aim of minimizing delay and packet loss. In the study by Wu et al., ¹⁸ a global-view–based intelligent QSR (IQR) algorithm and controller placement strategy were designed to adapt to varying QoS requirements. In the study by Boero et al., ¹⁹ three geosynchronous equatorial orbit (GEO) satellites were used as controllers to guarantee the effect of cross-region transmission delays. Bi et al. ¹⁰ proposed a software-defined (SD) architecture called software-defined space and terrestrial integrated network (SD-STIN), in which virtual resource collection was realized by adding an abstract layer, and discussed the significance of security, resource management, and data forwarding. Qiu et al. ²⁰ designed a model with resource scheduling and realized the joint allocation of subscriber resources through a deep Q-learning (DQL) algorithm. However, this model was designed only to minimize the consumer cost, without considering the QoS requirements of different tasks, and the resource types considered were relatively limited. In the study by Tahmasebi et al., ²¹ controller placement in software-defined network (SDN) was realized using an evolutionary optimal controller placement (SYCOP) strategy on the premise of ensuring load balancing and fault reconfiguration, but no experiment involving the satellite networks was conducted. Jia et al. ²² designed a framework based on satellite topology and studied its computing efficiency and resource preallocation, but focused only on the satellite layer. Therefore, the main contributions of this article are as follows.

1. We make full use of the edge gateway, and the idea of clustering is adopted to establish the MTPM to achieve cross-regional path assignment.

2. We determine the parameters in the MTPM and get the assignment result. The MTPM considers four factors, including regional weather, aircraft mobility, link congestion status, and remaining connection time, to ensure the maximum transition probability of the path assignment.

3. In view of the limited resources of the BDS, the Markov resource management strategy (MRMS) based on mission urgency is proposed to achieve a reasonable allocation of computing, storage, and bandwidth resources with the goal of fair allocation.

Cross-regional communication model for the BDS

Problem description and modeling

As shown in Figure 1, considering the mobility of BDS and the constraints of the antenna number, it is assumed that ISL is only established between medium earth orbit satellites, MEO2 and MEO3; and SG, G, and AG represent ship gateway, ground station, and aircraft gateway, respectively. When G1 transmits data to MEO1, assuming that there is no relay node between them, data can only be transmitted directly through the satellite ground link (SGL), $G1\to \mathrm{MEO}1$ .

Figure 1.

Schematic diagram of the cross-regional communication network.

When SG transmits data to MEO3, there are three types of routing cases, $\mathrm{SG}\to \mathrm{MEO}2\to \mathrm{MEO}3;\mathrm{SG}\to \mathrm{AG}\to \mathrm{MEO}2\to \mathrm{MEO}3;\mathrm{SG}\to \mathrm{AG}\to G2\to \mathrm{MEO}3$ , because SG has relay node AG, which is only in the communication range of MEO2. When the troposphere disturbance is small, the green path is better, but when the troposphere is unstable or MEO2 is in congestion, the yellow and blue bypass schemes are needed. The purpose of our path assignment model is to determine the optimal transmission path to transmit the Earth’s data to the BDS. The data show that when the number of nodes in Figure 1 is large, the situation of candidate routes is complex.

Therefore, this article establishes a path assignment model named MTPM, to reduce the number of candidate paths and the number of average handover times, and improve the link reliability.

The communication architecture is divided into the ocean layer, the astronautical layer, the terminal layer, and the atmospheric layer. Combined with network function virtualization (NFV), ¹⁰ a cross-regional communication model based on a Markov chain with the idea of clustering is established. In Figure 2, the red ellipses represent the controllers, which are responsible for routing and resource management in each domain. The black ellipses represent the edge gateways for each spatial region, and the blue ellipses represent the common nodes, which periodically send data to their corresponding edge gateways. This route planning is similar to the role of anchor satellites. ³ In the figure, P(i,j) is used to denote the transition probability of the path between nodes i and j. The solid lines represent candidate virtual paths and the circular dotted line represents the maximum communication range of gateway 2. All data are transmitted only between black ellipses.

Figure 2.

The MTPM cross-regional communication model.

A Markov chain with clustering idea strengthens the role of edge gateway, ²³ nodes have different functions, and common nodes have only intradomain communication capability, which is more in line with the framework of SDN/NFV. ¹⁰

Two propositions

The improved Markov chain based on clustering idea, MTPM, has the following advantages:

Proposition 1

Suppose that there are $N$ regions; $\mathrm{m}$ represents the number of edge gateways required in each region and $n$ represents the average number of common nodes $(1\le m<n)$ . Then, the total number of gateways is $N_{\mathrm{SUM}}=N\times \mathrm{m}$ , the total number of cross-regional paths based on the MTPM is $\sum _{i=0}^{N-2}{m}^{i+2}{A}_{N-2}^i$ , and the total number of candidate paths based on the global view is $\sum _{j=0}^{N(m+n+1)-2}{A}_{N(m+n+1)-2}^j$ .

Proof

Each region contains $(\mathrm{m}+n+1)$ nodes. If the path assignment relies on the global view instead of using the MTPM, there are $N(\mathrm{m}+n+1)-2$ nodes with relay capabilities, and the set $\left\{\mathrm{j}\right\}=[0,N(\mathrm{m}+n+1)-2]\cap R$ represents the number of intermediate nodes on a path. Then, the number of candidate paths with $\mathrm{j}$ relay nodes is $A_{N(m+n+1)-2}^j$ . Therefore, the total number of candidate paths based on the global view is $\sum _{j=0}^{N(m+n+1)-2}{A}_{N(m+n+1)-2}^j$ . By contrast, the MTPM designed in this article requires that cross-regional communication occurs only between edge gateways; thus, there are ${\mathrm{m}}^2$ possible ways for the initial and terminal nodes to transmit information to their respective edge gateways, and the set $\left\{i\right\}=[0,N-2]\cap R$ represents the number of relay regions. Therefore, when the number of relay regions is $\mathrm{i}$ , there are $A_{N-2}^i$ possible permutations. At the same time, each area has $\mathrm{m}$ candidate gateways, and the number of cross-regional virtual paths based on the MTPM is $\sum _{i=0}^{N-2}{m}^{i+2}{A}_{N-2}^i$ .

The following Proposition 2 shows the effect of adding one gateway node on the total number of candidate paths when only one edge gateway is configured in each region.

Proposition 2

Suppose that the model contains $\mathrm{n}$ edge gateway nodes $(\mathrm{n}\ge 2)$ . Then, there are $S_{\mathrm{sum}}=\sum _{i=0}^{n-2}{S}_i=\sum _{i=0}^{n-2}{A}_{n-2}^i$ candidate paths between any two nodes, and the number of possible candidate paths is increased by $(n-1)+(n-2)S_{\mathrm{sum}}$ with each additional node.

Proof

When two gateways are selected as the source and destination, these two nodes can be connected either directly or through a relay. Accordingly, the number of relay nodes between the source and destination nodes may be $0,1,2,\dots ,n-2$ , corresponding to $n-1$ distinct cases, where each case can be represented by $S_{\mathrm{i}}$ , $\mathrm{i}=0,1,2,\dots ,n-2$ . Then, $S_0=1,S_1=C_{n-2}^1=A_{n-2}^1,S_2=A_{n-2}^2,\dots ,S_2=A_{n-2}^{n-2}$ , and $S_{\mathrm{sum}}=S_0+S_1+\cdots +S_{n-2}=A_{n-2}^0+A_{n-2}^1+\cdots +A_{n-2}^{n-2}=\sum _{i=0}^{n-2}{S}_i=\sum _{i=0}^{n-2}{A}_{n-2}^i$ . The effect of one additional node on the number of candidate paths is shown as follows. To simplify the notation in the following derivation, we define ${\mathrm{a}}_{n-2}=S_1+\cdots +S_{n-2},{\mathrm{b}}_{n-2}=S_{\mathrm{sum}}={\mathrm{a}}_{n-2}+1$ , which yields the following

$$\begin{array}{c}\multicolumn{1}{c}{A_{\mathrm{n}}^{\mathrm{i}}=\frac{n!}{(n-i)!}=n\frac{(n-1)!}{[(n-1)-(i-1)]!}={\mathrm{nA}}_{n-1}^{i-1}}\\ \multicolumn{1}{c}{\frac{1}{n-2}{a}_{n-2}=\frac{1}{n-2}(A_{n-2}^1+A_{n-2}^2+\cdots +A_{n-2}^{n-2})}\\ \multicolumn{1}{c}{=\frac{1}{n-2}((n-2)+((n-2)A_{n-3}^1}\\ \multicolumn{1}{c}{+(n-2)A_{n-3}^2+\cdots +(n-2)A_{n-3}^{n-3}))}\\ \multicolumn{1}{c}{=1+(A_{n-3}^1+A_{n-3}^2+\cdots +A_{n-3}^{n-3})}\\ \multicolumn{1}{c}{=1+a_{n-3}}\\ \multicolumn{1}{c}{a_{n-2}=(n-2)(1+a_{n-3})}\\ \multicolumn{1}{c}{b_{n-2}=(n-1)+(n-2)b_{n-3}}\end{array}$$

The subsection “Problem description and modeling” established the MTPM model, and subsection “Two propositions” proved the effect of improved Markov chain based on clustering idea.

Parameter determination of the MTPM

This section will further explain the determination of MTPM parameters. The subsection “Determination of the transition probability matrix” analyzes the link communication probability from multiple factors, and the subsection “Objective function and constraints” is the final expression.

Determination of the transition probability matrix

The influence of the troposphere on GNSS is expressed by the factor ${\omega }_{\mathrm{ij}}$ , and $W$ is the matrix form. If the congestion probability of each gateway is defined as $P_c$ , and each gateway is connected with $\mathrm{m}$ links, then the available transmission probability allocated to each link is $p_{\mathrm{a}}=\frac{1-p_{\mathrm{c}}}{\mathrm{m}}$ .

Suppose that all nodes have radio receivers such that we can obtain the locations of all $N_{\mathrm{SUM}}$ edge gateways; then, the distance matrix among all gateways can be expressed as follows

$$D=\left[\begin{array}{ccc}{\mathrm{d}}_{\mathrm{MN}}^{11}\hfill & \cdots \hfill & {\mathrm{d}}_{\mathrm{MN}}^{1N_{\mathrm{SUM}}}\hfill \\ \multicolumn{1}{c}{⋮}& \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\mathrm{d}}_{\mathrm{MN}}^{N_{\mathrm{SUM}}1}}& \cdots \hfill & {\mathrm{d}}_{\mathrm{MN}}^{N_{\mathrm{SUM}}{N}_{\mathrm{SUM}}}\hfill \end{array}\right]=D^T$$

(1)

where the subscripts $M,N$ correspond to $\mathrm{o},s,t,a$ , which indicate that the nodes are in the ocean layer, space (astronautical) layer, terminal layer, and atmospheric layer, respectively. Since different devices usually operate at different frequencies, the communication distances between different pairs of gateways will be different; therefore, we define ${\mathrm{D}}_{max}=\left\{d_{\mathrm{MN}}\right\}=\{{\mathrm{d}}_{\mathrm{oo}},{\mathrm{d}}_{\mathrm{os}},{\mathrm{d}}_{\mathrm{ot}},{\mathrm{d}}_{\mathrm{oa}},{\mathrm{d}}_{\mathrm{ss}},{\mathrm{d}}_{\mathrm{st}},d_{\mathrm{sa}},d_{\mathrm{ta}},d_{\mathrm{tt}},d_{\mathrm{aa}}\}$ . Then, we obtain the link connectivity matrix $D_{0,1}$ by comparing the values of the elements of matrix $D$ with the associated elements of ${\mathrm{D}}_{max}$ as follows

$$D_{0,1}=\left[\begin{array}{ccc}{\mathrm{b}}_{11}\hfill & \cdots \hfill & {\mathrm{b}}_{1N_{\mathrm{SUM}}}\hfill \\ \multicolumn{1}{c}{⋮}& \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\mathrm{b}}_{N_{\mathrm{SUM}}1}}& \cdots \hfill & {\mathrm{b}}_{N_{\mathrm{SUM}}{N}_{\mathrm{SUM}}}\hfill \end{array}\right]={D_{0,1}}^T$$

(2)

where ${\mathrm{b}}_{\mathrm{ij}}=\{0,1\}$ is a connectivity factor indicating whether nodes $\mathrm{i}$ and $\mathrm{j}$ have the ability to establish a link, $i=1,2,\dots ,N_{\mathrm{SUM}}\mathrm{and}j=1,2,\dots ,N_{\mathrm{SUM}}$ . To ensure the reliability of the path assignment, the gateways should consider not only the current connectivity state of each link but also the future stability of this connectivity. The communication sustainability matrix $P_{\mathrm{l}}({\mathrm{d}}_{MN}^{\mathrm{ij}})$ is thus defined as follows

$${\mathrm{P}}_{\mathrm{l}}({\mathrm{d}}_{MN}^{\mathrm{ij}})=D_{0,1}·{\left[\frac{d_{MN}-{\mathrm{d}}_{MN}^{\mathrm{ij}}}{d_{MN}}\right]}_{N_{SUM}\times N_{SUM}}$$

(3)

where $d_{\mathrm{MN}}-{\mathrm{d}}_{\mathrm{MN}}^{\mathrm{ij}}$ denotes the remaining communication distance between gateway $\mathrm{i}$ in layer $M$ and gateway $\mathrm{j}$ in layer $N$ . This matrix defines the corresponding remaining connection time. The main reason for considering the remaining connection time is the mobility of the aircraft.

Neglecting the maritime vessel mobility and the shadow region, ²⁴ the communication model between the ocean layer and the atmospheric layer is shown in Figure 3. Suppose that the gateway of the atmospheric layer is at the position labeled 1. When the aircraft is inside the spherical area depicted, the fleet can establish communication with this air region. However, when the aircraft gateway moves out of this sphere, the fleet loses communication with the air region. If the radius of the spherical area is $R$ and the gateway moves to position 2 at time $\mathrm{t}$ , where the angle between the horizontal direction and the edge of the sphere is $\alpha$ , then the probability of the gateway moving out of the sphere at time $\mathrm{t}+1$ is as follows

$$\begin{array}{c}\multicolumn{1}{c}{{\mathrm{p}}_{\mathrm{un}}\left({\mathrm{d}}_{\mathrm{os}}^{\mathrm{ij}}\right)={\mathrm{p}}_{\mathrm{un}}\left({\mathrm{d}}_{\mathrm{ts}}^{\mathrm{ij}}\right)=\frac{1}{2}\underset{\genfrac{}{}{0ex}{}{\sqrt{R^2-{\mathrm{b}}^2\sin \alpha }-b\cos \alpha <\mathrm{vT}}{0\le \mathrm{vT}<2R,0\le \alpha \le 2\pi ,0\le z<2R}}{\int \int \int }\frac{v}{4\pi b}\mathbf{d}\alpha \mathbf{d}t\mathbf{d}z}\\ \multicolumn{1}{c}{=\frac{1}{\pi R}[\underset{R-b}{\overset{R+b}{\int }}\arccos \frac{R^2-b^2-{\left(\mathrm{vT}\right)}^2}{2\mathrm{bvT}}\mathbf{d}c-R+b]}\end{array}$$

(4)

Figure 3.

Communication model considering the mobility of the aircraft.

where $p_{\mathrm{un}}({\mathrm{d}}_{\mathrm{os}}^{\mathrm{ij}})$ and $p_{\mathrm{un}}({\mathrm{d}}_{\mathrm{ts}}^{\mathrm{ij}})$ represent the probabilities of connection interruption between the ocean and space layers and between the terminal and atmospheric layers, respectively.

Accordingly, ${\mathrm{P}}_{\mathrm{un}}({\mathrm{d}}_{MN}^{\mathrm{ij}})$ can be generated as follows when aircraft mobility is considered

$$\begin{array}{c}\multicolumn{1}{c}{{\mathrm{P}}_{\mathrm{un}}\left({\mathrm{d}}_{\mathrm{MN}}^{\mathrm{ij}}\right)=\left[\begin{array}{ccc}{\mathrm{p}}_{\mathrm{un}}\left({\mathrm{d}}_{\mathrm{MN}}^{11}\right)\hfill & \cdots \hfill & {\mathrm{p}}_{\mathrm{un}}\left({\mathrm{d}}_{\mathrm{MN}}^{1N_{\mathrm{SUM}}}\right)\hfill \\ \multicolumn{1}{c}{⋮}& \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\mathrm{p}}_{\mathrm{un}}\left({\mathrm{d}}_{\mathrm{MN}}^{N_{\mathrm{SUM}}1}\right)}& \cdots \hfill & {\mathrm{p}}_{\mathrm{un}}\left({\mathrm{d}}_{\mathrm{MN}}^{N_{\mathrm{SUM}}{N}_{\mathrm{SUM}}}\right)\hfill \end{array}\right]}\\ \multicolumn{1}{c}{={{\mathrm{P}}_{\mathrm{un}}}^T\left({\mathrm{d}}_{\mathrm{MN}}^{\mathrm{ij}}\right)}\end{array}$$

(5)

Thus far, the weather impact matrix ${\overline{W}}_{N_{\mathrm{SUM}}\times N_{\mathrm{SUM}}}$ , the link idle probability matrix ${\mathrm{P}}_{\mathrm{a}}$ , the communication sustainability matrix $P_{\mathrm{l}}({\mathrm{d}}_{MN}^{\mathrm{ij}})$ , and the connection interruption matrix ${\mathrm{P}}_{\mathrm{un}}({\mathrm{d}}_{MN}^{\mathrm{ij}})$ have been obtained; hence, the Markov transition probability matrix $P_{\mathrm{certain}}({\mathrm{d}}_{MN}^{\mathrm{ij}})$ between any two gateways can be calculated as follows

$$P_{\mathrm{certain}}({\mathrm{d}}_{MN}^{\mathrm{ij}})={\overline{W}}_{N_{SUM}\times N_{SUM}}·{\mathrm{P}}_{\mathrm{a}}·{\mathrm{P}}_{\mathrm{l}}({\mathrm{d}}_{MN}^{\mathrm{ij}})·{\mathrm{P}}_{\mathrm{un}}({\mathrm{d}}_{MN}^{\mathrm{ij}})$$

(6)

Objective function and constraints

The path assignment diagram based on MTPM is shown in Figure 4, where $N_{\mathrm{SUM}}$ represents the total number of nodes. Assuming $i,j$ are the start and destination nodes by existing relay nodes, then the black and red solid lines are two cases of path assignment, and because of symmetry, the dotted line has the same reverse transmission ability. The purpose of path assignment is to determine which path is the best. The optimal path can be expressed as the following nonlinear programming (NLP) problem, where $s=1,2,\dots ,S_{\mathrm{sum}}$ is used to denote all the paths that may be connected

$$\begin{array}{c}\multicolumn{1}{c}{max{\mathrm{P}}_{\mathrm{ij}}^s=max\{{\mathrm{P}}_{\mathrm{certain}}\left({\mathrm{d}}_{\mathrm{MN}}^{\mathrm{ik}}\right)\times {\mathrm{P}}_{\mathrm{certain}}\left({\mathrm{d}}_{\mathrm{MN}}^{\mathrm{kl}}\right)}\\ \multicolumn{1}{c}{\times \cdots \times {\mathrm{P}}_{\mathrm{certain}}({\mathrm{d}}_{\mathrm{MN}}^{\mathrm{gj}})\}}\\ s.t.{\mathrm{b}}_{\mathrm{ij}}=\{0,1\},\hfill \\ \forall \mathrm{p}\in [0,1]\hfill \\ \sum _{i,j}{\mathrm{P}}_{\mathrm{certain}}\left({\mathrm{d}}_{\mathrm{ss}}^{\mathrm{ij}}\right)=1\hfill \\ {\mathrm{P}}_{\mathrm{certain}}\left({\mathrm{d}}_{\mathrm{ss}}^{\mathrm{ij}}\right)={\mathrm{P}}_{\mathrm{certain}}\left({\mathrm{d}}_{\mathrm{ss}}^{\mathrm{ji}}\right)\hfill \end{array}$$

(7)

Figure 4.

Path assignment diagram based on Markov transition probability model (MTPM).

where $\mathrm{k},\mathrm{l},\dots ,\mathrm{g}$ represent the relay node. The goal of NLP is to find the path with the maximum transition probability. The first two constraints consider the visibility between nodes and the range of transition probability. The last two constraints ensure each BDS only establishes one ISL at the same time to meet the symmetry. ² In the study by Sun et al., ¹² they proved the ability of GA to solve this model. Based on MTPM, we assign the optimal path between nodes, and use the set $\Xi \left(\mathrm{t}\right)=\{L_1\dots L_i\dots L_r\}$ to represent all paths.

Onboard resource management strategy based on MTPM

General flow of MRMS

In the section “Parameter determination of the MTPM,” the model of the cross-regional communication path assignment for the BDS, MTPM, was established, but the satellite resources are limited. Therefore, the MRMS is designed to guarantee the rationality of resource allocation for each BDS.

As shown in Figure 5, the steps of the MRMS are as follows. Step 1: Each edge gateway uploads its resource request matrix ${\mathrm{P}}_{\mathrm{req}}$ to the BDS, where different resources are represented by the index $\mathrm{m}$ , and each row vector $R_{\mathrm{m}}=[R_{\mathrm{m}1\mathrm{req}},\dots ,R_{\mathrm{m}\mathrm{nreq}}]$ represents the allocation of the $\mathrm{m}\mathrm{th}$ resource to each link $\mathrm{n}$ . Step 2: The satellite calculates $R_{\mathrm{ireal}}=\sum _{j=1}^n{R}_{\mathrm{ij}\mathrm{req}},i=1,2,\dots ,m$ and obtains the vector of the total amount of each type of resource requested by all links $\mathrm{n}$ , $R_{\mathrm{real}}=[R_{1\mathrm{real}},\dots ,R_{\mathrm{ireal}},\dots ,R_{\mathrm{mreal}}]$ , including computational resources, storage resources, and bandwidth resources. Step 3: The satellite compares $R_{\mathrm{real}}$ against the maximum resource vector $R_{max}=[R_{1max},\dots ,R_{mmax}]$ . If the maximum resources of the gateway are not exceeded, then $P_{\mathrm{real}}=P_{\mathrm{req}}$ ; otherwise, the resource allocation process described in the next step will be carried out. Step 4: The satellite evaluates the task types such as remote sensing, meteorological monitoring, and deep sea exploration; recalculates the assignment matrix $P_{\mathrm{mn}}$ ; and then assigns it to $P_{\mathrm{real}}$ as follows

$$P_{\mathrm{real}}=\{\begin{array}{c}{P}_{\mathrm{req}},R_{\mathrm{real}}\le R_{max}\hfill \\ \multicolumn{1}{c}{P_{\mathrm{mn}},R_{\mathrm{real}}>R_{max}}\end{array}$$

(8)

$$P_{\mathrm{req}}=\left[\begin{array}{c}{R}_{11\mathrm{req}},R_{12\mathrm{req}},\dots ,R_{1\mathrm{jreq}},\dots ,R_{1\mathrm{n}\mathrm{req}}\hfill \\ \multicolumn{1}{c}{R_{21\mathrm{req}},R_{22\mathrm{req}},\dots ,R_{2\mathrm{jreq}},\dots ,R_{2\mathrm{n}\mathrm{req}}}\\ \multicolumn{1}{c}{⋮}\\ \multicolumn{1}{c}{R_{\mathrm{m}1\mathrm{req}},R_{\mathrm{m}2\mathrm{req}},\dots ,R_{\mathrm{m}\mathrm{jreq}},\dots ,R_{\mathrm{m}\mathrm{nreq}}}\end{array}\right]=\left[\begin{array}{c}{R}_1\hfill \\ \multicolumn{1}{c}{R_2}\\ \multicolumn{1}{c}{⋮}\\ \multicolumn{1}{c}{R_m}\end{array}\right]$$

(9)

Figure 5.

Flow chart of the MRMS.

The vectors $C_{\mathrm{i}}={[c_{i1},\dots ,c_{\mathrm{in}}]}_{1\times n},i=1,\dots ,m$ , are used to represent the allocation results once the resource allocation for the $\mathrm{n}$ links has been adjusted for the same resource. The set of different regions in the space is defined as $\Re =\{{\mathbb{R}}_1,\dots ,{\mathbb{R}}_r,\dots ,{\mathbb{R}}_N\},\mathrm{r}=1,2,\dots ,N$ , and all nodes in region ${\mathbb{R}}_{\mathrm{r}}$ are represented by $\mathrm{N}\left({\mathbb{R}}_{\mathrm{r}}\right)=\{C_r,E_r^1,\dots ,E_r^{\mathrm{i}},\dots ,E_r^p,N_r^1,\dots ,N_r^j,\dots ,N_r^{\mathrm{n}}\}$ , where $C_r,E_r^{\mathrm{i}}$ and $N_r^{\mathrm{j}}(\mathrm{i}=1,2,\dots ,p,\mathrm{j}=1,2,\dots ,\mathrm{n})$ represent the controller, the ith edge gateway and the jth common node, respectively, of region $\mathrm{r}$ . The set of all edge gateways in region $\mathrm{r}$ is ${\mathrm{E}}_r=\{E_r^1,\dots ,E_r^p\}$ and the bandwidth of edge gateway $E_r^{\mathrm{i}}$ at time $\mathrm{t}$ is $B_{E_{\mathrm{r}}^{\mathrm{i}}\left(\mathrm{t}\right)}$ .

Analysis of the task computing resources

In this analysis, $\Gamma \left(E_{\mathrm{r}}^{\mathrm{i}}\right)=\{{\mathrm{T}}_1,\dots ,{\mathrm{T}}_l\}$ is the set of tasks, and ${\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)\in {\Xi }_{E_{\mathrm{r}}^{\mathrm{i}}}\left(\mathrm{t}\right)$ is the jth link connected to satellite $E_r^{\mathrm{i}}$ , where $\mathrm{j}=1,2,\dots ,n,{\Xi }_{E_{\mathrm{r}}^{\mathrm{i}}}\left(\mathrm{t}\right)\subset \Xi \left(\mathrm{t}\right)$ . The binary set ${\mathrm{U}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}\left(\mathrm{t}\right)=\{{\mathrm{u}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}^{T_1}\left(t\right),\dots ,{\mathrm{u}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}^{T_{\mathrm{l}}}\left(t\right)\}$ indicates whether the jth link of $E_{\mathrm{r}}^{\mathrm{i}}$ needs to be processed, where ${\mathrm{u}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}^{T_l}\left(t\right)\in \{0,1\},0<\sum _j{\mathrm{u}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}^{T_l}\left(t\right)\le l$ . The task set $\Gamma \left(E_{\mathrm{r}}^{\mathrm{i}}\right)=\{{\mathrm{T}}_1\dots {\mathrm{T}}_l\}$ is divided into four categories as $D\mathrm{elR}=\{A,B,C,D\}$ , which describe the communication requirements for four degrees of urgency, that is, delay sensitive, delay guaranteed, delay allowed, and file download tasks. The proportions of these tasks can be expressed as ${\epsilon }_m\left({\mathrm{T}}_l\right),m=A,B,C,D$ . Suppose that the computational resources occupied by different tasks in a unit cycle are ${\varsigma }_i,\mathrm{i}=1,2,\dots ,l$ , and that ${\mathrm{n}}_{{\varsigma }_{\mathrm{i}}}$ represents the number of cycles. $\mathrm{ComR}{\left(\mathrm{t}\right)}_{E_{\mathrm{r}}^{\mathrm{i}}}$ and $\mathrm{ComR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}$ represent the resources that are actually needed and the maximum resource limit, respectively, of $E_{\mathrm{r}}^{\mathrm{i}}$ at time $t$ ; then, for the first resource, the vector of the computational resources allocated by $E_{\mathrm{r}}^{\mathrm{i}}$ to different links can be expressed as $C_1{\left(\mathrm{t}\right)}_{1\times n}={\left[c_{1\mathrm{j}}\left(\mathrm{t}\right)\right]}_{1\times n}$ , where each element of the vector is expressed as follows

$$c_{1\mathrm{j}}\left(\mathrm{t}\right)=\{\begin{array}{c}{R}_{1\mathrm{jreq}},\mathrm{ComR}{\left(\mathrm{t}\right)}_{E_{\mathrm{r}}^{\mathrm{i}}}\le \mathrm{ComR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}\hfill \\ \multicolumn{1}{c}{\frac{\sum _{T_{\mathrm{l}}\in \Gamma \left(E_{\mathrm{r}}^{\mathrm{i}}\right)}{\mathrm{u}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}^{T_l}{\epsilon }_m{\varsigma }_{\mathrm{l}}{\mathrm{n}}_{{\varsigma }_{\mathrm{l}}}}{\sum _{j=1}^n\sum _{T_{\mathrm{l}}\in \Gamma \left(E_{\mathrm{r}}^{\mathrm{i}}\right)}{\mathrm{u}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}^{T_l}{\epsilon }_m{\varsigma }_{\mathrm{l}}{\mathrm{n}}_{{\varsigma }_{\mathrm{l}}}}\mathrm{ComR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}},\mathrm{else}}\end{array}$$

(10)

with $c_{1j}\left(\mathrm{t}\right)\in (0,1]$ . The above equation indicates that if the processing capacity of $E_{\mathrm{r}}^{\mathrm{i}}$ is within the upper limit $C\mathrm{omR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}$ , the resources for all the links are fully allocated. However, when the computational resources are saturated, they must be reallocated in accordance with the different tasks. To enable the evaluation of the policy performance, a metric for assessing the fairness of resource allocation is defined as follows

$$D_{\mathrm{ComR}}=\frac{1}{n}\sum _{j=1}^n{(c_{1\mathrm{j}}-R_{1\mathrm{jreq}})}^2$$

(11)

Without resource reallocation, the satellite will allocate the resource to the link that established the connection first, which means that an urgent task in a later link will not be handled in time, and $D_{\mathrm{ComR}}$ is high. The MRMS adjusts the resources in the links, and $D_{\mathrm{ComR}}$ decreases. In particular, $D_{\mathrm{ComR}}=0$ indicates that the allocation is in the most reasonable state; thus, it is feasible to define $D_{\mathrm{ComR}}$ as a metric to describe the fairness of resource allocation.

Analysis of the storage resources

When the computational resources reach the upper limit of saturation, $\mathrm{ComR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}$ , the remaining data must be temporarily stored. Let $\mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{E_{\mathrm{r}}^{\mathrm{i}}}$ and $\mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}$ represent the actual amount of storage needed and the maximum storage capacity of the satellite, respectively, which must satisfy $\mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{E_{\mathrm{r}}^{\mathrm{i}}}\le \mathrm{Sto}\mathrm{R}{\left(\mathrm{t}\right)}_{{\mathrm{upper}E}_{\mathrm{r}}^{\mathrm{i}}}$ . The storage resources occupied by different tasks in a unit cycle are ${\eta }_i,\mathrm{i}=1,2,\dots ,l$ ; ${\mathrm{n}}_{{\eta }_{\mathrm{i}}}$ is the number of cycles of occupation; and $C_2{\left(\mathrm{t}\right)}_{1\times n}=[c_{2\mathrm{j}}\left(\mathrm{t}\right){]}_{1\times n}$ is the vector of storage resources allocated to link ${\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)$ for each satellite $E_{\mathrm{r}}^{\mathrm{i}}$ . Then, $c_{2\mathrm{j}}\left(\mathrm{t}\right)$ is as follows

$$c_{2\mathrm{j}}\left(\mathrm{t}\right)=\{\begin{array}{c}{R}_{2\mathrm{jreq}},\mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{E_{\mathrm{r}}^{\mathrm{i}}}\le \mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}\hfill \\ \multicolumn{1}{c}{\frac{\sum _{T_{\mathrm{l}}\in \Gamma \left(E_{\mathrm{r}}^{\mathrm{i}}\right)}{\mathrm{u}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}^{T_l}{\epsilon }_m{\eta }_{\mathrm{l}}{\mathrm{n}}_{{\eta }_{\mathrm{l}}}}{\sum _{\mathrm{j}=1}^n\sum _{T_{\mathrm{l}}\in \Gamma \left(E_{\mathrm{r}}^{\mathrm{i}}\right)}{\mathrm{u}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}^{T_l}{\epsilon }_m{\eta }_{\mathrm{l}}{\mathrm{n}}_{{\eta }_{\mathrm{l}}}}\mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}},}\\ \multicolumn{1}{c}{\mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{E_{\mathrm{r}}^{\mathrm{i}}}>\mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}}\end{array}$$

(12)

where $c_{2j}\left(\mathrm{t}\right)\in [0,1]$ . It can be seen from the above equation that when the storage resources are not saturated, the storage resources allocated to each link are the same as the requested values $R_{2\mathrm{jreq}}$ . However, when the storage resources are saturated, $\mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{E_{\mathrm{r}}^{\mathrm{i}}}>\mathrm{S}\mathrm{to}\mathrm{R}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}$ , and $E_{\mathrm{r}}^{\mathrm{i}}$ needs to allocate resources proportionally to ensure fairness among the different links. Thus, the fairness of storage resource allocation $D_{\mathrm{StoR}}$ is defined in the same way.

Analysis of the bandwidth resources

When the propagation delay is long, more bandwidth should be reserved in advance to prevent the bandwidth from being occupied by links with shorter delays. Therefore, it is necessary to design a mechanism to dynamically determine the bandwidth. The propagation delay can be expressed as follows

$$\{\begin{array}{c}0<{\mathrm{d}}_{\mathrm{SL}}^{\mathrm{SL}}\le \frac{2\pi (R_E+R_{\mathrm{LE}})}{\mathrm{c}},\mathrm{gateways}\mathrm{in}\mathrm{the}\mathrm{space}\mathrm{layer}\hfill \\ \multicolumn{1}{c}{0<{\mathrm{d}}_{\mathrm{TL}}^{\mathrm{TL}}={\mathrm{d}}_{\mathrm{OL}}^{\mathrm{OL}}={\mathrm{d}}_{\mathrm{AL}}^{\mathrm{AL}}={\mathrm{d}}_{\mathrm{OL}}^{\mathrm{AL}}={\mathrm{d}}_{\mathrm{OL}}^{\mathrm{TL}}={\mathrm{d}}_{\mathrm{AL}}^{\mathrm{TL}}\le \frac{\pi R_E}{\mathrm{c}},\mathrm{else}}\end{array}$$

(13)

where $M,N$ represents different regions, for example, ${\mathrm{d}}_{\mathrm{TL}}^{\mathrm{TL}}$ denotes the delay within the terminal layer, ${\mathrm{d}}_{\mathrm{TL}}^{\mathrm{AL}}$ denotes the delay between the terminal and atmospheric layers; the speed of light is denoted by $\mathrm{c}$ ; and $(R_E+R_{\mathrm{LE}})$ is the distance between anchor satellite and the center of the Earth

$$\frac{R_{\mathrm{LE}}}{\mathrm{c}}=\min {\mathrm{d}}_{\mathrm{SL}}\le {\mathrm{d}}_{\mathrm{SL}}^{\mathrm{TL}}={\mathrm{d}}_{\mathrm{SL}}^{\mathrm{OL}}={\mathrm{d}}_{\mathrm{SL}}^{\mathrm{AL}}\le \max {\mathrm{d}}_{\mathrm{SL}}$$

(14)

$$\max {\mathrm{d}}_{\mathrm{SL}}=\frac{1}{\mathrm{c}}(\sqrt{{R_E}^2\sin {\theta }_{\mathrm{SL}}+R_{\mathrm{LE}}^2+2R_{\mathrm{LE}}{R}_E}+R_{\mathrm{LE}}\sin {\theta }_{\mathrm{SL}})$$

(15)

where ${\mathrm{d}}_{\mathrm{SL}}^{\mathrm{TL}},{\mathrm{d}}_{\mathrm{SL}}^{\mathrm{OL}}$ , and ${\mathrm{d}}_{\mathrm{SL}}^{\mathrm{AL}}$ are the delays between the space layer and each of the other layers, with ranges expressed as shown in equations (14) and (15); and ${\theta }_{\mathrm{SL}}$ is the minimum elevation angle between a satellite and a vessel/aircraft/ground station. ¹⁹ Moreover, the four task classes have different delay adjustment coefficients ${\lambda }_m,m=A,B,C,D$ , as follows: ${\epsilon }_A=120\mathrm{\%},{\epsilon }_B=100\mathrm{\%},{\epsilon }_C=80\mathrm{\%},{\epsilon }_D=60\mathrm{\%}$ . Thus, a bandwidth reservation threshold ${\chi }_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)}$ can be set such that $C_3{\left(\mathrm{t}\right)}_{1\times n}={\left[c_{3j}\left(t\right)\right]}_{1\times n}={\left[{\chi }_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)}{B}_{E_{\mathrm{r}}^{\mathrm{i}}\left(\mathrm{t}\right)}\right]}_{1\times n}$ will meet the following requirement

$$\frac{{\chi }_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)}{B}_{E_{\mathrm{r}}^{\mathrm{i}}\left(\mathrm{t}\right)}}{{\lambda }_m}+(I_{\mathrm{in}}^{\mathrm{now}}-I_{\mathrm{out}})(\mathrm{\Delta }\mathrm{t}+{\mathrm{d}}_M^N)P_{\mathrm{num}}\le B_{E_{\mathrm{r}}^{\mathrm{i}}\left(\mathrm{t}\right)}$$

(16)

where ${\chi }_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)}\in [0,1]$ , $B_{E_{\mathrm{r}}^{\mathrm{i}}\left(\mathrm{t}\right)}$ is the total bandwidth of the gateway $E_{\mathrm{r}}^{\mathrm{i}}$ , ${\lambda }_m$ is used as the denominator to ensure that the threshold value is proportional to the task urgency, $(\mathrm{\Delta }\mathrm{t}+\mathrm{d})$ is the sum of the update period and the propagation delay, $P_{\mathrm{num}}$ is the packet size, and $I_{\mathrm{out}}$ is the output rate of link ${\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)$ . Also

$$I_{\mathrm{in}}^{\mathrm{now}}\left(t\right)={\beta }_1\mathrm{\Delta }{B}_{r_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}(t-\mathrm{\Delta }t)}+{\beta }_2{I}_{\mathrm{in}}(t-\mathrm{\Delta }t)+{\beta }_3{I}_{\mathrm{in}}\left(t\right)$$

(17)

$$\mathrm{\Delta }{B}_{r_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}(t-\mathrm{\Delta }t)}=\frac{B_{r_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)}-B_{r_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}(t-\mathrm{\Delta }t)}}{B_{r_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}(t-\mathrm{\Delta }t)}}$$

(18)

where $I_{\mathrm{in}}^{\mathrm{now}}\left(t\right)$ represents the transmission rate of link ${\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)$ to satellite $E_{\mathrm{r}}^{\mathrm{i}}$ at time $t$ , which depends on three components: the rate of change $\mathrm{\Delta }{B}_{r_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}(t-\mathrm{\Delta }t)}$ of the bandwidth occupied by link ${\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)$ at time $t-\mathrm{\Delta }t$ , the transmission rate $I_{\mathrm{in}}(t-\mathrm{\Delta }t)$ at time $t-\mathrm{\Delta }t$ , and the transmission rate $I_{\mathrm{in}}\left(t\right)$ at time $t$ . The coefficients satisfy $\sum _{i=1}^3{\beta }_i=1,\beta >0$ . The fairness of bandwidth resource allocation to each link $D_{\chi B}$ is defined in the same way as before.

Finally, the resource management matrix $P_{\mathrm{mn}}$ based on the computational, storage, and bandwidth resources and the total fairness of resource allocation metric $D_{\mathrm{total}}$ are as follows

$$\begin{array}{c}\multicolumn{1}{c}{P_{\mathrm{mn}}={\left[\begin{array}{c}{C}_1\left(\mathrm{t}\right)\hfill \\ \multicolumn{1}{c}{C_2\left(\mathrm{t}\right)}\\ \multicolumn{1}{c}{C_3\left(\mathrm{t}\right)}\end{array}\right]}_{3\times n}}\\ \multicolumn{1}{c}{={\left[\begin{array}{ccccc}{c}_{11}\left(\mathrm{t}\right)\hfill & \cdots \hfill & c_{1\mathrm{j}}\left(\mathrm{t}\right)\hfill & \cdots \hfill & c_{1n}\left(\mathrm{t}\right)\hfill \\ \multicolumn{1}{c}{c_{21}\left(\mathrm{t}\right)}& \cdots \hfill & c_{2j}\left(\mathrm{t}\right)\hfill & \cdots \hfill & c_{2n}\left(\mathrm{t}\right)\hfill \\ \multicolumn{1}{c}{c_{31}\left(\mathrm{t}\right)}& \cdots \hfill & c_{3j}\left(\mathrm{t}\right)\hfill & \cdots \hfill & c_{3n}\left(\mathrm{t}\right)\hfill \end{array}\right]}_{3\times n}}\end{array}$$

(19)

$$D_{\mathrm{total}}=D_{\mathrm{ComR}}+D_{\mathrm{StoR}}+D_{\chi B}$$

(20)

where $O_{\mathrm{j}}\left(\mathrm{t}\right)$ is a column vector, $\mathrm{j}=1,2,\dots ,n$ , and each $O_{\mathrm{j}}\left(\mathrm{t}\right)$ represents the reallocation results for gateway $E_{\mathrm{r}}^{\mathrm{i}}$ for link ${\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}\left(t\right)$ at time $\mathrm{t}$ . The pseudocode of this article is as follows:

Algorithm 1. Strategy of this article.

Preset parameters: Weather matrix $W$ , congestion status $p_{\mathrm{a}}$ , connectivity, and mobility matrix: $D,D_{0,1},R$ , and $T$ . The binary set ${\mathrm{U}}_{{\mathrm{r}}_{E_{\mathrm{r}}^{\mathrm{i}}}^{\mathrm{j}}}\left(\mathrm{t}\right)$ , task proportion ${\epsilon }_m$ , cycle ${\varsigma }_i,{\eta }_i$ , number ${\mathrm{n}}_{{\varsigma }_{\mathrm{i}}},{\mathrm{n}}_{{\eta }_{\mathrm{i}}}$ , $\mathrm{ComR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}},\mathrm{StoR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}$ maximum resource limit, coefficients ${\lambda }_m,{\beta }_i$ , total bandwidth $B_{E_{\mathrm{r}}^{\mathrm{i}}\left(\mathrm{t}\right)}$ , packet size $P_{\mathrm{num}}$ , link output rate $I_{\mathrm{out}}$ , update period $\mathrm{\Delta }\mathrm{t}$ Target: Determine the link with maximum probability ${\max \mathrm{P}}_{\mathrm{ij}}^s$ and resource allocation matrix $P_{\mathrm{mn}}$ Cross-regional communication path assignment: 1. According to $D,D_{0,1}$ , calculate communication remaining time ${\mathrm{P}}_{\mathrm{l}}({\mathrm{d}}_{MN}^{\mathrm{ij}})$ in equation (3) 2. The mobility parameter ${\mathrm{P}}_{\mathrm{un}}({\mathrm{d}}_{MN}^{\mathrm{ij}})$ is calculated by equations (4) and (5) 3. Multiply the parameters that affect the path assignment by equation (6), and solve the model according to equation (7) 4. The link with the maximum probability ${\max \mathrm{P}}_{\mathrm{ij}}^s$ is the path assignment result 5. If $R_{\mathrm{real}}>R_{max}$ 6. while $\mathrm{ComR}{\left(\mathrm{t}\right)}_{E_{\mathrm{r}}^{\mathrm{i}}}>\mathrm{ComR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}$ , do: 7. Calculate according to equation (10) to get $c_{1\mathrm{j}}\left(\mathrm{t}\right)$ 8. end while all points are calculated 9. while $\mathrm{StoR}{\left(\mathrm{t}\right)}_{E_{\mathrm{r}}^{\mathrm{i}}}>\mathrm{StoR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}$ , do: 10. Calculate according to equation (12) to get $c_{2\mathrm{j}}\left(\mathrm{t}\right)$ 11. end while all points are calculated 12. Analysis $c_{3j}\left(t\right)$ with equations (16)–(18) 13. Update the resource allocation matrix $P_{\mathrm{mn}}$ and calculate the evaluation index $D_{\mathrm{total}}$ by equations (19) and (20), and let $P_{\mathrm{real}}=P_{\mathrm{mn}}$ 14. end if 15. else $P_{\mathrm{real}}=P_{\mathrm{req}}$ 16. Output the resource matrix $P_{\mathrm{mn}}$

Simulation

The simulation assumes that the ground station and the ship gateway transmit data to the BDS, and the aircraft acts as the available relay node to verify the effectiveness of the path assignment model and the resource management strategy. Using STK 11 and matlab2016a software and referring to the Internet traffic data in the study by Liu et al. ²⁵ simulated as Figure 6, the simulation time is 1 day (24 h) and the experiment is repeated 10 times to get the average value. The simulation is carried out on a Dell T7600 workstation (2.5 GHz CPU, 8G memory, Windows 8) In this study, we use the optimal enumeration algorithm (OEA) proposed by Liu et al. ²⁶ and the GA proposed by Sun et al. ¹² to prove the validity of MTPM. OEA is an enumeration algorithm, which requires a long computing time. GA has been widely used to solve NLP through genetic, crossover, and mutation operations. At the same time, shortest path first (SPF) ¹⁷ and random joint (RANJ) ²⁶ are compared with MTPM.

Figure 6.

Traffic volume: (a) normalized traffic volume and (b) the difference.

The simulation parameters are shown in Table 1. At the same time, BDSim is used to generate BDS mobility and import it into the simulation. The trajectories of sub-satellite points within 1 h are shown in Figure 7. The color indicates coverage, and the service performance of green curve is much higher than that of red curve. Different satellites are also shown in different colors.

Table 1.

Primary experimental parameters.

BeiDou satellite	MEO Walker24/3/1, orbit height is 21,528 km, incline 55°
Transmission rate	ISL = 2 Mbps (1 packet = 1 kbits), SGL and others are 500 kbps
Longitude and latitude of ground station	BeiJing (40°N, 116°E), Himalaya (28°N, 87°E), Mamiraus (2°S, 66°W), Cape York(11°S, 142.5°E), Alaska Coast (60°N, 148°W), Greenland (69°N, 49°W)
Initial longitude and latitude of the ship	(45°N, 165°W), (50°N, 170°E), (50°S, 90°W), (20°S, 50°E), (15°S, 165°E)
Initial longitude and latitude of the aircraft	(40°N, 110°W), (20°N, 70°W), (45°N, 45°E), (15°N, 105°E), (15°S, 45°W),(50°S, 165°E)
Aircraft mobility	$\mathrm{f}(\mathrm{v},\alpha )~N({10}^3,20,10,0.25,0)$ , R = 10 km, T = 1.2 h
Resource constraints	$\mathrm{ComR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}=800\mathrm{packets},\mathrm{StoR}{\left(\mathrm{t}\right)}_{\mathrm{upper}{E}_{\mathrm{r}}^{\mathrm{i}}}=100\mathrm{packets}$

MEO: medium earth orbit; ISL: inter-satellite link; SGL: satellite ground link.

Figure 7.

Mobility simulation of BeiDou satellite.

Suppose that the ship speed is 30 km/h, the aircraft speed is 1000 km/h, the bandwidth weighting coefficient ${\beta }_1=0.2,{\beta }_2=0.2,{\beta }_3=0.6$ , the state update interval $\mathrm{\Delta }t=10\mathrm{ms},l=10$ , the task period and the occupied resources are staircase functions, and the congestion probability $P_C$ is a function of latitude, ²⁵ which is expressed as follows

$$P_C=\{\begin{array}{c}{P}_{C0}{e}^{\left|\mathrm{Lat}\left(t\right)\right|/{90}^{°}},0^{°}<\mathrm{Lat}\left(t\right)<{50}^{°}\hfill \\ \multicolumn{1}{c}{P_{C0}{e}^{-\left|\mathrm{Lat}\left(t\right)\right|/{90}^{°}},\mathrm{else}}\end{array}$$

(21)

Equation (21) indicates that the degree of congestion is related to latitude; $P_{C0}=0.2$ represents the base congestion, which must satisfy $P_{C0}{e}^{\frac{5}{9}}\le 1$ . Meanwhile, the weather stability matrix is as follows

$$W=\left[\begin{array}{cccc}{\omega }_{\mathrm{tt}}\hfill & {\omega }_{\mathrm{to}}\hfill & {\omega }_{\mathrm{ts}}\hfill & {\omega }_{\mathrm{ta}}\hfill \\ \multicolumn{1}{c}{{\omega }_{\mathrm{ot}}}& {\omega }_{\mathrm{oo}}\hfill & {\omega }_{\mathrm{os}}\hfill & {\omega }_{\mathrm{oa}}\hfill \\ \multicolumn{1}{c}{{\omega }_{\mathrm{st}}}& {\omega }_{\mathrm{so}}\hfill & {\omega }_{\mathrm{ss}}\hfill & {\omega }_{\mathrm{sa}}\hfill \\ \multicolumn{1}{c}{{\omega }_{\mathrm{at}}}& {\omega }_{\mathrm{ao}}\hfill & {\omega }_{\mathrm{as}}\hfill & {\omega }_{\mathrm{aa}}\hfill \end{array}\right]=\left[\begin{array}{cccc}0.9\hfill & 0.3\hfill & 0.6\hfill & 0.9\hfill \\ \multicolumn{1}{c}{0.3}& 0.1\hfill & 0.3\hfill & 0.6\hfill \\ \multicolumn{1}{c}{0.6}& 0.3\hfill & 0.9\hfill & 0.9\hfill \\ \multicolumn{1}{c}{0.9}& 0.6\hfill & 0.9\hfill & 0.9\hfill \end{array}\right]$$

The main metrics of MTPM are link reliability, average link handover times, and convergence time.

Link reliability: using the maximum transition probability in equation (8) to represent the link reliability. That is, because Liu et al. ²⁶ verifies the data transmission capability from the ground to the satellite with the goal of maximizing reliability.

Average link handover times: this indicator is the number of times that all network nodes change links in a day. If the value is high, it indicates that the algorithm does not fully consider the performance of each node. This frequent link handover requires antenna realignment and correction, which we do not want to happen.

Convergence time: it refers to the calculation time of each link update.

In Figure 8, the simulation results of the three models for link reliability index are shown. Taking SPF and RANJ as reference models to measure the performance of MTPM in this study, MTPM-OEA and MTPM-GA achieved good results. This is because SPF is a greedy model based on the shortest path. It marks the shortest path by traversing all possible situations with the goal of minimizing distance. The model is conservative and the influence factors of routing are single. In contrast, RANJ is a random routing model, and the visibility and mobility of the BDS are the important factors affecting the performance. The path assignment model converges rapidly, but the randomness leads to poor link reliability. MTPM has good path reliability under the premise of ensuring convergence speed. The simulation results show that the MTPM in this article is more suitable for integrated communication.

Figure 8.

Link reliability.

As shown in Figure 9, the simulation takes the average link handover times as the performance evaluation index. The average handover times and link duration are the same performance indicators, thus only one of them must be analyzed. Considering the mobility of the BDS, the cross-regional communication will inevitably involve frequent link handover. In the same way, SPF and RANJ are used to verify the performance of MTPM in the path handover times. The value of the three models increase with time, and the average link handover times of RANJ are the most, SPF is relatively moderate, and MTPM-OEA and MTPM-GA achieve the best performance. This is because the only constraint of RANJ to establish links is visibility, that is, network congestion status and mobility factors are ignored; SPF takes into account the distance between nodes on the basis of RANJ, and its performance is improved. MTPM-OEA and MTPM-GA ensure the minimum average link handover times in a day due to the consideration of mobility, remaining connection time, and other factors, and they are resistant to fluctuations from changes in network traffic. At the same time, MTPM-OEA uses a traversal method to find the optimal solution, and the heuristic algorithm applied by MTPM-GA will fall into a local optimum; therefore, the performance of MTPM-OEA is the best.

Figure 9.

Average link handover times.

In Figure 10, the convergence times of the three models are shown. Analyzing the link reliability and the average handover times shows that RANJ achieved the worst performance, while MTPM-OEA and MTPM-GA achieved the best performance. However, the convergence time of each path update is also an important factor. If the convergence time is too long, the algorithm will always be in a divergent state, and the correct solution cannot be obtained and can lead to link handover failure. The simulation results show that the convergence times of the three models are generally stable. RANJ achieved the fastest convergence rate because RANJ only needs to calculate the transition probability of the Markov chain, and the path assignment is random, and thus does not need to solve the complex objective function. Because SPF adopts the ergodic mechanism, it needs to adjust the order after calculating the transition probability of each virtual path, resulting in the highest convergence time. The values of MTPM-OEA and MTPM-GA are acceptable for path updating in the cross-regional communication. Considering the excellent performance in reliability and average handover times, the comprehensive effect of MTPM-OEA and MTPM-GA proposed in this article is positive.

Figure 10.

Convergence time.

The main evaluation indexes of resource management are resource allocation fairness and QoS. Using the BeiDou MEO constellation and assuming that the ground station and ship gateway transmit data to the BDS, based on the MTPM designed in this article, the same satellite is connected with multiple links at the same time and resource allocation fairness is used to ensure that all links occupy the satellite resources fairly. QoS is used to describe the resource allocation capability of MRMS for different task proportions, which is mainly reflected in the link delay and throughput. Taking the SPF as a control group, the performance of different data flows for delay and throughput are simulated to verify the effectiveness of the MTPM and MRMS in this article. The proportion of tasks is shown in Table 2.

Table 2.

Task proportion of four data flows.

Data flow	Task proportion
$\mathrm{tos}1$	${\epsilon }_A=80\mathrm{\%},{\epsilon }_B=10\mathrm{\%},{\epsilon }_C=5\mathrm{\%},{\epsilon }_D=5\mathrm{\%}$
$\mathrm{tos}2$	${\epsilon }_A=25\mathrm{\%},{\epsilon }_B=25\mathrm{\%},{\epsilon }_C=25\mathrm{\%},{\epsilon }_D=25\mathrm{\%}$
$\mathrm{tos}3$	${\epsilon }_A=5\mathrm{\%},{\epsilon }_B=5\mathrm{\%},{\epsilon }_C=10\mathrm{\%},{\epsilon }_D=80\mathrm{\%}$

Figure 11 shows the performance of four situations in resource allocation fairness. The fairness means the fairness degree of onboard resources allocated to different links when multiple links are connected with a BDS. Due to the limitation of the definition, the value is inversely proportional to the fairness. It can be found that since SPF has no resource management mechanism, the resource allocation strictly follows the first-come-first-served principle. When the onboard resources are less than the applied resources, the first connected path has priority occupation rights, and the later connected path will enter the cache queue regardless of whether it contains delay-sensitive tasks or not. The tasks $\mathrm{MRMS}-\mathrm{tos}1,\mathrm{MRMS}-\mathrm{tos}2,\mathrm{MRMS}-\mathrm{tos}3$ are redistributed according to different task types, and the link state is updated in a fixed period, such that the link achieves better fairness performance. In each time period, fairness is satisfied $\mathrm{MRMS}-\mathrm{tos}3>\mathrm{MRMS}-\mathrm{tos}2>\mathrm{MRMS}-\mathrm{tos}1$ , because the proportion of tasks in the data flow is different. The task tos1 is mainly a delay-sensitive task, tos3 is mainly a download task, and tos2 is a uniform task type. When the data stream in the network has a strict demand for delay, it is difficult to allocate resources among multiple links. However, when the data flow has no requirement on delay, resource allocation is easier.

Figure 11.

Fairness of resource allocation.

The simulation results of MRMS for the link delay is shown in Figure 12, where the data show that all curves reach the peak of delay at $[9.6,12]$ and $[14.4,16.8]$ . This is because the traffic distribution in a day reaches the maximum during this period, and the satellite resources limit the transmission bandwidth, resulting in a large link delay. SPF achieves the best transmission performance in the noncongested region $[0,4.8]\cup [21.6,24]$ because the network traffic is low and there is no need for reallocation of resources. However, with the increase of network traffic, $\mathrm{MRMS}-\mathrm{tos}1,\mathrm{MRMS}-\mathrm{tos}2,\mathrm{and}\mathrm{MRMS}-\mathrm{tos}3$ show the importance of resource allocation in interval $[7.2,19.2]$ . The link delay of the three curves is lower than that of SPF at any time, and because different tasks occupy different resources, the link delay meets $\mathrm{MRMS}-\mathrm{tos}1>\mathrm{MRMS}-\mathrm{tos}2>\mathrm{MRMS}-\mathrm{tos}3$ .

Figure 12.

Link delay.

The impact of the MRMS in this article on the network throughput is shown in Figure 13. During the time period $[0,7.2]\cup [21.6,24]$ , because of the unsaturated state of the resources, the data flow in the network is transmitted at the maximum rate, such that the SPF without resource allocation does not need extra calculation time and has high throughput. However, as the network load increases, the satellite resources gradually reach saturation. In addition, the throughput of tos1 with the largest number of tasks is the highest, while the throughput of tos3 with the smallest number of tasks is less than tos1 and tos2 at any time. At the same time, the resource utilization rate of the BeiDou MEO constellation is shown in Table 3, which validates the performance of the MTPM and MRMS proposed in this article.

Figure 13.

Network throughput.

Table 3.

Onboard resource utilization.

Scheme	SPF	$\mathrm{MRMS}-\mathrm{tos}1$	$\mathrm{MRMS}-\mathrm{tos}2$	$\mathrm{MRMS}-\mathrm{tos}3$
Onboardresourceutilization (%)	5.136	27.194	16.332	12.783

MRMS: Markov resource management strategy; SPF: shortest path first.

Conclusion

To solve the problem of path assignment of the BDS cross-regional communication, the MTPM based on Markov chain with the idea of clustering is proposed. Factors such as mobility, congestion state, and remaining connection time are used to determine the transition probability, and the nonlinear objective function based on maximum reliability is developed. Then, considering the limited space resources, the fairness of data flow resource allocation for different task types is studied, and the MRMS is designed to reallocate the computing, storage, and bandwidth resources in the satellite. Finally, the performance of MTPM and MRMS are verified by experiments, and the Walker Constellation is used to transmit the data from the ship and the ground gateway to the BDS based on real Internet traffic data. Using RANJ and SPF as the control group, it is shown that the MTPM improves link reliability, reduces the average link handover times, and has an acceptable convergence time. At the same time, taking four data flows composed of different tasks as examples, the outstanding performance of MRMS in resource allocation fairness, link delay, and network throughput is verified.

Although the model and resource management algorithm designed in this article has a certain QoS support capability, battery energy resources, antenna beam resources, and other factors are not currently taken into account. These considerations can be addressed in future research to improve our work.