Priority Based Dynamic Spectrum Allocation in Cognitive RadioUsing Particle Swarm Optimization

Priority Based Dynamic Spectrum Allocation in Cognitive RadioUsing Particle Swarm Optimization

Anindita Saha, Jibendu Sekhar Roy

School of Electronics Engineering, KIIT University Bhubaneswar-751024, Odisha, India

AbstractDynamic spectrum allocation is usefulto improve the spectrum utilization efficiency in cognitive radio. In this paper, binary particle swarm optimization (BPSO) algorithm is used to find an optimum allocation of channels and to solve the channel assignment problem in cognitive radio network. Optimization uses an advanced dynamic spectrum allocation algorithm based on the priority of user nodes and priority of channel, using the thoughts of best-available multiple-allocation in order to meet the requirements of the customers. It not only provides higher allocation efficiency, but also reflects the fairness of spectrum allocation better. Simulation results are compared with the conventional method and results show superiority of the optimization method.

Keywordsbandwidth;cognitive radio; dynamic spectrum allocation; particle swarm optimization; priority

1. INTRODUCTION

   Cognitive Radio (CR) is an intelligent radio that can be programmed and configured dynamically[1]. Such a radio automatically detects available channels in wireless spectrum, then accordingly changes its transmission or reception parameters to allow more concurrent wireless communications in a given spectrum band at one location. In fixed spectrum allocation (FSA) the spectrum resources are statically allocated to the licensed users. However, FCC research [2] shows that most of the authorized spectrums are of low utilization. Meanwhile, the unlicensed users cannot use the idle spectrum temporarily to improve the utilization efficiency. Dynamic spectrum allocation (DSA) technology is considered to be an effective method to solve this problem. In the paradigm of cognitive radio whenever primary (licensed) user is not using its licensed band, secondary (unlicensed) users are allowed to use licensed band, and whenever primary user again starts using its band, secondary user leaves that band to keep interference low. So, in a widely studied form of CR technology known as opportunistic or dynamic spectrum allocation.

   There are already many researches [3-6] which analyse the spectrum allocation algorithms, such as game theory model, price auction model, and graph colouring theory. Peng and others [4] proposed a colour sensitive- Graph-Colouring (CSGC) algorithm based on label mechanism, which improved the performance by 50% compared with the classical algorithm. However, all the nodes

   in above references are considered to be equally important and are not distinguished by the priority. So it is essential to assign priority to each node and to each channel both at the same time in order to shorten the allocation time and improve the allocation efficiency. Therefore, an advanced dynamic spectrum allocation algorithm based on priority of nodes is used, which improve the fairness and allocation efficiency to meet the needs of CR users comparing to the existing CMSB and CMPF Algorithm.

   Recently, different evolutionary algorithms are used to solve the channel allocation problem; genetic algorithms [7-8], particle swarm optimization [8-9]. In this paper, Particle Swarm Optimization (PSO) is used to find an optimum solution of channel assignment problem based on priority and achieve better results than the other conventional approaches. PSO is a simple, fast and efficient computational method that optimizes a problem iteratively. As channel allocation problem requires the decision variable to be Boolean this paper tested the effectiveness (bandwidth utilization maximization) by a Binary Particle Swarm Optimization (BPSO) algorithm for better result.

2. SPECTRUM ALLOCATION MODEL

   A spectrum allocation network model [10] is introduced for channel availability observed by the secondary users. Each secondary network topology abstracted into a graph, where vertexes represent wireless users such as wireless lines, WLANs, or cells, and edges represent interferences betweenvertexes.

   Fig. 1. A topology of CR network

   If two vertexes are connected by an edge in the graph, these two nodes cannot use the same spectrum simultaneously. In addition, each vertex is associated with a set, which represents the available spectra at this location. Due to the differences in the geographical location of each vertex, the sets of spectra of different nodes may be different.

   A distributed network, the topology of CR network is shown in Fig. 1. This topology is also considered to be the coexistence of the authorized network and CR network. In Fig. 1, the five vertexes 1 to 5 represent five different CR users, also known as secondary users. There are three frequency bands (channels), namely A, B, and C, which are opportunistically available to the secondary users (vertexes 1 – 5 in this figure). Here four primary users I-IV are present, using bands B, A, B, and C, respectively. Due to the sharing agreement, channels used by primary users cannot be utilized by secondary users in locality. Therefore, nodes within certain interference ranges of the primary users I-IV cannot reuse the same frequency. In the figure, an interference range is illustrated by dotted circle. For example, Node 1 is within the interference range of primary user III, who uses channel B. Therefore, channel B is not available for Node 2. Only channel A and channel C are available. As a consequence, each node has access to a different set of bandwidths. In this figure, the available channels are (A, B, C) at vertex 5, (A,C) at vertex 4, etc. The resource allocation problem is how they share these channels.

   Fig. 2. A model of CR network based on graph theory

   In Fig. 2 the channel allocation problem is expressed as a graph colouring problem. The network is abstracted as a undirected graph G = (V, EC, LB), where V is a series of vertexes waiting to be allocated, alsocalled cognitive users, and represented by nodes 1 – 5 in Fig. 1. And the threedifferent line sections in Fig. 2 represent a series ofundirected edges EC which means that interferenceexists between every two vertexes, ifthere is an edge between two vertexes, the two usersrepresented by the two vertexes cannot use the samefrequency band simultaneously.

   keeps a list of available channels. Different secondary users are assigned different available spectrums based on its location and other requirements, and should be aware of its position with respect to the surrounding primary users as it cannot use a channel occupied by a primary user.

   Some variables are defined as follows for system mode [12]:

   1. Let N (0, 1, 2,,N – 1) be the number of secondary users.

   2. Let edges be represented by the N×N matrix E =

      {eij}, where ei,j = 1 if there is an edge between vertexes i and j, and ei,j = 0 implies that i and j may use same frequencies.

   3. Let M (0,1,2,….,M – 1) be the number of vacant channels.

   4. Let D = { dn| dn {0,1,2,.}}Nis defined as the demand matrix of users, and dn represents the channel capacity of user n.

   5. Let L = { ln,m|ln,m {0, 1}} N×M characterize the per user available spectrum, i.e. spectrum band m is available for user n if ln,m= 1.

   6. Let C = {cn,k,m|cn,k,m {0, 1}}N×N×M represent the interference constraint. Where if cn,k,m= 1, users n and k would cause interference if they used the spectrum band m simultaneously. Here the constraints are spectrum band specific. Note that two users who are constrained by one spectrum band, the cannot use this band simultaneously

   7. Let matrix A = { an,m | an,m {0, 1}}N×M is the spectrum allocation matrix, which denotes the effectiveness of spectrum allocation. Where an,m = 1 denotes that spectrum band m is assigned to user n. A satisfies all the constraints defined by C, i.e.

      n,m · ak,m = 0, if cn,k,m= 1, n, k < N, m < M.

   8. Let B = {bn,m}N×M describe the reward that a user n gets by successfully acquiring available spectrum band m, i.e. bn,m represents the maximum bandwidth/throughput that can be acquired (assuming no interference from other neighbors).

   9. Let matrix Lb = {ln,m · bn,m}N×M represents the throughput or the bandwidth of each channel which is available for each user to use.

   Thus the performance of the results of allocation can be expressed as follows by the above definitions:

   1. The total bandwidth of the system is [4]

      1 1

3. PROBLEM FORMULATION

   , . ,

   =0 =0

   (1)

   It is assumed that the available spectrum is divided into a set of spectrum bands and that bands differ from each other in

   1. The fairness of allocation can be represented as

      bandwidth and transmission range [11]. Each secondary user

      1

      1

      10( , . ,

      ) (2)

      =0 =0

