# Ultrahigh-Dimensional Model and Optimization Algorithm for Resource Allocation in Large-Scale Intelligent D2D Communication System

Authors: Minxin Liang; Jiandong Liu; Jinrui Tang; Ruoli Tang
Journal: Complexity
 (2021)

---

## Abstract

The optimal resource allocation in the large-scale intelligent device-to-device (D2D) communication system is of great importance for improving system spectrum efficiency and ensuring communication quality. In this study, the D2D resource allocation is modelled as an ultrahigh-dimensional optimization (UHDO) problem with thousands of binary dimensionalities. Then, for efficiently optimizing this UHDO problem, the coupling relationships among those dimensionalities are comprehensively analysed, and several efficient variable-grouping strategies are developed, i.e., cellular user grouping (CU-grouping), D2D pair grouping (DP-grouping), and random grouping (R-grouping). In addition, a novel evolutionary algorithm called the cooperatively coevolving particle swarm optimization with variable-grouping (VGCC-PSO) is developed, in which a novel mutation operation is introduced for ensuring fast satisfaction of constraints. Finally, the proposed UHDO-based allocation model and VGCC-PSO algorithm as well as the grouping and mutation strategies are verified by a comprehensive set of case studies. Simulation results show that the developed VGCC-PSO algorithm performs the best in optimizing the UHDO model with up to 6000 dimensionalities. According to our study, the proposed methodology can effectively overcome the “curse of dimensionality” and optimally allocate the resources with high accuracy and robustness.


---

## Body

## 1. Introduction

Due to the fast development of cellular communication networks, the complexity of net structure and user number explosively increases in recent years. As a result, the device-to-device (D2D) communication technology is developed and plays an increasingly important role in the modern 5G cellular networks [1, 2]. However, due to the fast growing cellular users and high requirement for quality of service (QoS), the lack of spectrum resource becomes one of the main reasons which severely restricts the development of modern communication network [3, 4].In the D2D communication system, two types of user equipment nearby (namely, D2D-pair and DP) can directly communicate under the control of enhanced-Node B (eNB) [5]. However, the direct communication of DP always requires to reuse the physical resource blocks (PRBs) of the traditional cellular users (CUs). In order to obtain promising performance on spectrum efficiency and communication quality, the aforementioned PRB of CU should be optimally allocated to each DP. As a result, the resource allocation model and optimization algorithm are hot topics in the field of D2D communication in recent years [6–9]. For example, Li et al. developed a nonconvex mixed-integer nonlinear programming (MINLP) problem-based model to minimize the mobile power consumption to obtain efficient resource allocation solution and also ensured the QoS and high communication rate at the same time [10]. Su et al. proposed an approach to maximize the total D2D groups capacity by considering the requirement of QoS and energy causality constraints. Simulation results verified the effectiveness of their methodology [11]. In order to reduce the cross-tier interference in D2D communication, Khazali et al. proposed a fractional frequency reuse (FFR)-based spectrum partitioning scheme. In Khazali et al.’s study, they also modelled the spectral efficiency as an optimization problem, which can be effectively solved by employing iterative algorithms [12]. Mohamad et al. proposed a dynamic sectorization method in which eNB can vary the number of sectors dynamically and allocated the resource block to D2D users. According to their study, the signal-to-interference-noise-ratio (SINR) and the network overall performance were improved [13]. Amin et al. proposed a resource allocation algorithm based on the so-called Q-learning, in which the multiagent learners from multiple D2D users were created, and the system throughput was determined by the state-learning of Q value list. According to their study, the system throughput was effectively maximized by controlling the D2D users’ power, and a fine QoS of cellular users was also ensured [14].In this study, the resource allocation problem in an intelligent D2D communication system with large number of users is addressed. To be specific, by describing the communication constraints as penalty functions, the aforementioned resource allocation is modelled as a binary optimization problem with ultrahigh dimensionality, called the binary large-scale global optimization (BLSGO) problem in this study. Then, considering the consequent “curse of dimensionality,” the coupling relationships among the thousands of dimensionalities are comprehensively analysed and some efficient variable-grouping strategies are developed, i.e., the cellular user grouping (CU-grouping), D2D pair grouping (DP-grouping), and random grouping (R-grouping). In addition, a novel swarm-intelligence-based algorithm, namely, cooperatively coevolving particle swarm optimization with variable-grouping (VGCC-PSO) is developed, in which an efficient mutation operation is also introduced for rapidly escaping the punishment of penalty function and speeding up the convergence process. Finally, the proposed model and optimization methodologies are comprehensively verified by case studies.The contributions of this paper can be summarized as follows. Firstly, the BLSGO-based resource allocation model for the intelligent D2D communication system is established. Secondly, the variable-grouping strategies including the CU-grouping, DP-grouping, and R-grouping are developed. Finally, a novel VGCC-PSO algorithm is proposed and employed to optimize the aforementioned BLSGO-based model.The rest of this paper is organized as follows. In Section2, the ultrahigh dimensional resource allocation model is developed. The corresponding constraints and penalty functions as well as the encoding scheme for defining optimization vector are also discussed in this section. In Section 3, the variable-coupling relationships are comprehensively analysed, and the VGCC-PSO with different variable-grouping strategies and mutation operation is developed. Then, in Section 4, the effectiveness of the proposed variable-grouping strategies and mutation operation is tested. In Section 5, the proposed model and optimization methodologies are verified by a comprehensive set of case studies. Finally, this paper is concluded in Section 6.


## 2. Ultrahigh-Dimensional Resource Allocation Model

### 2.1. Resource Allocation in D2D Communication

