1. Introduction

Technological advances in the area of wireless communication (or cellular system) along with rapid development of handling wireless devices, have facilitated the rapid growth of mobile computing. In the past two decades telecommunication area has changed very significantly. These changes have given the telecommunications industry the capability to provide ubiquitous information access along with mobile multimedia services to its users.

In wireless systems, there are four traffic classes defined by 3GPP[1] conversational class, streaming class, interactive class, and background class. This classification is mainly based on delay sensitivity of the traffic. The conversational class is very delay-sensitive, while the background class is the most delay-insensitive class. Initially, using wireless network for all different classes ( real-time applications and nonreal-time applications) of communications was considered far from reality. Now with the technological advances, it seems to be more realistic to provide such a type of wireless network. Many mobile applications are now shifted to multimedia platforms or available on multimedia platforms, in order to present information more effectively and clearly. These applications require that the mobile network should provide seamless end-to-end multimedia services to fulfil the need of its users.

Bandwidth in wireless mobile systems is a very scarce resource. With the increasing population of multimedia application inclined mobile users, more channels are required to offer the services. As users continues to grow at a very fast rate, that too with the large bandwidth requirements of multimedia applications. There is necessity to use bandwidth efficiently to meet the bandwidth requirement. Efficient utilization of bandwidth is also linked to cost- effectiveness of service. The better bandwidth utilization in mobile communication systems has been a major area of research in telecommunication in the recent past.

In this paper we provide an overview of different channel allocation algorithms and compare terms of QoS parameters such as performance, flexibility, and complexity etc. We first give an overview of the channel assignment problem in a cellular environment and discuss the general idea behind different channel allocation schemes. Then we progress towards discussion of different channel allocation schemes within each category. We have used the term scheme, method and algorithm interchangeably, in this paper. In section 2 we state basic concepts of cellular systems including architecture, working principle, technologies and terminologies. In section 3, we have explained channel allocation problem, and concept of handoff in cellular systems. In section 4, different categories of channel allocation schemes and their interesting features are reviewed. In section 5, we have reviewed working and interesting features of some of channel allocation algorithms based on centralized control and distributed control on the channels. In section 6, we have highlighted the features of some failure tolerant channel allocation schemes. In section 7, we have highlighted important features of some channel allocation algorithms which are developed using concept of mutual exclusion. Section 8, describes use of genetic algorithm for channel allocation. In section 9, we highlight features of some channel allocation algorithms developed for hierarchical cellular networks. In section 10, we have reviewed some channel allocation algorithms developed for cellular networks with mobile base stations. In section 11 we, reviews some algorithms developed to allocate channels for multiclass of applications in cellular systems. In section 12, we have reviewed some of the handoff management schemes developed for cellular systems. In section 13 we, reviews some algorithms developed to allocate channels using power control mechanisms. Finally, in section 14, we conclude with the remarks on the present work in this area. We also comment on future direction of the research in the area of channel allocation in cellular system.

2. Basic Concepts Cellular Systems: Architecture, Working Principle, Technologies and Terminologies

In this section we summaries concepts of basic functioning of cellular systems, with basic descriptions of channel reuse principles.

2.1. Architecture

In a typical cellular system whole geographical area is divided into number of cells, which shape of these cells as hexagonal. Mobile users in each cell are serviced by a base station (BS) located at the center of the cell and the BSs are interconnected via a wired network [2, 3]. BSs are also known as Mobile Service Station (MSS). In this paper, terms, mobile user, mobile host (MH), mobile unit (MU) and user are used interchangeably. The wired network connecting BSs is known as backbone network. In backbone network several base stations are connected to a mobile switching center (MSC). The MCS acts as a gateway from the cellular network to the backbone wired networks, the Internet, and the PSTN[4]. A generic architecture of cellular network is shown in figure 1.

Figure 1. Architecture of a cellular network

The number of base stations required to service a given geographical area, is an important factor for a cellular system. A reduction in the number of base stations, reduces the cost of service, provided available bandwidth is effectively and efficiently reused. In wireless mobile system radio bandwidth is divided in to channels. Only a finite set of channels are available for one entire network. A channel or group of channels can be used to support a call or communication session. These channels are represented in terms of frequency channels, time slots, or modulation code. These channels are used for communication in a certain cell, and further, system allows the same channel to be reused in a number of different cells provided these cells are at least the minimum reusable distance away from the current cell. In figure 2, a reuse plan of seven channels namely A, B, C, D, E, F and G in the system is shown.

Figure 2. Concept of Channel Reuse in a 7-Cell Cluster

Cells that can use same channel are called co-channel cells. Always the co-channel cells in a system should be minimum reusable distance (D_min ) away[5]. In other words D_min be the minimum reuse distance which is usually defined as the distance between the centers of cells that are co-channel interference limited.

A channel can be used simultaneously by a number of different cells only if the distance between each pair of cells using the channel is greater than or equal to the minimum reuse distance. The minimum reuse distance depends both on the radius R of the cell and the minimum SIR ( signal to interference ratio). SIR is also known as CIR (carrier-to-interference ratio). One of the most basic level interference is caused by the proximity of other cells sharing the same channels. One of the objectives of channel assignment algorithms is to allocate channels in such a way that minimise the CIR.

2.2. Channel Interference

There are two major interference problems in wireless systems are adjacent-channel interference (ACI) and co-channel interference (CCI).

Adjacent Channel Interference (ACI)

Adjacent Channel Interference (ACI) is the interference due to signals which are adjacent in frequency to the desired allocated signal to a call. Adjacent-channel interference is basically due to equipment limitations such as frequency instability, receiver bandwidth, and imperfect filtering, which allow nearby frequencies to leak in to the passband[6] and also results from imperfect receiver filters which may allow nearby frequency leakage[7, 8]. To minimize ACI, channels need to be allocated in such a way that the frequency separation between channels in a given cell is maximized. Although cellular equipment are designed for maximum interference performance of the system, a combination of factors, such as cellular architecture and random signal fluctuation, generally cause deterioration of the received signal, primarily due to interference of adjacent channels. To minimize ACI, proper filtering and channel assignments is essential. The DCA scheme proposed in[9], is based on channel swapping and channel allocation cost function, in which those channels are assigned to a call which provides the required channel separation to avoid ACI, and channel swapping is done if a channel with ACI constraint is not available. Because of the QoS requirements CCI, which is discussed below, has received more attention from researchers. In general it is assumed that when channels are defined they are ACI free by using appropriate filtering mechanisms.

Co-channel interference (CCI)

Co-channel interference (CCI) is a complication that exists in mobile systems using cellular architecture[10, 11].The carrier-to-interference ratio (CIR) is the ratio of the power in the carrier to the power of the interference signal. The carrier-to-interference ratio is normally expressed in dB. C/I is the minimum ratios of the desired signal levels (C) to the interfering signal levels( I) that are necessary to protect radio systems against interference from other radio systems. The co-channel interference ratio (CIR) can be given by[12] :

(1)

where, I_k is co-channel interference of co-channel interfering cell i and M is the maximum number of co-channel interfering cells. In a wireless mobile cellular system, co-channel interference causes major limitation on overall system capacity [8,11,13]. A channel can be used simultaneously by a number of different cells only if the distance between each pair of cells using the channel is greater than or equal to the minimum reuse distance D_min. Thus, each cell c is associated with an interference neighborhood IN_c which is the set of cells whose distance to c is smaller than D_min , i.e. IN_c = { c’: dist{c; c’} < D_min}. If a , channel is being used by cell c, then it cannot be used by any cell in IN_c. Conversely, a channel is available for use by cell c if it is currently not being used by any cell in IN_c. If R is the radius of a cell, then the co-channel reduction factor Q is presented as the ratio of D_min to R[14]:

(2)

If Q is high, then co-channel interference decreases. Also, Q may increase in the cases when R is small i.e. cell size is small and D is large i.e. signal strength is high.

Figure 3. Co-channel cells in a Cellular System

Minimum reusable distance D_min also can be determined in terms of the cluster size K( the number of cells in cluster)[12, 15].

(3)

In general, the number of cells K per cluster is given by:

(4)

where, i represents the number of cells to be traversed along direction i, starting from centre of a cell, and j represents the number of cells in a direction 60⁰ to the direction of i.

The shaded hexagons in figure 3 represent co-channel cells. These cells may use the same set of channels without interference. In figure 3, the distance between centers of the nearest co-channel cells is denoted with D, and the radius of a cell with R. In a symmetric hexagonal cell system, each cell has exactly 6 co-channel cells at distance D. Also there are 6 co-channel cells at distance based on different signal strengths of the channels as shown in figure 3[15].

3. Channel Allocation

The bandwidth available to the cellular system is limited. Generally the total available bandwidth is divided permanently into a number of channels and these channels are allocated to cells without violating the minimum reusable distance constraint. Cells use the allocated channels for call handling. For better utilization of available channels, cellular communication system exploit the advantage of channel reuse, by using same channel simultaneously in different cells, where the cells are separated physically at least to minimum reusable distance, so that calls do not interfere with one another. In channel allocation, multiplexing, one of the basic concepts of data communication is used. Multiplexing uses the idea of allowing several transmitters to send information simultaneously over a single communication channel. Concept of multiplexing, allows many users to share a bandwidth of frequencies. With the use of multiplexing, a given radio frequency signals/bandwidth available in cellular system, can be divided into a set of disjoint or non-interfering radio channels.

There are many techniques of multiplexing such as, frequency division (FD), time division (TD), or code division (CD). In FD, the frequency spectrum is divided into disjoint frequency bands with each channel being assigned to a unique frequency range, whereas in TD separate channels are achieved by dividing the signal into different time slots. In CD, the channel separation is achieved by using special coding schemes. Further, more complex techniques can be designed based on combination of TD, FD and CD techniques. For example, with combination of TD and FD, a hybrid technique of multiplexing have been developed which will divide each frequency band of an FD scheme into time slots. No matter which multiple access technology (FDMA, TDMA, or CDMA) is used, the system capacity in terms of effective or equivalent bandwidth [16, 17] can be measured. In Orthogonal Frequency Division Multiple Access (OFDMA) also the system capacity can be measured in terms of effective or equivalent channels. In OFDMA systems the available spectrum is divided into orthogonal subcarriers, which are then grouped into subchannels. OFDMA works as a multi-access technique by allocating different users to different groups of orthogonal subchannels[17, 18].

The Orthogonal Frequency Division Multiple Access (OFDMA), is being widely recognized as a feasible technology for the future mobile communication systems due to its ability to allocate power, rate and frequency optimally among subcarriers[19]. In OFDMA networks, co-channel interference occurs mostly in the cases of the multiple users transmitting simultaneously on overlapping frequency bands. Hence in the downlink of an OFDMA system, such interference is limited to inter-cell interference, as users within a given cell use sub-carriers which are orthogonal to each other. The SIR is a metric that is commonly used to characterise the quality of a link. In OFDMA network, also the CCI is a great challenge, considering the aspiration of full frequency-reuse. One major advantage of OFDMA is that, any two MSs belonging to two different BSs can be assigned to the same subcarrier, if the SINR (signal to noise ratio) corresponding to that subcarrier is higher than the given threshold signal-to-interference-plus-noise ratio SINR_min [20].

A Simple Channel Allocation Scenario

For example let us consider a situation in which three cells A, B, and C share two channels, viz., channel1 and channel2. These three cells are in line and no two adjacent cells can use the same channel because of the channel reuse constraint. In a scenario of channel allocation, as shown in figure 4 (a) where, the cell A is serving a call on channel1 and cell C is serving another call on channel2. If at the same time, a new call arrives in the cell B, then it can not be handled by cell B because of non-availability of channel, as channel-1 and channel-2 are already in use by cell A and cell C respectively. Hence cell B can not use any of these two channels, because of the reusable distance constraint. In this situation any new call arriving in the middle cell B must be blocked. This example provides some basic idea about the nature of the cannel allocation problem.

Figure 4(a). Channel Allocation Scenario-1

Figure 4(b). Channel Allocation Scenario-2

There would be a better scenario as shown figure 4(b) where both cell A and cell C use channel1, satisfying channel reuse distance constrains for their calls. Then a new call in cell B could be assigned channel2 while taking care of the channel reuse distance constraint. Such a solution of channel allocation is an attempt of possible optimization of typical of the channel assignment problem. In a real world cellular system with more realistic cases which have many-- cells, channels, and calls, along with the uncertainty about when and where a call will be arriving to or existing from a cell, calls will cross from one cell to another cell etc., the problem of allocating channels become complex. With added QoS parameters such as minimise call blocking probability and call dropping probability, channel allocation problem really becomes very complex, especially in cases of intense and dynamic traffic loads. One way of measuring traffic intensity in cellular system uses the erlang as parameter. One erlang is equivalent to number of calls made in one hour multiplied by the duration of these calls in hours. In real life scenario, each call may have a different duration or a different call holding time. In such cases, for traffic intensity calculation, the average call holding time is taken into consideration[12, 21].

