Sage Journals: Discover world-class research

Abstract

In a multi-heterogeneous network with dense deployment and convergence environment, how to efficiently and reasonably allocate idle spectrum resources of the primary network to meet the diversified business demands of secondary users is a difficult problem. In this article, with the goal of maximizing the total transmission rate and minimizing the total cost, a dual-objective optimization mathematical model for network selection and idle spectrum allocation is established in the context of comprehensive consideration of the diversity of spectrum resource attributes and the diversification of secondary users’ business needs. Based on this, two kinds of technical paths to solve the complex network selection and spectrum allocation problem are applied in this article. The first is the simplification method. By preprocessing of objective function, constraint simplification, and standardization, the complex spectrum allocation problem is transformed into a standard form of the 01 programming problem, and the solution is obtained by an improved Hungarian algorithm. Second, an intelligent optimization algorithm named improved non-dominated sorting genetic algorithm II is proposed, which combines the interference constraints of the primary network and the service quality requirements of the secondary users into the objective value evaluation of non-dominated sorting, and corrects the chromosomes that do not meet the constraints. And then makes a decision selection on the optimal solution set to select a compromise solution. Finally, methods proposed in this article are compared with the multi-objective artificial bee colony algorithm through experiments. Experimental results show that the simplified method has higher efficiency, and the improved non-dominated sorting genetic algorithm II can get higher transmission rate, especially the transmission rate–priority strategy.

Keywords

Heterogeneous network cognitive radio network access spectrum allocation multi-objective optimization

Introduction

With the rapid development of wireless communication technologies and wireless services, the demand for user traffic surges. According to the “5G Vision and Demand White Paper”¹ released by the IMT-2020 (5G) recommendation group, it is expected that the growth of China Mobile’s data traffic will increase by nearly 40,000 times from 2010 to 2030. However, the scarce and low-utilization spectrum resources have become a major bottleneck restricting the development of wireless networks. Through the dense deployment of multi-heterogeneous networks, the use of cognitive radio technology to dynamically access required types of communication spectrum (including high- and low-frequency bands, authorized and unlicensed spectrum, continuous and discontinuous, etc.) can improve data transmission rate and system capacity. It is an effective method to solve the conflict between users’ demand for increased traffic and the shortage of spectrum resources with low utilization rate, and is also the key technology of future 5G networks.^2–4 Cognitive radio technology provides an effective technical means to solve the problem of shortage of spectrum resources and its low utilization rate. The user who obtains the spectrum authorization is called the primary user, and the user who does not receive the spectrum authorization is called the secondary user. The primary user has priority access to the spectrum and can use the spectrum at any time. At the same time, the primary network can transfer or lease the idle licensed frequency band to the secondary user, so that the secondary user can share the licensed frequency band. Most of the research results of cognitive radio mainly focus on the allocation of spectrum resources in a single primary network environment where the attributes of each spectrum resource are approximately the same and no need to consider the heterogeneity of spectrum resources of different primary networks.^5,6 With the development of wireless communication technology and the diversified business needs of users, dense deployment and integration of multiple different types of networks (such as WiFi, cellular, and WiMax) become an important feature of future wireless networks. In this environment, multiple primary networks overlap and have different network characteristics, such as price, bandwidth, delay, and packet loss rate. Different user services also have different requirements. In the environment where the network domain of multiple networks and the user domain with multiple users are coupled and dynamically changed, and the spectrum allocation between different users interacts, how to efficiently and reasonably allocate idle spectrum resources of the primary network for each secondary user is a challenge.

This article studies the diversity of spectrum resource attributes and the diversification of secondary users’ requirements under the heterogeneous network dense deployment environment, and models the spectrum resource allocation problem as a dual-objective optimization problem. That is, the mathematical model is constructed with the goal of maximizing the total transmission rate and minimizing the total cost, along with the user’s business requirements as constraints. In order to solve this multi-constrained spectrum resource allocation problem, we first try to simplify the optimization objects and multiple constraints, and seek a simple polynomial time algorithm. Second, the traditional multi-objective optimization method non-dominated sorting genetic algorithm II (NSGA-II) is improved, including combining the interference constraints and the service quality requirements of the secondary users into the objective value evaluation, and correcting the chromosomes that do not meet the constraints. And then, making a decision selection on the optimal solution set to select a compromise solution.

The remaining sections of this article are organized as follows: next section introduces related works. Section “Network model and problem derivation” gives the network model and the derivation of problems. The simplification method and the improved non-dominated sorting genetic algorithm II (INSGA-II) are introduced in section “Simplification method and improved intelligent optimization algorithm.” Section “Experimental results analysis” gives the experimental results and analysis. Finally, the article is concluded in section “Conclusion.”

Related works

Domestic and foreign scholars have carried out active research works on the network selection and dynamic spectrum allocation, and have achieved many results, mainly based on graph theory,^7–10 spectrum trading,^11–14 game theory,^15–19 and intelligent optimization algorithms.^20–23 They are as follows:

Graph theory–based method: Zhu et al.⁹ proposed a spectrum allocation algorithm using multiple-strategies discrete artificial bee colony algorithm, for the problem that the optimal frequency spectrum allocation strategy under the graph theory spectrum allocation model is difficult and time-consuming to search. In the algorithm, a coarse search strategy with strong global exploration capability was introduced to quickly optimize the initial population at the beginning of the search, and a fine search was performed with high-precision one-dimensional updates later. The graph theory-based approach is simple and easy to implement, and is mostly applicable to static network environments. This means that every change to the topology requires a recalculation of the allocation. If the topology changes frequently, the effectiveness of the algorithm will be greatly challenged.