In an intelligent D2D communication system, the allocation of PRB is of great importance for improving system spectrum efficiency and ensuring communication quality. In order to optimally allocate the CU resources to DP, an efficient offline model for evaluating the cost of each allocation solution is required [15].For a cellular network of LTE-advance systems, assume the eNB locates at the center of a region, in which all the CUs and DPs are randomly distributed. DenoteC = {CUn|n = 1, 2, …, N} as the set of CU, and denote D = {DPm|m = 1, 2, …, M} as the set of DP. The resource allocation principle employed in this study is defined as follows: on the one hand, the PRB of each CU should be reused by only one DP; on the other hand, each DP can reuse more than one CUs’ PRB (but at least one). Schematic of the evaluated D2D communication system is illustrated as Figure 1.Figure 1
Schematic of the D2D communication system.In the D2D communication system, an efficient resource allocation solution is to maximize the system energy efficiency by allocating all the CUs’ PRB to each DP while satisfying some constraints. The energy efficiency to be maximized can be formulized as follows:(1)ηe=∑m=1M∑n=1Nxm,n⋅Rm,n∑m=1M∑n=1Nxm,n⋅Pm,n+Pc,where ηe represents the system energy efficiency; xm,n is the binary variable, xm,n = 1 denotes the PRB of CUn which is reused by DPm, xm,n = 0 denotes the opposite, Rm,n, which is formulized as equation (2), represents the transmission speed of DPm when reusing the PRB of CUn, Pm,n represents the transmission power of DPm when reusing the PRB of CUn; and Pc represents the circuit power consumption of DPm.(2)Rm,n=log21+Pm,n⋅HmPn⋅Hn,m+n0,where Hm represents the channel gain from DP transmitter DTm to DP receiver DRm; Pn represents the transmission power of CUn; Hm,n represents the channel gain from DTm to CUn; and n0 represents the channel noise power under the effect of white Gaussian noise.According to reference [16], the maximization of energy efficiency ηe is equal to the minimization of the following equation:(3)fmin=∑m=1M∑n=1Nxm,n⋅Hn,m⋅Hm,nHm⋅Hn,where Hn represents the channel gain from CUn to eNB and Hn,m represents the channel gain from CUn to DRm. The channel gains here (Hn, Hm, Hn,m, and Hm,n) are all calculated as H = 10(−PL−SHD)/10, where PL represents the path loss and SHD represents the lognormal fading between each transmitter and receiver.As mentioned above, the PRB of each CU should be reused by only one DP and each DP should be allocated with one or more CUs’ PRB. As a result, the overall allocation model can be formulized as the following constrained optimization problem:(4)minxm,nf=∑m=1M∑n=1Nxm,n⋅Hn,m⋅Hm,nHm⋅Hns.t.xm,n∈0,1∑m=1Mxm,n=1,n=1,2,…,N∑n=1Nxm,n≥1,m=1,2,…,M.


### 2.2. Encoding Scheme

As shown in equation (4), the parameters to be optimized for obtaining optimal resource allocation are the N×M binary variables xm,n (m = 1, 2, …, M; n = 1, 2, …, N). In this study, the direct encoding scheme is employed, i.e., all the N×M binary variables xm,n are directly employed to combine the optimization vector x⟶, which is formulized as follows:(5)x⟶=x1,1,x1,2,…,x1,N,…,xM,1,xM,2,…,xM,N.Note that eachxm,n (m = 1, 2, …, M; n = 1, 2, …, N) in equation (5) is a binary variable, which indicates whether CUn is reused by DPm. Obviously, dimensionality of the optimization vector x⟶ is equal to N×M. This implies that the problem dimensionality (or complexity) will become extremely high when N and M are large. For example, assume that a D2D communication system contains 100 CU (i.e., N = 100) and 20 DP (i.e., M = 20). Then, dimensionality of the model will become N×M = 2000. Obviously, complexity of this 2000-dimensional problem is extremely high because of the “curse of dimensionality.” As a result, an effective optimization algorithm is required to solve this BLSGO problem.Note that in this study, the continuous evolutionary algorithm, namely, VGCC-PSO is developed and employed to optimize the variables listed in equation (5). As a result, all the binary variables xm,n are bounded within the interval [0, 100]. The encoding scheme is defined as follows: for the variable xm,n, encode xm,n to 0 when it belongs to [0, 50) in VGCC-PSO; otherwise, when xm,n belongs to [50, 100] in VGCC-PSO, encode it to 1.


### 2.3. Ultrahigh-Dimensional Model for D2D Resource Allocation

In order to optimize the variables in equation (5) using swarm-intelligence-based algorithms, the constraints listed in equation (4) are transformed into penalty function in our model. That is to say, the constrained problem shown in equation (4) is transformed into an unconstrained problem by defining the following penalty function:(6)fp=λ⋅N1+N2,where λ represents the penalty factor which is used to control the penalty intensity; N1 denotes the number of CU which does not satisfy the second constraint in equation (4), i.e., ∑m=1Mxm,n=1, (n = 1, 2, …, N); and N2 denotes the number of DP which does not satisfy the third constraint in equation (4), i.e., ∑n=1Nxm,n≥1, (m = 1, 2, …, M). Note that for a certain solution x⟶, the values of N1 and N2 can be calculated by decoding each dimensionality of x⟶.By introducing the penalty function, the overall resource allocation model can be formulized as(7)minxm,nf=∑m=1M∑n=1Nxm,n⋅Hn,m⋅Hm,nHm⋅Hn+λ⋅N1+N2.


## 2.1. Resource Allocation in D2D Communication

