Hybrid Satellite-UAV-Terrestrial Networks for 6G Ubiquitous Coverage: A Maritime Communications Perspective

Some recent research efforts have been devoted to characterize the maritime channel and accordingly promote the transmission efficiency of on-shore BSs. Wang et al. [9] developed a comprehensive framework to investigate the near-sea-surface channel. It was observed that the maritime channel is significantly influenced by propagation environments such as sea wave movement and the ducting effect over the sea surface. Particularly, for the impact of sea waves, Huo et al. [10] investigated the transmission link quality based on the ocean wave modeling for coastal and oceanic waters. As an interesting feature of maritime wireless channels, location-dependent large-scale fading dominates the channel condition. Exploiting this feature, Liu et al. [11] proposed a hybrid precoding scheme for on-shore BSs, to increase the minimum rate of users, which relies on only large-scale channel state information (CSI). Wei et al. [12] proposed a resource allocation scheme for extending the coverage area of on-shore BSs, which utilizes the shipping lane information. To avoid long-distance transmission for users on a ship, Kim et al. [13] proposed a hierarchical maritime radio network model, where users communicate with a cluster head equipped on the ship via Wi-Fi, and only the cluster head needs to communicate with on-shore BSs with long-distance transmission technologies. Recently, South Korea has launched a long-term evolution for maritime (LTE-Maritime) research project [14], which targets to cover key offshore areas using on-shore infrastructures. Despite these efforts, the coverage holes of on-shore BSs are inevitable due to their limited height and irregular site locations.

In addition to on-shore infrastructures, both mobile vessels and UAVs can be utilized to configure deployable BSs for maritime coverage enhancement. Yau et al. [15] envisioned a picture of multi-hop maritime network connecting various kinds of ships, buoys, and beacons. It was shown that the deployable infrastructure on the ocean is affected by sea surface movement, which may lead to frequent link breakages. In contrast to the vessel-based BS, aerial BSs suffer less from the sea surface movement. For example, Teixeira et al. [16] considered multi-hop airborne communications on the ocean, where the height of tethered flying BSs was optimized to maximize the network capacity. On the other hand, maritime UAVs can also be configured for deployable aerial BS, and they can be utilized for more agile deployment thanks to the high mobility. Li et al. [17] optimized both the trajectory and resource allocation of the UAV, to serve a sailing ship in an accompanying way. Therein the coexistence issue between UAVs and satellites/on-shore BSs have been discussed for the harmonization of the links in the hybrid network. For effective maritime search and rescue, Yang et al. [18] deployed UAVs in a cognitive mobile computing network, the communication throughput of which was improved with the help of reinforcement learning techniques.

In general, vessels have fixed shipping lanes [4]. Therefore, UAV-mounted BSs are more promising for on-demand maritime coverage enhancement. However, current research efforts on UAV communications mainly focus on the terrestrial scenario [19, 20]. Among the state-of-the-art research, Sun et al. [21] presented an optimal 3D aerial trajectory design and wireless resource allocation strategies for solar-powered UAV communication systems. Cai et al. [22] focused on the joint trajectory design and resource allocation problem for downlink energy-efficient UAV communication systems with eavesdroppers, in which a series of interesting insights were obtained for secure UAV communications. While maritime UAVs face some similar challenges to the terrestrial case, e.g., limited on-board energy, which should be elaborately scheduled [22, 23, 24], and complicated cooperation pattern [25, 26], they have unique challenges. On the one hand, much more harsh maritime environments require more robust and stronger UAVs, e.g., the oil-powered fixed-wing UAV [7]. On the other hand, the interaction between UAVs and other infrastructures becomes a touchy issue. Above the vast ocean, UAVs rely on on-shore BSs or vessel-based BSs for efficient backhaul, and rely on satellites for control signaling. This renders the hybrid network no longer a basic three-node relay model [27, 28]. A hierarchical dynamic model is more suitable to characterize it, which however remains unveiled so far.

In a nutshell, the research on maritime deployable infrastructures is still in its beginning stage, and it is still an open problem to effectively integrate the fixed and deployable infrastructures for maritime coverage enhancement.

We consider a hybrid satellite-UAV-terrestrial MCN with practical constraints. The system consists of a satellite for global signaling coverage over the target area, an on-shore BS, multiple UAVs and multiple vessels. Among all the vessels, some act as deployable BSs and provide communication services for the rest. For the blind hole areas which cannot be reached by either the on-shore BS or the vessel-based BSs, UAVs are dispatched for coverage. This hybrid network contains shore-to-vessel (S2V), shore-to-UAV (S2U), vessel-to-UAV (V2U), UAV-to-UAV (U2U), UAV-to-vessel (U2V), and vessel-to-vessel (V2V) links. Our design objective is to minimize the total energy consumption of the entire network by coordinately orchestrating all these links across a certain service period, while guaranteeing the quality of service (QoS) requirements of all users.

