Efficient User Scheduling for Uplink Hybrid Satellite-Terrestrial Communication

We study the hybrid satellite-terrestrial model with either instantaneous channel state information (CSI) or channel distribution information (CDI) available at the terrestrial station and the satellite. When instantaneous CSI is available, the terrestrial station is informed of the exact channel fading levels of each user, and the satellite is informed of the exact fading level from the terrestrial station. When CDI is available, the terrestrial and the satellite are only provided with the distribution of respective fading models. We study user scheduling algorithms for both cases. Our contributions are summarized as follows.

When instantaneous CSI is available, combining capacity results for the multiple access channel and the relay channel [15], we derive the optimal instantaneous achievable rate region of all ground users. Subsequently, under a homogeneous target rate constraint, we formulate an optimization problem to maximize the achievable sum rate via user scheduling algorithms. The optimal solution requires an exhaustive search and is too complicated for practical use. As a compromise, we first derive theoretical upper and lower bounds on the maximum achievable rate and then propose low-complexity scheduling algorithms. In particular, we propose a greedy algorithm that achieves close-to-optimal performance and a further simplified sub-optimal algorithm that has almost linear complexity. The efficiency, computational complexity and stability of our scheduling algorithms are analytically demonstrated and numerically verified.

When CDI is available, the instantaneous achievable rate region can not be obtained. Instead, under a homogeneous target rate constraint for all ground users, we derive the outage probability of the uplink communication as a function of the rate constraint and CDI. Subsequently, we formulate an optimization problem to minimize the outage probability and derive a theoretical lower bound that serves as the benchmark. Furthermore, to obtain a feasible solution to the optimization problem, we propose a user scheduling algorithm using the idea of alternative optimization (AO) [16, 17]. Via numerical simulations, we find that the outage probability obtained from our user scheduling algorithm converges to our derived benchmark after a small number of iterations. We also numerically illustrate the optimality and computational complexity of our scheduling algorithm by comparing with the optimal exhaustive search method.

The study on hybrid satellite-terrestrial communication systems has a long history. In contrast to our setting, most papers focused on the downlink model, where a satellite transmits messages to a group of ground users, e.g., [18, 19, 20, 21, 22]. In [18], for a multiuser hybrid AF satellite-terrestrial cooperative network, Yuan et al. proposed an opportunistic user scheduling algorithm using signal-to-noise ratio (SNR)-threshold based feedback. In [19], for a multiuser AF hybrid satellite-terrestrial relay network with opportunistic scheduling, Kang et al. derived the analytical bounds on the ergodic capacity. For a multiuser satellite-terrestrial downlink model with a multi-antenna satellite and a single-antenna AF relay, Bankey and Upadhyay [20] analyzed the ergodic capacity for opportunistic user scheduling with outdated CSI. However, the spectrum efficiency of the orthogonal opportunistic user scheduling algorithms of the above studies is very low since only one user is allowed to access the channel at a time slot. To improve the throughput and spectrum efficiency of the downlink hybrid system, subsequent works apply non-orthogonal multiple access (NOMA) into hybrid satellite-terrestrial systems to support multiple users simultaneously in a time slot, e.g., [21, 22]. However, studies on downlink NOMA-based integrated terrestrial-satellite network are significantly different from our uplink analysis in this paper.

The more related works to ours is the studies of the uplink hybrid satellite-terrestrial system, e.g., [23, 24, 25]. In [23], Yang et al. derived an upper bound on the ergodic capacity for a multi-beam geostationary earth orbit mobile satellite communication system. In [24], Huang et al. proposed a space division multiple access (SDMA) scheme to maximize the average sum rate of a hybrid satellite-terrestrial AF relaying network, where a high-altitude platform is deployed as a relay to assist the transmission from ground users to the satellite. In [25], Arti studied a two-way AF satellite system with only two ground users and one terrestrial relay and designed beamforming and combining vectors for the satellite.