Figure 5. Intercell Handoff

3.1. Handoff Calls

A connection request to a cell may be one of the two categories, it may be from a user in the current cell who wants to start the service, or it may be from a user who is currently connected to BS of a neighboring cell and have just got into the area of current cell. Also, it may be the case, where a currently active user in a cell may be replaced to another channel and cell may get back the channel currently in use, for allocating it to some other user in the cell or for lending it to some other cell. On the basis of request type of the connection, a connection may be either a new call or a handoff call. In a handoff process, the radio channel currently used by a connection is replaced by some other channel. In handoff process, if the new radio channel is allocated from the same base station then the handoff is called intracell handoff[22]. Doing so, improves co-channel reuse. In intracell handoff a channel currently used by some other call is assigned to a new call by reassigning new channels to calls already in progress.

If in a handoff process, current allocated channel to a connection is replaced by some channel from a new base station then that handoff is called intercell handoff. A situation of call dropping arises when the new base station will deny channel to a connection after it is in progress. A connection may be dropped during a intercell handoff, when the user moves from its current cell in which it is getting sufficient channels for communication, into a cell where currently, sufficient channels are not available to handle this call. During a intercell handoff, the user releases the currently used channel and is assigned a new channel by the destination BS.

Intracell handoff is a requirement for dynamic channel allocation (DCA) to adapt effectively to interference and variations in traffic. If intracell handoff is not permitted, DCA schemes follow inefficient reuse patterns, dictated by the specific pattern of call arrivals, call completion and intercell handoff. When intracell handoffs are permitted, complete reassignment of calls to channels can be performed system-wide, as often as necessary, so that the optimal assignment is achieved. This strategy is called maximum packing (MP) strategy[23]. To achieve better channel reuse, intracell handoff (or a channel switch) may be useful technique[12, 23, 24, 25]. Seamless transfer of user’s service from existing operator to a new operator bearing dissimilar radio access technology is called vertical handoff (VHO). In VHO[26, 27] mechanism, user maintains connection when switched from one radio access network (RAN) technology to another RAN technology.

Considering the user, call blocking and call dropping are the two most important parameters of QoS of mobile systems. The call blocking (CB) occurs in cellular system if a cell receives request for a new connection, and does not accept it due to non-availability of channel. If an existing connection is dropped in between due to traffic congestion or due to incapability of the cell to provide sufficient bandwidth to continue the connection, then call drooping (CD) occurs. Generally, call dropping occurs due to denying some channels to an existing connection. The call dropping probability (CDP) and the call blocking probability (CBP) in any system should be minimized for better QoS[ 7]. In mobile communication system, channel allocation problem is seen as optimization problem[4, 23, 28-31]. There have been attempts to provide channel allocation algorithms to improve QoS[4, 28, 29-31]. If QoS is seen from the usre’s point of view, call dropping will be unacceptable. However, in some cases call blocking may be tolerable up to some extent[32-35]. Minimizing the CDP and CBP is one of the main goals in terms of better QoS, in cellular networks. Most of the admission control and channel allocation schemes proposed in the literature have tried to minimize the CBP and/or CDP, to maintain QoS of wireless cellular networks[31, 37].

4. Different Channel Allocation Schemes

Many schemes for channel allocation[4, 24, 28, 37-38] have been proposed in the literature in last three decades. These channel allocation schemes can be divided into a number of different categories on the basis of comparison of strategies, they have used for channel allocation. The simplest strategy is to permanently allocate channels to cells in such a way that the channel reuse constraint can never be violated even if all channels of all cells are used simultaneously. This is called a fixed channel assignment (FCA) scheme. One advantage of FCA schemes is its simplicity, but they are not adaptive to changing traffic conditions. One major disadvantage of FCA schemes is that they block the calls if the number of calls exceeds the number of channels assigned to a cell, even if, the neighboring base stations may not be very busy and may have many free channels[39-41]. In FCA, initial channel assignment is important because each cell in the system is allocated specific channels and can not be changed during system operation. To gain more efficiency and effectiveness, FCA systems normally allocate channels in a manner that maximizes frequency reuse, under minimum reuse distance constraint. The common fundamental idea in all fixed assignment strategies is the permanent assignment of a set of channels to each cell. In the basic FCA strategy, a new call or a handoff call can only be handled if the free channels are available in the cell; otherwise, the call should be blocked. In FCA systems, the role of MSC is restricted and is to inform the new BS about handoff requests, and to receive a confirmation or rejection message from the new BS, about the handoff. FCA is used because of its simplicity. In practice, in FCA also, the number of channels allocated to a cell can be changed during operation, but this re-allocation can only happen in a medium to long term basis, unlike the allocations done in DCA.

To overcome the limitations of FCA, another strategy called dynamic channel allocation (DCA)[42-48], in which channels are dynamically assigned to the cells are used. Contrasts to FCA, in DCA available channels are reserved in a global pool and from there channels are allocated to the cells on demand as per their need. In DCA, any BS does not own any particular channels and a channel is released by the BS to the central pool when a call is completed. In the situations when call density in few cells are higher compare to other cells in the system, then these high call density cells can be assigned more channels than other low call density cells. This helps in minimizing the call blocking rate in these high call density cells. In DCA, channels are allocated in real-time based on the actual cell conditions by doing real-time computation to make decision about allocation of channels. Due to its real-time computational requirements DCA are of higher complexity and are less efficient than FCA. The real-time channel allocation makes DCA, adaptive to interference and traffic changes. In general, DCA strategies assume that all channels can be used by any cell or base station (BS) and there is no fixed relationship between the communication channels and cells[42-49]. The basic concept of DCA is that each base station attempt to maintain channel uses pattern similar to FCA, as long as this is compatible with the existing traffic pattern. In general requirements of a good DCA scheme is to take care of two aspects-- first is to maximize channel uses by maximizing the reuse of various channels in the system; second during dynamic system implementation minimum information exchange among BSs should be less. Hence, the DCA strategy should maintain, as far as possible, the maximum packing of channels[43-44].

In DCA schemes, contrary to FCA, the number of channels in each cell keeps on adaptively changing, to accommodate traffic fluctuations. In DCA schemes, during heavy traffic in a given cell, more channels are made available for that cell and during light traffic periods in a cell allocated channels are reduced. Those released channels are used by other cells which require more channels. This channel readjustment process requires a lot of communication and information exchange among cells. Therefore, a DCA strategy should be implemented in such a way that it requires the minimum information exchange among base stations in order to reduce the signaling overhead and complexity. In an ideal DCA, at any time, a call request should be satisfied, provided that the sufficient channels are available in the system in any cell. Such an ideal DCA is impractical because, in general, it would require a real-time reconfiguration of the carrier-to-cell assignment in the entire cellular network, and hence, turning up into a considerably large signaling overhead. In a pure DCA[49] scheme, it is assumed that the whole set of channels belongs to a common pool and the allocations are performed on a call-by-call basis according to certain frequency reuse criteria, frequency usage and future call blocking probability. The pure DCA under light loads provides better service quality than FCA in terms of blocking probability and handoff failure[42], because of better channel management and utilization.

Another scheme of channel allocation is called hybrid channel allocation (HCA), is a combination of FCA and DCA schemes. In HCA, advantages of both FCA and DCA are exploited. HCA scheme allocates some channels statically and other channels dynamically. In HCA[12, 50-51] schemes, total channels of mobile cellular system are partitioned into fixed and dynamic sets. The channels included in the fixed set are assigned to each cell through using the FCA schemes. Whereas, the dynamic set of channels is shared by the base stations. The channel allocation procedure from the dynamic set can use any of the DCA strategies. When a mobile host needs a channel for its call, and all the channels in the fixed set are busy, then a request from the dynamic set is made. In HCA, the ratio of the number of fixed and dynamic channels plays an important role in deciding QoS of the system[51].

Channel allocation schemes can be implemented in different ways. While allocating a channel to a base station, information regarding the system and network condition is required. This information can be a priori pattern of users, current information about the status of network operations, and status of available channels. Any scheme which gather more information and combine it with better use of the available information may give improved channel assignment decisions. The fully DCA approach do not require channel transfer mechanism while the FCA and HCA, always transfer channels from neighbors under high system load. Table 1 presents a summary of DCA, HCA and FCA schemes, characteristic for different working and QoS parameters.

Table 1. Comparison among FCA, DCA and HCA schemes Evaluation Parameter FCA DCA HCA Channel Allocation Do not change during processing of calls Change dynamically Change dynamically Minimum Reusable Distance Follow Follow Follow Complexity Less More Moderate Uniform Traffic Distribution Good Not good Not good Non Uniform Traffic Distribution Not good Good Good Implementation Cost Low High Moderate Role of MSC Less More Moderate Channel Utilization Less More More Flexibility Less More Moderate Awareness of Network Full Partial Partial Efficiency More Less Less

4.1. Some Fixed Channel Allocation Schemes

The simplest way to implement FCA is to allocate the same number of channels to each cell so that the channels are allocated uniformly among the cells in system. This strategy is good in situations when system is having uniform load distribution, as it decreases the overall average blocking probability. However, the problem with FCA systems occurs, whenever the traffic load in all the base stations is non-uniform. Generally, a real life network has non-uniform traffic clusters. For example, in a cellular system, there may be some clusters of heavy load such as, a sports complex during a tournament, busy shopping malls, market, business office area and highway etc. Also there may be some clusters like rural area, locally connected roads etc., of light traffic load. In a FCA scenario where two adjacent cells are allocated N channels each, there can be situations of non-uniform network traffic load in which one cell has a need for N+i channels while, the adjacent cell only requires N-j channels (for any positive integers i and j). In such scenario, some users in the first cell would be blocked from making calls due to unavailability of channels in the cell, while j channels in the second cell will be unutilized. In this type of scenario of non-uniform traffic, the available channels are not being used efficiently. To overcome such problem, various strategies like, Simple Borrowing (SB), Borrowing with Ordering (BO)[52] are used.

Simple Borrowing Scheme: In Simple Borrowing (SB), channels are borrowed from the adjacent cells and are returned to that cell after it becomes free. When a new call or handoff call reaches to a cell and if currently all the permanent channels allocated to the cell are busy then, channels are borrowed from adjacent cell if the channels are free and minimum reusable distance constraint is met. Once a channel is borrowed, other cells are stopped from using this channel till it become free. Stopping cells from using a channel is known as channel locking. In SB algorithms, a database is maintained for the record of channels as per their status—either currently in use, borrowed or free. MSC plays a role of supervisor for the channel borrowing activities and run the channel borrowing procedure, so that channels are borrowed from the cell having relatively more free channels. Channel borrowing is done under minimum reusable distance constraint. Channel borrowing makes FCA more flexible and SB algorithms minimize the call blocking probability and the call dropping probability[4, 25]. With the increase of MHs, in borrowing-based bandwidth allocation schemes[4, 25, 53], the QoS guarantees may be reduced for ongoing connections, due to increase of overheads in the base stations of the cellular system.

A FCA scheme for high altitude platform (HAP) system is proposed in[41]. This FCA is based on assumption that, as the size of the cells on the ground increases, the overlapped area (area served by more than one cell) also increases and the users in these overlap areas have the choice to select a channel from any of the overlapping cells. Under these assumptions, three FCA schemes of channel allocation --Standard FCA Scheme (FCA), Area Based FCA Scheme (ABFCA), and Uniform FCA Scheme (UFCA) are presented in[41]. In Standard FCA Scheme (FCA), no overlap is considered and hence choice is not available for selection on which cell channel to be allocated. In Area Based FCA Scheme (ABFCA), each cell has a fixed number of channels similar to FCA scheme but cell radius (R) of each cell has been increased to 1.25R so that there are overlapping areas in the system. Any user, positioned within a radius R of the centre of any cell can connect to this cell. Also, the users first search for the number of cells which they can connect to (up to 3 cells) and then, they picks up a channel from which ever cell has the most available channels. The Uniform FCA Scheme (UFCA) is based on the ABFCA scheme. In this scheme also, each cell has a fixed number of channels similar to FCA. In UFCA, a proportion of the channels are not allocated to the overlapping areas, and these channels, remains available for the users in the non-overlapping area of the cell. Advantage of these techniques is that, the number of channels being allocated into certain areas can be controlled without partitioning the group of channels of a cell into smaller groups. These techniques of channel allocation are useful for non-uniform traffic distribution. In [41], where the users have the option to choose from more than one cell, the blocking levels are much lower than the case with no overlap.As simulation result shows[41], in UFCA scheme total cell blocking has been significantly reduced compare to FCA scheme.

