Chai Zhengyi　 Zheng Baolin　 Shen Lianfeng　 Zhu Sifeng

(1National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)(2School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300384, China)(3Department of Information Engineering, Henan Vocational and Technical College, Zhengzhou 450046, China)



Throughput scheduling in cognitive radio networksbased on immune optimization

Chai Zhengyi1,2Zheng Baolin3Shen Lianfeng1Zhu Sifeng1

(1National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)(2School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300384, China)(3Department of Information Engineering, Henan Vocational and Technical College, Zhengzhou 450046, China)

Abstract：To study the throughput scheduling problem under interference temperature in cognitive radio networks, an immune algorithm-based suboptimal method was proposed based on its NP-hard feature. The problem is modeled as a constrained optimization problem to maximize the total throughput of the secondary users (SUs). The mapping between the throughput scheduling problems and the immune algorithm is given. Suitable immune operators are designed such as binary antibody encoding, antibody initialization based on pre-knowledge, a proportional clone to its affinity and an adaptive mutation operator associated with the evolutionary generation. The simulation results show that the proposed algorithm can obtain about 95% of the optimal throughput and operate with much lower liner computational complexity.

Key words：cognitive radio networks; throughput scheduling; immune algorithm; interference temperature

Received 2015-04-20.

Biography：Chai Zhengyi (1976—), male, doctor, associate professor,super_chai@126.com.

Foundation items：The National Natural Science Foundation of China (No.U1504613, 61202099, 61201175, U1204618), China Postdoctoral Science Foundation (No.2013M541586).

Citation：Chai Zhengyi, Zheng Baolin, Shen Lianfeng, et al. Throughput scheduling in cognitive radio networks based on immune optimization[J].Journal of Southeast University (English Edition),2015,31(4):431-436.[doi:10.3969/j.issn.1003-7985.2015.04.001]

The increasing growth in wireless communication demands has intensified the shortage crisis for the radio spectrum, while a significant amount of the licensed spectrum is not currently being utilized[1]. The spectrum is far more underutilized rather than naturally scarce. A cognitive radio network (CRN) is a kind of intelligent communication system, which enables the devices to opportunistically access the licensed spectrum, and thereby enhance the utilization of the existing spectrum resources[2-3]. The nodes in a cognitive radio network can be classified into primary users (PUs) and secondary users (SUs). A PU is a licensed user that has exclusive rights to the access spectrum. A SU is an unlicensed user that can utilize the spectrum opportunistically with primary users under interference restriction.

Throughput optimal scheduling for cognitive radio networks under interference temperature constraints is an open research issue[4]. The throughput scheduling determines how many packets and with which frequency each SU will transmit in each time slot[5]. The aim of it is to maximize the total throughput of the SUs in the cell. The throughput scheduler issue in conventional networks has been widely studied[6]. Nonetheless, the cognitive radio paradigm brings new challenges into the issue because of the coexistence of the PUs and the SUs. The throughput scheduling problem considered in this paper can be distinguished from these works by its cognitive radio specific nature. That is, not only the availability of different frequencies but also the maximum allowable transmission rate of the frequency bands are time-varying[5].

Researchers have done some work with different scenarios. In Ref.[6], a throughput scheduling algorithm was proposed which does not enable the true coexistence of the PUs and the SUs. The authors in Ref.[7] figureted a distributed heuristic to determine the channels and time slots for the cognitive nodes. However, they do not consider the interference for the PUs either in their optimization figuretion or in their suboptimal heuristic. The interference temperature model provides the true coexistence data of its licensed and unlicensed users. The throughput optimization is a binary integer programming problem, so the figureted scheduling algorithms have a high computational complexity[3-7]. In Ref.[3], its optimal solution was obtained by the branch-and-bound algorithm with very high computational complexity. In Ref.[4], the authors focused on throughput scheduling under interference temperature constraints and figureted the throughput maximization problems. Then, the authors proposed suboptimal schedulers, referred to as maximum frequency selection (MFS) and probabilistic frequency selection (PFS), with low complexity at the expense of poor throughput performance. Hence, the design of better performing suboptimal scheduling with reasonable complexity is very meaningful.

