Abstract: The easiest means of increasing capacity of a cellular network without compromising quality of service is through frequency reuse. However, frequency reuse usually results in certain additive and system-generated cellular types of channel interference (co-channel and adjacent channel). In this study, Particle Swarm Optimization (PSO) algorithm was employed to efficiently manage frequency reuse through a neighbour allocation list in order to reduce co-channel and adjacent channel interference to the barest minimum on a live GSM network. Co-channel interference was completely eliminated while adjacent channel interference was reduced by 55% which has a positive impact on the system performance.

INTRODUCTION

In practice, good coverage area can easily be achieved by using a high powered Omni-directional antenna mounted on a tall tower. However, it will be impossible to reuse those same frequencies throughout the system without introducing interference. The fact that spectrum is a scarce resource and cannot cater for increase in demand for mobile services lead to frequency reuse concept to achieve high capacity with limited radio spectrum while at the same time covering very large areas (Calhoun, 1988). The concept of frequency reuse makes wireless system cellular.

Cellular system offers very high capacity in a limited spectrum allocation without any major technological changes. This comes from the fact that the same radio frequency can be reused in a different geographical area subject the re-use distance (Kendall and Mohammad, 2004).

Cellular design techniques are needed to provide more channels per unit coverage area. However, no matter how these designs try to eliminate interference, there is need to use optimization tool to fine-tune the BCCH frequency from time to time as more base stations are added to the network.

The common tools usually used for neighbour list optimization in cellular network in practice are Test Mobile System (TEMS) investigation, Grakiter, Naster, Planet EV and etceteras. Most of these tools require license and huge amount of money before an operator can use them. To reduce cost for both training and licensing, operators usually look for solutions that are plug and play like Grakiter that runs on MapInfo for BCCH retune.

This study investigates a tool that is not dependant on MapInfo which uses Particle Swarm Optimization (PSO) to minimize interference of GSM neighbors list. It is aimed at relieving the users from the burden of manual frequency planning.

MATERIALS AND METHODS

Frequency reuse: For efficient utilization of the radio spectrum, a frequency reuse scheme that is consistent with the objectives of increasing capacity and minimizing interference is required (Greenstein and Gitlin, 1993). Cellular radio system divide the area covered by the mobile radio into cells.

Each cell is covered by a Base Station (BS) and BSs in adjacent cells are assigned channel groups which contain completely different channels than neighboring cells. The system was introduced to resolve spectral congestion problems of mobile communication systems. The same group of channels may then be reused to cover different cells that are separated from one another by distances large enough to keep interference levels within tolerable limits. However, frequency-use usually result in adjacent and co channel interference and if they are not taken care of will cause low Carrier-to-Interference ratio (C/I) or Carrier-to-Adjacent channel ratio (C/A) and thereby compromising network quality (Oeting, 1983). Cells with identical channel frequencies are called co-channel cells. The co-channel cells have to be sufficiently separated to avoid interference. The distance between co-channel cells is achieved by creation of cluster of cells (Peter, 2003). The total number of channels N_tcl in a cellular radio system is given by:

(1)

Where:

(2)

Where i and j are non-negative integers. N_l can only take values of:

Once the cluster size is chosen, it determines the amount of frequency re-use within a certain coverage area. The parameters that determine frequency reuse are the reuse distance and the reuse factor. The normalized reuse distance, D between the centers of the nearest co-channel cells, the number of cells per cluster, N_l and the cell radius, R are related by Eq. 3:

(3)

N_l and D can be related as (Prasad, 1998):

(4)

The frequency reuse factor is the rate at which the same frequency can be used in the network. It is 1/K where K is the number of cells which cannot use the same frequencies for transmission. Common values for the frequency reuse factor are 1/3, 1/7 and 1/12.

