Advanced
Quantum Bacterial Foraging Optimization for Cognitive Radio Spectrum Allocation
Quantum Bacterial Foraging Optimization for Cognitive Radio Spectrum Allocation
KSII Transactions on Internet and Information Systems (TIIS). 2015. Feb, 9(2): 564-582
Copyright © 2015, Korean Society For Internet Information
  • Received : October 11, 2014
  • Accepted : January 01, 2015
  • Published : February 28, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Fei Li
Key Lab of Broadband Wireless Communication and Sensor Network Technology of Ministry of Education, Nanjing University of Posts and Telecommunications Nanjing 210003, China
Jiulong Wu
College of Communication and Information Engneering, Nanjing University of Posts and Telecommunications Nanjing 210003, China
Wenxue Ge
College of Communication and Information Engneering, Nanjing University of Posts and Telecommunications Nanjing 210003, China
Wei Ji
Key Lab of Broadband Wireless Communication and Sensor Network Technology of Ministry of Education, Nanjing University of Posts and Telecommunications Nanjing 210003, China

Abstract
This paper proposes a novel swarm intelligence optimization method which integrates bacterial foraging optimization (BFO) with quantum computing, called quantum bacterial foraging optimization (QBFO) algorithm. In QBFO, a multi-qubit which can represent a linear superposition of states in search space probabilistically is used to represent a bacterium, so that the quantum bacteria representation has a better characteristic of population diversity. A quantum rotation gate is designed to simulate the chemotactic step for the sake of driving the bacteria toward better solutions. Several tests are conducted based on benchmark functions including multi-peak function to evaluate optimization performance of the proposed algorithm. Numerical results show that the proposed QBFO has more powerful properties in terms of convergence rate, stability and the ability of searching for the global optimal solution than the original BFO and quantum genetic algorithm. Furthermore, we examine the employment of our proposed QBFO for cognitive radio spectrum allocation. The results indicate that the proposed QBFO based spectrum allocation scheme achieves high efficiency of spectrum usage and improves the transmission performance of secondary users, as compared to color sensitive graph coloring algorithm and quantum genetic algorithm.
Keywords
1. Introduction
I n recent years, the swarm intelligence optimization methods inspired by biological evolution and animal swarm behaviors, such as ant colony optimization (ACO) [1] and particle swarm optimization (PSO) [2] , have found their way into the realm of optimization algorithms and proved their effectiveness. The swarm intelligence optimization methods have found a strongly increasing number of applications in diverse fields, including in signal processing [3] .
Bacteria Foraging Optimization (BFO), proposed by Passino [4] , is a new comer to the family of nature swarm inspired optimization algorithms. BFO is inspired by the social foraging behavior of Escherichia coli ( E. coli ) bacteria. Similar to ACO and PSO, BFO are designed for function optimization by moving a swarm of individuals called bacteria in the search space. One major step in BFO is the chemotaxis which mimics bacteria searching for nutrients. After every fixed number of chemotaxis steps, the swarm of bacteria performs a reproduction and elimination step.
Since its inception, BFO which mimics how bacteria forage over a landscape of nutrients to perform parallel nongradient optimization has drawn the attention of researchers from diverse fields of knowledge [5 - 8] due to its effectiveness in the optimization domain. It has already been applied to many real world problems and proved its effectiveness over many variants of GA and PSO [9] . However, according to mathematical analysis in [10] , the chemotaxis employed by the classical BFO usually results in sustained oscillation, especially on flat fitness landscapes, when a bacterium cell is close to the optima. In dealing with complex problems, BFO has a low convergence behavior and performance decreases rapidly with an increase in the search space. To accelerate the convergence speed of the group of bacteria near the global optima and avoid its premature convergence, a novel quantum bacterial foraging optimization (QBFO) algorithm is proposed by merging BFO and quantum computing in this paper.
The subject of quantum computing brings together ideas from classical information theory, computer science, and quantum physics [11] . Research on combining evolutionary computing and quantum computing has been started since late 1990s. It can be classified into two areas. One concentrates on generating new quantum algorithms using automatic programming techniques such as genetic programming [12] . The other concentrates on quantum-inspired evolutionary computing for a classical computer [13] . Encouraged by that quantum-inspired evolutionary algorithms show better performance on solving combinatorial optimization problems than their classical counterparts [14] [15] , this paper proposes a novel bacterial foraging optimization algorithm, called QBFO algorithm, which is based on the concept and principles of quantum computing such as a qubit, multiqubit, superposition of states and quantum gates.
In QBFO, a multiqubit is used to represent a bacterium, and quantum rotation gate is used to mimic chemotaxis. A multiqubit system (for example n -qubit system) has available 2 n mutually orthogonal quantum states, so the quantum bacterium with multiqubit has the advantage that it can represent a linear superposition of states (binary solutions) in search space probabilistically. A quantum rotation gate is defined as a chemotactic operator of QBFO to drive the individual bacterium toward better solutions and eventually toward a single state.
On a quantum bacteria-based algorithm for communication, there are some previous work address here. The reference [16] proposed a bacteria-based nanonetwork for communication between eukaryotic cell sized nano devices. The simulation results show that the performance in delay, capacity and throughput is 4 orders of magnitude higher than the other molecular communication approaches. In [17] , a new nano network architecture using flagellated bacteria was proposed to cover the medium-range. By using the ability of conjugation and chemotaxis-based motility, an opportunistic routing process in bacteria communication nanonetwork was proposed in [18] and an approach enable multi-hop transmission based bacteria nanonetworks was proposed in [19] . The reference [20] researched on applying a quantum bacteria-based optimization algorithm in spectrum sensing. The simulation results proved that spectrum sensing method based on quantum BFO algorithm is superior to the previous intelligence algorithms.
In this paper, we focus on applying our proposed QBFO to solve spectrum allocation problem in Cognitive Radio (CR) [21] .
Wireless spectrum is one of the most valuable natural resource. The demand for spectrum has been growing dramatically with the rapid development of the telecommunication industry, which has caused scarcity in the available spectrum bands. Furthermore, the underutilization of the licensed spectrum bands makes the situation even worse [22] . CR has very promising potential to improve spectrum utilization by allowing unlicensed Secondary Users (SUs) to access the spectrum dynamically without disturbing licensed Primary Users (PUs) [21] . A key challenge in CR network is how to adaptively and efficiently allocate spectrum among SUs according to the surrounding environment [23] [24] .
There exist a lot of research efforts on the problem of spectrum allocation in CR, including game theory [25] , pricing and auction mechanisms [26] [27] , local bargaining [28] , and graph coloring [29] [30] . Color sensitive graph coloring (CSGC) [30] algorithm has attracted a lot of attention, as it can realize flexible spectrum allocation. However, the computational complexity of the CSGC algorithm varies with the number of available spectrums and users, which make spectrum allocation to become an NP-Hard problem. As the allocation model can be inherently seen as an optimization problem, spectrum allocation approaches based on evolutionary algorithms, such as genetic algorithm (GA) [31] and quantum genetic algorithm (QGA) [32] [33] , are proposed for CR recently. However, evolutionary algorithms based spectrum allocation has some shortage on convergence and are hard to reach global optimization. A novel spectrum allocation scheme based on QBFO is proposed in this paper.
The work presented here has focused on the formulation of the QBFO algorithm, which takes advantage of BFO and quantum-inspired evolutionary computing such as QGA. The work in [34] uses a different swarming pattern, and the work in [20] [35] takes a different quantum representation of a bacterium. While our proposed QBFO takes a new representation of a bacterium, and a new quantum chemotaxis operator and a new quantum elimination-dispersal, which were not considered in these earlier studies. The simulations of QBFO based spectrum allocation have been conducted as compared to a very popular spectrum allocation algorithm known as CSGC and QGA, with respect to the following performance measures: solution quality and convergence speed. The simulation results show that the proposed scheme achieves high efficiency of spectrum usage and improvement of SUs’ performance.
The remainder of the paper is organized as follows: in section 2, we propose a quantum BFO. Section 3 provides detailed comparison between the classical BFO and its quantum variants over a test suite of 4 well-known numerical benchmarks. In section 4, a novel spectrum allocation scheme based on QBFO is proposed and analyzed. Finally, conclusions are drawn in section 5.
2. Designing of Quantum Bacterial Foraging Algorithm
- 2.1 Quantum Representation of a Bacterium
Inspired by the concept of quantum computing and quantum-inspired evolutionary algorithm [15] , we designed a novel quantum representation of a bacterium in QBFO, called a Quantum bacterium ( Q-bacterium ), which is defined below:
PPT Slide
Lager Image
where M is the number of multiqubit, which is defined with a pair of numbers ( α , β ) as [ α β ] T . ( α , β ) corresponds a qubit expressed in | ϕ > = α |0 > + β |1 > = ( α , β ) T .
QBFO with Q-bacterium representation has a better characteristic of population diversity than other representations, since it can represent linear superposition of states probabilistically. Only one Q-bacterium such as (1) is enough to represent 2 M states, but in binary representation at least 2 M strings.
Research results shows that E.coli bacteria have an interesting group behavior [36] . A group of E.coli cells arrange themselves in a traveling ring by moving up the nutrient gradient. The cells keep certain distance and exchange food information through various ways. It increases their understanding of the environment and so increases their survival chances. The bacteria swarm in QBFO is composed of a group of Q-bacteria . The tth population is
PPT Slide
Lager Image
where S is the size of population.
- 2.2 Quantum Chemotaxis
Chemotaxis simulates the movement of an E.coli cell through straight swimming and tumbling via flagella. If the bacterium senses that it is moving in the correct direction (toward attractant/away from repellent), it will keep swimming in a straight line for a longer time before tumbling. If it is moving in the wrong direction, it will tumble sooner and try a new direction at random. In other words, E. coli bacteria use temporal sensing to decide whether their situation is improving or not. In this way, it finds the location with the highest concentration of nutrition (usually the source) quite well. Even under very high concentrations, it can still distinguish very small differences in concentration. In the presence of a chemical gradient bacterium will chemotaxis, or direct their overall motion based on the gradient.
In QBFO, chemotaxis operation is not performed as same as original BFO [36] because Q-bacteria can be in quantum superposition state. A Q-gate is defined as a chemotaxis operator of QBFO, by which operation the updated qubit should satisfy the normalization condition, | α '| 2 + | β '| 2 = 1 , where α ' and β ' are the values of the updated qubit. The following rotation gate is used as a Q-gate in QBFO, such as:
PPT Slide
Lager Image
where θ is a rotation angle of each Q-bit toward either 0 or 1 state depending on its sign. θ should be designed in compliance with the application problem. The adjustment operation is as follows:
PPT Slide
Lager Image
where θm is rotating angle and θm = s ( αm , βm )·Δ θm · s ( αm , βm ) is used to control the rotation direction and Δ θm is used to control the size of the rotation angle which should be designed in compliance with the application problem.
Quantum chemotaxis operator acts on the linear superposition of states of all qubits in Q-bacteria and changes the phase information of qubit, as well as the amplitude information. As the result, the position of the Q-bacterium is updated.
- 2.3 Quantum Reproduction
Quantum reproduction is an evolutionary process based on survival of the fittest. Let
PPT Slide
Lager Image
be the health of the i th Q-bacterium (a measure of how many nutrients it got over its lifetime and how successful it was at avoiding noxious substances), where Nc is the number of chemotactic steps and fitness ( i, j ) is the fitness function value of i th Q-bacterium at j th chemotactic step.
The less healthy Q-bacteria eventually die while each of the healthier Q-bacteria asexually split into two bacteria, which are then placed in the same location. This keeps the swarm size constant.
- 2.4 Quantum Elimination-dispersal
Gradual or sudden changes in the survival environment, such as a significant local rise of temperature, may kill or disperse a group of bacteria that are currently in a region with a high concentration of nutrient gradients. To simulate this phenomenon in QBFO, quantum elimination-dispersal is performed after several steps of quantum chemotaxis and quantum reproduction. In this process, some Q-bacteria are dispersed at random with a very small probability Ped while the new replacements are randomly initialized over the search space as:
PPT Slide
Lager Image
where Xn is the n th state represented by the binary string ( x 1 , x 2 ,..., xM ), where xm , m = 1,..., M is either 0 or 1 according to the probability of either
PPT Slide
Lager Image
respectively.
- 2.5 The Procedure of QBFO
The detailed pseudo-code of the complete QBFO algorithm is shown in Table 1 .
The pseudo-code of QBFO
PPT Slide
Lager Image
The pseudo-code of QBFO
3. Experiments and Results over Benchmark Functions
This section presents some comparisons among the performances of the proposed QBFO, the original BFO and QGA which is a typical algorithm of quantum evolutionary computation. All methods have been applied to several benchmark test functions as depicted in Table 2 in order to check the effect of the proposed QBFO in the efficiency and the convergence speed.
Description of the Benchmark Function Used
PPT Slide
Lager Image
Description of the Benchmark Function Used
- 3.1 Test Functions
Our test suite includes 4 well-known benchmark functions of varying complexity. The formulas of these functions are presented in Table 2 .
The Sphere function ( f 1 ) is continuous, convex and unimodal with only one global minimum. The others are multimodal with a considerable number of local extremes in the region of interest. The Needle-in-haystack function ( f 2 ) has one global maximum with four local maxima, and the function behaves like a needle in the haystack (the function values for points in the space outside the narrow peaks give very little information on the location of the global optimum). The Schaffer’s F6 function ( f 3 ) has one global maximum with numerous local maxima, the difficulty in this function is that the size of the potential maxima that need to be overcome to get to a minimum increases the closer one gets to the global minimum. The Multi-peak function ( f 4 ) has one global maximum with huge number of local maxima, the difficulty in this function is asymmetric and having the global maximum at the edge of the search space. Table 2 summarizes the optima and search ranges used for all the functions. The contours of all the test functions are illustrated in Table 2 .
- 3.2 Parameter Settings
For the BFO, we chose the population size of the bacteria S =40, the number of chemotaxis Nc =50, the number of reproduction steps Nre =5, the number of elimination and dispersal events Ned =2, the probability of elimination and dispersal Ped =0.25, the depth of the attractant released by the cell d attract =0.1, the width of the attractant signal w attract =0.2, the height of the repellent effect h repellant = d attract =0.1, and the width of the repellent w repellant =2. The size of the step taken in the random direction specified by the tumble C was set as 0.1 for benchmarks f 1 and f 3 . For benchmarks f 2 and f 4 we chose C =0.001. For the QBFO, the parameter values of S , Nc , Nre , Ned , and Ped were kept exactly same as BFO. We fixed the length of the Quantum bacterium M =44, and the size of the rotation angle Δ θm = 0.08 π . For the QGA, we chose population size S =40, the length of the quantum chromosome len =44, the probability of cross pc =0.7, the probability of variation pm =0.15, the size of rotation angle Δ θm = 0.08 π , and the maximal generation number maxgen =500.
- 3.3 Results and Discussions
Twenty independent runs of the three competitor algorithms were carried out on each problem, and the experimental results are presented in Table 3 . In the table, the best results among the algorithms are shown in bold. The graphs presented in Fig. 1 - 4 illustrate the evolution of best fitness found by three algorithms averaged for 20 runs for each function.
Experimental Results for 20 Independent Runs on four Benchmark Functions
PPT Slide
Lager Image
Experimental Results for 20 Independent Runs on four Benchmark Functions
PPT Slide
Lager Image
Convergence Curve of three algorithms for f1
PPT Slide
Lager Image
Convergence Curve of three algorithms for f2
PPT Slide
Lager Image
Convergence Curve of three algorithms for f3
PPT Slide
Lager Image
Convergence Curve of three algorithms for f4
Table 3 illustrates the comparisons of the three algorithms on the benchmark functions. From Table 3 , it is observed that for all test problems, the proposed QBFO is superior to other two algorithms on the optimization problems although it converges slower sometimes (i.e. as shown in Fig. 1 ). The best value and the mean best value of the proposed method are closest to or even the same as the optimal value. QBFO is the most stable as the standard deviation of QBFO is smallest.
For convenience to show better search ability, Fig. 1 - 4 illustrate the comparisons on functions f 1 - f 4 . In general, the graphs in Fig. 1 - 4 show that the QBFO could converge to the global optimum keeping a good diversity and high speed when it conducts the optimization of Sphere, Needle-in-haystack, Shaffer’s F6 and Multi-peak problems.
As evident from Table 3 and Fig. 1 , it obviously shows that the Sphere function is easy to solve. It is shown that the QBFO converges slower than BFO and QGA, but the average run time of QBFO is less than QGA and the convergence runs of QBFO is more than QGA. QBFO hits the success 20 times by 20 runs.
For Needle-in-haystack function, it is evident from Table 3 and Fig. 2 that QBFO is the fastest algorithm in reaching the target global value. The frequency of hitting the optima of QBFO is 20 times in 20 runs, and that of BFO is only 6 times.
For Shaffer’s function, it can be easily observed from Table 3 and Fig. 3 that QBFO arrives at the global optimum value fastest. The frequency of hitting the optima of QBFO is 15 times in 20 runs, and BFO cannot reach to the global optimum value.
According to Table 3 and Fig. 4 , QBFO remained the best performance in the convergence rate, the best value, the mean best value and the frequency of hitting the optima.
According to the comparison analysis above, it is obvious to know that the proposed QBFO can keep a better diversity to develop the virgin space and have the best ability to reach the optimum. The relative results showed that QBFO is a good method to improve the global ability of BFO. QBFO shows good convergence performance not only for simple smooth function such as Sphere function but also for complex function such as multi-peak function and nonlinear optimization problem. The reason is that QBFO takes advantage of quantum computation, which provides the bacteria with more intelligence to search the global optimum, and contribute to the global optimization ability.
It can be shown from the above analysis that, the QBFO algorithm does not have the best performance in all aspects. The convergence of the QBFO algorithm is the best among the three algorithms and the complexity of QBFO algorithm is between BFO and QGA. In addation, the QBFO algorithm has better performance for complex optimizaiton problems. Therefore, the QBFO algotithm is a good choice for optimization problems considering the convergence, time complexity and stability.
4. Application to Cognitive Radio Spectrum Allocation
- 4.1 Cognitive Radio Spectrum Allocation Model
There are several models proposed for the problem of spectrum allocation in CR, such as pricing and auction mechanisms [26] [27] , local bargaining [28] , and graph coloring [29] [30] . The general CR spectrum allocation model in [30] called graph coloring model assumes that the environmental conditions are static during the time it takes to perform spectrum assignment, and CSGC is used to solve the allocation problem. The model belongs to “0, 1” format, which “0” and “1” can represent all the necessary modeling information. It is more simple and can get more accurate performance comparing with other models. We use graph coloring model for cognitive radio spectrum allocation.
The graph coloring spectrum allocation model can be described by channel availability matrix, channel reward matrix, interference constraint matrix, and conflict free channel assignment matrix [30] . Consider a network of N cognitive users (SUs) indexed from 1 to N competing for M spectrum channels indexed 1 to M which are non-overlapping orthogonal.
The channel availability matrix denotes the channel availability, which is defined as:
PPT Slide
Lager Image
where L is an N by M binary matrix , if and only if channel m is available at cognitive user n , ln,m = 1; otherwise ln,m = 0 .
The channel reward matrix represents the channel reward described by:
PPT Slide
Lager Image
where B is an N by M matrix representing the channel reward, where bn,m represents the maximum bandwidth/throughput that can be obtained by cognitive user n using channel m .
As two or more cognitive users may use the same channel at the same time, they may interfere with each another. We use the interference constraint matrix to denote the interference constraints among cognitive users, which is mathematically represented as:
PPT Slide
Lager Image
where C is an N by N by M matrix denoting the interference constraints among cognitive users, where cn,k,m = 1 if cognitive users n and cognitive users k interfere with each other as they use channel m simultaneously and cn,k,m = 1 otherwise. The constraint depends on channel availability when n = k , i.e., cn,n,m = 1 - ln,m .
The conflict free channel assignment matrix is defined as:
PPT Slide
Lager Image
where A is an N by M binary matrix. If channel m is assigned to cognitive user n , an,m = 1. Matrix A must satisfy all the interference constraints defined by C , that is:
PPT Slide
Lager Image
Given a conflict free channel assignment matrix A , the reward user n obtains is described as rn =
PPT Slide
Lager Image
, and the reward vector that each user gets for a given channel assignment is mathematically represented as:
PPT Slide
Lager Image
Let , ∧ L,C be the set of conflict free channel assignment for a given L and C . We define network utilization as:
PPT Slide
Lager Image
The spectrum allocation is to realize the maximization of network utilization U ( R ).
According to the model above, we can define the spectrum allocation problem as the following optimization problem:
PPT Slide
Lager Image
where A * is the optimal conflict free channel assignment matrix.
We summarize the experssions and value ranges used for all the above matrices as Table 4 .
Description of the matrices used
PPT Slide
Lager Image
Description of the matrices used
- 4.2 QBFO Based Cognitive Radio Spectrum Allocation
In this work, assume each quantum bacterium after being observed represent one possible spectrum allocation scheme, that is, a bacterium specifies a possible conflict free channel assignment. As an,m = 0 when ln,m = 0, if we use one bit to encode every element in A , there will be a lot of redundancy in the bacterium. Inspired by chromosome encoding in [32] , we encode only those elements which may take the value 1, i.e., an,m where ( n,m ) satisfies ln,m = 1. As a result, the length of the binary string is equal to the number of elements for 1 in L , and then the search space is greatly reduced. Fig. 5 gives the structure of an example bacterium, where N = 4, M = 4 . Note that encoding all the elements needs 16 bits, while encoding only the elements with underline only needs 8 bits. For evaluating the fitness of the bacteria, it is necessary to map the bacteria to the channel assignment matrix, as the arrows show in Fig. 5 .
PPT Slide
Lager Image
The structure of an example bacterium
The value of every qubit in the Q-bacteria after being observed is randomly generated at the initial population and determined by quantum chemotaxis, quantum reproduction and quantum elimination-dispersal as defined in section 2. Hence, it may not always satisfy the interference constraints defined by C . In order to satisfy the interference constraints, we design the following operations: (1) for all m (1 ≤ m M ) search all n and k that satisfies cn,k,m = 1, and (2) check whether both of the two bits corresponding to the element in the n th line and m th column of A and the element in the k th line and m th column of A are equal to 1; if so, randomly set one of them to 0.
The searching direction of QBFO is based on the fitness of the Q-bacteria in the population. We consider two objective functions as the fitness function, respectively:
(1) Max-Sum-Reward (MSR):
PPT Slide
Lager Image
(2) Max-Proportional-Fair(MPF):
PPT Slide
Lager Image
The proposed QBFO based spectrum allocation algorithm proceeds as following pseudo-code shown in Table 5 .
The pseudo-code of QBFO based spectrum allocation algorithm
PPT Slide
Lager Image
The pseudo-code of QBFO based spectrum allocation algorithm
- 4.3 Experimental Results and Performance Evaluation
The commonly used algorithm to solve the spectrum allocation problem is Color Sensitive Graph Coloring (CSGC) algorithm. In order to evaluate the performance of the proposed QBFO-based spectrum allocation scheme, we compare it with CSGC and QGA in our simulations. Numerical experiments were executed with QBFO, CSGC and QGA. The QBFO parameters were set to the following values: S = 20, Nc = 50, Nre = 5, Ned = 2, Ped = 0.25, Δ θm = 0.08 π , and iteration times as 500.
Fig. 6 shows the network rewards over 50 experiments where N = 5, M = 4. L , B , C are kept the same under all experiments under a particular objective, which are generated by referring to appendix I in [30] . It is obvious that the proposed QBFO-based spectrum allocation algorithm can obtain better sum reward, compared to the CSGC and QGA.
PPT Slide
Lager Image
Spectrum allocation performance for QBFO, QGA and CSCG
Refer to Fig. 7 and Fig. 8 , we can see the comparative results of the convergence processes of applying QBFO and QGA to solve the spectrum allocation problem. It is shown that QBFO can converge toward the optimal solution more quickly than QGA, and QBFO also outperforms QGA under objectives MSR and MPF in the performance of convergence value.
PPT Slide
Lager Image
Spectrum allocation performance (sum reward) for QBFO and QGA
PPT Slide
Lager Image
Spectrum allocation performance (fair reward) for QBFO and QGA
Fig. 9 shows the spectrum allocation performance for QBFO, QGA and CSCG with varying numbers of cognitive users when M = 30 , and Fig. 10 shows the corresponding experiment result with varying numbers of spectrums when N = 15. Compared to the other two algorithms, QBFO-based scheme can achieve best realization of the maximization of system utilization.
PPT Slide
Lager Image
Spectrum allocation performance with varying numbers of cognitive users N
PPT Slide
Lager Image
Spectrum allocation performance with varying numbers of spectrums M
5. Conclusion
In this paper, a novel QBFO is proposed, which is based on the BFO and quantum computing. A novel quantum bit expression mechanism called quantum bacteria is employed and the quantum chemotaxis is adopted to update the Q-bacteria. Quantum reproduction is performed after several steps of quantum chemotaxis, which makes most bacteria get together and accelerates convergence of the algorithm. Then quantum dispersal operation is performed on the bacteria swarm with a certain probability, which can expand the searching space and prevent the algorithm to fall into the local optimal value. The key to the application of QBFO to a new problem is to identify an appropriate representation for the problem (to be represented as a graph searched by many quantum bacteria). The simulated results in solving spectrum allocation problem in cognitive radio show that QBFO is superior to CSGC and QGA.
Future research may focus on extending the analysis presented in this paper to a group of quantum bacteria working on a multidimensional fitness landscape and also include effect of the quantum chemotaxis and elimination–dispersal events in the same.
BIO
Fei LI is a Ph.D., Professor in the College of Communication and Information Engneering, Nanjing University of Posts and Telecommunications, Nanjing, China. Her research interests include Quantum Intelligence Computing, Swarm Intelligence, and Signal Processing in Wireless Communication.
Jiulong WU is a Master in the College of Communication and Information Engneering, Nanjing University of Posts and Telecommunications, Nanjing, China. His research interest is Quantum Intelligence Computing.
Wenxue GE is a Master of the College of Communication and Information Engneering, Nanjing University of Posts and Telecommunications, Nanjing, China. Her research interest is Quantum Intelligence Computing.
Wei JI is a Ph.D., Associate Professor in the College of Communication and Information Engneering, Nanjing University of Posts and Telecommunications, Nanjing, China. Her research interests include cognitive radio, ad-hoc networks and radio resource management.
References
Colorni A. , Dorigo M. , Maniezzo V. 1991 “Distributed Optimization by Ant Colonies,”actes de la première conférence européenne sur la vie artificielle Elsevier Publishing Paris, France 134 - 142
Kennedy J. , Eberhart R. “Particle Swarm Optimization,” IEEE Press in Proc.of IEEE International Conference on Neural Networks 1995 1942 - 1948
Merkle D. , Middendorf M. 2008 “Swarm Intelligence and Signal Processing,” IEEE Signal Processing Magazine 25 (6) 152 - 158    DOI : 10.1109/MSP.2008.929839
Passino K.M. 2002 “Biomimicry of Bacterial Foraging For Distributed Optimization and Control,” IEEE Control Systems Magazine 22 (3) 52 - 67    DOI : 10.1109/MCS.2002.1004010
Mishra S. 2005 “a Hybrid Least Square-Fuzzy Bacterial Foraging Strategy for Harmonic Estimation,” IEEE Transactions on Evolutionary Computation 9 61 - 73    DOI : 10.1109/TEVC.2004.840144
Mishra S. , Bhende C.N. 2007 “Bacterial Foraging Technique-based Optimized Active Power Filter for Load Compensation,” IEEE Transactions on Power Delivery 22 (1) 457 - 465    DOI : 10.1109/TPWRD.2006.876651
Dasgupta S. , Das S. , Biswas A. , Abraham A. 2010 “Automatic Circle Detection on Digital Images with an Adaptive Bacterial Foraging Algorithm,” Soft Computing 14 (11) 1511 - 1164    DOI : 10.1007/s00500-009-0508-z
Nouria H. , Hong T. S. 2013 “Development of Bacteria Foraging Optimization Algorithm for Cell Formation in Cellular Manufacturing System Considering Cell Load Variations,” Journal of Manufacturing Systems 32 20 - 31    DOI : 10.1016/j.jmsy.2012.07.014
Das S. , Biswas A. , Dasgupta S. , Abraham A. 2009 “Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Applications, Foundations of Computational Intelligence,” Global optimization, studies in computational intelligence 3 23 - 55
Dasgupta S. , Das S. , Abraham A. , Biswas A. 2009 “Adaptive Computational Chemotaxis in Bacterial Foraging Optimization: An Analysis,” IEEE Tranactions on Evolutionary Computation 13 (4) 919 - 941    DOI : 10.1109/TEVC.2009.2021982
Steane A. M. 1998 “Quantum Computing,” Reports on Progress in Physics 61 117 - 173    DOI : 10.1088/0034-4885/61/2/002
Spector L. , Barnum H. , Bernstein H. J. , Swamy N. 1999 “Finding a Better-than-classical Quantum AND/OR Algorithm Using Genetic Programming,” Congress on Evolutionary Computation Piscataway 3 2239 - 2246
Narayanan A. , Moore M. “Quantum-Inspired Genetic Algorithms,” IEEE Press Piscataway in Proc. of IEEE International Conference on Evolutionary Computation 1996 1 - 66
Han K-H , Kim J-H “Genetic Quantum Algorithm and Its Application to Combinatorial Optimization Problem,” IEEE Press USA in Proc. of IEEE Congress on Evolutionary Computation 2000 1354 - 1360
Han K.-H. , Kim J.-H. 2002 “Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization,” IEEE Transactions on Evolutionary Computation 6 (6) 580 - 593    DOI : 10.1109/TEVC.2002.804320
Cobo L. C , Akyildiz I. F. 2010 “Bacteria-based Communication in Nanonetworks,” Nano Communication Networks 1 (4) 244 - 256    DOI : 10.1016/j.nancom.2010.12.002
Gregori M. , Akyildiz I. F. 2010 “A New Nanonetwork Architecture using Flagellated Bacteria and Catalytic Nanomotors,” IEEE Journal on Selected Areas in Communications 28 (4) 612 - 619    DOI : 10.1109/JSAC.2010.100510
Lio P. , Balasubramaniam S. 2012 “Opportunistic Routing through Conjugation in Bacteria Communication Nanonetwork,” Nano Communication Networks 3 (1) 36 - 45    DOI : 10.1016/j.nancom.2011.10.003
Balasubramaniam S , Lio P. 2013 “Multi-hop Conjugation based Bacteria Nanonetworks,” IEEE Transactions on NanoBioscience 12 (1) 47 - 59    DOI : 10.1109/TNB.2013.2239657
Gao H.Y. , Cui W. , Li C.W. 2013 “A Quantum Bacterial Foraging Optimization Algorithm and Its Application in Spectrum Sensing,” International Journal of Modelling, Identification and Control 18 (3) 29 - 36    DOI : 10.1504/IJMIC.2013.052817
Mitola J. , Maguire G.Q. 1999 “Cognitive radio: making software radios more personal,” IEEE Personal Commun. 6 (4) 13 - 18    DOI : 10.1109/98.788210
FCC 2003 “Facilitating Opportunities for Flexible, Efficient, and Reliable Spectrum Use Employing Cognitive Radio Technologies: Notice of Proposed Rule Making and Order,”FCC Document ET Docket No. 03-108
Akyildiz I.F. , Lee Won-Yeol , Vuran M.C. , Mohanty S. 2008 “A survey on spectrum management in cognitive radio networks,” IEEE Commun. Magazine 46 (4) 40 - 48    DOI : 10.1109/MCOM.2008.4481339
Jang S. , Kim J. , Byun J. , Shin Y. 2014 “Game Theory based Dynamic Spectrum Allocation for Secondary Users in the Cell Edge of Cognitive Radio Networks,” KSII Transactions on Internet and Information Systems 8 (7) 2231 - 2245
Nie N. , Comaniciu C. “Adaptive channel allocation spectrum etiquette for cognitive radio networks,” in Proc. of IEEE DySPAN 2005 269 - 278
Kloeck C. , Jaekel H. , Jondral F. K. “Dynamic and local combined pricing, allocation and billing system with cognitive radios,” in Proc. of IEEE DySPAN 2005 73 - 81
Huang J. , Berry R. , Honig M. L. 2006 “Auction-based spectrum sharing,” ACM Mobile Networks and Applications (MONET) 11 (3) 405 - 418    DOI : 10.1007/s11036-006-5192-y
Cao L. , Zheng H. “Distributed spectrum allocation via local bargaining,” in Proc. of IEEE DySPAN 2005 475 - 486
Zheng H. , Peng C. “Collaboration and fairness in opportunistic spectrum access,” in Proc.of 40th annual IEEE International Conference on Communications (ICC) 2005 3132 - 3136
Peng C. , Zheng H. , Zhao B. Y. 2006 “Utilization and Fairness in Spectrum Assignment for Opportunistic Spectrum Access,” ACM Mobile Networks and Applications(MONET) 11 (4) 555 - 576    DOI : 10.1007/s11036-006-7322-y
Nainay El M. Y. , Friend D. H. , MacKenzie A. B. 2008 “Channel allocation & power control for dynamic spectrum cognitive networks using a localized island genetic algorithm,”New Frontiers in Dynamic Spectrum Access Networks, DySPAN 1 - 5
Zhao Z. J. , Peng Z. , Zheng S. L. , Shang J. N. 2009 “Cognitive Radio Spectrum Allocation Using Evolutionary Algorithms,” IEEE Transactions on Wireless Communications 8 (9) 4421 - 4425    DOI : 10.1109/TWC.2009.080939
Li F. , Zhu D.P. , Tian F. , Li H.B. “Cognitive Radio Competitive Spectrum Sharing Using Improved Quantum Genetic Algorithm,” in Proc. of International Conference on Wireless Communications and Signal Processing 2011 1203 - 1209
Cao J.L. , Gao H.Y. 2012 “A Quantum-inspired Bacterial Swarming Optimization Algorithm for Discrete Optimization Problems,”Advances in Swarm Intelligence, Lecture Notes in Computer Science Springer vol.7331 29 - 36
Zhang G.Y. , Wu Y.G. 2013 “Bacterial Foraging Optimization Algorithm with Quantum Behavior,” Journal of Electronics & Information Technology 35 (3) 614 - 621    DOI : 10.3724/SP.J.1146.2012.00892
Passino K.M. 2010 “Bacterial Foraging optimization,” International Journal of Swarm Intelligence Research 1 (1) 1 - 16    DOI : 10.4018/jsir.2010010101