Genetic Fuzzy Scheduler for Spectrum Sensing inCognitive Radio Networks

Ahmed Mohamedou, Aduwati Sali, Borhanuddin Mohd. AliDepartment of Computer and

Communication Systems EngineeringUniversiti Putra Malaysia

Serdang 43300, Selangor, MalaysiaEmail: ahmadmalic18@hotmail.com; aduwati, borhan@eng.upm.edu.my

Mohamed OthmanDepartment of Communication

Technology and Computer NetworksUniversiti Putra Malaysia

Serdang 43300, Selangor, MalaysiaEmail: mothman@fsktm.upm.edu.my

Abstract—Spectrum sensing is a critical issue in any cognitiveradio (CR) system. Many factors can affect the overall systemperformance and one of them is the order of sensing attemptsof multiple channels. As the number of channels under consider-ation increases, the complexity of scheduling problem increasesas well. In addition, the problem is elevated if channels havedifferent behaviors and characteristics which is normally thecommon case. This paper proposes two scheduling techniquesfor spectrum sensing operations in cognitive-based IEEE 802.11system. The first technique adopts Fuzzy Inference System (FIS)approach to set the optimal order of sensing attempts. However,FIS scheduler is static and cannot adapt to the changing behaviorof wireless environment. Therefore, Genetic Algorithm (GA) isused to give the proposed FIS scheduler the ability to evolveand adapt to new environment conditions. The second techniqueproposed by this paper is heuristic-based scheduling algorithm.This algorithm is used as supporting mechanism for the geneticFIS scheduler. Several simulation experiments were conducted.They showed the outperformance of the proposed solution byachieving 300 Mbps increase in goodput.

Index Terms—Cognitive Radio, Wireless LAN, Genetic Algo-rithm, Fuzzy Inference System, Spectrum Sensing, Scheduling.

I. INTRODUCTION

Wireless local area network is one of the most used commu-nication technologies in the world. It can be seen everywhere;in public places and in private homes. This technology isfacing a big challenge in the near future [1]. The challengeis a result of the increasing demand on bandwidth due to thepopularity of many applications such as video sharing, highdefinition TV and Internet of Things [2]. WLAN providersaround the globe are looking for any useful technique thatcan deal with this challenge. One of the proposed solutionsto cope with this challenge is to implement cognitive radiotechnology [3], [4].

The primary motivation behind the implementation of CRin WLAN is spectrum underutilization in many bands such asTV white space.This underutilization can be considered as anopportunity to increase WLAN bandwidth. This can be doneby utilizing frequency bands that are not being used. However,WLAN must not cause any interference with the usage of thesefrequency bands by their owners.

The possibility of utilizing a channel depends on how the

owner of this channel is using it. The channel owner iscalled Primary User (PU), while the entity trying to utilizethe channel is called Secondary User (SU). In this paper, theSU is the WLAN system. The status of the channel underconsideration is always changing between two states based onthe PU activities in the channel. The first state is called Busystate where the PU is using the channel; while the secondstate is called Idle state where the PU is not utilizing thechannel. The idle state is usually called Opportunity as far asthe SU is concerned. The objective of SU is to find out anyopportunities in the channel and to use the channel duringthat time. To find an opportunity, the SU has to sense thechannel under consideration to determine if it is in the busystate or in the idle state. Sensing a channel consumes timethat can be better used for data communication. At the timeof sensing, WLAN cannot communicate since the wirelessstations in WLAN have only one set of radio front. This willreduce the total throughput of WLAN system especially ifno opportunity is discovered. The complexity of this problemincreases when the number of channels under consideration isincreased. Specifically, scheduling in cognitive WLAN is theability of finding the next channel to be sensed that has thehighest probability of being in the idle state.