4. A

   LLOCATION

   ALGORITHM

   1. System Initialization: Each base station in CR system 1st collects the position of CR users and accordingly collects the

      There are some algorithms like CMSB(Collaborative Max Sum Bandwidth) rule and CMPF(Collaborative Max Proportional Fair) rule. This rule aims to achieve a specific fairness among) algorithm where different label is defined for

      spectrum allocation[4]. In each stage, the algorithm labels all the vertices according to equation (3) with a non-empty color

      different priority function information of available spectrum resources. Among them, the number of available channels and the number of neighbour users are mainly used for pre allocation of spectrum, which can be defined as a ratio expressed as

      list according to a labelling rule. In this paper, dynamic spectrum allocation algorithm is used mainly based on the

      ratio =

      N

      (4)

      idea of BAMA (best available multiple allocate) [8] and the idea of CSGC algorithm [4] where each vertex is given color or channel from its color list, such that if a color m edge exists between any two distinct vertices, they cant be colored with m simultaneously.

   2. Resource Pre-allocation: During the pre-allocation of

      spectrum, like the CSGC algorithm, after calculating the ratio value for each user the user who has the max value of ratio will be allocated first until all users are allocated so that each user obtain maximum spectrum bandwidth. Every time the user who has the max value of ratio will be allocated first until

      ,

      label =

      (D , + 1)

      (3)

      all users are allocated.

   3. Check whether there are any unallocated users are left

      Where bn,m represents the maximum bandwidth and Dn,m denotes the number of users that have the same colour of edge (those who cannot use m if n uses color m).

      To improve the allocation efficiency and better fairness allocating priority to each node and to each channel both are needed. In order to meet the needs of CR users some priority function is defined based on the following features.

      1. Nrequired channel : the no of channel that users require;

      2. Nallocated channel :the number of channels that have been allocated for users in current allocation;

      3. Navailable channel : the no of available channel;

      4. Nneighbours: the no of neighbour users;

      The algorithm process is shown in Fig. 3. The step of allocation is described as follows:

      or not. If there is, modify the user priority and allocate again. Otherwise, allocate the channel according to the maximum value by the way of Step2 to realize the efficiency of CR system and to get the maximum utilization of system. But still there may be part of the users whose spectrum resources that cannot meet the minimum requirements of bandwidth for communication. Thus, the status of allocation, the demand of throughput will be considered comprehensively.

   4. For the remaining unallocated usersallocate the user with the highest priority for allocation based on Equation (3) & (4). Then delete the channel from matrix L (ln,m=0 ) of the current user and the neighbour user. Calculate the ratio and priority of each user again.

   5. Check whether Graph G is empty or not and then accordingly update the topology. If it is empty, the algorithm is finished. Otherwise, start allocation again from Step2.

5. PARTICLE SWARM OPTIMIZATION Evolutionary algorithm particle swarm optimization (PSO)

is a relatively recent heuristic search method whose mechanics are inspired by the swarming or collaborative behaviour of biological populations [13]. It optimizes a problem iteratively and trying to improve a candidate solution with regard to a given measure of quality. In PSO, a set of particles (NP) of swarm is defined and each particle represents a potential solution in the solution space and is characterized by its position and velocity. For a D- dimensional problem with N particles the position vector is represented as X(t) = (X1(t), X2(t), X3(t), XN(t)) where Xi = (xi1, xi2, xi3, . . . xiD) and the velocity vector is represented as V (t) = (V1(t), V2(t), V3(t),..,VN(t)) where Vi = (vi1, vi2, vi3,,viD)).Each particle updates its position and velocity based on its own best position (pbest) as well as the best position of the entire swarm (gbest) shown in Fig. 4.

i,d i,d 1 1 i,d i,d

V t+1= V t+ c t rand ( pbest t X t)

+ c2t rand2 (gbest t X t )

(5)

d i,d

Fig. 3. Flow chart of allocation algorithm

t+1 t t+1

X = X + V (6)

i,d i,d i,d

Where c1 and c2 are the learning factors, rand1 and

rand2 are independent random numbers, uniformly distributed in the range [0, 1].

V i,dt, X tand pbest t are the velocity, position and the

9: Determine the best particle (according to the particle's previous best positions).

10: Update particles' velocities according to the equation:

i,d

t

i,d

t

t V t+1= W

(pbest

tX

t) + W

(gbest tX t )

personal best of i particle in d dimension for the t iteration respectively. The gbesti,dt is the dt dimension of best particle

i,d 1

i,d

i,d 2

d i,d

(7)

in

In normal PSO the decision variables can assume a value in the real space. But channel allocation problem requires the decision variable to be Boolean. So in this paper, Binary Particle Swarm Optimization (BPSO) is used for solving the channel allocation problem based on priority in cognitive radio [14] using Boolean operators (bitwise operators). Particle velocity and positions are updated according to equations (2) and (3) respectively where denotes "XOR",

operator denotes "AND" operator, and + denotes "OR" operator [15].

1. BPSO ALGORITHM

   11: Move particles to their new positions according to the equation:

   i

   The algorithm starts with a randomly generated initial population (swarm) of particles. Particles in this population move through the problem space according to their velocities towards the optimum solution. Each particle stores its own best position, which is associated with the best objective function value it has obtained so far in a vector P t.

   The algorithm steps shown in Fig. 4 may be described as follows:

   1: Begin

   2: Determine utilization function U(R) using equation (1)

   X t+1 = X

   tV

   i,d

   i,d

   i,d

   & (2) for total bandwidth and fairness allocation.

   3: Initialize input parameters' values: B is the reward matrix, N denotes the number of radios, M denotes the number of channels, P denotes the number of particles. L denotes channel availability.

   4: Input controlling parameters' values containing personal best solution matrix pbestij, current solution matrix currentsolij, global solution matrix gbestij and velocity matrix velij, to

   zeroes where 0 <i N and 0 < j M.

   5: Generate an initial swarm randomly.

   6: For (t <max number of iterations) map the jth element in L where 1 < j < L for all particles. For all m, search all (n; k) that satisfies Cn,k,m= 1, and check if an,m= ak,m= 1, Then randomly set one of them to 0.

   7: Evaluate each particle's position according to the objective function U(R).

   8: Check if a particle's current position is better than its previous best position, accordingly update it.

   12: Find the current best solution for spectrum alloaction

   i.e. the optimum value then End.

   Fig. 4.BPSO algorithm – schematic illustration

2. SIMULATION RESULTS AND ANALYSIS

   The simulation results shows the performance analysis comparing the total bandwidth of CR system and the fairness of allocation based on the DSAPN algorithm (Dynamic spectrum allocation on priority of nodes) and the existing CMSB and CMPF algorithm in order to illustrate the influence of the improved algorithm.

   Assume that the number of channels which each user requires is random and less than the total number of channels. Here it is considered that the channel availability and the throughput or bandwidth of each channel within its range are random for different no of cognitive users. And the transmit power and channel gain are fixed in each channel of each user.

   Fig. 5. Total bandwidth of CR system for DSAPN for N=40

   Fig. 6. Total bandwidth of CR system for DSAPN for N=80

   In Fig. 5 and Fig. 6, the total bandwidth of CR system for DSAPN algorithm (Dynamic Spectrum Allocation based on Priority of Nodes) using equation (1), (3) & (4) are shown for the no of cognitive user N=40 and N=80 respectively. From the above two figures it can be seen that though the no of cognitive users is increasing the total bandwidth of CR system is not changing variedly, the nature is almost same. So it proves that the bandwidth utilization is not depends on the no of cognitive users.

   Fig. 7. Comparison of total bandwidth of CR system for different allocation algorithm

   In Fig. 7, comparison of total bandwidth of CR system is shown. No matter the algorithm is CMSB or CMPF only total bandwidth is considered during the process of allocation and it is shown that despite the increase in the number of cognitive radios, three algorithms get the same trend. CMSB can maximize the total bandwidth of CR system because it only considers the bandwidth, but also the performance of fairness should be considered.

   Fig. 8. Fairness of Allocation of CR system for DSAPN algorithm

   In Fig. 8 fairness of allocation of CR system for DSAPN algorithm is shown using Equation (2), (3) & (4). In this graph it is shown that as the no of cognitive user increases fairness is decreases and after that it saturates.

   Fig. 9. Comparison of fairness of Allocation for different algorithm

   In Fig. 9, comparison of fairness of allocation of DSAPN with exiting CMSB and CMPF is plotted, where it is shown despite the increase in the number of cognitive radios, three algorithms get the same trend in the fairness of allocation and CMPF can maximize the fairness of allocation.

   From the Fig. 7 and Fig. 9, it can be concluded that CMSB can maximize the total bandwidth of CR system because it only considers the bandwidth, but the performance of fairness is far worse than CMPF and DSAPN and CMPF can maximize the fairness of allocation but it also reduces the bandwidth of CR system. In view of the contradiction between the total bandwidth of CR system and the fairness of allocation, DSAPN algorithm used in this paper considers not only the influence of priority of channels but also the

   influence of priority of users to allocation. As there is a trade- off between bandwidth utilization and fairness of allocation, DSAPN gives better result for both cases to the maximum extent in order to have an eclectic curve of performance.

3. CONCLUSION

A dynamic spectrum allocation algorithm based on priority is used in this paper. It improves CSGC algorithm based on two factors: the bandwidth matching between the requirements of secondary users and the available channels, the interference avoidance to the primary users.It considers not only the priority of channels but also the priority of user nodes. And it pre-allocates the channels during the whole process. The results show that the algorithm can take both the total bandwidth of system and the fairness of allocation into account and obtains a compromising curve of performance. Simultaneously the algorithm can improve the effectiveness by optimizing the spectrum allocation method using BPSO algorithm.

In this work, it is assumed that the environment is static. If environment changes, this leads to significant overhead and delay.

Fig. 10. Optimized maximum bandwidth value in comparison with using BPSO and without using BPSO

In Fig. 10 the maximum bandwidth value i.e. gbest is optimized and plot the gbest value with the different no. of cognitive users for fixed no of available channels and particles. The spectrum allocation method using BPSO is compared with the conventional DSAPN method without using BPSO and it shows after optimization bandwidth is utilized maximum and gives better result. Here the effectiveness (utilization function maximization) is tested.

Fig. 11. Optimized fairness value in comparison with using BPSO and without using BPSO for fairness of allocation

In Fig. 11, the fairness of allocation value i.e. gbest is optimized and plot the fairness value with the different no. of cognitive users for fixed no of available channels and particles. The spectrum allocation method using BPSO is compared with the conventional DSAPN method without using BPSO and it shows after optimization it gives better result. Here the effectiveness (fairness of allocation) is tested.

REFERENCES

1. S. Haykin. Cognitive radio: brain empowered wireless communication. IEEE Journal on Selected Areas in Communications, 23:201220, February 2005.

2. Federal Communications Commission (FCC), Spectrum policy task force, Rep.ET Docket No.02-155, Nov.2002.

3. W. Wei, L. Xin. List-coloring Based Channel Allocation for Open- spectrum Wireless Networks [C]. The IEEE Vehicular Technology Conference (VTC), Seoul, Korea, 2005: 690-694.

4. Z. Haitao and P. chunyi. Collaboration and Fairness in Opportunistic Spectrum Access [C]. IEEE ICT2005, Wireless and Networking Group Microsoft Research Asia, Beijing, P.R. China, 2005, pp. 1-5.

5. I.F. Akyildiz et.al., next generation/dynamic spectrum access/cognitive radio wireless network: A survey Computer Networks, 2006, vol.50, pp. 2127-2159.

6. C. Liao, J. Chen, Y. Tang, S. Li. Parallel Algorithm of Spectrum Allocation in Cognitive Radio [J]. Academic Journal of Electronics] and Information Technology, 2007, pp. 1608-1611.