However, none of the above works use Shannon theory [26] to study the critical problem of efficient user scheduling algorithms to achieve the full potential of the uplink hybrid satellite-terrestrial system. Although above works considered multiple antennas, the analysis is mostly achievable without optimality guarantee. Specifically, these studies used dimensional advantage of multiple antennas to improve the throughout with SDMA or a certain beamforming design. Note that the capacity is the maximal rate achievable of any communication scheme and analysis based on specific coding scheme without optimality guarantee is far from satisfactory. In this paper, to complement the existing literature in the uplink hybrid satellite-terrestrial system, we use information theoretical results to study efficient user scheduling algorithms and demonstrate close-to-optimality performance of our proposed algorithms. For simplicity, we present results for the single antenna terminals in this paper. Our results can be generalized to the multi antenna terminals by using corresponding information theoretical results for the multiple input and multiple out channels [27, 28].

We use $\mathbb{R}$, $\mathbb{R}_{+}$ and $\mathbb{N}$ to denote the set of real numbers, positive numbers and integers respectively. Denote by $\mathcal{A}\setminus\mathcal{B}$ the minus between set $\mathcal{A}$ and $\mathcal{B}$. For any $x\in\mathbb{R}$, we use $\lfloor x\rfloor$ to denote the maximum integer that is less than or equal to $x$. For any $(a,b)\in\mathbb{N}^{2}$, we use $[a:b]$ to denote the set of integers between $a$ and $b$ and use $[a]$ to denote $[1:a]$. Furthermore, for any two integers $(a,b)\in\mathbb{N}^{2}$ such that $a<b$, denote by $[b]_{a}$ the set of vectors that contain exactly $a$ unique elements of $[b]$ and by $\mathcal{F}(a,b)$ the set of bijective mappings from $[b]_{a}$ to $[b]_{a}$.

We consider an uplink model for the hybrid satellite-terrestrial communication system as shown in Fig. 1. There are $N$ ground users with indices $\mathcal{N}=[N]$, one terrestrial relay, and one satellite, all assumed to have a single antenna. Each user wishes to transmit messages to the satellite with the assist of the relay. Since the resource of the satellite is finite, we assume that at most $K$ users are allowed to transmit messages in a time slot simultaneously. Let $\mathbf{u}=\{u_{1},\ldots,u_{K}\}\in[N]_{K}$ denote the vector of the indices of the selected users by a scheduling algorithm.

At each time slot, after user scheduling, the communication between the selected $K$ users and the satellite proceeds in the following two phases. In the first phase, for each $k\in[K]$, the selected user $u_{k}$ aims to send a message $M_{u_{k}}\in[1:2^{nR_{u_{k}}}]$ to the relay with power $P_{1}$, rate $R_{u_{k}}$ and blocklength $n$. Each message $M_{u_{k}}$ is then encoded into a length-$n$ codeword $X_{u_{k}}^{n}$. The received signal at the terrestrial relay is

where $h_{u_{k}}$ is the channel fading coefficient between the user $u_{k}$ and the relay, and $Z_{u_{k}}^{n}$ is the independent additive white Gaussian noise (AWGN) with zero mean and unit variance. Using $Y_{\mathrm{R}}^{n}$ and CSI for all $K$ users, the terrestrial relay decodes the messages of each user as $\{\tilde{M}_{u_{k}}\}_{k\in[K]}$. In the second phase, the relay encodes its decoded messages $\{\tilde{M}_{u_{k}}\}_{k\in[K]}$ into a combined codeword $X_{\mathrm{R}}^{n}$ with power $P_{2}$ and sends it to the satellite. The received signal at the satellite is

where $h_{\mathrm{D},\mathrm{R}}$ is the channel fading coefficient between the relay and the satellite, and $Z_{\mathrm{D},\mathrm{R}}^{n}$ is the independent AWGN with zero mean and unit variance. Finally, using the noisy outputs $Y_{\mathrm{D}}^{n}$ and CSI on the fading coefficient $h_{\mathrm{D},\mathrm{R}}$, the satellite decodes the message $\{\hat{M}_{u_{k}}\}_{k\in[K]}$.

We assume that the channel between each ground user $i\in[N]$ and the terrestrial relay is an AWGN with Rayleigh fading, i.e., the fading coefficient satisfies $h_{i}\sim\mathcal{CN}(0,2\sigma_{i}^{2}\mathbf{I})$. The fading random variables for different ground users are independent. Furthermore, we assume that the channel gain $|h_{\mathrm{D},\mathrm{R}}|$ for the channel from the relay to the satellite follows a Shadowed-Rician (SR) distribution with parameters $(\Omega,b_{0},m_{s})$, i.e., $|h_{\mathrm{D},\mathrm{R}}|\sim\mathrm{SR}(\Omega,b_{0},m_{s})$, where $\Omega$, $b_{0}$ and $m_{s}$ are positive real numbers. Here, $\Omega$ denotes the the average power of the LOS component, $m_{s}$ is the fading order, and $2b_{0}$ represents for the average power of the scattered component.

To evaluate the fundamental limits of the uplink hybrid satellite-terrestrial system, depending on the availability of CSI, we study the instantaneous sum rate as well as the outage probability and formulate corresponding optimization problems to schedule the transmission of ground users. Specifically, we consider the following two cases.

• •

  Case 1: Perfect Instantaneous CSI

  Similar to most existing works, e.g., [29, 30], we assume that perfect CSI of all channels are available. The CSI can be obtained by channel estimation during each transmission time slot via a backhaul channel [21]. In this setting, we derive the achievable instantaneous sum rate and propose efficient user scheduling algorithms to maximize the sum rate.

• •

  Case 2: Statistical CSI

  The assumption of perfect instantaneous CSI can be impractical for practical satellite communication systems. To address this concern, we also study the case where only CDI is available. Specifically, the relay only knows the distribution of fading coefficients for channels from each ground user and the satellite only knows the distribution of the fading coefficient for the channel from the relay. In practical systems, CDI can be estimated via channel parameter estimation methods, e.g., the MUSIC algorothm in [31]. Under this setting, we derive the outage probability and propose user scheduling algorithms to minimize the outage probability.

For each $k\in[K]$, let $S_{u_{k}}:=P_{1}|h_{u_{k}}|^{2}$ denote the received SNR for the channel between user $u_{k}\in[N]$ and the relay and let $S_{\mathrm{D},\mathrm{R}}:=P_{2}|h_{\mathrm{D},\mathrm{R}}|^{2}$ denote the SNR for the channel between the relay and the satellite. Using cut-set bounds for the relay channel and the multiple access channel in [15, Sec. 19.1 and Theorem 19.1], we conclude that given selected users $\mathbf{u}=(u_{1},\ldots,u_{K})$, the instantaneous rate of each user $R_{u_{j}}$ is upper bounded by

where $C(a)=\log(1+a)$ is the capacity of an AWGN channel with SNR $a\in\mathbb{R}_{+}$.

In a full-duplex DF relaying system with perfect CSI, the sum rate upper bound given by (3) can be achieved via block Markov coding and backward decoding ([15, Sec. 16.4.4 and Table 16.2]), when superposition encoding and successive cancellation decoding are used at the relay and the satellite. For subsequent analysis, we consider the case where the rate tuples $\{R_{u_{k}}\}_{k\in[K]}$ lies at a corner point on the rate region and thus maximal sum rate is achieved. In particular, let $\mathbf{u}:=(u_{1},\ldots,u_{K})\in[N]_{K}$ and let $u_{1}\rightarrow u_{2}\rightarrow\ldots\rightarrow u_{K}$ be the decoding order of successive cancellation decoding at the relay, then the signal-to-interference plus noise ratio (SINR) for user $u_{k}$ at the relay satisfies

Since the decoding order of successive cancellation at the satellite can be different from that at the relay, we use a bijective mapping $\Psi\in\mathcal{F}(K,N)$ and the decoding order $\mathbf{u}$ at the relay to describe the decoding order at the satellite. Specifically, for any $k\in[K]$, when $u_{k}$ is the $k$-th decoded message at the relay, then it is the $\Psi(u_{k})$-th decoded message at the satellite. Thus, the decoding order $\mathbf{u}$ and the bijective mapping $\Psi\in\mathcal{F}(K,N)$ suffice to describe the set of selected users and the decoding orders at both the terrestrial station and the satellite. Note that the transmission power $P_{2}$ is split among all $K$ messages and thus the SINR for each message from the relay to the satellite satisfies

where $\alpha_{\Psi(u_{k})}$ is the power splitting ratio of the message from user $u_{k}$ and satisfies $\sum_{k\in[K]}\alpha_{\Psi(u_{k})}=1$. Therefore, given $\mathbf{u}$ and $\Psi$, the instantaneous achievable rate of user $u_{k}$ satisfies

Under the assumption that at most $K$ users are allowed to transmit in a time slot, given a per user rate constraint $R_{k}\in\mathbb{R}_{+}$, we formulate the optimization problem in Problem 1 to maximize the achievable instantaneous sum rate as follows:

The objective function of Problem 1 is the maximum achievable sum rate and we need to optimize over all possible schedule user decoding orders $\mathbf{u}$ at the terrestrial station, all possible decoding orders at the satellite determined by $\mathbf{u}$ and the bijective mapping $\Psi$, all power allocation vectors $(\alpha_{\Psi(u_{1})},\ldots,\alpha_{\Psi(u_{K})})$ at the relay. The first constraint in (8) makes sure that every scheduled user satisfies the rate constraint $R_{\mathrm{target}}$, the second constraint in (9) is the power constraint at the relay to make sure the total transmission power at the relay is $P_{2}$, and the third constraint in (10) guarantees that the decoding order at the relay: $u_{1}\rightarrow u_{2}\rightarrow\ldots\rightarrow u_{K}$ is in the descend order of received SINRs. To solve the problem, we need to jointly optimize the scheduled users $\mathbf{u}$ at the terrestrial station, the decoding order $\{\Psi(u_{k})\}_{k\in[K]}$ at the satellite and power allocation vector $\{\alpha_{\Psi(u_{k})}\}_{k\in[K]}$ at the relay.

We remark that Problem 1 can be decomposed into two sub-problems. This is because $C(\sum_{u_{j}\in\mathcal{U}}S_{u_{j}})$ and $C(S_{\mathrm{D},\mathrm{R}})$ depend on different optimized parameters. Specifically, we have sequential sub-problems Problem 2(a) and Problem 2(b), where Problem 2(b) uses the solution of Problem 2(a) to proceed.

By solving Problem 2(a), we obtain the set of scheduled users and its decoding order $\mathbf{u}$ at the relay that maximizes the sum rates of $K$ users satisfying the rate constraint $R_{\mathrm{target}}$. Given $\mathbf{u}$, we can then solve Problem 2(b) for power allocation at the relay to maximize the achievable rate from the relay to the satellite that satisfies $R_{\mathrm{target}}$ for each scheduled user $u_{k}$. Note that the objective function of Problem 2(b) only depends on the fading coefficient $h_{\mathrm{\mathrm{D},\mathrm{R}}}$ between the satellite and the relay and is thus independent from user scheduling and power allocation strategies.

With the constraint in (15), the power allocation vector $\{\alpha_{\Psi(u_{k})}\}_{k\in[K]}$ satisfies $\frac{\alpha_{\Psi(u_{k})}}{\sum_{i=\Psi(u_{k})+1}^{K}\alpha_{i}+1/S_{\mathrm{D},\mathrm{R}}}\geq 2^{R_{\mathrm{target}}}-1$ for $\Psi(u_{k})\in[K-1]$ and $S_{\mathrm{D},\mathrm{R}}\alpha_{K}\geq 2^{R_{\mathrm{target}}}-1$. Thus, $\alpha_{\Psi(u_{k})}\geq\frac{2^{R_{\mathrm{target}}}-1}{S_{\mathrm{D},\mathrm{R}}}2^{R_{\mathrm{target}}(K-\Psi(u_{k}))}$. Combined with the power constraint that $\sum_{k\in[K]}\alpha_{\Psi(u_{k})}=1$, we conclude that Problem 2(b) is feasible and we can always find a feasible power allocation vector $\{\alpha_{\Psi(u_{k})}\}_{k\in[K]}$ if the number of users supported with rate $R_{\mathrm{target}}$ satisfies

Note that (17) also implies that $S_{\mathrm{D},\mathrm{R}}$ should be larger than $2^{R_{\mathrm{target}}}-1$ to make sure that at least one user can be served with desired rate, i.e., $K\geq 1$.

To obtain an exact solution of Problem 1, we need to use an exhaustive search method over all possible user scheduling $\mathcal{U}\in[N]_{K}$ and find the largest achievable sum rate $R_{\mathrm{sum}}^{*}$. However, such a method is infeasible, especially when the total number of users $N$ is large. As a compromise, we derive closed-form upper and lower bounds on the instantaneous achievable sum rate $R_{\mathrm{sum}}^{*}$, which can be used as benchmarks for low complexity user scheduling algorithms.

We assume that (17) holds so that Problem 2(b) is feasible and the achievable rate between the relay and the satellite is $C(S_{\mathrm{D},\mathrm{R}})$. Then, to bound $R_{\mathrm{sum}}^{*}$, it suffices to derive upper and lower bounds for the optimal value of Problem 2(a). For any decoding order $\mathbf{u}\in[N]_{K}$, let $S_{\mathrm{max}}:=\max_{k\in[N]}S_{k}$ and $S_{\mathrm{min}}:=\min_{k\in[N]}S_{k}$. Furthermore, let $\mathcal{S}=\{S_{i}\}_{i\in[N]}$, given any $a\in\mathbb{R}_{+}$ and any set $\mathcal{A}$, let $\phi(a,\mathcal{A}):=\min_{S_{i}\in\mathcal{A}:S_{i}\geq a}S_{i}$. Finally, given any $R_{\mathrm{target}}\in\mathbb{R}_{+}$, define the following quantities

The proof of Theorem 1 is available in Appendix -A.

To efficiently solve Problem 2(a) with low complexity, we propose a user scheduling algorithm that corresponds to a solution of Problem 2(a) and achieves a near optimal performance of exhaustive search. Specifically, our algorithm proceeds in two phases: given CSI, we first derive the maximum number of users $K$ that can be served by the system and then propose a greedy iterative user scheduling algorithm to select $K$ users to transmit. Details are as follows.

The complexity of the user scheduling scheme in Algorithm 1 is strongly related to the channel qualities of terrestrial users, and also scales polynomially with the total number of users $N$ and scales exponentially with the selected number of users $K$ in the worst case. Such a complexity might still not be feasible for power limited terrestrial stations.

In claim (ii) of Theorem 1, we derive a lower bound on the achievable sum rate using $\{S_{u_{k}}^{\mathrm{lb}}\}_{k\in[K]}$. Inspired by this idea, we propose a lower-bound based user scheduling algorithm (LBUS) by choosing all users to our theoretical derivations $\{S_{u_{k}}^{\mathrm{lb}}\}_{k\in[K]}$ except $u_{K}^{*}$. The user scheduling scheme is summarized in Algorithm 2.

In this section, we present simulation results of our proposed algorithms, i.e., the greedy algorithm GIUS and the lower complexity algorithm LBUS, under the assumption of knowledge of instantaneous CSI for channels. We assume that $\{S_{i}\}_{i\in[N]}$ are generated i.i.d. from a Rayleigh distribution with the variance $P_{1}\sigma^{2}=10$. To better evaluate the performance of different user scheduling schemes, we assume that the channel between the satellite and the relay is strong enough so that the sum rate is only restricted by user scheduling schemes.

The set of all terrestrial users $\mathcal{N}=[N]$ are divided into $M\leq N$ groups, where users with the same CDI are grouped together. Specifically, for any two users $(i,j)\in[N]_{2}$, they lie in the same group if the fading coefficients $(h_{i},h_{j})$ for their terrestrial channels to the relay have the same distribution. This is valid since this way, users close in locations are grouped together.

For simplicity, given each $k\in[M]$, we use $\mathcal{M}_{k}$ to denote users in group $k$, whose channel fading coefficients follow Rayleigh distribution with parameter $\sigma_{k}^{2}$, i.e., $h_{j}\sim\mathcal{CN}(0,2\sigma_{k}^{2}\mathbf{I})$ for all $j\in\mathcal{M}_{k}$ and $\sigma_{k}^{2}$ is the CDI of users in group $\mathcal{M}_{k}$. Note that when only CDI is available, user selection is essentially user group selection. For each time slot, $K$ ($K\leq M$) users are selected to transmit messages. Let $\mathbf{w}:=\{w_{1},\ldots,w_{K}\}\in[M]_{K}$ be the set of the indices of selected user groups and let $\mathbf{v}:=(v_{1},\ldots,v_{K})\in[N]_{K}$ be the index vector of the selected users where $v_{k}\in\mathcal{M}_{w_{k}}$. Each user $v_{k}$ in the group $\mathcal{M}_{w_{k}}$ is selected in a time division manner.

