{'fraction_non_alphanumeric': 0.03786893446723362, 'fraction_numerical': 0.008304152076038018, 'mean_word_length': 4.621766029246344, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Blue Data Computation Maximization in 6G Space-Air-Sea Non-Terrestrial Networks

Non-terrestrial networks (NTN), encompassing space and air platforms, are a key component of the upcoming sixth-generation (6G) cellular network. Meanwhile, maritime network traffic has grown significantly in recent years due to sea transportation used for national defense, research, recreational activities, domestic and international trade. In this paper, the seamless and reliable demand for communication and computation in maritime wireless networks is investigated. Two types of marine user equipment (UEs), i.e., low-antenna gain and high-antenna gain UEs, are considered. A joint task computation and time allocation problem for weighted sum-rate maximization is formulated as mixed-integer linear programming (MILP). The goal is to design an algorithm that enables the network to efficiently provide backhaul resources to an unmanned aerial vehicle (UAV) and offload HUEs tasks to LEO satellite for blue data (i.e., marine user's data). To solve this MILP, a solution based on the Bender and primal decomposition is proposed. The Bender decomposes MILP into the master problem for binary task decision and subproblem for continuous-time resource allocation. Moreover, primal decomposition deals with a coupling constraint in the subproblem. Finally, numerical results demonstrate that the proposed algorithm provides the maritime UEs coverage demand in polynomial time computational complexity and achieves a near-optimal solution.


I. INTRODUCTION
Non-terrestrial networks (NTN), composed of space and airborne platforms, will be a key component of the upcoming sixth-generation (6G) wireless cellular systems as a means to provide the ubiquitous and ultra-high capacity wireless connectivity [1]. As a supplement to terrestrial infrastructure, space, and airborne stations have enormous potential for promoting flexible global connectivity in densely populated areas, costeffective network coverage in public safety situations, last-mile service delivery, and backhaul in remote, rural, and difficult-toaccess zones [2].
Meanwhile, maritime transportation is rapidly emerging as a significant component of our transportation infrastructure for domestic and international trade, national security, scientific research, aquaculture (fastest-growing food sector), and recreational activities [3]. The maritime world faces many challenges [4]. Therefore, the United Nations coined the term blue economy to improve human well-being and social equity while significantly reducing environmental risks and ecological scarcities related to oceans. Growing global trade requires more and more ships, many of which have to safely and productively sail international waters and harbors. Reliable maritime transportation depends on seamless connectivity with terrestrial networks to ensure accurate and intelligent navigational communications. Similarly, the maritime internet-of-things (M-IoT) applications are rapidly increasing [5]. Therefore, NTN is a suitable candidate for reliable and seamless maritime network connectivity.
Based on the preceding discussion, we propose to use jointly the low earth orbit (LEO) satellite and unmanned aerial vehicle (UAV) empowered with multi-access edge computing (MEC) for maritime users [6], [7]. Due to a scarcity of optical fibers and base stations, maritime communications must operate in a highly complex and heterogeneous setting, thus posing significant challenges to reliable transmission and traffic steering performance for service-oriented maritime communication networks. Existing work more focused on marine users association and communication [8], [9].
The main contribution of this paper is to fill the knowledge gap of marine user's task computation mechanism. In particular, we consider a heterogeneous 6G space-air-sea non-terrestrial network (SAS-NTN) to meet the increasing maritime network requirements. In this system, an LEO-MEC satellite and a UAV-MEC will aid existing offshore base stations, which work in a coordinated fashion for better maritime coverage. LEO-MEC and UAV-MEC are proposed as a seamless and reliable method to enhance the computing capability of high (HUE) and lowantenna gain user equipments (LUE) respectively. LEO-MEC allows the HUEs to offload their intensive blue data (generated by maritime users) computations task in a binary offloading manner. Our key contributions can thus be summarized as follows: • We propose an LEO-MEC satellite and UAV-MEC-based 6G SAS-NTN architecture by considering both variants of maritime users, i.e., high and low antenna gain users.
• We propose a binary task computation policy for HUEs depending upon their channel condition. • We develop an iterative algorithm based on the Bender and primal decomposition to solve the proposed mixedinteger linear programming (MILP), demonstrating the effectiveness in the simulation results.

A. Network Model
As shown in Fig. 1, we consider a heterogeneous 6G SAS-NTN maritime communication network. SAS-NTN consists of MEC empowered LEO satellite 1 , and a flying UAV-MEC serves as an aerial base station. We define a set C of coastal base stations (CBS), having a limited coverage radius that cannot satisfy the deep-sea maritime users' demand. Consequently, the LEO-MEC, a suitable candidate for service provisioning to these UEs, is considered. The LEO-MEC has considered a single high-gain antenna that can service HUEs task computation and UAV-MEC backhauling. Moreover, maritime UEs can be of two types: a set M h of M h HUEs and a set M l of M l LUEs. HUE and LUE can be differentiated based on the power of their antenna gain. Specifically, we consider network resource management for HUEs and UAV-MEC backhauling. Additionally, we assume HUEs are deployed on their specific pre-defined shipping routes.

B. Channel Model
We assume that the HUEs and the UAV-MEC need to send their data to LEO-MEC in the studied time of duration T . Moreover, each timeslot of T can be allocated to each HUE depending upon their channel condition and UAV-MEC. The LEO-MEC communicates with HUEs and the UAV-MEC in a time division multiple access (TDMA) fashion to avoid network interference. Both communications links in the scenario operate on the Ka-band (30 GHz), which is a well-known millimeter wave (mmW) carrier frequency for satellite communication as discussed in [10]. The TDMA scheme is used to enable directional transmissions in the considerably high path loss mmW band while maintaining low complex designs for the very-small-aperture terminal (VSAT). We consider the HUEs to be equipped with a single antenna. Therefore, the composite channel capture line-of-sight (LoS) and non-line-of-sight (NLoS) gain between LEO-MEC and its associated HUE i can be defined as: where α denotes the Rician fading channel coefficient, G s and G i denote the antenna gain of LEO-MEC and HUE respectively, and β i =γ +10γ log 10 ( di d0 )+φ captures the largescale fading on mmWave between LEO-MEC and HUE i. Here, γ represents the intercept parameter (path loss at reference distance d 0 ), γ is the slope of the fit (path loss exponent), d i reflects this distance between LEO-MEC and HUE i, and φ is the model deviation in fitting represented by a zeromean Gaussian random variable with standard deviation ω [10]. Similarly, the channel gain between LEO-MEC and UAV can be defined as: where G u is the UAV antenna gain and β u is large-scale channel fading between LEO-MEC and UAV-MEC.

C. Local Computation Model
The HUEs utilize store energy in local task computational mode. Each HUE i has a process computing speed f i (Hertz) and and a computation time τ i . Therefore, each HUE can process f i τ i /χ bits, where χ is the required number of cycles to process one bit of computational task data. Additionally, each HUE has an energy budget constrained by ν i f 3 i τ i ≤ E th , where ν i represents the energy efficiency coefficient of processor chip [11]. The HUEs local computation can be maximized under the studied time and energy budget. Each HUE can compute the task throughout the time, i.e., τ * i = T and process computing speed will be f * i = E th νiT 1 3 . Hence, the HUEs local computational rate (bits/s) will be:

D. UAV-MEC Backhaul and LEO-MEC Computation Model
It is assumed that UAV-MEC and HUEs cannot transmit simultaneously. Therefore, firstly the UAV-MEC can use backhaul resource for the duration of τ u ∈ [0, 1] and secondly, associated HUEs will offload their task according to their received time duration, i.e., τ i ∈ [0, 1] in each timeslot as illustrated in Fig. 2. We assume that the LEO-MEC has significant energy resources and computational power. Therefore, the time of task computation at LEO-MEC and feedback of computation results to UAV and HUEs can be neglected [12]. Hence, the studied time can be divided into UAV-MEC backhaul resources and HUEs task offloading as: The UAV-MEC backhaul throughput in each timeslot can be define as: where τ u is the time duration for UAV backhauling, B is the network bandwidth, µ i is the communication overhead for task offloading, e.g., packet header and encryption [13], P u is the UAV transmit power, and σ 2 is the LEO-MEC received noise power. Additionally, each HUE i transmit a power, i.e., P i = E th τi to offload the task. Thus, the computational rate which is equal to the throughput capacity of HUE i can be defined as: where τ i is the time duration allocates to HUE i and P i is the transmit power of each HUE i. Both (5) and (6) are increasing function of time.

E. Problem Formulation
The channel gain g = {g u , g i |i ∈ M h } is a time-varying parameter in the studied period, while the remaining parameters are constant. Thus, the association of HUE i depends upon the channel gain g in the studied time. The weighted computational and communication sum-rate of the LEO-MEC for maritime network in the studied time can be given by: where z i is unique weight for each HUE which depends upon their contribution in computation, y = {y i |i ∈ M h } is the HUEs offloading decision variable, and τ = {τ i |i ∈ M h } is the duration of allocated time to each HUE i. Here, y i ∈ {0, 1}, where y i = 1 indicates that HUE i will transmit its computation task to the LEO-MEC and y i = 0 implies a local task computation. Our objective is to maximize the weighted sum of computational and communication rate in studied time with channel realization g. Therefore, we can define the optimization problem as: The proposed problem (8) is an MILP, which is a nondeterministic polynomial-time (NP-hard) problem. Although, if y is given, this problem can be modified as linear programming which is describe in Section III.

III. PROPOSED ALGORITHM
In this section, we propose the joint Bender and primal decomposition to deal with the problem (8). The major challenge of solving (8) lies in the task computation decision problem. Hence, we provide Bender decomposition (BD) to decompose the main problem (8) into two subproblems, i.e., task computation decision and time resource allocation problem. Furthermore, the time resource allocation problem will be handled by primal decomposition.

A. Bender Decomposition
BD is a well-known solution technique to solve MILP problem [14]. This algorithm decomposes the MILP into binary variables integer programming as a master problem and continuous variables linear programming as a subproblem [9]. The main goal of the master problem is to solve an integer linear programming problem, while the subproblem is used to solve a continuous linear programming problem. This algorithm uses an iterative method that can reach a point of convergence when the pre-defined criterion on upper and lower bounds is met.
The initialization process happens first with a particular scenario. By fixing integer variables, the subproblem is solved by using only continuous variables. The subproblem will provide the optimal value of continuous variables (time allocation). After getting this solution, we produce the Bender cut for feasibility and optimality conditions by getting dual variables associated with fixed value integer variables, which allows us to solve the master problem. As a result, the disparity between the upper and lower bounds serves as the stopping condition for this algorithm. The joint MUEs task decision and time resource allocation problem-solution method will follow the steps described next.

1) Initialization:
We consider that the master problem can generate trivial solutions, and therefore, arbitrary task decisions are initially generated. Subsequently, the loop counter is initialized, i.e., j = 1. The task offloading decision variable is a binary indicator and, thus, their upper and lower bound can be initialized as y UB = 1 and y LB = 0, respectively. Moreover, we use an auxiliary variable in the form of a function Ψ, representing the objective function value of subproblem in each iteration j into the master problem objective function. In first iteration j = 1, the function Ψ j can be initialized as Ψ down , to restrict the subproblem from infeasible solution.
2) Subproblem: We assume that the channel realization g in each iteration j is obtained as g j . Thus, the optimal solution of time resource allocation from linear programming, i.e., {τ * u , τ * i } can be found by a low-complexity algorithm that is suitable for dynamic SAS-NTN environment. The subproblem can be defined as: where y * j is the optimal task decision in iteration j = 1 and κ j i represents the dual variable value associate with constraint (9d) of fixed task decision variable y * j i in each iteration j.

