A traffic-awareness dynamic resource allocation scheme based on multi-objective optimization in multi-beam mobile satellite communication systems

Abstract

Mobile satellite communication systems play an important role in space information networks. They mostly operate at the L or S band and have multiple beams efficiently reusing the limited spectrum. Advanced technologies, such as beamforming, are used to generate numerous beams through multiple feeders, and each beam’s power allocation is correlated and constrained. Frequency reuse among multiple beams results in co-channel interference issue, which makes bandwidth allocation among multiple beams coupled. It is a challenging topic to optimize the resource allocation in the real-time service traffic. In this article, a new multi-objective programming scheme is used to solve the dynamic resource allocation problem, guaranteeing high quality-of-service for multiple services of different priorities. Since the dynamic resource allocation problem is formulated as NP-hard, a new traffic-aware dynamic resource allocation (TADRA) algorithm is proposed. This algorithm is proved to be optimal in terms of the Pareto-front under constraints of co-channel interference and onboard transmit power. Simulation results show that the trade-off is well balanced between the call completion ratio in high priority and the throughput for video and data services in medium and low priorities. Additionally, it is shown that the new multi-objective programming scheme, based on the traffic-awareness dynamic resource allocation algorithm, can rapidly achieve the Pareto-front solutions and reduce the computing complexity to a large extent.

Introduction

Mobile satellite communication systems (MSCSs) play an important role in space information networks, as they can establish a reliable wide-range mobile communication network under various scenarios, for example, remote areas, emergency situations, maritime, and aviation transportations. It is developed to connect remote terrestrial networks, direct network access, Internet services, and interactive voice and video using mobile terminals. ¹ The satellite’s ubiquitous coverage can be used to extend the emerging fifth-generation (5G) networks. ² Most of current MSCSs operate at the L or S band and have multiple (even up to several hundreds) beams, efficiently reusing the limited spectrum to support different users and different service traffics. In order to provide users with a good quality of service (QoS), efficient resource allocation schemes (RASs) should be studied for multi-beam MSCSs. ³

The RAS in satellite communication systems has been discussed in previous studies. To increase the system capacity in multi-beam satellite communications, Lim and Kim ⁴ investigated the orthogonal radio resource allocation for downlink signals, and an optimal radio resource allocation for packet transmission in the synchronous multi-beam system was presented. Du et al. ⁵ proposed a multiple access and bandwidth RAS for geostationary Earth orbit relay and a timeslot allocation strategy according to the slotted time-division multiple access. Based on data traffic demands and channel conditions, Choi and Chan ⁶ showed that a modest number of active parallel beams were sufficient to cover numerous cells efficiently by coupling the power allocation with multi-beam scheduling. To maximize the capacity under the upward transmission power constraint, Mokari et al. ⁷ integrated attractive techniques including multiple-input-multiple-output (MIMO), orthogonal frequency-division multiple (OFDM) access, and adaptive coding and modulation (ACM). It indicated that increasing the number of antennas could enhance the overall transmission efficiency. In cognitive satellite communications, Lagunas et al. ⁸ and Liu et al. ⁹ investigated the RAS for a cognitive spectrum scenario where the satellite system aimed at exploiting the spectrum allocated to terrestrial networks (i.e. the incumbent users) without imposing harmful interference on them. Based on the game theory, Markov modeling techniques, and discrete stochastic programming, Petraki et al. ¹⁰ and Davoli et al. ¹¹ presented a distributed call admission control algorithm which exploited the predictability of the satellite channel to guarantee QoS; a novel approach, based on the gradient of cost function determined from the relaxed continuous extension of the discrete constraint set, was also given in their study. Park et al. ¹² divided RAS into the resource calculation and the resource allocation. Anastasopoulos et al. ¹³ gave a priority-based call admission control scheme for two service classes under the rain fading. Higher priority is assigned to real-time users compared to non-real-time users, that is, the real-time traffic is restricted to use up to a certain proportion of the resources.

Previous studies have investigated the power-based RAS.^14–17 Using a stochastic model for rain attenuation prediction and a greedy approach, Srivastava and Chaturvedi ¹⁴ proposed a dynamic power allocation for an increased number of users compared to the static technique. Using adaptive modulation, for different QoS constraints and various channel conditions, Vassaki et al. ¹⁵ analytically solved the optimization problem for the power allocation of a downlink mobile satellite system. The effective capacity is given by a set of closed-form expressions, which corresponds to the optimal power allocation. Destounis and Panagopoulos ¹⁶ presented a simple propagation-based algorithm for the dynamic power allocation using a physical–mathematical model for rain attenuation prediction. Neely et al. ¹⁷ developed a power allocation policy which stabilized the system whenever the rate vector lies within the capacity region. In multi-beam satellite-switched time-division multiple access (SS-TDMA) systems and high-throughput satellite systems, Kyrgiazos and colleagues^18,19 proposed an architecture and a framework based on the assignment of a number of time slots; each gateway uplink connected to a user beam allowed a match to the user demands with the offered capacity of the gateways. A resource allocation policy is designed for video tasks based on the traffic prediction, which is obtained by learning and training the traffic characteristics. ²⁰ In literature,^7,10,21,22 delay-based RAS was investigated. Novel cross-layer packet scheduling scheme to balance the priority, fairness among QoS-differentiated traffic flows, and physical channel data rate factor was proposed by Fan et al. ²¹ The one-objective (e.g. power, loss, capacity, delay or frequency)-based RAS has been studied in Lim and Kim ⁴ and Lee. ²² However, these objectives are sometimes in contrast and coupled and hence multi-objective optimization is needed.

Relatively, only a few authors investigated the RAS with multi-objective programming (MOP) theory in multi-beam MSCSs. Bisio and Marchese ²³ formalized the bandwidth allocation as an MOP where the objectives were the power and loss. Aravanis et al. ²⁴ proposed a two-stage MOP approach to minimize the power and unmet system capacity (USC). Some studies gave an in-depth investigation of terrestrial wireless networks based on MOP. ²⁵ In wireless sensor networks (WSNs), Shahzad et al. ²⁶ formulated the multi-objective optimization functions to minimize the sensor localization errors and the number of transmission during the localization phase. Yaakob et al. ²⁷ mitigated congestion by selectively discarding some of the least important packets to transmit important packets. They defined criteria (e.g. duplicate packets, number of hops traversed, and packets lifetime) to maintain the WSN performance. In cellular networks, literatures^28–31 investigated a paradigm called green communication using a joint optimization of multiple criteria. ³² proposed an RAS called multi-objective distributed power and rate control for the multiple-objective (power, outage, and throughput) optimization problem.