In an intelligent D2D communication system, the allocation of PRB is of great importance for improving system spectrum efficiency and ensuring communication quality. In order to optimally allocate the CU resources to DP, an efficient offline model for evaluating the cost of each allocation solution is required [15].For a cellular network of LTE-advance systems, assume the eNB locates at the center of a region, in which all the CUs and DPs are randomly distributed. DenoteC = {CUn|n = 1, 2, …, N} as the set of CU, and denote D = {DPm|m = 1, 2, …, M} as the set of DP. The resource allocation principle employed in this study is defined as follows: on the one hand, the PRB of each CU should be reused by only one DP; on the other hand, each DP can reuse more than one CUs’ PRB (but at least one). Schematic of the evaluated D2D communication system is illustrated as Figure 1.Figure 1
Schematic of the D2D communication system.In the D2D communication system, an efficient resource allocation solution is to maximize the system energy efficiency by allocating all the CUs’ PRB to each DP while satisfying some constraints. The energy efficiency to be maximized can be formulized as follows:(1)ηe=∑m=1M∑n=1Nxm,n⋅Rm,n∑m=1M∑n=1Nxm,n⋅Pm,n+Pc,where ηe represents the system energy efficiency; xm,n is the binary variable, xm,n = 1 denotes the PRB of CUn which is reused by DPm, xm,n = 0 denotes the opposite, Rm,n, which is formulized as equation (2), represents the transmission speed of DPm when reusing the PRB of CUn, Pm,n represents the transmission power of DPm when reusing the PRB of CUn; and Pc represents the circuit power consumption of DPm.(2)Rm,n=log21+Pm,n⋅HmPn⋅Hn,m+n0,where Hm represents the channel gain from DP transmitter DTm to DP receiver DRm; Pn represents the transmission power of CUn; Hm,n represents the channel gain from DTm to CUn; and n0 represents the channel noise power under the effect of white Gaussian noise.According to reference [16], the maximization of energy efficiency ηe is equal to the minimization of the following equation:(3)fmin=∑m=1M∑n=1Nxm,n⋅Hn,m⋅Hm,nHm⋅Hn,where Hn represents the channel gain from CUn to eNB and Hn,m represents the channel gain from CUn to DRm. The channel gains here (Hn, Hm, Hn,m, and Hm,n) are all calculated as H = 10(−PL−SHD)/10, where PL represents the path loss and SHD represents the lognormal fading between each transmitter and receiver.As mentioned above, the PRB of each CU should be reused by only one DP and each DP should be allocated with one or more CUs’ PRB. As a result, the overall allocation model can be formulized as the following constrained optimization problem:(4)minxm,nf=∑m=1M∑n=1Nxm,n⋅Hn,m⋅Hm,nHm⋅Hns.t.xm,n∈0,1∑m=1Mxm,n=1,n=1,2,…,N∑n=1Nxm,n≥1,m=1,2,…,M.


## 2.2. Encoding Scheme

As shown in equation (4), the parameters to be optimized for obtaining optimal resource allocation are the N×M binary variables xm,n (m = 1, 2, …, M; n = 1, 2, …, N). In this study, the direct encoding scheme is employed, i.e., all the N×M binary variables xm,n are directly employed to combine the optimization vector x⟶, which is formulized as follows:(5)x⟶=x1,1,x1,2,…,x1,N,…,xM,1,xM,2,…,xM,N.Note that eachxm,n (m = 1, 2, …, M; n = 1, 2, …, N) in equation (5) is a binary variable, which indicates whether CUn is reused by DPm. Obviously, dimensionality of the optimization vector x⟶ is equal to N×M. This implies that the problem dimensionality (or complexity) will become extremely high when N and M are large. For example, assume that a D2D communication system contains 100 CU (i.e., N = 100) and 20 DP (i.e., M = 20). Then, dimensionality of the model will become N×M = 2000. Obviously, complexity of this 2000-dimensional problem is extremely high because of the “curse of dimensionality.” As a result, an effective optimization algorithm is required to solve this BLSGO problem.Note that in this study, the continuous evolutionary algorithm, namely, VGCC-PSO is developed and employed to optimize the variables listed in equation (5). As a result, all the binary variables xm,n are bounded within the interval [0, 100]. The encoding scheme is defined as follows: for the variable xm,n, encode xm,n to 0 when it belongs to [0, 50) in VGCC-PSO; otherwise, when xm,n belongs to [50, 100] in VGCC-PSO, encode it to 1.


## 2.3. Ultrahigh-Dimensional Model for D2D Resource Allocation

In order to optimize the variables in equation (5) using swarm-intelligence-based algorithms, the constraints listed in equation (4) are transformed into penalty function in our model. That is to say, the constrained problem shown in equation (4) is transformed into an unconstrained problem by defining the following penalty function:(6)fp=λ⋅N1+N2,where λ represents the penalty factor which is used to control the penalty intensity; N1 denotes the number of CU which does not satisfy the second constraint in equation (4), i.e., ∑m=1Mxm,n=1, (n = 1, 2, …, N); and N2 denotes the number of DP which does not satisfy the third constraint in equation (4), i.e., ∑n=1Nxm,n≥1, (m = 1, 2, …, M). Note that for a certain solution x⟶, the values of N1 and N2 can be calculated by decoding each dimensionality of x⟶.By introducing the penalty function, the overall resource allocation model can be formulized as(7)minxm,nf=∑m=1M∑n=1Nxm,n⋅Hn,m⋅Hm,nHm⋅Hn+λ⋅N1+N2.


## 3. Optimization Methodology

In the field of numerical optimization, different kinds of optimization methodologies are developed and employed in solving real-world engineering problems, e.g., the linear programming methods [17], neural network methods [18], evolutionary algorithms [19], and so on. In this study, the cooperatively coevolving algorithms are developed for solving the aforementioned UHDO-based resource allocation model.


### 3.1. Cooperatively Coevolving

