1 Introduction to high-altitude platforms
-
Their ability to fly on demand to temporarily or permanently serve regions with unavailable telecommunications infrastructure.
-
A single HAP has a large area coverage that can go up to 150 km compared to a single terrestrial cellular base station (BS) whose maximum radius, for macro cells, is in the range of 20–30 km.
-
Low propagation delays compared to satellites which implies better perceived quality of service (QoS) by the users for real-time applications like voice and video.
-
Stronger received signal strengths as compared to satellites and hence user terminals need not be bulky.
-
Deployment time is low since one platform and ground support are sufficient to start the service.
-
Much less ground-based infrastructure compared to terrestrial cellular networks.
2 Recent works in HAPs
3 Radio resource allocation and admission control for multicasting in HAPs (Methods)
3.1 Differences between rRA in HAP systems and terrestrial cellular systems
3.2 Motivations for the proposed aC-RRA scheme
3.3 Scope and contribution of the paper
4 Multicasting in a single HAP system: an efficient formulation and an extended problem
4.1 System model
Notation | Definition |
---|---|
M
| Is the number of multicast sessions in the HAP service area. |
S
| Is the number of HAP antennas onboard. |
K
| Number of users in the service area. |
C
| Is the number of available subchannels. |
T
| Total number of time slots available over OFDMA frame. |
Δ
B
| Is the subchannel bandwidth. |
Δ
T
| Is one time slot duration. |
F
| Is the OFDMA frame duration. |
σ
2
| Is the additive white Gaussian noise power per subchannel. |
p
m,
i,
c,
t
| Is the value of the HAP power assigned for multicast session m on antenna i in the frequency-time slot (c,t). |
g
i,
k,
c,
t
| Channel gain between antenna i and user k on frequency-time slot (c,t). |
λ
m,
k
| Is a binary constant that indicates whether user k requests to join session m. |
ϕ
m,
k
| Is a binary variable that indicates whether a user k gets assigned to receive multicast session m. |
ρ
m,
k
| Is a positive integer constant that represents priority for user k on session m. |
θ
m
| Is a binary variable that indicates whether session m receives any resources, or equivalently, whether any user gets assigned to receive the session’s transmission. |
y
m,
i,
c,
t
| Is a binary variable that indicates whether the trio combination (i,c,t) is assigned for session m. |
\(\hat {M}\)
| Is a very large arbitrary number. |
\(\gamma ^{th}_{m,i}\)
| Is the SINR value that satisfies a desired target BER for session m on antenna i. Different sessions transmitted on different antennas may be modulated and coded differently thus requiring different SINR thresholds. |
-
Takes the value of the SINR of the user k on the trio combination (i,c,t) if the user gets to receive session m,
-
Takes a very large number \(\hat {M}\) (theoretically infinity) if user k does not get to receive session m but some other users do, or
-
Zero if no users in the service area are assigned to receive session m.
-
GH(ϖi,k) is the gain seen at an angle ϖi,k between user terminal k and antenna i boresight axis and is defined by [21]$$ {G_{H}\left(\varpi_{i,k}\right)={Ap}_{eff}\cdot cos\left(\varpi_{i,k}\right)^{n}\frac{32log2}{2\left(2arccos\left(\sqrt[n]{0.5}\right)\right)^{2}}} $$(5)where Apeff is the antenna’s efficiency, n is the rate of roll-off for the raised cosine function.
-
dk is the distance between the HAP and user terminal k, \(\check {C}_{light}\) is the speed of light and fc is the carrier frequency.
-
A(dk) is the attenuation due to clouds and rain. This depends on the distance between the HAP and each user k in the service area.
-
\(G_{k}^{u}\) the antenna’s gain of user terminal k.
-
φk,c,t is the Ricean small scale gain in frequency-time slot (c,t) for user terminal k.
-
Takes the value of the SINR of user k on the trio combination (i,c,t) if the user gets to receive session m, or
-
Is zero if user k does not get to receive session m.
4.2 Key differences in the fundamental equations that describe e-Prob and p-Prob
-
Nm,i is the group of multicast users residing in cell i receiving session m and can only receive transmission from antenna i,
-
zm,i,k,c,t is the set of binary decision variables that indicated whether a user k got admitted to receive transmission m from the antenna covering cell i on a frequency-time slot (c,t),
-
xm,i,c,t was a binary decision variable that indicated whether a frequency-time slot (c,t) got assigned for the group Nm,i.
4.3 Formulation of E-Prob
-
The same QoS, resource and multicast transmission requirements as in the P-Prob,
-
As well as the differences in the extended system model explained earlier in Section 4.1.
-
The objective function represents a weighted sum of all admissions of different users over all sessions. The larger weights force user-to-session admissions of highest priorities as long as the QoS SINR and group data capacity requirements can be satisfied. This is different from the objective function in [22‐24] which sums all the users, assuming homogeneous priorities, in all the frequency-time slots across all HAP cells.
-
C1 ensures that if user k does not request to receive session m (i.e., λm,k=0) then the user can never be assigned to receive it (i.e., ϕm,k is set to zero). This constraint set is somehow similar to constraint set D1 of formulation (OP1) in [24] (P-Prob), yet consists of M.K constraints versus M.S.K.C.T in D1 of formulation (OP1) in [24]. The functional difference is that D1 for P-Prob ensures that the user can be admitted to receive session m when:
-
User k is in cell i, and
-
Session m is being transmitted in cell i.
In E-Prob, we do not have these two restrictions. -
-
C3 ensures that user k can be assigned to multicast group m only when the session gets assigned at least one resource trio combination (i,c,t). This constraint set, besides C4, are both required in \({\mathcal {H}\mathcal {A}\mathcal {P}^{Eff}}\) to connect the two sets of variables ϕm,k and ym,i,c,t. These were not required in formulation (OP1) in [24] since ϕm,k and ym,i,c,t were captured both in a single variable, zm,i,k,c,t.
-
C4 ensures that if no users are assigned to session m, then no resource trios (i,c,t) should be allocated to the group.
-
C5 ensures that if the trio combination (i,c,t) is not assigned for session m then the power level assigned for group m on (i,c,t) should be forced to zero. This is equivalent to constraint set D10 in formulation (OP1) in [24]. However, each constraint in C5 of \({\mathcal {H}\mathcal {A}\mathcal {P}^{Eff}}\) has only two variables compared to K+1 variables in each constraint of D10 in formulation (OP1) in [24].
-
C6 ensures that the total power at a given time slot assigned for all multicast groups on all antenna-frequency (i,c) pairs, must be limited to the total available HAP power. This is exactly the same constraint as D9 in formulation (OP1) in [24].
-
C7 ensures that the power values pm,i,c,t are all non-negative. This is exactly the same as D11 in formulation (OP1) in [24].
-
C8 is a constraint set that enforces the SINR for user k receiving session m to be greater than a threshold value \(\gamma ^{th}_{m,i}\) to admit the user to group m. There are three possibilities for this for each of the constraints in the set, which are explained as follows:1.If the trio combination (i,c,t) is not assigned to session m (i.e., ym,i,c,t=0), constraint C5 forces the power variable pm,i,c,t to be zero. This makes the left hand side (L.H.S) in constraint (C8) either equal to the very large number \(\hat {M}\), or equal to zero, depending on the value of ϕm,k. Both cases satisfy the inequality rendering the constraint redundant.2.If the trio (i,c,t) is assigned to session m (i.e., ym,i,c,t=1), but user k is not assigned to receive m (i.e., ϕm,k=0), the power variable pm,i,c,t could take any non-zero value. In this case, the term in the numerator of the R.H.S becomes greater than or equal to the very large number \(\hat {M}\) making the constraint redundant.3.For ym,i,c,t=1, if user k is to get admitted for session m, then ϕm,k=1. In this case, the term on the L.H.S of the constraint equivalent to the SINR for session m to user k since the numerator becomes the product of the power variable pm,i,c,t times the gain of the user on the trio combination (i,c,t). The R.H.S. also becomes equal to the acceptable threshold value,\(\gamma ^{th}_{m,i}\), for session m on antenna i. In this case the SINR constraint over the trio combination (i,c,t) comes into effect for user k and session m.Constraint set C8 in \({\mathcal {H}\mathcal {A}\mathcal {P}^{Eff}}\) is functionally equivalent to D3 in formulation (OP1) in [24].
-
C9 and C10 together ensure that only if there are any resources being assigned for session m, then this must set the variable θm=1, otherwise θm=0 is enforced. This is needed for the minimum data capacity constraint C12. Constraint sets C9 and C10 have no equivalent constraint sets in formulation (OP1) in [24].
-
C11 ensures the minimum capacity \(R^{min}_{m}\) of a multicast session is satisfied. We use the definition of the minimum capacity of a multicast group given in Eq. (1). There are four possibilities for xm,i,k,c,t (defined by Eq. 3) which are explained as follows:1.ym,i,c,t=0 and ϕm,k=0. In this case, constraints C5 will force the power variable pm,i,c,t to be zero which results in, xm,i,k,c,t=0 and \(\underset {k}{min}~x_{m,i,k,c,t}=0\) giving a capacity of zero on the trio combination (i,c,t).2.ym,i,c,t=0 and ϕm,k=1. This would have exactly the same result as the first case, a capacity of zero on that trio combination (i,c,t) for the same reasons.3.ym,i,c,t=1 and ϕm,k=0. In this case xm,i,k,c,t=∞ theoretically, which ensures that for that particular user, its SINR value is never returned by the term \(\underset {k}{min~}~x_{m,i,k,c,t}\). There are definitely other users who have ϕm,k=1, according to constraint C4, from which the least SINR on (i,c,t) is returned by \(\underset {k}{min~}~x_{m,i,k,c,t}\).4.ym,i,c,t=1 and ϕm,k=1 in this case \(x_{m,i,k,c,t}=\frac {p_{m,i,c,t}g_{i,k,c,t}}{\sum _{m=1}^{M}\sum _{\forall i^{\prime }\neq i}^{}g_{i^{\prime },k,c,t}p_{m,i^{\prime },c,t}+\sigma ^{2}}\) which is the SINR of the user k and session m over the trio combination (i,c,t). Therefore, \(\underset {k}{min}~x_{m,i,k,c,t}\) would return the minimum SINRs of all users in group m over (i,c,t).The variable θm ensures that the constraint is not in effect in the case that no resources are allocated at all for session m, i.e., θm=0. This constraint set extends the lower bound constraint set for C4 in formulation (O) in [24] by summing the data capacity of session m over all the HAP antennas. It is worth noting that for P-Prob, constraint set D2 in formulation (OP1) in [24] enforced all users to receive multicast sessions from only one antenna, which is the antenna that covers the cell they reside in.
-
C12 ensures that the maximum capacity of the group or session m, defined by Eq. (6), is satisfied. The possibilities for tm,i,k,c,t, defined by Eq. (8), are explained as follows:1.For the case ym,i,c,t=0, no matter what the value of ϕm,k is, the power variable pm,i,c,t is forced to zero by constraint C5, therefore we get tm,i,k,c,t=0 ∀ k, and \(\underset {k}{max}~t_{m,i,k,c,t}=0\).2.For the case ym,i,c,t=1, and user k is not assigned to group m, i.e., ϕm,k=0. In this case, tm,i,k,c,t returns zero but the term \(\underset {k}{max}~t_{m,i,k,c,t}\) returns the highest SINR, over (i,c,t), among all users assigned to session/group m. We are sure that if ym,i,c,t=1 then there is at least one user who has ϕm,k=1 according to constraint set C5.3.For the case ym,i,c,t=1 and user k assigned to the group m, i.e., ϕm,k=1, \(t_{m,i,k,c,t}=\frac {p_{m,i,c,t}g_{i,k,c,t}}{\sum _{m=1}^{M}\sum _{\forall i^{\prime }\neq i}^{}g_{i^{\prime },k,c,t}p_{m,i^{\prime },c,t}+\sigma ^{2}}\) and the term \(\underset {k}{max}~t_{m,i,k,c,t}\) returns the highest SINR over (i,c,t) among all users assigned to session/group m.Constraint set C12 in \({\mathcal {H}\mathcal {A}\mathcal {P}^{Eff}}\) is different from their equivalent upper bound data capacity constraint set C4 in formulation (O) in [24] in two aspects. The first aspect is that C12 in \({\mathcal {H}\mathcal {A}\mathcal {P}^{Eff}}\) utilizes the newly introduced concept of maximum multicast group data capacity mentioned earlier in this paper and given by Eqs. 6 and 7. In this way, it is guaranteed that no user in any multicast group can have a data capacity greater than \(R^{max}_{m}\). Constraint set C4 in formulation (O) in [24] on the other hand uses the data capacity of the user with the poorest channel conditions to define the group’s data capacity, and it is that data capacity that is enforced to be no more than \(R^{max}_{m}\). This could lead to users with good channel and interference conditions in a group receiving a capacity greater than \(R^{max}_{m}\), which constraint set C12 in \({\mathcal {H}\mathcal {A}\mathcal {P}^{Eff}}\) makes sure does not happen. The second difference is that since E-Prob allows the users in a group m to receive the multicast transmission on more than one antenna simultaneously, then the maximum data capacity of the group is obtained by summing all the group’s data capacities over all the antennas. This was not considered in formulation (O) in [24].
4.4 A cross-layer management for the optimization problem parameters
5 Reducing the formulation \({\mathcal {H}\mathcal {A}\mathcal {P}^{Eff}}\) to a mixed binary polynomial constrained problem
6 Reduction of the formulation to mixed binary quadratic constraints
7 Comparison of the formulation sizes with the aid of a numerical example
-
The number of binary variables, zm,i,k,c,t, is the product MSKCT
-
The number of continuous variables, pm,i,c,t, is MSCT
-
Hence, giving a total number of variables$$ {VN}_{OP1}=MSKCT+MSCT. $$(32)
-
Constraint set D1 comprises MSKCT constraints
-
Constraint set D2 comprises MSKCT[CT−1][K−1] constraints
-
Constraint set D3 comprises MSKCT constraints
-
Constraint set D4 comprises MSKCT constraints,
-
Constraint set D5 comprises MSKCT[M−1][K−1] constraints
-
Constraint set D6 comprises MSKCT constraints
-
Constraint set D7 comprises MSK constraints
-
Constraint set D9 comprises T constraints
-
Constraint set D10 comprises MSCT constraints
-
The numbers of binary variables ϕm,k,θm,ym,i,c,t are the MK, M and MSCT respectively giving a total number of binary variables MK+M+MSCT.
-
The number of continuous variables:
-
pm,i,c,t are MSCT,
-
um,i,c,t are MSCT,
-
wm,i,c,t are MSCT
-
Um,j are M[SCT−2], and
-
Wm,j are M[SCT−2].
all adding up to 3MSCT+2M[SCT−2] continuous variables. -
-
Constraint set \(\overline {C1}\) consists of MK constraints
-
Constraint set \(\overline {C2}\) consists of SCT constraints
-
Constraint set \(\overline {C3}\) consists of MK constraints
-
Constraint set \(\overline {C4}\) consists of MSCT constraints
-
Constraint set \(\overline {C5}\) consists of MSCT constraints
-
Constraint set \(\overline {C6}\) consists of T constraints
-
Constraint set \(\overline {C8}\) consists of MSKCT constraints
-
Constraint set \(\overline {C9}\) consists of M constraints
-
Constraint set \(\overline {C10}\) consists of M constraints
-
Constraint set \(\overline {Q1a}\) consists of M constraints
-
Constraint set \(\overline {Q1b}\) consists of M[SCT−3] constraints
-
Constraint set \(\overline {Q1c}\) consists of M[SCT−3] constraints
-
Constraint set \(\overline {Q1d}\) consists of M constraints
-
Constraint set \(\overline {Q1e}\) consists of M constraints
-
Constraint set \(\overline {Q2}\) consists of MSKCT constraints
-
Constraint set \(\overline {Q3a}\) consists of M constraints
-
Constraint set \(\overline {Q3b}\) consists of M[SCT−3] constraints
-
Constraint set \(\overline {Q3c}\) consists of M[SCT−3] constraints
-
Constraint set \(\overline {Q3d}\) consists of M constraints
-
Constraint set \(\overline {Q3e}\) consists of M constraints
-
Constraint set \(\overline {Q4}\) consists of MSKCT constraints
-
The number of multicast sessions M is varied in the range 1−250.×××××
-
the number of antennas on-board S is varied in the range 1−20.
-
the number of users K in the service area is varied in the range 1−500.
-
the number of available sub-channels C is varied in the range 1−32.
-
the number of available sub-channels T is varied in the range 1−24.
8 Proposed solution method: branching schemes and a presolving linearization-based reformulation
-
Presolving×
-
Branching
-
Separating cuts
-
Domain propagation
-
Primal heuristics
8.1 Presolving reformulation linearization for a particular quadratic constraint set \({\mathcal {H}\mathcal {A}\mathcal {P}}^{Eff}_{MBQCP}\)
8.2 Branch and bound-based solution framework
8.3 Branching
-
\(\mathcal {B}\) is the set of binary variables in \({\mathcal {H}\mathcal {A}\mathcal {P}}^{Eff}_{MBQCP}\),
-
\(\ddot {q}^{0}_{j}\) is a function that is directly dependent on and proportional to the dual bound improvement \(\ddot {\Delta }^{0}_{j}\) over the parent subproblem’s relaxation \(\mathcal {Q}_{relax}\) by setting \(\ddot {x}_{j}=0\),
-
\(\ddot {q}^{1}_{j}\) is a function that is directly dependent on and proportional to the dual bound improvement \(\ddot {\Delta }^{1}_{j}\) over the parent subproblem’s relaxation \(\mathcal {Q}_{relax}\) by setting \(\ddot {x}_{j}=1\),
-
\(\overline {\epsilon } \) which is a very small positive constant which is necessary to compare \(\left (\ddot {\Delta }^{0}_{j},\ddot {\Delta }^{1}_{j}\right)\) and \(\left (\ddot {\Delta }^{0}_{k},\ddot {\Delta }^{1}_{k}\right)\) and is set by default to \(\overline {\epsilon } =10^{-6}\) in SCIP.
8.3.1 Random branching
8.3.2 Most infeasible branching
8.3.3 Pseudocost branching
8.3.4 Strong branching
8.3.5 Hybrid strong/pseudocost branching
8.3.6 Reliability branching
-
\(\hat {\gamma }^{max}_{SB}\) is the number of simplex iterations for the strong branching done in \(\mathcal {Q}\)
-
\(\hat {\gamma }_{LP}\) is the number of regular simplex iterations
-
csbiterquot is maximal fraction of strong branching LP iterations compared to node relaxation LP iterations,
-
\(\hat {\gamma }_{fixed}\) is a fixed number that can be pre-set.
8.3.7 Inference branching
-
\(\ddot {\Phi }^{1}_{j}\) and \(\ddot {\Phi }^{0}_{j}\) are the total deductions by setting the binary variable \(\ddot {x}_{j}\) to 1 or 0 respectively,
-
\(\ddot {\nu ^{1}_{j}}\) and \(\ddot {\nu ^{0}_{j}}\) are the numbers of corresponding subproblems for which domain propagation has been applied.
8.3.8 Cloud branching
8.4 Computational experiments, results, and discussions
Parameter | Value |
---|---|
Solving time limit | 10 min |
LP iteration limit per node | 105 iterations |
BnB node limit | 107 nodes |
Feasibility tolerance | 1−12 |
Integrality tolerance | 1−7 |
Parameter | Value |
---|---|
Number of multicasting sessions (M) | 2 |
Number of antennas on board (S) | 7 |
Number of users in the service area (K) | 10 |
Number of available subchannels (C) | 3 |
Number of available time slots (T) | 2 |
HAP height | 20 km |
Degree of antenna beam footprint overlap | 105% |
HAP antenna footprint radius (rfootprint) | 500 m |
HAP antenna side lobe level | − 40 dB |
SINR threshold \(\left (\gamma ^{th}_{m,i}\right)\) | 35 |
Noise power spectral density (No) | − 173 dBm/Hz |
Maximum capacity requirements \(\left ({R^{max}_{m}}\right)\) | 20 Mbps |
Minimum capacity requirements \(\left ({R^{min}_{m}}\right)\) | 10 Mbps |
Carrier Frequency | 2.1 GHz |
Total HAP Power \(\left (P^{Total}_{PF}\right)\) | 1 Watt |
OFDMA frame length | 20 ms |
Total Bandwidth | 15 MHz |
Rice Factor (dB) | 20 dB |
Rain Attenuation Factor (χ) | 3 dB/Km |
Set of values for the user-over-session priority levels (ρm,k) | ρm,k∈{1,2,3,4,5} |
The binary constants indicating the admission request | |
of user k for session m (λm,k) | λm,k=1∀ m,k |
User antenna diameter \(\left (D^{Ant}_{user}\right)\) | 0.75 m |
8.5 Computational experiments and results: reformulation linearization at presolving phase
8.6 Computational experiments and results: branching schemes
-
The maximum value for the reliability threshold is \(\eta ^{max}_{rel}=5\),
-
the minimum value for the reliability threshold is \(\eta ^{min}_{rel}=1\),
-
\(\hat {\gamma }_{fixed}=0\) in Equation (5.8) in [28],
-
maximum size of the set of strong branching candidates, \(\overline {\mathit {F}} =15\),
-
maximum number of strong branching simplex iterations per branching variable is \(\hat {\gamma }_{sbiterbrancand}=100\),
-
the ratio csbiterquot in Equation (5.8) in [28] is set to csbiterquot=0.05 and csbiterquot=0.2 for two different experiments.