It is known that bio-inspired methods are ideal for such nonlinear optimization problems[8]. Some bio-inspired methods have been employed in conventional (non-cognitive) schedulers, such as the genetic algorithm[9]and particle swarm optimization[10]. In this paper, an improved immune algorithm is introduced to solve the throughput scheduling problem. The inspiration comes from the fact that the immune algorithm is ideal for nonlinear optimization problems with a large feasible solution space where a quick sub-optimal solution will suffice. Also, to the best of our knowledge, the use of the immune algorithm for scheduling in cognitive radio networks has not previously been explored.

1System Model

Consider a time-slotted IEEE 802.22 system in which the SUs are controlled and guided by the cognitive base station (CBS)[4-5]. The scheduler is at the CBS. Assume that the interference temperature perceived by the PUs is within the interference temperature limits; reliable communication between the CBS and the SUs is achieved; and collisions among the SUs are avoided[4]. Each SUncalculates every frequencyf, and the value is denoted asUnf, which is the maximum number of packets that it can transmit for frequencyfin a time slot. The calculation procedure forUnfvalues guarantees that the interference temperature perceived by the PUs is within the predetermined limits. The CBS then constitutes a matrix called U=[Unf].

The throughput optimal schedule can be formatted as

(1)

(1a)

Xnft+Xn′ft≤1∀n,n′∈1,2,…,N;n≠n′; ∀f,∀t

(1b)

whereN,F,Tare the total number of SUs, frequencies, time slots, respectively;Xnftis a binary variable such thatXnft=1 if userntransmits with frequencyfin time slottand 0 otherwise. Constraint (1a) guarantees that at least one time slot is assigned to each SU, whereas constraint (1b) makes certain that at most one user can transmit at a particular time slot and frequency combination, and consequently preventing collisions among the cognitive nodes. Moreover, the schedule lengthTis the time period in which the spectral and networking environment changes slowly enough so that theXnftvalues are not affected. For example, the TV bands used by an IEEE 802.22 network constitute a slowly altering spectral environment, and hence enableTto be large enough[4].

2Proposed Algorithm

2.1　Overview of immune optimization algorithm

The artificial immune system (AIS) is inspired by the human immune system. The AIS-based algorithms typically extract ideas from the human immune system’s characteristics of learning and adaptability to solve some complicated problems[10]. Most immune system inspired optimization algorithms are based on the clone selection principle. Clone selection is a dynamic simulation process of the immune system that is self-adaptive against antigens. The clone selection algorithm for optimization has been widely used in engineering-oriented fields, such as spectrum allocation[11], job scheduling[12], and image segmentation[13]and so on. These algorithms essentially evolve solutions to problems via the repetition of a clone, affinity maturation (via mutation) and a selection cycle for a candidate solutions population, and remaining good solutions in the population[10-12].

Some related terms are described briefly as follows:

1) Antigen. An antigen represents one sample in the solution space of the problem. In this paper, antigen refers to the throughput schedule problem to be solved and the total constraints.

2) Antibody. An antibody represents a candidate solution to the problem in this paper.

3) Antibody population. The complete antibodies consist of antibody population.

4) Affinity. Affinity is the fitness measurement for an antibody, which indicates the extent that the antigen satisfies the problem requirements.

5) Clone. In immunology, cloning means asexual propagation so that a group of identical cells can be descended from a single common ancestor. It is used to enlarge the search region.

6) Mutation. In immunology, mutation means the immune system recognizes external patterns from antibody gene mutation in order to obtain a higher affinity. Mutations take the search procedure out of a locally optimal region, and enable it to possibly enter a better region of the search space.

7) Selection. An immune algorithm takes a group of antigens from a population using an operation called selection. The selection operation serves the purpose of eliminating the relatively bad solution candidates and focusing the search operation on a relatively good portion of the solution space.

2.2　Realization of throughput scheduling based on the immune algorithm

Our motivations for utilizing the immune algorithm for the throughput optimal scheduling problems are manifold. First, the immune algorithm is suitable for problems with large search spaces. It is equipped with many tools to reduce the computational complexity and produce a diverse set of solutions. The fact that the immune algorithm operates on a population of solutions rather than a single solution implies that the algorithm makes parallel searches in the search space. Considering that the solution space in the throughput scheduling problems is enormous (even for 5 nodes, 3 frequencies, and 3 time slots, the size of the solution space is 245), the immune algorithm appears to be a suitable tool. Secondly, the immune algorithm can be conveniently implemented. The binary decision variablesXnftcan be easily encoded to a binary string.