Interference: One of the major limiting factors in the performance of cellular radio systems is interference, causing cross talk where the subscriber hears noise in the background due to an undesired transmission. It leads to blocked calls due to errors in the digital signaling. Interference is more severe in urban areas, due to the greater High Frequency (HF) noise floor and the large number of base stations and mobiles (Rapapport, 2002). Frequency reuse implies that in a given coverage area there are several cells that use the same set of frequencies.

These cells are called co-channel cells and the interference between signals from these cells is called co-channel interference. Unlike thermal noise which can be overcome by increasing the Signal-to-Noise Ratio (SNR), co-channel interference cannot be combated by simply increasing the carrier power of a transmitter. This is because an increase in carrier transmit power increases the interference to neighboring co-channel cells.

To reduce co-channel interference, co-channel cells must be physically separated by a minimum distance to provide sufficient isolation due to propagation (Rapapport, 2002).

Adjacent channel interference occurs when a radio tuned to and receiving a particular channel Ch suffers interference from an adjacent channel Ch-1 or Ch+1. Although, the radio is not actually tuned to the adjacent channel, it still offers a reduced response allowing the adjacent channel to interfere with the wanted channel to which the radio is tuned. The more selective the receiver is the less will be its response to adjacent channels. The carrier to adjacent channel (C/A) ratio expresses the strength of the wanted channel to that of the adjacent channel.

In GSM, the channel spacing is 200 KHz and so the interfering adjacent channel is 200 KHz, off tune. This sounds relatively large but the Gaussian Minimum Shift Keying (GMSK) modulation scheme employed in GSM produces a signal with a bandwidth in excess of this.

The Carrier-to-Interference (C/I) ratio expresses the relative strengths of the wanted and interfering signals. At lower C/I the Bit Error Rate (BER) becomes unacceptably high and the channel coding is unable to provide adequate error correction. The GSM recommendations specify a minimum working C/I of 9 dB, however, in practice a minimum C/I of 12 dB is usually used.

GSM channel coding includes error detection and correction, there is a limit to the interference it can deal with successfully. The GSM recommendations specify a working minimum C/A of -9 dB but in practice 0 dB or 3 dB is often used. The greater the distance between the source of the wanted signals and the source of the adjacent signal, the better will be the C/A.

Neighbor list allocation: Neighbor relationships affect frequency planning and frequency reuse because neighbor cells cannot use the same frequencies. Each cell in a wireless network relates with its neighbors to maintain good quality coverage to mobile users. As a Mobile Station (MS) user reaches the margins of coverage within a cell, stronger signals become from another cell. Therefore through a process called handover, the network re-routes the user’s call to one of the neighbor cells to maintain the connection. If cells have more neighbors than are required for reliable service, the result can be an inefficient use of the available spectrum.

The neighbor cells are defined in Broadcast Control Channel (BCCH) Allocation (BA) list. The list is used to inform the MS in the active mode to search the BCCH frequencies of adjacent cells. The list is sent through system information 5, 5bis and 5ter. They provide information of the GSM neighbouring cells. After the MS enters into the dedicated mode, it needs to regenerate the neighbor cell list according to the system information on Slow Associated Control Channel (SACCH).

It is recommended that 32 neighbor cells should be defined for a cell. In practice, the maximum neighbor cells does not exceed 15. During network optimization, all BCCH frequencies in the network can be put into the BA table so as to use the performance measuring function of the undefined neighboring cells in the traffic statistics to find out the adjacent missing cells. Figure 1 shows a transmitting cell and its neighbour cells on a live GSM network in Maiduguri city, Nigeria.

Problem formulation: For a given network with N_tcl cells and m radio channels per cell with a call demand whose elements are d_l and compatibility matrix C where C defines the co-channel, adjacent channel and co-site separation required by the cells.

Let Call_ik denotes Cell i with call k where 1≤i≤N_tcl, 1≤ k≤d_i. Then |f_ik - f_jm|$C_ij denotes the frequency separation for all i, j, k, m (I ≠ j, k ≠ m) where f_ik belongs to the set of radio channels. If i = j, it becomes co-site constraint. Therefore, the problem is defined as:

(5)

Particle Swarm Optimization (PSO): PSO was originally developed by Kennedy and Eberhart (1995). Like Genetic Algorithm (GA) that mimics the process of natural evolution, PSO was inspired by the social behavior and graceful motion of a swarm of birds migrating towards a common objective. The particles are like the flock of birds, the space they travel through, can be considered as the multi-dimensional problem space and the speed they travel can be considered as the velocity of the particles.

Fig. 1:	GSM network layout in Maiduguri city, Nigeria

The solution is evaluated by a fitness function that quantifies the quality of the solution. With each generation of movement, the direction and velocity will be altered until the particles finally converge at a solution (Cui et al., 2005). The Velocities and positions are define in PSO as:

(6)

(7)

where, i and i + 1 are the iteration numbers, ω, C₁ and C₂ are the PSO parameters to be initialized while r₁ and r₂ stand for a uniformly distributed random number in the interval (0, 1). Also, is the pbest for the nth particle and is the gbest represents a position in the search space which changes based on updates on v_nⁱ⁺¹ which represents the velocity (Rania et al., 2005). Velocities and positions are updated using the PSO in Eq. 7 and 8, respectively.

Particle swarm optimization algorithm: The steps involved in the implementation of the PSO/algorithm can be summarized as:

The pbest is updated by comparing the current pbest of the particle with that of its previous pbest and retaining the better of the two values while the best of all the pbest in any generation is selected as the gbest.

Fitness measure: Ideally, the highest fitness possible in a network corresponds to the channel assignment configuration in a network where interference is completely absent. The amount of interference on a channel assignment configuration can be measured by the frequency separation of the assigned channel to its co-channels and adjacent channels and penalty is assigned for cases where interference is present. From Eq. 6, when |f_ik - f_jm| ≥ C_ij for any channel in a cell, the penalty function F (x) will be defined by:

(8)

When co-channel or adjacent channel interference are present that is if:

(9)

or

(10)

For each violation F (x) = 1, the penalties are then summed for each assignment configuration. The

assignment with the highest fitness is that with the minimum sum of penalties.

Particle swarm optimization encoding details: Each particle P represents an entire network configuration having N_tcl number of cells, each cell having fik radio channel. The fitness of each network will be based on the fitness function F (x). The position will be the radio channels assigned to the cells of the network based on the traffic demand di. The velocity will be the numerical values representing the numbers to be added to the present radio channel.

RESULTS AND DISCUSSION

Based on Fig. 1, Maiduguri city has 28 sites; each site has 3 cells and each cell have some neighbours. A typical transmitting cell and its neighbours as defined in the neighbour list are also shown in Fig. 1.

Initial plan shows that there were 8 cells and 56 cells that suffer from co-channel and adjacent channel interference, respectively. The initial cells had co-channel and adjacent channel interference of 1 and 9%, respectively as shown in Fig. 2. After 200 iterations using the PSO as shown in Fig. 3, the co-channel and adjacent channel interference level reduced to 0 and 4% respectively as shown in Fig. 2.

Fig. 2:	Percentage of interference for initial/optimized plan

Fig. 3:	Interference count and iterations for initial/ optimized plan

Therefore, co-channel interference was completely eliminated while adjacent channel interference was reduced by 55% which impacts positively on service availability, network capacity, call set-up success rate, call retention rate and handover success rate.

CONCLUSION

In this study, we have shown that PSO can help wireless operators to eliminate Co-Channel interference completely and reduce adjacent channel interference. This research can be applied in wireless networks where a neighbour allocation list or compatibility matrix is used to manage network resources.

Such networks exist in mobile communication and wireless local area networks. It is the view that if this research is used by operators it will reduce operational cost and result in reduced service charge to customers as well as increased customer satisfaction.