The cooperatively coevolving (CC) is a general algorithm framework proposed for solving the high-dimensional optimization problem [20–22]. In basic CC, the D-dimensional problem is decomposed into several subproblems based on the philosophy of “divide and conquer.” Each of these low-dimensional subproblems is solved by a certain algorithm in turn. Then, a D-dimensional individual, namely, context vector is defined to connect these subproblems and ensure the coevolving process. The CC framework has been integrated with different evolutionary algorithms and obtained promising performance on solving high-dimensional problems [20, 23, 24]. Principle of the basic CC framework can be illustrated as the following steps:(1)
For aD-dimensional problem P, initialize the D-dimensional population with NP individuals. Then, decompose the original problem P into K subproblems SPi (i = 1, 2, …, K), i.e., P = [SP1, SP2, …, SPK]. Note that the dimensionality of each subproblem SPi is equal to D/K. For a D-dimensional individual x, x = (x1, x2, …, xK), where xi represents the corresponding variables that belong to the ith subproblem.(2)
Define the context vector as the current global best individualy. Then, the ith subproblem in CC is defined as(8)minfix,y,x∈RS,wherefix,y=fy1,…,yi−1,x,yi+1,…,yK and RS represents the solution space. Start an evolution circle, in which all the subproblems are optimized with a certain algorithm. The context vector y is updated in every iteration.(3)
Proceed another cycle if the stopping criteria are not satisfied; otherwise, stop the cooperative coevolution.Note that, in CC framework, in order to decrease the complexity of high-dimensional problem, the original problem is decomposed into several less difficult subproblems to be solved separately. According to reference [25], the basic CC framework is effective only if any two subproblems have no interaction. In another word, the variable-grouping strategy (means the subordinate relationship between variables and subproblems) significantly affects the performance of CC.


### 3.2. Variable-Grouping Strategy

In order to effectively optimize the ultrahigh-dimensional problem using CC, the coupled (or called nonseparable) variables should be grouped into the same subproblem and coevolved for enough iterations [25]. With regard to the resource allocation model as listed in equation (4), all the optimization variables xm,n (m = 1, 2, …, M; n = 1, 2, …, N) are grouped using the following strategies.


#### 3.2.1. Random Grouping (R-Grouping)

In R-grouping, all the variables are randomly disorganized and grouped into different subproblems. To be specific, flow of R-grouping mechanism is as the following steps:(i)
Firstly, orders of the entireD=N×M dimensionalities in the original model are randomly disorganized.(ii)
Secondly, these disorganized dimensionalities are decomposed intoK = D/s sub-problems. Obviously, each subproblem has s dimensionalities, where the group size s is randomly generated within a predefined set S.(iii)
Finally, the group sizes is dynamically changed during the coevolving process as the following principle: for each coevolving iteration, randomly selected a new s in S if the global optimum is not updated; otherwise, keep the current s value unchanged.Schematic of the R-grouping mechanism is illustrated in Figure2.Figure 2
Schematic of R-grouping.


#### 3.2.2. Cellular User Grouping (CU-Grouping)

As discussed in Section2.2, each optimization variable represents the reusing relationship between a certain CUn and a certain DPm. In CU-grouping, the variables reflecting the relationships between one certain CUn and every DP are grouped into a subproblem and are employed to coevolve for enough iterations. To be specific, the variables for CU1, i.e., x1,1, x2,1, …, xM,1, are regarded as the first subproblem, then the variables for CU2, i.e., x1,2, x2,2, …, xM,2, are regarded as the second subproblem, and so on. Note that in CU-grouping, as each subproblem (or called group) has M dimensionalities, i.e., s = M, the number of subproblems K is equal to D/s=N.Schematic of the CU-grouping mechanism is illustrated in Figure3.Figure 3
Schematic of CU-grouping.


#### 3.2.3. D2D Pair Grouping (DP-Grouping)

Similarly, in DP-grouping, the variables reflecting the relationships between every CUn and one certain DP are grouped into a subproblem. To be specific, the variables for DP1, i.e., x1,1, x1,2, …, x1,N, are regarded as the first subproblem, then the variables for DP2, i.e., x2,1, x2,2, …, x2,N, are regarded as the second subproblem, and so on. Note that in DP-grouping, as each subproblem has N dimensionalities, i.e., s = N, the number of subproblems K is equal to D/s=M.Schematic of the DP-grouping mechanism is illustrated in Figure4.Figure 4
Schematic of DP-grouping.


### 3.3. Mutation Operation

According to the encoding scheme developed in Section2.2, it can be easily concluded that the binary variable xm,n is not related to its specific value within the solution space but is directly decided by whether it is greater than the boundary 50. As a result, the encoding scheme will significantly increase the solution space and complicate the original model. In order to overcome this problem, a novel mutation operation is developed and imposed on all the context vectors of VGCC-PSO.As discussed in Section2, the PRB of each CU should be reused by only one DP, and each DP can reuse more than one CUs’ PRB (but at least one). That is to say, in a feasible solution, there is at most one variable in x1,n, x2,n, …, xM,n (n = 1, 2, …, N) which is greater than 0 at each time (denoted as Constraint I). In addition, there is at least one variable in xm,1, xm,2, …, xm,N (m = 1, 2, …, M) which is greater than 0 at each time (denoted as Constraint II). As Constraints I and II are closely related to the entire variables, most of the solutions in solution space will be infeasible because of these constraints. In order to reduce the model complexity caused by these so many infeasible solutions, the feasible solutions satisfying Constraint I and Constraint II are directly employed as the context vector and inserted into VGCC-PSO population. The proposed mutation operation for context vector is illustrated as the following steps:Step 1. Define parameters Pm1 and Pm2 satisfying Pm1≤Pm2 and Pm1,Pm2∈0,1 to control the mutation probabilities.Step 2. In each iteration, for each of the context vectors in VGCC-PSO, say the ith context vector in the tth iteration CVi (t), randomly generate a mutation variable Pi(t) with the interval [0, 1]. Then, mutate CVi (t) according to the following principles:(i)
IfPi(t) < Pm1, keep CVi (t) unchanged(ii)
IfPm1≤Pit<Pm2, each of the components [x1,n, x2,n, …, xM,n] (n = 1, 2, …, N) is randomly mutated to [r0, r0, …, r0, r1], [r0, …, r0, r1, r0], …, [r0, r1, r0, …, r0] and [r1, r0, r0, …, r0], in which each r0 is randomly generated within [0, 50) and each r1 is randomly generated within [50, 100](iii)
Otherwise (i.e.,Pit≥Pm2), check each of the components [xm,1, xm,2, …, xm,N] (m = 1, 2, …, M) if all the variables are lower than 50, i.e., xm,1, xm,2, …, xm,N are encoded to 0, then randomly set one variable (e.g., xm,n) to r1Step 3. Denote the mutated context vector CVi (t) as CVi-mut (t). Update CVi(t) using CVi-mut (t) if better.Note that the proposed mutation mechanism is only imposed on the context vectors rather than the entire individuals in current population. The reason is that, on the one hand, the mutated context vectors can better guide the other individuals to rapidly satisfy the constraints and thus significantly reduce the scope of solution space. On the other hand, the population diversity will be not destroyed in mutation process.


