1 Introduction

In recent years, the satellite communications have been paid more attention to due to the increasing requirement of high communication rate and communication quality [1,2,3]. Especially, the wide coverage of satellites was the main advantage and beneficial to the extension of terrestrial network. Hence, some satellite assisted terrestrial networks have been investigated to improve the network performance by many scholars. For example, in [4], the authors considered a satellite multi-beam system to provide the services for Internet of Things users and applied the non-orthogonal multiple access (NOMA) technique to improve the spectrum efficiency. Specifically, they provided an efficient resource allocation method for improving the network utility from the view of long-term optimization. In [5], the authors proposed integrated satellite-terrestrial networks to provide a variety of services by using software definition technique. Specially, a deep Q-learning learning framework was given to centrally allocate resources in the whole network including communication resources, computing resources, and so on. The author in [6] investigated the remote user communication scenarios that cannot be covered by ground network and used satellite to construct backhaul link to access the Internet. Moreover, the authors in [7] have taken into account the energy efficient optimization problem for cognitive satellite terrestrial networks based on the statistical information.

However, the existing work above paid more attention to the case that single satellite assisted the ground network to provide extended services or multiple satellites performed the same function independently. Hence, in order to meet the higher communication requirements, collaboration between satellites has become necessary especially with the advent of inter-satellite links (ISLs) [8,9,10]. Through satellite links data can be transmitted from one satellite to another satellite by multi-hop routing thereby reducing network latency and increasing network capacity. However, at present, there are still some difficulties in the study of satellite networks with ISLs such as network connectivity, routing, and so on. In [11], the authors investigated how to use ISLs to transmit satellite observations as much as possible so as to make full use of the visible time of each observing satellite. Moreover, with the increasing number of satellites, routing scheme has become a problem that has to be considered especially the performance analysis of routing. In [12], the authors provided an estimation method for the hop count of routing toward the large constellation satellite networks. Moreover, although ISL can make the whole satellite network connected, network connectivity will be affected by different ISLs establishment method, which will affect the network capacity. In [13], the authors proposed a dynamic ISLs establishment method based on matching algorithm. The authors investigated the ISLs design for the dual-hop satellite network by using graph theory. A summary has been given in [14] to provide more details for the existing work about inter-satellite communication. On other hand, the dynamic nature of satellite networks makes it difficult to plan ISLs since ISLs must be established dynamically. Currently, some graph methods have been proposed to abstract dynamic satellite networks including time expanded graph (TEG) and time aggregated graph (TAG). In [15], the authors provided the TEG for modeling the satellite network and proposed two optimized ISLs establishment method to improve network capacity. In [16], the authors investigated maximum flow problem of two different source-destination flow on the TAG.

Motivated by the existing work above, this paper focused on the network cost minimization for satellite networks. This paper is an expanded version of our conference paper [17]. In the current version, we have added an optimized power allocation method for given ISLs scheduling and analyzed the effect of power allocation optimization on performance in the simulation results. The main contributions are concluded as follows.

  • We proposed the computation offloading driven satellite network with the help of edge computing technique. Then, network cost optimization problem was investigated and formulated as a mixed integer linear programming.

  • With given power allocation method, Lagrange relaxation method was used to optimize the ISLs establishment scheme and routing scheme.

  • With given ISLs establishment scheme and routing scheme, we proposed an optimal power allocation method based on convex optimization theory.

  • 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 ISLs establishment method based on Lagrange relaxation. Section 4 proposed the power allocation method based on convex optimization theory. Section 5 analyzed the simulation results with different parameters. Finally, a conclusion was given in Sect. 6.

2 System model and problem formulation

2.1 System model

As described in Fig. 1, this paper takes into account the computation offloading scenario on satellite network which consists of source satellite, some relay satellites, the edge satellites, and the ground station. Here, the source satellites are those with computation services that are generated by themselves or received from remote sensing users. In general, the source satellite may not be necessarily capable of computing and in order to ensure the computation mission to be completed it needs to be delivered to the satellites with computation capacity or the ground station. Since the source satellite is not necessarily directly connected to the destination, the relay satellites are needed to assist the transmission of computation services. As mentioned earlier, some satellites with computation capacity can handle part of the computing task and are called edge satellites. However, it is worth noting that edge satellites have limited computing capacity and will lead to large computing delays when processing large tasks. On the contrary, it is assumed that ground stations are with infinite computing capacity and better suited to handle a large number of computing tasks. Unfortunately, communication capacity is one of the limitations of satellite networks, which leads to a lot of communication cost and storage cost due to the long transmission path from source satellite to the ground station. In this case, offloading the computation tasks to an edge satellite may also be a feasible option, which is actually a tradeoff between computation cost and communication cost. No matter which computation offloading scheme is selected, the overall performance of the network is closely related to resource allocation scheme and inter-satellite link scheduling. For the sake of this statement, let’s denote the number of satellites as M, the source satellite as I, and the destination satellite as D.

