Solving channel assignment problem with hyper-heuristics in cognitive radio networks

Wireless networks communicate with each other using radio spectrum bands which are assigned to license owners. Traditionally, there is a fixed spectrum assignment policy issued by the governments or the communication companies. Because of the fixed spectrum assignment policy, a large portion of the spectrum stays unused. To utilize these unused spectrum portions, the idea of Cognitive Radio was proposed by J.Mitola. The aim of Cognitive Radio is maximizing spectrum utilization in an intelligent way. By doing that, Cognitive Radio enables the unlicensed users to also access the spectrum. However, this process should be done in such a way that when an unlicensed user attempts to use a spectrum, it should not interfere with the licensed users. In Cognitive Radio Networks terminology, a primary user is a licensed user which has been assigned a spectrum, while a secondary user is an unlicensed user which does not have a license to access a spectrum. For this reason, Secondary users use the cognitive radio technology to access the spectrum when the spectrum is not occupied by the primary user. This unoccupied spectrum portion is represented by a spectrum hole or white space. In Cognitive Radio Networks, primary users are known as the owners of a spectrum. They can use the spectrum whenever they want. On the other hand, secondary users can use the spectrum if and only if the spectrum is not currently occupied by the primary user. However, recently, a new data transmission protocol, which allows a primary user and a secondary user to work cooperatively, was proposed. In this method, a primary user releases a portion of the bandwidth to the secondary user to transmit its own data in exchange for making the secondary user to also relay the primary user's data. Channel Assignment is a fundamental technique to control interference in the cognitive radio networks. The aim of channel assignment is to assign channels to secondary users in order to maximize channel utilization. In channel assignment, the percentage of channel utilization can be increased by transmitting secondary user's data and primary user's data simultaneously. In this study, we use hyper-heuristics to solve the channel assignment problem. In literature, channel assignment algorithms try to optimize various objectives such as utilization optimization, interference minimization, network overhead minimization, throughput maximization, etc. Our objective is to maximize channel utilization. Hyper-heuristics are methods that work on the search space of low level heuristics rather than on the search space of solution candidates. Single point based search heuristics or population based meta-heuristics can serve as hyper-heuristics. In this study we use a single point based search heuristic, namely Adaptive Iterated Construction Search. Hyper-heuristics are defined as heuristics that select heuristics. A more recent definition of Hyper-heuristics is as: "A hyper-heuristic is an automated methodology for selecting or generating heuristics to solve hard computational search problems". Hyper-heuristics work on a search space of low-level heuristics as opposed to working on the search space of solutions. There are two types of Hyper-heuristics, i.e. Selection Hyper-heuristics and Generation Hyper-heuristics. Selection Hyper-heuristics choose from existing heuristics defined for a problem, while generation Hyper-heuristics generate new heuristics fora given problem by using components of existing heuristics. In this study we work with selection Hyper-heuristics, so for the rest of the paper we will use Hyper-heuristics to denote selection Hyper-heuristics. Single point based search approaches as well as population based meta-heuristics, such as ant colony optimization algorithms, can be used as Hyper-heuristics. In this study we use a single point based search approach, namely Adaptive Iterated Construction Search. Adaptive Iterated Construction Search can be considered as being a simple Ant Colony Optimization algorithm which works using a single ant. In our channel assignment problem model, both primary users and secondary users can transmit their data simultaneously on the same channel. In this study, we assume an underlying network architecture. More specifically, a secondary user can utilize the vacant channel as long as it does not disturb the primary user. To solve the channel assignment problem, we use a Hyper-heuristic approach based on Adaptive Iterated Construction Search. Given a traffic matrix, i.e. the primary users' spectrum usage information for each channel and for each time slot, the Hyper-heuristic aims to assign a channel to the secondary users for each time slot. To accomplish this, first, the Hyper-heuristic constructs a solution candidate which includes a set of low-level heuristics. Then, each low-level heuristic in the solution candidate is invoked in the order given by the solution candidate, to assign a channel to a secondary user. Next, the fitness value of the resulting assignments is calculated. In this study, we proposed a solution approach to the channel assignment problem in cognitive radio networks which uses the Adaptive Iterated Construction Search algorithm as a Hyper-heuristic to select the secondary users at each step of the channel assignment. To test the proposed approach we generated several test instances based on four parameters as follows: (i) Traffic matrix: We generated the traffic matrix using the Poisson distribution to determine the arrival times of the packets. (ii) Packet counts: We used two different packet counts in the experiments. (iii) Number of secondary users: Four different settings were used for this parameter. (iv) Number of channels: Three different settings were used while generating the test instances. By using the above parameters we created 72 different test instances. We evaluate the approaches tested in this study based on two criteria: (i) Channel Assignment Success Rate shows the success rate of an approach. It is calculated as the percentage of feasible assignments to the total number of channels. (ii) Channel Utilization Rate shows the utilization rate of the channels at time t, weighted by the Channel Assignment Success Rate. To show the effectiveness of the Hyper-heuristic approach which uses six low-level heuristics, each of the 72 test instances was solved with the proposed Hyper-heuristic (Adaptive Iterated Construction Search) as well as each low-level heuristic separately. Since Adaptive Iterated Construction Search is a stochastic algorithm, we ran the Adaptive Iterated Construction Search algorithm 20 times independently for each test instance. For this reason, in our result plots, we show the average value of 20 runs for Adaptive Iterated Construction Search. The results are shown as Weighted Channel Utilization Rates over Time. The results show that among the low-level heuristics, Max. Degree and Max. Priority low-level heuristics are the best performers with regard to channel utilization rate in all cases. Similarly, Min. Request is the best performer among all low-level heuristics with regard to channel assignment success rate. However, the channel utilization rate for this low-level heuristic is very low. The reason for this behavior is that this low-level heuristic chooses the secondary users in the increasing order of their requests. It is easier to find a channel assignment for smaller requests, therefore the channel assignment success rate of this low-level heuristic is high. However, since it assigns channels to those secondary users with lower requests first, the channel assignment rates of the assigned channels do not increase much after the assignments. Min. Degree, Max. Request and Random are the worst performing low-level heuristics. In the results given in the thesis, Adaptive Iterated Construction Search is either the best performer or it has a performance of similar quality to the well performing low-level heuristics.