Spectrum trading–based method: Xie et al.¹⁴ proposed a spectrum allocation algorithm for cognitive wireless networks based on the equilibrium price theory. The algorithm uses two stages of inter-cluster and intra-cluster spectrum allocation to theoretically analyze and derive the mathematical expressions of the relationship between the optimal spectrum price and the number of spectrums, the number of cluster heads and cluster member nodes, the priority level of the node service and the number of communication activities of the node itself at different stages. The method based on spectrum trading is applicable to the application scenario based on the lease relationship between the primary user and the secondary user.

Game theory–based method: Tan et al.¹⁹ proposed two new spectrum-sharing strategies to facilitate the formation of a more flexible and reliable monopoly of spectrum-sharing cooperation among all primary networks. By designing two new spectrum pricing strategies for each primary network, multiple primary networks with different interests can form a certain level of cooperative monopolies in the process of spectrum-sharing a single secondary network, thereby improving their long-term transmission utility.

Intelligent optimization method: comprehensively considering the allocation fairness and spectrum resource requirements of inter-cluster code division, Chuanbao et al.²⁰ converted the maximizing code subdivision spectrum resource efficiency and allocation fairness as a multi-objective discrete optimization problem, and proposed a new discrete combinatorial optimization algorithm, named membrane quantum cuckoo search algorithm. The algorithm uses the potential solution of the quantum bird nest characterization problem and obtains the Pareto front solution set with multi-objective optimal solution by the inter-membrane information sharing and non-dominated hierarchical ranking. Dong et al.²² aimed at the contradiction between user surge traffic demand and spectrum shortage. Based on cognitive radio technology, an improved Hungarian algorithm was used to achieve rapid allocation of spectrum resources and improve spectrum utilization, however ignored the influence of channel conditions on the transmission rate. Hasan et al.²³ focused on the scenario where multi-heterogeneous primary networks overlap in a new generation network (5G network), and proposed an improved genetic algorithm and improved particle swarm optimization algorithm to solve the network selection and spectrum allocation problem according to the spectral characteristics of the primary network and the needs of the secondary users. However, Hasan et al.²³ only considered the differentiation of the spectrum in different primary networks, but ignored the differences in the attributes of different spectral resource blocks within the same primary network.

As mentioned above, a lot of achievements have been made in the network selection and spectrum allocation, but there is still the problem of scene adaptability. For example, the graph theory–based methods are suitable for a static network environment, and it is difficult to adapt to the requirements of secondary user mobility. The methods based on spectrum trading are suitable for the cognitive radio system in which the primary user and the secondary user are leased. The game theory allocation model is generally used to analyze the competition and cooperation relationship between spectrum users when the subject behaviors interact directly. Furthermore, research objects of most of the above methods are traditional channel allocation problems, that is, the heterogeneity of spectrum resources is not considered. The differentiation of the spectrum in different primary networks was considered by Dong et al.²² and Hasan et al.,²³ but they ignored the difference between spectrums in the same primary network and the influence of channel conditions on the transmission rate. Based on the works of Dong et al.²² and Hasan et al.,²³ this article considers more practical application requirements under the scenario of overlapping coverage of multi-heterogeneous primary networks. That is, each primary network has its own different network characteristics, even if the spectrum resources within the same primary network are different. At the same time, multiple secondary users existing in the secondary network have different service types and quality of service (QoS). Therefore, the above methods are obviously not directly applicable to the network selection and spectrum allocation of this article.

Network model and problem formulation

Network model

The schematic diagram of the multi-heterogeneous wireless network structure is shown in Figure 1, and the network model is as follows:

1. Suppose there are N primary networks with overlapping coverage (such as cellular networks and WiMax networks). Let the network set be $PN = {p n_{1}, p n_{2}, \dots, p n_{N}}$ . The primary users in the network are evenly distributed, and their behaviors are independent of each other. Thus, the probability of arrival of the primary user can be modeled as a Poisson process of the switch 2 state. Therefore, the spectrum resources can be modeled as independent and random two-state models, that is, idle and busy. Idle indicates that no primary user occupies the spectrum resource at present and can be assigned to one secondary user. The busy state indicates that the spectrum resource is currently occupied by the primary user and cannot be assigned to the secondary user. The spectrum resources include the idle licensed spectrum and the unlicensed industrial scientific medical (ISM) spectrum in the primary network. Let the idle spectrum set be $Sp = {s p_{1}, s p_{2}, \dots, s p_{n}}$ .

2. Assuming that the secondary network is based on the cognitive network of the infrastructure. The base station centrally senses the secondary user request information and the status information of spectrum resources, and uses this as a decision basis for the spectrum allocation. The secondary user is a cognitive device–equipped user within the coverage of the base station in the cognitive network and can only access one spectrum at a time. Let secondary user set be $SU = {s u_{1}, s u_{2}, \dots, s u_{m}}$ .

The transmission rate of the secondary user is related to the spectrum bandwidth, transmission power, and signal-to-noise ratio. According to Shannon’s theorem, the transmission rate of user j can be expressed as

r_{j} = b_{jk} x_{jk} \log_{2} (1 + \frac{S_{jk}}{N_{jk}})

(1)

where b_jk represents the spectrum bandwidth allocated to user j, x_jk indicates the probability that secondary user j occupies spectrum resource k, 1 means occupying the spectrum, and 0 means not occupying the spectrum. S_jk and N_jk represent signal power and noise power, respectively.

3. The spectrum of different primary networks varies in bandwidth, delay, cost, and packet loss rate. Even in the same primary network, the bandwidth, delay, cost, and packet loss rate of idle spectrum are also different, but they generally float within a certain range. Different secondary users have different businesses, such as voice, video, and file transfer which have different requirements for cost, bandwidth, delay, and packet loss rate. Therefore, the allocation of idle spectrum resources needs to take into consideration the attributes of different spectra and the service requirements of secondary users. In addition, when a secondary user accesses to the spectrum of a primary network, it will cause some interference to the primary network. The primary user’s communication quality will be seriously affected when the interference exceeds a certain threshold of the primary network, so the primary network must set a interference threshold to limit the number of secondary users’ access.

Figure 1.

