Keywords

1 Introduction

In recent years, the satellites have been paid more attention to due to the requirement of high communication rate and communication quality. Especially, the wide coverage of satellites is the main advantage and beneficial to the extension of terrestrial network. Hence, some satellite assisted terrestrial networks have been investigated by many scholars. In [1], the authors considered a satellite based Internet of Things system with the application of non-orthogonal multiple access (NOMA) technique. They provided an efficient resource allocation method for improving the network utility from the view of long-term optimization. In [2], the authors provided the deep Q-learning approach for allocating the computing and communication resources for satellite-terrestrial networks. The satellite acting as the base station has been used to serve the users in remote areas where users are divided into many cells according to location [3]. Moreover, they given the efficient data offloading method to improve the e energy efficiency. Similarly, the authors in [4] have taken into account the energy efficient problem for cognitive satellite terrestrial networks.

However, the existing work above paid more attention to the case of single satellite. In order to meet the higher communication requirements, the satellite services have tended to be networked. Hence, inter-satellite links are the key point for constructing the satellite networks. Some work has been done for the application of inter-satellite links. In [5], the authors investigated the download time allocation method by using inter-satellite links. With the increasing number of inter-satellite links, the optimal routing of each data flow becomes more difficult. Hence, the estimation method of hop-count for each path was studied in [6]. Moreover, the inter-plane connectivity was analyzed by [7]. Based on the analysis, an inter-satellite links establishment method was given. The authors investigated the inter-satellite links design for the dual-hop satellite network by using graph theory. For more details about the inter-satellite communication, the authors in [9] have provided a survey to conclude them.

Motivated by the existing work above, this paper focused on the inter-satellite links establishment method so as to reduce the energy consumption. The main contributions are concluded as follows.

  • The satellite network model was introduced to provide the computing service. The inter-satellite links establishment and routing problems were formulated as a mixed integer linear programming.

  • To decrease the computation complexity, a Lagrange relaxation method was used to find the suboptimal solution.

  • The simulation results have been provided for showing the validity of the proposed algorithm.

The remainder of this paper was organized as follows. In Sect. 2, the system model and problem formulation were given. Section 3 provided the main solution method of energy minimization problem. Section 4 analyzed the simulation results with different parameters. Finally, a conclusion was given in Sect. 5.

2 System Model and Problem Formulation

2.1 System Model

As described in Fig. 1, this paper takes into account such a satellite network that consists of M general satellites, a ground station, and the edge satellite which refers to the satellite with limited computing capabilities. The ground station is supposed to connect to the cloud service center and hence has infinite computing capabilities. In the beginning, the source satellite generates the computation task with a specific delay requirement. However, due to the lack of computing capabilities, the source satellite has to offload the task to the edge satellites or ground station through some relay satellites. For the path from source satellite to the ground station, there are usually a lot of communication cost and storage cost due to the long transmission path. Although the path from source satellite to the edge satellites is short, the costs usually consist of communication cost, storage cost, and computing cost due to the limited computing capabilities. Hence, there is a tradeoff between the two approaches. In addition, due to the limited number of antennas, only some inter-satellite links are feasible even if a satellite is visible to more than one satellite. Hence, it is critical to decide the inter-satellite links in order to ensure that the task can arrive in the specified time with a low cost.

The relative positions between satellites is time varying since the satellites move at high speed in their orbits. Therefore, the inter-satellite links and the satellite-ground links also change dynamically. To deal with the dynamics, the whole time period is divided into N continuous time slots \(\mathcal {T}=\{t_{1},t_{2},\ldots ,t_{N}\}\) of which the duration is \(\tau \). The topology of the network is regarded as fixed in each time slot but variational for different time slots.

Fig. 1.
figure 1

The satellite network model.

Full size image

2.2 Problem Formulation

The main focus of this paper is to minimize the cost of the task transmission with the time constraint. Before giving the optimization problem, the definition of cost is first provided as follows.

$$\begin{aligned} \begin{aligned} c_{t,i,j}^{1}=(p_{t,i,j}+q_{t,i,j})\frac{x_{t,i,j}}{C_{t,i,j}} \end{aligned} \end{aligned}$$
(1)

where \(c_{t,i,j}^{1}\) means the communication cost for the inter-satellite link between the satellite i and satellite j at the time slot t. Specifically, \(p_{t,i,j}\) and \(q_{t,i,j}\) represent the transmitted power and received power, respectively. \(x_{t,i,j}\) and \(C_{t,i,j}\) denote the data volume and the transmission rate from satellite i to satellite j at the time slot t, respectively. The transmission rate can be calculated as

$$\begin{aligned} \begin{aligned} C_{t,i,j}=B\log (1+\frac{p_{t,i,j}G_{i}^{1}G_{j}^{2}L_{t,i,j}}{N_{p}}) \end{aligned} \end{aligned}$$
(2)

where \(G_{i}^{1}\) denotes the transmission antenna gain of satellite i. \(G_{i}^{2}\) denotes the receiving antenna gain of satellite j. \(L_{t,i,j}\) represents the path loss of inter-satellite link at the time slot t. \(N_{p}\) refers to the noise. The path loss \(L_{t,i,j}\) is time varying due to the dynamic change of distance and is expressed as follows.

$$\begin{aligned} \begin{aligned} L_{t,i,j}=\left( \frac{v}{4\pi f d_{t,i,j}}\right) ^{2} \end{aligned} \end{aligned}$$
(3)

where v is the velocity of light, f is the carrier frequency, \(d_{t,i,j}\) is the distance between satellite i and satellite j.

Not all data can be transmitted to the destination in one time slot. Hence, the data storage is necessary but also leads to the storage cost which can be expressed as

$$\begin{aligned} \begin{aligned} c_{t,i}^{2}=\tau b_{t,i}P_{i} \end{aligned} \end{aligned}$$
(4)

where \(b_{t,i}\) is the amount of data stored on the satellite i at the time slot t. \(P_{i}\) is the price of storage.

Due to the limited computing resource, if the task will be transmitted to the edge satellite, then there is a computing cost expressed as

$$\begin{aligned} \begin{aligned} c_{t,i}^{3}=Q_{i}\sum _{j=1}^{M}\frac{x_{t,i,j}}{f_{i}} \end{aligned} \end{aligned}$$
(5)

where \(f_{i}\) is the computing capacities of satellite i and \(Q_{i}\) is the computing price.

Hence, the total cost of task is the summation of the communication cost, storage cost, and computing cost.

$$\begin{aligned} \begin{aligned} E=\sum _{t=1}^{N}\sum _{i=1}^{M}\left( \sum _{j=1}^{M}c_{t,i,j}^{1}+c_{t,i}^{2}+c_{t,i}^{3}\right) \end{aligned} \end{aligned}$$
(6)

For each satellite, the input flow should equal the output flow. If the data is not fully transmitted, it should be temporarily cached in itself. Then, we can write it as

$$\begin{aligned} \begin{aligned} \sum _{j=1}^{M}x_{t,i,j}+b_{t,i}=\sum _{j=1}^{M}x_{t,j,i}+b_{t-1,i} \end{aligned} \end{aligned}$$
(7)

At the initial moment, the source satellite I create task with the data volume D. To ensure that the task is successfully transmitted, the data volume of task received by destination node J is also D after N time slot. Then, we can obtain the following constraints.

$$\begin{aligned} \begin{aligned} \sum _{j=1}^{M}x_{1,I,j}+b_{1,I}=D \end{aligned} \end{aligned}$$
(8)
$$\begin{aligned} \begin{aligned} \sum _{t=1}^{N}\sum _{i=1}^{M}x_{t,i,J}=D \end{aligned} \end{aligned}$$
(9)

For each inter-satellite link, the amount of information transmitted can not be more than the link capacity. Then, we can express it as

$$\begin{aligned} \begin{aligned} x_{t,i,j}\le \tau C_{t,i,j} \end{aligned} \end{aligned}$$
(10)

Similar to the Eq. (10), the storage data also can not exceed the satellite’s storage capacity, i.e.,

$$\begin{aligned} \begin{aligned} b_{t,i}\le B_{i} \end{aligned} \end{aligned}$$
(11)

where \(B_{i}\) is the storage capacity of i-th satellite.

Considering the limited number of antennas on the satellite, it is assumed that the satellite or ground station can only communicate with at most U satellites or ground stations within its visual range. In order to express the connection state of communication link, a binary variable \(a_{t,i,j}\) is introduced in this model. \(a_{t,i,j}=1\) means that the i-th satellite established the inter-satellite link with the j-th satellite at the time slot t. Based on the definition above, some constraint can be provided.

$$\begin{aligned} \begin{aligned} \sum _{i=1}^{M}a_{t,i,j}\le U \end{aligned} \end{aligned}$$
(12)
$$\begin{aligned} \begin{aligned} \sum _{j=1}^{M}a_{t,i,j}\le U \end{aligned} \end{aligned}$$
(13)
$$\begin{aligned} \begin{aligned} a_{t,i,j}=a_{t,j,i} \end{aligned} \end{aligned}$$
(14)

The Eq. (11) and (12) are the constraints of limited number of antennas. The constraint (14) indicates the inter-satellite link is bidirectional.

In addition, the data flow can be transmitted from i-th satellite to j-th satellite only if there exists an inter-satellite link.

$$\begin{aligned} \begin{aligned} x_{t,i,j}\le \tau a_{t,i,j}C_{t,i,j} \end{aligned} \end{aligned}$$
(15)

Finally, the task completion time must not exceed the time requirement.

$$\begin{aligned} \begin{aligned} T_{total}\le T \end{aligned} \end{aligned}$$
(16)

For the constraint (16), we can calculate the number of time slot \(N=\frac{T}{\tau }\). Then, the constraint (16) is equivalent to \(t\le N\).

Then, the final optimization problem can be written as

$$\begin{aligned} \begin{aligned} \min ~&E\\ s.t.~&(7)-(15) \end{aligned} \end{aligned}$$
(17)

The main optimization variables are \(a_{t,i,j}\) and \(a_{t,i,j}\). The optimization problem (17) is the mixed integer linear programming. For obtaining the optimal solution, the exhaustive method is the feasible method but the computational complexity of this method is exponential. Hence, the optimal solution is difficult and impractical. To reduce the complexity, it is necessary to investigate an efficient algorithm.

3 Lagrange Relaxation Based Solving Method

In this section, the Lagrange relaxation based method is applied to deal with the optimization problem (17). It can be seen that the main difficulty is due to the coupling constraint (15). Hence, the optimization problem (17) can be decomposed into two subproblems by relaxing the constraint (15). The relaxed problem is written as

$$\begin{aligned} \begin{aligned} z(\boldsymbol{\lambda })=\min ~&E+\sum _{t=1}^{N}\sum _{i=1}^{M}\sum _{j=1}^{M}\lambda _{t,i,j}\left( x_{t,i,j}-\tau a_{t,i,j}C_{t,i,j}\right) \\ s.t.~&(7)-(9),(10)-(15) \end{aligned} \end{aligned}$$
(18)

Then, it can be seen that the variables have been separated. Moreover, the relaxed optimization problem (18) is equivalent to the following two subproblems \(\mathcal {P}1\) and \(\mathcal {P}2\).

$$\begin{aligned} \begin{aligned} \mathcal {P}1: \min ~&E+\sum _{t=1}^{N}\sum _{i=1}^{M}\sum _{j=1}^{M}\lambda _{t,i,j}x_{t,i,j}\\ s.t.~&\sum _{j=1}^{M}x_{t,i,j}+b_{t,i}=\sum _{j=1}^{M}x_{t,j,i}+b_{t-1,i}\\&\sum _{j=1}^{M}x_{1,I,j}+b_{1,I}=D\\&\sum _{t=1}^{N}\sum _{i=1}^{M}x_{t,i,J}=D\\&x_{t,i,j}\le \tau C_{t,i,j}\\&b_{t,i}\le B_{i}\\&x_{t,i,j}\ge 0 \end{aligned} \end{aligned}$$
(19)
$$\begin{aligned} \begin{aligned} \mathcal {P}2:\min ~&\sum _{t=1}^{N}\sum _{i=1}^{M}\sum _{j=1}^{M}\lambda _{t,i,j}\tau a_{t,i,j}C_{t,i,j}\\ s.t.~&\sum _{i=1}^{M}a_{t,i,j}\le U\\&\sum _{j=1}^{M}a_{t,i,j}\le U\\&a_{t,i,j}=a_{t,j,i}\\&a_{t,i,j}\in \{0,1\} \end{aligned} \end{aligned}$$
(20)

3.1 Solving Problem \(\mathcal {P}1\)

There are two options for each task. One is to transmit the task to edge satellite. Because the total data volume is fixed, the computing cost is also fixed. The another is to transmit the task to ground station where the computing cost can be neglected. Hence, regardless of which method the source satellite uses, the computing cost can be regarded as a constant and therefore can be removed for the optimization problem \(\mathcal {P}1\). Then, we can rewrite the objective function as

$$\begin{aligned} \begin{aligned} \min ~&\sum _{t=1}^{N}\sum _{i=1}^{M}\sum _{j=1}^{M}\mu _{t,i,j}x_{t,i,j}+\sum _{t=1}^{N}\sum _{i=1}^{M}\rho _{t,i}b_{t,i}\\ s.t.~&\sum _{j=1}^{M}x_{t,i,j}+b_{t,i}=\sum _{j=1}^{M}x_{t,j,i}+b_{t-1,i}\\&\sum _{j=1}^{M}x_{1,I,j}+b_{1,I}=D\\&\sum _{t=1}^{N}\sum _{i=1}^{M}x_{t,i,J}=D\\&x_{t,i,j}\le \tau C_{t,i,j}\\&b_{t,i}\le B_{i}\\&x_{t,i,j}\ge 0 \end{aligned} \end{aligned}$$
(21)

where \(\mu _{t,i,j}=\lambda _{t,i,j}+\frac{p_{t,i,j}+q_{t,i,j}}{C_{t,i,j}}\) and \(\rho _{t,i}=\tau P_{i}\).

Fig. 2.
figure 2

The time evolution graph of satellite network.

Full size image

It can be seen that the reformulated problem (21) can be regarded as the min-cost max-flow problem. To show it, we first create the time evolution graph \(\mathcal {G}\). As shown in Fig. 2, the time evolution graph \(\mathcal {G}\) consists of three kinds of edges, i.e., communication edges, storage edges, and virtual edges. According to the problem (21), the cost and capacity of communication edges are \(\mu _{t,i,j}\) and \(\tau C_{t,i,j}\), respectively. The cost and capacity of storage edges are \(\rho _{t,i}\) and \(B_{i}\), respectively. Because the satellite network is dynamic, the time at which data arrives at its destination may vary. Hence, we add the virtual node to represent the final destination SG and create the virtual edges with the destination at the different time slots. For the virtual edges, the cost is zero and the capacity is infinity. Then, the problem (21) can be though of the min-cost max-flow problem from source satellite to the final destination SG.

3.2 Solving Problem \(\mathcal {P}2\)

The optimization problem \(\mathcal {P}2\) is still an integer programming. But taking notice of that the optimization problem \(\mathcal {P}2\) is separable in terms of the time slot, hence the solving complexity can be reduced. Then, the optimization problem \(\mathcal {P}2\) can be dealt with by solving the following N subproblems in parallel.

$$\begin{aligned} \begin{aligned} \min ~&\sum _{i=1}^{M}\sum _{j=1}^{M}\lambda _{t,i,j}\tau a_{t,i,j}C_{t,i,j}\\ s.t.~&\sum _{i=1}^{M}a_{t,i,j}\le U\\&\sum _{j=1}^{M}a_{t,i,j}\le U\\&a_{t,i,j}=a_{t,j,i}\\&a_{t,i,j}\in \{0,1\} \end{aligned} \end{aligned}$$
(22)

On the one hand, the number of variables is less for each subproblem. On other hand, the optimization subproblem is sparse when U is small. Therefore, the branch and bound method is efficient for solving such a problem.

figure a

3.3 Optimizing Lagrange Multiplier

The optimization problem (17) is rewritten as optimization problem (18) by relaxing the constraint (15). For the fixed lagrangian multipliers, the optimal solution is a lower bound of the optimization problem (17). Then, to get close to the optimal solution, it is necessary to optimize the lagrangian multipliers.

$$\begin{aligned} \begin{aligned} \max ~&z(\boldsymbol{\lambda })\\ s.t.~&\boldsymbol{\lambda }\ge 0 \end{aligned} \end{aligned}$$
(23)

Then, a subgradient method is applied to find the optimal solution of problem (24). The update rule of lagrangian multipliers is provided as follows.

$$\begin{aligned} \begin{aligned} \lambda _{t,i,j}^{k+1}=\left[ \lambda _{t,i,j}^{k}-\phi ^{k} \left( x_{t,i,j}^{k}-\tau a_{t,i,j}^{k}C_{t,i,j}\right) \right] _{0}^{+} \end{aligned} \end{aligned}$$
(24)