In this hybrid network, all maritime UAVs should keep away from extremely harsh environmental conditions, and most vessels follow fixed shipping lanes for collision prevention. These facts render it impossible to arbitrarily deploy the so-called deployable infrastructures. To fully exploit their benefits with these constraints, we should establish close cooperation among all these fixed and deployable infrastructures, making them relying heavily on each other. The hybrid network is thus irregular and indecomposable in general, which is the most important difference between it and existing studies. In this situation, the coupling relationship between the backhaul and fronthaul links of one deployable BS should be carefully satisfied. Otherwise, this BS would turn into a bottleneck of the whole network, leading to wide-band coverage holes. Besides, it becomes challenging to acquire full CSI for resource orchestration, due to limited system overheads, which have already been mostly occupied for handling the irregularity and dynamic coupling of the network.

The main contributions of this paper are summarized as follows.

• •

  We establish a hierarchical framework for energy-efficient maritime coverage enhancement, by utilizing satellites for global signaling, on-shore BSs for sending source data, UAVs for on-demand filling of the blind spots of coverage, and some vessels for opportunistically relaying data. All these components are orchestrated in a process-oriented manner, by exploiting extrinsic information including the pre-designed trajectories of UAVs and the pre-planned shipping lanes of vessels. This framework may provide an enlightening case for efficiently and agilely integrating space-air-ground-sea fixed and deployable infrastructures.

• •

  Under this framework, we mathematically formulate a joint link scheduling and rate adaptation problem, to minimize the energy consumption of the whole hybrid network with QoS guarantees. The optimization problem uses the slowly-varying large-scale CSI only, which can be accurately predicted according to the position information of UAVs and vessels, under the practical composite channel models. The problem is shown to be an NP-hard mixed integer nonlinear programming (MINLP) problem with a group of hidden non-linear equality constraints.

• •

  We propose an efficient iterative solution to the problem, by leveraging the relaxation and gradually approaching method based on the gentlest ascent principle, as well as the Min-Max transformation. Accordingly, an efficient process-oriented joint link scheduling and rate adaptation scheme is proposed, which has a polynomial computation complexity, and thus is viable for resource-limited practical applications. Moreover, simulation results show that it can achieve a prominent performance close to the optimal solution. This corroborates the effectiveness of process-oriented resource orchestration under the proposed framework.

Note that the optimization of UAV trajectories is not included in our work for the time being, although it is rather critical [17, 21, 22, 23, 24, 25, 26]. According to the divide-and-conquer principle, we tend to solve the resource orchestration problem first, paving the way for joint trajectory design and resource orchestration. This idea is to some extent necessary, as the optimization of UAV trajectories will further complicate the resource orchestration problem, which itself is already found NP-hard under the considered practical conditions. Nevertheless, on the basis of some pioneering related works [21, 22, 26], we will try to take the joint optimization problem into account in our future work, so as to uncover its appealing potential gains in the maritime scenario.

The rest of this paper is organized as follows. Section II introduces the system model. In Section III, the joint link scheduling and rate adaptation problem is formulated to minimize the total energy consumption and an efficient process-oriented suboptimal solution is proposed. In Section IV, simulation results are presented with further discussions. Finally, concluding remarks are given in Section V.

We denote the link from transmitter $i\in\left\{{0,1,...,I+J^{\prime}}\right\}$ to receiver $j\in\left\{{1,...,I+J}\right\}$ at time slot $t$ by $i\to j@t$. Let $\delta_{i,j,t}\in\left\{{0,1}\right\},i\neq j$, denote the scheduling indicator, where ${{\delta_{i,j,t}}}=1$ means the link between transmitter $i$ to receiver $j$ is active at time slot $t$ on an allocated subcarrier, while ${{\delta_{i,j,t}}}=0$ means the link is idle. Note that the subcarrier identifier $n,n=1,...,N$, does not appear in the subscript of ${{\delta_{i,j,t}}}$. This is because the large-scale fading is assumed to be the same on different subcarriers for each link $i\to j@t$, and it is not necessary to distinguish the specific identifier of the subcarrier allocated to a link. Since the total number of subcarriers is $N$, we have⁴⁴4For simplicity, $i\neq j$ is omitted in (4) as well as all subsequent expressions.

$\displaystyle{}\sum\limits_{i=0}^{I+J^{\prime}}{\sum\limits_{j=1}^{I+J}{{{\delta_{i,j,t}}}}}\leq N,~{}~{}t\in\{1,...,T\}.$

(4)

Besides, $\delta_{i,j,t}$ is further constrained by the following inequations for $\forall t$, since all the UAVs and vessels are half-duplex.

		$\displaystyle\sum\limits_{i=0}^{I+J^{\prime}}{{{\delta_{i,j,t}}}}+\sum\limits_{j^{\prime}=1}^{I+J}{{{\delta_{j,j^{\prime},t}}}\leq{1}},~{}j\in\{1,...,I+J^{\prime}\},$		(5a)
		$\displaystyle\sum\limits_{i=0}^{I+J^{\prime}}{{{\delta_{i,j,t}}}}\leq 1,~{}~{}~{}~{}~{}~{}j\in\{I+J^{\prime}+1,...,I+J\}.$		(5b)

Denote the transmit power for link $i\to j@t$ by $p_{i,j,t}$, where $p_{i,j,t}\leq P_{i}$ with $P_{i}$ being the maximum transmit power of transmitter $i$. Then the total energy consumption of the MCN can be written as

$\displaystyle{}{E_{\rm{total}}\left(\{\delta_{i,j,t}\},\{p_{i,j,t}\}\right)=\sum\limits_{t=1}^{T}{{\sum\limits_{i=0}^{I+J^{\prime}}{\sum\limits_{j=1}^{I+J}{{p_{i,j,t}}\delta_{i,j,t}}}\Delta\tau}}}.$

(6)

When the large-scale CSI, i.e., $\beta_{i,i,t},\forall i,j,t$, is available, the transmission rate of link $i\to j@t$ can be derived as

$\displaystyle{}{r_{i,j,t}}$

$\displaystyle={{B_{s}}\mathbf{E}~{}{{\log}_{2}}\left({1+\frac{{{p_{i,j,t}}{\beta_{i,j,t}}{{\left|{{h_{i,j,t}}}\right|}^{2}}}}{{{\sigma^{2}}}}}\right)},$

(7)

where $\mathbf{E}$ denotes the expectation operator with respect to the unknown small-scale fading $h_{i,j,t}$, and $\sigma^{2}$ is the power of additive white Gaussian noise. Based on the random matrix theory, ${r_{i,j,t}}$ can be accurately approximated by [32]

	$\displaystyle{}r_{i,j,t}\approx$	$\displaystyle{B_{s}}\log_{2}\left(1+\frac{\beta_{i,j,t}p_{i,j,t}W_{i,j,t}^{-1}}{\sigma^{2}}\right)+B_{s}\log_{2}(W_{i,j,t})$
		$\displaystyle-B_{s}\log_{2}(e)\left(1-W_{i,j,t}^{-1}\right),$		(8)

with $W_{i,j,t}$ satisfying

$\displaystyle{}W_{i,j,t}=1+\frac{\beta_{i,j,t}p_{i,j,t}}{\sigma^{2}+\beta_{i,j,t}p_{i,j,t}W_{i,j,t}^{-1}}.$

(9)

In our considered network, the UAVs $i=1,...,I$, and vessels $i=I+1,...,I+J^{\prime}$, may work as either transmitter or receiver in a certain slot $t$, depending on the link scheduling result. On the contrary, vessel $i$, $i\in\{I+J^{\prime}+1,...,I+J\}$, only receives its own demanded data, and does not transmit to the others. Suppose that at the end of the $t$-th slot, UAV or vessel $j$ has a total data volume of $V_{j,t}$. Then $V_{j,t}$ is given by