Multi-heterogeneous cognitive wireless network.

Problem formulation

This article focuses on the effective allocation of idle spectrum resources among secondary users after the cognitive network base station effectively perceives the primary network status and the secondary user request information, with the goal of obtaining a larger transmission rate at a lower cost without affecting the communication quality of the primary user. Based on this, the spectrum allocation problem is modeled as a dual-objective optimization model, which aims at maximizing transmission rate and minimizing cost and subjects to the primary network’s interference and secondary user’s business requirements constraint.

According to transmission rate shown in equation (1), the total transmission rate of all secondary users can be derived

R = \sum_{k = 1}^{n} \sum_{j = 1}^{m} b_{jk} x_{jk} \log_{2} (1 + \frac{S_{jk}}{N_{jk}})

(2)

The spectrum allocation problem in this article is modeled, as a nonlinear constraint 01 integer programming, as follows

max R = \max \sum_{k = 1}^{n} \sum_{j = 1}^{m} b_{jk} x_{jk} \log_{2} (1 + \frac{S_{jk}}{N_{jk}})

(3)

\min C = \sum_{j = 1}^{m} \sum_{k = 1}^{n} c_{jk} x_{jk}

(4)

s.t.

r_{j}^{su} x_{jk} \leq r_{k}^{sp}, \forall j, k

(5)

c_{j}^{su} x_{jk} \geq c_{k}^{sp}, \forall j, k

(6)

d_{j}^{su} x_{jk} \geq d_{k}^{sp}, \forall j, k

(7)

l_{j}^{su} x_{jk} \geq l_{k}^{sp}, \forall j, k

(8)

\sum_{j = 1}^{m} i_{jy} x_{jy} \leq I_{y}, \forall y = 1, 2, \dots, N

(9)

\sum_{k = 1}^{n} x_{jk} \leq 1, \forall j = 1, 2, \dots, m

(10)

\sum_{j = 1}^{m} x_{jk} \leq 1, \forall k = 1, 2, \dots, n

(11)

x_{jk} \in {0, 1}

(12)

where objective function of equation (3) represents maximizing the total transmission rate obtained by all secondary users. The objective function of equation (4) represents minimizing the payment cost. $c_{jk}$ indicates the cost that the secondary user j needs to pay for the selection spectrum k. Constraints of equations (5)–(8), respectively, indicate that the selected spectrum resource must meet the transmission rate, cost, delay, and packet loss rate requirements of the secondary user. Equation (9) represents that the total interference should not exceed the interference threshold, I_y, of primary network y, and i_jy indicates the interference caused to the network y when the secondary user j accesses the spectrum of primary network, y. Equations (10) and (11) denote that any user can only access one idle spectrum and one spectrum k cannot be allocated to more than one secondary user at the same time. Equation (12) denotes the probability that the idle spectrum is occupied by the secondary user: 1 means occupied and 0 means not occupied.

Problem complexity analysis

Assuming that the number of idle spectrum resources and secondary users are n and m, respectively. According to the section “Network model,” one spectrum resource can only be assigned to one secondary user, and one secondary user can only access one spectrum resource. Therefore, the spectrum allocation in this article is a 01 programming problem. From the mathematical model of Section “Problem formulation,” we can see that the spectrum allocation problem has two optimization objectives and multiple constraints, that is, the problem is a constrained nonlinear multi-objective optimization problem. The literature in Sharma et al.²⁴ shows that this problem is NP-hard. That is, as the scale of the problem increases, its computational complexity increases with the factorial level.²⁵

Simplification method and improved intelligent optimization algorithm

As we can see from the analysis in section “Problem complexity analysis,” the spectrum allocation problem in this article is NP-hard, that is, there is no algorithm available for solving in polynomial time. Therefore, this article attempts to simplify the mathematical model and seeks a simple method to solve the problem. At the same time, for the complex allocation model, this article will also use an improved evolutionary algorithm to solve the problem.

Simplification method

The simplification method will simplify the constraints and objective functions, and use the proposed improved Hungarian algorithm to solve the spectrum allocation problem. The key steps are as follows.

Efficiency matrix construction

The efficiency matrix represents the efficiency value obtained by the secondary user in selecting the corresponding spectrum resource. The goal of this article is to obtain a larger transmission rate at a lower cost. Therefore, this article first constructs the transmission rate efficiency matrix and the cost efficiency matrix. The transmission rate corresponding to the spectrum resource can be calculated using equation (1).

Through the transmission rate efficiency matrix, the corresponding transmission rate when the secondary user selects the spectrum resource can be obtained. In the same way, the cost of the corresponding spectrum can be obtained through the cost–benefit matrix.

Objective function transformation

The objective of this article is to obtain the maximum transmission rate at the lowest cost while satisfying the QoS requirements of secondary user, and this is a dual-objective optimization problem. By introducing the relative transmission rate cost factor α, the dual-objective optimization problem of transmission rate and cost can be converted into a single-objective optimization problem with the maximum relative transmission rate factor α, where α is as follows

α_{jk} = \frac{r_{jk}}{c_{jk}}

(13)

where $α_{jk}$ denotes transmission rate obtained by a unit cost. By introducing α, objective functions (1) and (2) in section “Problem formulation” can be rewritten as following

Max : α = \sum_{j = 1}^{m} \sum_{k = 1}^{n} α_{jk} x_{jk}

(14)

Constraint simplification

Equation (5) indicates that the transmission rate of the idle spectrum selected by the secondary user must be greater than or equal to the transmission rate requirement of the secondary user. Therefore, the relative transmission rate factor, α, of the spectrum resource with a transmission rate smaller than that of the secondary user may be set to 0. Similarly, according to equations of (6)–(8), set the factor α of the idle spectrum that does not meet the requirements of the secondary user to 0. And then, the non-zero part represents available spectrum resources that satisfy the secondary user’s QoS requirements.