7. A. Hamza and M. Elghoneimy, "On the Effectiveness of using Genetic Algorithm for Spectrum Allocation in Cognitive Radio Networks," in Proc. 7th Int. Conf. on High Capacity Optical Networks and Enabling Technologies (HONET), 2010.

8. Z. Zhao, Z. Peng, S. Zheng and L. Shang, "Cognitive radio spectrum allocation using evolutionary algorithms," Wireless Communications, IEEE Transactions on, vol. 8, no. 9, pp. 4421-4425, 2009.

9. H. S. Abdelbaset, H. S. Hamza, A. M. AIShaar and H. M. Abdelsalam, &quotOn the Use of Particle Swarm Optimization Techniques for Channel Assignments in Cognitive Radio Networks," in Multidisciplinary computational intelligence techniques: Applications in business, Engineering, and Medicine, Hershey, IGI Global, 2013, pp. 202.

10. W. Wei, L. Xin. List-coloring Based Channel Allocation for Open- spectrum Wireless Networks [C]. The IEEE Vehicular Technology Conference (VTC), Seoul, Korea, 2005, pp. 690-694.

11. X. Xie, T. Zhou, X. Dong, L. He. A Requirement-based Algorithm in Dynamic Spectrum Allocation [J]. Communication Technology, 2008, vol. 41, pp. 9-11.

12. Z. Haitao and P. Chunyi. Collaboration and Fairness in Opportunistic Spectrum Access [C]. IEEE ICT2005, Wireless and Networking Group Microsoft Research Asia, Beijing, P.R. China, 2005, pp. 1-5.

13. L.Kennedy and R. Eberhart, "A discrete binary version of the particle swarm algorithm," in Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., 1997 IEEE International Conference on, vol. 5, Orlando, FL , USA , IEEE, 1997, pp. 4104- 4108.

14. A. Saha and J. S. Roy, Dynamic Spectrum Allocation in Cognitive Radio Using Particle Swarm Optimization International Journal of Emerging Technology and Advanced Engineering, vol. 4, pp. 54-60, April 2014.

15. N. Singh and S. Singh, "Personal Best Position Particle Swarm Optimization," Journal of Applied Computer Science, vol. 6, no. 12, pp. 69-76, 2012.