Abstract: This study presents the performance of call admission control and resource reservation schemes in WCDMA cellular systems with multi-class traffic and non-uniform traffic distribution among cells. In order to minimize the handoff dropping probability, the mobility of the user is predicted based on the mobility history of users. The mobility prediction scheme used in this research is based on computational learning theory, which has shown that prediction is synonymous with data compression. In order to utilize resource more efficiently, we predict not only the cell to which the mobile will handoff but also the time of occurrence of handoff. Based on the mobility prediction, resource is reserved in terms of Signal to Interference Ratio Guard margin (SIRGM) to guarantee a defined target handoff dropping probability. It is considered that the traffic distribution is non uniform among cells and some amount of resource is reserved for the traffic originated in the neighboring cells. Three types of traffic i.e., voice, audio, video each requiring different data rates are considered. The admission threshold is adaptively controlled to achieve a better balance between guaranteeing handoff dropping probability and maximizing resource utilization. Simulation results show that the mobility based resource reservation scheme outperforms the static-reservation scheme.
INTRODUCTION
The wide-band CDMA (W-CDMA) technology has emerged as the main air interface for 3G wireless systems, which promises to provide a transmission rate from 144 Kbps to 2Mbps, enabling multimedia services as those provided by broadband wired networks. The Radio Resource Management (RRM) module in the cellular network system is responsible for efficient utilization of air interface resources and guarantee a certain QoS level to different users according to their traffic profiles. The Call Admission Control (CAC) mechanism is one of the most important components of RRJ\.1. The radio Resource– reservation Estimation (RRE) mechanism helps CAC to decide the ammmt of resource (Signal to Interference Ratio Guard Margin) to be reserved in order to provide QoS guarantees to mobile users throughout the lifetime of the connection and also to resolve the inter-cell rmbalanced traffic problem. The amormt of SIR margin to be reserved in a cell depends on the mobility of the users in all the neighboring cells and also the traffic distribution.
As it is impractical to completely eliminate handoff call dropping, the best one could do is to keep the handoff dropping probability Phd below a target level. Moreover, maximizing resource utilization while keeping Pnb, the probability of new call blocking, below a target value, is another critical factor for evaluating CAC algoritlnns. Based on the above considerations, several schemes have recently been proposed for CAC in wireless cellular networks. The guard channel policy (Lu and Bharghavan, 1996) and fractional guard channel policy (Naghshineh and Schwartz, 1996) determine the number of guard channels for handoffs by considering just the status of the local cell. Users are assumed mriformly located in any cell of the mobile network nnder these polices. The distributed call admission control scheme (Papoulis, 1991) considers not only the status of the local cell but also that of adjacent cells. The shadow cluster scheme (Lu and Bharghavan 1996) estimates future resource requirements in a collection of cells in which a mobile is likely to visit in the future. Admission control is performed based on this estimate. However, this proposal lacks a mechanism to determine the shadow cluster in real networks, as it assumes either precise knowledge of user mobility or totally random user movements.
There have also been some research efforts to predict user mobility. In the study by Fang and Chlamtac (1999). the next cell to which a mobile will move is predicted in an indoor envirornnent. But this scheme does not estimate chmel holding time and therefore cannot be directly applied for efficient bandwidth reservation. In the study by Chao and Chen (1997). user mobility is estimated based on the aggregate history of handoff observed in each cell. The scheme assumes that each mobile will handoff to neighboring cells with equal probability in the mobility– estimate-time-window. This assumption may not be accurate in general. In this study, CAC and resource reservation schemes based on the probabilistic prediction of user mobility rmder more realistic assumptions, is analysed. In the mobility prediction approach used in this research, not only the cells where the mobile users will handoff but also when it will handoff are predicted.
MODEL DESCRIPTION
We consider a mobile commrmication network with a cellular wireless infrastructure. A handoff could fail due to insufficient bandwidth in the new cell, causing the handoff call to be dropped. We describe the network topology, channel holding time distribution and user mobility pattern considered in our study in the following subsections.
The capacity of a CDMA system is limited by the total interference it can tolerate, which is called the interference-limit system. Users with different traffic profiles and attributes, such as the service rate, the Signal-to-interference Ratio (SIR) requirement, media activity, etc., introduce a different amormt of interference to the system. The signal to interference Guard Margin (SIRGM) is a mtural extension of the guard channel idea developed in the context of TDMA/FDMA systems by considering the load factor for system capacity estimation in CDMA systems. The amount of SIRGM is dynamically adjusted by the RRE module.
Network topology: In solving the CAC and bandwidth reservation problems, the cellular network is modeled as a connected graph G = (V, E), where the vertex-set V represents the set of base stations, each serving a single cell and the edge-set E represents the adjacency between pairs of cells. Figure 1 shows an example network representation with vertex-set V ={a, b, c, ..., n} and edge– set E ={(a. b). (a. c),..., (n, 1)}.
| Fig. 1: | Modeling an actual cellular network |
Channel holding time: The channel holding time is defined as the time during which a new or handoff call occupies a channel in a given cell and it is dependent on the mobility of the user. While this is similar to the call holding time in the fixed telephone network, it is often a fraction of the total call duration in a wireless cellular network and need not have the same statistical properties (Jedrzycki and Leung. 1996; Langdon, 1983). Most research work on CAC and bandwidth reservation assumes the channel holding time follows an exponential distribution (Fang and Chlamtac. 1999; Viterbi. 1995). which is independent and identically distributed for all cells. We assume that the channel holding time follows a general distribution, which allows the i.i.d. exponential channel holding time assumption to be relaxed.
User mobility pattern: The symmetric random walk model has been quite popular among researchers in characterizing individualmovementbehavior (Papoulis. 1991; Viterbi. 1995). In such a model. a mobile user will move to any one of the neighboring cells with equal probability after leaving a cell. This model does not take into accormt the trajectory and channel holding time of a mobile. In cellular mobile networks, the mobility of a user during a call can be represented by a sequence of events, N, H1 H2 H3 , ... Hn ,... E, where N represents the event that a new call is admitted, Hn represents the event of a mobile’s nth handoff and E represents the call termination event. Note that in some cases, there are no handoff events during the lifetime of a call and thus no Hn in the sequence of events. In this sequence, N = (m, i, t), where m represents the mobile requesting the call, i represents the original cell and t represents the time when the call arrives; Hn= (Tk, i ), where Tkis the relative time elapsed since the beginning of the call and ‘i’ is the cell to which the mobile will handoff and E (Tk ). We quantize the relative time into slots of equal duration T, a design parameter. So, Tk is the kth time slot since the beginning of the call. In general, a mobile user usually travels with a specific destination in mind.
So, the mobile’s location and channel holding time in the future are likely to be correlated with its movement history. Therefore, in our model, the sequence of events N, H1 H2 H3 , ... Hn ,... E, is assumed to be generated by a mth order Markov source, in which the states correspond to the contexts ofthe previous m events. The probabilities of possible next events can depend on a list of m previous events.
Mobility prediction: In this study, the LZW (Lempel- Ziv– Welch) algorithm for data compression is used for predicting the mobility. The equivalent character-based LZW algorithm builds in an online fashion a probabilistic model (or a tree) that feeds probability information to an arithmetic coder , which encode a sequence of probability of p using bits.
The sequence of events N, H1 H2 H3 , ... Hn ,... E, during the lifetime of a call corresponds to the substring in the LZW algorithm. The mobility database of every mobile at a specific time holds a Mobility Tree, which is a probability model corresponding to that of the LZW algorithm. Each node except for the root in the Mobility Tree preserves the relevant statistics that can be used to predict the probability of following events. As in data compression, the Mobility Tree of the mobile is built in an online fashion.
When a mobile requests a new call, the predictor sets the current node to the root of the tree according to the mobile, cell and time and calculates the probabilities of all possible events of this mobile. On seeing the actual event of the mobile, the predictor walks down the tree and is ready to predict again. When an event is not in the Mobility Tree, a prediction fault is generated and the tree is updated. Figure 2 shows an example Mobility Tree of mobile mat cell a in the time interval 8:00-9:00 a.m.
| Fig. 2: | A mobility tree used for mobility prediction |
When the mobile requests a new call in cell a in the time interval 8:00-9:00 a.m., we can use the statistics preserved in the nodes of its Mobility Tree to predict the probabilities of the next possible events of this mobile: it will terminate the call without handoffs in the 2nd time slot with probability of 2/56, handoff to cell b in the 2nd time slot with probability of 15/56, etc.
Implementation of the mobility prediction scheme: The above mobility prediction scheme maintains the statistics in a tree. An important issue is how this model can be implemented. In fact, a tree is a multi-way tree with a path from the root to a unique node for each string represented in the tree. There are many ways to implement the nodes of a tree. The fastest approach is to create an array of pointers for each node in the tree with a pointer for each character of the input alphabet. This method can waste considerable memory space. An alternative is to use a linked list at each node, with one item for each possible branch. This uses memory economically, but can be more processing intensive. Some improvement may be achieved by moving an item to the front of the list each time it is used. In practice, in order to reduce the memory and computation complexity, it is desirable to limit the number of statistics used for mobility prediction. A sliding window may be used to ensure that only the most recent statistical data are involved in mobility prediction and the old data are discarded.
CALL ADMISSION CONTROL AND SIR MARGIN RESERVATION
Calculation of Pi, j(Tk : Our approach is based on the predicted mobility of each user. We calculate Pi,j(Tk), the probability that a mobile originally in cell i will visit cell j during time slot Tk. From the Mobility Tree, we can see that a mobile taking different paths can visit certain cell in the same slot. Using total probability theorem (Ramjee et al., 1996), we must add all of these probabilities to get Pi,j(Tk). We show by an example how to get this probability.
Example : A mobile m requests a new call at cell a in the time interval 8:00-9:00 a.m. From the Mobility Tree in Figure 2, we can see that m can take several different paths to visit cell b. We describe these paths by sequences of events:
Path 1: N(m, a, 8:00-9:00 a.m.), H(T1 b), E(T2 )
By Path 1, m will v isit cell b in T1 and T2 with probability:
(3/56)x(3/3) = 3/56
Path2: N(m, a, 8:00-9:00 a.m.), H(T2, b), E(T4 ).
By Path 2, m will visit cell b in T2, T3 and T4
with
probability (15/56)x(5115) 5/56
Path3: N(m. a. 8:00-9:00 a.m.). H(T2,b). H(T2, d)...
By Path 3. m will visit cell b in T2 with probability: (15/56)x(6115)
6/56
Path4: N(m. a. 8:00-9:00 a.m.). H(T2, b). H(T5, d)...
By Path 4, m will visit cell b in T2, T3, T4
and T5 with
probability (15/56)x(4115) 4/56.
So. Pa.b(T1) 3/56 Pa.b(T2) (3/56)+(5/56)+
(6/56)+(4/56) 18/56
Pa.b(T3) (5/56)+(4/56) 9/56,
Pa.b(T4) (5/56)+(4/56) 9/56 and
Pa.b(T5) 4/56
The Most Likely Cell-Time (MLCT): When a mobile is active in cell i, we can get the Most Likely Cell-Time (MLCT) of that mobile, a cluster of time mrits at a cluster of cells when and where a mobile will most likely visit in the future. We select cells and time slots with Pi.j(Tk) greater than MLCT threshold, a design parameter, to form the MLCT of this mobile.
Call admission control and SIR reservation for new calls: When a new
call arriving at mobile m with a signal to interference ratio requirement
Based on these values, the new call will be admitted if the following holds:
where, α is the admission threshold and should be controlled adaptively.
When a new call is admitted, signal to interference ratio is reserved in the
mobile’s MLCT. Let
The reserved SIR is:
The second term in the above expression indicates the ammmt of resource reserved for the traffic originated in the neighboring cells. The availability of SIR in MLCT is updated accordingly.
Adaptive control of admission threshold: The mobility prediction frmctions may not work well for some mobile users, especially those who do not have favorite routes. Moreover, if α is too small, the handoff dropping probability may exceed the target value; if a is too large, resource utilization will be decreased. So, admission threshold should be controlled adaptively. We calculate Phd(m). the handoff dropping probability of mobile m. by dividing the number of himdoff drops to the total number of its calls in the recent history. Let Phd, target(m) denote the target value of himdoff dropping probability of mobile m. If Phd(m) <Phd, target(m). admission threshold is decreased by ε, a design parameter; otherwise, is increased by ε. By adaptive control of α, we can achieve a better balance of guaranteeing Phd and maximizing resource utilization.
Call admission control and resource reservation for handoff calls: When
a mobile m, with SIR requirement
SIMULATION RESULTS AND DISCUSSIONS
In this section, we present and discuss the simulation results of this admission control scheme and its performance is compared with static reservation scheme. We consider each base station is surrmmded by 6 neighbors on an average. The distance between two base stations is 2 kms. Since most mobile users have favorite routes, we assume that each mobile user has 5 possible different paths in the network. The user will take these 5 paths with probability of 0.5. 0.2. 0.1. 0.1 and 0.1. respectively.
Among the cells within a path, mobile users can have a new call request with equal probabilities. During a call, the mobile will stay at the original cell or move along the path. If a call does not terminate when the mobile reaches the end of the path. it will stay at the end cell of that path. The path is generated as following: (1) Select two nodes in the graph randomly as original and destination nodes; and (2) Whenever the mobile user leaves the current cell, it moves to a neighboring cell which is closest to the destination.
| Fig. 3: | Pnb and Phd vs offered load (Low user mobility) |
| Fig. 4: | Pnb and Phd vs offered load (Medium user mobility) |
| Fig. 5: | Pnb and Phd vs offered load (High user mobility) |
Note that two paths with at least one edge not in common are different paths and different mobile users can have the same paths.
Also, we have the following assumptions in our model:
| • | A call is either a voice (requiring 7 dB) or audio requiring 10 dB). video (requiring 12 dB).. |
| • | Call duration is same for all calls and exponentially distributed with mean value of 120s. |
| • | Call requests are generated according to a Poisson process with rate λ (call/cell/second). |
| • | Three cases of mobility are considered: low user mobility, in which case the speeds of mobiles are rmiformly distributed between 0 and 40 kms h-1; medium user mobility with the speeds from 40 to 80 kms h-1. |
| • | The target hand off dropping probabilities are the same for all mobiles: Phd0.04. |
| • | MLCT threshold 0.08. admission threshold is initialized to 1 in each simulation and adaptive factor0.02. |
The offered load is calculated as follows:
where Pvoice is the percentage of voice in the offered traffic.
Simulations start without any pre-memorized information of mobiles. Long-term handoff dropping probability, new call blocking probability and utilization are obtained from the simulation. During each simulation, a Mobility Tree is constructed for each mobile and its mobility is predicted. Based on the prediction, a MLCT is constructed. Then CAC will check the availability of SIR margin and decide to admit or reject the new call and handoff call requests using the algorithms described in the previous section. If the call is admitted, SIR margin is reserved in the mobile’s MLCT accordingly. Figure 3-5 show Pnb and Phd as frmctions of the offered load for three different cases.
| Case 1: | Pvoice = 1; Paudio = 0: Pvideo = 0 |
| Case 2: | Pvoice = 0.8; Paudio = 0.1: Pvideo = 0.1 |
| Case 3: | Pvoice 0.5; Paudio 0.25: Pvideo 0.25 |
in the low mobility .medium mobility and high mobility cases.
The probabilities ofhandoff dropping are kept below the target values 0.04 irrespective of the offered load, Pvo!ce and user mobility. This shows that the proposed CAC and the resource reservation schemes achieve one of our goals: Keeping Phd below a target level. We also observe that the Pnb and Phd increase as Pvo!ce decreases rmder the same offered load. This is because the data traffic needs more SIR.
| Fig. 6: | Comparison with static reservation (7 dB) |
| Fig. 7: | Comparison with static reservation (10 dB) |
We also compare the proposed CAC and resource reservation schemes with static-reservation scheme (Sheinwald, 1994; Ganguly et al., 2003). In the static– reservation scheme, a SIR margin is reserved permanently for handoff calls. In our simulation, we consider SIR margin of 7 dB, 10 dB are reserved permanently for handoff calls in each cell. SIR margin is reserved in cells which the mobile will visit during the entire lifetime of the call.
Figure 6 and 7 show that the static-reservation scheme with 7 dB and 10 dB reserved for handoff calls can keep Phd below the target value of 0.04 when the network has a light load, but the reserved SIR margin 1s not enough when the offered load becomes heavier. Hence, this scheme carmot achieve the design goal. Although the static-reservation scheme has almost the same Phd compared with our scheme when the network load is lighter, its Pnb is higher in this area, i.e., it admits less new calls than our scheme for any given Pnb. In the static reservation scheme, Phd may be kept below the target value by statically reserving more bandwidth for handoff calls. However, this will result in higher Pnb, which means lower utilization if Pnb were to be reduced to an acceptable level. Based on the mobility prediction, we can reserve the SIR margin more efficiently. From these results, we can see that our scheme achieves better performance m terms of dropping probability and resource utilization.
CONCLUSIONS
In this study, the performance of the call admission control and resource reservation schemes for WCD:MA cellular mobile system with multi class traffic of non uniform distribution is analyzed based on assumptions more realistic than existing proposals. This scheme is applicable to arbitrary cell topologies and the channel holding time can follow a general distribution. The sequence of events of new call admission, handoffs and call termination is generated by stationary mth order Markov sources. The probabilistic predictions of next events based on the mobility history of users is derived using LZW algorithm which is an optimum algorithm in data compression. Based on the mobility prediction of the next cell, the time at which handoff will take place, type of traffic and also based on the user distribution, call admission control and SIR margin reservation schemes have been developed. The performance of the schemes have been analysed using computer simulations. The results show that these schemes can achieve a better balance of guaranteeing handoff dropping probability while maximizing resource utilization and they outperform the static-reservation. From the analysis it is found that, the performance improvement of the call admission control algorithm achieved with the dynamic reservation is about 11% over the static reservation with 7 dB and the improvement is only 3% with the static reservation 10 dB under heavy load. The performance improvement of this scheme with dynamic reservation is not very much significant when the static reservation is very high under lightly loaded condition.