### 3.4. VGCC-PSO Algorithm

In this study, a novel evolutionary algorithm, namely, VGCC-PSO is developed for optimizing the BLSGO-based allocation model. In VGCC-PSO, the aforementioned variable-grouping strategies and mutation operation are integrated for overcoming the ultrahigh dimensionality characteristic of the model.In VGCC-PSO, the basic CC framework described in Section3.1 is imposed on the PSO algorithm. Then, the R-grouping, CU-grouping, and DP-grouping mechanisms are randomly selected in each iteration as the following steps:Step 1. Set the selection probabilities PR (for R-grouping), PCU (for CU-grouping), and PDP (for DP-grouping), satisfying(9)PR,PCU,PDP∈0,1,PR+PCU+PDP=1.Step 2. In each iteration, randomly generate a variable Pg∈0,1. Then, select a grouping strategy according to the following equation:(10)selectR‐grouping,if0≤pg<PR,select CU‐grouping,ifPR≤pg<PR+PCU,select DP‐grouping,ifPR+PCU≤pg≤1.In addition, in VGCC-PSO, the mutation operation described in Section3.3 is imposed on each of the context vectors in each iteration. Pseudo code of VGCC-PSO is given in Algorithm 1.Algorithm 1: Pseudo code of VGCC-PSO.
Algorithm: VGCC-PSOInitialize aD-dimensional population with NP particles. Initialize p context vectors with the best p particles.repeatRandomly generate a variablePg, then select a variable-grouping strategy using equation (10).Decompose the original optimization vector intoK subproblems according to the selected variable-grouping strategy.Denote thejth subproblem as Pj.foreach subproblem PjdoCoevolve the corresponding dimensionalities ofPj using the CC-based PSO as discussed in our previous work [22].endUpdate the personal best of each particle, and update the context vectors according to reference [22].foreach context vector CVidoMutateCVi to CVi-mut according to the principles developed in Section 3.3.iff (CVi-mut) < f(CVi) thenUpdateCVi using CVi-mut.endUpdate the global best with the best context vector.until the stopping criteria are satisfied


## 3.1. Cooperatively Coevolving

The cooperatively coevolving (CC) is a general algorithm framework proposed for solving the high-dimensional optimization problem [20–22]. In basic CC, the D-dimensional problem is decomposed into several subproblems based on the philosophy of “divide and conquer.” Each of these low-dimensional subproblems is solved by a certain algorithm in turn. Then, a D-dimensional individual, namely, context vector is defined to connect these subproblems and ensure the coevolving process. The CC framework has been integrated with different evolutionary algorithms and obtained promising performance on solving high-dimensional problems [20, 23, 24]. Principle of the basic CC framework can be illustrated as the following steps:(1)
For aD-dimensional problem P, initialize the D-dimensional population with NP individuals. Then, decompose the original problem P into K subproblems SPi (i = 1, 2, …, K), i.e., P = [SP1, SP2, …, SPK]. Note that the dimensionality of each subproblem SPi is equal to D/K. For a D-dimensional individual x, x = (x1, x2, …, xK), where xi represents the corresponding variables that belong to the ith subproblem.(2)
Define the context vector as the current global best individualy. Then, the ith subproblem in CC is defined as(8)minfix,y,x∈RS,wherefix,y=fy1,…,yi−1,x,yi+1,…,yK and RS represents the solution space. Start an evolution circle, in which all the subproblems are optimized with a certain algorithm. The context vector y is updated in every iteration.(3)
Proceed another cycle if the stopping criteria are not satisfied; otherwise, stop the cooperative coevolution.Note that, in CC framework, in order to decrease the complexity of high-dimensional problem, the original problem is decomposed into several less difficult subproblems to be solved separately. According to reference [25], the basic CC framework is effective only if any two subproblems have no interaction. In another word, the variable-grouping strategy (means the subordinate relationship between variables and subproblems) significantly affects the performance of CC.


## 3.2. Variable-Grouping Strategy

In order to effectively optimize the ultrahigh-dimensional problem using CC, the coupled (or called nonseparable) variables should be grouped into the same subproblem and coevolved for enough iterations [25]. With regard to the resource allocation model as listed in equation (4), all the optimization variables xm,n (m = 1, 2, …, M; n = 1, 2, …, N) are grouped using the following strategies.


### 3.2.1. Random Grouping (R-Grouping)

In R-grouping, all the variables are randomly disorganized and grouped into different subproblems. To be specific, flow of R-grouping mechanism is as the following steps:(i)
Firstly, orders of the entireD=N×M dimensionalities in the original model are randomly disorganized.(ii)
Secondly, these disorganized dimensionalities are decomposed intoK = D/s sub-problems. Obviously, each subproblem has s dimensionalities, where the group size s is randomly generated within a predefined set S.(iii)
Finally, the group sizes is dynamically changed during the coevolving process as the following principle: for each coevolving iteration, randomly selected a new s in S if the global optimum is not updated; otherwise, keep the current s value unchanged.Schematic of the R-grouping mechanism is illustrated in Figure2.Figure 2
Schematic of R-grouping.


### 3.2.2. Cellular User Grouping (CU-Grouping)

