Optimizing location management cost through registration area overlapping: Models, problems and methods

Location management is an essential component of many of the current communication network technologies that provide services to mobile users, e.g., Mobile Internet Protocol (MobileIP) and Global System for Mobile Communications (GSM). The basic operations of location management are the pushing of location information (i.e., updating) and the pulling of location information (i.e., searching) around the network. Current trends in population rise, size of coverage and decrease in size of the registration/location areas greatly impact the overhead of location management.; Performance improvements on location management schemes have been based on the update/search trade-off. However, saturation of trade-off optimizations pushes research toward finding new ways to improve performance of location management. Location area overlapping is one such performance improvement with benefits widely known in the research community However, the limits of the improvements which location area overlapping offers are generally unexplored.; In this thesis, new ways of optimizing location management are devised through the study of optimization problems that arise from the application of overlapping registration areas in mobile networks. It is shown that knowledge of user mobility and call pattern can help further optimize the efficiency of location management, including finding an optimal degree of overlapping and determining an optimal registration choice.; The problem of optimal overlapping is studied under a detailed system cost model. An adaptive algorithm is devised to deal with changes in mobility and call conditions. The algorithm proposed has linear message and quadratic computational complexity and reaches a local optimal solution. Simulations using an urban gravitational mobility model show that an optimal overlapping can reduce by orders of magnitude the load of location management, subject to the input mobility and call patterns, with respect to a non-optimized or non-overlapping solution.; The problem of optimal registration choice is studied under various cost models, including a uniform cost model and a general cost model. Analysis of competitiveness shows that the competitive ratio of any deterministic algorithm can be made arbitrarily large, thus rendering the problem non-competitive. However, an on-line algorithm is proposed that has better performance than the random-choice approach. Moreover, it is shown that the problem in the generalized cost model is an abstraction of many known problems in mobile communications, including optimal anchoring and optimal address binding in MobileIP. Simulations using urban model show a reduction of thirty percent in the number of registrations.