Fig. 1
figure 1

The proposed satellite network model for computation offloading

Full size image

The dynamics of satellite network is a difficult problem to deal with since the satellites move at high speed in their orbits. Therefore, the ISLs and the satellite-ground links also change dynamically. Fortunately, the dynamics of satellite networks are predictable and regular, making them easier to study. The time expanded graph (TEG) is an efficient tool for dealing with such predictable dynamic topologies by discretizing the continuous dynamics. Specifically, 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.

2.2 Problem formulation

The main focus of this paper is to minimize the overall costs of the task transmission with the time constraint where the costs consists of communication cost, storage cost, and computation cost. Before giving the optimization problem, the definitions of those costs are first provided as follows. The communication cost of each link is defined as the sum of energy consumption for task transmission and reception.

$$\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}$$
(1)

where \(c_{t,i,j}^{1}\) means the communication cost for the ISL 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 amount of data passing through the ISL 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} C_{t,i,j}=B\log \left( 1+\frac{p_{t,i,j}G_{i}^{1}G_{j}^{2}L_{t,i,j}}{N_{p}}\right) \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 the data transmission in ISL 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} L_{t,i,j}=\left( \frac{v}{4\pi f d_{t,i,j}}\right) ^{2} \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 at the time slot t.

It is worth noting that not all tasks can be transmitted directly to the destination node. If not, they need to be stored in the current satellite for transmission in the next time slot. Moreover, the cost due to data storage should be also considered and can be expressed as follows.

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

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

Due to the limited computing resource of edge satellites, the energy consumption of computing is necessary to be considered if the task will be transmitted to the edge satellite. Hence, the computing cost is defined as the energy consumption of computing and expressed as

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

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

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

$$\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}$$
(6)

For each satellite, the input flow should equal the output flow where the input flow includes the flow received by other satellites and the data stored at the previous time slot and the output flow includes the flow transmitted to other satellites and the data stored at the current time slot. Then, we can write it as

$$\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}$$
(7)

At the initial moment, the source satellite I generates the task with the data volume D and aims to transmit them to the destination J. 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}{} & {} \sum _{j=1}^{M}x_{1,I,j}+b_{1,I}=D \end{aligned}$$
(8)
$$\begin{aligned}{} & {} \sum _{t=1}^{N}\sum _{i=1}^{M}x_{t,i,J}=D \end{aligned}$$
(9)

For each ISL, the amount of data transmitted can not be more than the link capacity. Then, we can express it as

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

where the link capacity \(C_{t,i,j}\) depends on the transmission power of satellite. Moreover, the sum of the transmission power of each link cannot exceed the maximum transmission power of the satellite, i.e.,

$$\begin{aligned} \sum _{j=1}^{M}p_{t,i,j}\le P_{max} \end{aligned}$$
(11)

where \(P_{max}\) is the maximum transmission power of the satellite.

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

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

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 ISL with the j-th satellite at the time slot t. Based on the definition above, some constraint can be provided.

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

The Eqs. (13) and (14) are the constraints of limited number of antennas. The constraint (15) indicates the ISL is bidirectional.

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

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

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

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

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

Then, the final optimization problem can be written as

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

The main optimization variables are \(x_{t,i,j}\), \(p_{t,i,j}\), and \(a_{t,i,j}\). The optimization problem (18) is the mixed integer linear programming. For obtaining the optimal solution, the exhaustive method can be used to find the optimal ISL scheduling and then the original problem becomes a convex optimization problem that can be solved efficiently. However, the computational complexity of this method is unacceptable when the number of variables is large. To reduce the complexity, it is necessary to investigate an efficient algorithm to solve it.

3 Lagrange relaxation based solving method

In this section, we used the Lagrange relaxation method to deal with the optimization problem (18) by assuming that the power allocation scheme has been given. It can be seen that the coupling constraint (16) makes the optimization problem (18) difficult to solve, which also drives the idea of this paper. Hence, the optimization problem (18) can be decomposed into two subproblems by using the Lagrange relaxation method to relax the constraint (16). Moreover, the relaxed optimization problem can be written as