It is challenging to balance the trade-offs among various conflicting optimization criteria. Using the technique of MOP, numerous studies investigated the terrestrial wireless networks. This study guarantees high call completion ratio of voice service and high throughput of non-voice services (which are conflicting criteria under limited resources), while optimizing the resource allocation in the real-time service traffic. The main contributions of this article are highlighted as follows.

First, a dynamic RAS based on multi-objective optimization is proposed, considering multiple services with different priorities.

Second, a low-complexity traffic-awareness dynamic resource allocation (TADRA) algorithm is proposed, which is more efficient than previous algorithms and likely to achieve optimal performance in terms of the Pareto-front.

Third, the average traffic estimation of each service can be more accurate due to the low calculation burden of the proposed algorithm. Hence, the resource allocation achieves a good dynamic match in the real-time traffic. The proposed algorithm’s low complexity indicates that this method can be applicable to more service traffics and more beams under the same hardware constraint.

System model

A multi-beam MSCS composed of a geostationary satellite, multiple gateway stations, and a lot of mobile user terminals as shown in Figure 1. In this system, the satellite has $B(B\ge 2)$ beams and provides services on a wide coverage area. Mobile user terminals are dispersed in these beams. The multi-beam satellite is assumed to be employing an onboard array of transparent transponders to support the feeder links (between the satellite and gateway station) and user links (between the satellite and users). Multiple gateway stations are used to accommodate the high bandwidth required in the feeder link. In the forward link (from the gateway station to users), onboard transponders receive multiplexed signals of $B$ beams from the gateway station, divide them, and then feed them into onboard $W$ solid-state power amplifiers (SSPAs) through a beamforming matrix. By aids of the user link antenna, $B$ beams are composed in space by the electromagnetic waves radiated from the $W$ SSPAs. In the backward-link (from users to the gateway station), onboard transponders receive user terminals’ signals from $B$ beams, synthesize them into the same signal, and feed it into the onboard traveling-wave tube amplifier (TWTA).

Figure 1.

Multi-beam MSCS model.

It is assumed that a frequency reuse factor of 7 (called seven-color) is used to improve the spectrum efficiency in the whole system. Specifically, the $B$ beams are divided into seven groups, each of which contains several beams (equal to $\lceil B/7\rceil$ or $\lceil B/7-1\rceil$ ) using the non-overlapped frequency bandwidth. The multi-frequency time-division multiple access (MF-TDMA) is adopted to make resource allocations flexible with low gains. For beam $b$ in Figure 2, the total bandwidth in the beam is assumed to be equally divided into $C_b$ carriers, and each carrier is equally divided into $E_b$ time slots. Hence, there are $T_b=C_b\times E_b$ frequency–time resource blocks (RBs) in each beam. However, in order to mitigate co-channel interference (CCI), the total reuse times of each carrier allocated to users should be limited, which involves a cross-beam constraint in the resource allocation. The upper bound of each same-frequency carrier reuse times in the whole system is assumed as L such that the CCI is low enough to guarantee the normal operation.

Figure 2.

MF-TDMA and frequency–time resource blocks (under beam $b$ ).

A satellite communication system should support multiple services, and voice, video, and data are considered in this article. Voice is rate-fixed and delay-sensitive information, and it is assigned with the highest priority. Video is a delay-sensitive service and its information rate can be selected from several pre-determined levels; it is assigned with the medium priority. Data is a best-effort service and the information rate and delay are not guaranteed; it is assigned with the lowest priority. Based on these traffic constraints, voice is a circuit-switch domain service and the concerned target is the call completion ratio, while video and data are packet-switch domain services and the concerned target is the total throughput.

Problem formulation

The services, supported by multi-beam satellite communication system, are considered with voice, video, and data. The user number in the beam $b(0<b<B)$ of voice, video, and data are denoted as $U_{b,\mathrm{vo}}$ , $U_{b,\mathrm{vi}}$ , and $U_{b,\mathrm{da}}$ , respectively. Allocation-fixed $r_{\mathrm{vo}}$ RBs and fixed power spectral density $d_{\mathrm{vo}}$ in the voice service are considered. Variable $r_{\mathrm{vi}}$ RBs and fixed power spectral density $d_{\mathrm{vi}}$ are assumed to be allocated to different users’ video service in the same beam or different beams. Hence, we have that

$$r_{\mathrm{vi}}\in \{r_1,r_2,\dots ,r_i,\dots ,r_n\}$$

(1)

where $r_i$ is the $i$ th kind of occupying RBs by the video.

For data services, variable $r_{\mathrm{da}}$ RBs and variable power spectral density $d_{\mathrm{da}}$ to different users in the same beam or different beams are allocated. Instead of uniform power spectral density allocation, different power spectral densities can be allocated to $C_b$ carriers in each beam $b$ . However, $r_{\mathrm{da}}$ and $d_{\mathrm{da}}$ are subject to formula (2) due to the limited rate range supported by the system

$$R_{\min }\le r_{\mathrm{da}}·{\log }_2(1+d_{\mathrm{da}}/n_0)\le R_{\max }$$

(2)

where $n_0$ is the noise power density of receiver; $R_{\min }$ and $R_{\max }$ are the minimum and maximum rates of data service, respectively.

When the resource is allocated to different services, two kinds of processing methods can be chosen. One is to accept it, and the other is to refuse it. A service-adopt-indicator ${\delta }_{b,x,i}$ is used to show different kinds of processing styles, where ${\delta }_{b,x,i}=1$ and ${\delta }_{b,x,i}=0$ represent accepting and refusing the $x$ th kind of services requirement by the $i$ th user in the $b$ th beam, respectively

$$\begin{array}{c}{\delta }_{b,\mathrm{vo},i}=\{0,1\},\forall b\in \{1,2,\dots ,B\}\hfill \\ \forall i\in \{1,2,\dots ,U_{b,\mathrm{vo}}\}\hfill \end{array}$$

(3)

$$\begin{array}{c}{\delta }_{b,\mathrm{vi},i}=\{0,1\},\forall b\in \{1,2,\dots ,B\}\hfill \\ \forall i\in \{1,2,\dots ,U_{b,\mathrm{vi}}\}\hfill \end{array}$$

(4)

$$\begin{array}{c}{\delta }_{b,\mathrm{da},i}=\{0,1\},\forall b\in \{1,2,\dots ,B\}\hfill \\ \forall i\in \{1,2,\dots ,U_{b,\mathrm{da}}\}\hfill \end{array}$$

(5)