$${}V_{j,t}=\left\{\begin{aligned} &\sum\limits_{i=0}^{I+J^{\prime}}{{r_{i,j,t}\delta_{i,j,t}}}\Delta\tau,~{}~{}~{}t=1,\forall j,\\ &\sum\limits_{\tau=1}^{t}{\left({\sum\limits_{i=0}^{I+J^{\prime}}{{r_{i,j,\tau}\delta_{i,j,\tau}}}-\sum\limits_{j^{\prime}=1}^{I+J}{{r_{j,j^{\prime},\tau}\delta_{j,j^{\prime},\tau}}}}\right)\Delta\tau},\\ &~{}~{}~{}~{}~{}~{}2\leq t\leq T,1\leq j\leq I+J^{\prime},\\ &\sum\limits_{\tau=1}^{t}{\sum\limits_{i=0}^{I+J^{\prime}}{{r_{i,j,\tau}\delta_{i,j,\tau}}}}\Delta\tau,\\ &~{}~{}~{}~{}~{}~{}2\leq t\leq T,I+J^{\prime}+1\leq j\leq I+J.\end{aligned}\right.$$

(10)

In order to ensure the causality of data forwarding in the network, the data that UAV or vessel $j$, $j\in\{1,...,I+J^{\prime}\}$, transmits at time slot $t+1$ should be no more than that it has at the end of time slot $t$, i.e.,

		$\displaystyle{V_{j,t}}\geq\sum\limits_{j^{\prime}=1}^{I+J}{{r_{j,j^{\prime},t+1}\delta_{j,j^{\prime},t+1}}}\Delta\tau,$		(11)
		$\displaystyle j\in\{1,...,I+J^{\prime}\},t\in\{0,...,T-1\}.$

Note that $V_{j,0}$ refers to the data volume that UAV or vessel $j$ has at the start of time slot $t=1$, and it satisfies

$\displaystyle{}V_{j,0}=0,j\in\{1,...,I+J\}.$

(12)

It can be inferred from (11) that

	$\displaystyle{}\delta_{j,j^{\prime},1}=0,j\in\{1,...,I+J^{\prime}\},j^{\prime}\in\{1,...,I+J\},$		(13a)
	$\displaystyle r_{j,j^{\prime},1}=0,j\in\{1,...,I+J^{\prime}\},j^{\prime}\in\{1,...,I+J\}.$		(13b)

Furthermore, to satisfy the QoS guarantees for the vessels, it is desired that

$\displaystyle{}V_{j,t}|_{t\geq t_{j}^{\rm{QoS}}}\geq V_{j}^{\rm{QoS}},j\in\{I+1,...,I+J\}.$

(14)

Based on (III-A), $p_{i,j,t}$ can be expressed as a function of $r_{i,j,t}$, i.e.,

$\displaystyle{}p_{i,j,t}=\frac{\sigma^{2}}{\beta_{i,j,t}}\left(2^{\frac{1}{B_{s}}r_{i,j,t}+\log_{2}(e)(1-W_{i,j,t}^{-1})}-W_{i,j,t}\right).$

(15)

Thus, the total energy consumption $E_{\rm{total}}\left(\{\delta_{i,j,t}\},\{p_{i,j,t}\}\right)$ can be rewritten as $E_{\rm{total}}\left(\{\delta_{i,j,t}\},\{r_{i,j,t}\}\right)$, which is shown in (16).

Accordingly, the joint link scheduling and rate adaptation problem aiming to minimize the network energy consumption can be formulated as

		$\displaystyle\!\!\!\!\!\!\!\!\!\!\!\!\mathop{\min}\limits_{{\left\{{{\delta_{i,j,t}}}\right\},\{r_{i,j,t}\}}}{E_{\rm{total}}\left(\{\delta_{i,j,t}\},\{r_{i,j,t}\}\right)}$		(17a)
	$\displaystyle{s.t.}\;\;$	$\displaystyle S^{\delta}_{j,t}\leq 1,~{}~{}1\leq j\leq I+J,1\leq t\leq T,$		(17b)
		$\displaystyle\sum\limits_{i=0}^{I+J^{\prime}}{\sum\limits_{j=1}^{I+J}{{{\delta_{i,j,t}}}}}\leq N,~{}~{}1\leq t\leq T,$		(17c)
		$\displaystyle\left.{{V_{j,t}}}\right|_{t\geq t_{j}^{{\rm{QoS}}}}\geq V_{j}^{\rm{QoS}},~{}~{}I+1\leq j\leq I+J,$		(17d)
		$\displaystyle~{}{V_{j,t}}\geq\sum\limits_{j^{\prime}=1}^{I+J}{{r_{j,j^{\prime},t+1}\delta_{j,j^{\prime},t+1}}}\Delta\tau,$		(17e)
		$\displaystyle~{}1\leq j\leq I+J^{\prime},0\leq t\leq T-1,$
		$\displaystyle~{}0\leq r_{i,j,t}\leq R_{i,j,t},\forall i,j,t,$		(17f)
		$\displaystyle~{}\delta_{i,j,t}\in\left\{{0,1}\right\},\forall i,j,t,$		(17g)
		$\displaystyle~{}W_{i,j,t}=1+\frac{\beta_{i,j,t}p_{i,j,t}}{\sigma^{2}+\beta_{i,j,t}p_{i,j,t}W_{i,j,t}^{-1}},\forall i,j,t,$		(17h)

in which

$${}S^{\delta}_{j,t}=\left\{\begin{aligned} &\sum\limits_{i=0}^{I+J^{\prime}}{{{\delta_{i,j,t}}}}+\sum\limits_{j^{\prime}=1}^{I+J}{{{\delta_{j,j^{\prime},t}}}},~{}~{}j\in\{1,...,I+J^{\prime}\},\\ &\sum\limits_{i=0}^{I+J^{\prime}}{{{\delta_{i,j,t}}}},~{}~{}j\in\{I+J^{\prime}+1,...,I+J\},\end{aligned}\right.$$

(18)

and

$\displaystyle{}{R_{i,j,t}}={{B_{s}}\mathbf{E}~{}{{\log}_{2}}\left({1+\frac{{{P_{i}}{\beta_{i,j,t}}{{\left|{{h_{i,j,t}}}\right|}^{2}}}}{{{\sigma^{2}}}}}\right)}.$

(19)

It can be inferred from (17) that with the joint link scheduling and rate adaptation optimization, the resultant energy consumption of the UAVs and that of the on-shore BS and the vessels will be mainly decided by the qualities of the links. To tackle the irregularity and dynamic coupling of the network, we target at minimizing the total energy consumption with QoS guarantees. In some extreme cases, this may lead to a violation of the on-board energy constraints of some UAVs [22, 23, 24]. To eliminate this risk, one somewhat coarse but effective approach is to adjust the maximum number of active links where the UAVs with limited on-board energy act as transmitters. Concretely, when there is a limitation, i.e., $\bar{E}_{\bar{j}}$, on the energy consumption for UAV $\bar{j},1\leq\bar{j}\leq I$, within the service period, an extra constraint $\sum_{t=1}^{T}\sum_{j^{\prime}=1}^{I+J}\delta_{\bar{j},j^{\prime},t}\leq\bar{E}_{\bar{j}}/P_{\bar{j}}$ could be added to (17). In the following, it will be seen that the extra constraint makes no difference to the derivations of the proposed scheme. Nevertheless, more elaborate approaches for incorporating the energy limitation of UAVs could be further explored in the future work.

To solve the problem in (17), we are confronted with two challenges. First, (17) is a MINLP problem, which is NP-hard according to [33]. Second, the closed-form approximation for $r_{i,j,t}$ in (III-A) brings a group of hidden non-linear equality constraints on the auxiliary variables $W_{i,j,t}$ and $r_{i,j,t}$, as shown in (17h).

In the folllowing, we analyze (17) in allusion to these two challenges, and try to pave the way to a suboptimal but efficient solution. Specifically, the relationship between $r_{i,j,t}$ and $\delta_{i,j,t}$ and that between $r_{i,j,t}$ and $W_{i,j,t}$ are analyzed and utilized. According to the analysis, we show that the integer scheduling indicators $\{\delta_{i,j,t}\}$ are able to be effectively processed with a merging and detaching strategy based on a process-oriented relaxation and gradually-approaching method, and the non-linear equality constraints on $W_{i,j,t}$ can be delicately circumvented through a Min-Max transformation of the problem.

1) Relaxation and gradually approaching

Note that $r_{i,j,t}$ and $\delta_{i,j,t}$ are closely related in the solutions for (17). For $\forall i,j,t$, the relation is described as

	$\displaystyle r_{i,j,t}=0\leftrightarrow\delta_{i,j,t}=0,$		(20a)
	$\displaystyle r_{i,j,t}>0\leftrightarrow\delta_{i,j,t}=1.$		(20b)

It means that if the scheduling indicator $\delta_{i,j,t}$ is $0$/$1$, i.e., the link $i\to j@t$ is set to be inactive/active, then the transmission rate on that link must be allocated a zero/non-zero value, and vise versa. Based on this observation, $\delta_{i,j,t}$ can be relaxed by being merged into $r_{i,j,t}$. The new problem after relaxation can be expressed as

		$\displaystyle\!\!\!\!\!\!\!\!\!\!\!\!\mathop{\min}\limits_{{\{r_{i,j,t}\}}}{\tilde{E}_{\rm{total}}\left(\{r_{i,j,t}\}\right)}$		(21a)
	$\displaystyle{s.t.}\;\;$	$\displaystyle S^{r}_{j,t}\leq 1,~{}~{}1\leq j\leq I+J,1\leq t\leq T,$		(21b)
		$\displaystyle\sum\limits_{i=0}^{I+J^{\prime}}{\sum\limits_{j=1}^{I+J}{\frac{{r_{i,j,t}}}{R_{i,j,t}}}}\leq N,~{}~{}1\leq t\leq T,$		(21c)
		$\displaystyle\left.{{\tilde{V}_{j,t}}}\right|_{t\geq t_{j}^{{\rm{QoS}}}}\geq V_{j}^{\rm{QoS}},~{}~{}I+1\leq j\leq I+J,$		(21d)
		$\displaystyle~{}{\tilde{V}_{j,t}}\geq\sum\limits_{j^{\prime}=1}^{I+J}{{r_{j,j^{\prime},t+1}}}\Delta\tau,$		(21e)
		$\displaystyle~{}1\leq j\leq I+J^{\prime},0\leq t\leq T-1,$
		$\displaystyle~{}0\leq r_{i,j,t}\leq R_{i,j,t},\forall i,j,t,$		(21f)
		$\displaystyle~{}W_{i,j,t}=1+\frac{\beta_{i,j,t}p_{i,j,t}}{\sigma^{2}+\beta_{i,j,t}p_{i,j,t}W_{i,j,t}^{-1}},\forall i,j,t,$		(21g)

where $\tilde{E}_{\rm{total}}\left(\{r_{i,j,t}\}\right)$ is shown in (22),

and

$${}S^{r}_{j,t}=\left\{\begin{aligned} &\sum\limits_{i=0}^{I+J^{\prime}}{\frac{r_{i,j,t}}{R_{i,j,t}}}+\sum\limits_{j^{\prime}=1}^{I+J}{\frac{r_{j,j^{\prime},t}}{R_{j,j^{\prime},t}}},~{}~{}j\in\{1,...,I+J^{\prime}\},\\ &\sum\limits_{i=0}^{I+J^{\prime}}{\frac{r_{i,j,t}}{R_{i,j,t}}},~{}~{}j\in\{I+J^{\prime}+1,...,I+J\},\end{aligned}\right.$$

(23)

$${}\tilde{V}_{j,t}=\left\{\begin{aligned} &\sum\limits_{i=0}^{I+J^{\prime}}{{r_{i,j,t}}}\Delta\tau,~{}~{}~{}t=1,\forall j,\\ &\sum\limits_{\tau=1}^{t}{\left({\sum\limits_{i=0}^{I+J^{\prime}}{{r_{i,j,\tau}}}-\sum\limits_{j^{\prime}=1}^{I+J}{{r_{j,j^{\prime},\tau}}}}\right)\Delta\tau},\\ &~{}~{}~{}~{}~{}~{}2\leq t\leq T,1\leq j\leq I+J^{\prime},\\ &\sum\limits_{\tau=1}^{t}{\sum\limits_{i=0}^{I+J^{\prime}}{{r_{i,j,\tau}}}}\Delta\tau,\\ &~{}~{}~{}~{}~{}~{}2\leq t\leq T,I+J^{\prime}+1\leq j\leq I+J.\end{aligned}\right.$$

(24)

Note that as compared to the original problem (17), the constraints (17b) and (17c) are now transformed into (21b) and (21c), respectively, where the original constraints on $\delta_{i,j,t}$ is now implicitly expressed in terms of $r_{i,j,t}$ via the relations described in (20).

Denote an optimal solution for (21) as $\{\tilde{r}_{i,j,t}\}$, and then the corresponding scheduling indicators, i.e., $\{\tilde{\delta}_{i,j,t}\}$, can be detached from $\{\tilde{r}_{i,j,t}\}$ according to (20). Because of relaxation, the obtained $\{\tilde{\delta}_{i,j,t}\}$ might be not able to satisfy the original constraints described in (17b) and (17c), as $\{\tilde{r}_{i,j,t}\}$ and $\{\tilde{\delta}_{i,j,t}\}$ are found from a larger solution space. However, it can be inferred that $\{\tilde{\delta}_{i,j,t}\}$ indicates the links with the best qualities in the network. Thus, we may approach a solution for the original problem in (17) based on $\{\tilde{r}_{i,j,t}\}$ and $\{\tilde{\delta}_{i,j,t}\}$, through gradually lessening the violations. This can be achieved by shrinking the solution space of the problem (21) gradually, referring to that of (17), with the help of $\{\tilde{r}_{i,j,t}\}$ and $\{\tilde{\delta}_{i,j,t}\}$.

To this end, we develop a process-oriented relaxation and gradually-approaching method for the original problem (17) in the following. Specifically, we first check the constraints in (17b) and (17c) with $\{\tilde{\delta}_{i,j,t}\}$ and find those that are violated. Then, a smaller solution space is derived for (21) based on the gentlest-ascent principle, in which the total energy consumption of the network always ascends the slowest. Lastly, we update $\{\tilde{r}_{i,j,t}\}$ and $\{\tilde{\delta}_{i,j,t}\}$ within the obtained smaller solution space, aiming to lessen the violations of the constraints in (17b) and (17c). The above operations are carried out iteratively, until all the constraints in (17b) and (17c) are satisfied.

Firstly, based on $\{\tilde{\delta}_{i,j,t}\}$, we determine the violated constraints in (17b) and (17c), and find all non-zero $\tilde{\delta}_{i,j,t}$ involved in the violated constraints. For $t=1,...,T$ and $x=1,2$, define

$\displaystyle{}\mathfrak{\Delta}_{t,x}=\{(i^{(t,x)}_{m},j^{(t,x)}_{m},t)|m=1,...,M_{t,x}\},$

(25)

where $(i^{(t,x)}_{m},j^{(t,x)}_{m},t)$ satisfies $\tilde{\delta}_{i^{(t,x)}_{m},j^{(t)}_{m},t}=1$, and $\tilde{\delta}_{i^{(t,x)}_{m},j^{(t,x)}_{m},t}$ is involved in at least one of the violated constraints in (17b) for $x=1$ or (17c) for $x=2$. By $\mathfrak{\Delta}_{t,1}$, $t=1,...,T$, and $\mathfrak{\Delta}_{t,2}$, $t=1,...,T$, the conflicting links $i\to j@t$ with respect to the half-duplex mode of the UAVs and vessels, and those with respect to the constraint of the total number of available subcarriers, are respectively identified and grouped according to the time slot division. It can be inferred that

$\displaystyle{}\!\!\!M_{t,x}\leq(I+J)^{2}.$

(26)

Note that $\mathfrak{\Delta}_{t,x},t=1,...,T$, are closely related due to the sequential characteristics of the data streaming on the links across the time slots $1$ to $T$. The definition of $\mathfrak{\Delta}_{t,x}$, $t=1,...,T$, $x=1,2$, forms a basis for the shrinking of the solution space of the relaxed problem (21) towards that of the original problem (17) following a process-oriented rule.

Secondly, with $\mathfrak{\Delta}_{t,x}$,$t=1,...,T$, $x=1,2$, we find a smaller solution space for the relaxed problem (21) based on the gentlest-ascent principle following a process-oriented rule. To do this, we form $\bar{M}_{x}$ sets, i.e., $\bar{\mathfrak{\Delta}}_{x,\bar{m}},\bar{m}=1,...,\bar{M}_{x}$, based on $\mathfrak{\Delta}_{t,x},t=1,...,T$, following a process-oriented rule, respectively for $x=1,2$. The specific process-oriented rule is delicately designed and the details are illustrated in Subsection C. Specially, for the process-oriented feature, $\bar{\mathfrak{\Delta}}_{x,\bar{m}}$ satisfies

$\displaystyle{}|\bar{\mathfrak{\Delta}}_{x,\bar{m}}\cap\mathfrak{\Delta}_{t,x}|\geq 1,$

(27)

for all non-empty $\mathfrak{\Delta}_{t,x},t=1,...,T$. For each of the sets $\bar{\mathfrak{\Delta}}_{x,\bar{m}},\bar{m}=1,...,\bar{M}_{x},x=1,2$, let $\{\tilde{r}^{(x,\bar{m})}_{i,j,t}\}$ denotes an optimal solution to the problem in (21) with a group of extra constraints

$\displaystyle{}r_{i,j,t}=0,~{}~{}(i,j,t)\in\bar{\mathfrak{\Delta}}_{x,\bar{m}},$

(28)

which can be written as

		$\displaystyle\!\!\!\!\!\!\!\!\!\!\!\!\mathop{\min}\limits_{{\{r_{i,j,t}\}}}{\tilde{E}_{\rm{total}}\left(\{r_{i,j,t}\}\right)}$		(29a)
	$\displaystyle{s.t.}\;\;$	$\displaystyle S^{r}_{j,t}\leq 1,~{}~{}1\leq j\leq I+J,1\leq t\leq T,$		(29b)
		$\displaystyle\sum\limits_{i=0}^{I+J^{\prime}}{\sum\limits_{j=1}^{I+J}{\frac{{r_{i,j,t}}}{R_{i,j,t}}}}\leq N,~{}~{}1\leq t\leq T,$		(29c)
		$\displaystyle\left.{{\tilde{V}_{j,t}}}\right|_{t\geq t_{j}^{{\rm{QoS}}}}\geq V_{j}^{\rm{QoS}},~{}~{}I+1\leq j\leq I+J,$		(29d)
		$\displaystyle~{}{\tilde{V}_{j,t}}\geq\sum\limits_{j^{\prime}=1}^{I+J}{{r_{j,j^{\prime},t+1}}}\Delta\tau,$		(29e)
		$\displaystyle~{}1\leq j\leq I+J^{\prime},0\leq t\leq T-1,$
		$\displaystyle~{}0\leq r_{i,j,t}\leq R_{i,j,t},\forall i,j,t,$		(29f)
		$\displaystyle~{}W_{i,j,t}=1+\frac{\beta_{i,j,t}p_{i,j,t}}{\sigma^{2}+\beta_{i,j,t}p_{i,j,t}W_{i,j,t}^{-1}},\forall i,j,t,$		(29g)
		$\displaystyle~{}r_{i,j,t}=0,~{}~{}(i,j,t)\in\bar{\mathfrak{\Delta}}_{x,\bar{m}}.$		(29h)

It can be inferred that (29) is with a smaller solution space compared to (21), and

$\displaystyle{}\tilde{E}_{total}(\{\tilde{r}^{(x,\bar{m})}_{i,j,t}\})\geq\tilde{E}_{total}(\{\tilde{r}_{i,j,t}\}).$

(30)

We set

$\displaystyle{}\bar{m}_{x}^{\prime}=\arg\min_{\bar{m}\in\{1,...,\bar{M}_{x}\}}\tilde{E}_{total}(\{\tilde{r}^{(x,\bar{m})}_{i,j,t}\}).$

(31)

Then the group of constraints in (28) with $\bar{\mathfrak{\Delta}}_{x,\bar{m}}=\bar{\mathfrak{\Delta}}_{x,\bar{m}_{x}^{\prime}}$, together with those in (21b)-(21g), define a shrinked solution space for the relaxed problem (21), with which the total energy consumption of the network increases the least compared to the solution spaces formed based on other groups of constraints in (28).

Lastly, derive a new group of $\{\tilde{r}_{i,j,t}\}$ and $\{\tilde{\delta}_{i,j,t}\}$ based on the relaxed problem (21) with the extra group of constraints in (28) with $\bar{\mathfrak{\Delta}}_{x,\bar{m}}=\bar{\mathfrak{\Delta}}_{x,\bar{m}_{x}^{\prime}}$. Note that with the group of extra constraints defined by $\bar{\mathfrak{\Delta}}_{x,\bar{m}_{x}^{\prime}}$, the newly obtained $\{\tilde{r}_{i,j,t}\}$ and $\{\tilde{\delta}_{i,j,t}\}$, i.e., the link scheduling and rate adaptation result, are adjusted across all the time slots $t=1,...,T$ coordinately, i.e., following the process-oriented rule. Further, check the constraints in (17b) and (17c). If any violation is found, then repeat the solution-space-shrinking operation and the updating of $\{\tilde{r}_{i,j,t}\}$ and $\{\tilde{\delta}_{i,j,t}\}$. Otherwise, the new group of $\{\tilde{r}_{i,j,t}\}$ and $\{\tilde{\delta}_{i,j,t}\}$ constitute a solution for the original problem in (17).

2) Min-Max transformation for $W_{i,j,t}$

In this part, we try to tackle the second challenge with problem (17), i.e, the group of hidden non-linear equality constraints in (17h), and find an efficient way to solve the relaxed problem in (21). Fortunately and interestingly, it is found that (21) can be transformed into a saddle-point problem for a convex-concave function with a group of linear inequality constraints

Define $f\left(\{r_{i,j,t}\},\{z_{i,j,t}\}\right)$ as shown in (32).

The following Theorem 1 shows that the non-linear equality constraints on $W_{i,j,t}$ and $r_{i,j,t}$, $\forall i,j,t$, in (17h) and further (21g) can be absorbed through a delicate Min-Max transformation of the problem.

Based on Theorem 1, the problem in (21) can be equivalently recast as the following Min-Max problem

		$\displaystyle\!\!\!\!\!\!\!\!\!\!\!\!\mathop{\min}\limits_{{\{r_{i,j,t}\}}}\max_{\{z_{i,j,t}\}}{f\left(\{r_{i,j,t}\},\{z_{i,j,t}\}\right)}$		(34a)
	$\displaystyle{s.t.}\;\;$	$\displaystyle S^{r}_{j,t}\leq 1,~{}~{}1\leq j\leq I+J,1\leq t\leq T,$		(34b)
		$\displaystyle\sum\limits_{i=0}^{I+J^{\prime}}{\sum\limits_{j=1}^{I+J}{\frac{{r_{i,j,t}}}{R_{i,j,t}}}}\leq N,~{}~{}1\leq t\leq T,$		(34c)
		$\displaystyle\left.{{\tilde{V}_{j,t}}}\right|_{t\geq t_{j}^{{\rm{QoS}}}}\geq V_{j}^{\rm{QoS}},~{}~{}I+1\leq j\leq I+J,$		(34d)
		$\displaystyle~{}{\tilde{V}_{j,t}}\geq\sum\limits_{j^{\prime}=1}^{I+J}{{r_{j,j^{\prime},t+1}}}\Delta\tau,$		(34e)
		$\displaystyle~{}1\leq j\leq I+J^{\prime},0\leq t\leq T-1,$
		$\displaystyle~{}0\leq r_{i,j,t}\leq R_{i,j,t},\forall i,j,t,$		(34f)
		$\displaystyle~{}z_{i,j,t}\geq 1,\forall i,j,t.$		(34g)

With a convex-concave objective function and a group of linear inequality constraints, (34) can be solved via computations with a polynomial complexity [34, 35, 36]. Its optimal solution is a saddle point of $f\left(\{r_{i,j,t}\},\{z_{i,j,t}\}\right)$ within the convex set determined by the constraints (34b)-(34g). Accordingly, an optimal solution can be obtained for the problem in (21).