UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Quality of service provisioning in cellular mobile networks Yu, Fei 2003

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
ubc_2003-860094.pdf [ 5.62MB ]
[if-you-see-this-DO-NOT-CLICK]
Metadata
JSON: 1.0065555.json
JSON-LD: 1.0065555+ld.json
RDF/XML (Pretty): 1.0065555.xml
RDF/JSON: 1.0065555+rdf.json
Turtle: 1.0065555+rdf-turtle.txt
N-Triples: 1.0065555+rdf-ntriples.txt
Original Record: 1.0065555 +original-record.json
Full Text
1.0065555.txt
Citation
1.0065555.ris

Full Text

Quality of Service Provisioning in Cellular Mobile Networks by FEI YU M.A.Sc, Beijing University of Posts and Telecommunications, 1998 B.A.Sc, Dalian University of Technologies, 1995 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA Oct. 2003 © Fei Yu, 2003 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department The University of British Columbia Vancouver, Canada DE-6 (2/88) Abstract In recent years, tremendous growth has occurred in the use of cellular mobile communica tions around the world. This thesis studies Quality of Service (QoS) provisioning in cellular mobile networks. In order to guarantee the handoff dropping probability of mobile users in cellu lar networks, call admission control and bandwidth reservation schemes are proposed based on more realistic assumptions than those made in existing proposals. A mobility prediction scheme is derived from data compression techniques that are both theoretically optimal and good in prac tice. In order to utilize resources more efficiently, the proposed scheme predicts not only which cell the mobile will handoff to but also when the handoff will occur. Based on the mobility predic tion, bandwidth is reserved to guarantee a given target handoff dropping probability. Simulation results show that the proposed schemes meet our design goals and outperform the static reserva tion scheme. We also develop a framework of combining QoS provisioning and mobility management in cellular mobile networks. The key component of this framework is a common mobility predic tion scheme, which can be used in both locating/paging mobiles and in making admission deci sions. Novel QoS provisioning and mobility management schemes are proposed in this framework. The performance of the proposed schemes is evaluated using simulations. Adaptive multimedia applications that can operate over a wide range of available band-widths are expected to be used in future cellular mobile networks. We present a QoS provisioning scheme in adaptive multimedia cellular networks via reinforcement learning. The proposed scheme does not require explicit state transition probabilities, and therefore, the underlying assumptions of this scheme are more realistic than those in previous schemes. Simulation results ii demonstrate the superior performance of the proposed scheme over some of the existing methods. Finally, call admission control for cellular-to-Internet protocol (IP) internetworking is studied. In order to provide QoS to the Internet and avoid scalability problems, several recent papers propose endpoint measurement-based admission control (EMAC) scheme. Although EMAC has many desirable features in the wireline networks as shown in previous work, in this thesis, we show that several distinct characteristics in cellular mobile networks make EMAC dif ficult to implement. A novel mobile-EMAC (M-EMAC) scheme for cellular-to-IP internetwork ing is proposed. Simulation results show that M-EMAC outperforms EMAC in cellular mobile networks. Ul Table of Contents Abstract ii List of Figures viiList of Tables xGlossary xii Acknowledgements xviChapter 1 Introduction 1 1.1 QoS Provisioning in Cellular Mobile Networks 1 1.2 Overview of Related Work 4 1.2.1 Call Admission Control for Non-Adaptive Traffic 4 1.2.2 Mobility Management 5 1.2.3 Call Admission Control and Bandwidth Adaptation for Adaptive Traffic 6 1.2.4 QoS Provisioning in the Internet 7 1.3 Motivations 8 1.4 Main Contributions 11 1.5 Organization of the Thesis 3 Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 14 2.1 Introduction 12.2 Model Description 4 2.2.1 Network Topology 15 2.2.2 Channel Holding Time 6 2.2.3 User Mobility Pattern , 17 2.3 Mobility Prediction 18 iv 2.3.1 Optimal Data Compression 19 2.3.2 Mobility Prediction 21 2.3.3 Analysis of the Mobility Prediction Scheme 22 2.3.4 Implementation Considerations 25 2.4 Call Admission Control and Bandwidth Reservation 27 2.4.1 Calculation of P(i,j, Tk) 22.4.2 The Most Likely Cell-Time 8 2.4.3 Bandwidth Reservation 29 2.4.4 Call Admission Control and Bandwidth Reservation for New Calls 30 2.4.5 Adaptive Control of Admission Threshold 32.4.6 Call Admission Control and Bandwidth Reservation for Handoff Calls 31 2.5 Simulation Results and Discussions 32.6 Summary '. 5 Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 39 3.1 Introduction 33.2 Common Mobility Prediction Scheme 39 3.3 Mobility Management in the Combined Framework 42 3.3.1 The Original Path-Based Scheme 43.3.2 The New Path-Based Scheme 3 3.3.3 Simulation Results and Discussions 45 3.4 Call Admission Control in the Combined Framework 46 3.4.1 Time Interval Prediction 47 3.4.2 Call Admission Control Scheme 50 V 3.4.3 Simulation Results and Discussions 52 3.5 Summary 54 Chapter 4 QoS Provisioning for Adaptive Multimedia 60 4.1 Introduction 64.2 QoS Provisioning in Adaptive Framework 62 4.2.1 Adaptive Multimedia Applications4.2.2 Adaptive Cellular Mobile Networks 63 4.2.3 QoS Provisioning in Adaptive Framework 64 4.2.4 Average Reward RL 66 4.3 Average Reward RL for Solving SMDP 67 4.3.1 Average Reward SMDP : 67 4.3.2 Solving the Average Reward SMDP Using RL 69 4.4 Formulation of QoS Provisioning in Adaptive Framework 72 4.4.1 State, Actions and Rewards 74.4.2 Constraints 75 4.4.3 Exploration 8 4.4.4 Trading off Action Space Complexity with State Space Complexity 79 4.5 Implementation Considerations 81 4.5.1 Approximate Representation of Action Values 81 4.5.2 Structure and Pseudo-code 82 4.6 Simulation Results and Discussions 3 4.7 Summary 90 Chapter 5 M-EMAC for Cellular-to-IP Internetworking 99 VI 5.1 Introduction 99 5.2 EMAC Scheme for the Internet 100 5.3 EMAC in Cellular Mobile Networks 101 5.3.1 Low Bandwidth 102 5.3.2 User Mobility 7 5.3.3 High Bit Error Rate 109 5.4 Mobile-EMAC for Cellular-to-IP Internetworking 110 5.4.1 UMTS QoS Management Functions 111 5.4.2 Mobile-EMAC Scheme 112 5.4.3 Performance Evaluation 4 5.5 Summary 116 Chapter 6 Conclusions 9 6.1 Summary 116.2 Further Work 121 Bibliography 123 vn List of Figures Figure 2.1 Modeling an actual cellular network 16 Figure 2.2 The trie constructed in Example 2.1 20 Figure 2.3 A pseudo-code of the mobility prediction scheme 22 Figure 2.4 A mobility trie used for mobility prediction 23 Figure 2.5 Implementation of trie nodes in Figure 2.2: (a) array and (b) linked list...26 Figure 2.6 and Phd vs. offered load 3Figure 2.7 Utilization vs. offered load 6 Figure 2.8 Pnd vs. simulation time with different values of time slot duration 37 Figure 2.9 Utilization vs. offered load with different values of time slot duration 37 Figure 2.10 Comparison with static reservation (4 BUs) 38 Figure 2.11 Comparison with static reservation (5 BUs) 38 Figure 3.1 The trie constructed in Example 3.1 41 Figure 3.2 The original path-based scheme 3 Figure 3.3 The proposed path-based scheme ; 44 Figure 3.4 Location update performance gain vs. call-to-mobility ratio 56 Figure 3.5 Paging performance gain vs. call-to-mobility ratio 56 Figure 3.6 Hyperbolic positioning in E-OTD, N= 3 .57 Figure 3.7 Pnb and Phd vs. offered load 5Figure 3.8 Pnd vs. simulation time with different values of adaptive factor 58 Figure 3.9 Comparison with YL01 and one of OKS98 schemes 58 Figure 3.10 Comparison with YL01 and one of OKS98 schemes 59 Figure 3.11 Pnd vs. simulation time in YL01 and proposed scheme 59 viii Figure 4.1 Radio bearer reconfiguration in UMTS 63 Figure 4.2 A reinforcement learning model 70 Figure 4.3 The neural network used in approximation 81 Figure 4.4 The structure of the QoS provisioning scheme 82 Figure 4.5 A pseudo-code of the QoS provisioning scheme 83 Figure 4.6 A cellular network used in simulations 84 Figure 4.7 Normalized average rewards 91 Figure 4.8 Normalized average rewards vs. adaptation operation cost 91 Figure 4.9 Handoff dropping probabilities 92 Figure 4.10 New call blocking probabilities of class 1 calls 92 Figure 4.11 New call blocking probabilities of class 2 calls 93 Figure 4.12 Normalized average bandwidths of class 1 calls 93 Figure 4.13 Normalized average bandwidths of class 2 calls 94 Figure 4.14 Normalized bandwidths variance of class 1 calls 94 Figure 4.15 Normalized bandwidths variance of class 2 calls 95 Figure 4.16 Normalized average rewards for different average bandwidth requirements 9Figure 4.17 Normalized average rewards for different bandwidth variance requirements 96 Figure 4.18 Normalized average rewards with non-uniform traffic 96 Figure 4.19 A traffic pattern of a typical business day 97 Figure 4.20 Normalized average rewards with time varying traffic 97 Figure 4.21 Normalized average rewards with convex reward function and non-uniform traffic 98 Figure 5.1 EMAC scheme for the Internet 100 ix Figure 5.2 Out-of-band probing in the wireless model 105 Figure 5.3 Out-of-band.probing in the wireline model 106 Figure 5.4 In-band probing in the wireless model 107 Figure 5.5 In-band probing in the wireline model 108 Figure 5.6 Retransmissions of RLC blocks 110 Figure 5.7 QoS management functions for the UMTS bearer service in control plane 112 Figure 5.8 Mobile-EMAC , 113 Figure 5.9 Mobile-EMAC procedure 114 Figure 5.11 Loss-load curves of M-EMAC and EMAC (probing 20 s) 118 Figure 5.10 Loss-load curves of M-EMAC and EMAC (probing 5 s) 118 X List of Tables Table 4.1 Experimental parameters 84 Table 4.2 Number of numerical operations 90 Table 5.1 Simulation parameters of traffic source 1 103 Table 5.2 Simulation parameters of traffic source 2 103 xi Glossary Acronyms 3G - 3rd Generation 3GPP - 3rd Generation Partnership Project BA - Bandwidth Adaptation BER - Bit Error Rate BS - Bearer Service BTS - Base Transceiver Station BU - Bandwidth Unit CAC - Call Admission Control EDGE - Enhanced Data Rate for GSM Evolution EMAC - Endpoint Measurement Based Admission Control E-OTD - Enhanced Observed Time Difference GPRS - General Packet Radio Service GSM - Global System for Mobile communications GTD - Geometric Time Difference xii ID - Identifier IP - Internet Protocol LA - Location Area M-EMAC - Mobile Endpoint Measurement Based Admission Control MLCT - Most Likely Cell-Time MM - Mobility Management OTD - Observed Time Difference PPM - prediction by partial match QoS - Quality of Service RL - Reinforcement Learning RTD - Real Time Difference SMART - Semi-Markov Average Reward Technique SMDP - Semi-Markov Decision Process TCP - Transport Control Protocol TDOA - Time Difference of Arrival UMTS - Universal Mobile Telecommunications System xiii Symbols a - The admission threshold e - A design parameter to control a adaptively X - New call arrival rate G„ - The time of the («+l)th decision epoch xn - The time between the nth and the (n+l)th decision epochs to - Lagrange multiplier pc(x") - The compression ratio attained by C for x" AB' - The normalized average allocated bandwidth of class / calls Br(i, j, m, Tk) - The reserved bandwidth in cell j during Tk for m from cell i Br(i, j, m, ta, td) - The reserved bandwidth in cell j during time interval ta and td Br(j, Tk) * The aggregate reserved bandwidth in cell j during Tk Br(j, ta, td) - The aggregate reserved bandwidth in cell j during time interval ta and B Aj, Tk) - The free bandwidth in cell j during T k B f(j, ta, td) - The free bandwidth in cell j during time interval ta and td C(x") - The length, in bits, of the output sequence of x" after compression Phd - Handoff dropping probability P;j( Tk) - The probability that a mobile in cell i will visit cell j during time slot Tk P(i, j, ta, td) - The probability that a mobile in cell / will visit cell j during time interval ta and td Pnb - New call blocking probability Pss>{a) - The probability of transition from state s to state s' under action a Pv - The percentage of voice in the offered traffic q(x") - A lower bound on the compression ratio attainable for x" by any codebook raci(s\ s, a) - The actual reward between decision epochs R(s,a) - The action value of doing an action a in state s ta(i, j) - The time when a mobile in cell i will arrive at cell j td(i, j) - The time when a mobile in cell / will depart from cell j XV TAB' - The target normalized average allocated bandwidth of class i TVB' - The target normalized bandwidth variance of class / calls Tk - The kth time slot since the beginning of the call r - The peak rate of a connection VB' - The normalized bandwidth variance of class i calls xu - The number of users in the local cell using bandwidth btj x" - The sequence with the length of n y;j - The number of users in the neighboring cells using bandwidth xvi Acknowledgments First of all, I would like to express my sincere thanks and deep gratitude to my supervisor, Professor Victor Leung, for his constant encouragement, insightful comments, and invaluable suggestions, which benefited not only the work presented in this thesis, but also my career for a long time to come. I would like to thank Professor Cyril Leung, Professor Hussein Alnuweiri, Professor Rob ert Donaldson for serving on my thesis committee. Their comments have enhanced my research in innumerable ways. I am also very grateful to my university examiners, Professor Vikram Krishnamurthy and Professor Martin Puterman, and my external examiner, for reading and supporting my work. During my Ph. D. program, I have had the privilege to work with Dr. Vincent Wong, who is now teaching in the ECE department of the University of British Columbia. I thank him, sin cerely, for his comments on my work. Friends and students have certainly made my studies here memorable and interesting. I would like to thank Mrs. Mary Ma, Dr. Cyril Iskander, Dr. Peter Chong, Mr. Patrick Wang, Mr. Charles Gu, Mrs. Jenny Zi, Mrs. Crystal Wang, and all the other people in the Communications Group for their friendship and enjoyable technical discussions. I would like to express my sincere thanks to my parents for their constant love and encour agement. Many thanks to my wife, Kathleen Hu, for her love, support, understanding, and encour agement, which helped me go though this difficult yet rewarding process. XVll Chapter I Introduction 1 Chapter 1 Introduction 1.1 QoS Provisioning in Cellular Mobile Networks In recent years, there has been significant growth in the use of cellular mobile telephony for communications around the world. With the growing demand for integrated services support ing data traffic such as the world wide web (WWW) and e-mail as well as multimedia such as video and audio in cellular mobile networks, quality of service (QoS) provisioning is becoming more and more important. Due to the intrinsic characteristics of cellular mobile networks, such as the scarcity of wireless bandwidth, location-dependent and time-varying wireless links and user mobility, QoS provisioning in cellular mobile networks is more challenging than in wireline networks. To utilize the radio spectrum efficiently, a cellular architecture is used in wireless mobile networks. The geographical coverage area is partitioned into cells, each served by a base station. Since a mobile user may change cells a number of times during the lifetime of a call, availability of wireless network resources at a call's setup time does not necessarily guarantee that wireless network resources are available throughout the lifetime of a call. Due to handoff and mobility, overload conditions can occur if the communication needs of a number of mobile terminals populating a small area exceed the total capacity of all base stations within their reach. Thus, users may experience performance degradations due to mobile handoffs. This problem will be magnified in future micro/picro-cellular networks, where handoff events may occur at a much higher rate compared to today's macro-cellular systems [63]. Call admission control (CAC) and bandwidth reservation are required to address this problem. Since forced call terminations, due to handoff blocking, are generally more objectionable than new call blocking, we consider Phd, the Chapter 1 Introduction 2 probability of handoff dropping, as a call-level QoS metric provisioned by CAC for non-adaptive traffic, which cannot change bandwidth during the lifetime of a call. As it is imprac tical to completely eliminate handoff call dropping, the best option is to keep 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 algorithms. Another important issue in cellular networks is mobility management (MM). Since mobile users are free to move within the area covered by the network, the network needs to first determine a particular user's location whenever there is a need to establish communica tion with that user. The problem of mobility management is usually divided into two parts: paging and location updating. Paging is the network operation to find the exact location of a called mobile user, whereas the location update process keeps track of each mobile's general location so as to reduce both paging cost and delay. Recent research shows that per-user mobility information plays an important role in designing efficient MM algorithms. Since per-user mobility information is very important for QoS provisioning as well, it will be helpful to consider MM and QoS provisioning jointly and have them share information with each other. The scarce and highly fluctuating bandwidth of wireless links has motivated the development of adaptive multimedia applications that can operate over a wide range of available bandwidths. In adaptive multimedia applications, the bandwidth of a call can be dynamically adjusted to adapt to the various communication environments, especially in link Chapter 1 Introduction 3 overload situations. Moreover, the systems proposed for future cellular mobile networks provide flexible radio resource allocation functions, based on resource availability conditions. Under this adaptive multimedia framework, a bandwidth adaptation (BA) algorithm needs to be used in conjunction with the CAC algorithm for QoS provisioning. CAC decides the admission or rejection of new and handoff calls, whereas BA reallocates the bandwidth of ongoing calls. Cellular mobile networks usually have to internetwork with wireline networks for end-to-end communications. As the Internet evolves into a global communication infrastruc ture, Internet services and Internet communications using open standard protocols (including those being developed to support the QoS guarantees required for multimedia and premium services) are expected to play key roles in future generation cellular mobile networks. There is a growing demand for replacing the current same-service-to-all paradigm in the Internet with a model in which packets, applications, and users are treated differently based on their service needs. Several schemes have recently been proposed to provide QoS in the Internet, such as integrated service (IntServ), differentiated service (DiffServ) and the endpoint measurement-based admission control (EMAC) schemes. Therefore, there are two sets of different QoS definitions and mechanisms in cellular mobile networks and the Internet. However, the QoS experienced by a mobile user is end-to-end, that is, from the server to the mobile host. So, effective internetworking schemes between cellular networks and the Internet are very important to guarantee the end-to-end QoS. The rest of this chapter is organized as follows. Section 1.2 gives an overview of Chapter 1 Introduction 4 related work. Section 1.3 discusses the motivations of this work. Section 1.4 summarizes our contributions. Section 1.5 describes the organization of this thesis. 1.2 Overview of Related Work 1.2.1 Call Admission Control for Non-Adaptive Traffic The guard channel policy [41], [60] and fractional guard channel policy [62] determine the number of guard channels, which are reserved statically for handoffs, by considering just the status of local cell. Users are assumed to be uniformly located in any cell of the mobile network under these policies. In a distributed call admission control scheme [55], not only the status of a local cell but also that of adjacent cells are considered. The total required bandwidth for both handoff and existing calls is calculated under the assumptions of exponentially-distributed channel holding time and perfect knowledge of the rate of handoff. These assumptions are unrealistic in real networks. There have also been some research efforts to consider user mobility in designing CAC. The shadow cluster scheme [47] estimates future resource requirements in a collection of cells, called the shadow cluster, 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 movement. In [57], bandwidth is reserved in neighboring cells based on user movement predic-Chapter I Introduction 5 tion, and an algorithm is used to control the size of reserved bandwidth pool. However, this scheme does not estimate channel holding time, and therefore, cannot be applied directly for efficient bandwidth reservation. In [24], user mobility is estimated based on the aggregate history ofthe handoff observed in each cell. This scheme assumes that each mobile will handoff to neighboring cells with equal probability in the mobility estimate time window. This assumption may not be realistic in general. 1.2.2 Mobility Management Several MM schemes have been proposed in the literature. A good survey can be found in [78]. Two MM schemes related to this thesis are summarized as follows. In location area (LA)-based scheme, the coverage area is partitioned into a number of LAs. Each LA contains a group of cells. All base stations within the same LA broadcast the identifier (ID) of its LA periodically. Each mobile terminal compares its registered LA ID with the current broadcast LA ID. A location update is triggered if the two IDs are different. Upon a call arrival for a particular mobile terminal, all the cells within its current LA are polled simultaneously, ensuring success within a single step. The LA-based update scheme is widely adopted by the current cellular systems, including the EIA/TIA IS-41 [3] and the Global System for Mobile Communication (GSM) networks [54]. The main drawback of this scheme is that for an LA with a large number of cells, a significant amount of radio bandwidth is consumed in paging for each call arrival. In addition, mobile terminals located close to an LA boundary may perform excessive location updates as they move back and forth between two LAs. Chapter 1 Introduction 6 The idea of the path-based scheme [13] is based on a data compression algorithm proposed by Ziv and Lempel. It works as an add-on module to the underlying update scheme (e.g., LA-based), which generates the movement history. However, a real update message is not sent to the network for each symbol. As with data compression, the algorithm parses the sequence of symbols to form code words for transmissions. The network database maintains the movement history in a compact form by a trie, which can by considered to be a part of the user's profile. Upon a call arrival, selective paging based on the trie information is used to locate the mobile terminal. 1.2.3 Call Admission Control and Bandwidth Adaptation for Adaptive Traffic Channel sub-rating scheme for telephony services is proposed in [50]. "Sub-rating" refers to an occupied full-rate channel being temporarily divided into two channels at half the original rate: one to serve the existing call and the other to serve the new request. Authors in [94] consider a similar scheme with one class of non-adaptive service and one class of adaptive service. In [25], an analytical model is derived for one class of adaptive service. The extension of these schemes designed for one class of adaptive traffic to the case of multiple classes in real cellular networks may not be an easy task. Talukdar et al. [71] study the trade-offs between network overload and fairness in bandwidth adaptation for multiple classes of adaptive multimedia. However, the proposed scheme in [71] does not consider maximizing wireless network utilization and may result in sub-optimal solution. Chapter 1 Introduction 7 Markov decision process formulation and linear programming are used in [82]. The large state and action space problems in [82] may hinder the deployment of this scheme in practical networks. Authors in [89] use a simulated annealing algorithm to find the optimal call-mix selection. In these schemes, only the status of the local cell is considered in QoS provisioning for adaptive multimedia. It is well known that the status of neighboring cells has an increased influence on the QoS of the local cell in future multimedia cellular networks [63], and therefore, the status information of neighboring cells is very important for the QoS provisioning that can adapt to changes in the traffic pattern. Authors in [35] and [45] make fine attempts to consider the status information of neighboring cells. However, only one class of traffic is studied and they do not consider maximizing network revenue. 1.2.4 QoS Provisioning in the Internet The traditional approach to addressing this problem is an IntServ architecture [18], in which applications and users request a certain performance level that can be guaranteed using resource reservation and admission control mechanisms. While such architectures provide excellent QoS, they face significant deployment and scalability difficulties. DiffServ [15] is another approach to provide QoS for the Internet. The DiffServ model is characterized by marking and creation of several traffic classes receiving differentiated treatment. DiffServ requires no per-flow admission control or signaling, and routers do not maintain any per-flow state. The combination of provisioning, service-level-agreements and DiffServ router mechanisms may prove sufficient for providing QoS for individual real-time Chapter 1 Introduction 8 flows. Attempting to combine DiffServ's superior scalability with IntServ's superior QoS, several recent papers [14], [19], [28], [42] have proposed the novel approach of using EMAC. In these designs, the end host probes the network by sending probe packets at the data rate it would like to reserve and recording the resulting level of packet losses (or congestion marks). The host then admits the flow only if the loss (or marking) percentage is below some thresh old value. Since EMAC requires no explicit support from the routers, and since routers keep no per-flow state and do not process reservation requests, this is an attempt to use the regular best-effort infrastructure (with its DiffServ extensions), and by adding control algorithms at the endpoints, deliver a real-time service. Analysis and simulation results from previous work suggest that a soft real-time service based on endpoint probing may be viable. 1.3 Motivations To guarantee Phd below a target level and maximize resource utilization at the same time for non-adaptive traffic, several CAC schemes have been reported in the literature. Although most of these proposals have achieved this goal, these schemes are derived under unrealistic assumptions. First of all, structured cell configurations are commonly used. Circular, hexagonal or square cell configurations are often used in two-dimensional models, and a linear model is commonly used in the one-dimensional case [24], [47], [55]. Although these network topology models simplify the analyses, they do not accurately represent a real cellular network, where the cell shape and size may vary depending on the receiver sensitiv ity, antenna radiation pattern of the base station and propagation environment, and where the Chapter 1 Introduction 9 number of neighboring cells varies from cell to cell. We believe a generalized graph model is more appropriate to represent the topology of an actual cellular network. Second, most existing schemes assume channel holding time follows an exponential distribution, which is independent and identically distributed for all calls. However, simulation studies and field data have shown that exponentially distributed channel holding time is not accurate in actual networks [31], [44]. Third, the symmetric random walk model has been quite popular among researchers in characterizing individual movement behavior. In this model, a mobile user moves to any one of the neighboring cells with equal probability after leaving a cell. This model does not take into account the direction of the mobile user. In general, a mobile user usually travels with a destination in mind. So, the mobile's location in the future is likely to be correlated with its movement history. Motivated by these observations, we investigate efficient CAC and bandwidth reservation schemes based on assumptions more realistic than existing proposals. Another part of our work focuses on a framework combining QoS provisioning and mobility management. The motivations behind this part of our work are based on the following observations. First, it is generally assumed in the literature that the sole purpose of the location update mechanism is to aid the paging process, and that the CAC decision should be based on a different information set. However, the MM problem in cellular networks arises primarily because of user mobility. On the other hand, user mobility is also the primary reason why CAC in cellular networks is required to take extra steps to guarantee call-level QoS. So, the information used to solve one problem may be useful for solving another one. Second, recent work [13], [66], [78] has considered per-user mobility patterns to design more efficient Chapter I Introduction 10 MM schemes. Authors in [47], [57], [83] have also considered per-user mobility patterns in CAC in cellular networks. Since analytic and simulation results in these papers show that the per-user mobility pattern can provide the basis for effective solutions that address these two system requirements, it will be helpful to consider them jointly and make them share information with each other. Third, in solving the MM problem, some schemes [8], [ 13], [48] only use out-of-session (i.e., between call arrivals) movements and ignore in-session (i.e., during the calls) mobility information. On the other hand, only in-session movements, but not out-of-session movements, are used in designing CAC in [24], [83]. In fact, both in-session and out-of-session movements are parts of a user's mobility pattern. Therefore, it is expected that using all available mobility information will improve the performance of both CAC and MM schemes. In adaptive multimedia cellular mobile networks, maximizing revenue while meeting QoS constraints suggests a constrained semi-Markov decision process (SMDP) [53]. The traditional model-based solutions [61] to SMDP, which require state transition probabilities, suffer from two "curses": The curse of dimensionality and the curse of modeling. The curse of dimensionality is that the complexity and solution space in these algorithms increase exponentially as the number of states increases. QoS provisioning in adaptive multimedia cellular networks involves very large state space, which makes model-based solutions infeasible. The curse of modeling is that in order to apply model-based methods, it is first necessary to express state transition probabilities explicitly. This is very difficult in real cellular networks due to irregular network topology, different propagation environments and random user mobility. These curses suffered by model-based approaches motivate us to Chapter 1 Introduction 11 pursue alternative solutions. A model-free reinforcement learning (RL)-based approach, which does not require explicit state transition probabilities, is studied in this thesis. The motivations behind our work on CAC for cellular-to-IP internetworking are based on the experience of Transmission Control Protocol (TCP) on wireless domain. Like reliable transport protocols such as TCP, EMAC is an end-to-end scheme. It is well known that TCP is tuned to perform well over wireline links and has degraded performance over wireless links. Consequently, many modifications of TCP have been made to improve the performance of TCP in such an environment [7]. Motivated from this experience, we believe that it is better to consider the wireless environment before the deployment of EMAC than to modify it after it is widely accepted. We will study the performance of EMAC in cellular mobile networks and propose a CAC scheme for cellular-to-IP internetworking. 1.4 Main Contributions The main contributions of this thesis are as follows: • Mobility-based predictive CAC and bandwidth reservation: To provide the call level QoS for non-adaptive traffic in cellular mobile networks, we propose to statisti cally predict user mobility based on the mobility history of users. The mobility prediction scheme is derived from data compression techniques that are both theoret ically optimal and good in practice. In order to utilize resources more efficiently, we predict not only the cell to which the mobile will handoff, but also when the handoff will occur. We also adaptively control the admission threshold to achieve a better balance between guaranteeing handoff dropping probability and maximizing Chapter 1 Introduction 12 resource utilization. Results show that the proposed schemes meet our design goals and outperform other schemes. • A framework combining QoS provisioning and mobility management: We propose a novel framework to solve QoS and mobility management problems in cellular networks using a common user mobility prediction scheme.We use all available location information of the mobile, both during calls and between calls, for a more accurate modeling of individual users' mobility. Particularly, in our framework, not only location updates between calls but also handoff records during a call lifetime are used to build the mobility trie. Results show that more effective solutions to both CAC and mobility management can be realized from this framework. • Solving QoS provisioning for adaptive multimedia using reinforcement learning: We present a QoS provisioning scheme for adaptive multimedia in cellular mobile networks via reinforcement learning, which can maximize the network revenue subject to several predetermined QoS constraints. Unlike other model-based algorithms, our scheme does not require the explicit state transition probabilities, and therefore, the underlying assumptions of our scheme are more realistic than those in previous schemes. Simulation results demonstrate the superior performance of the proposed scheme to some of the existing methods. • A CAC scheme for cellular-to-IP internetworking: Although EMAC has many desirable features in the wireline networks, as shown in the previous work, in this Chapter 1 Introduction 13 thesis we show that several distinct characteristics in cellular mobile networks make EMAC difficult to implement. We propose a mobile-EMAC (M-EMAC) scheme to internetwork cellular networks to the Internet. Results show that the proposed scheme performs better than EMAC in cellular mobile networks. 1.5 Organization ofthe Thesis The rest ofthe thesis is organized as follows. In Chapter 2, we propose and analyze the mobility-based predictive CAC and bandwidth reservation schemes. The mobility predic tion approach derived from optimal data compression scheme is described. Based on the mobility prediction, efficient CAC and bandwidth reservation schemes are proposed. We present performance comparisons using simulations. In Chapter 3, we propose a framework that combines QoS provisioning and mobility management. We present numerical results and compare the performance with other schemes. In Chapter 4, we propose to solve the QoS provisioning problem for adaptive multimedia in cellular mobile networks via reinforcement learning. We describe the formulation of the problem and our reinforcement-learning-based approach. Performance comparisons with other schemes by simulations are given. In Chapter 5, we present the numerical results of EMAC performance in cellular mobile networks. A novel M-EMAC scheme is proposed and its performance is evaluated using simulations. Finally, Chapter 6 concludes the thesis with a summary of the presented work and some suggestions for future work. Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 14 Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 2.1 Introduction In this chapter, we address the issues of CAC and bandwidth reservation by proposing and evaluating mobility-based predictive schemes under more realistic assumptions [83], [87]. In order to guarantee the handoff dropping probability, we propose to statistically predict user mobility based on the mobility history of users. Using this prediction scheme, we can predict not only the cell to which the mobile will handoff, but also when the handoff will occur. Bandwidth is reserved to guarantee some target handoff dropping probability. We also adaptively control the admission threshold to achieve a better balance between guaranteeing handoff dropping probability and maximizing resource utilization. Simulation results show that the proposed schemes meet our design goals and outperform the static reservation scheme. The rest of this chapter is organized as follows. System models that are more realistic than those considered previously in similar work are illustrated in Section 2.2. In Section 2.3, we describe and analyze the mobility prediction schemes. Based on the mobility prediction, efficient CAC and bandwidth reservation schemes are proposed in Section 2.4. Simulation results are presented and discussed in Section 2.5. A summary is given in Section 2.6. 2.2 Model Description We consider a mobile communication network with a cellular wireless infrastructure. A handoff could fail due to insufficient bandwidth in the new cell, causing the handoff call to Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 15 be dropped. In this study, we do not consider (1) soft handoff in Code Division Multiple Access (CDMA) systems [75], in which a mobile can communicate with two or more base stations simultaneously; (2) delay-insensitive applications, which can tolerate long handoff time delay caused by insufficient bandwidth. We describe the network topology, channel holding time distribution and user mobility pattern considered in our study in the following subsections. 2.2.1 Network Topology To address CAC and bandwidth reservation problems, most researchers model cellular networks by structured graphs. Circular, hexagonal or square cell configurations are often used in two-dimensional models, and a linear model is commonly used in the one-dimen sional case. Although these network topologies simplify the analyses, they do not accurately represent a real cellular network, where the number of neighboring cells varies from cell to cell, and the shape and size of each cell may vary depending on receiver sensitivity, antenna radiation pattern ofthe base station, and the propagation environment. Our network topology model is not restricted to structured cell configuration, such as hexagonal or linear. We use a generalized graph model to represent the actual cellular net work. The network is modeled as a connected graph G = [V, E), where the vertex-set Vrepre sents the set of base stations, each serving a single cell, and the edge-set E represents the adjacency between pairs of cells. Figure 2.1 shows an example network representation with vertex-set V = {a, b, c, /} and edge-set E = {(a, b), (a, c), (k, /)}. Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 16 e \ h ( a \ > '» h \ • il f \ g \ Figure 2.1 Modeling an actual cellular network 2.2.2 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 cellular mobile network and needs not have the same statistical properties [31], [44]. Most research work on CAC and bandwidth reservation assumes the channel hold ing time follows an exponential distribution [41], [47], [62], which is independent and identi cally distributed (i.i.d.) for all cells. Like the structured models for network topology, i.i.d. exponential distribution simplifies the analyses, but does not give an accurate representation of the real characteristics of cellular networks. 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. Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 17 2.2.3 User Mobility Pattern The symmetric random walk model has been quite popular among researchers in char acterizing individual movement behavior [55], [62]. 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 account 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, H^, H2, H^,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 termi nation 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, TV = (m, /, 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,j), where Tk is the time elapsed since the beginning of the call and j 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 Ath 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, Hh H2, #3, .... Hn, .... E is assumed to be generated by an mth order Markov source, in which the states correspond to the contexts of the previous m events. The probabilities of possible next events can depend on a list of m previous events. Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 18 2.3 Mobility Prediction We derive probabilistic predictions of user mobility based on the accumulated behav ior history of each specific mobile. The rationale behind the scheme is the observation that a user's mobility pattern is a reflection of the routines of his/her life and that most mobile users have favorite routes and habitual movement patterns. This repetitive nature of mobility pat terns suggests the stationarity of a sequence of events generated by an mth order Markov source. Thus, we can learn those patterns from the mobility history of a particular user and predict the user's next move when those patterns reappear. A similar prediction approach is used in [13] to solve the mobility management prob lem in cellular networks. This scheme records only the locations of mobile users to predict their future locations and cannot be used directly to derive efficient CAC and bandwidth res ervation schemes. Although the possibility of using this method for QoS provisioning in cel lular networks is mentioned in [13], as far as we know, our proposal is the first to realize this possibility. The novelty of our proposal compared to the previous one is that we record both the locations and the handoff times of mobile users. Therefore, we can derive a novel predic tion method that predicts not only where a mobile user will handoff, but also when the hand-off is likely to occur. Based on this novel prediction method, we further propose CAC and bandwidth reservation schemes that are more efficient than existing methods. The prediction approach is motivated from optimal data compression methods. In data compression, a data set (e.g., a text file or an image) is decomposed into a sequence of events, and encoded using as few bits as possible. Thus, short codewords should be assigned to more Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 19 probable events and longer codewords should be assigned to less probable events. So, in order to compress data well, one has to be able to predict future data well, and hence a good data compressor should also be a good predictor. If a data compressor expects a certain character to be next with a very high probability, it will assign that character a relatively short code. If the overall code length is small, then the predictions of the data compressor must have been good. 2.3.1 Optimal Data Compression In this study, we develop our mobility prediction algorithm based on the Ziv-Lempel algorithms for data compression, which are both theoretically optimal and good in practice. The original word-based Ziv-Lempel encoder [95] breaks the input string into block-to-vari able codes. The algorithm parses each block of size n in a greedy manner into distinct sub strings x\, x2, x„ with the following property: For each j > 1, substring x, without its last character is equal to some previous substring x,-, where 0 <i <j. Substring x, is encoded by the value /, using \\og2(j -1)1 bits, followed by the ASCII encoding of the last character of Xj, using riog2ctl bits, where a is the size of the input sequence's alphabet. Because of this Prefix Property, substrings parsed so far can be efficiently maintained in a trie [46], The equivalent character-based Ziv-Lempel algorithm builds in on-line fashion a probabilistic model (or a trie) that feeds probability information to an arithmetic coder [80], which encodes a sequence of probability of p using log,(l /p) = -log,/? bits. We show by example how these algorithms work. Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 20 Figure 2.2 The trie constructed in Example 2.1 Example 2.1: Let the alphabet be {a, b, c}. We consider an input string "ababcab-cababcab ..." that the Ziv-Lempel encoder parses as "(a)(b)(ab)(c)(abc)(aba)(bc)(ab...)... " Each substring in the parse is encoded as a pointer followed by a character. In particular, the match "ah" ofthe sixth substring "aba" is encoded using flog25] bits with a value 3, since the match "ab" is the third substring, and the last character "a" is encoded using [ log 23 "| bits, since the alphabet size is 3. In the character-based version of Ziv-Lempel encoder, a trie is built when each previ ous substring ends. The trie at the end of the seventh substring is pictured in Figure 2.2. There are four previous substrings beginning with an "a", two beginning with a "b" and one begin-4 ning with a "c." The character "a" is therefore assigned a probability of - at the root, "b" is Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 21 2 1 assigned a probability of - at the root, and "c" is assigned a probability of - at the root. Sim ilarly, ofthe four substrings that begin with an "a," three begin with an "ah" giving the prob-3 ability of - for "6," and so on. Any sequence that leads from the root of the trie to a leaf traverses a sequence of probabilities of P,, P2, P3, whose product FT/?, equals - . The arithmetic coder encodes the sequence with -log-FJ/', 2-1 i = riog27"| =3 bits. Note that the square nodes in Figure 2.2 denote the last nodes ending the sequences. 2.3.2 Mobility Prediction Our mobility prediction scheme is based on the character-based version of the Ziv-Lempel algorithm. The sequence of events N, H]t H2, #3, Hn, E during the lifetime of a call corresponds to the substring in the Ziv-Lempel algorithm. The mobility database of every mobile at specific time holds a mobility trie, which is a probability model corresponding to that of the Ziv-Lempel algorithm. Each node, except for the root, in the mobility trie preserves the relevant statistics that can be used to predict the probability of following events. As in data compression, the mobility trie of the mobile is built in an on-line fashion. When a mobile requests a new call, the predictor sets the current node to the root of the trie according to the mobile, cell and time, and calculates the probabilities of all possible events of this mobile. Upon recording an actual event of the mobile, the predictor "walks" down the trie and is ready for the next prediction. When an event is not in the mobility trie, a prediction fault is gener-Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 22 initialize mobility trie :=null initialize number_of_event :=0 loop wait for next event e if (e is a new call) look for a trie with a root of e in the database if (cannot find such a trie) create a trie :=single node (the root) endif else if (e exists in the trie) number_of_event :=number_of_event + 1 else create a leaf e calculate the probabilities of possible events based on the number_of_event of leaves forever Figure 2.3 A pseudo-code of mobility prediction ated and the trie is updated. A pseudo-code description of the mobility prediction scheme is given in Figure 2.3. Figure 2.4 shows an example of the mobility trie of mobile m at cell a in the time interval 8:00-9:00 a.m. 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 trie to predict the probabilities of the next possible events of this mobile: it will terminate the call without hand-2 offs in the 2nd time slot with probability of —, handoff to cell b in the 2nd time slot with 56 probability of , and so on. 56 2.3.3 Analysis of the Mobility Prediction Scheme We first analyze the optimality of the word-based Ziv-Lempel algorithm and show that the character-based Ziv-Lempel algorithm is as least as good as the word-based approach. Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 23 T2, [2/56] [5/56] Figure 2.4 A mobility trie used for mobility prediction Then, we will establish that our mobility prediction scheme inherits the optimality of these data compression algorithms. Given a sequence x" of length n over an alphabet A of a letters and an information lossless (IL) compressor C accepting inputs over A, let |C(JC")| denote the length, in bits, of the output that C produces on xn. The compression ratio pc(x") attained by C for x" is [95]: Q (xn)= |C(S")| *CK nlog2(cc) (2.1) Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 24 Define pa(x") as the best compression ratio attainable for x" by any IL compressor of a states. Sequence x" is parsed into different phrases: x"- x{, x2, x,, and t(x") is the maximal possible number of distinct phrases. Define: q(x")= 'OOlogzCC*'')) . (2.2) nlog2(a) A result in [95] shows that pa(x") > q(x") - 5(a, n) with lim 5(a, n) = 0. (2.3) n —» co So, q(x") is a lower bound on the compression ratio attainable for x" by any codebook. The Ziv-Lempel incremental parsing algorithm achieves for any sequence x" given to it a compression ratio that is (asymptotically) equal to q(x"), and thus the algorithm is univer sal and asymptotically optimal [67]. In [9], it has been shown that the code length obtained in the character-based version of the Ziv-Lempel algorithm is as least as good as that obtained using the word-based approach. Hence, the optimality result in [95] holds without change for the character-based approach. We define the event fault rate to be the total number of event faults that our mobility prediction algorithm incurs, divided by the total number of events. Also, we define the Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 25 expected fault rate to be the best possible fault rate achievable by any prediction algorithm that makes its prediction based only on the past history. A result in [76] shows this: If the source is a stationary mth order Markov source, the expected event fault rate of our prediction algorithm is within an additive factor of 0(1/ Jn) from the expected event fault rate of the source, where n is the length of the event sequence. From these, we see that our mobility prediction algorithm inherits the asymptotic opti mally of the Ziv-Lempel algorithm. By modeling the sequence of events during the lifetime of a call as that generated by a stationary mth order Markov source and predicting next events using the mobility prediction scheme derived from the Ziv-Lempel algorithm, we can predict not only to which cell a mobile will handoff, but also when the handoff will occur. 2.3.4 Implementation Considerations The mobility prediction scheme proposed above maintains the statistics in a trie, which can be stored in the user profile in cellular mobile networks. An important issue is how this model can be implemented. In fact, a trie is a multiway 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 trie. The simplest approach is to create an array of pointers for each node in the trie with a pointer for each character of the input alphabet (Figure 2.5-a). This method can waste considerable memory space, particularly if some characters of the alphabet are rarely used. An alternative is to use a linked list at each node, with one item for each possible branch Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 26 a b c a b c a b c a I b 1 c a b c (a) 1 1 c * c (b) Figure 2.5 Implementation of trie nodes in Figure 2.2: (a) array and (b) linked list. (Figure 2.5-b). The space needed for a node in the linked list requires two pointers, one counter and a symbol. A straightforward implementation of this would consume 13 bytes, and these could be packed into perhaps 11 bytes. 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. A trie can also be implemented as a single hash table with an entry for each node. The memory consumed by a trie can be reduced by truncating it prematurely at a shallow depth, and using some other data structure for subsequent characters. For further details, the reader can consult books on algorithms and data structures. In practice, in order to reduce the memory and computation complexity, it is desirable to limit the size ofthe data structure for prediction. Several techniques are known for limiting data structure size in [69]. An explicit upper bound S is placed on the size of the data Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 27 structure. The data structure is either frozen when its size reaches S, flushed and rebuilt when its size reaches S, or frozen when its size reaches S/2 and a new one is built while the old one is used for prediction. There are also more sophisticated techniques that use tags to determine what nodes are to be deleted when its size reaches S [21]. In the simulations, a linked list with 11 bytes at each node is used and the scheme in [21] is employed to maintain the size S = 40. 2.4 Call Admission Control and Bandwidth Reservation 2.4.1 Calculation of P(i,j, Tk) Our approach is based on the predicted mobility of each user. We calculate P(i,j, Tk), the probability that a mobile originally in cell / will visit cell j during time slot Tk. From the mobility trie, we can see that a mobile taking different paths can visit a certain cell in the same slot. Using the total probability theorem [58], we must add all of these probabilities to get P(i,j, Tk) . Example 2.2 shows how to get this probability. Example 2.2: A mobile m requests a new call at cell a in the time interval 8:00-9:00 a.m. From the mobility trie in Figure 2.4, we can see that m can take several different paths to visit cell b. We describe these paths by sequences of events: Path l:N(m, a, 8:00-9:00 a.m.), H(Th b), E(T2). 3 3 3 By Path 1, m will visit cell b in Tj and T2 with probability: - x- = — . Path 2: N(m, a, 8:00-9:00 a.m.), H(T2, b), E(T4). Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 28 15 5 5 By Path 2, m will visit cell b in T2, T3 and T4 with probability: — x — = — Path 3: 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: = ^- , 56 15 56 Path 4: 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, r3, T4 and T5 with probability: 15 4_ = 4_ 56 X 15 56 So, ur u n 3,5,6,4 18 J>(~, b, T4) = | + 1= 1 and P(«,ft,r,) = ±. 2.4.2 The Most Likely Cell-Time When a mobile is active in cell i, we can get the most likely cell-time (MLCT) of that Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 29 mobile, a cluster of time units at a cluster of cells when and where a mobile will most likely visit in the future. We select cell j and time slot Tk with P{i,j, Tk) greater than zero to form the MLCT of this mobile. 2.4.3 Bandwidth Reservation Using P(i,j, Tk), the probabilities of handing off from cell-/' into cell j during time slot Tk of mobile m, we can obtain the required bandwidth Br(i,j, m, Tk) to be reserved in cell j during the time slot Tk for the expected handoff of mobile m from cell i: Br(U, m, Tk) = P(i,j, Tk) • B(m) , (2.4) where B(m) is the bandwidth required by m. In this study, we assume that the traffic characteristics and the desired packet-level QoS guarantees (e.g., delay, jitter, loss and throughput) can together be represented by effective bandwidth. Techniques for computing the effective bandwidth for different traffic characteristics and QoS requirements can be found in [29], [39]. Moreover, the reserved bandwidth Br(j, Tk), which is the aggregate bandwidth to be reserved in cell j during Tk, is calculated as: Br(J, Tk) = X Br(i,j, m, Tk) , (2.5) 111 € M,ie I where M is the set of mobiles which will handoff to cell j from a set of cells / during Tk. Finally, the free bandwidth left after the reservation is: BjO\Tk) = B-Br(J,Tk) , - (2-6) Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 30 where B is the total bandwidth in cell j. 2.4.4 Call Admission Control and Bandwidth Reservation for New Calls When a new call arriving at mobile m with a bandwidth requirement B(m) requires admission to cell i, the CAC algorithm first checks if the current free bandwidth of cell i can support the call. The call is rejected if the cell does not have enough free bandwidth. Otherwise, CAC will check the availability of free bandwidth in the MLCT of this mobile. The checking result can be written as: Check(j, Tk,B(m)) \,Bj(j,Tk)>B(m) Mi^, otherwise (2.7) Based on these values, the new call will be admitted if the following holds: £ P(iJ,Tk)-Check(J,Tk,B(m))>a £ P(iJ,Tk) , (2.8) j,TkeMLCT /, Tk e MLCT where a is the admission threshold and should be controlled adaptively. We will describe how to control this threshold in the next subsection. When a new call is admitted, bandwidth is reserved in the mobile's MLCT. And the free bandwidth in the MLCT is updated accordingly. 2.4.5 Adaptive Control of Admission Threshold The mobility prediction functions may not work well for some mobile users, especially those who do not have favorite routes. Moreover, if the admission threshold a is Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 31 too small, the handoff dropping probability may exceed the target value; if a is too large, resource utilization will decrease. So, admission threshold a should be controlled adaptively. We calculate Phd, the handoff dropping probability of a mobile, by dividing the number of handoff drops to the total number of its calls recorded in the mobility trie. Let TPhd denote the target value of handoff dropping probability of mobile m. If Phd < TPhd, admission threshold a is decreased by s, a design parameter; otherwise, a is increased by e. The calculation of Phd and the update of admission threshold are done upon call completion. By adaptive control of a, we can achieve a better balance of guaranteeing Phd and maximizing resource utilization. 2.4.6 Call Admission Control and Bandwidth Reservation for Handoff Calls When a mobile m, with bandwidth requirement B(m), requires handoff to cell /, CAC will calculate P(i,j, Tk) and get the MLCT of m based on the mobility trie. Bandwidth is reserved for m in its MLCT accordingly. The CAC algorithm will admit the handoff call if the current free bandwidth of cell / can support the call. 2.5 Simulation Results and Discussions In this section, we present and discuss the simulation results of the proposed schemes as well as comparisons with two other CAC schemes. We consider a coverage area that consists of 40 base stations, each of which has 6 Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 32 neighbors on average. The distance between two base stations is 1 mile. 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, 0.1 respec tively. 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 follows: (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 that is closest to the destination. Note that two paths with at least one edge not in common are different paths, and that different mobile users can have the same paths. Also, we apply the following assumptions in our model: 1. Each cell has a fixed link capacity of 40 bandwidth units (BUs). 2. Time is quantized into units of T= 30s. 3. A call is either for voice (requiring 1 BU) or video (requiring 4 BUs). 4. Call durations are the same for all calls and exponentially distributed with a mean value of 3 minutes. 5. Call requests are generated.according to a Poisson process with rate A. (calls/cell/m). 6. The speeds of mobiles are uniformly distributed between 0 and 40 miles/hour. 7. The target hand off dropping probabilities are the same for all mobiles: Pnd= 0.01. 8. Admission threshold a is initialized to 1 in each simulation and adaptive factor e = 0.02. Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 33 The offered load is calculated as follows: Offered Load = 3 • X • ((1 - Pv) • 4 + Pv), where Pv is the percentage of voice in the offered traffic. The physical meaning of the offered load is the total bandwidth units required on average to support all existing calls. Simulations start without any pre-memorized information of mobiles. Long-term handoff dropping probability, new call blocking probability and utilization are obtained for a lOOh simulation time duration. During each simulation, a mobility trie is constructed for each mobile and its mobility is predicted. Based on the prediction, an MLCT is constructed. Then CAC algorithm will check the availability of bandwidth and decide to admit or reject the new call and handoff call requests using the algorithms described in Section 2.4. If the call is admitted, bandwidth is reserved in the mobile's MLCT accordingly. Figure 2.6 shows Pnb and Phd as functions of the offered load for two values of Pv: 0.8 and 1. The probabilities of handoff dropping are kept below the target values 0.01 irrespective of the offered load and Pr This shows that the proposed CAC and bandwidth reservation schemes achieve one of our goals: keeping Phd below a target level. We also observe that Pnb and Phd increase as Pv decreases under the same offered load. This is because the video calls need more bandwidth. Figure 2.7 shows the average utilization as a function of the offered load with different values of Pv Since the time slot is used in our mobility prediction scheme, the selection of time slot duration Twill influence both the convergence speed and the network utilization. We study Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 34 this issue in the following. In simulations, we choose 3 values of T, 15s, 30s and 90s. Figure 2.8 shows the handoff dropping probabilities as functions of simulation time with different time slot durations. In the beginning ofthe simulation, the system knows little about the mobility of mobile users and the handoff dropping probabilities cannot be kept below the target value 0.01. As the simulation goes on, the prediction tends to converge and the target handoff dropping probability can be guaranteed. From Figure 2.8 we can see that the convergence is faster when Tis 90s than when Tis 30s, which is in turn faster than when T is 15s. The reason for this is that the mobility sequence will be long when Tis small, and when T is large, the sequence will be short. The longer the sequence, the slower the convergence speed. It seems that it is better to have a large value of T, since the convergence will be fast. However, a large value of T means that the prediction is not accurate, and results in low utilization, which can be seen clearly in Figure 2.9. The utilization is higher when Tis 15s than when Tis 30s, which is higher than when Tis 90s. Therefore, choosing a suitable value of T according to real network conditions is very important for getting the best performance from the proposed scheme. We also compare the proposed CAC and bandwidth reservation schemes with the well known static reservation scheme [41], [60]. In the static reservation scheme, a set of bandwidth is reserved statically for handoff calls. In our simulation, we consider 4 BUs and 5 BUs reserved permanently for handoff calls in each cell. For comparison, we call our scheme cell-time-reservation. Figures 2.10 and 2.11 show that the static reservation scheme with 4 and 5 BUs Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 35 reserved for handoff calls can keep Phd below the target value of 0.01 when the network has a light load, but the reserved bandwidth is not enough when the offered load becomes heavier. Hence, this scheme cannot achieve the design goal. Although the static reservation scheme has almost the same PM 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 Pnh. 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. From these results, we can see that our proposed cell-time-reservation scheme achieves a better balance of guaranteeing Phd and maximizing utilization. 2.6 Summary In this chapter, we have proposed call admission control and bandwidth reservation schemes for non-adaptive traffic in cellular mobile networks based on assumptions more realistic than existing proposals. The proposed schemes are applicable to arbitrary cell topolo gies and the channel holding time can follow a general distribution. The sequences of events of new call admission, handoffs and call termination are modeled by stationary mth order Markov sources. We derived novel probabilistic predictions of next events based on the mobility history of users, using an algorithm motivated by optimal data compression. Based on the mobility prediction of where and when the mobile will handoff to the next cell, CAC and bandwidth reservation schemes have been developed. The performance of the proposed schemes have been studied using computer simulations. Results show that our schemes can achieve a better balance of guaranteeing handoff dropping probability while maximizing Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation resource utilization, and they outperform the static reservation scheme. 10 Offered load (BU) Figure 2.6 Pnb and P^ vs. offered load 1| 1 1 1 1 i 1 r -e- pv=0-8 20 30 40 50 60 70 80 90 Offered load (BU) Figure 2.7 Utilization vs. offered load Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 37 -H T=15sec -B- T=30sec 0 20 40 60 80 100 120 Simulation time (hour) Figure 2.8 PM vs. simulation time with different values of time slot duration 11 1 1 1 1 1 r 0.9 -0.2 - I T=15 sec -B- T=30sec T=90sec _i i i i i i I =U 20 30 40 50 60 70 80 90 Offered load (BU) Figure 2.9 Utilization vs. offered load with different values of time slot duration Chapter 2 Mobility-Based Call Admission Control and Bandwidth Reservation 38 og io': e H> P^ of static-reservation (4 BUs) -g- P^ of cell-time-reservation .0- PM of static-reservation (4 BUs) ^hd °' cell-time-reservation 40 50 60 Offered load (BU) 70 Figure 2.10 Comparison with static reservation (4 BUs) •o og 10 ^nb °' static-reservation (5 BUs) P^ of cell-time-reservation zj_ PM of static-reservation (5 BUs) 40 50 60 Offered load (BU) Figure 2.11 Comparison with static reservation (5 BUs) Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 39 Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 3.1 Introduction In this chapter, we propose a framework combining QoS provisioning and mobility management in cellular networks [84], [88], [89]. Since user mobility is the primary reason why both CAC and mobility management problems arise, the information used to solve one problem may be useful for solving another one. Moreover, recent work shows that the per user mobility pattern plays an important role in both of these two issues. It will be helpful to consider them jointly and have them share information with each other. Therefore, we can use the mobility prediction scheme in Chapter 2 as the key component in this framework, which can be used in both locating/paging mobiles and making admission decisions. Using this framework, we propose a new path-based MM scheme and a new CAC scheme that use all available mobility information. Simulation results are presented to show the performance improvements of the new QoS and MM schemes in this framework. The rest of this chapter is organized as follows. The common mobility prediction scheme is described in Section 3.2. In Section 3.3, we describe the location update and paging schemes in our framework. The new CAC scheme is described in Section 3.4. A summary of this chapter is given in Section 3.5. 3.2 Common Mobility Prediction Scheme If the position of a user can always be predicted in advance, then no explicit update is necessary and the optimal location area is the one that minimizes paging cost, i.e., a single Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 40 cell. On the other hand, if the network knows accurately where the mobile will move when the mobile needs to perform a handoff during a call, a more efficient CAC scheme can be designed. Therefore, the key component in our framework combining QoS provisioning and MM together is a common mobility prediction scheme that can be used for both paging mobiles and making admission decisions. In Chapter 2, we show that the mobility prediction scheme derived from the optimal data compression algorithm is optimal in terms of event fault rate. However, in Chapter 2, we only use the in-session (i.e., during calls) mobility information and ignore the out-of-session (i.e., between call arrivals) movements. In fact, both in-session and out-of-session movements are part of a user's mobility pattern. It is expected that using all available mobility information will improve the performance of both CAC and MM schemes. Although the Ziv-Lempel-based prediction scheme, which is used in Chapter 2, is shown to be optimal, the prediction by partial match (PPM) scheme usually outperforms the Ziv-Lempel algorithm due to implementation considerations and a faster convergence rate [9]. The basis of the PPM algorithm of order m is a set of m+1 Markov predictors. A Markov predictor of order j predicts the next event based on the j immediately preceding events. In order for PPM to work well, the network needs to maintain all contexts of order 0, 1, m. Note that although an enhanced symbol-wise model is used in [13], it cannot store all the contexts of different orders, which will eventually affect the convergence rate and prediction performance. Here, we use another trie [9] which will combine all contexts together into a single data structure. The following example demonstrates the data structure and how PPM works. Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 41 Figure 3.1 The trie constructed in Example 3.1 Example 3.1: Assume that a mobile has visited a sequence of cells, "ababcabcababcab..." which is same as the input string in Example 2.1. The mobile can send the "compressed" sequence of cells to the network. A trie at the end of the 7th subsequence is built at the network side, shown in Figure 3.1. Assume that the predictor in the network knows the last three cells visited by the mobile are "abc" and wants to predict the probabilities of cells that the mobile will next visit. We can estimate the probability distribution with order 0, 1, and 2. First, we can see that only one child "a" follows path '"be" in an order-2 prediction. So, we assign P2a = 1, P^b ~ ® > anc* ^2c = ® • Second, in an order-1 prediction based on the context "c", we assign Pla = 1 , Plb = 0 and Plc = 0 , since one child "a" is in the subtries rooted at node "c". Finally, in an order-0 estimate, we start from the root of the whole trie and get PQa = 5/13, PQb = 5/13 and P0c = 3/13. Given a blending weight vector w = [wQ, w,, w2] , the blended probability assignment is: Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 42 Pa = W2-P2a + Wl-Pla + W0-Pi Oa Pb = W2-P2b + Wl-Plb + W0-P< Ob Pc = w2-P2c + wrPlc + w0-p< Oc The weights can be fixed values or adapt as prediction proceeds to give more emphasis to high-order models. Different ways of choosing the weighs correspond to different PPM methods [9]. 3.3 Mobility Management in the Combined Framework In this section, we will present the MM scheme in the proposed combined framework using both out-of-session and in-session location information. Since analytic and simulation results in previous work show that path-based MM scheme is an efficient approach, we adopt the path-based scheme proposed in [13]. However, unlike with the original path-based scheme, in which the sole purpose of the location update is to aid paging, and where paging process depends only on the information provided by a location update, we use all available location information of a mobile for a more accurate modeling of individual users' mobility patterns. We present the original path-based scheme, our new path-based scheme, and numerical results of performance comparisons between the two schemes in the following subsections. 3.3.1 The Original Path-Based Scheme In path-based MM scheme [13], movement path history rather than current location is sent in an update message. The movement path history consists of a list of cell IDs the mobile terminal has crossed after the last update. The path-based scheme works as an add-on module Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 43 t t t t t t t a b a b cab C a b \a *' JWVA a B * • Tc ti time : Location update ~i : Information used in location prediction of time Tc Figure 3.2 The original path-based scheme to the underlying update scheme (e.g., LA-based), which generates the movement path history. However, a real update message is not sent to the network by the mobile for each movement. As with data compression, the algorithm sends the "compressed" movements to the network. For simplicity, assume that a mobile has visited a sequence of cells, "ababcabCaBabcaB..." which is same as that shown in Example 3.1. The capital letters represent the cells in which the mobile had a call, i.e., the in-session location information, and other letters represent the cells in which the mobile did not have a call, i.e., out-of-session location information. The transmissions of update messages in the original path-based scheme are shown in Figure 3.2, where Tc is the current time. Assume that the mobile is called at time Tc. The network can predict the location probability from previous update messages using the mobility prediction scheme in Section 3.2. After getting probabilities Pa, Pb and Pc, the network will page the mobile by ordering cells according to a decreasing sequence of probability values. Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 44 ft t t a b a b cab C a b a B time J : Location update ^ : In-session location information report ; : Information used in location prediction of time Tc Figure 3.3 The proposed path-based scheme 3.3.2 The New Path-Based Scheme The original path-based scheme does not use the in-session location information. However, the network knows the exact location of a mobile during the call session, which is very useful in searching the mobile, especially when the call-to-mobility ratio is high. Therefore, we propose to use this information in the new path-based MM scheme. In the proposed new path-based scheme shown in Figure 3.3, a mobile will give the network all unreported location information during the call session. Note that this in-session location information report requires little extra resources, because a mobile must report its location and any location changes to the network during each call in current cellular systems. Otherwise, the call cannot be delivered correctly. After the in-session location information report, the mobile will send a location update message only after it transverses a new path unseen before. For example, in Figure 3.3, a new out-of-session sequence "aba" is sent to the network after the in-session location information report in "C." There are 6 location updates before the time Tcin Figure 3.3, which is less than 7 location updates in the original path-based scheme. Without loss of generality, since some location information of a mobile is Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 45 reported to the network during the call session, the location sequences reported by out-of-session location updates in the new scheme should be shorter than those in the original scheme. Therefore, fewer update messages are needed in the new scheme, especially when the call-to-mobility ratio is high. On the network side, the same mobility trie is constructed to predict user mobility. However, in the new scheme, we can use more up-to-date information to make the prediction. For example, "caB" is used in Figure 3.3 and "aBc" is used in Figure 3.2. Obviously, prediction in the new scheme will be more accurate. If there is no in-session information between the last update and the current time, the prediction will be the same in the new scheme as in the original one. 3.3.3 Simulation Results and Discussions The simulation environment is similar to that in Chapter 2. We assume that the cell residence time follows an i.i.d. Gamma distribution with average time l/ur minutes. New calls arrive according to Poisson process with rate A, per minute and call durations are exponentially distributed with a mean value of l/ud, which is 3 minutes, p = X/ur is the call-to-mobility ratio. The underlying location update scheme is movement-based [8], which generates the movement path history. In this scheme, each mobile terminal counts the number of boundary crossings between cells incurred by its movements. A location update is performed when this number exceeds a predefined movement threshold. We use 1 as the threshold in the simulations. Given specific parameters, we can get the update messages when using the original Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 46 path-based scheme, denoted as "Update (original)." The term "Update (new)" denotes the number of update messages when using the new path-based scheme. The performance gain is the ratio Update (original)/Update (new). A similar procedure is used in evaluating the paging process. "Paging (original/new)" denotes the number of cells paged in the original/new scheme and Paging (original)/Paging (new) is the performance gain. Figures 3.4 and 3.5 show the performance gain versus the call-to-mobility ratio with different cell residence time. From these two figures, we can see that the performance gain is always greater than one. That is, Update (original) > Update (new) and Paging (original) > Paging (new). This implies that the proposed new scheme has less cost for mobility management, and therefore, has better performance than the original one. When the call-to-mobility ratio is small, the performance gain is not significant in these two figures. However, when the call-to-mobility ratio is large, the new scheme needs much fewer update messages and paging cells than the original one. This is because the new scheme uses both in-session and out-of-session information in the location management process. The higher the call-to-mobility ratio, the more in-session mobility information is used in the new scheme. We also observe that cell residence time has some effects on the performance gain in these figures. When cell residence time is small (i.e., ur is large), the mobile travels a lot and has more mobility information. The new scheme can give a better model and more accurate prediction of user mobility, and therefore, has more performance gain over the original one. 3.4 Call Admission Control in the Combined Framework Due to in-session user mobility, the CAC scheme needs to perform mobility-related QoS provisioning in cellular networks. If the in-session user mobility can be predicted, Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 47 efficient CAC schemes can be designed. In this section, we propose a novel CAC scheme within our combined framework. The key idea in our CAC scheme is to predict where and when the mobile will subsequently visit when the mobile originates or accepts a call. Then, we can check the availability of resources in these cells when resources are needed. If the resources are available, they are reserved for this mobile to guarantee the target Pnd, the probability of handoff call being dropped. In our framework, we can easily predict to which cell the mobile will move using our common mobility prediction scheme described in Section 3.3. However, since we do not record the time in our combined framework, we need to determine the time interval of the visit to make efficient resource reservations. Fortunately, we can use the mobile station positioning technology developed and standardized recently in [64] to get this time interval. We present these ideas in the following subsections. 3.4.1 Time Interval Prediction For the purpose of satisfying the US FCC E-911 location requirement and for driving location information applications in Europe, recent advances in mobile station positioning technology can locate a mobile within a certain accuracy level (i.e., 50m in 67% of cases and 150m in 95% of cases for handset based location solution, mandated by US FCC) [64]. We can use this location information to improve the system performance and increase wireless system functionality for location-based commercial services. In this study we are interested in how to design better CAC schemes using this technology. A variety of basic technologies are available to determine accurate position locations. One of them is the enhanced observed time difference (E-OTD) technology [3], which has been standardized for location services in GSM-based systems. Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 48 In the E-OTD method, the unknown mobile position p = (x, y) is estimated by processing the time difference of arrival (TDOA) measurements between the mobile and at least three base transceiver stations (BTSs) of known co-ordinates, BTS1; BTS2, BTSN. The TDOA between BT^ (the serving BTS) and BTS, (i = 2, N - the neighbor BTSs) defines a hyperbola whose foci coincide with the co-ordinates of the two BTSs. At least two hyperbolas (i.e., two TDOAs) are minimally sufficient to estimate the mobile position, as shown in Figure 3.6. The TDOA is defined as the geometric time difference (GTD). GTD, = ti - T,- 0 = 2,AO, where x, and x,- are the absolute propagation delays from the serving and the ith neighbor BTSs to the mobile. In principle, GTD can be determined by measuring the difference in reception epochs (REs) of bursts synchronously transmitted by the BTSs and received by the mobile. In practice, due to the non-synchronized BTSs, the different transmission epochs must be taken into account, x, is defined as x, = tRx, - tTx., where tRx, and tTx, are, respectively, the reception and transmission epochs of the burst from the ith BTS. With these definitions, GTD, can be written as the difference between the observed time difference (OTD) and the real time difference (RTD): GTD, = T, - x, = {tRXi - tRx) - (tTX{ - tTx) = OTD,- - RTD,. The mobile itself assists the location estimation by measuring the OTDs. The RTDs are measured by network monitoring equipment deployed in fixed and known locations. The positioning problem in the absence of measurement errors can be formulated with a set of AM equations describing hyperbolas with foci at the BTSs' co-ordinates (xit yj) (i= 1,AO and intersecting at p = (x, y): Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 49 GTD, = J{x -xxf + {y- y,)2 - J(x - xf + (y - y,)2, i = 1,...,N (3.1) where c is the speed of light. Exact non-iterative solutions of this problem can be found in [30]. If we can get the estimations of a mobile's locations, it is not difficult for us to estimate the velocity of the mobile, from which we can predict the time interval of the visit. However, in real applications, equation 3.1 is rendered inconsistent by measurement noise. A linear regression setup can be used to smooth the data for more accurate velocity and position estimation of a mobile [40]. In this scheme, k previous estimations are used to get the mobile's current estimated velocity and position. Let p(r„) = [x{tn), y(tn)], n = 1, M represent the estimated locations at subsequent time points tn. The velocity of a mobile can be obtained [40]: v(fB) = ||v(f,-)|| = [vz,(0 + v^(0]1/2, (3.2) where vx(tn) = X (tj-t)[x(tj)-x] j = n - k + 1 2 (h-i) and vy(tn) = £ (tj-i)[y(tj)-y] j = n - k + 1 n with t = I h \j = n-t + l J /k , X — 1 x(tj) \J = n-k+l •• n-k+\ ( /k and y = 1 y(tj) /k . The estimated position of the mobile at time tn is: (3.3) where 6(r„) is the estimated original position at time t0 = 0. ox(tn) = x-vx(tn) • t and oy(tn) = y-vy(tn) • t. Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 50 After getting the estimated velocity and the position of a mobile from equations 3.2 and 3.3, we can predict the time interval during which a mobile will visit a cell. Let ta(i, j) denote the time when the mobile in cell i will arrive at celland tji, j) denote the time when the mobile in cell i will depart from cell;'. ta(i, j) and td{i, j) can be calculated as: ta{Ui) = diV^j) and td(i,j) = + ^ • (3.4) where d(p(t),j) is the distance between the current position p(0 and the boundary of cell i and j, and d(j) is the route distance inside cell j. We assume this distance information is available from an internal map of the relevant area, since such information is essential to provide some location services in the future. 3.4.2 Call Admission Control Scheme The CAC scheme in our combined framework is similar to that in Chapter 2. We calculate p(Uj, ta, td), the probability that a mobile original in cell / will visit cell j during the time interval ta and td. Assume that the call durations follow exponential distribution with a mean value of \/ud. P(iJ, ta, td) = P(i,j) • P(The call is not terminated by td) = P(i,j) • *TudeUi,dt id = P{i,j)-e-u<\ (3.5) where P(i, j) can be calculated using the common mobility prediction scheme in Section 3.2. When a mobile is active in cell i, we can get the most likely cell-time (MLCT) of that mobile, a cluster of cells and time where and when the mobile will most likely visit in the future. We Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 51 select cell j and time ta, td with P(i,j, ta, td) greater than zero to form the MLCT of this mobile. Using P(i,j, ta, td), we can obtain the required bandwidth Br (i, j, m, ta, td) to be reserved in cell j for the expected handoff of m from cell i: Br(i,j,m,ta,td) = P(i,j,ta,td)-B{m) , (3.6) where B(m) is the effective bandwidth required by m. Moreover, the reserved bandwidth Br(j> td)» which is the aggregate bandwidth to be reserved in cell j during the time interval ta and td, is calculated as: Br(j,t„,td) = £ Br(i,j,m,ta,td) , (3.7) where M is a set of mobiles which will visit cell j from a set of cells / during the time interval. Br(j, ta, td) may not be a constant value due to the continuous time and the summation of equation 3.7. Finally, the free bandwidth left after the reservation is: B/J,ta,td) = B-Br(J,ta,td) , (3.8) where B is the total bandwidth in cell j. Again, note that Bj(j, ta, td) may not be a constant value. Let min[5y(/', ta, td)] denote the minimum value of free bandwidth in cell j during the time interval. When a new call arriving at mobile m with a bandwidth requirement B(m) requires admission to cell i, the CAC algorithm first checks if the current free bandwidth of cell i can support the call. The call is rejected if the cell does not have enough free bandwidth. Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 52 Otherwise, CAC will check the availability of free bandwidth in the MLCT of this mobile. The checking result can be written as the following: Check(j, ta, td, B(m)) = l,imn[Bj(j,ta,td)]<B(m) ™™<-<<)\ otherwise ' ^ B(m) Based on these values, the new call will be admitted if the following holds: I P(i,j,ta,td)Check(j,ta,td,B(m))>a £ P{i,j,ta,td) , (3.10) t,„ id e MLCT j, ta, td e MLCT where a is the admission threshold and should be controlled adaptively. 3.4.3 Simulation Results and Discussions The simulation environment is similar to that in Chapter 2. Some differences are as follows. We use 100 BUs as the link capacity to test our schemes in large link capacity situations. Moreover, we assume that the position information of a mobile is available but with error. The error of mobile position estimation follows a normal distribution A^O, a2) with o = 51 m, which will have an accuracy level of 50 m in 67% of the cases [3]. From the mobile's position information, we predict the time interval during which a mobile will visit a cell. Figure 3.7 shows the new call blocking probability Pnb and handoff dropping probability Phd as functions of offered load with two values of voice ratio. We observe that the handoff dropping probabilities are kept below the target value of 1%, which is similar to that in Chapter 2. Next, we evaluate the impact of different values of the adaptive factor e, Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 53 which is used to adaptively control the admission threshold to achieve a better balance of guaranteeing Phd and maximizing resource utilization. Figure 3.8 shows Phd as functions of simulation time in a cell with the offered load of 100 and ur = 0.2. We experiment with three values of £,0.01, 0.02 and 0.04. In the beginning of the simulation, the system has little information about users and cannot predict mobility accurately. Then, the admission threshold a is increased by a step of e to keep Pnd below the target value. From Figure 3.8, we observe that the scheme under-reacts when e = 0.01 and cannot quickly keep Phd below 1%, whereas it over-reacts when e = 0.04 and makes the Phd fluctuate near the target value. The value of 0.02 can keep Phd below the target value with reasonable speed and has no fluctuation. Choosing a suitable value of e according to real network conditions is very important to get the best performance from the proposed scheme. We use 8 = 0.02 in other simulations. We also compare the proposed CAC with two other schemes: (1) OKS98 [57]; and (2) YL01 [83] presented in Chapter 2. In OKS 98, bandwidth is reserved in all neighboring cells when a mobile has a new call or handoffs to a new cell. We choose the best scheme in [57] called movement-based and bandwidth-based for comparisons. In this scheme, different bandwidth is reserved in different neighboring cells based on user movement prediction and an algorithm is used to control the size of reserved bandwidth pool. However, OKS98 does not address how to predict user mobility. We can input the mobility prediction in our framework to OKS98. Thus, it can use the information regarding where the mobile will move in the reservation. Note that OKS98 does not use the prediction of when the mobile will move. In YL01, the mobility prediction scheme and CAC scheme are similar to those considered here. However, only in-session, but not out-of-session, mobility information is Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 54 collected and used for prediction. The proposed scheme is called combined framework (CF)-CAC in the following. Figure 3.9 shows the new call blocking probability and handoff dropping probability of CF-CAC, OKS98 and YL01. We observe that OKS98 can also keep Phd below the target value. However, it has higher Pnb, which means fewer new calls being admitted. This is because the proposed scheme predicts not only to which cell the mobile will handoff but also when the handoff will occur. Based on these mobility predictions, we can reserve bandwidth more efficiently. Because both YL01 and CF-CAC predict where and when of handoffs, the Pnb and Phd of YL01 are quite similar to those of CF-CAC, which are omitted in Figure 3.9. The utilization comparisons of these three schemes with different offered loads are shown in Figure 3.10. As expected, CF-CAC and YL01 have similar utilization, which is higher than that in OKS98. Figure 3.11 plots the Phd as functions of simulation time in a cell in YL01 and CF-CAC when the offered load is 100 and ur = 0.2. From this figure, we can observe that Phd can be kept below the target value in CF-CAC much faster than that in YL01. This is because although both schemes record user mobility history to make predictions, the proposed scheme uses all mobility information, both in-session and out-of-session, which makes the predictions converge faster compared with that of YL01. The proposed scheme is more desirable in a real network where user mobility and traffic patterns change over time, since it can adapt to changes faster, and therefore, make more accurate predictions. 3.5 Summary In this chapter, we have presented a novel framework combining QoS provisioning Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 55 and MM using all available mobility information. The key component of this framework is a common mobility prediction scheme, which can be used in both paging mobiles and making admission decisions. In addition, a new path-based MM scheme in the combined framework was proposed. Numerical results show that the new scheme offers performance gains over the original in terms of reduced update and paging costs. Finally, a CAC scheme based on our framework has been proposed. The proposed CAC scheme can predict where the mobile will handoff using the common mobility prediction scheme, and when the handoff will occur using positioning technology. Simulation results show that the proposed scheme meets our design goal and outperforms the CAC scheme in Chapter 2 and an existing scheme in [57]. Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 56 *"" U=0.2 -©- u=0.05 -B- u=0.01 0.5 1 1.5 2 Call-to-mobility ratio Figure 3.5 Paging performance gain vs. call-to-mobility ratio Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 57 Hyperbola of BTS3 (x3, y3) constant GTD3 Figure 3.6 Hyperbolic positioning in E-OTD, N = 3 Offered load (BU) Figure 3.7 Pnb and Phd vs. offered load Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 58 e=0.01 - e=0.02 -0- e=0.04 0 5 10 15 20 25 30 35 40 Simulation time (h) Figure 3.8 Phd vs. simulation time with different values of adaptive factor Offered load (BU) Figure 3.9 Comparison with YL01 and one of OKS98 schemes Chapter 3 A Framework Combining QoS Provisioning and Mobility Management 1.0 0.9 0.8 0.7 B 0.6 1 0.51 g 0.4 0.3 0.2 0.1 YL01 CF-CAC OKS98 100 150 Offered load (BU) 200 Figure 3.10 Comparison with YL01 and one of OKS98 schemes -+- YL01 CF-CAC V S-*—.... .^v-.rx'^v/^v„v*>—v*^^******^ 2000 3000 4000 5000 Simulation time (min) Chapter 4 QoS Provisioning for Adaptive Multimedia 60 Chapter 4 QoS Provisioning for Adaptive Multimedia 4.1 Introduction The last two chapters only consider non-adaptive traffic and non-adaptive cellular mobile networks, where the bandwidth of new or ongoing calls cannot be changed. However, in recent years, the scarce and highly fluctuating bandwidth of wireless links has motivated the development of adaptive multimedia applications that can operate over a wide range of available bandwidths. In adaptive multimedia applications, the bandwidth of a call can be dynamically adjusted to adapt to the. various communication environments, especially in the link overload situations. Under this adaptive multimedia framework in cellular mobile networks, a bandwidth adaptation algorithm needs to be used in conjunction with the CAC algorithm for QoS provisioning. This chapter presents a novel average reward reinforcement learning approach to solve the QoS provisioning problem for adaptive multimedia in cellular networks that aims to maximize the network revenue while satisfying several predetermined QoS constraints [90], [91]. The novelties of the proposed scheme are as follows: 1. The proposed scheme takes into account the effects of the status of neighboring cells with multiple classes of traffic, enabling it to dynamically adapt to changes in the traffic condition. 2. The underlying assumptions of the proposed scheme are more realistic than those in previous schemes. Particularly, the scheme does not need prior knowledge of system state transition probabilities, which are very difficult to estimate in practice due to the irregular Chapter 4 QoS Provisioning for Adaptive Multimedia 61 network topology, different propagation environment and random user mobility. 3. The algorithm can control the adaptation frequency effectively by formulating the cost of the bandwidth adaptation in the model. It is observed in [25], [71] that frequent bandwidth switching among different levels may consume a lot of resources and may be even worse than a large degradation ratio. The proposed scheme can control the adaptation frequency more effectively than previous schemes. 4. Trading off action space with state space is proposed in our scheme. As mentioned in [82], the large action space problem may hinder the deployment of the scheme in [82] in real systems. With the approach of trading off action space with state space, the large action space problem in QoS provisioning can be solved. 5. Average reward RL is used in this study. Average reward RL is more suitable than discounted reward RL in solving QoS provisioning problems in adaptive multimedia cellular networks. 6. Handoff dropping probability, average allocated bandwidth and inter-class fairness are considered simultaneously as QoS constraints in our scheme and can be kept below the predetermined values. The rest of this chapter is organized as follows. Section 4.2 describes the QoS provisioning problems in the adaptive multimedia framework. Section 4.3 introduces the average reward reinforcement learning algorithm. Our new approach to solve the QoS provisioning is presented in Section 4.4. Section 4.5 discusses some implementation issues of our approach. Section 4.6 presents and discusses the simulation results. Finally, we conclude this chapter in Section 4.7. Chapter 4 QoS Provisioning for Adaptive Multimedia 62 4.2 QoS Provisioning in Adaptive Framework 4.2.1 Adaptive Multimedia Applications Originally, adaptive multimedia applications are introduced in the wireline networks. Congestion in wireline broadband networks can cause fluctuations in the availability of network resources, thereby resulting in severe degradation of QoS. To overcome this problem, many techniques are proposed such as the adaptation of compression parameters [73] and layered coding [81]. The much more severe resource and bandwidth fluctuations in cellular mobile networks make it interesting to consider the use of adaptive multimedia in future cellular mobile systems. In adaptive multimedia applications, a multimedia call can dynamically change its bandwidth to adapt to the fluctuating communication environment throughout its lifetime. Assume that there are K classes of services in the network. A class i call uses bandwidth among {bn , ba, biJy bKNg} where bu < biU+1) for i = 1, 2, K,j = 1, 2, A7,- and Nj is the highest bandwidth level which can be used by class i calls. For example, using the layered coding technique, a raw video sequence is compressed into several layers [81], say, three layers: a base layer and two enhancement layers. The base layer can be independently decoded and it provides basic video quality; the enhancement layers can only be decoded together with the base layer and they further refine the quality of the base layer. Therefore, a video stream compressed into three layers can adapt to three levels of bandwidth usage (e.g., 64 kbps, 256 kbps, and 1Mbps). Chapter 4 QoS Provisioning for Adaptive Multimedia 63 4.2.2 Adaptive Cellular Mobile Networks Compared to wireline networks, the fluctuations in resource availability in cellular mobile networks are much more severe. This stems from two inherent characteristics of cellular mobile networks: fading and mobility. The fading in a wireless channel is highly varying with time and spatial dependencies which results in a transmission link with highly varying bandwidth. Moreover, mobile users are free to move from one cell to another one. The availability of resources of the original cell does not necessarily guarantee that the resources are available in new cells. The change in network resources can result in a major fluctuation in the availability of network resources served for a call. Due to the severe fluctuation of resources in wireless mobile networks, the ability of adapting to the communication environment is very important in future cellular mobile systems. For example, in universal mobile telecommunications system (UMTS), a radio bearer established for a call can be dynamically reconfigured during the call session [1]. Figure 4.1 shows the signaling procedure between user terminal (UE) and universal terrestrial UE UTRAN RADIO BEARER RECONFIGURATION RADIO BEARER RECONFIGURATION COMPLETE Figure 4.1 Radio bearer reconfiguration in UMTS Chapter 4 QoS Provisioning for Adaptive Multimedia 64 radio access network (UTRAN) in radio bearer reconfiguration. Radio bearer information in UMTS includes most of the information in layer 2 and layer 1 for that call, e.g., radio link control (RLC), power control, spreading factor, diversity, etc. By reconfiguring the radio bearer, the bandwidth of a call can be changed dynamically during a call session. 4.2.3 QoS Provisioning in Adaptive Framework The goal of QoS provisioning in an adaptive multimedia framework is to maximize the long-term network revenue and guarantee QoS constraints. We consider two important modules for QoS provisioning, CAC and BA, in this study. When a cell is in under-loaded condition, CAC tries to accept every call and BA tries to allocate as much bandwidth as possible to each call. However, network congestion may occur and QoS constraints may be violated. In this case, calls should be rejected by CAC or degraded to a lower bandwidth by BA. On the other hand, if a call releases the bandwidth due to either call completion or handoff to another cell, some of the calls left in that cell might increase their bandwidths. To decide which call to accept and which call(s) to change the bandwidth are the roles of CAC and BA, respectively, in the adaptive multimedia framework. To reduce network signaling overhead, we assume that the BA can only be used when a call arrival or departure occurs. That is, BA will not be used when a brief congestion occurs due to channel fading, because the reallocation of resources will be outdated when it is received by the mobile and the action taken in response to the brief congestion is likely to be ineffective. Low level mechanisms such as error correction coding and efficient packet scheduling are usually used to handle brief throughput variations of wireless links. Chapter 4 QoS Provisioning for Adaptive Multimedia 65 Smaller cells (micro/picro-cells) will be employed in future cellular mobile networks to increase capacity. Therefore, the number of handoffs during a call's lifetime is likely to be increased and the status of neighboring cells has an increased influence on the QoS of the local cell. In order to adapt to changes in traffic pattern, the status information of neighboring cells should be considered in QoS provisioning. We consider three QoS constraints in this study. Since forced call terminations due to handoff dropping are generally more objectionable than new call blocking, an important call-level QoS constraint in wireless cellular networks is Phd , the probability of handoff dropping, which is same as that in non-adaptive case considered in Chapters 2 and 3. In addition, although adaptive applications can tolerate decreased bandwidth, it is desirable for some applications to have a bound on the average allocated bandwidth. So, we need another QoS parameter to quantify the average bandwidth received by a call. The normalized average allocated bandwidth of class i calls, denoted as AB1, is the ratio of the average bandwidth received by class i calls to the bandwidth with un-degraded service. In order to guarantee the QoS of adaptive multimedia, AB' should also be kept above a target value. Finally, due to bandwidth adaptation, some calls may operate at very high bandwidth levels, whereas some calls within the same class may operate at very low bandwidth levels. This is undesirable from users' perspective. Therefore, QoS provisioning scheme should be fair to all calls within one class and intra-class fairness is another QoS constraint. These constraints will be formulated in Section 4.4. We formulate the QoS provisioning problem as a semi-Markov decision process Chapter 4 QoS Provisioning for Adaptive Multimedia 66 (SMDP) [61]. There are several well-known algorithms, such as policy iteration, value iteration and linear programming [61] that find the optimal solution of SMDP. However, these traditional model-based solutions (require state transition probabilities) to SMDP suffer from two "curses": The curse of dimensionality and the curse of modeling. These curses motivate us to pursue alternative approach to solve this problem. 4.2.4 Average Reward RL In recent year, an alternative approach called reinforcement learning has become a topic of intensive research. RL combines concepts from dynamic programming, stochastic approximation via simulation, and function approximation that may be performed with the help of regression or neural networks. This method has two distinct advantages over model-based methods. The first is that it can handle problems with complex transitions by making judicious use of stochastic approximation thereby eliminating the need to compute or store the transition probabilities. Secondly, RL can integrate within it various function approxima tion methods (e.g., neural networks), which can be used to approximate the value function even when the size of the state space is gargantuan. Most of the published research in RL is focused on the discounted sum of rewards as the optimality metric. In some domains, such as economics, discounting can be used to represent "interest" earned on rewards, so that an action that generates an immediate reward will be preferred over one that generates the same reward some steps into the future. Q-learning [77] is one of the most popular discounted reward RL algorithms. These techniques, however, cannot extend automatically to the average reward problem, which is harder to Chapter 4 QoS Provisioning for Adaptive Multimedia 67 analyze even when the model is readily available. Not surprisingly, the corresponding developments for average reward problems have been slower. In many engineering design and decision making problems, performance measures may not suitably be described in economic terms, and hence it may be preferable to compare policies based on time averaged expected reward rather than expected total discounted reward. Some examples of such measures are average waiting time of a job in the queue, average number of customers in the system, average throughput of a machine, and average percentage of satisfied demands in an inventory system. The QoS provisioning problem in this study falls in this category. Discounted RL methods, e.g., g-learning, can lead to sub-optimal behavior and may converge much more slowly than average reward RL methods [52]. An algorithm for average reward RL called SMART (Semi-Markov Average Reward Technique) [26], [37], [38] has emerged recently. The convergence analysis of this algorithm is given in [37] and it has been success fully applied to production inventory [26] and airline seat allocation [38] problems. We use this average reward RL method to solve the QoS provisioning problem for adaptive wireless multimedia in this chapter. The formulation and the performance of this method in solving QoS provisioning are presented in the following sections. 4.3 Average Reward RL for Solving SMDP 4.3.1 Average Reward SMDP For an SMDP, let 5 be a finite set of states and A be a set of possible actions. For se S, when an action a e A is chosen, a lump sum reward of k(s, a) is received. Further accrual of reward occurs at a rate c(s\ s, a), s' e S, for the time the natural process remains Chapter 4 QoS Provisioning for Adaptive Multimedia 68 in state s' between the decision epochs. Note that the natural process may change state several times between decision epochs, and therefore, the rate at which the rewards are accumulated between decision epochs may vary. The expected reward between two decision epochs, given that the system is in state s, and a is chosen at the first decision epoch, may be expressed as: r(s,a) = k(s, a) + E^f c(W„ s, a)dt^ , (4.1) where x is the transition time to the second decision epoch, and W, denotes the state of the natural process. Let n, denote the number of decisions made up to time t. Starting from state s at time 0 and using a policy 7t, the expected total reward generated by the process up to time t can be written as: n,-i v^s) = E:^'oc(wu,Sn,an)du+ £ + j • (4.2) The average reward gn for a policy can be given as: EnA £ [k(sm an) + £+,c(W„ an)dt] g\s) = lim—[— . (4.3) E: N St-n = 0 where a„ represents the time of the (n+l)th decision epoch and T„ = an +, - rj„. The Bellman optimality equation for average reward SMDPs can be stated as follows [61]. Theorem 4.1: Under considerations of average reward over an infinite time horizon Chapter 4 QoS Provisioning for Adaptive Multimedia 69 for any unichain SMDP, there exists a scalar g* and a value function R* satisfying the system of equations for all s' e S, R*(s) = max(r(s, a)-g*y(s, a) + £ ' (4-4) where y(s, a) is the expected sojourn time in state s when action a is taken in it, and Pss(a) is the probability of transition from state s to state s' under action a in one step. For a proof of Theorem 4.1, see Chapter 11 of [61 ]. There are several model-based algorithms that can be derived from the above Bellman equation for solving SMDPs. However, the two "curses" suffered by the model-based algorithms make these model-based algorithms impractical in solving SMDP for QoS provisioning in adaptive multimedia cellular systems. Therefore, we use the model-free RL algorithm to solve the average reward SMDP, which is described in the following subsection. 4.3.2 Solving the Average Reward SMDP Using RL RL is a way of teaching agents (decision makers) optimal policies by assigning rewards and punishments for their actions based on the temporal feedback obtained during active interactions of the agent with the system environment. In the RL model depicted in Figure 4.2, a learning agent selects an action for the system that leads the system along a unique path till another decision-making state is encountered. At this time, the system needs to consult with the learning agent for the next state. During a state transition, the agent gathers information about the new state, immediate reward and the time spent during the state-transi tion, based on which the agent updates its knowledge base using an algorithm and selects the Chapter 4 QoS Provisioning for Adaptive Multimedia 70 System Environment State s Reward Action a Agent (Decision maker) Figure 4.2 A reinforcement learning model next action. The process is repeated and the learning agent continues to improve its perfor mance. Average reward RL uses the action value representation that is similar to its counter part, g-learning. The action value Rn(s, a) represents the average adjusted value of doing an action a in state s once, and then following policy n subsequently [52]. Let R*(s, a) be the average adjusted value by choosing actions optimally. The Bellman equation for average reward SMDPs equation 4.4 can be rewritten as: R*(s, a) = r(s, a) - g*y(s, a) + £ P„.(a) max R*(s\ b) . (4.5) I'ES The optimal policy is n*(s) = arg max R*(s\ b). Since the R function makes the action be A explicit, the average reward RL algorithm estimates action values on-line using a temporal difference method, and then uses them to define a policy. The action value of state-action pair Chapter 4 QoS Provisioning for Adaptive Multimedia 71 (s, a) visited at the nth decision making epoch is updated as follows. Assume that action a in state 5 results in a system transition to s' at the subsequent decision epoch, then, Rnew(s>a) = (l-an)Rold(S>a) + an\-ract(S,>S>a)-PnXn+ max RoM{s\ b)] , (4.6) where a„ is the learning rate parameter for updating of the action value of a state-action pair of the nth decision epoch and ract{s\ s, a) is the actual cumulative reward earned between nth and (n+l)th decision epochs. x„ is the actual sojourn time between the decision epochs. In the original version of SMART [26], the reward rate, p„, is shown as: where T(ri) denotes the sum of the time spent in all states visited till the nth epoch. The original version of SMART does not involve a step-size (learning rate) and hence its rate of change per iteration is not controlled, which will results in the divergence behavior of this algorithm in some situations. A new version of SMART is proposed and the convergence proof is given in [37]. In the new version algorithm, the reward rate, p„, is: Pn = r(»-l)p,.1 + r(j,> j,a) T(n) (4.7) Pn = (l-pVOPrt-l + PV T(n- l)p„_i + r(s\ s, a) T(n) (4.8) where (3„_! is the learning rate parameter. If each action is executed in each state an infinite number of times on an infinite run and a„, (3„ are decayed appropriately, the above learning algorithm will converge to optimality [37]. Chapter 4 QoS Provisioning for Adaptive Multimedia 72 4.4 Formulation of QoS Provisioning in Adaptive Framework In adaptive multimedia cellular networks, we assume that call arrivals including new and handoff call arrivals follow a Poisson distribution. Each call needs a service time that is exponentially distributed. The arrival distribution and the service distribution are independent to each other. The QoS provisioning for adaptive multimedia problem can be formulated as an SMDP. In order to utilize the average reward RL algorithm, it is necessary to identify the system state, actions, rewards, and constraints. The exploration method to guarantee the RL algorithm convergence and the method to trade off action space with state space are also described in this section. 4.4.1 State, Actions and Rewards At random times an event e can occur in a cell c, where e is either a new call arrival, a handoff call arrival, a call termination, or a call handoff to a neighboring cell. At this time, cell c is in a particular configuration x defined by the number of each type of ongoing calls in cell c. x = (xi i, JCT 2, ...,xij, XKNK ), where stands for the number of ongoing calls of class / using bandwidth btj in cell c for 1 < i < K and 1 <j < N,•. Recall that K is the number of service classes in the system and N(- is the highest bandwidth level of class i defined in Section 4.2. Since the status of neighboring cells is very important for the QoS provisioning, we should consider it in the state description. The status of neighboring cells y can be defined as the number of each type of ongoing calls in all neighboring cells of cell c. y = (y i T , y12, ..., ytj, yKNi(), where y^ stands for the number of ongoing calls of class i using bandwidth in all neighboring cells of cell c. The configurations and the event together determine the state, s = Chapter 4 QoS Provisioning for Adaptive Multimedia 73 (x,y,e). We assume that each cell has a fixed channel capacity C and cell c has M neighboring cells. The state space is defined by as: f K Ni K N, -j S = \s(x,y,e):2 5>A^;£ ^yi]bu^MC\ . The state space will increase dynamically by considering the status of neighboring cells. It will be very difficult, if not impossible, to solve the problem using model-based approaches. When an event occurs, the agent must choose an action according to the state. An action can be denoted as: a = (aa, ad, au), where aa stands for the admission decision, i.e., admit (aa = 1) or reject (aa = 0), ad stands for the action of bandwidth degradation when a call is accepted and au stands for the action of bandwidth upgrade when there is a departure (call termination or handoff to a neighboring cell) from cell c. ad has the form ad = {(d\2, ..., d% ..., f/N'Kl), 1 < i < K, Kj < Nh 1 < n <j}, where d"j denotes the number of ongoing class i calls using bandwidth by that are degraded to bandwidth bm. au has the form 1 $ au= (("12, ••;u"j, i<i<K, 1 <j<N,J<n<N,}, where u"j denotes the number of ongoing class i calls using bandwidth that are upgraded to bandwidth bin. Chapter 4 QoS Provisioning for Adaptive Multimedia 74 After the action of bandwidth degradation, the configuration (xn, xi2, •••,xij,..., XKNK ) becomes ' AT, JV, N, j-l Nk-l > xn + X d\m,xn+ £ dlm — d\2, ...,Xjj+ £ X ^</' •••>XKNK~ £ ^ m = 2 m = 3 m =j+l m = 1 m = l , Similarly, after the action of bandwidth upgrade, the configuration (xii, xl2, ...,Xij,..., XKNK) becomes ( N, j-l N, Nk-\ \ Mll> *12 + "ll- 2J M]2-- •' XU 2J 2J UV> - -XKNK+ 2-, UKm • ^ m — 2 m = 3 m - 1 m =+ 1 m = 1 y Based on the action taken in a state, the network earns immediate deterministic revenue due to the carried traffic in the cell. On the other hand, in order to inform the senders and receivers of their new bandwidths in the bandwidth adaptation, extra signaling overhead is required, which will consume radio and fixed line bandwidth, as well as the battery power in the mobile. It is observed in [25], [71] that frequent bandwidth switching among different levels may consume a lot of resources and may be even worse than a large degradation ratio. Thus, there is a trade-off between the network resources utilized by the calls and the signaling and processing load incurred by bandwidth adaptation operation. We use a function to model the cost due to the action of bandwidth adaptation. The definition of the cost function depends on specific traffic, user terminal, network architecture, etc. in real networks. One intuitive definition is that the cost is proportional to the number of bandwidth adaptation operations, which is used in this study. Let rtj be the reward rate of a class i call using bandwidth bip ca be the cost of one Chapter 4 QoS Provisioning for Adaptive Multimedia 75 bandwidth adaptation operation, and Na(a) be the total number of bandwidth adaptation operations in action a. The actual cumulative reward, ract(s\ s, a), between two successive decision epochs starting in state s (with action a) and ending in state s' can be calculated as: K N, ract{s\ s, a) = Tacl(s\ s, a) £ £ x'uru - N„(a)c„ , • = \j= i where Tact(s\ s, a) is the actual sojourn time between the decision epochs. By formulating the cost of the bandwidth adaptation operation in the model, we can control the adaptation operation frequency effectively. Note that all ongoing calls in the cell, including those that have been degraded or upgraded, contribute to the reward racl(s\ s, a). Therefore, we do not need an extra term to formulate the penalty related to the bandwidth degradation. 4.4.2 Constraints For a general SMDP with L constraints, the optimal policy for at most L of the states is randomized [6]. Since L is much smaller than the total number of states in the QoS provision ing problem considered in this study, the non-randomized stationary policy learned by RL is often a good approximation to the optimal policy [34]. To avoid the complications of random ization, we concentrate on non-randomized policies in this study. As mentioned in Section 4.2, the first QoS constraint is related to the handoff dropping probability. Upon the nth decision epoch, the probability of a handoff call being Chapter 4 QoS Provisioning for Adaptive Multimedia 76 dropped, denoted as Phd{sn), should be kept below a target value. Let TPhd denote the target maximum allowed handoff dropping probability. The constraint associated with Phd can be formulated as: N lim < TPhd . " ~* °° N n = 0 The Lagrange multiplier formulation relating the constrained optimization to an unconstrained optimization [11], [12] is used in this study to deal with the handoff dropping constraint. To fit into this formulation, we need to include the history information in our state descriptor. The new state descriptor is's = (Nhp Nnd, x, s), where Nhr and Nnc{ are the total number of handoff call requests and handoff call drops, respectively, from each class, x is the time interval between the last and the current decision epochs, and s is the original state descriptor. In order to make the state space finite, quantified values of Phd = Nhd/Nhr and x are used. A Lagrange multiplier to is used for the parameterized reward ; racl{s\'s,a) = ract{'s\ 1, a) - (az('s', s, a), where racl(s\ s, a) is the original reward function and z(s\ s, a) = PArf(S)TflC,(5', s, a) is the cost function associated with the constraint. A nice monotonicity property associated Chapter 4 QoS Provisioning for Adaptive Multimedia 77 with to shown in [11] facilitates the search for a suitable co. The second QoS constraint is related to AB', the normalized average allocated bandwidth of class i calls, let B' denote the bandwidth allocated to class i calls, AB' can be defined as the mean of B'/biN over all class / calls in the current cell. Recall that biNj is the bandwidth of a class i call with un-degraded service. N, AB< = E\f\ = mi = ^_ biN, X xu 7 = 1 ,i = l,...,K AB' should be kept larger than the target value TAB': ABl>TABl,i = \,...,K The third QoS constraint is the intra-class fairness constraint, which can be character ized as the variance of B'/biN over all class i calls in the current cell: N, N: flM _ var{fl'} _ E{{Bi)2}-E2{Bi) _ 7 = 1 j.i 2Zxu2Zxu(bu) ~ VB' = var ^- = , biN, biN. t N, \ Z xubu V7 = l J i = 1, ...,K. biN. ( N, \ lxu VJ = 1 J VB' reflects how different are the bandwidths between class i calls. For absolute Chapter 4 QoS Provisioning for Adaptive Multimedia 78 fairness, VB' should be kept to zero all the time. However, this will be very difficult in the real situation. Therefore, it is better to keep VB' below a target value TVB' as well: VB'>TVB\i = 1, K • Afi'and VB' are intrinsic properties of a state. With the current state and action information (s, a), we can forecast AB' and VB' in the next state s', AB'(s') and VB'(s'). If ABl(s?) < TAB1 and VB'(s') < TVB1, i = 1, K, the action is feasible. Otherwise, this action should be eliminated from the feasible action set A(s). 4.4.3 Exploration As mentioned in Section 4.3, each action should be executed in each state an infinite number of times to guarantee the convergence of RL algorithms. This is called exploration [10]. Exploration plays an important role in ensuring that all the states of the underlying Markov chain are visited by the system and all the potentially beneficial actions in each state are tried out. Therefore, with a small probability pn upon the nth decision-making epoch, decisions other than that with the highest action value should be taken. In this work, we use the Darken-Chang-Moody search-then-converge procedure [27] to decay the learning rates an, and the exploration rate pn. In the following expression, 0„ O can be substituted by an, P„ and pn for learning and exploration respectively. 0„ = y-^- , Chapter 4 QoS Provisioning for Adaptive Multimedia 79 where u = —p-—, where 0O and 0r are constants. 0r + n 4.4.4 Trading off Action Space Complexity with State Space Complexity We can see that the action space in our formulation is quite large. It will be very time-consuming to find the suitable action given a specific state using RL. As mentioned in [82], the large action space problem may hinder the deployment of the scheme proposed in [82] in real networks where the number of bandwidth levels is usually large. In this work, we propose a method to trade off action space complexity with state space complexity in the QoS provisioning scheme using an algorithm described in [10]. The advantages of doing this are that the action space will be reduced and the extra state space complexity may still be dealt with by using the function approximation described in Section 4.5. Suppose that a call arrival event occurs in a cell with state s, the action that can be chosen from is a = (aa, d\2, d"j, cCKNl(l), where there are at most V = 1+XZ(/-1) components. We can break down the action a into a sequence of V i = 1; = 2 controls &ai d\2i •••> djj, CIKNK > 3.i\d introduce some artificial intermediate "states (s, cta), (s, aa, d\2), ..., (s, aa, d\2, d"j, cfKkNt'), and the corresponding transitions to model the effect of these actions. In this way, the action space is simplified at the expense of introducing V- 1 additional layers of states and V- 1 additional action values R(s, a), R(s, aa, d\2) R(s, aa, d\2, • •., dip ..., c$Nk2) in addition to R(s, aa, d\2, ..., dnu, ..., cfKkNk'). Actually, we view Chapter 4 QoS Provisioning for Adaptive Multimedia 80 the problem as a deterministic dynamic programming problem with V stage. For v = 1, ..., V, we can have an v-solution (a partial solution involving just v components) for the vth stage of the problem. The terminal state corresponds to the V-solution (a complete solution with V components). Moreover, instead of selecting the controls in a fixed order, it is possible to leave order subject to choice. In the reformulated problem, at any given state s = (Nnr Nhd, x, x, y, e) where e is a call arrival of class i, the control choices are: 1. Reject the call, in which case the configuration x does not evolve. 2. Admit the call and no bandwidth adaptation is needed, in which case the configuration x evolves to (xu, xn, ..., xu, ..., xiNi + 1, ..., XKNK) . 3. Admit the call and bandwidth adaptation is needed. In this case, the problem can be divided into V stages. On the vth stage (v = 1, V), one particular call type that has not been selected in previous stages, say the one using bandwidth b,j with xtJ > 0, can be selected and there are following options: a. Degrade one call using bandwidth btj one level, in which case the configuration x evolves to (xn,xl2, xtj_, + 1, *y - 1, ..., xiNi + 1, ..., xKNf) . b. Degrade two calls using bandwidth btj one level, in which case the configuration x evolves to (xu, x12, ..., xu_2 + 2, xu - 2, ..., xiNi + 1, ..., XKNK) . c. Increase the number of calls being degraded until the call arrival can be accommo dated. Please note that the number of options depends on specific selected call type and the class of call arrival. Chapter 4 QoS Provisioning for Adaptive Multimedia 81 The similar trade-off can be done when a call departure event occurs. 4.5 Implementation Considerations 4.5.1 Approximate Representation of Action Values In practice, an important issue is how to store the action value R(s, a) in cellular mobile networks. There are several approaches, among which the lookup table is the most straightforward method to represent action values. A lookup table representation means that a separate variable R(s, a) is kept in memory for each state-action pair (s, a). This method will be prohibitive when the number of state-action pairs becomes large because memory require ment can be huge. Approximate representation should be used to break the curse of dimensionality in the face of very large state spaces. A neural network is an efficient method to represent the action values. A common popular neural network architecture is the multi layer perceptron (MLP) with a single hidden layer [10] as shown in Figure 4.3. Under this architecture, the state-action pair (s, a) is encoded as a vector and transformed linearly through the input layer involving coefficients in this layer to give several scalars. Then, each of these scalars becomes the input to the sigmoidal function in the hidden layer. Finally, the outputs of the sigmoidal functions are linearly combined using coefficients to produce the final output. These coefficients are also known as weights of the network. The network is trained in a supervised fashion using the back-propagation algorithm. This means that during training both network inputs and target outputs are used. An input pattern is applied to the network and an output is generated. This output is compared to the corresponding target output and an error is produced and propagated back through the Chapter 4 QoS Provisioning for Adaptive Multimedia 82 Linear Sigmoidal Linear Layer Layer LayeFigure 4.3 The neural network used in approximation network, and the network weights are adjusted to minimize the sum of the errors squared. The procedure is repeated until the error is reduced to a sufficient level. 4.5.2 Structure and Pseudo-code The structure of the RL-based QoS provisioning scheme is shown in Figure 4.4. First of all, an event (either a call arrival or a call departure) occurs and a state s can be identified by getting the status of the local cell and neighboring cells. Then, a set of actions {a} can be found according to the state. Feed the state and action information into the neural network to get the action values. With probability 1 -pn, choose the action with the largest action value. Otherwise, perform the exploration, i.e., choose an action randomly. When the next event occurs, the action value is updated and the process is repeated. A pseudo-code description of the proposed scheme is given in Figure 4.5. 4.6 Simulation Results and Discussions A cellular network of 19 cells is used in our simulations, as shown in Figure 4.6. To Chapter 4 QoS Provisioning for Adaptive Multimedia 83 Identify state s Find action set {a} Retrieve action values a With probability l-pn choose and execute an action with the largest action value. Otherwise, perform the exploration. Action value representation OH Action value update The next event occurs Figure 4.4 The structure of the QoS provisioning scheme initialize iteration count n -.= 0, action value R(s, a) := 0, cumulative reward CR := 0, total time T := 0, reward rate po := o while n < MAX_STEPS do calculate p„,a„,fusing iteration count n with probability of (l - pn), tradeoff action space with state space and choose an action^ e A that maximizes R(sm,aJ. Otherwise, choose a random (exploratory) action from A execute the chosen action wait for the next event e update Rm(sn,a,) = (l-a„)RM(sn,a.) + if the action value is stored in neural network R„w(s„,aJ-RM(s„,aJ is served as an back propagated error to learn the weight parameters in the neural network endif if an exploration action was not chosen update CR = CK + r(s„tl,,s-„,aj, =r +r(.v„tl,i„,a„) and endif update iteration count n = n + 1 Figure 4.5 A pseudo-code of the QoS provisioning scheme avoid the edge effect of the finite network size, wrap-around is applied to the edge cells so that each cell has six neighbors. For example, cells 2, 9,10,14,18 and 19 are the neighbors of Chapter 4 QoS Provisioning for Adaptive Multimedia 84 cell 8. Each cell has a fixed bandwidth of 2 Mbps. Two classes of flows are considered (see Table 4.1). Class 1 traffic has three different bandwidth levels, 128, 192 and 256 kbps. 64, 96 8 19> 9 18 7 . 2 3 10 17 6 , 1 4 11 16 15 , 5 v13 12 Figure 4.6 A cellular network used in simulations and 128 kbps are the three possible bandwidth levels of class 2 traffic. Two reward functions are used in simulations, as shown in Table 4.1. Reward function 1 represents the scenario that the reward generated by a call is a linear growing function with the bandwidth assigned to the call. Specifically, rtj = bij. In reward function 2, a convex function rtJ = -22£—^—^ 'n^-" max is used, where bmax is largest bandwidth used by a call in the network. We assume that the highest possible bandwidth level is requested by the call arrival. That is, call arrival of class 1 always requests 256 kbps and call arrival of class 2 always requests 128 kbps. Then the Table 4.1 Experimental parameters Traffic Class Bandwidth Level (kbps) Reward Function 1 Reward Function 2 Class 1 bn: 128 rn: 128 ru: 192 bn: 192 r12: 192 r12: 240 bn: 256 r13: 256 r13: 256 Chapter 4 QoS Provisioning for Adaptive Multimedia 85 Table 4.1 Experimental parameters Traffic Class Bandwidth Level (kbps) Reward Function 1 Reward Function 2 Class 2 b2l: 64 r21: 64 r21: 112 b22: 96 r22- 96 r22: 156 b23: 128 r23: 128 r23: 192 network will make the CAC decision and decide which bandwidth level the call can use if it is admitted. 30% of the offered traffic is from class 1. Moreover, call holding time and cell residence time are assumed to follow exponential distributions with mean values 180 seconds and 150 seconds, respectively. The probability of a user handing off to any adjacent cell is equally likely. The target maximum allowed handoff dropping probability, TPhd, is 1% for both classes. Other QoS parameters are changed in the simulations. The action values are learnt by running the simulation for 30 million steps with a constant new call arrival rate of 0.1 calls/cell/second. The constants used for the learning and exploration rates are chosen as ot0 = po = p0 = 0.1, and ar = p% = pr = 10n , which are common values in the Darken-Chang-Moody decaying scheme [27]. The monotonicity property associated with the Lagrange multiplier shown in [11] is used to search a suitable to, which is 157560 in the simulations. A multi-layer neural network is used in the approximate representation of action values. There are 31 inputs units representing the state and action, 20 hidden units with sigmoid functions, and one output unit representing the action value. Among the 31 input units, one unit represents the event; six units represent the status of the local cell and six units represent the status of neighboring cells; one unit represents the Chapter 4 QoS Provisioning for Adaptive Multimedia 86 handoff dropping probability; one unit represents the time interval between the last and the current decision epochs; 13 units represent the action; one unit represents the number of bandwidth adaptation operations; one unit represent the Lagrange multiplier; one unit is the bias unit that always has an input of one. The neural network is trained on-line by using the back-propagation algorithm in conjunction with the reinforcement learning. Two QoS provisioning schemes are used for comparisons, guard channel (GC) scheme [41], [60] for non-adaptive traffic and ZCD02 scheme [92] for adaptive multimedia. 256 kbps is reserved for handoff calls in the GC scheme. In ZCD02, an optimal call mix selection scheme is derived using simulated annealing. The proposed scheme is called RL in the following. The linear reward function is used in all simulation experiments unless otherwise mentioned. We first use uniform traffic in simulations, where the traffic load is the same among all 19 cells. Call arrivals of both classes to each cell form a Poisson process with mean A,. The average rewards of different schemes normalized by the GC scheme are shown in Figure 4.7. Average allocated bandwidth and intra-class fairness constraints are not consid ered here. We can see that RL and ZCD02 yield more rewards than GC. In GC scheme, bandwidth adaptation is not used and a call will be rejected if no free bandwidth is available. Both RL and ZCD02 have bandwidth adaptation function, and therefore, can yield more rewards than GC. In Figure 4.7, the reward of the proposed scheme is similar to that in ZCD02, because both of them can maximize network revenue in QoS provisioning. We can also observe that at low traffic load, as the new call arrival rate increases, the gain becomes Chapter 4 QoS Provisioning for Adaptive Multimedia 87 more significant. This is because the heavier the offered load, the more the bandwidth adapta tion is needed when the cell is not saturated. However, when the traffic is high and the cell is becoming saturated, the performance gain of RL and ZCD02 over GC is less significant. The cost of adaptation operation is not considered, i.e., ca = 0, in Figure 4.7. Figure 4.8 shows the effects of ca, the cost of adaptation operation, when new call arrival rate is 0.067 calls/cell/second. The reward of ZCD02 drops quickly as ca increases, and even becomes less than that in GC when ca = 150. In contrast, the reward drops slowly in RL. Since the proposed scheme formulates ca in the reward function, it eliminates those actions requiring a large number of adaptation operations when ca is high by comparing the action values of different actions. Therefore, the proposed scheme can control the adaptation cost, and therefore, the adaptation frequency, effectively. We use c„ = 30 in the following simulation experiments. Figure 4.9 shows that RL maintains an almost constant handoff dropping probability for a large range of new call arrival rates. In contrast, neither ZCD02 nor GC can enforce the QoS guarantee for the handoff dropping probability. We can reduce the handoff dropping probability in GC scheme by increasing the number of guard channels and in ZCD02 by increasing the "virtual gain function" of handoff calls. However, this will further reduce the reward earned in these two schemes. Figures 4.10 and 4.11 show the new call blocking probabilities of class 1 and class 2 traffic, respectively. Both ZCD02 and RL have less blocking probabilities compared with GC, because both of them have adaptation capability and can accept more new calls. Chapter 4 QoS Provisioning for Adaptive Multimedia 88 Figures 4.12 and 4.13 show the normalized allocated average bandwidths of class 1 and class 2 traffic, respectively. TAB' = 0.7 is considered here. We can observe that as the new call arrival rate increases, the average bandwidths of both classes in ZCD02 and RL decrease. This is the result of the bandwidth adaptation. For some applications, it maybe desirable to have a bounded average allocated bandwidth. In Figures 4.12 and 4.13, it is shown that the normalized allocated average bandwidth can be bounded by the target value in RL. In contrast, ZCD02 cannot guarantee this average bandwidth QoS constraint. The average bandwidth of GC is always 1, because no adaptation operation is done in GC. Please note that the lowest possible normalized average bandwidth is 0.5 for both classes. This can be seen from Table 4.1, where the lowest bandwidth level.is half of the highest bandwidth level for both classes. The normalized bandwidth variance, TVB, an indicator of intra-class fairness, is shown in Figures 4.14 and 4.15. We can see that RL can keep the bandwidth variance below the target value. Since the bandwidth in GC cannot be changed, the bandwidth variance is always 0 in GC. It can be seen that ZCD02 has very large bandwidth variance, which means that intra-class fairness cannot be satisfied in ZCD02. The achievements of higher QoS requirements come at a cost to the system. The effects of different values of TAB and TVB on the average reward are shown in Figures 4.16 and 4.17, respectively. We can see that higher TAB, which is preferred from users' point of view, will reduce the reward. Similarly, lower TVB, which means higher intra-class fairness, will reduce the reward as well. We also consider a non-uniform traffic situation, where the cells in the second ring, Chapter 4 QoS Provisioning for Adaptive Multimedia 89 i.e., cell 2-7 in Figure 4.6, have 1.5 times the new call arrival rate in the outer ring, i.e., cell 8-19. The central cell has 2 times the new call arrival rate in the outer ring. Since the method of predicting handoff rate from neighboring cells is not given in ZCD02, a static predicted handoff rate is used in the revenue function, and we call it ZCD02-static. Figure 4.18 shows that RL yields more rewards than ZCD02-static and GC schemes. The performance gain of RL over GC and the difference between RL and ZCD02-static are significant in the non uniform traffic situation. This is because our RL method takes into account the status of neighboring cells, and therefore, it can dynamically adapt to different traffic patterns. The traffic load in cellular networks is typically time varying. A typical traffic pattern [32] during a 24 hour business day is shown in Figure 4.19. The peak hours occur around 11:00 a.m. and 4:00 p.m. Figure 4.20 plots the normalized average rewards under the assump tion that the traffic loads are both non-uniformly distributed and temporally varying (maximum 0.067 calls/second). The reward is calculated on an hour-by-hour basis. The improvement of the proposed scheme over ZCD02-static is apparent. b^ (b b We then use a convex reward function rtj = —^ in the simulations. O max The reward rate for specific bandwidth level of each class is shown in Table 4.1. The simula tion results using the convex reward function show a very similar pattern to those using the linear reward function, and therefore, only one figure is provided here. Figure 4.21 shows the average rewards of different QoS schemes with non-uniform traffic. We can see that Figure 4.21 is similar to Figure 4.18. Chapter 4 QoS Provisioning for Adaptive Multimedia 90 ZCD02 uses simulated annealing to find the optimal call-mix, in which a variable called temperature is decreased periodically by employing a monotone descendent cooling function. We follow the example given in ZCD02, where 90 temperature steps are used and each step repeats 100 times. In each of 9000 steps, the revenue and the constraints are re evaluated. In RL, since neural network is used in the approximate representation, the major operations required to make the CAC and BA decisions come from retrieving action values and comparing these action values. We run the simulations with a fixed call arrival rate of 0.1 calls/second for 1000 call arrivals and departures, and calculate the average number of operations (additions, multiplications and comparisons) required to make one decision. Table 4.2 shows the average number of operations. We observe that ZCD02 needs many more operations than RL to make the CAC and BA decisions. This shows that ZCD02 will be more expensive than RL for computation resources in practice. However, training is needed for the RL approach, whereas ZCD02 and GC do not need any training. 4.7 Summary In this chapter, we have proposed a QoS provisioning scheme for adaptive multimedia in cellular mobile networks. By considering the status of neighboring cells, the proposed scheme can dynamically adapt to the changes in traffic condition. The rapid growth in the number of states and the difficulty to estimate the state transition probabilities in practical cellular systems motivate us to choose a model free average reward reinforcement learning solution to solve this problem. A method to trade off action space with state space has been proposed to solve the large action space problem in QoS provisioning. Three QoS constraints, handoff dropping probability, average allocated bandwidth and intra-class fairness are consid-Chapter 4 QoS Provisioning for Adaptive Multimedia 91 ered in the scheme. Simulation results have been presented to show the effectiveness of the proposed scheme in adaptive multimedia cellular networks. Table 4.2 Number of numerical operations QoS Schemes Number of numerical Operations ZCD02 181,240 RL 9,872 ler 4 QoS Provisioning for Adaptive Multimedia Adaptation operation cost Figure 4.8 Normalized average rewards vs. adaptation operation cost 10 New call arrival rate (calls/cell/second) Figure 4.9 Handoff dropping probabilities Chapter 4 QoS Provisioning for Adaptive Multimedia 93 0.91 1 1 1 r New call arrival rate (calls/cell/second) Figure 4.10 New call blocking probabilities of class 1 calls 0.9 r 1 1 1 1 1 r ^ 0.8 -New call arrival rate (calls/cell/second) Figure 4.11 New call blocking probabilities of class 2 calls Chapter 4 QoS Provisioning for Adaptive Multimedia 94 0.04 0.06 0.08 0.1 0.12 New call arrival rate (calls/cell/second) Figure 4.12 Normalized average bandwidths of class 1 calls 1 16 3 "O C 0.9 CO n o O) 0.8 2 0J ca 0.7 ~o Q) * 0.6 CO O 0.5 -e e e e--e- GC -x- RL Class 2 - - TAB' = 0.7 • B- ZCD02 Class 2 -e e-"B-— 0.02 0.04 0.06 0.08 0.1 0.12 New call arrival rate (calls/cell/second) Figure 4.13 Normalized average bandwidths of class 2 calls Chapter 4 QoS Provisioning for Adaptive Multimedia 95 CD O c a g 0.08I--0- ZCD02 Class 1 - - TVB] = 0.03 -*- RL Class 1 -e- QC •g 0.06 to .O ~o CD £ 004 <c E o 0.12 New call arrival rate (calls/cell/second) Figure 4.14 Normalized bandwidths variance of class 1 calls Figure 4.15 Normalized bandwidths variance of class 2 calls Chapter 4 QoS Provisioning for Adaptive Multimedia —x— RL (no average bandwidth guarantee) •B" RL (TAB1 = 0.7) -e- GC 0.04 0.08 0.08 0.1 0.12 New call arrival rate (calls/cell/second) 0.14 Figure 4.16 Normalized average rewards for different average bandwidth requirements RL (no average bandwidth guarantee) -H- RL (TVB' = 0.03) -e- GC 0.02 0.04 0.06 0.08 0.1 0.12 New call arrival rate (calls/cell/second) 0.14 Figure 4.17 Normalized average rewards for different bandwidth variance requirements Chapter 4 QoS Provisioning for Adaptive Multimedia 97 Figure 4.18 Normalized average rewards with non-uniform traffic 120 —v 100^ |l I ' ' >-0 5 10 15 20 Hour of day Figure 4.19 A traffic pattern of a typical business day Chapter 4 QoS Provisioning for Adaptive Multimedia 98 1.3, 1.2|-g 1.15^ 0 CO 1.1 > 1.05|-co N 1$—e—e—e—e—e—e—e—e—e—e—o—e—e—e—e—e—e—e—e—e—e—e—e—a> RL' ZCD02-static GC 10 Hour of day Figure 4.20 Normalized average rewards with time varying traffic Figure 4.21 Normalized average rewards with convex reward function and non-uniform traffic Chapter 5 M-EMAC for Cellular-to-IP Internetworking 99 Chapter 5 M-EMAC for Cellular-to-IP Internetworking 5.1 Introduction In this chapter, we address the issue of end-to-end QoS provisioning in cellular-to-IP internetworking. When a mobile/wireless user access the Internet via a cellular network, the traffic passes through two networks: cellular network and Internet. In these two networks, they have different QoS definitions and mechanisms. However, the QoS experienced by users is end-to-end, i.e., from the server to the mobile host. Therefore, effective internetworking schemes between cellular networks and the Internet are very important to guarantee the end-to-end QoS. Particularly, we study the EMAC scheme that is proposed to enable QoS in the Internet over wireline networks. Although EMAC has many desirable features in the wireline networks as shown in previous work, in this chapter, we will show that several distinct characteristics in cellular mobile networks make EMAC difficult to implement. On the other hand, cellular mobile network, e.g., UMTS, has been designed to include its own call admission control functions. We propose a mobile EMAC (M-EMAC) scheme for cellular-to-IP internetworking [85], [86]. Simulation results show that M-EMAC outperforms EMAC in the cellular mobile domain. The rest of this chapter is organized as follows. The EMAC scheme is presented in Section 5.2. Section 5.3 describes the performance of EMAC in cellular mobile networks. M-EMAC is proposed and its performance is evaluated in Section 5.4. Finally, we conclude this chapter in Section 5.5. Chapter 5 M-EMAC for Cellular-to-IP Internetworking 100 5.2 EMAC Scheme for the Internet The basic feature of EMAC proposed in previous work is to use end-to-end measure ments to determine whether the QoS requested by a new call can be supported over the net work, and if so to accept the new call. Figure 5.1 shows the two phases of a call: a probing phase and, if the call is accepted, a data transmission phase. First the sender that wants to set up a real-time call probes the network by transmitting a stream of fixed-length packets at con stant intervals, at the data rate that it wishes to reserve over the network. Upon reception of the first probing packet, the receiver starts measuring the probing packets' arrival statistics over a measurement period x. The measured statistics can be as simple as the average rate received during the period x, or more complex including delay and jitter statistics. At the end of the measurement period, the receiver estimates whether there are enough resources avail-Sender Receiver transmission phase Data Probing phase Figure 5.1 EMAC scheme for the Internet Chapter 5 M-EMAC for Cellular-to-IP Internetworking 101 able along the call path to meet a predetermined QoS requirement based on the statistics col lected. The sender is notified of this decision to start the data transmission phase or abort the call. In EMAC schemes, core routers are stateless and they need only to discriminate between classes of packets, in full agreement with the DiffServ paradigm. As observed in [19], there is a bandwidth stolen problem when fair queueing is used to service admission-controlled traffic; i.e., the bandwidth of a call having a successful probing phase may be sto len by subsequent arrivals. So, one should not use fair queueing or its variants to service admission-controlled traffic. Moreover, the admission-controlled traffic will coexist with cur rent best-effort traffic and it is necessary to provide isolation between them. So, one must use scheduling mechanisms with strict rate limits on the admission-controlled flows. Based on these considerations, we use priority queueing with a rate limiter [93] to separate admission-controlled flows from best-effort ones, with FIFO service within the admission-controlled traffic itself in the following study. Moreover, there are two choices in probing [19]: (a) send the probe packets at a lower priority than the admission-controlled data traffic (but still at a higher priority than best-effort traffic), called out-of-band probing; and (b) send the probe packets at the same priority as data traffic, called in-band probing. We will study both of these choices in our simulations. 5.3 EMAC in Cellular Mobile Networks Similar to TCP, EMAC has been designed to operate over wireline networks, where the hosts are fixed, the bit error rate (BER) is very low and packet losses occur mostly Chapter 5 M-EMAC for Cellular-to-IP Internetworking 102 because of congestion. However, in cellular mobile networks, the scarce bandwidth, higher BER on wireless links and host mobility combine to make the implementation of EMAC challenging. We study these issues in the following subsections. 5.3.1 Low Bandwidth Compared to the bandwidth of a typical Ethernet which is around 10 Mbps (100 Mbps for fast Ethernet), the link capacity in cellular mobile networks is very scarce. For example, 3G systems such as UMTS offer only about 380 kbps for high mobility users requiring wide-area coverage. For EMAC to work well in such networks, the loss probability experienced by the probe packet in the probing phase must be a good predictor of the loss probability experi enced by the data in the data transmission phase. We study this relationship in UMTS net works by simulations. In the simulation models, mobile users communicate with servers elsewhere through a wireless access network. We assume the majority of the traffic is sent from servers outside the cellular access network to the mobile users, and the sole congestion point of the system is the forward radio link. For simplicity, the amount of uplink traffic is assumed to be negligible and have no queueing delay. The link layer assumptions in the simulation follow the specifica tions for Enhanced Data rate for GSM Evolution (EDGE) [33], which is one of the radio access technologies in UMTS. Without going into greater detail, one can assume that there is one time frame every 20 msec, divided into 8 time-slots. A user is allowed to occupy one or multiple time-slots in each frame. EDGE also defines eight different combinations of modula tion and coding schemes, which have different data rates and robustness. A link adaptation Chapter 5 M-EMAC for Cellular-to-lP Internetworking 103 algorithm tries to select the most effective combination based on current channel conditions. For this study, we fix the modulation and coding scheme to the one with the second highest rate. It allows 112 bytes per time slot (excluding header), which results in a peak data rate of 44.8 kbytes/sec (358 kbps) [33]. In addition to using fixed modulation and coding scheme, we also assume that there is no packet error over the radio link in the current study, to investigate the effects of bandwidth difference between wireless and wireline networks on EMAC. In addition, we have also developed a similar wireline model for comparisons. The link bandwidth in the wireline model is 10 Mbps. The traffic in both models are generated by on-off traffic sources, as shown in Tables 5.1 and 5.2. One source has exponentially distrib uted on and off times with a mean of 1 second and the lifetime is exponentially distributed with a mean of 300 seconds. Another one has on and off times generated by a Pareto distribu tion with a mean of 1 second and the lifetime is taken from a lognormal distribution with a median of 300 seconds following. Due to the lower data rate in the cellular network, we expect mobile users to be more cautious about downloading very large files. So, we set the Table 5.1 Simulation parameters of traffic source 1 Model Burst Rate On Time Off Time Average Rate Lifetime Wireless 80 kbps 1 s (exp.) 1 s (exp.) 40 kbps 300 s (exp.) Wireline 512 kbps 1 s (exp.) 1 s (exp.) 256 kbps 300 s (exp.) Table 5.2 Simulation parameters of traffic source 2 Model Burst Rate On Time Off Time Average Rate Lifetime Wireless 80 kbps 1 s (Pareto) 1 s (Pareto) 40 kbps 300 s (logn.) Wireline 512 kbps 1 s (Pareto) 1 s (Pareto) 256 kbps 300 s (logn.) Chapter 5 M-EMAC for Cellular-to-IP Internetworking 104 average data rate to a lower value of 40 kbps in the wireless model and 256 kbps in the wire line model. Session arrivals are generated according to a Poisson process. In our simulations, only packet loss but not delay due to the network congestion is considered by the admission control process. Delay is instead limited by the use of small buff ers in the nodes, which should provide packet-scale buffering [65]. The admission-controlled traffic is given strict priority over best-effort traffic, but there is a bandwidth limit. In our sim ulations, we merely simulated the admission-controlled traffic as being serviced by a queue running at the speed of its bandwidth limit. This is very close to the behavior of a rate-limited priority queue. Simulations are run for 6,000 simulation seconds. The probe loss rate is calcu lated at the end of each probing period. Moreover, the packet loss probability of the estab lished sessions in the network is also recorded in the simulations for comparisons. We first consider the out-of-band probing scheme, which has two priority queues, one for the high pri ority accepted data traffic and the other for probe packets. 10 packets of the accepted data traffic and one packet of the probe stream can be buffered at the node.The probing time is 5 seconds. A robust EMAC should relate the probe loss probability experienced at the receiver to the expected session loss probability. Although this may be true in wireline networks, as shown in previous work, this relationship is very weak in the wireless domain. Figure 5.2 shows the probe loss probability and session loss probability using out-of-band probing in the wireless model. Figure 5.3 shows the probe loss probability and session loss probability using out-of-band probing in the wireline model. Traffic source 1 is used in these simulations. The Chapter 5 M-EMAC for Cellular-to-IP Internetworking 105 0.16 — Probe loss probability — Session loss probability 0.14 -0.12 -& 0.1 -S CO n O 0.08 -Q. W CO O 0.06 -0.041 2000 2100 2200 2300 2400 2500 2600 2700 2800 Simulation time (sec) Figure 5.2 Out-of-band probing in the wireline model offered load is such that the utilizations are 0.56 in both cases. The probe loss rate in the wire less model shows wide fluctuations, ranging from 0.02 to 0.74, although the session data loss rate has little variation. On the other hand, in the wireline case, the probe loss rate is much more constant and may act as a predictor for the session data loss rate. (Note that the scale of the vertical axis in Figure 5.3 is different from that in Figure 5.2.) Similar results have been obtained using traffic source 2. The key reason for the poor performance of out-of-band prob ing in the wireless domain is the low bandwidth and the burstiness of the data traffic. When the bandwidth is low, the multiplexing level is low and data traffic is active for only short periods of time. As a result, when data traffic is active, the probe packets cannot compete with the data packets, so the probe loss rate varies greatly, even when the utilization of the link is as low as 0.56. We can certainly increase the probing time to improve the performance, but it results in a substantial delay before the host can start sending data and much bandwidth being Chapter 5 M-EMAC for Cellular-to-IP Internetworking 106 CO JD o CO CO O 0.2 Probe loss probability - - Session toss probability 2000 2100 2200 2300 2400 2500 2600 2700 2800 Simulation time (sec) Figure 5.3 Out-of-band probing in the wireless model wasted, which are not desirable in real networks. One may think that this problem can be avoided using in-band probing, with the probe packets treated at the same priority level as data. We will study in-band probing in the follow ing. As shown in [19], there is a thrashing problem. When so many flows are probing at once that the drop rate is significant, none of the probing flows will be accepted. So, slow-start probing is suggested [19], whereby the probing rate slowly ramps up, to detect congestion without unnecessarily creating it. For example, we first probe at rate r/16 for 1 s, where r is the peak rate of the call; if the loss (or mark) percentage is below a threshold then probe at rate of r/8 for 1 s and the loss rate is checked again. This process is continued for 5 s. Although this scheme can prevent thrashing, the probing result in each shortened step, say 1 s, will not be accurate in predicting the actual session data loss rate, because there is a trade-off between probing time and prediction accuracy, especially in wireless networks. Figures 5.4 Chapter 5 M-EMAC for Cellular-to-IP Internetworking 107 r= 0.015 JD CO JD O CO CO 0.01 o Probe loss probability Session loss probability 2000 2100 2200 2X0 2400 2500 2600 2700 2800 Simulation time (sec) Figure 5.4 In-band probing in the wireline model and 5.5 show the probe loss probability and session data loss probability using in-band prob ing with traffic source 1 in the wireless model and wireline model, respectively. In these sim ulations, the probe is sent with the same priority as data at r/4 rate for 1 s in each case. Again, we see that in the wireless case, the probe loss probability during each 1 s interval varies greatly ranging from 0 to 0.41, thus giving poor predictions of the session data loss rates. (Note again that the scale of the vertical axis in Figure 5.5 is different from that in Figure 5.4.) The results of using traffic source 2 are similar. The poor performance of in-band probing is again due to the low bandwidth and the burstiness of the traffic, and also the short probing period. 5.3.2 User Mobility Since mobile users may change cells a number of times during the lifetime of their Chapter 5 M-EMAC for Cellular-to-IP Internetworking 108 0.4 CO 0.25 JD O CO CO o 0.2 Probe loss probability Session loss probability 2"000 2100 2200 2300 2400 2500 2600 2700 2800 Simulation time (sec) Figure 5.5 In-band probing in the wireless model calls, availability of wireless network resources at the call setup time does not necessarily guarantee that resources will be available throughout the lifetime of a call. Therefore, the probing result from one cell during the probing phase of a call may not predict accurately the session data loss rate during the lifetime of a call. One possible solution is to probe all the paths that the mobile user will visit during the lifetime. This is however not feasible in prac tice as probing is done in an end-to-end manner and it is not possible to probe for resource availability in the potential handoff cells in which the mobile user is not currently located. Furthermore, since the mobility of users is usually not known a priori, any approach that probes all potential handoff cells will waste a lot of precious wireless bandwidth. Chapter 5 M-EMAC for Cellular-to-IP Internetworking 109 5.3.3 High Bit Error Rate Wireless hosts use radio transmission for communications. This mode of communica tion is vulnerable to signal degradations due to the propagation environment and interference from other transmissions. BERs on wireless links are found to be about 10~6 or worse, com pared to 10~12 or better for fibre optic links. Moreover, communication over wireless links is often characterized by sporadic high BERs due to multipath fading [7]. The two main classes of techniques employed by reliable link-layer protocols are: forward error correction, and automatic retransmissions of lost packets. In UMTS, retransmission schemes are used at the radio link control/medium access control (RLC/MAC) layers. Since previous EMAC propos als are for wireline networks, only packet losses or congestion marks are considered as accep tance threshold, which is based on the assumption that packets are lost (or marked) because of network congestion. Unfortunately, this is not enough if wireless links are included in the probing path, because packets can be lost for reasons other than congestion and will be retransmitted over the wireless links. We show this by simulations of RLC block transmis sions over the air, with random block loss rate 3%. Figure 5.6 shows the sequence numbers of RLC blocks sent at specific time instants with the star dot indicting a lost block that is subse quently retransmitted. High BER and retransmissions in wireless links complicate the application of EMAC in wireless mobile networks, as they need to be considered in admission decisions, in addition to packet losses and congestion marks. Chapter 5 M-EMAC for Cellular-to-IP Internetworking 110 L i 1 I I I I I I.I I I I I I1*1.1 I I ,—1 1 1 1 l.l I I i * Correct block sequence No. I i i i i Lost block sequence No. j l 1 l i i ' i 913.7 913.8 913.9 914 914.1 914.2 914.3 914.4 914.5 914.6 Simulation time (sec) Figure 5.6 Retransmissions of RLC blocks 5.4 Mobile-EMAC for Cellular-to-IP Internetworking From the analysis and simulation results presented in the last section, we see that the distinct characteristics of cellular mobile networks make EMAC unsuitable for applications in the wireless domain. However, since EMAC has many desirable features in the wireline Internet, especially within the DiffServ framework, it could potentially be widely adopted in the future. Consequently we should have a scheme to internetwork the cellular network to the wireline Internet to add to the potential success of EMAC in the future. In this section, we. first review the QoS management functions in UMTS, based on which we propose a mobile-EMAC scheme that incorporates the internetworking function. The performance of the proposed scheme is evaluated by simulations. 4.0395 6 Z d) £2 4.039 CO 8" CO 4.0385 8 CQ 4.038 Chapter 5 M-EMAC for Cellular-to-IP Internetworking 111 5.4.1 UMTS QoS Management Functions Since UMTS is designed to provide multimedia and packet-switched services, Internet and intranet access, entertainment and value-added services, the UMTS standardization pro cess has taken steps to tackle QoS management functions in the 3rd generation partnership project (3GPP) [2]. QoS provisioning in UMTS is based on the traffic classification model with four main traffic classes: Conversational, Streaming, Interactive and Background classes. The main distinguishing factor between these classes is the delay sensitiveness of the traffic: Conversational class has the most stringent delay requirement, whereas Background class is the most delay insensitive class. In addition to classifying the traffic, the network needs to have means to provide and maintain the QoS for each admitted user traffic stream. UMTS QoS management functions can be logically divided into control and user plane functions. Call admission control addressed in this study belongs to the control plane functions described below. The control plane incorporates the following four main entities. The service manager co-ordinates the functions of the control plane for establishing, modifying and maintaining the service it is responsible for. The translation function converts between the internal service primitives for UMTS bearer service control and the various protocols for service control of external networks that are interconnected to the UMTS network, including conversion between UMTS BS attributes and QoS attributes of the external networks' service control protocols. Admission/capability control maintains information about all available resources of a network entity and resources allocated to all UMTS bearer services, determines for each Chapter 5 M-EMAC for Cellular-to-IP Internetworking 112 UMTS bearer service request or modification whether the required resources can be provided by this entity, and reserves these resources if they are allocated to the UMTS bearer service. Subscription control checks the administrative rights of the UMTS bearer service users to use the requested services with the specified QoS attributes. The QoS management functions for controlling the UMTS bearer service are shown in Figure 5.7. These functions support the establishment and modification of UMTS bearer services by signaling/negotiation with the UMTS external services and by the establishment or modification of appropriate UMTS inter nal services with the required characteristics. 5.4.2 Mobile-EMAC Scheme Since UMTS already incorporates admission control and capacity allocation functions TE Local Service Control MT Transl. Adm./Cap|. Control UMTS BS| Manager Local BS Manager Radio BS Manager UTRA ph. BS M UTRAN Adm./Cap. Control RAB Manager Radio BS Manager IuBS Manager UTRA ph. BS M lu NS Manager] CN EDGE UMTS Ba; Manager lu BS Manager CN BS Manager IuNS Manager BB NS Manager! protocol interface service primitive interface Adm./Cap Subscr. Adm./Cap. Control Control Control Gateway Transl. UMTS BS Manager CN BS Ext. BS Manager Manager BB NS Manager TE = Terminal equipment MT = Mobile terminal UTRAN = UMTS terrestrial radio access network CN = Core network BS = Bearer service RAB = Radio access bearer Ext Ext. Service Control Figure 5.7 QoS management functions for the UMTS bearer service in control plane Chapter 5 M-EMAC for Cellular-to-IP Internetworking 113 in its control plane that will be optimized for the wireless environment, information for call admission decision is readily available in the network elements. Thus the use of probing within the UMTS segment is unnecessary. Moreover, the UMTS control plane specifically includes translation functions that can be used to facilitate internetworking between UMTS and the various protocols for service control of external networks. Therefore, in our proposed M-EMAC, we terminate the EMAC probing for the wireline Internet at the UMTS gateway that serves as a pseudo-end-point for the EMAC protocol, as shown in Figure 5.8. We assume the majority of the traffic is sent from a remote host to the mobile host. In this case the gate way receives the probing packets and translates the QoS parameters inside the probing pack ets into UMTS QoS parameters. Then the admission/capacity control functions in UMTS check whether or not such a call request can be admitted and return the result using UMTS signaling. After the gateway gets both the checking result within UMTS and the probing result from the Internet, an admission decision can be made based on these results and the end hosts are informed accordingly. Figure 5.9 shows this procedure. In this internetworking Mobile-EMAC EMAC Remotel Host Internet r UMTS Admission Control UMTS Gateway Transl. Adm./Cap. Control UMTS BS Manager LL-h Mobile Host J Figure 5.8 Mobile-EMAC Chapter 5 M-EMAC for Cellular-to-IP Internetworking 114 Sender Gateway Mobile Host Probing phase Data trans, phase Figure 5.9 Mobile-EMAC procedure approach, the probing packets need not go through the UMTS network and we can avoid the problems described in Section 5.3. 5.4.3 Performance Evaluation In this subsection, we compare the performance of EMAC in wireless domain with that of the proposed M-EMAC. The simulation models include the EDGE model and the 10 Mbps wireline model described in Section 5.3. The traffic is sent from a server to a mobile via the 10 Mbps wireline network and the wireless EDGE network. There is a gateway between the wireless and wireline networks, which has the functions described in the last subsection. The radio link assumptions are the same as in Section 5.3, i.e., a fixed modulation and coding scheme. The traffic sources are also the same as before. In the M-EMAC scheme, the tradi-Chapter 5 M-EMAC for Cellular-to-IP Internetworking 115 tional measurement-based admission control (MBAC) [43] is used in the wireless network. As shown in [20], although various MBAC algorithms in the literature are derived from diverse motivations and theories, they all produce essentially the same performance. So, we use a simple measured sum (MS) algorithm [20] in the wireless part of the M-EMAC scheme. In EMAC schemes, we test the out-of-band probing in EMAC with acceptance thresholds 8 = 0.05, 0.09, 0.15, 0.25, 0.4, and the in-band probing in EMAC with £ = 0.01, 0.03, 0.05, 0.07, 0.09. We evaluate EMAC and the proposed M-EMAC algorithms according to how well they are able to achieve the highest possible utilization for a given level of service failure probability. We compare the performance frontier or loss-load curve achieved by each algo rithm. The loss-load curve depicts the rate of packet losses that occur at a given level of wire less channel utilization, as experienced by the mobile host. Figures 5.10 and 5.11 show loss-load curves of EMAC and M-EMAC. For a given EMAC algorithm (in-band probing or out-of-band probing) each point shown on the curve reflects the loss probability and utilization produced by a different e value. For the M-EMAC scheme, we test the utilization with differ ent loss rates of 0.0009, 0.003, 0.01, 0.03 and 0.09. Simulations are run for 6000 simulation seconds. Data collected during the first 1500 seconds are discarded. The plot data are obtained by averaging over 10 simulation runs with different random seeds. Traffic source 1 is used in these simulations. Other simulation parameters are the same as presented in the pre vious section. In Figure 5.10, where the probing time is 5 seconds, the frontiers of EMAC with in-Chapter 5 M-EMAC for Cellular-to-IP Internetworking 116 band and out-of-band probing seem to be fairly close to each other. However, for a given level of utilization the loss rates achieved by EMAC (both in-band probing and out-of-band prob ing) are much higher than those achieved by M-EMAC. The reason is that the probe loss rates do not give very accurate predictions of the session data loss rates in the wireless domain, as explained in Section 5.3. EMAC could presumably achieve better performance by probing for longer time periods. Figure 5.11 shows the loss-load curves achieved by EMAC with 20 sec ond probes. We can see that out-of-band probing for 20 seconds can achieve a better perfor mance than probing for 5 seconds (but still worse than that of M-EMAC), since a longer probing time yields probe loss rates that are closer to the session loss rates. However, while a longer time for in-band probing leads to decreased packet drop rates, they can cause the utili zation to be decreased substantially. Since the probe and data packets have the same priority, longer probing time means that more bandwidth is consumed by probe packets. We can get similar results using traffic source 2. These results show that the proposed M-EMAC outper forms EMAC in the mobile/wireless domain. 5.5 Summary In this chapter, we have studied the performance of EMAC in cellular mobile networks. Simulation and analysis results show that EMAC may not be suitable for cellular mobile environments due to the scarce bandwidth, user mobility and high bit error rate. On the other hand, cellular mobile network such as UMTS already includes call control and capacity allocation functions optimized for its environment. This motivates the M-EMAC scheme proposed in this study for cellular-to-IP internetworking. In the M-EMAC scheme, the gateway makes admission decisions based on the results of EMAC probing on the Chapter 5 M-EMAC for Cellular-to-IP Internetworking 117 wireline side and the admission control on the wireless side. Simulation results show that M-EMAC outperforms EMAC in the cellular mobile domain in terms of the end-to-end packet loss rate at any given level of channel utilization. Chapter 5 M-EMAC for Cellular-to-IP Internetworking 118 JD CO JD o 10' CO CO o -*- M-EMAC -e- EMAC (out-of-band probing 5s) EMAC (in-band probing 5s) 0.5 Utilization Figure 5.10 Loss-load curves of M-EMAC and EMAC (probing 5 s) JD CO JD O 10 CO CO o -*- M-EMAC -e- EMAC (out-of-band probing 20s) -B- EMAC (in-band probing 20s) 0.4 0.6 Utilization Figure 5.11 Loss-load curves of M-EMAC and EMAC (probing 20 s) Chapter 6 Conclusions 119 Chapter 6 Conclusions We conclude this thesis with a summary of our contributions and suggestions for future work. 6.1 Summary In Chapter 2, we proposed call admission control and bandwidth reservation schemes for non-adaptive traffic in cellular mobile networks, based on assumptions more realistic than in existing proposals. The sequences of events of new call admission, handoffs and call termination are modeled by stationary mth order Markov sources. We derived probabilistic predictions of next events based on the mobility history of users, using an algorithm motivated by optimal data compression. Based on the mobility prediction of where and when the mobile will handoff to the next cell, call admission control and bandwidth reservation schemes were developed. The performance of the proposed schemes has been studied using computer simulations. Handoff dropping probabilities can be kept below a target value in the proposed call admission control and bandwidth reservation schemes. It is also shown that our schemes can achieve a better balance of guaranteeing handoff dropping probability while maximizing resource utilization, and they outperform the static reservation scheme. In Chapter 3, we presented a framework combining QoS provisioning and mobility management. In this framework, we use all available information, both during calls and between calls to build the mobility trie, which is used in mobility prediction. Networks can use this mobility prediction scheme in both paging mobiles and making admission decisions. A new path-based MM scheme in the combined framework was proposed. Numerical results Chapter 6 Conclusions 120 show that the new scheme has performance gain over the original one, in that the new scheme can reduce both location update and paging costs. A new CAC scheme in our framework was proposed in the framework. The proposed CAC scheme can predict where the mobile will handoff using the common mobility prediction scheme and when the handoff will occur using positioning technology. Based on mobility predictions, bandwidth can be reserved more efficiently. Simulation results show that the proposed scheme meets our design goal and outperforms some existing schemes. In Chapter 4, we proposed a QoS provisioning scheme for adaptive multimedia in cellular mobile networks. The rapid growth in the number of states and the difficulty to estimate the state transition probabilities in practical cellular systems motivate us to choose a model-free reinforcement learning solution to solve this problem. Three QoS constraints, handoff dropping probability, average allocated bandwidth and intra-class fairness are consid ered in this scheme. The algorithm can control the adaptation frequency effectively by formulating the cost of bandwidth adaptation in the model. Trading off'action space with state space was proposed to solve the large action space problem in QoS provisioning. The perfor mance of the proposed scheme was demonstrated by simulations. The algorithm works well under a variety of traffic conditions with reasonable computation complexity. Finally, we studied the performance of EMAC in cellular mobile networks in Chapter 5. Although EMAC has many desirable features in wireline networks, simulation and analysis results show that EMAC may not be suitable in a cellular mobile environment due to the scarce bandwidth, user mobility, and high bit error rate. Since EMAC has many desirable Chapter 6 Conclusions 121 features in the wireline Internet, especially within the DiffServ framework, it could potentially be widely adopted in the future. We proposed an M-EMAC scheme to internet work the cellular network to the wireline Internet to add to the potential success of EMAC in the future. In the M-EMAC scheme, the gateway makes admission decisions based on the results of EMAC probing on the wireline side and the admission control on the wireless side. Simulation results show that the loss rates achieved by EMAC are much higher than those achieved by the proposed M-EMAC for a given level of utilization. These results demonstrate that M-EMAC outperforms EMAC in cellular mobile networks. 6.2 Further Work In the course of the investigations reported in this thesis, a number of interesting problems have been discovered which merit further research. • More Realistic Traffic and Mobility Models: Traffic and mobility models are essential for solving QoS provisioning problems in future cellular mobile networks. Although there are some traffic and mobility models available in the literature, new applications, such as multimedia message services (MMS), gaming and positioning applications, are emerging very fast. Few of the existing models are general enough to provide good approximations for these new applications. Further work is required in this area. • Vertical Handoff: Future wireless mobile networks will be heterogeneous. Simulta neously there will be a proliferation of different wireless access technologies - from those providing global coverage, such as cellular mobile networks, to those provid-Chapter 6 Conclusions 122 ing wireless hotspots such as wireless local area network (WLAN). As a result, mobile communications will be conducted over heterogeneous wireless networks. Continuous connectivity and QoS provisioning in these networks remain open issues. • Other QoS Provisioning Schemes in the Internet: Many other schemes to provide QoS in the Internet have been proposed, including new scheduling algorithms and new CAC schemes. To guarantee the end-to-end QoS of cellular mobile users, there may be some internetworking issues for mobile users accessing the wireless Internet. Finding an efficient way to internetwork cellular mobile network to the Internet is a very interesting problem. • User Profile: Some schemes in this thesis predict user mobility based on mobile users' histories, positions, velocities, etc. This information has to be stored in the user profile, which is very important to provide personalized services in future cellular mobile networks. An efficient way of collecting, storing, updating and disseminating the user profile information is crucial. Bibliography 123 Bibliography [I] 3GPP, "RRC protocol specification," TS25.331 version 3.12.0, Sept. 2002. [2] 3GPP, "Technical Specification Group Services and System Aspects, QoS Concept and Architecture," TS 23.107 version 3.9.0, Sept. 2002. [3] EIA/TIA IS-41.3 (Revision B), Cellular Radio-Telecommunications Intersystem Opera tions, July 1991. [4] T1P1, Evaluation Sheet for the Enhanced Observed Time Difference (E-OTD) Method, Doc. TlP1.5/98-021r8, Aug. 1998. [5] I. E Akyildiz, J. Ho, and Y.-B. Lin, "Movement-based location update and selective pag ing for PCS networks," IEEE/ACM Trans. Networking, vol. 4, no. 4, pp. 629-638, Aug. 1996. [6] E. Altman, Constrained Markov decision process, Chapman and Hall, London, 1999. [7] H. Balakrishnan, V.N. Padmanabhan, S. Seshan and R.H. Katz, "A comparison of mech anisms for improving TCP performance over wireless links", IEEE/ACM Trans. Net working, vol. 5, no. 6, pp. 756-769, Dec. 1997. [8] A. Bar-Noy, I. Kessler, and M. Sidi, "Mobile users: to update or not to update?," Wireless Networks, vol. 1, no.2, pp. 175-185, July 1995. [9] T. C. Bell, J. C. Cleary and I. H. Witten, Text Compression, Prentice-Hall Advanced Ref erence Series, Prentice-Hall, Englewood Cleffs, NJ, 1990. [10] D. P. Bertsekas and J. N. Tsitsiklis, Neuro-dynamic programming, Athena Scientific, Belmont, MA, 1996. [II] F. J. Beutler and K. W. Ross, "Optimal policies for controlled Markov chains with a con straint," J. Math. Anal. Appl, vol. 112, pp. 236-252, 1985. [12] F. J. Beutler and K. W. Ross, "Time-average optimal constrained semi-Markov decision processes," Adv. Appl. Prob., vol. 18, pp. 341-359, 1986. Bibliography 124 [13] A. Bhattacharya and S. K. Das, "LeZi-update: An information-theoretic framework for personal mobility tracking in PCS networks," Wireless Networks, vol. 8, no. 2, pp. 121-135, May 2002. [14] G. Bianchi, A. Capone, and C. Petrioli, "Throughput analysis of end-to-end measure ment-based admission control in IP", in Proc. IEEE INFOCOM'00, vol. 3, Tel Aviv, Israel, Mar. 2000, pp. 1461 -1470. [15] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang and W. Weiss, "An architecture for differentiated services," IETF RFC 2475, Dec. 1998. [16] V. Bolotin, "Modeling call holding time distributions for CCS network design and per formance analysis", IEEE J. Sel. Areas in Commun., vol. 12, no. 3, pp. 433-438, Apr. 1994. [17] R. Board and L. Pitt, "On the necessity of occam algorithms," in Proceedings of the 22nd Annual ACM Symposium on Theory of Computation, New York, NY, May 1990. [18] R. Braden, D. Clark, and S. Shenker, "Integrated services in the internet architecture: an overview," IETF RFC1633, June 1994. [19] L. Breslau, E. W. Knightly, S. Shenker, I. Stoica and H. Zhang, "Endpoint admission control: architectural issues and performance", in Proc. ACM SIGCOMM'00, Stock holm, Sweden, Aug. 2000, pp. 57-69. [20] L. Breslau, S. Jamin, and S. Shenker, "Comments on the performance of measurement-based admission control algorithms", in Proc. IEEE INFOCOM'00, vol. 3, Tel Aviv, Israel, Mar. 2000, pp. 1233 -1242. [21] S. Bunton, G. Borriello, "Practical dictionary management for hardware data compres sion," Commun. ACM, vol. 35, no. 1, pp.95-104, Jan. 1992. [22] C. Cetinkaya and E. Knightly, "Egress admission control", in Proc. IEEE INFO COM'00, vol. 3, Tel Aviv, Israel, Mar. 2000, pp. 1471-1480. [23] C. Chao and W. Chen, "Connection admission control for mobile multiple-class per-Bibliography 125 sonal communications networks," IEEE J. Select. Areas Commun., vol. 15, No. 8, pp. 1618-1626, Oct. 1997. [24] S. Choi and K. G. Kin, "Adaptive bandwidth reservation and admission control in QoS-sensitive cellular networks," in IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 9, pp. 882-897, Sept. 2002. [25] C. Chou and K. G. Shin, "Analysis of combined adaptive bandwidth allocation and admission control in wireless networks," in Proc. IEEE INFOCOM'02, vol. 2, New York, NY, June 2002, pp. 676-684. [26] T. K. Das, A. Gosavi, S. Mahadevan and N. Marchalleck, "Solving semi-markov deci sion problems using average reward reinforcement learning," Management Science, vol. 45, no. 4, pp. 560-574, 1999. [27] C. Darken, J. Chang, and J. Moody, "Learning rate schedules for faster stochastic gradi ent search," in Proc. IEEE Workshop on Neural Networks for Signal Processing, Hels-ingoer, Denmark, Sept. 1992. [28] V. Elek, G. Karlsson, and R. Ronngren, "Admission control based on end-to-end mea surements", in Proc. IEEE INFOCOM'00, vol. 2, Tel Aviv, Israel, Mar. 2000, pp. 623-630. [29] A. I. Elwalid and D. Mitra, "Effective bandwidth of general Markovian traffic sources and admission control of high-speed networks," IEEE/ACM Trans. Networking, vol. 1, no. 3, pp. 329-343, June 1993. [30] B. T. Fang, "Simple solutions for hyperbolic and related position fixes," IEEE Trans. Aerosp. Electron. Syst., vol. 26, no. 5, pp. 748-753, Sept. 1990. [31] Y. Fang and I. Chlamtac, "Teletraffic analysis and mobility modelling of PCS networks," IEEE Trans. Commun., vol. 47, no. 7, pp. 1062-1072, July 1999. [32] R. L. Freeman, Telecommunication System Engineering, 3rd ed., New York: Wiley, 1996. Bibliography 126 [33] A. Furuskar, M. Frodigh, H. Olofsson, and J. Skold, "System performance of EDGE, a proposal for enhanced data rate in existing digital cellular systems", in Proc. IEEE VTC'98, vol. 2, Ottawa, Canada, May, 1998, pp. 1284 -1289. [34] Z. Gabor, Z. Kalmar, and C. Szepesvari, "Multi-criteria reinforcement learning," In Proc. Int'l Conf. Machine Learning, Madison, WI, July 1998. [35] S. Ganguly and B. Nath, "QoS provisioning for adaptive services with degradation in cellular network," in Proc. IEEE WCNC'03, New Orleans, LA, Mar. 2003. [36] R. Gibbens and F. Kelly, "Distributed connection acceptance control for a connection less network", in Proc. ITC'99, Edinburgh, UK, June 1999. [37] A. Gosavi, An algorithm for solving semi-Markov decision problems using reinforce ment learning: convergence analysis and numerical results, Ph.D. Dissertation, Univer sity of South Florida, 1999. [38] A. Gosavi, N. Bandla and T. K. Das, "A reinforcement learning approach to airline seat allocation for multiple fare classes with overbooking," HE Transaction, vol. 34, pp. 729-742, 2002. [39] R. Guerin, H. Ahmadi, and M. Naghshineh, "Equivalent capacity and its application to bandwidth allocation in high-speed networks," IEEE J. Select. Areas Commun., vol. 9, no. 7, pp. 968-981, Sept. 1991. [40] M. Hellebrandt, R. Mathar, and M. Scheibenbogen, "Estimating position and velocity of mobiles in a cellular radio network," IEEE Trans. Veh. Technol., vol. 46, pp.65-71, Feb. 1997. [41] D. Hong and S. S. Rappaport, "Traffic model and performance analysis for cellular mobile radio telephone systems with prioritized and nonprioritized handoff procedure," IEEE Trans. Veh. Technol, vol. VT-35, no. 3, pp. 77-92, 1986. [42] F. Kielly, P. Key, and S. Zachary, "Distributed admission control, " 1EEEJ. Select. Areas Commun., vol. 18, no. 12, pp 2617-2628, Dec. 2000. Bibliography 127 [43] S. Jamin, P. B. Danzig, S. J. Shenker, L. Zhang, "A measurement-based admission con trol algorithm for integrated services packet networks", IEEE/ACM Trans. Networking, vol. 5, no. 1, pp. 56-70, Feb. 1997. [44] C. Jedrzycki and V. C. M. Leung, "Probability distributions of channel holding time in cellular telephony systems," in Proc. IEEE VTC'96, vol. 1, Atlanta, GA, May 1996, pp. 247-251. [45] T. Kwon, Y. Choi, C. Bisdikian and M. Naghshineh, "QoS provisioning in wireless/ mobile multimedia networks using an adaptive framework," Wireless Networks, vol. 9, no. 1, pp. 51-59, 2003. [46] G. G. Langdon, "A note on Ziv-Lempel model for compressing individual sequences," IEEE Trans. Inf. Theory, vol. 29, no. 2, pp. 284-287, Mar. 1983. [47] D. A. Levine, I. F. Akyildiz, and M. Naghshineh, "A resource estimation and call admis sion algorithm for wireless multimedia networks using the shadow cluster concept," IEEE/ACM Trans. Networking, vol. 5, no. 1, pp. 1-12, Feb. 1997. [48] B. Liang and Z. Haas, "Predictive distance-based mobility management for PCS net works," in Proc. IEEE INFOCOM'99, vol. 3, New York, NY, Mar. 1999, pp. 1377-1384. [49] Y. B. Lin, S. Mohan, and A. Noerpel, "Queueing priority channel assignment strategies for hanoff and initial access for a PCS network," IEEE Trans. Veh. Technol, vol. 43, no.3, pp. 704-712, Aug. 1994. [50] Y. B. Lin, A. Noerpel, and D. Harasty, "The sub-rating channel assignment strategy for PCS hand-offs," IEEE Trans. Veh. Technol., vol. 45, no. 1, pp. 122-130, Feb. 1996. [51] S. Lu and V. Bharghavan, "Adaptive resource management algorithms for indoor mobile computing environment," in Proc. ACM SIGCOMM'96, Palo Alto, CA, Sept. 1996, pp. 231-242. [52] S. Mahadevan, "Average reward reinforcement learning: Foundations, algorithms, and empirical results," Machine Leaning, vol. 22, pp. 159-196, 1996. Bibliography 128 [53] D. Mitra, M. I. Reiman and J. Wang, "Robust dynamic admission control for unified cell and call QoS in statistical multiplexers," IEEE J. Select. Areas Commun., vol. 16, no. 5, pp. 692-707, June 1998. [54] M. Mouly and M.-B. Pautet, The GSM System for Mobile Communications, Palaiseau, France, 1992. [55] M. Naghshineh and M. Schwartz, "Distributed call admission control in mobile/wireless networks," IEEEJ. Select. Areas Commun., vol. 14, no. 4, pp. Ill-Ill, May 1996. [56] M. Naghshineh and A. S. Acampora, "QoS provisioning in micro-cellular networks sup porting nultiple classes of traffic," Wireless Networks, vol. 2, no. 3, pp. 195-203, 1996. [57] C. Oliveira, J. B. Kim, and T. Suda, "An adaptive bandwidth reservation scheme for high-speed multimedia wireless networks," IEEE J. Select. Areas Commun., vol. 16, no. 6, pp. 858-874, Aug. 1998. [58] A. Papoulis, Probability, Random Variables, and Stochastic Processes, McGraw-Hill, 3rded., 1991. [59] G. P. Pollini and C.-L. I, "A profile-based location strategy and its performance," IEEE J. Select. Areas Commun., vol. 15, no. 8, pp. 1415-1425, Oct. 1997. [60] E. C. Posner and R. Guerin, "Traffic policies in cellular radio that minimize blocking of handoff calls," in Proc. 11th Teletraffic Cong. (ITC-U), Kyoto, Japan, Sept. 1985. [61] M. L. Puterman, Markov Decision Processes, Wiley Interscience, New York, USA, 1994. [62] R. Ramjee, D. Towsley, and R. Nagarajan, "On optimal call admission control in cellular networks," Wireless Networks, vol. 3, no. 1, pp. 29-41, 1997. [63] T. S. Rappaport, Wireless Communication: Principles and Practice, Englewood Cliffs, NJ: Prentice Hall, 1996. [64] J. H. Reed, K. J. Krizman, B. D. Woerner, and T. S. Rappaport, "An overview of the challenges and progress in meeting the E-911 requirement for location service," IEEE Bibliography 129 Commun. Mag., vol. 36, no. 4, pp. 30-37, Apr. 1998. [65] J. Roberts et al, "Broadband network teletraffic, Final report of action COST 242", Springer, 1996. [66] S. K. Sen, A. Bhattacharya, and S. K. Das, "A selective location update strategy for PCS users," Wireless Networks, vol. 5, no.5, pp. 313-326, Oct. 1999. [67] D. Sheinwald, "On the Ziv-Lempel proof and related topics," Proc. IEEE, vol. 82, no. 6, pp. 866-871, June 1994. [68] D. D. Sleator and R. E. Tarjan, "Amortized efficiency of list update and paging rules," Commun. ACM 28, vol. 2 , pp. 202-208, Feb. 1985. [69] J. A. Storer, Data Compression Methods and Theory, Computer Science Press, Rock-ville, MD, 1998. [70] S. Tabbane, "An alternative strategy for location tracking," IEEE J. Select. Areas Com mun., vol. 13, no. 5, pp. 880-892, June 1995. [71] A. K. Talukdar, B. R. Badrinath, and A. Acharya, "Rate adaptive schemes in networks with mobile hosts," in Pore. ACM/IEEE MOBICOM'98, Dallas, TX, Oct. 1998, pp. 169-180. [72] A. K. Talukdar, B. R. Badrinath and A. Acharya, "Integrated services packet networks with mobile host: Architecture and performance," Wireless Networks, vol. 5, no. 2, pp. 111-124. 1999. [73] D. Taubman and A. Zakhor, "A common framework for rate and distortion based scaling of highly scalable compressed video," IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 4, pp. 329-354, Aug. 1996. [74] H. Tong and T. X. Brown, "Adaptive call admission control under quality of service con straints: a reinforcement learning solution," IEEE J. Select. Areas Commun., vol. 18, no. 2, pp. 209-221, Feb. 2000. [75] A. J. Viterbi, CDMA: Principle of Spread Spectrum Communication, Addison-Wesley, Bibliography 130 Reading, MA, 1995. [76] J. S. Vitter and P. Krishnan, "Optimal prefetching via data compression," J. ACM, vol. 43, no.5, pp. 771-793, Sept. 1996. [77] C. J. C. H. Watkins and P. Dayan, "Q-learning," Machine Learning, vol. 8, pp. 279-292, 1992. [78] V. W. S. Wong and V. C. M. Leung, "Location management for next-generation personal communications networks," IEEE Networks, vol. 14, no. 5, pp. 18-24, Oct. 2000. [79] V. W. S. Wong and V. C. M. Leung, "An adaptive distance-based location update algo rithm for next-generation PCS networks," IEEE J. Select. Areas Commun., vol. 19, no. 10, pp. 1924-1952, Oct. 2001. [80] I. H. Witten, R. M., Neal and J. G. Geary, "Arithmetic coding for data compression," Commun. ACM, vol. 30, no. 6, pp. 520-540, June 1987. [81] D. Wu, Y. T. Hou, and Y. Q. Zhang, "Scalable video coding and transport over broad band wireless networks," Proc. IEEE, vol. 89, no.l, pp. 6-20, Jan. 2001. [82] Y. Xiao, P. Chen, and Y. Wang, "Optimal admission control for multi-class of wireless adaptive multimedia services," IEICE Trans. Commun., vol. E84-B, no. 4, pp. 795-804, Apr. 2001. [83] F. Yu and V. C. M. Leung, "Mobility-based predictive call admission control and band width reservation in wireless cellular networks," in Proc. IEEE INFOCOM'01, vol. 1, Anchorage, Alaska, Apr. 2001, pp. 518-526. [84] F. Yu and V. C. M. Leung, "A framework of combining connection admission control and mobility management in wireless cellular networks," in Proc. IEEE ICC'01, vol. 7, Helsinki, Finland, June 2001, pp. 2286-2290. [85] F. Yu and V. C. M. Leung, "Connection admission control for PCS-to-IP interworking," in Proc. IEEE PIMRC'01, vol. 1, San Diego, CA, Sept. 2001, pp. B70-B74. [86] F. Yu and V. C. M. Leung, "Connection admission control for PCS-to-IP interworking," Bibliography 131 Kluwer Int'l J. Wireless Information Networks, vol. 9, no. 1, pp. 1-12, Jan. 2002. [87] F. Yu and V. C. M. Leung, "Mobility-based predictive call admission control and band width reservation in wireless cellular networks," Elsevier Computer Networks, vol. 38, no. 5, pp. 577-589, Apr. 2002. [88] F. Yu and V. W. S. Wong and V. C. M. Leung, "Performance enhancements of combining QoS provisioning and location management in wireless cellular networks," in Proc. IEEE Globecom'02, vol. 1, Nov. 2002, Taipei, Taiwan, pp. 956-960. [89] F. Yu and V. W. S. Wong and V.C.M. Leung, "Performance enhancements of combining QoS provisioning and location management in wireless cellular networks," accepted and to appear in IEEE Trans. Wireless Communications, Sept. 2003. [90] F. Yu, V.W.S. Wong and V.C.M. Leung, "Reinforcement Learning For Call Admission Control and Bandwidth Adaptation in Mobile Multimedia Networks," to be presented at ICICS-PCM'03, Singapore, Dec. 2003 [91] F. Yu, V.W.S. Wong and V.C.M. Leung, "Efficient QoS Provisioning for Adaptive Multi media in Mobile Communication Network by Reinforcement Learning," to be presented at ACM/SPIE Conference on Multimedia Computing and Networking (MMCN), Santa Clara, CA, Jan. 2004. [92] G. V. Zaruba, I. Chlamtac and S. K. Das, "A prioritised real-time wireless call degrada tion framework for optimal call mix selection," Mobile Networks and Applications, vol. 7, no. 2, pp. 143-151, 2002. [93] H. Zhang and D. Ferrari, "Rate-controlled service disciplines", Journal of High Speed Networks, vol. 3, no. 4, pp. 389-412, 1994. [94] W. Zhuang, B. Bensaou, and K. C. Chua, "Adaptive quality of service handoff priority scheme for mobile multimedia networks," IEEE Trans. Veh. Technol, vol. 49, no. 2, pp. 494-505, Mar. 2000. [95] J. Ziv and A. Lempel, "Compression of individual sequences via variable-rate coding," IEEE Trans. Inf. Theory, vol. 24, no. 5, pp. 530-536, Sept. 1978. 

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 28 13
United States 10 0
Saudi Arabia 9 0
India 7 0
Japan 7 0
Tajikistan 3 0
Republic of Lithuania 2 0
Canada 2 0
Germany 1 3
United Kingdom 1 0
City Views Downloads
Beijing 19 0
Unknown 15 11
Tokyo 7 0
Guangzhou 6 0
Jalalpur 6 0
Ashburn 4 0
Shenzhen 3 13
Mountain View 2 0
Riyadh 2 0
Vancouver 2 0
Redmond 1 0
Mumbai 1 0
San Mateo 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065555/manifest

Comment

Related Items