Hany Kamal

Marceau Coupechoux

Philippe Godlewski

A Tabu Search DSA Algorithm for Reward Maximization in Cellular Networks

In this paper, we present and analyze a Tabu Search (TS) algorithm for DSA (Dynamic Spectrum Access) in cellular networks. We study a mono-operator case where the operator is providing packet services to the end-users. The objective of the cellular operator is to maximize its reward while taking into account the trade-off between the spectrum cost and the revenues obtained from end-users. These revenue are modeled here as an increasing function of the achieved throughput. Results show that the algorithm allows the operator to increase its reward by taking advantage of the spatial heterogeneity of the traffic in the network, rather than assuming homogeneous traffic for radio resource allocation. Our TS-based DSA algorithm is efficient in terms of the required memory space and convergence speed. Results show that the algorithm is fast enough to suit a dynamic context.

I. INTRODUCTION

Due to the spectrum crowd situation and the high demands on spectral resources, spectrum sharing and DSA techniques have been active research topics. The existing spectrum allocation process, denoted as FSA (Fixed Spectrum Access), headed for static long term exclusive rights of spectrum usage [START_REF] Buddhikot | Understanding Dynamic Spectrum Allocation: Models, Taxonomy and Challenges[END_REF] and shown to be inflexible [START_REF] Kamakaris | A Case of Coordinated Dynamic Spectrum Access in Cellular Networks[END_REF].

Spectrum sharing has been proposed as a promising method for better usage of spectrum. Researchers have worked on spectrum sharing algorithms motivated by the incentives taken by FCC to promote a better usage of spectrum [START_REF]Report of the Spectrum Efficiency Working Group[END_REF] [START_REF]Report of the Spectrum Rights and Responsibilities Working Group[END_REF]. For example, the authors of [START_REF] Buddhikot | DIMSUM-Net: New Directions in Wireless Networking Using Coordinated Dynamic Spectrum Access[END_REF] propose a coordinated DSA system where a common pool of resources (CAB or Coordinated Access Band) is shared and controlled by a regional spectrum broker.

In this paper, we consider a framework of several operators sharing a common pool of resources (or a CAB) inspired by [START_REF] Buddhikot | DIMSUM-Net: New Directions in Wireless Networking Using Coordinated Dynamic Spectrum Access[END_REF], and we focus on the strategy of one operator leasing spectrum from the broker. The operator does not own the spectrum, but rather has to lease it according to the demands. The operator is providing packet services for the end-users. We are interested in developing a DSA algorithm based on Tabu Search (TS) that provides the number of spectrum blocks to be acquired from the broker, as well as the frequency assignment corresponding to the maximum reward.

Several algorithms have been proposed to solve the CAP (Channel Assignment Problem) in cellular mobile networks. The classical CAP consists of assigning the channels to the cells within the mobile network while satisfying: [START_REF] Buddhikot | Understanding Dynamic Spectrum Allocation: Models, Taxonomy and Challenges[END_REF] interference constraints (co-channel, adjacent channel or both together) and ( 2) the traffic load demands. The proposed algorithms in the literature could be categorized as follows: algorithms based on heuristic methods [START_REF] Chakraborty | An Efficient Heuristic Algorithm for Channel Assignment Problem in Cellular Radio Networks[END_REF], others based on genetic algorithm [START_REF] Thilakawardana | Darwinian Approach for Dynamic Spectrum Allocation in Next Generation Systems[END_REF], on graph coloring method [START_REF] Subramanian | Fast Spectrum Allocation in Coordinated Dynamic Spectrum Access Based Cellular Networks[END_REF], and on neural network methods [START_REF] Wang | A Dynamic Channel-Borrowing Approach with Fuzzy Logic Control in Distributed Cellular Networks[END_REF].

Researchers have also studied frequency assignment using TS algorithm. For example, papers [START_REF] Peng | Optimal Channel Assignment in Cellular Systems using Tabu Search[END_REF], [START_REF] Montemanni | An Improved Tabu Search Algorithm for the Fixed-Spectrum Frequency-Assignment problem[END_REF], [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF], and [START_REF] Ph | Measurements of Propagation and Cohabitation in Ilede-France[END_REF] make a partial list of the references proposed TS algorithm to solve the fixed-spectrum CAP.

It is worth mentioning that most of the work done using TS to solve the fixed-spectrum CAP in cellular networks, has focused on circuit switched traffic (i.e. voice traffic) with application to the GSM networks (see [START_REF] Montemanni | An Improved Tabu Search Algorithm for the Fixed-Spectrum Frequency-Assignment problem[END_REF] for example). Treating voice traffic using TS has always been associated with a hard interference requirement: below a certain CIR (Carrier to Interference Ratio) threshold, the service is not accessible, while above this level, there is no significant increase of the service quality.

For this reason, the previous works have focused on the minimization of the interference (as an objective function), while satisfying the traffic demands. Note that in order to be able to perform the spectrum assignment, in fixed-spectrum CAP problems, it is necessary to know the number of channels required by each cell.

With the increasing demand of packet data services along with the development of new standards supporting packet applications, i.e. LTE and WiMAX, it would be interesting for DSA techniques to take into consideration the specificities of packet traffic. This is the challenge we are tackling in this paper. In contrast with the case of voice traffic, in packet traffic services, we see the interference constraint as a soft interference requirement, where interference can be tolerated without a hard threshold. A higher level of interference however induces a soft degradation of end-users throughput and consequently affects their satisfaction.

Different from references [START_REF] Subramanian | Fast Spectrum Allocation in Coordinated Dynamic Spectrum Access Based Cellular Networks[END_REF], [START_REF] Peng | Optimal Channel Assignment in Cellular Systems using Tabu Search[END_REF], [START_REF] Montemanni | An Improved Tabu Search Algorithm for the Fixed-Spectrum Frequency-Assignment problem[END_REF] and [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF] that used TS algorithms, we set an objective function of maximizing the operators' reward. The reward is computed here as the sum of revenues obtained from end-users deduced from the spectrum cost. The revenue obtained from a user is in turn an increasing function of its throughput.

