Abstract
Abstract -This paper proposes a methodology for the channel assignment problem in the cellular communication industry. The problem considers the assignment of a limited channel bandwidth to satisfy a growing channel demand without violating electromagnetic interference constraints. The initial solution is generated using a random constructive heuristic. This solution is then improved by using a hyper-heuristic technique based on the great deluge algorithm. Our experimental results, on benchmarks data sets, gives promising results.
INTRODUCTION
The choice of a cellular network as a communication platform has significantly increased in recent years and will continue to do so as mobile phones become more widespread and the number of services available increases. This phenomenon results in a requirement to efficiently allocate a limited frequency bandwidth to create extra channel capacity and coverage in a cellular network. The definition of a channel refers to the access methods used in a cellular system. If the cellular system uses frequency division multiple access (FDMA), the channel is referred to as a frequency slot. It is referred to as a time slot in a time division multiple access (TDMA) system. The 2"' generation cellular system Global System for Mobile Communications (GSM) uses a combination of both F D W D M A .
The methods available to increase channel capacity and coverage in a cellular network comprise of frequency reuse and cell splitting. Frequency reuse involves using the same frequency or channel simultaneously in other cells subject to the base transceivers station (BTS) distance. Cell splitting splits a larger cell into smaller cells in order to cover a particular geographical area. Each cell has a lower transmission power and thus offers the ability to reuse frequencies more often.
The problem with these methods is the electromagnetic interference between channels in the same cell (co-site channel constraint), interference between neighbouring cells (adjacent channel constraint) and interference between other cells utilising the same channel (co-channel constraint).
For a co-site channel constraint, the channels in the same site need to be separated by a minimum distance in the frequency domain. For an adjacent channel constraint, adjacent or neighbourhood cells cannot use an adjacent channel simultaneously. For a co-channel constraint, the same Channel cannot be assigned to certain pairs of radio cells simultaneously.
The offline task of allocating a set of radio channels to meet the requested traffic demand for a given numbers of calls is referred to as the fixed channel assignment problem (CAP) or the fixed frequency assignment problem (FAP). The term 'fixed' refers to the fact that channels are permanently assigned to a particular cell. The variant of this fixed scheme is dynamic CAP, where all channels are located in a central pool and dynamically assigned based on channel requests. In the 1' and 2"d generation cellular system, the performance of fixed CAP outperformed dynamic CAP under heavy traffic loads and uniform traffic distribution [I] .
There are two possible objectives in fixed CAP i.e. 121:
Minimum span problem (MS-CAP)
Given a traffic demand, cell station number and compatibility matrix, find the minimum number of consecutive channels used with free electromagnetic interference i.e.
Minimise the number of radio channels 5.t. traffic demand and interference constraint 2. Minimum interference problem (MI-CAP) Given a fixed number of radio channels, cell station number, traffic demand and Compatibility matrix, minimise the severity of channel interference i.e.
Minimise severity of channel interferences s.t. demand constraints In this paper, we consider the minimum span problem (MS-CAP). This paper is organised as follows. In Section 2 we discuss the problem description and the mathematical formulation. In Sections 3 and 4 we describe our proposed methodology followed by our experimental results and 
Ms-CAP PROBLEM DESCRIPTION
In the I* and 2"d generation of cellular systems, the frequency spec" is divided into evenly spaced consecutive channels using frequency division (FD) or time division (TD) [3] . Therefore, the channels are represented by positive integers 1, 2, 3,. . .,Z where Z is a maximum number of available channels.
The basic model of MS-CAP can be represented as follows (mostly adopted from [4, 5] ) N : a set of cells in the network, where N = (celll,ceZ12,. . , cell,").
where dj is the number of rad0 channels required in cell, in order to satisfy the channel demand. C : compatibility matrix, CNxN, where each element CO denotes the frequency separation required between cell, and cellj f;x : U* channel assigned to cell;.
Therefore, the objective of MS-CAP is to [6] Minimise 2 Subject to I , =,
A GREAT DELUGE HYPER-HEURISTIC FORMS-

CAP
Many heuristics are problem dependent, meaning that one heuristic cannot be used to solve different problems [I] . In order to alleviate this problem, the concept of a hyper-heuristic was introduced, which is, a (meta-)heuristics that operates on (meta-)heuristics [7] .
Hyper-heuristics are problem independent and have been successfully applied to various optimisation and scheduling problem [8, 9, 10 There is a barrier between the LLHs and hyper-heuristic, meaning that only non-domain data can pass through the harrier. Referring to the MS-CAP case, only the quality of solution (value of Z) and computation time of each heuristic is allowed to cross the barrier. The hyper-heuristic has no knowledge of the problem it is trying to solve, only that it has a set of LLHs, which it can call, and whether it is trying to minimise or maximise the evaluation function. The set of LLHs act as simple local search or other problem specific heuristics. Each LLH will typically, search a different neighbourhood structnre and each move by the LLHs will produce a new solution. The hyper-heuristic will make a decision whether to accept or reject the new solution. The hyper-heuristic is also used to decide which LLH to call at each iteration.
Continuously applying a single LLH can lead to becoming trapped in a local optima. One diversification strategy is to change the neighbourhood structure, i.e. by calling different LLHs. This is similar to the idea of Variable Neighbourhood Search (VNS) [12] . However, whereas VNS keeps applying a single heuristic, until it gets trapped in a local optima, hyperheuristics have a 'free' choice at each decision point as to which heuristic to call. Previous works on hyper-heuristic have mainly concentrated on the calling sequence of LLHs. The choice function hyper-heuristic [I31 ranks the solution quality performance of each LLH. Based on the previous quality result; the hyper-heuristic will decide which LLH should be called next. A genetic algorithm hyper-heuristic [9] used an allele in a chromosome to represent each LLH. The quality of the solution is evaluated based on the sequence of calls within the chromosome. Another approach has used a tabu list to monitor the performance of each LLH in solving an examination timetabling problem [ 1 I]. Instead of concentrating on LLH sequences, a Monte Carlo hyper-heuristic [IO] used an acceptance criteria based on the solution quality returned by randomly calling LLHs.
We have used the hyper-heuristic method from [lo] but propose a different acceptance criteria as used by Dueck [ 141. The method, the Great Deluge Algorithm (GOA), was extended and the performance of the algorithm as a local search metaheuristic was evaluated and gave a superior result on examination timetabling problem [ 151.
We can model MS-CAP as a local search framework by defining a solution space S, an objective function f and a neighborhood N. The basic concept of the Great Deluge Hyper-heuristic Algorithm can be shown by the pseudocode in figure 2:
Step I : Initialisation During the initialisation stage, the objective function f(sJ is set as LEVEL at the start of the algorithm. This is slowly reduced by DownRate at each iteratioa The performance of the algorithm is dependent upon the choice of the DownRate parameter and the starting value of LEVEL. In our case, we define DownRate using the concept adopted from [I51 and shown in figure 3:
Where DownRate = IfsJ-LB) /Iter LB =Best result Iter = Number of iterations problem, we set our stopping criteria as reaching this lowef bound. For more difficult instances, we use m time duration as our stopping criteria, which we set to 480 seconds.
Based on our preliminary experiments, the calling sequence of LLHs do not affect the solution quality. Therefore, in this paper, we only use randomly called LLHs, hut it could be extended to use other methods of calling LLHs as in [8, 9, 13] .
The proposed method is similar to a random decent method, which only accepts an improved solution, but in our proposed algorithm the acceptance of the new solution will be decreased according to DownRate value. As long as the returned solution is below the current value of LEVEL, the hyper-heuristic will accept this solution.
LOW LEVEL HEURISTICS
We have created four simple 2-opt local search methods to act as our low level heuristics (LLHs). The definition of each LLH is as follows:
Sort the channel from lowest to highest, delete the call with the highest channel assignment, randomly insert at any point and reassign the channel. Same ash,, but randomly select the call to delete. Same as h,, but find the hest point at which to reassign. Same as hi, but randomly change the call order starting from the insertion point. All the proposed LLHs will create unique moves with zero violating constraint with faster computation time except for h,, which acts like a steepest decent heuristic. h3 will find the best neighbour in the current nighbourhood struchxe; therefore it h, -h2 -hi-
II-

TESTING AND RESULTS
We have implemented and tested ow algorithm on a Pentium 111-700 MHz computer. We compare our performance with [16] , which proposed an algorithm that generates a population of random valid solutions using a quadnary representation [0,+1,-1 ,+91, which means [assignable,used,unassignable,unused].
Another comparison is with the latest work of Ghosh et al. [17] , where they use a genetic algorithm based on geometric symmetry and Batiti et. al [ 181, where they used a combination of randomised saturation degree and a local search approach. We implemented three different networks sizes (21, 25 and 55) with different compatibility matrix, C , and traffic demand, D. The details C and D can be found in [16] .
We use a random constructive heuristic to generate an initial solution and use two stopping criteria (reach the best known result or the maximum runtime is reached). We ran each experiment 10 times. By applying our approach we were able to achieve promising results as presented in table 1 and table 2 which respectively shown the average of minimum bandwidth (z) and the time taken to produce the result.
The results show that we found the lower bound on 11 out of 20 benchmarks problem within reasonable computation times. For the more difficult problem, (e.g. test 11 and test 12) with the maximum allowed time (480 seconds) and 'poor' initial solutions, we still manage to improve the solution quality by 26.4% and 16.3% respectively. As stated in [17] , these are the most difficult benchmarks problems and they had tun times of 16-80 hours in order to achieve their solutions. Also, due to the random element in our LLHs, the computation time varies for each run. For example, the computation time for test 1 varies from 17s to 102s and for test 3, the computation time vanes from 4s to 11 Is.
CONCLUSION
In this work, we have proposed an algorithm based on a hyperheuristic approach. As a problem independent, methodology hyper-heuristics are a rapid development tool for optimisation problem. We use a greedy constructive heuristic to generate an initial solution then apply LLHs to improve the solution quality. Results shows that our proposed algorithm can achieve promising results for all benchmarks problem, even though we cannot produce better quality solutions compared to previous work for some of the benchmark problem. However, our results are competitive, if not superior with respect to run time. In future work, we will use other acceptance criterias to compare against our proposed great deluge acceptance criteria and, we will increase the number of low level heuristics. We will also use different strategies to produce initial solutions, such as the use of randomised saturation degree (RSD), which has eiven sunerior result in orevious work 1181. wherebv they intelligent LLHs and by enhancing OUT approach by using the combination of the calling sequence and acceptance criteria, we hope to produce even better results in the future. 

{'paper_id': '1404568', 'title': 'Channel assignment in cellular communication using a great deluge hyper-heuristic', 's2_url': 'https://api.semanticscholar.org/CorpusID:1404568', 'source': 'S2ORC'}