Dynamic Delay-Sensitive Observation-Data-Processing Task Offloading for Satellite Edge Computing: A Fully-Decentralized Approach

Abstract

Satellite edge computing (SEC) plays an increasing role in earth observation, due to its global coverage and low-latency computing service. In SEC, it is pivotal to offload diverse observation-data-processing tasks to the appropriate satellites. Nevertheless, due to the sparse intersatellite link (ISL) connections, it is hard to gather complete information from all satellites. Moreover, the dynamic arriving tasks will also influence the obtained offloading assignment. Therefore, one daunting challenge in SEC is achieving optimal offloading assignments with consideration of the dynamic delay-sensitive tasks. In this paper, we formulate task offloading in SEC with delay-sensitive tasks as a mixed-integer linear programming problem, aiming to minimize the weighted sum of deadline violations and energy consumption. Due to the limited ISLs, we propose a fully-decentralized method, called the PI-based task offloading (PITO) algorithm. The PITO operates on each satellite in parallel and only relies on local communication via ISLs. Tasks can be directly offloaded on board without depending on any central server. To further handle the dynamic arriving tasks, we propose a re-offloading mechanism based on the match-up strategy, which reduces the tasks involved and avoids unnecessary insertion attempts by pruning. Finally, extensive experiments demonstrate that PITO outperforms state-of-the-art algorithms when solving task offloading in SEC, and the proposed re-offloading mechanism is significantly more efficient than existing methods.

1. Introduction

Satellite edge computing (SEC) is regarded as a promising architecture in Earth observation [1], the Internet of Things [2], and other scientific applications. Driven by the rapid growth in observation satellites, massive observational data are generated and need to be further processed [3,4]. However, local processing is impractical due to the limited capacities of observation satellites [5]. Moreover, transferring data from satellites to a cloud center also leads to both long latency and an unaffordable network burden [4]. Therefore, the SEC, which deploys mobile edge computing (MEC) [6] servers on satellites, providing global coverage and low-latency computing services, has drawn increasing attention in recent years [7,8,9,10,11].

In SEC, a group of satellites linked by laser intersatellite links (LISLs), perform collaborative computing for submitted data from observation satellites. These data are typically represented as tasks [8]. Some tasks, such as military monitoring [12] and target tracking [13], are delay-sensitive, and expected to be processed before their deadlines. Hence, task offloading, determining where and when tasks are executed, plays a pivotal role in SEC.

Unfortunately, due to the distributed and dynamic nature of SEC [7], it is tough to obtain offloading assignments for delay-sensitive tasks. Specifically, on the one hand, there are sparse ISL connections in SEC; thus, it is hard to gather all the necessary information from all satellites, and sending information from satellites to the control center also involves unnecessary delays. Additionally, the satellite states change rapidly during task processing, collecting such information leading to a huge communication burden on the satellite network. On the other hand, due to the dynamics in SEC, delay-sensitive tasks are continually generated by observation satellites, which causes a daunting challenge for task offloading. That is because newly generated tasks may have the same time horizon as the offloaded ones, affecting the original offloading assignment, and even make it infeasible. Thus, task offloading problems should be carefully addressed to resolve the above challenges.

The task offloading problem in SEC has received increasing attention recently. Specifically, recent works [14,15,16,17,18,19,20,21,22,23] obtain offloading assignments by various centralized approaches deploying on the access satellites or gateway stations. Meanwhile, considering the non-centrality of SEC, works [24,25,26,27,28] adopt the distributed algorithm to reduce the latency caused by long-distance communication [25]. Unfortunately, some practical issues are still neglected, such as the sparsity of ISLs, the limited network resources, and the dynamic arrival of delay-sensitive tasks. To the best of our knowledge, task offloading problems jointly considering the aforementioned practical issues, have not been addressed for SEC.

In this paper, we investigate the task offloading problem in SEC with delay-sensitive tasks by jointly considering the distributed satellites and the dynamic environment. The main contributions of this article are summarized as follows:

• This paper establishes a mixed-integer linear programming (MILP) model for delay-sensitive task offloading in SEC, which aims to reduce the deadline violation of delay-sensitive tasks while minimizing the system’s energy consumption.
• Considering the limited ISL connections, we propose a fully decentralized PITO algorithm. The PITO operates on each satellite in parallel and only relies on local communication via ISLs. It iterates between two stages, called task inclusion and consensus and task removal. The first stage aims to include appropriate tasks in each satellite. The second stage reaches consensus on the removal impact of tasks among all satellites and removes conflict tasks which may increase the objective value. Using PITO, tasks can be directly offloaded on board without depending on any central server. Its effectiveness and polynomial complexity are demonstrated.
• To handle the dynamic arrival of delay-sensitive tasks, a fast re-offloading mechanism is further introduced, which reduces the tasks involved and avoids unnecessary insertion attempts, by pruning. It enables PITO to perform online re-offloading during the computing serving process.

The remainder of this paper is organized as follows. Section 2 introduces the related works. Section 3 describes the MILP model. Section 4 details the proposed PITO algorithm. Then, a re-offloading mechanism is further developed for handling the dynamics in SEC. Section 5 shows the simulation results of the proposed PITO, and these are further discussed in Section 6. Finally, the paper is summarized in Section 7.

2. Related Works

There are two main techniques for task offloading in SEC: centralized and distributed approaches. In centralized ones, offloading schemes of satellites are typically generated by a central server [14]. Some works [16,17] employed exact methods to obtain optimal offloading assignments. For example, Song et al. [16] divided the computation offloading problem into the ground and space segments and proposed an energy-efficient offloading method. Similar to [16], Ding et al. [17] decomposed the optimization problem into four subproblems, and quadratic transform-based fractional programming and the interior point method were used. Since the task offloading problem is NP-hard [29], exact methods can be effective only for small instances. Hence, heuristic and meta-heuristic approaches were adopted [14,15,18]. Specifically, Zhang et al. [14] established a greedy-based task allocation algorithm. Considering the efficiency of the meta-heuristic algorithm in solving the NP-hard problem, Hu et al. [15] and Wang et al. [18] introduced particle swarm optimization-based methods for task offloading in SEC. Additionally, reinforcement learning methods [19,20,22,23,30,31] are also employed to quickly obtain high-quality offloading assignments. Specifically, Qiu et al. [19] first developed a deep Q-learning approach for offloading problems. Mao et al. [20] embedded the long short-term memory model into a learning-based offloading strategy, addressing the dynamics of energy harvesting performance. Considering the data dependence among tasks, Yu et al. [21] proposed a deep imitation learning-driven offloading and caching algorithm. To achieve cooperative scheduling with both tasks and resources, Cui et al. [22] proposed a mixed algorithm combining deep reinforcement learning with convex optimization. Zhang et al. [23] proposed a deep deterministic policy gradient-based algorithm outputting both discrete and continuous variables, achieving simultaneous decisions on offloading locations and allocating resources. To address security concerns in SEC, Sthapit et al. [30] developed a deep deterministic policy gradient-based security-aware offloading algorithm. Subsequently, Liu et al. [31] introduced a federated reinforcement learning-based offloading method to enhance privacy protection. Centralized approaches are usually easier to implement and run faster, but may have the following drawbacks: (1) the central server requires consistent communication with each satellite, leading to a heavy communication burden. For ground-based central servers especially [17,22,32], it also occupies satellite–terrestrial network resources; (2) a high computational demand is caused by generating all offloading assignments and monitoring any state changes of satellites during task processing; and (3) there is a resulting single point of failure.

Considering the non-centrality of SEC, distributed approaches [24,25,26,27,28] are adopted. Specifically, Chen et al. [24] adopted a contract net protocol (CNP)-based method to resolve the autonomous mission planning problem. Works [25,26] employed the diffusion algorithm-based approach. Wang et al. [25] introduced a transmission capacity and computing capacity-aware diffusion algorithm to obtain task offloading assignments. Then, based on [25], Ma et al. [26] proposed a directed diffusion-enhanced task scheduling algorithm (DETS), which embedded a computing gradient that considered both the computing and communication resources. Other works [27,28] used the distributed convex optimization-based approach. For example, Tang et al. [27] employed a binary-variable relaxation method to convert the original nonconvex problem into a linear programming problem, then proposed an alternating-direction method of multipliers (ADMM)-based distributed computation offloading scheme. Finally, a binary-variable recovery algorithm was adopted to obtain the required discrete offloading assignment. Similarly, Zhou et al. [28] adopted the ADMM-based distributed algorithm to resolve the mobility-aware computation offloading problem. The performance impact (PI) algorithm [33,34] is another distributed approach, in which the required assignments can be directly constructed without additional transformations, and the consensus process [35] helps with jumping out of the local optimum and resolving task conflicts. However, the implementation of PI for the task offloading problem in SEC has not been reported.

Few studies have investigated the dynamic arrival of delay-sensitive tasks in SEC [36,37]. Ng et al. [36] proposed z-stage stochastic integer programming to resolve the task offloading problem, which minimizes the cost amid stochastic uncertainties. Based on [36], Ng et al. [37] further presented a z-stage stochastic offloading optimization scheme, in which uncompleted tasks can be re-offloaded in the next stage. In this paper, we introduce a fast re-offloading mechanism using the match-up strategy [38,39,40], which is confirmed to not only achieve good solutions but also reduce re-offloading time.

3. Problem Description and Modeling

3.1. Scenario

The SEC scenario is shown in Figure 1, in which delay-sensitive tasks generated by observation satellites are further uploaded to SEC satellites for processing. There are m SEC satellites S = {1, 2, …, m} and n observation satellites D = {1, 2, …, n} in total. Each SEC satellite s ∈ S is equipped with a server whose computing capacity and buffer size are C_s and M_s, respectively. Due to the limited energy supply in orbit, the maximum energy consumption for each SEC satellite is limited to H_s. Every SEC satellite also connects with four neighboring satellites via LISL, so that network topology can be represented as an m × m matrix G, where G[k, l] = 1 if an LISL exists between satellites k and l, and otherwise, G[k, l] = 0. Some useful notations are listed in

Table 1. Notations.

Notation	Description
m	Total number of SEC satellites.
n	Total number of observation satellites.
S	Set of SEC satellites.
D	Set of observation satellites.
Cs	Computing capacity of SEC satellite s.
Ms	Buffer space of SEC satellite s.
Hs	Energy consumption limitation on SEC satellite s.
G	Network topology matrix.
T = {t1, t2, …, tn}	Set of tasks t.
θ = {θ1, θ2, …, θm}	Task offloading solution.
F(θ)	Objective value of solution θ.
$\mathcal{R}$(θs ⊖ t)	Removal impact, indicating the variation of F(θs) after removing t from θs.
$\mathcal{I}$(θs ⊕ t)	Inclusion impact, indicating the minimum variation of F(θs) after inserting t into θs.
Rs = [Rs1, Rs2, …, Rsn]T, Ws = [Ws1, Ws2, …, Wsn]T, Qs = [Qs1, Qs2, …, Qsm]T	Consensus vectors of satellite s, where Rs implies the removal impacts of tasks, Ws represents the considered offloaded satellites of tasks, and Qs indicates the latest timestamp of satellites.
Ψs	Pending removal tasks in satellite s.
[μa, μb]	Influence horizon.
Us = [Us1, Us2, …, Us(n+q)]T	Task classification vector of satellite s.
Φs	Candidate insertion positions of sequence θs.

.

Each observation satellite i ∈ D generates a delay-sensitive task t_i, and all tasks T = {t₁, t₂, …, t_i, …, t_n} are indivisible. Every task t_i ∈ T can be characterized by a tuple <λ_i, μ_i, σ_i>, where λ_i represents the input data size of t_i, μ_i denotes the workload of t_i, and σ_i refers to the deadline.

According to [23], observation satellite i ∈ D can access a specific SEC satellite a ∈ S covering i for data uploading. Initially, data from task t_i ∈ T are uploaded from observation satellite i to access satellite a. Then, task t_i can be executed directly on a or offloaded to another satellite in S via LISLs. Let s ∈ S be the offloaded satellite. Since tasks can be executed only after the required data are received, all offloaded tasks in s must not exceed the available buffer size (represented as MA_s), and these tasks are processed sequentially. After t_i is completed, its data in s will be released. Then, the whole process is continued until all generated delay-sensitive tasks are finished. Due to a typically small size of outputs, the results feedback process is ignored in this paper.

3.2. Communication Model

The communication latency is composed of two parts: propagation delay and transmission delay.

In this paper, we use Ka-band for the links between the observation satellites and SEC satellites. Therefore, for task t_i ∈ T, let $r_{i,a}^{RISL}$ be the rate of radio intersatellite links (RISLs) from observation satellite i to access satellite a, which can be obtained by [22]. Then, the latency for uploading t_i is

$${\mathrm{\tau }}_{i,a}^{RISL}=\frac{l_{i,a}}{c}+\frac{{\mathrm{\lambda }}_i}{r_{i,a}^{RISL}}$$

(1)

where l_i,a is the distance of RISL, and c is the speed of light. Similarly, let r^LISL be the rate of LISLs among SEC satellites, which is a constant. The latency for transmitting t_i from a to another satellite s is

$${\mathrm{\tau }}_{i,a,s}^{LISL}=\frac{{\mathcal{l}}_{a,s}}{c}+\frac{{\mathrm{\lambda }}_i}{r^{LISL}}$$

(2)

where 𝓁_a,s represents the length of the shortest route from satellite a to s.

Thus, when task t_i is offloaded to satellite s ∈ S, the communication latency of task t_i is given by

$${\mathrm{\tau }}_{i,s}^{comm}={\mathrm{\tau }}_{i,a}^{RISL}+{\mathrm{\tau }}_{i,a,s}^{LISL}$$

(3)

Specially, if t_i is offloaded to access satellite a, there is no LISL transmission, and we have ${\mathrm{\tau }}_{i,a}^{comm}$ = ${\mathrm{\tau }}_{i,a}^{RISL}$.

3.3. Computational Model

For task t_i ∈ T, the required CPU cycles for processing t_i is λ_iμ_i. Thus, the computational latency of t_i on offloaded satellite s is

$${\mathrm{\tau }}_{i,s}^{comp}=\frac{{\mathrm{\lambda }}_i{\mathsf{\mu }}_i}{C_s}$$

(4)

In this paper, we consider a sequential computation model [14] in Figure 2, i.e., each satellite can process only one task at a time, and preemption is not allowed. Hence, when multiple tasks are offloaded to a specific satellite, there will be queue delays that must be taken into account for task computation.

Then we let θ = {θ₁, θ₂, …, θ_m} be a task offloading assignment, where θ_s, ∀s ∈ S, represents the task sequence on satellite s. Several time parameters of task t_i are defined as follows:

• ${\mathrm{\tau }}_i^A$: the time that offloaded satellite s is available for task t_i;
• ${\mathrm{\tau }}_i^D$: the time that all required data of t_i are received by s;
• ${\mathrm{\tau }}_i^S$: the time at which t_i is performed;
• ${\mathrm{\tau }}_i^F$: the finish time of task t_i.

First, we let t_ρ(i) ∈ T be the preceding task of t_i in task sequence θ_s. If t_i is the first task of θ_s, we set t_ρ(i) = ∅; otherwise, t_i can be executed by s only after task t_ρ(i) is completed. Thus, we have

$${\mathrm{\tau }}_i^A=\left\{\begin{array}{c}0, \mathrm{if} t_{\rho (i)}=\mathsf{\varnothing }\\ {\mathrm{\tau }}_{\rho (i)}^F, \mathrm{otherwise}\end{array}\right.$$

(5)

Furthermore, task t_i can be performed only after s receives the data from t_i. We assume that all data begin transmitting simultaneously (i.e., time 0), and we have

$${\mathrm{\tau }}_i^D=0+{\mathrm{\tau }}_{i,s}^{comm}$$

(6)

Then, the start time of task t_i can be calculated by

$${\mathrm{\tau }}_i^S=\max \{{\mathrm{\tau }}_i^A,{\mathrm{\tau }}_i^D\}$$

(7)

where the queue delay of t_i is defined as ${\mathrm{\tau }}_i^{queue}={\mathrm{\tau }}_i^S-{\mathrm{\tau }}_i^D$.

Finally, the finish time of t_i is given by

$${\mathrm{\tau }}_i^F={\mathrm{\tau }}_i^S+{\mathrm{\tau }}_{i,s}^{comp}$$

(8)

Based on above analysis, given an offloading assignment θ, we can calculate ${\mathrm{\tau }}_i^A$, ${\mathrm{\tau }}_i^D$, ${\mathrm{\tau }}_i^S$, and ${\mathrm{\tau }}_i^F$ for each t_i ∈ T, sequentially, using (5), (6), (7), and (8), respectively.

3.4. Energy Model

The energy consumption of SEC consists of two parts: transmission and computation. For transmission, the power of RISL and LISL are ε₁ and ε₂, respectively. Regarding computation, we use the widely adopted model of energy consumption per computing cycle, ${\kappa C}_s^2$ [19]. Then the energy consumption of processing task t_i on satellite s is calculated by

$$E_{i,s}={\epsilon }_1{\mathrm{\tau }}_{i,a}^{RISL}+{\epsilon }_2{\mathrm{\tau }}_{i,a,s}^{LISL}+\kappa C_s^2{\mathrm{\lambda }}_i{\mathsf{\mu }}_i$$

(9)

Similar to Section 3.2, when t_i is offloaded to access satellite a, we have E_i,a = ε₁${\mathrm{\tau }}_{i,a}^{RISL}$ + κ$C_a^2$λ_iμ_i.

3.5. Problem Formulation

This paper aims to enhance the service experience for delay-sensitive tasks while minimizing overall energy consumption. Let x_si be the decision variable, such that x_si = 1 if task t_i is offloaded to satellite s and otherwise, x_si = 0. Another variable is y_sij = 1 if satellite s needs to perform task t_i before t_j, and y_sij = 0 otherwise. Decision variables x_si and y_sij describe the offloading assignment θ. Then, the MILP model of the considered problem is presented as follows:

$$F(\mathbf{\theta })=\underset{x_{si},y_{sij}}{\min }{\displaystyle \sum _{i\in D}\left(\alpha \cdot \max \{0,{\mathrm{\tau }}_i^F-{\sigma }_i\}+\beta \cdot {\displaystyle \sum _{s\in S}{E}_{i,s}{x}_{si}}\right)}$$

(10)

$${\displaystyle \sum _{s\in S}{x}_{si}=1,} \forall i\in D$$

(11)

$${\displaystyle \sum _{i\in D}{\mathrm{\lambda }}_i{x}_{si}}\le M{A}_s, \forall s\in S$$

(12)

$${\displaystyle \sum _{i\in D}{E}_{i,s}{x}_{si}}\le H_s, \forall s\in S$$

(13)

$${\displaystyle \sum _{j\in D}{y}_{sij}{x}_{si}\le 1,} \forall s\in S,\forall i\in D$$

(14)

$${\displaystyle \sum _{i\in D}{y}_{sij}{x}_{sj}\le 1, }\forall s\in S,\forall j\in D$$

(15)

$$y_{sij}({\mathrm{\tau }}_j^S-{\mathrm{\tau }}_i^F)\ge 0, \forall s\in S,\forall i,j\in D$$

(16)

$$x_{si}\in \{0,1\},y_{sij}\in \{0,1\}, \forall s\in S,\forall i,j\in D$$

(17)

$$\alpha +\beta =1, \alpha \in [0,1], \beta \in [0,1]$$

(18)

where x_ki and y_kij are decision variables representing offloading assignment θ. α and β are weight factors. Equation (10) represents the objective function, which aims to minimize the weighted sum of deadline violation and energy usage of all tasks. Equation (11) indicates that each task can only be offloaded to a specific satellite. Equation (12) states that all offloaded tasks on s should not surpass the available buffer size MA_s, to avoid task overflow, and we have MA_s = M_s, initially. Equation (13) indicates that the energy consumption for processing all offloaded tasks on s should not exceed the energy consumption limitation H_s. Equations (14) and (15) suggest that each task has, at most, one predecessor and one successor in its sequence. Equation (16) illustrates temporal relations among tasks offloaded to the same satellite. Equations (17) and (18) state the domains of variables.

4. The PI-Based Task Offloading Algorithm

This article develops a PITO algorithm for resolving delay-sensitive task offloading problems in SEC. The PITO performs on each satellite in parallel, and only relies on local communication via LISLs. We first introduce the distributed framework of PITO, followed by its two stages: task inclusion and consensus and task removal. Additionally, we establish a re-offloading mechanism to handle the dynamic arriving delay-sensitive tasks.

4.1. General Framework

In PITO, satellites exchange information with their neighbors via LISLs. Each satellite s ∈ S iteratively adds or removes delay-sensitive tasks into or out of its task sequence θ_s, minimizing the global objective F(θ). To do this, we first introduce two indicators for each task t ∈ T, i.e., removal impact and inclusion impact.

(1)

Removal impact: for task t ∈ θ_s, the removal impact $\mathcal{R}$(θ_s ⊖ t) indicates the variation of F(θ_s) after removing t from θ_s; then, we have

$$\mathcal{R}({\mathsf{\theta }}_s\ominus t)=F({\mathsf{\theta }}_s)-F({\mathsf{\theta }}_s\ominus t)$$

(19)

where F(θ_s) is the objective value of θ_s, we have F(θ) = ∑_s∈SF(θ_s). θ_s ⊖ t represents the removal of task t from θ_s. For completeness, we set $\mathcal{R}$(θ_s ⊖ t) = ∞ for any t ∉ θ_s.

(2)

Inclusion impact: for task t ∉ θ_s, the inclusion impact $\mathcal{I}$(θ_s ⊕ t) represents the minimum variation of F(θ_s) after inserting t into θ_s; then, we have

$$\mathcal{I}({\mathsf{\theta }}_s\oplus t)=\underset{p\in \{1,2,\dots ,\left|{\mathsf{\theta }}_s\right|+1\}}{\min }\{F({\mathsf{\theta }}_s{\oplus }_{p}t)-F({\mathsf{\theta }}_s)\}$$

(20)

where θ_s ⊕_p t indicates the inclusion of task t into the p-th position of θ_s. Similarly, we set $\mathcal{I}$(θ_s ⊕ t) = ∞ under two states: when t ∈ θ_s, or when constraints (12) and (13) cannot be satisfied after incorporating task t.

To introduce the general framework in Figure 3, let us begin with a straightforward example. Initially, satellite s ∈ S adds tasks into its sequence θ_s, following the inclusion rules in Section 4.2. Then, satellite s sends the removal impact $\mathcal{R}$(θ_s ⊖ t) of all tasks t ∈ θ_s to neighboring satellite k (i.e., G[s, k] = 1) via LISLs. After that, satellite k evaluates the received $\mathcal{R}$(θ_s ⊖ t) against the inclusion impact $\mathcal{I}$(θ_k ⊕ t) derived from its sequence θ_k. If criterion (21) is met, task t will be reassigned from θ_s to the appropriate position within θ_k, and then F(θ) decreases. Simultaneously, satellite k updates the removal impact of t and relays it to neighboring satellites via LISLs. This process is continued until (21) is no longer met. Then, we introduce Lemma 1 to the detail criterion (21).

Lemma 1. 

For offloading assignment θ = {θ₁, θ₂, …, θ_m}, two satellites s and k connect by LISL (i.e., G[s, k] = 1) and a task t∈ θ_s\θ_k. The F(θ) will be decreased by removing t from θ_s to an appropriate position within θ_k, as long as (21) is met.

$$\mathcal{R}({\mathsf{\theta }}_s\ominus t)>\mathcal{I}({\mathsf{\theta }}_k\oplus t)$$

(21)

Proof. 

Let p′ be the optimal position in θ_k, i.e., p′ = argmin_{p∈{1,2,…,|θk|+1}}{F(θ_k ⊕_p t) − F(θ_k)}, so we have $\mathcal{I}$(θ_k ⊕ t) = F(θ_k ⊕_p′ t) − F(θ_k). After removing task t from θ_s to the p′-th position of θ_k, a new assignment θ′ is obtained, where θ_s′ = θ_s ⊖ t, θ_k′ = θ_k ⊕_p′ t, and θ_l′ = θ_l, ∀l ∈ S/{s, k}. According to (19) and (20), we have F(θ′) = ∑_l∈S F(θ_l′) = F(θ) − $\mathcal{R}$(θ_s ⊖ t) + $\mathcal{I}$(θ_k ⊕ t). Thus, F(θ′) < F(θ) holds (i.e., F(θ) decreases) only when $\mathcal{R}$(θ_k ⊖ t) > $\mathcal{I}$(θ_l ⊕ t) is met. □

Unfortunately, the limited LISL connections in SEC cause a challenge in spreading removal impacts among all satellites, leading the SEC system to be easily trapped into local optimum [33]. Consider the example in Figure 4: nine satellites s₁–s₉ are connected via LISLs, and task t ∈ T is located in θ₅. We make two assumptions: (1) $\mathcal{I}$(θ_s ⊕ t) > $\mathcal{R}$(θ₅ ⊖ t) for ∀s ∈ {4, 8}, and (2) $\mathcal{I}$(θ₇ ⊕ t) < $\mathcal{R}$(θ₅ ⊖ t). That means that removing task t from θ₅ to θ₇ will decrease F(θ). However, given that $\mathcal{I}$(θ_s ⊕ t) > $\mathcal{R}$(θ₅ ⊖ t) exists for ∀s ∈ {4, 8}, task t cannot be incorporated into either θ₄ or θ₈ by Lemma 1, and so t cannot be added to θ₇, resulting in a local optimum. This problem also exists in other distributed approaches, such as CNP [24] and DETS [26].

To avoid local optimum and update removal impacts among satellites, each satellite s ∈ S uses three vectors: R_s, W_s, and Q_s, when communicating with its neighbors in PITO.

(1)

R_s = [R_s1, R_s2, …, R_sn]^T is a vector recording the latest removal impacts of tasks in T. Initially, we set R_st = $\mathcal{R}$(θ_s ⊖ t) for ∀ t ∈ θ_s, and otherwise R_st = ∞.

(2)

W_s = [W_s1, W_s2, …, W_sn]^T is a vector recording the considered offloaded satellite of tasks in T. The entry W_st = k represents the fact that satellite s believes t is offloaded to satellite k. Initially, we set W_st = s for ∀ t ∈ θ_s, and otherwise, W_st = 0.

(3)

Q_s = [Q_s1, Q_s2, …, Q_sm]^T is a vector where entry Q_sk is the timestamp where satellite s thinks it receives the latest information from satellite k. Initially, Q_sk = 0 for ∀ k ∈ S. During the communication process, Q_sk is updated under the following rules:

$$Q_{sk}=\left\{\begin{array}{l}{\mathrm{\tau }}_{sk},\hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\mathrm{if} G[s,k]=1\\ {\max }_{l\in S\wedge G[s,l]=1}{Q}_{lk}, \hspace{0.5em}\mathrm{otherwise}\end{array}\right.$$

(22)

where τ_sk is the time that satellite s receives vectors from k. If satellite k is a neighboring satellite of s (i.e., G[s, k] = 1), we have Q_sk = τ_sk; otherwise, Q_sk is set to the latest timestamp Q_lk from its neighbors l (i.e., l ∈ S ∧ G[s, l] = 1).

Subsequently, we detail the framework of PITO in Figure 3. Algorithm PITO runs on each satellite in parallel, including two stages: (1) task inclusion, and (2) consensus and task removal. Specifically, in the task inclusion stage, each satellite s ∈ S independently constructs sequence θ_s. This process may result in various removal impacts for a specific task t ∈ T on different satellites. Then, another stage is required, consisting of a further two steps: first, a common removal impact vector R_s is reached among satellites during the consensus process; then, satellites remove conflict tasks from their sequences in the task removal process. The above two stages perform alternately. When there are no changes in offloading assignment θ, Algorithm PITO terminates in all satellites. Notably, in PITO, satellites only communicate with neighbors during the consensus process, which is expected to reduce the communication times. The procedure of PITO is then summarized in Algorithm 1.

Algorithm 1. PITO

Input: satellites S, delay-sensitive tasks T, network topology G. Output: offloading assignment θ. Initialize Rs, Ws, and Qs for each satellite s ∈ S; Initialize θ = {θs| s ∈ S} where θs = ∅ for ∀s ∈ S, and converged = False; while not converged      Let θold = θ;      Performs task inclusion on each s ∈ S;      Send vectors Rs, Ws, and Qsof each s ∈ S to its neighbors k with G[s, k] = 1;      Update Qs of each s ∈ S by received information;      Perform consensus process until a common Rs is reached;      Perform task removal on each s ∈ S;      if θ = θold           Let converged = True;      end end Output offloading assignment θ;

4.2. Task Inclusion

In the task inclusion stage, each satellite independently incorporates tasks into its task sequence, based on local information.

For satellite s ∈ S, the inclusion impact vector I_s = [I_s1, I_s2, …, I_sn]^T is first constructed according to (20), where entry I_st = $\mathcal{I}$(θ_s ⊕ t) for ∀ t ∈ T. Then, I_s is compared with vector R_s = [R_s1, R_s2, …, R_sn]^T (after consensus). One of the tasks in T will be inserted into θ_s only if

$$\underset{t\in T}{\max }\{R_{st}-I_{st}\}>0$$

(23)

According to Lemma 1, when (23) is satisfied, it indicates the presence of an inclusion that can reduce F(θ). Then task t′ = argmax_t∈T{R_st − I_st} will be inserted into the p′-th position of sequence θ_s, where p′ leads to value $\mathcal{I}$(θ_s ⊕ t′) (i.e., p′= argmin_{p∈{1,2,…,|θs|+1}}{F(θ_s ⊕_p t′) − F(θ_s)}). Next, we update vectors R_s and W_s by setting R_st′ = I_st′ and W_st′ = s. After that, I_s is recalculated and (23) is checked again. This process is repeated until there are no remaining tasks in T or (23) is no longer met. Finally, we obtain new R_s′ based on updated θ_s′. The task inclusion stage is further presented in Algorithm 2.

Algorithm 2. Task Inclusion

Input: task set T, task sequence θs, and vectors Rs and Ws. Output: new task sequence θs′, new vectors Rs′ and Ws′. Calculate inclusion impact vector Is; while {T/θs} ≠ ∅ and (23) is met      Obtain task t′= argmaxt∈T{Rst − Ist} and appropriate position p′ in θs;      Insert t′ into p′-th of θs;      Update Rst′ = Ist′, Wst′ = s;      Update Is; end Let θs′ = θs and Ws′ = Ws; Obtain Rs′ based on θs′; Output θs′, Rs′, and Ws′;

Following the task inclusion stage, new parameters (θ_s′, R_s′, and W_s′) are generated on each satellite s ∈ S. However, since tasks are included independently, a specific task may be assigned to multiple satellites, leading to task conflicts. Moreover, variations exist in obtained R_s among different satellites s ∈ S. These pose a challenge in achieving a unified offloading assignment θ. Thus, we introduce the consensus and task-removal stage to resolve the above problems.

4.3. Consensus and Task Removal

In this stage, satellites reach a common R_s and remove conflict tasks from their task sequences.

4.3.1. Consensus

During the consensus process, satellites s ∈ S broadcasts R_s, W_s and Q_s to neighboring satellites via LISL. Subsequently, the values of R_s and W_s in satellite s ∈ S are revised, based on the information of its neighbors, following the action rules [35] designed to achieve consensus. Then, the adopted consensus mechanism is detailed as follows.

Considering sending satellite s and receiving satellite k, vectors R_s = [R_s1, R_s2, …, R_sn]^T, W_s = [W_s1, W_s2, …, W_sn]^T and Q_s = [Q_s1, Q_s2, …, Q_sm]^T are transmitted from s to k via LISL. After receiving these vectors, satellite k first updates its timestamp vector Q_k, based on (22). Then, for each task t ∈ T, elements R_kt and W_kt in R_k and W_k are updated according to

Table 2. Action Rules for satellite k after receiving information from satellite s.

Value of Wst from Sending Satellite s	Value of Wkt from Receiving Satellite k	Actions Taken by k
s	k	if Rst < Rkt → Update
	s	Update
	l ∉ {s, k}	if Qsl > Qkl or Rst < Rkt → Update
	0	Update
k	k	Maintain
	s	Reset
	l ∉ {s, k}	if Qsl > Qkl → Reset
	0	Maintain
l ∉ {s, k}	k	if Qsl > Qkl and Rst < Rkt → Update
	s	if Qsl > Qkl → Update else → Reset
	l	Qsl > Qkl → Update
	q ∉ {s, k, l}	if Qsl > Qkl and Qsq > Qkq → Update if Qsl > Qkl and Rst < Rkt → Update if Qsq > Qkq and Qsl < Qkl → Reset
	0	if Qsl > Qkl → Update
0	k	Maintain
	s	Update
	l ∉ {s, k}	if Qsl > Qkl → Update
	0	Maintain

. In Table 2, three actions are considered, with Maintain being the default one: (1) Update: R_kt = R_st and W_kt = W_st; (2) Maintain: R_kt = R_kt and W_kt = W_kt; and (3) Reset: R_kt = ∞ and W_kt = 0.

Notably, the consensus process is crucial for reaching a common R_s among satellites. Recall that the removal impact vector R_s, as defined in Section 4.1, relies heavily on its task sequence θ_s. Broadcasting the removal impacts directly to all satellites may lead to server elements in R_s reaching non-existent small values, which cannot be achieved by any satellite s ∈ S with its task sequences θ_s.

4.3.2. Task Removal

After reaching a common R_s through the consensus process, there still exist task conflicts. Thus, the task removal process is conducted on each satellite s ∈ S to eliminate task conflicts in θ_s.

For satellite s ∈ S, we first obtain pending removal tasks Ψ_s = {t ∈ θ_s| W_st ≠ s}. Tasks in Ψ_s are those which exist in θ_s but are believed not to be offloaded to s, according to W_s. Then, a local removal impact vector R_s^• = [R_s1^•, R_s2^•, …, R_sn^•]^T is calculated by θ_s, where entry R_st^• = $\mathcal{R}$(θ_s ⊖ t) for ∀ t ∈ θ_s, and otherwise, R_st^• = ∞. Next, a task t ∈ Ψ_s will be removed from θ_s when

$$\underset{t\in {\mathrm{\Psi }}_s}{\max }\{R_{st}^{•}-R_{st}\}>0$$

(24)

If condition (24) is met, it implies the presence of a conflicting task with a higher removal impact value, indicating a worse offloading assignment. Then, task t′ = argmax_t∈Ψs{R_st^• − R_st} will be removed from θ_s and Ψ_s. After that, R_s^• are updated and (24) is evaluated again. This process is continued until Ψ_s = ∅ or (24) is no longer met. Finally, the remaining tasks in Ψ_s will be retained in θ_s, and we set W_st = s and R_st = $\mathcal{R}$(θ_s ⊖ t) for each t ∈ Ψ_s. The task removal process is summarized in Algorithm 3.

Algorithm 3. Task Removal

Input: task sequence θs, and vectors Rs and Ws. Output: new task sequence θs′, new vectors Rs′ and Ws′. Obtain pending removal tasks Ψs = {t ∈ θs| Wst ≠ s}; Calculate local removal impact vector Rs• = [Rs1•, Rs2•, …, Rsn•]T; while Ψs ≠ ∅ and (24) is met      Obtain task t′ = argmaxt∈Ψs{Rst• − Rst};      Remove t′ from θs and Ψs;      Update Rs•; end for each remaining tasks t ∈ Ψs      Update Wst = s;      Update Rst = $\mathcal{R}$(θs ⊖ t); end Let θs′ = θs, Rs′ = Rs and Ws′ = Ws; Output θs′, Rs′, and Ws′.

4.4. Convergence and Complexity Analysis

The convergence of PITO is naturally guaranteed. In PITO, each satellite s ∈ S optimizes F(θ) by iteratively adding or removing tasks into or out of its task sequence θ_s. According to Lemma 1, the offloading assignment θ_s of each satellite s will be changed as long as F(θ) is decreased. Thus, Algorithm PITO achieves convergence when there are no changes to θ after one iteration.

Subsequently, we discuss the complexity of PITO. There are m satellites and n delay-sensitive tasks in SEC. In the task inclusion stage, a total of m satellites independently integrate, at most, n tasks into their task sequences, and then the complexity is $\mathcal{O}$(mn). In the consensus process, each of the m satellites receives information from up to four neighboring satellites, and updates elements in its vectors for n tasks; then, the corresponding complexity is denoted as $\mathcal{O}$(4mn). In the task removal process, a maximum of m satellites remove no more than n conflicting tasks from their sequences; then, its complexity is $\mathcal{O}$(mn). Therefore, the computational complexity in each iteration of PITO is $\mathcal{O}$(mn) + $\mathcal{O}$(4mn) + $\mathcal{O}$(mn) = $\mathcal{O}$(6mn). Let δ denote the number of iterations required for convergence, and then the complexity of Algorithm PITO is $\mathcal{O}$(6δmn), i.e., it is of polynomial complexity.

4.5. Re-Offloading Mechanism

Using PITO, delay-sensitive tasks can be offloaded on board by satellites. However, due to the dynamics in SEC, the dynamic arrival of delay-sensitive tasks disrupts the original offloading assignment, even making it infeasible. Thus, we propose a re-offloading mechanism based on match-up strategy [38,39,40] in this subsection.

At time τ, q delay-sensitive tasks T_x = {t_n+1, t_n+2, …, t_n+q} are newly generated by observation satellites D_x = {n + 1, n + 2, …, n + q}, which need to be processed by SEC satellites in S. Each task t_i ∈ T_x is also characterized by tuple <λ_i, μ_i, σ_i> in Section 3.1. Given the original assignment θ, the procedure of the proposed re-offloading mechanism is described as follows:

Step 1: Obtain the influence horizon. Let ε be the expected re-offloading time, then the re-offloading assignment θ* = {θ_s*| s ∈ S} will be executed at time τ + ε. Additionally, new tasks in T_x are expected to be completed before max_ti∈Txσ_i. Thus, the influence horizon is defined as [μ_a, μ_b] = [τ + ε, max_ti∈Txσ_i].

Step 2: Determine the re-offloading tasks. With horizon [μ_a, μ_b], when new delay-sensitive tasks in T_x are offloaded, the original tasks in the same horizon of θ are disrupted, represented as T_o = {t_i ∈ T | ${\mathrm{\tau }}_i^S$ ∈ (μ_a, μ_b)}. Next, by the time μ_a, several tasks in θ may have been completed or are currently in processing. Since re-offloading assignment θ* must not conflict with implemented tasks, tasks T_a = {t_i ∈ T | ${\mathrm{\tau }}_i^S$ ≤ μ_a} cannot be re-offloaded. Additionally, tasks in θ executing after μ_b are slightly impacted, and then these tasks, denoted as T_b = {t_i ∈ T | ${\mathrm{\tau }}_i^S$ ≥ μ_b}, are reserved to reduce the re-offloading time. Thus, T = T_a ∪ T_o ∪ T_b exists, and the re-offloading tasks are T_r = T_x ∪ T_o. Figure 5 illustrates an example of the proposed task sets in θ, where tasks in T_a, T_o and T_b are marked in orange, cyan, and red, respectively.

The above task sets (T_a, T_o and T_b) are obtained in a distributed way in Algorithm 4. First, each satellite s ∈ S calculates time parameters for tasks in θ_s, as described in Section 3.3. Then, vector U_s = [U_s1, U_s2, …, U_s(n+q)]^T is generated, where entry U_st = 1 for t ∈ {θ_s | ${\mathrm{\tau }}_t^S$ ≤ μ_a}, U_st = 2 for t ∈ {θ_s | ${\mathrm{\tau }}_t^S$ ≥ μ_b}, and otherwise, U_st = 0. Since U_st is only determinated by satellite s with t ∈ θ_s, a common U_s can be easily obtained, where U_st = 0, 1, and 2 for t belonging to T_r, T_a, and T_b, respectively.

Algorithm 4. Task classification

Input: satellites S, original assignment θ. Output: vectors Us, ∀s ∈ S. Each satellite s ∈ S calculates time parameters for tasks in θs; Obtain initial Us for each satellite s ∈ S; while a common Us is not reached     SendUs of each s ∈ S to neighboring satellites k with G[s, k] = 1;     for each received Uk by satellite s      //Update Us on satellite s         for each t ∈ T             if Ust = 0 and Ukt ≠ 0                 Let Ust = Ukt;             end         end     end end Output Us, ∀s ∈ S.

Step 3: Obtain re-offloading assignment. First, we obtain the available buffer size MA_s for each s ∈ S. By original assignment θ, several tasks T_c = {t_i ∈ T | ${\mathrm{\tau }}_i^F$ ≤ μ_a} have been accomplished at time μ_a, and buffer resources occupied by them are released; then, we have

$$M{A}_s=M_s-{\displaystyle \sum _{t_i\in {\mathsf{\theta }}_s}{\mathrm{\lambda }}_i}+{\displaystyle \sum _{t_i\in {\mathsf{\theta }}_s\cap T_c}{\mathrm{\lambda }}_i}$$

(25)

Subsequently, two modifications are involved in F(θ*). For task t_i ∈ T_x, data uploading begins at time μ_a. Then, the data readiness time ${\mathrm{\tau }}_i^D$, as defined in (6), is revised as

$${\mathrm{\tau }}_i^D={\mathsf{\mu }}_a+{\mathrm{\tau }}_{i,s}^{comm}$$

(26)

Moreover, some tasks in θ_k may also be re-offloaded to θ_s*. At time μ_a, the involved data are transmitted from k to s, leading to additional delays and energy usage. Therefore, for tasks t_i ∈ θ_k ∩ θ_s*, the data readiness time ${\mathrm{\tau }}_i^D$ in (6) and energy consumption E_i,s in (9) are revised as

$${\mathrm{\tau }}_i^D={\mathsf{\mu }}_a+{\mathrm{\tau }}_{i,k,s}^{LISL}$$

(27)

$$E_{i,s}={\epsilon }_1{\mathrm{\tau }}_{i,a}^{RISL}+{\epsilon }_2{(\mathrm{\tau }}_{i,a,k}^{LISL}+{\mathrm{\tau }}_{i,k,s}^{LISL})+\kappa C_s^2{\mathrm{\lambda }}_i{\mathsf{\mu }}_i$$

(28)

After that, the re-offloading is performed, which introduces two main modifications in the original PITO: (1) in the task inclusion stage, only tasks t ∈ T_r (i.e., U_st = 0) can be inserted into each θ_s*. The insertion positions are also limited by the pruning approach; (2) the tasks in T_a ∪ T_b are reserved in θ_s* during the task removal process.

Specifically, in the task inclusion stage, the pruning approach in Algorithm 5 is proposed, generating candidate insertion positions Φ_s for each satellite s ∈ S with θ_s*.

Algorithm 5. Pruning approach

Input: task sequence θs* and vectors Us. Output: candidate positions Φs. Initialize positions pa = 1 and pb = |θs∗|+1; for u = 1 to |θs∗|     Let t = θs∗[u];     if Ust = 2         Let pb = u;         Break;     end end for v = |θs∗| to 1     Let t = θs∗[v];     if Ust = 1         Let pa = v + 1;         Break;     end end Output candidate positions Φs = {pa, pa +1, …, pb};

In Algorithm 5, positions p_a and p_b are initialized as 1 and |θ_s*| + 1, respectively. Then, in Lines 2–8, index u of the first task t ∈ θ*∩ T_b is obtained, and we set p_b = u. Similarly, index v of the last task t ∈ θ_s* ∩ T_a is obtained by Lines 9–15, and we set p_a = v + 1. By p_a and p_b, we obtain candidate insertion positions Φ_s = {p_a, p_a +1, …, p_b}. Based on Φ_s, the inclusion impact vector I_s = [I_s1, I_s2, …, I_s(n+q)]^T is calculated, where entry I_st = min_p∈Φs{F(θ_s* ⊕_p t) − F(θ_s)} for ∀ t ∈ T_r/θ_s*, satisfying constraint (12), and otherwise, I_st = ∞. After inserting a task into θ_s*, we update Φ_s and I_s. Differently from Algorithm 2, the task inclusion process in re-offloading is continued until {T_r/θ_s*} = ∅ or (23) is no longer satisfied.

Moreover, in the task removal process, tasks t ∈ T_a ∪ T_b are retained, and only tasks in T_r can be removed from θ_s*. Hence, the pending removal tasks for satellite s are revised as Ψ_s = {t ∈ θ_s* ∩ T_r | W_st ≠ s} in re-offloading. Apart from above modifications, Algorithm PITO proceeds as the original design, and the two stages of PITO are alternately performed until a re-offloading assignment θ* is obtained.

The proposed re-offloading mechanism has the following advantages: Firstly, it reduces the re-offloaded tasks and uses a pruning approach to minimize insertion attempts, thereby reducing re-offloading time. Secondly, reserving tasks t ∈ T_b in θ* prevents unnecessary data transmission, resulting in lower extra-energy usage and maintaining assignment quality.

5. Computational Experiments

A series of computational experiments are conducted to describe the performance of the proposed PITO.

5.1. Experimental Setup

We establish an SEC simulation environment using MATLAB, as in [1,21,27], adopting six Walker Delta constellations A–F, listed in

Table 3. Satellite Constellations.

Constellation	Altitude (km)	Inclination (deg)	Planes	Satellites (m)
A	5000	97.4	2	6
B	5000	53.8	3	9
C	3000	60	4	16
D	480	97.4	3	24
E	550	60	6	36
F	780	86.4	6	66

. The simulation is set to start at [20 Mar 2024 00:00:00.000 UTCG], with satellite coordinates obtained from the Satellite Tool Kit (STK). We conduct the experiments under three types of instances: small, medium, and large, resulting in 48 combinations (3 × 16), detailed in

Table 4. Parameter Size for Each Instance Type.

Instance Type	Constellations	Task Number	Task Density	Deadline	Combination Number
Small	A, B	3, 5	low, high	emergency, normal	2 × 2 × 2 × 2 = 16
Medium	C, D	10, 20	low, high	emergency, normal	2 × 2 × 2 × 2 = 16
Large	E, F	50, 100	low, high	emergency, normal	2 × 2 × 2 × 2 = 16

. Each combination consists of 10 different testing instances. The altitudes of observation satellites are set to 500 km, with an average distance between satellites of 1000 km and 100 km for low-density and high-density instances, respectively. The task deadlines σ_i are randomly generated from [15,25] for emergency cases and [15,31] for normal cases. Additional parameters are detailed in

Table 5. Simulation Parameters.

Parameters	Default Values
Data size of tasks λi	10~30 Mbit
Workload of task μi	1~1.5 Kcycle/bit
Computing capacity of satellites Cs	5 GHz
Memory space of satellites Ms	500 Mbit
Energy consumption limitation of satellites Hs	5000 J
Rate of LISL rLISL	100 Mbps
Transmission power of RISL ε1	2 w
Transmission power of LISL ε2	1 w
Effective capacitance coefficient κ	10−28
Weight factors α and β	0.5

.

The proposed PITO is compared with three state-of-the-art algorithms: CNP [24], DETS [26], and ADMM [27]. The brief explanations of these algorithms are as follows.

CNP is a distributed coordination mechanism based on market-like agreements, where agents bid on tasks announced by a manager agent, with the most suitable agent winning the contract.

DETS is a centerless method based on the directed diffusion algorithm, using a novel computing gradient that jointly considers communication and computation resources.

ADMM is a distributed mechanism that uses binary variable relaxation to convert the original nonconvex problem into a linear programming problem. After solving it with distributed convex optimization, a variable recovery algorithm is applied to obtain a discrete solution.

Then, we use the following three performance indicators:

(1)

RV: the relative value of F(θ) for an algorithm compared with others; we have

$$RV=\frac{F(\mathbf{\theta })-F_{all}(\mathbf{\theta })}{F_{all}(\mathbf{\theta })}$$

(29)

where F(θ) is the objective value of an algorithm for a testing instance, and F_all(θ) is the optimal objective value obtained by all algorithms for the same instance. A lower RV value means better performance. It helps to reduce variation among instances in the same combination.

(2)

CT: the communication times, indicating the communication burden between satellites during task offloading.

(3)

RT: the running time required for the task offloading process.

To eliminate randomness, each algorithm is independently run 10 times for each instance. We then calculate average RV (aRV), average CT (aCT), and average RT (aRT), to evaluate their performance. All these algorithms are coded in MATLAB and run on a PC with an Intel Core i7-14700k CPU @ 5.6 GHz and 64 GB of RAM in the 64-bit Windows 11 operation system.

5.2. Comparison with Existing Distributed Algorithms

In this subsection, Algorithm PITO is compared with three competitors (i.e., CNP [24], DETS [26], and ADMM [27]), as described in Section 5.1. The comparison results for small-scale, medium-scale, and large-scale instances are grouped in

Table 6. Comparison results for small-scale instances.

Instance Type	CNP			DETS			ADMM			PITO
	aRV	aCT	aRT	aRV	aCT	aRT	aRV	aCT	aRT	aRV	aCT	aRT
{A, 3, low, emergency}	0.0380	12	0.0172	0.0141	17.59	0.0172	0.0103	52	0.7014	0.0014	8	0.0177
{A, 3, low, normal}	0.0427	12	0.0172	0	17.85	0.0187	0.0079	52	0.6914	0.0016	8	0.0169
{A, 3, high, emergency}	0.0450	12	0.0021	0.0196	16.00	0.0029	0.0155	52	0.3789	0.0033	7.75	0.0031
{A, 3, high, normal}	0.0497	12	0.0228	0.0207	21.44	0.0185	0.0105	54	0.5845	0.0028	9.36	0.0187
{A, 5, low, emergency}	0.0449	20	0.0226	0.0274	36.00	0.0435	0.0110	50	2.5463	0.0002	15	0.0567
{A, 5, low, normal}	0.0413	20	0.0224	0	36.00	0.0431	0.0155	50	2.5087	0.0002	15	0.0591
{A, 5, high, emergency}	0.0346	20	0.0186	0.0954	38.77	0.0438	0.0248	52	2.5411	0.0001	16	0.0565
{A, 5, high, normal}	0.0337	20	0.0192	0.0932	38.42	0.0434	0.0280	52	2.5181	0.0006	16	0.0590
{B, 3, low, emergency}	0.0401	15	0.0030	0.0287	18.59	0.0038	0.0239	84	1.1158	0.0022	8	0.0074
{B, 3, low, normal}	0.0383	15	0.0029	0.0250	18.65	0.0037	0.0232	84	1.1061	0.0019	8	0.0045
{B, 3, high, emergency}	0.0436	15	0.0023	0.0459	18.74	0.0032	0.0244	87	1.0348	0.0038	9	0.0041
{B, 3, high, normal}	0.0421	15	0.0036	0.0372	23.39	0.0048	0.0194	81	1.0032	0.0035	7	0.0046
{B, 5, low, emergency}	0.0430	25	0.0097	0.0060	36.59	0.0309	0.0175	93	6.8399	0.0011	12	0.0409
{B, 5, low, normal}	0.0433	25	0.0180	0.0040	36.76	0.0302	0.0158	93	6.9443	0.0010	12	0.0412
{B, 5, high, emergency}	0.0698	25	0.0191	0.0656	38.74	0.0345	0.0481	93	7.0396	0.0004	13	0.0350
{B, 5, high, normal}	0.0691	25	0.0237	0.0552	38.34	0.1103	0.0428	93	6.0205	0.0010	13	0.0269

,

Table 7. Comparison results for medium-scale instances.

Instance Type	CNP			DETS			ADMM			PITO
	aRV	aCT	aRT	aRV	aCT	aRT	aRV	aCT	aRT	aRV	aCT	aRT
{C, 10, low, emergency}	0.0725	50	0.0516	0.0752	76.80	0.1100	0.0270	490.24	79.1380	0.0004	47	0.3098
{C, 10, low, normal}	0.0778	50	0.0351	0.0661	76.35	0.1249	0.0267	490.72	78.9001	0.0005	47	0.3202
{C, 10, high, emergency}	0.0486	50	0.0185	0.0326	65.00	0.0729	0.0559	506.08	82.4659	0.0009	43.28	0.3141
{C, 10, high, normal}	0.0481	50	0.0180	0.0293	65.00	0.0713	0.0455	506.64	81.9928	0.0008	43.78	0.3106
{C, 20, low, emergency}	0.0961	100	0.1143	0.0703	193.82	0.5209	0.0471	1317.76	994.6563	0	92	1.0020
{C, 20, low, normal}	0.0964	100	0.1112	0.0739	193.97	0.6528	0.0477	1317.92	993.6440	0	92	1.0063
{C, 20, high, emergency}	0.0580	100	0.0611	0.0909	186.79	0.6226	0.0388	1349.44	1022.2295	0	100	0.9560
{C, 20, high, normal}	0.0583	100	0.0667	0.0869	186.99	0.5507	0.0395	1349.76	1024.8514	0	100	1.8343
{D, 10, low, emergency}	0.0350	50	0.0165	0.0401	78.48	0.0681	0.0272	1592	307.8734	0.0049	38	0.4731
{D, 10, low, normal}	0.0360	50	0.0165	0.0452	78.82	0.0689	0.0274	1592	306.6067	0.0048	38	0.4596
{D, 10, high, emergency}	0.0403	50	0.0158	0.0156	76.37	0.0776	0.0212	952	186.0931	0.0011	37	0.4362
{D, 10, high, normal}	0.0407	50	0.0161	0.0148	76.63	0.0797	0.0179	952	188.0270	0.0011	37	0.4368
{D, 20, low, emergency}	0.0437	100	0.0388	0.0409	153.49	0.3190	0.0303	2424	1377.0521	0.0090	87	3.2001
{D, 20, low, normal}	0.0408	100	0.0386	0.0393	153.83	0.3346	0.0337	2424	1484.6625	0.0079	87	3.1638
{D, 20, high, emergency}	0.1193	100	0.0740	0.0704	165.00	0.4541	0.0393	2424	1528.1982	0.0036	81	3.0737
{D, 20, high, normal}	0.1063	100	0.0960	0.0675	165.00	0.5563	0.0360	2424	1514.9961	0.0005	81	3.2331

and

Table 8. Comparison results for large-scale instances.

Instance Type	CNP			DETS			ADMM			PITO
	aRV	aCT	aRT	aRV	aCT	aRT	aRV	aCT	aRT	aRV	aCT	aRT
{E, 50, low, emergency}	0.0745	250	0.1506	0.0767	456.57	0.5345	0.0339	2352	1335.7939	0	169.59	5.8748
{E, 50, low, normal}	0.0767	250	0.1541	0.0696	456.18	0.5302	0.0300	2352	1335.2840	0	169.91	5.9403
{E, 50, high, emergency}	0.0750	250	0.1440	0.0667	460.00	0.5649	0.0327	1964	1754.5021	0.0002	203.17	22.9450
{E, 50, high, normal}	0.1037	250	0.1814	0.0965	545.00	0.8223	0.0387	1964	1907.0651	0.0002	217	32.2933
{E, 100, low, emergency}	0.2919	500	0.8558	0.1197	1153.46	1.9715	0.0713	3744	2251.2133	0	337.34	90.3036
{E, 100, low, normal}	0.2711	500	0.9952	0.1438	1088.29	2.0296	0.0751	3744	2362.8377	0	373.81	158.2195
{E, 100, high, emergency}	0.3003	500	2.1974	0.1355	1278.63	3.0104	0.0905	3858	2634.2013	0	358.68	147.7549
{E, 100, high, normal}	0.3068	500	2.2224	0.1204	1278.98	2.7709	0.0871	3924	2756.0978	0	358.64	156.2090
{F, 50, low, emergency}	0.0439	250	0.0931	0.0537	445.00	0.4262	0.0330	2574	1393.1036	0.0082	164	34.4894
{F, 50, low, normal}	0.0449	250	0.1209	0.0494	445.00	0.6396	0.0312	2574	1445.8109	0.0070	164	35.5420
{F, 50, high, emergency}	0.0625	250	0.1138	0.0472	383.92	0.4567	0.0251	2552	2783.5166	0.0028	192.31	37.9846
{F, 50, high, normal}	0.0550	250	0.1523	0.0165	441.85	0.4779	0.0150	2816	2609.7868	0.0024	191.38	60.5440
{F, 100, low, emergency}	0.1388	500	0.4792	0.1054	936.68	1.2663	0.0473	4092	3436.2467	0.0006	316.96	163.3933
{F, 100, low, normal}	0.0859	500	0.3493	0.0483	1008.56	1.3893	0.0305	4224	3792.8678	0.0006	389.23	256.1243
{F, 100, high, emergency}	0.2422	500	0.5703	0.0874	1008.98	1.3540	0.0443	4224	3851.9423	0	332	236.6883
{F, 100, high, normal}	0.2377	500	0.6161	0.0909	1008.29	1.6362	0.0420	4686	4013.7642	0	332	221.7397

, respectively. The performances of the four algorithms vary markedly in terms of aRV, aCT, and aRT, and optimal values are marked in bold. These tables show that PITO obtains the optimal aRV and aCT in almost all instances, and only in a few cases does DETS perform the best. This is because DETS uses a directed diffusion algorithm that considers communication and computation resources, yielding good solutions for small-scale instances. However, it tends to become stuck in local optima for large-scale instances. Figure 6 further illustrates the line charts of aRV, aCT, and aRT for these algorithms across different instances.

Figure 6a illustrates the fact that PITO achieves minimal aRV values compared to the three competitors, highlighting its superiority in offloading assignment quality. For small-scale instances, algorithm differences are relatively small due to the limited solution space. However, as the instance scale increases, variations between algorithms become more pronounced. For example, in instances with {E, 100}, the objective value F(θ) of PITO is decreased by 22.63% (≈(1.2925 − 1)/1.2925) and 11.49% (≈(1.1298 − 1)/1.1298) compared to CNP and DETS, respectively. This is because the CNP and DETS are more easily trapped into local optima [33] due to reliance on direct neighbor information (as discussed in Section 4.1), which consequently impacts offloading assignment quality. In contrast, PITO adopts a consensus process, where satellites share comprehensive information vectors with their neighbors, enabling PITO to escape from local optimum. Algorithm ADMM sidesteps these local optimum issues by centrally updating global variables [27]. However, it still faces challenges for discrete–continuous transformation and binary variables recovery [27], which affect assignment quality, especially for large-scale instances.

Figure 6b shows the aCT of all algorithms. PITO achieves the smallest values in all instances, indicating its low communication burden. This is because satellites in PITO only communicate with neighbors during the consensus process, and the adopted vectors further reduce the required communication times. The CNP and DETS rank second and third, respectively. The diffusion mechanism in DETS necessitates more communication times, compared to CNP. The ADMM performs the worst because the global variables update in each iteration, requiring local variables from all satellites. This results in a significant communication burden, which also increases with the number of satellites and tasks.

Figure 6c illustrates the aRT of all algorithms. CNP has the shortest running time due to its simplicity. Notably, CNP, DETS, and PITO show a slight increase in running time as the scale grows, while ADMM exhibits a significant ascending trend. This is attributed to ADMM relying on the iteration of convex optimization algorithms or CVX tools [27], which are time-consuming, especially for large-scale instances. PITO has a certain increase of aRT in large-scale instances, due to the higher number of satellites and tasks requiring more iterations to reach consensus, and this issue can be addressed by dividing tasks into groups or clustering satellites.

Based on Figure 6, PITO consistently achieves the best assignments with minimal communication burden, although taking slightly more time than DETS and CNP. Generally, the slight increase in runtime for better assignments is worthwhile. Consequently, we conclude that PITO outperforms existing methods in solving task offloading problems in SEC.

5.3. Validation of the Re-Offloading Mechanism

In this subsection, we validate the effectiveness of the proposed re-offloading mechanism. We compare it with the existing z-stage method [37] in two groups. The z-stage method re-offloads all uncompleted tasks. In contrast, our proposed mechanism only re-offloads tasks in T_r = T_x ∪ T_o, and uses a pruning approach to avoid unnecessary insertion attempts, further speeding up the re-offloading process. Similar to Section 5.2, ten different testing instances are generated for each combination, and each algorithm independently runs ten times for each instance. The comparison results are presented as follows.

Figure 7 shows the results of aRV and aRT under different numbers of newly generated tasks, q, using origin instances with size of {B, 20}. The proposed re-offloading mechanism consistently generates assignments with aRV values similar to those of the z-stage method. When q = 5, although the proposed re-offloading mechanism exhibits slight backwardness in aRV, the running time decreases by 89.11% (≈(0.1038 − 0.0113)/0.1038) compared to the z-stage method. As q increases, the difference between the two methods diminishes. This is because more newly generated tasks tend to have a larger μ_b value, leading to more tasks involved in re-offloading. With the instances of q = 30, the differences in aRV between the two approaches are negligible, yet the proposed re-offloading mechanism still reduces running time by 57.36% ((≈(0.7024 − 0.2995)/0.7024)).

Figure 8 illustrates the comparison results of aRV and aRT under different instances with q = 10. The difference in aRV between two approaches remains consistently small. However, as the instance scales increase, there is a notable contrast in their running time. Especially in instances with size {F, 100}, the proposed re-offloading mechanism reduces the running time by 91.23% (≈(34.0785 − 2.9881)/34.0785). This reduction is attributed to the proposed mechanism retaining several original subsequences based on influence intervals, thereby minimizing re-offloading tasks. Furthermore, the employed pruning approach significantly reduces insertion attempts. These special designs of our proposed mechanism allow a reduction in running time while ensuring assignment quality. Conversely, the z-stage method includes all uncompleted tasks in re-offloading, leading to a significant increase in runtime as the instance scale grows.

6. Discussion

In this subsection, we further discuss the effect of instance parameters (number of observation satellite n and number of SEC satellites m) on these algorithms. We organize our comparisons into two groups. Similarly, we generate ten different testing instances for each combination, and each algorithm independently runs ten times for each instance. Here are the comparison results:

Figure 9 illustrates comparison results of aRV, aCT, and aRT under different observation satellite numbers. The performance ranking of algorithms remains unchanged, despite variations in observation satellite numbers. PITO consistently achieves the optimal aRV and aCT across all instances, demonstrating its statistical effectiveness. Moreover, as the number of observation satellite increases, all algorithms exhibit an ascending trend in both aCT and aRT. With the instances of n = 80, PITO not only achieved significantly superior aRV values but also required 80.35% (≈(789 − 155)/789) and 74.29% (≈(603 − 155)/603) fewer communication times compared to ADMM and DETS, respectively.

Figure 10 shows the results of aRV, aCT, and aRT under different constellations. Once again, PITO achieves the optimal aRV. Additionally, with an increase in satellite number, the aCT and aRT values of CNP, DETS, and PITO show only marginal growth, while the values of ADMM exhibit a pronounced upward trend. That is because, in the consensus process of PITO, satellites only communicate with their neighbors using the vectors defined in Section 4.1, resulting in only a slight increase in the required convergence iterations δ as the satellite number increases. In the instances with constellation F (i.e., m = 66), PITO still achieves the best aRV value compared to other algorithms, and requires 26.00% (≈(100 − 74)/100) and 43.79% (≈(131.67 − 74)/131.67) fewer communication times than CNP and DETS, respectively.

7. Conclusions

This paper focuses on the task offloading problem in SEC with dynamic delay-sensitive tasks. Considering the special demands of delay-sensitive tasks, an MILP model is first presented minimizing the weight sum of deadline violations and energy consumption. Based on the MILP model, we take into account the sparsity of ISLs, and further propose a fully-decentralized algorithm called PITO to resolve the task offloading problem. To improve assignment quality, PITO utilizes a consensus process to avoid local optimum, which also reduces the required communication times. To deal with dynamic arriving delay-sensitive tasks, we introduce a re-offloading mechanism based on a match-up strategy, which reduces re-offloaded tasks and prevents unnecessary insertion attempts by pruning. The simulation results demonstrate that PITO outperforms state-of-the-art algorithms in [24,26,27]. It obtains optimal assignments with only a small additional time cost and reduces the communication burden, as well. The proposed re-offloading mechanism achieves significantly higher efficiency than the existing method [37], while maintaining the quality of re-offloading assignments. Extending PITO to handle more practical scenarios with data-dependence tasks is planned in our future work.