In our formulation of the dynamic-CAP for packet service, the operator does not know the number of frequency blocks required by the cells. Assigning only one, but poorly inter-fered, block to a given cell might provide higher throughput to the end-users than assigning two (or more) highly interfered blocks. The operator needs to find a certain level of compromise in order to maximize its reward (Section II-B).

In [START_REF] Subramanian | Fast Spectrum Allocation in Coordinated Dynamic Spectrum Access Based Cellular Networks[END_REF], the authors have used TS method to solve the minimum interference DSA problem. Our approach differs from [START_REF] Subramanian | Fast Spectrum Allocation in Coordinated Dynamic Spectrum Access Based Cellular Networks[END_REF] mainly due to the consideration of packet context. Consequently our formulation of the objective function, the neighborhood structure, and the tabu list is different and adapted to the packet traffic assumption. Our formulations presented in this paper leads to obtain a simple algorithm that does not require excessive memory space, and can be envisaged for the implementation in a dynamic context. Hereafter we summarize our main contributions: Presenting and analyzing a DSA algorithm based on adapted TS method, where (1) we consider packet traffic services, (2) we address the spectrum pricing issue, and (3) we set an objective function for maximizing the operator's reward.

In this paper we extend our work in [START_REF] Kamal | Inter-Operator Spectrum Sharing for Cellular Networks using Game Theory[END_REF] and [START_REF] Coupechoux | Optimal and Heuristic DSA Policies for Cellular Networks with Coordinated Access Band[END_REF] by presenting an algorithm for heterogeneous traffic, where we do not suppose a priori that a classical frequency reuse (e.g. reuse 1 or reuse 3) is deployed as it is done in the above references.

The paper is organised as follows: Section II presents the network model in terms of system model, DSA principle, cell capacity calculations, and reward model. In section III, we illustrate the TS framework and we give our algorithm's details. Section IV gives the numerical results. Conclusion is finaly given in section V.

II. NETWORK MODEL

A. System model

We study DSA on the cell level and we focus on a monooperator case. The operator is supposed to depoly one RAN (Radio Access Network) providing packet services to the endusers. The operator does not own the spectrum but rather has to lease it according to the traffic load. We are considering a hexagonal topology for the RAN, consisting of one central cell and two rings of cells surrounding the central cell. Fig. 1 gives the hexagonal model of our study, where parameter R is the cell radius. It is worth mentioning that the usage of a hexagonal model is only for the sake of simple simulations. Our algorithm behaves the same way no matter the type of network topology.

We assume a scheduling fair in throughput for the users of a given cell. The average data rate accessible by users in a cell is proportional to the bandwidth allocated to the cell and is equally divided among all users of the cell.

B. Dynamic spectrum access

In the considered system model, the core issue for the operator lies in the trade-off to be found between spectrum cost and revenues obtained from users: more spectrum means a higher cost for the operator but also higher throughputs for users that are encouraged to pay more for the service [START_REF] Coupechoux | Optimal and Heuristic DSA Policies for Cellular Networks with Coordinated Access Band[END_REF].

We suppose a DSA decision is taken by the operator at each event, i.e. arrival of a new user, or a user departure in any cell. A DSA decision assigns spectrum blocks to each cell in the RAN. We assume that at least one spectrum block is always available to each cell, so that starvation is not possible.

C. CIR and cell capacity

Clearly, the bit-rate obtained by the end-users depends on the perceived CINR (Carrier to Interference plus Noise Ratio) level. The CINR level depends on the frequency assignment.

The exact CINR distribution in a cell is hard to be determined in practice. For the sake of simplicity, we rely on an approximate calculation for the CINR by focusing on the cell edge, which is a worst case in terms of interference.

We consider an urban environment, and hence we neglect the noise and we focus on the CIR (Carrier to Interference Ratio). The users are assumed to be located on the cell border and facing the highest level of interference from the interefering cells.

According to the previous assumptions, the CIR perceived by the users in cell c on frequency block f , can be denoted by:

CIR f c = R -α B f i=1 (d c,i -R) -α ,
where R is the cell radius, α is the path-loss exponent, d c,i is the distance between the victim cell c and the interfering cell i, and B f is set of all cells using the frequency block f . We approximate the cell capacity (in bps) using Shannon's classical formula. The cell capacity is the sum of capacities provided by the frequency blocks used by the cell. Formaly, the cell capacity C c of cell c is denoted by:

C c = Fc f =1 W f log 2 (1 + CIR f c ),
where W f is the block size of frequency f in Hz, CIR f c is the CIR perceived by cell c on frequency block f and F c is the number of frequency blocks used by cell c.

As we consider fair throughput scheduling between users of a given cell. The data-rate D c obtained by each of the users in cell c is given by: D c = C c /N c , where N c is the number of users in cell c.

D. Reward model

The challenging issue in DSA techniques for the operator lies in the trade-off between the cost paid for the spectrum and the revenues obtained from the satisfied users: more spectrum per cell means a higher cost for the operator but also means higher throughputs for the end-users. Based on this principle we define a reward model that takes into account both the user date-rate as well as the spectrum price.

The reward function depends on the revenue expected by the operators. The higher the satisfaction of users, the higher the operator revenue. The revenue obtained from a given customer in cell c increases with its satisfaction:

φ c (D c ) = K u (1 -exp(-D c /D com )),
where K u is a constant in euros per unit of satisfaction, D com is a constant called comfort data-rate, and the satisfaction is an increasing function of the user data rate (without unit) [START_REF] Enderlé | User Satisfaction Models and Scheduling Algorithms for Packet-Switched Services in UMTS[END_REF].

We consider the spectrum price to be fixed by MHz. The cost paid by the operator for the spectrum can be given as:

K B W f F,
where F is the number of frequency blocks used by the RAN, W f is the block size in Hz, and K B is a constant in euros per block. Note that considering a different spectrum price function (for example a function that depends on the demands in the market as considered in [START_REF] Kamal | Inter-Operator Spectrum Sharing for Cellular Networks using Game Theory[END_REF] and [START_REF] Coupechoux | Optimal and Heuristic DSA Policies for Cellular Networks with Coordinated Access Band[END_REF]) will not affect the behavior nor the performance of our algorithm.

The reward obtained by the operator can thus be written:

g = B c=1 N c φ c (D c ) -K B W f F,
where B is the total number of cells in the cluster area where DSA is performed.

III. TABU SEARCH A. Principle

Tabu search is a metaheuristic that guides a local heuristic search procedure to explore the solution space beyond local optimality (by allowing a degenerated solution) [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF]. TS was originally presented by Glover in [START_REF] Glover | Tabu Search, Part I[END_REF] and [START_REF] Glover | Tabu Search, Part II[END_REF].

The basic idea is to forbid a move that would return to recently visited solutions by classifying them as tabu. Hereafter we give the fundamentals of TS. Let S be the set containing the possible solutions to a problem. For each solution s ∈ S there exists a subset of S called neighborhood of s. The neighborhood contains feasible solutions, each of them is obtained by making a simple move from the solution s. The algorithm uses a memory structure called TL (Tabu List) to avoid cycles. The algorithm forbids the selection of a solution among the neighborhood, if this solution have been visited in a previous iteration. At each iteration the TS updates the TL by adding attributes of the selected solution. Note that such attributes do not contain the complete solution otherwise handling the TL will become costly (in terms of required memory) when the number of iterations increases [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF]. Note that the TL has a limited size (called TT for Tabu Tenure) and the choice of the TT has an impact on the obtained result. The smaller the TT, the higher the chance to have cycles (visiting previously visited solutions) and hence TS cannot go beyond the local optimal solution. However if the TT is very large, very few options will be left for the neighborhood formation.

The initial point of the TS algorithm has its importance in determining the time (i.e. number of iterations) required to reach the optimal solution. Starting from a solution very far away from the zone where the optimal solution exists, will require more iterations to explore the different zones. An initialization process aims at facilitating the search procedure for the algorithm, through the reduction of the time required to reach the optimal solution. Usually an initialization process is based on some heuristic method.

B. Definitions

Before illustrating our implementation of the TS algorithm, we give the following key definitions.

• A solution s is defined as a Boolean matrix of size F max ×B, where F max is the CAB size (or the maximum number of blocks the operator can lease) and B is the number of cells in the RAN. An element s f c of the matrix is defined as:

s f c = 1, if frequency f is assigned to cell c, 0, otherwise.
Taking an example of F max = 3 blocks, and B = 5 cells, then a "possible" solution s can be given as:

s =   1 0 1 0 1 0 1 0 1 1 0 0 0 0 0  
In this simple example, only 2 blocks are used by the RAN (F = 2) and the operator pays for the corresponding spectrum size. • According to our model, a "possible" solution means there is at least one block assigned to any cell. Practically, this assumption helps reducing the search space for the algorithm, and hence increasing the chance of reaching a better solution in less number of iterations.

The assumption is also realistic that avoids a starvation situation.

• For each solution s ∈ S, we define the set of moves M (s) which can be applied to s in order to obtain a new solution s . • A neighbor s of the solution s is created by applying one move m, where m ∈ M (s). • The move m is a Boolean matrix of the same size as s, all its elements equal to zero except one, or two elements equal to one. • The reward g(s) achieved using a solution s is calculated as illustrated previously in sections II-C and II-D. The maximum reward ever-reached during the search process is denoted g max .

• At each iteration, attributes of the selected solutions are added to the TL.

We have chosen to consider the reward corresponding to each selected (among all neighbors at each iteration) solution as its attribute. There is two main advantages behind choosing the reward as the attribute of the visited solution. First, adding the reward g(s) (of the selected solution s) in the TL, will not only forbid the TS from selecting s as a valid solution for the following iterations, but will also forbid visiting all solutions that achieve the same reward as g(s).

The second advantage is related to the required memory space for the TL. Our TL is composed of a single vector of size TT, each of its elements being equal to the reward g(s) corresponding to the selected solution s. Note that, in our case, g(s) holds the complete needed information (from the operator's perspective) of the solution matrix s.

C. Implementation

We present hereafter our TS algorithm that suits the CAP for packet services: Algorithm 1 TS algorithm for reward maximization in packet services context 1: Initialization: an initial solution s init is found. Neighborhood formation: all possible neighbors of the initial solution s are created, except those who are listed as tabu.

6:

Neighbor selection: one solution s is chosen among the set of neighbors to be considered as the "initial" solution for the next iteration.

7:

Tabu list update: the reward g(s ) corresponding to the selected solution s is added to the TL.

8:

Max. reward update: the maximum ever-obtained reward g max is updated: if g(s ) > g max , then g max ← g(s ) end if 9: end while

We illustrate now the details of the steps given in Algorithm 1.

Initialization: We have chosen an initialization method based on randomly formed solutions. Note that the operator does not have any requirements on the number of blocks to assign to the cells (unlike [START_REF] Subramanian | Fast Spectrum Allocation in Coordinated Dynamic Spectrum Access Based Cellular Networks[END_REF], [START_REF] Peng | Optimal Channel Assignment in Cellular Systems using Tabu Search[END_REF] and [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF]), hence the total number of blocks to be used is unknown to the operator. We divide the search zones according to the total number of blocks the operator can lease (1, ..., F max ). Note that the search zone with a single block is a trivial one because in this case, there is a single possible solution corresponding to frequency reuse 1. We generate randomly 300 possible solutions for each search zone. The TS algorithm starts using the solution corresponding to the maximum obtained reward among all randomly created solutions.

Neighborhood formation: All possible neighbors are created by whether: (1) removing an assigned block from a random cell, (2) adding a non-used block to a random cell, or (3) replacing one of the used blocks in a random cell by a non-used block. Note that adding, removing, or replacing a frequency can be performed by a simple XOR operation. The neighbor s = s ⊕ m, where m is a Boolean matrix that contains zeros except one element equal to one in case of adding or removing a block. In case of replacing a block, two elements of the matrix m equal to one.

Neighbor selection: According to our defined objective function, the neighbor that achieves the maximum reward among all neighbors is selected.

IV. NUMERICAL RESULTS

A. Simulation scenarios and parameters

We consider a RAN consisting of 19 cells. The RAN's topology is formed of one central cell and two rings of cells surrounding the central cell as shown in Fig. 1.

Hereafter we define the parameters we used for our simulations. The maximum number of blocks F max the operator can lease is assumed to be 6 blocks, with block size of 1 MHz. The comfort bit-rate for the user D com = 500 Kbps, the cell radius R = 1 Km, and the path-loss exponent α = 3. The pricing constants are fixed as follows: K u = 10 euros and K B = 50 euros.

TS algorithm parameters are set as follows: Tabu Tenure = 200 and the maximum number of iterations M AXIT ER = 800 iterations. According to the defined parameter set as well as to the neighbor definition, the total number of possible neighbors created from a solution s equals to:

F max B -B s0 + B c F c Fc ,
where B s0 is the number of cells having one block in s, B is the total number of cells in the RAN, F c is the number of frequency blocks used by cell c, and Fc is the number of blocks not used by cell c. Note that F c + Fc = F max . The first part of the equation (F max B -B s0 ) represents the total number of possible neighbors created due to adding or removing a block from a cell, knowing that at least one block should be assigned to any cell. The summation part represents the total number of possible neighbors created due to the replacement of a block.

It is clear that, for our case study, generating all possible neighbors at each iteration is very feasible.

B. Homogeneous versus heterogenous traffic

Now we are going to use TS to compare the obtained reward through serving a specific amount of traffic load (determined by the total number of active users) in two different cases:

(1) the case of an operator using FSA, who assumed a homogeneous traffic over the RAN to perform its channel assignment, and (2) the case of an operator using DSA, who considers the exact (heterogenous) distribution of the traffic to dynamically assign spectrum blocks.

We have considered the parameter set given in section IV-A, with a total number of users equal to 57 users. We suppose the distribution of the users is following a decreasing function of the distance from the central cell. There is a high concentration of users in the central cell, and this concentration decreases with the distance from the center of the cluster. Tab. I gives all studied users' distributions following this criterion with a total number of users equals to 57 users. It gives the number of users/cell for the central cell, the middle-circle cells, and the outer-circle cells as well as the distributions' standarddeviation σ. The homogeneous traffic scenario is also included with its zero standard deviation (all cells have the same number of users). The operator using FSA has assigned frequency blocks to the cells while assuming a homogeneous traffic (last line of Tab. I). For a fair comparison, the assignment is obtained using the TS algorithm but remains fixed whatever the traffic conditions.

The operator using DSA adapts its frequency assignment according to the dynamic of the traffic and try to maximize its reward whatever its heterogeneity using the proposed TS based DSA algorithm.

Fig. 2 gives the obtained reward versus the standard deviation σ for both operators. Each point corresponds to a line in Tab. I. For σ = 0, as both operators launch the TS algorithm, obtained reward are equal. As heterogeneity grows up (σ increases), the FSA allocation remains the same for the first operator, while for the second, DSA strategy adapts the assignment to the traffic.

We can notice that the obtained reward decreases as σ increases for both cases, even for the operator who considers the real traffic in the RAN. Fig. 2 shows however that the reward obtained by the DSA operator exceeds the reward obtained by the FSA operator for all values of σ.

We give in Fig 3 the spectrum assignment obtained using TS-based DSA algorithm for σ = 7.28.

The numbers indicated on the cells represent the block numbers. The TS-based DSA algorithm has assigned one block to all the cells, except the central cell. The algorithm has assigned 3 blocks to the central cell; two of them (block 4 and block 5) are not assigned to any of the other cells, while the third block (block 2) is assigned to some of the cells on the outer-circle. We see this assignment is coherent with the distribution of users in the cells. Note that the central cell has 33 users (see Table I).

C. Performance of TS

In this section, we evaluate the performance of our TS algorithm in terms of the minimum number of iterations required to reach an "efficient" solution. This metric is important from the dynamicity point of view of the algorithm. We assume the same parameter set as given in section IV-A. The RAN has a total number of 57 users. We compare different cases of users' distributions: homogeneous and heterogeneous distributions.

Fig. 4 gives the mean obtained reward using TS as a function of the number of iterations for σ = 0, 2.76 and 3.46 (see Table I for the exact number of users in each cell). Each of the presented curves in Fig. 4 is the output of averaging 250 trials.

It is clear that the higher the number of iterations, the higher the chance to get a better solution. A too high number of iterations would however prevent an operator from using the proposed algorithm in a dynamic context.

We can notice from Fig. 4 that the mean value of the reward increases with the increase of the iterations' number until it stabilizes (this is true for all values of σ).

The minimum number of iterations required for the mean reward to stabilize is found to be approximately 200, 240, and 320 iterations for σ = 0, 2.76, and 3.46 respectively.

In the homogenenous distribution case (σ = 0) the mean re- ward curve stabilizes very fast. However in the heterogeneous case, the mean reward curve needs higher number of iterations to stablize. Obviously, finding the allocation which maximizes the reward in a heterogenous traffic case is more challenging. We can notice that the required minimum number of iterations are reasonable enough to allow the operator to launch the algorithm at each new event.

It is very important to note that the obtained minimum number of iterations is very dependant on the initial start point. In a dynamic context, and at each new event, the operator is supposed to start TS algorithm from the last reached allocation solution. Hence the minimum number of iterations are expected to be reduced.

V. CONCLUSION AND FUTURE WORK

We have presented and analyzed a TS algorithm for DSA in cellular systems adapted to packet services. We have studied a mono-operator case assuming the operator is sharing the spectrum. We focused on packet traffic context where we considered the revenues obtained from users as well as the spectrum price. We modeled an objective function for the maximization of the operator's reward. Our TS based DSA algorithm is simple, does not require an excessive memory space, and hence can be envisaged for the implementation in a dynamic context. Results have also shown that the algorithm is efficient in terms of convergence speed.

In our future work, we plan to study the temporal aspects of the traffic using event based simulations. We also plan to study a distributed approach that allows the operators to perform DSA on a larger RAN with high number of cells.

Fig. 1 .

 1 Fig. 1. Hexagonal network of study.

Fig. 2 .

 2 Fig. 2. Obtained reward by the two operators as a function of σ.

Fig. 3 .

 3 Fig. 3. Obtained spectrum assignment using TS-based DSA for σ = 7.28.

Fig. 4 .

 4 Fig. 4. Average reward versus the number of iterations.


Hany Kamal

Marceau Coupechoux

Philippe Godlewski

An Efficient Tabu Search DSA Algorithm for Heterogeneous Traffic in Cellular Networks

In this paper, we propose and analyze a TS (Tabu Search) algorithm for DSA (Dynamic Spectrum Access) in cellular networks. We consider a scenario where cellular operators share a common access band, and we focus on the strategy of one operator providing packet services to the end-users. We consider a soft interference requirement for the algorithm's design that suits the packet traffic context. The operator's objective is to maximize its reward while taking into account the trade-off between the spectrum cost and the revenues obtained from endusers. We focus on the temporal heterogeneity of the traffic and we show that our algorithm allows the operator to increase its reward by taking advantage of this heterogeneity, rather than assuming homogeneous traffic for spectrum allocation. We study the dynamicity of the algorithm through event-based simulations. Results show that our algorithm uses less spectrum and achieves less blocking probability than the FSA (Fixed Spectrum Access) case at the price of reduced user throughput.

I. INTRODUCTION

Due to the spectrum crowd situation and the high demands on spectral resources, spectrum sharing and DSA techniques have been active research topics. The existing spectrum allocation process, denoted as FSA (Fixed Spectrum Access), headed for static long term exclusive rights of spectrum usage [START_REF] Buddhikot | Understanding Dynamic Spectrum Allocation: Models, Taxonomy and Challenges[END_REF] and is shown to be inflexible [START_REF] Kamakaris | A Case of Coordinated Dynamic Spectrum Access in Cellular Networks[END_REF].

Spectrum sharing has been proposed as a promising method for better usage of spectrum. Researchers have worked on spectrum sharing algorithms motivated by the incentives taken by FCC to promote a better usage of spectrum [START_REF]Report of the Spectrum Efficiency Working Group[END_REF] [START_REF]Report of the Spectrum Rights and Responsibilities Working Group[END_REF]. For example, the authors in [START_REF] Buddhikot | DIMSUM-Net: New Directions in Wireless Networking Using Coordinated Dynamic Spectrum Access[END_REF] propose a coordinated DSA system where a common pool of resources (CAB or Coordinated Access Band) is shared and controlled by a regional spectrum broker.

In this paper, we consider a framework of several operators sharing a common pool of resources (or a CAB) inspired by [START_REF] Buddhikot | DIMSUM-Net: New Directions in Wireless Networking Using Coordinated Dynamic Spectrum Access[END_REF], and we focus on the strategy of one operator leasing spectrum from the broker. The operator does not own the spectrum, but rather has to lease it according to the demands in order to provide packet services for the end-users. We are interested in developing a DSA algorithm based on TS (Tabu Search) that provides the number of spectrum blocks to be acquired from the broker, as well as the frequency assignment corresponding to the maximum reward.

Several algorithms have been proposed to solve the CAP (Channel Assignment Problem) in cellular mobile networks. The classical CAP consists of assigning the channels to the cells within the mobile network while satisfying: [START_REF] Buddhikot | Understanding Dynamic Spectrum Allocation: Models, Taxonomy and Challenges[END_REF] interference constraints (co-channel, adjacent channel or both together) and ( 2) the traffic load demands. The proposed algorithms in the literature could be categorized as follows: algorithms based on heuristic methods [START_REF] Chakraborty | An Efficient Heuristic Algorithm for Channel Assignment Problem in Cellular Radio Networks[END_REF], others based on genetic algorithm [START_REF] Thilakawardana | Darwinian Approach for Dynamic Spectrum Allocation in Next Generation Systems[END_REF], on graph coloring method [START_REF] Subramanian | Fast Spectrum Allocation in Coordinated Dynamic Spectrum Access Based Cellular Networks[END_REF], and on neural network methods [START_REF] Wang | A Dynamic Channel-Borrowing Approach with Fuzzy Logic Control in Distributed Cellular Networks[END_REF].

Researchers have also studied frequency assignment using TS algorithm. For example, the references [START_REF] Peng | Optimal Channel Assignment in Cellular Systems using Tabu Search[END_REF], [START_REF] Montemanni | An Improved Tabu Search Algorithm for the Fixed-Spectrum Frequency-Assignment problem[END_REF], [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF], and [START_REF] Subramanian | Fast Spectrum Allocation in Coordinated Dynamic Spectrum Access Based Cellular Networks[END_REF] make a partial list of the references proposing TS algorithm to solve the fixed-spectrum CAP.

It is worth mentioning that most of the work done using TS to solve the fixed-spectrum CAP in cellular networks, has focused on circuit switched traffic (i.e. voice traffic) with application to the GSM networks (see [START_REF] Montemanni | An Improved Tabu Search Algorithm for the Fixed-Spectrum Frequency-Assignment problem[END_REF] for example). Treating voice traffic using TS has always been associated with a hard interference requirement: below a certain CIR (Carrier to Interference Ratio) threshold, the service is not accessible, while above this level, there is no significant increase of the service quality.

For this reason, previous works have focused on the minimization of the interference (as an objective function), while satisfying the traffic demands. Note that in order to be able to perform the spectrum assignment, in fixed-spectrum CAP problems, it is necessary to know the number of channels required by each cell.

With the increasing demand of packet data services along with the development of new standards supporting packet applications, i.e. LTE and WiMAX, it would be interesting for DSA techniques to take into account the specificities of packet traffic. This is the challenge we are tackling in this paper. In contrast with the case of voice traffic, in packet traffic services, we see the interference constraint as a soft interference requirement, where interference can be tolerated without a hard threshold. A higher level of interference however induces a soft degradation of end-users throughput and consequently affects their satisfaction.

Different from references [START_REF] Subramanian | Fast Spectrum Allocation in Coordinated Dynamic Spectrum Access Based Cellular Networks[END_REF], [START_REF] Peng | Optimal Channel Assignment in Cellular Systems using Tabu Search[END_REF], [START_REF] Montemanni | An Improved Tabu Search Algorithm for the Fixed-Spectrum Frequency-Assignment problem[END_REF] and [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF] that used TS algorithms, we set an objective function of maximizing the operators' reward. The reward is computed here as the sum of revenues obtained from end-users deduced from the spectrum cost. The revenue obtained from a user is in turn an increasing function of its throughput.

Our formulations presented in this paper leads to a simple algorithm that does not require excessive memory space, and suits the implementation in a dynamic context. Hereafter we summarize our main contributions with respect to the related work: proposing and analyzing a DSA algorithm based on adapted TS method, where (1) we consider packet traffic services, (2) we address the spectrum pricing issue, (3) we set an objective function for maximizing the operator's reward, and (4) we introduce adaptations to TS for a dynamic deployment of the algorithm.

In this paper we extend our work in [START_REF] Kamal | Inter-Operator Spectrum Sharing for Celullar Networks using Game Theory[END_REF] and [START_REF] Coupechoux | Optimal and Heuristic DSA Policies for Cellular Networks with Coordinated Access Band[END_REF], where we supposed a priori that a classical frequency reuse scheme is deployed. We also extend the work in [START_REF] Kamal | A Tabu Search DSA Algorithm for Reward Maximization in Cellular Networks[END_REF] by focusing on the temporal heterogeneity of the network's traffic, rather than the spatial heterogeneity as done in [START_REF] Kamal | A Tabu Search DSA Algorithm for Reward Maximization in Cellular Networks[END_REF].

In this paper we also introduce amendements to the algorithm, in [START_REF] Kamal | A Tabu Search DSA Algorithm for Reward Maximization in Cellular Networks[END_REF], to better suit the implementation in a dynamic context: (1) enhancing the initialization process, (2) increasing the algorithm's convergence speed through: a) limiting the number of generated neighbors at each new event depending on the event type, b) reducing the complexity of calculating the reward corresponding to each neighbor by selecting only the concerned cells. Finally (3) we evaluate the performance of the algorithm's dynamicity using event-based simulations.

The paper is organised as follows: Section II presents the network model in terms of system model, DSA principle, cell capacity calculations, and reward model. In Section III, we illustrate the TS framework and we give our algorithm's details. Section IV gives the numerical results. Conclusion is finally given in Section V.

II. NETWORK MODEL A. System model

We study DSA on the cell level and we focus on a monooperator case. The operator is supposed to deploy a RAN (Radio Access Network) providing packet services to the endusers. The operator does not own the spectrum but rather has to lease it according to the traffic load. We are considering a hexagonal topology for the RAN, consisting of one central cell and two rings of cells surrounding the central cell. Fig. 1 gives the hexagonal model of our study, where parameter R is the cell radius. We assume a fair scheduling in throughput for the users of a given cell. The average data rate accessible by users in a cell is proportional to the bandwidth allocated to the cell and is equally divided among all users of the cell.

B. Dynamic spectrum access

In the considered system model, the core issue for the operator lies in the trade-off to be found between spectrum cost and revenues obtained from users: more spectrum means a higher cost for the operator but also higher throughputs for users that are encouraged to pay more for the service [START_REF] Coupechoux | Optimal and Heuristic DSA Policies for Cellular Networks with Coordinated Access Band[END_REF].

We suppose a DSA decision is taken by the operator at each new event, i.e. arrival of a new user, or a user departure in any cell. A DSA decision assigns spectrum blocks to each cell in the RAN. We assume that at least one spectrum block is always available to each cell, so that starvation is not possible.

At the very beginning, the operator is supposed to launch the TS for a sufficient number of iterations (which depends on the users' distribution in the RAN, as shown in [START_REF] Kamal | A Tabu Search DSA Algorithm for Reward Maximization in Cellular Networks[END_REF], and that ensures the algorithm is able to track the traffic changes), then at each new event the operator launches TS-based DSA for a reasonably limited number of iterations.

C. CIR and cell capacity

Clearly, the bit-rate obtained by the end-users depends on the perceived CINR (Carrier to Interference plus Noise Ratio) level. The CINR level depends on the frequency assignment.

The exact CINR distribution in a cell is hard to be determined in practice. For the sake of simplicity, we rely on an approximate calculation for the CINR by focusing on the cell edge, which is worst case in terms of interference. We consider an urban environment, and hence we neglect the noise and we focus on the CIR (Carrier to Interference Ratio). The users are assumed to be located on the cell border and facing the highest level of interference from the interefering cells.

According to the previous assumptions, the CIR perceived by the users in cell c on frequency block f , can be denoted by:

CIR f c = R -α B f i=1,i =c (d c,i -R) -α ,
where R is the cell radius, α is the path-loss exponent, d c,i is the distance between the victim cell c and the interfering cell i, and B f is set of all cells using the frequency block f . We approximate the cell capacity (in bps) using Shannon's classical formula. The cell capacity C c is the sum of capacities provided by the frequency blocks used by the cell:

C c = Fc f =1 W f log 2 (1 + CIR f c ),
where W f is the block size of frequency f in Hz, CIR f c is the CIR perceived by cell c on frequency block f and F c is the number of frequency blocks used by cell c.

As we consider fair throughput scheduling between users of a given cell, the data-rate D c obtained by each of the users in cell c is given by: D c = C c /N c , where N c is the number of users in cell c.

D. Reward model

The challenging issue in DSA techniques for the operator lies in the trade-off between the cost paid for the spectrum and the revenues obtained from the satisfied users. Based on this principle we define a reward model that takes into account both the user date-rate as well as the spectrum price.

The reward function depends on the revenue expected by the operators. The higher the satisfaction of users, the higher the operator revenue. The revenue obtained from a given customer in cell c increases with its satisfaction:

φ c (D c ) = K u (1 -exp(-D c /D com )),
where K u is a constant in euros per unit of satisfaction (without unit), D com is a constant called comfort data-rate, and the satisfaction is an increasing function of the user data rate [START_REF] Enderlé | User Satisfaction Models and Scheduling Algorithms for Packet-Switched Services in UMTS[END_REF].

We consider the spectrum price to be fixed by MHz. The cost paid by the operator for the spectrum can be given as:

K B W f F,
where F is the number of frequency blocks used by the RAN, W f is the block size in Hz, and K B is a constant in euros per block. The reward obtained by the operator can thus be written:

g = B c=1 N c φ c (D c ) -K B W f F,
where B is the total number of cells in the cluster area where DSA is performed.

III. TABU SEARCH

A. Principle

Tabu search is a metaheuristic that guides a local heuristic search procedure to explore the solution space beyond local optimality (by allowing a degenerated solution) [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF]. TS was originally presented by Glover in [START_REF] Glover | Tabu Search, Part I[END_REF].

The basic idea is to forbid a move that would return to recently visited solutions by classifying them as tabu. The algorithm uses a memory structure called TL (Tabu List) to avoid cycles. At each iteration the TS updates the TL by adding attributes of the selected solution. Note that such attributes do not contain the complete solution otherwise handling the TL will become costly (in terms of required memory) when the number of iterations increases [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF]. The TL has a limited size called Tabu Tenure TT.

The initial point of the TS algorithm has its importance in determining the time (i.e. number of iterations) required to reach the optimal solution. Starting from a solution very far away from the zone where the optimal solution exists, will require more iterations to explore different zones. An initialization process aims at facilitating the search procedure for the algorithm, through the reduction of the time required to reach the optimal solution.

As the minimum number of iterations required to reach an "efficient" solution using TS is very dependent on the initial start point, the basic idea of our TS-based DSA algorithm makes use of this dependency and applies the TS at each new event. In a dynamic context, the algorithm is launched at each new event where it starts from the last reached allocation solution.

B. Definitions

Before illustrating our implementation of the TS algorithm, we give the following key definitions.

A solution s, in our context, is defined as a Boolean matrix of size F max × B, where F max is the CAB size (or the maximum number of blocks the operator can lease) and B is the number of cells in the RAN. An element s f c of the matrix equals to 1 if frequency f is assigned to cell c, and 0 otherwise.

Taking an example of F max = 3 blocks, and B = 5 cells, then a "possible" solution s can be given as:

s =   1 0 1 0 1 0 1 0 1 1 0 0 0 0 0  
In this simple example, only 2 blocks are used by the RAN (F = 2) and the operator pays for the corresponding spectrum size. According to our model, a "possible" solution, means there is at least one block assigned to any cell. Practically, this assumption helps reducing the search space for the algorithm, and hence increasing the chance of reaching a better solution in less number of iterations. The assumption is also realistic that avoids a starvation situation.

For each solution s, we define the set of moves M (s) which can be applied to s in order to obtain a new solution s . A neighbor s of the solution s is created by applying one move m, where m ∈ M (s). The move m is a Boolean matrix of the same size as s, all its elements equal to zero except one or two elements that equal to one.

The reward g(s) achieved using a solution s is calculated as illustrated previously in Sections II-C and II-D. The maximum reward ever-reached during the search process is denoted g max . At each iteration, attributes of the selected solution are added to the TL. We have chosen to consider the reward corresponding to each selected solution (among all neighbors at each iteration) as its attribute (see section III-C).

C. Implementation

We present in Algorithm 1 our TS algorithm that suits the CAP for packet services.

We illustrate now the details of the steps given in Algorithm 1, and we illustrate the improvements with respect to the work in [START_REF] Kamal | A Tabu Search DSA Algorithm for Reward Maximization in Cellular Networks[END_REF] that suit a dynamic deployment of the algorithm.

Initialization: From our experience, we have noticed that the TS algorithm assigns a number of blocks to each cell that is proportional to the number of users in the cell. Accordingly, in this paper we add an amendment to the initialization method used in [START_REF] Kamal | A Tabu Search DSA Algorithm for Reward Maximization in Cellular Networks[END_REF] making use of this property, to get a good starting solution closer to the zone where the optimal solution exists.

We have chosen an initialization method based on randomly formed solutions. Note that the operator does not have any Algorithm 1 TS algorithm for reward maximization in packet services context 1: Initialization: an initial solution s init is found. 2: s ← s init 3: g max ← g(s init ) 4: while Nb. of iterations ≤ M AXIT ER do 5:

Neighborhood formation: all possible neighbors of the initial solution s are created, except those who are listed as tabu.

6:

Neighbor selection: the solution s that achieves the maximum reward is chosen, among the set of neighbors, s ← s 7:

Tabu list update: the reward g(s ) corresponding to the selected solution s is added to the TL.

8:

Maximum reward update: g max is updated: if g(s ) > g max , then g max ← g(s ) end if 9: end while requirements on the number of blocks to assign to the cells (unlike [START_REF] Subramanian | Fast Spectrum Allocation in Coordinated Dynamic Spectrum Access Based Cellular Networks[END_REF], [START_REF] Peng | Optimal Channel Assignment in Cellular Systems using Tabu Search[END_REF] and [START_REF] Capone | Channel Assignment Problem in Cellular Systems: A New Model and a Tabu Search Algorithm[END_REF]), hence the total number of blocks to be used is unknown to the operator. We divide the search zones according to the total number of blocks F the operator can lease, F ∈ (1, ..., F max ). We generate randomly 300 possible solutions for each search zone with the conditions: (1) only one block is assigned to the cell(s) having one user, (2) a number of blocks equals to F is assigned to the cell(s) having the maximum number of users. The TS algorithm starts using the solution corresponding to the maximum obtained reward among all randomly created solutions.

Neighborhood formation: All possible neighbors are created by whether: (1) removing an assigned block from a random cell, (2) adding a non-used block to a random cell, or (3) replacing one of the used blocks in a random cell by a non-used block. Note that adding, removing, or replacing a frequency can be performed by a simple XOR operation. The neighbor s = s ⊕ m, where m is a Boolean matrix that contains zeros except one element equal to one in case of adding or removing a block. In case of replacing a block, two elements of the matrix m equal to one.

For an efficient algorithm that can be executed at each new event, a limitation of the number of neighbors for the first iteration is introduced, in this paper, depending on the event type (i.e. arrival or departure of a user). In case of arrival or departure of a user, replacing one of the used blocks is considered, however: (a) adding a non-used block to a random cell is only considered in case of arrival, and (b) removing an assigned block from a random cell is only considered in case of departure.

Neighbor selection: In order to choose one TS neighbor, the operator needs to calculate the reward for all neighbors. This process might affect the efficiency of the algorithm. In order to reduce the algorithm's complexity, we introduce in this paper the following method for the selection of cells while calculating the reward for each TS neighbor.

For each move that creates a TS neighbor, only the affected cells by the move are chosen for the reward update. For example: In case of replacing f 5 by f 4 in a cell, then only the cells using f 5 or f 4 need to be updated. Tabu list update: we have chosen to consider the reward corresponding to each selected solution (among all neighbors at each iteration) as its attribute. There is two main advantages behind this approach: first, adding the reward g(s) (of the selected solution s) in the TL, will not only forbid the TS from selecting s as a valid solution for the following iterations, but will also forbid visiting all solutions who achieve the same reward as g(s).

The second advantage is related to the required memory space for the TL. Our TL is composed of a single vector of size TT, each of its elements being equal to the reward g(s) corresponding to the selected solution s. Note that, in our case, g(s) holds the complete needed information (from the operator's perspective) of the solution matrix s.

IV. NUMERICAL RESULTS

A. Simulation scenario and parameters

We consider a RAN consisting of 19 cells. The RAN's topology is formed of one central cell and two rings of cells surrounding the central cell as shown in Fig. 1.

Hereafter we define the parameters used for our simulations. The maximum number of blocks F max the operator can lease is assumed to be 6 blocks, with block size of 1 MHz. The comfort bit-rate for the user D com = 500 Kbps, the cell radius R = 1 Km, and the path-loss exponent α = 3. The pricing constants are fixed as follows: K u = 20 euros and K B = 100 euros. The maximum number of users that each cell accepts (according to the Connection Admission Control configuration) equals to 10 users. We suppose a heterogenous traffic (arrival rate per cell) in the RAN. There is a high concentration of traffic in the central cell, and this concentration decreases as the distance from the cluster's center increases. We assume the arrival rate for the central cell λ 1 = 4λ 2 , where λ 2 is the arrival rate per cell for the cells in the middle-circle, and λ 1 = 6λ 3 , where λ 3 is the arrival rate per cell for the cells in the outer-circle.

TS algorithm parameters are set as follows: TT = 200, the maximum number of iterations M AXIT ER = 300 iterations at the very begining of launching the TS, and 10 iterations at each new event. The presented results are the average of 20K events.

According to the defined parameter set as well as to the neighbor definition, the total number of possible neighbors created from a solution s, in the worst case, equals to 285 neighbors. It is clear that, for our case study, generating all possible neighbors at each iteration is very feasible.

We compare the reward obtained by two operators; (1) one assumes a homogeneous traffic over the RAN to perform its channel assignment, and (2) a second operator uses DSA, and considers the exact (heterogenous) distribution of the traffic to dynamically assign spectrum blocks.

In the coming section we evaluate the performance of the algorithm's dynamicity using event-based simulations.

Fig. 1 .

 1 Fig. 1. Hexagonal network of study.

B. Results

We compare between FSA and TS-based DSA in terms of the obtained reward, CAB utilization, blocking probability, and the user throughput. Note that in FSA case the operator uses the whole spectrum of the CAB and applies reuse 3 scheme. Fig. 2 gives the obtained reward as well as the CAB utilization versus the mean arrival rate λ using both TS-based DSA and FSA. We can notice that the obtained rewards using TS-based DSA exceed significantly the rewards obtained using FSA for all values of simulated λ, even for 2 ≤ λ ≤ 4s -1 where both techniques use 100% of the CAB. At λ = 1s -1 , the reward obtained using TS-based DSA is 334.5 compared to 75.9 using FSA (+345%). We can also see from Fig. 2 that a considerable spectrum conservation using the proposed DSA algorithm is achieved with respect to FSA for λ < 2s -1 .

Fig. 3 gives the end-user throughput as well as the blocking probability obtained using both FSA and TS-based DSA. As the FSA uses more spectrum than TS-based DSA, consequently the achieved user throughput is reduced for the DSA case, especially for low values of λ, as shown in Fig. 3. Note that in FSA case a single user in a cell takes advantage of using 2 blocks assigned to the cell, while in DSA case only 1 block is assigned to the user. As the spectrum allocation depends on the cells' traffic loads, the blocking probability decreases using DSA with respect to FSA.

V. CONCLUSION

We have proposed and analyzed a TS-based DSA for cellular systems adapted to packet services. We have considered a spectrum sharing context and we focused on the strategy adapted by one operator to maximize its reward. The revenues are modeled as an increasing function of the achieved throughput of end-users. We adapted the TS objective function to suit packet traffic. Our TS-based DSA algorithm is simple, does not require an excessive memory space. The proposed algorithm allows the operator to increase its rewards, to use less spectrum, and to achieve less blocking probability, however at the price of reduced user throughput.