LOCATION UPDATING AND PAGING STRATEGIES IN A CELLULAR SYSTEM by KENNY C. H. LAM B.A.Sc (Hons.), The University of British Columbia, 1991 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA April 1993 © Kenny C. H. Lam, 1993 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. (Signature) Department of The University of British Columbia Vancouver, Canada Date DE-6 (2/88) ABSTRACT 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. ii TABLE OF CONTENTS ABSTRACT^ ii LIST OF FIGURES^ vi LIST OF TABLES^ x ACKNOWLEDGEMENT^ xi CHAPTER 1 INTRODUCTION ^ 1 1.1 Background ^ 1 1.2 Motivations and Objectives ^ 3 1.3 Outline of the Thesis ^ 4 CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER ^ 5 2.1 Directional Random Walk ^ 5 2.2 Stochastic Model ^ 9 2.2.1 Simulation ^ 10 2.2.2 Radial distance p d f.^ 10 2.2.3 Angular deviation p.d.f. ^ 15 CHAPTER 3 CELL AND LOCATION AREA LAYOUT MODEL ^21 3.1 Cell Map ^ 21 3.2 Location Area ^ 23 CHAPTER 4 LOCATION UPDATING SCHEME ^ 25 4.1 Overlapping Location Areas ^ 25 4.2 Conditions for Location Updates ^ 26 4.3 Effective Ring Radius^ 26 4.4 Location Updating Traffic ^ 111 31 CHAPTER 5 LOCATION AREA PAGING SCHEMES ^ 5.1 Preliminaries ^ 35 35 5.1.1 Call arrival model ^ 35 5.1.2 LA ring probability ^ 39 5.2 Paging Schemes : Description and Performance Analysis ^41 5.2.1 Flood paging ^ 41 5.2.2 Spread paging ^ 42 5.2.3 Selective paging ^ 43 5.3 Numerical Results ^ 44 CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION 50 6.1 LA Sectorization ^ 50 6.2 LA Sector Probability ^ 52 6.4 Performance Analysis of the Paging Schemes with Location Area Sectorization . ^ 54 6.4.1 Flood paging and Spread Paging ^ 54 6.4.2 Selective paging ^ 57 6.5 Numerical Results^ 59 CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY IN MOBILITY PARAMETER VALUES ^ 65 7.1 Angular Deviation Parameter ^ 65 7.2 Mean Speed ^ 66 7.3 Mean Velocity Hold Time ^ 68 7.4 Mean Trip Length ^ 71 iv CHAPTER 8 CONCLUSION AND FUTURE WORK BIBLIOGRAPHY ^ ^ APPENDIX A ALPHA PROBABILITY DENSITY FUNCTION 73 74 ^ 78 APPENDIX B ASYMMETRIC GAUSSIAN PROBABILITY DENSITY FUNCTION 80 APPENDIX C TAIL PROBABILITY OF THE CALL ARRIVAL PROBABILITY DENSITY FUNCTION^ 83 LIST OF FIGURES 2.1 Illustration of the random walk model. ^ 6 2.2 Speed distribution with mean speed = 1 km/hr. ^ 8 2.3 p.d.f. of the angular deviation ^ 8 2.4 Radial distance p.d.f.'s of the random walk with v = 30 km/hr and th = 60 sec. (a) 11 Simulation. (b) Analysis ^ 2.5 Angular deviation p.d.f.'s of the random walk with I., = 30 km/hr and th = 60 sec. (a) Simulation. (b) Analysis ^ 11 2.6 Illustration of the analytical directional random walk model. ^ 12 2.7 N(t) versus -* for parameter sets IT (km/hr), t h (sec)} : (25, 30), (25, 60), (35, 14 60), (35, 90), (45, 90) and (45, 180). ^ 2.8 Goodness of fit of the analytical radial distance p.d.f. (a)^= 90 sec. (h) T = 35 km/hr^ 16 2.9 The variance of the Gaussian part of the angular deviation p.d.f. versus ^for th parameter sets IT(km/hr), th (sec)} : (25, 30), (25, 60), (35, 60), (35, 90), (45, 17 90) and (45, 180). versus 7t ^ 2.10 a A of the Alpha part of the angular deviation p.d.f. versus t for parameter sets IT(km/hr),th (sec)} : (25, 30), (25, 60), (35, 60), (35, 90), (45, 90) and (45, 180). ^ 2.11 Weighting function p (t , 7h) versus^ to ^ 19 19 2.12 Goodness of fit of the analytical angular deviation p.d.f. (a) 7 / , = 90 sec. (h) T = 35 20 km/hr^ 3.1 Cell grid of a cellular system. ^ 22 3.2 Equivalent radius of a cell . ^ 22 3.3 Location area of size = 3 ^ 23 vi ^ 4.1 A mobile user's changing LA viewed as entering the new LA at some point on its circumference 27 4.2 Geometry for the evaluation of the effective radius of the i th ring. ^ 28 4.3 Evaluation of cos(l3) using Pythagoras's theorem ^ 29 30 4.4 Geometry for evaluating O. ^ 4.5 Illustration of the updating traffic analysis ^ 32 4.6 Location updating traffic versus the equivalent LA radius for T = 40 km/hr,^= 60 sec and d = 20 km. (a) LA size = 1. (b) LA size = 5. (c) LA size = 10 ^ 34 5.1 An exponential p.d.f. of the inter-call arrival time with Acall = 1 call/hr and 7R = 40 37 min^ 5.2 P.d.f.'s of the call arrival time with respect to the last location updating time for T, = 39 40 km/hr, th = 60 sec and Acall = 1 call arrival/hr. ^ 5.3 Goodness of fit of the p.d.f.'s in Fig. 5.2. ^ 40 5.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. . 46 5.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) 47 LA size = 10. 5.6 Performances of spread paging and selective paging versus the user mean velocity hold time for T,. = 40 km/hr, A call = 1 call/hr and rcell = 1 km. (a) LA size = 2. (1) 48 LA size = 6. (c) LA size = 10. ^ 5.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) LA 49 size = 10^ 6.1 Sectorization of an LA. (a) sectorization of an LA of size 2. (b) idealized sectorized 51 LA. ^ 6.2 Grouping of the sectors for sectorization patterns. (a) Pattern 1. (b) Pattern 2. . .. 52 vii 6.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.. 55 6.4 Performance of flood paging without LA sectorization, with LA sectorization pattern 1 and with pattern 2 for T = 40 km/hr, th = 60 sec, m alt = 1 call/hr and rcell = 1 km. (a) Analysis. (a) Simulation 60 6.5 Performance of spread paging without LA sectorization, with LA sectorization pattern 1 and with pattern 2 for T = 40 km/hr, th = 60 sec, k a li = 1 call/hr and rcell 60 = 1 km. (a) Analysis. (a) Simulation. ^ 6.6 Performance of selective paging without LA sectorization, with LA sectorization pattern 1 and with pattern 2 for T = 40 km/hr, th = 60 sec, can = 1 call/hr and rcell 61 = 1 km. (a) Analysis. (a) Simulation. ^ 6.7 Performance of LA sectorization on flood paging, spread paging and selective paging versus 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. 62 6.8 Performance of LA sectorization on flood paging, spread paging and selective paging versus user mean velocity hold time for T = 40 km/hr, Acall lcall/hr and rcell = 1 63 km. (a) LA size = 2. (b) LA size = 6. (c) LA size = 10. ^ 6.9 Performance of LA sectorization on flood paging, spread paging and selective paging versus the call arrival rate for T = 40 km/hr, th = 60 sec and rcell = 1 km. (a) LA 64 size = 2. (b) LA size = 6. (c) LA size = 10. ^ 7.1 Sensitivity of the performances of selective paging and spread paging to uncertainty in ao for T = 40 km/hr, ti, = 60 sec, d = x, rcell = 1 km, kat! = 1 call/hr and system's ao = 4.2. (a) Average paging delay. (b) Average paging traffic. ^ 67 7.2 Sensitivity of the performances of selective paging and spread paging to uncertainty in T for th = 60 sec, d = oo, ao = 4.2, rcell = 1 km, A ca ll = 1 call/hr and system's t = 40 km/hr. (a) Average paging delay. (b) Average paging traffic 69 7.3 Sensitivity of the performances of selective paging and spread paging to uncertainty in th for v = 40 km/hr, d = x, ao = 4.2, rcell = 1 km, k a li = 1 call/hr and system's t h = 60 sec. (a) Average paging delay. (b) Average paging traffic. viii 70 7.4 Sensitivity of the performance of selective paging and spread paging to uncertainty in d for T.5= 40 km/hr, 7h = 60 sec, ao = 4.2, reel' = 1 km, Acall = 1 call/hr and system's d = 00. (a) Average paging delay. (b) Average paging traffic ^ 72 A.1 Effects of a on Alpha p.d.f. with w = 1 and x = 0 ^ 79 B.1 Effects of ry on Asymmetric Gaussian p.d.f. with m = 0 and cri = 1. ^ 81 ix LIST OF TABLES 4.1 Numerical values of the normalized effective radii 6.1 Angular ranges of the sectors for sectorization pattern 1 and 2 x 31 53 ACKNOWLEDGEMENT I 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 to thank Dr. R. W. Donaldson for offering me an opportunity to be a part of the Inter-Networking Research 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 conversation ignited my desire for graduate studies. I am grateful to all my friends and colleagues at the University of British Columbia who made my studies here more enjoyable and rewarding than I expected. Among them, I would like to 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 from my family whose love has brought sunshine in my rainy days. For this, I would like to dedicate the 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 Telecommunication Research (CITR) under the NCE program of the Government of Canada and in part by NSERC grant OGP0001731. xi CHAPTER 1 INTRODUCTION In the past few decades, the emergence of communication technologies, such as telephones and FAX, has brought instant and affordable global communication closer to the average person. In particular, telephones provide an easily accessible means of communication. Nowadays, there is a growing demand for systems which are capable of setting up connections regardless of the locations of the calling and the called parties. The concept of delivering a call to a person instead of a fixed physical port is the underlining concept behind personal communication networks (PCN's). Such networks are intended to provide ubiquitous communication coverage, enabling people to call each other regardless of their geographic locations. Because of potentially high user capacity due to frequency reuse and cell splitting, present cellular mobile telephone networks will be used for the wireless communication part of PCN's [1-4]. It has been forecast that in the future, 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 automatic call routing, will be handled by the network. 1.1 Background The 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 in the Very High Frequency (VHF) band [7]. The transceivers were commonly used by police and fire departments as well as taxi companies. To provide a wide area coverage, a base station with a powerful multi-channel radio transceiver was employed. Several such base stations were connected to a Mobile Switching Center (MSC) which provided an interface to the Public 1 CHAPTER 1 INTRODUCTION 2 Switched Telephone Network (PSTN). However, the user capacity of this system was limited by the available number of radio channels. Not until the emergence of the cellular concept did a promising solution to this problem appear. The cellular concept was first formulated in the 1940's [7]. Unlike the conventional one high power transmitter system, the service area is covered by a number of base stations, each transmitting at low power such that the coverage area of each base station (called a cell) is very much 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 increase in MSC and network management complexity. The network needs to keep track of the location of each mobile user so that when a call comes in for a user, the call can automatically be routed to the cell the called user is in [9-11]. This is referred to as mobility management. Cells are grouped to form location registration areas or location areas (LA's). A user reports its current LA to 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 examined in [12-16]. Paging schemes have also been studied in [17-19]. To ensure the continuity of an ongoing call when the calling or called parties change cells, the network has to allocate a new radio 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 and frequency 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 response from the market [7]. The systems developed at that time, such as AMPS, are often described as first generation systems, characterized by analog frequency modulated voice transmission. To satisfy the rapidly increasing number of cellular phone subscribers and the exchange of an increasing variety of information such as images and video, several second generation systems are currently being developed around the world. Second generation systems are characterized by CHAPTER 1 INTRODUCTION ^ 3 the extensive application of digital technologies such as digital voice transmission. There are three second-generation cellular standards : GSM (a Pan-European digital cellular mobile telephone system) [29-31], IS-54 (an emerging North American digital cellular mobile telephone standard) [32] and the upcoming Japanese standard. Furthermore, Bell Communications Research has proposed Universal Digital Portable Communications [33] as a means of delivering basic services to telephone company subscribers. Unfortunately, the second generation systems are not directly compatible with each other. Inter-Networking of cellular systems using different standards to provide a worldwide integrated information network is one of the challenges of third generation systems. 1.2 Motivations and Objectives As discussed in the previous section, the mobility management function of a cellular system keeps track of the location of a mobile user. It is supported by a location updating scheme which determines the LA a user is in. When a call comes in for a user, the cells in its LA are paged. A flood paging scheme in which all cells in the LA are paged simultaneously is commonly used [34-36]. In this paging scheme, the paging channels in the cells are not utilized efficiently because some of the cells are paged unnecessarily. As the mobile user population increases, there is a need for more efficient paging schemes to avoid long paging delays due to queueing of paging requests. In [18], [19], paging schemes, in which disjoint subsets of the cells in the LA are paged in sequence until the user is located, are suggested. Paging traffic (number of cells paged) is reduced at the expense of an increase in paging delay (number of paging stages needed). If the mobility model of a mobile user is known, we can predict the group of cells the user 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 ^ 2. 4 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 Thesis In Chapter 2, a mobility model for a mobile telephone user is described. In Chapter 4, a location updating scheme is proposed. The analysis and simulation results for location updating traffic are provided. In Chapter 3, the cell and LA geometries are described. In Chapter 5, two LA paging schemes, namely spread paging and selective paging, are presented. The analysis and simulation results of their performances, in terms of average paging delay and average paging traffic, are shown. Chapter 6 describes and provides the performance evaluation of an LA sectorization 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 deviation parameter, 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 mobility parameter values is examined. The main results of this thesis are summarized in Chapter 8. CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER Mobility 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, and the 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 driving behavior were discussed. Traffic flow theories have been developed. A variety of traffic flow models were proposed in [38], in which fluid diffusion equations were commonly used to model the mobility of vehicles in a small area (e.g., a segment of a street). In analyses of problems such as hand-off frequency and location area boundary crossing frequency in a vehicular cellular communication 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 uniformly distributed 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 seems to be a better mobility model. hi [36], the mobility of a portable mobile telephone user is modelled by a Brownian movement type symmetric random walk. However, in application to a vehicular telephone user, this model ignores the fact that typically, a driver tends to travel in a certain direction. In this chapter, a directional random walk model is proposed, and it will be used as the mobility model for a vehicular telephone user throughout this thesis. 2.1 Directional Random Walk In this directional random walk model, the movements of different mobile users are assumed to be uncorrelated. The travelling pattern of a mobile user is on a journey basis. To start a journey, the user first chooses a destination which is at a distance, 2, and at an angle, 0, from the 5 CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER ^ 6 destination v4 x1,114^131, , - -^, '13 V3 X t h3 -V2 x t h2 Vl X t hi av travelling path — — — principal direction starting point Figure 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 to the destination defines the principal direction at that time. The user heads towards the destination with a random angular deviation 0, with p.d.f. fB(13), from the principal direction. The speed at a 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, the new 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 the destination if the user arrives within a distance, d101, of the destination. The random walk model is illustrated in Fig. 2.1. In choosing the p.d.f.'s fr (7) and f4,(0) for the destination, we assume a Cartesian coordinate system and x, y distances are normally distributed with equal variances, cd, and means equal to 0. 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 ^ 7 ry, is given by the Rayleigh p.d.f. ;^> 0 Y^20'2 d fr('Y) =^ad (2.1) ; otherwise and the angular p.d.f. is uniform ^; 0 < < 27r zr (2.2) 01 .4(0) = ; otherwise. Since the mean of fr(-y) is 7 =^Expressing ad in terms of 7, we have (2.3) ad = 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 statistics of the free-flow speeds from radar speedometer measurements at 31 rural areas in Australia during 3 different years were collected and the speed distributions are found to be normal with standard deviations equal to 0.17 times the respective arithmetic means. We will use this results to model the speed. We have ()2 fv(v) = ^ 1^ c ^27ra j (2.4) - where a d = 0.17 x T. The speed distribution with unity mean speed is shown in Fig. 2.2. From our literature search, it seems that there are no available statistics on direction changes of a vehicle (e.g., at an intersection). We will model the angular deviation from the principal direction by an Alpha p.d.f. (see Appendix A) with mean deviation equal to 0. We have /1^ ;^< 3 < r 2 {1i-a 0 83 1 tan ^e7r) fE3( /3) = ; otherwise. 0^ 2 2 -1 (2.5) We assume that with probability 0.95, a user travels in the forward direction i.e., the angular deviation is in the range^,^The corresponding a j is 4.2. The p.d.f. is plotted in Fig. , 2.3. CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER ^ 8 2 1 .5 1 0.5 0 0.5 1 1.5 speed (km/hr) Figure 2.2 Speed distribution with mean speed = 1 km/hr.. angular deviation (rad) Figure 2.3 p.d.f. of the angular deviation 2 CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER 9 We 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 with parameter Air where th is the mean velocity hold time, i.e., AhE—Aht ; t > 0 fix(t) ; otherwise. = (2.6) 2.2 Stochastic Model Given the location updating scheme of the cellular system as described in Chapter 4, the system always knows the location area (LA) the user is in, the cell of entry to the LA and the elapsed time since the user entered the LA. In a call delivery to the user, the system has to page the cells in the LA to locate the user. The paging load, defined as the number of cells paged before the user is located, can be reduced if the spacial distribution of the user in the LA is known. 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), of a 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.'s using simulation results (see Section 2.2.1). The random walk model is simplified with the assumption that the destination is at infinite distance from the starting point; therefore, the parameters 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 good approximation 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^ 10 2.2.1 Simulation With the destination at infinite distance from the starting point, the random walk model 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 deviation p.d.f.'s at different times are obtained and will be used to obtain approximate analytical forms in the following sections. The time increment in the simulation is 4 seconds and the sample size is 400000 samples for each p.d.f. The frequency distributions of the radial distance and angular deviation were obtained first. The resolutions of the distance and angular deviation in the frequency distribution are 400 cells per 70 km and 200 cells per 27r radian. Therefore, the widths of the cells are Or = 175 m and AO = 0.01r radian. The frequency distributions of the radial 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 the p.d.f.'s are shown in Fig. 2.4 (a) and 2.5 (a). The 99% confidence intervals are within ±5% of the average values and are omitted from the figures. The simulation program was written in C and was run on a SUN SPARCstation IPX. To obtain the above simulation results at times t = 1, 2, 3, , 120 minutes (i.e., a total of 120 p.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 starting point of the journey is at the origin, the destination is at d-x. on the x-axis and the starting , time is t = 0. From the radial distance p.d.f.'s obtained by simulation in Section 2.2.1, we find that they can be fitted by an asymmetric Gaussian p.d.f. (see Appendix B). We will express the three parameters (0 1, 7, m) of the asymmetric Gaussian p.d.f. as functions of time to obtain the - analytical form for the radial distance p.d.f. For convenience in the derivation, we express time in seconds, distance in meters and speed in meters per second. 11 CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 15^20^25^30^35 radial distance (km) (a) 10^15^20^25^30^35^40 radial distance (km) (b) Figure 2.4 Radial distance p.d.f.'s of the random walk with v = 30 km/hr and -3^-2 ^ 0 th = 60 sec. (a) Simulation. (b) Analysis. ^ 2^3 angular deviation (rad) (a) t t=41 min ^ t-31 min 21 mitt ^ t - 11 mm ^ - I min -3^-2^-1 0 angular deviation (rad) (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. 2 3 CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER ^ 12 y xi •^ x2 •• •• x3 x4 destination at +co starting point (a) x1 x2 • '•^► • x3 ► • x4 vit b V2t h2 starting point destination at + co (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 an asymmetric Gaussian p.d.f. given in Eqn. (B.7), i.e., max [fR(rIt)] = V2 7r a? Or ^Ai a1 = { max [fR(rIt)] ^1 f ^ (2.7) 2 2 7r .^ (2.8) . To obtain an analytical approximation to max [fR(r/t)], we view the random walk as consisting of discrete independent steps of variable lengths as in Fig. 2.6 (a). Note that the longer a user has travelled, the more likely that its angular deviation, 0, from the general direction is small. It is also reflected in the angular deviation p.d.f. in Fig. 2.5. The spread of the p.d.f. becomes less as 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 and max [fR(rIt)]^max [fy (x/i )].^ (2.9) CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER ^ 13 We will express max [fx(x/t)] analytically. Referring to Fig. 2.6 (b), the x-component of the 1 step is denoted by xi = v2 t h , cos (/3i) where vi, t ip, and 13i are independent random variables as described in Section 2.1. After time t, the x-displacement is N(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 is N(t)a^ (2.11) where o is the variance of x 2 =^- (T) 2 = v2 COS 2 (0) — (V th cos (3)) 2 = V 2 t'/, cos 2 (j3) — (TT: cos (0)) 2 ^ which can be evaluated numerically. The maximum value of this Gaussian p.d.f. is 71" N(t) (2.12) or . By Eqn. (2.9), we have max [fR WO] ti max [fa (x/t)] 1 (2.13) -V2 N(t) or 1^ .N(t) ^ 2 7 Cq {max [fR(r/t)]} 2 (2.14) However, N(t) is a random variable correlated with ti, (ti, is exponentially distributed) and has expected value N(t) = 71 . We obtain N(t) for parameter set 'T E {25, 35, 45} km/hr and 71, 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 ..L^an It can be seen that they all t h 14 CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER 70 60 50 z 40 30 20 10 th Figure 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 by 4 N (t, 9.0773 x 10 -6 (0 - 5.1106 x 10 -4 ( 7:t2 +0.0143 1h - 0.0273 (=L) + 0.0028 ^th 0.3191 (--0 - 3.1812 (-6 . Substituting Eqn. (2.13) in (2.8), o 5 + 3.1008 ) 3 0 <^< 13 (2.15) 13< is obtained as o.2^4 i 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.'s from simulation as ry (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 ^ 15 To obtain m, we rearrange Eqn. (B.10) and we have 2 in(t,th ) = r(t,th ) +^— 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 as r(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 by simulation as c(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 absolute difference between the 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.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 for large 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 approximation of fo(0/t) is expressed as fe(e It) = P(t) fc -;( 0 It) + [1 — p(t)] fA (0 It)^(2.21) CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER ^ 16 1.2 1 mean speed = 25 km/hr mean speed = 35 km/hr mean speed = 45 km/hr 0.8 0.6 0.4 0.2 0^20^40^60^80^100^120 time (min) (a) 1.5 mean hold time = 30 sec mean hold time = 90 sec mean hold time = 180 sec 0.5 • 20 ^ 40^60^80^100^120 time (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 form fG( e / t ) = 1^ ^ ,V21 1- 0-2 (t) e 82 (2.22) 23(t) • , 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 V2 (2.23) at(1) or o ?- (t)= - Fig. 2.9 shows ; 1 27{max [le ( 0 /0]} 2 (2.24) • o 6(t) for different sets of random walk parameters versus 7L. - It can be seen that they all exhibit the same functional relationship. By piecewise curve fitting, the analytical CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER ^ 17 0.08 0.07 0.06 0.05 0.04 0.03 0.02 0.01 50 ^ 100 ^ 150 ^ 200 ^ 250 th Figure 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) is 4^ 1.8613 x 10 -7 (0 — 1.5580 x 10 -5 (7t-) 3 h 2 +5.0597 x 10 -4 (6 — 0.0083 ( 79 +0.0805^ 0-6 (t, t h ) = —0.3344 (=i- ; 0 < (^< 27 (2.25) 2 0.08 c^+ 0.0025^; 27 _< (=tht- < 132 —0.3 (=L 2 0.08 c^+ 0.0017^; 132 5_ (7 9. The Alpha part of the p.d.f. has the form 1 ^A(t) 2 [1-Fo 2A (t)9]tan -1 (ct A (t) ir) f^ A( 6 /t) = / 0 ; —7r < < 7r ; otherwise. (2.26) CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER^ 18 Similarly, a A (t) is estimated by equating the peak value of the p.d.f. from simulation to that of the Alpha p.d.f. given in Eqn. (A.3) and we have aA (t) (2.27) MaX[fe0/01 = 2 tan -1 (aA(t) 7) . We solve aA(t)'s for different random walk parameters numerically. Fig. 2.10 shows a A (t) for different sets of random walk parameters versus 7L. It can be seen that they all exhibit the same functional relationship. By piecewise curve fitting, the analytical form of a A is aA (t,^= 1 =(t,t ii ) (2.28) and zz, is given by 3 -5.9969 x 10^1880 —6 (6 +4. x 10-4 ) ( 2 in -0.0117 (6 + 0.2335 ; 0< ( th ) <25 \ 3^ -2.7376 x 10^+ 4. 9513 x 10 -5 ( t ) 2 th r.7(t, th ) -0.0036 ( 70 • 25 < ( 79 < 60 0.1718 65 0.0840 C^ ^h) + 0.0412 60 <^< 120 0.060 e^122 120< GO. ( th) + 0.0319 (2.29) We use a scaled and vertically shifted arctan function as the weighting function, p(t), to provide a smooth transition from 0 to 1 i.e., p(t,7) =^tan -1 [a (— t - 1)] th + 1 2 (2.30) The parameters a and b together control how fast p(t.7 1,) changes from 0 to 1. By comparing the analytical 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 between the 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. CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER ^ 19 25 20 15 10 6 curves 50^100^150^200^250 th Figure 2.10 ct A 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}. 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0 50 100 150 th Figure 2.11 Weighting function p(t,7 h ) versus th 200 CHAPTER 2 MOBILITY MODEL FOR A MOBILE USER ^ 20 0.1 0.08 mean speed = 25 km/hr - - - - - mean speed = 35 km/hr - • - mean speed = 45 km/hr 0.06 0.04 0.02 20 ^ 60 ^ 80^100^120 time (min) (a) 0.1 0.08 mean hold time = 30 sec mean hold time = 90 sec 0.06 mean hold time 180 sec 0.04 0.02 20 40 60 ^ 80 ^ 100 ^ 120 time (min) (b) Figure 2.12 Goodness of fit of the analytical angular deviation p.d.f. (a) 7h = 90 sec. (b) 7 = 35 km/hr. CHAPTER 3 CELL AND LOCATION AREA LAYOUT MODEL In this chapter, layouts of the cells and location areas of a cellular system used in the subsequent chapters are described. 3.1 Cell Map For convenience and simplification in system analysis, the service area of a cellular system is commonly viewed as consisting of smaller service area units termed cells. Each cell is served by a base station. All cells are assumed to be of identical shape and size, and hexagonal packing of the cells is assumed. Hence, we have a hive-like cell grid on the service area of the cellular system as shown in Fig. 3.1. The size of a cell depends on the transmission power of the base station transmitter. The larger the transmission power is, the larger the cell size is. Each cell is assigned a unique identity number which is broadcast by its base station; this is heard by all mobile users within 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 illustrated in Fig. 3.2 where rcell is the 'radius' of the hexagonal cell. Therefore, 71- ) 7r r 2q , = 6 [^] 721- r,2 , 11 sin ( 7 (3.1) or r e v, 3 — sin (.-7T7r^3 re el ! 0.9094 21 (3.2) CHAPTER 3 CELL AND LOCATION AREA LAYOUT MODEL ^ cellular system service area Figure 3.1 Cell grid of a cellular system. Figure 3.2 Equivalent radius of a cell [28]. 22 CHAPTER 3 CELL AND LOCATION AREA LAYOUT MODEL ^ 23 Figure 3.3 Location area of size = 3. 3.2 Location Area Cells are grouped to form location registration areas or location areas (LA's). The system has a mapping function between cells and LA's. A user updates the LA it is in to the system according to the location updating scheme in Chapter 4 so that the uncertainty in the user location is 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 (or rings) of cells. The cells immediately surrounding the center cell form the 1s 1 ring. The layer that surrounds the /' ring is the 2nd ring and so on. The size of an LA is specified by the number of 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, the equivalent radius, R eo,.(k), is defined as the radius of a circle having the same total area as all cells in rings, 1, 2, . . . , k. The number of cells in the i ih ring is 6x i for i E {1, 2,3, • • •} 24 CHAPTER 3^CELL AND LOCATION AREA LAYOUT MODEL and the total number of cells in rings 1, 2, ... , k is N^= 1 + = E 6i 1+3k(1+k) ;^ k (3.3) We can express R eq,(k) as R' q ,(k) = N(k)71 - ;^ k E {0,1,2,-•.} (3.4) or Reqv(k) = r eq „ A/N(k) ;^k E {0, 1,2, ...}. (3.5) The width of the k th ring, W(k), is defined as W(k) = R egv (k) — R ev,(k — 1) ;^k E (3.6) CHAPTER 4 LOCATION UPDATING SCHEME With location tracking of mobile users, calls can be routed to their destinations regardless of the calling and called parties' locations. Location tracking is supported by the location updating scheme, which determines the LA the mobile user is currently in. When a call arrives, the called user can then be paged in the correct LA. In [16], several location updating schemes were discussed, including schemes based on the timing method in which a user updates periodically and the zone method in which the update is triggered by the crossings of the geographic boundaries of LA's. In [12], the concept of overlapping LA's was proposed to reduce the location updating load in the cells on the LA boundaries. In this chapter, we present a location updating scheme which is based on the zone method as well as overlapping LA's. 4.1 Overlapping Location Areas An LA is specified by its center cell and its size in terms of rings as discussed in Section 3.2 and we assume that the system determines the size of the LA. When a mobile user updates its 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. Knowing the center cell and the size of the new LA, the system identifies its member cells and sends their i.d.'s to the mobile user. The mobile user stores these i.d.'s and uses them to determine if it has exited the current LA by monitoring the i.d. broadcast of the current cell. If this i.d. does not match any of the stored i.d.'s, the user knows that it has entered a new LA. 25 CHAPTER 4 LOCATION UPDATING SCHEME ^ 26 4.2 Conditions for Location Updates We define a location update as a report to the system of the cell a mobile user is currently in 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 location updating activities of the mobile user when it is on a journey because there is no need to update the location when the mobile user is not moving. Location updates are triggered by any of the following events : 1. The mobile user starts a journey. When a mobile user starts a journey, it performs location update 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 initiated by 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 a new 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 the call setup. This enables the most up-to-date location information to be made available to the system without the need for an additional connection. 4. The mobile user ends a journey. After a user has reached the destination, it updates its location to the system. The update indicates to the system that the user has finished a journey and will stay in the current cell (the center cell of the LA) until further notice (the update event 1). If a call comes in during this time, the system can direct the call to this cell without paging other cells in the LA. It may be initiated by the user manually or triggered by turning off the vehicle engine. 4.3 Effective Ring Radius In the evaluation of the ring probability in the performance analysis of the paging scheme CHAPTER 4 LOCATION UPDATING SCHEME^ old LA 27 -^------^new LA ithring „- - - cent range of directions Figure 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 cell of an LA of size R to the point the user reaches the equivalent radius [Eqn. (3.5)] of the ith ring of the LA. We view the change of LA in the way that the user enters the new LA at some point on its circumference and we assume that the user is travelling in a straight line in the principal direction 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 direction of 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 i th ring as the average of this distance over the range of the principal direction, and use it to evaluate the ring probability. We assume that the direction is uniformly 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 = r 0 cos (a)^r, cos (3).^ (4.1) CHAPTER 4 LOCATION UPDATING SCHEME ^ 28 center cell Figure 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 as ri = r egt,VN(i) r„u p ^ (4.2) where P= 3 — sin (7r ) 77"^3 (4.3) and .N(i)=1+3i(.1.+i).^ (4.4) Using the sine rule, we have sin (3)^S111 ( 0 ) rR^ri (4.5) or sin ())^ rR — sin (0).^ (4.6) CHAPTER 4 LOCATION UPDATING SCHEME ^ 29 Figure 4.3 Evaluation of cos(3) using Pythagoras's theorem. By Pythagoras's theorem as in Fig. 4.3, cos (,3) = T R) 2 2 1 — -- sin (9)• r (4.7) Similarly, cos(a) is given by 2 ^ ( cos (a) = ro sin 2 (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)sin 2 (0) +^— N(R ) sin 2 (9) Therefore, the effective radius of the i t h ring in an LA of size R is 1 do R) = 1, Ref f^ ' 2 ^RV') 0 -e (4.10) CHAPTER 4 LOCATION UPDATING SCHEME ^ 30 Figure 4.4 Geometry for evaluating O. - = rcell 0 ^ - = rcert 4 '01,R(0) —0 ^ (4.11) where rP i , R is the normalized effective radius of the i th ring in of LA of size R 0 =21)'^7i'i,R(0) dO. -0 (4.12) Referring to Fig. 4.4, the 0 in the limits of the integration is evaluated by sin (0) = To — rR 1 (4.13) ./N(R) or 1 0 = sin-1 ^ ( ^ ) VN(R) Table 4.1 shows the T'i ,R for LA's of different sizes. (4.14) CHAPTER 4 LOCATION UPDATING SCHEME ring ^ 31 LA size 0 1 2 3 4 5 6 7 8 9 10 0 1.1579 1.4193 1.4252 1.4268 1.4275 1.4278 1.4280 1.4281 1.4282 1.4282 1.4283 1 - 3.0559 3.0596 3.0606 3.0611 3.0613 3.0614 3.0615 3.0615 3.0615 3.0616 2 - - 4.6401 4.6410 4.6414 4.6416 4.6417 4.6417 4.6418 4.6418 4.6418 3 - - - 6.2187 6.2191 6.2193 6.2194 6.2194 6.2195 6.2195 6.2195 4 - - - - 7.7956 7.7958 7.7959 7.7960 7.7960 7.7960 7.7961 5 - - - - - 9.3718 9.3719 9.3720 9.3720 9.3721 9.3721 6 - - - - - - 10.9477 10.9477 10.9478 10.9478 10.9478 7 - - - - - - - 12.5233 12.5233 12.5234 12.5234 8 - - - - - - - - 14.0988 14.0988 14.0988 9 - - - - - - - - - 15.6742 15.6742 10 - - - - - - - - - - 17.2495 Table 4.1 Numerical values of the normalized effective radii. 4.4 Location Updating Traffic We define the location updating traffic as the number of location updates per unit time per user. Since the location updates due to updating event 3 (call arrivals) are performed during call 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 updating traffic analysis, we assume that a user starts one journey after another continuously In 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 as shown in Fig. 4.5. The projection of the user mean velocity on the principal direction is Tr = T • cos (0) (4.15) where 6 is the angular deviation of the user's current direction from the principal direction and its p.d.f. is given in Eqn. (2.5). The expected time, 7cross, a user takes to cross the LA boundary from the LA center is approximated by dividing the effective radius of the LA by this CHAPTER 4 LOCATION UPDATING SCHEME^ 32 principal direction Figure 4.5 Illustration of the updating traffic analysis. mean speed as R,f f(R,R) across^ (4.16) 177, Expressing the effective radius of the LA in terms of its equivalent radius in Eqn. (3.5), we have across^-Rcgv(R 7,i^ 'RR 1 Tp p Viv(R) (4.17) - where p is given by Eqn. (4.3). Thus, the average location updating traffic due to event 2 is 1 T cross^7^ (4.18) t CT OSS To derive the updating traffic due to events 1 and 4, we first approximate the user mean trip duration by d Trip^ VP (4.19) CHAPTER 4 LOCATION UPDATING SCHEME ^ 33 where d is the mean trip length. Since there are two such updates in a journey, the updating traffic is approximated by T start,end 2 (4.20) tirip The total location updating traffic is approximated by T Tcross +T start,end • ^ (4.21) The location updating traffic was obtained by simulation for 7v- = 40 km/hr, t h = 60 sec, d = 20 km and no call arrvial. The simulation results are shown together with the analytical results in Fig. 4.6. The 99% confidence intervals for the simulation results are within ±5% of the average values shown. CHAPTER 4 LOCATION UPDATING SCHEME^ In 30- ^ analysis = 20 C., cd 34 simulation 10 0 fa.^ 0 ■ 5 15^20^25^30^35^40 equivalent LA radius (km) (a) analysis X^simulation 5^10^15^20^25^30^35^40 equivalent LA radius (km) (b) analysis X^simulation 5^10^15^20^25^30^35^40 equivalent 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 5 LOCATION AREA PAGING SCHEMES The location updating scheme discussed in Chapter 4 enables the system to locate the LA a user is in. When a call comes in to a user, the system pages the user in its registered LA. The flood paging scheme in which the cells in the LA are paged simultaneously is commonly used in locating the called user when a call comes in [34-36]. This paging scheme is not efficient in terms of paging traffic defined as the number of cells paged before the user is located. A more 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 traffic is reduced at the expense of an increase in paging delay, defined as the number of paging stages needed before the user is located. By carefully choosing the set of cells for each paging stage, we can 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 Preliminaries In this section, a call arrival model and the ring probability which will be used in the performance analyses of the paging schemes in subsequent sections are discussed. 5.1.1 Call arrival model Call arrival is commonly modelled by a Poisson process with rate time. The p.d.f. of the inter-call arrival time, denoted by with mean f„//(t), Ac aji arrivals per unit is exponentially distributed 1 In selective paging, the time, t e , between a call arrival and the last location update is used to estimate the position of the mobile user when a call comes in. Let fc (t) denote the p.d.f. of 35 36 CHAPTER 5 LOCATION AREA PAGING SCHEMES^ te . An exact expression for Mt) appears to be difficult to obtain. Hence, an approximation to fc(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 user mobility model with infinitely long trip length in Chapter 2 were simulated for the parameter sets T E {20, 30, 40} kin/hr, t, E {30, 60, 120} sec, A ca ll E {0.5, 1, 2} arrivals per hour and R E {2, 7, 12, 15, 22} km. The frequency distribution of t, is obtained. The time increment of the simulation is 4 seconds, and the sample size is 40000 calls. The resolution of to is 100 cells per 70 min. Therefore, the width of each cell is At, = 0.7 min. The frequency distribution is normalized, 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 user travels in a straight line in the principal direction. The projection of the mean velocity on the principal direction is t7p 7 = 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 direction from the principal direction. The mean time for the user to exit an LA of radius R from the center of the LA is approximated by R 'TT) 7R (5.2) We observe that if 7R is x,^= Jecall(t). If time t is small compared to 7R, say t < c < tR, 1 so that the user is not likely to have exited the LA during time (0, t), it will be shown that fc(t) has the same shape as feall(t). For t > c, we find that f,(t) can be approximated by a half Gaussian p.d.f.^Therefore, fc(t) = A A,/i c —A "u t 2 \17— 2— T-cr? 0 0<t<c ;^c < t ;^otherwise. (5.3) CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 37 0.018 0.016 0.014 0.012 0.01^tR^tR^ tR tR ^ tR 0.008 0.006 0.004 0.002 0 20^40^60^80^100 120 140 160 180 200 inter-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 7 R = 40 min. We refer to the exponential p.d.f. of the inter-call arrival time in Fig. 5.1 for the derivation of the exponential part of 1,(t), denoted by fe (t). Time is slotted with slot length tR. fe (t) is the 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 A mu C — Ac.ii (t—i7R) =( E ei A-7R Acau C i=o = A can e—Ac,,,, t A' 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. f tR^tR fe(t) dt =fA 0^0 = A (1 Acait c"" 1 dt — c" JR) , = 1.^ (5.5) 38 CHAPTER 5 LOCATION AREA PAGING SCHEMES^ Therefore, 1 A= (5.6) For the Gaussian part of fc (t), we need to determine two parameters : B and a,. To determine B, we use the condition that the area under the L(t) curve is 1, i.e. 00 00C^ I fc (t) dt = I A Acau C A "" 0^0^ t dt I ^ B^ -V2 C^ dt C = A ( 1^A""^+ 0.5 B (5.7) = 1. Therefore, (5.8) B = 2 [1 — A (1 — c —\— "c)]. We choose a, such that 1,(t) is continuous at c and we have —A n c^ A Aran= B r 02 (5.9) - or ac = B (5.10) 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 as (ER) = 1 0.00023 (7R)^ 2 + 0.4307 (7R) — 8.7879^; 0 < 7R < 900 0.85917R — 204.8937 (5.12) 900 < 7R and g(7 h ) = 0.00167h+ 1.1041^30 < 7h < 180. — (5.13) Fig. 5.2 shows the fc (t) obtained from simulation together with /At). The 99% confidence intervals for the simulation results are within ±5% of the average values shown. The goodness CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 39 0.35 simulation 0.3 analysis LA radius = 2 km 0.25 LA radius = 7 km 0.2 LA radius = 12 km 0.15 LA radius = 17 km 0.1 LA radius = 22 km 0.05 10 ^ 20 ^ 30 ^ 40 ^ 50 time (min.) Figure 5.2 P.d.f.'s of the call arrival time with respect to the last location updating 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. The maximum value is 2 and the minimum is 0. The corresponding goodness of fit for Fig. 5.2 is shown in Fig. 5.3. 5.1.2 LA ring probability In the paging delay and traffic analyses of spread paging and selective paging, we need the probability that a user is in a particular ring in its registered LA at a particular time. We refer to this as the ring probability. In the derivation of the ring probability, we need the p.d.f. of the radial distance, r, of a user 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 of entry to the center cell of an LA of size R and the point the user reaches the equivalent radius of the i' ring of the LA depends on the principal direction of the user when it enters the LA. CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 40 0.11 0.1 - 0.09 - 0.08 - 0.07 0.06 0.05 2^4^6^8^10^12^14^16^18^20^22 radius 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 i lh ring at time t, denoted by Pring(i, t), we should first evaluate the ring probability given that the user is travelling in a certain principal direction by integrating fR(r/t, LA not yet exited) over the width of the ilh ring from /i-1,R to /i,R. Then, we average this ring probability over the range of principal directions the user can possibly have when it changes LA as discussed in Section 4.3. However, we find that Pring(t,t) can be well approximated by simply integrating fR(r/t, LA not yet exited) over the effective width of the i ll' ring from R eff(i-1 , R) to R eff(i, R) where R eff(i, R) is the effective radius of the i th ring of an LA of size R given by Eqn. (4.11). In the random walk model discussed in Chapter 2, we assume that every time a user chooses a new direction, with only probability 0.05, the user travels in backward direction. We assume the probability that the radial distance the user has travelled in time t is less than that travelled in time t' < t is insignificant and fR(r/t, LA not yet exited)^fR(r/t, r <^f(R. R)) CHAPTER 5 LOCATION AREA PAGING SCHEMES^ fR(rIt) R eff (R,R) f ; r < R e ff(R, R) f R(0) de 41 (5.14) 0 where fR(r/t) is the radial distance p.d.f. for the directional random walk model given in Section 2.2.2. Then, the ring probability of the I ith ring at time t is approximated by R ,f f (1, R ) ^ Pring (i, t) fR(r/t, LA not yet exited) dr.^(5.15) 5.2 Paging Schemes : Description and Performance Analysis In this section, three paging schemes, flood paging, spread paging and selective paging, are described. We evaluate the performance of the paging schemes by the average paging delay and the average paging traffic. We assume that the location updating scheme discussed in Chapter 4 provides accurate location information so that the user will be in the registered LA and paging only occurs in the registered LA. 5.2.1 Flood paging Flood paging is the simplest paging scheme. When a call comes in to a user, all the cells in the user's registered LA are paged simultaneously. In response to the paging, the called user sends a reply to the system through the serving base station. Since we assume that the user will be 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) 42 CHAPTER 5 LOCATION AREA PAGING SCHEMES ^ 5.2.2 Spread paging According 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 of an LA contain less cells than outer rings, in this paging scheme, paging starts from the center of the LA and spreads outward. The system first pages the center cell. If there is no response from the 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 ring probabilities of all the rings in the registered LA. We denote the ring probability of the i h ring 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) as CK) 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, we need to page rings 0, 1, 2, . . . , i. Thus, there are (i+/) paging stages. Averaging the number of paging stages using the ring probabilities, we have =E ( i + 1) Pr i„g (i).^ (5.19) 0 We follow a similar approach for the derivation of the average paging traffic T. If the user is in the i `h ring, we need to page the cells in rings 0, 1, 2, . . . , i. We denote the total number of paged cells by N(i) which is given by Eqn. (3.3). Averaging N(i) using the ring probabilities, we have T E N(i) Prt „ g (i) 2= 43 CHAPTER 5 LOCATION AREA PAGING SCHEMES^ = 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=1 5.2.3 Selective paging In this paging scheme, the mobility model of a mobile user developed in Chapter 2 and the time, tc , between a call arrival and the last location update are used to select the rings of cells for successive paging stages. When a call comes in, we evaluate the ring probabilities at t, given by 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(t e ). Then, we average D(t,), using the call arrival p.d.f.,f,(t), to obtain the average paging delay. For mathematical convenience, we use matrix representation in the derivation. Let Prin g (tc) be a column vector whose components are the ring probabilities at time tc . For an LA of size R, we define Piin g ( tc) = - PrIng Og tC) Pring (1, tc) „ 9 ( (5.21) R, t, )_ Let N r i ng be an R x I vector whose^component is the number of cells in the i ll' ring of the LA, i.e. Nrin g = "Vri,g( 0) Nrin g (1 ) -vr,„(R)- (5.22) CHAPTER 5 LOCATION AREA PAGING SCHEMES^ where / 1^ ; i= 44 0 (5.23) Nring (i)^ 6 X i^{ 1,2, 3, ...}. When a call comes in, P ri ng (t c ) is sorted in descending order to yield the vector Psring (t c ) and Nsring is the corresponding Nri„ g . If the user is in the ring which is the i th component of Prsing(tc the paging delay is i+/. Therefore, the average paging delay at time t, is D(t c ) = [1 2 3 • • • R^1] x P;ing (t c ).^(5.24) Averaging 15(t) using the call arrival p.d.f., Pt), we obtain the average paging delay as CO = D(t) Mt) dt. ^ (5.25) We follow a similar approach in the derivation of the average paging traffic. If the user is in the ring which is the i di component of P rs ing (t e ), the paging traffic is the sum of the components of Nsring from the 1 to the i th component. The average paging traffic at time t, is T (t c ) = [N; ing i T X 1 0 _0 •• • 1 1 ••^. 1' I • • • 0 1_ x P; i „ g (t c.) (5.26) where [ • ] T is the transpose operation. Averaging T (I) using the call arrival p.d.f., fe (t), we have the average paging traffic as T =^T(t) fc (t) dt.^ (5.27) 5.3 Numerical Results In this section, the simulation results of the average paging delay and traffic of spread paging and selective paging are provided. The LA layout in Chapter 3, location updating scheme CHAPTER 5 LOCATION AREA PAGING SCHEMES 45 in Chapter 4 and the random walk model in Chapter 2 with infinitely long trip length were simulated for spread paging and selective paging. The mean speed of the user is 40 km/hr. Since we cannot find any reference on the mean velocity hold time, we assume the mean hold time to be 60 sec and the cell radius is 1 km. Fig. 5.4 shows the average paging delay and traffic obtained by simulation and analysis. The 99% confidence intervals for the simulation results are within ±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 average paging traffic which increases as the square of the size of the LA. In comparing the different paging schemes, we will use flood paging as the reference. In spread paging, the traffic is reduced by more than 50% but the delay increases roughly linearly with the size of the LA. The rate of increase is approximately 0.5 delay per unit increase in the size of the LA. In the selective paging, the reduction in average paging traffic is greater than that by the spread paging. For an LA size of 5, the traffic can be reduced by more than 66%. For LA size > 8, the traffic can be reduced 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 an LA 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 in such parameters as mean speed (v), mean velocity hold time T1 ) and call arrival rate (Acall)• We fix 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 are plotted against mean speed in Fig. 5.5. against mean velocity hold time in Fig. 5.6 and against call 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 than spread paging in terms of average paging delay and average paging traffic. CHAPTER 5 LOCATION AREA PAGING SCHEMES^ simulation 46 Spread paging - - -x- - - analysis Selective paging Flood paging ^x ----- x-- --x - .^ , 2^3^4^5^6 size of the LA 7^8^9^10 (a) 350 300 250 200 150 100 50- 5^6 10 size of the LA (h) Figure 5.4 Performance of flood paging, spread paging and selective paging with 17 = 40 km/hr, i h = 60 sec and r,,, 11 = l km. (s) Average paging delay. (b) Average paging traffic. CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 2.2^ 47 9.5 cd ao 1.8 —K.— Spread paging 1.6 - -e- - Selective paging 1.4 1.2 20 30^40 50^20^30^40^50 mean speed (km/hr) mean speed (km/hr) (a) 50 ^X^ 45 .be 40 ;a. 35 —x-- Spread paging - -0- - -0- Selective paging 30 0- 30^40^50 20 mean speed (km/hr) • — 30^40 50 mean speed (km/hr) (b) 120 .1_ 1 00 •— g a 80 CrJ 60 4 ,^ 30^40^50^ e0^30^40^50 mean 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. CHAPTER 5 LOCATION AREA PAGING SCHEMES^ 2.2^ 48 9.5 cO ..e=1 eao bl) ect n 5) . tab 1.8 —X-- Spread paging 1.6 - -e- - Selective paging CS 0) 1.4 1. 40^60^80 100 120 40^60^80 100 120 mean velocity hold time (min) mean velocity hold time (min) (a) 4x 50 X X X^ 45 x — 3 -- Spread paging 40 - -e- - Selective paging 35 2 0 -------0 -------- 30 -0 E 25 40^60^80 100 120 mean velocity hold time (min) 40 ^ 60 80 100 120 mean velocity hold time (min) (b) 6 120 5 100 X^ X )( Spread paging 4 - -e- - Selective paging 3 2 -------^----1 X 40 60 80 a) to -C ; 60 1- 40 100 120 mean velocity hold time (min) 80 -^-^------- 40^60^80 100 120 ^ (c mean velocity hold time (min) ) Figure 5.6 Performances of spread paging and selective paging versus the user mean velocity hold time for 7 = 40 km/hr, ka t/ = 1 call/hr and r «11 = 1 km. (a) LA size = 2. (b) LA size = 6. (c) LA size = 10. CHAPTER 5 LOCATION AREA PAGING SCHEMES ^ 49 9. 8.5. -e--- 1 05 1.5 0 5^1^1.5 call arrival rate (calls/hr) ^ (a) call arrival rate (calls/hr) 05 ^ 2 ^call arrival rate (calls/hr) call arrival rate (calls/hr) 1^1.5 call 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 = 40 km/hr, th = 60 sec and r,11 = 1 km. (a) LA size = 2. (b) LA size = 6. (c) LA size = 10. CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION In Chapter 5, we examined three paging schemes namely flood paging, spread paging and selective paging. Since a user is likely to travel in the principal direction of the journey, the user 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 given sector is termed its sector probability. By applying a paging scheme in descending order of LA sector probabilities, we can reduce the paging traffic at the expense of an increase in the paging delay. This trade-off is examined in this chapter. 6.1 LA Sectorization Due to the hexagonal packing of the cells in an LA discussed in Chapter 3, it is convenient to divide an LA into six basic sectors as shown in Fig. 6.1 (a). Fig. 6.1 (b) shows the idealized sectorized LA. The sector probability depends on how close the sector is to the principal direction of the user and how large, in terms of the total angle a subtended, the sector is as shown in Fig. 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 cells in the LA is paged in each sector paging stage. In LA sectorization, we group a number of basic sectors to form larger sectors to attain different performances. We will examine two LA sectorization 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 the 50 CHAPTER 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, sector 2 is then paged. In pattern 2, we divide an LA into three sectors, sector 1, 2 (2a and 2b) and 3, as shown in Fig. 6.2 (b). Sector 1 covers the portion of the LA along the user's principal direction. Sector 2 is 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 paging stage. However, more paging stages are needed to locate the user due to the smaller sector probabilities. 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 that the constituent basic sectors of each sector in the patterns change, depending on the principal direction of the user. We assume that the system knows the principal direction of the user. The sector in which the principal direction lies has the highest sector probability and is referred to CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION range of the angle bisector of sector 1 angle bisector of sector 1 • _ _^direction^• principal -^direction ^ 52 principal direction rarige of the dikection V (b) (a) Figure 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 center constituent basic sector as illustrated in Fig. 6.2 (a). In pattern 2, the two basic sectors whose boundary is closest to the principal direction form sector 1 as shown in Fig. 6.2 (b). 6.2 LA Sector Probability In the performance analysis of the LA sectorization in Section 6.4, we need to know the sector probability of an LA. Let to he the time elapsed since the last location update. The sector probability of sector i at time to is denoted by Psec(iy tc)• To evaluate Psec(i, (c), we first obtain the 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 to obtain the sector probability and we have = 2010 dO.^ o , (6.1) CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION ^ Sector Pattern 1 Pattern 2 1 [-90°, 90°] [-60°, 60°] 2 [-180°, -90°], [90°, 180°] [-120°, -60°], [60°, 120°] 3 — 53 [-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. We now proceed to find g(010. In forming a sectorization pattern, we know that the principal direction is in some angular range [-/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 ) be the 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 have 9( 0 Itc) = it I h(0 — a It c ) da. ^ (6.2) It remains to find h(9/t c ). An exact expression for h(G/te ) appears to be difficult to obtain. Hence, we obtain an approximation to h(Olt,) using simulation. We run the simulation described in Section 2.2.1 except that when the user has reached a radial distance R (the LA radius), we reposition the user back to its starting point (the LA center) corresponding to a location update. We obtain h(Olt,) for the random walk parameters T E {25, 30, 35. 40, 4.5) km/hr, tip E {30. 60, 90. 120, 180} sec and R E {3, 6. 12) km. Note that in the analysis of the LA sectorization performance in Section 6.4, we interpret tc in h(Olt c ) 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 (see Appendix 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^54 we will find an approximation to h(Olt,) for t, < t* seconds. We find that the p.d.f. of the angular deviation 0 of a user from the principal direction given that the user has travelled for time t gives a good approximation to h(01t,) for t, < t* seconds. This p.d.f. is denoted by f(01t) and is given in Eqn. (2.21). We evaluate the goodness of fit of f(91t) to h(01t,) obtained from simulation by integrating the absolute difference between them. The maximum value is 2 and the minimum is 0. Fig. 6.3 shows the goodness of fit for T7 = 40 km/hr, 7 /, = 60 sec., A, // = 1 call/hr together with the corresponding call arrival p.d.f. 6.4 Performance Analysis of the Paging Schemes with Location Area Sectorization In this section, the effects of LA sectorization on flood paging, spread paging and selective paging are studied. 6.4.1 Flood paging and Spread Paging The performance analyses of flood paging and spread paging with LA sectorization are basically the same. We will express the average paging delay and paging traffic with LA sectorization, denoted by D s , and Ts „, in terms of the average paging delay and paging traffic without 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 of sector 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), as 00 Ps , 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 average paging delay, D,,(i), given that the user is in sector i. Then, we average these paging delays CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION ^55 1 0.8 goodness of fit 0.6 call arrival p.d.f. 0.4 0.2 00^ ----------- 4^6 2 8^10 call arrival time (min) (a) 0.8 0.6 goodness of fit 0.4 call arrival p.d.f. 0.2 0 0 2^4^6^8^10^12^14 16^18 call arrival time (min) (b) 0.5 0.4 0.3 0.2 0.1 0 ^ ^ ^ ^ 20 25 5 10^15 call 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. 30 CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION ^ 56 using sector probabilities to obtain D SeC . For flood paging, D„,(i) = i. For N sectors, Dsec = N (6.4) E Psec(i)• =i 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 N sectors, we have D„, = 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) =1 To derive the average paging traffic, T,, with LA sectorization, we first find the average paging traffic Tsec (i) given that the user is in sector i. T„, is obtained by averaging T„.„(i) using sector probabilities. Flood paging and spread paging have the same expression for T „JO. Let NR be the total number of cells contained in an LA of size R, as given in Eqn. (3.3) and let a; be the fractional angle subtended by sector i, i.e., ai = T9 .7-,where B, is the total angle subtended by , sector 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,}. For CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^57 N sectors, we have T = [(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 =1 If all sectors are of the same size, we have a, =^and T„, becomes T , = 1+ (T —1) + —(NR— ) N -1 ^ s Ps„(i + 1).^(6.7) i=1 For sectorization patterns 1 and 2, N = 2 and 3 respectively. 6.4.2 Selective paging In the analysis of the average paging delay D SeC and traffic T s , with LA sectorization, we first 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 D SeC and T We will find the average paging delay, D,,(i,t), given that the user is in sector i at time t and 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 by (1 /) — 7) (t); -7) SEC (2 t) = (R^1) +D(t); Eqn. (5.24). For an LA of size R and at time t, TO _ sEc,–, 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 have D„,(1) =^P„c(i,t)+ [(R + 1) +D(t)]P„,(2,t) + • • • ^ CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION + RR + 1) R (N — ^ 58 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=1 Then, the average paging delay of the LA sectorization is 00 D sec = f D,„(t) f (t) dt.^ c (6.9) 0 In the derivation of T S ,(t), we will find the average paging traffic, T„,(i,t), given that the user is in sector i and then, average T sec (i,t) using sector probabilities to obtain Tsec(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 is the total angle subtended by sector i. Let T(t) denote the average paging traffic of selective paging without LA sectorization given in Eqn. (5.26). For an LA of size R and at time t, 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 have T sec (t) = T(t)^+ {[(NR — 1)ai +1]+ T(t)a 2 IP„,(2,t) + {[(N R — 1)a 1 + 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 P ec(i, 1,t)^ak.^ s (6.10) i=1^k=1 If all sectors are of the same size, ai = kr and T S ,(t) becomes T(t) NR —1 N-1 . T,,(t) = [ 1— P„^ ,(1,t)]+^ ^+ N N 14). (6.11) i=1 Then, the average paging traffic of LA sectorization is = I T,,,(t) L(t) dt. 00 T„, (6.12) 0 For sectorization patterns 1 and 2, N = 2 and 3 respectively. 6.5 Numerical Results In 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 in Chapter 3, the location updating scheme in Chapter 4 and the random walk model in Chapter 2 with infinitely long trip length were simulated for the three paging schemes with LA sectorization pattern 1 and pattern 2. The speed of the user is 40 km/hr. We assume the mean hold time to be 60 sec and the cell radius is 1 km. The average paging delay and traffic of the paging schemes with 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.5 and 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 and selective paging with LA sectorization pattern 1, the average paging traffic can be reduced by approximately 50% and the increase in the average paging delay is less than 10%. With LA sectorization pattern 2, the reduction in the average paging traffic is approximately 60% and the increase in the average paging delay is less than 20%. CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^60 400 1.4 p no sectorization pattern 1 pattern 2 1.2 1.7.1 'a 200 to ' Ei 1 0.8 300 ou 2 4^6^8 100 0 10 LA size 2^4^6 8 10 8 10 LA size (a) 400 >,^1.4 -c) 0.0 .s^1.2 a. - • -^- no sectorization pattern 1 pattern 2 ------ a.) co 300 au Cs CC ---------^ - - c).0 CC 0.8 2 4^6^8 200 100 0 10 LA size 2^4^6 LA size (b) Figure 6.4 Performance of flood paging without LA sectorization, with LA sectorization pattern 1 and with pattern 2 for 7 = 40 km/hr, th = 60 sec,^= 1 call/hr and re d/ = 1 km. (a) Analysis. (a) Simulation. - • - • • no sectorization pattern 1 - - - - • pattern 2 6 -c) 01) . n. 4 0.0 C) 2 C) 0 2^4^6 8 LA size (a) C) OD ou C) CC C) 2^4^6 8 10 LA size - • - • no sectorization pattern 1 - - - - • pattern 2 6 .5 0 10 4 2 0 2^4^6 8 10 LA size Figure 6.5 Performance of spread paging without LA sectorization, with LA sectorization pattern 1 and with pattern 2 for 7 = 40 km/hr, th = 60 sec, ^= 1 call/hr and r,en = 1 km. (a) Analysis. (a) Simulation. CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION^61 - - - no sectorization pattern 1 ^ pattern 2 . --------------------- 2^4^6 LA size 8 - u 60 • 1 40 ) 0.0 0 10 - . - . - no sectorization ^ pattern 1 ^ pattern 2 20 (a) • 2^4^6 LA size 8 10 60 E`1 40 n . V 20 ts ^ ^ 2^4^6 8 10 LA size 0 (b) ^ ^ 8 10 2^4^6 LA size Figure 6.6 Performance of selective paging without LA sectorization, with LA sectorization pattern 1 and with pattern 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 changes in 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 the mean 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 are omitted from the figures. These figures show that the paging schemes are not very sensitive to 7/.. and Acall• • CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION ^62 2 Flood^0 pattern 1 Spread x pattern 2 Selective on ro °'1.5 ------- -0^-0-^----0 --------- ------- 20^30^40^50 mean speed (km/hr) 30^40^50 mean speed (km/hr) (a) 60 - - • - Flood^0 Spread x ^ Selective 3. pattern 1 pattern 2 oti 40 a. 01) ctl 2. ▪ 5 2 --------^ -a ^ -a ,-,-,^ 1t 20^30^40^50^20 - -'- - _,. - mean speed (kin/hr) 30^40 50 mean speed (km/hr) (b) 200 150 - • - • - Flood^0 pattern 1 Spread x pattern 2 ^ Selective oL • 100 op 4. 20^30^40 ^mean speed (km/hr) ^ 5 50^20^30^40 ^ ^ 50 mean speed (km/hr) (c) Figure 6.7 Performance of LA sectOrization on flood paging, spread paging and selective paging versus user mean speed 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. CHAPTER 6 PAGING SCHEMES WITH LOCATION AREA SECTORIZATION ^63 12 1 - - • - Flood^0 pattern I Spread X pattern 2 ^ Selective - -x ------- -o ------- -0 7.0 ^=^= = = )( 40^60^80 100 120 40^60^80 100 120 mean velocity hold time (sec) mean velocity hold time (sec) - • - • - Flood^0 pattern I Spread X pattern 2 ^ Selective 40^60^80 100 120 40^60^80 100 120 mean velocity hold time (sec) mean velocity hold time (sec) - • - • - Flood^0 pattern I Spread X pattern 2 ^ Selective = -- -^- - -----^-------- 40^60^80 100 120 40^60^80 100 120 mean velocity hold time (sec) mean velocity hold time (sec) (c) Figure 6.8 Performance of LA sectorization on flood paging, spread paging and selective paging versus user mean 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 x^ ^x . 12 ^ e E.,.,.,:^10 ^ T., .r - • - • - o^ 64 Flood^0 pattern 1^‘'d Spread X pattern 2 Selective^ .? 8 VIc .:1.5^ t,".4 x x ^ x0 ^ v.,^xp ^ 0^I) ^ ^ e^ Cd^ Cd : 5 05^1^1.5^2 1.5 call arrival rate (calls/hr) call arrival rate (calls/hr) (a) 80 4 3 2 Eu 60 Flood^0 pattern I Spread x pattern 2 Selective oA 7 40 ------- x -------- -------- x e -------- -------- o^:L%) 2 1 0 5^1^1.5 8 2^ 5^1^1.5 call arrival rate (calls/hr) call arrival rate (calls/lu) (b) - • - • - Flood^0 pattern I Spread X pattern 2 ^ Selective 05 1^1.5 call 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 call arrival rate for 7 = 40 km/hr, ih = 60 sec and r re ll = 1 km. (a) LA size = 2. (h) LA size = 6. (c) LA size = 10. CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY IN MOBILITY PARAMETER VALUES In the selective paging scheme, the cellular system keeps estimates of the user mobility parameters : 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 comes in. In Section 5.3, we analyzed the performance of selective paging assuming that the system has exact knowledge of the mobility parameter values. It was found that selective paging gives better performance than spread paging in terms of average paging delay and traffic. In this chapter, we examine the sensitivity of selective paging to uncertainty in mobility parameter values. 7.1 Angular Deviation Parameter In the user mobility model, the parameter as affects how close the actual user direction is 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 corresponding value of a9 is 4.2. In this section, we examine the sensitivity of selective paging to uncertainty in this parameter value. In the sensitivity tests, we assume that the mobility parameters kept by the system are T = 40 km/hr, 7h = 60 sec, d = oc and a9 = 4.2 (95% criterion), and the user has the same mobility parameters except for a9. We examine two cases in which 85% and 98% 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 cell radius rcen = 1 km and call arrival rate A c aii = 1 call/hr. The results are shown in Fig. 7.1. The 99% confidence intervals are within ±5% of the average values shown and are omitted from the 65 CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY ^ 66 IN MOBILITY PARAMETER VALUES figure. Spread paging is not sensitive to the changes of ao and both the average paging delay and traffic change by less than 5%. In selective paging, there is practically no change in the average paging delay and traffic in the performance with 98% criterion. For the performance with 85% criterion, there are significant increases in both average paging delay and traffic. For an LA of size 10, the average paging delay increases from 1.75 to 2.7 and the average paging traffic increases from 55 to 96. In both cases, selective paging still has a better performance than spread paging in terms of average paging delay and traffic. 7.2 Mean Speed In this section, we examine the sensitivity of selective paging to uncertainty in user mean speed. We let the mobility parameters kept by the system be T = 40 km/hr, = 60 sec, d = oc and 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. The performances of selective paging and spread paging are obtained from simulation for rcell = 1 km and 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 user mean speed; the changes in the average paging delay and traffic are less than 10%. The higher the user mean speed is, the higher are the average paging delay and traffic. The reason is that with 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. Selective paging is increasingly sensitive to uncertainty in user mean speed as the LA size increases. In case 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, resulting in more paging delay and traffic. For an LA of size 10, the average paging delay increases from 1.7 to 4.5 and the average paging traffic increases from 55 to 102. Nevertheless, selective paging still gives a better performance. In case 2 when the actual user mean speed is 20 km/hr and the CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY ^ IN MOBILITY PARAMETER VALUES 6 5.5 85% criterion 95% criterion 98% criterion 5 4.5 0^Selective paging X^Spread paging 4 3.5 3 2.5 2 2^3^4^5^6 7 8 9 10 7 8 9 10 LA size (a) 120 100 85% criterion 95% criterion 98% criterion 80 0^Selective paging X^Spread paging 60 40 20 2^3^4^5^6 LA size (b) Figure 7.1 Sensitivity of the performances of selective paging and spread paging to uncertainty in ao for 7 = 40 km/hr, 7,, = 60 sec. d = x, r,en = 1 km. ) can = 1 call/hr and system's^= 4.2. (a) Average paging delay. (b) Average paging traffic. 67 CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY ^ 68 IN MOBILITY PARAMETER VALUES system estimates it to be 40 km/hr, the system overestimates the radial distance travelled by the user from the LA center resulting in more delay and traffic. For an LA of size 10, the average paging 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, the increase in the average paging traffic is much greater. The reason is that with roughly the same number of additional rings paged due to uncertainty in user mean speed, the system tends to first page 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 paging while the average paging traffic is higher. 7.3 Mean Velocity Hold Time In the user mobility model of Section 2.1, the user holds a speed and a direction for some random time, th, with mean, t i„ 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 mobility parameters 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 paging are obtained from simulation for rce n = 1 km and kale = 1 call/hr. The results are shown in Fig. 7.3. The 99% confidence intervals are within ±5% of the average values shown. Both schemes are not very sensitive to uncertainty in th. In spread paging, there is practically no change in the average paging delay and traffic. In selective paging, the changes in the average paging delay and traffic are less than 10%. In both cases examined, selective paging still gives a better performance. CHAPTER 7 SENSITIVITY OF PAGIVG SCHEMES TO UNCERTAINTY ^ IN MOBILITY PARAMETER VALUES 6 5.5 5 4.5 T.) -a^4 - • - - • mean speed = 20 km/hr ^ mean speed = 40 km/hr ^ mean speed = 60 km/hr O Selective paging x^Spread paging .C5 oq •- 1.5 2^3^4^5^6 ^ 7^8^9^10 LA size (a) 160 140 U $.• 120 100 a cd a. mean speed = 20 km/hr ^ mean speed = 40 km/hr ^ mean speed = 60 km/hr O • Selective paging Spread paging 80 di) cd 60 40 20 10 5 LA size (b) Figure 7.2 Sensitivity of the performances of selective paging and spread paging to uncertainty in 17 for 7 h = 60 sec, 7 = x,, a e = 4.2, r,en = 1 km, kali = 1 call/hr and system's IT = 40 km/hr. (a) Average paging delay. (b) Average paging traffic. 69 CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY ^ IN MOBILITY PARAMETER VALUES 6 5.5 mean hold time = 30 sec mean hold time = 60 sec mean hold time = 90 sec 5 0^Selective paging Spread paging 4.5 4 3.5 3 2.5 2 1.5 2^3^4^5^6 ^ 7^8^9^10 LA size (a) 120 mean hold time = 30 sec mean hold time = 60 sec mean hold time = 90 sec 100 80 60 40 20 0 2^3^4^5^6 ^ ^ ^ ^ 9 10 8 7 LA size (b) Figure 7.3 Sensitivity of the performances of selective paging and spread paging to uncertainty in 7 h for F = 40 km/hr, d = oc. 0 0 = 4.2. r,11 = 1 km. kali = 1 call/hr , and system's 7h = 60 sec. (a) Average paging delay. (b) Average paging traffic. 70 CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY ^ 71 IN MOBILITY PARAMETER VALUES 7.4 Mean 'Drip Length For convenience in analysis, the trip length in the user mobility model used in selective paging is taken to be oo. However, half of automobile trips in the United States are under 8 km long [37]. In this section, we examine the sensitivity of selective paging to uncertainty in the trip 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 parameters except for d. We examine two cases, d = 8 km and d = 16 km. The performances of selective paging and spread paging are obtained from simulation for rce ll = 1 km and Acall = 1 call/hr. The results are shown in Fig. 7.4. The 99% confidence intervals are within ±5% of the average values shown. In spread paging, the performance becomes more sensitive to the trip length as the 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 to 3.9 for d = 8 km; the average paging traffic decreases to 81 from 108 for d = 16 km and to 51 for d = 8 km. Selective paging is not very sensitive to uncertainty in the trip length. For an LA of size 10, the average paging delay changes from 1.7 to 1.9 for both d = 8 km and d = 16 km and the average paging traffic changes from 55 to 50 for d = 16 km and to 40 for d = 8 km. In both cases examined, selective paging still gives a better performance. CHAPTER 7 SENSITIVITY OF PAGING SCHEMES TO UNCERTAINTY ^ IN MOBILITY PARAMETER VALUES 6 5.5 5 mean trip length = 8 km mean trip length =16 km mean trip length =infinitely long Selective paging O X^Spread paging cc 4.5 c^4 •— • 3.5 Ce b4, 3 2.5 2 1.5 2^3^4^5^6 7 ^ ^ ^ 9 10 8 LA size (a) 120 100 mean trip length = 8 km mean trip length 16 km mean trip length = infinitely long 80 X ' O Selective paging X^Spread paging 60 40 20 2^3^4^5^6 LA size 7^8^9^10 (b) Figure 7.4 Sensitivity of the performance of selective paging and spread paging to uncertainty in 7 for F = 40 km/hr, i h = 60 sec, (19 = 4.2, r„ll = 1 km, Acall = 1 call/hr and system's 7/ = x. (a) Average paging delay. (b) Average paging traffic. 72 CHAPTER 8 CONCLUSION AND FUTURE WORK This thesis has examined the problem of locating a mobile user in a cellular system. To support location tracking of a mobile user, the idea of overlapping LA's was used. Two LA paging schemes, namely spread paging and selective paging, were proposed to determine the cell currently hosting a mobile user. A two-dimensional directional random walk process was proposed and used to model user mobility for performance evaluation. In comparison to a conventional flood paging scheme, spread paging and selective paging can yield typical paging traffic reductions of 50%. Selective paging performs better than spread paging in terms of average paging delay and average paging traffic. The disadvantage is greater implementation complexity. To further reduce the paging traffic, an LA sectorization technique was applied to spread paging and selective paging. Two sectorization patterns are examined. The results show that sectorization can yield typical paging traffic reductions of about 50% without any significant increase in paging delay. 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, was studied. It was found that spread paging is most sensitive to the mean trip length whereas 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. mobility model for portable telephone users instead of vehicular telephone users. 73 74 BIBLIOGRAPHY [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 Tetherless Access," IEEE Commun. Mag., pp. 30-39, July 1989. [6] D. C. Cox, "A Radio System Proposal for Widespread Low-Power Tetherless Communications," 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 Mobile Communications 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 Vehicular Technology, vol. VT-26, no. 1, pp. 43-46, Feb. 1977. [11] A. Murase and K. Imamura, "Location of Mobile Subscriber Station on Land Mobile Radio 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 Method for 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 Updates in Cellular Systems," IEEE 42'1 Veh. Tech. Conf., Denver, Colorado, pp. 694-697, May 1992. 75 [14] R. Thomas, H. Gilbert and G. Mazziotto, "Influence of the Moving of the Mobile Stations on the Performance of a Radio Mobile Cellular Network," 3rd Nordic Seminar on Digital Land 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 International Symposium on Personal, Indoor and Mobile Radio Communications, King's College, London, Sept. 1992. [17] K. Imamura and A. Murase, "Mobile Communication Control Using Multi-transmitter Simul/Sequential Casting (MSSC)," IEEE 36 th Veh. Tech. Conf., pp. 334-341, May 1986. [18] D. Munoz-Rodriguez, "Cluster Paging for Travelling Subscribers," IEEE 40 th Veh. Tech. Conf., Orlando, Florida, pp. 748-753, May 1990. [19] J. Lehmusvuori, "Network Aspects of the UMTS," 1992 IEEE International Conference on Selected Topics in Wireless Communications, Vancouver, B.C., pp. 16-20, June 1992. [20] 0. Grimlund and B. Gudmundson, "Handoff Strategies in Microcellular Systems," IEEE 41' Veh. Tech. Conf, St. Louis, MO, pp. 505-510, May 1991. [21] L. G. Anderson, "A Simulation Study of Some Dynamic Channel Assignment Algorithms in 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 Cellular Mobile 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 Mobile Communication Systems," IEEE Trans. on Veh. Tech., vol. 37, no. 2, pp. 92-103, May 1988. [24] S. Tekinay and B. Jabbari, "Handover and Channel Assignment in Mobile Cellular Networks," IEEE Commun. Mag., pp. 42-46, Nov. 1991. [25] S. M. Elnoubi, R. Singh and S. C. Gupta, "A New Frequency Channel Assignment Algorithm 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 Cellular 76 Communication 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 Mobile 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 Mobile Communication Standard," IEEE 38 th Veh. Tech. Conf., pp. 30-37, May 1988. [30] A. Eizenbofer and W. Fuhrmann, "Validation of the GSM Radio Interface Signalling Protocols — 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 Equipment 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 Communications 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 for Universal 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. of Traffic 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 Highways in 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 Mobile Communications Network Architecture for Universal Personal Telecommunications (UPT) Services," IEEE 41' Veh. Tech. Conf., St. Louis, MO, pp. 83-87, May 1991. 78 APPENDIX A ALPHA PROBABILITY DENSITY FUNCTION 1 The Alpha probability density function (p.d.f.) is given by f(x) = a [1-1-cr 2 (x-i.) 2 1tan - ' (aw) x— w< x<x w (A.1) ;^otherwise 0 and its cumulative density function (c.d.f.)^is x <^- w 0 F(x) = 1 tan 1 1a(x-)1 2^tan -1 (aw) x - w<x<x+w 1 - 2 (A.2) w < x. 1 There are three parameters ( x, w, a) which control different properties of the p.d.f. The p.d.f. is - symmetric about the mean 3; at which point the p.d.f. takes on its maximum value -- = a 2 tan -1 (aw).^ (A.3) The width of the interval of the random variable is defined by 2w. The parameter a controls the deviation of the random variables from the mean value. The larger a is, the less the random variable 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. The effects of a on the p.d.f. are illustrated in Fig. A.1. The variance is determined by w and a as 2 Cr = a tan -1 (aw)^a 2 . (A.4) 79 r -0.8^-0.6^-0.4^-0.2^0^0.2^0.4^0.6^0.8 x Figure A.1 Effects of a on Alpha p.d.f. with w = 1 and x = 0 ^ 80 APPENDIX B ASYMMETRIC GAUSSIAN PROBABILITY DENSITY FUNCTION The 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 by f(x) = Ai A2 1/27ra e^ ; x < 771 (B.1) 1_.= . _„L = 20 /2--- e^ 27rcr ; m <X and its c.d.f. is ;^x < 711 A14, ( 1 7:71 ) (B.2) F(x) = where + A2 ['12^("72s)1 ;^711 < X a2 = ry ai 2 Al^= A2 (B.3) 1 (B.4) +7 2'y — 1+ (B.5) y x = 1^1^yl 4)(x)^dy. (B.6) _CO There are three parameters : nz, aj and^The peak value of the p.d.f. occurs at m max [f (x)] = f(m) = A2 = Al 1 V2 7 Cq 1 V2 r cri (B.7) 81 0.6 0.5 0.4 03 0.2 0.1 2 x Figure 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 of m respectively. The left and right sides are scaled such that the p.d.f. is continuous at m and the area sum is one. Q 1 controls the spread of the p.d.f. and y determines how asymmetric the p.d.f. is. When y > 1, the right side is wider than the left side. If 7 = 1, the p.d.f. becomes the Gaussian 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. G B €--1.‘; dx = I xV270 - 0 2 ^ i 5 B^1c = ,2 ^2iro-2 = 0 2 d(2) x B ^1 ( 2a2) [ c _ 1_"27 I OC 27 — 2^r.o cr -\/77 B ^ .= Q. 27 , (B.8) ^ 82 The mean of the asymmetric Gaussian p.d.f. is I x f(x) dx -00 in 00 X A l^—^2^ A2 ^2dx^x ^ e^ °2 dx .\/rcrl 2'rcri2 2 . in —00^ CC o^ _ .2^ y ^ 2 A2^2 e °2 dx. = in+ I x Al e 2 °f dx + I x V271- oq^V27r al 2 (B.9) 0 ^—00^ Substituting Eqn. (B.3), (B.4), (B.5) and (B.8) in (B.9), we have = m+ = in + l Al ^A2 ai^a L^\ 127r f2Tr 2 1 r^2^2-y 1 + 7 cri ^+^°-1 ] a 1^2 (^1 + 7 2) = in+^ r1+ Vt2jr = in +^ 1 ).^ 7T — (B.10) 83 APPENDIX C TAIL PROBABILITY OF THE CALL ARRIVAL PROBABILITY DENSITY FUNCTION In Section 5.1.1, the call arrival p.d.f., fdt), in the paging scheme performance analysis is approximated by Mt) _ 1^ A Ali ca C —A " "i B V2 ir cr? ; 0< t< c c "?^; C < i (C.1) 0^; otherwise where 1^ A= ^ 1 — eA-1/ 7 R, B = 2 [1 — A (1 —^ Cf c = 11,^ B 211/ 2 Acair C A “'" (C.2) (C.3) (C.4) — = f (7R) = and 1 f (if?) g Ct h), 0.00023 (7R) 2 + 0.4307 (TR) — 8.7879^; 0 < 7R < 900 (C.5) (C.6) 0.8591 (tR) — 204.8937^; 900 < 7R g(1 1 ,) = —0.00167 h + 1.1041^; 30 < tip < 180.^(C.7) In this section, we want to find the tail probability, f, that a call arrives at time t > t*. For t* < c, = f t. f( 7) dr 84 t- = 1 — f Mr) dr t= 1 — A A C A T dr = 1 — A (1 — C At* ).^ (C.8) For t* > c, Mr) dr = t" co t- B^tr-o2 e 2 °? dr V2 ac? =BQ t* c ) ) (C.9) where Q(x) -= P' f^dY. r (C.10) S From Eqn. (C.3), B is upper bounded by 2; therefore, < 2Q (t* —c Qt. For example, if^= 1.65 (i.e. t* = c + 1.65 a c ) , Q (") = 0.0495 and E < 0.099. (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 |
File Format | 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. |
DOI | 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 |
Graduation Date | 1993-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | 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