In this paper, IEEE 802.11-2007 standard [5] is used as areference for WLAN since it is the most used standard.To con-struct any cognitive radio network, some level of coordinationis needed. In wireless LAN infrastructure mode, the accesspoint (AP) can play the role of coordinator. The main job ofcoordinating AP is to synchronize timing among the rest ofstations and to distribute any information about primary useractivities. Here, a scheduler for the AP is proposed as themain contribution. This scheduler is based on fuzzy inferencesystem and genetic algorithm. The contribution of this paperis improving the WLAN goodput by a factor of two or moredepending on the number of underutilized primary channels.

Many researches in literature have used the concept of fuzzyinference system and genetic algorithm to develop cognitiveradio systems. Hiremath and Patra [6] has proposed a tech-nique that can predict the transmission rate in cognitive radiosystem. They used Adaptive Neural Fuzzy Inference Systemapproach to construct their system. The main purpose of their

2012 International Symposium on Communications and Information Technologies (ISCIT)

978-1-4673-1157-1/12/$31.00 © 2012 IEEE 770

proposal is to simplify the use Elman neural networks. Theirmethod was able to outperform neural network performancewith less computational requirements. Kaur et al [7] proposedfuzzy inference system that can allocate the available band-width among cognitive users. The proposed system composedof two layers. The higher layer uses a mathematical model tomeasure the access delay; while the other layer is responsibleabout assuring Quality of Service (QoS) of different cognitiveusers.

On genetic algorithm front, Moghal et al [8] has usedGA to find the optimal radio settings of secondary usersto achieve the required quality of service. They encoded allradio parameters such as modulation technique and operatingfrequency as genes in chromosomes. They found out that geneswith small range of possible settings accelerate the evolutiontoward the optimal radio setting. Ye et al [9] work concernedon the interference restrictions in channel allocation. Theyused GA to find the optimal channel allocation in cogni-tive radio network. Specifically, penalty function concept isused to punish chromosomes that do not satisfy interferencerestrictions. Chromosomes with high penalty will have lowprobability in producing new generation. Their method wasable to turn good channel allocation policies.

The rest of the paper is organized as follow: the next sectionwill highlight the system model. Then, the proposed algo-rithms will be presented and explained. Subsequently, section4 will evaluate the proposed scheduler. Finally, conclusion willbe drawn in section 5.

II. SYSTEM MODEL

GFIS is composed of two parts, the Genetic Algorithm (GA)part and the Fuzzy Inference System (FIS) part. FIS is theactual system that controls the performed operations; whileGA is running on the top of FIS to improve its performance.

The corner stone in FIS [10], [11] is Fuzzy Logic Theory[12] where the variables are not limited to only two values(True or False). They can take any value between these twoextremities. The job of FIS is to take these fuzzy variables asan input and to produce a decision by using set of If-Thenrules.

GA [13] is a type of meta-heuristic approach that can beused to solve optimization problem with large solution space.It is inspired by the genetic evolution process in biologicalsystems. Each solution in the solution space of the problemis encoded as chromosome. GA chooses random set of theseschromosomes as initial population. Then, it applies the geneticprocess on this population to make it evolves toward theoptimal solution.

In this system model, it is assumed all participating stationsin the network can hear the AP transmission. If a station cannothear the AP, then it cannot receive data; therefore, it is not apart of the network. All stations can hear AP transmissioneven if they are not the recipient of that transmission. Thisfact is very useful in synchronization process among stations.Wireless stations in the network have to be synchronized inorder to execute the quiet period. This quiet period is necessary

to sense the channels without any interference from neighborstation transmissions.

Fig. 1: Typical WLAN operation in time dimension [5].

Most of the time, AP sends two types of frames to wirelessstations in unicast transmission mode. The first type is dataframe; while the second type is acknowledgment frame. Thetransmission of these frames can be used by wireless stationsin the network as trigger to their stopwatch for spectrum sens-ing. All wireless stations should listen to the AP transmission(either data frame or acknowledgment frame) and recognizewhen the AP finish transmitting. The moment the AP finishits transmission, all wireless stations can calculate how longthey should wait before they start sensing the channel underconsideration. In the case where the AP is transmitting dataframe, wireless stations should wait for a duration equivalentto SIFS time + acknowledgment time + DIFS time (see figure1). Note that the acknowledgment time is constant since theacknowledgment frame size is fixed. After concluding thiswaiting time, all wireless stations in the network (including theAP) should sense the channel under consideration to discoverits occupancy status.

A. System Parameters

Each channel in the spectrum will have two states dependingon the primary user operation (Busy or Idle). This paperassumes that the lengths of idle period and busy period areexponentially distributed which is a realistic assumption forhighly dynamic system such as mobile telecommunicationsystems. Here, nI is the number of successful sensing attemptsthat lead to idle channel states and nB is the number ofunsuccessful sensing attempts that lead to busy channel states.ni is the only parameter that the system can control. Whereni is the total number of sensing attempts on i-th channel(ni = nI

i + nBi ). By manipulating this parameter, the system

should be able to increase or decrease the probability ofsuccessful sensing attempts.

One of the variables that are controlled by ni is the SuccessRate (Ri) which is the ratio between nI

i and ni:

Ri =nIi

ni(1)

In addition to success rate, this paper proposes the use ofanother parameter in scheduling decision. This parameter is

771

called Relative Utilization (U). It describes how much eachchannel is being utilized by the CR system in comparison tothe rest of channels. In other words, it describes how mucheach channel is contributing to the CR system performancein comparison to the rest of channels. Relative utilization canbe computed by taking the ratio between the amount of timechannel i-th being utilized (Ti) and the total utilization timeof all channels. It can be calculated based on the followingformula where the total number of channels is M:

Ui = Ti/

M∑j

Tj (2)

The last parameter that is going to be used is calledRelative Investment (I). It is aimed to measure how much thesystem invested in specific channel to utilize it. It shows howmany sensing attempts have been consumed by each channel.Mathematically, Relative Investment is measured as follow:

Ii = ni/

M∑j

nj (3)

Both of Relative Utilization and Relative Investment can beused to measure the success of the scheduler. It is intuitiveto direct more investment (sensing attempts) to channels thathave more utilization.

III. COGNITIVE GENETIC FUZZY SCHEDULER (CGFS)

The proposed scheduling algorithm can be described in twolevels. The higher level describes the general architecture ofthe algorithm; while the lower level explains how genetic fuzzymechanism is used to produce the scheduling decision.

A. General Architecture

The spinal cord of the proposed algorithm is the Eligibilitylist (E). Each element in this list corresponds to one of thechannels that the cognitive system is trying to utilize. Thevalue stored in element i-th (Ei) shows the eligibility of i-thchannel to be selected by the scheduler. In other words, thescheduler selects the channel which has the largest eligibilityvalue. After every sensing attempt, values of the eligibilitylist are updated by the genetic fuzzy inference system. Usingonly fuzzy inference system (FIS) is much faster than usingthe genetic version (GFIS). However, FIS is a static controlsystem. It is supposed to work in the same fashion formdesign to the end of its usage. This fact makes it lack theability to control cognitive wireless systems because of theirdynamicity. Therefore, genetic algorithm is used to provideFIS with adapting capabilities. As a result, it can perform verywell with dynamic systems such as cognitive radio systems.

B. Scheduling Decision

The most important part in the proposed scheduler is howto calculate the eligibility values. The main method is throughthe genetic fuzzy inference system. However, the proposedscheduler does not depend only on genetic FIS. This due to thefact that genetic algorithm is slow and takes time to converge

to the optimal solution. Therefore, a faster method is proposedto take over when the genetic algorithm is not ready yet. First,genetic FIS method is explained. Then, the supporting methodwill be highlighted.

1) Genetic Fuzzy Inference System (GFIS): The primarycomponent of GFIS is the fuzzy inference system. Thiscomponent consists of a set of rules and knowledge base.These rules use the cognitive system parameters as an inputto calculate the eligibility values. The used parameters areSuccess Rate, Relative Utilization and Relative Investment.There are three fuzzy sets that are associated with the used sys-tem parameters and the eligibility. These fuzzy sets are Low,Medium and High. Gaussian membership function is used tocalculate each fuzzy set membership value for each parameter(fuzzification). Each fuzzy set has mean and standard deviationvalues. The knowledge base is the collection of all mean andstandard deviation values for every fuzzy set on every inputand the eligibility output. An example of reasonable rule is:

IF Ui is High AND Ri is High AND Ii is Low,

THEN Ei is High

This rule makes sense because a channel that has highutilization and successful rate with low investment should havemore investment by increasing its eligibility.

To use genetic algorithm, each possible FIS should beencoded into chromosome. This work uses a technique pub-lished in [14] to encode these chromosomes. To explain thetechnique, assume there are only two inputs. Each one of theseinputs can be imagined as a dimension in two dimensionscoordination system. There are only four values in eachdimension. These values are Low (1), Medium (2), High (3)and Ignore (0). The ignore value is used when the input is notconsidered in the rule. Also, each point in the coordinationsystem will have a value that represents the output fuzzy set.Possible values of the output are similar to the possible valuesof the inputs. The only difference is that the ignore valuemeans that the rule is not considered at all. Figure 2 shows anexample of this FIS:

At point (1,2) the value is 2 which can be interpreted to thisrule:

IF Input 1 is Low AND Input 2 is Medium,

THEN Output is Medium

Another example is point (3,3) where the output value is 2.This is can be translated as follow:

IF Input 1 is High AND Input 2 is High,

THEN Output is Medium

The rule at point (3,2) is ignored since the output value isignore (0). There are four possible output values to be coded inchromosomes. Also, what logical operator is used to combinethe rule with others is needed to be coded (Each rule is

772

Fig. 2: An example of FIS with two inputs.

combined with the rest of rules by either OR operator or ANDoperator). As a result, there are six possible combinations ofoutput values and logical operators. Three bits are required tocode these combinations. Each circle in figure 2 is coded bythree bits. These three bits form a gene in the chromosome.The total number of genes is equal to the total number ofpoints which is 16 in figure 2. Each gene is correspondingto a point in the coordination system. For example, the firstgene in the chromosome representing figure 2 is at point (0,0)and has a value of [000]. The third gene is at point (2,0)and has a value of [100] (note that the third bit is for thecombining logical operator which is zero for OR combining).The eleventh gene is at point (2,2) and has a value of [110].

Based on the geometric representation for the proposedscheduler, there are 64 points since there are three inputs(Ri,Ui and Ii which construct three dimensional coordinationsystem). The first point is ignored since all inputs are ignored.Therefore, there are 63 genes in scheduler chromosomes. Eachgene is represented by three bits. As a result the chromosomesize is equal to 189 bits.

Each chromosome in the genetic algorithm is evaluatedby how much time it utilizes during the evolution process.The chromosome that achieves the largest utilization is thechosen one to be decoded as the cognitive genetic fuzzy sched-uler. Two factors are very important in reaching the optimalscheduler. These factors are population size and number ofgeneration that the genetic algorithm used for the evolution.Increasing population size causes more diversity in the popu-lation which may lead to faster convergence. However, morecomputational resources are needed as well. Also, allowing thegenetic algorithm to run for many generations may producebetter scheduler but it takes longer time. Therefore balancingthese two factors is very important for the overall systemperformance.

2) Supporting Algorithm: The main purpose of the support-ing algorithm is to generate scheduling decision as fast andsimple as possible. It will be used when GFIS is not fully readyyet to take over the scheduling responsibilities. GFIS may not

be ready in times such as the starting period of the network orwhen the AP moves to new geographical location where thewireless environment is totally different. In these situations,GFIS needs some time to evolve toward the optimal FIS forthe new location. Supporting algorithm uses system parametersto update the eligibility values which will lead to a schedulingdecision.

Number of simple policies can be used in the supportingalgorithm. For example, the scheduling policy of the algorithmcan be ”Schedule the least invested channel” to give thischannel an opportunity to be utilized. The eligibility for thispolicy will be calculated as follow:

Ei = 1− Ii (4)

Or, the scheduling policy can be ”Schedule the channel withthe best performance so far”:

Ei = Ui ×Ri (5)

However, both of these policies have some drawback. Thefirst policy may waste a lot of sensing attempts on channelsthat are busy most of the time. These sensing attempts can beused for sensing channels that are idle. On the other hand, thesecond policy may cause starvation problem which leads tolow investment on channels that did not perform well at thebeginning of the network. One way to solve these drawbacks isto alternate between both of these policies. By doing that, thesupporting algorithm balances between the risk of starvationand unsafe investments.

IV. EVALUATION AND DISCUSSION

This section tries to evaluate the proposed scheduler throughsimulation in term of two performance metrics: Goodput andthe General Success Rate. Goodput is the total amount ofdata that has been sent so far at each moment of simulationtime. General Success Rate is computed by dividing the totalnumber of successful attempts by the total number of attemptsduring the evaluation. The general configuration setup ofsimulation is shown in table 1.

TABLE I: SIMULATION SETUP

Simulation Parameter Value

Minimum Mean 100 millisecondsMaximum Mean 1 secondSimulation Time 120 secondsPopulation Size 5 chromosomesNumber of Generations 5 generationsData Frame Time 1.573 millisecondsACK Frame Time 0.511 millisecondsChannel Bandwidth 20 MHzSpectrum Efficiency 7.22 bit/sec/HzNumber of Channels 5 channels

The main objective of any scheduler is to deliver the highestpossible goodput which is the first performance metric. Whenthe network starts, GFIS perform poorly because it is in the

773

phase of evolution. The length of evolution process dependsessentially on the complexity of fitness computation. Requiringmore time to evaluate the chromosome causes longer timeof poor performance. Keep in mind that each chromosomeshould be evaluated for enough time to capture the essenceof primary user behavior. As long as the GFIS performance ispoor, the supporting algorithm comes to handle the schedulingresponsibilities while GFIS is evolving. This holds until itsperformance become poorer than GFIS performance. Figure3 shows the goodput performance of the scenario with fivechannels. In this experiment GFIS performance by pass thesupporting algorithm performance after fifty seconds of evo-lution.

Fig. 3: Goodput of five channels scenario.

At the beginning of the cognitive wireless LAN, the generalsuccess rate will achieve high values although lot of fluctua-tions is observed. This behavior is a result of small numberof total attempts. To reach the real general successful rate, thetotal number of attempts should be very high. Figure 4 showshow the general success rate is decreasing as time increases.

Figures 3 and 4 show interesting results on how theproposed techniques work. GFIS outperforms the supportingalgorithm in term of goodput; while the later outperformGFIS in term of general success rate. This behavior is dueto the nature of how each algorithm generates its schedulingdecision. Half of the time, supporting algorithm depends on thesuccess rate to schedule (see equation 5). It chooses channelswith high success rate regardless of how long they will be idle;which is not a wise approach because data is transmitted inframes and these frames require specific period of idle time.Therefore, to have a successful transmission, a channel hasto be idle for at least the minimum period of frame time.However, this is not the case in the supporting algorithm. Itends up scheduling channels which are idle but not for long.This strategy leads to choose channels where the primary usersshow up in the middle of transmission of the first frame.Because of that, no real data ever transmitted easily sinceframes will be dropped due to the high error rate. On the other

Fig. 4: Success rate of five channels scenario.

hand, GFIS evolves based on a fitness function that favorschromosomes which can achieve longest cumulative idle time.Here, the system is more stable and steady. Therefore, totalnumber of transmission interruption caused by the appearanceof primary users will be reduced to the minimum. Frames willbe fully transmitted which leads to high goodput.

V. CONCLUSION

