Given the user association
and the backhaul bandwidth allocation factor
, the optimization problem
is transformed into a power allocation problem
, as follows:
Given a fixed power allocation
and a backhaul bandwidth allocation factor
, the optimization problem
is transformed into a user association problem
, as follows:
Given the user association
and the fixed power allocation
, the optimization problem
is transformed into a backhaul bandwidth allocation problem
, as follows:
4.1. Power Allocation Based on Successive Convex Approximation
Given the user association matrix
and the backhaul bandwidth allocation factor
, the original optimization problem
is transformed into a power allocation subproblem
. The convexity of the power constraint (18b) is straightforward to verify. Since the objective function (18a), constraints (18c), and (18d) are non-convex, the optimization problem
is still non-convex. To solve the non-convex problem
, the Dinkelbach transformation method and successive convex approximation (SCA) method are used to transform it into a series of convex subproblems. Specifically, the access link rate from the mmWave UBS cluster
to UE
k, as well as from the mmWave UBS
n to UE
k, is relaxed and reformulated into convex functions. The access link rate from the mmWave UBS cluster
to UE
k can be rewritten as
The access link rate from mmWave UBS
n to UE
k can be rewritten as
where
It can be readily demonstrated that
,
,
, and
are concave functions. Consequently, both
and
are the difference of concave functions. The optimization problem
represents a typical differential convex programming problem. Utilizing the first-order Taylor approximation, the following relaxed upper bounds for
and
can be derived:
where ∇ denotes the gradient operation. Each element of
and
can be divided into
Let
denote the lower bound of the UE rate
, and
denote the upper bound of the UE rate
, respectively; then,
The upper and lower bounds are attained if and only if
. Incorporating
and
into the optimization problem
, the problem
can be reformulated as
It is evident that the optimization problem
falls into the category of typical fractional programming, characterized by a concave numerator, which stems from the concavity of the function
, retaining its concavity when summed, whereas the denominator is convex. Additionally,
is convex with respect to the continuous variable
, thereby ensuring that the feasible solution set defined by the constraints (33b), (33c), and (33d) is convex. Consequently, according to Theorem 1, the Dinkelbach transformation method can be employed to convert it into a more tractable form.
It is evident that the optimization problem
is a convex optimization problem. The reason is that the objective function (34a) is concave with respect to the continuous variable
. Additionally, the feasible solution set defined by the constraints (34b), (34c), and (34d) is convex. The optimization problem
can be efficiently solved using the interior point method [
45,
46], and the detailed procedure is outlined in Algorithm 1.
Algorithm 1 Power Allocation Algorithm Based on Dinkelbach Transformation and SCA Method |
- 1:
Initialization: Minimum convergence threshold , maximum number of iterations , number of iterations . - 2:
Dinkelbach transformation method - 3:
repeat - 4:
Given , solve the optimization problem using the interior point method to obtain ; - 5:
Update ; - 6:
Update . - 7:
until or . - 8:
Output: The optimal power allocation .
|
4.2. User Association Based on Energy Efficiency Maximization in Cell-Free mmWave UAV Network
Given a fixed power allocation and a backhaul bandwidth allocation factor , the optimization problem is transformed into a user association problem . This subproblem addresses the formation of UBS clusters in a cell-free mmWave network. This goal is pursued by simultaneously increasing the UE rate and minimizing power consumption. In practice, prior to the formation of cell-free clusters, it is not feasible to precisely compute the rate that UE k obtains from a cell-free cluster. However, we can utilize the data rate from the cellular network architecture to roughly estimate the achievable data rate when UE k is associated with a single UBS. Therefore, is employed as an approximation for the rate of UE k, where , .
From the perspective of the UEs, UEs naturally prefer mmWave UBSs that offer high data rates and low power consumption. For each UE
k, the utility derived from associating with mmWave UBS
n can be expressed as
. If
, then
, denoting the rate achieved by UE
k when associated with mmWave UBS
n. Conversely, if
, it indicates that UE
k is not associated with mmWave UBS
n, resulting in
. From the perspective of the mmWave UBS, the selection is biased towards UEs that offer high data rates with low energy consumption. In the process of user association, due to the difficulty in predicting the rate received by UE
k from its cell-free cooperative UBS cluster, we have decided to remove the original constraint (19d) and instead utilize the decision condition outlined in Algorithm 2 to guide our decision making. Based on this principle, the user association optimization problem can be formulated as follows:
Algorithm 2 User Association Algorithm Based on Energy Efficiency Maximization in Cell-Free mmWave UAV Network |
- 1:
Input: Power allocation matrix and backhaul bandwidth allocation factor . - 2:
Initialization: The Lagrange multipliers are zero vectors. - 3:
for each UE do - 4:
while and do - 5:
Calculate according to Equation (42); - 6:
Update using according to Equation (41). - 7:
for each mmWave UBS do - 8:
if then - 9:
. - 10:
end if - 11:
Set , update . - 12:
repeat - 13:
Update , , according to Equations (43)–(45). - 14:
until Convergence. - 15:
end for - 16:
end while - 17:
end for - 18:
Output: The user association matrix .
|
The problem
is a non-convex 0–1 integer programming problem. It poses significant challenges due to its non-convex nature. To address this, the problem can be approached using the relaxation method combined with the Lagrangian method. If the binary variable
is relaxed to a continuous variable such that
, the optimization problem
is transformed into
Given a fixed power allocation and bandwidth allocation factor, any term independent of
is treated as a constant. The objective function of
in (36a) is a linear function of
, while the constraints in (36b)–(36e) evidently form a convex set with respect to
. The convexity of
arises from the removal of the constraint (36e). Although this operation seemingly expands the constraint set, we have incorporated an additional verification step in Algorithm 2 to check whether UE satisfies the QoS requirements, which essentially re-introduces the effect of the constraint (19d). Consequently, we consider the non-convexity issue of
to be resolved. Therefore, it can be demonstrated that the optimization problem
is a convex optimization problem with respect to the continuous variable
. Subsequently, the derivation will show that the solution obtained after relaxing the variables remains the optimal solution to the original problem
. By employing Lagrangian pairwise decomposition, the Lagrangian function for the problem
is formulated as
where
,
, and
are the dual variables associated with the constraints (36b), (36c), and (36d), respectively. The dual problem of
can be expressed as
where
The first-order partial derivatives of
with respect to
is
Define the elements of the user association matrix
in the subproblem
as those that satisfy the following conditions:
where
Equation (
41) can be considered a judgment criterion for UEs to determine the optimal mmWave UBS. Additionally, the Lagrange multipliers can be updated using the subgradient method, which can be expressed as
where
.
,
and
denote the step size. By updating the Lagrangian multipliers, the dual problem becomes globally optimal when the multipliers converge. Slater’s condition is a suitable constraint qualification for concave maximization problems subject to convex constraints [
42,
45,
47]. When Slater’s conditions are satisfied and the primal problem is convex, a strong duality is established. It is evident, based on the problem formulation, that the feasible region is proven to be a convex set. Furthermore, the constraint function (
36a) has been verified to be convex. More importantly, we can readily identify a specific solution
that is neither zero nor one, yet strictly satisfies all the constraint conditions. Consequently, we can confidently assert that Slater’s condition holds in the problem
.
The user association algorithm based on cell-free and maximum energy efficiency is summarized by Algorithm 2. As described in Algorithm 2, UEs sequentially select their associated UBSs. Each always chooses up to UBSs with the highest utility function values for association. Provided that the selected UBSs can fulfill the QoS requirements of , the process then proceeds to associate the next UE with its respective UBSs.
4.3. Backhaul Link Bandwidth Allocation Factor Optimization
After completing the mmWave UBS clustering, the user association matrix
is obtained. Subsequently, the backhaul bandwidth allocation factor
is determined. With the fixed power allocation results and the established user association matrix, the optimization problem
can be simplified as
. The objective function of the optimization problem
can be expressed as
It is evident that the objective function of the optimization problem
is a monotone decreasing function. Therefore, maximizing this function is equivalent to maximizing
. The constraints for the optimization problem
are subsequently reformulated. From the constraint (20b), the following can be derived:
Based on the constraint (20c), it is obtained that
Therefore, a closed-form expression for the backhaul bandwidth allocation factor
can be obtained.
Simultaneously, it needs to satisfy
where
The optimization process for the backhaul bandwidth allocation factor
is outlined in Algorithm 3. In this process, each mmWave UBS
computes the values of
and
per Equations (51) and (52). These values are subsequently communicated to the HAPS-SMBS. The HAPS-SMBS then selects the maximum
as the optimal bandwidth allocation factor
. This selected
is broadcast to allocate bandwidth for the backhaul link between the HAPS-SMBS and each UBS. Simultaneously, the factor
is broadcast to manage bandwidth allocation for the access link between each UBS and UE.
Algorithm 3 Backhaul Bandwidth Factor Optimization |
- 1:
for each mmWave UBS do - 2:
Calculate and according to Equations (51) and (52) and feed back to HAPS-SMBS. - 3:
end for - 4:
Find and satisfies in HAPS-SMBS side; - 5:
Use as the optimal backhaul bandwidth allocation factor; - 6:
Broadcast to the backhaul link and to the access link. - 7:
Output: The optimal backhaul bandwidth allocation factor and .
|
4.4. Joint User Association, Backhaul Bandwidth, and Power Allocation Alternate Optimization Based on Maximum Energy Efficiency
After providing solutions for each subproblem, the overall algorithm for solving the optimization problem is presented. Initially, the backhaul bandwidth allocation factor and power allocation are initialized, with each HAPS-SMBS uniformly allocating transmission power to each UBS on the backhaul link. During each iteration, the process involves sequential optimization of the three variables: user association, backhaul bandwidth allocation factor, and power allocation. Each variable is optimized in turn, while the other two variables are held constant, as detailed in Algorithm 4.
In the
iteration of Algorithm 4, given
, the power allocation optimization is performed, and the power optimization matrix
is updated by executing Algorithm 1. Next, given
, the mmWave UBS clustering is performed first by executing Algorithm 2 to obtain the user association matrix
. Finally, with
fixed, Algorithm 3 is executed. Additionally, each mmWave UBS calculates
and
according to Equations (51) and Equations (52), respectively. These values are then fed back to the HAPS-SMBS, which selects the maximal
as the optimal bandwidth allocation factor
. The HAPS-SMBS broadcasts
for use in the bandwidth allocation of the backhaul link between the HAPS-SMBS and each UBS, and broadcasts
for the access link bandwidth allocation between the UBS and UE. As the number of iterations increases,
monotonically increases, and since an upper bound exists, the iterative process of Algorithm 4 is guaranteed to eventually converge.
Algorithm 4 Joint User Association, Backhaul Bandwidth, and Power Allocation Alternate Optimization Algorithm Based on Energy Efficiency Maximization |
- 1:
Input: UBS maximal number of associations , UBS maximal number of UEs served , UE QoS requirement value , maximal number of iterations , convergence threshold . - 2:
Initialization: Transmission power , backhaul bandwidth allocation factor , and number of iterations . The HAPS-SMBS distributes the transmission power uniformly for each UBS. Each UE k establishes associations with the top UBSs that are nearest in distance. Calculate and according to Equations ( 10) and ( 14). And calculate . - 3:
while && do - 4:
Given , perform Algorithm 1 to update the power allocation matrix ; - 5:
Given , execute Algorithm 2 to update the user association matrix ; - 6:
Given , perform Algorithm 3 to update the backhaul bandwidth allocation factor and ; - 7:
Update . - 8:
end while - 9:
Output: The optimal user association , backhaul bandwidth allocation factor , and power allocation .
|
4.5. Algorithm Complexity
The computational complexity of the proposed algorithm is evaluated as follows: Since the formulated problem
is not convex, the only way to obtain the optimal solution is to use the exhaustive algorithm (EA). For each iteration, UE and UBS need to compute their respective utility functions and perform pairing based on these functions. On the UE side, establishing associations with all potential pairing partners requires
computations. Considering that there are a total of
K UEs in the system, the computational complexity of the entire process can be denoted as
. Therefore, the computational complexity of Algorithm 2 is
[
41,
42]. Consequently, the overall complexity of Algorithm 2 is
, where
denotes the number of iterations within Algorithm 2. In comparison, the complexity of the EA increases exponentially with the number of UEs and mmWave UBSs, highlighting the efficiency of Algorithm 2 in significantly reducing computational complexity relative to the EA. The computational complexity in Algorithm 3 is negligible [
40,
41]. For power allocation optimization, Algorithm 1 employs the interior point method, resulting in a computational complexity of
based on the result of [
45,
46], where
represents the number of iterations in Algorithm 1. The total complexity of Algorithm 4 is primarily dependent on the user association and power allocation phases, which can be expressed as
, with
representing the number of iterations of Algorithm 4. When the numbers of UEs and UBSs increase, the complexity of the EA increases exponentially, so the complexity of the EA is much larger than the complexities of the proposed algorithms.