LOCATION UPDATING AND PAGINGSTRATEGIES IN A CELLULAR SYSTEMbyKENNY C. H. LAMB.A.Sc (Hons.), The University of British Columbia, 1991A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF ELECTRICAL ENGINEERINGWe accept this thesis as conforming to the required standardTHE UNIVERSITY OF BRITISH COLUMBIAApril 1993© Kenny C. H. Lam, 1993In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature) Department ofThe University of British ColumbiaVancouver, CanadaDateDE-6 (2/88)ABSTRACTThe problem of locating a mobile user in a cellular system is addressed. The mobility ofa user is modelled by a two-dimensional directional random walk process. A location updatingscheme based on overlapping location areas (LA's) is presented for keeping track of the LA auser is in. Two LA paging schemes, namely spread paging and selective paging, are proposedand are compared to a conventional flood paging scheme in which all cells in the LA are pagedsimultaneously. It is found that both spread paging and selective paging can yield typical pagingtraffic reductions of more than 50%. The cost is a small increase in the average paging delay.Selective paging performs better than spread paging in terms of both average paging delay andaverage paging traffic, but is more complex to implement.An LA sectorization technique is applied to spread paging and selective paging to furtherreduce paging traffic. Two sectorization patterns are examined. The results show that sectorizationcan yield typical average paging traffic reductions of about 50%. The resulting increases inpaging delay are negligible for both patterns.The sensitivity of spread paging and selective paging to uncertainty in user mobility parametervalues, such as the angular deviation parameter, mean speed, mean velocity hold time and meantrip length, is studied. It is found that spread paging is most sensitive to the mean trip length ofa user while selective paging is most sensitive to uncertainty in user mean speed.iiTABLE OF CONTENTSABSTRACT^ iiLIST OF FIGURES^ viLIST OF TABLES xACKNOWLEDGEMENT^ xiCHAPTER 1 INTRODUCTION^ 11.1 Background ^ 11.2 Motivations and Objectives ^ 31.3 Outline of the Thesis 4CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 52.1 Directional Random Walk ^ 52.2 Stochastic Model ^ 92.2.1 Simulation 102.2.2 Radial distance p d f.^ 102.2.3 Angular deviation p.d.f. 15CHAPTER 3 CELL AND LOCATION AREA LAYOUT MODEL^213.1 Cell Map ^ 213.2 Location Area 23CHAPTER 4 LOCATION UPDATING SCHEME^ 254.1 Overlapping Location Areas ^ 254.2 Conditions for Location Updates 264.3 Effective Ring Radius^ 264.4 Location Updating Traffic 31111CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 355.1 Preliminaries ^ 355.1.1 Call arrival model ^ 355.1.2 LA ring probability 395.2 Paging Schemes : Description and Performance Analysis ^415.2.1 Flood paging ^ 415.2.2 Spread paging 425.2.3 Selective paging ^ 435.3 Numerical Results 44CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION 506.1 LA Sectorization^ 506.2 LA Sector Probability 526.4 Performance Analysis of the Paging Schemes with Location Area Sectorization . ^ 546.4.1 Flood paging and Spread Paging ^ 546.4.2 Selective paging ^ 576.5 Numerical Results 59CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY INMOBILITY PARAMETER VALUES^ 657.1 Angular Deviation Parameter ^ 657.2 Mean Speed ^ 667.3 Mean Velocity Hold Time ^ 687.4 Mean Trip Length ^ 71ivCHAPTER 8 CONCLUSION AND FUTURE WORK^73BIBLIOGRAPHY^74APPENDIX A ALPHA PROBABILITY DENSITY FUNCTION^78APPENDIX B ASYMMETRIC GAUSSIAN PROBABILITY DENSITY FUNCTION 80APPENDIX C TAIL PROBABILITY OF THE CALL ARRIVAL PROBABILITYDENSITY FUNCTION^ 83LIST OF FIGURES2.1 Illustration of the random walk model. ^ 62.2 Speed distribution with mean speed = 1 km/hr. ^ 82.3 p.d.f. of the angular deviation ^ 82.4 Radial distance p.d.f.'s of the random walk with v = 30 km/hr and th = 60 sec. (a)Simulation. (b) Analysis^ 112.5 Angular deviation p.d.f.'s of the random walk with I., = 30 km/hr and th = 60 sec.(a) Simulation. (b) Analysis^ 112.6 Illustration of the analytical directional random walk model. ^ 122.7 N(t) versus -* for parameter sets IT (km/hr), t h (sec)} : (25, 30), (25, 60), (35,60), (35, 90), (45, 90) and (45, 180). ^ 142.8 Goodness of fit of the analytical radial distance p.d.f. (a)^= 90 sec. (h) T = 35km/hr^ 162.9 The variance of the Gaussian part of the angular deviation p.d.f. versus^forthparameter sets IT(km/hr), th (sec)} : (25, 30), (25, 60), (35, 60), (35, 90), (45,90) and (45, 180). versus 7t^ 172.10 aA of the Alpha part of the angular deviation p.d.f. versus t for parameter setsIT(km/hr),th (sec)} : (25, 30), (25, 60), (35, 60), (35, 90), (45, 90) and (45,180). ^ 192.11 Weighting function p (t , 7h) versus^ 19to 2.12 Goodness of fit of the analytical angular deviation p.d.f. (a) 7 /, = 90 sec. (h) T = 35km/hr^ 203.1 Cell grid of a cellular system. ^ 223.2 Equivalent radius of a cell . 223.3 Location area of size = 3^ 23vi4.1 A mobile user's changing LA viewed as entering the new LA at some point on its^circumference 274.2 Geometry for the evaluation of the effective radius of the i th ring. ^ 284.3 Evaluation of cos(l3) using Pythagoras's theorem^ 294.4 Geometry for evaluating O. ^ 304.5 Illustration of the updating traffic analysis^ 324.6 Location updating traffic versus the equivalent LA radius for T = 40 km/hr,^= 60sec and d = 20 km. (a) LA size = 1. (b) LA size = 5. (c) LA size = 10 345.1 An exponential p.d.f. of the inter-call arrival time with Acall = 1 call/hr and 7R = 40min^ 375.2 P.d.f.'s of the call arrival time with respect to the last location updating time for T, =40 km/hr, th = 60 sec and Acall = 1 call arrival/hr. ^ 395.3 Goodness of fit of the p.d.f.'s in Fig. 5.2. ^ 405.4 Performance of flood paging, spread paging and selective paging with Ti = 40 km/hr,= 60 sec and rcell = 1 km. (s) Average paging delay. (b) Average paging traffic. . 465.5 Performances of spread paging and selective paging versus the user mean speed for= 60 sec, Acall =1 call/hr and rcell = 1 km. (a) LA size = 2. (b) LA size = 6. (c)LA size = 10. 475.6 Performances of spread paging and selective paging versus the user mean velocityhold time for T., = 40 km/hr, Acall = 1 call/hr and rcell = 1 km. (a) LA size = 2. (1)LA size = 6. (c) LA size = 10. ^ 485.7 Performances of spread paging and selective paging versus the call arrival rate for= 40 km/hr, 7/, = 60 sec and rcell = 1 km. (a) LA size = 2. (h) LA size = 6. (c) LAsize = 10^ 496.1 Sectorization of an LA. (a) sectorization of an LA of size 2. (b) idealized sectorizedLA. ^ 516.2 Grouping of the sectors for sectorization patterns. (a) Pattern 1. (b) Pattern 2. . .. 52vii6.3 Goodness of fit of f(0/0 to the p.d.f. from simulation and the call arrival p.d.f. for T =40 km/hr, th = 60 sec., ''cart = 1 call/hr. (a) R = 3 km. (b) R = 6 km. (c) R = 12 km.. 556.4 Performance of flood paging without LA sectorization, with LA sectorization pattern1 and with pattern 2 for T = 40 km/hr, th = 60 sec, malt = 1 call/hr and rcell = 1 km.(a) Analysis. (a) Simulation 606.5 Performance of spread paging without LA sectorization, with LA sectorizationpattern 1 and with pattern 2 for T = 40 km/hr, th = 60 sec, k ali = 1 call/hr and rcell= 1 km. (a) Analysis. (a) Simulation. ^ 606.6 Performance of selective paging without LA sectorization, with LA sectorizationpattern 1 and with pattern 2 for T = 40 km/hr, th = 60 sec, can = 1 call/hr and rcell= 1 km. (a) Analysis. (a) Simulation. ^ 616.7 Performance of LA sectorization on flood paging, spread paging and selective pagingversus user mean speed for th = 60 sec, call = lcall/hr and rcell = 1 km. (a) LA size= 2. (b) LA size = 6. (c) LA size = 10. 626.8 Performance of LA sectorization on flood paging, spread paging and selective pagingversus user mean velocity hold time for T = 40 km/hr, Acall lcall/hr and rcell = 1km. (a) LA size = 2. (b) LA size = 6. (c) LA size = 10. ^ 636.9 Performance of LA sectorization on flood paging, spread paging and selective pagingversus the call arrival rate for T = 40 km/hr, th = 60 sec and rcell = 1 km. (a) LAsize = 2. (b) LA size = 6. (c) LA size = 10. ^ 647.1 Sensitivity of the performances of selective paging and spread paging to uncertaintyin ao for T = 40 km/hr, ti, = 60 sec, d = x, rcell = 1 km, kat! = 1 call/hr andsystem's ao = 4.2. (a) Average paging delay. (b) Average paging traffic. ^ 677.2 Sensitivity of the performances of selective paging and spread paging to uncertaintyin T for th = 60 sec, d = oo, ao = 4.2, rcell = 1 km, A call = 1 call/hr and system's t= 40 km/hr. (a) Average paging delay. (b) Average paging traffic 697.3 Sensitivity of the performances of selective paging and spread paging to uncertaintyin th for v = 40 km/hr, d = x, ao = 4.2, rcell = 1 km, k ali = 1 call/hr and system'sth = 60 sec. (a) Average paging delay. (b) Average paging traffic. 70viii7.4 Sensitivity of the performance of selective paging and spread paging to uncertainty ind for T.5= 40 km/hr, 7h = 60 sec, ao = 4.2, reel' = 1 km, Acall = 1 call/hr andsystem's d = 00. (a) Average paging delay. (b) Average paging traffic^ 72A.1 Effects of a on Alpha p.d.f. with w = 1 and x = 0 ^ 79B.1 Effects of ry on Asymmetric Gaussian p.d.f. with m = 0 and cri = 1. ^ 81ixLIST OF TABLES4.1 Numerical values of the normalized effective radii 316.1 Angular ranges of the sectors for sectorization pattern 1 and 2 53xACKNOWLEDGEMENTI would like to express my sincerest gratitude to my research supervisor, Dr. Cyril Leung,for his valuable advice and constant supervision during the course of my research. I would like tothank Dr. R. W. Donaldson for offering me an opportunity to be a part of the Inter-NetworkingResearch Group in the Department of Electrical Engineering at the University of British Columbia.I am in debt to Dr. Septimui Salcudean whose encouragement and inspiring conversationignited my desire for graduate studies.I am grateful to all my friends and colleagues at the University of British Columbia whomade my studies here more enjoyable and rewarding than I expected. Among them, I would liketo convey my special thanks to Richard Cam for his enlightening and comforting conversation.Finally, but foremost, I would like to express my deepest appreciation of the support frommy family whose love has brought sunshine in my rainy days. For this, I would like to dedicatethe spirit of hard work in this thesis as a symbol of my persistent and loyal love for them.This research was supported in part by a grant from the Canadian Institute of Telecommu-nication Research (CITR) under the NCE program of the Government of Canada and in part byNSERC grant OGP0001731.xiCHAPTER 1INTRODUCTIONIn the past few decades, the emergence of communication technologies, such as telephonesand FAX, has brought instant and affordable global communication closer to the average person.In particular, telephones provide an easily accessible means of communication. Nowadays, thereis a growing demand for systems which are capable of setting up connections regardless of thelocations of the calling and the called parties. The concept of delivering a call to a person insteadof a fixed physical port is the underlining concept behind personal communication networks(PCN's). Such networks are intended to provide ubiquitous communication coverage, enablingpeople to call each other regardless of their geographic locations. Because of potentially highuser capacity due to frequency reuse and cell splitting, present cellular mobile telephone networkswill be used for the wireless communication part of PCN's [1-4]. It has been forecast that in thefuture, everyone will carry a light weight communicator served by low power base stations (cells)[3], [5], [6]. Mobility management of network users, such as location tracking and automaticcall routing, will be handled by the network.1.1 BackgroundThe first radio telephone services were operated in the high-frequency radio band in 1921[7]. Their applications were mainly for communications with ships and aircraft. In the 1940's,a transceiver, a device combining a radio transmitter and receiver, was developed for the use inthe Very High Frequency (VHF) band [7]. The transceivers were commonly used by policeand fire departments as well as taxi companies. To provide a wide area coverage, a basestation with a powerful multi-channel radio transceiver was employed. Several such base stationswere connected to a Mobile Switching Center (MSC) which provided an interface to the Public1CHAPTER 1 INTRODUCTION 2Switched Telephone Network (PSTN). However, the user capacity of this system was limited bythe available number of radio channels. Not until the emergence of the cellular concept did apromising solution to this problem appear.The cellular concept was first formulated in the 1940's [7]. Unlike the conventional onehigh power transmitter system, the service area is covered by a number of base stations, eachtransmitting at low power such that the coverage area of each base station (called a cell) is verymuch reduced. This allows for cells that are far enough apart to use the same radio channels [8].Although this "frequency reuse" idea allows for more user capacity, there is an attendant increasein MSC and network management complexity. The network needs to keep track of the locationof each mobile user so that when a call comes in for a user, the call can automatically be routedto the cell the called user is in [9-11]. This is referred to as mobility management. Cells aregrouped to form location registration areas or location areas (LA's). A user reports its current LAto the network according to a location updating scheme so that when a call comes in for the user,the cells in its registered LA are paged. Various location updating schemes have been examinedin [12-16]. Paging schemes have also been studied in [17-19]. To ensure the continuity of anongoing call when the calling or called parties change cells, the network has to allocate a newradio channel in the new cell for the ongoing call. This is referred to as a hand-off procedure.A number of frequency allocation algorithms, such as fixed allocation, dynamic allocation andfrequency borrowing, have been studied to ensure high successful hand-off rates [20-28].Since cellular systems started operation in the 1980's, there has been a very positive responsefrom the market [7]. The systems developed at that time, such as AMPS, are often describedas first generation systems, characterized by analog frequency modulated voice transmission.To satisfy the rapidly increasing number of cellular phone subscribers and the exchange of anincreasing variety of information such as images and video, several second generation systemsare currently being developed around the world. Second generation systems are characterized byCHAPTER 1 INTRODUCTION^ 3the extensive application of digital technologies such as digital voice transmission.There are three second-generation cellular standards : GSM (a Pan-European digital cellularmobile telephone system) [29-31], IS-54 (an emerging North American digital cellular mobiletelephone standard) [32] and the upcoming Japanese standard. Furthermore, Bell CommunicationsResearch has proposed Universal Digital Portable Communications [33] as a means of deliveringbasic services to telephone company subscribers. Unfortunately, the second generation systemsare not directly compatible with each other. Inter-Networking of cellular systems using differentstandards to provide a worldwide integrated information network is one of the challenges of thirdgeneration systems.1.2 Motivations and ObjectivesAs discussed in the previous section, the mobility management function of a cellular systemkeeps track of the location of a mobile user. It is supported by a location updating schemewhich determines the LA a user is in. When a call comes in for a user, the cells in its LAare paged. A flood paging scheme in which all cells in the LA are paged simultaneously iscommonly used [34-36]. In this paging scheme, the paging channels in the cells are not utilizedefficiently because some of the cells are paged unnecessarily. As the mobile user populationincreases, there is a need for more efficient paging schemes to avoid long paging delays due toqueueing of paging requests. In [18], [19], paging schemes, in which disjoint subsets of the cellsin the LA are paged in sequence until the user is located, are suggested. Paging traffic (numberof cells paged) is reduced at the expense of an increase in paging delay (number of paging stagesneeded). If the mobility model of a mobile user is known, we can predict the group of cells theuser is most likely in. From this, we determine the groups of cells to be paged in sequence.The main objectives of this thesis are :1. To obtain a statistical model of the mobility of a mobile user.CHAPTER 1 INTRODUCTION^ 42. To study criteria for location updates.3. To study which subsets of cells in the LA are to be paged in successive paging stages.4. To examine the effects of an LA sectorization technique for reducing paging traffic.1.3 Outline of the ThesisIn Chapter 2, a mobility model for a mobile telephone user is described. In Chapter 4, alocation updating scheme is proposed. The analysis and simulation results for location updatingtraffic are provided. In Chapter 3, the cell and LA geometries are described. In Chapter 5, twoLA paging schemes, namely spread paging and selective paging, are presented. The analysisand simulation results of their performances, in terms of average paging delay and averagepaging traffic, are shown. Chapter 6 describes and provides the performance evaluation of an LAsectorization technique, as applied to the paging schemes in Chapter 5, for reducing paging traffic.The trade-off between paging delay and paging traffic is studied. In the selective paging scheme,the cellular system maintains estimates of user mobility parameters such as the angular deviationparameter, mean speed, mean velocity hold time and mean trip length for the paging procedure.In Chapter 7, the sensitivity of spread paging and selective paging to uncertainty in user mobilityparameter values is examined. The main results of this thesis are summarized in Chapter 8.CHAPTER 2MOBILITY MODEL FOR A MOBILE USERMobility modelling of a vehicle has been widely studied in traffic engineering. In [37],statistics of daily usage frequency and average trip length of vehicles were analyzed, andthe effects of environmental conditions (e.g., weather and route), psychological factors (e.g.,emotional state and maturity) and physical factors (e.g., vision and reaction time) on drivingbehavior were discussed. Traffic flow theories have been developed. A variety of traffic flowmodels were proposed in [38], in which fluid diffusion equations were commonly used to modelthe mobility of vehicles in a small area (e.g., a segment of a street). In analyses of problemssuch as hand-off frequency and location area boundary crossing frequency in a vehicular cellularcommunication system, we are interested in the mobility model of a vehicle over a longer distance.In [9], a vehicle is modelled as travelling in a straight line at a speed which is constant or uniformlydistributed over some range. Since there is randomness in vehicular movement due, for example,to the configuration of the roads and drivers' preferences for different routes, random walk seemsto be a better mobility model. hi [36], the mobility of a portable mobile telephone user ismodelled by a Brownian movement type symmetric random walk. However, in application to avehicular telephone user, this model ignores the fact that typically, a driver tends to travel in acertain direction. In this chapter, a directional random walk model is proposed, and it will beused as the mobility model for a vehicular telephone user throughout this thesis.2.1 Directional Random WalkIn this directional random walk model, the movements of different mobile users are assumedto be uncorrelated. The travelling pattern of a mobile user is on a journey basis. To start ajourney, the user first chooses a destination which is at a distance, 2, and at an angle, 0, from the5v4 x1,114-^131, ,-^,'13V3 X t h3travelling path— — — principal direction-V2 x t h2Vl X t hiavCHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 6destinationstarting pointFigure 2.1 Illustration of the random walk model.starting point. y and are random variables having probability density functions (p.d.f.'s)fr(2)and 4(0) respectively. At any point in the journey, the line drawn from the current position tothe destination defines the principal direction at that time. The user heads towards the destinationwith a random angular deviation 0, with p.d.f. fB(13), from the principal direction. The speed ata given point is a random variable with p.d.f. fv(v). Once the speed and the direction have been, chosen, the user holds them for some random time, th, with p.d.f. fh(t). After th, expires, thenew principal direction at that time will he used in choosing a new set of direction and speed.The process repeats until the destination is reached. The user is considered to have reached thedestination if the user arrives within a distance, d101, of the destination. The random walk modelis illustrated in Fig. 2.1.In choosing the p.d.f.'s fr (7) and f4,(0) for the destination, we assume a Cartesian coordinatesystem and x, y distances are normally distributed with equal variances, cd, and means equal to0. Expressing the coordinates of the destination in polar form, the p.d.f. of the radial distance,CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 7ry, is given by the Rayleigh p.d.f.Y^20'2dfr('Y) =^ad;^> 0(2.1); otherwiseand the angular p.d.f. is uniform.4(0) = 1^; 0 < < 27rzr0Since the mean of fr(-y) is 7 =^Expressing ad in terms of 7, we have; otherwise.(2.2)ad = (2.3)Statistics of the speed distribution of vehicles have been extensively studied in [37-39].Numerous investigators have used a normal distribution to represent speed. In [39], the statisticsof the free-flow speeds from radar speedometer measurements at 31 rural areas in Australia during3 different years were collected and the speed distributions are found to be normal with standarddeviations equal to 0.17 times the respective arithmetic means. We will use this results to modelthe speed. We have()2 fv(v) = 1^^ c^27ra-jwhere ad = 0.17 x T. The speed distribution with unity mean speed is shown in Fig. 2.2.(2.4)From our literature search, it seems that there are no available statistics on direction changesof a vehicle (e.g., at an intersection). We will model the angular deviation from the principaldirection by an Alpha p.d.f. (see Appendix A) with mean deviation equal to 0. We havefE3( /3) =0^ ; otherwise.We assume that with probability 0.95, a user travels in the forward direction i.e., the angulardeviation is in the range^,^The corresponding a ,j is 4.2. The p.d.f. is plotted in Fig./ 1^ ;^< 3 < r2 {1i-a 20 83 2 1 tan -1^e7r) (2.5)2.3.21 .510.5CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 80 0.5 1speed (km/hr)Figure 2.2 Speed distribution with mean speed = 1 km/hr..1.5 2angular deviation (rad)Figure 2.3 p.d.f. of the angular deviationCHAPTER 2 MOBILITY MODEL FOR A MOBILE USER 9We model the arrival of events that cause the change of velocity by a Poisson process.Therefore, the inter-event arrival time (velocity hold time) is exponentially distributed withparameter Air where th is the mean velocity hold time, i.e.,AhE—Aht ; t > 0fix(t) = (2.6); otherwise.2.2 Stochastic ModelGiven the location updating scheme of the cellular system as described in Chapter 4, thesystem always knows the location area (LA) the user is in, the cell of entry to the LA and theelapsed time since the user entered the LA. In a call delivery to the user, the system has to pagethe cells in the LA to locate the user. The paging load, defined as the number of cells pagedbefore the user is located, can be reduced if the spacial distribution of the user in the LA isknown. Using the proposed random walk model, we will find the radial distance p.d.f., fR(rIt),of a user given that the user has travelled for time t, and the angular deviation p.d.f., fo(O/t), ofa user from the general direction 1 given that the user has travelled for time t.Since it is not easy to derive fR(rIt) and fe(O/t) analytically, we will approximate the p.d.f.'susing simulation results (see Section 2.2.1). The random walk model is simplified with theassumption that the destination is at infinite distance from the starting point; therefore, theparameters of the resultant random walk model are the mean speed, V, and mean hold time,tai . We approximate the p.d.f.'s for the parameter values T) E (25, 30, 35, 40, 45) km/hr, t i, E(30, 60, 90, 120, 180) sec and time t E 11, 2, ... , 120) min. From the approximation results(see Fig. 2.8 and 2.12), we believe that the analytical model will still give a reasonably goodapproximation beyond t = 120 min.The general direction of a journey is defined as the vector pointing from the starting point to the destination of the journey.CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 102.2.1 SimulationWith the destination at infinite distance from the starting point, the random walkmodel described in Section 2.1 for parameters v E {25, 30, 35, 40, 45} kin/hr and 7h E{30, 60, 90, 120, 180} sec was simulated on a computer. The radial distance and angular devi-ation p.d.f.'s at different times are obtained and will be used to obtain approximate analyticalforms in the following sections. The time increment in the simulation is 4 seconds and thesample size is 400000 samples for each p.d.f. The frequency distributions of the radial distanceand angular deviation were obtained first. The resolutions of the distance and angular deviationin the frequency distribution are 400 cells per 70 km and 200 cells per 27r radian. Therefore, thewidths of the cells are Or = 175 m and AO = 0.01r radian. The frequency distributions of theradial distance and angular deviation are normalized by the number of samples, scaled by :27,and 2B , and used to estimate the radial distance and angular deviation p.d.f.'s. Examples of thep.d.f.'s are shown in Fig. 2.4 (a) and 2.5 (a). The 99% confidence intervals are within ±5% ofthe average values and are omitted from the figures.The simulation program was written in C and was run on a SUN SPARCstation IPX. Toobtain the above simulation results at times t = 1, 2, 3, , 120 minutes (i.e., a total of 120p.d.f.'s) for one set of speed and hold time, it takes approximately 4 CPU hours.. 2.2.2 Radial distance p.d.f.Without loss of generality, we choose the Cartesian coordinate system such that the startingpoint of the journey is at the origin, the destination is at d-x. , on the x-axis and the startingtime is t = 0. From the radial distance p.d.f.'s obtained by simulation in Section 2.2.1, we findthat they can be fitted by an asymmetric Gaussian p.d.f. (see Appendix B). We will express thethree parameters (0-1, 7, m) of the asymmetric Gaussian p.d.f. as functions of time to obtain theanalytical form for the radial distance p.d.f. For convenience in the derivation, we express timein seconds, distance in meters and speed in meters per second.15^20^25^30^35radial distance (km)(a)10^15^20^25^30^35^40radial distance (km)(b)CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 11Figure 2.4 Radial distance p.d.f.'s of the random walk with v = 30 km/hr and th = 60 sec. (a) Simulation. (b) Analysis.-3^-2^ 0^ 2^3angular deviation (rad)(a) t t=41 min^ t-31 min21 mitt^ t - 11 mm^ - I min2-3^-2^-1 0angular deviation (rad)3(b)Figure 2.5 Angular deviation p.d.f.'s of the random walk with= 30 km/hr and t h = 60 sec. (a) Simulation. (Li) Analysis.V2t h2starting pointx2 x4• • x3 ••x1vit bx2• '•^►x4• x3 •►xi•^starting point destination at +co(a)destination at + coCHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 12y(b)Figure 2.6 Illustration of the analytical directional random walk model.To determine cri, we relate the peak value of fR(r/t) from simulation to the peak value of anasymmetric Gaussian p.d.f. given in Eqn. (B.7), i.e.,max [fR(rIt)] = ^ (2.7)V2 7r a?Or{ ^Ai ^1 2a1 = max [fR(rIt)] f 2 7r .^ (2.8). To obtain an analytical approximation to max [fR(r/t)], we view the random walk as consistingof discrete independent steps of variable lengths as in Fig. 2.6 (a). Note that the longer a userhas travelled, the more likely that its angular deviation, 0, from the general direction is small. Itis also reflected in the angular deviation p.d.f. in Fig. 2.5. The spread of the p.d.f. becomes lessas time increases. The x-component, x, of the distance travelled is related to the radial distance, r,as x(t) = r(t) cos [0(t)]. For large enough t, 0(t) becomes small and x(t) r(t). Their p.d.f.'s,fx(x/t) and fR(rIt), are approximately the same andmax [fR(rIt)]^max [fy (x/i )].^ (2.9)or71"CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 13We will express max [fx(x/t)] analytically. Referring to Fig. 2.6 (b), the x-component of the1 step is denoted by xi = v2 th , cos (/3i) where vi, t ip, and 13i are independent random variablesas described in Section 2.1. After time t, the x-displacement isN(t)Ds E xi (2.10)where N(t) is the number of steps in time t. If N(t) is deterministic given t and is large enough,by central limit theorem, Dx tends to have a Gaussian distribution and its variance isN(t)a^ (2.11)where o is the variance of x2 =^- (T) 2= v2 COS 2 (0) — (V th cos (3)) 2= V 2 t'/, cos 2 (j3) — (TT: cos (0)) 2^(2.12)which can be evaluated numerically. The maximum value of this Gaussian p.d.f. is. By Eqn. (2.9), we haveN(t)max [fR WO] ti max [fa (x/t)]1 (2.13)-V2 N(t)or.N(t) ^1^(2.14)2 7 Cq {max [fR(r/t)]} 2However, N(t) is a random variable correlated with ti, (ti, is exponentially distributed) and hasexpected value N(t) = 71 . We obtain N(t) for parameter set 'T E {25, 35, 45} km/hr and71, E {30, 60, 90, 120, 180} sec from simulation from which max [fR(r/t)] is obtained. Fig.2.7 shows N(t) for six sets of random walk parameters versus t h.. It can be seen that they allL^anCHAPTER 2 MOBILITY MODEL FOR A MOBILE USER70605040z302010t hFigure 2.7 N(t) versus^for parameter sets 17(km/hr), 7h (sec)}: {25, 30), {25, 60}, (35, 60), (35, 90), (45, 90) and {45, 180).exhibit the same functional relationship. By piecewise curve fitting, the analytical form of N(t)is given by14t ) 39.0773 x 10 -6 (04 - 5.1106 x 10 -4 (7:-2+0.0143 1h^th- 0.0273 (=L) + 0.00280.3191 (--0 - 3.1812 (-6 5 + 3.1008. Substituting Eqn. (2.13) in (2.8), o is obtained asN (t, 0 <^< 1313<(2.15)o.2^4i N JO (7,2 .^ (2.16)The parameter 7 in Eqn. (B.3) is obtained by fitting the analytical p.d.f.'s to the p.d.f.'sfrom simulation asry (71) = - 5.4612 x 10 -8 (70 3 + 2.9028 x 10-5 (70 2- 0.0050 (7/i ) + 0.8393.^ (2.17)CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 15To obtain m, we rearrange Eqn. (B.10) and we have in(t,th ) = r(t,th ) +^—2 cr1 [-y ( 1,) — 1]7r(2.18)where r (t, h ) is the mean radial distance of the user at time t with mean hold time th . r(t,th )is estimated by the mean distance in x direction with an offset asr(t,th) = x(t, 7 , /3) + c(7,= T cos (13) t^c(T), (2.19)where the offset c(73, 70 is obtained by fitting the analytical p.d.f.'s to those obtained bysimulation asc(7, 70 =3.24 (T) 2 — 37.8(7)+ 0.0096 (70 2 + 1.3586 (70 + 150.3608.^(2.20)The analytical radial distance p.d.f.'s are shown with those obtained from simulation in Fig.2.4. The goodness of fit of the radial distance p.d.f. is evaluated by integrating the absolutedifference between the p.d.f.'s from analysis and simulation. The maximum value is 2 and theminimum value is 0. Goodness of fit for different random walk parameters is shown in Fig. 2.8.2.2.3 Angular deviation p.d.f.From the angular deviation p.d.f. obtained by simulation in Section 2.2.1, we find that forlarge t, fo(O/t) is well approximated by a Gaussian p.d.f. whereas for small t, an Alpha p.d.f.gives a better fit. Therefore, we combine the two p.d.f.'s by weighting them as a function of t.Denoting the Gaussian part of the p.d.f. by fc,(0/t) and Alpha part by fA(0/t), the approximationof fo(0/t) is expressed asfe(e It) = P(t) fc -;( 0 It) + [1 — p(t)] fA (0 It)^(2.21)1.210.80.60.40.2mean hold time = 30 secmean hold time = 90 secmean hold time = 180 sec•1.50.5o-?-; (t)=27{max [le ( 0/0]} 2 •1(2.24)CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 16mean speed = 25 km/hrmean speed = 35 km/hrmean speed = 45 km/hr0^20^40^60^80^100^120time (min)(a)20^40^60^80^100^120time (min)(b)Figure 2.8 Goodness of fit of the analytical radial distance p.d.f. (a) 7 h = 90 sec. (b) v = 35 km/hr.where p(t) is the weighting function which is a positive number less than 1.The Gaussian part has the form1^82 fG( e / t ) = ^,V21 1- 0-2 (t) e 23(t) •(2.22), The variance or, (t) is estimated by the peak values of the p.d.f.'s from simulation as follow max [fe(O/t)] = 1 (2.23)orV2 at(1)Fig. 2.9 shows o-6(t) for different sets of random walk parameters versus 7L. It can be seenthat they all exhibit the same functional relationship. By piecewise curve fitting, the analyticalf^1 ^A(t) A( 6 /t) = /2 [1-Fo 2A (t)9]tan -1 (ct A (t) ir)0; —7r < < 7r(2.26); otherwise.CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 17 0.080.070.060.050.040.030.020.0150^100^150^200^250thFigure 2.9 The variance of the Gaussian part of the angular deviation p.d.f. versus:— for parameter sets{T(km/hr), 7h (sec) } : (25, 30), 125, 60}, (35, 60), (35, 90}, (45, 90) and (45, 180). versus -L.form of Q6(t) is4^ 31.8613 x 10 -7 (0 — 1.5580 x 10 -5 (7th-)2+5.0597 x 10-4 (6 — 0.0083 ( 79+0.0805^ ; 0 < (^< 270.08 c^+ 0.0025^; 27 _< (=t-th < 132—0.3344 (=i- 20-6 (t, th ) =20.08 c^+ 0.0017^; 132 5_(7 9.—0.3 (=L(2.25)The Alpha part of the p.d.f. has the formp(t,7) =^tan-1 [a (—t - 1)]th 21+ (2.30)CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 18Similarly, aA (t) is estimated by equating the peak value of the p.d.f. from simulation to that ofthe Alpha p.d.f. given in Eqn. (A.3) and we have aA (t) MaX[fe0/01 = 2 tan -1 (aA(t) 7) .(2.27)We solve aA(t)'s for different random walk parameters numerically. Fig. 2.10 shows aA (t) fordifferent sets of random walk parameters versus 7L. It can be seen that they all exhibit the samefunctional relationship. By piecewise curve fitting, the analytical form of aA is1(2.28)aA (t,^= =(t,tii )and zz, is given by2—6 (63 +4.-5.9969 x 10^1880 x 10-4 ( in )+ 0.2335-0.0117 (6 ; 0< ( th ) <25\ 3^2-2.7376 x 10^+ 4. 9513 x 10 -5 ( t )thr.7(t, th ) 0.1718-0.0036 ( 70 • 25 < ( 79 < 60 (2.29)0.0840 C^6 5^h) + 0.0412 60 <^< 1200.060 e^122 ( th) + 0.0319 120< GO.We use a scaled and vertically shifted arctan function as the weighting function, p(t), toprovide a smooth transition from 0 to 1 i.e.,The parameters a and b together control how fast p(t.7 1,) changes from 0 to 1. By comparing theanalytical p.d.f. to the one from simulation, a and b are determined to be 0.1 and 1 respectively.Fig. 2.11 shows the plot of p(t,th ).The goodness of fit of the p.d.f. is evaluated by integrating the absolute difference betweenthe p.d.f.'s from analysis and simulation. The maximum value is 2 and the minimum value is 0.Goodness of fit for different random walk parameters is shown in Fig. 2.12.6 curves10.90.80.70.60.50.40.30.20 50 100 150 200CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 192520151050^100^150^200^250thFigure 2.10 ctA of the Alpha part of the angular deviation p.d.f. versus 7!-- for parameter sets{7(km/hr), 7h, (sec) : {25, 30), {25, 60), {35, 601, {35, 90), {45, 90) and {45, 180}.thFigure 2.11 Weighting function p(t,7h ) versus th20 40 60^80^100^120time (min)(b)20^60^80^100^120time (min)(a)0.10.080.060.040.020.10.080.060.040.02mean hold time = 30 secmean hold time = 90 secmean hold time 180 secmean speed = 25 km/hr- - - - - mean speed = 35 km/hr- • - mean speed = 45 km/hrCHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 20Figure 2.12 Goodness of fit of the analytical angular deviation p.d.f. (a) 7h = 90 sec. (b) 7 = 35 km/hr.CHAPTER 3CELL AND LOCATION AREA LAYOUT MODELIn this chapter, layouts of the cells and location areas of a cellular system used in thesubsequent chapters are described.3.1 Cell MapFor convenience and simplification in system analysis, the service area of a cellular system iscommonly viewed as consisting of smaller service area units termed cells. Each cell is served by abase station. All cells are assumed to be of identical shape and size, and hexagonal packing of thecells is assumed. Hence, we have a hive-like cell grid on the service area of the cellular systemas shown in Fig. 3.1. The size of a cell depends on the transmission power of the base stationtransmitter. The larger the transmission power is, the larger the cell size is. Each cell is assigneda unique identity number which is broadcast by its base station; this is heard by all mobile userswithin the coverage area. Therefore, a mobile user can always identify the cell it is currently in.A user is considered to have changed serving base station if it crosses the cell boundary.For mathematical convenience, we take a cell to be circular. In [28], the equivalent radius,ree , of the cell is defined as the radius of a circle having the same area of the cell as illustratedin Fig. 3.2 where rcell is the 'radius' of the hexagonal cell. Therefore,or7r r 2q, = 6 72-1 r,2, 11 sin (7-71 )[^] (3.1)rev, reel ! —3 sin (. 7--T7r^30.9094 (3.2)21CHAPTER 3 CELL AND LOCATION AREA LAYOUT MODEL^ 22cellular system service areaFigure 3.1 Cell grid of a cellular system.Figure 3.2 Equivalent radius of a cell [28].CHAPTER 3 CELL AND LOCATION AREA LAYOUT MODEL^ 23Figure 3.3 Location area of size = 3.3.2 Location AreaCells are grouped to form location registration areas or location areas (LA's). The systemhas a mapping function between cells and LA's. A user updates the LA it is in to the systemaccording to the location updating scheme in Chapter 4 so that the uncertainty in the user locationis within an LA. In a call delivery to a user, the cells in its registered LA are paged. Therefore,• an LA is also a paging area.In forming an LA, we choose a cell to be the center cell and it is surrounded by layers (orrings) of cells. The cells immediately surrounding the center cell form the 1s 1 ring. The layerthat surrounds the /' ring is the 2nd ring and so on. The size of an LA is specified by the numberof rings it contains. Fig. 3.3 shows an LA of size 3.For mathematical convenience, we take the rings to be circular. For the k th ring, theequivalent radius, Reo,.(k), is defined as the radius of a circle having the same total area asall cells in rings, 1, 2, . . . , k. The number of cells in the i ih ring is 6x i for i E {1, 2,3, • • •}CHAPTER 3^CELL AND LOCATION AREA LAYOUT MODELand the total number of cells in rings 1, 2, ... , k is24N^= 1 + E 6i= 1+3k(1+k) ;^k (3.3)We can express Req,(k) asR' q,(k) = N(k)71-or;^k E {0,1,2,-•.} (3.4)Reqv(k) = req „ A/N(k) ;^k E {0, 1,2, ...}. (3.5)The width of the k th ring, W(k), is defined asW(k) = Regv (k) — Rev,(k — 1) ;^k E (3.6)CHAPTER 4LOCATION UPDATING SCHEMEWith location tracking of mobile users, calls can be routed to their destinations regardless ofthe calling and called parties' locations. Location tracking is supported by the location updatingscheme, which determines the LA the mobile user is currently in. When a call arrives, the calleduser can then be paged in the correct LA.In [16], several location updating schemes were discussed, including schemes based on thetiming method in which a user updates periodically and the zone method in which the updateis triggered by the crossings of the geographic boundaries of LA's. In [12], the concept ofoverlapping LA's was proposed to reduce the location updating load in the cells on the LAboundaries. In this chapter, we present a location updating scheme which is based on the zonemethod as well as overlapping LA's.4.1 Overlapping Location AreasAn LA is specified by its center cell and its size in terms of rings as discussed in Section3.2 and we assume that the system determines the size of the LA. When a mobile user updatesits location, it reports the cell it is currently in as the center cell of the new LA to the system.Therefore, an LA is formed such that the mobile user is at the center of the new LA. Knowingthe center cell and the size of the new LA, the system identifies its member cells and sends theiri.d.'s to the mobile user. The mobile user stores these i.d.'s and uses them to determine if it hasexited the current LA by monitoring the i.d. broadcast of the current cell. If this i.d. does notmatch any of the stored i.d.'s, the user knows that it has entered a new LA.25CHAPTER 4 LOCATION UPDATING SCHEME^ 264.2 Conditions for Location UpdatesWe define a location update as a report to the system of the cell a mobile user is currentlyin as the center cell of the new LA; a record of the updating time (time stamp of the update)is also kept. Assuming the user mobility model in Chapter 2, we only consider the locationupdating activities of the mobile user when it is on a journey because there is no need to updatethe location when the mobile user is not moving. Location updates are triggered by any of thefollowing events :1. The mobile user starts a journey. When a mobile user starts a journey, it performs locationupdate to confirm its current LA with the one registered at the end of the previous journey.The update also indicates to the system that the user is ready to move. It may be initiatedby the user manually or automatically when the vehicle is started.2. The mobile user crosses the LA boundary. If a mobile user detects that it has entered anew LA as described in Section 4.1, it updates its location to the system.3. A call comes in. When a call comes in to a user, the user updates its location during thecall setup. This enables the most up-to-date location information to be made available to thesystem without the need for an additional connection.4. The mobile user ends a journey. After a user has reached the destination, it updates itslocation to the system. The update indicates to the system that the user has finished a journeyand will stay in the current cell (the center cell of the LA) until further notice (the updateevent 1). If a call comes in during this time, the system can direct the call to this cellwithout paging other cells in the LA. It may be initiated by the user manually or triggeredby turning off the vehicle engine.4.3 Effective Ring RadiusIn the evaluation of the ring probability in the performance analysis of the paging scheme-^------^new LAold LAithring„- - - -centrange ofdirectionsCHAPTER 4 LOCATION UPDATING SCHEME^ 27Figure 4.1 A mobile user's changing LA viewed as entering the new LA at some point on its circumference.in Section 5.1.2, we need to find the distance, /,R, from a user's point of entry to the center cellof an LA of size R to the point the user reaches the equivalent radius [Eqn. (3.5)] of the ith ringof the LA. We view the change of LA in the way that the user enters the new LA at some pointon its circumference and we assume that the user is travelling in a straight line in the principaldirection as shown in Fig. 4.1. The range of the principal direction in which the user travels• when the change of LA occurs is [-0, +0]. The distance, iiR, depends on the principal directionof the user as it enters the LA. This distance is the 'radius' of the i th ring experienced by the user.We define the effective radius of the ith ring as the average of this distance over the range of theprincipal direction, and use it to evaluate the ring probability. We assume that the direction isuniformly distributed over this range. Referring to Fig. 4.2, we first express li,R in terms of 0.Then, we average /;,R(B) over 0 to get the effective radius. For the ill' ring, i id? is given by= r0 cos (a)^r, cos (3).^ (4.1)center cellCHAPTER 4 LOCATION UPDATING SCHEME^ 28Figure 4.2 Geometry for the evaluation of the effective radius of the^ring.ri is the equivalent radius of the i t h ring given in Eqn. (3.5) rewritten here asri = regt,VN(i)r„u p^ (4.2)where—3 sin (-7r )77"^3(4.3).N(i)=1+3i(.1.+i).^ (4.4)Using the sine rule, we havesin (3)^S111 ( 0 )rR^riorP=and(4.5)sin ())^—rR sin (0).^ (4.6)CHAPTER 4 LOCATION UPDATING SCHEME^ 29Figure 4.3 Evaluation of cos(3) using Pythagoras's theorem.By Pythagoras's theorem as in Fig. 4.3,cos (,3) =TrR) 2 21 — -- sin (9)• (4.7)Similarly, cos(a) is given bycos (a) =2(ro^sin2 (0). (4.8)Substituting Eqn. (4.2), (4.7) and (4.8) in (4.1), we have(4.9)where h,R(0) = pk, — N (R)sin2 (0) +^— N(R ) sin2 (9)Therefore, the effective radius of the it h ring in an LA of size R isRef f^210 1 ,R) = ^RV') do'-e(4.10)CHAPTER 4 LOCATION UPDATING SCHEME^ 30Figure 4.4 Geometry for evaluating O.- 0= rcell^'01,R(0)- —0= rcert 4 (4.11)where rP i , R is the normalized effective radius of the ith ring in of LA of size R0= 12 )'^7i'i,R(0) dO.-0Referring to Fig. 4.4, the 0 in the limits of the integration is evaluated by(4.12)Tosin (0) = —rR 1 (4.13)./N(R)or( ^)0 = sin-1 1VN(R)Table 4.1 shows the T'i ,R for LA's of different sizes.(4.14)CHAPTER 4 LOCATION UPDATING SCHEME^31ringLA size0 1 2 3 4 5 6 7 8 9 100 1.1579 1.4193 1.4252 1.4268 1.4275 1.4278 1.4280 1.4281 1.4282 1.4282 1.42831 - 3.0559 3.0596 3.0606 3.0611 3.0613 3.0614 3.0615 3.0615 3.0615 3.06162 - - 4.6401 4.6410 4.6414 4.6416 4.6417 4.6417 4.6418 4.6418 4.64183 - - - 6.2187 6.2191 6.2193 6.2194 6.2194 6.2195 6.2195 6.21954 - - - - 7.7956 7.7958 7.7959 7.7960 7.7960 7.7960 7.79615 - - - - - 9.3718 9.3719 9.3720 9.3720 9.3721 9.37216 - - - - - - 10.9477 10.9477 10.9478 10.9478 10.94787 - - - - - - - 12.5233 12.5233 12.5234 12.52348 - - - - - - - - 14.0988 14.0988 14.09889 - - - - - - - - - 15.6742 15.674210 - - - - - - - - - - 17.2495Table 4.1 Numerical values of the normalized effective radii.4.4 Location Updating TrafficWe define the location updating traffic as the number of location updates per unit time peruser. Since the location updates due to updating event 3 (call arrivals) are performed duringcall setup, we consider that location updating traffic are due to events 1 (starting a journey), 2(crossings of LA boundaries) and 4 (ending a journey). For convenience in the location updatingtraffic analysis, we assume that a user starts one journey after another continuouslyIn deriving the updating traffic due to event 2, we let the user's trip length be infinitely long.We assume that the user is travelling in a straight line in the principal direction of the journey asshown in Fig. 4.5. The projection of the user mean velocity on the principal direction isTr = T • cos (0) (4.15)where 6 is the angular deviation of the user's current direction from the principal direction andits p.d.f. is given in Eqn. (2.5). The expected time, 7cross, a user takes to cross the LAboundary from the LA center is approximated by dividing the effective radius of the LA by thisprincipaldirectionacross^177,R,f f(R,R)CHAPTER 4 LOCATION UPDATING SCHEME^ 32Figure 4.5 Illustration of the updating traffic analysis.mean speed as(4.16)Expressing the effective radius of the LA in terms of its equivalent radius in Eqn. (3.5), we have'RRacross^-Rcgv(R 7,i^(4.17)p Viv(R) -T1 pwhere p is given by Eqn. (4.3). Thus, the average location updating traffic due to event 2 is1T cross^7 (4.18)t CT OSSTo derive the updating traffic due to events 1 and 4, we first approximate the user meantrip duration byTrip^d VP(4.19)CHAPTER 4 LOCATION UPDATING SCHEME^ 33where d is the mean trip length. Since there are two such updates in a journey, the updatingtraffic is approximated byTstart,end2(4.20)tiripThe total location updating traffic is approximated byT Tcross +T start,end •^ (4.21)The location updating traffic was obtained by simulation for 7v- = 40 km/hr, th = 60 sec, d =20 km and no call arrvial. The simulation results are shown together with the analytical resultsin Fig. 4.6. The 99% confidence intervals for the simulation results are within ±5% of theaverage values shown.analysisX^simulationCHAPTER 4 LOCATION UPDATING SCHEME^ 3430-In= 20 -C.,cd100fa.^0 ^ analysissimulation■ 15^20^25^30^35^40equivalent LA radius (km)(a)55^10^15^20^25^30^35^40equivalent LA radius (km)(b)analysisX^simulation5^10^15^20^25^30^35^40equivalent LA radius (km)(c)Figure 4.6 Location updating traffic versus the equivalent LA radius for 7 = 40 km/tu- ,th = 60 sec and d = 20 km. (a) LA size = 1. (h) LA size = 5. (c) LA size = 10.CHAPTER 5LOCATION AREA PAGING SCHEMESThe location updating scheme discussed in Chapter 4 enables the system to locate the LA auser is in. When a call comes in to a user, the system pages the user in its registered LA. Theflood paging scheme in which the cells in the LA are paged simultaneously is commonly usedin locating the called user when a call comes in [34-36]. This paging scheme is not efficientin terms of paging traffic defined as the number of cells paged before the user is located. Amore efficient paging scheme which consists of a number of paging stages was examined in [18],[19]. In each paging stage, only a subset of the cells are paged. In this way, the paging trafficis reduced at the expense of an increase in paging delay, defined as the number of paging stagesneeded before the user is located. By carefully choosing the set of cells for each paging stage, wecan reduce the paging traffic without a significant increase in the paging delay. In this chapter,we present two paging schemes, spread paging and selective paging.5.1 PreliminariesIn this section, a call arrival model and the ring probability which will be used in theperformance analyses of the paging schemes in subsequent sections are discussed.5.1.1 Call arrival modelCall arrival is commonly modelled by a Poisson process with rate Acaji arrivals per unittime. The p.d.f. of the inter-call arrival time, denoted by f„//(t), is exponentially distributedwith mean 1In selective paging, the time, te , between a call arrival and the last location update is usedto estimate the position of the mobile user when a call comes in. Let fc (t) denote the p.d.f. of35CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 36te . An exact expression for Mt) appears to be difficult to obtain. Hence, an approximation tofc(t), denoted by fe (t), is obtained by simulation.The LA layout model in Chapter 3, the location updating scheme in Chapter 4 and the usermobility model with infinitely long trip length in Chapter 2 were simulated for the parametersets T E {20, 30, 40} kin/hr, t, E {30, 60, 120} sec, A ca ll E {0.5, 1, 2} arrivals per hour andR E {2, 7, 12, 15, 22} km. The frequency distribution of t, is obtained. The time increment ofthe simulation is 4 seconds, and the sample size is 40000 calls. The resolution of to is 100 cellsper 70 min. Therefore, the width of each cell is At, = 0.7 min. The frequency distribution isnormalized, scaled by *, and is used to estimate fc (t).In the derivation of f,(t), we assume that a user's trip length is infinitely long and the usertravels in a straight line in the principal direction. The projection of the mean velocity on theprincipal direction is7t7p = T cos (0) (5.1)where t is the mean speed of the user and 0 is the angular deviation of the user's current directionfrom the principal direction. The mean time for the user to exit an LA of radius R from thecenter of the LA is approximated by7RR'TT)(5.2)We observe that if 7R is x,^= Jecall(t). If time t is small compared to 7R, say t < c < tR,so that the user is not likely to have exited the LA during time (0, t), it will be shown thatfc(t) has the same shape as feall(t). For t > c, we find that f,(t) can be approximated by a halfGaussian p.d.f.^Therefore,A A,/i c —A"u t 0 < t < cfc(t) = ;^c < t (5.3)212—\17—T-cr?0 ;^otherwise.CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 370.0180.0160.0140.012 -0.01^tR^tR^tR0.0080.006 -0.004 -0.002 -20^40^60^80^100 120 140 160 180 200inter-call arrival time (min)Figure 5.1 An exponential p.d.f. of the inter-call arrival time with Ac.r/ = 1 call/hr and 7R = 40 min.We refer to the exponential p.d.f. of the inter-call arrival time in Fig. 5.1 for the derivationof the exponential part of 1,(t), denoted by fe(t). Time is slotted with slot length tR. fe (t) isthe p.d.f. of the call arrival time w.r.t. the beginning of the time slot the call lands in, i.e.fe(t) = E Amu C — Ac.ii (t—i7R)0tR^tR(= E ei A-7R Acau C A' ti=o= A can e—Ac,,,, t ; 0 < t < tR.^(5.4)To solve for A, we use the condition that the area under the fe (t) curve is 1, i.e.tR^tRf fe(t) dt = f A Acait c"" 1 dt0^0= A (1 — c" , JR)= 1.^ (5.5)CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 38Therefore,A= 1 (5.6) For the Gaussian part of fc (t), we need to determine two parameters : B and a,. To determineB, we use the condition that the area under the L(t) curve is 1, i.e.00C^ 00I fc (t) dt = I A Acau C A"" t dt I B^^ C^dt0^0^ C-V2= A ( 1^A""^+ 0.5 B= 1.Therefore,(5.7)B = 2 [1 — A (1 — c —\—"c)]. (5.8)We choose a, such that 1,(t) is continuous at c and we have—A n c^BA Aran= (5.9)r 0- 2orB (5.10)ac = AN/27r Acarr c^c.It was found that c can be approximately expressed as= f (7R) g (th ) (5.11)where f (7R) and g (71,) were obtained by comparing /JO to fc (t) from simulation as20.00023 (7R)^+ 0.4307 (7R) — 8.7879^; 0 < 7R < 900(ER) =1(5.12)0.85917R — 204.8937andg(7h ) = — 0.00167h+ 1.1041^30 < 7h <900 < 7R180. (5.13)Fig. 5.2 shows the fc(t) obtained from simulation together with /At). The 99% confidenceintervals for the simulation results are within ±5% of the average values shown. The goodnessLA radius = 7 kmLA radius = 12 kmLA radius = 17 kmLA radius = 22 kmsimulationanalysisCHAPTER 5 LOCATION AREA PAGING SCHEMES^ 390.350.30.250.20.150.10.0510^20^30^40^50time (min.)Figure 5.2 P.d.f.'s of the call arrival time with respect to the last locationupdating time for 7 = 40 km/hr, 7h = 60 sec and kat/ = 1 call arrival/hr.of fit of Mt) to Mt) is evaluated by integrating the absolute difference between them. Themaximum value is 2 and the minimum is 0. The corresponding goodness of fit for Fig. 5.2 isshown in Fig. 5.3.LA radius = 2 km5.1.2 LA ring probabilityIn the paging delay and traffic analyses of spread paging and selective paging, we need theprobability that a user is in a particular ring in its registered LA at a particular time. We referto this as the ring probability.In the derivation of the ring probability, we need the p.d.f. of the radial distance, r, of auser at time t given that the user has not exited its LA during time (0, t). We denote this p.d.f.by fR(rIt, LA not yet exited). As discussed in Section 4.3, the distance, /i,R, between the point ofentry to the center cell of an LA of size R and the point the user reaches the equivalent radiusof the i' ring of the LA depends on the principal direction of the user when it enters the LA.0.11 0.1 -0.09 -0.08 -0.070.06CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 400.052^4^6^8^10^12^14^16^18^20^22radius of a LA (km)Figure 5.3 Goodness of fit of the p.d.f.'s in Fig. 5.2.In evaluating the ring probability of the ilh ring at time t, denoted by Pring(i, t), we should firstevaluate the ring probability given that the user is travelling in a certain principal direction byintegrating fR(r/t, LA not yet exited) over the width of the ilh ring from /i-1,R to /i,R. Then, weaverage this ring probability over the range of principal directions the user can possibly havewhen it changes LA as discussed in Section 4.3. However, we find that Pring(t,t) can be wellapproximated by simply integrating fR(r/t, LA not yet exited) over the effective width of the ill'ring from Reff(i-1 , R) to Reff(i, R) where Reff(i, R) is the effective radius of the ith ring of an LAof size R given by Eqn. (4.11).In the random walk model discussed in Chapter 2, we assume that every time a user choosesa new direction, with only probability 0.05, the user travels in backward direction. We assumethe probability that the radial distance the user has travelled in time t is less than that travelledin time t' < t is insignificant andfR(r/t, LA not yet exited)^fR(r/t, r <^f(R. R))CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 41fR(rIt) Reff (R,R)f f R(0) de; r < Reff(R, R)(5.14)0where fR(r/t) is the radial distance p.d.f. for the directional random walk model given in Section2.2.2. Then, the ring probability of the ith ring at time t is approximated byR,f f (1, R )Pring (i, t)^I fR(r/t, LA not yet exited) dr.^(5.15)5.2 Paging Schemes : Description and Performance AnalysisIn this section, three paging schemes, flood paging, spread paging and selective paging, aredescribed. We evaluate the performance of the paging schemes by the average paging delay andthe average paging traffic. We assume that the location updating scheme discussed in Chapter 4provides accurate location information so that the user will be in the registered LA and pagingonly occurs in the registered LA.5.2.1 Flood pagingFlood paging is the simplest paging scheme. When a call comes in to a user, all the cellsin the user's registered LA are paged simultaneously. In response to the paging, the called usersends a reply to the system through the serving base station. Since we assume that the user willbe in the registered LA, the average paging delay is.T) = 1.^ (5.16)For an LA of size R, the average paging traffic is the total number of cells, N(R), the LA contains.Therefore, the average paging traffic is [Eqn. (3.3)]T = iv(R)= 1 + 3 R(1 + 1?).^ (5.17)CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 425.2.2 Spread pagingAccording to the location updating scheme in Chapter 4, whenever a user updates its location,a new LA is formed such that the user is in the center cell of the new LA. Since inner rings ofan LA contain less cells than outer rings, in this paging scheme, paging starts from the center ofthe LA and spreads outward. The system first pages the center cell. If there is no response fromthe user, the system pages the cells in the P t ring and so on until the user is located.In the derivation of the average paging delay and traffic, we need to know the ringprobabilities of all the rings in the registered LA. We denote the ring probability of the i hring by Pi.,„g (i). It is obtained by averaging the time dependent ring probability, Pri„g (i, t),approximated by Eqn. (5.15) using the call arrival p.d.f.,)`,(t), approximated by Eqn. (5.3) asCK)Pr i„g (i) =^Pr i„g (i,t) Mt) dt.^ (5.18)To derive the average paging delay D, we first observe that if the user is in the ith ring, weneed to page rings 0, 1, 2, . . . , i. Thus, there are (i+/) paging stages. Averaging the numberof paging stages using the ring probabilities, we have= E ( i + 1) Pr i„g (i).^ (5.19)0We follow a similar approach for the derivation of the average paging traffic T. If theuser is in the i `h ring, we need to page the cells in rings 0, 1, 2, . . . , i. We denote the totalnumber of paged cells by N(i) which is given by Eqn. (3.3). Averaging N(i) using the ringprobabilities, we haveT E N(i) Prt „g (i)2 =CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 43= E [1 + 3 i (1 + i)] Pri„g (i)i=0= E Pring(i) + 3 E i ( 1 + i) Pri„g (i)i=0^i=0= 1 + 3 (1 + i) Pr i„3 (i).^ (5.20)i = 15.2.3 Selective pagingIn this paging scheme, the mobility model of a mobile user developed in Chapter 2 and thetime, tc , between a call arrival and the last location update are used to select the rings of cellsfor successive paging stages. When a call comes in, we evaluate the ring probabilities at t, givenby Eqn. 5.15. We page the ring with the highest ring probability first. If the user is not found,we page the ring with the second highest ring probability and so on until the user is located.To derive the average paging delay, we first derive the average paging delay at time /c,denoted by D(te ). Then, we average D(t,), using the call arrival p.d.f.,f,(t), to obtain the averagepaging delay. For mathematical convenience, we use matrix representation in the derivation. LetPring (tc) be a column vector whose components are the ring probabilities at time tc. For anLA of size R, we definePiing ( tc) = PrIng Og tC)Pring (1, tc)(5.21)- „9 ( R, t, )_Let N r ing be an R x I vector whose^component is the number of cells in the ill' ring of theLA, i.e."Vri,g( 0)Nring (1 )-vr,„(R)-Nring = (5.22)CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 44where1^i = 0Nring (i)^/6 X i^{ 1,2, 3, ...}.;When a call comes in, P ring (t c ) is sorted in descending order to yield the vector Psring (tc ) andNsring is the corresponding Nri„g . If the user is in the ring which is the i th component ofPrsing(tc the paging delay is i+/. Therefore, the average paging delay at time t, isD(tc ) = [1 2 3 • • • R^1] x P;ing (tc ).^(5.24)Averaging 15(t) using the call arrival p.d.f., Pt), we obtain the average paging delay asCO= D(t) Mt) dt.^ (5.25)We follow a similar approach in the derivation of the average paging traffic. If the user is inthe ring which is the i di component of Prsing (t e ), the paging traffic is the sum of the componentsof Nsring from the 1 to the i th component. The average paging traffic at time t, is1 • • • 1 1'T (t c ) = [N;ing i T X 0 1••^. I x P;i„g (t c.) (5.26)_0 • • • 0 1_where [ • ]T is the transpose operation. Averaging T (I) using the call arrival p.d.f., fe (t), wehave the average paging traffic asT =^T(t) fc (t) dt.^ (5.27)5.3 Numerical ResultsIn this section, the simulation results of the average paging delay and traffic of spread(5.23)paging and selective paging are provided. The LA layout in Chapter 3, location updating schemeCHAPTER 5 LOCATION AREA PAGING SCHEMES 45in Chapter 4 and the random walk model in Chapter 2 with infinitely long trip length weresimulated for spread paging and selective paging. The mean speed of the user is 40 km/hr. Sincewe cannot find any reference on the mean velocity hold time, we assume the mean hold timeto be 60 sec and the cell radius is 1 km. Fig. 5.4 shows the average paging delay and trafficobtained by simulation and analysis. The 99% confidence intervals for the simulation results arewithin ±5% of the average values and are omitted from the figure.Flood paging has the smallest average paging delay (of 1) but it also has the highest averagepaging traffic which increases as the square of the size of the LA. In comparing the differentpaging schemes, we will use flood paging as the reference. In spread paging, the traffic is reducedby more than 50% but the delay increases roughly linearly with the size of the LA. The rateof increase is approximately 0.5 delay per unit increase in the size of the LA. In the selectivepaging, the reduction in average paging traffic is greater than that by the spread paging. For anLA size of 5, the traffic can be reduced by more than 66%. For LA size > 8, the traffic can bereduced by more than 75%. The paging delay increases roughly linearly with the size of the LA.The rate of increase is approximately 0.05 delay per unit increase in the size of the LA. For anLA size of 10, the average delay is 1.8 for selective paging compared to 5.6 for spread paging.We next compare the performances of spread paging and selective paging with changes insuch parameters as mean speed (v), mean velocity hold time T1 ) and call arrival rate (Acall)• Wefix two of the parameters at the reference values (T, = 40 km/hr, tr, = 60 sec and Ace = 1 call/hr)and vary the third parameter. The simulation results for spread paging and selective paging areplotted against mean speed in Fig. 5.5. against mean velocity hold time in Fig. 5.6 and againstcall arrival rate in Fig. 5.7. The 99% confidence intervals for the simulation results are within±5% of the average values shown. These figures show that selective paging performs better thanspread paging in terms of average paging delay and average paging traffic.7^8^9^10.^ , 2^3^4^5 6size of the LA(a)5^6size of the LA(h)1035030025020015010050-simulationSpread paging- - -x- - - analysisSelective pagingFlood paging----- -x-- --x ^xCHAPTER 5 LOCATION AREA PAGING SCHEMES^ 46Figure 5.4 Performance of flood paging, spread paging and selective paging with 17 = 40km/hr, ih = 60 sec and r,,, 11 = l km. (s) Average paging delay. (b) Average paging traffic.30^40mean speed (km/hr)50^20^30^40^50mean speed (km/hr)CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 472.2^ 9.5cdao(a)1.81.61.41.220—K.— Spread paging- -e- - Selective paging^X^—x-- Spread paging- -0- - Selective paging -0- 0-504540.be;a.3530• —20 30^40 50mean speed (km/hr)30^40^50mean speed (km/hr)(b)120.1_1 00•—ag 80CrJ60,^30^40^50^4e0 30^40^50mean speed (km/hr) mean speed (km/hr)(c)Figure 5.5 Performances of spread paging and selective paging versus the user mean speed for 7h= 60 sec, A„ll = 1 call/hr and rm, = 1 km. (a) LA size = 2. (b) LA size = 6. (c) LA size = 10.2.2^ 9.5—X-- Spread paging- -e- - Selective pagingcO..e=1eaobl)n.5)ecttabCS0)1.81.61.41.40^60^80 100 120mean velocity hold time (min)(a)40^60^80 100 120mean velocity hold time (min)mean velocity hold time (min)^mean velocity hold time (min)mean velocity hold time (min)^mean velocity hold time (min)(c )X^454035304x320 -------0--------E40^60^80 100 1202540 60 80 100 12050-0X—x-- Spread paging- -e- - Selective pagingX543XX^ X(b)12010080a)to;1- 604040^60^80 100 1202 -------^-----640 60 80 100 1201-C -^-^-------)( Spread paging- -e- - Selective pagingCHAPTER 5 LOCATION AREA PAGING SCHEMES^ 48Figure 5.6 Performances of spread paging and selective paging versus the user mean velocity hold time for 7 =40 km/hr, kat/ = 1 call/hr and r«11 = 1 km. (a) LA size = 2. (b) LA size = 6. (c) LA size = 10.9.8.5.-e---0 5^1^1.5 205 1 1.5CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 49call arrival rate (calls/hr)^(a)^call arrival rate (calls/hr) call arrival rate (calls/hr) call arrival rate (calls/hr)05^1^1.5call arrival rate (calls/hr) call arrival rate (calls/hr)(c)Figure 5.7 Performances of spread paging and selective paging versus the call arrival rate for 7 = 40km/hr, th = 60 sec and r,11 = 1 km. (a) LA size = 2. (b) LA size = 6. (c) LA size = 10.CHAPTER 6PAGING SCHEMES WITHLOCATION AREA SECTORIZATIONIn Chapter 5, we examined three paging schemes namely flood paging, spread paging andselective paging. Since a user is likely to travel in the principal direction of the journey, theuser is likely to be in a sector of the LA close to the principal direction when a call comes in.Therefore, we divide an LA into a number of sectors. The probability that the user is in a givensector is termed its sector probability. By applying a paging scheme in descending order of LAsector probabilities, we can reduce the paging traffic at the expense of an increase in the pagingdelay. This trade-off is examined in this chapter.6.1 LA SectorizationDue to the hexagonal packing of the cells in an LA discussed in Chapter 3, it is convenientto divide an LA into six basic sectors as shown in Fig. 6.1 (a). Fig. 6.1 (b) shows the idealizedsectorized LA. The sector probability depends on how close the sector is to the principal directionof the user and how large, in terms of the total angle a subtended, the sector is as shown inFig. 6.1. The closer the sector is to the principal direction, the larger is the sector probability.For larger sectors, the reduction in the paging traffic is less because a larger fraction of the cellsin the LA is paged in each sector paging stage. In LA sectorization, we group a number ofbasic sectors to form larger sectors to attain different performances. We will examine two LAsectorization patterns.In pattern 1, we divide an LA into two halves (sector 1 and 2) as shown in Fig. 6.2 (a).Sector 1 covers the portion of the LA along the user's principal direction. Sector 2 covers the50CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^51(a) (b)Figure 6.1 Sectorization of an LA. (a) sectorization of an LA of size 2. (b) idealized sectorized LA.remaining portion of the LA. When a call comes in, sector 1 is first paged; if necessary, sector2 is then paged.In pattern 2, we divide an LA into three sectors, sector 1, 2 (2a and 2b) and 3, as shown inFig. 6.2 (b). Sector 1 covers the portion of the LA along the user's principal direction. Sector 2is split into two parts so as to preserve the sectorization symmetry about the principal direction. of the user. The paging sequence of the sectors is sector 1, 2 and 3 until the user is located.Compared to pattern 1, a smaller fraction of the cells in the LA is paged in each sector pagingstage. However, more paging stages are needed to locate the user due to the smaller sectorprobabilities. The performances of patterns 1 and 2 will be discussed in Section 6.4.The grouping of the basic sectors in the sectorization patterns is dynamic in the sense thatthe constituent basic sectors of each sector in the patterns change, depending on the principaldirection of the user. We assume that the system knows the principal direction of the user. Thesector in which the principal direction lies has the highest sector probability and is referred to(a) (b)angle bisectorof sector 1range of the_ _^direction^• •principal-^directionangle bisectorof sector 1 principaldirectionrarige of thedikectionVCHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^52Figure 6.2 Grouping of the sectors for sectorization patterns. (a) Pattern 1. (b) Pattern 2.as sector 1. In pattern 1, sector 1 is formed such that the principal direction lies in its centerconstituent basic sector as illustrated in Fig. 6.2 (a). In pattern 2, the two basic sectors whoseboundary is closest to the principal direction form sector 1 as shown in Fig. 6.2 (b).6.2 LA Sector ProbabilityIn the performance analysis of the LA sectorization in Section 6.4, we need to know thesector probability of an LA. Let to he the time elapsed since the last location update. The sectorprobability of sector i at time to is denoted by Psec(iy tc)• To evaluate Psec(i, (c), we first obtainthe p.d.f. of the angular deviation 0 of the user from the angle bisector of sector 1 at time te,denoted by 9( 914). We integrate g(0 It c ) over the angular range 0, subtended by sector i toobtain the sector probability and we have= 2010 dO.^ (6.1)o ,CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^53Sector Pattern 1 Pattern 21 [-90°, 90°] [-60°, 60°]2 [-180°, -90°], [90°, 180°] [-120°, -60°], [60°, 120°]3 — [-180°, -120°], [120°, 180°]Table 6.1 Angular ranges of the sectors for sectorization pattern 1 and 2.The angular ranges of the sectors for sectorization patterns 1 and 2 are shown in Table 6.1. Wenow proceed to find g(010.In forming a sectorization pattern, we know that the principal direction is in some angularrange [-/3, /3] from the angle bisector of sector 1 as illustrated in Fig. 6.2. For patterns 1 and 2,is 30°. Since there is no reason that the principal direction will fall at a particular angle in [-13,we assume that the principal direction is uniformly distributed over this range. We let h(O/tc ) bethe p.d.f. of the angular deviation of the user from its principal direction given at time tc . Then,g(014) is obtained by averaging h(Olt,) by the principal direction over^13] and we have9( 0 Itc) = it I h(0 — a It c ) da. (6.2)It remains to find h(9/tc ).An exact expression for h(G/te) appears to be difficult to obtain. Hence, we obtain anapproximation to h(Olt,) using simulation. We run the simulation described in Section 2.2.1except that when the user has reached a radial distance R (the LA radius), we reposition the userback to its starting point (the LA center) corresponding to a location update. We obtain h(Olt,) forthe random walk parameters T E {25, 30, 35. 40, 4.5) km/hr, tip E {30. 60, 90. 120, 180} secand R E {3, 6. 12) km.Note that in the analysis of the LA sectorization performance in Section 6.4, we interpret tcin h(Oltc ) as the call arrival time w.r.t. the last location update. Its p.d.f. is given by Eqn. (5.3).The probability that a call arrives at t c > t* = (c + 1.65 x or.) seconds is less than 0.1 (seeAppendix C) where c and ci are the parameters in the call arrival p.d.f. For analysis purposes,CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^54we will find an approximation to h(Olt,) for t, < t* seconds. We find that the p.d.f. of the angulardeviation 0 of a user from the principal direction given that the user has travelled for time t givesa good approximation to h(01t,) for t, < t* seconds. This p.d.f. is denoted by f(01t) and is givenin Eqn. (2.21). We evaluate the goodness of fit of f(91t) to h(01t,) obtained from simulation byintegrating the absolute difference between them. The maximum value is 2 and the minimum is0. Fig. 6.3 shows the goodness of fit for T7 = 40 km/hr, 7 /, = 60 sec., A, // = 1 call/hr togetherwith the corresponding call arrival p.d.f.6.4 Performance Analysis of the Paging Schemeswith Location Area SectorizationIn this section, the effects of LA sectorization on flood paging, spread paging and selectivepaging are studied.6.4.1 Flood paging and Spread PagingThe performance analyses of flood paging and spread paging with LA sectorization arebasically the same. We will express the average paging delay and paging traffic with LAsectorization, denoted by D s, and Ts„, in terms of the average paging delay and paging trafficwithout LA sectorization, denoted by D and T. For flood paging, D and T are given by Eqn.(5.16) and (5.17). For spread paging, D and T are given by Eqn. (5.19) and (5.20).In the average paging delay and traffic analyses, we need to find the sector probability ofsector i, denoted by PS ,(i). This is evaluated by averaging the time dependent sector probability,Ps„(i,t), using the call arrival p.d.f., _Pt) given in Eqn. (5.3), as00Ps , c (i) = f Psec (i,t) fc (t) dt.^ (6.3)To derive the average paging delay, D SeC , for the LA sectorization, we first find the averagepaging delay, D,,(i), given that the user is in sector i. Then, we average these paging delaysgoodness of fitcall arrival p.d.f.goodness of fitcall arrival p.d.f.CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^5510.80.60.40.200^2 4^6 8^10-----------call arrival time (min)(a)0.80.60.40.200 2^4^6^8^10^12^14call arrival time (min)(b)16^180.50.40.30.20.1300^5^10^15^20^25call arrival time (min)(c)Figure 6.3 Goodness of fit of f(Bit) to the p.d.f. from simulation and the call arrival p.d.f. for 7 =40 km/hr, to = 60 sec.. m a ll = 1 call/hr. (a) R = 3 km. (b) R = 6 km. (c) R = 12 km.CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^ 56using sector probabilities to obtain DSeC . For flood paging, D„,(i) = i. For N sectors,Dsec = E Psec(i)•=iN(6.4)For spread paging, letting R be the size of the LA being paged, we have 13,,(1) = D. Also,TiSeC (2) = ( R + 1) + (33- 1). For i > 3, = (R + 1) + R (i — 2) + (T3 - 1). For Nsectors, we haveD„, = D P„,(1) + [(R + 1) + (T) — 1)]P,,(2)+ RR + 1)+R + (70- 1)]p,(3)+ RR + + 2 R^1)]P,„(4)+ [(R^R (AT — 2) + CU— 1)]Psee (N)= [P„,(1) + P„,(2) + • • • + Psec(N)]+ (D- - 1)[P,,(1)+ P,,(2) + • • • + P„,(N)]R [F„,(2) + 2 Pse,(3) + • • • (N — 1)Psec (N)]N-1=.79+R^iPsee (i+1).^ (6.5)=1To derive the average paging traffic, T,, with LA sectorization, we first find the averagepaging traffic Tsec (i) given that the user is in sector i. T„, is obtained by averaging T„.„(i) usingsector probabilities. Flood paging and spread paging have the same expression for T „JO. LetNR be the total number of cells contained in an LA of size R, as given in Eqn. (3.3) and let a; bethe fractional angle subtended by sector i, i.e., ai = T.,-7,9 where B, is the total angle subtended bysector i. We have T„,( 1)^[(T — 1)a 1 + 1] and TsEc( 2 ) = { [(NR — nal + + (T — 1)a 2 }.For i > 3, TsEc(i) = {[(NR — nal + 1] + (NR — 1)(02 +^+ • • • +^)^- 1)a,}. ForCHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^57N sectors, we haveT = [(T —^+ 1]P„,(1)+ {[(NR — nal +^(T — 1)a2}P,,(2)+ {[(NR — nal + 1] + (NR — 1)a2 (T — 1)ct3IP,(3) + • • -+ { [(NR — 1)a i +^(NT? — 1 )(a2 + • • • +^— 1)aNIP„ c (N)= [Psec(1) + Psec(2) + • • • + P„,(N)]+ (T — 1)[aiP„,(1)+ a2P„,(2)-1-^aNPsec(N)]• (NR — 1)[cciPsec(2) -F (cti^ct2)P,(3)^• • (cei + •^cleN—OPsec(N)]N N -1^= 1+ CT — 1)E ajPsec(i) + (NR —1)E Ps„(i+1)Eak.^(6.6)i=1 ^k=1If all sectors are of the same size, we have a, =^and T„, becomesN -1Ts, = 1+ (T —1) + —(NR— )^Ps„(i + 1).^(6.7)i=1For sectorization patterns 1 and 2, N = 2 and 3 respectively.6.4.2 Selective pagingIn the analysis of the average paging delay D SeC and traffic Ts, with LA sectorization, wefirst find the average paging delay D 3 (t) and traffic T „,(t) at time t. Then, we average D „,(t)and T „„(t) using the call arrival p.d.f., fc (t), given in Eqn. (5.3) to obtain DSeC and TWe will find the average paging delay, D,,(i,t), given that the user is in sector i at time tand then average D„,(i,t) using the sector probabilities at that time to obtain D s,(t). Let D(t)denote the average paging delay of selective paging without LA sectorization at time t given byEqn. (5.24). For an LA of size R and at time t, TO (1_ sEc,–, /) — 7) (t); -7) SEC (2 t) = (R^1) +D(t);D„,(3, t) = (R 1) -F R +T)(t). For i > 3, D„,,(i, t) = (R + 1) + R (i — 2)+D(t). Therefore,for N sectors, we haveD„,(1) =^P„c(i,t)+ [(R + 1) +D(t)]P„,(2,t) + • • •^CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^58+ RR + 1) R (N — 2)+75(t)]P„,(N,t)= T(t)[Ps,(1,t) + P,„(2, t) + • • • + P,„(N ,t)]+ R[P,„(2,t) + 2Psec (3, t) + • • + (N — 1)P3„(N ,t)]+ [P,„(2, t) + P„,(3, t) + • • + P„AN ,t)]N-1= 75(t) [1— Ps,(1, + RE i^+ 1,t).^(6.8)i=1Then, the average paging delay of the LA sectorization is00D sec = f D,„(t) fc (t) dt.^ (6.9)0In the derivation of TS ,(t), we will find the average paging traffic, T„,(i,t), giventhat the user is in sector i and then, average T sec (i,t) using sector probabilities to obtainTsec(t). Let NR be the total number of cells contained in an LA of size R given by Eqn.(3.3) and let a, be the fractional angle subtended by sector i, i.e., a, = awhere Oi isthe total angle subtended by sector i. Let T(t) denote the average paging traffic of selectivepaging without LA sectorization given in Eqn. (5.26). For an LA of size R and at timet, T s„.(1,t) = T (t) a l ; Tse,(2,t) = [(NR — 1)a i + 1] +T(t)a 2. For i > 2, Ts,(i,t) ={ [(NR - + 1] + (NR - 1)(a2 a3 + • • a2-1) +T(t)a,I. Therefore, for N sectors,, we haveT sec (t) = T(t)^+ {[(NR — 1)ai +1]+ T(t)a 2 IP„,(2,t)+ {[(N R — 1)a1 + 1] (NR — 1)a2 +T(t)a3}Ps ,(3,0+ • • •• {[(NR — nal + 1] + (NR — 1)(a2 + •^aN-1)+T(t)aNI/3„,(N,t)= [Psec( 2 , t) + P,(3,t) + • + P„,(N , t)]+T(t)[ctiPse,(1.t) + a 2 Psec (2, t)^• + aNP,,(N,• (NR — 1)[a1 Psec(2, t) + • • • + (al^•-•+ ctiv - 1 ).Psec(N t)]CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^59—^Psec(i,t)] +TO Ect2psec(i,t)N_,+ (NR. —^E Psec(i, 1,t)^ak. (6.10)i=1^k=1If all sectors are of the same size, ai = kr and TS ,(t) becomes— N-1 .T,,(t) = [1— P„^T(t),(1,t)]+^NR N 1^+ 14).N i=1Then, the average paging traffic of LA sectorization is00T„, = I T,,,(t) L(t) dt.0For sectorization patterns 1 and 2, N = 2 and 3 respectively.(6.11)(6.12)6.5 Numerical ResultsIn this section, the simulation results for the average paging delay and traffic for flood paging,spread paging and selective paging with LA sectorization are provided. The LA layout model inChapter 3, the location updating scheme in Chapter 4 and the random walk model in Chapter 2with infinitely long trip length were simulated for the three paging schemes with LA sectorizationpattern 1 and pattern 2. The speed of the user is 40 km/hr. We assume the mean hold time to be60 sec and the cell radius is 1 km. The average paging delay and traffic of the paging schemeswith LA sectorization are shown together with those without LA sectorization for comparison.The results for flood paging, spread paging and selective paging are shown in Fig. 6.4, 6.5and 6.6 respectively. The 99% confidence intervals for the simulation results are within +5%of the average values and are omitted from the figures. For flood paging, spread paging andselective paging with LA sectorization pattern 1, the average paging traffic can be reduced byapproximately 50% and the increase in the average paging delay is less than 10%. With LAsectorization pattern 2, the reduction in the average paging traffic is approximately 60% and theincrease in the average paging delay is less than 20%.1.4p 1.21.7.1ou400300no sectorization1patternpattern 2'a 2001 to'Ei 1000.8 02 4^6^8 10LA size (a)400>,^1.4 - • -^- no sectorization-c)0.0.s^1.2a.1patternau CsCC300200pattern 2a.)---------------^- -co c).0 100CC0.8 02 4^6^8 10LA size (b)8 102^4^6LA size8 102^4^6LA size6420-c)01).0.0n.C)C)8 102^4^6LA size8 102^4^6LA size- • - • • no sectorization- pattern 1- - - - • pattern 21082^4^6LA size6420C)OD.5ouC)CCC)- • - • no sectorizationpattern 1- - - - • pattern 20(a)CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^60Figure 6.4 Performance of flood paging without LA sectorization, with LA sectorization pattern 1 and with pattern2 for 7 = 40 km/hr, th = 60 sec,^= 1 call/hr and red/ = 1 km. (a) Analysis. (a) Simulation.Figure 6.5 Performance of spread paging without LA sectorization, with LA sectorization pattern 1 and with pattern2 for 7 = 40 km/hr, th = 60 sec,^= 1 call/hr and r,en = 1 km. (a) Analysis. (a) Simulation.u 60• 40. 1)0.0 2008108 10(a)2^4^6LA size2^4^6LA size- - - no sectorizationpattern 1^ pattern 2-------------- ---- CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^61(b)- . - . - no sectorization^ pattern 1^ pattern 22^4^6^8^10LA size2^4^6^8^1 0LA size• 60E`140n.V 20ts0Figure 6.6 Performance of selective paging without LA sectorization, with LA sectorization pattern 1 and withpattern 2 for iT = 40 km/hr,th = 60 sec, Acan = 1 ca11/hr and r,ert = 1 km. (a) Analysis. (a) Simulation.We next examine the performance of the paging scheme with LA sectorization due to changesin such parameters as mean speed (v), mean velocity hold time ) and call arrival rate (kali).In the sensitivity tests, we fix two of the parameters at the reference values Cf = 40 km/hr, tj, =60 sec and Acall = 1 call/hr) and vary the third parameter. The simulation results for flood paging,spread paging and selective paging are plotted against the mean speed in Fig. 6.7, against themean velocity hold time in Fig. 6.8 and against the call arrival rate in Fig. 6.9. The 99%confidence intervals for the simulation results are within ±5% of the average values and areomitted from the figures. These figures show that the paging schemes are not very sensitive to7/.. and Acall•- - • - Flood^0- Spread x^ Selectivepattern 1pattern 220^30^40^50mean speed (km/hr)2onro°'1.53.2. ---------^ -a^ -a60oti40a.01)ctl▪ 5• 21 t - -'- - - ,-,-,^_,.20^30^40^50^20mean speed (kin/hr)(b)30^40mean speed (km/hr)5030^40^50mean speed (km/hr)(a)Flood^0 pattern 1Spread x pattern 2Selective------- --------- --------0^-0-^----0- • - • - Flood^0 pattern 1- Spread x pattern 2^ Selective200150oL• 100op4.5CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^6220^30^40^50^20^30^40^50^mean speed (km/hr) mean speed (km/hr)(c)Figure 6.7 Performance of LA sectOrization on flood paging, spread paging and selective paging versus user meanspeed for h = 60 sec, A c ,i] = lcall/hr and r„ll = 1 km. (a) LA size = 2. (b) LA size = 6. (c) LA size = 10.velocity hold time for 7 = 40 km/hr, A can = lcall/tu- and r„ll= 1 km. (a) LA size = 2. (h) LA size = 6. (c) LA size = 10.CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^63121- - • - Flood^0 pattern I- Spread X pattern 2^ Selective- -x -------- -o -------7. )0(^=^= = =-040^60^80 100 120mean velocity hold time (sec)- • - • - Flood^0 pattern I- Spread X pattern 2^ Selective40^60^80 100 120mean velocity hold time (sec)- • - • - Flood^0 pattern I- Spread X pattern 2^ Selective-^- - -----^--------= --40^60^80 100 120mean velocity hold time (sec)(c)Figure 6.8 Performance of LA sectorization on flood paging, spread paging and selective paging versus user mean40^60^80 100 120mean velocity hold time (sec)40^60^80 100 120mean velocity hold time (sec)40^60^80 100 120mean velocity hold time (sec):05^1^1.5^2call arrival rate (calls/hr)5 1.5call arrival rate (calls/hr)CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATIONx^ 12^x e^. E.,.:,..,^10T., - • - • - Flood^0 pattern 1^‘'dSpread X pattern 2.r Selective .?co^ VI.:1.5 t,".4v.,^x^x^x^xp e 0 0^I)Cd Cd864Flood^0 pattern ISpread x pattern 2Selective(a)80Eu 60oA7 40x -------- -------- x-------e -------- -------- o^:L%) 210 5^1^1.5call arrival rate (calls/lu)2^8 5^1^1.5call arrival rate (calls/hr)(b)43205 1^1.5- • - • - Flood^0 pattern ISpread X pattern 2^ Selectivecall arrival rate (calls/hr) call arrival rate (calls/hr)(c)Figure 6.9 Performance of LA sectorization on flood paging, spread paging and selective paging versus the callarrival rate for 7 = 40 km/hr, ih = 60 sec and rrell = 1 km. (a) LA size = 2. (h) LA size = 6. (c) LA size = 10.CHAPTER 7SENSITIVITY OF PAGINGSCHEMES TO UNCERTAINTY INMOBILITY PARAMETER VALUESIn the selective paging scheme, the cellular system keeps estimates of the user mobilityparameters : the angular deviation parameter (as), mean speed (v), mean velocity hold time (th)and mean trip length (d), and uses them to estimate the position of the user when a call comesin. In Section 5.3, we analyzed the performance of selective paging assuming that the system hasexact knowledge of the mobility parameter values. It was found that selective paging gives betterperformance than spread paging in terms of average paging delay and traffic. In this chapter, weexamine the sensitivity of selective paging to uncertainty in mobility parameter values.7.1 Angular Deviation ParameterIn the user mobility model, the parameter as affects how close the actual user directionis to the principal direction (see Section 2.1). In Section 2.1, we determine as using the 95%criterion, i.e., with probability 0.95, a user will choose to travel forward. The correspondingvalue of a9 is 4.2. In this section, we examine the sensitivity of selective paging to uncertaintyin this parameter value. In the sensitivity tests, we assume that the mobility parameters keptby the system are T = 40 km/hr, 7h = 60 sec, d = oc and a9 = 4.2 (95% criterion), and theuser has the same mobility parameters except for a9. We examine two cases in which 85% and98% criteria are used for the user with corresponding a0 values of 1.4 and 10.3 respectively.The performances of selective paging and spread paging are obtained from simulation for cellradius rcen = 1 km and call arrival rate Acaii = 1 call/hr. The results are shown in Fig. 7.1. The99% confidence intervals are within ±5% of the average values shown and are omitted from the65CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY^ 66IN MOBILITY PARAMETER VALUESfigure. Spread paging is not sensitive to the changes of ao and both the average paging delayand traffic change by less than 5%. In selective paging, there is practically no change in theaverage paging delay and traffic in the performance with 98% criterion. For the performancewith 85% criterion, there are significant increases in both average paging delay and traffic. Foran LA of size 10, the average paging delay increases from 1.75 to 2.7 and the average pagingtraffic increases from 55 to 96. In both cases, selective paging still has a better performance thanspread paging in terms of average paging delay and traffic.7.2 Mean SpeedIn this section, we examine the sensitivity of selective paging to uncertainty in user meanspeed. We let the mobility parameters kept by the system be T = 40 km/hr, = 60 sec, d = ocand ao = 4.2 (95% criterion). The user has the same set of mobility parameters except for T.We examine two cases in which the actual user mean speeds are 20 km/hr and 60 km/hr. Theperformances of selective paging and spread paging are obtained from simulation for rcell = 1 kmand Acall = 1 call/hr. The results are shown in Fig. 7.2. The 99% confidence intervals are within±5% of the average values shown. Spread paging is not very sensitive to the changes in the usermean speed; the changes in the average paging delay and traffic are less than 10%. The higherthe user mean speed is, the higher are the average paging delay and traffic. The reason is thatwith higher mean speed, the user travels farther away from the LA center when a call comes in;therefore, more rings are paged to locate the user, resulting in more delay and traffic. Selectivepaging is increasingly sensitive to uncertainty in user mean speed as the LA size increases. Incase 1 when the actual user mean speed is 60 km/hr and the system estimates it to be 40 km/hr,the system underestimates the radial distance travelled by the user from the LA center, resultingin more paging delay and traffic. For an LA of size 10, the average paging delay increases from1.7 to 4.5 and the average paging traffic increases from 55 to 102. Nevertheless, selective pagingstill gives a better performance. In case 2 when the actual user mean speed is 20 km/hr and the1 07 8 92^3^4^5^6LA size(a)65.554.543.532.5285% criterion95% criterion98% criterion0^Selective pagingX^Spread paging107 982^3^4^5^6LA size(b)1201008060402085% criterion95% criterion98% criterion0^Selective pagingX^Spread pagingCHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY^ 67IN MOBILITY PARAMETER VALUESFigure 7.1 Sensitivity of the performances of selective paging and spread paging touncertainty in ao for 7 = 40 km/hr, 7,, = 60 sec. d = x, r,en = 1 km. ) can = 1 call/hrand system's^= 4.2. (a) Average paging delay. (b) Average paging traffic.CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY^ 68IN MOBILITY PARAMETER VALUESsystem estimates it to be 40 km/hr, the system overestimates the radial distance travelled by theuser from the LA center resulting in more delay and traffic. For an LA of size 10, the averagepaging delay increases from 1.7 to 3.9 and the average paging traffic increases from 55 to 144.The increase in the average paging delay is roughly the same as that in case 1. However, theincrease in the average paging traffic is much greater. The reason is that with roughly the samenumber of additional rings paged due to uncertainty in user mean speed, the system tends to firstpage outer rings which contain more cells while in case 1, inner rings are likely to be first paged.This also explains why the average paging delay in case 2 is smaller than that in spread pagingwhile the average paging traffic is higher.7.3 Mean Velocity Hold TimeIn the user mobility model of Section 2.1, the user holds a speed and a direction for somerandom time, th, with mean, ti„ before choosing a new speed and a new direction. In this section,we examine the sensitivity of selective paging to uncertainty in th. We assume that the mobilityparameters kept by the system are 73= 40 km/hr, th = 60 sec, d = oc and a = 4.2 (95% criterion).The user has the same set of mobility parameters except for th. We examine two different actual. user values of th = 30 sec and 90 sec. The performances of selective paging and spread pagingare obtained from simulation for rcen = 1 km and kale = 1 call/hr. The results are shown inFig. 7.3. The 99% confidence intervals are within ±5% of the average values shown. Bothschemes are not very sensitive to uncertainty in th. In spread paging, there is practically nochange in the average paging delay and traffic. In selective paging, the changes in the averagepaging delay and traffic are less than 10%. In both cases examined, selective paging still givesa better performance..C55 10mean speed = 20 km/hr^ mean speed = 40 km/hr mean speed = 60 km/hrO Selective paging• Spread pagingCHAPTER 7 SENSITIVITY OF PAGIVG SCHEMES TO UNCERTAINTY^ 69IN MOBILITY PARAMETER VALUES65.554.5T.)-a^4oq•-1.5- • - - • mean speed = 20 km/hr^ mean speed = 40 km/hr mean speed = 60 km/hrO Selective pagingx^Spread paging2^3^4^5^6^7^8^9^10LA size(a)160140120U$.• 100acda. 80di)cd604020LA size(b)Figure 7.2 Sensitivity of the performances of selective paging and spread paging touncertainty in 17 for 7h = 60 sec, 7 = x,, a e = 4.2, r,en = 1 km, kali = 1 call/hr andsystem's IT = 40 km/hr. (a) Average paging delay. (b) Average paging traffic.12010080604020mean hold time = 30 secmean hold time = 60 secmean hold time = 90 sec0^Selective pagingSpread paging65.554.543.532.521.5mean hold time = 30 secmean hold time = 60 secmean hold time = 90 secCHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY^ 70IN MOBILITY PARAMETER VALUES02^3^4^5^6^7^8^9^10LA size(a)2^3^4^5^6^7^8^9^10LA size(b)Figure 7.3 Sensitivity of the performances of selective paging and spread paging touncertainty in 7h for F = 40 km/hr, d = oc. 0, 0 = 4.2. r,11 = 1 km. kali = 1 call/hrand system's 7h = 60 sec. (a) Average paging delay. (b) Average paging traffic.CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY^71IN MOBILITY PARAMETER VALUES7.4 Mean 'Drip LengthFor convenience in analysis, the trip length in the user mobility model used in selectivepaging is taken to be oo. However, half of automobile trips in the United States are under 8 kmlong [37]. In this section, we examine the sensitivity of selective paging to uncertainty in thetrip length. We assume that the mobility parameters kept by the system are Ti = 40 km/hr, =60 sec, d = oo and ae = 4.2 (95% criterion). The user has the same set of mobility parametersexcept for d. We examine two cases, d = 8 km and d = 16 km. The performances of selectivepaging and spread paging are obtained from simulation for rcell = 1 km and Acall = 1 call/hr.The results are shown in Fig. 7.4. The 99% confidence intervals are within ±5% of the averagevalues shown. In spread paging, the performance becomes more sensitive to the trip length asthe LA size increases. The average paging delay and traffic decrease as the trip length decreases.For an LA size of 10, the average paging delay decreases to 4.8 from 5.1 for d = 16 km and to3.9 for d = 8 km; the average paging traffic decreases to 81 from 108 for d = 16 km and to 51for d = 8 km. Selective paging is not very sensitive to uncertainty in the trip length. For an LAof size 10, the average paging delay changes from 1.7 to 1.9 for both d = 8 km and d = 16 kmand the average paging traffic changes from 55 to 50 for d = 16 km and to 40 for d = 8 km. Inboth cases examined, selective paging still gives a better performance.mean trip length = 8 kmmean trip length =16 kmmean trip length =infinitely longO Selective pagingX^Spread paging65.55cc 4.5c^4•—• 3.5b4,32.521.5120100806040207^8^9^102^3^4^5^6LA size(b)(a)X 'mean trip length = 8 kmmean trip length 16 kmmean trip length = infinitely longO Selective pagingX^Spread pagingCHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY^ 72IN MOBILITY PARAMETER VALUES2^3^4^5^6LA sizeFigure 7.4 Sensitivity of the performance of selective paging and spread paging touncertainty in 7 for F = 40 km/hr, ih = 60 sec, (19 = 4.2, r„ll = 1 km, Acall = 1call/hr and system's 7/ = x. (a) Average paging delay. (b) Average paging traffic.Ce7^8^9^10CHAPTER 8CONCLUSION AND FUTURE WORKThis thesis has examined the problem of locating a mobile user in a cellular system. Tosupport location tracking of a mobile user, the idea of overlapping LA's was used. Two LApaging schemes, namely spread paging and selective paging, were proposed to determine thecell currently hosting a mobile user. A two-dimensional directional random walk process wasproposed and used to model user mobility for performance evaluation. In comparison to aconventional flood paging scheme, spread paging and selective paging can yield typical pagingtraffic reductions of 50%. Selective paging performs better than spread paging in terms of averagepaging delay and average paging traffic. The disadvantage is greater implementation complexity.To further reduce the paging traffic, an LA sectorization technique was applied to spreadpaging and selective paging. Two sectorization patterns are examined. The results show thatsectorization can yield typical paging traffic reductions of about 50% without any significantincrease in paging delay.The sensitivity of spread paging and selective paging to uncertainty in user mobility parametervalues, such as the angular deviation parameter, mean speed, mean velocity hold time and meantrip length, was studied. It was found that spread paging is most sensitive to the mean trip lengthwhereas selective paging is most sensitive to uncertainty in user mean speed.Among the topics which could be further investigated are :• To analyze the effects of queueing of paging requests on paging delay.• To analyze the paging scheme performance using different user mobility models e.g. mobilitymodel for portable telephone users instead of vehicular telephone users.7374BIBLIOGRAPHY[1] D. C. Cox, "Personal Communications — A View Point," IEEE Commun. Mag., pp. 8-20,Nov. 1990.[2] A. R. Potter, "Implementation of PCNs Using DCS 1800," IEEE Commun. Mag., pp.32-36, Dec. 1992.[3] S. Chia, "The Universal Mobile Telecommunication System," IEEE Commun. Mag., pp.54-62, Dec. 1992.[4] D. C. Cox, "Wireless Network Access for Personal Communications," IEEE Commun.Mag., pp. 96-115, Dec. 1992.[5] D. C. Cox, "Portable Digital Radio Communications — An Approach to TetherlessAccess," IEEE Commun. Mag., pp. 30-39, July 1989.[6] D. C. Cox, "A Radio System Proposal for Widespread Low-Power Tetherless Commu-nications," IEEE Trans. Commun., vol. 39, no. 2, pp. 324-335, Feb. 1991.[7] G. Calhoun, Digital Cellular Radio. Norwood, MA, Artech House: Englewood Cliffs,1988.[8] W. C-Y. Lee, Mobile Cellular Telecommunication Systems. McGraw Hill, 1989.[9] A. Nakajima, K. Yamamoto and H. Sawada, "Automatic Pursuit Routing for MobileCommunications Network," Electronics and Communications in Japan, part 1, vol. 73,no. 3, pp. 81-91, 1990.[10] G. D. Ott, "Vehicle Location in Cellular Mobile Radio System," IEEE Trans. on VehicularTechnology, vol. VT-26, no. 1, pp. 43-46, Feb. 1977.[11] A. Murase and K. Imamura, "Location of Mobile Subscriber Station on Land MobileRadio with MSSC," Electronics and Communications in Japan, part 1, vol. 69, no. 4,pp. 85-93, 1986.[12] A. Okasaka, S. Onoe, S. Yasuda and A. Maebara, "A New Location Updating Methodfor Digital Cellular Systems," IEEE 41' Veh. Tech. Conf., St. Louis, MO, pp. 345-350.May 1991.[13] I. Seskar, S. V. Mark, J. Holtzman and J. Wasserman, "Rate of Location Area Updatesin Cellular Systems," IEEE 42'1 Veh. Tech. Conf., Denver, Colorado, pp. 694-697, May1992.75[14] R. Thomas, H. Gilbert and G. Mazziotto, "Influence of the Moving of the Mobile Stationson the Performance of a Radio Mobile Cellular Network," 3rd Nordic Seminar on DigitalLand Mobile Radio Communications, pp. 1-9, Sept. 1988.[15] Y. Akaiwa, "A Conceptual Design of Microcellular Radio Communications System,"IEEE 40 th Veh. Tech. Conf., Orlando, Florida, pp. 156-160, May 1990.[16] E. G. Tiedemann, "Registration in Cellular Telephone Systems," IEEE InternationalSymposium on Personal, Indoor and Mobile Radio Communications, King's College,London, Sept. 1992.[17] K. Imamura and A. Murase, "Mobile Communication Control Using Multi-transmitterSimul/Sequential Casting (MSSC)," IEEE 36th Veh. Tech. Conf., pp. 334-341, May 1986.[18] D. Munoz-Rodriguez, "Cluster Paging for Travelling Subscribers," IEEE 40th Veh. Tech.Conf., Orlando, Florida, pp. 748-753, May 1990.[19] J. Lehmusvuori, "Network Aspects of the UMTS," 1992 IEEE International Conferenceon Selected Topics in Wireless Communications, Vancouver, B.C., pp. 16-20, June 1992.[20] 0. Grimlund and B. Gudmundson, "Handoff Strategies in Microcellular Systems," IEEE41' Veh. Tech. Conf, St. Louis, MO, pp. 505-510, May 1991.[21] L. G. Anderson, "A Simulation Study of Some Dynamic Channel Assignment Algorithmsin a High Capacity Mobile Telecommunications System," IEEE Trans. on Veh. Tech., vol.VT-22, no. 4, pp. 210-217, Nov. 1973.[22] M. Zhang and T. S. P. Yum, "Comparisons of Channel-Assignment Strategies in CellularMobile Telephone Systems," IEEE Trans. on Veh. Tech., vol. 38, no. 4, pp. 211-215,Nov. 1989.[23] J. Tajima and K. Imamura, "A Strategy for Flexible Channel Assignment in MobileCommunication Systems," IEEE Trans. on Veh. Tech., vol. 37, no. 2, pp. 92-103, May1988.[24] S. Tekinay and B. Jabbari, "Handover and Channel Assignment in Mobile CellularNetworks," IEEE Commun. Mag., pp. 42-46, Nov. 1991.[25] S. M. Elnoubi, R. Singh and S. C. Gupta, "A New Frequency Channel AssignmentAlgorithm in High Capacity Mobile Communication Systems," IEEE Trans. on Veh.Tech., vol. VT-31, no. 3, pp. 125-131, Aug. 1982.[26] S. S. Rappaport, "The Multiple-Call Hand-Off Problem in High-Capacity Cellular76Communication Systems," IEEE Trans. on Veh. Tech., vol. 40, no. 3, pp. 546-557, Aug.1991.[27] M. Gudmundson, "Analysis of Handover Algorithms," IEEE 41' Veh. Tech. Conf., St.Louis, MO, pp. 537-541, May 1991.[28] D. Hong and S. S. Rappaport, "Traffic Model and Performance Analysis for Cellular Mo-bile Radio Telephone Systems with Prioritized and Nonprioritized Handoff Procedures,"IEEE Trans. on Veh. Tech., vol. VT-35, no. 3, pp. 77-92, Aug. 1986.[29] W. Fuhrmann and A. Eizenhofer, "Radio Access Protocol of the New GSM Land MobileCommunication Standard," IEEE 38 th Veh. Tech. Conf., pp. 30-37, May 1988.[30] A. Eizenbofer and W. Fuhrmann, "Validation of the GSM Radio Interface SignallingProtocols — Selected Studies," IEEE 41" Veh. Tech. Conf, St. Louis, MO, pp. 333-338,May 1991.[31] M. Pautet and M. Mouly, "GSM Protocol Architecture: Radio Sub-System Signalling,"IEEE 41' Veh. Tech. Conf., St. Louis, MO, pp. 326-332, May 1991.[32] Electronic Industries Association, "Dual-Mode Subscriber Equipment Network Equip-ment Compatibility Specification," Interim Standard 54, Dec. 1989.[33] D. C. Cox, H. W. Arnold and P. T. Porter, "Universal Digital Portable Communications:A System Perspective," IEEE Journal on Selected Areas in Commun., vol. SAC-5, no. 5,pp. 764-773, June 1987.[34] A. Nakajima, M. Eguchi, T. Arita and H. Takeda, "Intelligent Digital Mobile Com-munications Network Architecture," Proc. of XIII International Switching Symposium,Stockholm, Sweden, vol. VI, May-June 1990.[35] M. Wizagall, "ECR 900: The Pan-European Digital Mobile Communication System,"International Telecommunications Symposium, pp. 263-272, 1988.[36] Y. N. Dogmata, T. X. Brown and E. C. Posner, "Call Setup Strategy Tradeoffs forUniversal Digital Portable Communications," Computer Networks and ISDN System, vol.20, pp. 455-465, 1990.[37] N. Kennedy, Fundamentals of Traffic Engineering, 8th edition. Berkeley, Calif. Inst. ofTraffic and Transportation Engineering, Univ. of Calif. Berkeley, 1973.[38] D. L. GerLough, M. J. Huber, Traffic Flow Theory. Transportation Research Board,National Research Council, Washington, D. C., 1975.77[39] H. J. W. Leong, "The distribution and Trend of Free Speeds on Two-Lane Rural Highwaysin New South Wales," Proc. Austr. Road Res. Board, 4: pp. 791-814, 1968.[40] D. J. Goodman, "Cellular Packet Communications," IEEE Trans. Commun., vol. 38, no.8, pp. 1272-1280, Aug. 1990.[41] A. Nakajima, M. Kuramoto, K. Watanabe and M. Eguchi, "Intelligent Digital MobileCommunications Network Architecture for Universal Personal Telecommunications(UPT) Services," IEEE 41' Veh. Tech. Conf., St. Louis, MO, pp. 83-87, May 1991.78APPENDIX AALPHA PROBABILITY DENSITY FUNCTIONThe Alpha probability density function (p.d.f.) is given by[1-1-cr 2 (x-i.) 2 1tan- 'a x— w< x<x wf(x) = 1 0and its cumulative densityF(x) =function (c.d.f.)^is01 tan- 1 1a(x-)1(aw)12;^otherwisex <^- wx - w<x<x+ww < x.(A.1)(A.2)2^tan-1 (aw)1There are three parameters ( -x, w, a) which control different properties of the p.d.f. The p.d.f. issymmetric about the mean -3-; at which point the p.d.f. takes on its maximum value=a2 tan -1 (aw).^(A.3)The width of the interval of the random variable is defined by 2w. The parameter a controlsthe deviation of the random variables from the mean value. The larger a is, the less the randomvariable deviates from the mean. In the extreme case when a tends to zero, the Alpha p.d.f.becomes a uniform distribution; when a tends to infinity, the p.d.f. becomes a delta function. Theeffects of a on the p.d.f. are illustrated in Fig. A.1. The variance is determined by w and a as2Cr = a tan-1 (aw)^a 2 .(A.4)r-0.8^-0.6^-0.4^-0.2^0^0.2^0.4^0.6^0.8xFigure A.1 Effects of a on Alpha p.d.f. with w = 1 and x = 07980APPENDIX BASYMMETRIC GAUSSIANPROBABILITY DENSITY FUNCTIONThe asymmetric Gaussian p.d.f. is a modification of the Gaussian p.d.f. in which the p.d.f.is no longer symmetric about the mean. It is given byf(x) =x < 771m < X(B.1)Ai^e^;1/27ra.=L.1_=_„20/2--- e^;A2 27rcrand its c.d.f. isA14, ( 17:71 ) ;^x < 711F(x) = (B.2)+ A2 ['12^("72s)1 ;^711 < Xwherea2 = ry ai (B.3)Al^ 2 (B.4)= 1 + 72'yA2 (B.5)—1+ yx1^1^yl4)(x)^dy.= (B.6)_COThere are three parameters : nz, aj and^The peak value of the p.d.f. occurs at mmax [f (x)] = f(m)= A2V2 7 Cq= Al 1V2 r cri1(B.7)0.60.50.4030.20.1 812xFigure B.1 Effects of -y on Asymmetric Gaussian p.d.f. with m = 0 and al = 1.We combine two half Gaussian p.d.f.'s of variances, ol and 0-1, on the left and right sides ofm respectively. The left and right sides are scaled such that the p.d.f. is continuous at m andthe area sum is one. Q 1 controls the spread of the p.d.f. and y determines how asymmetric thep.d.f. is. When y > 1, the right side is wider than the left side. If 7 = 1, the p.d.f. becomes theGaussian p.d.f. The effects of 7 on the p.d.f. are shown in Fig. B.1.To find the mean ± of the p.d.f., we first consider the mean of a scaled half Gaussian p.d.f.BG = I x €--1.‘; dx0V270- 2= B^1c 5,2^ id(2)x^2iro-2 0 2B ^1 ( 2a2) [c _ 1_"cr 72 I OC ,=27 — 2 r.oB.= ^ Q.-\/772 (B.8)The mean of the asymmetric Gaussian p.d.f. isI x f(x) dx-00in 00A l^—^2^ A2X 2 dx^x ^2'rcri2 ..\/rcrl—00^ ine^2°2 dx^o CC_ y.2^ 2Al^ A2^2= in+ I x e 2°f dx + I x e 2°2 dx.V271- oq V27r al^—00^ 0Substituting Eqn. (B.3), (B.4), (B.5) and (B.8) in (B.9), we have= m+= in +Al ^A2ai alL^\ 127r1f2Tr 2r^2^2-y1 + 7 cri ^+^°-1 ]Vt2jra1^2 (^1 += in+ 7 2)r 1 += in +^— 1 ).^ (B.10)7T82(B.9)83APPENDIX CTAIL PROBABILITY OF THE CALL ARRIVALPROBABILITY DENSITY FUNCTIONIn Section 5.1.1, the call arrival p.d.f., fdt), in the paging scheme performance analysis isapproximated byMt) _wherecaA Ali C —A" "i1^; 0< t< cB c "?^; C < iV2 ir cr?0^; otherwise(C.1)A =^1^ (C.2)1 — eA-1/ 7R,B = 2 [1 — A (1 —^11,^(C.3)B211/2 Acair C — A “'"= f (if?) g Ct h),Cfc = (C.4)(C.5)(C.6)1 0.00023 (7R) 2 + 0.4307 (TR) — 8.7879^; 0 < 7R < 9000.8591 (tR) — 204.8937^; 900 < 7Rg(11,) = —0.00167h + 1.1041^; 30 < tip < 180.^(C.7)f (7R) =andIn this section, we want to find the tail probability, f, that a call arrives at time t > t*. For t* < c,= f f( 7) drt.For t* > c,84t-= 1 — f Mr) drt-= 1 — A A C AT dr= 1 — A (1 — C At* ).^ (C.8)= Mr) drt"coB^tr-o2 e 2 °? drV2 ac?t-)= B Q t* c)(C.9)whereQ(x) -P'= f^dY.SrFrom Eqn. (C.3), B is upper bounded by 2; therefore,< 2 Q (t* —cQt.For example, if^= 1.65 (i.e. t* = c + 1.65 a c) , Q (") = 0.0495 and E < 0.099.(C.10)(C.11)
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Location updating and paging strategies in a cellular...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Location updating and paging strategies in a cellular system Lam, Kenny C. H. 1993
pdf
Page Metadata
Item Metadata
Title | Location updating and paging strategies in a cellular system |
Creator |
Lam, Kenny C. H. |
Date Issued | 1993 |
Description | The problem of locating a mobile user in a cellular system is addressed. The mobility of a user is modelled by a two-dimensional directional random walk process. A location updating scheme based on overlapping location areas (LA's) is presented for keeping track of the LA a user is in. Two LA paging schemes, namely spread paging and selective paging, are proposed and are compared to a conventional flood paging scheme in which all cells in the LA are paged simultaneously. It is found that both spread paging and selective paging can yield typical paging traffic reductions of more than 50%. The cost is a small increase in the average paging delay. Selective paging performs better than spread paging in terms of both average paging delay and average paging traffic, but is more complex to implement. An LA sectorization technique is applied to spread paging and selective paging to further reduce paging traffic. Two sectorization patterns are examined. The results show that sectorization can yield typical average paging traffic reductions of about 50%. The resulting increases in paging delay are negligible for both patterns. The sensitivity of spread paging and selective paging to uncertainty in user mobility parameter values, such as the angular deviation parameter, mean speed, mean velocity hold time and mean trip length, is studied. It is found that spread paging is most sensitive to the mean trip length of a user while selective paging is most sensitive to uncertainty in user mean speed. |
Extent | 3561872 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2008-09-10 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0064908 |
URI | http://hdl.handle.net/2429/1826 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1993-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1993_spring_lam_kenny.pdf [ 3.4MB ]
- Metadata
- JSON: 831-1.0064908.json
- JSON-LD: 831-1.0064908-ld.json
- RDF/XML (Pretty): 831-1.0064908-rdf.xml
- RDF/JSON: 831-1.0064908-rdf.json
- Turtle: 831-1.0064908-turtle.txt
- N-Triples: 831-1.0064908-rdf-ntriples.txt
- Original Record: 831-1.0064908-source.json
- Full Text
- 831-1.0064908-fulltext.txt
- Citation
- 831-1.0064908.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0064908/manifest