where \([x]_{0}^{+}=\max \{0,x\}\) and \(\phi ^{k}\) is the step size at the k-th iteration. The step size \(\phi ^{k}\) satisfies the following conditions.

$$\begin{aligned} \begin{aligned} \sum _{k=1}^{\infty }\phi ^{k}=\infty , \lim _{k\rightarrow \infty }\phi ^{k}=0 \end{aligned} \end{aligned}$$
(25)

3.4 Solution Reconstruction Method

Although the relaxed solution is close to the optimal solution of problem (17), the relaxed solution may be not feasible. To find an optimized feasible solution, an efficient reconstruction method needs to be investigated. It can be seen that the optimal solution \(\boldsymbol{a}\) of problem \(\mathcal {P}2\) is always feasible. Hence, we only need to make sure the optimal solution \(\boldsymbol{x}\) feasible by keeping the the optimal solution \(\boldsymbol{a}\) fixed. Specifically, for the given optimal solution \(\boldsymbol{a}\), update the link capacity as \(\tau a_{t,i,j}C_{t,i,j}\). Then, solve the the min-cost max-flow problem again and obtain the new optimal solution \(\boldsymbol{x}^{*}\). The whole detailed solution process can be referred to Algorithm 1.

Table 1. The parameters in simulation.
Full size table

4 Simulation Results

This section provided the simulation results for evaluating the effectiveness of proposed algorithm. By using the Satellite Tool Kit (STK), we created a Walker constellation with the type “Delta”. The parameters of seed satellite are listed as follows. The orbit altitude is 14000 km. The inclination is \(60^{\circ }\). The right ascension of ascending node is \(0^{\circ }\). The true anomaly is \(120^{\circ }\). Then, an edge satellite was created with the parameters that the orbit altitude, inclination, right ascension of ascending node, and true anomaly are 3000 km, \(45^{\circ }\), \(0^{\circ }\), \(45^{\circ }\). Other parameters used in this paper are listed in Table 1. Moreover, the random inter-satellite links scheduling are used to compare with the proposed algorithm. The random inter-satellite links scheduling means that the inter-satellite links are built randomly in each time slot under the condition that the constraints are satisfied.

Fig. 3.
figure 3

The energy consumption versus the length of time slot.

Full size image
Fig. 4.
figure 4

The energy consumption versus the data volume.

Full size image

In Fig. 3, the relationship between the length of time slot and the energy consumption has been shown. As we can see, the energy consumption increases with the length of time slot growing. The reason is that the transmission power of each satellite is fixed. For some inter-satellite links, the resource is wasted because the link capacity is not fully utilized. In addition, compared with the random algorithm, the energy consumption has been obviously decreased by using our proposed algorithm. Hence, an optimized inter-satellite links scheduling is necessary for improving the network performance.

Fig. 5.
figure 5

The energy consumption versus the transmission power.

Full size image

In Fig. 4, the relationship between energy consumption and data volume is demonstrated. It is obvious that the energy consumption increases with the increasing of the data volume. As we can see, the proposed algorithm is always superior to the random algorithm. For example, the energy consumption is reduced by 108% when the data volume is 3.4 Gbits. Moreover, when the data volume is more than 4.4 Gbits, there is even no feasible path to ensure that the task is successfully transmitted at the required time. Hence, reasonable and efficient inter-satellite link scheduling is crucial to make full use of the resource.

Figure 5 provides the relationship between the transmission power and the energy consumption. For the random algorithm, increased transmission power must lead to the increase of the energy consumption because the length of time slot and number of links are given. For the proposed algorithm, the inter-satellite links are built only if there is data flow through the link. Hence, the energy consumption with the proposed algorithm is always lower than it with the random algorithm. Even though, similar to Fig. 3, the link capacities of some inter-satellite links may be not fully utilized. Moreover, the energy consumption will increases but not by much. Hence, it is unnecessary to improve the transmission power unless there is no feasible paths.

5 Conclusions

This paper proposed the satellite network model aiming to provide the computing services for satellites with some requirements. Once the source satellites generate the computation missions, they can select to offload the missions to edge satellites or ground station. Then, the corresponding optimization problem was formulated as the mixed integer linear programming. To save the energy consumption and allocate resources quickly, a Lagrange relaxation based method was proposed to decide the inter-satellite links design scheme and routing planning. According to the simulation results, the energy consumption was significantly reduced by using the proposed algorithm.