Printer Friendly

Quantum bacterial foraging optimization for cognitive radio spectrum allocation.

1. Introduction

In 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 2n 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:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

where M is the number of multiqubit, which is defined with a pair of numbers ([alpha], [beta]) as [[[alpha] [beta]].sup.T] ([alpha], [beta]) corresponds a qubit expressed in |[phi]) = [alpha]|0) + [beta]| 1> = [([alpha], [beta]).sup.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.sup.M] states, but in binary representation at least [2.sup.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

Q(t) = ([q.sup.t.sub.1], [q.sup.t.sub.2], ..., [q.sup.t.sub.s]) (2)

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, [[absolute value of ([alpha]')].sup.2] + [[absolute value of ([beta]')].sup.2] = 1, where [alpha]' and [beta]' are the values of the updated qubit. The following rotation gate is used as a Q-gate in QBFO, such as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

where [theta] is a rotation angle of each Q-bit toward either 0 or 1 state depending on its sign. 0 should be designed in compliance with the application problem. The adjustment operation is as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

where [[theta].sub.m] is rotating angle and [[theta].sub.m] = s([[alpha].sub.m], [[beta].sub.m]) x [DELTA][[theta].sub.m] x s([[alpha].sub.m], [[beta].sub.m]) is used to control the rotation direction and [DELTA][[theta].sub.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

Jhealth(i) = [[N.sub.c].summation over (j=1)]fitness(i,j)] (5)

be the health of the ith Q-bacterium (a measure of how many nutrients it got over its lifetime and how successful it was at avoiding noxious substances), where [N.sub.c] is the number of chemotactic steps and fitness(i,j) is the fitness function value of ith Q-bacterium at jth 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 [P.sub.ed] while the new replacements are randomly initialized over the search space as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

where [X.sub.n] is the nth state represented by the binary string ([x.sub.1], [x.sub.2], ..., [x.sub.M]), where [x.sub.m], m = 1, ..., M is either 0 or 1 according to the probability of either [absolute value of ([[alpha].sup.t.sub.m])] or [absolute value of ([[beta].sup.t.sub.m])], respectively.

2.5 The Procedure of QBFO

The detailed pseudo-code of the complete QBFO algorithm is shown in Table 1.

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.

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.sub.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.sub.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.sub.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.sub.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 [N.sub.c] = 50, the number of reproduction steps [N.sub.re] = 5, the number of elimination and dispersal events [N.sub.ed] = 2, the probability of elimination and dispersal [P.sub.ed] =0.25, the depth of the attractant released by the cell [d.sub.attract] = 0.1, the width of the attractant signal [w.sub.attract] = 0.2, the height of the repellent effect [h.sub.repellant] = [d.sub.attract] = 0.1, and the width of the repellent [w.sub.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.sub.1] and [f.sub.3]. For benchmarks [f.sub.2] and [f.sub.4] we chose C = 0.001. For the QBFO, the parameter values of S, [N.sub.c], [N.sub.re], [N.sub.ed], and [P.sub.ed] were kept exactly same as BFO. We fixed the length of the Quantum bacterium M=44, and the size of the rotation angle [DELTA][[theta].sub.m] = 0.08[pi]. For the QGA, we chose population size S=40, the length of the quantum chromosome len=44, the probability of cross [p.sub.c] = 0.7, the probability of variation [p.sub.m] = 0.15, the size of rotation angle [DELTA][[theta].sub.m] = 0.08[pi], 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.

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.sub.1]-[f.sub.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:

L = [{[l.sub.n,m]|[l.sub.n,m] [member of] {0,1}}.sub.NxM], n = 1, ... N, m = 1, ... M (7)

where L is an N by M binary matrix, if and only if channel m is available at cognitive user n, [l.sub.n,m] = 1; otherwise [l.sub.n,m] = 0.

The channel reward matrix represents the channel reward described by:

B = [{[b.sub.n,m]}.sub.NxM], n = 1, ... N, m = 1, ... M (8)

where B is an N by M matrix representing the channel reward, where [b.sub.n,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:

C = [{{[c.sub.n,k,m]|[c.sub.n,k,m] [member of] {0,1}}.sub.NxNxM], n = 1, ... N, m = 1, ... M (9)

where C is an N by N by M matrix denoting the interference constraints among cognitive users, where [c.sub.n,k,m] = 1 if cognitive users n and cognitive users k interfere with each other as they use channel m simultaneously and [c.sub.n,k,m] = 1 otherwise. The constraint depends on channel availability when n = k, i.e., [c.sub.n,n,m] = 1-[l.sub.n,m].

The conflict free channel assignment matrix is defined as:

A = [{[a.sub.n,m]|[a.sub.n,m] [member of] {0,1}}.sub.NxM], n = 1, ... N, m = 1,... M (10)

where A is an N by M binary matrix. If channel m is assigned to cognitive user n, anm = 1. Matrix A must satisfy all the interference constraints defined by C, that is:

[a.sub.n,m] + [a.sub.k,m] [less than or equal to] 1 if [c.sub.n,k,m] = 1, [for all] 1 [less than or equal to] n, k [less than or equal to] N, 1 [less than or equal to] m [less than or equal to] M

Given a conflict free channel assignment matrix A, the reward user n obtains is described as [r.sub.n] = [[SIGMA].sup.M.sub.m=1] [a.sub.n,m] x [b.sub.n,m], and the reward vector that each user gets for a given channel assignment is mathematically represented as:

R = [{[r.sub.n] = [[SIGMA].sup.M.sub.m=1] [a.sub.n,m] x [b.sub.n,m]}.sub.Nx1] (12)

Let [[LAMBDA].sub.L,C] be the set of conflict free channel assignment for a given L and C. We define network utilization as:

U(R) = [[SIGMA].sup.N.sub.n=1] [r.sub.n] (13)

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:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

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.

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 [a.sub.n,m] = 0 when [l.sub.n,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., [a.sub.n,m] where (n,m) satisfies [l.sub.n,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.

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 [less than or equal to] m [less than or equal to] M) search all n and k that satisfies [c.sub.n,k,m] = 1, and (2) check whether both of the two bits corresponding to the element in the nth line and mth column of A and the element in the kth line and mth 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):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

(2) Max-Proportional-Fair(MPF):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

The proposed QBFO based spectrum allocation algorithm proceeds as following pseudo-code shown in Table 5.

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, [N.sub.c] = 50, [N.sub.re] = 5, [N.sub.ed] = 2, [P.sub.ed] = 0.25, [DELTA][[theta].sub.m] = 0.08[pi], 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.

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.

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.

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.

This work was supported in part by National Natural Science Foundation of China (No. 61471200) and the Six Top Talents Foundation of Jiangsu Province, China (No. 2011WLW011)

http://dx.doi.org/10.3837/tiis.2015.02.005

References

[1] A. Colorni, M. Dorigo, and V. Maniezzo, "Distributed Optimization by Ant Colonies," actes de la premiere conference europeenne sur la vie artificielle, Elsevier Publishing, Paris, France, pp. 134-142, 1991. Article (CrossRef Link).

[2] J.Kennedy, R. Eberhart, "Particle Swarm Optimization," in Proc.ofIEEE International Conference on Neural Networks, IEEE Press, pp. 1942-1948, 1995. Article (CrossRef Link).

[3] D. Merkle and M. Middendorf, "Swarm Intelligence and Signal Processing," IEEE Signal Processing Magazine, vol. 25(6) pp. 152-158, 2008. Article (CrossRef Link).

[4] K.M. Passino, "Biomimicry of Bacterial Foraging For Distributed Optimization and Control," IEEE Control Systems Magazine, vol. 22(3), pp. 52-67, 2002. Article (CrossRef Link).

[5] S. Mishra, "a Hybrid Least Square-Fuzzy Bacterial Foraging Strategy for Harmonic Estimation," IEEE Transactions on Evolutionary Computation, vol. 9, pp. 61-73, 2005. Article (CrossRef Link).

[6] S. Mishra and C.N. Bhende, "Bacterial Foraging Technique-based Optimized Active Power Filter for Load Compensation," IEEE Transactions on Power Delivery, vol. 22(1), pp. 457-465, 2007. Article (CrossRef Link).

[7] S. Dasgupta, S. Das, A. Biswas and A. Abraham, "Automatic Circle Detection on Digital Images with an Adaptive Bacterial Foraging Algorithm," Soft Computing, vol. 14(11), pp. 1151-1164, 2010. Article (CrossRef Link).

[8] H. Nouria and T. S. Hong, "Development of Bacteria Foraging Optimization Algorithm for Cell Formation in Cellular Manufacturing System Considering Cell Load Variations," Journal of Manufacturing Systems, vol. 32, pp 20-31, 2013. Article (CrossRef Link).

[9] S. Das, A. Biswas, S. Dasgupta and A. Abraham, "Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Applications, Foundations of Computational Intelligence," Global optimization, studies in computational intelligence, vol. 3. pp. 23-55, 2009. Article (CrossRef Link).

[10] S. Dasgupta, S. Das, A. Abraham and A. Biswas, "Adaptive Computational Chemotaxis in Bacterial Foraging Optimization: An Analysis," IEEE Tranactions on Evolutionary Computation, vol. 13(4), pp. 919-941, 2009. Article (CrossRef Link).

[11] A. M. Steane, "Quantum Computing," Reports on Progress in Physics, vol. 61, pp. 117-173, 1998. Article (CrossRef Link).

[12] L. Spector, H. Barnum, H. J. Bernstein, and N. Swamy, "Finding a Better-than-classical Quantum AND/OR Algorithm Using Genetic Programming," Congress on Evolutionary Computation, Piscataway, vol. 3, pp. 2239-2246, 1999. Article (CrossRef Link).

[13] A. Narayanan and M. Moore, "Quantum-Inspired Genetic Algorithms," in Proc. of IEEE International Conference on Evolutionary Computation, IEEE Press, Piscataway, pp. 1-66, 1996. Article (CrossRef Link).

[14] K-H Han and J-H Kim, "Genetic Quantum Algorithm and Its Application to Combinatorial Optimization Problem," in Proc. of IEEE Congress on Evolutionary Computation, IEEE Press, USA, pp. 1354-1360, 2000. Article (CrossRef Link).

[15] K.-H. Han and J.-H. Kim, "Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization," IEEE Transactions on Evolutionary Computation, vol. 6(6), pp. 580-593, 2002. Article (CrossRef Link).

[16] Cobo L. C and Akyildiz I. F., "Bacteria-based Communication in Nanonetworks," Nano Communication Networks, Vol. 1(4), pp, 244-256, 2010. Article (CrossRef Link).

[17] Gregori M. and Akyildiz I. F., "A New Nanonetwork Architecture using Flagellated Bacteria and Catalytic Nanomotors," IEEE Journal on Selected Areas in Communications, Vol. 28(4), pp. 612-619, 2010. Article (CrossRef Link).

[18] Lio P. and Balasubramaniam S., "Opportunistic Routing through Conjugation in Bacteria Communication Nanonetwork," Nano Communication Networks, Vol. 3(1), pp. 36-45, 2012. Article (CrossRef Link).

[19] Balasubramaniam S and Lio P., "Multi-hop Conjugation based Bacteria Nanonetworks," IEEE Transactions on NanoBioscience, Vol. 12(1), pp. 47-59, 2013. Article (CrossRef Link).

[20] Gao H.Y., Cui W. and Li C.W.. "A Quantum Bacterial Foraging Optimization Algorithm and Its Application in Spectrum Sensing," International Journal of Modelling, Identification and Control, vol. 18(3), pp. 29-36, 2013. Article (CrossRef Link).

[21] Mitola J. and Maguire G.Q., "Cognitive radio: making software radios more personal," IEEE Personal Commun., Vol. 6, Is. 4, pp. 13-18, 1999. Article (CrossRef Link).

[22] FCC, "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, 2003. Article (CrossRef Link).

[23] Akyildiz I.F., Lee Won-Yeol, Vuran M.C. and Mohanty S., "A survey on spectrum management in cognitive radio networks," IEEE Commun. Magazine, Vol. 46, Is. 4, pp. 40-48, 2008. Article (CrossRef Link).

[24] Jang S., Kim J., Byun J. and Shin Y., "Game Theory based Dynamic Spectrum Allocation for Secondary Users in the Cell Edge of Cognitive Radio Networks," KSII Transactions on Internet and Information Systems, Vol. 8, No. 7, pp. 2231-2245, 2014. Article (CrossRef Link).

[25] Nie N. and Comaniciu C., "Adaptive channel allocation spectrum etiquette for cognitive radio networks," in Proc. of IEEEDySPAN, pp. 269-278, 2005. Article (CrossRef Link).

[26] Kloeck C., Jaekel H., and Jondral F. K., "Dynamic and local combined pricing, allocation and billing system with cognitive radios," in Proc. of IEEE DySPAN, pp. 73-81, 2005. Article (CrossRef Link).

[27] Huang J., Berry R., and Honig M. L., "Auction-based spectrum sharing," ACM Mobile Networks and Applications (MONET), Vol. 11, No. 3, pp. 405-418, 2006. Article (CrossRef Link).

[28] Cao L. and Zheng H., "Distributed spectrum allocation via local bargaining," in Proc. of IEEE DySPAN, pp. 475-486, 2005. Article (CrossRef Link).

[29] Zheng H. and Peng C., "Collaboration and fairness in opportunistic spectrum access," in Proc.of 40th annual IEEE International Conference on Communications (ICC), pp. 3132-3136, 2005. Article (CrossRef Link).

[30] Peng C., Zheng H., and Zhao B. Y., "Utilization and Fairness in Spectrum Assignment for Opportunistic Spectrum Access," ACM Mobile Networks and Applications (MONET), Vol. 11(4), pp. 555-576, 2006. Article (CrossRef Link).

[31] Nainay El M. Y., Friend D. H., and MacKenzie A. B., "Channel allocation & power control for dynamic spectrum cognitive networks using a localized island genetic algorithm," New Frontiers in Dynamic Spectrum Access Networks, DySPAN, pp. 1-5, 2008. Article (CrossRef Link).

[32] Zhao Z. J., Peng Z., Zheng S. L. and Shang J. N., "Cognitive Radio Spectrum Allocation Using Evolutionary Algorithms," IEEE Transactions on Wireless Communications, Vol. 8(9), pp. 4421-4425, 2009. Article (CrossRef Link).

[33] Li F., Zhu D.P., Tian F. and Li H.B.. "Cognitive Radio Competitive Spectrum Sharing Using Improved Quantum Genetic Algorithm," in Proc. of International Conference on Wireless Communications and Signal Processing, pp. 1203-1209, 2011. Article (CrossRef Link).

[34] Cao J.L. and Gao H.Y., "A Quantum-inspired Bacterial Swarming Optimization Algorithm for Discrete Optimization Problems," Advances in Swarm Intelligence, Lecture Notes in Computer Science, Springer, vol. 7331, pp 29-36, 2012. Article (CrossRef Link).

[35] Zhang G.Y., Wu Y.G. and Y.X., "Bacterial Foraging Optimization Algorithm with Quantum Behavior," Journal of Electronics & Information Technology, vol. 35(3), pp. 614-621, 2013. Article (CrossRef Link).

[36] Passino K.M., "Bacterial Foraging optimization," International Journal of Swarm Intelligence Research, vol. 1(1), pp. 1-16, 2010. Article (CrossRef Link).

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.

Fei Li (1,2), Jiulong Wu1, Wenxue Ge (1) and Wei Ji (1,2)

(1) College of Communication and Information Engneering, Nanjing University of Posts and Telecommunications Nanjing 210003, China [e-mail: lifei@njupt.edu.cn]

(2) Key Lab of Broadband Wireless Communication and Sensor Network Technology of Ministry of Education, Nanjing University of Posts and Telecommunications Nanjing 210003, China

* Corresponding author: Fei Li

Received October 11, 2014; revised December 11, 2014; accepted January 1, 2015; published February 28, 2015

Table 1. The pseudo-code of QBFO

Step   Do

1      Initialize parameters p, S, [N.sub.c], [N.sub.s], [N.sub.re],
         [N.sub.ed], [P.sub.ed]. where

       p: dimension of the search space
       S: total number of bacteria in the population
       [N.sub.c]: number of quantum chemotactic steps
       [N.sub.re]: the number of quantum reproduction steps
       [N.sub.ed]: the number of quantum elimination-dispersal events
       [P.sub.ed]: quantum elimination-dispersal probability

2      Let t,j,k,l = 0

3      Initialization Q-bacteria population Q (t),
       [[alpha].sup.0.sub.m] and [[beta].sup.0.sub.m] of all
       [q.sup.0.sub.i] are initialized with 1-[square root of (2)].
       It means that one Q-bacterium [q.sup.0.sub.i] represents the
       linear superposition of all possible states with the same
       probability. The state of [q.sup.0.sub.i] is as (1).

4      Make P(0) by observing the states of Q(0). Quantum state Q(0)
       collapses to P(0), which is the set of binary solutions

5      Evaluate P(0). Each binary solution is evaluated to give a
       level of its fitness

6      Store the best solutions among P(0) into B(0), the initial
       best solutions are then selected among the binary solutions

7      while (not termination-condition) do
         begin
           t [left arrow] t + 1
           while (l [less than or equal to] Ned) do Quantum
             Elimination-dispersal
           begin
             l [left arrow] l + 1
             while (k [less than or equal to] Nr) do Quantum
               Reproduction
             begin
               k [left arrow] k + 1
               while (j [less than or equal to] Nc) do Quantum
                 Chemotaxis
               begin
                 j [left arrow] j + 1

8        Make P(t) by observing the states of Q(t-1). Quantum state
       Q(t-1) collapses to P(t), which is the set of binary solutions

9        Evaluate P(t). Compute fitness function, obtain the best
       fitness of the bacterium as the target of next evolution
       values

10       Update Q(t) using Q-gates. Q-bacteria in Q(t) are updated
       by applying Quantum rotation gates

11     Store the best solutions among B(t-1) and P(t) into B(t)

12         Store the best solution b among B(t)
         end

13     Compute Jhealth(i). Sort Q-bacteria in order of ascending
       cost

14       Quantum Reproduction. The half of the bacteria with the
       better values split (this process is performed by placing the
       copies that are made at the same location as their parent and
       the other half is eliminated
         end

15       Quantum Elimination-dispersal. Generate a random number
       rand, a Q-bacterium is eliminated if rand<[P.sub.ed]. Disperse
       another one to a random state as eq. (6).
         End

16       if (migration-condition)
           then migrate b or [b.sup.t.sub.j] to B(t) globally or
       locally, respectively
       end

Table 2. Description of the Benchmark Function Used

Function             Formula
name

Sphere function      [f.sub.1] (x,y) = [x.sup.2] + [y.sup.2]
([f.sub.1])

Needle-in-haystack   [f.sub.2](x,y) = [(3/0.05 + [x.sup.2] +
function             [y.sup.2]).sup.2] + [([x.sup.2] +
([f.sub.2])          [y.sup.2]).sup.2]

Shaffer's F6         [f.sub.3] (x,y) = 0.5 + [sin.sup.2]
function             [square root of ([x.sup.2] +
([f.sub.3])          [y.sup.2])] /0.5/[(1 + 0.001 x
                     ([x.sup.2] + [y.sup.2])).sup.2]

Multi-peak           [MATHEMATICAL EXPRESSION NOT
function             REPRODUCIBLE IN ASCII]
([f.sub.4])

Function             Optima                   Search
name                                          domain

Sphere function      [f.sub.1] (0,0) = 0      -100 [less than or
([f.sub.1])                                   equal to] x,y [less
                                              than or equal to] 100

Needle-in-haystack   [f.sub.2] (0,0) = 3600   -5.12 [less than or
function                                      equal to] x,y [less
([f.sub.2])                                   than or equal to] 5.12

Shaffer's F6         [f.sub.3] (0,0) = 1      -100 [less than or
function                                      equal to] x, y [less
([f.sub.3])                                   than or equal to]  100

Multi-peak           [f.sub.4](-512,-512) =   -512 [less than or
function             511.7319                 equal to] x, y [less
([f.sub.4])                                   than or equal to] 512

Function             Contour
name

Sphere function
([f.sub.1])

Needle-in-haystack
function
([f.sub.2])

Shaffer's F6
function
([f.sub.3])

Multi-peak
function
([f.sub.4])

Table 3. Experimental Results for 20 Independent Runs on four Benchmark
Functions

Function name        Algorithm   Best value   Worst value   Mean best
                                                              value

Sphere                  BFO      2.6980e-07   8.6672e-04    6.8164e-05
function                QGA      1.3296e-04   6.1000e-02    5.4486e-03
([f.sub.1])            QBFO      1.1369e-09   1.6220e-04    1.5472e-05
Needle-in-haystack      BFO         3600        2748.8        3004.2
function                QGA         3600         3594         3598.7
([f.sub.2])            QBFO         3600         3599         3599.9
Shaffer's F6            BFO        0.9903       0.7268        0.9457
function                QGA        0.9982       0.9900        0.9918
([f.sub.3])            QBFO        1.0000       0.9903        0.9989
Multi-peak              BFO       511.7078     497.2463      503.7723
function                QGA       511.5752     501.3417      508.4660
([f.sub.4])            QBFO       511.7319     501.8813      510.7167

Function name         Standard     Average     Average    Convergence
                     deviation    iterations   run time      runs
                                                 (s)

Sphere               1.8469e-04     156.67     0.932624       20
function             1.2980e-02     421.52     5.669402        9
([f.sub.1])          4.1785e-05     284.81     3.743355       20
Needle-in-haystack    400.2022      481.45     2.551758        6
function               1.6706       361.8      4.893244       12
([f.sub.2])            0.2471       295.3      3.808226       20
Shaffer's F6           0.0656        500       2.873371        0
function               0.0031       448.40     6.312885        4
([f.sub.3])            0.0030       230.40     3.001256       15
Multi-peak             4.5548       479.85     2.370211        3
function               2.9080       436.10     5.800089        4
([f.sub.4])            2.2493       182.00     2.490855       15

Table 4. Description of the matrices used

Matrix name                         Mathmatical expression

Channel availability matrix(A)      L = {[l.sub.n,m]|[l.sub.n,m]
                                    [member of] [{0, 1}}.sub.NxM]

Channel reward matrix(B)            B = [{[b.sub.n,m]}.sub.NxM]

Interference constraint matrix(C)   C = [{{[c.sub.n,m,k]|[c.sub.n,k,m]
                                    [member of] {0,1}}.sub.NxNxM]

Conflict free channel               A = [{[a.sub.n,m]|[a.sub.n,m]
  assignment matrix(A)              [member of] {0,1}}.sub.NxM]

Matrix name                         Value range

Channel availability matrix(A)      n = 1, ...N, m = 1, ...M

Channel reward matrix(B)            n = 1, ...N, m = 1, ...M

Interference constraint matrix(C)   n = 1, ...N, m = 1, ...M

Conflict free channel               n = 1, ...N, m = 1, ...M
  assignment matrix(A)

Table 5. The pseudo-code of QBFO based spectrum allocation algorithm

Step   Do

1      Initialize parameters p, S, [N.sub.c], [N.sub.s], [N.sub.re],
       [N.sub.ed], [P.sub.ed], L, B, C. where

         p: dimension of the search space
         S: total number of bacteria in the population
         [N.sub.c]: number of quantum chemotactic steps
         [N.sub.re]: the number of quantum reproduction steps
         [N.sub.ed]: the number of quantum elimination-dispersal events
         [P.sub.ed]: quantum elimination-dispersal probability
         L = {[l.sub.n,m]|[l.sub.n,m]}: channel availability matrix
         B = [{[b.sub.n,m]}.sub.NxM]: channel reward matrix
       C = [{{[c.sub.n,k,m]|[c.sub.n,k,m] [member of]
       {0,1}}.sub.NxNxM] : interference constraint matrix

2      Set t,j,k,l = 0, p = [N.summation over (n=1)][M.sub.summation
       over(m=1)] [l.sub.n,m] and set [L.sub.1] = {(n, m)|[l.sub.n,m]
       = 1}

3      Initialization Q/bacteria.population Q (t),
       [[alpha].sup.0.sub.m] and [[beta].sup.0.sub.m] of all
       [q.sup.0.sub.i] are initialized with 1/[square root of (2)].

4      Make P(t) by observing the states of Q(t).

5      Map w th (w = 1, 2, ..., p) bit of [p.sup.t.sub.v] to
       [a.sub.n,m], where (n,m) is the wth element in [L.sub.1]. For
       all m , search all (n,k) that satisfies [c.sub.n,k,m] = 1 and
       check whether both of the two bits corresponding to the element
       in the nth line and mth column of A and the element in the k
       th line and mth column of A are equal to 1; if so, randomly
       set one of them to 0.

6      Evaluate P(t) using test function of (15) or (16). Store the
       best solutions among P(t) into B(t), the initial best solutions
       are then selected among the binary solutions.

7      while (not termination-condition) do
       begin
         t [left arrow] t + 1
         while (l[less than or equal to]Ned) do Quantum
           Elimination-dispersal
         begin
           l [left arrow] l +1
           while (k[less than or equal to]Nr) do Quantum Reproduction
           begin
             k [left arrow] k + 1
             while (j[less than or equal to]Nc) do Quantum Chemotaxis
             begin
               j [left arrow] j +1

8      Make P(t) by observing the states of Q(t-1). Repeat the
       processes in step5.

9      Evaluate P(t) using test function of (15) or (16). Compute
       fitness function, obtain the best fitness of the bacterium as
       the target of next evolution values

10     Update Q(t) using Q-gates. Q-bacteria in Q(t) are updated by
       applying Quantum rotation gates

11     Store the best solutions among B(t-1) and P(t) into B(t)

12     Store the best solution b among B(t) end

13     Compute Jhealth(i). Sort Q-bacteria in order of ascending cost

14     Quantum Reproduction. The half of the bacteria with the better
       values split (this process is performed by placing the copies
       that are made at the same location as their parent and the
       other half is eliminated end

15     Quantum Elimination-dispersal. Generate a random number rand, a
       Q-bacterium is eliminated if rand<[P.sub.ed]. Disperse another
       one to a random state as eq. (6). End

16       if (migration-condition)
           then migrate b or [b.sup.t.sub.j] to
       B(t) globally or locally, respectively end
COPYRIGHT 2015 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Li, Fei; Wu, Jiulong; Ge, Wenxue; Ji, Wei
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Feb 1, 2015
Words:7640
Previous Article:Outage analysis and optimization for time switching-based two-way relaying with energy harvesting relay node.
Next Article:Group-sparse channel estimation using Bayesian matching pursuit for OFDM systems.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters