UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Modeling and performance evaluations of teletraffic in cellular networks Yavuz, Emre Altug 2007

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2007-268247.pdf [ 5.64MB ]
Metadata
JSON: 831-1.0100585.json
JSON-LD: 831-1.0100585-ld.json
RDF/XML (Pretty): 831-1.0100585-rdf.xml
RDF/JSON: 831-1.0100585-rdf.json
Turtle: 831-1.0100585-turtle.txt
N-Triples: 831-1.0100585-rdf-ntriples.txt
Original Record: 831-1.0100585-source.json
Full Text
831-1.0100585-fulltext.txt
Citation
831-1.0100585.ris

Full Text

MODELING AND PERFORMANCE EVALUATIONS OF TELETRAFFIC IN C E L L U L A R NETWORKS by Emre Altug Yavuz B. Sc., Middle East Technical University, 1995 M. Sc., Middle East Technical University, 1998 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA February 2007 © Emre Altug Yavuz, 2007 ABSTRACT The g r o w i n g interest for cel lular technology has mot iva ted operators to provide a wide variety o f services f rom convent ional c i rcui t -swi tched vo ice to packet-switched data and mu l t imed ia applicat ions. P r o v i d i n g these services anyt ime and anywhere is chal lenging due to not o n l y frequent status changes i n network connect ivi ty, but also l imi ted resources such as bandwidth . Different priori t ies are assigned to services to satisfy diverse Q o S requirements. C a l l admiss ion control schemes have been proposed to manage resources b y select ively l i m i t i n g the number o f admitted cal ls to ensure that Q o S measures such as ca l l b lock ing /d ropp ing probabi l i t ies stay w i t h i n acceptable l imi t s . E x a c t analysis methods based on mul t id imens iona l M a r k o v chain models are used to evaluate performance o f these schemes, yet they suffer f rom curse o f d imensional i ty that results i n very h igh computat ional cost. Large sets o f equations are avoided us ing approx imat ion methods based on one dimensional M a r k o v cha in models assuming that channel occupancy t imes are exponent ial ly distributed w i t h equal mean values and a l l cal ls require equal capacities. E x i s t i n g approximat ion methods lead to significant discrepancies w h e n average channel occupancy times differ. W e propose a nove l performance evaluat ion approx imat ion method, effective holding time, w i t h l o w computat ional complex i ty to relax this assumption. In mul t i - serv ice networks , vo ice is accompanied b y data and mu l t imed ia applications that require dist inct capacities. W h e n capacity requirements differ, exis t ing approximat ion methods based on one d imens iona l M a r k o v cha in models become inaccurate i f not obsolete. W e propose a computa t iona l ly efficient approximat ion method, state space decomposition, to relax this assumption. N u m e r i c a l results show that the proposed method provide h igh ly i i accurate results that match w e l l w i t h exact solutions. Traffic statistics are essential to understand the dis t r ibut ion o f id le periods o f voice channels to over lay packet-switched services o n c i rcu i t - swi tched technology and to feed simulations w i t h realist ic data. C a l l ho ld ing and channel occupancy t imes are k e y elements for comput ing performance metrics such as c a l l b lock ing /d ropp ing probabi l i t ies . W e present an empi r i ca l approach to determine the dis tr ibut ion o f c a l l h o l d i n g and channel occupancy times. W e show that lognormal dis tr ibut ion is the closest fitted candidate to approximate channel occupancy t imes and c a l l ho ld ing t imes for s tat ionary/mobile users a long w i t h the number o f handoffs commi t t ed b y a user. i n T A B L E OF CONTENTS Abstract • >> Table of Contents iv List of Tables vii List of Figures ix List of Symbols xii Acknowledgements xiv Dedication.......... xvi Co-Authorship Statement xvii C H A P T E R 1 Introduction : 1 1.1 Motivations and Objectives 6 1.2 Main Contributions 8 1.3 Organization of the Dissertation 9 1.4 Bibliography 11 C H A P T E R 2 Computationally Efficient Method To Evaluate The Performance Of Guard-Channel-Based Call Admission Control In Cellular Networks 15 2.1 Introduction 15 2.2 Existing Methods to Analyze Performance of C A C Schemes 18 2.2.1 New Call Bounding Scheme 18 2.2.2 Cutoff Priority Scheme 21 2.2.3 Fractional Guard Channel Scheme 22 2.3 The Proposed Performance Evaluation Method 24 iv 2.4 Numerical Results 27 2.4.1 Performance Evaluation of Existing and Proposed Methods 27 2.4.2 Accuracy and Runtime Computational Cost.... 30 2.5 Summary 31 2.6 Bibliography 40 C H A P T E R 3 Computationally Efficient Performance Evaluation Methods For Call Admission Control Schemes In Multi-Service Cellular Networks 43 3.1 Introduction 43 3.2 Performance Evaluation of Symmetric Call Admission Control Schemes 46 3.3 Performance Evaluation of Asymmetric Call Admission Control Schemes 49 3.4 Numerical results 54 3.5 Summary 58 3.6 Bibliography 71 C H A P T E R 4 Probability Distribution Of Channel Occupancy Times And Number Of User Handoff In Cellular Networks. 74 4.1 Introduction 74 4.2 Data Acquisition and System-Related Anomalies .78 4.3 Statistical Methods 80 4.3.1 Candidate Probability Distributions 80 4.3.2 Parameter Estimation 81 4.3.3 Goodness-of-fit Tests 82 4.4 Numerical Results 86 4.4.1 Statistical Results for Channel Occupancy Times 86 4.4.2 The Effects of Traffic Remodeling on Performance Evaluation 88 4.4.3 Channel Occupancy and Call Holding Times for Stationary/Mobile Users...89 4.4.4 Statistical Results for Number of Handoffs Committed by Users . 90 4.5 Summary ....90 v 4.6 B i b l i o g r a p h y 101 C H A P T E R 5 C o n c l u s i o n A n d R e c o m m e n d a t i o n s F o r F u r t h e r W o r k 103 5.1 C o n c l u s i o n 103 5.2 F u t u r e W o r k . . . . 106 5.3 B i b l i o g r a p h y 108 A P P E N D I C E S 109 A p p e n d i x A 109 vi LIST OF TABLES Table 2.1 Sys tem parameter values used for each scenario 38 Table 2.2 Errors i n handoff c a l l dropping probabi l i ty approximat ions relative to direct method 38 Table 2.3 Errors i n new ca l l b l o c k i n g probabi l i ty approximat ions relative to direct method 38 Table 2.4 Percentage gains i n accuracy o f handoff c a l l d ropp ing probabi l i t ies obtained b y the proposed approximat ion method relative to those obtained b y the normalized and the traditional methods 38 Table 2.5 C o m p a r i s o n o f runtime computat ional costs between the proposed method and the direct and iterative numer ica l methods 39 Table 3.1 C o m p a r i s o n o f runtime computat ional costs between the proposed approx imat ion method and the Borst-Mitra, direct and iterative methods 70 Table 4.1 A n example o f a " N e i g h b o r L i s t T u n i n g Da ta A r r a y " message taken f rom a ce l lu lar c a l l data set 97 Table 4.2 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis t r ibut ion fitting (new2same) 97 Table 4.3 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis tr ibut ion fitting (new2ho) 98 Table 4.4 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis tr ibut ion fitting (new2sameorho) 98 Table 4.5 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis tr ibut ion fitting (ho2same) 98 Table 4.6 Goodness o f fit test results for Channe l Occupancy T i m e dis tr ibut ion fitting (ho2ho) 99 Table 4.7 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis tr ibut ion fitting (ho2sameorho) 99 Table 4.8 Goodness o f fit test results for C a l l H o l d i n g T i m e dis tr ibut ion fitting (total) 99 v n Table 4.9 Goodness o f fit test results for C a l l H o l d i n g T i m e dis t r ibut ion fitt ing (totaljnobility) 100 Table 4.10 Goodness o f fit test results for N u m b e r o f U s e r Handoffs dis tr ibut ion fitting (userJiandoffs) 100 v i i i LIST OF FIGURES Figure 2.1 State transi t ion d iagram for the new c a l l bound ing scheme 33 Figure 2.2 State transi t ion d iagram for the cutoff p r ior i ty scheme 33 Figure 2.3 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r ior i ty scheme (Case I) 34 Figure 2.4 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r io r i ty scheme (Case I) 34 Figure 2.5 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r ior i ty scheme (Case II) 35 Figure 2.6 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r ior i ty scheme (Case II) 35 Figure 2.7 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r ior i ty scheme (Case III) 36 Figure 2.8 H a n d o f f c a l l d ropp ing probabi l i ty i n the cutoff p r io r i ty scheme (Case III) 36 Figure 2.9 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r ior i ty scheme (Case I V ) 37 Figure 2.10 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r ior i ty scheme (Case I V ) 37 Figure 3.1 Trans i t ion d iagram for asymmetric c a l l admiss ion control schemes w i t h supernodes for pr io r i t i zed calls 60 Figure 3.2 Trans i t ion d iagram for asymmetric c a l l admiss ion control schemes w i t h supernodes for non-pr ior i t ized cal ls .60 Figure 3.3 One d imens iona l M a r k o v chain m o d e l obtained for the pr ior i t i zed ca l l s ' supernodes 61 Figure . 3.4 One d imens iona l M a r k o v chain mode l obtained for the non-pr ior i t ized ca l l s ' supernodes 61 Figure . 3.5 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 1, and m = 24 62 Figure 3.6 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 1, bnp = 1, and m = 24 62 Figure 3.7 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 2, bnp = 1, and m = 24 63 Figure 3.8 N o n - p r i o r i t i z e d ca l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 2, bnp = 1, and m = 24 63 Figure 3.9 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 4, bnp = 1, and m - 24 64 ix Figure 3.10 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 4, bnp = 1, and m = 24 64 Figure 3.11 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 1, and = 28 65 Figure 3.12 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 1, bnp = 1, and m = 28 65 Figure 3.13 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 2, and m = 28 66 Figure 3.14 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 1, bnp = 2, and m = 28 66 Figure 3.15 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 4, and m = 28 67 Figure 3.16 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 1, bnp = 4, and m = 28 67 Figure 3.17 P r io r i t i z ed ca l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = bnp = 1, pnp = 20, pp = 2.5 to 50, Xp = 0.05 to 1 68 Figure 3.18 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = bnp =l,pnp = 20, pp = 2.5 to 50, Xp = 0.05 to 1 68 Figure 3.19 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = bnp = 1, pnp = 20 , pp = 2.5 to 50, V/ip = 5 to 100 69 Figure 3.20 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = bnp =\,p„p = 20,p p = 2.5 to 50, \lpp = 5 to 100 69 Figure 4.1 Di s t r ibu t ion o f channel occupancy times (new2same) and the fitted lognormal and exponential distributions 92 Figure 4.2 Di s t r i bu t ion o f channel occupancy times (new2ho) and the fitted lognormal and exponential distr ibutions 92 Figure 4.3 Di s t r i bu t ion o f channel occupancy times (new2sameorho) and the fitted lognormal and exponential distributions 93 Figure 4.4 Di s t r i bu t ion o f channel occupancy times (ho2same) and the fitted lognormal and exponential distr ibutions 93 Figure 4.5 Di s t r i bu t ion o f channel occupancy t imes (ho2ho) and the fitted lognormal and x exponential distr ibutions 94 Figure 4.6 Di s t r i bu t ion o f channel occupancy times (ho2sameorho) and the fitted lognormal and exponential distributions 94 Figure 4.7 Di s t r i bu t ion o f c a l l ho ld ing times (total) and the fitted lognormal and exponential distr ibutions 95 Figure 4.8 C a l l b l o c k i n g probabi l i t ies for exponentially and lognormally distributed ca l l h o l d i n g t imes 95 Figure 4.9 Di s t r i bu t ion o f c a l l ho ld ing times (total mobility) and the fitted lognormal dis t r ibut ion 96 Figure 4.10 Dis t r ibu t ion o f number o f user handoffs (user Jiandoffs) and the fitted lognormal dis t r ibut ion 96 xi LIST OF SYMBOLS C Number of channels in a cell. c Number of occupied channels in a cell. K Threshold for new call bounding scheme. m Threshold for the cutoff priority scheme. Xn Arrival rate for new calls. Xh Arrival rate for handoff calls. Xnp Arrival rate for non-prioritized calls. Xp Arrival rate for prioritized calls. l/ju„ Average channel holding time for new calls. l/uh Average channel holding time for handoff calls. \lpnp Average channel holding time for non-prioritized calls. \lup Average channel holding time for prioritized calls. Mueff Average effective channel holding time. b„p Capacity requirement in bandwidth units for non-prioritized calls. bp Capacity requirement in bandwidth units for prioritized calls. p„ Traffic intensity for new calls (i.e., X„ I /u„). ph Traffic intensity for handoff calls (i.e., Xh i uh). p„p Traffic intensity for non-prioritized calls (i.e., Xnp I unp). pp Traffic intensity for prioritized calls (i.e., Xp I pp). nnp Number of non-prioritized calls in the system. np Number of prioritized calls in the system. pnb Blocking probability for new calls. pM Dropping probability for handoff calls. pa Blocking probability for new calls from the normalized approximation. p" Dropping probability for handoff calls from the normalized approximation. x i i 'nb Blocking probability for new calls from the traditional approximation. p' Dropping probability for handoff calls from the traditional approximation. peff Blocking probability for new calls from the proposed approximation. peff Dropping probability for handoff calls from the proposed approximation. Pi User defined admission probability for non-prioritized (new) calls in a call admission control scheme. q(c) Equilibrium channel occupancy probability when c channels are occupied. q(c) Approximated equilibrium channel occupancy probability when c channels are occupied. Bnp Blocking probability for non-prioritized calls. Bp Blocking probability for prioritized calls. kj Admission probability for prioritized calls. hr Admission probability for non-prioritized calls. qp(j) Equilibrium channel occupancy probability when j prioritized calls exist in the system. q„p(r) Equilibrium channel occupancy probability when r non-prioritized calls exist in the system. q(n ,n ) Estimated equilibrium channel occupancy probability for nnp non-prioritized and np prioritized calls. xin ACKNOWLEDGEMENTS Y e s ! A fierce and savage w i n d tore at us. W e were on top o f Annapurna ! 8,075 meters ... O u r hearts over f lowed w i t h an unspeakable happiness. " I f o n l y the others cou ld k n o w . . . " I f o n l y everyone cou ld k n o w ! M a u r i c e H e r z o g o n summi t ing Annapurna To me, w r i t i n g a P h . D . thesis is l ike c l i m b i n g a h i g h altitude mounta in for the first t ime. Often y o u do not have any spectators and acknowledgement is not acquired unless y o u make it to the top. T h e graduate leve l courses guide y o u w h i l e y o u are o n your w a y to the base camp and every paper y o u manage to pub l i sh afterwards means reaching higher camps, taking y o u closer to the summit for the final push yet. Ne i the r everybody c l imbs the same mountain nor under the same condit ions. That is w h y c l i m b i n g w i t h the right guide is important not o n l y to p i c k the right route on the w a y to the top but also to k n o w where your h igh altitude camps sha l l be set up. Sometimes the condi t ions and the d i f f icul ty o f the route force y o u to back o f f o n l y to return later k n o w i n g that what does not k i l l makes stronger. Yet , from an outsider 's point o f v i e w what matters most is whether y o u c l i m b it or not regardless o f what happened o n the way. Th i s is a self-guided journey where a passionate c l i m b e r never gives up for the sake o f learning about one's se l f and l imi t s . However , choos ing a competent guide is not on ly v i ta l to avo id storms, c l i m b i n g to dead ends and be ing left to destiny w h e n i n trouble but also to lift the spirits up w h e n needed. I a m thankful to m y perseverance and d i l igence for not on ly m a k i n g it to the top through storms and tu rmoi l but also getting m y s e l f back on the right track despite surrounded b y a th ick fog at most t imes. W i t h a l i t t le twist on what H i l l a r y said when he c l i m b e d M o u n t Everest , "It wasn ' t the title I was after, it was to conquer mysel f . " xiv I dedicate this w o r k to m y parents for their uncondi t iona l love and support. I am thankful for their un l imi t ed patience and confidence i n me dur ing this arduous c l i m b . I w o u l d not be able to complete m y graduate studies without their dedicated sacrif ice, understanding, and encouragement. I a m grateful to m y friends; A l i y e , G o r k e m , K a a n , R i ibab and Verda, who helped me i n m a n y ways that kept me c l i m b i n g i n good times and bad. Las t but not the least I w o u l d l i ke to express m y gratitude to m y supervisor Dr . V i c t o r C . M . L e u n g for his guidance, comments and f inancia l support. To conclude, I w o u l d once more l ike to quote M a u r i c e H e r z o g as he says, "There are other Annapurnas i n men's l i f e . " x v To my mom, Semra, and my dad, Huseyin, for their unconditional love and absolute support ... x v i Go-Authorship Statement I am the first author and principle contributor of all manuscript chapters. A l l manuscript chapters are co-authored with V . C . M . Leung, who co-supervised the thesis research. xvii CHAPTER 1 I N T R O D U C T I O N C e l l u l a r network technology is one o f the fastest g r o w i n g ways o f mob i l e communica t ions today. The bounds o f an exis t ing communica t i on network infrastructure have been extended b y ce l lu lar technology v i a connect ing m o b i l e units to pub l ic network operated b y the l oca l exchange or l ong distance carriers to make specia l features and functions specific to both cel lu lar and pub l ic networks avai lable to a l l users. G l o b a l standards have been developed to p rov ide vo ice and data services anyt ime and anywhere regardless o f user m o b i l i t y w h i l e sat isfying their diverse Qua l i t y o f Serv ice ( Q o S ) requirements. R a d i o resources such as bandwid th , transmit power, channel codes and base stations are generally l imi ted i n ce l lu lar networks due to phys ica l and regulatory restrictions as w e l l as the interference-limited nature o f the cel lu lar structure. Eff ic ient management o f these resources is not o n l y c ruc ia l to the eff ic iency o f system operation and congest ion prevention, but it is also very important to satisfy the Q o S requirements o f user applicat ions. Services w i t h specific data rate, bandwid th , power and latency requirements need specific amount o f system resources to be al located at the t ime o f ca l l admiss ion to ensure that these requirements are attained and sustained dur ing communica t ion . Signif icant challenges confronted b y ce l lu la r networks due to frequent status changes i n connect iv i ty and h igh ly variable no i sy communica t i on channels can be overcome b y Q o S p rov i s ion ing w h i c h has become one o f the most demanding problems. Resource management requires more sophisticated techniques i n a mob i l e environment than those used i n f ixed systems since a b l i n d spot m a y be reached where Q o S is severely l im i t ed due to a weak signal or a loss o f communica t i on m a y occur during a handoff w h e n the new point o f attachment m a y not be able to p rov ide resources s imi la r to the o ld one. Nevertheless , the p rob lem o f mainta in ing service cont inui ty for users' applications during handoffs has been intensif ied w i t h the increasing number o f mic roce l l s and p icocel l s i n cel lular networks. C a l l admiss ion control ( C A C ) schemes have been developed to manage scarce radio resources to m a x i m i z e network u t i l iza t ion b y se lect ively l i m i t i n g the number o f admitted cal ls . Probabi l i t ies o f ca l l b l o c k i n g and dropping are two important Q o S measures 1 used when evaluat ing performance o f ca l l admiss ion control schemes. C a l l b l o c k i n g occurs when a ce l lu lar ne twork is unable to assign network resources to enable a c a l l init iated i n a ce l l , whereas ca l l d ropp ing occurs when a ce l lu lar network is unable to assign network resources to enable a c a l l handed o f f f rom a ne ighbor ing ce l l . Sufficient network resources shall be p rov ided to ensure that ca l l b l o c k i n g and d ropp ing probabi l i t ies stay w i t h i n acceptable l imi t s for user applicat ions. A higher pr ior i ty is n o r m a l l y assigned to handoff calls over the new ones to m i n i m i z e c a l l dropping probabi l i ty since dropping an on-going ca l l is generally more object ionable to a user than b l o c k i n g a new c a l l request. H o w e v e r reducing b l o c k i n g probabi l i t ies o f cal ls w i t h higher priori t ies increases the p robab i l i ty o f b l o c k i n g for calls w i t h re la t ive ly l ower priori t ies result ing i n a trade o f f between both types o f cal ls . Therefore the goal is to sustain a balance between calls o f different pr ior i t ies w h i l e satisfying the respective Q o S requirements. C a l l admiss ion control has been intensively studied i n the past [1][2] and many priori ty-based C A C schemes have been proposed [3]-[18]. One d imens iona l M a r k o v chain models are c o m m o n l y used to evaluate these schemes (e.g., [6] [7] [15]) assuming that ca l l requests that originate f rom different types o f users are independently Po i s son distributed, channel occupancy t imes for each ca l l are exponent ia l ly distr ibuted w i t h equal mean values and each c a l l requires an equal channel capacity. Yet these assumptions m a y not be appropriate since cal ls w i t h different priori t ies , such as new and handoff, m a y have different average channel occupancy t imes i f not different distr ibutions as shown i n [19], [20] and references therein. E x i s t i n g performance evaluat ion approximat ion methods based on one d imens iona l M a r k o v cha in m o d e l i n g lead to significant discrepancies w h e n average channel occupancy t imes for different c a l l types are not equal [21]. Gersht and L e e proposed an iterative a lgor i thm i n [22] b y m o d i f y i n g the approximat ion suggested b y Roberts i n [23] to improve its accuracy w h e n service rates differ. H o w e v e r the a lgor i thm is o n l y accurate when appropriate in i t i a l values are chosen and therefore m a y not be competent [21]. L i and Chao obtained a product fo rm solu t ion i n [24] b y mode l ing a m u l t i c e l l ne twork as a network o f queues e m p l o y i n g a h y b r i d guard channel/queuing p r io r i ty scheme w i t h transfer o f unsuccessful requests to ne ighbor ing cel ls . The i r solut ion is restrictive to the protocol considered and therefore m a y not be appropriate to be used for the performance evaluation o f ca l l admiss ion cont ro l schemes i n general. Thus , exact analysis methods based on 2 > mul t id imens iona l M a r k o v cha in models appeared to be the o n l y means to obtain accurate solutions for evaluat ing c a l l admiss ion control schemes. Rappaport obtained c a l l b l o c k i n g probabil i t ies for cal ls w i t h various priori t ies b y us ing a mul t id imens iona l m o d e l o f a cel lular network i n [25]. Rappaport and M o n t e developed an analyt ical m o d e l for traffic performance analysis us ing a mul t id imens iona l b i r th death process i n [26] b y cons ider ing the effects o f various pla t form types dis t inguished b y different m o b i l i t y characteristics o n performance. E v e n though mul t id imens iona l M a r k o v chain models are capable o f p r o v i d i n g the exact solutions, these methods suffer f rom the curse o f dimensional i ty , w h i c h results i n very h igh computat ional cost for large systems. A n easy to implement analyt ical approximat ion method w i t h h i g h l y accurate solutions and l o w computat ional cost is needed to compute new/handoff c a l l b lock ing /d ropp ing probabil i t ies o f cal ls for several w i d e l y k n o w n ca l l admiss ion control schemes under more general assumptions. The fast evo lu t ion o f ce l lu lar networks has been accompanied not o n l y b y basic voice services but also b y development , growth and use o f a w i d e var ie ty o f network applications that range from text-based ut i l i t ies such as S M S messaging, f i le transfer, remote log in and electronic m a i l i n g to m u l t i m e d i a util i t ies such as v ideo conferencing and streaming, web surfing and electronic commerce . T h i s has mot ivated cel lu lar ne twork operators to move away from just p r o v i d i n g convent ional vo ice services to embrac ing a w i d e variety o f traffic from data to m u l t i m e d i a applicat ions due to increasing demand c o m i n g f rom users that these services shal l also be avai lable on the move . Different techniques have been proposed to allocate l imi t ed and v a r y i n g network resources efficiently to a var ie ty o f services w i t h different characteristics and Q o S requirements at different network layers. [27]. M o d u l a t i o n and power control schemes are designed to be Q o S aware at the phys i ca l layer [28] as m e d i u m access control is adjusted to support reservations and Q o S guarantees at the data l ink layer. A t the ne twork layer, techniques o f m o b i l i t y management and seamless connectivity, i nc lud ing the extension o f rout ing mechanisms to be Q o S aware and able to handle mobi l i ty , are appl ied [29]. M u l t i m e d i a cod ing systems such as H . 2 6 3 L v ideo codecs are introduced for the appl icat ion layer [30]. C a l l admiss ion control schemes are analyzed us ing M a r k o v cha in models based on c i rcui t -swi tched network architectures, however convent ional c i rcu i t - swi tched services such as vo ice are gradual ly be ing replaced b y packet-switched data and mu l t imed ia applications. 3 Conven t iona l c a l l admiss ion control schemes w i l l continue to be useful w h e n applied w i t h suitable schedul ing techniques to guarantee Q o S at the packet l eve l since most data and mul t imed ia applicat ions are inherently connect ion oriented and packet-swi tched connections can be p rov i s ioned to their effective bandwidths [31]-[33]. Effect ive bandwid th represents the phys i ca l l y dedicated bandwid th o f a packet-switched connect ion to match its overa l l traffic demand. M a r k o v cha in m o d e l i n g w i l l s t i l l be useful since a ce l lu lar network can have a s imi la r fo rm to a c i rcui t -swi tched network operating w i t h f ixed rout ing [32]. H o w e v e r calcula t ing channel occupancy dis t r ibut ion o f such a mul t i - serv ice ce l lu lar network using an exact so lu t ion method based on mul t id imens iona l M a r k o v cha in mode l ing involves numer ica l ly s o l v i n g the balance equations, w h i c h is demanding for a l l but smallest channel capacities i n the absence o f a product form solution. E x i s t i n g approximat ion methods based on one d imens iona l M a r k o v cha in mode l ing , on the other hand, become obsolete when packet-switched connect ions such as data and mu l t imed ia applicat ions have distinct capacity requirements. In [34], Bors t and M i t r a developed computat ional algori thms for a mul t i -service ce l lu lar ne twork b y coup l ing the computat ion o f jo in t channel occupancy probabil i t ies w i t h that o f used capaci ty assuming that channels are occupied independently. The authors so lved the balance equations through numer ica l i teration but the results can on ly be comparat ive w h e n the number o f exis t ing ca l l a r r ival types are h i g h due to authors' channel occupancy independence assumption. A nove l performance evaluation approximat ion method w i t h h i g h l y accurate solutions and l o w computat ional cost is needed to compute ca l l b l o c k i n g probabi l i t ies o f circui t and packet-switched connect ion type o f calls that have dist inct capaci ty requirements for several w i d e l y k n o w n c a l l admiss ion control schemes under more general assumptions. The advantage o f hav ing packet-switched connect ion type o f services over la id on c i rcui t -swi tched technology over the same air interface is the u t i l i za t ion o f excess network capacity avai lable i n each c e l l . W h e n large numbers o f sources w i t h bursty characteristics are mul t ip lexed , it is u n l i k e l y that a l l o f them transmit at their peak rates at the same time. The network can then allocate each user less resource than the corresponding requested peak capacity w h i l e meet ing the statistical performance requirements. D a t a packets can be transmitted over radio interface us ing statistical m u l t i p l e x i n g to p rov ide a Q o S level comparable to that o f c i rcu i t - swi tched services. Statistical m u l t i p l e x i n g ga in arises from the 4 talk spurt to si lence ratio found i n speech w h i c h makes it possible to mul t ip lex more than one service on to the same radio channel . H o w e v e r accurate vo ice traffic statistics are needed to understand the length and frequency distributions o f id le periods o f cel lular channels assigned to vo ice i n order to exploi t the statistical m u l t i p l e x i n g ga in i n ce l lu lar networks. Traffic statistics are important for network management and op t imiza t ion along w i t h traffic mode l ing , b i l l i n g and a l locat ion o f safety buffers. These statistics are also used to evaluate performance dur ing network s imula t ion or analysis us ing mathematical models . T w o o f these traffic statistics, c a l l ho ld ing and channel occupancy t imes, are k e y elements to compute performance metr ics such as ca l l b l o c k i n g and dropping probabi l i t ies . In cel lular network analysis c a l l h o l d i n g t imes are generally assumed to be exponent ia l ly distributed due to studies on wi re l ine traffic statistics. In [3], H o n g and Rappaport proposed a traffic mode l for ce l lu lar m o b i l e radio telephone systems and approximated channel occupancy t ime distr ibution b y exponent ia l dis t r ibut ion when ca l l h o l d i n g t imes are assumed to be exponent ia l ly distributed. Ramjee et al. [6], F a n g and Z h a n g [7], Naghsh ineh and Schwartz [15], Gersht and L e e [22], Bors t and M i t r a [34] and Y a v u z and L e u n g [21] studied the performance o f var ious c a l l admiss ion control schemes us ing one d imens iona l M a r k o v chain models assuming that channel occupancy times are exponent ia l ly distr ibuted based on H o n g and Rappaport ' s study due to its tractability. In [25], Rappaport developed mul t id imens iona l models under the same assumption and w i t h M o n t e the author obtained ca l l b l o c k i n g probabil i t ies us ing this m o d e l [26]. H o w e v e r s imula t ion studies and f ie ld data have shown that these assumptions are not perpetually va l i d . In [35], G u e r i n used a s imula t ion mode l to show that channel occupancy t ime dis tr ibut ion displays a rather poor agreement w i t h the exponential f i t t ing for m o b i l e users w i t h l o w change rate o f movement direct ion. Jedrzyck i and L e u n g showed i n [36] that exponential dis t r ibut ion assumption for channel occupancy times is not correct and a lognormal mode l approximat ion fits m u c h better us ing real cel lular data. Fang et al. demonstrated i n [37] and [38] that channel occupancy t imes i n a cel lular network depend not o n l y o n c a l l ho ld ing times but also on users ' m o b i l i t y w h i c h can be characterized b y c e l l residence t ime distr ibution. In [20], the authors showed that channel occupancy t ime is exponent ia l ly distributed o n l y i f c e l l residence t ime is exponent ia l ly distributed. Yet , it is also observed i n the same study that channel occupancy t ime distr ibution have a good approximat ion b y exponential dis t r ibut ion i n general w h e n the m o b i l i t y is low. 5 Barce lo and Jordan analyzed a ce l lu lar network based o n a fu l ly empi r i ca l approach i n [39] and observed that channel occupancy is less spread out than i f exponent ial dis t r ibut ion was assumed. M a r k o v cha in mode ls are developed to evaluate performance analy t ica l ly i n cel lular networks. C a l l s a r r iv ing to a part icular c e l l are grouped into Q o S classes or ca l l types, such as new and handoff, based on their first appearance i n the corresponding ce l l . Channe l occupancy t imes for each group are measured from c a l l starting t ime t i l l the occupied channel i n the respective ce l l is discarded due to ca l l terminat ion or handoff. However , ca l l ho ld ing t imes are measured f rom ca l l starting t ime t i l l c a l l terminat ion regardless o f occupy ing a channel i n the same c e l l or not. The characteristics o f var ious types o f channel occupancy t imes are needed to be analyzed to provide suff icient ly representative channel occupancy t ime statistics not o n l y w h e n developing analyt ica l models but also for feeding simulat ions w i t h realist ic traffic statistics to obtain network performance metrics. The rest o f this chapter is organized as fo l lows : Sec t ion 1.1 discusses the motivat ions and objectives o f our w o r k . Sec t ion 1.2 presents an ove rv iew o f our contributions. Sect ion 1.3 describes the organizat ion o f this dissertation. 1.1 Motivations and Objectives M a n y guard channel based ca l l admiss ion control schemes have been proposed to provide the desired qua l i ty o f service to new and handoff cal ls i n ce l lu lar networks. One d imens iona l M a r k o v cha in m o d e l i n g is generally used under specif ic assumptions to compute b l o c k i n g and d ropp ing probabi l i t ies o f these cal ls approximate ly to avo id so lv ing large sets o f f low equations that makes exact analysis o f these schemes us ing mul t id imens iona l M a r k o v chain models infeasible. The " t radi t ional" approximat ion method provides accurate results on ly w h e n channel occupancy t imes for new and handoff cal ls have equal mean values w h i l e the " n o r m a l i z e d " approach relaxes this assumption o n l y for the new c a l l bounding c a l l admiss ion control scheme. Yet , these assumptions m a y not be appropriate since these two types o f cal ls m a y have different average channel occupancy t imes i f not different distributions [19] [20]. T h i s motivates us to develop an accurate yet easy to implement method to compute new and handoff c a l l b l o c k i n g and d ropp ing probabi l i t ies for several w i d e l y k n o w n c a l l admiss ion control schemes when channel occupancy t imes for new and 6 handoff cal ls have separate mean values. A w i d e var ie ty o f ne twork applications that range f rom text-based to mul t imed ia util i t ies are p rov ided b y ce l lu lar networks a long w i t h basic vo i ce services. These util i t ies are grouped under var ious qua l i ty o f service classes and a higher p r io r i ty is no rma l ly assigned to calls w i t h higher bandwid th and lower latency requirements based o n the application's importance for ce l lu lar network operator. C a l l admiss ion control schemes are also used to opt imize c a l l b l o c k i n g and dropping probabil i t ies o f these applicat ions for qual i ty o f service p rov i s ion ing i n ce l lu la r networks. Performances o f these c a l l admiss ion control schemes are evaluated us ing either one d imens iona l or mul t id imens iona l M a r k o v cha in models w i t h the former preferred over the latter to avo id so lv ing large sets o f f l ow equations. A computat ional ly efficient so lu t ion is also important for qual i ty o f service p rov i s ion ing when dynamic c a l l admiss ion control schemes are used since efficient adaptive reservation depends on rel iable and up to date system status feedback s imul taneously p rov ided to the ca l l admiss ion control mechan i sm. However , re lax ing the assumptions to have separate mean values for channel occupancy times o f different classes o f cal ls is not sufficient to evaluate mult i -service ce l lu la r networks us ing approximat ion methods based on one d imensional M a r k o v cha in m ode l i ng . W h e n assumptions are relaxed further to have cal ls w i t h separate capacity requirements, p rev ious ly developed one d imens iona l M a r k o v cha in models become obsolete due to the mul t id imens iona l i ty introduced b y cal ls w i t h unequal bandwid th requests. Bors t and M i t r a proposed an approximat ion method [34] w i t h a c losed form and therefore a fast solut ion, but it o n l y approximates sufficiently accurately w h e n the number o f exis t ing ca l l arr ival types are h igh . The need for an accurate and computa t ional ly efficient performance evaluat ion approximat ion method for c a l l admiss ion cont ro l schemes motivates us to develop an easy to implement method to compute c a l l b l o c k i n g and dropping probabil i t ies o f different classes o f cal ls i n mult i -service ce l lu lar networks. Packet -swi tched services are over la id on c i rcu i t - swi tched technology over the same air interface to use the access capaci ty i n ce l lu lar networks. Statist ical m u l t i p l e x i n g is used to transmit data packets over radio interface to provide a qual i ty o f service leve l comparable to that o f c i rcu i t - swi tched services. Accura te vo ice traffic statistics are needed to understand the dis tr ibut ion o f id le periods o f vo ice channels to mul t ip lex more than one service on to the same radio channel . In c lass ica l vo ice traffic mode l i ng c a l l h o l d i n g t imes are approximated 7 by exponential d is t r ibut ion and this assumption is w i d e l y used due to its tractabil i ty to obtain analyt ical results for evaluat ing ce l lu lar networks [6] [7] [15] [21] [22] [34]. H o w e v e r it has been shown that a lognormal dis t r ibut ion approximat ion fits m u c h closer [36] [39]. In a cel lular ne twork w h e n a c a l l admiss ion control scheme is mode led for each ce l l , a r r iv ing calls to a part icular c e l l are grouped into qual i ty o f service classes or c a l l types, such as new and handoff, based o n their first appearance i n the corresponding c e l l . Channe l occupancy time dis tr ibut ion for each group includes respective channel occupancy t imes counted o n l y unt i l the corresponding cal ls discard the occupied channels i n the c e l l due to ca l l termination or handoff. C a l l h o l d i n g t ime dis t r ibut ion, on the other hand, includes the amount o f times that the channels are occup ied b y a ca l l un t i l it terminates either i n its or ig inat ing ce l l or another. The above d i scuss ion mot ives us to provide sufficiently representative channel occupancy t ime statistics to develop analyt ical models since ca l l h o l d i n g t ime statistics are not sufficient alone. Th i s is also ve ry useful for feeding simulat ions w i t h realist ic traffic statistics to obtain network performance metr ics . 1.2 Main Contributions The m a i n contr ibutions o f this dissertation are as fo l lows : • Develop a computationally efficient approximation method to evaluate performance of call admission control schemes in single service cellular networks: W e propose an easy to implement approximat ion method to evaluate ca l l admiss ion cont ro l schemes when average channel occupancy t imes for new and handoff cal ls are not necessari ly equal. O u r proposed approximat ion method yields more accurate results compared w i t h the p rev ious ly proposed " t radi t ional" and " n o r m a l i z e d " methods w h i l e keeping the computat ional c o m p l e x i t y low. • Develop computationally efficient approximation methods to evaluate performance of call admission control schemes in multi-service cellular networks: W e class i fy c a l l admiss ion control schemes into two categories cal led symmetr ic and asymmetr ic . W e present the product fo rm solu t ion formula to evaluate symmetr ic c a l l admiss ion control schemes and propose a nove l performance evaluat ion approximat ion method to evaluate asymmetr ic c a l l admiss ion control 8 schemes w h e n average channel occupancy times for different classes o f cal ls are not necessari ly equal and a l l a r r iv ing cal ls m a y have dist inct capaci ty requirements. The proposed method performs better i n accuracy compared to the p rev ious ly proposed method b y Bors t and M i t r a w h i l e keeping the computat ional c o m p l e x i t y low. • Statistical modeling of channel occupancy times for voice service in cellular networks: W e present an empi r i ca l approach to determine the probabi l i ty distr ibution functions that fit var ious types o f channel occupancy t imes i n ce l lu lar networks. W e show that these channel occupancy t imes can be approximated b y lognormal dis tr ibut ion. • Statistical modeling of call holding times for stationary and mobile users along with the number of handoffs committed by a mobile user in cellular networks: W e show that the closest fit candidate to approximate stationary and mob i l e users' ca l l ho ld ing t imes is l ognormal dis t r ibut ion a long w i t h the dis t r ibut ion o f the number o f handoffs commi t t ed b y a mob i l e user. 1.3 Organization of the Dissertation T h i s dissertation is organized as fo l lows. In chapter 2, w e propose a computat ional ly efficient approximat ion method to evaluate performance o f c a l l admiss ion control schemes i n single service ce l lu la r networks. W e reevaluate the analyt ica l methods for comput ing new/handoff c a l l b lock ing /d ropp ing probabil i t ies for w i d e l y k n o w n c a l l admiss ion control schemes and show that the proposed approach gives more accurate results under relaxed assumptions w h e n compared w i t h the exis t ing methods. In chapter 3, w e propose computat ional ly efficient approximat ion methods to evaluate performance o f c a l l admiss ion control schemes i n mul t i - serv ice cel lu lar networks assuming that average values for channel occupancy t imes o f different classes o f cal ls are not equal and a l l a r r iv ing cal ls have different capacity requirements. W e present the numer ica l results that show the proposed methods provide results that match w e l l w i t h the exact solutions w h i l e keeping the computat ional complex i ty low. In chapter 4, w e determine the probabi l i ty d is t r ibut ion functions that fit various types o f channel occupancy times i n ce l lu lar networks and show that these channel occupancy t imes can be approximated by lognormal dis t r ibut ion. W e also show that the closest fit candidate to approximate stationary and m o b i l e users ' c a l l ho ld ing times is 9 lognormal dis t r ibut ion a long w i t h the dis tr ibut ion o f the number o f handoffs commit ted by a mobi le user. Chapter 5 concludes the thesis w i t h a summary o f the presented work , and describes the future w o r k s . 10 1.4 Bibliography [I] D . E . Ever i t t , "Traff ic engineering o f the radio interface for ce l lu la r mob i l e networks," Proc. IEEE, v o l . 82, no. 9, pp.1371-1382, 1994. [2] H . C h e n , L . H u a n g , S. K u m a r , and C . C . J . K u o , Radio Resource Management for Multimedia QoS Support in Wireless Networks. Bos ton : K l u w e r A c a d e m i c Publishers , 2004, chapter 2. [3] D . H o n g and S. S. Rappaport , "Traff ic mode l and performance analysis for cel lular mob i l e radiotelephone systems w i t h pr ior i t i zed and non-pr ior i t ized handoff procedures," IEEE Transactions on Vehicular Technology, v o l . 35, pp. 77-92, A u g . 1986. [4] B . L i , C . L i n , and S. T. Chanson , " A n a l y s i s o f a h y b r i d cu tof f p r ior i ty scheme for mul t ip le classes o f traffic i n mul t imed ia wireless ne tworks ," Wireless Networks, v o l . 4, no. 4, pp. 279-290, J u l y 1998. [5] Y . B . L i n , S. M o h a n , and A . Noerpe l , " Q u e u i n g p r io r i ty channel assignment strategies for handoff and in i t i a l access for a P C S network," IEEE Transactions on Vehicular Technology, v o l . 43 , no. 3, pp. 704-712, A u g . 1994. [6] R . Ramjee, R . Nagarajan, and D . Towsley, " O n op t ima l c a l l admiss ion control i n cel lu lar ne tworks ," Wireless Networks, v o l . 3, no. 1, pp. 29-41 , M a r c h 1997. [7] Y . Fang , and Y . Z h a n g , " C a l l admiss ion control schemes and performance analysis i n wireless m o b i l e ne tworks ," IEEE Transactions on Vehicular Technology, v o l . 51, no.2, pp. 371-382, M a r c h 2002. [8] M . D . Kulavaratharasah, and A . H . A g h v a m i , "Teletraffic performance evaluation o f m i c r o c e l l personal communica t ion networks ( P C N s ) w i t h p r io r i t i zed handoff procedures," IEEE Transactions on Vehicular Technology, v o l . 48 , no. 1, pp. 137-152, Jan. 1999. [9] R . A . G u e r i n , " Q u e u i n g - b l o c k i n g system w i t h two arr ival streams and guard channels," IEEE Transactions on Communications, v o l . 36, no. 2, pp. 153-163, Feb . 1988. [10] E . D . R e , R . Fan tacc i , and G. Giambene , "Handover queuing strategies w i t h dynamic and f ixed channel a l loca t ion techniques i n l o w earth orbit m o b i l e satellite systems," IEEE Transactions on Communications, v o l . 47, no. 1, pp. 89-102, Jan. 1999. [ I I ] C . H . Y o o n , and C . K . U n , "Performance o f personal portable radio telephone systems w i t h or wi thout guard channels ," IEEE Journal on Selected Areas in Communications, v o l . 11, no. 6, pp. 911-917, A u g . 1993. 11 [12] C . Chang , C . J . C h a n g , and K . R . L o , " A n a l y s i s o f a h ierarchica l ce l lu lar system w i t h reneging and dropp ing for wa i t i ng new cal ls and handoff ca l l s , " IEEE Transactions on Vehicular Technology, v o l . 48 , no. 4, pp. 1080-1091, J u l y 1999. [13] V . K . N . L a u , and S. V . M a r i e , " M o b i l i t y o f queued c a l l requests o f a new ca l l queuing technique for ce l lu lar systems," IEEE Transactions on Vehicular Technology, v o l . 47, no. 2, pp. 480-488, M a y 1998. [14] A . S. A c a m p o r a and M . Naghsh ineh , " C o n t r o l and qual i ty o f service p rov i s ion ing i n high-speed mic ro -ce l lu l a r ne tworks ," IEEE Personal Communications, v o l . 1, no. 2, pp. 36-43, 1996. [15] M . Naghsh ineh and S. Schwar tz , "Dis t r ibuted ca l l admiss ion control i n mobi le /wire less ne tworks ," IEEE Journal on Selected Areas in Communications, v o l . 14, no. 4, pp. 711-717, M a y 1996. [16] D . L e v i n e , I. A k y i l d i z , and M . Naghshineh , " A resource est imation and c a l l admiss ion a lgor i thm for wireless mu l t imed ia networks us ing the shadow cluster concept," IEEE/ACM Transactions on Networking, v o l . 5, no. 1, pp. 1-12, Feb . 1997. [17] C . O l i v e i r a , J . B . K i m , and T. Suda, " A n adaptive bandwid th reservation scheme for high-speed m u l t i m e d i a wireless ne tworks ," IEEE Journal on Selected Areas in Communications, vol. 16, pp. 858-874, A u g . 1998. [18] R Ramanathan, K . M . S iva l i ngam, R A g r a w a l , and S. K i s h o r e , " D y n a m i c resource a l locat ion schemes dur ing handoff for mob i l e m u l t i m e d i a wireless networks ," IEEE Journal on Selected Areas in Communications, v o l . 17, no. 7, pp. 1270-1283, Ju ly 1999. [19] Y . F a n g and I. Ch lamtac , "Teletraffic analysis and m o b i l i t y mode l i ng for P C S networks ," IEEE Transactions on Communications, v o l . 47 , pp. 1062-1072, J u l y 1999. [20] Y . Fang , I. Ch lamtac , and Y . B . L i n , "Channe l occupancy t imes and handoff rate for mob i l e comput ing and P C S networks," IEEE Transactions on Computers, v o l . 47, pp. 679-692, June 1998. [21] E . A . Y a v u z and V . C . M . L e u n g , "Computa t iona l ly efficient method to evaluate the performance o f guard-channel-based c a l l admiss ion control i n ce l lu lar networks ," IEEE Transactions on Vehicular Technology, v o l . 55, no. 4, pp. 1412-1424, J u l y 2006. [22] A . Gersht and K . J . L e e , " A bandwidth management strategy i n A T M networks," Technica l report, G T E Laboratories , 1990. [23] J . W . Roberts , "Teletraffic models for the Te lecom 1 integrated services network," Proceedings of the 10th International Teletraffic Conference, M o n t r e a l , 1983. [24] W . L i and X . C h a o , " M o d e l i n g and performance evaluat ion o f a cel lular mob i l e network," IEEE/ACM Transactions on Networking, v o l . 12, no. 1, Feb . 2004. 12 [25] S. S. Rappaport , " T h e mul t ip le ca l l handoff p rob lem i n personal communicat ions ne tworks ," IEEE 40th Vehicular Technology Conference, pp. 2 8 7 - 2 9 4 , M a y 1990. [26] S. S. Rappaport and G. M o n t e , " B l o c k i n g , hand-off and traffic performance for cel lular communica t i on systems w i t h m i x e d platforms," IEEE 42" Vehicular Technology Conference, v o l . 2, pp. 1018-1021 , M a y 1992. [27] L . H u a n g , S. K u m a r and C . C . J . K u o , " A d a p t i v e resource a l loca t ion for mul t imed ia services i n wire less communica t ion networks ," Distributed Computing Systems Workshop, 2001 International Conference on, 2001 , pp. 307 - 312. [28] L . Q i u , R X i a and J . Z h u , "S tudy on wideband C D M A modula t ion , power control and wireless access for C D M A mul t imed ia systems," Proceedings of IEEE 50th Vehicular Technology Conference, v o l . 5, pp. 2944 - 2948, 1999. [29] S. C h e n and K . Nahrstedt, "Dis t r ibuted qual i ty o f service rout ing i n ad-hoc networks," IEEE Journal on Selected Areas in Communications, v o l . 17, no. 8, Augus t , 1999. [30] I T U - T S G 1 6 / Q . 1 5 v ideo cod ing experts group, I T U - T recommendat ion H . 2 6 3 : V i d e o cod ing for l o w bit rate communica t ion , October 1995. [31] R . G u e r i n , "Equ iva len t capaci ty and its appl ica t ion to bandwid th a l locat ion i n high-speed ne tworks ," IEEE Journal on Selected Areas in Communications, v o l . 9, no. 7, pp. 968-981 , Sept. 1991. [32] J . S. Evans and D . Everi t t , "Effect ive bandwidth-based admiss ion control for mul t i -service C D M A cel lu lar networks ," IEEE Transactions on Vehicular Technology, v o l . 48 , no. 1, Jan. 1999. [33] Q . R e n and G. Ramamurthy , " A real-t ime dynamic connect ion admiss ion controller based on traffic mode l ing , measurement, and fuzzy log ic con t ro l , " IEEE Journal on Selected Areas in Communications, v o l . 18, no. 2, Feb . 2000. [34] S. C . Bors t and D . M i t r a , " V i r t u a l par t i t ioning for robust resource sharing: computat ional techniques for heterogeneous traffic," IEEE Journal on Selected Areas in Communications, v o l . 16, no. 5, pp. 668-678, June 1998. [35] R . A . G u e r i n , " C h a n n e l occupancy t ime dis tr ibut ion i n a ce l lu lar radio system," IEEE Transactions Vehicular Technology, v o l . 35, no. 3, pp. 89-99, 1987. [36] C . J ed rzyck i , and V . C . M . L e u n g , "Probab i l i ty dis t r ibut ion o f channel ho ld ing t ime i n cel lu lar te lephony systems," IEEE Vehicular Technology Conference (VTC'96), v o l . 1, pp. 247 - 2 5 1 , A p r . 1996. [37] Y . Fang , I. Ch lamtac , and Y . B . L i n , " C a l l performance for a P C S network," IEEE Journal on Selected Areas in Communications v o l . 15, no. 8, pp. 1568-1581 , Oct . 1997. 13 [38] Y . Fang , I. Ch lamtac , and Y . B . L i n , " M o d e l i n g P C S networks under general ca l l ho ld ing t imes and c e l l residence t ime distr ibut ions," IEEE Transactions on Networking v o l . 5, no. 6, pp. 893 - 906, D e c . 1997. [39] F. B a r c e l o , and J . Jordan, "Channe l ho ld ing t ime dis t r ibut ion i n pub l ic telephony systems ( P A M R and P C S ) , " IEEE Transactions on Vehicular Technology, v o l . 49, no. 5, pp. 1615-1625, Sep. 2000. 14 C H A P T E R 2 COMPUTATIONALLY EFFICIENT METHOD TO EVALUATE THE PERFORMANCE O F GUARD-CHANNEL-BASED CALL ADMISSION CONTROL IN CELLULAR NETWORKS1 2.1 Introduction The emerging g loba l standards for wireless c o m m u n i c a t i o n networks, such as the third generation ( 3 G ) ce l lu la r networks, promise the eff ic iency and f l ex ib i l i t y o f mu l t i p l ex ing a w ide variety o f traffic f rom convent ional c i rcui t -swi tched vo i ce service to packet-switched voice , data, and m u l t i m e d i a services w h i l e p rov id ing the qual i ty o f service (QoS) expected by service subscribers and their applications. Services w i t h specif ic bandwid th and latency requirements need specif ic amount o f system resources to be al located at the t ime o f ca l l admiss ion to ensure that the required Q o S can be mainta ined dur ing the ca l l . The performance o f c a l l admiss ion control ( C A C ) i n a ce l lu lar ne twork is specified b y the b l o c k i n g p robab i l i ty o f new cal ls i n a ce l l and dropping probabi l i t ies o f handoff cal ls entering a ce l l . C a l l d ropping m a y occur before a ca l l is terminated b y the communica t ing parties i f the cel lular network is unable to assign network resources to enable the c a l l to be handed o f f to a new c e l l that the m o b i l e user has m o v e d into. N e t w o r k planners need to p rov i s ion sufficient network resources such as channel bandwidth to ensure that c a l l b lock ing /dropp ing probabil i t ies stay w i t h i n acceptable l imi t s for various c a l l types or applications. Since dropping an on-go ing c a l l is general ly more objectionable to a m o b i l e user than b l o c k i n g a new ca l l request, a higher pr ior i ty is no rmal ly assigned i n C A C for handoff cal ls over the new ones i n order to m i n i m i z e the ca l l dropping probabil i ty . C a l l admiss ion control for wireless networks has been in tens ive ly studied i n the past [1] [2] and m a n y pr ior i ty-based C A C schemes have been proposed [3]-[18]. In the context o f a g iven number o f channels be ing avai lable i n each c e l l for assignment to admitted calls , 1 A version of this chapter has been published. E. A. Yavuz and V. C. M . Leung, "Computationally Efficient Method to Evaluate the Performance of Guard-Channel-Based Call Admission Control in Cellular Networks," IEEE Transactions on Vehicular Technology, vol. 55, no. 4, pp.1412-1424, July 2006. 15 these C A C schemes can be c lass i f ied into two broad categories. 1) Guard Channel (GC) Schemes: A number o f guard channels are reserved for handoff cal ls . There are four different schemes. a) The cutoff priority scheme b locks a new c a l l i f the number o f free channels is less than the number o f guard channels reserved for handoff ca l l s [3]-[5]. b) The fractional guard channel scheme admits a new c a l l w i t h certain probabi l i ty that depends o n the number o f busy channels i n the c e l l [6]. c) The new call bounding scheme l imi ts the number o f new cal ls admitted to the ce l l to some number less than the total number o f avai lable channels [7]. d) The rigid division-based scheme d ivides a l l channels avai lable i n a ce l l into two groups: one for c o m m o n use and the other o n l y for handof f cal ls [8]. 2) Queuing Priority (QP) Schemes: C a l l s are accepted whenever there are free channels; otherwise either new cal ls are queued w h i l e handoff cal ls are dropped [9], new calls are b l o c k e d w h i l e handoff cal ls are queued [10][11], or a l l a r r iv ing cal ls are queued w i t h certain rearrangements i n the queue [12] [13]. In addi t ion to those g iven above, many dynamic G C schemes [14]-[18] have also been discussed i n the literature to improve system efficiency. These dynamic schemes manage to accept more lower-pr ior i ty cal ls as compared to the f ixed schemes b y adaptively reserving the amount o f resources needed for h igh-pr ior i ty cal ls . In the literature C A C schemes are analyzed us ing M a r k o v cha in models based on a c i rcui t -swi tched ne twork architecture w i t h the assumption that independent Po i s son distributed c a l l requests are originated from different classes o f service or c a l l types, ce l l residence t ime for each c a l l is exponent ia l ly distributed, and each c a l l requires a predetermined channel bandwidth . Convent iona l c i rcu i t - swi tched services inc lud ing telephony are gradual ly be ing replaced b y packet-switched ones as today's communica t ion networks evolve . Conven t iona l C A C schemes, on the other hand, w i l l continue to be useful when appl ied w i t h suitable schedul ing techniques to guarantee Q o S at the packet level since most applicat ions such as interactive mul t imed ia are inherently connect ion oriented and packet-switched connect ions can be provis ioned according to their effective bandwidths [19]-[33]. To avo id the computat ional complex i ty o f s o l v i n g mu l t i d imens iona l M a r k o v chain 16 models , one d imens iona l M a r k o v chain models are c o m m o n l y used (e.g., [11][15]) to obtain the b lock ing /d ropp ing probabi l i t ies for new/handoff cal ls under the assumption that the channel occupancy t imes for both types o f cal ls are iden t ica l ly distr ibuted w i t h the same average values. Ye t this assumption m a y not be appropriate as new and handoff calls m a y have different average channel occupancy times i f not different distr ibutions, as shown i n [19][20] and references therein. E v e n though analysis i n [7] accounts for the more general case o f different average channel occupancy t imes for new and handoff cal ls , the approximat ion emp loyed s t i l l leads to significant discrepancies w i t h the exact solutions. In [22], L i and C h a o mode l ed a m u l t i - c e l l wireless network e m p l o y i n g a h y b r i d GCIQP scheme w i t h transfer o f unsuccessful requests to neighbor ing cel ls as a ne twork o f queues and obtained a product fo rm solut ion. However , the solut ion is restrictive to the protocol considered and m a y not be appl icable for performance evaluations o f GC schemes i n general. Thus , us ing mul t id imens iona l M a r k o v chain models appears to be the on ly means to obtain accurate solut ions for the analysis o f GC schemes. T h i s approach is used i n [22] to evaluate a ce l lu lar ne twork ' s performance b y determining the new c a l l b l o c k i n g and handoff ca l l d ropping probabi l i t ies , and is extended i n [26] to analyze the traffic performance taking into considerat ion the effects o f various types o f mob i l e platforms dis t inguished by different m o b i l i t y characteristics. E v e n though the mul t id imens iona l M a r k o v cha in mode l is capable o f p rov id ing the exact results, the method suffers f rom the curse o f dimensional i ty , w h i c h results i n ve ry h i g h computat ional cost for large systems. Therefore it is s t i l l desirable to come up w i t h approximate solutions that have h igh accuracy and is computa t ional ly efficient. In this chapter, w e propose a nove l method ca l led the "effective holding time''' approach to compute the above-mentioned C A C performance metrics us ing an approximat ion based o n one d imens iona l M a r k o v cha in m o d e l i n g under the condi t ion that the channel occupancy t imes for new and handoff cal ls are independent and exponent ial ly distributed w i t h different average values. The proposed method is easy to implement and has l o w computat ional cost. Th i s chapter is organized as fo l lows . In the next section w e examine three o f the w i d e l y k n o w n C A C schemes b y evaluating their performances us ing the traditional and the normalized analyt ica l methods proposed i n the literature under the assumption that the new and handoff cal ls have different average channel occupancy times. In Sec t ion 2.3, we present 17 the new analyt ical me thod based o n effective holding time, w h i c h y ie lds more accurate approximations than the tradit ional or normal ized methods. In addi t ion to the numerica l results obtained us ing the tradit ional , normal ized , proposed and the direct methods, the accuracy o f the results are also presented and compared a long w i t h the runtime computat ional costs i n Sec t ion 2.4. W e w i l l conclude the paper i n Sec t ion 2.5. 2.2 Existing Methods to Analyze Performance of C A C Schemes In this section w e examine three o f the w i d e l y k n o w n C A C schemes: the new call bounding priority, the cutoff priority, and the fractional guard channel schemes b y evaluating their performance us ing the traditional and the normalized analyt ical methods proposed i n the literature under the assumption that the new and handoff cal ls have different average channel occupancy t imes. Le t A„ and Xn denote the ar r ival rates and 1/JU„ and l/p„ denote the average channel occupancy t imes for new and handoff cal ls , respectively. Le t C denote the total number o f channels i n a c e l l . W e assume that the arr ival processes for new and handoff calls are Poisson , and the channel occupancy times for new cal ls and handoff cal ls are exponent ial ly distributed. A s s u m i n g that both new and handoff calls have the same channel occupancy t ime distributions and average values, the system m o d e l is approximated b y a one d imensional M a r k o v cha in w i t h a f ixed average channel occupancy t ime for the total c e l l traffic. W e refer to this method o f de r iv ing b lock ing /dropp ing probabi l i t ies ana ly t ica l ly as the traditional approach [3][6][7][10][11]. To improve the inaccurate results obtained when the above assumption o n equal average channel occupancy t ime is no longer v a l i d , F a n g and Z h a n g [7] proposed n o r m a l i z i n g the average service times for new and handoff traffic to uni ty so that they become ident ica l for both streams. A l t h o u g h this approximat ion , w h i c h w e ca l l the normalized approach, seems to give better accuracy than the t radi t ional approach, it is s t i l l inaccurate especia l ly for C A C schemes l ike cutoff pr ior i ty and fractional guard channel. 2.2.1 N e w C a l l B o u n d i n g S c h e m e F i g . 2.1 shows the state transit ion diagram for the new c a l l bound ing scheme modeled 18 b y a two-d imens iona l M a r k o v chain , where kn, A/„ un, un and C are as defined before and K is the threshold between 0 and C such that a new ca l l request is admitted o n l y when there are less than K channels occup ied b y new cal ls . Le t p{n\,n2) denote the steady state probabi l i ty that there are n\ new cal ls and n2 handoff cal ls i n the ce l l , w h i c h can be found b y so lv ing the g lobal balance equations obtained from the state transition. Yet as ment ioned above, so lv ing these balance equations becomes computat ional ly ve ry intensive w h e n the state d imens ion increases. A n a l y t i c a l results to compute the b l o c k i n g probabi l i t ies o f new calls pnb and the dropping probabi l i t ies o f handoff cal ls pn(t have been der ived for this scheme i n [7], and an approximat ion is developed b y no rma l i z ing the average service t ime for new and handoff calls . T h i s normalized approach a l lows the ar r iv ing traffic for each type o f ca l l to be scaled appropriately and the b lock ing /d ropp ing probabil i t ies to be related to the traffic intensities. Here is h o w the normalized approach works . Le t p„ = Xn I un and ph = h I Uh, then we can consider an equivalent Po i s son new ca l l arr ival stream w i t h ar r ival rate pn and service rate equal to 1, and an equivalent Po i s son handoff ca l l a r r ival stream w i t h arr ival rate p/t and service rate equal to 1. Le t pa(n\,n2) denote the steady state p robab i l i ty that there are n\ new calls and n2 handoff cal ls i n the ce l l for the normal ized approximat ion mode l . Thus, the f o l l o w i n g stationary dis t r ibut ion is obtained for this approximate m o d e l from the balance equations: n, _ n , pa(nx,n2) = ^LT-^jLT-p"(0,0), 0 < n i <K, nx + n2 < C, n2 > 0, «,! n2\ where P"(0,0) = Pn Ph 0 £ n , < A : , n , + n 2 S C U V W 2 • K n » i C - n , » 2 V " n V P h „ , = o « , ! „ 2 = o n2\ The formulas for new c a l l b l o c k i n g and handoff c a l l d ropping probabi l i t ies are as fo l lows: 19 P n h K n n , C-n, n2 Z Pn y Ph n,=0 " i ! «,=0 " 2 1 „,=o »i! ( C - n , ) ! - (2") «,=0 " | • n,=0 " 2 -O n the other hand, the traditional approach uses the average channel occupancy t ime juav for total ce l l traffic g iven by: 1 - Xn 1 , K 1 = Pn+Ph H ) Pav K+h Pn K+h Ph K+h to replace n„ and JU„ i n (1) and (2) and to obtain new c a l l b l o c k i n g and handoff c a l l dropping probabil i t ies i n the resul t ing one dimensional M a r k o v cha in m o d e l . In that case, the traffic intensities for new and handoff cal ls are g iven by: Pn- — = y^rr-(Pn+ph) P«v + *h ^h / \ Ph =— = . \ -(Pn+Ph) Pav K + K W h e n channel occupancy t imes for both new and handoff cal ls are assumed to be ident ica l ly distr ibuted w i t h the same parameters, the c e l l average channel occupancy t ime also becomes the same as can be easi ly deduced from (3). H o w e v e r , the traditional approach can y i e l d s igni f icant ly inaccurate results w h e n the channel occupancy t imes for new and handoff cal ls have different average values except when the non-pr io r i t i zed scheme (K = C) is used. The normalized approach overcomes this inaccuracy i n the new c a l l bound ing scheme b y exp lo i t ing the symmetr ic nature and the product fo rm o f the detai led balance equations 20 that characterizes this C A C scheme. W e w i l l show i n the f o l l o w i n g sections that both approximations ment ioned above are not good enough to obtain new c a l l b l o c k i n g and handoff ca l l d ropp ing probabi l i t ies w i t h an acceptable accuracy for other C A C schemes. 2 . 2 . 2 C u t o f f P r i o r i t y Scheme Let m < C denote the channel occupancy threshold for acceptance o f new calls . I f the total number o f busy channels is less than m when a new c a l l arrives, the ca l l is accepted; otherwise the n e w c a l l is b locked . A handoff c a l l is a lways accepted i f a free channel is available. T h i s scheme has been extensively studied us ing one d imens iona l M a r k o v chain mode l ing under the assumption that the average channel occupancy t imes o f new and handoff calls are equal [3]. H o w e v e r , this approach provides inaccurate results w h e n the equal mean channel occupancy t ime assumption does not ho ld true. Le t Xn, un, U)„ and C be defined as before. The system can be mode led b y the two dimensional M a r k o v cha in shown i n F i g . 2.2, where (tt\, n2) denotes a feasible state w i t h n\ and n2 representing the numbers o f new and handoff cal ls i n the c e l l , respectively. In contrast w i t h the new c a l l bound ing scheme, the state f lows for the cutoff p r io r i ty scheme no longer have the symmetr ic nature since the f lows for some o f the states are unidi rec t ional , spo i l ing the symmetry as s h o w n w i t h i n circles d rawn i n F i g . 2.1 and F i g . 2.2. Hence , no product form solut ion exists for this scheme w h e n un ^ u„. The f o l l o w i n g stationary dis tr ibut ion is obtained for the cu tof f p r io r i ty scheme us ing the normalized approach, where p" denotes the probabi l i ty that there are / (j = 0, 1, Q busy channels i n the steady state: (Pn + PH)J (p„ + phy-pr.pl^ m+l<j<c where Po = y = 0 J' j=m+l f-21 U s i n g the stationary dis t r ibut ion g iven above, the b l o c k i n g probabi l i t ies for new cal ls , p°b and the d ropp ing probabi l i t ies for handoff cal ls , pahd are obtained as fo l lows : P'L = — J — . — (4) <h(p„+p„y , ^  {P. + P>)M • PC 7=0 ]• j=m+\ J-v" = Q ( 5 ) f(p„+ph)J, f (pn+phr-pr 7=0 J- j=m+\ J-O n the other hand, the corresponding results for the traditional approach i n w h i c h the new and handoff c a l l channel occupancy times are replaced w i t h the average channel occupancy t ime, g iven b y (3), are as fo l lows: t j=m J- Mav Pav Pnb m « 3 , 3 C 7=0 J- P J- Pav Pav p . = Pav Pav G-V J _ . + ^«y + V 1 . ( A + Ky _^ K y-m 7=0 J- fJ-av j=m+\ J- Pav Pa 2.2.3 F r a c t i o n a l G u a r d C h a n n e l S c h e m e The fractional guard channel scheme admits new cal ls w i t h certain probabil i t ies that depend on the number o f busy channels, /. W h e n the number o f busy channels is i, an ar r iv ing new c a l l w i l l be admitted w i t h probabi l i ty / i„ where 0 < 8, < 1, i = 0, 1, . . . , C - l . The new c a l l stream is smooth ly throttled b y decreasing /?, as the network traffic is b u i l d i n g up. A n ar r iv ing handoff c a l l w i l l a lways be admitted unless there is no free channel available, i n 22 w h i c h case a l l cal ls w i l l be b locked . Obv ious ly , this scheme becomes the cutoff pr ior i ty scheme when B0= ... = Pm-i = 1 and Bm = ... = Bc = 0. W h e n B0 > B\ > B2 > ... > Bc, it can also be observed that the new cal ls stream grows at a decreasing rate as the number o f busy channels increases. D u e to this f lexible choice o f new c a l l admiss ion probabil i t ies , the fractional guard channel scheme can be made very general. Le t Xn, Xn, un, Mh, and C be defined as before and let q(c) denote the equ i l ib r ium channel occupancy probab i l i ty when exact ly c channels are occup ied i n a ce l l . It has been shown [27] that q(c) satisfies the f o l l o w i n g recursive equation. ( ^ ^ ± + ^ .).q(c-\) = c-q(c), c = l, . . . ,C (6) R e p l a c i n g the new and handoff ca l l arr ival rates, X„ and Xn, w i t h the new and handoff traffic intensities, pn and ph, respectively, and setting the corresponding channel occupancy times to 1 as suggested b y the normalized approach transform (6) to (A, • Pc-\ + Ph) • <?(c - ! ) = c • l(c)> c = c (7) w h i c h gives us a general expression for a l l GC schemes. c S o l v i n g for #(0) i n the equation ^ q(j) = 1 , w e obtain 7=0 where ft(P.-A+A) g(j)=^ g(0), \<j<c q(0) = 7-1 7=1 Y[(pn-pk+ph) k=0 (8) (9) F r o m (8) and (9), the b l o c k i n g and dropping probabi l i t ies for new and handoff calls 23 for the no rma l i zed approach are respect ively g iven by: c p:h-zZi}-Pj)-q(j), Pc = o (10) P'L = * ( C ) ( i i ) O n the other hand, the corresponding results for the traditional approach can be obtained b y rep lac ing the average channel occupancy t imes o f both types o f cal ls i n (6) w i t h the average channel occupancy t ime o f the total c e l l traffic g iven b y (3). 2.3 The Proposed Performance Evaluation Method E v e n though the normalized approach [7] provides a better approximat ion than the traditional one, it is s t i l l inaccurate for many GC schemes. Therefore, i n order to provide more accurate results w h i l e keeping the computat ional c o m p l e x i t y low, w e present the f o l l o w i n g nove l performance evaluat ion method for GC schemes, referred as the effective holding time approach. S ince it is c ruc ia l to f ind an approximat ion that overcomes the curse o f d imensional i ty when the state d imens ion is large, it is inevitable to attempt reduc ing the two dimensional M a r k o v chain m o d e l to a one d imens iona l one. A s shown previously, this enables a product form solut ion o f the detai led balance equations to be obtained us ing (6). However , w e proceed to s impl i fy (6) b y replacing the average channel occupancy times for both new and handoff cal ls w i t h an average channel occupancy t ime for the total ce l l traffic w h i c h w e refer as the average effective channel occupancy time and denote b y llfieff instead o f \ltiav used b y the traditional approach. The average channel occupancy time, ll/iav, g iven b y (3) can not approximate the value o f the average channel occupancy t ime for the total c e l l traffic accurately, since new and handoff cal ls are not b l o c k e d equally. To obtain 1/jUeff, w e app ly an idea proposed b y Gersht and L e e [28] w h e n deve lop ing an iterative a lgor i thm to calculate approximate occupancy distr ibutions o f objects be ing placed into a knapsack to m a x i m i z e the total reward that is accrued each t ime an object is placed into the knapsack. Inspired b y the w e l l k n o w n Li t t l e ' s theorem, fx = X/N, they defined ue/f as the ratio 24 o f expected number o f both types o f ca l l arrivals to the expected number o f occupied channels, c-i c-i Peff- c ,/=o (12) W e n o w s i m p l y approximate the occupancy probabi l i t ies b y setting q(c) = q(c), c = 0, . . .,C i n (6) and us ing the updated recursive fo rmula g iven be low. (K • + A)• <?(c-1) = c• Meff• «?( c), c = L . . . , C c S o l v i n g for q(0) w i t h X = 1 , we obtain q(j)=——j—* #o)> ^ J ^ c where q(0) = r h v / w . ) *=0 (13) (14) (15) In their knapsack p r o b l e m approach, Gersht and L e e [28] suggested obtaining jue/f us ing (12) b y rep lac ing q(c) w i t h q(c) and updat ing the approximate equ i l ib r ium occupancy probabi l i t ies iteratively, us ing (14) and (15) unt i l each q(c) changes b y no more than e for a l l c = 0,...,C, where e is a smal l number. A l t h o u g h their approach d i d not emphasize starting w i t h an appropriate in i t i a l value for each approximate equ i l i b r i um occupancy probabi l i ty , w e real ize that it becomes a p rob lem since more than one set o f equ i l ib r ium occupancy probabi l i t ies can satisfy (14) and (15) at the same t ime. W h a t makes a set to be the unique solu t ion depends on the values o f 25 the arr ival rates and average channel occupancy t imes o f both types o f cal ls . Therefore, we consider it important that these values are inc luded d i rec t ly i n the computat ion to obtain better approximate results. The c a l l arr ival rates for both types o f cal ls are embraced i n (12), (14) and (15); however w e observe that the average channel occupancy t ime o f each type o f ca l l is not considered di rect ly i n these equations w h e n comput ing the approximate equ i l ib r ium occupancy probabi l i t ies since they are replaced b y the average effective channel occupancy t ime, l/uejf. Hence , w e propose to set the approximate equ i l i b r i um occupancy probabil i t ies in i t i a l ly w i t h the values obtained b y the normalized approach proposed b y F a n g and Zhang [7] i n order to make the approximate equ i l ib r ium occupancy probabi l i t ies closer to the unique solut ion that w e look for, then apply (14) and (15) to obtain the new and handoff ca l l d ropping probabi l i t ies . To summarize , the a lgor i thmic descript ion o f our proposed effective holding time approach is as fo l lows : 1. I n i t i a l i z e e q u i l i b r i u m o c c u p a n c y p r o b a b i l i t i e s q(c) (c = 0 , . . . , C ) b y s e t t i n g t h e m t o t h e c o r r e s p o n d i n g v a l u e s o b t a i n e d f r o m t h e n o r m a l i z e d a p p r o a c h . 2. C a l c u l a t e /ueff u s i n g ( 1 2 ) b y r e p l a c i n g q(c)'s w i t h q(c)'s . 3. C a l c u l a t e q(c) f o r c = 0 , . . . , C u s i n g ( 1 4 ) a n d ( 1 5 ) . 4 . O b t a i n n e w c a l l b l o c k i n g a n d h a n d o f f c a l l d r o p p i n g p r o b a b i l i t i e s u s i n g q(c). A l t h o u g h Gersht and L e e suggested an iterative approach for the solut ion o f the knapsack p rob lem, w e present our approximat ion method i n c losed form since once we compute the effective channel occupancy t ime, ueff, f rom (12) us ing the in i t i a l condit ions obtained from the normalized approach and the corresponding values o f the estimated equ i l ib r ium occupancy probabi l i t ies , q(c), f rom (14) and (15) f o l l o w e d b y that, the value o f the recomputed effective channel occupancy t ime us ing the estimated equ i l i b r i um occupancy probabil i t ies w i l l r emain the same w h i c h w i l l also stabi l ize the values o f the estimated equ i l ib r ium occupancy probabi l i t ies . Af te r the estimated equ i l i b r i um occupancy probabil i t ies 26 are obtained, the new c a l l b l o c k i n g and handoff ca l l d ropping probabi l i t ies are calculated as fo l lows: c-i c-i hd C I 7=0 £V$(./) 7=0 / t f = l - ^ (17) 2.4 Numerical Results 2.4.1 Performance Evaluation of Existing and Proposed Methods In this sect ion w e present numer ica l results o f performance evaluations us ing our nove l effective holding time approach presented i n Sect ion 2.3 and compare them w i t h those obtained us ing the exis t ing traditional and the normalized approaches based on one d imensional M a r k o v cha in models . W e also obtain accurate results us ing a mul t id imens iona l M a r k o v cha in m o d e l for compar i son purposes. T h i s is accompl i shed us ing a numer ica l method ca l led direct (also k n o w n as LU decomposition) to calculate the exact values o f the performance metr ics and the corresponding results are labeled as "direct method" . The numer ica l results obtained for this study not o n l y show that the results obtained from the normalized and the traditional approaches can deviate s ignif icant ly from the accurate results obtained from the direct approach, but also show that our new approach, effective holding time, can achieve results very close to the accurate direct ones. W e do not g ive the results here for the new call bounding scheme since the normalized approach can overcome the inaccuracy o f the traditional approach w h i c h overestimates the n e w c a l l b l o c k i n g probabi l i ty w h i l e it underestimates the handoff ca l l d ropping probab i l i ty w h e n the handoff ca l l traffic is higher than the new c a l l traffic load (i.e., 27 ph > Pn) or v i ce versa b y exp lo i t ing the symmetr ic nature o f the scheme's state transitions and thus leaves l i t t le r o o m for improvement . However , w e focus o n the other schemes considered above for w h i c h this property does not apply. Since fractional guard channel is a general izat ion o f the cutoff priority scheme, we evaluate o n l y the cutoff priority scheme here due to space constraints as same property applies for both schemes. Before examin ing this scheme to evaluate its performance, w e should determine the range o f values that system parameters such as Xn, Xh, l/p.n and l/p.n take i n order to reflect prac t ica l situations. It is general ly accepted i n the literature [3][7][11] to set the ar r ival rate, Xn, and the average channel occupancy t ime, l/pi„, o f new calls i n propor t ion w i t h the arr ival rate, Xh, and the average channel occupancy t ime, 1/uh, o f handoff cal ls , respectively. Therefore f o l l o w i n g the scenarios that have been considered i n the literature, w e apply the values w h i c h are grouped under four different cases and presented i n Table 2.1 as the a r r iva l rates and average channel occupancy t imes for new and handoff cal ls i n order to evaluate the performances o f the selected schemes. To put it shortly, w e assume both ratios, XJXh, p-hlp-n, to have values changing w i t h i n the range o f 4 and 0.5 i n order to cover the scenarios c o m m o n l y considered i n the literature. W e set the total number o f channels, C , to 30 and the channel occupancy threshold, m, to 25 as i n [7]. R e d u c i n g handoff c a l l dropping b y assigning higher pr ior i t ies or other means increases the p robab i l i ty o f b l o c k i n g for new cal ls and thus results i n a tradeoff between these two Q o S measures [6]. Nevertheless , the goal o f a network service provider is to m a x i m i z e the revenue b y i m p r o v i n g network resource u t i l iza t ion , w h i c h is usua l ly associated w i t h m i n i m i z i n g the new c a l l b l o c k i n g probabi l i ty w h i l e keeping the handoff dropping probabi l i ty be low a certain threshold. Hence w e evaluate the approximate evaluat ion methods mentioned above b y grouping the poss ible scenarios into four different cases w i t h parameter values chosen as shown i n Table 2.1 i n order to obtain handoff c a l l d ropping probabil i t ies w i t h i n the range o f 0.01 and 0.1 since this is the interval o f interest w h e n p r o v i d i n g Q o S guarantees i n a cel lular network. In the literature the c o m m o n l y accepted method to evaluate a scheme is to simulate a system mode led w i t h that scheme w i t h c a l l arr ival rates be ing va r i ed to change the traffic load w h i l e the average channel occupancy times o f different types o f cal ls are kept constant. 28 However , cons ider ing that the objective o f this study is to re lax the assumption made b y prev ious ly suggested approx imat ion methods for different types o f cal ls to have different average channel occupancy t imes, w e simulate the system b y v a r y i n g the average channel occupancy t imes instead as i n [7], since hav ing different average channel occupancy times for new and handoff ca l l s is what makes the exis t ing methods inaccurate. One can also notice that b lock ing /d ropp ing probab i l i ty values obtained b y (4) and (5) or (8) and (9), w h i c h were der ived for cutoff priority and fractional guard channel schemes, respectively, b y us ing the normalized approach, r ema in the same as long as the c a l l a r r ival rates and average channel occupancy t imes change w i t h same proportions, thus keeping the traffic loads for both types o f cal ls , ph and p„, constant. Yet , the direct method is expected to g ive different results i n such a case as it considers the c a l l a r r ival rates and average channel occupancy times separately. Cons ide r ing that average channel occupancy times p l ay a stronger role compared to ca l l arr ival rates w h e n obta in ing c a l l b l o c k i n g probabil i t ies accurately us ing g iven approximat ion methods, va ry ing average channel occupancy times o f both types o f cal ls i n proport ion w i t h each other can be jus t i f i ed as w e expect that it w o u l d be more cha l lenging to obtain accurate results w h e n differences i n average channel occupancy t imes exist. In F ig s . 2.3-2.10, w e show the new ca l l b l o c k i n g and handoff ca l l dropping probabil i t ies computed b y the ment ioned approaches for each case g iven i n Table 2.1. In F igs . 2.3 and 2.4, for s imula t ion scenario 1, it is observed that as the new c a l l traffic load gets higher, the t radi t ional approach overestimates both the new c a l l b l o c k i n g and handoff c a l l d ropping probabi l i t ies b y the largest marg in w h i l e the no rma l i zed approach underestimates the handoff ca l l d ropp ing probabil i ty. However , the results obtained b y our proposed effective holding time approximat ion method match the curve obtained b y us ing the direct method very w e l l . A s imi la r conc lu s ion can be drawn for the comparisons o f new ca l l b l o c k i n g and handoff c a l l d ropp ing probabi l i t ies f rom F igs . 2.5 and 2.6 for s imula t ion scenario 2, F igs . 2.7 and 2.8 for scenario 3 and F i g s . 2.9 and 2.10 for scenario 4, respectively. A s expected and mentioned above, w e observe f rom F igs . 2.2, 2.4, 2.6 and 2.8 that the results obtained b y the proposed approx imat ion method diverge from the exact ones s l o w l y w h e n the ratio o f average channel occupancy t imes for new to handoff cal ls increases. In short, when the new and handoff cal ls have different average channel occupancy t imes, the traditional and the normalized approaches result i n significant discrepancies compared to the direct method 29 especial ly w i t h respect to handoff c a l l dropping probabil i ty , w h i c h is overestimated b y the former approach w h i l e it is underestimated b y the latter one. H o w e v e r , the results obtained by the proposed approach can overcome such inaccuracy. 2.4.2 A c c u r a c y a n d R u n t i m e C o m p u t a t i o n a l Cos t s In this sect ion w e examine the accuracy o f traditional, normalized, and the proposed effective holding time approximat ion methods b y us ing the "mean average error ( M A E ) " and the "root mean square error ( R M S E ) " w h i c h are calculated as g iven below. The results are g iven i n Table 2.2 for handoff ca l l d ropping and Table 2.3 for new c a l l b l o c k i n g probabi l i t ies . Further to the results i n F ig s . 2.3-2.10, the most significant results on accuracy are shown i n Table 2.2 for handoff ca l l d ropping probabi l i t ies , where our proposed effective holding time approximat ion method reduces est imation errors substantially compared to the exis t ing approximat ion methods. E v e n though our proposed method estimates the new c a l l b l o c k i n g probabil i t ies w i t h very smal l errors as shown i n Table 2.3, it does not s igni f icant ly reduce them w i t h respect to the est imation errors g iven b y the exis t ing methods due to the re la t ive ly sma l l error margins. The percentage gains i n accuracy o f the results on handoff c a l l d ropping probabi l i ty obtained b y the proposed approximat ion method relative to those obtained b y the normalized and the traditional methods are g iven i n Table 2.4. The percentage gains i n accuracy o f the results o n new c a l l b l o c k i n g probabi l i ty obtained b y the proposed approximat ion method are not g iven here since they are ve ry smal l compared w i t h the results o n handoff ca l l dropping shown i n Table 2.4. In Table 2.4, it is observed that the percentage gains i n estimation accuracy p rov ided b y our proposed approximat ion method relat ive to the exis t ing methods decrease as the ratio o f new to handoff ca l l ho ld ing t imes decreases even though the gains 1 abs(p Pi,real) (18) (19) 30 obtained s t i l l r emain significant. The reason w h y an acceptable approximat ion method is needed to evaluate the performance o f a c a l l admiss ion control scheme when an exact so lu t ion w i t h a numerica l method based o n mul t id imens iona l M a r k o v chain m o d e l i n g exists, is to avo id so lv ing large sets o f f low equations and therefore the curse o f dimensional i ty . To give the reader a better idea regarding the "CPU time" and the amount o f "memory used for evaluating the performance o f any o f the pol ic ies mentioned above, we implement one direct and two w i d e l y used iterative methods, w h i c h are direct (LU decomposition), method of Jacobi (iterative), and method of Gauss-Seidel (iterative), i n order to compare their runtime computat ional costs w i t h that o f the proposed method. The results are g iven i n Table 2.5 for three different scenarios o f total and shared number o f channels, where "CPU time" represents the total process ing t ime ( in seconds) the C P U spent f rom the t ime that the computat ion was started for each method, "number of iterations" represents the number o f times that each a lgor i thm (except the direct one) needs to iterate before it converges wi th respect to the chosen tolerance value, and "used memory" represents the amount o f storage allocated for nonzero matr ix elements. F o r the s imula t ion results presented i n Table 2.5, the f o l l o w i n g parameters are chosen respect ively for the three different scenarios: (a) C = 6, m = 5, A/, = 0.0067, (b) C = 30, m = 25 , Xh = 0.0334, (c) C = 60, m = 50, Xh = 0.1667, w h i l e fi„ = 1/600, uh = 1 /300, and Xn varies from 1/600 to 1/50, 1/120 to 1/10 and 1/2 to 1/24, respectively. T h e new and handoff ca l l arr ival rates are chosen to obtain s imi la r values o f ca l l b lock ing /d ropp ing probabil i t ies w i t h the p rev ious ly computed ones i n each scenario i n order to make the comparisons appropriate. A s seen i n Table 2.5, as the number o f channels increases, the values o f CPU time for the numer ica l so lu t ion methods (both direct and iterative) become s igni f icant ly greater than the corresponding value for the proposed method. The same observat ion can also be made for the used memory. T h i s shou ld not be surprising since our proposed approximat ion method has m u c h smal ler number o f states i n its mode l and a c losed form formulat ion. 2.5 Summary In this chapter w e have examined various guard channel based c a l l admiss ion control 31 schemes i n wire less m o b i l e networks to evaluate their performance ana ly t ica l ly b y using a one d imens iona l M a r k o v cha in mode l . W h e n the average channel occupancy times for new and handoff cal ls are s igni f icant ly different, w e have shown that the traditional and the normalized approaches m a y not be appropriate to use due to their discrepancies i n compar ison w i t h the exact results. E v e n though us ing a two d imens iona l M a r k o v chain mode l c o u l d solve this p rob lem and y i e l d exact results, it gives rise to another problem k n o w n as the curse o f d imens iona l i ty since the d imens ion o f the state space i n such a mode l can increase ve ry qu ick ly . W i t h the objective o f p rov id ing a pract ica l and closed form solut ion to this p rob lem, w e have proposed a new method ca l led effective holding time, w h i c h gives more accurate results w h e n compared to the exis t ing approx imat ion approaches w h i l e keeping the computa t ional cost low. W e have evaluated the accuracy o f the proposed method b y compar ing it w i t h the exact results obtained f rom the direct method based on a mul t id imens iona l M a r k o v chain mode l . W h e n compared w i t h the exis t ing traditional and normalized approximate methods, it is observed that the proposed effective holding time method outperforms the others especial ly w i t h its h i g h percentage ga in i n accuracy when comput ing the handoff c a l l dropping probabil i ty. To demonstrate that the proposed effective holding time method has very l o w runtime computat ional cost, w e have presented results showing that the CPU time and the amount o f memory used b y the proposed method are ve ry l o w compared to the direct and iterative numer ica l methods that can be employed to obtain exact results. A s computat ional cost p lays an important role i n real t ime applicat ions, w e bel ieve a better approximat ion method w i t h l o w complex i ty for evaluat ing the performance o f C A C schemes w i l l motivate the pract ical implementat ion o f these schemes when p rov id ing dynamic c a l l admiss ion control i n the future. H o w e v e r w h e n a s imi la r performance evaluation p rob lem is addressed w i t h the proposed method i n a m u l t i - c e l l network, not on ly ca l l arr ival rates and c a l l durat ion t imes but also changing c e l l capaci ty should be considered due to its dependence o n the locat ion o f users i n ne ighbor ing cel ls . W e are extending this w o r k to inc lude analyt ica l performance evaluation o f mul t i - serv ice mode ls w i t h mul t ip le channel requests, cons ider ing that the level o f relative pr ior i t i za t ion p rov ided to different service types w i t h different Q o S requests is specif ied b y relat ive b lock ing /dropp ing probabil i t ies . 32 F i g . 2.1 State transi t ion diagram for the new c a l l bound ing scheme. F i g . 2.2. State transit ion diagram for the cutoff p r io r i ty scheme. 33 F i g . 2.3 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r io r i ty scheme (Case I) F i g . 2.4 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r io r i ty scheme (Case 34 F i g . 2.5 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r io r i ty scheme (Case II). F i g . 2.6 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r io r i ty scheme (Case II). 35 0.9 0.7 ra 0.6 o 3 o 0.5 a 0.3 m 0.2 X s / / / x / / / / / ' / / / gS . . , . / . . .jr7. . . /j / jT /X / / • *• Direct Method —x- Traditional approach —f— Normalized approach - 0 - Proposed approach 10 15 20 25 New call traffic toad g. 2.7 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r ior i ty scheme (Case III). 0.1 0.09 0.08 0.07 g 0.06 0.05 0.04 0.03 0.02 0.01 *• Direct Method - x - Traditional approach —I— Normalized approach - e - Proposed approach / / / / / >< / / / / / / / / / 7-/ / / X y ^<^C\. A • / — " X * . • • * " " ' . - * • " I—I H 1 10 15 20 25 New call traffic load 30 35 2.8 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r io r i ty scheme (Case III). 36 0.5 •s °-4 S. 0.3 0.1 - •#• Direct Method -x- Traditional approach - 4 — Normalized approach _ - e - Proposed approach / / / / / X / / X x / . y 10 12 14 New call traffic load 16 18 F i g . 2.9 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r io r i ty scheme (Case I V ) . 0.03 0.025 0.02 i i 0.015 S 0.01 • * • Direct Method - x - Traditional approach —t— Normalized approach Proposed approach / / / >< / / / / / / / / >< / / / / / / -® L « ( s t- \ 1 f • 1 H T r New call traffic load F i g . 2.10 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r io r i ty scheme (Case I V ) . 37 T A B L E 2.1 Sys tem parameter values used for each scenario Cases X„ h l/fi„ (sec) \/fih (sec) I 1/40- 1/5 1/20 800 200 II 1/40- 1/5 1/20 400 200 III 1/40- 1/5 1/20 200 200 IV 1/40- 1/5 1/20 100 200 T A B L E 2.2 Errors i n handoff c a l l d ropping probabi l i ty approximations relative to direct method Traditional approach Normalized approach Proposed approach Cases MAE RMSE MAE RMSE MAE RMSE I 2.76 3.42 1.07 1.53 0.14 0.15 II 2.23 2.81 0.95 1.23 0.16 0.18 III 1.57 2.02 0.79 0.89 0.21 0.22 IV 0.88 1.15 0.66 0.70 0.27 0.30 T A B L E 2.3 Errors i n new c a l l b l o c k i n g probabi l i ty approximations relat ive to direct method Traditional approach Normalized approach Proposed approach Cases MAE RMSE MAE RMSE MAE RMSE I 0.09 0.09 0.005 0.006 0.006 0.007 II 0.15 0.16 0.013 0.02 0.012 0.015 III 0.21 0.25 0.018 0.028 0.016 0.02 IV 0.21 0.27 0.035 0.039 0.026 0.03 T A B L E 2.4 Percentage gains i n accuracy o f handoff ca l l d ropping probabi l i t ies obtained b y the proposed approximat ion method relative to those obtained b y the normalized and the traditional methods % Gain over traditional approach % Gain over normalized approach Cases MAE RMSE MAE RMSE I 94.95 95.55 86.98 90.07 II 92.73 93.75 82.97 85.75 III 86.70 89.08 73.62 75.23 IV 68.78 74.00 58.44 57.20 38 T A B L E 2.5 C o m p a r i s o n o f runt ime computat ional costs between the proposed method and the direct and iterative numer ica l methods Total number o f channels = C, total number o f shared channels = m C = 6, m = 5 C = 30, m = 25 C = 60, m = 50 Numerical Methods C P U time number of iterations used memory C P U time number of iterations used memory C P U time number of iterations used memory L U decomposition 0.156s - 4157 3ml4s - 1164845 5h35m36s 16884530 Method of Jacobi 2.172s 1000* 2728 4m8s 1000* 702606 Ih25m50s 1000* 10144576 Method of Gauss-Seidel 0.406s 24 2728 3m49s 59 702606 2h41ml7s 172 10144576 Proposed method 0.109s - 170 0.266s - 698 1.844s - 1358 * indicates that the number of iterations for the method of Jacobi is limited to 1000 in each scenario due to divergence to the desired tolerance. 39 2.6 Bibliography [I] D . E . Ever i t t , "Traff ic engineering o f the radio interface for ce l lu lar mob i l e networks," Proc. IEEE, v o l . 82, no. 9, pp.1371-1382, 1994. [2] H . C h e n , L . H u a n g , S. K u m a r , and C . C . J . K u o , Radio Resource Management for Multimedia QoS Support in Wireless Networks. B o s t o n : K l u w e r A c a d e m i c Publishers , 2004, chapter 2. [3] D . H o n g and S. S. Rappaport , "Traff ic mode l and performance analysis for cel lular mob i l e radiotelephone systems w i t h p r io r i t i zed and non-pr ior i t ized handoff procedures," IEEE Transactions on Vehicular Technology, v o l . 35, pp. 77-92, A u g . 1986. [4] B . L i , C . L i n , and S. T. Chanson , " A n a l y s i s o f a h y b r i d cu tof f p r ior i ty scheme for mul t ip le classes o f traffic i n mul t imed ia wireless ne tworks ," Wireless Networks, v o l . 4, no. 4, pp. 279-290, J u l y 1998. [5] Y . B . L i n , S. M o h a n , and A . Noe rpe l , " Q u e u i n g p r io r i ty channel assignment strategies for handoff and in i t i a l access for a P C S network," IEEE Transactions on Vehicular Technology, v o l . 43 , no. 3, pp. 704-712, A u g . 1994. [6] R . Ramjee, R . Nagarajan, and D . Towsley, " O n op t ima l ca l l admiss ion control i n cel lu lar ne tworks ," Wireless Networks, v o l . 3, no. 1, pp. 29-41 , M a r c h 1997. [7] Y . Fang , and Y . Z h a n g , " C a l l admiss ion control schemes and performance analysis i n wireless m o b i l e ne tworks ," IEEE Transactions on Vehicular Technology, v o l . 5 L no. 2, pp. 371-382, M a r c h 2002 . [8] M . D . Kulavaratharasah, and A . H . A g h v a m i , "Teletraffic performance evaluation o f m i c r o c e l l personal communica t ion networks ( P C N s ) w i t h p r io r i t i zed handoff procedures," IEEE Transactions on Vehicular Technology, v o l . 48 , no. 1, pp. 137-152, Jan. 1999. [9] R . A . G u e r i n , " Q u e u i n g - b l o c k i n g system w i t h two arr ival streams and guard channels," IEEE Transactions on Communications, v o l . 36, no. 2, pp. 153-163, Feb . 1988. [10] E . D . R e , R . Fan tacc i , and G. Giambene , "Handover queuing strategies w i t h dynamic and f ixed channel a l loca t ion techniques i n l o w earth orbit m o b i l e satellite systems," IEEE Transactions on Communications, v o l . 47, no. 1, pp. 89-102, Jan. 1999. [ I I ] C . H . Y o o n , and C . K . U n , "Performance o f personal portable radio telephone systems w i t h or wi thout guard channels ," IEEE Journal on Selected Areas in Communications, v o l . 11, no. 6, pp. 911-917, A u g . 1993. 40 [12] C . Chang , C . J . Chang , and K . R . L o , " A n a l y s i s o f a hierarchical ce l lu lar system w i t h reneging and dropp ing for wa i t ing new calls and handoff ca l l s , " IEEE Transactions on Vehicular Technology, v o l . 48, no. 4, pp. 1080-1091, J u l y 1999. [13] V . K . N . L a u , and S. V . M a r i e , " M o b i l i t y o f queued c a l l requests o f a new ca l l queuing technique for ce l lu la r systems," IEEE Transactions on Vehicular Technology, v o l . 47, no. 2, pp. 480-488, M a y 1998. [14] A . S. A c a m p o r a and M . Naghshineh , " C o n t r o l and qual i ty o f service p rov i s ion ing i n high-speed mic ro -ce l lu l a r ne tworks ," IEEE Personal Communications, v o l . 1, no. 2, pp. 36-43, 1996. [15] M . Naghsh ineh and S. Schwartz , "Dis t r ibuted ca l l admiss ion control i n mobi le /wire less ne tworks ," IEEE Journal on Selected Areas in Communications, v o l . 14, no. 4, pp. 711-717, M a y 1996. [16] D . L e v i n e , I. A k y i l d i z , and M . Naghshineh , " A resource est imation and ca l l admiss ion a lgor i thm for wireless mu l t imed ia networks us ing the shadow cluster concept," IEEE/ACM Transactions on Networking, v o l . 5, no. 1, pp. 1-12, Feb . 1997. [17] C . O l i v e i r a , J . B . K i m , and T. Suda, " A n adaptive bandwid th reservation scheme for high-speed m u l t i m e d i a wireless networks ," IEEE Journal on Selected Areas in Communications, v o l . 16, pp. 858-874, A u g . 1998. [18] R Ramanathan, K . M . S iva l ingam, R A g r a w a l , and S. K i s h o r e , " D y n a m i c resource a l locat ion schemes dur ing handoff for mob i l e mu l t imed ia wireless networks ," IEEE Journal on Selected Areas in Communications, v o l . 17, no. 7, pp. 1270-1283, J u l y 1999. [19] R . G u e r i n , "Equ iva len t capaci ty and its appl ica t ion to bandwid th a l locat ion i n high-speed ne tworks ," IEEE Journal on Selected Areas in Communications, v o l . 9, no. 7, pp. 968-981 , Sept. 1991. [20] J . S. Evans and D . Everi t t , "Effec t ive bandwidth-based admiss ion control for mul t i - serv ice C D M A cel lu lar networks ," IEEE Transactions on Vehicular Technology, v o l . 48, no. 1, Jan. 1999. [21] Q . R e n and G. Ramamurthy , " A real-t ime dynamic connect ion admiss ion controller based o n traffic mode l ing , measurement, and fuzzy log ic con t ro l , " IEEE Journal on Selected Areas in Communications, v o l . 18, no. 2, Feb . 2000. [22] Y . F a n g and I. Ch lamtac , "Teletraffic analysis and m o b i l i t y mode l i ng for P C S networks ," IEEE Transactions on Communications, v o l . 47 , pp. 1062-1072, Ju ly 1999. [23] Y . Fang , I. Ch lamtac , and Y . B . L i n , "Channe l occupancy t imes and handoff rate for mob i l e comput ing and P C S networks ," IEEE Transactions on Computers, v o l . 47, pp. 679-692, June 1998. 41 [24] W . L i and X . C h a o , " M o d e l i n g and performance evaluat ion o f a ce l lu lar mobi le network," IEEE/ACM Transactions on Networking, v o l . 12, no. 1, Feb . 2004. [25] S. S. Rappaport , "The mul t ip le ca l l handoff p rob lem i n personal communicat ions networks ," IEEE 40th Vehicular Technology Conference, pp. 2 8 7 - 2 9 4 , M a y 1990. [26] S. S. Rappaport and G. M o n t e , " B l o c k i n g , hand-off and traffic performance for cel lular communica t i on systems w i t h m i x e d platforms," IEEE 42" Vehicular Technology Conference, v o l . 2, pp. 1018-1021 , M a y 1992. [27] K . W . Ross , M u l t i - s e r v i c e L o s s M o d e l s for Broadband Te lecommunica t ion Ne tworks . L o n d o n : Spr inger -Ver lag , 1995, chapter 3. [28] A . Gersht and K . J . Lee , " A bandwidth management strategy i n A T M networks," Technica l report, G T E Laboratories , 1990. 42 C H A P T E R 3 COMPUTATIONALLY EFFICIENT PERFORMANCE EVALUATION METHODS FOR CALL ADMISSION CONTROL SCHEMES IN MULTI-SERVICE CELLULAR NETWORKS2 3.1 Introduction The emerging g loba l standard for next generation wireless networks has promised to provide not o n l y convent ional vo ice services but also the eff ic iency and f l ex ib i l i ty o f mu l t i p l ex ing a w i d e var ie ty o f traffic f rom data to mu l t imed ia applicat ions due to increasing demand c o m i n g f rom users that these services shal l also be avai lable o n the move . H o w e v e r satisfying the diverse Q o S requirements o f these services over ce l lu la r networks has become even more cha l lenging due to reduced c e l l size and hence increased user mobi l i ty . C a l l admiss ion control ( C A C ) schemes are deployed to select ively l i m i t the number o f admitted calls f rom each Q o S class to m a x i m i z e the network u t i l i za t ion w h i l e satisfying the Q o S constraints [1]. C a l l admiss ion control for w i r ed and wireless networks has been intensively studied i n the past and m a n y pr ior i ty based ca l l admiss ion control schemes have been proposed [2]-[14]. C a l l s w i t h more stringent Q o S requirements are g iven higher priorit ies b y hav ing exc lus ive access to a number o f reserved channels. R e d u c i n g b l o c k i n g probabil i t ies o f calls w i t h higher pr ior i t ies increases the probabi l i ty o f b l o c k i n g for cal ls w i t h relat ively lower priorit ies resul t ing i n a tradeoff between Q o S classes. The goal is to sustain a balance between Q o S classes w h i l e satisfying the respective Q o S requirements. H a n d o f f cal ls are g iven pr ior i ty over n e w ones to m i n i m i z e ca l l d ropping probabi l i t ies since dropping an ongoing c a l l is general ly more objectionable to a m o b i l e user than b l o c k i n g a new ca l l request. A set o f guard channels are reserved for p r io r i t i zed cal ls i n Guard Channel (GC) schemes such as cutoff priority [2]-[5], fractional guard channel [6], new call bounding [7] 2 A version of this chapter has been accepted for publication. E. A. Yavuz and V. C. M. Leung, "Efficient Approximations for Call Admission Control Performance Evaluations in Multi-Service Networks," IEEE GLOBECOM 06, San Francisco, CA, November 2006. 43 and rigid division based [8] schemes. M a n y dynamic G C schemes have also been proposed to m a x i m i z e the ne twork u t i l i za t ion by reserving network resources for relat ively higher pr ior i ty cal ls adapt ively so that more re la t ively lower pr ior i ty cal ls can be admitted [9]-[14]. Eff icient adaptive reservation depends on reliable and up-to-date system status feedback; however exact analyses o f these schemes us ing mul t id imens iona l M a r k o v chain models are intractable i n real t ime due to the need to solve large sets o f f l o w equations. Hence , performance metr ics such as c a l l b l o c k i n g probabil i t ies are general ly evaluated us ing one dimensional M a r k o v cha in models based on c i rcui t -swi tched network architecture under the s impl i fy ing assumptions that ca l l arrivals are Po i sson , channel occupancy times are exponent ia l ly distr ibuted w i t h equal mean values and traffic classes have same capacity requirements. D u e to the popular i ty o f Internet and m u l t i m e d i a applicat ions, increasingly traffic carr ied over wire less networks are packet-switched and stat is t ical ly mul t ip l exed over shared channels to improve network u t i l iza t ion , w h i c h makes performance evaluation o f ca l l admiss ion control schemes harder due to the dynamic nature o f the traffic. T h i s dif f icul ty can be overcome b y us ing the effective bandwidth [15]-[17] to represent the traffic demand o f a packet-switched traffic stream so that appl icat ion o f the above schemes to a packet-switched network can s t i l l be evaluated us ing M a r k o v cha in models . T h i s approach has been successfully appl ied to ce l lu la r network b y Evans and Ever i t t i n [16]. Howeve r , the s i m p l i f y i n g assumptions ment ioned above m a y not be appropriate i n many situations since cal ls w i t h different priori t ies m a y have different average channel occupancy t imes i f not different distributions [18] [19]. E x i s t i n g performance evaluation methods based o n one d imens iona l M a r k o v chain approximat ions , such as traditional and normalized, lead to significant discrepancies when average channel occupancy times for distinct Q o S classes are different [20]. Thus exact analysis methods based on mul t id imens iona l M a r k o v cha in models appeared to be the o n l y means to obtain accurate solutions for evaluat ing c a l l admiss ion control schemes. In [21], Rappaport obtained ca l l b l o c k i n g probabi l i t ies for cal ls o f various priori t ies i n a ce l lu lar network by us ing a mul t id imens iona l m o d e l , whereas w i t h M o n t e , the authors developed an analyt ical mode l for traffic performance analysis us ing a mul t id imens iona l b i r th death process to take into considerat ion the effects o f various platform types dis t inguished b y different m o b i l i t y characteristics o n performance [22]. These methods suffer f rom the curse o f dimensionali ty, 44 w h i c h results i n ve ry h i g h computat ional cost for large systems, despite p r o v i d i n g the exact solutions. A p p r o x i m a t i o n methods for performance evaluations that have a h igh accuracy and l o w computat ional cost are needed i f dynamic ca l l admiss ion control schemes are to be implemented i n real t ime systems that adapt to dynamic changes i n traffic statistics. L i and Chao [23] obtained a product form solut ion b y mode l ing a m u l t i c e l l wireless network as a network o f queues e m p l o y i n g a hyb r id GCIQP scheme w i t h transfer o f unsuccessful requests to neighbor ing cel ls ; however their solut ion is restrictive to the pro toco l considered and therefore m a y not be appropriate to be used for the performance evaluat ion o f mult i -service models . In [24], Gersht and L e e proposed an iterative a lgor i thm b y mod i fy ing the approximat ion suggested b y Roberts [25] to improve its accuracy w h e n the service rates differ. H o w e v e r w e showed i n [20] that starting w i t h an inappropriate in i t i a l value leads to significant discrepancies and thus proposed an easy to implement c losed form approximat ion method based on one d imens iona l M a r k o v chain mode l ing . W e assumed that a l l classes have same capaci ty requirements and independent and exponent ia l ly distributed channel occupancy t imes wi thout the necessity o f hav ing the same average values. Yet this method applies o n l y w h e n the c a l l traffic is homogeneous. In the absence o f a product form solut ion when capaci ty requirements o f various classes differ, c a l l traffic is heterogeneous, calculat ing the channel occupancy dis t r ibut ion involves so lv ing the balance equations numerical ly , w h i c h is demanding for a l l but smallest channel capacities. In [26], Bors t and M i t r a developed computa t ional algori thms for the mul t i -service case b y c o u p l i n g the computat ion o f jo in t channel occupancy probabi l i t ies w i t h that o f used capaci ty assuming that channels are occupied independently. The authors solved the balance equations through numer ica l iteration but the results can o n l y be comparative when the number o f exis t ing ca l l arr ival types are h igh due to authors ' channel occupancy independence assumption. In this chapter, we classify c a l l admiss ion control schemes into two nove l categories based on the nature o f connect ing l inks i n a scheme's transit ion diagram; symmetric and asymmetric. W e present performance evaluat ion methods w i t h h igh computat ional eff ic iency for each category under the s imp l i fy ing assumptions that ca l l arr ival and channel occupancy t imes for a l l Q o S classes are exponent ia l ly distr ibuted, but w i t h different average values i n general. Th i s chapter is organized as fo l lows. In the next section w e obtain the product form 45 exact solut ion fo rmula to evaluate symmetric c a l l admiss ion control schemes i n mult i -service networks. In Sec t ion 3.3, w e propose a nove l performance evaluat ion approximat ion method, w h i c h w e c a l l state space decomposition, to evaluate asymmetric c a l l admiss ion control schemes i n mul t i - se rv ice networks. Sect ion 3.4 presents the numer ica l results to compare the approximat ion method proposed i n Sect ion 3.3 w i t h the exact analysis and previous ly proposed approx imat ion methods. W e show that the runt ime computat ional cost o f the proposed approximat ion method is s ignif icant ly lower than that o f the exact analysis. Sect ion 3.5 concludes the chapter. 3.2 Performance Evaluation of Symmetric Call Admission Control Schemes W e define a c a l l admiss ion control scheme symmetric i f each pai r o f nodes are connected b y two unid i rec t iona l l inks i n opposite directions i n state transit ion diagram o f the scheme's M a r k o v cha in m o d e l . The w i d e l y k n o w n complete sharing (CS), complete partitioning (CP) and new call bounding schemes can then be regarded as symmetr ic . In this section w e obtain a product form exact solut ion formula to evaluate symmetr ic ca l l admiss ion control schemes i n mul t i - serv ice networks where a l l Q o S classes have distinct capacity requirements. W e consider a cel lu lar system employ ing a symmetr ic scheme, new ca l l bounding i n this case, and two classes o f calls for the benefit o f s imp l i c i t y al though any number o f classes c o u l d be possible; non-pr ior i t ized and pr io r i t i zed , where the latter enjoy a h igh service pr ior i ty than the former: Le t Xnp and \ p denote the ar r iva l rates, and l/unp and XIpp denote the average channel occupancy t imes for non-pr ior i t i zed and pr ior i t i zed cal ls respectively. Le t C denote the total number o f channels i n a c e l l and b„p and bp denote the required bandwid th for non-pr ior i t ized and pr ior i t i zed cal ls , respectively. W e assume that the arr ival processes for both types o f cal ls are Poisson , and their channel occupancy times are exponent ia l ly distributed. Then , let K be the threshold between 0 and C for the new ca l l bounding scheme and a non-pr ior i t ized ca l l is admitted o n l y w h e n there are less than K channels occup ied b y non-pr ior i t i zed calls i n the network. The traditional method, w h i c h uses a one d imens iona l M a r k o v cha in mode l w i t h a fixed average channel h o l d i n g t ime for total ce l l traffic, leads to inaccurate results when average channel occupancy t imes for a l l types o f cal ls differ. A product form solut ion is 46 presented i n [7] to obtain the b l o c k i n g probabil i t ies o f non-pr ior i t ized , B„p and pr ior i t ized cal ls , Bp accurately b y exp lo i t ing the symmetr ic nature o f the scheme assuming that a l l Q o S classes have same capaci ty requirements. The authors [7] no rma l i zed the average channel occupancy t ime for both types o f cal ls to a l low the a r r iv ing traffic for each type o f ca l l to be scaled appropriately. In this section we obtain a product form solu t ion where a l l Q o S classes have distinct capaci ty requirements. Le t pnp = Xnp I pnp and pp = Xp I JUP, then the pr ior i t i zed and non-pr ior i t ized Poisson ca l l arr ival stream is P o i s s o n w i t h arr ival rates pp and pnp, respect ively and service rates (corresponding channel occupancy times) that are equal to 1, are equivalent to the or ig ina l streams w i t h respect to the M a r k o v chain mode l since o n l y traffic loads are required to obtain the stationary distr ibutions. Yet , the arr ival rates i n the o r ig ina l system are different. Le t q{nnp,np) denote the steady state probabi l i ty that there are nnp non-pr ior i t ized cal ls and np pr ior i t i zed cal ls i n the.system. T h e n w e obtain the f o l l o w i n g stationary dis t r ibut ion: 0<n„pbnp<K " np " p (nnpbnp + npbp) < C where rip, nnp > 0 q(0,0) z p p r np I p \K/KP J n n»p lc-(%, -K K )J n y np V Hp Z n np «„ = 0 and |_...J represents the " f l o o r " function w h i c h rounds its input to the nearest integer less than or equal to the value o f the input itself. Thus, the formulas for non-pr io r i t i zed and pr ior i t ized 47 ca l l b l o c k i n g p robab i l i ty are as fo l lows : Wlb„P\\ic-{n„p-bnp))lbp\ Bnp = S (nnp>np) (1) "nP=(> « / p = 0 {(ripbp + rinpbnp) >C}U {nnpbnp > K) LwJL(c-(«»,-^ KJ n ! n ! Z Z n ^ J ^ lc-((»„-6vK)J n" «„„=0 I n =0 U / O «„=o (2) rnp P i(C-(npbnp))/bJ _[K^_np\ 'i(C-(np-bnp))/bJ 2^ n « =0 l*/*J [c-{{"nP\P)/bp)\ D"n "„„=0 "«/> «„=() W h e n K = C, the new ca / / bounding scheme becomes the non-pr ior i t ized scheme, however non-pr ior i t ized , B , and pr ior i t ized , Bp, ca l l b l o c k i n g probabi l i t ies w i l l not be the same unt i l bnp = bp. Appa ren t ly w h e n bnp = bp= 1, both probabi l i t ies become: (PnP+ PPY a B =B = — np p f(pnP+pPy 48 3.3 Performance Evaluation of Asymmetric Call Admission Control Schemes W e define a c a l l admiss ion control scheme asymmetric w h e n some pairs o f nodes i n the state transi t ion d iagram o f scheme's M a r k o v cha in m o d e l have unidi rec t ional l inks on ly i n one direct ion. The w i d e l y k n o w n cutoff priority and fractional guard channel schemes, w h i c h make decis ions on whether an ar r iv ing non-pr ior i t ized ca l l is go ing to be accepted or not based on the number o f total occupied channels i n the system, can both then be regarded as asymmetr ic schemes. W e consider a cel lular system w i t h two classes o f calls where pr ior i t ized cal ls enjoy a higher service pr ior i ty than the non-pr ior i t i zed ones. Le t Xp, X„p, p:p, HnP, bp, bnp, Bi, m and C be defined as before and qp(j) and qnp(r) denote the estimated equ i l ib r ium channel occupancy probabil i t ies when exact ly j p r io r i t i zed calls and r non-pr ior i t ized ca l ls , respectively, exist i n the system. Le t /?,• (z = 0, 1,..., C - 1) denote the admiss ion probabi l i ty o f an a r r iv ing non-pr ior i t ized ca l l w h e n the number o f busy channels is i and kj (j - 0,1,... (]_c/6 J - i ) ) denote the admiss ion probabi l i ty o f an a r r iv ing pr ior i t i zed ca l l when j p r io r i t i zed cal ls exist i n the ce l l regardless o f the number o f exis t ing non-pr ior i t ized cal ls . Thus kj is s imi l a r to /?,, however /?, is a predefined user cont ro l led parameter that indicates whether an a r r iv ing non-pr ior i t ized ca l l w i l l be admitted or not based on the number o f occupied channels i n the system as opposed to kj w h i c h is extracted from the mul t id imens iona l m o d e l o f the system. W e present the f o l l o w i n g nove l performance evaluat ion approximat ion method referred as state space decomposition. Instead o f evaluat ing the system using a one dimensional M a r k o v cha in m o d e l b y grouping the nodes w i t h the same total number o f occupied channels regardless o f the types o f cal ls , we group the nodes w i t h the same number o f calls o f a certain type to obtain "supernodes" to compose a one d imens iona l M a r k o v chain mode l for each type o f c a l l . B y grouping nodes w i t h the same number o f pr ior i t ized calls such as (0,0), (bnp,0),...,(bnplmibnp\-{),0), (b„plm/b„Jfi) or (0, bp), (bnp,bp),..., (bnplm/b„p]-\),bp), (bnp^njb^bp) together to obtain supernodes as s h o w n i n F i g . 3.1, we can frame a one d imens iona l M a r k o v cha in mode l that w e can solve to obtain the steady state probabil i t ies o f each o f these supernodes. The same approach can be u t i l i zed to group nodes that have the same number o f non-pr ior i t ized cal ls such as (0,0), (0, bp),...,(0, bp.§c/bp§) or 49 (bnp,0), (bnp, bp),..., (bnp, bp.^c-b )jbJj) together. B o t h one d imens iona l M a r k o v chain models obtained above are g iven i n F igs . 3.1 and 3.2 for p r io r i t i zed and non-pr ior i t ized cal ls , respectively. In F i g . 3.1, w e observe that for a l l supernodes except the ones that have at least one member node that represents a system state i n w h i c h the total number o f occupied channels is equal to the total number o f channels i n the system, C, there exist (m+\) pairs o f transit ional f lows between their member nodes and the corresponding member nodes that belong to their ne ighbor ing supernodes. Conversely , for the rest o f the supernodes there exist some member nodes that do. not have transitional f lows i n between any o f the corresponding nodes that be long to their ne ighbor ing supernodes. Same can also be observed for the supernodes shown i n F i g . 3.2; however i n addi t ion to those ment ioned above there exist some other member nodes w i t h unidi rec t ional transition f lows. In F i g . 3.3, w e show the one d imens iona l M a r k o v cha in m o d e l for pr ior i t i zed calls where each node represents a supernode composed o f a set o f nodes shown i n F i g . 3.1. W e determine the values o f the admiss ion probabil i t ies for p r io r i t i zed cal ls , kj, b y obtaining the ratio o f the sum o f occupancy probabil i t ies o f the feasible member nodes o f a supernode, for w h i c h the system admits an a r r iv ing pr ior i t ized ca l l , to the sum o f occupancy probabil i t ies o f a l l feasible member nodes o f that part icular supernode. Thus , when j = 0, ^•.•••§_(C-{m/b„/,\-brip)/bp}-\), the admiss ion probabil i t ies for p r io r i t i zed cal ls , kj, are equal to 1. The equ i l i b r i um channel occupancy probabi l i ty w h e n exact ly j p r io r i t i zed calls exist, where qp(j),j = 0, 1,... \cjbp\, can be obtained from the f o l l o w i n g recursive equation. (3) , w e obtain (4) 50 where -1-1 (5) 7=1 Le t hr, where (r = 0, 1,... (Jm/6,,J-i))> denote the admiss ion probabi l i ty o f an ar r iv ing non-pr ior i t ized c a l l w h e n r non-pr ior i t ized calls exist, regardless o f the number o f exis t ing pr ior i t ized cal ls . Howeve r , hr shal l not be confused w i t h /?,• since the latter is a predefined user control led parameter that indicates whether an a r r iv ing non-pr ior i t i zed c a l l w i l l be admitted or not depending o n the number o f occupied channels. S i m i l a r to, yet s l igh t ly different than kj, w e determine the values o f hr b y obtaining the ratio o f the sum o f occupancy probabil i t ies o f the feasible member nodes o f a supernode, for w h i c h an a r r iv ing non-pr ior i t ized ca l l is admitted, mu l t i p l i ed w i t h Bt to the sum o f occupancy probabi l i t ies o f a l l the feasible member nodes o f that part icular supernode. In F i g . 3.4, w e show the one d imensional M a r k o v cha in m o d e l for non-pr ior i t ized calls where each node represents a supernode composed o f a set o f nodes shown i n F i g . 3.2. The equ i l ib r ium channel occupancy probabil i t ies , qnp(r), c o u l d be obtained s imi la r ly to pr ior i t ized cal ls i f unid i rec t ional transit ion f lows, shown i n F i g . 3.2, d i d not exist. H o w e v e r their existence needs to be taken into account b y adjusting p n p affil iated w i t h each supernode appropriately. Therefore w e initiate u'„p(r) to replace unp affil iated w i t h each supernode i n the mode l g iven i n F i g . 3.4 and determine its value b y d i v i d i n g the number o f transit ion f lows departing f rom the associated supernode w i t h the number o f pairs o f b id i rec t iona l transition f lows i n between the same part icular supernodes. (r)=uC~<r)l\p^\ • r=\-mlb> J ( 6 ) l(m-(r-l))/bp] 51 T h e n w e can obtain the occupancy probabil i t ies qnp(r), r = 0,1, . . .(LTM/6 J - l ) , w h i c h satisfy the f o l l o w i n g recursive equation. (KP • hr-\ )-qnp{r-\) = r- M'np (r) • qnp (r), r = 1,..., \_m/bnp _ (7) \j»JK J S o l v i n g for q„p(0) i n the equation y qn ( r ) = i , w e obtain qnpir) = ~° • qnpm < r < [mjbj (8) where (9) The admiss ion probabi l i t ies for pr ior i t ized , kj, and non-pr ior i t i zed cal ls , hr, cannot be obtained wi thout comput ing the occupancy probabi l i ty o f each feasible node. E v e n i f the occupancy probabi l i t ies o f the supernodes for p r io r i t i zed and non-pr ior i t i zed calls can be obtained us ing this method, we s t i l l need to compute the occupancy probabi l i t ies o f certain feasible nodes since jo in t occupancy probabil i t ies o f these supernodes cannot be used due to their dependencies. 52 To overcome these diff icul t ies , we suggest the f o l l o w i n g iterative approach: 1. Ini t ia l ize the value o f estimated equ i l ib r ium occupancy probabi l i t ies (q{nnp,np) for nnp = 0,1..[m/bnp\ and np = 0,1..{_C/bp J) b y setting them equal to 1 / (total number o f feasible nodes). 2. Calcula te ju'np(r) f o r r = l , . . . \mjbnp\ us ing (6). 3. Iterate w i t h the f o l l o w i n g steps unt i l the changes i n the updated values o f kj and hr are not less than a chosen resolut ion. 3.1. Calcula te and update kj for / = 0 ,1 , . . . {_C/bp J -1 ) and qp(j) for / = 0 ,1 , . . . \_C/bp J us ing (4) and (5). 3.2 Update the values o f estimated occupancy probabi l i t ies , q(n ,n), by apport ioning the value o f the last updated occupancy probabil i ty , qp(j), o f the corresponding supernode for p r io r i t i zed cal ls amongst its nodes w i t h respect to the value o f last updated occupancy probabil i ty , qnp(r), o f the corresponding supernode for non-pr ior i t i zed cal ls . 3.3. Calcula te and update hr for r = 0 ,1 , . . . §m/bnp}-\) and qnp(r) for r = 0 ,1 , . . . [ m / / 3 j us ing (8) and (9). 3.4. Update the values o f estimated occupancy probabi l i t ies , q(n ,n), by apport ioning the value o f the last updated occupancy probabi l i ty , qnp(r), o f the corresponding supernode for non-pr ior i t i zed calls amongst its nodes w i t h respect to the value o f last updated occupancy probabi l i ty , qp(j), o f the corresponding supernode for p r io r i t i zed cal ls . 4. Obta in c a l l b l o c k i n g probabil i t ies for pr ior i t ized and non-pr ior i t ized calls us ing The ca l l b l o c k i n g probabi l i t ies for both types o f cal ls are calculated as fo l lows when the f inal estimated values o f equ i l i b r ium occupancy probabi l i t ies , q(n ,n ), are obtained. Bp=^q(ni(C-(n-bv))/bJ (10) «=o 53 [m/b„p\[(C-a.b„p/bp\ Bnp = Z Z^'") n=0 «=0 (11) (a-bnp+n-bp)>[m/bnp\ Despi te its iterative nature, w e expect the state space decomposition method to have l o w computat ional cost since decompos ing the whole state space into subspaces and forming supernodes to app ly one d imens iona l M a r k o v chain m o d e l i n g u t i l ize the closed form formulas obtained f rom one d imens iona l M a r k o v chain models and make the proposed method easy to implement for real t ime applications. 3.4 Numerical Results In this sect ion w e compare the performance o f the proposed method, state space decomposition, w i t h Bor s t and M i t r a ' s approximat ion [26] and the direct (also k n o w n as LU decomposition) numer ica l method. W e show that the runt ime computat ional cost o f the proposed approx imat ion method is negl ig ible compared to the exis t ing numer ica l methods ' (i.e., direct, method o f Jacobi , method o f Gauss-Seidel) w i t h respect to CPU time and memory needed to obtain the results. W e investigate the cutoff p r io r i ty scheme, w h i c h is a special case o f fractional guard channel scheme, us ing the f o l l o w i n g set o f parameters: C = 32, m = 24 (/5, = 1 for i - 0, . . . 23, 0 otherwise), = 0.1, \/\xnp = 200, IIup = 50 and Xp is varied f rom 1 to 0.05. H o w e v e r any fractional guard channel scheme can be chosen since other choices o f /5,'s w o u l d give s imi lar results. W e set the capaci ty requirement for non-pr ior i t ized cal ls , bnp, to 1 and vary the capacity requirement for p r io r i t i zed calls , bp, by setting its value to 1, 2 and 4. F igs . 3.5 to 3.10 depict the p r io r i t i zed and non-pr ior i t ized ca l l b l o c k i n g probabi l i t ies obtained us ing the direct, Bors t and M i t r a ' s and the proposed methods under va ry ing p r io r i t i zed ca l l traffic load, respectively. W e observe for a l l values o f bp that when pr io r i t i zed ca l l traffic load is higher than non-pr ior i t ized c a l l traffic load (i.e., pp > pnp), both ca l l b l o c k i n g probabi l i t ies approximated b y the proposed method match the exact results obtained b y the direct numer ica l method very w e l l . H o w e v e r Bors t and M i t r a ' s approximat ion method overestimates the pr io r i t i zed ca l l b l o c k i n g probabi l i ty generously 54 w h i l e it underestimates the non-pr ior i t ized ca l l b l o c k i n g p robab i l i ty extensively when PP > pnP- W h e n the p r io r i t i zed ca l l traffic load is lower than the non-pr ior i t ized ca l l traffic load (i.e., pp < pnp), the state space decomposition method s l igh t ly overestimates the pr ior i t ized ca l l b l o c k i n g probabi l i ty w h i l e it s l ight ly underestimates the non-pr ior i t ized ca l l b l o c k i n g probabi l i ty w i t h the discrepancy increasing as both traffic loads are decreasing. Yet , Bors t and M i t r a ' s method gives a better approximat ion o n l y w h e n both traffic loads are very l o w due to its assumption on independent channel occupancy. The discrepancy observed when non-pr ior i t ized ca l l traffic load takes over pr ior i t ized ca l l traffic load (i.e., pp < pnp) is due to an assumption that we made i n the iterative solut ion described above, i.e., the steady state probabil i t ies o f a l l nodes that are members o f the same particular supernode for p r io r i t i zed calls are proport ional to each other w i t h the same ratio that exists between the steady state probabil i t ies o f the corresponding supernodes for non-pr ior i t ized cal ls , and v i ce versa. Therefore w e expect proposed method to approximate steady state probabi l i t ies o f nodes that are members o f supernodes w h i c h have relat ively less number o f member nodes better w i t h respect to the others that are members o f supernodes w h i c h have re la t ive ly more number o f member nodes. H o w e v e r this is not a significant p roblem unless pnp » pp, since ca l l b lock ings mos t ly occur at nodes that are members o f supernodes w h i c h have re la t ive ly less number o f member nodes and thus closer to the edges o f transit ion diagrams. W h e n non-pr ior i t ized ca l l traffic load takes over the pr ior i t ized ca l l traffic load, the steady state probabil i t ies o f the nodes that have re la t ive ly more number o f non-pr ior i t ized cal ls dominates the others needed to compute a part icular ca l l b l o c k i n g probabi l i ty and thus lead to discrepancy. O n the other hand, Bors t and M i t r a ' s method approximates better on ly when both ca l l traffic loads are ve ry l o w due to the channel occupancy independence assumption that the authors made [26]. W h e n each o f the ind iv idua l classes accounts for a substantial por t ion o f the total amount o f capaci ty i n use, it leads to mutual dependence as the traffic load increases. B o t h approx imat ion methods perform relat ively better w h e n the capaci ty requirement for p r io r i t i zed cal ls , bp, increases. W h e n w e increase the number o f shared channels, m, to 28 and keep a l l the parameters g iven above same, less number o f non-pr ior i t ized cal ls are b locked . W e observe that ca l l b l o c k i n g probabi l i t ies for both types o f cal ls are estimated more accurately since scheme's transit ion d iagram has more supernodes for non-pr ior i t ized cal ls that have relat ively 55 less number o f member nodes. W e make another compar i son i n F ig s . 3.11 to 3.16 b y us ing the f o l l o w i n g set o f parameters: C = 32, m = 28 (/?, = 1 for i = 0, . . . 27, 0 otherwise), X„p = 0.1, l/fi„p = 200, 1/jUp = 50 and Xp is var ied f rom 1 to 0.05. W e set the capacity requirement for p r io r i t i zed cal ls , bp, to 1 and vary the capaci ty requirement for non-pr ior i t ized cal ls , b„p, b y setting its value to 1, 2 and 4. The results are s imi la r to the first case, however w h e n the capaci ty requirement for non-pr ior i t ized cal ls , bnp, increases, the discrepancy observed i n non-pr ior i t ized ca l l b l o c k i n g probabi l i t ies obtained from the proposed method increases w h i l e it decreases for the ones obtained f rom Bors t and Mi t r a ' s method. Yet , Bors t and M i t r a ' s method s t i l l approximates better than the proposed method on ly when both traffic loads are ve ry low. In [20] w e proposed a c losed form approximat ion method, effective duration time, to evaluate ca l l b l o c k i n g performance i n cel lular networks under homogeneous traffic. The method provides accurate results, but the results are sensitive to the average values o f channel occupancy t imes. W e use the f o l l o w i n g set o f parameters to compare the performance o f this method to the proposed state space decomposition method's to observe i f it is more sensitive than the p rev ious ly proposed method under homogeneous traffic: C = 32, m = 28, X„p = 0.1, \lp-np = 200, \lpp = 50, bp = bnp = 1 and Xp is var ied f rom 1 to 0.05. Figs . 3.17 and 3.18 depict the pr io r i t i zed and non-pr ior i t ized ca l l b l o c k i n g probabil i t ies , respectively, under different p r io r i t i zed ca l l traffic loads. W h e n c a l l traffic load is var ied b y changing the value o f c a l l arr ival rates we observe that both methods s l igh t ly overestimate the pr ior i t i zed c a l l b l o c k i n g probabi l i ty when pp < pnp whereas the results obtained from both approximat ion methods match the results obtained f rom the direct numer ica l method very w e l l when pp > pnp. The state space decomposition method underestimates the non-pr ior i t ized ca l l b l o c k i n g p robab i l i ty w h i l e the effective duration time method provides results that match w e l l w i t h the exact solutions. O n the other hand, w h e n we keep the set o f parameters g iven above the same but set Xp to 0.5 and vary the c a l l traffic load b y changing the value o f average channel occupancy times, \lpLp, f rom 5 to 100, w e observe that the results obtained f rom both approximat ion methods matched the ones obtained b y the direct numer ica l method ve ry w e l l when pp > pnp whereas the effective durat ion t ime method degenerates s l igh t ly compared to the previous results g iven above w h e n pp < pnp. F igs . 3.19 and 3.20 show the ca l l b l o c k i n g probabil i t ies for 56 pr ior i t ized and non-pr io r i t i zed calls , respectively. W e observe that the state space decomposition method is indifferent to changes i n average channel occupancy times as opposed to the effective duration time method. Computa t iona l ly efficient approximat ion methods for evaluat ing ca l l admiss ion control schemes are studied to replace methods such as the direct w h i c h provides exact solutions b y s o l v i n g large sets o f f low equations. Product fo rm solutions are preferable due to their computat ional eff ic iency; however it is very diff icult to f ind one to evaluate asymmetric ca l l admiss ion control schemes. Cons ide r ing that state space decomposition method is iterative, we need to compare it w i t h the direct and other w i d e l y used iterative methods such as the method o f Jacobi, method o f Gauss-Seidel and method o f Borst-Mitra w i t h respect to runtime computat ional cost to emphasize its benefits. W e choose the parameters "CPU time" and "used memory" to compare the computat ional efficiencies o f the numer ica l and the approximat ion methods. W e define "CPU time" as the total process ing t ime ( in seconds) a C P U spends f rom the t ime that the computat ion is started for each method arid the "used memory" as the amount o f storage allocated for nonzero matr ix elements. W e use the f o l l o w i n g set o f parameters to obtain the numer ica l results presented i n Table 3.1 by evaluating an asymmetr ic C A C scheme, cutoff priori ty, for three different scenarios: C = 6, m = 5, Xnp = 0.02, C = 32, m = 28, Xnp = 0.1, C = 64, m = 56, Xnp = 0.5, w h i l e l//unp = 200, Xljip = 50, bp = bnp = 1 and Xp varies f rom 0.2 to 0.01, 1 to 0.05 and 5 to 0.25, respectively. The parameters are chosen to obtain s imi la r values o f ca l l b l o c k i n g probabil i t ies for both classes o f cal ls i n a l l three scenarios to make the comparisons appropriate. The s imula t ion results g iven i n Table 3.1 show that the CPU times and the used memory obtained f rom our approximat ion method is almost negl ig ib le w h e n compared w i t h the ones obtained f rom the direct numer ica l solut ion, method o f Jacobi and method o f Gauss-Seidel especia l ly w h e n the number o f channels i n the system increases. Th is is not surprising even though the proposed approximat ion method is iterative, since one dimensional M a r k o v cha in models w i t h c losed form formula solutions for each ca l l type are u t i l i zed to estimate the steady state probabil i t ies . Nevertheless the values o f the admission probabil i t ies for the pr ior i t i zed , kj, and the non-pr ior i t ized, hr, cal ls converge fast. B o t h the method o f state space decomposition and Borst-Mitra perform s imi la r to a closed form formula solut ion w i t h respect to CPU times and used memory g iven i n Table 3.1. The latter 57 computes the solu t ion faster us ing less m e m o r y compared to the former, however the proposed method approximates more accurately compared to the latter despite the insignif icant rise i n computat ional cost. 3.5 Summary In this chapter w e have class i f ied ca l l admiss ion control schemes into two categories; symmetric and asymmetric. W e obtained a product form exact so lu t ion fo rmula to evaluate symmetric c a l l admiss ion control schemes i n mul t i -service networks i n section 3.2 and proposed a nove l computa t iona l ly efficient approximat ion method that uses an iterative approach to evaluate the c a l l b l o c k i n g performance o f asymmetr ic ca l l admiss ion control schemes i n mul t i - serv ice networks i n section 3.3. W e compared the numer ica l results obtained f rom the proposed approximat ion method, state space decomposition, w i t h the ones obtained f rom a p rev ious ly proposed approximat ion method b y Bors t and M i t r a and the numer ica l method, direct, w h i c h provides the exact solut ion. W e showed that the total processing t ime a C P U spends to compute the solut ion and the amount o f storage allocated dur ing this computa t ion are almost negl ig ible when the proposed approx imat ion method is compared w i t h the exis t ing numer ica l methods ' such as direct, method o f Jacobi and method o f Gauss-Seidel. N u m e r i c a l results showed that the proposed method provides results that match better w i t h the exact solutions compared to the ones p rov ided b y the method o f Borst-Mitra w h i l e keeping the computat ional cost low. D e c o m p o s i n g the w h o l e state space into subspaces and fo rming supernodes to apply one d imensional M a r k o v cha in m o d e l i n g to use its c losed form formulas i terat ively make our proposed approximat ion method have comparat ively l o w C P U times and m e m o r y usage w i t h respect to those obtained f rom single c losed form formula solutions. M a n y dynamic ca l l admiss ion control schemes have been proposed to m a x i m i z e the network u t i l i za t ion . These dynamic schemes help networks to accept more calls w i t h l o w priorit ies b y adapt ively reserving the amount o f resources needed for cal ls w i t h h igh priori t ies. H o w e v e r the accuracy o f adaptive reservation depends on the qual i ty and up-to-dateness o f the feedback received dur ing real t ime applicat ions. Thus the challenge is to provide this feedback to the ca l l admiss ion control mechan i sm i n real t ime. Cons ide r ing 58 the h igh computat ional cost o f the exis t ing numer ica l solut ion methods, f ind ing performance evaluation approximat ion methods w i t h l o w computat ional cost is inevitable i f these dynamic ca l l admiss ion control schemes are go ing to be implemented i n ce l lu lar networks. We bel ieve that p rov id ing easy to implement performance evaluat ion approximat ion methods w i t h l o w computat ional cost w i l l help motivate the practical implementa t ion o f dynamic ca l l admiss ion control schemes. 59 (aVl"AJ {<Xbp{(C-m)/bJ (0,bpi(C-m)/bp\+\)) ( O A I ^ J M»/U*,) (VkUVkU k{"ibJb„{(C-m)lbJ F i g . 3.1 Trans i t ion d iagram for asymmetric c a l l admiss ion control schemes w i t h supernodes for p r io r i t i zed cal ls . (0,b„{,rfbj {0,bp{(C-m)jbJ (0,bpi(C-m)/bp\+\)) (ftVL^J F i g . 3.2 Trans i t ion d iagram for asymmetric c a l l admiss ion control schemes w i t h supernodes for non-pr ior i t i zed cal ls . 60 xpk0 xpk, VMf„KK VM^vk) AP'kc-lc/bP\bpybp F i g . 3.3 One d imens iona l M a r k o v chain mode l obtained for the p r io r i t i zed ca l l s ' supernodi KP 2KP 3M'V CM'„p / [m/b„pi- 6 F i g . 3.4 One d imens iona l M a r k o v chain mode l obtained for the non-pr ior i t i zed ca l l s ' supernodes. 61 i : : : : : : : : ^ . : : : : : : ; : : : : : : : : : : : : : : : : : : ; : : : : : : : : ^ Direct method ^ ; : I I Borst-Mitra method : • - A - Proposed method 10-'l 1 ' i i i 1 i ' i i 0 5 10 15 20 25 30 35 40 45 50 Prioritized call traffic load F i g . 3.5 P r io r i t i z ed ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp=\,b„pz=\, and m = 24. -*-• Direct method Borst - Mltra method Proposed method 1 0-2i 1 i i i i 1 1 1 i i ' i 0 5 10 15 20 25 30 35 40 45 50 Prioritized call traffic load F i g . 3.6 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp=\,b„p=\, andm = 24. 62 10" D i r e c t m e t h o d B o r s t - M l t r a m e t h o d ' P r o p o s e d m e t h o d 0 5 10 15 2 0 2 5 3 0 3 5 4 0 4 5 5 0 Pr ior i t i zed cal l traffic l o a d F i g . 3.7 P r io r i t i z ed ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 2, bnp = 1, and m = 24. 10 15 2 0 2 5 3 0 3 5 Pr ior i t i zed call traffic l o a d F i g . 3.8 N o n - p r i o r i t i z e d ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 2, bnp = 1, and m = 24. 63 10" - * H Direct method Borst - Mltra method - A - Proposed method 10 15 20 25 30 Prioritized call traffic load 35 40 45 50 F i g . 3.9 P r io r i t i z ed ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 4, bnp = 1, and m = 24. 15 20 25 30 35 Prioritized call traffic load F i g . 3.10 N o n - p r i o r i t i z e d ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 4,b„p-\, and m = 24. 64 10 10 '5 10" Q. •s 10" 8 m 10" 10" D i r e c t m e t h o d - B o r s t - M i t r a m e t h o d - P r o p o s e d m e t h o d 10 15 20 25 30 Prioritized call traffic load 35 40 45 50 F i g . 3.11 P r io r i t i z ed ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 1, and m = 28. 10" D i r e c t m e t h o d B o r s t - M t t r a m e t h o d - A - P r o p o s e d m e t h o d 10 15 20 25 30 Prioritized call traffic load 35 40 45 50 F i g . 3.12 N o n - p r i o r i t i z e d ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 1, and m = 28 . 65 10 Direct method Borst - Mltra method -A~ Proposed method 10 15 20 25 30 Prioritized call traffic load 35 40 45 50 F i g . 3.13 P r io r i t i z ed ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp= 1, bnp = 2, and m = 28. F i g . 3.14 N o n - p r i o r i t i z e d ca l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = \,bnp = 2, and m = 28. 66 10° 3 ID-'S aa ot J 10" 8 m 10" Direct method - O - Borst - Mitra method - A - Proposed method 10 15 20 25 30 Prioritized call traffic load 35 40 45 50 F i g . 3.15 P r io r i t i z ed ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp= \ ,bnp = 4, and m = 28 . 10 8 C O 10 10" Direct method Borst - Mltra method - A - Proposed method 10 15 20 25 30 Prioritized call traffic load 35 40 45 50 F i g . 3.16 N o n - p r i o r i t i z e d ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 4, and m = 28 . 67 10 Direct Method, b = bn =1 -r?-. Effective duration time, b =b =1 P np ^y. Proposed method, b = b =1 10 15 20 25 30 Prioritized call traffic load 35 40 45 50 F i g . 3.17 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = bnp =l,p„p = 20, pp = 2.5 to 50, Xp = 0.05 to 1. 10" 10 10 Direct Method, b = b =1 P np •V- Effective duration time, bp = b n p = 1 Proposed method, bo = b p p = 1 10 15 20 25 30 Prioritized call traffic load 35 40 45 50 F i g . 3.18 N o n - p r i o r i t i z e d ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = bnp= 1, pnp = 20, pp = 2.5 to 50, Xp = 0.05 to 1. 68 - * - Direct Method, b = b Effective duration time' b =b Proposed method, b = bn n = f 10 15 20 25 30 Prioritized call traffic load 35 40 45 50 F i g . 3.19 P r io r i t i z ed ca l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = bnp = 1, pnp = 20, pp = 2.5 to 50, \lp.p - 5 to 100. C O \ / • 6 \ —*— Direct Method *?-• Effeclive duralion time •O- Proposed method ! l I i I i 1 I i ' I I I 0 5 10 15 20 25 30 35 40 45 50 Prioritized call traffic load F i g . 3.20 N o n - p r i o r i t i z e d ca l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bP = b„p =\,pnP = 20,p p = 2.5 to 50, \lpp = 5 to 100. 69 T A B L E 3.1 C o m p a r i s o n o f runt ime computat ional costs between the proposed approximat ion method and the Borst-Mitra, direct and iterative methods Total number of channels = C, total number of shared channels = m C = 6, m = 5 C = 32, m = 28 C=64, m = 56 Numerical Methods CPU time used memory CPU time used memory CPU time used memory Direct Method 0.07s 3.82e+03 30.74s 152e+04 49m8s 222.52e+05 Method of Jacobi 0.25s 2.46e+03 29.96s 91.6e+04 llm24s 133.64e+05 Method of Gauss-Seidel 0.18s 2.46e+03 lm46s 91.6e+04 Ih33m24s 133.64e+05 Borst - Mitra Method 0.003s 0.12e+03 0.02s 0.05e+04 0.033s 0.011e+05 Proposed method 0.006s 0.13e+03 0.04s 0.14e+04 0.45s 0.046e+05 70 3 . 6 B i b l i o g r a p h y [I] L . Huang , S. K u m a r , and C . C . J . K u o , "Adap t ive resource a l locat ion for mul t imed ia services i n wireless communica t ion networks ," 21s' International Conference on Distributed Computing Systems Workshop (ICDCSW '01), pp. 307-312, 2001 . [2] D . H o n g and S. S. Rappaport , "Traff ic mode l and performance analysis for cel lular mob i l e radiotelephone systems w i t h p r io r i t i zed and non-pr ior i t ized handoff procedures," IEEE Transactions on Vehicular Technology, v o l . 35, pp. 77-92, A u g . 1986. [3] B . L i , C . L i n , and S. T. Chanson , " A n a l y s i s o f a h y b r i d cutoff p r ior i ty scheme for mul t ip le classes o f traffic i n mu l t imed ia wireless ne tworks ," Wireless Networks, v o l . 4, no. 4, pp. 279-290, J u l y 1998. [4] Y . B . L i n , S. M o h a n , and A . Noerpe l , " Q u e u i n g pr ior i ty channel assignment strategies for handoff and in i t i a l access for a P C S network," IEEE Transactions on Vehicular Technology, v o l . 43 , no. 3, pp. 704-712, A u g . 1994. [5] J . Y . L e e , and S. B a h k , " S i m p l e admiss ion control schemes support ing Q o S i n wireless mul t imed ia ne tworks ," IEE Electronics Letters, v o l . 37, no. 11, pp. 712-713, M a y 2001. [6] R . Ramjee, R . Nagarajan, and D . Towsley, " O n op t imal c a l l admiss ion control i n cel lular ne tworks ," Wireless Networks, v o l . 3, no. 1, pp. 29-41 , M a r c h 1997. [7] Y . Fang , and Y . Zhang , " C a l l admiss ion control schemes and performance analysis i n wireless m o b i l e ne tworks ," IEEE Transactions on Vehicular Technology, v o l . 51, no.2, pp. 371-382, M a r c h 2002. [8] M . D . Kulavaratharasah, and A . H . A g h v a m i , "Teletraffic performance evaluation o f m i c r o c e l l personal communica t ion networks ( P C N s ) w i t h p r io r i t i zed handoff procedures," IEEE Transactions on Vehicular Technology, v o l . 48 , no. 1, pp. 137-152, Jan. 1999. [9] A . S. A c a m p o r a and M . Naghshineh , " C o n t r o l and qual i ty o f service p rov i s ion ing i n high-speed mic ro -ce l lu l a r networks ," IEEE Personal Communications, v o l . 1, no. 2, pp. 36-43, 1996. [10] M . Naghsh ineh and S. Schwar tz , "Dis t r ibuted ca l l admiss ion control i n mobi le /wire less networks," IEEE Journal on Selected Areas in Communications, v o l . 14, no. 4, pp. 711-717, M a y 1996. [ I I ] D . L e v i n e , I. A k y i l d i z , and M . Naghshineh , " A resource est imation and ca l l admiss ion a lgor i thm for wireless mu l t imed ia networks us ing the shadow cluster concept," IEEE/ACM Transactions on Networking, v o l . 5, no. 1, pp. 1-12, Feb . 1997. 71 [12] A . Su t ivong and J . M . Peha, " N o v e l heuristics for c a l l admiss ion control i n cel lular systems," 1997 IEEE 6th International Conference on Universal Personal Communications Record, v o l . 1, pp. 129-133, Oct . 1997. [13] C . O l i v e i r a , J . B . K i m , and T. Suda, " A n adaptive bandwid th reservation scheme for high-speed m u l t i m e d i a wireless networks," IEEE Journal on Selected Areas in Communications, v o l . 16, pp. 858-874, A u g . 1998. [14] P. Ramanathan, K . M . S iva l ingam, P. A g r a w a l , and S. K i s h o r e , " D y n a m i c resource a l locat ion schemes dur ing handoff for mob i l e m u l t i m e d i a wireless networks," IEEE Journal on Selected Areas in Communications, v o l . 17, no. 7, pp. 1270-1283, Ju ly 1999. [15] R . G u e r i n , "Equ iva len t capacity and its appl ica t ion to bandwid th a l locat ion i n high-speed ne tworks ," IEEE Journal on Selected Areas in Communications, v o l . 9, no. 7, pp. 968-981, Sept. 1991. [16] J . S. Evans and D . Everi t t , "Effect ive bandwidth-based admiss ion control for mul t i -service C D M A cel lu lar networks," IEEE Transactions on Vehicular Technology, v o l . 48, no. 1, Jan. 1999. [17] Q . R e n and G. Ramamurthy, " A real-time dynamic connect ion admiss ion controller based on traffic mode l ing , measurement, and fuzzy log ic con t ro l , " IEEE Journal on Selected Areas in Communications, v o l . 18, no. 2, Feb . 2000. [18] Y . Fang and I. Ch lamtac , "Teletraffic analysis and m o b i l i t y mode l i ng for P C S networks ," IEEE Transactions on Communications, v o l . 47, pp. 1062-1072, Ju ly 1999. [19] Y . Fang , I. Chlamtac , and Y . B . L i n , "Channe l occupancy t imes and handoff rate for mob i l e comput ing and P C S networks," IEEE Transactions on Computers, v o l . 47, pp. 679-692, June 1998. [20] E . A . Y a v u z and V . C . M . Leung , "Computa t iona l ly efficient method to evaluate the performance o f guard-channel-based ca l l admiss ion control i n ce l lu lar networks," IEEE Transactions on Vehicular Technology, v o l . 55, no. 4, pp. 1412-1424, Ju ly 2006. [21] S. S. Rappaport , "The mul t ip le ca l l handoff p r o b l e m i n personal communicat ions networks," IEEE 40th Vehicular Technology Conference, pp. 2 8 7 - 2 9 4 , M a y 1990. [22] S. S. Rappaport and G. M o n t e , " B l o c k i n g , hand-off and traffic performance for cel lular communica t ion systems w i t h m i x e d platforms," IEEE 42" Vehicular Technology Conference, v o l . 2, pp. 1018-1021 , M a y 1992. [23] W . L i and X . C h a o , " M o d e l i n g and performance evaluat ion o f a cel lu lar mob i l e network," IEEE/ACM Transactions on Networking, v o l . 12, no. 1, Feb . 2004. [24] A . Gersht and K . J . Lee , " A bandwidth management strategy i n A T M networks," Technica l report, G T E Laboratories, 1990. 72 [25] J . W . Roberts , "Teletraffic models for the Te lecom 1 integrated services network," Proceedings of the 10th International Teletraffic Conference, M o n t r e a l , 1983. [26] S. C . Bors t and D . M i t r a , " V i r t u a l par t i t ioning for robust resource sharing: computat ional techniques for heterogeneous traffic," IEEE Journal on Selected Areas in Communications, v o l . 16, no. 5, pp. 668-678, June 1998. [27] K . W . Ross , M u l t i - s e r v i c e L o s s M o d e l s for Broadband Te lecommunica t ion Ne tworks . L o n d o n : Spr inger-Ver lag , 1995, chapter 3. [28] W . J . Stewart, Introduction to the N u m e r i c a l So lu t ion o f M a r k o v Chains . Pr inceton U n i v e r s i t y Press, Pr inceton, N e w Jersey, 1994. 73 C H A P T E R 4 PROBABILITY DISTRIBUTION OF CHANNEL OCCUPANCY TIMES AND NUMBER OF USER HANDOFF IN CELLULAR NETWORKS3 4.1 Introduction The evolu t ion o f cel lu lar networks has been accompanied not o n l y b y voice but also by the development, growth, and use o f a wide variety o f network applications. Packet-switched services are gradual ly integrated w i t h the convent ional c i rcui t -swi tched ones such as vo ice to accommodate network applications that range f rom text-based util i t ies such as S M S messaging, f i le transfer, remote l og in and electronic m a i l to M M S messaging, videoconferencing, m u l t i m e d i a streaming, web surfing and electronic commerce. The advantage o f h a v i n g packet-switched data services over la id on c i rcui t - swi tched technology over the same air interface is the ut i l iza t ion o f excess network capaci ty avai lable i n each ce l l . Statistical m u l t i p l e x i n g is used to transmit data packets over radio interface to provide a Q o S level comparable to that o f c i rcui t -swi tched services. Statist ical m u l t i p l e x i n g gain arises from the talk spurt to si lence ratio found i n speech w h i c h makes it possible to mul t ip lex more than one service on to the same radio channel . H o w e v e r accurate vo ice traffic statistics are needed to understand the length and frequency distributions o f idle periods o f cel lular channels assigned to vo i ce i n order to exploi t the statistical mu l t i p l ex ing ga in i n cel lu lar networks. Traffic statistics are important not on ly for statistical m u l t i p l e x i n g and thus network management but also for performance evaluat ion i n communica t i on networks, b i l l i n g , op t imiza t ion and a l locat ion o f safety buffers. These statistics simulate network traffic when evaluating networks us ing mathematical models . C a l l h o l d i n g and channel occupancy times are two o f these traffic statistics that are needed to compute performance metrics such as ca l l b lock ing /d ropp ing probabi l i t ies . Call holding time is defined as the durat ion o f requested ca l l connect ion w h i c h corresponds to ho ld ing t ime for a w i r e d phone ca l l or session t ime i n a computer system, whereas channel occupancy time is defined as the t ime that a mob i l e 3 A version of this chapter has been accepted for publication. E. A. Yavuz and V. C. M . Leung, "Modeling Channel Occupancy Times for Voice Traffic in Cellular Networks," IEEE ICC 2007, Glasgow, Scotland, June 2007. 74 occupies channel(s) w i t h i n a ce l l dur ing its residence i n the ce l l . In the literature, wireless network traffic has been approximated based on wi re l ine traffic statistics where ca l l ho ld ing times are general ly considered to be exponent ia l ly distributed. H o n g and Rappaport [1] proposed a traffic m o d e l for ce l lu lar mob i l e radio telephone systems and showed that channel occupancy t ime dis t r ibut ion can be approximated by exponential dis t r ibut ion o n l y when ca l l ho ld ing times are exponent ia l ly distributed. In the literature ce l lu lar networks have been mos t ly evaluated under this assumption due to its tractability. Ramjee et al. [2], Fang and Zhang [3], Naghsh ineh and Schwar tz [4], Gersht and L e e [5], Bors t and M i t r a [6] and Y a v u z and L e u n g [7] studied performance o f various ca l l admiss ion control schemes us ing one d imensional M a r k o v cha in models assuming that channel occupancy times are exponent ial ly distributed. In [8], Rappaport developed mul t id imens iona l models under the same assumption and w i t h M o n t e , the author obtained ca l l b l o c k i n g probabi l i t ies us ing this mode l [9]. H o w e v e r s imula t ion studies and f ie ld data have shown that these assumptions are not perpetually v a l i d . G u e r i n [10] used a s imula t ion mode l to show that channel occupancy time distr ibution displays a rather poor agreement w i t h the exponent ial f i t t ing for mob i l e users w i t h l o w change rate o f movement direct ion. J ed rzyck i and L e u n g showed i n [11] that exponential d is t r ibut ion assumption for channel occupancy t imes is not correct and a lognormal m o d e l approximat ion fits m u c h better us ing real ce l lu lar data. In [12] and [13], Fang et al. demonstrated that channel occupancy times i n a ce l lu lar network depend not on ly on ca l l ho ld ing t imes but also on users' m o b i l i t y w h i c h can be characterized by ce l l residence t ime distr ibut ion. The authors showed i n [14] that channel occupancy t ime is exponential ly distributed o n l y i f c e l l residence t ime is exponent ia l ly distributed. H o w e v e r it is also observed i n the same study that channel occupancy t ime dis t r ibut ion have a good approximat ion b y exponent ial dis t r ibut ion i n general w h e n the m o b i l i t y is low. In [15], Barce lo and Jordan analyzed a ce l lu lar network based on a fu l ly empi r i ca l approach and observed that channel occupancy is less spread out than i f exponential distr ibution was assumed. In this chapter, w e present an analysis o f real traffic data obtained f rom a number o f ce l l sites i n B e l l M o b i l i t y Canada 's ce l lu lar network. S i m i l a r to the empi r i ca l study presented i n [11], we obtain the probabi l i ty distributions for channel occupancy times however we classify them accord ing to their occupancy types to perform goodness-of-fit tests for each 75 type o f channel occupancy t imes and users. In order to facilitate this c lass i f icat ion, we br ief ly review the l ife cyc l e o f a typ ica l ce l lu lar ca l l first. In a cel lu lar network, the service area is covered b y base stations whose radio coverage defines the corresponding ce l l . E a c h base station is assigned a set o f mob i l e users. W h e n a new ca l l is originated b y a mob i l e user in a ce l l , one o f the channels assigned to the base station is used for communica t ion between that mobi le user and the base station i f a channel is available. I f a channel can be assigned to a ca l l , it w i l l be kept un t i l the c a l l is completed or the user moves out o f the corresponding ce l l . W h e n the user moves into a new ce l l w h i l e hav ing an active c a l l , a new channel needs to be acquired i n the new c e l l us ing a "handoff procedure." W e name the amount o f t ime that a ca l l occupies any channel dur ing its ho ld ing t ime total regardless o f be ing started i n a ce l l and completed i n the same c e l l or handoff to another. W e classify channel occupancy times based on the f o l l o w i n g occupancy type characteristics: channels occup ied b y calls that are started and comple ted i n the same ce l l (new2same). channels occup ied by calls that are started i n a c e l l but handed o f f to a ne ighbor ing c e l l (new2ho). channels occup ied b y cal ls that are started i n a c e l l and either completed i n the same ce l l or handed o f f to a ne ighbor ing ce l l (new2sameorho). Th i s type o f channel occupancy is ve ry important for M a r k o v cha in mode l ing o f cel lular networks and class i f ied as "new ca l l s " i n the models . channels occup ied b y cal ls that are handed o f f to a ce l l and completed i n that ce l l (ho2same). channels occup ied b y cal ls that are handed o f f to a ce l l but handed o f f once more before comple ted (ho2ho). channels occup ied b y cal ls that are handed o f f to a c e l l and either completed i n that ce l l or handed o f f once more before comple ted (ho2sameorho). Th is type o f channel occupancy is ve ry important for M a r k o v chain mode l ing o f cel lular networks and class i f ied as "handoff ca l l s " i n the models . The benefits o f good knowledge about various types o f channel occupancy times are 76 bas ica l ly twofo ld . 1. A n a l y t i c a l models are developed us ing M a r k o v cha in mode l ing to evaluate performance i n ce l lu lar networks. W h e n a c a l l admiss ion control scheme is mode led for each c e l l i n a cel lular network, a r r iv ing cal ls to a part icular ce l l are grouped into Q o S classes or ca l l types, such as new and handoff, based on their first appearance i n the corresponding ce l l . Channe l occupancy time distr ibution for each Q o S class or ca l l type includes respective channel occupancy times counted o n l y un t i l the corresponding calls d iscard the occupied channels i n the ce l l due to c a l l terminat ion or handoff. C a l l h o l d i n g t ime dis tr ibut ion, on the other hand, includes the amount o f times that the channels are occup ied b y a ca l l unt i l it terminates either i n its or iginat ing ce l l or another. The results presented i n this paper are useful for p r o v i d i n g sufficiently representative channel occupancy time statistics to develop analyt ical models since ca l l h o l d i n g t ime statistics are not sufficient alone. 2. S i m u l a t i o n provides a second approach towards ne twork performance evaluation b y b u i l d i n g a mathematical mode l o f the ne twork to analyze its behavior as t ime progresses. T h e results presented i n this chapter are very useful for feeding s imulat ions w i t h realistic traffic statistics to obtain network performance metrics. Th i s chapter is organized as fo l lows. In Sect ion 4.2, w e exp la in the data acquis i t ion method that w e use to obtain statistics for various types o f channel occupancy times and discuss system related anomalies that w e observe. Sec t ion 4.3 consists o f the candidate distributions that w e propose to represent the empi r i ca l data set, the statistical tools, parameter est imation techniques and goodness-of-fit tests u t i l i zed i n the study. In Sect ion 4.4, we present the statistical results obtained from the goodness-of-fit tests performed for each aforementioned type o f channel occupancy times a long w i t h the observed data histograms and fitted distr ibutions. W e examine h o w mode l ing ca l l h o l d i n g t imes w i t h the best fi t t ing candidate dis t r ibut ion w o u l d impact performance metrics such as c a l l b l o c k i n g probabil i t ies instead o f m o d e l i n g w i t h the t radi t ional ly accepted exponential dis t r ibut ion. W e provide the statistical results obtained f rom the goodness-of-fit tests performed for channel occupancy 77 and ca l l h o l d i n g t ime distr ibutions for stationary and mob i l e users. F i n a l l y we present the statistical results obtained f rom the goodness-of-fit test performed to fit the distr ibution o f the number o f handoffs commi t t ed b y a user to a candidate dis t r ibut ion. W e w i l l conclude the chapter i n Sec t ion 4.5. 4.2 Data Acquisition and System-Related Anomalies In this chapter, w e analyze cel lu lar ca l l data obtained f rom the C D M A system deployed b y B e l l M o b i l i t y i n Ontar io , Canada. In B e l l ' s C D M A system a c a l l can be i n up to 6 w a y soft/softer handoff at anytime. H o w e v e r c a l l handoffs have been mode led differently i n the literature i n t radi t ional mathematical and s imula t ion ne twork models developed for evaluating performance i n ce l lu lar networks: a ca l l is t radi t ional ly assumed to communicate v i a one p r imary sector at any g iven t ime unless it is i n handoff. In the empi r i ca l data set, we obtain the values o f EJI0, ratio o f the p i lo t s ignal energy to the total power i n the channel, for each active c a l l b y observ ing the corresponding " N e i g h b o r L i s t T u n i n g Data A r r a y " messages to determine a cal l ' s p r imary sector. A n example o f a " N e i g h b o r L i s t Tun ing Data A r r a y " message is g iven i n Table 4 .1 . F o r a ca l l at any g iven t ime, we take the sector w h i c h the ca l l has the highest EJI0 value i n its active set as the p r imary sector o f that ca l l for that particular t ime. W e compute EJI0 value o f a ca l l i n a sector b y d i v i d i n g the value o f cal l ' s "p i lo t strength" g iven for that sector i n the "Ne ighbor L i s t T u n i n g Da ta A r r a y " message b y -2. F o r example for the sample message g iven i n Table 4.1, EJI0 value o f the active ca l l is equal to -12 for its p r imary sector where the corresponding "p i lo t strength" is equal to 24. W e assume that handoffs are technology independent w h i c h happen at the equal power boundaries. W e use the "Ne ighbor L i s t T u n i n g Da ta A r r a y " messages to detect the commit ted handoffs b y observ ing a cal l ' s p r imary sector be ing replaced b y other sectors that have the highest EJI0 value i n the corresponding ca l l ' s active set at the t ime o f observation. We take an ent irely empi r i ca l approach i n this w o r k based on true data col lected f rom actual w o r k i n g systems. H o w e v e r un l ike analyt ical and s imula t ion approaches, the empir ica l approach depends on the environment and therefore m a y conta in system related anomalies. The results presented i n this paper might have been different i f taken i n a different place, t ime etc. W e bel ieve that a l l approaches are complementary and have more or less advantages or disadvantages depending on the specific appl icat ion. F igs . 4.1 to 4.7 depict the distr ibution o f 78 channel occupancy t imes c lass i f ied as new2same, new2ho, new2sameorho, ho2same, ho2ho, ho2sameorho and total respectively. U p o n close inspect ion o f the distr ibutions g iven i n F igs . 4.1 to 4.7, w e observe two sorts o f anomalies: unusual ly h igh number o f short channel occupancy t imes and spikes. The unexpected behavior o f channel occupancy times classif ied as ho2ho (see F i g . 4.5) and ho2sameorho (see F i g . 4.6) are due to the "p i lo t p o l l u t i o n " i n the data set since several p i lo t signals are observed to be close to the "add-drop" thresholds and thus come i n and get out o f their active sets frequently (no dominant p r imary sector). The unexpected behavior o f the channel occupancy times c lass i f ied as new2same (see F i g . 4.1), new2sameorho (see F i g . 4.3) and total (see F i g . 4.7) is s imi l a r to what is observed b y B o l o t i n i n [16]. The author categorized the observed short channel occupancy times into four different classes i n order o f increasing average times [16]: various abandonment before the connect ion over the network is established, ou tgoing cal ls that encounter busy condi t ion and therefore be ing abandoned by the caller. outgoing cal ls that encounter no answer condi t ion and therefore be ing abandoned by the caller. ou tgoing cal ls that encounter a busy or no answer cond i t ion and therefore fo l l owed b y a vo ice m a i l message left b y the caller. Second type o f anomaly is the spikes that we observe w i t h i n channel occupancy time samples c lass i f ied as new2same around 16 t h second and ho2ho around 4 t h second. The former can be expla ined due to cal ls that encounter no answer and therefore go to voice m a i l wh i l e the latter can be expla ined due to "immediate handoff candidatecy". The spikes observed around 16 t h second w i t h i n channel occupancy t ime samples c lass i f ied as new2sameorho and total and the spikes observed around 4 t h second w i t h i n channel occupancy t ime samples classif ied as ho2sameorho are due to same samples that created the spikes w i t h i n channel occupancy t ime samples c lass i f ied as new2same and ho2ho, respectively. 79 4.3 Statistical Methods 4.3.1 C a n d i d a t e P r o b a b i l i t y D i s t r i b u t i o n s W e choose the f o l l o w i n g theoretical dis t r ibut ion models that can reasonably represent the observed empi r i ca l distr ibutions before car ry ing out the f i t t ing estimations. W e propose a list o f candidate theoretical continuous distributions and describe their properties a long w i t h examples o f processes for w h i c h they can serve as models . The list o f the proposed candidate distributions is g iven b e l o w a long w i t h the m a i n statistics p rov ided i n the A p p e n d i x . 1. Exponential Distribution: Th i s dis tr ibut ion is often used to mode l the t ime between events that happen at a constant average rate. It is the on ly continuous memoryless p robabi l i ty distr ibution and thus h i g h l y appreciated for achieving analyt ical results i n M a r k o v processes, m a k i n g it easier to analyt ica l ly solve systems i n v o l v i n g queues. The exponential dis t r ibut ion plays a strong role i n the theory o f congest ion systems and mode l ing processes such as duration o f t radit ional phone cal ls , the t ime between failures o f certain types o f electronic devices, and the t ime between interrupts received b y a C P U i n a computer system. 2. Lognormal Distribution: The lognormal dis t r ibut ion is the probabi l i ty distr ibution o f any random variable whose logar i thm is no rma l ly distributed. A variable might be mode led as lognormal i f it can be thought o f the product o f many smal l independent pos i t ive variables. A typica l example is m o d e l i n g the t ime unt i l a system fails or the t ime to perform manual tasks such as assembly, inspection or repair. 3. Gamma Distribution: The gamma distr ibut ion is a continuous dis tr ibut ion that is often used to m o d e l the average l i fet ime or the sum o f l ifet imes o f various items that have exponent ial l i fet imes. It describes the t ime un t i l n consecutive rare random events occur i n a process w i t h no memory. It is a popular candidate for m o d e l i n g processes such as the t ime to perform a manual task and the C P U time a j o b requires due to its ab i l i ty to assume many shapes. The exponential distr ibution and the E r l a n g distr ibut ion, w h i c h can be expressed as the sum o f independent 80 exponent ia l distr ibutions, are the two important special cases o f the gamma dis t r ibut ion. 4. Weibull Distribution: Th i s distr ibution is often used i n re l i ab i l i ty analysis due to its versat i l i ty to m o d e l the dis tr ibut ion o f t ime un t i l failure. In part icular every exponent ia l dis t r ibut ion is also a W e i b u l l d is t r ibut ion since a W e i b u l l distr ibution is defined b y m o d i f y i n g the constant event occurrence rate o f an exponential d is t r ibut ion to make it t ime dependent. Other distr ibutions such as Beta , Po i s son or Pareto are not proposed as candidate distributions i n this study due to l ack o f theoretical and empi r i ca l cr i ter ia to support them as candidates. 4.3.2 P a r a m e t e r E s t i m a t i o n Once the candidate distributions are proposed, we need the parameters for each dis tr ibut ion estimated f rom the empi r ica l data set. There are m a n y methods to estimate a particular parameter o f a g iven dis tr ibut ion such as probabi l i ty plot t ing, method o f moments and m a x i m u m l i k e l i h o o d estimation. A probability plot is a graphical compar ison o f an empi r ica l d is t r ibut ion w i t h that o f a candidate distr ibut ion. The method of moments consists o f equating the first few moments obtained from an empi r i ca l data set w i t h the corresponding moments o f a candidate dis t r ibut ion to solve the number o f equations that match w i t h the number o f u n k n o w n parameters to obtain the required estimates. T h i s method usual ly yields fa i r ly s imple and consistent estimators, however the g iven estimators can be biased and inefficient. The maximum likelihood estimation ( M L E ) method consists o f obtaining parameters that m a x i m i z e the probabi l i ty o f obtaining the empi r i ca l data i n the whole sample set [17]. The pr inc ip le o f this method is to select a value as an estimate for w h i c h the observed sample is most l i k e l y to occur. In this chapter, w e use the m a x i m u m l i k e l i h o o d est imation method to obtain the required parameters since it usual ly produces consistent estimators. It is also shown to be the most efficient method under certain regulari ty condit ions w h e n the sample size approaches inf in i ty [18]. The advantage o f us ing M L E over other methods is that it gives better fit results 81 than method o f moments w h e n the goodness o f fit test is appl ied [17]. M L E captures the shape o f the empi r i ca l d is t r ibut ion m u c h better than the method o f moments since it is not t ied to the first moments o f the sample. E v e n though the method usua l ly works quite w e l l , it has some drawbacks: the estimators m a y be biased for smal l sample sizes; the method has a higher c o m p l e x i t y o f parameter computat ion; and the moments o f the empir ica l and candidate distr ibutions m a y not agree. The difference between the moments o f the candidate and empi r ica l d is t r ibut ion is slight for distributions w i t h good fit; however the system o f equations that needs to be so lved to compute the required parameters m a y not always be a c losed form solut ion or a unique solut ion m a y not even exists. 4.3.3 Goodness -o f - f i t Tests Statistical tests that determine whether a g iven theoretical p robabi l i ty distr ibution is appropriate to characterize an observed sample data set are ca l l ed goodness-of-fit tests [19]. These tests are statistical hypothesis tests that are used to assess fo rma l ly whether the observed data are independent samples from a part icular dis t r ibut ion. H o w e v e r failure to reject the n u l l hypothesis that c la ims the observed data samples to be I ID random variables w i t h a part icular d is t r ibut ion function, should not be interpreted as accepting the n u l l hypothesis as be ing true. L a w and K e l t o n noted i n [17] that these tests are often not very powerful for sma l l to moderate sample sizes and thus should be regarded as a systematic approach for detecting fa i r ly gross differences instead. Yet i f the sample size is very large, the authors observed that these tests almost always reject the n u l l hypothesis . E v e n an instant departure f rom the hypothes ized dis t r ibut ion is detected for a large sample size, since the n u l l hypothesis is v i r tua l ly never exact ly true. Therefore it is more important to f ind the theoretical d is t r ibut ion that fits the empir ica l data best even i f it m a y be rejected w i t h a "re la t ively s m a l l " marg in b y the respective goodness o f fit test. In this chapter w e are not on ly l o o k i n g for an accepted theoretical distr ibution, but also an order i n w h i c h the candidate distributions fit the empi r i ca l data set since it is usua l ly sufficient to have a dis tr ibut ion that is "near ly" correct due to its benefits such as [15]; 82 b u i l d i n g appropriate queuing models w i t h the corresponding general distributions to simulate systems since h i g h l y accurate performance metrics can also be obtained us ing approximations. exp lo i t ing id le t imes i n the traffic channels o f the m o b i l e systems for the insertion o f data on a non-preemptive basis. schedul ing the channel to be interrupted when an emergency ca l l arrives at a b l o c k e d system (to interrupt the channel w i t h the lowest expected remaining occupancy t ime or to predict the first available channel for handoff). The chi-square test is the oldest goodness-of-fit hypothesis test that can be thought o f as a more formal compar i son o f a his togram w i t h the proposed candidate probabi l i ty distr ibution. To compute the chi-square test statistic i n either continuous or discrete case, the entire range o f candidate dis t r ibut ion must be d iv ided into k adjacent intervals [to, tf), [ij, ti), ... , [tk-i, tk), where to and tk can either or both be - o o and + 0 0 , respectively. T h e n we check for 7 = 1,2, k and compute the expected proport ion pj o f the observations that w o u l d fall i n the /th interval i f we were sampl ing from the candidate probabi l i ty distr ibut ion. In the continuous case, where fc(x) is the p robab i l i ty function o f the candidate continuous dis tr ibut ion. F o r discrete data, Nj = number o f observations i n the /th interval [4-/, 4 ) (1) 83 Pj= E / r f f e ) (2) where fd(xj) is the p robab i l i ty function o f the candidate discrete dis t r ibut ion. F ina l ly , the test statistic is The test statistic is expected to be smal l i f the fit were good since npj w i l l then be the expected number o f observations that w o u l d fa l l i n the yth interval . The most troublesome aspect o f ca r ry ing a chi-square goodness o f fit test is choos ing the number and size o f the bins. Th i s is a diff icul t p r o b l e m and no definit ive prescr ipt ion can be g iven that is guaranteed to produce good results i n terms o f va l id i ty (actual l eve l o f the test close to the desired level a) and h igh power for a l l hypothes ized distributions and a l l sample sizes. Therefore the major drawback o f the chi-square test is the lack o f clear prescr ip t ion for interval selection. H o w e v e r L a w and K e l t o n suggested a few guidelines i n [17]. The authors proposed the equiprobable approach w h i c h chooses the b in intervals so that the expected proport ion o f the empir ica l data set that fa l l i n each interval w i l l be equal to each other. E v e n though this might be inconvenient to app ly to some continuous distributions since the dis t r ibut ion function o f the candidate d is t r ibut ion must be inverted, it w i l l be poss ible to make the values o f the expected propor t ion o f the empi r i ca l data set approximate ly equal for discrete distributions. It is also stated i n [17] that the chi-square test w i l l be approximate ly v a l i d i f the number o f bins is greater than 3 and the m i n i m u m number o f expected number o f observations in a b i n is 5 for equiprobable intervals. Kolmogorov-Smirnov ( K - S ) tests, on the other hand, compare an empi r ica l data set w i t h a candidate dis t r ibut ion wi thout grouping the data. Thus , no informat ion is lost when apply ing this test w h i c h eliminates the troublesome p rob lem o f interval specification. It is v a l i d for any sample size however the major drawback o f a K - S test is its range o f (3) 84 appl icabi l i ty w h i c h is more l i m i t e d than that for chi-square tests [17]. These tests are v a l i d on ly i f a l l the parameters o f the hypothesized distr ibution are k n o w n and the distr ibution is continuous, w h i c h means that the parameters cannot be estimated f rom the empi r ica l data set and even i f it w i l l ; this i n fact w i l l produce a conservative test. The K - S test statistic is the largest (vertical) distance between the empi r ica l and the candidate dis tr ibut ion function, however g i v i n g the same weight to this distance for a l l observed values is another drawback o f these tests since m a n y distributions o f interest differ p r i m a r i l y i n their tails. The Anderson-Darling ( A - D ) test is a modi f ica t ion o f the K - S test that is designed to detect these discrepancies i n the tails. It has higher power than the K - S test against many alternative distributions yet it is o n l y avai lable for a few specific distr ibutions [17]. In this study, w e use the chi-square test w h i c h remains i n wide use since it can be appl ied to any hypothes ized dis tr ibut ion w i t h parameters estimated f rom the observed data. W e perform the f o l l o w i n g steps: 1. D i v i d e the data into groups w i t h respect to occupancy types and sort it by channel occupancy t imes. T h i s w i l l let us v i sua l ly see the data dis t r ibut ion for each group w i t h a different occupancy type as a his togram. The no rma l i zed histograms for a l l channel occupancy types are shown i n F igs . 4.1 to 4.7. 2. Choose a l is t o f candidate distributions to w h i c h each group o f data w i l l be fitted and calculate the parameters for each dis t r ibut ion us ing the corresponding m a x i m u m l i k e l i h o o d estimation equations. 3. Choose the number o f bins into w h i c h each group o f data w i l l be d iv ided , calculate the expected number o f observations i n each b i n and conf i rm that it exceeds the minimum number of expected number of observations g iven i n [17]. E a c h b i n should be created to assure that its expected number o f observations is equal to that o f others created for the same candidate dis t r ibut ion be ing tested. Therefore the bins have to be recalculated every t ime a different set o f distr ibution parameters are used or a new distr ibution is tested. F o r each group o f data, the b in boundaries should satisfy 85 nPj = n • (pr{x <tj\- pr[x < t{H)})] > 5 (4) where j = 1,2, . . . k Pj is the p robab i l i ty o f a data i tem from the dis t r ibut ion that falls into b i n j , k is the number o f created bins, to, t], ... tk are the upper b i n boundaries, n is the total number o f observations i n the data set and npj is the expected number o f observations i n the /th b in . 4. D i v i d e the observed data i n each group into its corresponding created bins whose upper boundaries are g iven i n the previous step. H o w e v e r each data group should be made continuous i n advance b y spreading it evenly w i t h i n 0.5 seconds o f their discrete values since a l l candidate distributions that w e propose are continuous due to their nature. 5. Calcula te the test statistics for each data group us ing (3). 6. The n u l l hypothesis is rejected i n each case i f the value o f the test statistics calculated b y the previous step is greater than the value o f the chi-square statistics w i t h k - 1 - z degrees o f freedom, where z is the number o f parameters estimated. W e set the s ignif icance leve l o f the performed tests equal to the traditional value o f 0.95 (a = 0.05). 4.4 Numerical Results 4.4.1 Statistical Results for Channel Occupancy Times In this section, w e present the statistical results obtained f rom the goodness-of-fit tests performed for each aforementioned type o f channel occupancy t imes. The results show that 86 a l l types o f channel occupancy times resemble either lognormal or w e i b u l l distributions. H o w e v e r o n l y for two o f these, new2ho and ho2new, the candidate probabi l i ty distributions were able to pass the chi-square goodness-of-fit test w i t h l ognorma l be ing a better fit than w e i b u l l . U p o n close inspect ion o f the rest o f data histograms g iven i n F ig s . 4 .1, 4.3, 4.5, 4.6 and 4.7, we observed two sorts o f anomalies w h i c h we addressed i n section 4.2: unusual ly h igh number o f short channel occupancy times and spikes. N o n e o f these distributions fits statistically to a proposed candidate distr ibution due to the observed anomalies. Thus, f i l tering these empi r i ca l data sets is inevitable since no candidate dis t r ibut ion can otherwise be fitted to the data. A l l short channel occupancy times less than 3 seconds are discarded from the respective data sets o f channel occupancy t ime distr ibutions c lass i f ied as new2same, new2sameorho and total since most o f them are calls terminated abnormal ly due to reasons given i n section 4.2. The excess channel occupancy times observed at the 16 t h second i n the same data sets g iven above and at the 4 t h second i n the data sets o f channel occupancy time distributions c lass i f ied as ho2ho and ho2sameorho are stripped f rom the rest us ing s imple means. The test and the chi-square statistics obtained f rom the revised goodness-of-fit tests for each type o f channel occupancy are presented i n Tables 4.2 to 4.8. The n u l l hypothesis is rejected i n each case i f the value o f the test statistics is greater than the value o f the chi-square statistics. A l l significant levels are 0.95, the candidate p robab i l i ty distributions w h i c h pass the chi-square goodness o f fit test are marked w i t h a star (*) and the test statistics for the closest fitted candidate distributions g iven i n the tables are b o l d e d . F igs . 4.1 to 4.7 show the closest fitted candidate distr ibution and the fitted exponent ia l dis t r ibut ion along w i t h the no rma l i zed histograms for a l l types o f channel occupancy t imes, respectively. F igs . 4 .1 , 4.3 and 4.7 show the tradi t ional ly accepted fitted exponent ial distr ibution underestimating the short channel occupancy t imes w h i l e overest imating the rest except around 16 t h second, where unusual ly h igh number o f channel occupancy t imes is observed. H o w e v e r the closest fitted candidate distr ibution, lognormal , s l igh t ly overestimates the short channel occupancy t imes except at 16 t h second w h i l e it matches w e l l w i t h the rest. F o r channel occupancy types o f new2ho and ho2same, it is shown i n F igs . 4.2 and 4.4 that the fitted exponential d is t r ibut ion underestimates the short channel occupancy times w h i l e it 87 overestimates the rest. The closest fitted candidate dis t r ibut ion, lognormal , matches the observed dis t r ibut ion ve ry w e l l except for very short channel occupancy times w h i c h it s l ight ly overestimates. F ig s . 4.5 and 4.6 show the channel occupancy t ime distributions for types o f ho2ho and ho2sameorho. The tradi t ional ly accepted fitted exponential distr ibution underestimates the short channel occupancy times w h i l e it overestimates the rest. Yet , the closest fitted candidate dis t r ibut ion, lognormal , s l ight ly overestimates the short channel occupancy t imes except around 4 t h second w h i l e it matches w e l l w i t h the rest. W e observe i n general that lognormal d is t r ibut ion is. b y far the closest fitted dis t r ibut ion for each channel occupancy type w h e n compared w i t h other candidate distr ibutions. 4.4.2 The Effects of Traffic Remodeling on Performance Evaluation In this section, w e demonstrate h o w mode l ing c a l l h o l d i n g t imes w i t h a lognormal dis tr ibut ion w o u l d impact performance metrics such as c a l l b l o c k i n g probabi l i t ies instead o f mode l ing w i t h a t radi t ional ly accepted exponential dis t r ibut ion. Le t us assume that we are mode l ing a ce l lu lar ne twork i n a single ce l l w i t h a f ixed amount o f bandwidth capacity, C . We assume that a Po i s son process describes the arr ival o f each c a l l that requires a single channel and w h e n a l l channels are occupied, a l l a r r iv ing cal ls are assumed to be rejected and thus lost. W e can compare this mode l to an M/M/C system w i t h no queues available. First , we simulate our m o d e l us ing exponent ia l ly distributed ca l l h o l d i n g t imes w i t h various mean values (111) w i t h i n the range o f 10 sec/cal l to 120 sec/cal l that are set equal to the mean values o f a l l types o f channel occupancy times obtained f rom the empi r i ca l data set us ing the m a x i m u m l i k e l i h o o d estimation. W e assume that the bandwid th capaci ty o f the ce l l , C , is equal to 20 and w e choose a constant average ca l l arr ival rate o f 1 call /sec to obtain ca l l b l o c k i n g probabi l i t ies that over lay [0, 1] interval exclus ively . T h e n we simulate the mode l us ing l ogno rma l ly distr ibuted ca l l ho ld ing times w i t h the corresponding /u's and a's obtained from the same empi r i ca l data set to have equivalent mean values w i t h the exponent ial ly distributed ca l l h o l d i n g t imes. The results are g iven i n F i g . 4.8. W e observe that ca l l b l o c k i n g probabil i t ies obtained w h e n ca l l ho ld ing times are exponent ia l ly distr ibuted match w e l l w i t h the ca l l b l o c k i n g probabi l i t ies obtained when ca l l ho ld ing times are lognorma l ly distributed provided that both distr ibutions have means that are al ike. However , we shal l note that it is more cha l lenging to compute the parameters (ju and a) o f a lognormal dis t r ibut ion us ing the 88 expected value obtained f rom an empi r ica l data set when compared to comput ing the mean value for an exponent ial dis t r ibut ion. 4.4.3 Channel Occupancy and Call Holding Times of Stationary and Mobile Users In this section, w e present the statistical results obtained f rom the goodness-of-fit tests performed to fit a proposed candidate distr ibution to observed channel occupancy and ca l l ho ld ing times w h e n these distributions are grouped w i t h respect to user mob i l i t y : stationary and mobi le . In [12] and [13], the authors demonstrated theoret ical ly that traffic characteristics such as channel occupancy t imes depend not on ly on ca l l h o l d i n g t imes but also on users' m o b i l i t y w h i c h can be characterized b y ce l l residence times. Howeve r , it is diff icul t to obtain ce l l residence t imes f rom the data sets since the observed data are col lected from network nodes w h i c h track id le mob i l e users by exchanging messages very infrequently. Thus, we classify users i n our data set w i t h respect to their m o b i l i t y characteristics based on the number o f handoffs that they c o m m i t dur ing a ca l l . W e identify each user w i t h zero number o f handoffs stationary or low mobility and the rest (wi th number o f handoffs more than zero) mobile. No te that some stationary users may i n fact be p h y s i c a l l y m o b i l e w i t h i n a ce l l yet we s t i l l consider them stationary w i t h respect to their ce l l residency. W e consider users mobile i f on ly the number o f handoffs that they commi t is more than a certain threshold (set to 3 handoffs i n this study) since "p i lo t p o l l u t i o n " may cause a stationary c a l l to commi t handoff once i n a w h i l e . Users that are affi l iated w i t h new2same type o f channel occupancy times can be considered stationary whereas users affiliated w i t h new2ho, new2sameorho, ho2same, ho2ho and ho2sameorho types o f channel occupancy times can be considered mobi l e . Thus, ca l l ho ld ing t ime dis t r ibut ion for stationary users is equivalent to channel occupancy time distr ibution for new2same. H o w e v e r we have to obtain c a l l h o l d i n g t ime dis tr ibut ion for mobi le users (totaljnobility) separately f rom the data set since the ca l l ho ld ing t ime distr ibution obtained p rev ious ly includes times affiliated w i t h both stationary and mobi le users. The test results and chi-square statistics for a l l types o f channel occupancy times are prev ious ly g iven. W e apply the chi-square goodness o f fit test o n l y to the total jnobility data set after the observed anomalies were stripped us ing s imple means. The results are presented i n Table 4.9 where s ignif icant l eve l is 0.95, the candidate p robab i l i ty dis tr ibut ion w h i c h 89 passes the chi-square goodness o f fit test is marked w i t h a star (*) and the test statistics for the closest fitted candidate dis t r ibut ion g iven i n the table is bolded. F igure 4.9 shows the closest fitted candidate dis t r ibut ion, lognormal , a long w i t h the norma l i zed his togram for mobi le users' ca l l h o l d i n g times. In [14], Fang , Ch lamtac and L i n showed analy t ica l ly that w h e n c e l l residence times are exponent ia l ly distributed, channel occupancy t ime dis t r ibut ion for "new ca l l s " can be approximated b y the fitted exponential distr ibution for stationary users (or when m o b i l i t y is low) and yet for mob i l e users there is a significant mismatch between channel occupancy t ime dis t r ibut ion for "handoff ca l l s " and the fitted exponential dis t r ibut ion. In this study, w e observe that not o n l y channel occupancy and c a l l ho ld ing t ime dis t r ibut ion for mobi le users fit lognormal dis t r ibut ion very strongly compared to other proposed candidate distributions but also both distr ibutions for stationary users fit lognormal dis t r ibut ion w h i l e rad ica l ly differing f rom the fitted exponential distr ibution. Hence w e expect c e l l residence times also not to be exponent ia l ly distributed. 4.4.4 Statistical Results for Number of Handoffs Committed by Users In this section, w e present the statistical results obtained f rom the goodness-of-fit test performed to fit a proposed candidate dis tr ibut ion to the dis t r ibut ion o f number o f handoffs commit ted b y mob i l e users i n a cel lu lar network. The dis t r ibut ion o f the number o f handoffs becomes significant w h e n feeding network simulat ions. The test and chi-square statistics are presented i n Table 4.10 where significant l eve l is 0.95, the candidate probabi l i ty distr ibution w h i c h passes the chi-square goodness o f fit test is marked w i t h a star (*) and the test statistics for the closest fitted candidate dis tr ibut ion g iven i n the table is bolded. F igure 4.10 shows the closest fitted candidate dis t r ibut ion, lognormal , a long w i t h the no rma l i zed histogram for users' number o f commi t t ed handoffs. 4 . 5 S u m m a r y In this chapter, w e have presented an empi r ica l approach to determine the probabi l i ty distr ibution functions that fit various types o f channel occupancy t imes for vo ice service i n cel lular networks. The results are environment dependent however w e have made no 90 assumptions that can inf luence the results as opposed to previous analyt ical and s imulat ion studies where the obtained results can be h igh ly dependent on the assumptions made by the authors. W e have expla ined the data acquis i t ion method that w e used to obtain the statistics for various types o f channel occupancy times and discussed the system related anomalies that we have observed. The statistical results obtained f rom the goodness-of-fit tests have been presented a long w i t h the candidate probabi l i ty distributions that m a y fit the empi r ica l data. W e have shown that not o n l y c a l l ho ld ing times but also various types o f channel occupancy times can be approximated b y lognormal distr ibution. W e have examined h o w mode l ing ca l l ho ld ing times w i t h a lognormal dis tr ibut ion w o u l d impact the value o f performance metrics such as c a l l b l o c k i n g probabi l i t ies instead o f mode l ing w i t h an equivalent t radi t ionally accepted exponent ial dis t r ibut ion. We have observed that ca l l b l o c k i n g probabi l i t ies obtained when ca l l h o l d i n g t imes are exponent ia l ly distributed match w e l l w i t h the ca l l b l o c k i n g probabil i t ies obtained w h e n ca l l h o l d i n g times are l ognorma l ly distr ibuted p rov ided that both distributions have equal means. W e have d iscovered that not on ly channel occupancy and ca l l ho ld ing t ime distributions for m o b i l e users fit the lognormal dis t r ibut ion ve ry s t rongly compared to other proposed candidate distr ibutions but also both distr ibutions for stationary users fit the lognormal dis t r ibut ion ve ry w e l l w h i l e it rad ica l ly differs f rom the exponent ial distr ibution. We have presented the statistical results obtained from the goodness-of-fit test performed to fit a proposed candidate dis t r ibut ion to the number o f handoffs commi t ted b y mob i l e users i n a cel lular network. W e have shown that the closest fitted candidate dis tr ibut ion to approximate the dis t r ibut ion o f number o f handoffs commit ted b y users i n a ce l lu lar network is also a lognormal dis t r ibut ion. The results are expected to be useful i n traffic and network mode l ing , performance evaluation, b i l l i n g , ne twork management and opt imiza t ion i n ce l lu lar networks. 91 0.06 0.05 0.01 0 I New 2 Same channel occupancy times — Fitted lognormal distribution — Fitted exponential distribution | -;g \ : \ i -0 20 40 60 80 100 120 140 160 180 200 Channel Occupancy Times (sec) F i g . 4.1 Di s t r ibu t ion o f channel occupancy times (new2same) and the fitted lognormal and exponential distr ibutions. F i g . 4.2 Di s t r ibu t ion o f channel occupancy times (new2ho) and the fitted lognormal and exponential distr ibutions. 92 F i g . 4.3 Di s t r ibu t ion o f channel occupancy times (new2sameorho) and the fitted lognormal and exponential distr ibutions. 0.07 Ho 2 Sams channel occupancy times — Fitted lognormal distribution — Fitted exponential distribution 0.06 ~ 0.05 Channel Occupancy Times (sec) F i g . 4.4 Di s t r ibu t ion o f channel occupancy t imes (ho2same) and the fitted lognormal and exponential distr ibutions. 93 F i g . 4.5 Di s t r ibu t ion o f channel occupancy t imes (ho2ho) and the fitted lognormal and exponential distr ibutions. — Ho 2 Same or Ho channel occupancy times — Fitted lognormal distribution — Filled exponential distribution 30 40 50 60 70 Channel Occupancy Times (sec) g. 4.6 Dis t r ibu t ion o f channel occupancy times (ho2sameorho) and the fitted lognormal and exponential distr ibutions. 94 0.04 Total, call holding times Fitted lognormal distribution Fitted exponential distribution 60 80 100 120 140 160 180 200 Call Holding Times (sec) F i g . 4.7 Di s t r ibu t ion o f c a l l ho ld ing times (total) and the fitted lognormal and exponential distr ibutions. 60 Call traffic load 120 F i g . 4.8 C a l l b l o c k i n g probabil i t ies for exponentially and lognormally distributed ca l l ho ld ing t imes. 95 F i g . 4.9 Dis t r ibu t ion o f ca l l ho ld ing times {total mobility) and the fitted lognormal distr ibution. ;. 4.10 Dis t r ibu t ion o f number o f user handoffs (user Jiandoffs) and the fitted lognormal dis tr ibut ion. 96 T A B L E 4.1 A n example o f a "Neighbor List Tuning Data Array" message taken f rom B e l l M o b i l i t y cel lular ca l l data set. Attribute Name: Neighbor List Tuning Data Array TimeStamp: 2003/09/19- 11:46:28.240 Source Node Id: 0xd6ad45 Call Id: 0x00000520cb286664 Resource Info: Frame 4 Shelf 1 Slot 15 DSP 7 Baseld KeepBit PilotStrength PNOffset PNPhase 0x09771101 1 32 36 0 0x09770e21 1 31 222 14225 0x09771372 1 26 300 19209 0x09770e72 1 28 336 21507 0x09771073 1 34 396 25357 0x09771081 1 27 114 7304 0x09770e71 1 40 330 21124 0x09771382 1 44 372 23828 0x09771071 1 24 384 24589 T A B L E 4.2 Goodness o f fit test results for Channe l Occupancy T i m e dis t r ibut ion fi t t ing (new2same). Distribution Test Statistics Chi-square Statistics Exponential 9.8955e+02 5.5102e+02 Lognormal* 3.1824e+02 5.4997e+02 Gamma 1.3068e+03 5.4997e+02 Weibull 1.178e+03 5.4997e+02 number of bins: 500, number of data samples per bin: 11.892 97 T A B L E 4.3 Goodness o f fit test results for Channe l Occupancy T i m e dis t r ibut ion fi t t ing (new2ho). Distribution Test Statistics Chi-square Statistics Exponential 1.2794e+03 5.5102e+02 Lognormal* 3.0301e+02 5.4997e+02 Gamma 6.8892e+03 5.49975e+02 Weibull* 5.4559e+02 5.4997e+02 number of bins: 500, number of data samples per bin: 9.336 T A B L E 4.4 Goodness o f fit test results for Channe l Occupancy T i m e dis t r ibut ion fi t t ing (new2sameorho). Distribution Test Statistics Chi-square Statistics Exponential 1.7965e+03 5.5102e+02 Lognormal 6.9142e+02 5.4997e+02 Gamma 1.7968e+03 5.4997e+02 Weibull 1.67174e+03 5.4997e+02 number of bins: 500, number of data samples per bin: 19.554 T A B L E 4.5 Goodness o f fit test results for Channe l Occupancy T i m e dis t r ibut ion fi t t ing (ho2same). Distribution Test Statistics Chi-square Statistics Exponential 1.1922e+03 5.5102e+02 Lognormal* 3.325e+02 5.4997e+02 Gamma 6.651e+02 5.4997e+02 Weibull* 5.1167e+02 5.4997e+02 number of bins: 500, number of data samples per bin: 10.832 98 T A B L E 4.6 Goodness o f fit test results for Channe l Occupancy T i m e dis t r ibut ion fi t t ing (ho2ho). Distribution Test Statistics Chi-square Statistics Exponential Lognormal Gamma Weibull 3.4501 e+03v 5.5853e+02 2.9586e+03 2.3558e+03 5.5102e+02 5.4997e+02 5.4997e+02 5.4997e+02 number of bins: 500, number of data samples per bin: 35.13 T A B L E 4.7 Goodness o f fit test results for Channe l Occupancy T i m e dis t r ibut ion fi t t ing (ho2sameorho). Distribution Test Statistics Chi-square Statistics Exponential 4.6679e+03 2.8574e+02 Lognormal 6.4289e+02 2.8466e+02 Gamma 3.6019e+03 2.8466e+02 Weibull 2.7327e+03 2.8466e+02 number of bins: 250, number of data samples per bin: 91.86 T A B L E 4.8 Goodness o f fit test results for C a l l H o l d i n g T i m e dis t r ibut ion fi t t ing (total). Distribution Test Statistics Chi-square Statistics Exponential 1.8421e+03 5.5102e+02 Lognormal* 4.3353e+02 5.4997e+02 Gamma 2.8244e+03 5.4997e+02 Weibull* 1.7486e+03 5.4997e+02 number of bins: 500, number of data samples per bin: 22.426 99 T A B L E 4.9 Goodness o f fit test results for C a l l H o l d i n g T i m e dis t r ibut ion f i t t ing (totaljnobility). Distribution Test Statistics Chi-square Statistics Exponential Lognormal* Gamma Weibull 7.0154e+02 3.1515e+02 6.445 le+02 6.8223e+02 5.5102e+02 5.4997e+02 5.4997e+02 5.4997e+02 number of bins: 500, number of data samples per bin: 5.398 T A B L E 4.10 Goodness o f fit test results for N u m b e r o f Use r Handoffs dis t r ibut ion fi t t ing (user handoffs). Distribution Test Statistics Chi-square Statistics Exponential 1.0844e+03 2.5884e+02 Lognormal* 2.0881e+02 2.5776e+02 Gamma 1.8877e+03 2.8466e+02 Weibull 9.62e+02 2.5344e+02 number of bins: 250, number of data samples per bin: 22.704 100 4.6 Bibliography [I] D . H o n g and S. S. Rappaport , "Traff ic mode l and performance analysis for cel lular mob i l e radiotelephone systems w i t h p r io r i t i zed and non-pr ior i t ized handoff procedures," IEEE Transactions on Vehicular Technology, v o l . 35, pp. 77-92, A u g . 1986. [2] R . Ramjee, R . Nagarajan, and D . Towsley, " O n op t ima l c a l l admiss ion control i n ce l lu lar ne tworks ," Wireless Networks, v o l . 3, no. 1, pp. 29-41 , M a r c h 1997. [3] Y . Fang , and Y . Zhang , " C a l l admiss ion control schemes and performance analysis i n wireless m o b i l e ne tworks ," IEEE Transactions on Vehicular Technology, v o l . 51, no.2, pp. 371-382, M a r c h 2002. [4] M . Naghsh ineh and S. Schwartz , "Dis t r ibuted ca l l admiss ion control i n mobi le /wire less networks ," IEEE Journal on Selected Areas in Communications, v o l . 14, no. 4, pp.711-717, M a y 1996. [5] A . Gersht and K . J . Lee , " A bandwidth management strategy i n A T M networks," Technica l report, G T E Laboratories , 1990. [6] S. C . Bors t and D . M i t r a , " V i r t u a l par t i t ioning for robust resource sharing: computat ional techniques for heterogeneous traffic," IEEE Journal on Selected Areas in Communications, v o l . 16, no. 5, pp. 668-678, June 1998. [7] E . A . Y a v u z and V . C . M . L e u n g , "Computa t iona l ly efficient method to evaluate the performance o f guard-channel-based ca l l admiss ion control i n ce l lu lar networks," IEEE Transactions on Vehicular Technology, v o l . 55, no. 4, pp. 1412-1424, Ju ly 2006. [8] S. S. Rappaport , "The mul t ip le ca l l handoff p r o b l e m i n personal communicat ions networks," IEEE 40th Vehicular Technology Conference, pp. 287-294, M a y 1990. [9] S. S. Rappaport and G. M o n t e , " B l o c k i n g , hand-off and traffic performance for cel lular communica t ion systems w i t h m i x e d platforms," IEEE 42" Vehicular Technology Conference, v o l . 2, pp. 1018-1021, M a y 1992. [10] R . A . G u e r i n , " C h a n n e l occupancy t ime dis tr ibut ion i n a ce l lu lar radio system," IEEE Transactions Vehicular Technology, v o l . 35, no. 3, pp. 89-99, 1987. [ I I ] C . J ed rzyck i , and V . C . M . L e u n g , "Probab i l i ty dis t r ibut ion o f channel ho ld ing t ime i n cel lu lar te lephony systems," IEEE Vehicular Technology Conference (VTC'96), v o l . 1, pp. 247-251, A p r . 1996. [12] Y . Fang , I. Ch lamtac , and Y . B . L i n , " C a l l performance for a P C S network," IEEE Journal on Selected Areas in Communications v o l . 15, no. 8, pp. 1568-1581, Oct . 1997. 101 [13] Y . Fang , I. Ch lamtac , and Y . B . L i n , " M o d e l i n g P C S networks under general ca l l ho ld ing t imes and c e l l residence t ime distr ibutions," IEEE Transactions on Networking v o l . 5, no. 6, pp. 893-906, D e c . 1997. [14] Y . Fang , I. Ch lamtac and Y . B . L i n , "Channe l occupancy t imes and handoff rate for mob i l e comput ing and P C S networks," IEEE Transactions on Computers v o l . 47, no. 6, pp. 679-692, June 1998. [15] F. Barce lo , and J . Jordan, "Channe l ho ld ing t ime dis t r ibut ion i n pub l ic telephony systems ( P A M R and P C S ) , " IEEE Transactions on Vehicular Technology, v o l . 49, no. 5, pp. 1615-1625, Sep. 2000. [16] V . A . B o l o t i n , " M o d e l i n g ca l l ho ld ing t ime distr ibutions for C C S network design and performance analysis ," IEEE Journal on Selected Areas in Communications, v o l . 12, no.3, pp. 433-438, A p r i l 1994. [17] A . M . L a w and W . D . K e l t o n , Simulation, Modeling and Analysis, 3 r d edit ion, N e w Y o r k : M c G r a w - H i l l , 2000. [18] K . S. T r i v e d i , Probability and Statistics with Reliability, Queuing and Computer Science Applications, N e w Jersey: Pren t ice -Hal l , 1982. [19] M . R . She ldon , Introduction to Probabi l i ty and Statistics for Engineers and Scientists, 3 r d edi t ion, U S A : E l sev i e r A c a d e m i c Press, 2004. 102 C H A P T E R 5 C O N C L U S I O N A N D R E C O M M E N D A T I O N S F O R F U R T H E R W O R K 5.1 Conclusion W e conclude this dissertation w i t h a summary o f our contributions and directions for future work . One d imens iona l M a r k o v chain models are c o m m o n l y used to evaluate ca l l admiss ion control schemes i n cel lu lar networks assuming that ca l l requests that originate from different types o f users are independently Po i s son distributed, channel occupancy times for each ca l l are exponent ia l ly distributed w i t h equal mean values and each ca l l requires an equal channel capacity. These assumptions m a y not be appropriate since cal ls w i t h different priorit ies, such as new and handoff, m a y have different average channel occupancy times i f not different distr ibutions. W h e n average channel occupancy times for different ca l l types are not equal, ex is t ing performance evaluat ion approximat ion methods based o n one dimensional M a r k o v chain models lead to significant discrepancies. Thus , accurate solutions can on ly be obtained b y exact analysis methods based on mul t id imens iona l M a r k o v chain models . However , these methods suffer f rom the curse o f dimensional i ty , w h i c h results i n very h igh computat ional cost for large systems. In chapter 2, we proposed an easy to implement analyt ical performance evaluat ion approximat ion method, effective holding time, w i t h l o w computat ional cost for several w i d e l y k n o w n ca l l admiss ion control schemes under more general assumptions. The proposed approximat ion method provides a h i g h l y accurate closed form solut ion and thus has l o w computat ional cost. W e compared the accuracy o f the proposed method w i t h the exis t ing approximat ion methods ' w i t h respect to exact results obtained f rom the direct method based on mul t id imens iona l M a r k o v chain mode l ing . The results showed that the proposed method outperforms the exis t ing approximat ion methods i n accuracy w h i l e keep ing the computat ional cost low. A n accurate performance evaluation approximat ion method w i t h l o w computat ional cost w i l l motivate the practical implementat ion o f dynamic ca l l admiss ion control schemes. Conven t iona l c i rcu i t - swi tched services such as vo ice are gradual ly be ing replaced b y packet-switched data and mu l t imed ia applications due to increasing demand c o m i n g from 103 users that these services shal l also be available on the move . Conven t iona l ca l l admiss ion control schemes, on the other hand, w i l l continue to be useful when appl ied w i t h suitable scheduling techniques to guarantee Q o S at the packet l eve l since most data and mul t imed ia applications are inherent ly connect ion oriented and packet-swi tched connections can be provis ioned to their effective bandwidths . Performance o f ca l l admiss ion control schemes for mult i -service ce l lu la r networks, w h i c h provide packet-switched services, can be evaluated by mul t id imens iona l M a r k o v cha in mode l ing since they have a s imi l a r fo rm to c i rcui t -swi tched networks. H o w e v e r ca lcula t ing channel occupancy dis t r ibut ion o f a mul t i -service cel lular network involves numer i ca l l y so lv ing the balance equations w h e n a mul t id imens iona l M a r k o v chain m o d e l is used. In the absence o f a product fo rm solut ion this is demanding for a l l but smallest channel capacities, yet a computat ional ly efficient one d imens iona l M a r k o v chain mode l can o n l y be used when a l l c i rcui t and packet swi tched services have equal capacity requirements. E x i s t i n g performance evaluat ion approximat ion methods for mult i -service ce l lu la r networks are o n l y accurate when c a l l traffic loads are ve ry l o w due to the assumption that channels are occupied independently. In chapter 3, w e classif ied ca l l admiss ion control schemes into two categories ca l led symmetric and asymmetric. W e presented a product fo rm solut ion formula to evaluate symmetr ic c a l l admiss ion control schemes and proposed a nove l computat ional ly efficient performance evaluation approximat ion method, state space decomposition, to evaluate asymmetr ic ca l l admiss ion control schemes w h e n a l l services have distinct capacity requirements. W e compared the numerica l results obtained f rom the proposed method w i t h the ones obtained from previous ly proposed approximat ion methods and the numer ica l exact method based on mul t id imens iona l M a r k o v cha in mode l ing . The results showed that proposed method provides more accurate solutions w h i l e keep ing the computat ional cost low. Packet -swi tched services are over la id on c i rcui t -swi tched technology over the same air interface to u t i l i ze ce l lu lar network 's access capacity. M o r e than one service can be mul t ip lexed stat ist ically on to the same radio channel since it is u n l i k e l y that a l l services transmit at their peak rates at the same time. The network can allocate each user less resource than the corresponding requested peak capacity to meet its statistical performance requirements. Thus , data packets can be transmitted efficiently to provide packet-switched services a Q o S leve l comparable to that o f c i rcui t -swi tched services. H o w e v e r accurate voice 104 traffic statistics are needed to understand the length and frequency distr ibutions o f idle periods o f ce l lu lar channels assigned to vo ice i n order to exploi t the statistical mul t ip l ex ing gain i n ce l lu lar networks. Traffic statistics are also used to feed network s imulat ions w i t h realistic traffic data or develop mathematical models to evaluate network performance analyt ical ly . T w o o f these statistics, ca l l h o l d i n g and channel occupancy times, are k e y elements to compute performance metrics such as ca l l b l o c k i n g and dropping probabi l i t ies . Channe l occupancy times are measured f rom ca l l starting t ime t i l l the occupied channel i n the respective ce l l is discarded due to ca l l terminat ion or handoff w h i l e ca l l h o l d i n g t imes are measured from ca l l starting t ime t i l l c a l l terminat ion regardless o f occupy ing a channel i n the same ce l l or not. In classical vo ice traffic m o d e l i n g ca l l ho ld ing times are approximated b y exponential distr ibution, yet it has been shown that a lognormal dis t r ibut ion approximat ion fits m u c h closer. H o w e v e r performance evaluation models for c a l l admiss ion control require the distr ibution o f channel occupancy times rather than dis t r ibut ion o f ca l l ho ld ing times. In chapter 4, w e presented an empi r ica l approach to determine the probabi l i ty distr ibution functions that fit channel occupancy times classif ied accord ing to their occupancy types to provide suff iciently representative statistics. The results are environment dependent but no assumptions that can be inf luent ial have been made as opposed to previous analyt ical and s imulat ion studies where the obtained results are h igh ly dependent on the assumptions made by the authors. W e showed that a l l types o f channel occupancy t imes can be approximated b y lognormal dis t r ibut ion. F o r stationary users channel occupancy t imes are approximated b y exponential d is t r ibut ion due to its tractabili ty assuming that c e l l residence times are also exponent ia l ly distributed. Ye t we observed that lognormal dis t r ibut ion fits m u c h better to channel occupancy times w h e n users are stationary. W e examined the impact o f mode l ing ca l l ho ld ing t imes w i t h lognormal distr ibution on performance metrics instead o f mode l ing w i t h the t radi t ional ly accepted exponential dis tr ibut ion. W h e n averages are same both distributions p rov ide very close results i n a single service system w i t h one type o f ca l l . We showed that l ognorma l d is t r ibut ion is the closest fitted candidate to approximate the number o f handoffs commi t ted by a user. W e expect the results to p lay an important role i n traffic and network mode l ing , performance evaluation, b i l l i n g p lanning , network management and opt imiza t ion i n ce l lu lar networks. 105 5.2 Future Work W h i l e this thesis provides achievements for evaluat ing performance o f ca l l admiss ion control mechanisms i n single and m u l t i service ce l lu lar networks b y proposing computat ional ly efficient approximat ion methods and m o d e l i n g channel occupancy times, there are emerging issues deserving further invest igation. To facilitate the pract ical implementat ion o f proposed approximat ion methods, we need to investigate techniques that can provide good estimations o f ca l l arr ival rates and average channel occupancy t imes o f a l l types o f calls i n real-t ime. In [1], we showed that the proposed state space decomposition method outperforms the B o r s t - M i t r a approach when evaluating the performance o f c a l l admiss ion control schemes under h igh traffic load w h e n the number o f exis t ing ca l l arr ival types are low. H o w e v e r the two-class m o d e l w i t h the heterogeneous traffic m a y be the most cha l lenging one to Bors t and M i t r a ' s approach due to their assumption on independent channel occupancy [2]. Since each o f the i nd iv idua l classes accounts for a substantial por t ion o f the total amount o f capacity i n use, it is wor th invest igat ing to what extent the performance o f authors' approach can improve under h i g h traffic load w i t h respect to the proposed approach when more than two-class models are considered. W e showed i n [3] that channel occupancy times can be approximated b y lognormal distr ibution a long w i t h c a l l h o l d i n g times. H o w e v e r results obtained f rom a simulated cel lular network revealed that performance metrics such as ca l l b l o c k i n g probabi l i t ies are not affected s ignif icant ly w h e n channel occupancy times are mode led w i t h t radi t ional ly accepted exponential d is t r ibut ion p r o v i d i n g that average values for both distr ibutions are same. The exponential d is t r ibut ion underestimates the dis tr ibut ion o f channel occupancy times for its short values w h i l e it overestimates for l ong ones. W h e n the dis t r ibut ion o f channel occupancy times is obtained us ing empi r i ca l data col lected dur ing certain t imes o f a day such as the lunch t ime or rush hours or w h e n the cel lu lar operator offers discounts, this misest imat ion m a y extend. Cons ide r ing that the results i n [3] are environment dependent, we need to seek further investigations for system response us ing empi r i ca l data co l lec ted at various times. 106 B a n d w i d t h scarceness is another important p rob lem i n ce l lu lar networks. M a k i n g radio cel ls smaller is one solut ion, however as ce l l size is reduced, more users w i l l probably require handoffs. O n the other hand, more handoffs can be observed i n environments such as h ighway stretches where users m o v e very fast. These are typ ica l situations where h igh m o b i l i t y o f users m a y affect ce l l residence times and thus the characteristics o f channel occupancy t imes [4]-[6]. It m a y be necessary to analyze empi r i ca l data col lected from base stations serving c e l l sites w i t h h igh m o b i l i t y profi le to determine its effects on distributions o f the classif ied channel occupancy times g iven i n [3]. Fang , Ch lamtac and L i n showed analyt ica l ly i n [7] that channel occupancy time distributions for stationary users can be approximated b y exponent ia l dis t r ibut ion when ce l l residence times are exponent ia l ly distributed. Yet , it is diff icul t to obtain ce l l residence t ime data since network nodes w h i c h track idle mobi le users exchange messages very infrequently. Thus, we class i f ied users w i t h respect to their m o b i l i t y characteristics and observed that channel occupancy and c a l l h o l d i n g t ime distributions for stationary users fit lognormal distr ibution better rather than exponential distr ibution as opposed to results obtained i n [7]. It m a y be interesting to investigate w h i c h dis tr ibut ion fits best to c e l l residence times and how ce l l residence t imes are related to channel occupancy t imes us ing corresponding empir ica l data. 107 Bibliography E . A . Y a v u z and V . C . M . L e u n g , "Eff ic ient approximat ions for c a l l admiss ion control performance evaluations i n mult i -service networks," presented at I E E E G L O B E C O M 06, San Franc isco , L A , N o v e m b e r 2006. S. C . Bors t and D . M i t r a , " V i r t u a l par t i t ioning for robust resource sharing: computat ional techniques for heterogeneous traffic," IEEE Journal on Selected Areas in Communications, v o l . 16, no. 5, pp. 668-678, June 1998. E . A . Y a v u z and V . C . M . Leung , " M o d e l i n g channel occupancy times for voice traffic i n ce l lu lar ne tworks ," to be presented at I E E E I C C 2007, G la sgow, Scot land, June 2007. H . Z e n g , and I. E . Chlamtac , " H a n d o f f traffic d is t r ibut ion i n ce l lu lar networks," I E E E W C N C Wire less Communica t ions and N e t w o r k i n g Conference, v o l . 1, pp. 413-417, Sept 1999. F. K h a n and D . Zeghlache, "Effect o f ce l l residence t ime dis tr ibut ion on the performance o f ce l lu lar mob i l e networks," I E E E 4 7 t h Veh icu la r Technology Conference, v o l . 2, pp. 949-953, M a y 1997. R . B o l l a and M . Repetto, " A new mode l for network traffic forecast based on user's m o b i l i t y i n ce l lu la r networks w i t h h ighway stretches," International Journal of Communication Systems, v o l . 17, no. 10, pp. 911-934, D e c 2004. Y . Fang , I. Ch lamtac , and Y . B . L i n , "Channe l occupancy t imes and handoff rate for mob i l e comput ing and P C S networks," IEEE Transactions on Computers, v o l . 47, pp. 679-692, June 1998. 108 APPENDICES Appendix A PROBABILITY DENSITY FUNCTIONS 1. Exponen t i a l dis t r ibut ion f{x) = A-e~*',x>0 1 _ 1 " Maximum Likelihood Estimators: X = — , where x = — • y\x i x " 2. L o g n o r m a l dis t r ibut ion ln(.v) // f(X) = —^j=-e{ Maximum Likelihood Estimators: ft = — , and a = — i=i 3. G a m m a dis t r ibut ion f(x) = xk~x • e . , , , J C > 0 ek r(k) where k > 0 is the shape parameter, 6 > 0 is the scale parameter ri»= JV"1 -e-'dt -(x/0) 109 Maximum Likelihood Estimators: 0 = -j- • V Xi and ln(*) - <p(k) = lnf— • Y xt, 1 - - • Y ln(x,.), where tp(kj) = kn ,=1 V« w 7 " M r W There is no close form solution for k. The numerical solution can be found using Newton's method. \ 4. W e i b u l l d is t r ibut ion f(x)=(k/X)ix/Af-l)-e-U#,xZO where k > 0 is the shape parameter and X > 0 is the scale parameter o f the dis tr ibut ion. Maximum Likelihood Estimators: X - — and — Y ln(x , ) = 0 n Y^xk k n ,=, There is no close form solution for k. The numerical solution can be found using Newton's method. 110  MODELING AND PERFORMANCE EVALUATIONS OF TELETRAFFIC IN C E L L U L A R NETWORKS by Emre Altug Yavuz B. Sc., Middle East Technical University, 1995 M. Sc., Middle East Technical University, 1998 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA February 2007 © Emre Altug Yavuz, 2007 ABSTRACT The g r o w i n g interest for cel lular technology has mot iva ted operators to provide a wide variety o f services f rom convent ional c i rcui t -swi tched vo ice to packet-switched data and mu l t imed ia applicat ions. P r o v i d i n g these services anyt ime and anywhere is chal lenging due to not o n l y frequent status changes i n network connect ivi ty, but also l imi ted resources such as bandwidth . Different priori t ies are assigned to services to satisfy diverse Q o S requirements. C a l l admiss ion control schemes have been proposed to manage resources b y select ively l i m i t i n g the number o f admitted cal ls to ensure that Q o S measures such as ca l l b lock ing /d ropp ing probabi l i t ies stay w i t h i n acceptable l imi t s . E x a c t analysis methods based on mul t id imens iona l M a r k o v chain models are used to evaluate performance o f these schemes, yet they suffer f rom curse o f d imensional i ty that results i n very h igh computat ional cost. Large sets o f equations are avoided us ing approx imat ion methods based on one dimensional M a r k o v cha in models assuming that channel occupancy t imes are exponent ial ly distributed w i t h equal mean values and a l l cal ls require equal capacities. E x i s t i n g approximat ion methods lead to significant discrepancies w h e n average channel occupancy times differ. W e propose a nove l performance evaluat ion approx imat ion method, effective holding time, w i t h l o w computat ional complex i ty to relax this assumption. In mul t i - serv ice networks , vo ice is accompanied b y data and mu l t imed ia applications that require dist inct capacities. W h e n capacity requirements differ, exis t ing approximat ion methods based on one d imens iona l M a r k o v cha in models become inaccurate i f not obsolete. W e propose a computa t iona l ly efficient approximat ion method, state space decomposition, to relax this assumption. N u m e r i c a l results show that the proposed method provide h igh ly i i accurate results that match w e l l w i t h exact solutions. Traffic statistics are essential to understand the dis t r ibut ion o f id le periods o f voice channels to over lay packet-switched services o n c i rcu i t - swi tched technology and to feed simulations w i t h realist ic data. C a l l ho ld ing and channel occupancy t imes are k e y elements for comput ing performance metrics such as c a l l b lock ing /d ropp ing probabi l i t ies . W e present an empi r i ca l approach to determine the dis tr ibut ion o f c a l l h o l d i n g and channel occupancy times. W e show that lognormal dis tr ibut ion is the closest fitted candidate to approximate channel occupancy t imes and c a l l ho ld ing t imes for s tat ionary/mobile users a long w i t h the number o f handoffs commi t t ed b y a user. i n T A B L E OF CONTENTS Abstract • >> Table of Contents iv List of Tables vii List of Figures ix List of Symbols xii Acknowledgements xiv Dedication.......... xvi Co-Authorship Statement xvii C H A P T E R 1 Introduction : 1 1.1 Motivations and Objectives 6 1.2 Main Contributions 8 1.3 Organization of the Dissertation 9 1.4 Bibliography 11 C H A P T E R 2 Computationally Efficient Method To Evaluate The Performance Of Guard-Channel-Based Call Admission Control In Cellular Networks 15 2.1 Introduction 15 2.2 Existing Methods to Analyze Performance of C A C Schemes 18 2.2.1 New Call Bounding Scheme 18 2.2.2 Cutoff Priority Scheme 21 2.2.3 Fractional Guard Channel Scheme 22 2.3 The Proposed Performance Evaluation Method 24 iv 2.4 Numerical Results 27 2.4.1 Performance Evaluation of Existing and Proposed Methods 27 2.4.2 Accuracy and Runtime Computational Cost.... 30 2.5 Summary 31 2.6 Bibliography 40 C H A P T E R 3 Computationally Efficient Performance Evaluation Methods For Call Admission Control Schemes In Multi-Service Cellular Networks 43 3.1 Introduction 43 3.2 Performance Evaluation of Symmetric Call Admission Control Schemes 46 3.3 Performance Evaluation of Asymmetric Call Admission Control Schemes 49 3.4 Numerical results 54 3.5 Summary 58 3.6 Bibliography 71 C H A P T E R 4 Probability Distribution Of Channel Occupancy Times And Number Of User Handoff In Cellular Networks. 74 4.1 Introduction 74 4.2 Data Acquisition and System-Related Anomalies .78 4.3 Statistical Methods 80 4.3.1 Candidate Probability Distributions 80 4.3.2 Parameter Estimation 81 4.3.3 Goodness-of-fit Tests 82 4.4 Numerical Results 86 4.4.1 Statistical Results for Channel Occupancy Times 86 4.4.2 The Effects of Traffic Remodeling on Performance Evaluation 88 4.4.3 Channel Occupancy and Call Holding Times for Stationary/Mobile Users...89 4.4.4 Statistical Results for Number of Handoffs Committed by Users . 90 4.5 Summary ....90 v 4.6 B i b l i o g r a p h y 101 C H A P T E R 5 C o n c l u s i o n A n d R e c o m m e n d a t i o n s F o r F u r t h e r W o r k 103 5.1 C o n c l u s i o n 103 5.2 F u t u r e W o r k . . . . 106 5.3 B i b l i o g r a p h y 108 A P P E N D I C E S 109 A p p e n d i x A 109 vi LIST OF TABLES Table 2.1 Sys tem parameter values used for each scenario 38 Table 2.2 Errors i n handoff c a l l dropping probabi l i ty approximat ions relative to direct method 38 Table 2.3 Errors i n new ca l l b l o c k i n g probabi l i ty approximat ions relative to direct method 38 Table 2.4 Percentage gains i n accuracy o f handoff c a l l d ropp ing probabi l i t ies obtained b y the proposed approximat ion method relative to those obtained b y the normalized and the traditional methods 38 Table 2.5 C o m p a r i s o n o f runtime computat ional costs between the proposed method and the direct and iterative numer ica l methods 39 Table 3.1 C o m p a r i s o n o f runtime computat ional costs between the proposed approx imat ion method and the Borst-Mitra, direct and iterative methods 70 Table 4.1 A n example o f a " N e i g h b o r L i s t T u n i n g Da ta A r r a y " message taken f rom a ce l lu lar c a l l data set 97 Table 4.2 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis t r ibut ion fitting (new2same) 97 Table 4.3 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis tr ibut ion fitting (new2ho) 98 Table 4.4 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis tr ibut ion fitting (new2sameorho) 98 Table 4.5 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis tr ibut ion fitting (ho2same) 98 Table 4.6 Goodness o f fit test results for Channe l Occupancy T i m e dis tr ibut ion fitting (ho2ho) 99 Table 4.7 Goodness o f fit test results for Channe l O c c u p a n c y T i m e dis tr ibut ion fitting (ho2sameorho) 99 Table 4.8 Goodness o f fit test results for C a l l H o l d i n g T i m e dis tr ibut ion fitting (total) 99 v n Table 4.9 Goodness o f fit test results for C a l l H o l d i n g T i m e dis t r ibut ion fitt ing (totaljnobility) 100 Table 4.10 Goodness o f fit test results for N u m b e r o f U s e r Handoffs dis tr ibut ion fitting (userJiandoffs) 100 v i i i LIST OF FIGURES Figure 2.1 State transi t ion d iagram for the new c a l l bound ing scheme 33 Figure 2.2 State transi t ion d iagram for the cutoff p r ior i ty scheme 33 Figure 2.3 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r ior i ty scheme (Case I) 34 Figure 2.4 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r io r i ty scheme (Case I) 34 Figure 2.5 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r ior i ty scheme (Case II) 35 Figure 2.6 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r ior i ty scheme (Case II) 35 Figure 2.7 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r ior i ty scheme (Case III) 36 Figure 2.8 H a n d o f f c a l l d ropp ing probabi l i ty i n the cutoff p r io r i ty scheme (Case III) 36 Figure 2.9 N e w c a l l b l o c k i n g probabi l i ty i n the cutoff p r ior i ty scheme (Case I V ) 37 Figure 2.10 H a n d o f f c a l l d ropping probabi l i ty i n the cutoff p r ior i ty scheme (Case I V ) 37 Figure 3.1 Trans i t ion d iagram for asymmetric c a l l admiss ion control schemes w i t h supernodes for pr io r i t i zed calls 60 Figure 3.2 Trans i t ion d iagram for asymmetric c a l l admiss ion control schemes w i t h supernodes for non-pr ior i t ized cal ls .60 Figure 3.3 One d imens iona l M a r k o v chain m o d e l obtained for the pr ior i t i zed ca l l s ' supernodes 61 Figure . 3.4 One d imens iona l M a r k o v chain mode l obtained for the non-pr ior i t ized ca l l s ' supernodes 61 Figure . 3.5 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 1, and m = 24 62 Figure 3.6 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 1, bnp = 1, and m = 24 62 Figure 3.7 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 2, bnp = 1, and m = 24 63 Figure 3.8 N o n - p r i o r i t i z e d ca l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 2, bnp = 1, and m = 24 63 Figure 3.9 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 4, bnp = 1, and m - 24 64 ix Figure 3.10 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 4, bnp = 1, and m = 24 64 Figure 3.11 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 1, and = 28 65 Figure 3.12 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 1, bnp = 1, and m = 28 65 Figure 3.13 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 2, and m = 28 66 Figure 3.14 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 1, bnp = 2, and m = 28 66 Figure 3.15 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoffpriority scheme bp = 1, bnp = 4, and m = 28 67 Figure 3.16 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = 1, bnp = 4, and m = 28 67 Figure 3.17 P r io r i t i z ed ca l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = bnp = 1, pnp = 20, pp = 2.5 to 50, Xp = 0.05 to 1 68 Figure 3.18 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = bnp =l,pnp = 20, pp = 2.5 to 50, Xp = 0.05 to 1 68 Figure 3.19 P r io r i t i z ed c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = bnp = 1, pnp = 20 , pp = 2.5 to 50, V/ip = 5 to 100 69 Figure 3.20 N o n - p r i o r i t i z e d c a l l b l o c k i n g probabi l i ty for the cutoff priority scheme bp = bnp =\,p„p = 20,p p = 2.5 to 50, \lpp = 5 to 100 69 Figure 4.1 Di s t r ibu t ion o f channel occupancy times (new2same) and the fitted lognormal and exponential distributions 92 Figure 4.2 Di s t r i bu t ion o f channel occupancy times (new2ho) and the fitted lognormal and exponential distr ibutions 92 Figure 4.3 Di s t r i bu t ion o f channel occupancy times (new2sameorho) and the fitted lognormal and exponential distributions 93 Figure 4.4 Di s t r i bu t ion o f channel occupancy times (ho2same) and the fitted lognormal and exponential distr ibutions 93 Figure 4.5 Di s t r i bu t ion o f channel occupancy t imes (ho2ho) and the fitted lognormal and x exponential distr ibutions 94 Figure 4.6 Di s t r i bu t ion o f channel occupancy times (ho2sameorho) and the fitted lognormal and exponential distributions 94 Figure 4.7 Di s t r i bu t ion o f c a l l ho ld ing times (total) and the fitted lognormal and exponential distr ibutions 95 Figure 4.8 C a l l b l o c k i n g probabi l i t ies for exponentially and lognormally distributed ca l l h o l d i n g t imes 95 Figure 4.9 Di s t r i bu t ion o f c a l l ho ld ing times (total mobility) and the fitted lognormal dis t r ibut ion 96 Figure 4.10 Dis t r ibu t ion o f number o f user handoffs (user Jiandoffs) and the fitted lognormal dis t r ibut ion 96 xi LIST OF SYMBOLS C Number of channels in a cell. c Number of occupied channels in a cell. K Threshold for new call bounding scheme. m Threshold for the cutoff priority scheme. Xn Arrival rate for new calls. Xh Arrival rate for handoff calls. Xnp Arrival rate for non-prioritized calls. Xp Arrival rate for prioritized calls. l/ju„ Average channel holding time for new calls. l/uh Average channel holding time for handoff calls. \lpnp Average channel holding time for non-prioritized calls. \lup Average channel holding time for prioritized calls. Mueff Average effective channel holding time. b„p Capacity requirement in bandwidth units for non-prioritized calls. bp Capacity requirement in bandwidth units for prioritized calls. p„ Traffic intensity for new calls (i.e., X„ I /u„). ph Traffic intensity for handoff calls (i.e., Xh i uh). p„p Traffic intensity for non-prioritized calls (i.e., Xnp I unp). pp Traffic intensity for prioritized calls (i.e., Xp I pp). nnp Number of non-prioritized calls in the system. np Number of prioritized calls in the system. pnb Blocking probability for new calls. pM Dropping probability for handoff calls. pa Blocking probability for new calls from the normalized approximation. p" Dropping probability for handoff calls from the normalized approximation. x i i 'nb Blocking probability for new calls from the traditional approximation. p' Dropping probability for handoff calls from the traditional approximation. peff Blocking probability for new calls from the proposed approximation. peff Dropping probability for handoff calls from the proposed approximation. Pi User defined admission probability for non-prioritized (new) calls in a call admission control scheme. q(c) Equilibrium channel occupancy probability when c channels are occupied. q(c) Approximated equilibrium channel occupancy probability when c channels are occupied. Bnp Blocking probability for non-prioritized calls. Bp Blocking probability for prioritized calls. kj Admission probability for prioritized calls. hr Admission probability for non-prioritized calls. qp(j) Equilibrium channel occupancy probability when j prioritized calls exist in the system. q„p(r) Equilibrium channel occupancy probability when r non-prioritized calls exist in the system. q(n ,n ) Estimated equilibrium channel occupancy probability for nnp non-prioritized and np prioritized calls. xin ACKNOWLEDGEMENTS Y e s ! A fierce and savage w i n d tore at us. W e were on top o f Annapurna ! 8,075 meters ... O u r hearts over f lowed w i t h an unspeakable happiness. " I f o n l y the others cou ld k n o w . . . " I f o n l y everyone cou ld k n o w ! M a u r i c e H e r z o g o n summi t ing Annapurna To me, w r i t i n g a P h . D . thesis is l ike c l i m b i n g a h i g h altitude mounta in for the first t ime. Often y o u do not have any spectators and acknowledgement is not acquired unless y o u make it to the top. T h e graduate leve l courses guide y o u w h i l e y o u are o n your w a y to the base camp and every paper y o u manage to pub l i sh afterwards means reaching higher camps, taking y o u closer to the summit for the final push yet. Ne i the r everybody c l imbs the same mountain nor under the same condit ions. That is w h y c l i m b i n g w i t h the right guide is important not o n l y to p i c k the right route on the w a y to the top but also to k n o w where your h igh altitude camps sha l l be set up. Sometimes the condi t ions and the d i f f icul ty o f the route force y o u to back o f f o n l y to return later k n o w i n g that what does not k i l l makes stronger. Yet , from an outsider 's point o f v i e w what matters most is whether y o u c l i m b it or not regardless o f what happened o n the way. Th i s is a self-guided journey where a passionate c l i m b e r never gives up for the sake o f learning about one's se l f and l imi t s . However , choos ing a competent guide is not on ly v i ta l to avo id storms, c l i m b i n g to dead ends and be ing left to destiny w h e n i n trouble but also to lift the spirits up w h e n needed. I a m thankful to m y perseverance and d i l igence for not on ly m a k i n g it to the top through storms and tu rmoi l but also getting m y s e l f back on the right track despite surrounded b y a th ick fog at most t imes. W i t h a l i t t le twist on what H i l l a r y said when he c l i m b e d M o u n t Everest , "It wasn ' t the title I was after, it was to conquer mysel f . " xiv I dedicate this w o r k to m y parents for their uncondi t iona l love and support. I am thankful for their un l imi t ed patience and confidence i n me dur ing this arduous c l i m b . I w o u l d not be able to complete m y graduate studies without their dedicated sacrif ice, understanding, and encouragement. I a m grateful to m y friends; A l i y e , G o r k e m , K a a n , R i ibab and Verda, who helped me i n m a n y ways that kept me c l i m b i n g i n good times and bad. Las t but not the least I w o u l d l i ke to express m y gratitude to m y supervisor Dr . V i c t o r C . M . L e u n g for his guidance, comments and f inancia l support. To conclude, I w o u l d once more l ike to quote M a u r i c e H e r z o g as he says, "There are other Annapurnas i n men's l i f e . " x v To my mom, Semra, and my dad, Huseyin, for their unconditional love and absolute support ... x v i Go-Authorship Statement I am the first author and principle contributor of all manuscript chapters. A l l manuscript chapters are co-authored with V . C . M . Leung, who co-supervised the thesis research. xvii CHAPTER 1 I N T R O D U C T I O N C e l l u l a r network technology is one o f the fastest g r o w i n g ways o f mob i l e communica t ions today. The bounds o f an exis t ing communica t i on network infrastructure have been extended b y ce l lu lar technology v i a connect ing m o b i l e units to pub l ic network operated b y the l oca l exchange or l ong distance carriers to make specia l features and functions specific to both cel lu lar and pub l ic networks avai lable to a l l users. G l o b a l standards have been developed to p rov ide vo ice and data services anyt ime and anywhere regardless o f user m o b i l i t y w h i l e sat isfying their diverse Qua l i t y o f Serv ice ( Q o S ) requirements. R a d i o resources such as bandwid th , transmit power, channel codes and base stations are generally l imi ted i n ce l lu lar networks due to phys ica l and regulatory restrictions as w e l l as the interference-limited nature o f the cel lu lar structure. Eff ic ient management o f these resources is not o n l y c ruc ia l to the eff ic iency o f system operation and congest ion prevention, but it is also very important to satisfy the Q o S requirements o f user applicat ions. Services w i t h specific data rate, bandwid th , power and latency requirements need specific amount o f system resources to be al located at the t ime o f ca l l admiss ion to ensure that these requirements are attained and sustained dur ing communica t ion . Signif icant challenges confronted b y ce l lu la r networks due to frequent status changes i n connect iv i ty and h igh ly variable no i sy communica t i on channels can be overcome b y Q o S p rov i s ion ing w h i c h has become one o f the most demanding problems. Resource management requires more sophisticated techniques i n a mob i l e environment than those used i n f ixed systems since a b l i n d spot m a y be reached where Q o S is severely l im i t ed due to a weak signal or a loss o f communica t i on m a y occur during a handoff w h e n the new point o f attachment m a y not be able to p rov ide resources s imi la r to the o ld one. Nevertheless , the p rob lem o f mainta in ing service cont inui ty for users' applications during handoffs has been intensif ied w i t h the increasing number o f mic roce l l s and p icocel l s i n cel lular networks. C a l l admiss ion control ( C A C ) schemes have been developed to manage scarce radio resources to m a x i m i z e network u t i l iza t ion b y se lect ively l i m i t i n g the number o f admitted cal ls . Probabi l i t ies o f ca l l b l o c k i n g and dropping are two important Q o S measures 1 used when evaluat ing performance o f ca l l admiss ion control schemes. C a l l b l o c k i n g occurs when a ce l lu lar ne twork is unable to assign network resources to enable a c a l l init iated i n a ce l l , whereas ca l l d ropp ing occurs when a ce l lu lar network is unable to assign network resources to enable a c a l l handed o f f f rom a ne ighbor ing ce l l . Sufficient network resources shall be p rov ided to ensure that ca l l b l o c k i n g and d ropp ing probabi l i t ies stay w i t h i n acceptable l imi t s for user applicat ions. A higher pr ior i ty is n o r m a l l y assigned to handoff calls over the new ones to m i n i m i z e c a l l dropping probabi l i ty since dropping an on-going ca l l is generally more object ionable to a user than b l o c k i n g a new c a l l request. H o w e v e r reducing b l o c k i n g probabi l i t ies o f cal ls w i t h higher priori t ies increases the p robab i l i ty o f b l o c k i n g for calls w i t h re la t ive ly l ower priori t ies result ing i n a trade o f f between both types o f cal ls . Therefore the goal is to sustain a balance between calls o f different pr ior i t ies w h i l e satisfying the respective Q o S requirements. C a l l admiss ion control has been intensively studied i n the past [1][2] and many priori ty-based C A C schemes have been proposed [3]-[18]. One d imens iona l M a r k o v chain models are c o m m o n l y used to evaluate these schemes (e.g., [6] [7] [15]) assuming that ca l l requests that originate f rom different types o f users are independently Po i s son distributed, channel occupancy t imes for each ca l l are exponent ia l ly distr ibuted w i t h equal mean values and each c a l l requires an equal channel capacity. Yet these assumptions m a y not be appropriate since cal ls w i t h different priori t ies , such as new and handoff, m a y have different average channel occupancy t imes i f not different distr ibutions as shown i n [19], [20] and references therein. E x i s t i n g performance evaluat ion approximat ion methods based on one d imens iona l M a r k o v cha in m o d e l i n g lead to significant discrepancies w h e n average channel occupancy t imes for different c a l l types are not equal [21]. Gersht and L e e proposed an iterative a lgor i thm i n [22] b y m o d i f y i n g the approximat ion suggested b y Roberts i n [23] to improve its accuracy w h e n service rates differ. H o w e v e r the a lgor i thm is o n l y accurate when appropriate in i t i a l values are chosen and therefore m a y not be competent [21]. L i and Chao obtained a product fo rm solu t ion i n [24] b y mode l ing a m u l t i c e l l ne twork as a network o f queues e m p l o y i n g a h y b r i d guard channel/queuing p r io r i ty scheme w i t h transfer o f unsuccessful requests to ne ighbor ing cel ls . The i r solut ion is restrictive to the protocol considered and therefore m a y not be appropriate to be used for the performance evaluation o f ca l l admiss ion cont ro l schemes i n general. Thus , exact analysis methods based on 2 > mul t id imens iona l M a r k o v cha in models appeared to be the o n l y means to obtain accurate solutions for evaluat ing c a l l admiss ion control schemes. Rappaport obtained c a l l b l o c k i n g probabil i t ies for cal ls w i t h various priori t ies b y us ing a mul t id imens iona l m o d e l o f a cel lular network i n [25]. Rappaport and M o n t e developed an analyt ical m o d e l for traffic performance analysis us ing a mul t id imens iona l b i r th death process i n [26] b y cons ider ing the effects o f various pla t form types dis t inguished b y different m o b i l i t y characteristics o n performance. E v e n though mul t id imens iona l M a r k o v chain models are capable o f p r o v i d i n g the exact solutions, these methods suffer f rom the curse o f dimensional i ty , w h i c h results i n very h igh computat ional cost for large systems. A n easy to implement analyt ical approximat ion method w i t h h i g h l y accurate solutions and l o w computat ional cost is needed to compute new/handoff c a l l b lock ing /d ropp ing probabil i t ies o f cal ls for several w i d e l y k n o w n ca l l admiss ion control schemes under more general assumptions. The fast evo lu t ion o f ce l lu lar networks has been accompanied not o n l y b y basic voice services but also b y development , growth and use o f a w i d e var ie ty o f network applications that range from text-based ut i l i t ies such as S M S messaging, f i le transfer, remote log in and electronic m a i l i n g to m u l t i m e d i a util i t ies such as v ideo conferencing and streaming, web surfing and electronic commerce . T h i s has mot ivated cel lu lar ne twork operators to move away from just p r o v i d i n g convent ional vo ice services to embrac ing a w i d e variety o f traffic from data to m u l t i m e d i a applicat ions due to increasing demand c o m i n g f rom users that these services shal l also be avai lable on the move . Different techniques have been proposed to allocate l imi t ed and v a r y i n g network resources efficiently to a var ie ty o f services w i t h different characteristics and Q o S requirements at different network layers. [27]. M o d u l a t i o n and power control schemes are designed to be Q o S aware at the phys i ca l layer [28] as m e d i u m access control is adjusted to support reservations and Q o S guarantees at the data l ink layer. A t the ne twork layer, techniques o f m o b i l i t y management and seamless connectivity, i nc lud ing the extension o f rout ing mechanisms to be Q o S aware and able to handle mobi l i ty , are appl ied [29]. M u l t i m e d i a cod ing systems such as H . 2 6 3 L v ideo codecs are introduced for the appl icat ion layer [30]. C a l l admiss ion control schemes are analyzed us ing M a r k o v cha in models based on c i rcui t -swi tched network architectures, however convent ional c i rcu i t - swi tched services such as vo ice are gradual ly be ing replaced b y packet-switched data and mu l t imed ia applications. 3 Conven t iona l c a l l admiss ion control schemes w i l l continue to be useful w h e n applied w i t h suitable schedul ing techniques to guarantee Q o S at the packet l eve l since most data and mul t imed ia applicat ions are inherently connect ion oriented and packet-swi tched connections can be p rov i s ioned to their effective bandwidths [31]-[33]. Effect ive bandwid th represents the phys i ca l l y dedicated bandwid th o f a packet-switched connect ion to match its overa l l traffic demand. M a r k o v cha in m o d e l i n g w i l l s t i l l be useful since a ce l lu lar network can have a s imi la r fo rm to a c i rcui t -swi tched network operating w i t h f ixed rout ing [32]. H o w e v e r calcula t ing channel occupancy dis t r ibut ion o f such a mul t i - serv ice ce l lu lar network using an exact so lu t ion method based on mul t id imens iona l M a r k o v cha in mode l ing involves numer ica l ly s o l v i n g the balance equations, w h i c h is demanding for a l l but smallest channel capacities i n the absence o f a product form solution. E x i s t i n g approximat ion methods based on one d imens iona l M a r k o v cha in mode l ing , on the other hand, become obsolete when packet-switched connect ions such as data and mu l t imed ia applicat ions have distinct capacity requirements. In [34], Bors t and M i t r a developed computat ional algori thms for a mul t i -service ce l lu lar ne twork b y coup l ing the computat ion o f jo in t channel occupancy probabil i t ies w i t h that o f used capaci ty assuming that channels are occupied independently. The authors so lved the balance equations through numer ica l i teration but the results can on ly be comparat ive w h e n the number o f exis t ing ca l l a r r ival types are h i g h due to authors' channel occupancy independence assumption. A nove l performance evaluation approximat ion method w i t h h i g h l y accurate solutions and l o w computat ional cost is needed to compute ca l l b l o c k i n g probabi l i t ies o f circui t and packet-switched connect ion type o f calls that have dist inct capaci ty requirements for several w i d e l y k n o w n c a l l admiss ion control schemes under more general assumptions. The advantage o f hav ing packet-switched connect ion type o f services over la id on c i rcui t -swi tched technology over the same air interface is the u t i l i za t ion o f excess network capacity avai lable i n each c e l l . W h e n large numbers o f sources w i t h bursty characteristics are mul t ip lexed , it is u n l i k e l y that a l l o f them transmit at their peak rates at the same time. The network can then allocate each user less resource than the corresponding requested peak capacity w h i l e meet ing the statistical performance requirements. D a t a packets can be transmitted over radio interface us ing statistical m u l t i p l e x i n g to p rov ide a Q o S level comparable to that o f c i rcu i t - swi tched services. Statistical m u l t i p l e x i n g ga in arises from the 4 talk spurt to si lence ratio found i n speech w h i c h makes it possible to mul t ip lex more than one service on to the same radio channel . H o w e v e r accurate vo ice traffic statistics are needed to understand the length and frequency distributions o f id le periods o f cel lular channels assigned to vo ice i n order to exploi t the statistical m u l t i p l e x i n g ga in i n ce l lu lar networks. Traffic statistics are important for network management and op t imiza t ion along w i t h traffic mode l ing , b i l l i n g and a l locat ion o f safety buffers. These statistics are also used to evaluate performance dur ing network s imula t ion or analysis us ing mathematical models . T w o o f these traffic statistics, c a l l ho ld ing and channel occupancy t imes, are k e y elements to compute performance metr ics such as ca l l b l o c k i n g and dropping probabi l i t ies . In cel lular network analysis c a l l h o l d i n g t imes are generally assumed to be exponent ia l ly distributed due to studies on wi re l ine traffic statistics. In [3], H o n g and Rappaport proposed a traffic mode l for ce l lu lar m o b i l e radio telephone systems and approximated channel occupancy t ime distr ibution b y exponent ia l dis t r ibut ion when ca l l h o l d i n g t imes are assumed to be exponent ia l ly distributed. Ramjee et al. [6], F a n g and Z h a n g [7], Naghsh ineh and Schwartz [15], Gersht and L e e [22], Bors t and M i t r a [34] and Y a v u z and L e u n g [21] studied the performance o f var ious c a l l admiss ion control schemes us ing one d imens iona l M a r k o v chain models assuming that channel occupancy times are exponent ia l ly distr ibuted based on H o n g and Rappaport ' s study due to its tractability. In [25], Rappaport developed mul t id imens iona l models under the same assumption and w i t h M o n t e the author obtained ca l l b l o c k i n g probabil i t ies us ing this m o d e l [26]. H o w e v e r s imula t ion studies and f ie ld data have shown that these assumptions are not perpetually va l i d . In [35], G u e r i n used a s imula t ion mode l to show that channel occupancy t ime dis tr ibut ion displays a rather poor agreement w i t h the exponential f i t t ing for m o b i l e users w i t h l o w change rate o f movement direct ion. Jedrzyck i and L e u n g showed i n [36] that exponential dis t r ibut ion assumption for channel occupancy times is not correct and a lognormal mode l approximat ion fits m u c h better us ing real cel lular data. Fang et al. demonstrated i n [37] and [38] that channel occupancy t imes i n a cel lular network depend not o n l y o n c a l l ho ld ing times but also on users ' m o b i l i t y w h i c h can be characterized b y c e l l residence t ime distr ibution. In [20], the authors showed that channel occupancy t ime is exponent ia l ly distributed o n l y i f c e l l residence t ime is exponent ia l ly distributed. Yet , it is also observed i n the same study that channel occupancy t ime distr ibution have a good approximat ion b y exponential dis t r ibut ion i n general w h e n the m o b i l i t y is low. 5 Barce lo and Jordan analyzed a ce l lu lar network based o n a fu l ly empi r i ca l approach i n [39] and observed that channel occupancy is less spread out than i f exponent ial dis t r ibut ion was assumed. M a r k o v cha in mode ls are developed to evaluate performance analy t ica l ly i n cel lular networks. C a l l s a r r iv ing to a part icular c e l l are grouped into Q o S classes or ca l l types, such as new and handoff, based on their first appearance i n the corresponding ce l l . Channe l occupancy t imes for each group are measured from c a l l starting t ime t i l l the occupied channel i n the respective ce l l is discarded due to ca l l terminat ion or handoff. However , ca l l ho ld ing t imes are measured f rom ca l l starting t ime t i l l c a l l terminat ion regardless o f occupy ing a channel i n the same c e l l or not. The characteristics o f var ious types o f channel occupancy t imes are needed to be analyzed to provide suff icient ly representative channel occupancy t ime statistics not o n l y w h e n developing analyt ica l models but also for feeding simulat ions w i t h realist ic traffic statistics to obtain network performance metrics. The rest o f this chapter is organized as fo l lows : Sec t ion 1.1 discusses the motivat ions and objectives o f our w o r k . Sec t ion 1.2 presents an ove rv iew o f our contributions. Sect ion 1.3 describes the organizat ion o f this dissertation. 1.1 Motivations and Objectives M a n y guard channel based ca l l admiss ion control schemes have been proposed to provide the desired qua l i ty o f service to new and handoff cal ls i n ce l lu lar networks. One d imens iona l M a r k o v cha in m o d e l i n g is generally used under specif ic assumptions to compute b l o c k i n g and d ropp ing probabi l i t ies o f these cal ls approximate ly to avo id so lv ing large sets o f f low equations that makes exact analysis o f these schemes us ing mul t id imens iona l M a r k o v chain models infeasible. The " t radi t ional" approximat ion method provides accurate results on ly w h e n channel occupancy t imes for new and handoff cal ls have equal mean values w h i l e the " n o r m a l i z e d " approach relaxes this assumption o n l y for the new c a l l bounding c a l l admiss ion control scheme. Yet , these assumptions m a y not be appropriate since these two types o f cal ls m a y have different average channel occupancy t imes i f not different distributions [19] [20]. T h i s motivates us to develop an accurate yet easy to implement method to compute new and handoff c a l l b l o c k i n g and d ropp ing probabi l i t ies for several w i d e l y k n o w n c a l l admiss ion control schemes when channel occupancy t imes for new and 6 handoff cal ls have separate mean values. A w i d e var ie ty o f ne twork applications that range f rom text-based to mul t imed ia util i t ies are p rov ided b y ce l lu lar networks a long w i t h basic vo i ce services. These util i t ies are grouped under var ious qua l i ty o f service classes and a higher p r io r i ty is no rma l ly assigned to calls w i t h higher bandwid th and lower latency requirements based o n the application's importance for ce l lu lar network operator. C a l l admiss ion control schemes are also used to opt imize c a l l b l o c k i n g and dropping probabil i t ies o f these applicat ions for qual i ty o f service p rov i s ion ing i n ce l lu la r networks. Performances o f these c a l l admiss ion control schemes are evaluated us ing either one d imens iona l or mul t id imens iona l M a r k o v cha in models w i t h the former preferred over the latter to avo id so lv ing large sets o f f l ow equations. A computat ional ly efficient so lu t ion is also important for qual i ty o f service p rov i s ion ing when dynamic c a l l admiss ion control schemes are used since efficient adaptive reservation depends on rel iable and up to date system status feedback s imul taneously p rov ided to the ca l l admiss ion control mechan i sm. However , re lax ing the assumptions to have separate mean values for channel occupancy times o f different classes o f cal ls is not sufficient to evaluate mult i -service ce l lu la r networks us ing approximat ion methods based on one d imensional M a r k o v cha in m ode l i ng . W h e n assumptions are relaxed further to have cal ls w i t h separate capacity requirements, p rev ious ly developed one d imens iona l M a r k o v cha in models become obsolete due to the mul t id imens iona l i ty introduced b y cal ls w i t h unequal bandwid th requests. Bors t and M i t r a proposed an approximat ion method [34] w i t h a c losed form and therefore a fast solut ion, but it o n l y approximates sufficiently accurately w h e n the number o f exis t ing ca l l arr ival types are h igh . The need for an accurate and computa t ional ly efficient performance evaluat ion approximat ion method for c a l l admiss ion cont ro l schemes motivates us to develop an easy to implement method to compute c a l l b l o c k i n g and dropping probabil i t ies o f different classes o f cal ls i n mult i -service ce l lu lar networks. Packet -swi tched services are over la id on c i rcu i t - swi tched technology over the same air interface to use the access capaci ty i n ce l lu lar networks. Statist ical m u l t i p l e x i n g is used to transmit data packets over radio interface to provide a qual i ty o f service leve l comparable to that o f c i rcu i t - swi tched services. Accura te vo ice traffic statistics are needed to understand the dis tr ibut ion o f id le periods o f vo ice channels to mul t ip lex more than one service on to the same radio channel . In c lass ica l vo ice traffic mode l i ng c a l l h o l d i n g t imes are approximated 7 by exponential d is t r ibut ion and this assumption is w i d e l y used due to its tractabil i ty to obtain analyt ical results for evaluat ing ce l lu lar networks [6] [7] [15] [21] [22] [34]. H o w e v e r it has been shown that a lognormal dis t r ibut ion approximat ion fits m u c h closer [36] [39]. In a cel lular ne twork w h e n a c a l l admiss ion control scheme is mode led for each ce l l , a r r iv ing calls to a part icular c e l l are grouped into qual i ty o f service classes or c a l l types, such as new and handoff, based o n their first appearance i n the corresponding c e l l . Channe l occupancy time dis tr ibut ion for each group includes respective channel occupancy t imes counted o n l y unt i l the corresponding cal ls discard the occupied channels i n the c e l l due to ca l l termination or handoff. C a l l h o l d i n g t ime dis t r ibut ion, on the other hand, includes the amount o f times that the channels are occup ied b y a ca l l un t i l it terminates either i n its or ig inat ing ce l l or another. The above d i scuss ion mot ives us to provide sufficiently representative channel occupancy t ime statistics to develop analyt ical models since ca l l h o l d i n g t ime statistics are not sufficient alone. Th i s is also ve ry useful for feeding simulat ions w i t h realist ic traffic statistics to obtain network performance metr ics . 1.2 Main Contributions The m a i n contr ibutions o f this dissertation are as fo l lows : • Develop a computationally efficient approximation method to evaluate performance of call admission control schemes in single service cellular networks: W e propose an easy to implement approximat ion method to evaluate ca l l admiss ion cont ro l schemes when average channel occupancy t imes for new and handoff cal ls are not necessari ly equal. O u r proposed approximat ion method yields more accurate results compared w i t h the p rev ious ly proposed " t radi t ional" and " n o r m a l i z e d " methods w h i l e keeping the computat ional c o m p l e x i t y low. • Develop computationally efficient approximation methods to evaluate performance of call admission control schemes in multi-service cellular networks: W e class i fy c a l l admiss ion control schemes into two categories cal led symmetr ic and asymmetr ic . W e present the product fo rm solu t ion formula to evaluate symmetr ic c a l l admiss ion control schemes and propose a nove l performance evaluat ion approximat ion method to evaluate asymmetr ic c a l l admiss ion control 8 schemes w h e n average channel occupancy times for different classes o f cal ls are not necessari ly equal and a l l a r r iv ing cal ls m a y have dist inct capaci ty requirements. The proposed method performs better i n accuracy compared to the p rev ious ly proposed method b y Bors t and M i t r a w h i l e keeping the computat ional c o m p l e x i t y low. • Statistical modeling of channel occupancy times for voice service in cellular networks: W e present an empi r i ca l approach to determine the probabi l i ty distr ibution functions that fit var ious types o f channel occupancy t imes i n ce l lu lar networks. W e show that these channel occupancy t imes can be approximated b y lognormal dis tr ibut ion. • Statistical modeling of call holding times for stationary and mobile users along with the number of handoffs committed by a mobile user in cellular networks: W e show that the closest fit candidate to approximate stationary and mob i l e users' ca l l ho ld ing t imes is l ognormal dis t r ibut ion a long w i t h the dis t r ibut ion o f the number o f handoffs commi t t ed b y a mob i l e user. 1.3 Organization of the Dissertation T h i s dissertation is organized as fo l lows. In chapter 2, w e propose a computat ional ly efficient approximat ion method to evaluate performance o f c a l l admiss ion control schemes i n single service ce l lu la r networks. W e reevaluate the analyt ica l methods for comput ing new/handoff c a l l b lock ing /d ropp ing probabil i t ies for w i d e l y k n o w n c a l l admiss ion control schemes and show that the proposed approach gives more accurate results under relaxed assumptions w h e n compared w i t h the exis t ing methods. In chapter 3, w e propose computat ional ly efficient approximat ion methods to evaluate performance o f c a l l admiss ion control schemes i n mul t i - serv ice cel lu lar networks assuming that average values for channel occupancy t imes o f different classes o f cal ls are not equal and a l l a r r iv ing cal ls have different capacity requirements. W e present the numer ica l results that show the proposed methods provide results that match w e l l w i t h the exact solutions w h i l e keeping the computat ional complex i ty low. In chapter 4, w e determine the probabi l i ty d is t r ibut ion functions that fit various types o f channel occupancy times i n ce l lu lar networks and show that these channel occupancy t imes can be approximated by lognormal dis t r ibut ion. W e also show that the closest fit candidate to approximate stationary and m o b i l e users ' c a l l ho ld ing times is 9 lognormal dis t r ibut ion a long w i t h the dis tr ibut ion o f the number o f handoffs commit ted by a mobi le user. Chapter 5 concludes the thesis w i t h a summary o f the presented work , and describes the future w o r k s . 10 1.4 Bibliography [I] D . E . Ever i t t , "Traff ic engineering o f the radio interface for ce l lu la r mob i l e networks," Proc. IEEE, v o l . 82, no. 9, pp.1371-1382, 1994. [2] H . C h e n , L . H u a n g , S. K u m a r , and C . C . J . K u o , Radio Resource Management for Multimedia QoS Support in Wireless Networks. Bos ton : K l u w e r A c a d e m i c Publishers , 2004, chapter 2. [3] D . H o n g and S. S. Rappaport , "Traff ic mode l and performance analysis for cel lular mob i l e radiotelephone systems w i t h pr ior i t i zed and non-pr ior i t ized handoff procedures," IEEE Transactions on Vehicular Technology, v o l . 35, pp. 77-92, A u g . 1986. [4] B . L i , C . L i n , and S. T. Chanson , " A n a l y s i s o f a h y b r i d cu tof f p r ior i ty scheme for mul t ip le classes o f traffic i n mul t imed ia wireless ne tworks ," Wireless Networks, v o l . 4, no. 4, pp. 279-290, J u l y 1998. [5] Y . B . L i n , S. M o h a n , and A . Noerpe l , " Q u e u i n g p r io r i ty channel assignment strategies for handoff and in i t i a l access for a P C S network," IEEE Transactions on Vehicular Technology, v o l . 43 , no. 3, pp. 704-712, A u g . 1994. [6] R . Ramjee, R . Nagarajan, and D . Towsley, " O n op t ima l c a l l admiss ion control i n cel lu lar ne tworks ," Wireless Networks, v o l . 3, no. 1, pp. 29-41 , M a r c h 1997. [7] Y . Fang , and Y . Z h a n g , " C a l l admiss ion control schemes and performance analysis i n wireless m o b i l e ne tworks ," IEEE Transactions on Vehicular Technology, v o l . 51, no.2, pp. 371-382, M a r c h 2002. [8] M . D . Kulavaratharasah, and A . H . A g h v a m i , "Teletraffic performance evaluation o f m i c r o c e l l personal communica t ion networks ( P C N s ) w i t h p r io r i t i zed handoff procedures," IEEE Transactions on Vehicular Technology, v o l . 48 , no. 1, pp. 137-152, Jan. 1999. [9] R . A . G u e r i n , " Q u e u i n g - b l o c k i n g system w i t h two arr ival streams and guard channels," IEEE Transactions on Communications, v o l . 36, no. 2, pp. 153-163, Feb . 1988. [10] E . D . R e , R . Fan tacc i , and G. Giambene , "Handover queuing strategies w i t h dynamic and f ixed channel a l loca t ion techniques i n l o w earth orbit m o b i l e satellite systems," IEEE Transactions on Communications, v o l . 47, no. 1, pp. 89-102, Jan. 1999. [ I I ] C . H . Y o o n , and C . K . U n , "Performance o f personal portable radio telephone systems w i t h or wi thout guard channels ," IEEE Journal on Selected Areas in Communications, v o l . 11, no. 6, pp. 911-917, A u g . 1993. 11 [12] C . Chang , C . J . C h a n g , and K . R . L o , " A n a l y s i s o f a h ierarchica l ce l lu lar system w i t h reneging and dropp ing for wa i t i ng new cal ls and handoff ca l l s , " IEEE Transactions on Vehicular Technology, v o l . 48 , no. 4, pp. 1080-1091, J u l y 1999. [13] V . K . N . L a u , and S. V . M a r i e , " M o b i l i t y o f queued c a l l requests o f a new ca l l queuing technique for ce l lu lar systems," IEEE Transactions on Vehicular Technology, v o l . 47, no. 2, pp. 480-488, M a y 1998. [14] A . S. A c a m p o r a and M . Naghsh ineh , " C o n t r o l and qual i ty o f service p rov i s ion ing i n high-speed mic ro -ce l lu l a r ne tworks ," IEEE Personal Communications, v o l . 1, no. 2, pp. 36-43, 1996. [15] M . Naghsh ineh and S. Schwar tz , "Dis t r ibuted ca l l admiss ion control i n mobi le /wire less ne tworks ," IEEE Journal on Selected Areas in Communications, v o l . 14, no. 4, pp. 711-717, M a y 1996. [16] D . L e v i n e , I. A k y i l d i z , and M . Naghshineh , " A resource est imation and c a l l admiss ion a lgor i thm for wireless mu l t imed ia networks us ing the shadow cluster concept," IEEE/ACM Transactions on Networking, v o l . 5, no. 1, pp. 1-12, Feb . 1997. [17] C . O l i v e i r a , J . B . K i m , and T. Suda, " A n adaptive bandwid th reservation scheme for high-speed m u l t i m e d i a wireless ne tworks ," IEEE Journal on Selected Areas in Communications, vol. 16, pp. 858-874, A u g . 1998. [18] R Ramanathan, K . M . S iva l i ngam, R A g r a w a l , and S. K i s h o r e , " D y n a m i c resource a l locat ion schemes dur ing handoff for mob i l e m u l t i m e d i a wireless networks ," IEEE Journal on Selected Areas in Communications, v o l . 17, no. 7, pp. 1270-1283, Ju ly 1999. [19] Y . F a n g and I. Ch lamtac , "Teletraffic analysis and m o b i l i t y mode l i ng for P C S networks ," IEEE Transactions on Communications, v o l . 47 , pp. 1062-1072, J u l y 1999. [20] Y . Fang , I. Ch lamtac , and Y . B . L i n , "Channe l occupancy t imes and handoff rate for mob i l e comput ing and P C S networks," IEEE Transactions on Computers, v o l . 47, pp. 679-692, June 1998. [21] E . A . Y a v u z and V . C . M . L e u n g , "Computa t iona l ly efficient method to evaluate the performance o f guard-channel-based c a l l admiss ion control i n ce l lu lar networks ," IEEE Transactions on Vehicular Technology, v o l . 55, no. 4, pp. 1412-1424, J u l y 2006. [22] A . Gersht and K . J . L e e , " A bandwidth management strategy i n A T M networks," Technica l report, G T E Laboratories , 1990. [23] J . W . Roberts , "Teletraffic models for the Te lecom 1 integrated services network," Proceedings of the 10th International Teletraffic Conference, M o n t r e a l , 1983. [24] W . L i and X . C h a o , " M o d e l i n g and performance evaluat ion o f a cel lular mob i l e network," IEEE/ACM Transactions on Networking, v o l . 12, no. 1, Feb . 2004. 12 [25] S. S. Rappaport , " T h e mul t ip le ca l l handoff p rob lem i n personal communicat ions ne tworks ," IEEE 40th Vehicular Technology Conference, pp. 2 8 7 - 2 9 4 , M a y 1990. [26] S. S. Rappaport and G. M o n t e , " B l o c k i n g , hand-off and traffic performance for cel lular communica t i on systems w i t h m i x e d platforms," IEEE 42" Vehicular Technology Conference, v o l . 2, pp. 1018-1021 , M a y 1992. [27] L . H u a n g , S. K u m a r and C . C . J . K u o , " A d a p t i v e resource a l loca t ion for mul t imed ia services i n wire less communica t ion networks ," Distributed Computing Systems Workshop, 2001 International Conference on, 2001 , pp. 307 - 312. [28] L . Q i u , R X i a and J . Z h u , "S tudy on wideband C D M A modula t ion , power control and wireless access for C D M A mul t imed ia systems," Proceedings of IEEE 50th Vehicular Technology Conference, v o l . 5, pp. 2944 - 2948, 1999. [29] S. C h e n and K . Nahrstedt, "Dis t r ibuted qual i ty o f service rout ing i n ad-hoc networks," IEEE Journal on Selected Areas in Communications, v o l . 17, no. 8, Augus t , 1999. [30] I T U - T S G 1 6 / Q . 1 5 v ideo cod ing experts group, I T U - T recommendat ion H . 2 6 3 : V i d e o cod ing for l o w bit rate communica t ion , October 1995. [31] R . G u e r i n , "Equ iva len t capaci ty and its appl ica t ion to bandwid th a l locat ion i n high-speed ne tworks ," IEEE Journal on Selected Areas in Communications, v o l . 9, no. 7, pp. 968-981 , Sept. 1991. [32] J . S. Evans and D . Everi t t , "Effect ive bandwidth-based admiss ion control for mul t i -service C D M A cel lu lar networks ," IEEE Transactions on Vehicular Technology, v o l . 48 , no. 1, Jan. 1999. [33] Q . R e n and G. Ramamurthy , " A real-t ime dynamic connect ion admiss ion controller based on traffic mode l ing , measurement, and fuzzy log ic con t ro l , " IEEE Journal on Selected Areas in Communications, v o l . 18, no. 2, Feb . 2000. [34] S. C . Bors t and D . M i t r a , " V i r t u a l par t i t ioning for robust resource sharing: computat ional techniques for heterogeneous traffic," IEEE Journal on Selected Areas in Communications, v o l . 16, no. 5, pp. 668-678, June 1998. [35] R . A . G u e r i n , " C h a n n e l occupancy t ime dis tr ibut ion i n a ce l lu lar radio system," IEEE Transactions Vehicular Technology, v o l . 35, no. 3, pp. 89-99, 1987. [36] C . J ed rzyck i , and V . C . M . L e u n g , "Probab i l i ty dis t r ibut ion o f channel ho ld ing t ime i n cel lu lar te lephony systems," IEEE Vehicular Technology Conference (VTC'96), v o l . 1, pp. 247 - 2 5 1 , A p r . 1996. [37] Y . Fang , I. Ch lamtac , and Y . B . L i n , " C a l l performance for a P C S network," IEEE Journal on Selected Areas in Communications v o l . 15, no. 8, pp. 1568-1581 , Oct . 1997. 13 [38] Y . Fang , I. Ch lamtac , and Y . B . L i n , " M o d e l i n g P C S networks under general ca l l ho ld ing t imes and c e l l residence t ime distr ibut ions," IEEE Transactions on Networking v o l . 5, no. 6, pp. 893 - 906, D e c . 1997. [39] F. B a r c e l o , and J . Jordan, "Channe l ho ld ing t ime dis t r ibut ion i n pub l ic telephony systems ( P A M R and P C S ) , " IEEE Transactions on Vehicular Technology, v o l . 49, no. 5, pp. 1615-1625, Sep. 2000. 14 C H A P T E R 2 COMPUTATIONALLY EFFICIENT METHOD TO EVALUATE THE PERFORMANCE O F GUARD-CHANNEL-BASED CALL ADMISSION CONTROL IN CELLULAR NETWORKS1 2.1 Introduction The emerging g loba l standards for wireless c o m m u n i c a t i o n networks, such as the third generation ( 3 G ) ce l lu la r networks, promise the eff ic iency and f l ex ib i l i t y o f mu l t i p l ex ing a w ide variety o f traffic f rom convent ional c i rcui t -swi tched vo i ce service to packet-switched voice , data, and m u l t i m e d i a services w h i l e p rov id ing the qual i ty o f service (QoS) expected by service subscribers and their applications. Services w i t h specif ic bandwid th and latency requirements need specif ic amount o f system resources to be al located at the t ime o f ca l l admiss ion to ensure that the required Q o S can be mainta ined dur ing the ca l l . The performance o f c a l l admiss ion control ( C A C ) i n a ce l lu lar ne twork is specified b y the b l o c k i n g p robab i l i ty o f new cal ls i n a ce l l and dropping probabi l i t ies o f handoff cal ls entering a ce l l . C a l l d ropping m a y occur before a ca l l is terminated b y the communica t ing parties i f the cel lular network is unable to assign network resources to enable the c a l l to be handed o f f to a new c e l l that the m o b i l e user has m o v e d into. N e t w o r k planners need to p rov i s ion sufficient network resources such as channel bandwidth to ensure that c a l l b lock ing /dropp ing probabil i t ies stay w i t h i n acceptable l imi t s for various c a l l types or applications. Since dropping an on-go ing c a l l is general ly more objectionable to a m o b i l e user than b l o c k i n g a new ca l l request, a higher pr ior i ty is no rmal ly assigned i n C A C for handoff cal ls over the new ones i n order to m i n i m i z e the ca l l dropping probabil i ty . C a l l admiss ion control for wireless networks has been in tens ive ly studied i n the past [1] [2] and m a n y pr ior i ty-based C A C schemes have been proposed [3]-[18]. In the context o f a g iven number o f channels be ing avai lable i n each c e l l for assignment to admitted calls , 1 A version of this chapter has been published. E. A. Yavuz and V. C. M . Leung, "Computationally Efficient Method to Evaluate the Performance of Guard-Channel-Based Call Admission Control in Cellular Networks," IEEE Transactions on Vehicular Technology, vol. 55, no. 4, pp.1412-1424, July 2006. 15 these C A C schemes can be c lass i f ied into two broad categories. 1) Guard Channel (GC) Schemes: A number o f guard channels are reserved for handoff cal ls . There are four different schemes. a) The cutoff priority scheme b locks a new c a l l i f the number o f free channels is less than the number o f guard channels reserved for handoff ca l l s [3]-[5]. b) The fractional guard channel scheme admits a new c a l l w i t h certain probabi l i ty that depends o n the number o f busy channels i n the c e l l [6]. c) The new call bounding scheme l imi ts the number o f new cal ls admitted to the ce l l to some number less than the total number o f avai lable channels [7]. d) The rigid division-based scheme d ivides a l l channels avai lable i n a ce l l into two groups: one for c o m m o n use and the other o n l y for handof f cal ls [8]. 2) Queuing Priority (QP) Schemes: C a l l s are accepted whenever there are free channels; otherwise either new cal ls are queued w h i l e handoff cal ls are dropped [9], new calls are b l o c k e d w h i l e handoff cal ls are queued [10][11], or a l l a r r iv ing cal ls are queued w i t h certain rearrangements i n the queue [12] [13]. In addi t ion to those g iven above, many dynamic G C schemes [14]-[18] have also been discussed i n the literature to improve system efficiency. These dynamic schemes manage to accept more lower-pr ior i ty cal ls as compared to the f ixed schemes b y adaptively reserving the amount o f resources needed for h igh-pr ior i ty cal ls . In the literature C A C schemes are analyzed us ing M a r k o v cha in models based on a c i rcui t -swi tched ne twork architecture w i t h the assumption that independent Po i s son distributed c a l l requests are originated from different classes o f service or c a l l types, ce l l residence t ime for each c a l l is exponent ia l ly distributed, and each c a l l requires a predetermined channel bandwidth . Convent iona l c i rcu i t - swi tched services inc lud ing telephony are gradual ly be ing replaced b y packet-switched ones as today's communica t ion networks evolve . Conven t iona l C A C schemes, on the other hand, w i l l continue to be useful when appl ied w i t h suitable schedul ing techniques to guarantee Q o S at the packet level since most applicat ions such as interactive mul t imed ia are inherently connect ion oriented and packet-switched connect ions can be provis ioned according to their effective bandwidths [19]-[33]. To avo id the computat ional complex i ty o f s o l v i n g mu l t i d imens iona l M a r k o v chain 16 models , one d imens iona l M a r k o v chain models are c o m m o n l y used (e.g., [11][15]) to obtain the b lock ing /d ropp ing probabi l i t ies for new/handoff cal ls under the assumption that the channel occupancy t imes for both types o f cal ls are iden t ica l ly distr ibuted w i t h the same average values. Ye t this assumption m a y not be appropriate as new and handoff calls m a y have different average channel occupancy times i f not different distr ibutions, as shown i n [19][20] and references therein. E v e n though analysis i n [7] accounts for the more general case o f different average channel occupancy t imes for new and handoff cal ls , the approximat ion emp loyed s t i l l leads to significant discrepancies w i t h the exact solutions. In [22], L i and C h a o mode l ed a m u l t i - c e l l wireless network e m p l o y i n g a h y b r i d GCIQP scheme w i t h transfer o f unsuccessful requests to neighbor ing cel ls as a ne twork o f queues and obtained a product fo rm solut ion. However , the solut ion is restrictive to the protocol considered and m a y not be appl icable for performance evaluations o f GC schemes i n general. Thus , us ing mul t id imens iona l M a r k o v chain models appears to be the on ly means to obtain accurate solut ions for the analysis o f GC schemes. T h i s approach is used i n [22] to evaluate a ce l lu lar ne twork ' s performance b y determining the new c a l l b l o c k i n g and handoff ca l l d ropping probabi l i t ies , and is extended i n [26] to analyze the traffic performance taking into considerat ion the effects o f various types o f mob i l e platforms dis t inguished by different m o b i l i t y characteristics. E v e n though the mul t id imens iona l M a r k o v cha in mode l is capable o f p rov id ing the exact results, the method suffers f rom the curse o f dimensional i ty , w h i c h results i n ve ry h i g h computat ional cost for large systems. Therefore it is s t i l l desirable to come up w i t h approximate solutions that have h igh accuracy and is computa t ional ly efficient. In this chapter, w e propose a nove l method ca l led the "effective holding time''' approach to compute the above-mentioned C A C performance metrics us ing an approximat ion based o n one d imens iona l M a r k o v cha in m o d e l i n g under the condi t ion that the channel occupancy t imes for new and handoff cal ls are independent and exponent ial ly distributed w i t h different average values. The proposed method is easy to implement and has l o w computat ional cost. Th i s chapter is organized as fo l lows . In the next section w e examine three o f the w i d e l y k n o w n C A C schemes b y evaluating their performances us ing the traditional and the normalized analyt ica l methods proposed i n the literature under the assumption that the new and handoff cal ls have different average channel occupancy times. In Sec t ion 2.3, we present 17 the new analyt ical me thod based o n effective holding time, w h i c h y ie lds more accurate approximations than the tradit ional or normal ized methods. In addi t ion to the numerica l results obtained us ing the tradit ional , normal ized , proposed and the direct methods, the accuracy o f the results are also presented and compared a long w i t h the runtime computat ional costs i n Sec t ion 2.4. W e w i l l conclude the paper i n Sec t ion 2.5. 2.2 Existing Methods to Analyze Performance of C A C Schemes In this section w e examine three o f the w i d e l y k n o w n C A C schemes: the new call bounding priority, the cutoff priority, and the fractional guard channel schemes b y evaluating their performance us ing the traditional and the normalized analyt ical methods proposed i n the literature under the assumption that the new and handoff cal ls have different average channel occupancy t imes. Le t A„ and Xn denote the ar r ival rates and 1/JU„ and l/p„ denote the average channel occupancy t imes for new and handoff cal ls , respectively. Le t C denote the total number o f channels i n a c e l l . W e assume that the arr ival processes for new and handoff calls are Poisson , and the channel occupancy times for new cal ls and handoff cal ls are exponent ial ly distributed. A s s u m i n g that both new and handoff calls have the same channel occupancy t ime distributions and average values, the system m o d e l is approximated b y a one d imensional M a r k o v cha in w i t h a f ixed average channel occupancy t ime for the total c e l l traffic. W e refer to this method o f de r iv ing b lock ing /dropp ing probabi l i t ies ana ly t ica l ly as the traditional approach [3][6][7][10][11]. To improve the inaccurate results obtained when the above assumption o n equal average channel occupancy t ime is no longer v a l i d , F a n g and Z h a n g [7] proposed n o r m a l i z i n g the average service times for new and handoff traffic to uni ty so that they become ident ica l for both streams. A l t h o u g h this approximat ion , w h i c h w e ca l l the normalized approach, seems to give better accuracy than the t radi t ional approach, it is s t i l l inaccurate especia l ly for C A C schemes l ike cutoff pr ior i ty and fractional guard channel. 2.2.1 N e w C a l l B o u n d i n g S c h e m e F i g . 2.1 shows the state transit ion diagram for the new c a l l bound ing scheme modeled 18 b y a two-d imens iona l M a r k o v chain , where kn, A/„ un, un and C are as defined before and K is the threshold between 0 and C such that a new ca l l request is admitted o n l y when there are less than K channels occup ied b y new cal ls . Le t p{n\,n2) denote the steady state probabi l i ty that there are n\ new cal ls and n2 handoff cal ls i n the ce l l , w h i c h can be found b y so lv ing the g lobal balance equations obtained from the state transition. Yet as ment ioned above, so lv ing these balance equations becomes computat ional ly ve ry intensive w h e n the state d imens ion increases. A n a l y t i c a l results to compute the b l o c k i n g probabi l i t ies o f new calls pnb and the dropping probabi l i t ies o f handoff cal ls pn(t have been der ived for this scheme i n [7], and an approximat ion is developed b y no rma l i z ing the average service t ime for new and handoff calls . T h i s normalized approach a l lows the ar r iv ing traffic for each type o f ca l l to be scaled appropriately and the b lock ing /d ropp ing probabil i t ies to be related to the traffic intensities. Here is h o w the normalized approach works . Le t p„ = Xn I un and ph = h I Uh, then we can consider an equivalent Po i s son new ca l l arr ival stream w i t h ar r ival rate pn and service rate equal to 1, and an equivalent Po i s son handoff ca l l a r r ival stream w i t h arr ival rate p/t and service rate equal to 1. Le t pa(n\,n2) denote the steady state p robab i l i ty that there are n\ new calls and n2 handoff cal ls i n the ce l l for the normal ized approximat ion mode l . Thus, the f o l l o w i n g stationary dis t r ibut ion is obtained for this approximate m o d e l from the balance equations: n, _ n , pa(nx,n2) = ^LT-^jLT-p"(0,0), 0 < n i <K, nx + n2 < C, n2 > 0, «,! n2\ where P"(0,0) = Pn Ph 0 £ n , < A : , n , + n 2 S C U V W 2 • K n » i C - n , » 2 V " n V P h „ , = o « , ! „ 2 = o n2\ The formulas for new c a l l b l o c k i n g and handoff c a l l d ropping probabi l i t ies are as fo l lows: 19 P n h K n n , C-n, n2 Z Pn y Ph n,=0 " i ! «,=0 " 2 1 „,=o »i! ( C - n , ) ! - (2") «,=0 " | • n,=0 " 2 -O n the other hand, the traditional approach uses the average channel occupancy t ime juav for total ce l l traffic g iven by: 1 - Xn 1 , K 1 = Pn+Ph H ) Pav K+h Pn K+h Ph K+h to replace n„ and JU„ i n (1) and (2) and to obtain new c a l l b l o c k i n g and handoff c a l l dropping probabil i t ies i n the resul t ing one dimensional M a r k o v cha in m o d e l . In that case, the traffic intensities for new and handoff cal ls are g iven by: Pn- — = y^rr-(Pn+ph) P«v + *h ^h / \ Ph =— = . \ -(Pn+Ph) Pav K + K W h e n channel occupancy t imes for both new and handoff cal ls are assumed to be ident ica l ly distr ibuted w i t h the same parameters, the c e l l average channel occupancy t ime also becomes the same as can be easi ly deduced from (3). H o w e v e r , the traditional approach can y i e l d s igni f icant ly inaccurate results w h e n the channel occupancy t imes for new and handoff cal ls have different average values except when the non-pr io r i t i zed scheme (K = C) is used. The normalized approach overcomes this inaccuracy i n the new c a l l bound ing scheme b y exp lo i t ing the symmetr ic nature and the product fo rm o f the detai led balance equations 20 that characterizes this C A C scheme. W e w i l l show i n the f o l l o w i n g sections that both approximations ment ioned above are not good enough to obtain new c a l l b l o c k i n g and handoff ca l l d ropp ing probabi l i t ies w i t h an acceptable accuracy for other C A C schemes. 2 . 2 . 2 C u t o f f P r i o r i t y Scheme Let m < C denote the channel occupancy threshold for acceptance o f new calls . I f the total number o f busy channels is less than m when a new c a l l arrives, the ca l l is accepted; otherwise the n e w c a l l is b locked . A handoff c a l l is a lways accepted i f a free channel is available. T h i s scheme has been extensively studied us ing one d imens iona l M a r k o v chain mode l ing under the assumption that the average channel occupancy t imes o f new and handoff calls are equal [3]. H o w e v e r , this approach provides inaccurate results w h e n the equal mean channel occupancy t ime assumption does not ho ld true. Le t Xn, un, U)„ and C be defined as before. The system can be mode led b y the two dimensional M a r k o v cha in shown i n F i g . 2.2, where (tt\, n2) denotes a feasible state w i t h n\ and n2 representing the numbers o f new and handoff cal ls i n the c e l l , respectively. In contrast w i t h the new c a l l bound ing scheme, the state f lows for the cutoff p r io r i ty scheme no longer have the symmetr ic nature since the f lows for some o f the states are unidi rec t ional , spo i l ing the symmetry as s h o w n w i t h i n circles d rawn i n F i g . 2.1 and F i g . 2.2. Hence , no product form solut ion exists for this scheme w h e n un ^ u„. The f o l l o w i n g stationary dis tr ibut ion is obtained for the cu tof f p r io r i ty scheme us ing the normalized approach, where p" denotes the probabi l i ty that there are / (j = 0, 1, Q busy channels i n the steady state: (Pn + PH)J (p„ + phy-pr.pl^ m+l<j<c where Po = y = 0 J' j=m+l f-21 U s i n g the stationary dis t r ibut ion g iven above, the b l o c k i n g probabi l i t ies for new cal ls , p°b and the d ropp ing probabi l i t ies for handoff cal ls , pahd are obtained as fo l lows : P'L = — J — . — (4) <h(p„+p„y , ^  {P. + P>)M • PC 7=0 ]• j=m+\ J-v" = Q ( 5 ) f(p„+ph)J, f (pn+phr-pr 7=0 J- j=m+\ J-O n the other hand, the corresponding results for the traditional approach i n w h i c h the new and handoff c a l l channel occupancy times are replaced w i t h the average channel occupancy t ime, g iven b y (3), are as fo l lows: t j=m J- Mav Pav Pnb m « 3 , 3 C 7=0 J- P J- Pav Pav p . = Pav Pav G-V J _ . + ^«y + V 1 . ( A + Ky _^ K y-m 7=0 J- fJ-av j=m+\ J- Pav Pa 2.2.3 F r a c t i o n a l G u a r d C h a n n e l S c h e m e The fractional guard channel scheme admits new cal ls w i t h certain probabil i t ies that depend on the number o f busy channels, /. W h e n the number o f busy channels is i, an ar r iv ing new c a l l w i l l be admitted w i t h probabi l i ty / i„ where 0 < 8, < 1, i = 0, 1, . . . , C - l . The new c a l l stream is smooth ly throttled b y decreasing /?, as the network traffic is b u i l d i n g up. A n ar r iv ing handoff c a l l w i l l a lways be admitted unless there is no free channel available, i n 22 w h i c h case a l l cal ls w i l l be b locked . Obv ious ly , this scheme becomes the cutoff pr ior i ty scheme when B0= ... = Pm-i = 1 and Bm = ... = Bc = 0. W h e n B0 > B\ > B2 > ... > Bc, it can also be observed that the new cal ls stream grows at a decreasing rate as the number o f busy channels increases. D u e to this f lexible choice o f new c a l l admiss ion probabil i t ies , the fractional guard channel scheme can be made very general. Le t Xn, Xn, un, Mh, and C be defined as before and let q(c) denote the equ i l ib r ium channel occupancy probab i l i ty when exact ly c channels are occup ied i n a ce l l . It has been shown [27] that q(c) satisfies the f o l l o w i n g recursive equation. ( ^ ^ ± + ^ .).q(c-\) = c-q(c), c = l, . . . ,C (6) R e p l a c i n g the new and handoff ca l l arr ival rates, X„ and Xn, w i t h the new and handoff traffic intensities, pn and ph, respectively, and setting the corresponding channel occupancy times to 1 as suggested b y the normalized approach transform (6) to (A, • Pc-\ + Ph) • <?(c - ! ) = c • l(c)> c = c (7) w h i c h gives us a general expression for a l l GC schemes. c S o l v i n g for #(0) i n the equation ^ q(j) = 1 , w e obtain 7=0 where ft(P.-A+A) g(j)=^ g(0), \<j<c q(0) = 7-1 7=1 Y[(pn-pk+ph) k=0 (8) (9) F r o m (8) and (9), the b l o c k i n g and dropping probabi l i t ies for new and handoff calls 23 for the no rma l i zed approach are respect ively g iven by: c p:h-zZi}-Pj)-q(j), Pc = o (10) P'L = * ( C ) ( i i ) O n the other hand, the corresponding results for the traditional approach can be obtained b y rep lac ing the average channel occupancy t imes o f both types o f cal ls i n (6) w i t h the average channel occupancy t ime o f the total c e l l traffic g iven b y (3). 2.3 The Proposed Performance Evaluation Method E v e n though the normalized approach [7] provides a better approximat ion than the traditional one, it is s t i l l inaccurate for many GC schemes. Therefore, i n order to provide more accurate results w h i l e keeping the computat ional c o m p l e x i t y low, w e present the f o l l o w i n g nove l performance evaluat ion method for GC schemes, referred as the effective holding time approach. S ince it is c ruc ia l to f ind an approximat ion that overcomes the curse o f d imensional i ty when the state d imens ion is large, it is inevitable to attempt reduc ing the two dimensional M a r k o v chain m o d e l to a one d imens iona l one. A s shown previously, this enables a product form solut ion o f the detai led balance equations to be obtained us ing (6). However , w e proceed to s impl i fy (6) b y replacing the average channel occupancy times for both new and handoff cal ls w i t h an average channel occupancy t ime for the total ce l l traffic w h i c h w e refer as the average effective channel occupancy time and denote b y llfieff instead o f \ltiav used b y the traditional approach. The average channel occupancy time, ll/iav, g iven b y (3) can not approximate the value o f the average channel occupancy t ime for the total c e l l traffic accurately, since new and handoff cal ls are not b l o c k e d equally. To obtain 1/jUeff, w e app ly an idea proposed b y Gersht and L e e [28] w h e n deve lop ing an iterative a lgor i thm to calculate approximate occupancy distr ibutions o f objects be ing placed into a knapsack to m a x i m i z e the total reward that is accrued each t ime an object is placed into the knapsack. Inspired b y the w e l l k n o w n Li t t l e ' s theorem, fx = X/N, they defined ue/f as the ratio 24 o f expected number o f both types o f ca l l arrivals to the expected number o f occupied channels, c-i c-i Peff- c ,/=o (12) W e n o w s i m p l y approximate the occupancy probabi l i t ies b y setting q(c) = q(c), c = 0, . . .,C i n (6) and us ing the updated recursive fo rmula g iven be low. (K • + A)• <?(c-1) = c• Meff• «?( c), c = L . . . , C c S o l v i n g for q(0) w i t h X = 1 , we obtain q(j)=——j—* #o)> ^ J ^ c where q(0) = r h v / w . ) *=0 (13) (14) (15) In their knapsack p r o b l e m approach, Gersht and L e e [28] suggested obtaining jue/f us ing (12) b y rep lac ing q(c) w i t h q(c) and updat ing the approximate equ i l ib r ium occupancy probabi l i t ies iteratively, us ing (14) and (15) unt i l each q(c) changes b y no more than e for a l l c = 0,...,C, where e is a smal l number. A l t h o u g h their approach d i d not emphasize starting w i t h an appropriate in i t i a l value for each approximate equ i l i b r i um occupancy probabi l i ty , w e real ize that it becomes a p rob lem since more than one set o f equ i l ib r ium occupancy probabi l i t ies can satisfy (14) and (15) at the same t ime. W h a t makes a set to be the unique solu t ion depends on the values o f 25 the arr ival rates and average channel occupancy t imes o f both types o f cal ls . Therefore, we consider it important that these values are inc luded d i rec t ly i n the computat ion to obtain better approximate results. The c a l l arr ival rates for both types o f cal ls are embraced i n (12), (14) and (15); however w e observe that the average channel occupancy t ime o f each type o f ca l l is not considered di rect ly i n these equations w h e n comput ing the approximate equ i l ib r ium occupancy probabi l i t ies since they are replaced b y the average effective channel occupancy t ime, l/uejf. Hence , w e propose to set the approximate equ i l i b r i um occupancy probabil i t ies in i t i a l ly w i t h the values obtained b y the normalized approach proposed b y F a n g and Zhang [7] i n order to make the approximate equ i l ib r ium occupancy probabi l i t ies closer to the unique solut ion that w e look for, then apply (14) and (15) to obtain the new and handoff ca l l d ropping probabi l i t ies . To summarize , the a lgor i thmic descript ion o f our proposed effective holding time approach is as fo l lows : 1. I n i t i a l i z e e q u i l i b r i u m o c c u p a n c y p r o b a b i l i t i e s q(c) (c = 0 , . . . , C ) b y s e t t i n g t h e m t o t h e c o r r e s p o n d i n g v a l u e s o b t a i n e d f r o m t h e n o r m a l i z e d a p p r o a c h . 2. C a l c u l a t e /ueff u s i n g ( 1 2 ) b y r e p l a c i n g q(c)'s w i t h q(c)'s . 3. C a l c u l a t e q(c) f o r c = 0 , . . . , C u s i n g ( 1 4 ) a n d ( 1 5 ) . 4 . O b t a i n n e w c a l l b l o c k i n g a n d h a n d o f f c a l l d r o p p i n g p r o b a b i l i t i e s u s i n g q(c). A l t h o u g h Gersht and L e e suggested an iterative approach for the solut ion o f the knapsack p rob lem, w e present our approximat ion method i n c losed form since once we compute the effective channel occupancy t ime, ueff, f rom (12) us ing the in i t i a l condit ions obtained from the normalized approach and the corresponding values o f the estimated equ i l ib r ium occupancy probabi l i t ies , q(c), f rom (14) and (15) f o l l o w e d b y that, the value o f the recomputed effective channel occupancy t ime us ing the estimated equ i l i b r i um occupancy probabil i t ies w i l l r emain the same w h i c h w i l l also stabi l ize the values o f the estimated equ i l ib r ium occupancy probabi l i t ies . Af te r the estimated equ i l i b r i um occupancy probabil i t ies 26 are obtained, the new c a l l b l o c k i n g and handoff ca l l d ropping probabi l i t ies are calculated as fo l lows: c-i c-i hd C I 7=0 £V$(./) 7=0 / t f = l - ^ (17) 2.4 Numerical Results 2.4.1 Performance Evaluation of Existing and Proposed Methods In this sect ion w e present numer ica l results o f performance evaluations us ing our nove l effective holding time approach presented i n Sect ion 2.3 and compare them w i t h those obtained us ing the exis t ing traditional and the normalized approaches based on one d imensional M a r k o v cha in models . W e also obtain accurate results us ing a mul t id imens iona l M a r k o v cha in m o d e l for compar i son purposes. T h i s is accompl i shed us ing a numer ica l method ca l led direct (also k n o w n as LU decomposition) to calculate the exact values o f the performance metr ics and the corresponding results are labeled as "direct method" . The numer ica l results obtained for this study not o n l y show that the results obtained from the normalized and the traditional approaches can deviate s ignif icant ly from the accurate results obtained from the direct approach, but also show that our new approach, effective holding time, can achieve results very close to the accurate direct ones. W e do not g ive the results here for the new call bounding scheme since the normalized approach can overcome the inaccuracy o f the traditional approach w h i c h overestimates the n e w c a l l b l o c k i n g probabi l i ty w h i l e it underestimates the handoff ca l l d ropping probab i l i ty w h e n the handoff ca l l traffic is higher than the new c a l l traffic load (i.e., 27 ph > Pn) or v i ce versa b y exp lo i t ing the symmetr ic nature o f the scheme's state transitions and thus leaves l i t t le r o o m for improvement . However , w e focus o n the other schemes considered above for w h i c h this property does not apply. Since fractional guard channel is a general izat ion o f the cutoff priority scheme, we evaluate o n l y the cutoff priority scheme here due to space constraints as same property applies for both schemes. Before examin ing this scheme to evaluate its performance, w e should determine the range o f values that system parameters such as Xn, Xh, l/p.n and l/p.n take i n order to reflect prac t ica l situations. It is general ly accepted i n the literature [3][7][11] to set the ar r ival rate, Xn, and the average channel occupancy t ime, l/pi„, o f new calls i n propor t ion w i t h the arr ival rate, Xh, and the average channel occupancy t ime, 1/uh, o f handoff cal ls , respectively. Therefore f o l l o w i n g the scenarios that have been considered i n the literature, w e apply the values w h i c h are grouped under four different cases and presented i n Table 2.1 as the a r r iva l rates and average channel occupancy t imes for new and handoff cal ls i n order to evaluate the performances o f the selected schemes. To put it shortly, w e assume both ratios, XJXh, p-hlp-n, to have values changing w i t h i n the range o f 4 and 0.5 i n order to cover the scenarios c o m m o n l y considered i n the literature. W e set the total number o f channels, C , to 30 and the channel occupancy threshold, m, to 25 as i n [7]. R e d u c i n g handoff c a l l dropping b y assigning higher pr ior i t ies or other means increases the p robab i l i ty o f b l o c k i n g for new cal ls and thus results i n a tradeoff between these two Q o S measures [6]. Nevertheless , the goal o f a network service provider is to m a x i m i z e the revenue b y i m p r o v i n g network resource u t i l iza t ion , w h i c h is usua l ly associated w i t h m i n i m i z i n g the new c a l l b l o c k i n g probabi l i ty w h i l e keeping the handoff dropping probabi l i ty be low a certain threshold. Hence w e evaluate the approximate evaluat ion methods mentioned above b y grouping the poss ible scenarios into four different cases w i t h parameter values chosen as shown i n Table 2.1 i n order to obtain handoff c a l l d ropping probabil i t ies w i t h i n the range o f 0.01 and 0.1 since this is the interval o f interest w h e n p r o v i d i n g Q o S guarantees i n a cel lular network. In the literature the c o m m o n l y accepted method to evaluate a scheme is to simulate a system mode led w i t h that scheme w i t h c a l l arr ival rates be ing va r i ed to change the traffic load w h i l e the average channel occupancy times o f different types o f cal ls are kept constant. 28 However , cons ider ing that the objective o f this study is to re lax the assumption made b y prev ious ly suggested approx imat ion methods for different types o f cal ls to have different average channel occupancy t imes, w e simulate the system b y v a r y i n g the average channel occupancy t imes instead as i n [7], since hav ing different average channel occupancy times for new and handoff ca l l s is what makes the exis t ing methods inaccurate. One can also notice that b lock ing /d ropp ing probab i l i ty values obtained b y (4) and (5) or (8) and (9), w h i c h were der ived for cutoff priority and fractional guard channel schemes, respectively, b y us ing the normalized approach, r ema in the same as long as the c a l l a r r ival rates and average channel occupancy t imes change w i t h same proportions, thus keeping the traffic loads for both types o f cal ls , ph and p„, constant. Yet , the direct method is expected to g ive different results i n such a case as it considers the c a l l a r r ival rates and average channel occupancy times separately. Cons ide r ing that average channel occupancy times p l ay a stronger role compared to ca l l arr ival rates w h e n obta in ing c a l l b l o c k i n g probabil i t ies accurately us ing g iven approximat ion methods, va ry ing average channel occupancy times o f both types o f cal ls i n proport ion w i t h each other can be jus t i f i ed as w e expect that it w o u l d be more cha l lenging to obtain accurate results w h e n differences i n average channel occupancy t imes exist. In F ig s . 2.3-2.10, w e show the new ca l l b l o c k i n g and handoff ca l l dropping probabil i t ies computed b y the ment ioned approaches for each case g iven i n Table 2.1. In F igs . 2.3 and 2.4, for s imula t ion scenario 1, it is observed that as the new c a l l traffic load gets higher, the t radi t ional approach overestimates both the new c a l l b l o c k i n g and handoff c a l l d ropping probabi l i t ies b y the largest marg in w h i l e the no rma l i zed approach underestimates the handoff ca l l d ropp ing probabil i ty. However , the results obtained b y our proposed effective holding time approximat ion method match the curve obtained b y us ing the direct method very w e l l . A s imi la r conc lu s ion can be drawn for the comparisons o f new ca l l b l o c k i n g and handoff c a l l d ropp ing probabi l i t ies f rom F igs . 2.5 and 2.6 for s imula t ion scenario 2, F igs . 2.7 and 2.8 for scenario 3 and F i g s . 2.9 and 2.10 for scenario 4, respectively. A s expected and mentioned above, w e observe f rom F igs . 2.2, 2.4, 2.6 and 2.8 that the results obtained b y the proposed approx imat ion method diverge from the exact ones s l o w l y w h e n the ratio o f average channel occupancy t imes for new to handoff cal ls increases. In short, when the new and handoff cal ls have different average channel occupancy t imes, the traditional and the normalized approaches result i n significant discrepancies compared to the direct method 29 especial ly w i t h respect to handoff c a l l dropping probabil i ty , w h i c h is overestimated b y the former approach w h i l e it is underestimated b y the latter one. H o w e v e r , the results obtained by the proposed approach can overcome such inaccuracy. 2.4.2 A c c u r a c y a n d R u n t i m e C o m p u t a t i o n a l Cos t s In this sect ion w e examine the accuracy o f traditional, normalized, and the proposed effective holding time approximat ion methods b y us ing the "mean average error ( M A E ) " and the "root mean square error ( R M S E ) " w h i c h are calculated as g iven below. The results are g iven i n Table 2.2 for handoff ca l l d ropping and Table 2.3 for new c a l l b l o c k i n g probabi l i t ies . Further to the results i n F ig s . 2.3-2.10, the most significant results on accuracy are shown i n Table 2.2 for handoff ca l l d ropping probabi l i t ies , where our proposed effective holding time approximat ion method reduces est imation errors substantially compared to the exis t ing approximat ion methods. E v e n though our proposed method estimates the new c a l l b l o c k i n g probabil i t ies w i t h very smal l errors as shown i n Table 2.3, it does not s igni f icant ly reduce them w i t h respect to the est imation errors g iven b y the exis t ing methods due to the re la t ive ly sma l l error margins. The percentage gains i n accuracy o f the results on handoff c a l l d ropping probabi l i ty obtained b y the proposed approximat ion method relative to those obtained b y the normalized and the traditional methods are g iven i n Table 2.4. The percentage gains i n accuracy o f the results o n new c a l l b l o c k i n g probabi l i ty obtained b y the proposed approximat ion method are not g iven here since they are ve ry smal l compared w i t h the results o n handoff ca l l dropping shown i n Table 2.4. In Table 2.4, it is observed that the percentage gains i n estimation accuracy p rov ided b y our proposed approximat ion method relat ive to the exis t ing methods decrease as the ratio o f new to handoff ca l l ho ld ing t imes decreases even though the gains 1 abs(p Pi,real) (18) (19) 30 obtained s t i l l r emain significant. The reason w h y an acceptable approximat ion method is needed to evaluate the performance o f a c a l l admiss ion control scheme when an exact so lu t ion w i t h a numerica l method based o n mul t id imens iona l M a r k o v chain m o d e l i n g exists, is to avo id so lv ing large sets o f f low equations and therefore the curse o f dimensional i ty . To give the reader a better idea regarding the "CPU time" and the amount o f "memory used for evaluating the performance o f any o f the pol ic ies mentioned above, we implement one direct and