# Optimized Hybrid Resource Allocation in Wireless Cellular Networks with and without Channel Reassignment

Authors: Xin Wu; Arunita Jaekel; Ataul Bari; Alioune Ngom
Journal: Journal of Computer Systems, Networks, and Communications
 (2010)

---

## Abstract

In cellular networks, it is important to determine an optimal channel assignment scheme so that the available channels, which are considered as “limited” resources in cellular networks, are used as efficiently as possible. The objective of the channel assignment scheme is to minimize thecall-blockingand the call-droppingprobabilities. In this paper, we present two efficient integer linear programming (ILP) formulations, for optimallyallocating a channel (from a pool of available channels) to an incoming call such that both “hard” and “soft” constraints are satisfied. Our first formulation, ILP1, does not allow channel reassignment of the existing calls, while our second formulation, ILP2, allows such reassignment. Both formulations can handle hard constraints, which includes co-siteand adjacent channelconstraints, in addition to the standard co-channelconstraints. The simplified problem (with only co-channel constraints) can be treated as a special case of our formulation. In addition to the hard constraints, we also consider soft constraints, such as, the packing condition, resonance condition,and limiting rearrangements, to further improve the network performance. We present the simulation results on a benchmark 49 cell environment with 70 channels that validate the performance of our approach.


---

## Body

## 1. Introduction

In recent years, there has been a great development in the field of the cellular networks due to the tremendous growth in the demand of mobile wireless communication services. The cellular principle partitions a geographical area intocells where each cell has a base station and a number of mobile terminals (e.g., mobile phone). The base station is equipped with radio transmission and reception equipment. A group of base stations are connected to the Mobile Switching Center (MSC). The MSC connects the cellular network to other wired or wireless networks. The base station is responsible for the communication between a mobile terminal and the rest of the information network. A typical cellular system architecture is illustrated in Figure 1.Figure 1
A typical cellular system architecture.In order to start a communication with a base station, a mobile terminal must obtain achannel from the base station. A channel consists of a pair of frequencies: one frequency (the down-link) for transmission from the base station to the mobile terminal, and another frequency (the up-link) for the transmission in the reverse direction. The channel assignment problem deals with assigning an appropriate channel for each communication request that arrives in a cell.Radio transmission in a channel may cause radio frequency interference in other channels, resulting in the degradation of the signal quality. Therefore, to alleviate the interference between channels, a channel that can be selected to be assigned to a new call must satisfy the following electromagnetic compatibility constraints [1], also referred to as hard constraints.(i)
Cochannel constraint (CCC): the same channel cannot be assigned to two cells that are separated by a distance less than a specified minimumreuse,(Some relevant terminologies are discussed in Section 2.), distance, r0.(ii)
Cosite constraint (CSC): channels in the same cell must be separated by a minimum amountg. That is, their radio frequencies must be far enough apart.(iii)
Adjacent channel constraint (ACC): channels assigned to neighboring cells must be separated by a minimum amountw.The hard constraintsmust be satisfied for the system to work properly. In addition to the above hard constraints, there are a number of soft constraints that can be used to guide the channel assignment process to improve the quality of the solution. However, the soft constraints may be violated if necessary [2]. The soft constraints include the following.(a)
Packing condition: try to use the minimum number of channels every time a call arrives [3]. This condition encourages the selection of channels already in use in other cells as long as the hard constraints are satisfied.(b)
Resonance condition: try to assign the same channels to cells that belong to the same reuse scheme [3]. The purpose of this approach is to leave as many channels as possible to be allocated to other cells belonging to other reuse schemes. Consequently, the probability of causing cochannel interference in the system is reduced.(c)
Limiting rearrangement: try to assign, whenever possible, the same channels assigned before to the existing calls, thus limiting the reassignment of channels. Channel reassignment is the process of transferring an ongoing call to a new channel without call interruption [4]. Such reassignment in the entire cellular network upon the arrival of a new call will obviously result in lower call blocking probability, but it is complex, both in terms of time and computation [3]. Therefore, the reassignment processes should be limited to a low level. On this account, limiting rearrangement condition is used to prevent excessive reassignment in a cell [3].The packing condition encourages reuse of the channels that are already in use in other cells. The motivation behind this is that the channels that are currently not being used anywhere can be allocated with more flexibility. So, if there is an option between using a channel (sayλ1) that is currently in use in one or more cells, and another channel (say λ2) that has not been allocated in any cell, the packing condition will promote the use of λ1 for the current call (assuming no hard constraints are being violated). This leads to increased flexibility, that is, it leaves the more flexible option (i.e., using λ2) available for any future incoming calls, thus increasing the likelihood that future calls can be accommodated more easily. To see why the packing condition can lead to a lower blocking probability (and hence, to better system performance), we consider a very simple example with three cells (C1, C2, and C3) and two available dynamic channels (λ1 and λ2). Suppose the cells are placed one after the other in a straight row (as shown in Figure 1) and the reuse distance r0=2, that is, the same channel cannot be used in two adjacent cells, but can be used if there is at least one intervening cell separating the two cells. Assume that there is an ongoing call in C1, which is using channel λ1. Now a call request arrives in C3. According to the packing condition, it should also use λ1. If a third request arrives in C2, this can then be accommodated using λ2. On the other hand, if the packing condition was ignored and the call in the cell C3 was allocated to channel λ2, then when the third call arrives in C2, it cannot be accommodated using either λ1 or λ2, and hence, must be blocked.The channel assignment schemes proposed in the literature can generally be divided into three categories: fixed channel-assignment (FCA), dynamic channel-assignment (DCA), and hybrid channel-assignment (HCA). In FCA, a fixed number of channels is assigned to each cell beforehand, based on estimated traffic, and in DCA, channels are dynamically allocated based on incoming call and the current network configuration. HCA is a hybrid of both FCA and DCA.In this paper, we present twooptimal integer linear programming (ILP) formulations, ILP1 and ILP2, that can be used for the hybrid channel assignment (HCA) problem in wireless cellular networks. The formulation ILP1 does not consider reassignment of existing calls in the cell, while the formulation ILP2 allows such reassignment to further reduce the blocking probability. Our approach can be applied to the dynamic channel assignment (DCA) problem as well. As opposed to the many existing channel assignment schemes [5, 6] that solve a simplified version of the channel assignment problem by addressing the cochannel constraint (CCC) only, our approach not only handles all three hard constraints, but also takes into consideration the soft constraints, mentioned above. In summary, the motivations behind the proposed formulations are as follows.(1)
Although there are many existing schemes for dynamically allocating channels to an incoming call, the vast majority of these only consider the simple cochannel constraint (CCC), but ignore the cosite constraint (CSC) and adjacent channel constraint (ACC) [6–10].(2)
The existing schemes are primarily based on heuristics, with no specified performance bounds. Therefore, it is not easy to analyze the quality of their solutions.(3)
Most existing schemes focus on the standard FCA or DCA techniques and relatively little work has been done on HCA.In this paper, our objective is to develop novel mathematical formulations (rather than heuristics) capable of generating optimal solutions for HCA. We wanted to develop an approach that jointly considers CCC, CSC and ACC as an integrated part of the channel selection process, rather than simply selecting a channel and then checking if the constraints are satisfied. Since the proposed formulations provide optimal solutions for this complex design problem, these can be used as benchmarks to evaluate existing (or future) heuristics.An earlier version of this paper appeared in [11]. The remainder of the paper is organized as follows. In Section 2, we review the relevant work on channel assignment schemes for cellular networks. In Section 3, we present our ILP formulations. We discuss our cellular model and experimental results in Sections 4 and 5 and conclude in Section 6.