$$\begin{aligned} \begin{aligned} z(\varvec{\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)-(15) \end{aligned} \end{aligned}$$
(19)

where \(\varvec{\lambda }\) is the lagrangian multipliers. Then, the relaxed optimization problem (19) is equivalent to the following two subproblems \(\mathcal {P}1\) and \(\mathcal {P}2\) since the variables have been separated.

$$\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}$$
(20)
$$\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}$$
(21)

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

It is obvious that the problem \(\mathcal {P}1\) has become a linear programming problem which can be solved by using many current approaches such as simplex method. However, as the number of variables gets very large it’s still very complicated to solve it and that makes us more inclined to other substitutable algorithms. Before the algorithm is executed, some analysis is necessary to help transforming the problem \(\mathcal {P}1\) as a new form. As mentioned in the past section, there are two available options for computation offloading on satellite network, i.e., offload the computation task to edge satellite or ground station. Regardless of which method the source satellite uses, the computing cost can be regarded as a constant because the total data volume is fixed and the computing cost is also fixed. Hence, we can rewrite the problem \(\mathcal {P}1\) by removing the computing cost as follows.

$$\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}$$
(22)

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 expanded graph of satellite network

Full size image

It can be seen that the reformulated problem (22) can be regarded as the min-cost max-flow problem. To show it, we first construct the time expanded graph \(\mathcal {G}=(\mathcal {V},\mathcal {E})\) as shown in Fig. 2 where \(\mathcal {V}\) and \(\mathcal {E}\) are the vertices and edges of TEG. The vertices set \(\mathcal {V}\) consists of all the satellites on different time slots and one virtual vertex which is used to connected every satellite node. The edge set \(\mathcal {E}\) consists of three kinds of edges, i.e., communication edges, storage edges, and virtual edges. For all edges in TEG, we need to further define the cost set \(\mathcal {W}\) and capacity set \(\mathcal {C}\). According to the problem (22), 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. The cost and capacity of virtual edges are zeros and infinite, respectively. Then, the problem (22) 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\)

Although the optimization problem \(\mathcal {P}2\) is still an integer programming, the solving complexity can be reduced by taking notice of that the optimization problem \(\mathcal {P}2\) has been separable in terms of the time slot. 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}$$
(23)

Due to less number of variables for each subproblem, the current solving method such as branch and bound method is efficient for solving such an integer programming problem. In addition, a near-optimal method based on Lagrange relaxation has been proposed to deal with this problem in our previous paper and hence can also be used to here to solve it.

figure g

3.3 Optimizing lagrange multiplier

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

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

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

$$\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}$$
(25)

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} \sum _{k=1}^{\infty }\phi ^{k}=\infty , \lim _{k\rightarrow \infty }\phi ^{k}=0 \end{aligned}$$
(26)

3.4 Solution reconstruction method

Although the relaxed solution is close to the optimal solution of problem (18), the relaxed solution may be infeasible or ineffective even if it is feasible. In order to ensure the feasibility and efficiency of the solution, an efficient reconstruction method needs to be investigated to modify the relaxation solution. It can be seen that the optimal solution \(\varvec{a}\) of problem \(\mathcal {P}2\) is always feasible. Hence, we only need to make sure the optimal solution \(\varvec{x}\) feasible by keeping the the optimal solution \(\varvec{a}\) fixed. Specifically, the link capacity can be updated as \(\tau a_{t,i,j}C_{t,i,j}\) based on the given optimal solution \(\varvec{a}\). Then, the new optimal solution \(\varvec{x}^{*}\) is given by solving the the min-cost max-flow problem again. The whole detailed solution process can be referred to algorithm 1.

4 Power allocation method based on convex optimization

In the previous section, we have presented an optimized ISL establishment scheme and flow allocation results with given power allocation method. However, power allocation scheme is also the key factor affecting network cost. Hence, in this section, we proposed an efficient power allocation scheme based on convex optimization for further reducing the network cost.

With the given ISL establishment scheme and flow allocation results, the original optimization problem (18) can be rewritten as follows.

$$\begin{aligned} \begin{aligned} \min ~&\sum _{t=1}^{N}\sum _{i=1}^{M}\sum _{j=1}^{M}\frac{x_{t,i,j}(p_{t,i,j}+q_{t,i,j})}{C_{t,i,j}}+H\\ s.t.~&\sum _{j=1}^{M}a_{t,i,j}p_{t,i,j}\le P_{max}\\&x_{t,i,j}\le \tau C_{t,i,j}\\&p_{t,i,j}\ge 0 \end{aligned} \end{aligned}$$
(27)

where H denotes the sum of storage cost and computation cost. In fact, H can be regarded as a constant because the flow allocation results have been given. Hence, this term can be removed from the optimization problem (27), which will not affect the optimal solution. The first constraint indicates that the power allocated to all the links cannot exceed the maximum transmitted power of the satellite. The second constraint indicates that the capacity of each link can ensure the passage of actual traffic after power allocation. In addition, it can be seen that the above optimization problem can be decomposed and equivalent to solving the following NM sub-problems.

$$\begin{aligned} \begin{aligned} \min ~&\sum _{j=1}^{M}\frac{x_{t,i,j}(p_{t,i,j}+q_{t,i,j})}{C_{t,i,j}}\\ s.t.~&\sum _{j=1}^{M}a_{t,i,j}p_{t,i,j}\le P_{max}\\&x_{t,i,j}\le \tau C_{t,i,j}\\&p_{t,i,j}\ge 0 \end{aligned} \end{aligned}$$
(28)

Although the above problem is not a convex optimization problem, it can be transformed into a convex optimization problem by some method of variable substitution which can be solved efficiently. By substitution of variables \(y_{t,i,j}=\frac{C_{t,i,j}}{B\log _{2}(e)}\), we can obtain the following formula.

$$\begin{aligned} p_{t,i,j}=\frac{e^{y_{t,i,j}}-1}{h_{t,i,j}} \end{aligned}$$
(29)

where \(h_{t,i,j}=\frac{G_{i}^{1}G_{j}^{2}L_{t,i,j}}{N_{p}}\).

Then, based on the variable substitution above, the objective function can be reformulated as

$$\begin{aligned} \begin{aligned}&{ {\sum \limits _{j = 1}^M {\frac{{\left( {{e^{{y_{t,i,j}}}} - 1 + {h_{t,i,j}}{q_{t,i,j}}} \right) {x_{t,i,j}}}}{{{y_{t,i,j}}\left( {B{{\log }_2}e} \right) {h_{t,i,j}}}}} } } \\&\qquad = { {\sum \limits _{j = 1}^M {{w_{t,i,j}}\frac{{\left( {{e^{{y_{t,i,j}}}} - {v_{t,i,j}}} \right) }}{{{y_{t,i,j}}}}} } } \\&\qquad = { {\sum \limits _{j = 1}^M {{w_{t,i,j}}f\left( {{y_{t,i,j}}} \right) } } } \end{aligned} \end{aligned}$$
(30)

where \(w_{t,i,j}=\frac{x_{t,i,j}}{B\log _{2}(e)h_{t,i,j}}\) and \(v_{t,i,j}=1-h_{t,i,j}q_{t,i,j}\).

Then, the original optimization problem (28) is equivalent to following problem.

$$\begin{aligned} \begin{aligned} \min ~&{ {\sum \limits _{j = 1}^M {{w_{t,i,j}}f\left( {{y_{t,i,j}}} \right) } } }\\ s.t.~&\sum _{j=1}^{M}a_{t,i,j}\frac{e^{y_{t,i,j}}-1}{h_{t,i,j}}\le P_{max}\\&x_{t,i,j}\le \tau B\log _{2}(e) y_{t,i,j}\\&p_{t,i,j}\ge 0 \end{aligned} \end{aligned}$$
(31)

Obviously, the optimization problem is much easier to solve if the above problem is a convex optimization problem. Hence, a theorem is first provided blow to further show the convexities of objective functions and constraints.

Theorem 1

The optimization problem (31) is a convex optimization problem.

Proof

Since the exponential function is convex, the first constraint is the weighted sum of the exponential function and is obviously convex. The second constraint is also clearly convex due to the linear constraint. Hence, the proof will be completed if the function \(f(y_{t,i,j})\) is convex due to the non-negative weights \(w_{t,i,j}\). For convenience, we will replace \(y_{t,i,j}\) with y below. By taking the derivative of function f(y), we can obtain