${\delta }_{\mathrm{vo}}$ is the indicator matrix for the voice traffic which consists of ${\delta }_{b,\mathrm{vo},i}=\{0,1\},\forall b\in \{1,2,\dots ,B\},\forall i\in \{1,2,\dots ,U_{b,\mathrm{vo}}\}$ , that is

$${\delta }_{\mathrm{vo}}=\left[\begin{array}{ccccc}{\delta }_{1,\mathrm{vo},1}\hfill & \cdots \hfill & {\delta }_{b,\mathrm{vo},1}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{vo},1}\hfill \\ \multicolumn{1}{c}{{\delta }_{1,\mathrm{vo},2}}& \cdots \hfill & {\delta }_{b,\mathrm{vo},2}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{vo},2}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\delta }_{1,\mathrm{vo},i}}& \cdots \hfill & {\delta }_{b,\mathrm{vo},i}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{vo},i}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\delta }_{1,\mathrm{vo},U_{1,\mathrm{vo}}}}& \cdots \hfill & {\delta }_{b,\mathrm{vo},U_{b,\mathrm{vo}}}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{vo},U_{B,\mathrm{vo}}}\hfill \end{array}\right]$$

(6)

${\delta }_{\mathrm{vi}}$ is the indicator matrix for the video traffic which consists of ${\delta }_{b,\mathrm{vi},i}=\{0,1\},\forall b\in \{1,2,\dots ,B\},\forall i\in \{1,2,\dots ,U_{b,\mathrm{vi}}\}$ , that is

$${\delta }_{\mathrm{vi}}=\left[\begin{array}{ccccc}{\delta }_{1,\mathrm{vi},1}\hfill & \cdots \hfill & {\delta }_{b,\mathrm{vi},1}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{vi},1}\hfill \\ \multicolumn{1}{c}{{\delta }_{1,\mathrm{vi},2}}& \cdots \hfill & {\delta }_{b,\mathrm{vi},2}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{vi},2}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\delta }_{1,\mathrm{vi},i}}& \cdots \hfill & {\delta }_{b,\mathrm{vi},i}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{vi},i}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\delta }_{1,\mathrm{vi},U_{1,\mathrm{vi}}}}& \cdots \hfill & {\delta }_{b,\mathrm{vi},U_{b,\mathrm{vi}}}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{vi},U_{B,\mathrm{vi}}}\hfill \end{array}\right]$$

(7)

${\delta }_{\mathrm{da}}$ is the indicator matrix for the data traffic which consists of ${\delta }_{b,\mathrm{da},i}=\{0,1\},\forall b\in \{1,2,\dots ,B\},\forall i\in \{1,2,\dots ,U_{b,\mathrm{da}}\}$ , that is

$${\delta }_{\mathrm{da}}=\left[\begin{array}{ccccc}{\delta }_{1,\mathrm{da},1}\hfill & \cdots \hfill & {\delta }_{b,\mathrm{da},1}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{da},1}\hfill \\ \multicolumn{1}{c}{{\delta }_{1,\mathrm{da},2}}& \cdots \hfill & {\delta }_{b,\mathrm{da},2}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{da},2}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\delta }_{1,\mathrm{da},i}}& \cdots \hfill & {\delta }_{b,\mathrm{da},i}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{da},i}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\delta }_{1,\mathrm{da},U_{1,\mathrm{da}}}}& \cdots \hfill & {\delta }_{b,\mathrm{da},U_{b,\mathrm{da}}}\hfill & \cdots \hfill & {\delta }_{B,\mathrm{da},U_{B,\mathrm{da}}}\hfill \end{array}\right]$$

(8)

For users in the system, the call completion ratio of voice service and total throughput of non-voice service (video and data) are concerned. The call completion ratio of voice in this system can represent the performance of the real-time services in high priority. Most of the non-voice services require more resources to improve the efficiency for ensuring the accuracy of the transmission, and the throughput is usually used to evaluate the system efficiency. Some studies concentrate on the resource allocation problem for increasing the call completion ratio of voice, while some works proposed resource optimization approaches to improve the throughput of non-voice services. To the best of our knowledge, there is no such a study which considers the two performances as the optimization objectives simultaneously. The single-objective optimization can approach the optimal bounds of the system; however, the other objective will be deteriorated when a single objective is solely improved. These two performances are conflicting to each other. Improving the call completion ratio of voice means an enhancement of the allocated proportion of users for the voice service; whereas, improving throughput of non-voice services indicates that more resources need to be allocated to users for the non-voice service. When the real-time service traffic of the voice and non-voice varies in a large margin, the challenge will be quite distinct. Hence, it is meaningful to find the trade-off between these two conflicting objectives. In this article, these two conflicting objectives are considered as optimization objectives under multiple constraints presented previously. The optimization problem is formulated as equations (9) and (10), where $g_1$ and $g_2$ represent the call completion ratio and total throughput of the whole system, respectively. There are six optimization variables. One is the resource occupying by the $i$ th user’s video service $r_{\mathrm{vi},i}$ , under constraint (1). The second and third variables are resources occupied by the $i$ th user’s data service $r_{\mathrm{da},i}$ and power density allocated to $i$ th user’s data service $d_{\mathrm{da},i}$ , under the constraint (2). The last three variables are three services’ adopting indicators ${\delta }_{b,\mathrm{vo},i}$ , ${\delta }_{b,\mathrm{vi},i}$ , and ${\delta }_{b,\mathrm{da},i}$ , under constraints (3)–(5), respectively.

Complexity analysis

Investigating the complexity of the MOP problem formulated previously is important from both the academic perspective and practical perspective since it is necessary to find out whether optimal solutions to the problem can be obtained within feasible computational time. When the number of computing steps required determining the optimal solution to a problem is a polynomial function of the size of the input problem variables, that is, when a polynomial amount of computational time is required, the problem can be solved in feasible computational time. In such cases, it is very important to find an effective approach to decrease the computing complexity especially for a complex system such as the multi-beam