Some key techniques are as follows:

1) Antigen representation (encoding). We use the binary encoded antigen which containsXnftvalues. Thus, the antigen [X111,X211,X311,X112,X212,…,X123,X223,X323], whereas the other antigen structure is [X111,X112,X113,X121,X122,…,X322,X323].Xnftis a gene bit of antibody.

2) Affinity evaluation. In this paper, the optimization model is described in Eq.(1). The affinity is a mapping of the value of Eq.(1) for a given antibody. SinceQis to be maximized, it can be stated that if an antibody has higher affinity, it is the better one.

The proposed algorithm for throughput optimal scheduling schemes is implemented as follows:

Step 1Initialization. Set the maximum iterative generationtmax. Sett=0, wheretis termed as the current iterative generation. Create an initial antibody population A(t) with sizekin accordance with antibody encoding in section 3.2. That is

A(t)={p1(t),p2(t),…,pk(t)}

(2)

where pi(1≤i≤k) is a candidate throughput scheduling scheme; A(t) is a set of candidate throughput scheduling schemes.

Here, some pre-knowledge is used to initialize the antibody piin order to accelerate algorithm convergence, which is proved by the latter simulation experiments. From constraint (1a), it is known that at least one time slot is assigned to each SU. Constraint (1b) makes certain that at most, one user can transmit at a particular time slot and frequency combination. Each antibody pi(1≤i≤k) that satisfies the constraints (1a) and (1b) will be a candidate.

Step 2Affinity evaluation. The affinities of all antibodies in A(t) are calculated according to Eq.(1) and it is denoted as

f(A(t))={f(p1(t),f(p2(t)),…,f(pk(t)}

(3)

If an antibody pi(t) (1

Step 3Proportional cloneTc. In this paper, B(t) is obtained by applying clone proliferationTcto A(t), and it is defined as

B(t)=Tc(A(t))={Tc(p1(t)),Tc(p2(t)),…,Tc(pk(t))}

(4)

Here, the clone scaleqifor each antibody pi(1≤i≤k) is proportional to its affinityf(pi(t)). That is

(5)

where Int() denotes the integer function, andncis a given value (nc>k). The antibody with a large affinity value (objective function value of Eq.(1)) has a largeqi.

(6)

Actually, clone proliferation on antibody pi(t) is to make multiple identical copies of it.

Step 4MutationTm. In this paper, it is defined as C(t)=Tm(B(t)). An adaptive mutation which associates the mutation probabilitympwith the evolutionary generation is designed. That is

(7)

wheretis the current evolutionary generation;tmaxis the maximum evolutionary generation.

The advantages of the mutation lie in its searching ability within a large scope in the early evolution process while it searches in a local scope in the latter evolution process, which can accelerate the convergence. After mutation, the population becomes

C(t)={p″1(t),p″2(t),…,p″z(t)}

(8)

In this paper, the mutation is done by exchanging the element one and element zero with each other with probabilitymp. The proposed mutation is easily realized and it does not violate the constraints.

Step 5Affinity evaluation. The affinities of all antibodies in C(t) are calculated according to Eq.(1) and it is defined as

f(C(t))={f(p″1(t),f(p″2(t)),…,f(p″z(t)}

(9)

Step 6Clone selectionTsis defined as

A(t+1)=Ts(C(t)∪A(t)=

(p1(t+1),p2(t+1),…,pk(t+1))

(10)

That is,kantibodies with a high affinity are selected from C(t) and A(t) to form the next population A(t+1).

Step 7Termination test. Iftmaxis reached, stop the algorithm. Output the antibody with the maximum affinity in A(t+1) as the result of the throughout scheme. Otherwise,t=t+1, and go to Step 3.

2.3　Computational complexity

Recall thatNdenotes the number of SU, andFdenotes the number of available frequencies. For the immune-based scheme, the total computational complexity is mainly composed of that for initialization, affinity evaluation, cloning, mutation, and selection. Given the population sizek, the clone scalenc(nc>k) and the maximum generationtmax, the procedure of population initialization, the affinity evaluation and proportional clone (Step 1 to Step 3) has the same computational complexity ofO(kFN) in each generation, while the procedure of mutation, affinity evaluation, selection (Step 4 to Step 6) has the computational complexity ofO(kncFN) in each generation. Hence, for each generation, the total computational complexity isO(3kFN+3kncFN). Sincenc>k, according to the properties of symbolicO[10,13-14], it can be denoted asO(ncFN). When the throughout scheduling is finished, it has the total computational complexity ofO(tmaxncFN).

The computer simulations show thattmaximplicitly depends onFandN. The more complex the search space is, the larger the number of generations should be. Thus, for givenncandtmax, the gradual computational complexity of the proposed algorithm isO(NF) in accordance with the properties of symbolicO.

A brief summary of the complexities of previous typical algorithms and our proposed algorithm is as follows. The complexity of algorithm in Ref.[3] isO(FN2), while the complexity of our proposed algorithm is the same as the algorithm in Ref.[4], which isO(FN).

3Simulation Results and Discussion

3.1　Experimental environments and parameter settings

We simulated the suboptimal schedulers and acquired theUnfvalues in OPNET Modeler, and we solved the optimization problems in CPLEX[15]. Additive white Gaussian noise (AWGN) channels are considered. In all the simulations, each SU has three primary neighbors in its interference range. The simulation results are the average of 100 independent tests. The parameter settings are as the same as that in Refs.[4-5]. There are three frequencies with interference temperature thresholds of 1 000, 2 000, and 3 000 K.

3.2　Sensitivity in relation to the immune algorithm parameters

Four parameters are to be set at the initialization phase: the antibody population sizek, the clone population sizenc, the mutation probabilitymp, and the maximum number of generationstmax. The sequential experimental design method of employing a series of small experiments each with a specific objective is a common method in experimental design[16], because the experimenter can quickly learn crucial information from a small group of runs that can be used to plan the next experiment.kandncdirectly affect the computational complexity of the algorithm[10-13]. If the givenkandncare large enough, the diversity of the population can be enhanced and the prematurity can be avoided in some extent, but the computational complexity will also be very large.tmaxclearly depends onFandN. The more complex the search space is, the larger the number of generations should be.mpis very important for local search in the algorithm. A largemphas the ability to produce more new antibodies, but it also has the probability to destroy some good antibodies. Whenmpis too small, the convergence speed is not quick enough to find the best solution in appointed generations.

Since the optimal choice is difficult to determine by theoretical analysis, it is important to analyze the performance affected by experiments in different cases. After trial and error, the parameters employed in the proposed immune algorithm are as follows: the number of generationstmaxis 100; the population sizekis 50; the clone scalencis 10; and the mutation probabilitympis 0.3.

3.3　The performances of the proposed algorithm

In order to evaluate the performances of the proposed algorithm, the effect of number of iterations (evolutionary generation) on throughout scheduling is studied, and the number of SUs is set to be 5. As it is evident from Fig.1, the throughout initially increases with the number of evolutionary generations and then gradually converges to the high value, close to an optimal point. It is also can be seen that the proposed method provides significant gain in throughout and fast convergence rate. The simulation results prove the effectiveness of the proposed immune operators. It also can be seen from Fig.2 that the evolutionary generation increases with the numbers of SUs. It is effective.

The results of different numbers of SUs are shown in Tab.1. It can be seen that the proposed algorithm gives consistent good results. First of all, the proposed solution yields better results than the MFS and PFS schedulers proposed in Ref.[4], at the same time being very close to the throughput optimal scheduler performance in Ref.[3].

Fig.1　Throughout vs. evolutionary generation

Fig.2　Evolutionary generation vs. different numbers of SUs

Tab.1　The results of relative algorithms for different numbers of SUs

Fig.3 presents the optimal throughput[3], MFS, and PFS[4]scheduling schemes compared with the proposed scheduling scheme. The algorithm in Ref.[3] can be regarded as the upper-bound of the proposed heuristic algorithm.

Fig.3　Comparison of different algorithms

Fig.4 shows the performances comparisons of relative algorithms with the increase in the numbers of SUs. It can be seen that the proposed algorithm performs excellently. It is very close to the optimal performances in Ref.[3] and is better than the algorithm in Ref.[4].

All in all, the proposed scheduling scheme achieves performances close to the optimal scheduling operating with much lower complexity. However, the iterations in the simulation results reveal that the proposed algorithm is computationally more costly than the MFS and the PFS schedulers in Ref.[4]. Nevertheless, when they are compared with the throughput performance, we can see that the proposed algorithm is approximately twice as good as the MFS and the PFS schedulers. Moreover, the proposed algorithm is computationally more efficient than the classical branch and bound algorithms that are used to solve binary integer programming problems. Therefore, ther proposed algorithm presents a very reasonable tradeoff between computational complexity and performance.

Fig.4　Throughout vs. numbers of SUs

4Conclusion

The immune algorithm-based suboptimal scheduling for the throughput problem in cognitive radio networks is proposed. The simulation results show that the proposed algorithm is very close to optimal performance with a relatively lower complexity. Hence, it can be concluded that the proposed scheduling is more suitable for slowly varying spectral environments. Considering that IEEE 802.22 networks that operate on the TV broadcast bands that are slowly changing, it can be confidently concluded that the proposed algorithm can operate in realistic network settings, and provide useful solutions for the open research problem.

References

[1]Akyildiz I, Lee W, Vuran M, et al. Next generation/dynamic spectrum access/cognitive radio wireless networks[J].ASurveyComputerNetworks, 2006, 50(13): 2127-2159.

[2]Busson A, Jabbari B, Babaei A, et al. Large overlaid cognitive radio networks: from throughput scaling to asymptotic multiplexing gain[J].JournalofCommunicationsandNetworks, 2014, 16(1): 67-80.

[3]Tian Z, Leus G, Lottici V. Joint dynamic resource allocation and waveform adaptation for cognitive networks[J].IEEEJournalonSelectedAreasinCommunications, 2011, 29(2): 443-454.

[4]Gözüpek D, Alagöz F. Throughput and delay optimal scheduling in cognitive radio networks under interference temperature constraints[J].JournalofCommunicationsandNetworks, 2009, 11(2): 147-155.

[5]Arshad K, Mackenzie R, Celentano U, et al. Resource management for QoS support in cognitive radio networks[J].IEEECommunicationsMagazine, 2014, 52(3): 114-120.

[6]Chaporkar P, Kar K, Luo X, et al. Throughput and fairness guarantees through maximal scheduling in wireless networks[J].IEEETransactionsonInformationTheory, 2008, 54(2): 572-594.

[7]Chai Zhengyi, Liu Fang. A novel immune optimization algorithm for fairness resource allocation in cognitive wireless network[J].WirelessPersonalCommunications, 2013, 69(4): 1671-1687.

[8]He A, Kyung K B,Newman T R, et al. A survey of artificial intelligence for cognitive radios[J].IEEETransactionsonVehicularTechnology, 2010, 59(4): 1578-1592.

[9]Zhao Jun, Liu Quanli, Wang Wei, et al. A parallel immune algorithm for traveling salesman problem and its application on cold rolling scheduling[J].InformationSciences, 2011, 181(7): 1212-1223.

[10]Chai Zhengyi, Liu Fang. On the use of immune clonal optimization for joint subcarrier and power allocation in OFDMA with proportional fairness rate[J].InternationalJournalofCommunicationSystems, 2013, 26(10): 1273-1287.

[11]Luh G-C, Chueh C-H. A multi-modal immune algorithm for the job-shop scheduling problem[J].InformationSciences, 2009, 179(10): 1516-1532.

[12]Yang Dongdong, Jiao Licheng, Gong Maoguo, et al. Artificial immune multi-objective SAR image segmentation with fused complementary features[J].InformationSciences, 2011, 181(13): 2797-2812.

[13]Tarcisio F, Maciel M, Anja K. On the performance, complexity, and fairness of suboptimal resource allocation for multi-user MIMO-OFDMA Systems[J].IEEETransactionsonVehicularTechnology, 2010, 59(1): 406-421.

[14] Banaei A, Georghiades C N, Cui S G. Maximum-minimum throughput for MIMO systems in cognitive radio networks[J].IEEETransactionsonWirelessCommunications, 2014, 13(6): 3042-3055.

[15]Sadr S, Anpalagan A, Raahemifar K. Radio resource allocation algorithms for the downlink of multiuser OFDM communication systems[J].IEEECommunicationsSurveys&Tutorials, 2009, 11(3): 92-106.

doi:10.3969/j.issn.1003-7985.2015.04.001