Equation (9) indicates that the secondary user’s interference to the primary network should not exceed the primary network’s interference threshold. With the secondary user’s access, the interference to each primary network is gradually increased. This is a dynamic process, so equation (9) cannot be eliminated here by the same method. However, an improved Hungarian algorithm is proposed in this article, in which the secondary user’s interference to the primary network is considered in the process of assigning 0 elements. See section “Improved Hungarian algorithm” for details.

Standardized processing

Since the number of secondary users requesting services may not be equal to the number of idle spectrum $(m \neq n)$ , that is, the allocation problem may be an unbalanced assignment problem, normalization preprocessing is required before using the improved Hungarian algorithm. The details are given as follows:

When $n = m$ , no need to deal.

When $m > n$ , add $(m - n)$ virtual spectrum resources and let their relative bandwidth cost factor α be 0, so that the secondary user can give priority to the actual idle spectrum.

When $m < n$ , add $(n - m)$ virtual secondary users and let the relative bandwidth cost factor α of the row where the secondary user is located be 0, so that the actual existing secondary users will give priority to the actual idle spectrum.

At the same time, normalization preprocessing also includes converting the relative transmission rate cost factor α maximization problem into a minimization problem. That is, finding the maximum value $α_{max}$ in the efficiency matrix first and then subtracting each element of the efficiency matrix with the maximum value $α_{max}$ to obtain a new efficiency factor $β_{jk} = α_{max} - α_{jk}$ .

Improved Hungarian algorithm

The Hungarian algorithm is a classical algorithm proposed by American mathematician, Kuhn, to solve the assignment problem. It is a polynomial time algorithm with the advantages of simple steps and high efficiency.²⁶

In this article, the Hungarian algorithm is improved, that is, the interference value constraint of the primary network is merged into the trial assignment step to ensure that the interference threshold of the primary network is not exceeded. At the same time, this article improves the key step “transform efficient matrix” of the traditional Hungarian algorithm to improve the efficiency of the algorithm.

The key steps of the improved Hungarian algorithm are as follows:

Transform efficiency matrix: compared with the traditional Hungarian algorithm, randomly subtracting the smallest element of the row (or column) from the row (or column) to get the 0 element, the improved method first counts the minimum number r (or c) of elements in each row (or column). Then, according to the relationship between the numbers r and c, it is decided to first subtract the smallest element from the row or column. If r < c, start from the row, otherwise start from the column. By this method, the number of 0 elements can be increased, and the probability of successful trial assignment is improved, thereby improving the execution efficiency of the algorithm.

Trial assignment: trial assignment includes two sub-steps: (1) independent 0 assignment: first, find the independent 0 element of each row in turn and calculate the primary network k to which the element belongs. If the interference value does not exceed the interference threshold of primary network k after adding the secondary user corresponding to the row, assign this 0 element to the secondary user, while marking the row and column where the 0 element is located can no longer assign 0 elements and updating the primary network interference value. Similarly, search for the independent 0 elements in each column in turn and do the same operation as row independent 0 elements. Finally, loop search and trial allocation of independent 0 elements in each row and column are performed until there is no independent 0 element. (2) Non-independent 0 assignment: search for whether there are 0 elements in each row and column. If so, start from the row with the minimum number of 0 elements (if row and column have the same number of 0 elements, we can randomly choose from the row or the column with minimum number of 0 elements). Calculate the primary network to which the 0 element belongs and perform the interference value processing in accordance with sub-step 1. Then, assign the non-assigned 0 element that meets the requirements to the secondary user corresponding to the row and perform the assignment labeling processing. Finally, loop search and trial allocation of 0 elements are performed until no 0 element is found. Calculate the number of allocated 0 elements num; if num is equal to the efficiency matrix dimension n, then the optimal solution of the allocation problem has been found, otherwise go to step 3.

Cover all 0 elements with a minimum line. The number of straight lines is l. If $l = n$ , go to step 2 and reassign. If $l < n$ , go to step 4.

Transform the matrix to increase 0 elements. Set the minimum value of the elements not covered by the straight line of step 3 to be β. Then subtract β from the unmarked line, add t to the unmarked column and go to step 2.

By applying the above objective function transformation, constraint condition reduction, and standardized processing, the optimization model in Section “Problem formulation” can be simplified as

Min : β = \sum_{j = 1}^{m} \sum_{k = 1}^{n} β_{jk} x_{jk}

(15)

s.t.

\sum_{k = 1}^{n} x_{jk} \leq 1, \forall j = 1, 2, \dots, m

(16)

\sum_{j = 1}^{m} x_{jk} \leq 1, \forall k = 1, 2, \dots, n

(17)

x_{jk} \in {0, 1}

(18)

The above optimization model can be transformed into the following standard matrix form

\underset{X \in {0, 1}}{Min} f (X) = c^{T} X, s . t . AX \leq b

(19)

where $c^{T} = [\overset{| n |}{\overset{︷}{c_{11}, \dots, c_{1 n}}}, \dots, \overset{| n |}{\overset{︷}{c_{m 1}, \dots, c_{mn}}}]$ is an $n * m$ dimensional vector, that is, a vectorization of the two-dimensional efficiency matrix. $X^{def} =$ ${[\overset{| n |}{\overset{︷}{x_{11}, \dots, x_{1 n}}}, \dots, \overset{| n |}{\overset{︷}{x_{m 1}, \dots, x c_{mn}}}]}^{T}$ is an $n * m$ dimensional vector, that is, a vectorization of the decision variable matrix. $A = (\begin{matrix} {A_{1}}_{(n * m)} \\ A_{2 (n * m)} \end{matrix})$ is a $2 m * n$ dimensional constraint matrix, in which A₁ and A₂ are both $m * n$ dimensional matrices corresponding to equations (16) and (17).

Time complexity analysis

