Simple Analysis of Dynamic Location Update Schemesin Cellular Wireless NetworksBhaskar Krishnamachari and Stephen WickerComputer Engineering Technical Report CENG 02-09Department of Electrical Engineering – SystemsUniversity of Southern CaliforniaLos Angeles, California 90089-2562213-740-4465A simple analysis of dynamic location update schemesin cellular wireless networksBhaskar Krishnamachari, Stephen [email protected], [email protected] present a simple first order analysis comparingthree dynamic location update schemes that have beenprop os ed for mobility management in cellular net-works. The analysis is used to compare the relativeperformance of the three schemes and to illustratethe tradeoff between the c osts of frequent locationupdates and paging.1 IntroductionOne of the fundamental problems in a cellular wire-less network is that of efficient user location for com-pletion of incoming calls. A three-step procedure iscommonly involved: location updates, paging and mo-bile acknowledgement.In most existing systems, the cellular network is di-vided into static location areas consisting of multi-ple cells. Cellular users provide registration messageswhen they move from one location area to another.When a call arrives, all cells in a location area arepaged. The mobile then acknowledges the call whenit receives a page and the call session is initiated.There is a tradeoff between costs associated with up-date and paging. When the location areas are small,updates occur more frequently, and conversely whenthe location areas are large, a greater number of cellsneed to be paged. As Bar-Noy et al. point out, “fre-quent up dates cause high power consumption at themobile units and load the w ireless network. Network-wide searches load the backbone and the wireless net-works” [1].Static update strategies such as the ones currently inuse can be inefficient because i) they are common toall users, and ii) cells in the border of location ar-eas tend to have higher location update traffic. Todeal with this, dynamic location update s chemes arerequired in which the updates are based on individ-ual user mobility patterns. Three such schemes arethe time-based, movement-based, and distance-basedstrategies proposed in [1].The authors in [1] presented a somewhat complicatedanalysis of these schemes assuming memoryless andMarkovian movement patterns for a topology of cellsarranged as a ring. They show that, in terms of thetradeoff achieved between the costs of location up-date and paging, the distance-based strategy is thebest, and that the time-based strategy performs theworst of the three. However, it is not clear to what ex-tent the assumptions about movement patterns andtopology in [1] re present realistic situations.We consider the same three dynamic location updateschemes, and present a first-order analysis of theirperformance. Our analysis makes few assumptionsregarding the use r mobility model and captures themain issues in a straightforward manner.12 Model and AssumptionsWe assume that all cells are roughly of the samesize. The only assumption about the users’ move-ments is that their speed (in terms of the numberof cells crossed per unit time) is always bounded byVmax. Let us further define Vavas the average speedof the mobile user, also m easured in cells crossed perunit time.The number of all cells at most k cells away from agiven cell, M , can be defined as follows:M = 1 +k−1Xi=0L ∗ i (1)where L is the number of neighbors of each cell - 2for a ring topology, 6 for hexagonal cells in the plane,and 8 for square cells.In comparing the three location update schemes, wewill assume the following common model for paging:all cells where the user could possibly be are pagedsimultaneously. The schemes are compared in termsof their average update cost, while keeping the pagingcost the same.3 AnalysisWe consider each of the three schemes in turn:3.1 Distance-based SchemeIn this scheme, the mobile provides an update whenits location is m ore than k cells away in distance fromthe location of the last update. In this case, since theuser can be potentially in any of the M cells aroundthe last location, the average cost of paging in termsof numb er of cells paged per call is:Cp= M = 1 +L2(k2− k) (2)The location update cost, which we define as thenumber of location updates per unit time, will thendepend upon the speed of the user. Specifically,Cdistanceu,av≤Vavk(3)We have an inequality here because although the usermay cross Vavcells in unit time the number of up-dates for this scheme will be less than Vav/k if theuser’s motion is not a straight line.3.2 Time-based SchemeIn this scheme, the mobile provides a periodic updateexactly once every t time units. If we wish to keep thepaging cost the same as that of the distance-basedscheme, the following relationship must hold: t =k/Vmax. In this case too, the user could potentiallyagain be located in any of the cells that are within aradius k of the last location. Hence the paging cost isagain given by equation (2). With this time period t,the average location update cost for the time-basedscheme is:Ctimeu,av=1t=Vmaxk(4)3.3 Movement-based SchemeIn this scheme, the mobile provides an update when itcrosses exactly k cell boundaries. Again, in the worstcase, the user could potentially be in any of the Mcells around the last location, hence the paging costwould still be given by equation (2). The locationupdate cost for this scheme is:2Cmov ementu,av=Vavk≤Vmaxk(5)3.4 Comparison of Update SchemesCombining the results shown in equations (3), (4)and (5), we ge t that when the paging cost for allthree schemes is kept constant as per equation 2, thefollowing relationship holds:Cdistanceu,av≤ Cmov ementu,av≤ Ctimeu,av(6)Thus we have that the distance-based dynamic up-date scheme in general performs better than themovement-based dynamic update scheme, which inturn performs better than the time-based dynamicupdate scheme – the same conclusion reached by theauthors in [1].3.5 Illustration of the Update-PagingTradeoffWe can also study the trade-off between the costs ofpaging and location updates in these schemes. This isillustrated here for the time-based approach. Com -bining equations (2) and (4), we get the followingrelationship between the two costs:Cp= 1 +L2 V2max− VmaxCtimeu,avCtimeu,av2!(7)Similar expressions can be easily derived for the dis-tance and movement-based approaches. This rela-tionship is shown graphically