3) Bounds Calculation & Convergence Analysis:
The convergence of the BD can be analyzed by taking the difference between upper and lower bounds. The lower bound is given by computing the optimal value of an objective function in problem (13) for each iteration j, which can be defined as: where R j LB progressively less and less relaxed as iteration increase, therefore, lower bound is monotonously increasing with the iterations [14]. Subsequently, the upper bound is given by computing the optimal value of objective function in problem (8) for each iteration j as: After acquiring both bounds, the difference between them will decide the convergence and stopping criterion which can be defined as, continue, (12) and the tolerance parameter is pre-defined. Following convergence, the optimal value of {τ * u , τ * i }, and y * can be achieved.

4) Master Problem:
The master problem deals with binary task decisions in each iteration j. After the increment in loop counter, i.e., j = j + 1, the master problem solves which can be define as: where the inequality constraints in (13b) and (13c) indicate the Bender optimality and feasibility cuts, respectively. In each Compute optimal τ * j u , τ * j i , and κ j i by Algorithm 2 5:

6:
Compute the lower (R j LB ) and upper (R j UB ) bounds by (10) and (11) 7: Master Problem 8: Step 1: Update the loop counter j = j + 1 9: Step 2: Add new cut to the Master problem (13) 10: Step 3: Solve the updated master problem 11: Step 4: Compute the optimal value of y * j i and Ψ j 12: end while iteration, a new Bender cut is added to the master problem. The Bender cuts approximate the objective function of the subproblem (9) from below, which compose of j − 1 hyperplanes. The details of the BD are given in Algorithm 1.

B. Primal Decomposition
To deal with the time resource coupling constraint in (9b), we apply the primal decomposition. We use transformation on this constraint, and convert it into coupling variable . Thus, an auxiliary variable θ is introduced and can be given as [15]: At this point, our subproblem can be modified as: By fixing the value of θ, we can divide the modified subproblem (16) into two primal subproblems. The first primal subproblem can be defined as follows: Solve the primal-subproblems in parallel 4: Solve problem (17) and acquire the optimal timeresource allocation τ * i for associated HUEs and dual variable associated with constraint (17c). 5: Solve problem (18) and acquire the optimal timeresource allocation τ * u for UAV-MEC and dual variable associated with constraint (18c). 6: Update the time resource allocation auxiliary variable: θ = θ − ζ(λ 2 − λ 1 ). 7: until convergence where y * j represents the fix value of task computation decisions from master problem and λ 1 represents the dual variable associated with constraint (17c) in iteration j. The second primal-subproblem will be: where λ 2 represents the dual variable associated with constraint (18c). After getting the optimal solution from both primalsubproblems, we need to update the fixed auxiliary variable value by the following equation: where ζ is a step size. Both primal-subproblems, i.e., (17) and (18) can satisfy the conditions of linear programming. Therefore, we can use a standard optimization solver, e.g., Gurobi [16], to find an optimal solution. The details of the primal decomposition are summarized in the Algorithm 2.

IV. SIMULATION RESULTS AND DISCUSSION
For our simulations, we consider the HUEs in SAS-NTN to be uniformly distributed in 500 nautical mile square area (NM 2 ) as shown in Fig. 3. In this system, we deploy M h = 100 HUEs within the coverage region of an LEO-MEC and CBS. Each HUE transmits power is considered as P = 33 dBm because each HUE is assumed to be an energy-efficient device. The initial value of the lower bound to avoid infeasibility is set to Ψ down =−25. We use the python environment and the Gurobi optimization solver for implementing the proposed algorithm. Statistical results are averaged over 100 independent runs of random locations of HUEs. Our main simulation parameters are given in Table I. In Fig. 4, we present the convergence of the BD algorithm. The difference between the upper bound R UB and lower bound R LB value is decreasing and then finally converges. Fig. 4 shows that the BD algorithm converges to the optimal solution  just after eight iterations, which is a very efficient convergence time.
In Fig. 5, the total weighted sum of the computation and communication rates versus the number of HUEs is presented. Fig. 5 also demonstrates the comparison of the proposed algorithm with two schemes. Scheme 1 is considered as optimal results, which are computed by use of a standard optimization solver. Scheme 2 is regarded as a random task decision and time allocation to each HUE. Compared with scheme 2, our proposed algorithm performs better, which is close to optimal in the case of fewer HUEs. These patterns can be analyzed with both network bandwidth cases, i.e., B = 10 MHz and B = 20 MHz.
In Fig. 6, we present the total weighted sum of the communication, computation, and UAV-MEC backhaul rates. In this configuration, the system bandwidth is set to B = 20 MHz. We can observe that, in each scenario, the network allocates time for HUEs computation and UAV-MEC backhauling. As the number of HUEs increases, the network performance improves because more HUE needs to execute their task at the LEO-MEC satellite. This LEO-MEC enabled the SAS-NTN network to

V. CONCLUSION
In this paper, we devised task decisions and time resource allocation for the blue data computation maximization in space-air-sea non-terrestrial networks. The proposed problem is designed to be mixed-integer linear programming. To solve this problem, we have proposed a joint Bender and primal decomposition algorithm. Bender decomposition is an outer structure algorithm that divides the initial problem into master and subproblem and then solves iteratively. To deal with the coupling constraint in the subproblem, we proposed a primal decomposition algorithm to solve the subproblem iteratively. Simulation results have shown that the proposed algorithm can yield better results with efficient convergence time. In our future work, we will consider the user's mobility in the network.