According to the steps of the simplification method, the execution time of the efficiency matrix construction, the dual-objective transformation, the constraint simplification, and the standardization processing is negligible relative to the solution process of the improved Hungarian algorithm, and the following discussion focuses on the time complexity of the improved Hungarian algorithm. Assume that the numbers of secondary users and idle spectrum are both n (the number of them is equal after standardization). It can be seen from the trial assignment (step 2) of improved Hungarian algorithm that the consumption time is mainly the independent 0 assignment, wherein the assignment of the row independent 0 elements needs to search each element of each row and the time complexity is O(n²). Similarly, the time complexity of the assignment of the column independent 0 elements is also O(n²), so the time complexity of the step 2 trial assignment is O(n²). Step 3 determines whether all the secondary users are assigned a free spectrum, if not, jumps to step 4 to transform the efficiency matrix to increase 0 elements and then proceeds to step 2 to continue the trial assignment. In the worst case, it is necessary to perform the efficiency matrix transformation of step 4 n times to increase the 0 element, that is, the trial assignment of step 2 needs to be performed cyclically n times. Therefore, the time complexity of the simplification method is O(n³), which is an effective algorithm for solving the assignment problem in a polynomial time.

INSGA-II

The NSGA-II proposed by Deb et al.²⁷ solves the multi-objective optimization problem using a powerful global search capability. The algorithm searches in parallel in multiple directions in the solution space and ultimately finds the possible solutions. This article proposes an INSGA-II, which integrates the interference constraint of the primary network and the QoS requirements of the secondary user into the objective value assessment of non-dominated sorting, and correct chromosomes that do not meet the constraints. At the same time, makes decision-making on the optimal solution set to get the final spectrum allocation scheme. The specific process of the proposed INSGA-II algorithm is as follows:

Step 1. Initialize the population: let the population size be Num and create a random initial population $P_{0}$ based on the chromosome coding scheme.

Step 2. Non-dominated sorting: according to the interference constraints of the primary network and the service quality requirements of each secondary user, the improved non-dominated sorting scheme is used to allocate corresponding non-dominated ranks and crowding distances for each chromosome.

Step 3. Genetic manipulation: using the binary tournament selection operator, a parent population P_parent is screened from the initial population P₀ and then chromosomes in the population P_parent are double-crossed and mutated to generate new offspring populations P_offspring.

Step 4. Generate a preferred population for loop iterations: the initial population is mixed with the progeny population P_offspring in step 3 to obtain a mixed population. The mixed population is again non-dominated and filtered to obtain a preferred population P_opt. Let P₀ = P_opt and go to step 3 to generate optimal population by loop iteration until the upper limit of iterations is reached and then go to step 5.

Step 5. Decision selection: a decision-making selection strategy is used to select a chromosome from the optimal Pareto solution set as a final spectrum resource allocation scheme.

The following mainly introduces the improvement of the algorithm in this article.

Non-dominated sorting

The optimization objectives of this article include transmission rate maximization and cost minimization which are used for non-dominated sorting as follows.

Evaluation of chromosome objective values

If the allocation scheme corresponding to the chromosome satisfies the constraint of mathematical model in section “Problem formulation,” the optimization objective values are equal to the sum of the transmission rate and cost of each secondary user. Due to the randomness of the crossover and mutation operations, there are chromosomes that do not satisfy the constraint, such as the same spectrum allocated to multiple secondary users. For non-compliant chromosomes, they are usually removed from the population. In order to avoid eliminating too many non-conforming chromosomes and affecting the optimization effect, this article starts the correction procedure for non-compliant chromosomes as follows:

Step 1. Calculate the network and spectrum corresponding to the genes in the chromosome, and extract the corresponding transmission rate, price, time delay, and other attribute values of the spectrum.

Step 2. Determine whether the attributes of the spectrum in step 1 satisfy the service requirements of secondary, or the spectrum is allocated to multiple secondary users. If the requirements are not met, perform step 3 to correct the gene. Otherwise, return to the step 1 to calculate the next gene until all genes meet the requirements and exit.

Step 3. Genetic modification: according to the range of values of the network and the spectrum, the network and spectrum values of the gene are randomly adjusted to other networks and spectrum, and return to step 2 to detect whether the gene meets the requirements.

Non-dominated sorting based on objective values

Definition 1. Suppose a and b are any two different chromosomes in the population. If the following two conditions are met, a is said to dominate b as follows:

For the total cost C and the total transmission rate R, chromosome a is not worse than b, that is