As discussed in Section2.2, each optimization variable represents the reusing relationship between a certain CUn and a certain DPm. In CU-grouping, the variables reflecting the relationships between one certain CUn and every DP are grouped into a subproblem and are employed to coevolve for enough iterations. To be specific, the variables for CU1, i.e., x1,1, x2,1, …, xM,1, are regarded as the first subproblem, then the variables for CU2, i.e., x1,2, x2,2, …, xM,2, are regarded as the second subproblem, and so on. Note that in CU-grouping, as each subproblem (or called group) has M dimensionalities, i.e., s = M, the number of subproblems K is equal to D/s=N.Schematic of the CU-grouping mechanism is illustrated in Figure3.Figure 3
Schematic of CU-grouping.


### 3.2.3. D2D Pair Grouping (DP-Grouping)

Similarly, in DP-grouping, the variables reflecting the relationships between every CUn and one certain DP are grouped into a subproblem. To be specific, the variables for DP1, i.e., x1,1, x1,2, …, x1,N, are regarded as the first subproblem, then the variables for DP2, i.e., x2,1, x2,2, …, x2,N, are regarded as the second subproblem, and so on. Note that in DP-grouping, as each subproblem has N dimensionalities, i.e., s = N, the number of subproblems K is equal to D/s=M.Schematic of the DP-grouping mechanism is illustrated in Figure4.Figure 4
Schematic of DP-grouping.


## 3.2.1. Random Grouping (R-Grouping)

In R-grouping, all the variables are randomly disorganized and grouped into different subproblems. To be specific, flow of R-grouping mechanism is as the following steps:(i)
Firstly, orders of the entireD=N×M dimensionalities in the original model are randomly disorganized.(ii)
Secondly, these disorganized dimensionalities are decomposed intoK = D/s sub-problems. Obviously, each subproblem has s dimensionalities, where the group size s is randomly generated within a predefined set S.(iii)
Finally, the group sizes is dynamically changed during the coevolving process as the following principle: for each coevolving iteration, randomly selected a new s in S if the global optimum is not updated; otherwise, keep the current s value unchanged.Schematic of the R-grouping mechanism is illustrated in Figure2.Figure 2
Schematic of R-grouping.


## 3.2.2. Cellular User Grouping (CU-Grouping)

As discussed in Section2.2, each optimization variable represents the reusing relationship between a certain CUn and a certain DPm. In CU-grouping, the variables reflecting the relationships between one certain CUn and every DP are grouped into a subproblem and are employed to coevolve for enough iterations. To be specific, the variables for CU1, i.e., x1,1, x2,1, …, xM,1, are regarded as the first subproblem, then the variables for CU2, i.e., x1,2, x2,2, …, xM,2, are regarded as the second subproblem, and so on. Note that in CU-grouping, as each subproblem (or called group) has M dimensionalities, i.e., s = M, the number of subproblems K is equal to D/s=N.Schematic of the CU-grouping mechanism is illustrated in Figure3.Figure 3
Schematic of CU-grouping.


## 3.2.3. D2D Pair Grouping (DP-Grouping)

Similarly, in DP-grouping, the variables reflecting the relationships between every CUn and one certain DP are grouped into a subproblem. To be specific, the variables for DP1, i.e., x1,1, x1,2, …, x1,N, are regarded as the first subproblem, then the variables for DP2, i.e., x2,1, x2,2, …, x2,N, are regarded as the second subproblem, and so on. Note that in DP-grouping, as each subproblem has N dimensionalities, i.e., s = N, the number of subproblems K is equal to D/s=M.Schematic of the DP-grouping mechanism is illustrated in Figure4.Figure 4
Schematic of DP-grouping.


## 3.3. Mutation Operation

According to the encoding scheme developed in Section2.2, it can be easily concluded that the binary variable xm,n is not related to its specific value within the solution space but is directly decided by whether it is greater than the boundary 50. As a result, the encoding scheme will significantly increase the solution space and complicate the original model. In order to overcome this problem, a novel mutation operation is developed and imposed on all the context vectors of VGCC-PSO.As discussed in Section2, the PRB of each CU should be reused by only one DP, and each DP can reuse more than one CUs’ PRB (but at least one). That is to say, in a feasible solution, there is at most one variable in x1,n, x2,n, …, xM,n (n = 1, 2, …, N) which is greater than 0 at each time (denoted as Constraint I). In addition, there is at least one variable in xm,1, xm,2, …, xm,N (m = 1, 2, …, M) which is greater than 0 at each time (denoted as Constraint II). As Constraints I and II are closely related to the entire variables, most of the solutions in solution space will be infeasible because of these constraints. In order to reduce the model complexity caused by these so many infeasible solutions, the feasible solutions satisfying Constraint I and Constraint II are directly employed as the context vector and inserted into VGCC-PSO population. The proposed mutation operation for context vector is illustrated as the following steps:Step 1. Define parameters Pm1 and Pm2 satisfying Pm1≤Pm2 and Pm1,Pm2∈0,1 to control the mutation probabilities.Step 2. In each iteration, for each of the context vectors in VGCC-PSO, say the ith context vector in the tth iteration CVi (t), randomly generate a mutation variable Pi(t) with the interval [0, 1]. Then, mutate CVi (t) according to the following principles:(i)
IfPi(t) < Pm1, keep CVi (t) unchanged(ii)
IfPm1≤Pit<Pm2, each of the components [x1,n, x2,n, …, xM,n] (n = 1, 2, …, N) is randomly mutated to [r0, r0, …, r0, r1], [r0, …, r0, r1, r0], …, [r0, r1, r0, …, r0] and [r1, r0, r0, …, r0], in which each r0 is randomly generated within [0, 50) and each r1 is randomly generated within [50, 100](iii)
Otherwise (i.e.,Pit≥Pm2), check each of the components [xm,1, xm,2, …, xm,N] (m = 1, 2, …, M) if all the variables are lower than 50, i.e., xm,1, xm,2, …, xm,N are encoded to 0, then randomly set one variable (e.g., xm,n) to r1Step 3. Denote the mutated context vector CVi (t) as CVi-mut (t). Update CVi(t) using CVi-mut (t) if better.Note that the proposed mutation mechanism is only imposed on the context vectors rather than the entire individuals in current population. The reason is that, on the one hand, the mutated context vectors can better guide the other individuals to rapidly satisfy the constraints and thus significantly reduce the scope of solution space. On the other hand, the population diversity will be not destroyed in mutation process.


## 3.4. VGCC-PSO Algorithm

In this study, a novel evolutionary algorithm, namely, VGCC-PSO is developed for optimizing the BLSGO-based allocation model. In VGCC-PSO, the aforementioned variable-grouping strategies and mutation operation are integrated for overcoming the ultrahigh dimensionality characteristic of the model.In VGCC-PSO, the basic CC framework described in Section3.1 is imposed on the PSO algorithm. Then, the R-grouping, CU-grouping, and DP-grouping mechanisms are randomly selected in each iteration as the following steps:Step 1. Set the selection probabilities PR (for R-grouping), PCU (for CU-grouping), and PDP (for DP-grouping), satisfying(9)PR,PCU,PDP∈0,1,PR+PCU+PDP=1.Step 2. In each iteration, randomly generate a variable Pg∈0,1. Then, select a grouping strategy according to the following equation:(10)selectR‐grouping,if0≤pg<PR,select CU‐grouping,ifPR≤pg<PR+PCU,select DP‐grouping,ifPR+PCU≤pg≤1.In addition, in VGCC-PSO, the mutation operation described in Section3.3 is imposed on each of the context vectors in each iteration. Pseudo code of VGCC-PSO is given in Algorithm 1.Algorithm 1: Pseudo code of VGCC-PSO.
Algorithm: VGCC-PSOInitialize aD-dimensional population with NP particles. Initialize p context vectors with the best p particles.repeatRandomly generate a variablePg, then select a variable-grouping strategy using equation (10).Decompose the original optimization vector intoK subproblems according to the selected variable-grouping strategy.Denote thejth subproblem as Pj.foreach subproblem PjdoCoevolve the corresponding dimensionalities ofPj using the CC-based PSO as discussed in our previous work [22].endUpdate the personal best of each particle, and update the context vectors according to reference [22].foreach context vector CVidoMutateCVi to CVi-mut according to the principles developed in Section 3.3.iff (CVi-mut) < f(CVi) thenUpdateCVi using CVi-mut.endUpdate the global best with the best context vector.until the stopping criteria are satisfied


## 4. Verification for Variable-Grouping Strategies and Mutation Operation

In this section, efficiency of the proposed variable-grouping strategies and mutation operation is verified by simulation experiments. In the following simulation, the numbers of CU and DP are set to 80 and 20, respectively. The location of each CU, DT, and DR is randomly generated within a hexagon region with the radius of 700 m. As suggested in reference [5], the communication model and parameters employed in the following simulation are chosen in accordance with 3GPP LTE regulation for the OFDMA system. In addition, the path loss model is defined as follows:(11)eNB‐UE:PL=33.65+23.47log10dm,UE‐UE:PL=36.67+19.54log10dm.According to the encoding scheme described in Section2.2, the model dimensionality D in this case is equal to N×M=1600. In this section, the VGCC-PSO algorithm is employed for optimizing this 1600-dimensional problem. In order to verify effectiveness of the proposed variable-grouping strategy and mutation operation, the basic PSO without CC framework, variable-grouping strategy, and mutation operation (denoted as PSO), the CC-based PSO (i.e., without variable-grouping strategy and mutation operation, denoted as CCPSO), the CC-based PSO only integrated with mutation operation (i.e., without variable-grouping strategy, denoted as CCPSOmut), and the CC-based PSO only integrated with variable-grouping strategy (i.e., without mutation operation, denoted as CCPSOvg) are employed for comparison.For all the compared algorithms, the dynamic group sizeS in R-grouping is set as S = {10, 20, 50, 100, 200}. According to our numerical experiments, the selection probabilities for variable-grouping strategies PR, PCU, and PDP are suggested to be set as follows: PR = 0.4, PCU = 0.3, and PDP = 0.3. The penalty factor λ in equation (6) is set to 10000. The probabilities in mutation operation Pm1 and Pm2 are set to 0.3 and 0.6, respectively. The maximum number of fitness evaluations (FEmax) is set to 1×106. The population size is set to 50, and the number of context vectors is set to 5. Results of the simulation experiments are compared in Figure 5 and Table 1.Figure 5
Convergence graphs for optimizing the 1600-dimensional model.Table 1
Optimization results of the compared algorithms.
AlgorithmOptimization resultVGCC-PSO12.7027CCPSO49.3261PSO631.2110CCPSOvg17.4469CCPSOmut27.9705According to the simulation results, the proposed VGCC-PSO algorithm performs the best and obtains the minimum fitness function value of 12.7027. Compared with the CC-based algorithms, the basic PSO without CC framework fails to optimize the 1600-dimensional problem and obtains the worst performance of 631.2110, which is significantly larger than its competitors. This implies that by decomposing the original problem into several low-dimensional subproblems, the CC framework is very efficient on overcoming the ultrahigh dimensional characteristic.By integrating the CC framework, the result obtained by CCPSO is significantly better than that of PSO but worse than the best performer VGCC-PSO. Obviously, the gap between CCPSO and VGCC-PSO shows the efficacy of the developed variable-grouping strategies and mutation operation. To be specific, by integrating the variable-grouping strategies, the CCPSOvg obtains the final result of 17.4469, which significantly outperforms 49.3261 obtained by CCPSO. Rationale behind the achievement is that by integrating the CU-grouping and DP-grouping strategies, the coupled variables are given higher probability to be grouped into the same subproblem and coevolved for enough iterations.By integrating the mutation operation, CCPSOmut obtains the final result of 27.9705, which outperforms 49.3261 obtained by CCPSO. In addition, according to the convergence graph shown in Figure 5, the mutation operation can help the algorithm to fast satisfy the constraints and avoid the punishment brought by penalty function. As discussed above, the developed variable-grouping strategies and mutation operation are efficient on improving the performance of the evolutionary algorithm on solving ultrahigh dimensional problem. To be specific, the variable-grouping strategies can improve the global exploration ability and optimization accuracy, while the mutation operation can significantly accelerate the convergence or satisfaction speed of constraints.


