### Paper Menu >>

### Journal Menu >>

Communications and Network, 2013, 5, 22-26 http://dx.doi.org/10.4236/cn.2013.53B2005 Published Online September 2013 (http://www.scirp.org/journal/cn) Cognitive Radio Spectrum Allocation Strategy Based on Improved Genetic Algorithm Bin Hou, Yunxiao Zu, Weihai Li, Gang Liu, Junjie Ding School of Electronic Engineering, Beijing University of Post & Telecommunication, Beijing China Email: robinhou@163. com Received March, 2013 ABSTRACT With the rapid development of wireless communication industry, shortage situation of spectrum resource is increasingly significant. It has become an important topic to study cognitive radio spectrum allocation algorithm that is of higher spectrum utilization ratio, less system power consumption and better algorithm efficiency. Analyzes spectrum allocation models based on genetic algorithm, and then puts forward new improved genetic algorithm. The algorithm adopts niche crowding operation to avoid individual inbreeding. It adaptively adjusts crossover and mutation probability to keep them always in the appropriate state. It provides more equal individual competition opportunity by hierarchical meas- ures, which can effectively avert premature convergence to local optimal solution. It obviously improves the district's total transfer rate on the premise that it has met the requirements of minimum user transfer rate and limitations of max- imum total power and maximum bit error rate. Simulation results prove the effectiveness of the proposed algorithm. Keywords: Cognitive Radio; Spectrum Allocation ; Genetic Algorithm; Niche; Adaption 1. Introduction Under the background of increasingly shortage of spec- trum resource, realization of rational allocation for cross band spectrum and utilized techno logy of cognitive radio (CR) are becoming focus of research in wireless commu- nication arhjyjea. Though cognitive radio has achieved high attention from researchers, many key technology problems remain to be solved and there is still a long way to go for commercial application. Due to the fact that CR network s are made up of plen- tiful high density distribution of base stations, sensor nodes and users, resource allocation should take fully into account parameters such as free carrier quantity, rate needs of users, channel quality, bit error rate constraints and transmission power, etc. But with the growth of users and subcarrier number, complexity of resource allocation problems in cognitive radio networks is increasing ex- ponentially. Traditional resource allocation methods can no longer meet demand [1]. Besides, Equipment power, bit error rates and computational complexity o f cognitive radio network are restricted owing to its properties. In this case, better resource allocation methods are required to ensure transmission quality and network performance and improve network cap acity and transfer rate of cogni- tive radio network. This paper puts forward a kind of cognitive radio spectrum allocation strategy based on improved genetic algorithm. The simulation results indicate that under the circumstances of same system total power, minimum user rate and bit error rate, this proposed allocation algo- rithm is superior to traditional common genetic algorithm on spectrum efficiency. 2. Improved Genetic Algorithm Genetic Algorithm (GA) is a kind of algorithm that imi- tates biological evolution mechanism to search global optimal solution to target problem. It puts the potential solution in problem space as a biological individual, and encodes the individual. It imitates biological evolution process, carries out selection, crossover and mutation operation circularly and finally chooses the individual of optimal performance as the solution to a problem [2]. Genetic algorithm is appropriate to large and complex search problems, and cognitive radio spectrum allocation is such a problem—when allocating spectrum, there is an enormous quantity of available distribution schemes. It’s unpractical for enumerative search, and input parameters influence each other. Thus, genetic algorithm can be applied to research on cognitive radio spectrum allocation issue. Consider problems existing in traditional genetic algo- rithm as follows: (a) towards the end of algorithm run- ning, individual genetic is approximate and their off- spring cause inbreeding, thus resulting in population ge- netic redundancy. (b ) Crossover and mutatio n probability C opyright © 2013 SciRes. CN B. HOU ET AL. 23 is fixed, which influences algorithm speed. (c) The popu- lation is single. If there exists some individual whose fitness is more outstanding in the initial population, then it’s easy to converge to the local optimal solution [2, 5]. The shortage of the traditio nal genetic algorithm is modi- fied and improved in this paper. In view of problem (a), adopt niche crowding opera- tion to remove individuals that have similar gene. In view of problem (b), adaptively adjust crossover and mutation probability to keep them always in the op- timal range. In view of problem (c), take stratified measures to di- vide the population into more child population. Inde- pendently run low-level genetic algorithm in each child population. When running up to certain algebra, merge the child population and then turn to high-level genetic algorithm. Thereby reduce occurrence probability of lo- cal optimum solution. 3. Spectrum Allocation Model Design 3.1. Scene Design Suppose a cell cellular radius is 1 km and a base station tower’ height is 40 m. Apply shadow fading model and supposes that shadow effect doesn’t change with time. The channel gain of user m at subcarrier n is ,mn dB. The average power spectral density of WGN (white Gaussian noise) at the receiving end is W/Hz. Ac- cording to empirical value, set the value of 0 to 10-12 W/Hz [2]. The number of available subcarriers in a cell and total users is 2000 and 50. Every subcarrier band- width is 30 KHz. Descending frequency band is 1900- 1930MHz and ascending frequency band is 1950-1980 MHz. Adopt MQAM (Multiple Quadrature Amplitude Modulation) modulation and permissible highest modu- lation order is 256. The MQAM modulation order and transmission power of user m at subcarrier n are ,mn and ,mn. Bit period ,mn equals to 100us. If a subcar- rier has not been used by any user, then set ,mn to 0. Tolerable maximum BER (bit error rate) of every user is e, it set to 0.0005%. Minimum rate demand min R equals to 64 Kbits/s. Maximum transmission power of base station in a cell is 80W. b W 0 NN W P x T P ma G 3.2. Channel Gain Matrix Design Suppose the channel gain of user m at subcarrier n is dB. It is presented by matrix B. ,mn b 1,1 1,21,1 1, 2,12,2 2,12, , 1,1 1,21,1 1, ,1,1, 1, NN NN mn MMMN MN M MMNMN bbb b bbb b b B bbb b bbb b Formula (2) is for path loss value of free space[3]. (dB) 32.45+10lg20lg L fd (2) In the formula, f represents the center frequency of carrier and d represents the distance (km) between receiv- ing antenna and transmitting antenna. Considering shadow fading effect, channel gain is ex- pressed as Formula (3) [3]. (dB) s(dB) , mn bL (3) In the formula, s is level variation produced by shadow effect. When under simulation, assume that s is a normal distribution random variable with 0 dB mean. In macro-cellular, the standard deviation ranges from 5 dB to 12 dB. In the micro-cellular, the standard devia- tion ranges from 4 dB to 13 dB. The typical value of is 8 dB and it is set to 8 dB for simulation. 3.3. Target of Resource Allocation Solution The target of CR resource allocation discussed in this paper is described as follows. On the basis of channel gain of each subcarrier, determine which subcarrier be allocated to which users, transmission power of each subcarrier and modulation order of MQAM to achieve total maximum rate of the CR system. In addition, the following constraint conditions should be satisfied. 1) The transfer rate of each user should be higher than min imu m rat e min Mbits/s, as high as possible. 2) BER of each user is lower than the maximum BER e, as low as possible. 3) The system total power consumption is less than power consumption upper limit dBm, as little as possible. RP xma G 3.4. Fitness Function Design According to the target of resource allocation, designed fitness function is delivered by formula (4): , 11 2, , () 2 NM Am nm mn mn fA DS log W S n (4) (1) () A f A stands for fitness of resource allocation scheme A. D is bandwidth of subcarrier. ,mn Represents spec- trum utilization and ,mn represents MQAM modula- tion order of user m at subcarrier n. Therefore, the value of fitness function is system total transfer rate. S M The system should meet the three constraints described in 3.3. If anyone of them is not satisfied, then set the fit- ness function value of the individual to 0, resulting that it cannot participate in the generation of next population. Hence we can get individual fitness function modified from constraints. Copyright © 2013 SciRes. CN B. HOU ET AL. 24 ,, 11 1 ,( ( ,)) 0, NM N mnmnmin me nm n DSDSRPPgABG ,, Others () A fA max (5) 4. CR Resource Allocation Based on M improved and Child Population Formlays matrix coding form adopted by in- Improved Genetic Algorithm ain steps of CR spectrum allocation based on genetic algorithm are individual coding, child population division, niche crowding operation, excluding individuals that don’t accord with constraint conditions, selection, crossover and mutation of low-level genetic algorithm, adaptive adjustment of low-level algorithm parameters, selection, crossover and mutation of high-level genetic algorithm and adaptive adjustment of high-level algo- rithm parameters. 4.1. Individual Coding Division ula (6) disp dividuals. Figure 1. CR Spectrum Allocation Flow Chart Based on Improved Genetic Algorithm. 1,1 1,2 aa 1, 11, 2,12,22,12, , 1,11,21, 11, ,1,1, 1, ,,, =( ) NN NN mn MM MNMN MMMNMN mnmn mn a a aaa a a A aaa a aaaa aWP ， (6) Matrix A represents one kind of spectrum resource al- lo ubca cation mode. There are M user facilities and N subcar- riers in CR system. ,mn W represents MQAM modula- tion order and ,mn Presents transmission power of user m at srrier n in CR system. The two parameters are randomly generated, and each subcarrier can at most be occupied by one user facility. There are only six mod- ulation modes of every subcarrier. The items in expres- sion: ,{0,16,32,64,128,256} mn W rep are on behalf of no , 64QAM, 128QAM and 256QAM modulation. When the algorithm begi use, usi ns running, first it randomly ge ng 16MQAM, 32QA nerates X Y initial individuals with matrix A for- mat. Theyitute the initial population P the algo- rithm. Then P divided i nt o X child population const 12 1 ,,' XX PP PP by line. Every child population includes Y individu- 4.2. Selection, Crossover and Mutation rithm Low i P als. Operation of Low-level Genetic Algo -level genetic algorithm is meant for child popula- tion. When individual fitness of each resource allocation way is figured out, the probability of the i-th individual , x i A being selected in child population ,1 ,2, [, ] x xx xY PAA A is determined by the following formula[. 3] , ( Axi fA , , 1 ) () () selectlowx iY Axy y pA fA (7) , () Axi f A population stands for the i-th individual fitness of child x P. Operate on child population x P for roulette selection based on fitness. The better fitn the individual of child population owns, the larger probabil- ity the individual is selected. Then new child population can form. After se ess lection operation, do crossover operation on ne exchange for m, that is, randomly in terchange individuals w population. The crossover operation of low-level genetic algorithm uses single-point crossover. Cross po- sition is selected by roulette wheel selection. Mutation operation of low-level genetic algorithm adopts two-line Copyright © 2013 SciRes. CN B. HOU ET AL. 25 from two lines of selected matrix, as shown in Figure 2. 4.3. Niche Crowding Operation of Low-level Genetic Algorithm tion, croseration with the initial non- Blend the new formed child population after selec sover and mutation op iterated child population, forming new child population with 2Yindividuals. Make use of formula (8) to com- pute the hamming distance between every two individu- als. 2 1 1, 2,,1 || MiMN AA || ()1,2, , ij ikjk k a ajiiMN (8) When |||| ij A AL with lower fitness , impose Penalty Function o dividual between n in- i A and j A to re- du v ver and Mutation Probability ) ce this tness. L is the minimum hamming distance limit between two individuals, whosealue is 1/3 of average hamming distance of the population. Rank the child population individuals in descending order de- pending on new fitness, and then choose the first Y indi- viduals to compose new population [4]. 4.4. Adaptive Adjustment of Crosso individual’s fi Formula (9) reveals crossover probability. (FA ,, is the crossover probability of individual , crosslows isj A , s i A and , s j A in population s P. 1 on the basis of empirical value. , () Asi k is constant coficsetefient , to 0.1 f A , ( Asj fA is the fitness of cssover individuals. maxA f is the maximum fitness in and ) ro s P , and minA fitness. f is the minimum max ,, ,, 1max min 2()() AAsiAsj cross ff fA F (,) lows isjAA A AAkff (9) Formula(10) reveals mutation probability. is stant coefficient , set to 0.02 on the basis of empirical va 2 kcon- lue. , () Asi f A is the fitness of mutation operation in- dividuals. maxA f is the maximum of individual fitness in populat minA f is the minimum of individual fitness. ion, and , ,2 max min () Asi fA () cross lows iAA FAk ff (10) 4.5. Selection, Crossover and Mutation Operation of High-level Genetic Algorithm - latio - en- tia results. When BER limit of N jN iN MN High-level genetic algorithm is meant for the total popu n. When low-level genetic algorithm has independ ently run a certain iterative algebra in each child popula- tion, merge all child population into total population P. Do roulette selection operation on P based on fitness. The crossover operation of high-level genetic algo- rithm adopts uniform crossover [6]. Every point is pot l intersection. According to the 0-1 sequence that is randomly generated and equals the number of individual DNA bits, two father populations randomly choose indi- viduals in accordance with corresponding position of 0-1 sequence to generate two child populatio ns. 5. Analysis of Simulation Results Simulate for 50 times, and take average there are 50 users in the system and the each user is 0.0005%, Figure 3 displays the variation of system transfer rate with traditional genetic algorithm iteration times. As can be seen, system transfer rate of traditional genetic algorithm is steadily rising with itera- tion times, and ultimately converge to a subopti mal value. By comparison, system transfer rate of improved genetic algorithm present in this paper is rapidly rising with it- eration times, and soon reaches a high level. Therefore, the system total transfer rate obtained from resource al- location scheme based on improved genetic algorithm is superior to that of traditional genetic algorithm. 1,1 1,1,1N aaa 1, ,1 ,,1 , ,1 ,,1 , ,1 ,,1 , * ii N j mutation jjN i MMN M a aa aa AA aa aa aa aa Figure 2. Mutation operation of low-level genetic algorithm. Figure 3. System Total Transfer Rate Comparison Between Improved Genetic Algorithm and Traditional Genetic Al- gorithm. Copyright © 2013 SciRes. CN B. HOU ET AL. Copyright © 2013 SciRes. CN 26 Figure 4. System Final Total Transfer Rate Variation Amount of Users. ays the variation of system final ans with amount of users when the BER limit of ea rum allocation problems in cognitive r comes up with resource alloca- 7. Acknowledgements y the Youth Research and REFERENCES [1] P. Kolodzy, Sorce: Findings and . Wang and L. M. Cao, “Genetic Algorithm—— its on Detection in Low SNR. with Figure 4 displ total Recommendations, International Symposium on Ad- vanced Radio Technologies (ISART), March 2003, pp. 1-3 [2] X. P trfer rate ch user is 0.0005% and the amount of total users is 10, 50, 100, 150 or 200. As can be seen, with increasing of users in system, the total transfer rates decline due to congestion. However, if apply the improved algorith m in this paper, all system total transfer rate obtained from resource allocation scheme increases significantly com- pared to traditional genetic algorithm. 6. Conclusions In allusion to spect radio network, this pape tion scheme based on improved genetic algorithm and constructs steps of the algorithm and related parameters. The simulation results demonstrate that in comparison to simple genetic algorithm; under the condition of the same system total power limit, minimum user rate needs and maximum BER limit, the system total transfer rate of improved genetic algorithm increases substantially. This work was supported b Innovation Program of the Electronic Engineering School, BUPT. (Grant No. 2012RC0304 ). pectrum Policy Task F Theory, Application and Software Implementation,” Xi’an Press of Xi'an Jiaotong University, 2002, pp. 68-79. [3] C. C. Zeng and Y. X. Zu, “Cognitive Radio Spectrum Allocation Based on Niche Adaptive Genetic Algorithm, 2011 The IET International Conference on Communica- tion Technology and Application, Beijing, 2011, pp. 1-4. [4] B. Wild and K. Ramchandran, “Detecting Primary Re- ceivers for Cognitive Radio Applications. in Proc. IEEE Symp. New Frontiers Dynamic Spectrum Access Net- works, 2005, pp. 124-130. [5] R. Tandra, Fundamental Lim International Conference on Wireless Networks, Com- munications and Mobile Computing, 2005, pp. 464-469. [6] Y. X. Zu and J. Zhou, Cross-layer Resource Allocation and Packet Scheduling Scheme in Cognitive Radio Net- work, Invention Patent of People's Republic of China， 2011, pp. 1-4. |