{\begin{matrix} C_{a} \leq C_{b} \\ R_{a} \geq R_{b} \end{matrix}

(20)

where C_a and C_b denote the total cost C of chromosomes a and b, respectively. $R_{a}$ and $R_{b}$ denote the total transmission rate of chromosomes a and b, respectively.

There is at least one objective value that a is better than b, that is, $C_{a} < C_{b}$ or if a and b satisfy the above conditions of (1) and (2), a is called non-dominated solution, and b is dominated by a.

Definition 2. If $C_{a} = C_{b}$ and $R_{a} = R_{b}$ , or the two objective values have advantages or disadvantages, then a and b are not dominated by each other and will be allocated at a same rank. That is, chromosomes satisfying one of the following three conditions are not dominated by each other and are allocated at a same rank

{\begin{matrix} C_{a} = C_{b} and R_{a} = R_{b} \\ C_{a} < C_{b} and R_{a} < R_{b} \\ C_{a} > C_{b} and R_{a} > R_{b} \end{matrix}

(21)

As mentioned above, non-dominated sorting first requires that all chromosomes of the population be evaluated for objective values. Then, use the non-dominated definition to find all the non-dominated solutions in the population and assign the corresponding ranks, and perform until all the chromosome ranks of the population are allocated.^27,28

Decision-making

The non-dominated sorting algorithm is used to obtain a set of optimal Pareto solutions. There is no solution in the set of solutions that can make all the optimization objectives optimal at the same time. However, in this article, a unique solution is required to allocate spectrum resources to each secondary user. Therefore, this article proposes a compromise selection strategy. The strategy is as follows

Y_{j} = \sum_{i = 1}^{k} λ_{i} \frac{| f_{i}^{j} - f_{i}^{opt} |}{f_{i}^{max} - f_{i}^{min}}

(22)

The above formula expresses the degree of closeness of each objective value of the chromosome to the optimal value, where Y_j represents the degree of closeness of the chromosome j; $f_{i}^{j}$ denotes the ith objective value of chromosome j; $f_{i}^{opt}, f_{i}^{max}, and f_{i}^{min}$ denote the optimal value, maximum value, and minimum value of the ith objective of the optimal Pareto solution, respectively. For the objective maximization problem, there is $f_{i}^{opt} = f_{i}^{max}$ , such as the maximum bandwidth in this article. For the objective minimization problem, there is $f_{i}^{opt} = f_{i}^{min}$ , such as the cost minimization in this article. In order to use a unified standard to measure the degree of closeness of each objective with respect to the optimal value, a normalization process needs to be performed, and the final degree of closeness of chromosome j is the sum of the degree of closeness of its respective optimization objects. The smaller the degree of closeness Y_j, the closer to the optimal value. $λ_{i}$ is the weighting factor for each objective $(\sum_{i = 1}^{k} λ_{i} = 1)$ which indicates the user’s degree of emphasis on the objective, and the greater the value, the greater the emphasis.

Experimental results analysis

Simulation setting

Assume that there are four primary networks (including two cellular networks, one WiMax, and one WiFi network), each with 10 idle spectrums. Suppose the interference caused by the same secondary user to different primary networks is the same, and the secondary user brings at least one unit (a dimensionless scalar) of interference. Therefore, the interference value n indicates that n units of interference are caused.

As shown in Table 1, the bandwidth, cost, delay, packet loss rate, and interference threshold of the network are all within a certain range. The experimental idle spectrums are randomly and uniformly distributed within this range.

Table 1.

Characteristics of the idle spectrum of each primary network.

Primary network	Bandwidth (kbps)	Cost	Delay (ms)	Packet loss rate (%)	Interference
Cellular 1	1000–3000	80–100	35–50	<1	7–9
Cellular 2	80–120	40–60	35–50	<1	11–13
WiMax	10,000–20,000	70–90	300–500	<5	9–11
WiFi	2000–8000	40–60	100–300	<5	9–11

Assume that there are three types of service requirements (voice, video, and file transfer) and 10 secondary users. Business-type distribution conforms to random uniform distribution. Different services and users have different service quality requirements, specifically as shown in Table 2.

Table 2.

User service and service quality requirements.

Secondary user	Transmission rate (kbps)	Cost	Delay (ms)	Packet loss rate (%)	Interference
Voice	40–60	90	50	<3	1–3
Video	100–140	100	400	<5	1–3
File	150–190	95	5000	<15	1–3

To evaluate the algorithm performance, the proposed methods are compared with the multi-objective artificial bee colony (MOABC) algorithm. Assume that the INSGA-II has a population size of 40, a crossover probability of 0.9, a mutation probability of 0.1, and a maximum iteration number of 1000. At the same time, in order to eliminate the randomness, the experiment was carried out 20 times, and the average value was taken as the experimental result.

Performance evaluation

This article mainly evaluates the effectiveness and time efficiency of three algorithms, and investigates the convergence performance of the proposed INSGA-II.

Effectiveness analysis of optimization results

Figures 2 and 3 compare the optimized objective values of the three algorithms as iterations from 100 to 1000, in which the INSGA-II method gives the results of three different decision selection weights, including cost-priority strategy (transmission rate weight 0.4, cost weight 0.6), transmission rate–priority (transmission rate weight 0.6, cost weight 0.4), and balance strategy (transmission rate weight 0.5, cost weight 0.5). The simplification method does not have an evolutionary iterative process, but it is still put into the figures.

Figure 2.

Total transmission rate obtained by different strategies.

Figure 3.

Comparison of the total costs of different strategies.

As shown in Figure 2, the transmission rate of the INSGA-II and MOABC algorithms generally increases with the number of iterations. When the number of iterations is greater than 300, the growth is slow and tends to converge. We can also see from Figure 2 that transmission rate of the INSGA-II with transmission rate–priority strategy is significantly higher than other algorithms. Similar to Figure 2, it can be seen from Figure 3 that the cost of the INSGA-II and MOABC algorithms gradually decreases as the number of iterations increases, especially the cost-priority strategy of INSGA-II. When the number of iterations is greater than 300, the costs tend to converge. The simplification method and INSGA-II of cost-priority strategy get the smallest cost.

In summary, for users with high transmission rate of service requirements, choosing the INSGA-II with transmission rate–priority strategy for spectrum allocation can achieve higher transmission rate. And, cost-sensitive users should use the simplification method or the INSGA-II with cost-priority strategy. The MOABC algorithm and the INSGA-II with balance strategy achieve more balanced performance.

Access probability analysis of different network spectrum

Figures 2 and 3 show the optimization results of the total transmission rate and total cost. The following experiments further study spectrum resources of which primary network are selected by different user services at the micro level and try to analyze why it is so selected to explain the results obtained in Figures 2 and 3. The ordinates of Figures 4 –6 represent the accessing probability which is calculated by dividing the number of times the secondary user accesses the primary network by the number of experiments. As shown in the Figure 4 of simplification method, users who apply for voice services all choose to access the spectrum of cellular networks 2, because it can meet the high latency requirements of voice services, and its cost is low, thus having a high relative transmission rate–cost ratio compared to cellular network 1. For users who apply for video services, spectrum of WiFi network can provide the maximum relative transmission rate cost factor α, so users all access the spectrum of WiFi network. Similarly, for the users who apply for the file transmission service, the spectrum of WiMax and WiFi network can provide a higher relative transmission rate cost factor α, so users has a high probability to access spectrum of these two primary networks. The following takes the INSGA-II with balance strategy and MOABC algorithms as examples to analyze the spectrum access of the secondary user. We can observe from Figures 5 and 6 that users who apply for voice services choose spectrum resource of cellular networks 1 and 2 with low latency, which is consistent with the characteristics of voice transmission. Users who apply for video and file transmission service choose WiMax and WiFi Network, because the spectrum of these two networks has a large bandwidth and a lower cost.

Figure 4.

Network selection probabilities for simplification method.

Figure 5.

Network selection probabilities for INSGA-II with balanced strategy.

Figure 6.

Network selection probabilities for MOABC.

Overall, it can be seen from Figures 4 –6 that simplification method accesses to the spectrum resource of cellular network 2 and WiFi network with a high probability, while the probability that the INSGA-II with balance strategy and MOABC algorithm access four networks is relatively balanced. From the properties of the primary networks in Table 1, we can see that spectrum resource of cellular network 2 and WiFi network has a lower cost. Therefore, the cost of the simplification method is much lower than those of INSGA-II with balance strategy and MOABC algorithm. This is consistent with the results of Figures 5 and 6.

Comparison of execution efficiency

As shown in Figure 7, the running time of INSGA-II and MOABC algorithms increases linearly with the number of iterations, while the simplification method is almost negligible compared to the INSGA-II and MOABC algorithm because the simplification method mainly performs simpler 0 element search operations. So, the simplification method has obvious advantages in execution efficiency. It can also be seen from Figure 7 that the INSGA-II runs slightly slower than the MOABC algorithm, because the INSGA-II needs to perform large-scale cross-variation operations.

Figure 7.

Comparison of execution efficiency.

For two evolutionary algorithms, theoretically, the more the iterations, the better the results, but it is at the expense of time. As shown in Figures 2 and 3 when the number of iterations is small (about less than 300 times), the transmission rate grows faster, while the cost is reduced faster too. But when the number of iterations is greater than 300, the evolutionary speed is getting slower and slower, and tends to converge. Therefore, we can stop iterations when the evolution speed is slow to save time.

Pareto frontier analysis of INSGA-II

Pareto frontier of the INSGA-II under different iteration numbers (100, 200, 300, 400, 500, and 600 iterations) is given below to further observe the convergence of the INSGA-II. The INSGA-II obtains a set of non-dominated solutions at each iteration, which cannot be averaged through multiple experiments. Therefore, we randomly performed 20 experiments, classifying all the results and randomly selecting some images from the classified images for analysis.

As can be seen from Figure 8, experimental results do have some randomness. For example, as shown in Figure 8(a) and (b), the objective values converge slowly as the iteration proceeds. In Figure 8(c) and (d), the objective values converge rapidly and almost overlap when iterated to 200 times. In Figure 8(e) and (f), the objective values have been overlapped from the iteration number 100. The above phenomenon reflects the different convergence speeds of different experiments, but they basically follow the rule that the transmission rate becomes larger and larger for the same cost as the number of iteration increases, and with the same transmission rate, the cost is getting smaller as the iteration proceeds. At the same time, Pareto front tends to converge as the number of iterations increases and basically tends to overlap when the number of iterations reaches 500 or more.

Figure 8.

Pareto front of INSGA-II: (a)(b) objective values converge slowly, (c)(d) objective values converge rapidly, and (e)(f) objective values overlap.

Conclusion

In the context of multi-heterogeneous network convergence, this article comprehensively considers the heterogeneity of different network spectrums and the requirements of different user service. With the goal of maximizing user transmission rate and minimizing costs, a dual-objective optimization model for the allocation of idle spectrum resources is established. The complexity of the problem is analyzed and proved to be an NP-hard problem. On this basis, two solutions are proposed: (1) simplification method: first, the complex spectrum allocation problem is transformed into a standard form of the 01 programming problem by preprocessing of objective function, constraint simplification, and standardization. Then, the solution is solved by an improved Hungarian algorithm. (2) Using intelligent algorithms: this article improves the traditional multi-objective optimization algorithm NSGA-II, and proposes an INSGA-II method which integrates the interference constraints of the primary network and the secondary user’s service quality requirements into the objective value evaluation of non-dominated sorting and then correct chromosomes that do not meet the constraints. At the same time, makes decision-making on the optimal solution set to get the final spectrum allocation scheme. Finally, it can be seen from the experimental results that the simplification method has a greater efficiency advantage that its execution time is almost negligible compared to the evolutionary algorithms of INSGA-II and MOABC. In the case of high efficiency and low cost requirement, the simplification method can be prioritized, while INSGA-II, especially the transmission rate–priority strategy, is suitable for high transmission rate required scene.

This article mainly focuses on the spectrum allocation scenario of multi-primary networks and single secondary network, while the user terminal only has a single access capability. However, with the dense deployment of heterogeneous networks, multiple primary networks and multiple secondary networks overlapping scenarios will occur. At the same time, with the development of intelligent user terminals and diversified service requirements, terminals with multiple access capabilities will be deployed on a large scale. In a multi-primary networks and multi-secondary networks overlapping scenario, studying the spectrum resources allocation and switching, and user associations among secondary networks, researching the efficient allocation of spectrum resources among multi-access terminals, and achieving load balancing between networks and maximizing network and user benefits is a difficult problem. It is also a key issue for our future research.

Footnotes

Handling Editor: Donatella Darsena

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was funded by the Science and Technology Project of Guangdong Province (2016A020209012, 2017B 090901019, and 2015A010103015), Chinese National Natural Science Foundation (61502110), and the Natural Science Foundation of Guangdong Province (2014A030307014).

ORCID iD

Xiaoqing Dong

References

IMT-2020(5G) Promotion Group. White paper on 5G vision and requirements, 2014, http://www.imt-2020.org.cn/zh/documents/1?currentPage=2&content=

IMT-2020(5G) Promotion Group. White paper on 5G CONCEPT, 2015, http://www.imt-2020.org.cn/zh/documents/1?currentPage=1&content=

IMT-2020(5G) Promotion Group. White paper on 5G network technology architecture, 2015, http://www.imt-2020.org.cn/zh/documents/1?currentPage=1&content=

IMT-2020(5G) Promotion Group. White paper on 5G network architecture design, 2016, http://www.imt-2020.org.cn/zh/documents/1?currentPage=1&content=

Darsena

Gelli

Verde

. Convolutive superposition for multicarrier cognitive radio systems. IEEE J Sel Area Comm 2016; 34(11): 2951–2967.

Darsena

Gelli

Verde

. An opportunistic spectrum access scheme for multicarrier cognitive sensor networks. IEEE Sens J 2017; 17(8): 2596–2606.

Zhao

Liu

Chai

et al . Spectrum allocation and power control for non-orthogonal multiple access in HetNets. IEEE T Wirel Commun 2017; 16: 5825–5837.

Chai

Wang

. Spectrum allocation of cognitive radio network based on artificial physics optimization. Acta Physica Sinica 2014; 63(22): 53–81.

Zhu

Duan

. An improved spectrum allocation algorithm using multi-strategy discrete artificial bee colony technology. J Xian Jiaotong Univers 2016, http://en.cnki.com.cn/Article_en/CJFDTotal-XAJT201602004.htm

10.

Chen

Xiong

Wang

et al . Ensuring minimum spectrum requirement in matching-based spectrum allocation. IEEE T Mobile Comput 2018; 17: 2028–2040.

11.

Ileri

Samardzija

Sizer

et al . Demand responsive pricing and competitive spectrum allocation via a spectrum server. In: First IEEE international symposium on new frontiers in dynamic spectrum access networks, 2005 (DySPAN 2005), Baltimore, MD, 8–11 November 2005, pp.194–202. New York: IEEE.

12.

Lam

Zhao

et al . Spectrum trading for satellite communication systems with dynamic bargaining. IEEE T Commun 2018; 66: 4680–4693.

13.

Zhang

Bao

. Agent-based dynamic spectrum trading algorithm in cognitive radio network. J Commun 2013(3): 119–125.

14.

Xie

Zhao

. Research on spectrum allocation algorithm based on equilibrium price for cognitive radio network. J China Railw Soc 2014; 36(1): 70–75.

15.

Cao

Zheng

. Distributed spectrum allocation via local bargaining. In: 2005 second annual IEEE communications society conference on sensor and Ad Hoc communications and networks (IEEE SECON 2005), Santa Clara, CA, 26–29 September 2005, pp.475–486. New York: IEEE.

16.

Etkin

Parekh

Tse

. Spectrum sharing for unlicensed bands. IEEE J Sel Area Comm 2007; 25(3): 517–528.

17.

Hajisami

Pompili

. Joint virtual edge-clustering and spectrum allocation scheme for uplink interference mitigation in C-RAN. Ad Hoc Netw 2018; 72: 91–104.

18.

Sun

Guo

Tang

. Spectrum allocation with SINR guarantee for cognitive wireless multi-hop networks. J Commun 2011; 32(11): 111–117.

19.

Tan

Chao

Wei

. Spectrum sharing schemes in cognitive radio networks based on collusion formation. J Commun 2014; 3: 58–68.

20.

Chuanbao

Quan

Youxi

et al . Frequency spectrum resource allocation based on membrane-inspired quantum cuckoo search for wireless dual-channel ad hoc network. Chin J Radio Sci 2016; 31: 129–137.

21.

Orsino

Araniti

Molinaro

et al . Effective RAT selection approach for 5G dense wireless networks. In: 2015 IEEE 81st vehicular technology conference (VTC Spring), Glasgow, 11–14 May 2015, pp.1–5. New York: IEEE.

22.

Dong

Cheng

Zheng

et al . Multi-objective optimization method for spectrum allocation in cognitive heterogeneous wireless networks. AIP Adv 2019; 9: 045130.

23.

Hasan

Ejaz

et al . Network selection and channel allocation for spectrum sharing in 5G heterogeneous networks. IEEE Access 2016; 4: 980–992.

24.

Sharma

Shroff

Mazumdar

. Maximum weighted matching with interference constraints. In: Fourth annual IEEE international conference on pervasive computing and communications workshops, 2006 (PERCOMW’06), Pisa, 13–17 March 2006, pp.5–74. New York: IEEE.

25.

Salameh

HAB

. Throughput-oriented channel assignment for opportunistic spectrum access networks. Math Comput Model 2011; 53(11): 2108–2118.

26.

Kuhn

. The Hungarian method for the assignment problem. Nav Res Log 1955; 2(1–2): 83–97.

27.

Deb

Agrawal

Pratap

et al . A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: International conference on parallel problem solving from nature (PPSN 2000): PPSN VI, Paris, 18–20 September 2000, pp.849–858. Berlin, Heidelberg: Springer.

28.

Tao

. Collaborative task allocation algorithm based on multi-objective optimization in WSN. J Southeast Univ 2014; 44(4): 712–771.

Network access and spectrum allocation in next-generation multi-heterogeneous networks

Abstract

Keywords

Introduction

Related works

Network model and problem formulation

Network model

Problem formulation

Problem complexity analysis

Simplification method and improved intelligent optimization algorithm

Simplification method

Efficiency matrix construction

Objective function transformation

Constraint simplification

Standardized processing

Improved Hungarian algorithm

Time complexity analysis

INSGA-II

Non-dominated sorting

Evaluation of chromosome objective values

Non-dominated sorting based on objective values

Decision-making

Experimental results analysis

Simulation setting

Performance evaluation

Effectiveness analysis of optimization results

Access probability analysis of different network spectrum

Comparison of execution efficiency

Pareto frontier analysis of INSGA-II

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References