The communication proceeds in the two phases as described in Section II. After user scheduling, $K$ users $\mathbf{v}$, each from a group are selected. For each $k\in[K]$, user $v_{k}$ sends a message $M_{v_{k}}$ to the satellite with power $P_{1}$ with the aid of the terrestrial relay, who works in full-duplex DF mode with power $P_{2}$. Successive cancellation decoding is done at the relay and the satellite. The decoding order at the relay is given by $v_{1}\rightarrow v_{2}\rightarrow\ldots\rightarrow v_{K}$, which satisfies $\sigma_{v_{1}}^{2}>\sigma_{v_{2}}^{2}>\ldots>\sigma_{v_{K}}^{2}$. This assumption simplifies the theoretical analysis in the following section. The decoding order at the satellite is related with that at the relay via the bijective mapping $\Psi^{\prime}\in\mathcal{F}(K,M)$.

When only CDI is available, we consider the outage probability, which is the probability that the transmission at a given rate is not supported, as the performance criterion. Given $\mathbf{v}=(v_{1},\ldots,v_{K})$, the outage event of user $v_{j}$ occurs if any one of the first $j-1$ user suffers an outage event. Specifically, given a target rate $R_{\mathrm{target}}$ and thus corresponding $\gamma_{\mathrm{target}}$ (cf. (18)), for each $k\in[K]$, the outage probability for user $v_{k}$ during the first phase satisfies

where $S_{v_{k}}=P_{1}|h_{v_{k}}|^{2}$ is the received SNR of the signals from user $v_{k}$.

Recall that DF is used at the relay and a power allocation vector is used to split the power $P_{2}$ at the relay among $K$ messages of users. Recall that $\gamma_{\Psi(v_{k})}$ is the received SNR of user $v_{k}$ defined in (5). For the second phase, the outage probability of each user $v_{k}$ is

Note that (31) is subject to the power allocation $\{\alpha_{\psi(v_{k})}\}_{k\in[K]}$ and the received SNR $S_{\mathrm{D},\mathrm{R}}$ for the satellite-relay channel. From arguments around (17), if the number of selected users satisfies $K\leq\frac{\log(S_{\mathrm{D},\mathrm{R}}+1)}{R_{\mathrm{target}}}$, we can always find a power allocation scheme that guarantees $\gamma_{\Psi(v_{k})}$ is larger than the threshold $\gamma_{\mathrm{target}}$. Thus, the outage probability of each user at the second hop satisfies $\mathbb{P}_{v_{k},\mathrm{out}}^{2}=1-\mathbb{P}\left(K\leq\frac{\log(S_{\mathrm{D},\mathrm{R}}+1)}{R_{\mathrm{target}}}\right)$ for $k\in[K]$, i.e., $\mathbb{P}_{v_{k},\mathrm{out}}^{2}=\mathbb{P}_{\mathrm{out}}^{2}=\mathbb{P}(S_{\mathrm{D},\mathrm{R}}<2^{KR_{\mathrm{target}}}-1)$ for $k\in[K]$.

In Theorem 2, we derive a closed-form expression for $\mathbb{P}_{v_{K},\mathrm{out}}$, the outage probability for user $v_{K}$ at the relay. As we shall show, our user scheduling algorithm relies only on $\mathbb{P}_{v_{K},\mathrm{out}}$.

The proof of Theorem 2 is available in Appendix -B.

Note that the outage probability $\mathbb{P}_{\mathrm{out}}^{2}$ is a fixed function of the SNR of the satellite-relay channel and does not relay on user scheduling in the first phase. Thus, to minimize the outage probability of uplink communication, it suffices to minimize the outage probability for the first phase. We then have the following optimization problem.

Recall that successive cancellation decoding is used at the relay. Given a decoding order $\mathbf{v}=(v_{1},\ldots,v_{K})$, the outage event of user $v_{k}$ occurs if any user $v_{i}$ with $i<k$ suffers an outage. Thus, $\mathbb{P}_{v_{K},\mathrm{out}}^{1}\geq\mathbb{P}_{v_{k},\mathrm{out}}^{1}$ for $k\in[K-1]$ and thus $\max_{k\in[K]}\mathbb{P}_{v_{k},\mathrm{out}}=\mathbb{P}_{v_{K},\mathrm{out}}$.