$$\max \{\begin{array}{c}{g}_1({\delta }_{\mathrm{vo}})=\frac{\sum _{b=1}^B\sum _{i=1}^{U_{b,\mathrm{vo}}}{\delta }_{b,\mathrm{vo},i}}{\sum _{b=1}^B{U}_{b,\mathrm{vo}}}\hfill \\ \multicolumn{1}{c}{\begin{array}{c}{g}_2({\delta }_{\mathrm{vi}},{\delta }_{\mathrm{da}},r_{b,\mathrm{vi},i},r_{b,\mathrm{da},i},d_{b,\mathrm{da},i})=\sum _{b=1}^B\sum _{i=1}^{U_{b,\mathrm{vi}}}{\delta }_{b,\mathrm{vi},i}{r}_{b,\mathrm{vi},i}{\log }_2(1+d_{b,\mathrm{vi},i}/n_0)\hfill \\ \multicolumn{1}{c}{+\sum _{b=1}^B\sum _{i=1}^{U_{b,\mathrm{da}}}{\delta }_{b,\mathrm{da},i}{r}_{b,\mathrm{da},i}{\log }_2(1+d_{b,\mathrm{da},i}/n_0)}\end{array}}\end{array}$$

(9)

$$s.t.\{\begin{array}{c}{r}_{b,\mathrm{vi},i}\in \{r_1,r_2,\dots ,r_N\},\forall b\in \{1,2,\dots ,B\},\forall i\in \{1,2,\dots ,U_{b,\mathrm{vi}}\}\hfill \\ \multicolumn{1}{c}{R_{\min }\le r_{b,\mathrm{da},i}\underset{2}{\log }(1+d_{b,\mathrm{da},i}/n_0)\le R_{\max },\forall b\in \{1,2,\dots ,B\},\forall i\in \{1,2,\dots ,U_{b,\mathrm{da}}\}}\\ \multicolumn{1}{c}{{\delta }_{b,\mathrm{vo},i}=\{0,1\},\forall b\in \{1,2,\dots ,B\},\forall i\in \{1,2,\dots ,U_{b,\mathrm{vo}}\}}\\ \multicolumn{1}{c}{{\delta }_{b,\mathrm{vi},i}=\{0,1\},\forall b\in \{1,2,\dots ,B\},\forall i\in \{1,2,\dots ,U_{b,\mathrm{vi}}\}}\\ \multicolumn{1}{c}{{\delta }_{b,\mathrm{da},i}=\{0,1\},\forall b\in \{1,2,\dots ,B\},\forall i\in \{1,2,\dots ,U_{b,\mathrm{da}}\}}\end{array}$$

(10)

satellite communication system. Hence, before selecting the proper scheme to solve the MOP problem, a complexity investigation for the problem is necessary.

Non-deterministic polynomial hardness and optimization

An optimization problem can be divided into the polynomial (P) problems and the non-deterministic polynomial (NP) problems, depending on whether it can be solved within a polynomial time. ³³ The number of computing steps required for the P problem determining the optimal solution is equal to or less than a polynomial function, for example, $\tau \left(x\right)\le \sigma x^{\beta }$ (where $\sigma$ is a constant greater than 0, and $\beta$ is a finite natural number). The P problem can be solved within a polynomial time for arbitary $x$ . ³³ For a NP function, for example, $\tau \left(x\right)~{\beta }^x$ or $x!$ , it cannot be solved within a polynomial time.

Problem (9, 10) is a dynamic MOP problem whose complexity needs to be investigated to design the appropriate algorithm. Actually, the problem in equation (5) can be treated as a two-dimensional bin-packing problem (2D-BPP), ³⁴ and the total resource of the multi-beam mobile satellite system is a container to store RBs and power allocated to users and services.

For given $r$ and $d$ , the feasible solutions for each ${\delta }_{b,\mathrm{vo},i}$ , ${\delta }_{b,\mathrm{vi},i}$ , or ${\delta }_{b,\mathrm{da},i}$ are 0 and 1, that is, the amount of feasible solutions for each user is at least 2. Hence, there are at least $2X$ feasible solutions for the three kinds of $\delta$ , where $X$ is defined as the total number of users requiring the resource and can be calculated by equation (11)

$$X=\sum _{b=1}^B(U_{b,\mathrm{vo}}+U_{b,\mathrm{vi}}+U_{b,\mathrm{da}})$$

(11)

Taking $r$ and $d$ into consideration, the complexity of Problem (9, 10) is higher than $O\left(2^x\right)$ , which means that it is a NP-hard problem. Hence, the resource allocation Problem (9, 10) based on MOP in multi-beam MSCS is proven to be an NP-hard. The optimal solutions of Problem (9, 10) need brute-force search, whose complexity is non-feasible.

From previous analysis, it is known that the MOP problem is an NP-hard problem whose optimal solutions cannot be determined within feasible time. The MOP is more challenging than the single-objective optimization as the multiple objectives are usually in contradictions and there is no global optimal solution. Considering Problem (9, 10), for given available RBs and power resource, if more resource is allocated to voice users, then $g_1$ becomes larger while $g_2$ becomes lower, and vice versa. It means that these two objectives are conflicting to each other, and it makes the proposed problem become a Pareto optimization problem. ³⁵ The process of finding the trade-off between these two conflicting objectives is a Pareto optimization for rejecting the dominated solutions and retaining the non-dominated solutions. Hence, the optimal solution of the problem proposed is a Pareto predominance equilibrium and consists of non-dominated solutions called Pareto-front solutions.

Due to the NP hardness and infeasibility of deriving analytical solutions, an iteration algorithm is required to accomplish the Pareto optimization. The iteration algorithm should have three characteristics. ³⁶ First, a reasonable initial solutions generation algorithm is required to acquire solutions with wide and uniform distributions in the solution space. Second, an efficient searching (iterating) direction is needed to change the state for acquiring non-dominated solutions with a low expenditure of time. Third, a scientific selecting method needs to be designed to reject the dominated solutions and retain the non-dominated solutions.

Multiple coupled constraints to optimization

The MOP problem in this system becomes more complex due to (1) the NP hardness and requirement of Pareto optimization and (2) multiple coupled constraints to the optimization. These constraints are related with the cross-beam and interrelated MSCSs, especially in multi-beam MSCSs. According to the system model stated previously, three kinds of constraints to the MOP problem are analyzed in the system, comprising the timeslot-frequency resource constraint, the reuse time constraint, and the output power constraint. These constraints should be considered during the optimization and highly enhance the complexity of the problem.

Timeslot-frequency resource constraint

For a multi-beam MSCS, its allocated resources include frequency–time RBs $T_b$ and power, where $j$ denotes $j$ th carrier in beam $b$ and $i$ denotes $i$ th timeslot on $j$ th carrier. In beam $b$ , all the occupied frequency–time RBs has a minimum of $T_b$ satisfying relation (12), where $\sum _{i=1}^{U_{b,\mathrm{vo}}}{\delta }_{b,\mathrm{vo},i}{r}_{\mathrm{vo},i}$ represents RBs occupied by the voice service in the $b$ th beam. $\sum _{i=1}^{U_{b,\mathrm{vi}}}{\delta }_{b,\mathrm{vi},i}{r}_{\mathrm{vi},i}$ represents RBs occupied by the video service in the $b$ th beam. $\sum _{i=1}^{U_{b,\mathrm{da}}}{\delta }_{b,\mathrm{da},i}{r}_{\mathrm{da},i}$ represents RBs occupied by the date service in the $b$ th beam

$${\displaystyle \sum _{i=1}^{U_{b,vo}}{\delta }_{b,vo,i}}{r}_{vo,i}+{\displaystyle \sum _{i=1}^{U_{b,vi}}{\delta }_{b,vi,i}}{r}_{vi,i}+{\displaystyle \sum _{i=1}^{U_{b,da}}{\delta }_{b,da,i}}{r}_{da,i}\le T_b,\forall b\in \left\{1,2,\mathrm{\dots },B\right\}$$

(12)

Reuse time constraint

As stated before, the total reuse amount of each carrier allocated to users should be no more than a designed value in order to control CCI. This restriction can be illustrated by relation (13), where $B_j$ denotes the $j$ th beam group and $L$ denotes the maximum reuse times of each same-frequency RBs in the whole system

$${\displaystyle \sum _{b\in B_j}\left({\displaystyle \sum _{i=1}^{U_{b,vo}}{\delta }_{b,vo,i}}{r}_{vo,i}+{\displaystyle \sum _{i=1}^{U_{b,vi}}{\delta }_{b,vi,i}}{r}_{vi,i}+{\displaystyle \sum _{i=1}^{U_{b,da}}{\delta }_{b,da,i}}{r}_{da,i}\right)}\le L,(\forall j=1,2,\mathrm{\dots },7)$$

(13)

Output power constraint

In multi-beam MSCSs, the downlink power is combined by $W$ power amplifiers onboard. The saturation output powers of $W$ power amplifiers onboard are $P$

$$\mathbf{P}=[P_1,P_2,\dots ,P_k,\dots ,P_W{]}^T$$

(14)

Assuming ${\mathbf{a}}_{\mathbf{k}\mathbf{,}\mathbf{b}}$ is the index of power in beam $b$ ’s occupation of the $k$ th downlink power amplifier. $a$ consists of $a_{k,b}=\{0,1\},\forall k\in \{1,2,\dots ,W\},\forall b\in \{1,2,\dots ,B\}$

$$\mathbf{a}=\left[\begin{array}{cccccc}{a}_{1,1}\hfill & a_{1,2}\hfill & \cdots \hfill & a_{1,b}\hfill & \cdots \hfill & a_{1,B}\hfill \\ \multicolumn{1}{c}{a_{2,1}}& a_{2,2}\hfill & \cdots \hfill & a_{2,b}\hfill & \cdots \hfill & a_{2,B}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{a_{k,1}}& a_{k,2}\hfill & \cdots \hfill & a_{k,b}\hfill & \cdots \hfill & a_{k,B}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{a_{W,1}}& a_{W,2}\hfill & \cdots \hfill & a_{W,b}\hfill & \cdots \hfill & a_{W,B}\hfill \end{array}\right]$$

(15)

which satisfies $\sum _{i=1}^W{a}_{i,b}=1,\forall b$ and $\sum _{i=1}^W{a}_{k,i}=1,\forall k$ .

According to the saturation of each power amplifier, resource allocation should satisfy formula (16), where $\sum _{i=1}^{U_{b,\mathrm{vo}}}{\delta }_{b,\mathrm{vo},i}{r}_{\mathrm{vo},i}{d_{\mathrm{vo}}}_{,i}$ denotes the total power occupied by the online voice users, $\sum _{i=1}^{U_{b,\mathrm{vi}}}{\delta }_{b,\mathrm{vi},i}{r}_{\mathrm{vi},i}{d}_{\mathrm{vi},i}$ denotes the total power occupied by the online video (data) users, $\sum _{i=1}^{U_{b,\mathrm{da}}}{\delta }_{b,\mathrm{da},i}{r}_{\mathrm{da},i}{d}_{\mathrm{da},i}$ denotes the total power occupied by the online data users, and $P_k$ denotes the saturation output power of $k$ th power amplifier onboard

$$\sum _{b=1}^B{\alpha }_{k,b}(\sum _{i=1}^{U_{b,\mathrm{vo}}}{\delta }_{b,\mathrm{vo},i}{r}_{\mathrm{vo},i}{d_{\mathrm{vo}}}_{,i}+\sum _{i=1}^{U_{b,\mathrm{vi}}}{\delta }_{b,\mathrm{vi},i}{r}_{\mathrm{vi},i}{d}_{\mathrm{vi},i}+\sum _{i=1}^{{U_{b,}}_{\mathrm{da}}}{\delta }_{b,\mathrm{da},i}{r}_{\mathrm{da},i}{d}_{\mathrm{da},i})\le P_k,\forall k\in \{1,2,\dots ,W\}$$

(16)

Algorithm statement

From analysis of the problem formulated previously, it is found that two objectives of the problem are conflicting to each other. The goal of the optimization problem is to find the Pareto-front of the two objectives, whose analytical solutions cannot be derived. The Pareto-front consists of a set of Pareto optimal solutions, which are known as non-dominated solutions. Some works have been done for solving the Pareto optimization problem; some intelligence algorithms, such as simulated annealing (SA) algorithm and genetic algorithm (GA), have been developed to search the Pareto-front solutions. Non-dominated sorting genetic algorithm II (NSGA-II) ³⁷ is used to find the non-dominated solutions of Pareto optimization problem by introducing the non-dominated sorting operator. The NSGA-II includes operators shown as follows.

Population initialization operator. It initializes the candidate solutions (populations) which are based on the domain of definition and limited by constraints. The candidate populations are denoted by

$$\mathbf{I}=\mathrm{Ra}\left(\mathrm{\Theta }(s.t)\right)$$

(17)

where $\mathbf{I}$ is the matrix of initial populations, $\mathrm{\Theta }(s.t)$ is the domain of definition, and $\mathrm{Ra}(·)$ is a function generating the initial populations over the input domain randomly.

Non-dominated sorting operator. This operator sorts the candidate populations based on non-dominations, and the non-dominated serial numbers of each population for selecting solutions to next iteration and output can be obtained. Deb and Agarwal ³⁸ proposed a fast sorting operator, which improved the original NSGA. The operator is denoted by

$$[\mathbf{S},{\mathbf{I}}_s]=N_{\mathrm{sort}}\left(\mathbf{I}\right)$$

(18)

where ${\mathbf{I}}_s$ is a candidate solution matrix sorted by the non-dominated sorting operator, $\mathbf{S}$ is the non-dominated serial number matrix of the sorted candidate solution matrix ${\mathbf{I}}_s$ , and $N_{\mathrm{sort}}(·)$ is the non-dominated sorting operator.

Crowding distance calculation operator. The distribution of the candidate solutions in each iteration determines the convergence rate of the algorithm. To obtain candidate solutions with an uniform and wide distribution, a crowding distance calculation operator is needed, and it can be formulated as the algorithm description in Li et al. ³⁵

Crossover and mutation operator. It can increase the diversity of the candidate solutions, which helps to approach the Pareto-front. The simulated binary crossover operator and polynomial mutation operator in Bansal et al. ³⁴ are efficient to reduce the complexity, and it can be used to find the non-dominated solutions.

Selecting and updating operator. This operator selects and updates the candidate solutions for the next iteration or output.

The NSGA-II presented above can be used for the Pareto optimization problem in this article. However, how to decrease the calculation complexity and reduce computation time is the main problem when using the NSGA-II algorithm to solve the Pareto optimization problem. The NSGA-II algorithm includes three kinds of modules, that is, initialization module, searching module, and selecting module. In order to restrain the computation time and make the calculation complexity stay the same for every iteration, the number of solutions must be the same for NSGA-II. The selecting module selects the non-dominated solutions with the uniform distribution for next iteration. Hence, after multiple iterations, there are some non-dominated solutions being rejected by selecting module, which might decrease the convergence rate. If we store non-dominated solutions of each iterations, some of the non-dominated solutions which might be Pareto-front solutions will not be rejected and the convergence rate of the algorithm will be improved further. As we know, the calculation complexity of the algorithm is associated with the number of populations and the dimension of solutions (user number in this article). Observing the problem, it is found that there is always a non-dominated solution for each feasible solution of $g_1$ . The essential idea of the NSGA-II is to use random initial candidate solutions to find the non-dominated solutions through the simulated genetic operator and selection. If we can find a set of solutions in or near the Pareto-front, the convergence rate of the algorithm will be improved without the loss of accuracy. If we allocate the RBs based on the arriving proportion, $g_1$ can be expressed as

$$g_1=\frac{1}{\sum _{b=1}^B{U}_{b,\mathrm{vo}}}\sum _{b=1}^B\frac{U_{b,\mathrm{vo}}^2}{U_{b,\mathrm{vo}}+U_{b,\mathrm{vi}}+U_{b,\mathrm{da}}}$$

(19)

Then, the single-objective problem is given as formula (20)

$$max={\displaystyle \sum _{b=1}^B{\displaystyle \sum _{i=1}^{U_{b,vi}}{\delta }_{b,vi,i}}}{r}_{vi,i}{\log }_2\left(1+d_{vi,i}/n_0\right)+{\displaystyle \sum _{b=1}^B{\displaystyle \sum _{i=1}^{U_{b,da}}{\delta }_{b,da,i}}}{r}_{da,i}{\log }_2\left(1+d_{da,i}/n_0\right)$$

(20)

$$s.t.\{\begin{array}{c}\sum _{i=1}^{U_{b,\mathrm{vo}}}{\delta }_{b,\mathrm{vo},i}{r}_{\mathrm{vo},i}+\sum _{i=1}^{U_{b,\mathrm{vi}}}{\delta }_{b,\mathrm{vi},i}{r}_{\mathrm{vi},i}+\sum _{i=1}^{U_{b,\mathrm{da}}}{\delta }_{b,\mathrm{da},i}{r}_{\mathrm{da},i}\le T_b,\forall b\in \{1,2,\dots ,B\},r_{\mathrm{vi}}\in \{r_1,r_2,\dots ,r_N\}\hfill \\ \multicolumn{1}{c}{\sum _{b=1}^B{\alpha }_{k,b}(\sum _{i=1}^{U_{b,\mathrm{vo}}}{\delta }_{b,\mathrm{vo},i}{r}_{\mathrm{vo},i}{d_{\mathrm{vo}}}_{,i}+\sum _{i=1}^{U_{b,\mathrm{vi}}}{\delta }_{b,\mathrm{vi},i}{r}_{\mathrm{vi},i}{d}_{\mathrm{vi},i}+\sum _{i=1}^{{U_{b,}}_{\mathrm{da}}}{\delta }_{b,\mathrm{da},i}{r}_{\mathrm{da},i}{d}_{\mathrm{da},i})\le P_k,\forall k\in \{1,2,\dots ,W\}}\\ \multicolumn{1}{c}{R_{\min }\le r_{\mathrm{da}}{\log }_2(1+d_{\mathrm{da}}/n_0)\le R_{\max }}\\ \multicolumn{1}{c}{\sum _{i=1}^{U_{b,\mathrm{vo}}}{\delta }_{b,\mathrm{vo},i}=\frac{U_{b,\mathrm{vo}}^2}{U_{b,\mathrm{vo}}+U_{b,\mathrm{vi}}+U_{b,\mathrm{da}}}}\end{array}$$

(21)

We can obtain one non-dominated solution by optimizing the problem above. The optimal solutions of the problem satisfy that the RBs are allocated to the users with the highest rate. This non-dominated solution can be used as initial seed for approaching the Pareto-front. Based on this, we design a TADRA algorithm based on the improved NSGA algorithm (NSGA-II algorithm) to solve the Pareto optimization problem, and the TADRA algorithm is shown in Table 1.

Table 1.

Description of algorithm.

Algorithm: traffic-awareness dynamic resource allocation (TADRA) algorithm
1. Algorithm initialization (Stopping criterion, Generation $G$ , Clone ratio $\mathbf{R}$ )
2. Find the initial seed $\mathbf{X}$ based on the arriving proportion
3. Clone the initial seed based on $\mathbf{R}$ to obtain $\mathbf{I}$
4. Repeat
5.  Crossover and mutation for generating offsprings from $\mathbf{I}$
6. Until Iteration = $\mathbf{R}$
7. Non-domination sorting to obtain serial number matrix $\mathbf{S}$
8. Repeat
9.  Repeat
10.  Tournament selection for parent chromosome ${\mathbf{I}}_1$
11.  Crossover and mutation for generating offsprings from ${\mathbf{I}}_1$ to obtain ${\mathbf{I}}_2$
12.  Non-domination sorting to update $\mathbf{S}$
13.  Update the chromosome $\mathbf{I}$ with $\mathbf{S}$ and ${\mathbf{I}}_2$
14.  Store the non-dominated solutions (chromosomes with $s_i=1,s_i\forall \mathbf{S}$ )
15.  Until Iteration = $\mathbf{G}$
16.  Non-domination sorting to updating the $\mathbf{S}$ and $\mathbf{I}$ in store table
17. Until meet the stopping criterion
18. Output the non-dominated solutions and update the storing table

The Pareto-front approached by TADRA algorithm is a set of feasible solutions under certain traffic states and arriving models. The service ratio and the average users in each beam have some influence on the distribution of the Pareto solutions, that is, for a specific arriving model, the solution space is known, based on the traffic state. Some optimized results obtained from the Pareto-front are empirical results that can be used for similar traffic conditions. In this section, we propose the traffic-awareness RB allocation method. The flowchart of the method is shown in Figure 3. At the beginning of the allocation, we estimate the traffic and inquire the database to find if there is any similar pattern that can be used for the allocation. If no feasible allocation is found, the TADRA algorithm is activated to find the Pareto-front. Then, some feasible solutions are obtained based on some parameters and constraints and are stored into the database. This method can learn the allocated pattern and accomplish the allocation based on the traffic adaptively, and it is meaningful for multi-beam MSCSs with constantly changing traffic models and multiple constrains.

Figure 3.

Adaptive traffic-awareness resource block allocation method.

As shown in Table 1, the TADRA algorithm has three advantages compared with the NSGA-II.

First, the Pareto solution obtained from the single-objective optimization is introduced as an initial seed which is used as the start point to approach the Pareto-front. With a small clone ratio, an additional crossover and mutation operation, we can obtain a set of initial solutions closer to the Pareto-front compared with the NSGA-II, which can narrow the gap between initial solutions and the Pareto-front and reduce the searching time.

Second, the algorithm complexity is mainly related to the iteration times and the number of populations (alternative solution). With the initial seed close to the Pareto-front, we can only use population for iteration, which is far smaller than population used for NSGA-II. This will be verified in the next section.

Third, different form NSGA-II, the database we used to store the Pareto optimization solution for different traffic pattern is also used to store non-dominated solutions of each iteration. Some of the non-dominated solutions might be Pareto-front solutions, and without rejecting some of them, the TADRA algorithm can improve the convergence rate further.

Finally, in order to ensure the final solutions being globally Pareto optimal, additional non-dominated sorting and updating can reject some dominated solutions to improve the correctness.

As a matter of fact, almost all the heuristic algorithms are similar to each other, such as ant colony optimization and artificial immune algorithms, and they all include three modules, that is, initialization module, searching module, and selecting module. To restrain the computation time and ensure the complexity being same for every iteration, the number of the solutions has to be the same. The selecting module selects the non-dominated solutions obeying the uniform distribution for next iteration. Hence, after multiple iterations, there are some non-dominated solutions rejected by the selecting module, which may decrease the convergence rate. The essential idea of the heuristic algorithms applied for the Pareto algorithm is to find the searching direction for approaching the Pareto-front. When one cannot derive the analytical solutions for the Pareto optimization problem, these classical heuristic algorithms presented previously can be utilized to determine the Pareto-front. However, when one can obtain some of the Pareto solutions with low calculation complexity, the search time (computation complexity) can be reduced by introducing the obtained Pareto solutions as initial solutions. This framework of the improved NSGA-II can be extended into any heuristic algorithms with three aforementioned modules. Because of using one Pareto solution and the database, the complexity is only related to the clonal ratio and the numbers of the arriving service requests, which is far lower than that of all classical heuristic algorithms. Moreover, the convergence rate is quicker than the classical heuristic algorithms, and this will be proved in the next section with simulation results.

Simulation results and analysis

After we have described the TADRA algorithm for solving the MOP we proposed, we simulate the algorithm under different conditions. First of all, we compared the performances of NSGA-II and the TADRA algorithm. The simulation parameters are shown in Table 2. It is assumed that the service arrival queues of satellites satisfy the Poisson arrival, and the average user numbers of voice, video, and data services are 1000, 100, and 100, respectively. For the NSGA-II and the TADRA algorithm, simulation parameters are shown in Table 2. The simulation results are shown in Figure 4. As we can see from the Figure 4, the Pareto-fronts of the two different algorithms are similar. With the same iteration, TADRA algorithm can find more Pareto-front solutions compared with the NSGA-II. It means that the convergence rate of the TADRA algorithm is quicker than NSGA-II. Since the initial seed for the TADRA algorithm is one Pareto-front solution, this algorithm can narrow the searching space for optimized Pareto-fronts. At the meantime, the complexity in every step of the TADRA algorithm is lower than the traditional NSGA-II. There are $N_{\mathrm{pop}}\times \sum _{b=1}^B(U_{\mathrm{vo},b}+U_{\mathrm{vi},b}+U_{\mathrm{da},b})$ operations for each operator in each step of NSGA-II, and the complexity is $O(200\sum _{b=1}^B(U_{\mathrm{vo},b}+U_{\mathrm{vi},b}+U_{\mathrm{da},b}))$ . On the contrary, the complexity of the TADRA algorithm is $O(10\sum _{b=1}^B(U_{\mathrm{vo},b}+U_{\mathrm{vi},b}+U_{\mathrm{da},b}))$ because of storing of the non-dominated solutions in each iteration. In fact, the TADRA algorithm can obtain the same Pareto solutions with lower steps than the NSGA-II. The complexity of the algorithm is mostly contributed by the non-dominated searching and the objective evaluation. The TADRA algorithm only involves one more non-dominated sorting and selecting operator with 10 sets of the populations. Hence, the total complexity is lower than the NSGA-II.

Table 2.

Simulation parameters of the system and the TADRA algorithm.

Parameters	Values
$B$	$20$
$T_b$	$1000\times 16\mathrm{kbps}$
$R_{\min }$	$9.6\mathrm{kbps}$
$R_{\max }$	$384\mathrm{kbps}$
$r_i$	$16\times i\mathrm{kbps},i\in \{8,16,24\}$
$d_{\mathrm{vi}}$	$1$
$r_{\mathrm{vo}}$	$3.2\mathrm{kbps}$
$d_{\mathrm{vo}}$	$1$
${\lambda }_{\mathrm{vo}}$	$1000$
${\lambda }_{\mathrm{vi}}$	$100$
${\lambda }_{\mathrm{da}}$	$100$
$a$	Random
$P_{\mathrm{total}}$	$800\mathrm{W}$
Population for NSGA-II	$200$
Population for proposed	$1$
Clone ratio for proposed	$10$
Generations	$800$
Pool size	$100$
Tour size	$2$
Crossover index, ${\eta }_c$	$20$
Mutation index, ${\eta }_m$	$20$

TADRA: traffic-awareness dynamic resource allocation; NSGA II: non-dominated sorting genetic algorithm II.

Figure 4.

Algorithm performance simulations.

We also analyze the Pareto-front solutions under different conditions. We compared the Pareto-front of the system states with different service ratios under different arriving models. The service ratio is the proportion of the voice service in the whole system, and it can be denoted by

$$\xi =\frac{\sum _{b=1}^B{U}_{\mathrm{vo},b}}{\sum _{b=1}^B(U_{\mathrm{vo},b}+U_{\mathrm{vi},b}+U_{\mathrm{da},b})}$$

(22)

Two kinds of arriving models are considered: the average user number being 1200/beam and the average use number being 2000/beam. The first one is the same as parameters in Table 2, and ${\lambda }_{\mathrm{co}}$ , ${\lambda }_{\mathrm{vi}}$ , and ${\lambda }_{\mathrm{da}}$ of the second one are 1800, 100, and 100, respectively. With reasonable traffic monitoring method, the total traffic of the system can be obtained. The total traffic cannot represent the traffic mode of the whole network, because one result of the total traffic may correspond to multiple combinations of the services ratio. Hence, we use the service ratio and the total traffic to distinguish different traffic modes. These two parameters can be stored into the database with feasible solutions selected from the Pareto-front. The simulation results are shown in Figure 5. Through analysis of Figure 5, we can find that the Pareto-front with lower $\xi$ and lower average number of users is better than other ones, and different arriving models can make the Pareto-front change dynamically. Hence, we can store the allocation result and build an adaptive allocation mechanism for future works. The TADRA algorithm can find the Pareto-front of the problem. Different Pareto-fronts of the TADRA algorithm could supply the multiple feasible solutions for system states with different arriving models under different traffic conditions. Under the complex environment conditions in multi-beam MSCS, the resource allocation determined by man-made decision might not be accurate for the system requirement. On the contrary, the adaptive traffic-awareness allocation can avoid this circumstance, and the machine-learning and big data technologies could be used for traffic pattern recognition and finding the feasible solution with low expenditure of time.

Figure 5.

Pareto-fronts for various service ratios with different average users.

In order to further understand the significance of the TADRA algorithm we proposed and the Pareto-front solutions we obtained, we compare the performance of different allocation criterion with some results come from the Pareto-front under the same system model. We consider the RB allocation for single beam. The average arriving rates ${\lambda }_{\mathrm{co}}$ , ${\lambda }_{\mathrm{vi}}$ , and ${\lambda }_{\mathrm{da}}$ of the second one are 1800, 100, and 100 per allocation duration, respectively, which are shown in Figure 6(a), and the arriving process is a Poisson arrival process. The service type 1, 2, and 3 in Figure 6 represent the voice, video, and data service, respectively. We use the Monte–Carlo simulation method with 1000 allocation duration, and we assume that all services arrived only existing for one allocation duration. With the service rate constraint, we can evaluate the average traffic of the system of 1000 allocation duration, which is shown in Figure 6(b). We consider four allocation criterions: the voice prior allocation, the proportional fairness allocation, and the 90% and 95% call completion allocation from the Pareto-front we obtained. The voice prior allocation is common way for engineering practice, allocating, or obligating the resource to the voice service with top priority, and it is also known as the highest priority first (HPF) algorithm. In this simulation, the voice prior allocation criterion is realized by allocating the RBs to voice service with highest priority (video and data services with the same priority for the rest of the resource). The proportional fairness allocation can be expressed by

$$\mathrm{ma}{x}_{T_b}\sum _{\mathrm{type}=1}^3\log \left[f\left(T_b\right)\right]$$

(23)

where $f(·)$ is the resource utility function, and $T_b$ is the set of RBs. In this simulation, we use the average traffic demand as the resource utility function. Figure 6(c) and (d) shows the allocated capacity and the service completion of three types of service. As we can see, the voice-first allocation can obtain high call completion ratio. However, the completion ratios of video and data services are reduced because of the resource competition between these three services. With higher voice arriving rate, some of the video and data services may not be rejected for all the time. Proportional fairness allocation can ensure the service completion fairness (shown in Figure 6(d)), but the call completion rate of the voice service is lower than 60%. The 90% and 95% call completion allocation from the Pareto-front we obtained are trade-off results between the voice prior allocation and proportional fairness allocation. With multiple results from the Pareto optimization, we could avoid the weakness of these two allocating criterion stated previously.

Figure 6.

Different allocation criteria comparison for single beam: (a) average arriving rate of different types of users, (b) average traffic of different types of users, (c) allocated capacity of different types of users under different allocation criterion, and (d) service completion of different types of users under different allocation criterion.

As a matter of fact, the allocation result is a Pareto-front solution as long as all resources are allocated to users. At the situation, in Figure 6, all results of different allocated criteria are Pareto optimal. Figure 7 shows the achieved traffic $g_2$ of different allocation methods. As we can see, the proportional fairness allocation could achieve better performance, and $g_2$ of the voice prior allocation is lowest, which is because of the performance caused by high call completion ratio protection. On the contrary, the proportional fairness allocation maximizes the achievable total traffic with unacceptable call completion ratio loss. Figure 8 shows the call completion ratio of proportional fairness under different video and voice services arriving rates. As we can see, with traffic demand that is out of the system capacity, the call completion performance is decreasing with the increase in the arriving rate. With the TADRA algorithm, we can adjust the allocation criterion based on the traffic mode, which could avoid the performance loss with traffic changes shown as Figure 6, and we can obtain the trade-off between call completion ratio and achieved traffic or approach the stable traffic intensity shown in Figure 5 with feasible call completion ratio.

Figure 7.

Traffic comparison of different allocation criterion under different video services arriving rate.

Figure 8.

Call completion ratio of proportional fairness under different video and voice services arriving rate.

Conclusion

Resources, comprising frequency–time RBs and output power onboard the multi-beam mobile satellite system, need to be properly allocated to different services and different users to achieve high QoS and match variable real-time service traffic. After proving the NP hardness and analyzing the complexity of Pareto optimization, multiple coupled constraints to the optimization, this article studies multiple resource allocation in multi-beam satellite systems proposing a multi-objective optimization scheme. Employing a TADRA algorithm proposed in this article, the proposed multi-objective optimization scheme has been shown to obtain the Pareto-front rapidly, matched the variable real-time service traffic, and reduces the computing complexity by 95% compared to NSGA II algorithm. Moreover, the proposed scheme sets a general framework to highly reduce the complexity of the MOP algorithms based on populations by employing traffic awareness to decrease the necessary number of populations to only one, making feasible the practical implementation of the proposed RAS.