In [12] an FCA scheme has been proposed in which an efficient distributed resource planning mechanism is used. In this scheme, each cell can concurrently search for a set of channels according to its traffic load and can use these channels to serve the incoming calls. This scheme uses the concept of primary and secondary channels, where in a cell C, the set of channels Ch is divided into a set of primary channels Pc and a set of secondary channels Sc, with a condition that Sc = Ch-Pc. This scheme ensures that when cell allocates a channel to an incoming call, the same channel is not concurrently allocated to other calls in its interfering cells. A cell uses its secondary channels only when no other primary channels are available in the cell. With the help of reward function for appropriate assignment of channel set to each cell, this scheme is adaptive to variations in traffic conditions. As simulation result shows[12], by using the mechanism of[ 12], the traffic-carrying capacity of fixed assignment (FA), simple borrowing (SB), borrowing with a channel-ordering (BCO) and borrowing with directional channel locking (BDCL) schemes[54] are significantly improved for the similar simulation parameters. This happens probably because mechanism in[12] allocates primary channels in accordance of traffic load.

Localized Channel Sharing (LCS) Scheme: The LCS scheme proposed in[24] is a channel sharing based on FCA, in which channels between adjacent cells are shared with localized channel management within adjacent cells. This scheme uses the concept of meta-cells. A meta- cell is defined as a fixed collection of neighboring cells (typically a pair of two adjacent cells). Each meta-cell is designated by a pair (X, Y ), where X and Y are individual cells called the component cells of that meta-cell. In this scheme, channels to meta-cells are allocated in such a way that a maximum number of channels can be assigned to each meta-cell while any two meta-cells assigned to the same channels satisfy the minimum reuse distance requirement. This scheme is having two advantages, first is sharing of resources between cells ( in meta-cells) leads to more efficient utilization of the resources and reduces the probability of blocking a new call. The second is that when a user moves from one cell to another, under certain circumstances (from one cell of meta-cell to other cell of meta-cell) it may not be necessary to assign another channel to the user. This reduces the probability of blocking a handoff call. The LCS scheme does not require complex power control techniques, global channel coordination. Simulation results in[24] show that, LCS scheme can admit 20% more call into the network than a tightest FCA for call blocking probability P_b<= 10^-2 . In 2-D case, for the minimum possible reuse factor R = 3, scheme[24] outperforms the fixed scheme by more than 10% and for the reuse factor R = 19, the improvement is about 30%. That shows, the LCS scheme is much better compare to tightest FCA for larger reuse factor.

4.2. Some Hybrid Channel Allocation (HCA) Algorithms

Nominal Channel Allocation Scheme: The Nominal Channel Allocation Scheme proposed in[50], is a HCA scheme, which is composed of two parts. The first part is the allocation of nominal channels for each cell at planning stage of wireless communication network. The second part is the allocation of channels to ongoing call requests while the wireless network is in use. The channel allocation, to call originating in a cell, is done dynamically, if that cell is not having free nominal channels. Nominal channel slot order and channel assignment strategy are used as two important factors in allocation of nominal channels. In this scheme, interaction between nominal channel slot order and channel assignment strategy, is used for effective channel utilization. In[50] , it is observed that by using different channel assignment strategies on the same nominal channel slot order, results in different nominal channel assignment schemes. Unlike general hybrid channel allocation methods, this method does not divide channels into fixed and dynamic groups. In the case of non- availability of nominal channels, all the channels in this scheme are considered for dynamic allocation, including those used in other cells as nominal channels, by doing this efficiency of channel usage increases. The simulation result shows[50] that compare to fixed channel allocation, simple channel borrowing, and borrowing with channel ordering methods, the HCA scheme proposed in[50] gives better performance in terms of call blocking probability, especially under heavy traffic load. When traffic load increases, the percentage of blocked channel requests for this HCA scheme grows slower than for the other tested methods. Also in the case of heavy traffic load and unbalanced traffic distribution, nominal channels are used up in many cells. In these cells, while fixed channel allocation rejects all the new channel requests, this HCA method handles the imbalance and satisfies new channel requests by borrowing channels from cells with light traffic or using channels from dynamic channel pool.

Sector Based Scheme: The HCA scheme proposed in[40] is a sector based scheme, where all the cells in the system are divided into several sectors, and each sector is covered by several directional beams. Specific channels are allocated to each sector using FCA. The DCA is used across multiple sectors and channels of a sector are dynamically assigned to wireless users in the sector as long as the co-channel interference constraints are satisfied. In this scheme a wireless user can access any of the channels of a sector without regard to the beam through which it communicates. Also this scheme give importance to a handoff call over a new call and reserves a certain number of channels for use by hand-off calls only. After a call completion and a hand-off departure, channels are rearranged to maintain a compact pattern. This scheme, dynamically decides about the allowable co-channel interference and the channels of a sector, without considering the beam through which they communicate. In this scheme unnecessary blocking of calls are avoided by combining channel rearrangement with DCA. This allows the channel resources to be used more efficiently; in turn it improves the QoS of the system. As simulation result shows[ 40], this scheme has smaller forced call termination probability than the traditional scheme, because this scheme uses dynamic channel assignment across multiple sectors and FCA-DCA combined approach enhances channel reuse.

Channel Borrowing based HCA Algorithms[15, 55]: A nominal channel and channel borrowing based flexible channel assignment scheme is presented in[55]. In this scheme, when a call request occurs in a cell, the nominal channels of this cell are tested in order starting by the first channel of the list looking for a free channel. Once a free channel is found, it is assigned to the call. If all the nominal channels are busy, a channel is borrowed from the adjacent cell which is having the largest number of channels available for borrowing. In channel borrowing scheme presented in[55], if all channels in one cell are busy then it borrows channel from a nearby cell, if available. In this scheme, in all conditions of borrowing, there is a necessity of locking two identical channels if both are free to prevent co-channel interference. As simulation result shows, the scheme in[55] is having better call blocking probability and better average delay for call dispatch compare to the fixed channel assignment scheme for the same traffic range. The algorithm in[55] also performs better than the fixed channel assignment up to more than a 100 percent increase above the base load. It happens due to the flexible ratio between fixed and borrowed channels and the new switching strategies used in[55].

In Channel Borrowing with Minimal Locking (CBML) scheme[15], BS is made aware about users location and users closers to the BS get higher priority compare to users who are away from BS. The scheme[15] performs better as compared with the conventional FCA, DCA and HCA schemes especially at high traffic loads. As simulation result[15] shows, the CBML channel assignment scheme performance lies between the fixed scheme and the borrowing scheme in the region below 30% of the offered load. Also CBML is having about 12% relative improvement compared to BCA scheme and about 26% relative improvement over the FCA scheme, under a 100% increase in traffic loads[15].

Channel-Borrowing with Locking (CBWL)[56-57]: It is very important for a dynamic load-balancing algorithm to consider, how to take decisions, such as from where to borrow and when to borrow channels for better QoS. In channel borrowing with locking (CBWL) schemes, neighboring cells of the system are allowed to use each other’s channels. This arrangement increases the effective channel availability in the cells in the case of non-uniform load distribution in the system. In this scheme the co-channel interference which occurs due to channel borrowing is eliminated by co-channel locking. In HCA, channel locking is used to prevent the increase in co-channel interference[56-57]. If a channel is locked then, cells within the required minimum channel reuse distance from a cell that borrows this channel cannot use the same channel. Channel locking has some disadvantages also, such as the number of channels that are available for lending to a cell is limited. This limitation arises because a channel can be borrowed by a cell only when it is idle in all of the cells within the required channel reuse distance of the borrowing cell. Another disadvantage of channel locking is the difficulty in maintaining co-channel reuse distance at the minimum required value everywhere in the system[56-57].

Channel-Borrowing without Locking (CBWL) [56-58]: The channel borrowing without locking (CBWL) schemes, work on the techniques of power control to avoid channel locking of the lending cells. Power control technique works by reducing the power transmission on borrowed channels, hence removing the need for locking co-channels of the borrowed channel. CBWL scheme uses the borrowed channel under less power[56-58]. CBWL uses a power limitation to control interference generated by use of borrowed channels. Because a borrowed channel is not used through the base station that owns it, the power reduction is made so that the signal-to-interference ratio of the overall channel reuse pattern is not significantly changed. To increase system capacity, CBWL requires neither new cell sites nor additional antenna towers. Hence, the CBWL does not require additional changes in the current cellular systems and can be employed without additional costly infrastructure. Therefore, it can be considerably less costly to implement than cell splitting[56]. In CBWL the complexity of base stations is less. Without channel locking and directional lending, channel reuse distance can always be kept at a desired minimum. Thus, the CBWL scheme gives better performance under light as well as heavy communications traffic loads[56-58].

In the CBWL scheme proposed in[56], even if the set of channels in a cell gets exhausted, they are used under reduced transmission power. This scheme borrows channels only from adjacent cells in an orderly manner. The set of channels in a particular cell is divided into seven groups. One group is exclusively for the users in that cell, while each of the six other groups caters for channel requests from one of the neighboring cells. This decreases, the excessive co-channel interference and channel borrowing conflicts. Also, if the number of channels in a channel-group gets exhausted, a user using one of the channels can be switched to an idle channel in another group, thereby freeing up one in the occupied group. Since in this scheme, borrowing channels are transmitted at low power, not all users (within range) are capable of receiving them. If such a user finds all the channels occupied, an ordinary user using regular channel can handover its channel to the former while itself switching to a borrowed channel, if available. This particular variation of the scheme is called CBWL with channel rearrangements or CBWL/CR. One major problem in reduced power transmission strategy is that not all users are in the right zone all the time for borrowing channels if the need arises. To overcome this limitation, CBWL/CR is used along with channel reassignments, with a compromise in increases the number of intra-cellular hand-offs. As simulation result shows[56], in comparison with FCA, the CBWL/NR can reduce the blocking probability about 50%, while CBWL/CR can reduce the blocking probability by factor of 10 to 1000.

Here it is worth mentioning that power control technique fails when the MS requesting for a channel is not within the low power transmission region.The borrowing schemes, which work only based on local surrounding information, perform better as it require less computation[59]. A channel allocation scheme named borrowing with directional channel-locking (BDCL)[59], does not require system-wide information, hence as the simulation result shows[59], it gives the lowest call blocking probability in a 49-cell system in the case of both uniform and non-uniform traffic distributions.

In some cases, situations arise, where same channel is chosen by two cells simultaneously while some cells are changing its configuration. To avoid conflicts in channel choice, a channel allocation scheme is presented in[60].

This scheme ensures that, when a cell is changing its configuration, none of its neighbors up to the reuse distance does the same channel allocation simultaneously. This scheme is implemented by a multiple token-passing protocol in such a way that any two tokens are at least minimum reuse distance apart. As simulation result[60] in figure 6 shows, BDCL scheme minimize call blocking rate significantly

Figure 6. Performance comparison among algorithms[60] between cell load and blocking frequency

A channel borrowing based channel assignment (BCA) scheme is proposed in[61], which consists of two phases. The first phase is the ordinary channel allocation phase, which assigns a call request the lowest numbered free nominal channels (NC) assigned to the cell. If no free NC is found, a free non-nominal channel (NNC) selected by a borrowing strategy is allocated to the call. The NNC’s are channels which can be borrowed from neighboring cells. The second phase of the scheme is channel reallocation phase, which has a reallocation procedure for locked-channel utilization and a reallocation procedure for efficient channel reuse. The second phase is designed to further improve the efficiency of the system. It is interesting to observe that the schemes proposed in[61] further reduce the system blocking probability significantly over the BDCL scheme[59], because of its impact-based channel borrowing strategy.

The hybrid channel allocation scheme proposed in[51] uses concept of “hot-spot”. A cell becomes a “hot-spot” when traffic generated in that cell exceeds far beyond its normal traffic load, for particular time duration. An example of a “hot-spot” cell(s) could be the area covered by a cricket stadium for the duration of a T20 cricket game. In this scheme whole channel is divided into two groups-- one is allocated to base stations (using FCA) and other is kept in a central pool located at MCS for dynamic assignment (DCA). The scheme proposed in[51], works in two phases one is channel acquisition and other is channel release. In acquisition phase when a new call send request to its BS for channel, and if channel is available it is allocated otherwise a request is send to the central pool of channel for borrowing. If channel is not available in central pool then call is blocked. When a call complete the channel allocated to it become free. In channel release phase it is decided whether a free channel of central pool is to be returned to it or not. This decision is taken based on the current number of hot-spots in the cell. Main advantage of the this algorithm is that it can adapt from dynamic strategy ( DCA) at low traffic load to static strategy (FCA) at higher traffic load. Hence, when value of “hot-spot” level is increases in the system, the system performance, in general improves, in both regions of low and high system loads. As simulation result shows[51], in figure 7, by increasing the value of maximum “hot-spot” level , the system performance, in general improves, in both regions of low and high system loads.

Figure 7. Simulation Results of algorithm[51] for various values of ruse factor N for maximum hotspot level M=8, and their comparison with FCA

4.3. Some Dynamic Channel Allocation (DCA) Algorithms

Dynamic Load Balancing Based DCA Schemes [45-46]: The DCA schemes proposed in[45-46] are based on dynamic load balancing techniques. In these schemes , allocation of channel start with a fixed assignment scheme where each cell is initially allocated a set of channels, and then each cell is assigned channels on demand to a user in that cell. This scheme divides the cells into in two categories hot-cells and cold-cells. The degree of coldness of a cell is defined as the ratio of the number of available channels to the total number of channels required for that cell. A cell is said to be “hot”, if the degree of coldness of a cell, is less than or equal to some threshold value, otherwise the cell is “cold”. In these schemes, unused channels are shifted from under loaded cells to an overloaded cell through borrowing a fixed number of channels from cold cells to a hot cell according to the channel borrowing algorithm proposed in[45]. The authors of[46] , have proposed channel allocation strategy based on dividing the users in a cell into three broad types – ‘new’, ‘departing’, ‘others’, and then forming different priority classes of channel demands from these three types of users, where channels are allocated based on priority. The simulation result in both[45] and[46] shows that call blocking rate is considerably less even in heavy traffic load for similar evaluation parameters.

Dynamic Frequency Time Channel Allocation (DFTCA)[47]: In addition to the generic adaptive channel allocation as done in any DCA algorithm, in DFTCA scheme, the time slots of each channel is also adaptively allocated. This implies that, if two calls in progress in two neighboring cells then they may occupy the same frequency but at different time slots. It is observed that a very interesting and unexpected simulation results shown in[47], find that, in high handover rate, DCA and DFTCA performance worse than FCA. This happens probably because of the low capacity island effect. Low capacity island are those cells whose channels are borrowed but not returned to them and as a result of that these cells have low capacity to cope with high channel demand. During low traffic periods, due to dynamic channel allocation, some channels will be borrowed from a certain cell for the benefit of other cells. In the case of the overload traffic situation, this particular cell may not be able to obtain back these channels when its traffic level increases. As simulation results show[47], with the increase in the total traffic load, the overall blocking probability increases for each of FCA, DCA and DFTCA. As the rate and point of increase in probability is different for the various schemes[47], in the case of FCA, the overall blocking probability starts to increase as the arrival rate in each cell increases from four[calls / minute].

In the case of DCA, the overall blocking probability starts to increase at five[calls / minute]. In the case of DFTCA, congestion only set in when the arrival rate in each cell is higher than six[calls / minute]. This shows that DFTCA is more efficient than each of the FCA and DCA schemes, and the DFTCA gives better overall call blocking probability in comparison to FCA and DCA algorithms[47]. It is also observer that with the increase in handover rate drop out probability increases, as shown in figure 8a. Also with increase of arrival rate, overall blocking probability for FCA, DCA and DFTCA increases, as shown in figure 8b.

Reused Partitioning Based Dynamic Channel Allocation: DCA algorithm in[48] is based on reused partitioning concept, which exploits a given channel reuse pattern for better channel allocation. This DCA algorithm uses first-order reuse partitioning. According to the reuse partitioning concept, this scheme enables a smaller reuse distance of a subset Fs of the entire channels set F available in the network. The detailed analysis shows that the signalling load increases due to the cell partitioning induced by reuse partitioning and user mobility. The numerical results in[48] show that the capacity of the scheme is considerately higher than that of a dynamic channel allocation without reuse partitioning. Also, the numerical result shows in[48] that this scheme also has significant improvement in the call blocking probability compared to without reuse partitioning approach.

Figure 8a. Effect of Handover Rate on overall Call Drop Out probability for FCA, DCA and DFTCA[47]

Figure 8b. Effect of arrival rate on overall blocking probability for FCA, DCA and DFTCA[47]

The DCA scheme in[62] is based on the concept of reconfiguring the network of cells to obtain a new assignment of nominal channels. In this scheme, channel allocation has been done in such a way that (i) the minimum possible number of channels is used for the new load, and (ii) the number of different frequency assignments is minimum. For the general case of non-uniform traffic, the number of channel requirements in each cell is derived based on:

i. The arrival rates of new calls and

ii. Handover calls along with the expected grade of service for each type of calls.

The estimations used in[62] are based on[63], which says that, for a given arrival rates of new calls and handover calls during some time interval, and the grade of service of both types of calls, the number of channel requirements of each cell can be estimated. In[62] it has been observed that reconfiguration in the microcellular case normally is required more frequently compare to macro cellular case.

Co-channel Information-Based Dynamic Channel Assignment (CDCA): The frequency reuse distance and channel reuse pattern directly influence the co-channel interference levels. Longer the reuse distance, smaller the co-channel interference, but this also gives smaller reuse efficiency. Hence, a trade-off between interference and efficiency always needs to be adjusted. In[64] a Co-channel Information-based Dynamic Channel Assignment (CDCA) strategy is proposed, which makes the assignment decision according to channel’s Carrier-to-Interference Ratio (CIR) and neighbor information. Also, in[64] a Group Dynamic Channel Assignment (GDCA) strategy is proposed for managing multichannel traffic. In this algorithm, similar to a distributed DCA[64], each cell can handle channel assignment or handoff autonomously. One major advantage of this channel assignment scheme is that it is self-organizing. In this scheme, cells with busy channels, near the full capacity, acquire new channels while cells with idle capacity release assigned channels. The specific channels acquired and released are selected on the basis of use patterns in surrounding cells. In this scheme, a new call is blocked only if there is no possible reassignment of channels to calls (including reallocation of the calls in progress) which results in the call being carried. When a new call arrives, and the system is in a state where the call would normally be blocked, the system finds it possible to reconfigure the radio channels in use to accept a new call, subject to reuse constraints and the new call is accepted. In practical networks, this strategy is not cost effective to implement from the control point of view. Because it requires system-wide information about channels in use, in every cell. One advantage of this scheme is that it provides a bound on the performance of the system. This scheme may be quite useful and effective in the time critical systems. As simulation result shows[ 64] with respect to the total success rates of multichannel calls for GDCA and NGDCA strategies, the success rate of GDCA is better than of NGDCA when traffic intensity increases. As simulation results shows[64], traffic intensity is larger than 30 erlangs, GDCA has about a 10% higher success rate than NGDCA.

5. Centralized Vs Distributed Approach of Channel Allocation Schemes

Under dynamic channel allocation, channels are allocated to cells on demand, thus increasing channel utilization and hence improving the quality of service. In cellular networks, mobile service stations and backbone network links may fail. It is desirable for a channel allocation algorithm to be fault –tolerant and also work well, in network congestion situation, link failures, and/or mobile service station failures. Based on channel control mechanisms used in system, channel allocation schemes are implemented either using centralized control or distributed control, of the channels. Such channel allocation approaches are respectively called centralized channel allocation and distributed channel allocation. The centralized approaches are neither scalable nor reliable, while distributed approaches are having potential to be both reliable and scalable. In the centralized schemes, the channel is assigned by a central controller, whereas in distributed schemes a channel is selected either by the local base station of the cell from which the call is initiated or selected autonomously by the mobile user[2, 37].Channel allocation scheme in[28,65] are distributed dynamic and fault tolerant schemes for cellular networks. These algorithms can tolerate the failure of mobile nodes as well as static nodes and enhance the quality of service by making efficient reuse of channels.

In[2], a channel allocation matrix (CAM) is proposed. This matrix has been used for representing degree of centralization and quality of measurements of different channel allocation algorithms. The vertical axis[2] represents the degree of centralization required by the algorithm and the horizontal axis[2] represents the quantity of measurements performed by a base station or mobile terminal for channel allocation decision making. To decide whether an algorithm is of centralized or distributed type, it is required to know the number of base stations that are communicating with the central controller for decision making about channel allocation. For example in a fully centralized system, all the base stations will communicate with a central controller. This makes centralized system more complex, as all the BS in the system needs to have global knowledge of the entire network .In this case the load of computing is high at central controller. On the other hand, in a fully distributed system the base station is able to make a channel allocation decision independently, similar to what happen in the case of FCA implementation. A fully distributed system is simple and takes fast decision for allocation of channels but its performance is not optimal due to lack of knowledge of current network situations[2].

The horizontal axis of the channel allocation matrix is representing the quantity of measurements performed by a base station and/or the user’s mobile equipment for making channel allocation decision. These measurement parameters including, channel interference power or CIR, environmental noise, and application context parameters. Though these measurements take some time and introduce delay by decreasing the overall throughput of a network, yet for QoS point of view these measurements are essential[2].

5.1. Centralized Channel Allocation Algorithms[37, 45-46, 57, 66-69]

In Centralized Channel Allocation Algorithms, a Mobile Switching Center (MSC), allocates channels. In the network, MSC is the only one that has access to system-wide channel usage information. In centralized approaches, MSC allocates the channels to a cell in such a way that no co-channel interference arises. In this approach particularly, each cell notifies the MSC when it acquires or releases a channel so that the MSC knows which channels are available in each cell at any time and assigns the available channels to requesting cells accordingly. The centralized approach may suffer from the single-point failure problem because the functioning of the whole system depends only on the MSC. If the MSC fails, then the entire system stops functioning. This approach is neither scalable nor reliable, because the failure of an MSC brings down the whole system covered by it. Also, in the case of very heavy system traffic load the MSC can become a bottleneck. The centralized channel allocation scheme based systems are not scalable.

5.2. Distributed Channel Allocation Algorithms:

The distributed dynamic approach of channel allocation[28, 39, 68, 70-75, 80], are better as compared to centralized channel allocation due to their high reliability and scalability. In general, in most of the algorithms for distributed dynamic channel allocation, cell that wants to borrow a channel has to wait for replies from all its interference neighbors and, hence, is not fault-tolerant. In distributed approach, in contrast to centralized approach, there is no central controller such as MSC .Also , there is a BS in each cell of the system. MSSs in cells assume the responsibility to allocate channels. Each BS makes this decision independently based on local information. MSSs make this decision independently and they work together to ensure no co-channel interference. MSSs exchange channel usage information if necessary, in order to compute the set of available channels such that using them causes no co-channel interference. In this approach a base station communicates with other base stations directly to find the available channels and to guarantee that assigning a channel does not cause interference with other cells. They adopt a different control strategy, where the allocation algorithm performed in each base station uses local information from the cell controlled by the base station. Such local information includes either cell-based local information[76] or signal strength measurements information[63].

Generally, a channel allocation algorithm[51, 68] consists of two parts: a channel acquisition algorithm and a channel selection algorithm. The channel acquisition algorithm is responsible for collecting information from other cells and for making sure that cells will not use the channels in the interfering region. The channel selection algorithm is used to choose a channel from a large number of available channels in order to achieve better channel reuse. Due to the advantages of DCA allocation strategies, most of the distributed channel allocation algorithms have used DCA strategies as their channel selection algorithm[68, 71, 74,77]. Distributed channel allocation algorithms[68, 71, 74-75] are having high reliability and scalability because of their distributed channel management operations.

Distributed channel allocation schemes are generally simpler and more robust when compared the centralized DCA schemes, because each base station in the distributed DCA schemes maintains local information, and failure of one base station has limited side effects. Channel allocation algorithm in[78] is a complete distributed channel allocation algorithm which efficiently utilizes the bandwidth, adoptively manages handoff and provides QoS guarantees. Some Distributed DCA algorithms are fault-tolerant as they propose mechanisms for recovery from MH failure, MSS failure, and communication link failure[24, 68].

Table 2. Comparison between Centralized and Distributed Channel Allocation Approaches Evaluation Parameter Centralized Approach Distributed Approach Network Knowledge Global Local Complexity More Less Reliable Less More Scalability No Yes Robustness No Yes Use of Local Information More Less Channel Allocation Optimum Sub- optimum

5.3. Some Distributed Dynamic Channel Allocation (DDCA) Algorithms

In distributed dynamic channel allocation (DDCA) algorithms[68, 71-72, 74,79], two schemes, Search and Update, are usually adopted for channel allocation. These schemes work better in opposite scenarios and hence can be seen as complementary to each other. The basic update scheme is better than basic search scheme when the percentage of channel busy in a interference neighborhood is low. However, when higher percentage of channels is busy the basic search scheme becomes better[68, 71-72, 77].

Search Approach: In search approach[28, 39, 68, 71-72, 74-75], when a cell needs channel it sends a request to all its interference neighbors. Based on the information about available channels in the replies received from its neighbors, it computes the set of channels that can be borrowed. It chooses a channel from this set and consults with its interference neighbors on whether it can use this channel. After choosing one such channel it sends messages to its interference neighbors to borrow that channel. If all the neighbors to whom that channel, has been allocated agree to lend that channel, the channel borrowing process is complete. In this approach[75]:

i. Cells exchange channel usage information only when it is necessary,

ii. Borrowed channels are blocked for the period of its use and

iii. A cell communicates with its interference neighbors only when it needs to borrow a channel.

On receiving a call request, a cell marks some channels as reserve and then sends its channel information to the borrower. The borrower selects a channel using its own selection algorithm. Borrowing from any interference neighbor, is done from the reserved channels. In most algorithms proposed in the literature that use the search approach[12, 28, 39, 75] , in order to borrow a channel, a cell has to receive a reply message from each of its interference neighbors. Search approach is not fault-tolerant because, in real-life networks, MSSs may fail and the network may experience link failure and/or network congestion under a heavy traffic load. In[39], a distributed dynamic channel allocation protocol using the 3-cell cluster model is proposed. This model uses search approach for channel allocation, where channels are not pre-allocated to cells. The 3-cell cluster model requires that a channel can support at most one communication session in a cluster of 3 mutually adjacent cells at any given time. Also authors of[80] have considered a 3-cell cluster model for channel allocation study.

Table 3. Comparison between Search and Update Approaches for Channel Allocation Evaluation Parameter Search Approach Update Approach Acquisition Delay Large Short Message Complexity Less More Fault Tolerant No Yes Efficiency Less More Channel Reuse Poor Good

Update Approach: In update approach[74, 79, 81], a cell notifies its interference neighbors regularly, whenever it acquires or releases a channel, about its channel usage information. So, each cell knows the set of available channels all the time. When a cell needs a channel, it just picks one from the set of available channels and consults with its interference neighbors on whether it can use this channel. In this approach, a cell notifies its interference neighbors about its current channel usage information whenever it updates its channel usage information. When all interference neighbors agree, then only it can use the channel. The advantage of the update approach is that a cell responds to a call request very quickly, because it knows the channel usage information of its interference neighbors. However in update approach, the cost of message complexity is high, due to the exchange of channel usage information whenever the status of channel utilization changes. Also, one disadvantage of update approach is that, a cell notifies its interference neighbors about its change on channel usage, irrespective of whether its neighbors need this information or not. This leads to unnecessary exchange of channel usage information in some cases. Also in this approach the message complexity become much higher when the system has a very heavy load, where cells acquire and/or release channels frequently. The update approach is having more message complexity as compared to search approach because of the need of continued communication among cells[75]. In update approach, a cell maintains information about the available channels. A cell keeps communicating with its interference neighbors for giving the up-to date information of channels availability in the cell. In[73], an update approach is used, where all the channels are pre-allocated to cells. Channels pre-allocated to a cell are called primary channels of that cell, and have higher priority to be allocated for calls in that cell. The approach[73] is efficient as in order to borrow a channel, a cell does not need to receive a reply message from all of its interference neighbors.

Ordered Borrow First Available with Reassignment (OBFAR) scheme[82]: It is a distributed channel allocation algorithm. This scheme makes use of fixed channel assignment with borrowing and channel reorganization. Where the channel reorganization algorithms are used to free channels within a neighborhood of the cell in which the requesting call originates. Generally, traffic distribution in system is non-uniform. In this situation, and if the channels are locked in interfering cells, then throughput is degraded. Throughput, of the system can be improved by allocating the nominal channels according to the real traffic distribution of the system[59]. As simulation result shows[82] OBFAR, channel borrowing exhibits significant improvements over fixed channel assignment schemes in handoff call and new call handling.

The distributed dynamic channel allocation scheme proposed in[39], is based on a 3-cell cluster model. In this scheme, at most one communication session can be supported by a channel, in a cluster of 3 mutually adjacent cells, at any given time. This scheme, dynamically adjusts to spatial and temporal fluctuations in channel demand. This scheme provides more channels to heavily loaded cells compare to lightly loaded cells. A drawback of this algorithm is that when a cell needs to borrow a channel, it has to wait until it gets reply messages from all its interference neighbors. This feature of the scheme makes it non- fault tolerant, since real-life cellular networks may encounter network congestion and/or failures, including links failure and mobile service station failures. In[28] also, a fault-tolerant distributed dynamic channel allocation algorithm is given for cellular networks under the 3-cell cluster model which is deadlock free and more efficient in channel reuse than scheme proposed in[39].

CIR-based Distributed Dynamic Channel Allocation: As CIR in any system is a relative value, and it does not contain much information about the distribution of channel reuse in a given geographical area. However, CIR can be used as a sufficient criterion for guarantee good communication quality[64]. The schemes proposed in[64] are CIR based distributed dynamic channel assignment strategies for small cell and microcell systems. In this scheme, each base station does channel assignment locally with the help of knowledge about their neighbor, including the number of co-channels in the neighboring area. This scheme considers three cases of channel selection[64]:

Case A—Always choose the channel with the largest CIR (LDCA),

Case B—Always choose the channel with the smallest CIR (SDCA), and

Case C—Choose the first channel with CIR qualified. The only criterion for this strategy is that the CIR must be equal to or larger than the CIR threshold.

The limitation of these schemes is that only the CIR criteria used for a channel-assignment decision, and they do not provide information about distribution of channel reuse.

To overcome the problem of message complexity and channel locking, in search and update approaches, in[83], a distributed dynamic algorithm for channel allocation is proposed. The major difference between the update approach and the algorithm proposed in[83] is that, this algorithm only notifies those cells to which it has lent channels instead of to all its interference neighbors. This scheme, assumes that the number of borrowers in cells, compared to the number of interference neighbors are very small. Doing this, the algorithm significantly reduces the update notification message complexity compared to the update approach. As simulation results show[83], this algorithm significantly reduces the call blocking rate as compared to the search approach, and minimized the acquisition delay by almost half and compared to the update approach.

The channel allocation scheme in[84] has used a distributed low complexity approach of channel assignment, where nodes are self-organized into coordination groups and adapt their channel assignment to approximate the global optimal assignment. This scheme uses concurrent coordination to reduce the coordination delay and apply proper regulations to prevent conflicts and cascading effects due to concurrent coordination. This is achieved with two simple coordination formats: one-to-one fairness coordination and feed poverty coordination, which maximizes the fairness based system utility. Each coordination group modifies channel assignment within the group to improve system utility while ensuring that local changes in channel assignment do not conflict with nodes outside the group[84]. In this scheme nodes periodically broadcast their current channel assignment and interference constraints to their neighbors. Also each node switches among three states: coordination, disabled, and enabled, but only enabled nodes can perform coordination. The major advantages of this scheme are that it reduces the number of computations and message exchanges required to adapt to topology changes.

Distributed Channel Acquisition Algorithms: In the literature some algorithms[25, 28, 39, 72, 74, 82, 85] have used one of the two approaches- on demand/ reactive approach or proactive approach, for channel acquisition. In on demand/reactive approach[28, 39,68, 71-72, 86], when a cell needs a channel for a call, it first checks for availability of channels in the set of channels allocated to it. If such channels exist, then it picks one from it, otherwise, it gets channel uses information from its interference neighbors. Based on the information received from interference neighbors, it computes the set of available channels. It picks an available channel r using channel selection algorithm in such a way that this selection give a good channel reuse pattern, and sends messages to its interference neighbors to borrow that channel. The channel borrowing process completes, only if all the neighbors to whom that channel has been allocated, agree to lend that channel. Most of the algorithms[39, 68, 71-72], using on demand/reactive approach require that a cell that wants to borrow a channel needs to get reply from each interference neighbor before using a channel. Under this approach, even if one of the neighboring cells has failed, a channel cannot be borrowed and, hence, this approach is not fault tolerant.

In proactive approach[74], a cell notifies its interference neighbors about the channel usage information whenever it acquires or releases a channel. So, each cell is always aware of the set of available channels. When it needs a channel, it just picks one of the available channels using the some basic channel selection strategy and uses it to support a communication after ensuring that none of its neighbors are using that channel. This approach is less complex in terms of message passing complexity compared to reactive approach; hence, response time of proactive approach is better and preferable for handoff handling process.

Resource Planning Model[68, 71-72, 74, 87-88]: In order to achieve better channel reuse pattern, most channel selection algorithms require that the status of channels should be known in advance. In literature, the process of assigning status to channels beforehand is known as Resource Planning Model (RPM)[68,72, 74, 87]. In this model, each cell is preallocated a set of primary channels and a set of secondary channels. When a channel is needed to support a call in a cell, and if there are available primary channels in the cells, then one such channel is used to support the call without consulting its neighbors. Otherwise, the MSS in this cell sends request messages to its interference neighbors to borrow a secondary channel. In RPM, a MSS borrow a channel from its neighbors with consideration of co-channel interference. To avoid co-channel interference, a MSS consults its neighbors before it uses the borrowed channel. When the call terminates, the borrowed channel is returned to the cell from which it was borrowed. In RPM, the whole pool of available channels is not reused efficiently. One major drawback of these algorithms[68, 71-72, 89] is that, if one MSS wants to borrow a channel, it has to wait until it receives replies from all its interference neighbors. In summary, in a RPM the set of all cells is divided into K disjoint subsets S₀, S₁, . . . , S_k-1, in such a way that in the same subset, the distance between any two cells is at least minimum reusable distance . The set of all channels is divided into K disjoint subsets correspondingly: PC₀, PC₁, . . . , PC_k-1 . Channels in PCi are called primary channels of cells in Si and secondary channels of cells in Sj (i ≠j). Cells in Si are called primary cells of channels in PCi and secondary cells of channels in PCj (i ≠ j). Primary channels of a cell, say Ci, have higher priority than secondary channels to be assigned to support a call in Ci. A secondary channel of a cell is used to support a call only if there is no primary channel available[89-90].

6. Some Failure Tolerant Channel Allocation Schemes

In a mobile cellular network, the MHs, the wireless links between MHs and BSs, the BSs and the communication links between two BSs, through MSC are prone to fail[39, 68]. To avoid deadlock in the system, it is necessary that the channel assignment algorithm be fault tolerant. In mobile cellular system, generally, failure occurs due to MH failure, wireless link failure, or when wired communication links between BSs and MSC fails. Fault tolerance of the communication link failures between two neighboring BSs in more complex and complicated compare to other types of failure tolerance. In[30, 68, 71-72, 89], some fault-tolerant channel allocation algorithms are been proposed. Fault tolerant channel allocation algorithms presented in[68, 71-72, 74] are based on the proactive approach based Resource Planning Model. In scheme[74], in each cell, the primary channels having higher priority are allocated. When a cell Ci needs a channel, it selects an available channel r. If r is a primary channel, then it marks r as a used channel, and informs all of its interference neighbors about this. If r is a secondary channel, then the cell sends a request message to each interference neighbor which has r as a primary channel. If all these neighbors agree to lend channel r to Ci, then Ci can use the borrowed channel r. Otherwise, Ci try to find another secondary channel to borrow. Whenever, a cell acquires or releases a channel, it informs all its interference neighbors about this. Due to this proactive approach, the algorithm proposed in[74] achieves short channel acquisition delay at the expense of higher message overhead. Distributed fault-tolerant algorithm proposed in[30], makes full use of the available channels by reusing channels efficiently. This algorithm run at each base station and the control of channel usage does not require a MSC. In this scheme, the neighboring base stations cooperate together by exchanging the channel usage information and assign available channels at run time. In this scheme, all channels are partitioned into equal sized groups. Also, this scheme allow to any base station to acquire a channel group at any time as long as no one of its neighbors is already holding it. When a cell that tries to borrow a channel, it does not wait until it receives a reply message from each of its interference neighbors. The scheme[30], tolerate the failure of mobile nodes as well as static nodes without any significant degradation in service.

A fault tolerant, mutual exclusion based dynamic channel allocation algorithm proposed in[91], improve QoS by dynamically adjusting the number of reserved channels for the handoff in terms of the traffic situation. In[91], whole system is divided into a number of cell clusters and each cluster consists of seven cells and channel allocation process run in each cell. Each base station accesses a channel group but any two neighboring base stations have access to the different channel groups. Based on the three-coloring theorem, any two adjacent base stations can hold different channel groups within the entire mobile network. In this scheme, all base stations can simultaneously hold channel groups using mutual exclusion. This scheme uses a timer at each base station for the purpose of channel allocation and timeout calculation. This scheme uses, timeout time, for determining the statistical connection dropping rate and adjusts the reserved channels at each BS accordingly. In this scheme, in the uniform traffic distribution load, timeout value is kept bigger and in non-uniform traffic distribution, the timeout value is kept small for strict monitoring of QoS parameters. The simulation result shows[91] , this scheme significantly improve call dropping rate and helps to reduce significantly the call blocking rate.

7. Channel Allocation and Mutual Exclusion

The nature of channel allocation problem is a type of resource management problem, which has used mutual exclusion as a solution of the problem. Channel allocation problem can be seen as a form of the mutual exclusion problem which is studied extensively in the operating systems and distributed computing research. There are many channel allocation algorithms which are developed based on mutual exclusion concept[5, 30, 39, 44, 72, 79, 91-94]. With all mobile cellular networks, the higher the upper bound of response time, the more requests will be satisfied at the price of QoS. On the other hand, if the upper bound of response time is lower , more calls will be dropped, and the blocking rate will also increase. Many of the existing distributed mutual exclusion algorithms do not consider real-time requirements[30, 39, 75, 79, 91]. However, all dynamic channel algorithms, there is always need to make an acceptable trade-off between response time and blocking rate. To improve channel utilization, the same channels in a mobile cellular network can be reused at the same time in different cells as long as the two cells are distant enough. This characteristics of channel utilization makes channel allocation problem, a kind of relaxed mutual exclusion problem.

In[44, 93], two different class of mutual exclusion algorithms are discussed. One class of algorithms are based on token concept[93], where a single token is taken in the system and the process that currently holds the token is allowed to use the resource. Since there is only one token in the system, mutual exclusion is guaranteed. This type of mutual exclusion approach is not suitable for channel allocation problem because any two cells might be using a given channel at the same time as long as these two cells are at least minimum reusable distance away. The other class of mutual exclusion algorithm is based on nontoken-based approach[44]. In nontoken-based approach a process which need the resource, sends request messages to a subset of the processes, and waits for appropriate responses from some processes in order to gain access of the resource. A process which is using shared recourses i.e. channels in the case of cellular system , release it after it is completed and sends appropriate messages to a subset of processes, about the “releasing” of resource, which helps in allocating the released channels to other process. The nontoken-based mutual exclusion[94] algorithms, uses the idea of an information structure, which consists of a number of sets (for each process in the system) in which appropriate information about the current state of the system, such as information about hold resources, the processes which are waiting to access the resource, amount of resource required by a process in waiting, etc., is stored[94]. There is no need to mention that, these are the essential information used for channel allocation problem.

In[79, 81, 95], the channel-allocation problem in cellular networks is visualized as a distributed mutual exclusion[96] problem. In this approach, the channels are divided into several disjoint groups. To acquire a channel, a BS needs to hold a group first. These algorithms are not fault tolerant because if any queried BS fails, then the BS that submits the query cannot get a hold on a group and therefore is unable to acquire a channel, causing a high call-failure rate. The mutual exclusion model based, distributed dynamic resource allocation algorithm (DDRA) proposed in[81], is deadlock-free and has limited waiting time. The advantage of this algorithm is that, it remains stable with regard to the different arrival patterns and it happens, because it does not allow any BS to be a host of a group channels and takes advantage of the fast response time and the low denial rate even under a very high system load.

The dynamic distributed channel allocation (DDCA) schemes based on distributed mutual exclusion proposed in[5, 7, 63, 73, 97] attempts for maximizing channel reuse in various cells. These schemes give due consideration to interference among cells which is caused by more than one cell, while attempting to reuse the same channel. The schemes in[74-75, 90] have attempted to prevent the interference among cells by ensuring that neighboring cells do not simultaneously use the same channel. The distributed mutual exclusion used in DDCA, is different from a common mutual exclusion problem, because here a channel also may be reused in different cells simultaneously. In scheme[5], authors have introduced the concept of relaxed mutual exclusion, to model for channel sharing aspect of the DDCA problem. The relaxed mutual exclusion scheme[5, 73], which dynamically assign critical resources to different sites, worked on two criteria. The first criteria is that, a given critical resource may be used simultaneously at different sites as long as no two of them are mutually interfering, which is the requirement of channel allocation problem. The other criteria is, at any single site, a given critical resource may not be shared by two or more processes. In relaxed mutual exclusion based DDCA , each cell i maintains two sets: Ri and Ii. Ri, which is the request set for cell i, is the set of cells from which i will request a permission for using a channel. Ii, which is the inform set for cell i, is the set of cells that cell i will inform about its channel usage information. When cell i needs to acquire a channel r, it sends a request message to each cell in set Ri. It acquires channel r only if it receives a grant message from each cell in Ri. When cell i releases channel r, it notifies all the cells in set Ii about it. This algorithm guarantees relaxed mutual exclusion for a single resource. The relaxed mutual exclusion schemes in[5, 73], are also used for efficient channel selection and deadlock resolution. One disadvantage of these algorithms is that they are not fault tolerant because a cell cannot acquire a channel if any cell in its request set fails.

A DDCA scheme based on combination of clustering and mutual exclusion model is proposed in[79]. In this scheme, the channels are grouped by the number of cells in a cluster and each group of channels cannot be shared concurrently within the cluster. This scheme uses the mutual exclusion with simple competitiveness and multiple critical sections. This scheme, based on request/reply model and runs on all base stations. Therefore, it takes advantage of the fast response time and the low denial rate under a very high system load. In this scheme, each base station is assigned a unique id number and uses a variable competition to count the number of competitions with other base stations required to get a free channel group gj[79]. As simulation results shows that there is significant improvement in channel acquisition time and reduction in the denial rate. Mutual exclusion based DCA in[92], uses 3-clustor cells, where all the channels are grouped into three clusters and this partitioning is done using three coloring theorem. In this scheme, any cell in a cluster can not hold a channel group as long as another cell in the same cluster is holding the same group. This algorithm consider four QoS metrics, they are dropping rate, denial rate, acquisition time and message complexity. In this scheme, each cell in a cluster has control over usage of channels and doest not require a MSC, because the neighboring base stations cooperate together by exchanging the channel usage information at run time. In this scheme, total channels in the mobile cellular system are partitioned equitably into three groups. Any base station can acquire a channel group as long as no one of its adjacent cells is holding this group.

8. Genetic-Algorithms for Channel Allocation

The genetic programming was developed based on the concept of “survival of the fittest”, and has been used to address diverse practical optimization problems[98]. Genetic algorithm (GA) as optimizers are robust, stochastic search methods modeled on natural selection and evolution found in nature. As an optimizer, the powerful heuristic of GA is very effective at solving, complex optimization problems. The use of GAs were initially limited for machine learning systems, but later on GAs have been used extensively as a great function optimization tool[99] . The genetic programming has the features of simplicity, parallelism andmulti-directional search. As the channel allocation problem is also a kind of optimization problem, the genetic programming has been extensively used by the researchers to solve the channel assignment problem in the complex network environment[100]. Genetic algorithm is extensively used in solving channel allocation problem in cellular system[88, 101- 105].

In[104] a genetic algorithm for solving problem of fixed channel allocation (FCA) is proposed. This scheme exploits the past results along with exploring some new areas of the search space. In GA based channel allocation scheme[101], the channel allocation is considered as a call admission problem. In this work, GA is used to find good call admission policies. The chromosome is encoded using three genes in a group to describe a local call admission policy. The encoding used in this scheme is binary. The bits of the chromosome represent admit or reject decisions for a new call arrival, a hand-off request from a cell on the left, and a hand-off request from a cell on the right. It is interesting to observe the result that, when a two-dimensional network is packed into a linear chromosome, the GA performs better than the best heuristic hand-off policies available[101]. In[105], a control scheme is proposed based on the genetic programming , which select the optimal number of channels need to be assigned in a cell for wireless networks, to reduce thee call blocking probability. In[103] a hybrid of Genetic Algorithm named Guided Genetic Algorithm (GCA) used for channel allocation. The GCA, modifies both the fitness function and fitness template of candidate solutions based on feedback from constraints. The GA based channel allocation algorithm proposed in[102], assumes that the traffic load is inhomogeneous, considering that in real life generally, each cell has different traffic requirements. In[102] a modified genetic algorithm for channel allocation is proposed. This scheme, consists of a genetic-fix algorithm that generates and manipulates individuals with fixed size subsets. This is achieved by using special crossover and mutation operators which can maintain the property of a fixed number of ones for each individual. Also, this scheme uses a minimum-separation encoding scheme that eliminates redundant zeros each individual. This scheme considers all the three electromagnetic compatibility (EMC) constraints:

i. the co-channel constraint (CCC), where the same channel cannot be assigned to certain pairs of radio cells simultaneously,

ii. the adjacent channel constraint (ACC), where channels adjacent in the frequency spectrum cannot be assigned to adjacent radio cells simultaneously and

iii. the co-site constraint (CSC), where channels assigned in the same radio cell must have a minimal separation in frequency between each other.

As simulation result shows[102], the genetic-fix algorithm is a good method for solving the FCA problem, as it gives 80%- 100% convergence which is very good compare to benchmark problems[ 38, 106]. A GA-based reliability model for channel allocation is presented in[88], which exploits the potential of the GA to improve the reliability of the communication network system by assigning the channels to the MHs, based on the reliability computation parameters as failure rate of the BS and the failure rate of channels.

Figure 9. Genetic Algorithm Operations

9. Channel Allocation in Hierarchical Cellular Network (HCN)

The HCN[92, 107-109], is a category of cellular network, which have three types of base stations (BSs)-- micro BSs, macro BSs and pico BSs. A HCN can be of-- single-tier, two-tier (consisting of macrocell and microcell), or three-tier (consisting of, macrocell, microcell and picocell), based on the configuration of the cells within it[110] and the way the base stations are loaded.

Figure 10. A three-tier hierarchical cellular network

A structure of three-tier hierarchical cellular network is given in figure 10. A micro BS cover small radio coverage are called microcell, and macro BS cover large radio coverage are called macrocell. The microcells cover mobile stations (MSs) in heavy traffic areas.

A macrocell is overlaid with several microcells to cover all MSs in these microcells. In HCN the radio signal strength of micro BSs is very less compare to macro BSs. Some channel borrowing, such as channel sharing and cell splitting[48, 58] are used for load balancing in mobile. In cell splitting, existing cells are break down cells into smaller cells. Through cell splitting several different levels of cell coverage are obtained in the system. These different levels are macrocells, microcells and picocells. A macrocell is like an umbrella over a set of microcells and picoclls. Loads are shared between microcell, macrocell and picocell. In low traffic situation picocell handle the call but when traffic becomes heavy for a cell to handle then, the cell can be switched into the microcell and subsequently to the macrocell. Any user in a picocell can be served either by the base station in the picocell itself or by the base station in the corresponding microcell or by the base station in the macrocell. Two tier and three tier systems are costly to implement, due to increase in number of base stations. Also the load on backbone network increases due to introduction of additional cell

In HCN overflow is an operation that hands off a call from a lower-tier cell to the corresponding higher-tier cell, and repacking is an operation that hands off a call from a higher-tier cell to the corresponding lower-tier cell[20].

The HCN schemes proposed in[107-108], reduce call blocking and force-termination through repacking techniques. HCN) channel assignment approach discussed in[92] is based on repacking based on demand (RoD)[111] where repacking is performed only right before a new call is to be blocked.Considering user movement is essential for channel allocation in HCN to satisfy the following two criteria, for better QoS:

Criterion 1: Calls for slow MSs tend to be assigned with microcell channels so that the ‘‘global resources’’ of macrocells can be effectively shared by calls in the microcells which are not having any idle channel.

Criterion 2: Calls for fast MSs tend to be assigned with macrocell channels so that the number of handoffs can be reduced.

Some speed-sensitive HCN channel assignment and repacking schemes are proposed in the literature[107-108, 112, 113-114], which satisfies the above mention two criteria.

10. Cellular Networks with Mobile BSs (MBS)

Deviating from traditional cellular structure, in literature some schemes[86-87,115-116], have discussed the channel allocation issues in cellular networks, where the BSs are also mobile as shown in figure 11. In such systems, BSs are also connected by wireless links and the entire network become wireless. Location of BSs keeps on changing in MBSs, hence the geographical area covered by the cell changes dynamically with the location of BS of the cells changes dynamically. This dynamic change in location of the BSs, add more complexity in the system, as the neighboring information changes dynamically.

It is needless to mention that the channel-allocation schemes used for the traditional cellular networks do not work for cellular networks with MBSs. In MBS systems, all the decisions pertaining to channel allocations are taken based on the information available locally [117].

Because the base stations are mobile, the set of cells within the co-channel interference range changes with time. By doing this the channel reuse pattern is made very dynamic and almost unpredictable. In MBS situation, the problem of channel allocation become more complicated and challenging, and need to do the followings[117]:

i. Develop a dynamic channel allocation algorithm for backbone as well as short-hop links,

ii. Make channel allocation decisions in distributed manner to make system more scalable and robust,

iii. Reduce dependency on relatively resource-poor mobile nodes (MNs) to a minimum, and

Minimize overhead of channel rearrangements.

In MBS system the issue of co-channel interference can only be taken care at the time of channel allocation. In the case when any two MBSs using the same channel to support short-hop sessions move into co-channel interference range, one of the two MBS need to switch these channels to avoid the interference.

Figure 11. A fully wireless cellular network[117]

In mobile base station scenario, channel allocation is more complex than the conventional wireless system algorithms, because it does not have backbone wired network[117]. At the same time, the algorithm for channel allocation with mobile BS have many advantages, such as bounded latency, deadlock freedom, low system overhead and network traffic, and concurrency. The MBS systems definitely are not preferred in the environment where the existing cellular networks with fixed BSs are deployed. As in, convenient environment including towns, cities, plane areas etc; establishment cost, security, duration service requirement etc are always in favor of the fixed BSs system. The MBS systems may be applicable in areas such as military use in battlefields and emergency condition such as disaster rescue including flood, earth quack, tsunami etc. Cellular networks with MBSs are similar to Mobile Ad Hoc Networks (MANETs)[118-119] with clusters and with rich in resource, having more energy, computational power, and memory.

In MBS based, distributed channel allocation algorithm for cellular networks channels are allocated to support the links between MBSs, referred to as backbone link and the links between MBSs and MHs, referred to as short-hop links[115]. Where, channels used to support the backbone links and the short-hop links, is having no distinction. Hence, the same channel can be used concurrently for the two different types of links as long as they are not within co-channel interference distance. In[116,117], distributed dynamic channel-allocation algorithms for cellular networks with MBSs are proposed. In these algorithms, the set of channels is divided into two disjoint subsets: one for short-hop links, the communication between MBS and MH and the other for backbone links, the communication between MBSs. The algorithm consists of two parts:

1) Short-hop channel allocation: When an MBS, MBSi needs a channel, it first checks whether there exists an available channel allocated to it. If there such a channel exists, it can use this channel. Otherwise, it sends a request message to each neighboring MBS within the short-hop channel reuse distance. Upon receiving replies from neighboring MBSs, it computes the set of channels that can be borrowed. Depending on availability it selects a channel r from this set and consults with its neighbors, to which r has been allocated, on whether it can borrow this channel to use. It can use the selected channel if all the neighbors it consults grant its request. This approach is not fault tolerant because if any of the neighboring MBS fails channel allocation process stops.

2) Backbone channel allocation: Whenever an MBS, MBSi wants to communicate with another MBS MBSj, all the BSs within the backbone channel reuse distance of either MBSi or MBSj are polled to gather their channel usage information. A channel is chosen to support the communication if the channel is not being used by MBSi, MBSj , and the BSs that are polled. When the communication between MBSi and MBSj terminates, the channel serving this call is returned to the system. In short-hop channel-allocation attempt, when an MBS does not receive a message from a neighbor within a timeout period, it is assumed that the neighbor either has crashed or moved out of its co-channel interference range.

In MBS based distributed channel allocation scheme proposed in[115], the responsibility for channel allocation is distributed among all the base stations. Doing so, this scheme becomes robust and scalable. The MBS’s neighborhood is divided into three regions: no-use region, partial-use region, and full-use region. If a channel r is used by an MBS, MBSi, then r cannot be used concurrently by any other MBS, MBSj , which is in the no-use region of MBSi. When allocating channels, an MBS may need to take into account the neighbors in some or all of the regions. The algorithm in[115] is not fault tolerant because an MBS needs to get a reply message from each neighbor to borrow a channel. In MBS systems there is more likely that the MBSs may fail and degrade the performance of the cellular network. Therefore, it is desirable for MBS, that the channel allocation algorithm should be fault tolerant and may work even in the presence of failure of the MBSs, may be under more relaxed QoS parameters. Considering these issues, in[117] an efficient, fault tolerant, QoS based channel allocation algorithm for cellular networks with mobile BSs (MBS) is presented.

Table 4. Comparison between Cellular Systems with Mobile BS and Cellular Systems with Fixed BS Parameter Cellular Networks with Mobile BS (MBS) Cellular Networks with Fixed BS Base Station Moves Stable Link Between BSs Wireless Wired Co-channel Interference Dynamically Change Static System Complexity More Less Channel Allocation Decision Only based on local information Based on both global and local information

In this algorithm, MBSs exchange message with any of its neighbors by transmitting signal at a power level high enough to reach the neighbor. Also each MBS has the knowledge of the identity of its neighbors by listening to their beacons[115]. The MBS based channel allocation scheme in[117], divides the available wireless channel into two disjoint subsets. One subset used exclusively for backbone links and another subset used exclusively for short-hop links. As simulation result shows[117], the three QoS parameters, call-blocking rate, handoff-drop rate, and call-failure rate, not only increase with the call arrival rate but also increase with the number of cell failures. This happens because when some cell fails then the demand for channels increases, then it is more difficult for a neighboring cell to find an available channel to borrow. Hence in the case of more cell failures it is very difficult for the neighboring cells to borrow channels[117]. This algorithm is fault tolerant because a cell does not need to get a reply message from each neighbor to borrow a channel.

11. Channel Allocation for Multiclass Applications

Wireless multimedia services in cellular system are generally having varying channel requirements, services of different class may have different bandwidth requirement[4, 53,120]. For example a real-time multimedia service need relatively more bandwidth than a voice service, hence channel requirements may vary application to application[6]. Due to the varying and unpredictable bandwidth requirement, fair channel allocation to different types of services is difficult. Also, it is observed that in multimedia based services, channel allocation bear some overheads of bandwidth redistribution[4,53]. When a base station accepts a connection, these schemes may re-distribute the bandwidth allocation for all ongoing connections. In the borrowing-based channel allocation schemes[4,53], it is assumed that multimedia applications can tolerate transient fluctuations in the QoS and allows for the temporary borrowing of bandwidth from existing connections in order to accommodate new and handoff connections. In these schemes, each call/ request for the connection provides-- the connection class and the required, minimum, and expected levels of bandwidth. Different types of services, need different amount of minimum bandwidth to start or to keep that service continue. This minimum bandwidth is called minimum threshold value required for that service[17].

In scheme[120], users are classified into two classes class I and class II. In this scheme, when a connection request is made, fist of all it is identified as a class I or class II connection. The network tries to reserve some bandwidth for the connection in the cells surrounding the cell in which the request is made. This reservation anticipates that the host will attempt a handoff into one of its neighbors in the future. For Class I traffic, a new connection is blocked unless some reservation can be made for it in all six neighboring cells. In the case of a handoff, a class I connection is dropped if the new cell cannot provide its minimum acceptable bandwidth or if a reservation cannot be made for it in the expected new set of neighbors. In class II, handoffs are accepted if there is any free bandwidth available for them in this case no minimum bandwidth requirement is respected[120]. In[85], a threshold based bandwidth reservation scheme for multi-class wireless cellular networks is proposed. In this scheme, connections are prioritized according to their QoS constraints by reserving a maximum occupancy. In his scheme, handoff calls get priority over new call and separate pool of the bandwidth reserved for aggregate handoff connections. One disadvantage of this scheme is that it uses FCA, which means the cell has only a fixed amount of channels. In the scheme[120], utilization of bandwidth is not good compared to scheme[4], because scheme in[4] attempts to do fairness in channel allocation. As simulation result shows[4], this scheme makes more bandwidth available to both new and handoff connections. There are some limitations of the scheme[4 ], such as ,due to its fairness quality and use of its equal share concept, this scheme only suitable for services with low bandwidth requirements. Applications which need high bandwidth may not even get necessary bandwidth to get started due to the fairness of this scheme. Also this scheme frequently needs bandwidth reconfiguration and redistribution which increases the overheads. In[121], an adaptive scheme for provisioning connection-level QoS in cellular-based multimedia wireless networks is proposed. This scheme, support real-time and adaptive multimedia services, where, the bandwidth of ongoing connections are adjusted dynamically. Due to its flexible nature of the scheme[121], multimedia applications dynamically adapt its bandwidth, depending on the network load situation during its lifetime. As simulation result shows[121], this scheme is good in terms of channel utilization and call dropping probability.

Service-Oriented Bandwidth Borrowing Scheme(SOBBS)[122] :In[122], a service-oriented bandwidth borrowing scheme (SOBBS) is proposed to overcome the problems of scheme proposed in[4 ]. In both[4] and[122] schemes, all multimedia traffic is classified into real-time (Class I) and nonreal-time (Class II) traffic. In these schemes it is assumed that when an MH requests a new connection in the current cell or moves into the neighboring cell, the following parameters are provided:

i. The traffic class (I or II),

ii. The required bandwidth for the connection and

iii. The minimum required bandwidth for the connection.

To overcome the problems of[4], the scheme in[122] works on the idea, that a borrowing approach with high satisfying degree of QoS for user does not increase the re-distribution overheads in mobile communication systems. The SOBBS strategies reduce the overhead of bandwidth reconfiguration and also satisfy QoS requirements of ongoing users in cellular systems. The strategy used in scheme[122] re-adjusts the allocated bandwidth of MHs, when bandwidth is borrowed or returned. In SOBB scheme, to minimize the overhead of bandwidth reconfiguration and to satisfy the QoS requirements of ongoing connection, class I connection is classified into four degrees (A, B, C, and D) and class II connection into five degrees (A, B, C, D, and E) .As simulation result shows[122], this scheme is better in average QoS of degree and require less number of redistribution of channels for class I traffic and class II traffics are compared to the fair resource allocation scheme of[4], for the similar simulation parameters.

12. Handoff Management Schemes for Cellular Systems

In microcellular and picocellular networks[4,29,53,120, 123-124,136], due to smaller coverage areas of base stations, more frequent handoffs occur. Also, due to, frequently changing network traffic load, it becomes more difficult to offer guarantee of QoS. Hence, research in the area of high-speed wireless networks has been given due consideration on the integration of channel allocation and admission control policies, including handoff handling[4,29,53,75, 120,123-124-126,136], to provide better QoS. There are many channel allocation management schemes[32, 124-127], have been studied with more focus on handoff management and provide good QoS guarantees in terms of handoff calls handling. Objective of any handoff management scheme is to minimize the probability of forced call termination or call dropping. As distributed channel allocation schemes are designed to improve bandwidth utilization, handoff management schemes are designed to provide better QoS[29, 45, 75, 125-126, 136]. To minimize the call dropping probability, handoff calls need to be handled on priority basis, and for this, a fixed or dynamically adjustable numbers of channels are allocated to cells exclusively for handoff calls[128]. The handoff prioritizing approach[32,37,75, 124-126] , allow the handoff calls to be queued until channels are obtained in the cell for handoff calls. In some handoff management schemes[32,75,124-127], the moving direction of MH is predicted in advance, this helps in reserving channels at the potential destination cells, instead of at all neighboring cells for expected handoff calls. Considering the fact that handoff handing operation need to be completed in time bound duration, in[21] a channel allocation algorithm is proposed in which the borrowing cell does not need to receive a response from every interference neighbor. It only needs to receive responses from a small portion of them.

Handoff Handling Schemes Based on Prediction of the Moving Direction of MHs[ 32, 75, 124-127, 136]: In mobile cellular network, some cells are comparatively very congested and need more number channels for handling new calls. In such situations, more congested cells needs to have more reserve channels for holding all the incoming handoff calls. Some time, reserved bandwidth for expected handoff calls is not utilized properly due to unawareness of expected handoff. With the help of technologies available today, such as Global Positioning System (GPS), now BSs can be made aware of the moving direction of MHs. This helps in predicting the expected handoff with more reliability. The technique of (GPS) is now widely used in military operations and many commercial applications related to the provision of road safety services, fleet tracking, and intelligent transportation systems (ITS). The accuracy achieved by GPS using basic point positioning technique at 100 more is than 95% probability level. Also adequate accuracy at the 3–5 m level can be achieved by using differential GPS (DGPS)[129].

Guard Channel Scheme for Radio Channel Allocation: The adaptive handoff management scheme named as DCA Variable Reservation (DVR), proposed in[130] is based on variable channel reservation, which adapts the number of reserved channel, according to the current number of ongoing calls and on the localisation of users. This scheme, reduces handoff call blocking probability at the expense of a small increase in new calls blocking probability in cellular networks. This scheme, give more priority to handoff calls over new calls in admission control[130]. In this scheme, some reserved channels are kept in the pool, for each cell, according to the current number of ongoing calls in neighboring cells and on the anticipation of the future localisation of the users. Assuming that a mobile user does not move randomly due to the existence of roads, offices, dead-ends, shops, etc. In[130], it is argued that, if the users mobility pattern is known even approximately, it is possible to use it in order to manage the bandwidth reservation efficiently. This scheme has used mobility pattern for managing the efficient utilization of bandwidth. In this scheme, the guard bandwidth in the next cell, decided using two parameters : on the current number on ongoing calls in the cell and on the observed mobility pattern of the system. As simulation result[130], which is shown in figure12, adaptive reservation scheme is more efficient, especially in the case of unbalanced traffic.

Channel Carrying Algorithms for Handoff Handling: In channel carrying approaches of handoff handling[24, 56], a mobile user moves from one cell to another, under certain mobility conditions. In this approach, the user is allowed to carry its current channel into the new cell, but it communicates with the base-station in the new cell, using those carried channels. An important feature of channel carrying algorithm is that no global coordination is required[24 ]. In a typical scenario, the channel carrying is not difficult to achieve. For example, in an FDMA-based system, if a user requesting for handoff to some cell communicates over a channel x and that cell is not allowed to use channel x. In this condition a normal handoff is not possible, but it is possible if the user’s current base-station could signal to the destination cell giving it permission to communicate with it over channel x[56]. One major constraint that in channel carrying approach should be taken care is that, the movement of channels should not lead to any extra co-channel interference or channel locking[24]. In channel carrying scheme[24], the mobility of channels depends completely on localized information, without any global coordination. Two approaches -- channel reservation[132-133] and queuing[131] are integrated in scheme[24], to improve the handoff blocking probability and the overall channel utilization. In scheme[24], it is allowed that the channels to be carried into a neighboring cell without violating the minimum reuse distance requirement. In this handoff scheme, channel coordination is achieved locally, with prior arrangement of channel movement. For example let N denote the total number of distinct channels that are available in the cellular system. In the conventional fixed channel assignment scheme, channels are assigned such that the same channels are reused exactly r cells apart, where r is the minimum reusable distance. Therefore, the total number of distinct channels available for each cell is N/r. This channel assignment is referred as r-channel assignment. In the channel carrying scheme[24], handoff call blocking is reduced by allowing calls to “carry” channels from one cell to another. If in scheme[24] r-channel assignment is used, then a call that carries a channel to an adjacent cell may violate the minimum reuse distance requirement. Therefore, to ensure that the minimum reuse distance requirement is not violated, authors in[24] have used an (r+1) channel assignment scheme.

In channel allocation and admission control scheme proposed in[125], the concept of shadow cluster is used , with the objective of reducing the call-dropping probability by predictive resource allocation. The scheme in[125] , estimate future resource requirements and perform admission control to minimize the handoff dropping probability This scheme, not only focus on voice traffic, but also consider multimedia traffic with varying requirement of connection bandwidths, traffic loads, and user’s mobility. Concept of shadow cluster is to represents a set of cells around an active mobile. Also, this scheme required each base station in the shadow cluster to predict future resource demands according to the information about active mobile user’s bandwidth requirement, position, movement pattern, and time. Also scheme[125] uses, precise knowledge of each user mobility in terms of location and time, as an important parameter for evaluating resource requirements.

An adoptive handoff handling scheme proposed in[29], provide appropriate QoS according to service requests from end users, under the constraint of limited and varying bandwidth resources. The main features of this scheme are:

i. It is based on a comprehensive service model consisting of three service classes, handoff-guaranteed, handoff-prioritized, and best-effort,

ii. It deploys different resource-reservation schemes adaptively for real-time service classes (i.e., handoff- guaranteed and handoff-prioritized) to guarantee their connection-level QoS through a connection-oriented virtual-circuit service,

iii. It uses an efficient dynamic call-admission-control scheme to meet the target handoff-dropping probability of real-time services and

iv. It exploits the rate-adaptive feature of multimedia applications to further improve the efficiency of resource utilization.

In scheme[29] authors have categorize applications to the following three classes:

i. Handoff-guaranteed service represents real-time applications that require absolute continuity,

ii. Handoff-prioritized service represents real-time applications that can tolerate a reasonably low handoff-dropping probability, and

iii. Best-effort service represents nonreal-time applications that do not need a minimum bandwidth to set up a connection.

In[29], three types of real-time multimedia traffic, i.e., voice, audio, and video are considered for simulation study. It is considered that each required one, two, and four channels from the network, respectively. For simulation, among the generated handoff-guaranteed and handoff-prioritized calls, 50% as voice, 25% as audio, and the re-maining 25% as video applications are randomly selected [[29]. The comparative performance simulation [[29] results in terms of the new call-blocking probability, the handoff-dropping probability, for adaptive and nonadaptive applications are shown in figure. It is evident from the simulation results[29], that the adoptive scheme proposed in[29] performs better in terms of handoff dropping probability and new call blocking probability.

In the predictive channel allocation (PCR) scheme [134], channel allocation decisions are based on the prediction (extrapolation) of the motion of MS’s. Each MS periodically measures its position and orientation. It is based on real-time position measurement and movement extrapolation. In this scheme, position measurement is made by using GPS. The user orientation is obtained by using the vector of two consecutive position measurements taken over a short time. Authors in[134] have also discussed different variations of PCR based obtained based on different channel reservation pooling mechanisms. The predictive and adaptive scheme proposed in[128], estimates user’s mobility and history of handoffs occurrence in each cell. This scheme, reserves some bandwidth in each cell only for possible handoff calls handling. The bandwidth to be reserved for hand-offs is calculated by estimating the total sum of fractional bandwidths of the expected hand-offs within a mobility-estimation time window. This scheme uses the user mobility prediction for predicting mobile’s directions and hand-off times in a cell by considering variations in the path/location information available from the direction-finding system. In this scheme, any handoff call carries information about the time when user move from current cell, the time duration of the user was active in the current cell. This information is used by the target BS in which handoff call is to be handled, to build hand-off estimation function[128].

The handoff priority based scheme proposed in [141] assumes the traffic model which follows the blocked-calls-cleared queuing discipline. An incoming call is served immediately if a free channel with an appropriate power level is found, otherwise the new call is blocked and not queued. This scheme gives priority for real time handoff calls.

The scheme proposed in [136] divide the service calls into four different types as real time originating calls, real time handoff calls, non-real time originating calls and non-real time handoff calls. Also it reserves some channels exclusively for real time handoff calls, some channels are reserved for both real time and non-real time originating calls. There are common channels which may be acquired by any type of call. A real time handoff call in the queue is deleted when it is served or when it crosses the handoff area before getting a channel. But when the non-real time handoff call in the queue crosses the handoff area, then it is transferred to the new base station. Hence it avoids the packet loss. In [136] it is observed that the dropping probability of real time and non-real time handoff calls are negligibly small in the case of dynamic queue size, i.e., queue size is also important to evaluate the dropping probability. Hence it is chosen such that it is not too large or too small. In the scheme, the queue size of real time handoff calls and originating calls are kept less than the queue size of non-real time handoff calls because the real time handoff calls in queue are dropped when they cross the handoff area before getting the channel. The non-real time handoff calls are forwarded to the new base station.

13. Channel Allocation and Power Control

Unlike a wired communication medium, a wireless physical channel cannot be abstracted using a few simple perlink (nontime varying) parameters, such as propagation delay or link capacity. In a wireless network, signal power from awireless transmitter is broadcast into space, rather than confined within a wire. Hence the transmitted signal is considerably attenuated over a distance, depending on the combination of path loss, shadowing, fading, etc. [140].

In any channel assignment algorithm, one necessary condition is to maintain a certain level of carrier-to-interference ratio (CIR) while assigning channels user. Power control and channel allocation can be considered as two sides of a coin. Power control schemes play an important role in the channel allocation in cellular networks. The idea behind power control schemes is based on the fact that the CIR at a wireless terminal is directly proportional to the power level of the desired signal and inversely proportional to the sum of the power of co-channel interferers. There are many schemes of channel allocation based on power control are proposed in literature [138,140-142].The main objective of power control schemes are to, try to reduce the overall CIR in the system by measuring the received power and increasing/decreasing the transmitted power in order to maximize the minimum CIR in a given channel allocation of the system[138,140,142] , so that capacity of the system can be increased. The purpose of different power control schemes is to adjust a trade-off between the change of power level in opposite directions.

In paper [141] a scheme based on an integer linear program (ILP) formulation has been used to optimally solve the combined channel assignment and power control problem in wireless cellular networks. This scheme ensures that the CIR requirements are met, not only for the new incoming call but also for all ongoing calls using the same channel. In case of not meeting of CIR requirements of all ongoing calls, the new call is simply blocked, which means more importance is given to handoff calls in this scheme. Also this scheme assigns an appropriate power level to the incoming call and all ongoing calls by maintaining CIR through using the selected channel such that the overall power consumption is minimized. Doing so significantly reduces the call blocking probability. Also a scheme is proposed in [140] to minimizes power consumption and maximizes user-perceivable QoS. It is to note that adjusting the transmit power involves a certain amount of time delay, in reaching the transmit power to a specified level. The packet loss rate for wireless networks is much higher than that for wired networks due to the physical characteristics of wireless networks such as channel interference. One way of improving the BER in wireless networks, is to increase the transmit power. For improving BER it is also necessary to properly incorporate the relationship between the channel-interference level and the BER to maximize the channel-power utilization and the user-perceivableQoS. One interesting point to note that, due to varying degree of QoS requirements of individual packets in multimedia streaming some time an improving BER also does not result in improved user perceivable QoS[ 140]

In the scheme [142], HQ(High Quality) packets and LQ(Low Quality) packets are queued into individual buffers. The resource allocation is carried out on the HQ and LQ packets separately through their separate buffers with the objective of minimizing the total transmit power. Considering that energy efficiency is one of focuses in future wireless systems, a novel resource allocation scheme is proposed in[142] with the objective to minimize the total transmit power by using multiple BER constraints in resource allocation formulation.

In the wireless communication systems the most important question has become: how to provide ubiquitous seamless coverage for all the users in the network in a cost-efficient manner while at the same time satisfy high data rates and the Quality of Service (QoS) requirements by the Next Generation Network (NGN). Also the NGN is expected to integrate triple-play services, such as all traffic classes of voice, video and data , with the particular Quality of Service (QoS) requirements, such as strict packet delay, jitter and loss guarantees. The NGN will be using Internet as the major backbone network i.e. fourth generation (4G) is proposed to be fully IP centric [138]. Despite amazing advancements in wireless communication technology, still there are many technical challenges. These include high bit-error rates (BERs) and channel interference. Also it is very important for NGN to have dynamically changing information of the requirements of the users and the system load distribution. Many of the channel allocation algorithms reported in the literature does not consider these information together. The accurate knowledge of the type of services i.e. real time/non-real time, multimedia/non multimedia etc. and the system load distribution are very essential for offering QoS in NGN [ 138,139].

14. Conclusions

Due to applicability and effectiveness of the services, in the area of wireless communications, in recent years, the wireless resource allocation problem has received tremendous attention. As a consequence of it, vast amount of innovations taken place, which introduced a large number of new techniques for solving channel allocation problem. Also, a large number of researches have been done to extend the earlier work with objective of improving QoS level of services. Most of the recent work has been in the area of multiclass services, distributed, adaptive, priority-based, and overlay channel allocation schemes. Some schemes for channel allocation, based on genetic algorithms with some modifications in basic genetic algorithm are reported in literature. These schemes are able to address issue of QoS such as reliability and other service QoS, partially. Some research in the area of cellular system with mobile base stations are also reported in the literature. In literature, a vast amount of results have been published which provide an insight into the QoS, complexity, and reliability of system of different channel allocation algorithms. In this paper, we have provided a survey of the channel allocation problem in cellular systems and presented a detailed and comparative discussion of the major channel allocation schemes including different FCA, HCA and DCA schemes. We have discussed and compared different approaches used for channel allocation, including, centralized approach, distributed approach, relaxed mutual exclusion approach and genetic algorithm approach etc.

Acknowledgements

Authors are thankful to University Grant Commission India, for financial assistance to Prof. P.C. Saxena as an Emeritus Fellow. Authors are also thankful to the anonymous reviews for their valuable comments and suggestions.