## 2. Review

The availability of channels or frequency spectrum is very limited, as compared to the exponential growth of mobile terminals. This requires a method to share these channels for efficient assignment and proper management of channel resources.As the reuse of channels is inevitable in a cellular system, channels used at one cell site may also be used at other cell sites in the case of absence of cochannel interference. Cochannel interference is the radio interference caused due to the allocation of the same channel to certain pairs of cells with geographical separation not enough to avoid deterioration of signal quality. The minimum distance required between the centers of two cells using the same channel to maintain the desired signal quality is known as thereuse distance [3, 6, 12, 13]. Reuse distance determines an interference region marked by gray cells which locate around a given cell x as shown in Figure 2. Figure 3 shows a reuse pattern, with reuse distance equal to three, in which the cells with same number belong to the same reuse scheme and are free from cochannel interference. This reuse scheme is obtained by jumping from one cell to another in steps of length equal to the reuse distance [3, 14, 15]. The longer the reuse distance is, the smaller will be the cochannel interference level. However, a long reuse distance may result in lower reuse efficiency [15]. Thus, the frequency reuse scheme should be determined taking into consideration both the cochannel interference level and the reuse efficiency. Traditionally, channel assignment is made according to the cochannel interference level determined by a fixed reuse distance which is decided during network planning. Many approaches proposed in the literature to solve channel allocation problem are based on such concept [3, 6, 12, 13, 15–17].Figure 2
Reuse distance.Figure 3
Reuse pattern (reuse distance is 3).The channel assignment problem is the problem of allocating frequencies to mobile terminals and base stations such that the network's capacity, in terms of number of mobile users, is maximal. This is a well-known NP-hard problem [18] and has been widely investigated in the literature. Various channel assignment schemes have been studied widely to find better ways to assign channels to calls and to achieve higher level of channel reuse, which can be broadly classified as FCA, DCA, and HCA schemes.The FCA schemes [16, 19–22] allocate channels permanently to each cell based on predetermined estimated traffic. FCA scheme is simple but it does not adapt to the changes in traffic conditions. In a cell, a call can be assigned to a channel only if there is a free channel available in the predetermined set for this cell. Otherwise, the call might be rejected, even in some cases when many channels may be available in the network.In DCA, there is no permanent allocation of channels to cells. Instead, the whole set of available channels is accessible to all the cells, and the channels are assigned on a call-by-call basis, in a dynamic manner [7–9, 23–26]. Since a cell can use any of the channels in a dynamic way, it is possible that if a cell uses all channels at a given time, then there will be no channel available to its neighboring cells at that time due to the interferences. DCA makes wireless networks more efficient, especially if the traffic load distribution is not known beforehand, or varies with time. The advantage of DCA is the flexibility and the traffic adaptability, since channel assignment is based on the current network conditions. DCA methods have better performance than FCA methods for light to medium traffic load [6]. Most of the proposed DCA algorithms are based on heuristics, and do not guarantee an optimal solution. In addition, many existing DCA schemes consider a simplified problem with only cochannel constraints [7–10, 23–25, 27]. Recently, DCA schemes for multihop wireless communications [28–32] have also been proposed.In addition to the fact that most DCA techniques use a heuristic approach with possibly suboptimal solutions, the main drawbacks of DCA are as follows.(i)
After a call request arrives, DCA requires some computation since allocation is done based on the “current state” of the network. In FCA the channel allocation is done offline, before the network starts operating, so when a call arrives at a cellk, any of the available channels assigned to the cell can be allocated to the new call immediately, without having to consider how the neighboring cells are being affected. Therefore, FCA is typically faster than DCA.(ii)
In DCA, it is possible for a “greedy” cell to use up too many channels at a given time, so that there are no channels available for the neighboring cells.HCA [5, 6, 17, 33, 34] combines the features of both FCA and DCA techniques to overcome the drawbacks of FCA and DCA. In HCA, the set of channels is divided into two subsets [6], the Fixed Channels set (or FC set: a set of channels permanently allocated to given cells) and the Dynamic Channels set (or DC set: a set of channels available to all cells). The ratio of the number of channels in each set is fixed a priori by the cellular network designer. For example, the representative ratios, FC : DC, for a set of 70 channels could be 35 : 35, 49 : 21, or 21 : 49 (If FC is empty, then the HCA problem reduces to the classical DCA problem). When a new call arrives in a cell, the system first tries to serve it from the set of fixed channels, FC. If no channel is available in the set of fixed channels FC, then the DCA scheme determines a suitable channel from the set of dynamic channels DC, satisfying the interference constraints and the traffic demands in cells. A channel is selected from the set DC, only if all channels in FC are busy. Therefore, HCA does not require a computation every single time (like DCA) and hence is faster than DCA on average (but not as fast as FCA). In addition, in HCA, a “greedy” cell can use up all the dynamic channels in DC, but it cannot use the fixed channels assigned to its neighboring cells. So, the neighboring cells are not as adversely affected as in the case of DCA.


## 3. ILP Formulation for Hybrid Channel Assignment

Channel assignment schemes help to increase the network's capacity by efficiently distributing the channels across the network. We assume that each base station in a cellular network has a computer that stores the current state of its cell. The state of the cell includes information about the channels, the mobile elements, and the ongoing calls in the cell. Each base station sends its state to other base stations through a wired network between their computers. Channel assignment is made by the computer of the concerned base station according to the channel usage information stored in the allocation matrix. Let,C be the total number of cells in the network and L be the total number of channels in the network. The allocation matrix A is the binary matrix of size C×L such that each element of A is defined as(1)ai,j={1ifchanneljisinuseincelli,0otherwise.The allocation matrix is updated every time a channel is allocated or released in the network, and each base station receives a copy of the allocation matrix. The total number of channels is divided into two sets: FC and DC. If FC is empty, then the problem reduces to the classical DCA problem.We solve HCA problem based on reuse distance concept. In this section, we propose two ILP formulations, ILP1 and ILP2, to solve the channel assignment problem, where ILP1 does not allow channel reassignment, but ILP2 allows it. Unlike most existing techniques, we consider all the three hard constraints, that is, cochannel, cosite, and adjacent channel constraints, as well as the soft constraints. Our HCA approach works as follows. When a call arrives in a cellk at time t, we first search for a channel in the FC set that can serve the call. If no such channel is available from FC, then we apply our ILP formulations on the DC set to obtain a best assignment of channels in cell k. The solution contains channels to be assigned to all ongoing calls in the cell k (ongoing calls maybe reassigned new channels to minimize blocking or dropping of calls, for ILP2) and the channel to be assigned to the new call.


### 3.1. Notation Used

In our ILP1 and ILP2 formulations, we will use the following symbols to represent input data:(1)
k: cell where a call arrives,(2)
dk: number of calls in cell k (traffic demand in cell k), including the new call.(3)
r0: reuse distance,(4)
r1: minimum distance between cells to avoid adjacent channel interferences,(5)
g: cosite interference channel interval,(6)
w: adjacent site interference channel interval, g≥w,(7)
C: number of cells in the network,(8)
L: total number of channels in the network (including both fixed and dynamic channels),(9)
Ld: number of dynamic channels in the network,(10)
B: set {1,2,…,Ld} of channel numbers for all dynamic channels,(11)
Bf: subset of B, containing the channels currently not in use in cell k,(12)
𝒦i: subsets of B containing the channels currently in use in cell i,1≤i≤C,(13)
W1, W2 and W3: positive constants,(14)
di,j: normalized distance between cell i and cell j, 1≤i,j≤C,(15)
res(i,j): a function defined as follows:
(2)res(i,j)={1ifcelliandcelljbelongtothesamereusescheme,0otherwise,(16)
ai,j: an element of a C×L allocation matrix A, where each element, ai,j, is defined as follows:
(3)ai,j={1ifchanneljisinuseincelli,0otherwise.We also define the following binary variables:(4)xl={1ifchannellisselectedforthenewcallincellk,∀l∈Bf,0otherwise,(5)ym={1ifchannelm∈BisselectedforanexistingcallornewcallincellK,0otherwise.


### 3.2. ILP Formulation without Channel Reassignment (ILP1)

We now present our first ILP formulation that allocates a free channel to a new call without any reassignment of existing channels. Using the notation given above, we formulateILP1 as follows.Objective Function
(6)Minimize-W1∑i=1,i≠kC∑l∈Bfai,l·xldi,k+W2∑i=1,i≠kC∑l∈Bfai,l·xl·(1-res(i,k)),
subject to (1)
constraint for one channel per call(7)∑l∈Bfxl=1,(2)
cochannel constraint(8)xl+ai,l≤1,∀l∈Bf,1≤i≤C,di,k<r0,i≠k,(3)
cosite constraint(9)xl+ak,q≤1,∀l∈Bf,∀q∈BBf,|l-q|<g,(4)
adjacent channel constraint(10)xl+ai,q≤1,∀l∈Bf,∀q∈𝒦i,1≤i≤C,i≠k,di,k<r1,|l-q|<w,l≠q.In our formulation, the traffic demand and the “hard” constraints are handled by (7)–(10). There may be multiple channels that satisfy these constraints, but, among them, the objective function specified in (6) selects one channel that best meets the requirements of the “soft” constraints. W1 and W2 are positive constants and determine the relative significance of the different terms. The first term expresses the packing condition. The objective value decreases if channel l is also in use in cell i which is free from cochannel interference with cell k. The decrease in the value depends upon the distance between the cells i and k. The second term expresses the resonance condition. The objective value decreases if channel l is also in use in cell i, and cells i and k belong to the same reuse scheme. Therefore, the objective function attempts to increase packing and assign the same channel to cells that belong to the same reuse scheme.We note that, if we were simply minimizing the objective function (without considering any of the constraints) the packing condition could lead to the same channel being assigned to two ongoing calls in adjacent cells, at the same time. However, such an assignment would violate the cochannel constraint (Constraint (8)), and hence would not be selected as a feasible solution, even though it gives a lower objective value.Constraint (7) ensures that each call is allocated exactly one channel from the pool of available dynamic channels that are currently not in use in cell k.Constraint (8) enforces the cochannel constraint by ensuring that a channel l∈Bf is not selected for a call in cell k if it is already in use in any neighboring cell i, assuming i and k are separated by a distance less than the reuse distance r0.Constraint (9) is the cosite constraint. It ensures that a channel l is selected in cell k only if it separated by at least the cosite interval, g, from any other channel q, currently in use in cell k.Constraint (10) states the adjacent channel constraint. It ensures that a channel l is selected in cell k only if it separated by at least the adjacent channel interval, w, from any other channel q, currently in use in a neighboring cell i, which is at a distance r1. Since the channel separation within the same cell should be at least as high as that between adjacent cells, we should always have g≥w and r0≥r1.We note that𝒦i is valid for all i,1≤i≤C (including cell k). However, the condition i≠k, given in adjacent channel constraint (Constraint (10)), indicates that this constraint is not applicable for cell k. Of course, there will be no problems if the constraint actually is satisfied in cell k, but it need not be enforced. Therefore, the qualifier i≠k given in Constraint (10) is used to select cells for which the adjacent channel constraint should (or should not) be applied.


### 3.3. ILP Formulation with Channel Reassignment (ILP2)

Channel reassignment, the process of transferring an ongoing call to a new channel without call interruption [4], can improve the quality of service in terms of lowering call blocking probability. Hence it is an important process in dynamic channel allocation. We now present our second ILP formulation that makes use of reassignment of existing channels. Using the notation given above, we formulate ILP2 as follows.Objective Function
(11)Minimize-W1∑i=1,i≠kC∑m∈Bai,m·ymdi,k+W2∑i=1,i≠kC∑m∈Bai,m·ym·(1-res(i,k))-W3∑m∈Bak,m·ym.
subject to (1)
constraint for one channel per call(12)∑m∈Bym=dk,(2)
cochannel constraint(13)ym+ai,m≤1,∀m∈B,1≤i≤C,i≠k,di,k<r0,(3)
cosite constraint(14)ym+yp≤1,∀m,p∈B,|m-p|<g,m≠p,(4)
adjacent channel constraint(15)ym+ai,p≤1,∀m,p∈B,|m-p|<w,1≤i≤C,di,k<r1,i≠k.Equation (11) is the objective function. The first two terms are similar to those in ILP1. The third term expresses the limiting rearrangement condition. This term results in a decrease in the objective value if the new assignment for the ongoing calls in the cell k is same as the previous allocation. As in ILP1, W1, W2, and W3 are positive constants and determine the significance of different terms.Constraint (12) ensures that each call is allocated exactly one channel among all dynamic channels.Constraint (13) enforces the cochannel constraint and is similar to constraint (8) except that here, we consider every dynamic channel m∈B.Constraint (14) is the cosite constraint. It ensures that two channels m∈B and p∈B are not selected in cell k if they do not have enough cosite interval distance, g.Constraint (15) is the adjacent channel constraint, similar to constraint (10). But here, we consider every dynamic channel m,p∈B.


## 3.1. Notation Used

In our ILP1 and ILP2 formulations, we will use the following symbols to represent input data:(1)
k: cell where a call arrives,(2)
dk: number of calls in cell k (traffic demand in cell k), including the new call.(3)
r0: reuse distance,(4)
r1: minimum distance between cells to avoid adjacent channel interferences,(5)
g: cosite interference channel interval,(6)
w: adjacent site interference channel interval, g≥w,(7)
C: number of cells in the network,(8)
L: total number of channels in the network (including both fixed and dynamic channels),(9)
Ld: number of dynamic channels in the network,(10)
B: set {1,2,…,Ld} of channel numbers for all dynamic channels,(11)
Bf: subset of B, containing the channels currently not in use in cell k,(12)
𝒦i: subsets of B containing the channels currently in use in cell i,1≤i≤C,(13)
W1, W2 and W3: positive constants,(14)
di,j: normalized distance between cell i and cell j, 1≤i,j≤C,(15)
res(i,j): a function defined as follows:
(2)res(i,j)={1ifcelliandcelljbelongtothesamereusescheme,0otherwise,(16)
ai,j: an element of a C×L allocation matrix A, where each element, ai,j, is defined as follows:
(3)ai,j={1ifchanneljisinuseincelli,0otherwise.We also define the following binary variables:(4)xl={1ifchannellisselectedforthenewcallincellk,∀l∈Bf,0otherwise,(5)ym={1ifchannelm∈BisselectedforanexistingcallornewcallincellK,0otherwise.


## 3.2. ILP Formulation without Channel Reassignment (ILP1)

We now present our first ILP formulation that allocates a free channel to a new call without any reassignment of existing channels. Using the notation given above, we formulateILP1 as follows.Objective Function
(6)Minimize-W1∑i=1,i≠kC∑l∈Bfai,l·xldi,k+W2∑i=1,i≠kC∑l∈Bfai,l·xl·(1-res(i,k)),
subject to (1)
constraint for one channel per call(7)∑l∈Bfxl=1,(2)
cochannel constraint(8)xl+ai,l≤1,∀l∈Bf,1≤i≤C,di,k<r0,i≠k,(3)
cosite constraint(9)xl+ak,q≤1,∀l∈Bf,∀q∈BBf,|l-q|<g,(4)
adjacent channel constraint(10)xl+ai,q≤1,∀l∈Bf,∀q∈𝒦i,1≤i≤C,i≠k,di,k<r1,|l-q|<w,l≠q.In our formulation, the traffic demand and the “hard” constraints are handled by (7)–(10). There may be multiple channels that satisfy these constraints, but, among them, the objective function specified in (6) selects one channel that best meets the requirements of the “soft” constraints. W1 and W2 are positive constants and determine the relative significance of the different terms. The first term expresses the packing condition. The objective value decreases if channel l is also in use in cell i which is free from cochannel interference with cell k. The decrease in the value depends upon the distance between the cells i and k. The second term expresses the resonance condition. The objective value decreases if channel l is also in use in cell i, and cells i and k belong to the same reuse scheme. Therefore, the objective function attempts to increase packing and assign the same channel to cells that belong to the same reuse scheme.We note that, if we were simply minimizing the objective function (without considering any of the constraints) the packing condition could lead to the same channel being assigned to two ongoing calls in adjacent cells, at the same time. However, such an assignment would violate the cochannel constraint (Constraint (8)), and hence would not be selected as a feasible solution, even though it gives a lower objective value.Constraint (7) ensures that each call is allocated exactly one channel from the pool of available dynamic channels that are currently not in use in cell k.Constraint (8) enforces the cochannel constraint by ensuring that a channel l∈Bf is not selected for a call in cell k if it is already in use in any neighboring cell i, assuming i and k are separated by a distance less than the reuse distance r0.Constraint (9) is the cosite constraint. It ensures that a channel l is selected in cell k only if it separated by at least the cosite interval, g, from any other channel q, currently in use in cell k.Constraint (10) states the adjacent channel constraint. It ensures that a channel l is selected in cell k only if it separated by at least the adjacent channel interval, w, from any other channel q, currently in use in a neighboring cell i, which is at a distance r1. Since the channel separation within the same cell should be at least as high as that between adjacent cells, we should always have g≥w and r0≥r1.We note that𝒦i is valid for all i,1≤i≤C (including cell k). However, the condition i≠k, given in adjacent channel constraint (Constraint (10)), indicates that this constraint is not applicable for cell k. Of course, there will be no problems if the constraint actually is satisfied in cell k, but it need not be enforced. Therefore, the qualifier i≠k given in Constraint (10) is used to select cells for which the adjacent channel constraint should (or should not) be applied.


## 3.3. ILP Formulation with Channel Reassignment (ILP2)

Channel reassignment, the process of transferring an ongoing call to a new channel without call interruption [4], can improve the quality of service in terms of lowering call blocking probability. Hence it is an important process in dynamic channel allocation. We now present our second ILP formulation that makes use of reassignment of existing channels. Using the notation given above, we formulate ILP2 as follows.Objective Function
(11)Minimize-W1∑i=1,i≠kC∑m∈Bai,m·ymdi,k+W2∑i=1,i≠kC∑m∈Bai,m·ym·(1-res(i,k))-W3∑m∈Bak,m·ym.
subject to (1)
constraint for one channel per call(12)∑m∈Bym=dk,(2)
cochannel constraint(13)ym+ai,m≤1,∀m∈B,1≤i≤C,i≠k,di,k<r0,(3)
cosite constraint(14)ym+yp≤1,∀m,p∈B,|m-p|<g,m≠p,(4)
adjacent channel constraint(15)ym+ai,p≤1,∀m,p∈B,|m-p|<w,1≤i≤C,di,k<r1,i≠k.Equation (11) is the objective function. The first two terms are similar to those in ILP1. The third term expresses the limiting rearrangement condition. This term results in a decrease in the objective value if the new assignment for the ongoing calls in the cell k is same as the previous allocation. As in ILP1, W1, W2, and W3 are positive constants and determine the significance of different terms.Constraint (12) ensures that each call is allocated exactly one channel among all dynamic channels.Constraint (13) enforces the cochannel constraint and is similar to constraint (8) except that here, we consider every dynamic channel m∈B.Constraint (14) is the cosite constraint. It ensures that two channels m∈B and p∈B are not selected in cell k if they do not have enough cosite interval distance, g.Constraint (15) is the adjacent channel constraint, similar to constraint (10). But here, we consider every dynamic channel m,p∈B.


## 4. Cellular Model Assumptions

Our ILP approach is applied to the mobile cellular model used in [2]. The basic characteristics of the model are briefly summarized as follows(1)
The topological model is a group of 49 hexagonal cells that form a parallelogram shape, as shown in the Figure4.(2)
The total number of channels for the network is 70, distributed in FC and DC, that is,|FC∪DC|=70. A channel serves one call at most. In FCA, the available fixed channels are distributed among the cells, while in DCA, all dynamic channels are put in a central pool. A channel is assigned to an incoming call by a central controller that monitors the whole cellular network.(3)
Incoming calls at each cell may be served by any of the available channels.(4)
The selection of a channel is subject to cochannel, cosite, and adjacent channel interference.(5)
The basic object of the network model is the link, which is a communication between a base station and a mobile terminal  through a channel.(6)
A new call at cellk is blocked if neither a fixed channel nor a dynamic channel is available to satisfy the electromagnetic interference constraints.(7)
Existing calls in a cell involved in a new call arrival may be reassigned new channels (ILP2 only).Figure 4
Cellular topological model.In our simulation, we assume the traffic model to follow the blocked-calls-cleared queuing discipline. An incoming call is served immediately if a channel is available, otherwise the new call is blocked and not queued. The most fundamental characteristics of this model include infinite number of users, finite number of channels for the network, no queue for new calls, call arrival following a Poisson process with mean arrival rate ofλ calls/hour. The call duration is a random variable with exponential distribution of the form:(16)f(x)={bexp-bxifx≥0,0otherwise,
where b is the mean duration time of calls [3]. Interarrival time follows a negative exponential distribution with mean b. The product of the mean arrival rate and the mean call duration gives the traffic load offered to the cellular network. We used nonuniform traffic distribution (where each cell may have a different call arrival rate) and considered the traffic pattern used in [3] shown in Figure 5. The entry in a cell represents the mean call arrival rate per hour, under normal load condition. In addition, we set the mean call duration to 180 seconds.Figure 5
Non uniform traffic distribution pattern.


## 5. Simulations and Discussions

In our simulations, similar to the works in [6], we used three representative ratios of fixed and dynamic channels, FC : DC, 21 : 49, 35 : 35, and 49 : 21. The initial load in each cell was set to 60% of the normal load and the results were obtained by increasing the traffic rates by 33% for all cells in each pattern, with respect to the initial rates on each cell. The performance of the ILP formulations is derived in terms of blocking probability for new incoming calls, which is defined as the ratio between the number of blocked calls and the total number of call arrivals in the system. In all of our experiments, set the reuse distance, r0=3. We also set W1=1.5,W2=2, and W3=1, which were determined by trial-and-error.To ascertain the values ofW1=1.5,W2=2, and W3=1, we investigated performances of different combinations. Figure 6 shows a comparison of blocking probability of ILP2 for three configurations, namely, {1,1,1}, {1.5,0.5,1}, and {1.5,2,1}, for ratio 35 : 35 with g=4 and w=3. By and large, Conf 3, which was taken for the rest of our simulations, works best, but the gap between their performances is inconspicuous. For both ILP1 and ILP2, the similar situation was sustained with other ratios and values of g and w.Figure 6
Comparison of performances of ILP2 with different combinations of values ofW1,  W2, and W3, for ratio 35 : 35 with g=4 and w=3.Table1 shows the blocking probabilities for channel allocation without any reassignment of existing calls (obtained using ILP1). As expected the blocking probability increases with increasing traffic load on the network, and with the required channel interval for cosite constraint (g) and adjacent channel constraint (w), but the network performs better as the number of dynamic channels increases. This was expected as the higher number of dynamic channels means that the scheme has more freedom and can choose channels from a larger set to assign to calls.Table 1
Blocking probabilities with no reassignment.
Percentage increase of traffic loadFC : DCgw0336610013316620021 : 49110.000.000.000.030.090.120.18220.000.050.110.180.260.300.36320.010.080.150.230.310.350.40330.060.160.240.320.400.430.4935 : 35110.000.000.020.090.160.210.27220.010.080.140.220.310.340.40320.020.100.180.260.340.390.44330.070.170.250.340.400.440.5049 : 21110.000.040.100.170.260.300.36220.040.120.200.280.360.400.45320.050.150.230.300.380.420.47330.080.200.270.350.420.460.52We have tested ILP2, where channel reassignment is allowed, with different combinations for the values ofg and w, each ranging from 1 to 4. Figure 7 shows the blocking probabilities when g=2 and w=2. Results with other values of g and w are similar. As before, blocking probability increases with traffic, and also with required channel intervals for cosite and adjacent channel constraints. However, as shown in the figure, the 21 : 49 ratio consistently gives the best performance, followed by 35 : 35 and 49 : 21.Figure 7
Performances with reassignment forg=2 and w=2.Figure8 shows how the blocking probabilities are affected by the requirement of different values of cosite and adjacent channel intervals, for the ratio of 21 : 49, under reassignment scheme. We see that even small changes in the values of g and w can have a significant effect on the blocking probability. The results for the 35 : 35 and 49 : 21 ratios followed a similar pattern, but the overall blocking probabilities were higher.Figure 8
Performances with reassignment for ratio 21 : 49.The effect of channel reassignment on blocking probability with the following representative ratios: 21 : 49, 35 : 35, and 49 : 21 was illustrated in Figures9, 10, and 11, respectively, under reassignment scheme. Our results indicate that although channel reassignment does reduce blocking probability, the amount of improvement seems to vary with traffic load and the values for g and w. We are conducting further experiments to determine the conditions under which channel reassignment is most beneficial.Figure 9
Performances of ILP1 versus ILP2 for ratio 21 : 49 with initial traffic load.Figure 10
Performances of ILP1 versus ILP2 for ratio 35 : 35 with initial traffic load.Figure 11
Performances of ILP1 versus ILP2 for ratio 49 : 21 with initial traffic load.Finally, we have compared our approach with the evolutionary strategy- (ES-) based HCA scheme proposed in [6], which considers cochannel constraints only. We note that, the approach in [6] not only provides criteria for selecting among multiple feasible solutions (similar to our approach), but also it has been shown to outperform another well-known approach for HCA [3]. However, like most existing approaches, both [6] and [3], do not consider CSC and ACC. So we had to use a restricted case of our formulation, for CCC only, to get a meaningful comparison. Furthermore, since we use ILP to generate the solutions, we can expect the performance advantage to be consistently greater than (or at least equal to) existing heuristics, for the same parameters.We simulate this by settingg=1 and w=1 in our formulation. Initial traffic in each cell, percentage increase of load, and other parameters including the values of W1 and W2 were set to the same values as in [6]. In Table 2, the rows ES and ILP1 indicate the blocking probabilities in [6] and our ILP1, respectively, under different traffic loads. As shown in the table, our results without channel reassignment are close to those in [6] with channel reassignment. A qualitative comparison of the results for ES [6], ILP1, and ILP2 is shown in Figure 12 for the ratio of 35 : 35. The results for the other ratios follow a similar pattern. We note that ILP1 (without any channel reassignment) has a slightly higher blocking probability compared to ES, which is expected, but ILP2 consistently outperforms ES.Table 2
Performances of ILP1 and the ES approach proposed in [6].
Percentage increase of traffic loadFC : DCScheme02040608010012021 : 49ES0.000.000.010.020.070.140.17ILP10.000.000.040.060.110.170.1935 : 35ES0.000.000.010.030.080.140.17ILP10.000.000.030.050.110.160.1949 : 21ES0.000.000.030.050.100.160.19ILP10.000.010.050.070.120.180.21Figure 12
Relative performances of ES [6], ILP1, and ILP2 for ratio 35 : 35 with initial traffic load.


## 6. Conclusions

In this paper, we have presented two new integer linear program formulations for hybrid channel assignment in wireless cellular networks. The first formulation does not allow channel reassignment for existing calls, while the second formulation is capable of performing channel reassignment. To the best of our knowledge, these are the first formulations for optimally solving the hybrid channel assignment problem that take into consideration the cosite and the adjacent channel constraints, in addition to the cochannel constraints. We also integrate soft constraints such as the packing condition, resonance condition and limiting channel reassignment to further optimize the objective function. The results indicate that even without channel reassignment, our approach (in ILP1) produces results comparable to some existing schemes that perform reassignment. Additional improvements are obtained if we allow channel reassignment (in ILP2) as well. We are currently investigating the relative importance of the soft constraints and effect of varying the constants in the objective function, on the overall performance of our formulations.



---

*Source: 524854-2010-09-21.xml*