In conclusion, this paper shed a light on one of the mostimportant issues in cognitive radio which is scheduling ofchannel sensing. Each technology that tries to implementcognitive radio has to deal with this issue according to differentconditions such as the behavior of primary user, the nature ofthe wireless system or the requirements of regulatory bodies.Wireless LAN technology is primary focus of this work.Based on its characteristics, two scheduling technique wereproposed. The first technique adopts fuzzy inference systemto derive the scheduling decision. It uses genetic algorithm tofind the optimal set of rules that will be used to obtain thescheduling decision. The second technique follows heuristicapproach to achieve simplicity and rapidity. Both techniqueswere combined to produce a better scheduler. Several evalu-ation experiments were conducted which show the proposedscheduler ability of utilizing most of existing channels anddelivering high goodput.

REFERENCES

[1] K. J. Negus and A. Petrick, History of wireless local area networks(WLANs) in the unlicensed bands, vol. 11, no. 5, pp. 36 – 56, 6 2009.

[2] L. G. T. W. J. Yao and Y. Zhang, “Research on sensor design forinternet of things and laser manufacturing,” in Asia Communicationsand Photonics Conference and Exhibition (ACP), December 8 2010.

[3] I. Mitola, J. and J. Maguire, G.Q., “Cognitive radio: making softwareradios more personal,” Personal Communications, IEEE, vol. 6, no. 4,pp. 13 –18, aug 1999.

[4] I. F. Akyildiz, W.-Y. Lee, M. C. Vuran, and S. Mohanty, “Next genera-tion/dynamic spectrum access/cognitive radio wireless networks: A sur-vey,” Computer Networks, vol. 50, no. 13, pp. 2127 – 2159, 2006. [On-line]. Available: http://www.sciencedirect.com/science/article/B6VRG-4K00C5M-4/2/3ad0ce34d1af95ffc509bf0ccaa455ab

774

[5] “Ieee standard for information technology-telecommunications andinformation exchange between systems-local and metropolitan areanetworks-specific requirements - part 11: Wireless lan medium accesscontrol (mac) and physical layer (phy) specifications,” IEEE Std 802.11-2007 (Revision of IEEE Std 802.11-1999), pp. C1 –1184, 12 2007.

[6] S. Hiremath and S. Kumar Patra, “Transmission rate prediction for cog-nitive radio using adaptive neural fuzzy inference system,” in Industrialand Information Systems (ICIIS), 2010 International Conference on, 292010-aug. 1 2010, pp. 92 –97.

[7] P. Kaur, M. Uddin, and A. Khosla, “Fuzzy based adaptive bandwidthallocation scheme in cognitive radio networks,” in Knowledge Engineer-ing, 2010 8th International Conference on ICT and, nov. 2010, pp. 41–45.

[8] M. Riaz Moghal, M. Khan, and H. Bhatti, “Spectrum optimizationin cognitive radios using elitism in genetic algorithms,” in EmergingTechnologies (ICET), 2010 6th International Conference on, oct. 2010,pp. 49 –54.

[9] F. Ye, R. Yang, and Y. Li, “Genetic algorithm based spectrum assignmentmodel in cognitive radio networks,” in Information Engineering andComputer Science (ICIECS), 2010 2nd International Conference on, dec.2010, pp. 1 –4.

[10] E. H. Mamdani, “Advances in the linguistic synthesis of fuzzy con-trollers,” International Journal of Human-computer Studies / Interna-tional Journal of Man-machine Studies, vol. 8, pp. 669–678, 1976.

[11] M. Sugeno, Industrial Applications of Fuzzy Control. New York, NY,USA: Elsevier Science Inc., 1985.

[12] L. A. Zadeh, “Outline of a new approach to the analysis of complexsystems and decision processes,” Systems, Man and Cybernetics, IEEETransactions on, vol. SMC-3, no. 1, pp. 28 –44, jan. 1973.

[13] J. H. Holland, Adaptation in Natural and Artificial Systems: An Intro-ductory Analysis with Applications to Biology, Control and ArtificialIntelligence. Cambridge, MA, USA: MIT Press, 1992.

[14] P. R. Thrift, “Fuzzy logic synthesis with genetic algorithms,” in Inter-national Conference on Genetic Algorithms, 1991, pp. 509–513.

775