TMCnet News
A Discrete Geese Swarm Algorithm for Spectrum Assignment of Cognitive Radio [Sensors & Transducers (Canada)](Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: In order to solve spectrum assignment problem, this paper proposes a discrete geese swarm algorithm (DGSA) based on particle swarm optimization and quantum particle swarm optimization, and we evaluate the performance of the DGSA through some classical benchmark functions. The proposed DGSA algorithm applies the quantum computing theory to particle swarm optimization, and thus has the advantages of both quantum computing theory and particle swarm optimization. We also use it to solve cognitive radio spectrum assignment problem. The new spectrum allocation method has the ability to search global optimal solution under different network utility functions. Simulation results for cognitive radio system are provided to show that the designed spectrum allocation algorithm is superior to some previous spectrum allocation algorithms. Copyright © 2013 IFSA. Keywords: Geese Swarm Algorithm, Spectrum Assignment, Quantum Particle Swarm Optimization, Network Utility Function, Cognitive Radio. (ProQuest: ... denotes formulae omitted.) 1. Introduction With the development of radio communication technology, spectrum resources have been more widely employed, but the scarceness of wireless spectrum prevents the continual development of wireless communication. In order to fully utilize the scarce spectrum resources, dynamic spectrum access becomes a promising approach to improve the efficiency of spectrum usage. This new networking paradigm is also referred to as next generation networks as well as cognitive radio networks [1], This new wireless technology can sense the wireless environment, search for available spectrum resources and allocate spectrum dynamically, so that the efficiency of spectrum usage is improved and the capacity of wireless communication system is increased. Cognitive radio has the ability to sense, to learn, and to adapt to the outside world [2]. Assuming that the environmental conditions are static during the time it takes to perform spectrum assignment, an allocation model is proposed in [3], and color sensitive graph coloring (CSGC) is used to solve the allocation problem. Cognitive radio (CR) provides a feasible solution for dynamic spectrum access. It solves the contradiction between the scarcity of spectrum resources and increasing radio access demands through letting the secondary users use the available spectrum while avoiding interference with the primary users and their neighbors. This new wireless technology can sense the wireless environment, search for available spectmm resources and allocate spectrum dynamically, so that the efficiency of spectrum usage is improved and the capacity of wireless communication system is increased. Cognitive radio has the ability to sense, to learn, and to adapt to the outside world. Based on its interaction with the environment, cognitive radio enables the users to communicate over the most appropriate spectrum bands through four main functionalities: spectrum sensing, spectrum management, spectrum mobility and spectrum sharing. Spectrum sharing, i.e. spectrum allocation, one important part of the cognitive radio technology, which decides the network reward or the throughput of the secondary users directly, plays a vital role in cognitive radio system performance. This paper focuses on how to share the available spectmm bands which are not occupied by primary users between all the secondary users. There exist a lot of research efforts on the problem of spectrum sharing in cognitive radio networks. Based on centralized or distributed architecture, cooperative or non-cooperative spectrum allocation behavior, overlay or underlay spectrum access technique, lots of models have been proposed for dynamic spectrum access, including game theory [7], pricing and auction mechanisms [8], local bargaining [9], and graph coloring [10]. Assuming that the environmental conditions are static during the time it takes to perform spectrum assignment, an allocation model is proposed in [11-13], and color sensitive graph coloring (CSGC) is used to solve the allocation problem. As the spectrum assignment problem can be inherently seen as an optimization problem, and exact and analytical methods do not produce optimal solution within a reasonable computation time, we may use evolutionary algorithms, which are capable of finding near-optimal solutions to the problem of cognitive radio spectrum allocation. Evolutionary algorithms are stochastic search methods that mimic natural evolution and the social behavior of species. The first evolutionary-based technique introduced in the literature is genetic algorithm (GA), which attempts to simulate the phenomenon of natural evolution [14-17]. Quantum genetic algorithm (QGA) combines quantum computation with genetic algorithm [18], while particle swarm optimization (PSO) [19] is inspired by the social behavior of bird flocking. The above three intelligent algorithms are representatives of classic evolutionary algorithms, which have disadvantages of local convergence for spectrum assignment [18-19]. Swarm intelligence and quantum information are the rich sources of inspiration for inventing new intelligent algorithms. Swarm intelligence is a population-based stochastic optimization technique and well adapted to the optimization of nonlinear functions in multi-dimensional space. Swarm intelligence algorithms are important scientific fields that are closely related to physical and biological phenomenon existing in nature, and some algorithms are widely studied for application. At present, particle swarm optimization [20-21] and ant colony optimization [22] were successfully applied to solve engineering problem. In the quantum information theory, we must broaden definition of information as merely a string of Os and Is and examine the consequence of the quantum nature of media for information, such as its uncertainty and entanglement of states [23]. The researches on the combing of quantum mechanism with other classical methods focus on two respects, one is designing new quantum algorithm in the classical computer [24]; the other is introducing the quantum idea into classical algorithm and modifying the conventional algorithms to get a better performance [25-26]. Now, much attention is paid to quantum computing and swarm intelligence because it has the characteristics of strong searching capability, rapid convergence, short computing time, and small population size [27]. But it is complexity algorithm which using quantum individuals. All quantum evolutionary use quantum bit and quantum gate in quantum domain. A simple evolutionary algorithm with high performance is vital for function optimization and engineering application. In order to design the simple discrete geese swarm algorithm to solve optimization problem, quantum bee swarm optimization [22] is improved by good evolutional equations and simple updating equations. A simple evolutionary algorithm with high performance is vital for function optimization and engineering application. Our method, discrete geese swarm algorithm (DGSA), which is based on PSO and simulating of quantum computing theory, has the advantages of both PSO and quantum computing. 2. Description of Cognitive Spectrum Assignment Model The general spectrum assignment model consists of channel availability matrix, channel reward matrix, interference constraint matrix and conflict free channel assignment matrix. Assume a network of secondary users indexed from 1 to N competing for spectrum channels indexed from 1 to M which are non-overlapping orthogonal. Each secondary user can be a transmission link or a broadcast access point. The channel availability matrix L = {C K,» £ {(UHwxm is a N by M binary matrix, representing the channel availability. Secondary user n determines whether channel m is available by detecting the signals of primary users, and if it is not occupied by primary users, which means channel m is available to user« , then/n ffl = 1 , and ln m = 0 otherwise. The channel reward matrix B = {bn m }NxM is an N by M matrix, representing the channel reward, where bn m represents the reward that can be obtained by user n using channel m. As two or more secondary users may use the same channel at the same time, they may interfere with each other. The interference constraint matrix C = Kk,m \Cn,k,m ^ {0,1} }WxWxA/ is a N by N by M matrix representing the interference constraint among secondary users, where cnkm = 1 if users n and k would interfere with each other if they use channel m simultaneously, and cnkm = 0 otherwise. In particular, cn k m = 1 - ln m if n = k , which is only decided by the channel availability matrix. In real applications, the spectrum environment varies slowly while users quickly perform networkwide spectrum assignment. We assume that the location, available spectrum, etc. are static during the spectrum allocation, thus L , B and C are constants in an allocation period. The conflict free channel assignment matrix ... represents the channel assignment, where an m = 1 if channel m is allocated to secondary user n , and anm = 0 otherwise. A must satisfy the interference constraints defined by ... .Given a conflict free channel assignment, the reward user n gets is defined as rn - ... We use ... to represent the reward vector that each user gets for a given channel assignment. Let A(L,C)(VxAÍ be the set of conflict free channel assignment for a given L and C. The spectrum allocation is to maximize network utilization U{R) . Given the model above, the spectrum allocation problem can be defined as the following optimization problem: ... (1) where A* is the optimal conflict free channel assignment matrix. In this paper, we consider the objective functions proposed by [8]: Max-Sum-Reward (MSR): ... (2) Max-Min-Reward (MMR): ... (3) Max-Proportional-Fair (MPF): ... (4) In this model, we assume that environmental conditions such as user location, available spectrum bands are static during the time it takes to perform spectrum assignment. This corresponds to a slow varying spectrum environment where users quickly adapt to environmental changes by re-performing network-wide spectrum allocation. 3. Spectrum Assignment Based Discrete Geese Swarm Algorithm 3.1. Discrete Geese Swarm Algorithm Discrete geese swarm algorithm is a novel multiagent optimization system inspired by social behavior metaphor of agents. Each agent, called goose, flies in an /-dimensional space according to the historical experiences of its own and its colleagues. There are h geese that are in a space of / dimensions in a geese swarm, the zth goose's position in the space is ... , (z = l,2,-,A ), which is a latent solution. The zth goose's velocity is ... and until now the best position (the local optimal position) of the zth goose is ... ). ... is the global optimal position discovered by the whole geese swarm until now. At each generation, the zth goose is updated by the following moving equations: ... (5) ... (6) ... (7) where (z = 1,2,-,A) , (d = 1,2,***,/) , r is uniform random number between 0 and 1, cx is mutation probability which is a constant among ... is uniform random number, superscript Z + l and t represent number of iterations, (v/1 )2 represents the selection probability of bit position state in the (t + l)th generation. The value of ex , e2 and e2 expresses the relative important degree of p(. , pg and p(._2 in the flying process. 3.2. Spectrum Assignment Using Discrete Geese Swarm Algorithm The initial position population of geese swarm is randomly chosen from the solution space. All velocity may be initialized as 1 / yi2 .The goal of the objective function is to evaluate the status of each goose. In the spectrum allocation of cognitive radio, the target of position optimization is the maximization of network utilization function. The proposed DGSA applies the quantum computing theory to the geese swarm optimization. In this algorithm, every velocity is updated by geese swarm theory. The particle swarm optimization is able to locate the appropriate regions for a solution in the search space, but fairly slow to find the nearoptimal solution using the moving equations that are random in nature. It has the disadvantage of local convergence. However, the proposed DGSA has the advantages of both swarm theory and the swarm optimization and can find the near-optimal solution compared to other algorithms. Summarizing, the proposed new algorithm can overcome the disadvantages of the previous intelligence algorithm. According to the above analysis, the work processes of discrete geese swarm algorithm for spectrum allocation are shown below: Stepl: Given L = |/" e {0,1}, ... AND ... ' set the length of the position and velocity as ... and set L, = {{n,m)\lnm = i} such that elements in L, are arranged increasingly in n and m. Therefore, the number of elements in L, is equal to the value of l Step 2: Randomly generate an initial geese swarm. Step 3: For all geese positions, map the fh bit of the position to anm, where (n,m) is thefh element in L, and 1 < j < l. For all m , search all (n,k) that satisfies cnkm - 1 and n^k , and check whether both of the two bits corresponding to the element in the /1th line and m01 column of A and the element in the ä* line and m01 column of A are equal to 1 ; if so, randomly set one of them to 0. Step 4: Compute the fitness of each goose. Step 5: Renew each goose's local optimal position. Update the global optimal position as evolutionary objective of the whole geese population. Step 6: Update velocities and positions of geese swarm. Step 7: If it reaches the predefined maximum generation, stop and output outcome; if not, go to step 3. 4. Experiment Results of Spectrum Assignment Based on Discrete Geese Swarm Algorithm The commonly used algorithm to solve the spectrum allocation problem is color sensitive graph coloring algorithm (CSGC). For more information of CSGC, please refer to paper [11]. In order to evaluate the performance of the proposed DGSA-based spectrum allocation method, we compare it with CSGC and other evolutionary algorithms in our simulations. In this paper, we set initial population and maximum generation of the four evolutionary algorithms identical. For GA[18], PSO[18]and QGA[19], the parameters are set according to reference. For DGSA, we set ex - 0.06, e2 - 0.03, e2 - 0.01, and c, = 0.001//. For GA, QGA, PSO and DGSA, the population size is set to 20. All intelligence algorithms will be terminated at the same maximal iterations (1000). During the simulation, B,L,C are generated by the pseudo code for modeling network conflict graph in the paper [11]. CSGC used the non-collaborative labeling rule. For Fig. 1, we set the number of secondary users (A) to 18, the number of channels (M) available to 16, the number of primary users(K) to 14 , and see the performance of the five algorithms. For Fig. 1, we set the number of secondary users to 14, the number of channels available to 13. Figs. 1-3 illustrate the performance gain offered by the DGSA approaches using Max-Sum-Reward utility function and MaxMin-Reward respectively. When all simulation conditions are identical, and CSGC, QGA, PSO and GA are also included, they show the target gap of performance. We can see that the average reward obtained by GA, QGA,PSO and DGSA after 200 generations are better than CSGC, which validates the effectiveness of the proposed evolutionary algorithms-based spectrum allocation methods. DGSA performs the best under objectives MSR, MMR and MPF in terms of convergence value, while QGA and GA has similar performance under objectives MSR, MMR and MPF. Even though GA and QGA perform better than CSGC, the convergence values after 400 generations by DGSA are still higher than those obtained by GA, PSO and QGA. For both two simulations, DGSA performs better than GA, PSO and QGA in terms of convergence value. We set that the number of secondary users increases while the number of primary users and the number of channels available remain 14 and 16 respectively. Increasing the number of secondary users in one area, thus increases the user density, and then creates additional interference constraints. So from Tables 1-3, we can see that the average reward degrades as the number of secondary users increases. Also, we can see that our method is better than other methods. Tables 1-3 show the DGSA is superior to GA, QGA, PSO and CSGC. We set that the number of channels available increases while the number of secondary users and the number of primary users remain constant. Increasing the number of channels available in one area makes secondary users get more reward from the increasing channels, so the reward upgrades as the number of channels available increases. Tables 4-6 clearly show that the DGSA achieves near-optimal performance from 10 to 30 channels. Although the GA, the QGA and the PSO have good performance, in some cases they are unable to reach the optimal solution in limited iterations. As is observed above, the DGSA shows good performance. So from Tables 4 - 6, we can see that the average reward upgrades as the number of channels increases. Also, we can see our method is better than other methods. Tables 4-6 show the DGSA is superior to GA, QGA, PSO and CSGC. 5. Conclusion and Future Work This paper has proposed a DGSA algorithm which is a novel algorithm for discrete optimization problems. Based on DGSA, we have proposed a spectrum allocation method. Experimental results show that our method not only improves the reward gotten by the secondary users, but also has better convergence rate. In the simulation, we also assume that available spectra are static during the time it takes to perform spectrum assignment. But if we consider a dynamic network, spectrum allocation becomes a more complex problem, and all of the algorithms need to compute spectrum allocations again. So, an adaptive approach should be developed to adapt the environment change and the change of spectrum availability. Acknowledgements This research has been supported by National Natural Science Foundation of China under Grant 61201410 and 61072086. Authors are grateful to their colleagues from China Ship Development and Design Center for providing helpful comments. References [1] . I. F. Akyildiz, W. Lee, M. C. Vuran, S. Mohanty, Next generation/dynamic spectrum access/cognitive radio wireless networks: a survey, Computer Networks, 50,2006, pp. 2127-2159. [2] . F. L. Liu, S. M. Guo, Q. P. Zhou, An effective wideband spectrum sensing method based on sparse signal reconstruction for cognitive radio networks, Progress in Electromagnetics Research, Vol. 28, 2012, pp. 99-111. [3] . L. L. Zhou, H. B. Zhu, and N. T. Zhang, A secondorder cone programming approach for robust downlink beamforming with power control in cognitive radio networks, Progress in Electromagnetics Research, Vol. 18, 2011, pp. 221-231. [4] . S. Haykin, Cognitive radio: brain-empowered wireless communications, IEEE J. Select. Areas Commun. Vol. 23,2005, pp. 201-220. [5] . B. O. Obele, M. Iftikhar, Determining optimal sensing time for multi-radio multi-channel cognitive radios, Progress in Electromagnetics Research, Vol. 22,2011, pp. 241-258. [6] . R. Urban, P. Fíala, T. Kriz, Stochastic description of wireless channel for cognitive radio, in Proceedings of the Progress in Electromagnetics Research Symposium PIERS, 2013, pp. 38-42. [7] . N. Nie and C. Comaniciu, Adaptive channel allocation spectrum etiquette for cognitive radio networks, in Proceedings of the IEEE DYSPAN, 2005, pp. 269-278. [8] . J. Huang, R. Berry, and M. L. Honig, Auction-based spectrum sharing, ACM Mobile Networks and Applications (MONET), Vol. 11, No. 3, 2006, pp. 405-418. [9] . L. Cao and H. Zheng, Distributed spectrum allocation via local bargaining, in Proceedings of the IEEE DYSPAN, 2005, pp. 475-486. [10] . H. Zheng and C. Peng, Collaboration and fairness in opportunistic spectrum access, in Proceedings of the 40th Annual IEEE International Conference on Communications (ICC), 2005, pp. 3132-3136. [11] . C. Peng, H. Zheng, B. Y. Zhao., Utilization and fairness in spectrum assignment for opportunistic spectrum access, ACM Mobile Networks and Applications, Vol. 11,2006, pp. 555-576. [12] . M. Akbari, M. Riahi Manesh, Maximizing the probability of detection of cooperative spectrum sensing in cognitive radio networks, Progress in Electromagnetics Research Symposium, PIERS, Kuala Lumpur, 2012, pp. 123-126. [13] . O. Van Den Biggelaar, J. M. Dricot, P. D. Doncker, F. Horlin, Distributed allocation of the spectrum sensing durations for cooperative cognitive radios, Progress in Electromagnetics Research Symposium, PIERS, Kuala Lumpur, 2012, pp. 303-307. [14] . J. H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, University of Michigan Press, Michigan, 1975. [15] . Gutierrez Blanco, O. Saez de Adana, F. del Corte Valiente, Antonio, Application of the particle swarm optimization to the computation of the GO/UTD reflection points over nurbs surfaces, Progress in Electromagnetics Research Letters, Vol. 35, 2012, pp. 19-28 . [16] . S. M. Mikki, A. A. Kishk, Physical theory for particle swarm optimization, Progress in Electromagnetics Research, Vol. 75, 2007, pp. 171-207. [17] . A. Chatteijee, G. K. Mahanti, Chatterjee, Arindam, Design of a fully digital controlled reconfigurable switched beam concentric ring array antenna using firefly and particle swarm optimization algorithm, Progress in Electromagnetics Research B, Vol. 36, 2011, pp. 113-131. [18] . Z. J. Zhao, Z. Peng, S. L. Zheng, J. N. Shang, Cognitive radio spectrum allocation using evolutionary algorithms, IEEE Transactions on Wireless Communications, Vol. 8, 2009, pp. 44214425. [19] Z. J. Zhao, Z. Peng, S. L. Zheng, S. Y. Xu, C. Y. Lou, X. N. Yang, Cognitive radio spectrum assignment based on quantum genetic algorithms, Acta Physica Sínica, 52, 2009,2009, pp. 1358-1363,. [20] . J. Kennedy and R. Eberhart, Discrete binary version of the particle swarm optimization, in Proceedings of the IEEE International Conference on Computational Cybernetics and Simulation, 1997, pp. 4104^1108. [21] . D. L. Yuan and Q. Chen, Particle swarm optimization algorithm with forgetting character, International Journal of Bio-Inspired Computation, Vol. 2, No. 1, 2010, pp. 14-31. [22] . S. L. Hijazi and B. Natarajan, Novel low-complexity DS-CDMA multiuser detector based on ant colony optimization, IEEE Vehicular Technology Conference, Vol. 3, Sep. 2004, pp. 1939-1943. [23] . K. Han, J.-H. Kim, Genetic quantum algorithm and its application to combinatorial optimization problems, in Proceedings of the IEEE Conference on Evolutionary Computation, 2000, pp. 1354-1360. [24] H. Y. Gao, C. W. Li, W. Cui, A simple quantuminspired bee colony algorithm for discrete optimisation problems, International Journal of Computer Applications in Technology, Vol. 46, 2013, pp. 244-251. [25] . L. C. Jiao, Y. Y. Li, M. G. Gong, X. Y. Zhang, Quantum-inspired immune clonal algorithm for global optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 38, 2008, pp. 1234-1253. [26] . H. Y. Gao, M. Diao, X. M. Yu, Robust MC-CDMA multiuser detection based on quantum shuffled frog leaping, Journal of Computational Information Systems, Vol. 6,2010, pp. 3309-3318. [27] . H. Y. Gao, J. L. Cao, Membrane-inspired quantum shuffled frog leaping algorithm for spectrum allocation, Journal of Systems Engineering and Electronics Vol. 23, 2012, pp. 679-688. 1 Hao FENG ,2 Biyang WEN, 3 Lutao LIU 1 China Ship Development and Design Center, No.268 Zhang Zhidong Road Wuhan, 430000, China 2 School of electronic information, Wuhan University, Wuhan, China 3 Colleges of Information and Communication Engineering, Harbin Engineering University, China E-mail: [email protected], [email protected], [email protected] Received: 18 September 2013 /Accepted: 22 November 2013 /Published: 30 December 2013 (c) 2013 International Frequency Sensor Association |