## 5. Simulation Experiments and Analysis

In this section, the performance of VGCC-PSO is empirically evaluated on a comprehensive set of case studies. Parameters setting of VGCC-PSO is the same with Section4. In addition, some state-of-the-art evolutionary algorithms are employed for comparison, including the CPSO-SK [26], CPSO-SK-rg-aw [27], CCPSO2 [28], and CCDE [29]. Parameter settings of these algorithms are following their original studies. The detailed model parameters for each case are listed in Table 2.Table 2
Parameter settings of resource allocation models.
Case numberNumber of CUNumber of DPModel dimensionalityDynamic group size in R-groupingCase 1308240{5, 10, 12, 20, 40}Case 25010500{5, 10, 20, 25, 50}Case 360201200{10, 20, 50, 100, 200}Case 480252000{20, 50, 100, 200, 400}Case 5100404000{20, 50, 100, 200, 500}Case 6120506000{50, 100, 200, 600, 1000}Simulation results of the case studies are listed in Table3, in which the best performance is set in bold. The convergence graphs for each case are plotted in Figure 6.Table 3
Simulation results for Case 1 to 6.
AlgorithmCase 1Case 2Case 3Case 4Case 5Case 6VGCC-PSO10.518210.077118.879413.145530.067348.7768CCDE22.908721.606935.079323.216242.054787.0291CCPSO224.260834.451730.032927.028396.044177.4215CPSO-SK146.3635264.6194613.8953431.42422098.56291602.9015CPSO-SK-rg-aw24.181062.8635130.2828115.9234315.2044321.8840Figure 6
Convergence graphs for Case 1 to 6: (a) Case 1; (b) Case 2; (c) Case 3; (d) Case 4; (e) Case 5; (f) Case 6.
(a)(b)(c)(d)(e)(f)As shown in Table3, the proposed VGCC-PSO obtains the best performance for all the cases. To be specific, for the low-dimensional models (i.e., Cases 1 and 2), the outperformance of VGCC-PSO is not significant compared with that of CCDE, CCPSO2, and CPSO-SK-rg-aw. However, when scale of the D2D communication system becomes large (i.e., the numbers of CU and DP increase to several decades and the model dimensionality increases to more than 1000 in Cases 3 to 6), VGCC-PSO can obtain its efficiency and significantly outperforms the competitors because of the integration of variable-grouping mechanism and mutation operation. For example, in Cases 3 and 4, VGCC-PSO obtains the final results of 18.8794 and 13.1455 for the 1200-dimensional and 2000-dimensional problems, respectively. However, the results obtained by other algorithms are 35.0793 and 23.2162 for CCDE, 30.0329 and 27.0283 for CCPSO2, and 130.2828 and 115.9234 for CPSO-SK-rg-aw. Note that the results obtained by CPSO-SK for Cases 3 and 4 are 613.8953 and 431.4242, which implies that CPSO-SK losses its efficacy and fails to optimize these ultrahigh dimensional problems.In Cases 5 and 6, the model dimensionality increases to 4000 and 6000, and VGCC-PSO is still able to effectively optimize the model and obtains the final results of 30.0673 and 48.7768, which significantly outperforms 42.0547 and 87.0291 by CCDE, 96.0441 and 77.4215 by CCPSO2, 315.2044 and 321.8840 by CPSO-SK-rg-aw, and 2098.5629 and 1602.9015 by CPSO-SK. Note that the final results listed in Table 3 are all lower than the penalty factor λ which is set to 10000 in the simulations. This indicates that because of the application of CC framework, all the algorithms can satisfy the constraints and avoid punishment for each of the ultrahigh-dimensional cases.


## 6. Conclusion

In this study, the ultrahigh dimensional model for resource allocation in a large-scale intelligent D2D communication system is established, and a novel optimization methodology, namely, VGCC-PSO is also developed for optimizing the BLSGO-based model.For a large-scale D2D communication system withN CUs and M DPs, by defining the binary encoding scheme and penalty function, the resource allocation problem is modelled as an unconstrained optimization problem with ultrahigh dimensionalities of N×M. In order to effectively optimize the ultrahigh dimensional model, the CC framework is applied to decompose the original problem and coevolve each subproblem according to the philosophy of “divide and conquer.”For further improving the optimization performance, some efficient variable-grouping strategies like the R-grouping, CU-grouping, and DP-grouping are developed to rearrange and co-optimize the large number of optimization variables. In addition, a novel mutation operation is also developed to accelerate the convergence speed. Simulation results show the effectiveness of these algorithm mechanisms; the integration of variable-grouping strategies can improve global exploration ability and final optimization accuracy, while the mutation operation can significantly accelerate the satisfaction of constraints.Finally, by integrating the CC framework, variable-grouping strategies, and mutation operation, the proposed VGCC-PSO algorithm is empirically evaluated on a comprehensive set of case studies, and some state-of-the-art algorithms are also employed for comparison. Simulation results show that VGCC-PSO performs the best in optimizing the ultrahigh-dimensional model with up to 6000 dimensionalities. In a word, the proposed methodology can effectively overcome the “curse of dimensionality” and optimally allocate the resources in the large-scale intelligent D2D communication system with high accuracy and robustness.



---

*Source: 7321719-2021-08-04.xml*