$$\begin{aligned}{} & {} f'(y)=\frac{ye^{y}-(e^{y}-v)}{y^{2}} \end{aligned}$$
(32)
$$\begin{aligned}{} & {} \begin{aligned} f''(y)&=\frac{(ye^{y}-e^{y}+v)'y^{2}-2y(ye^{y}-e^{y}+v)}{y^{4}}\\&=\frac{y^{3}e^{y}-2y(ye^{y}-e^{y}+v)}{y^{4}}\\&=\frac{y^{2}e^{y}-2(ye^{y}-e^{y}+v)}{y^{3}} \end{aligned} \end{aligned}$$
(33)

Then, let \(z(y)=y^{2}e^{y}-2(ye^{y}-e^{y}+v)\) and take the derivative of function z(y).

$$\begin{aligned} \begin{aligned} z'(y)&=(y^{2}+2y)e^{y}-2ye^{y}\\&=y^{2}e^{y}\\&\ge 0 \end{aligned} \end{aligned}$$
(34)

Obviously, the function z(y) is increasing function with respect to variable y. Due to \(y\ge 0\), we can obtain the minimum value of z(y) as follows.

$$\begin{aligned} \begin{aligned} z(0)&=2(1-v)\\&\ge 0 \end{aligned} \end{aligned}$$
(35)

Hence, we can know that \(z(y)\ge 0\) always holds. Combined with the formula (33), the fact \(f''(y)\ge 0\) can be given. In other words, function f(y) is a convex function. The proof has been completed. \(\square\)

5 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 1400 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. As described in the previous section, source satellite is randomly selected from the created Walker constellation and the remaining satellites serve as relay satellites.

Table 1 The Parameters in Simulation
Full size table

To show the effectiveness of proposed ISL scheme based on Lagrange relaxation and optimized power allocation method (ISLLR-OP), we provide two benchmarks for comparison algorithms including ISL scheme based on Lagrange relaxation and equal power allocation method (ISLLR-EP) and random ISL scheme and equal power allocation method (RISL-EP). The provided RISL-EP means that the ISLs are built randomly in each time slot under the condition that the constraints are satisfied.

Fig. 3
figure 3

The network cost versus the length of time slot

Full size image

Figure 3 has shown the relationship between the length of time slot and the network cost. As we can see, the network cost increases with the length of time slot growing for the case of RISL-EP. However, there is no significant change in network cost for the case of ISLLR-OP and ISLLR-EP. In fact, if we assume that the flow allocation result is constant, the total communication cost does not change because the transmission power is fixed for each satellite and actual transmission time is also fixed for each flow. However, the storage costs will increase over length of time slot. Hence, data transmission prefers to use more communication links and as few storage links as possible to reduce network cost. For the case of RISL-EP, random ISL scheme is inefficient and thus limits the amount of data that can pass through. Moreover, data cannot be transferred efficiently from storage links to communication links, which results in an increase of storage cost. On the contrary, the proposed ISL scheme is better able to overcome this difficulty so that the cost does not increase significantly. Besides, the network cost is further reduced by using the proposed optimized power allocation method.

Fig. 4
figure 4

The network cost versus the data volume

Full size image

Figure 4 provides the relationship between network cost and the total data volume. It is obvious that the energy consumption increases with the increasing of the data volume. As we would expect, as the amount of data transmitted increases, the network has to pay more to keep the data transmitted successfully. Moreover,it can be seen that the proposed ISLLR-OP is always superior to ISLLR-EP and RISL-EP. For example, compared with RISL-EP, the network cost is approximately reduced by 51.6% when the total data volume is 4.2 Gbits by using ISLLR-EP, which indicates that optimized ISL scheme is necessary to reduce network cost. Moreover, compared with ISLLR-EP, the network cost can be further reduced by 14.4% with the use of ISLLR-OP, which means the proposed power allocation is efficient.

Fig. 5
figure 5

The network cost versus the transmission power

Full size image

Figure 5 demonstrates the relationship between the transmission power and the network cost. We can see that the cost of the network increases as the transmission power of each satellite increases. From a mathematical point of view, the ratio of transmission power to ISL rate is an increasing function. Combining with the formula (1) and equal power allocation method, the communication cost that the network pays per unit of traffic has to increase when the transmission power increases. Hence, the increase of network cost is in line with our expectations. Moreover, the ISLLR-OP is designed on the basis of ISLLR-EP. As can be seen from the figure, there is a significant decrease in network cost by using ISLLR-OP.

6 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. This paper investigates the network cost optimization problem which is formulated as the mixed integer linear programming. Then, by assuming the equal power allocation method, a Lagrange relaxation based method is proposed to optimize the ISLs establishment scheme and routing scheme. Moreover, the transmission power is reallocated based on the given ISLs establishment scheme and routing scheme. Simulation results indicates that the network cost can be significantly reduced by using the proposed algorithm.