2. Channel Allocation - A Survey

Channel allocation  is one of many ways to reduce interference in a cellular network.  Reduced interference leads to an increase in capacity and throughput of the system and hence good channel allocation can lead to more effective use of the spectrum.  Apart from reducing interference, channel allocation algorithms can also be used to adapt to traffic changes in a network, and together with reduced interference, the traffic that can be supported is higher.

The task of channel allocation in a cellular system is to allocate C available channels to B base stations, where each base station j has a specific traffic demand (e.g. calls) that requires d_j channels (e.g. one channel per call).  Hence, channel allocation is a permutation problem with a search space of

where D is the total traffic demand of all the B base stations (i.e. D = Sd_j).  If C = 15 and D = 50, there are about 2.94 ´ 10²⁴ possible solutions.  If a computer can evaluate a solution in 1 microsecond, it would take 93 billion years to evaluate all possible solutions.  However, not all the solutions are valid.  The same channel is allocated to two different base stations only if there is a sufficient distance between them such that the interference is tolerable.  In order to ensure the interference between the co-channel cells is tolerable, the channel allocation solutions must conform to a Compatibility Matrix  C.  The Compatibility Matrix gives the minimum required frequency (or channel) separation between two cells (or base stations) and it is defined as a B ´ B symmetric matrix where an element c_j,k in the matrix is the minimum frequency separation required between cell j and k. 

In this dissertation, a free channel  is defined as an unused channel that will not violate the compatibility matrix if it is used.  In a voice service, a call block  occurs when a new call is denied service if no free channel is available at the serving base station.  The number of radio transceivers required in a base station is dependent upon the expected traffic and the grade of service (i.e. probability of call block).  The traffic demand vector D = [d₁, d₂, … d_B] is the number of radio transceivers needed in each base station. 

Figure 2.1: An example of a cellular network with 3 cells and a possible channel allocation solution.

For an example of a channel allocation problem, consider a cellular network with 3 cells, each with one base station and let the set of base stations B = {b₁, b₂, b₃} as shown in Figure 2.1.  The cellular system requires a channel separation of at least 2 for calls within the same cell and 0 for calls in neighbouring cells.  The Compatibility Matrix C is therefore:

For this example, let the traffic demand (represented by a vector) be D = [2 1 1] and the set of channels (e.g. frequencies) be C = {c₁, c₂, c₃} where |C| = C.  Define S as the set of all solutions (i.e. all possible channel assignment) and the matrix s=[s_j,k] for 1£ j £ B, 1£ k £ C, where j and k are integers – is one of the solutions in S where an element s_j,k in s is defined as:

A possible solution is shown in Figure 2.1 and the corresponding matrix s is:

The Compatibility Matrix is formed on the basis that the interference  between two cells using the same frequency is tolerable.  In a voice oriented service, the quality of the received audio is important and it is considered to be acceptable for an AMPS system [2] if the SNR is at least 18 dB, which corresponds with a Signal to Interference Ratio (SIR) of at least 17 dB.  For a given propagation channel and the required SIR, the co-channel reuse ratio can be determined.  If the cells are laid out uniformly, the cluster size N_c can be found using (1.4) .

The task of allocating a set of C channels to a set of B base stations with traffic demand D constrained by a Compatibility Matrix C is known as a Nondeterministic Polynomial  time complete (NP-complete) problem.  NP-complete is a decision problem that can be solved using a nondeterministic Turing Machine in polynomial time [8].  A decision problem gives only a yes or a no answer.  In this case, the decision problem is whether there is a channel assignment to the given channel allocation problem that uses C or less channels.  For a given channel allocation problem, the optimum solution is one that uses the least number of channels C_MIN.  Finding the optimum  solution is a NP-hard problem.  The task of finding a solution (or an optimisation) increases exponentially with the size of the problem (e.g. the number of base stations).  The Channel Allocation Problem can be transformed into a graph colouring problem [19], which is also a NP-complete problem.  Since the Channel Allocation problem can be transformed to another known NP-complete problem, the Channel Allocation problem itself is NP-complete [8].

2.1         Channel Allocation Matrix

Channel Allocation algorithms can be divided into the following categories, namely Fixed Channel Allocation (FCA) , Dynamic Channel Allocation (DCA)  and Hybrid Channel Allocation (HCA) [18].  In FCA,  channels are allocated to a base station for its exclusive use and the allocation is usually performed prior to network operation.  Since the channels are static in FCA, it is difficult to adapt to changes in interference and traffic conditions.  In DCA,  any channel in the system can be assigned to any base station when it is needed (i.e. during network operation) contingent upon a set of conditions (e.g. Compatibility Matrix) being satisfied.  Unlike FCA, the base stations employing DCA do not own any particular channels and a channel is released when a call is completed.  Since the channels are assigned during network operation, DCA is able to adapt to interference and traffic changes.  In a circuit switched network, DCA performs better than FCA under light to moderate traffic but it performs worse than FCA under conditions of heavy traffic [18].  HCA  is a combination of FCA and DCA whereby a set of channels are statically assigned to a base station as in FCA while another set are placed in a central pool and are assigned in a DCA manner.  In this way, HCA is able to inherit the advantages of both DCA and FCA.

The classification into FCA and DCA does not reveal much about the underlying algorithms.  To allocate a channel to a base station, information regarding the system and the layout of the network is required.  Information can be a priori and/or current information gained during network operation.  The more information the scheme obtains combined with better use of the available information, will yield improved channel assignment decisions.  The channel allocation algorithms can be reclassified in a Channel Allocation Matrix, which is based on the strategy used to obtain the required information used during a channel assignment.  The Channel Allocation Matrix is introduced in [87] and is shown in Figure 2.2 (with citations to the methods that fall into each category).

Figure 2.2: Channel Allocation Matrix

The vertical axis is a measure of the degree of centralisation  required by the algorithm.  The degree of centralization is quantified by the number of base stations required to communicate with a central controller in order to obtain the required information to make a single channel allocation decision.  In a fully centralized system, all the base stations in the network needs to communicate with a central controller and thus each base station will have global knowledge of the entire network.  It also requires signalling between base stations and central controllers and this will introduce delay in assigning a channel.  The complexity of a fully centralized system increases non-linearly with the number of base stations and hence it may not be practical in a network with a large number of base stations, since the complexity may introduce long delays causing system instability.  For example, the channel usage of a neighbouring base station may change by the time this information reaches a base station that is assigning a channel.  In a voice service this delay may increase the number of dropped calls leading to user dissatisfaction while in a data service delay may reduce data throughput if frequent channel changes occur.  On the other hand, in a fully distributed  system the base station is able to make a channel allocation decision independently (i.e. without communication with a central controller or other base station).  The base station can obtain knowledge of the interference environment using measurement or may rely upon a priori information of the network configuration.  A fully distributed system may not have global or current knowledge of the network, but it permits fast and simple allocations to be made.  However, without global knowledge, the channel allocated may not give an optimum performance.

The horizontal axis represents the quantity of measurements performed by a base station and/or the subscriber’s equipment in order to make a channel allocation decision.  The measurements can be the interference power of a channel or an estimated SNR (or SIR) and in either case the aim is to evaluate the interference environment prior to allocating a channel.  Measurement may introduce delay decreasing the overall throughput of a network.  However, if it is performed too quickly, it may not give an accurate picture of the interference environment.

The Channel Allocation Matrix is divided into four quadrants specifically: