Cache-Enhanced Dynamic Movement-Based Location Management Schemes for 3G Cellular Networks.

Authors Avatar

Cache-Enhanced Dynamic Movement-Based Location Management Schemes for 3G Cellular Networks

A Thesis

Presented in Partial Fulfillment of Requirements for the

Degree of Master of Science

in the College of Arts and Sciences, Georgia State University, 2003

by

Krishna Priya Patury

Committee:

____________________________________

Dr. Yi Pan, Chair

____________________________________

Dr. Anu Bourgeois, Member

____________________________________

Dr. Alex Zelikovsky, Member

____________________________________

Date

____________________________________

Dr. Martin D. Fraser

Department Chair

Abstract

Keeping track of mobile terminals moving from one place to another has been and will always be one of the key issues in mobile communication, be it cellular or Personal Communications Service. Location management involves two major kinds of operations: Location update- by which the system keeps track of the location of the mobile terminals that are not in conversation and Paging which is a search process by which the system searches for the Mobile Terminal by sending polling signals to cells in the paging area (which may include one or more cells). To perform either of these operations would incur a significant amount of cost, which should be minimized in the systems.

Many mobility management schemes have been proposed as of now for 2-tier Cellular/PCS networks but none for the 3G cellular networks, especially for dynamic location management (where the size of a location area is determined dynamically according to the changes of mobility and calling patterns of mobile terminals).

A recent proposal challenges the same, where the gateway location registers have been deployed as a cache to handle the location management of roaming subscribers in a visited network with the underlying architecture having Home Location Register/Visitor Location Register remaining the same. This not only helps in reducing the signaling traffic between the visited and home mobile system but also location updating and handling of user profile data across network boundaries is optimized. This thesis research aims at implementing this new concept and an improvement over the existing proposal is attempted by employing a caching location strategy at the location registers for certain classes of users meeting certain call and mobility criteria. The results obtained for the standard 3G (without any additional cache) would be compared with those from the three cases when a cache is applied only at the GLR, only at the VLR, and at both. It can be analyzed from the results when and for what cases a cache would be most profitable in 3G Cellular Networks.

Acknowledgements

I would like to thank my advisor Dr. Yi Pan for his support and invaluable guidance throughout my thesis work. I am also very grateful to the other members of my thesis committee, Dr. Anu Bourgeois and Dr. Alex Zelikovsky for their advice and spending their valuable time in reviewing the material. I would also like to express my gratitude to Dr. Yang Xiao and Dr. Jie Li for taking time to evaluate my experimental results and review and comment on the thesis document.

I also want to thank my friends and family for their encouragement without whose support I could not have lived through this dream of mine.

Table of Contents

Abstract        

Acknowledgements        

Table of Contents        

LIST OF FIGURES        

LIST OF TABLES        

LIST OF ACRONYMS        

1.        Introduction        

2.        Literature Review        

2.1. Evolution of Cellular networks and the concepts involved:        

2.2. Framework of a Wireless Network in 3G and Location Management in 3G        

2.3. Teletraffic Modeling        

2.3.1 Network Topology Model        

2.3.2 The Mobile Residence Model        

2.3.3 Mobility Models        

2.3.4 The Call Arrive Model        

2.4. Basic Approaches of Location Management        

2.5. Current Approaches in Location Update        

2.5.1 Mobile Initiated Location Update Strategies        

2.5.2 Prediction-based Location Update Schemes.        

2.5.3 Profile-based Location Update Scheme        

2.5.4 Protocol-based Location Update Scheme        

2.6. Current approaches on Terminal Paging        

2.7.Qualitative comparisons of the location management schemes        

3.        A Location Management Scheme in 3G and Per-User Caching        

3.1. A Recently Proposed Movement-based Location Management Scheme in 3G        

3.2. The Concept Of Caching In Cellular Networks        

3.3. Per - user caching        

4.        The Cache-Enhanced Location Management Scheme        

4.1. Need for an Improved Movement-based Location Management Scheme        

4.2.1. The New Improved Scheme – Employing the concept of Per-user Caching        

4.2.2. The standard 3G without any additional cache        

4.2.3. The standard 3G with a cache at the VLR        

4.2.4. The standard 3G with a cache at the GLR        

4.2.5. The Standard 3G with a cache at both the VLR and the GLR        

4.3. The Location Update Scheme in Detail.        

4.4. Paging scheme.        

5. Simulation Model        

5.1. Network Topology.        

5.2 Teletraffic modeling        

5.2.1 Residence time model        

5.2.2 Mobility Model        

5.2.3 Call Arrival Model        

5.3. Discrete Event Simulator Design        

5.3.1 Object Description        

5.3.2 Simulation controls flow        

6. Experiments and Analysis        

6.1 Experiment Setup        

6.1.1 Assumption        

6.1.2 Network initialization        

6.1.3 Input and output        

6.2 Experiment 1: Relationship of CMR and total location management Cost.        

6.2.1 Case1—Standard 3G Dynamic Movement-based location management scheme        

6.2.2 Case2—Standard 3G Dynamic Movement-based location management scheme with Cache at VLR        

6.2.3 Case3—Standard 3G Dynamic Movement-based location management scheme with Cache at GLR        

6.2.4 Case4—Standard 3G Dynamic Movement-based location management scheme with Cache at the VLR and the GLR        

6.2.5. Relationship between the CBR and CMR for the caching schemes        

6.2.6. Analysis        

6.3 Experiment 2: Comparison of the four schemes of location management.        

6.3.1 Total location management cost        

6.3.2 Paging cost.        

6.4 Experiment 3: The effect of cache size on the improved movement-based location management scheme.        

6.4.1. The effect of cache size at the VLR on the improved movement-based location management scheme.        

6.4.2. The effect of cache size at the GLR on the improved movement-based location management scheme.        

7. Conclusion        

BIBLIOGRAPHY        


LIST OF FIGURES

Figure.1.1 The Cell Topology …………………………………………………………...10

Figure.1.2 Roaming-As the MT moves from cell to cell the signal is passed accordingly………………...……………………………………………………………..14

Figure 2.1 In FDMA, each phone uses a different frequency…………………………....20

Figure 2.2 TDMA splits a frequency into time slots ……………………………………21

Figure 2.3 In CDMA, each phone's data has a unique code. …………………..………..22

Figure 2.4 Summary of forthcoming cellular-data services……………………...………25

Figure 3.1 The Structure of the 3G Network. …………………………………………...48

Figure 3.2 Mobility Database Architecture  …………………………………………….49

Figure 4.1 The flow of control for the location updates case1  …………………………60

Figure 4.2 The flow of control for the location updates case2  …………………………62

Figure 4.3 The SDF Partitioning Scheme  ………………………………………………63

Figure 4.4 The flow of control for call delivery when the called MT is not within the

same GLR. (For Case 3)..………………………………………………………………..66

Figure 5.1 Overall Structure Of The Target Network.  …………………….……………69

Figure 5.2. Location Area Topology.  …………………………………………………...70

Figure 5.3 Neighboring Topology of Target Network. .…………………………….…...70

Figure 5.4 The Overall Cell Structure of Target Network.  ………………………….….71

Figure 5.5 The Simulation Control Flow.  ………………………………………………75

Figure 6.1 CMR vs. Total cost for the Standard 3G Location Management Scheme…...83

Figure 6.2 Cost Analysis for the Standard 3G Location Management Scheme. ………..84

Figure 6.3 Total Cost vs. CMR for Scheme2 (Standard 3G With Cache at VLR). ..…....86

Figure 6.4 Cost Analysis for Scheme2 (Standard 3G With Cache at VLR)  ……………87

Figure 6.5 Total Cost vs. CMR for Scheme3 (Standard 3G with Cache at GLR) ………89

Figure 6.6 Cost Analysis for Scheme3 (Standard 3G with Cache at GLR)  ……………90

Figure 6.7. Total Cost vs. CMR for Scheme4 (3G with Cache at GLR and VLR). …… .93

Figure 6.8 Cost Analysis for Scheme4 (3G with Cache at GLR and VLR………………………………………………………………………………………94

Figure 6.9 Cost Benefit Ratio Vs CMR  ………………………………………………..95

Figure 6.10. Comparison of the Four Location Management Schemes  ………………..99

Figure 6.11. Comparison of Paging Cost for the Four Schemes  ……………………...101

Figure 6.12. Effect of different sizes of Cache at the VLR on the Total Cost …………103

Figure 6.13 Effect of different sizes of cache at the GLR on Total Cost  ……………..104


LIST OF TABLES

Table 6-1 Constants for Network Initialization.  ……………………………………..…79

Table 6-2 Input parameters for Scheme1 (Standard 3G)  ……………………………….82

Table 6-3 Outputs for Scheme1 (Standard 3G)  ………………………………………...82

Table 6-4 Input parameters for Scheme2 (Standard 3G with Cache at VLR).…………..85

Table 6-5 Outputs for Scheme2 (Standard 3G with Cache at VLR). …………………...86

Table 6-6 Input parameters for Scheme3 (Standard 3Gwith Cache at GLR). …………..88

Table 6-7 Outputs for Scheme3 (Standard 3Gwith Cache at GLR)  ……………………88

Table 6-8 Input parameters for Scheme4 (3G with cache at GLR and VLR)  ………….91

Table 6-9 Outputs for Scheme4 (3G with cache at GLR and VLR)  ……….…………..92

Table 6-10 CBR for the different values of CMR. ……………………………………...95

Table 6-11 Total Location Management Cost For The Four Schemes  …….…………..98

Table 6-12. Total Paging Cost For The Four Schemes  ……………………………….100

Table 6-13. Effect of cache size at VLR on the Total Cost   …………………………..102

Table 6-14 Effect of cache size at GLR on the Total Cost  ……………………………104

LIST OF ACRONYMS

  1. HLR – Home Location Register
  2. VLR – Visitor Location Register
  3. GLR – Gateway Location Register
  4. PCS – Personal Communication Systems
  5. MT – Mobile Terminal
  6. MSC- Mobile Switching Center
  7. 3G – Third Generation
  8. PDA – Personal Digital Assistant (electronic handheld information device)
  9. GPS – Global Positioning System
  10. BS – Base Station
  11. LA – Location Area
  12. MTSO – Mobile Telephone Switching Office
  13. RA – Registration Area
  14. SA – Service Area
  15. MIN – Mobile Identification Number
  16. SID – System Identification Number
  17. G_LA – Gateway Location Area
  18. CMR – Call-to-Mobility Ratio
  19. TDMA – Time Division Multiple Access
  20. FDMA – Frequency Division Multiple Access
  21. CDMA – Code Division Multiple Access
  22. WCDMA – Wideband Code Division Multiple Access
  23. GSM – Global System for Mobile Communication
  24. PDC – Personal Digital Cellular
  25. UMTS – Universal Mobile Telecommunications System
  26. SMS – Short Message Service
  27. QoS – Quality of Service
  28. GPRS – Global Packet Radio Service
  29. EDGE – Enhanced Datarates for Global Evolution
  30. PSTN – Public Switched Telephone Network
  31. PA – Paging Area
  32. 3GPP – Third Generation Partnership Project
  33. LCMR – Local Call-to-Mobility Ratio
  34. LRU – Least Recently Used
  35. SDF – Shortest Distance Partitioning
  36. TLDN – Temporary Location Directory Number
  37. STP – Signal Transfer Point
  38. GTT – Global Title Translation
  39. CBR – Cost Benefit Ratio


  1. Introduction

         Millions of people within the United States and around the world use cellular phones. They are such great gadgets that with a cell phone one can talk to anyone on the planet from just anywhere!! No wonder they are so popular and commonly used!

These days, cell phones provide an incredible array of functions, and new ones are being added at a breakneck pace. Depending on the cell-phone model, we can store contact information, make task or to-do lists, keep track of appointments and set reminders, use the built-in calculator for simple math, send or receive electronic-mail, get information (news, entertainment, stock quotes) from the Internet, play simple games and integrate other devices such as PDA’s, MP3 Players and GPS receivers. It’s not exaggerating by saying that cell phones might become a necessity rather than a luxury in a few years to come.

Having heard about a cell phone for a long time, it natural of us to wonder how a cell phone actually works? This is precisely the question that has lead me to choose to do my thesis on a related topic. One of the most interesting things about a cell phone is that it is actually a radio -- an extremely sophisticated radio, but a radio nonetheless. In the dark ages before cell phones, people who really needed mobile-communications ability installed radio telephones in their cars. In the radio-telephone system, there was one central antenna tower per city, and perhaps 25 channels available on that tower. This central antenna meant that the phone in your car needed a powerful transmitter -- big enough to transmit 40 or 50 miles (about 70 km). It also meant that not many people could use radio telephones -- there just were not enough channels [].

The genius of the cellular system is the division of a city into small cells. This allows extensive frequency reuse across a city, so that millions of people can use cell phones simultaneously. In a typical analog cell-phone system in the United States, the cell-phone carrier receives about 800 frequencies to use across the city. The carrier divides the entire city into cells. Each cell is typically sized at about 10 square miles (26 square kilometers) [1]. Cells are normally thought of as hexagons on a larger hexagonal grid, as shown in Figure1.1:

                                                                                                               Location Area

                                                                                                         

                                                                                       

                                                                                                            Base Station

                                                                                                                  Rings

                   

FIGURE 1.1 THE CELL TOPOLOGY

Each cell has a base station that consists of a tower and a small building containing the radio equipment that is used to communicate with Mobile Terminals over preassigned radio frequencies.

Cell phones have low-power transmitters in them. Many cell phones have two signal strengths: 0.6 watts and 3 watts [1]. The base station also transmits at low power. Low-power transmitters have two advantages:

  • The transmissions of a base station and the phones within its cell do not make it very far outside that cell. Therefore, in Figure1.1, both of the cells in alternate rings and non-adjacent cells can reuse the same frequency. The same frequencies can be reused extensively across the city.
  • The power consumption of a cell phone, which is normally battery-operated, is relatively low. Low power corresponds to small batteries, and this is what has made handheld cellular phones possible.

The cellular approach requires a large number of base stations in a city of any size. A typical large city can have hundreds of towers. But because so many people are using cell phones, costs remain low per user. Each carrier in each city also runs one central office called the Mobile Telephone Switching Office (MTSO). This office handles all of the phone connections to the normal land-based phone system, and controls all of the base stations in the region. Groups of several cells are connected to a Mobile Switching Center (MSC) through which the calls are then routed to the telephone networks. The area serviced by a MSC is called a Registration Area (RA) or Location Area (LA). A group of RA’s composes a Service Area (SA). Each SA is serviced by a Home Location Register (HLR). A wireless network may include several SAs and thus several HLRs. More about the Location Registers is discussed in the Literature Review (Chapter2).

All cell phones have special codes associated with them. These codes are used to identify the phone, the phone's owner and the service provider. Electronic Serial Number (ESN) (a unique 32-bit number programmed into the phone when it is manufactured), Mobile Identification Number (MIN) (a 10-digit number derived from the owners phone's number), and a System Identification Code (SID) (a unique 5-digit number that is assigned to each carrier by the FCC-Federal Communications Commission (A U.S. government agency charged with the task of regulating all forms of interstate and international communication)) are a few of the standard cell phone codes employed. While the ESN is considered a permanent part of the phone, both the MIN and SID codes are programmed into the phone when one purchases a service plan and has the phone activated.

The next most intriguing question would be what exactly happens when a person A is trying to make a call to a person B. Here is what happens to the call [1](in 1G systems):

  • When B first powers up his/her phone, it listens for an SID on the control channel. The control channel is a special frequency that the phone and base station use to communicate to one another about things like call set-up and channel changing. If the phone cannot find any control channels to listen to, it determines that it is out of range and displays a "no service" message.
  • When it receives the SID, the phone compares it to the SID programmed into the phone. If the SIDs match, the phone knows that the cell it is communicating with is part of its home system.
  • Along with the SID, the phone also transmits a registration request, and the MTSO keeps track of B’s phone location in a database -- this way, the MTSO knows which cell B is in when it wants to ring his/her phone.
  • The MTSO gets the call from user A, and it tries to find B. It looks in its database to see which cell B is in.
  • The MTSO picks a frequency pair that the phone will use in that cell to take the call.
  • The MTSO communicates with B’s phone over the control channel to tell it which frequencies to use, and once B’s phone and the tower switch on those frequencies, the call is connected. B is then able to talk by two-way radio to his friend A.
  • As B moves toward the edge of the cell, B’s cell's base station notes that the signal strength is diminishing. Meanwhile, the base station in the cell B is moving toward sees B’s phone signal strength increasing. The two base stations coordinate with each other through the MTSO, and at some point, B’s phone gets a signal on a control channel telling it to change frequencies. This hand off switches B’s phone to the new cell. This is llustrated in Figure 1.2 [1].

FIGURE.1.2 ROAMING-AS THE MT MOVES FROM CELL TO CELL THE SIGNAL IS PASSED ACCORDINGLY.

           

If the SID on the control channel does not match the SID programmed into one’s phone, and then the phone knows it is roaming. The MTSO of the cell that the person is roaming in contacts the MTSO of his/her home system, which then checks its database to confirm that the SID of the phone he is using, is valid. His home system verifies his phone to the local MTSO, which then tracks his phone as he moves through its cells. And the amazing thing is that all of this happens within seconds.

Both of the above concepts constitute location management in cellular networks, which is the focus of this thesis. Location management is a key issue in the operation of PCS networks. Two kinds of activity are involved in the operation: location update and paging. The basic approaches in location update, and terminal paging and more about the network topology will be discussed in the second chapter. The technique that is used for location update in this thesis is LA-based i.e. location registration will be triggered when a MT moves into new LA [].

There are generally two kinds of techniques for location update: static and dynamic. In the static location update, the size of a paging area is fixed and is equal to the LA. Each cell in the LA will page once when a call arrives. The problem with this however would be if the LA is large, the paging cost is very high and a MT located at the boundary of LAs may suffer from excessive location updates.

In dynamic schemes, the size of the location area is determined dynamically according to the changes of mobility and calling patterns of the mobile terminals. The different kinds of dynamic location management schemes in use and the concepts involved are discussed in Chapter 2.

Although commercial mobile telephone networks existed as early as the 1940’s, many consider the analog networks of the late 1970’s to be the first generation (1G) wireless networks. The details of 1G, 2G and 3G and their stages of evolution and the concepts involved are discussed in the Literature review of the second chapter.

The most interesting feature of this thesis is that not only is it implemented for 3G networks where an additional register called the Gateway location register [] it utilized (more details in Chapter 3), but a caching strategy is also employed at the different registers to analyse how well the current structure can be optimised. The caching strategy [] would basically deal with that set of users who make a number of calls to a particular region, as is usually the case in practise. The entire simulation is done for four cases:

  • The standard 3G network without any cache.
  • 3G with a cache at the GLR
  • 3G with a cache at the VLR
  • 3G with a cache at both GLR and VLR.

 The improved scheme employing caching is discussed in more detail in the fourth Chapter.

A simulation model is designed to evaluate the performance of the proposed scheme. It is assumed that the cellular network is partitioned into hexagonal cells of the same size. The target network consists of two SAs, 4 G_LAs and eight LAs, two hundred and forty four BSs and nine hundred and seventy six MTs.

An exponential cell residence time distribution is assumed in the study. We assume each MT resides in a cell for a time period then moves to one of its neighbors with equal probability. The Poisson process and exponential process are used to describe the incoming call arrivals and the service time of a phone call respectively.

A discrete event simulator is designed to implement the simulation model. The object-oriented design makes it easier to extend the model or make modifications to the existing model. The objects in the design represent the objects’ natural behavior and structure. The design is implemented entirely with Java programming language, which is portable across platforms.  The system design and location update and call delivery strategies employed in the improved scheme are discussed in Chapter 4. Chapter 5 has the detailed discussion about the simulation model and discrete event simulator.

The following experiments are conducted using discrete event simulator among the four schemes:

  1. Relationship between Call Migrate Ratio (CMR- it is the ratio of an MT’s call arrival rate to it’s migration rate) and the total location management cost.
  2. Total location management cost among four selected schemes.
  3. The effect of movement threshold value and paging delay on our proposed scheme (with cache) as compared with the standard scheme.

The experimental results show that employing a cache at both the GLR and the VLR would be the most beneficial compared to any other case. However, there would always be a trade-off between the memory costs and the performance gain. But since the memory costs are coming down every day, employing a cache for most user populations is beneficial any day. More details about the experiments are given in Chapter 6.

 In summary, this paper is organized as follows: Chapter 1 is the introduction. The literature review is provided in the second chapter. Location management in 3G in particular and the caching strategies employed are discussed in Chapter 3. The details of the improved location management scheme are in Chapter 4 with the details of the simulation model in Chapter 5. The experimental results are analyzed in Chapter 6. Chapter 7 draws the conclusion.


  1. Literature Review

Location management is a key issue in the operation of wireless networks. The Mobile Terminals (MT’s) are either the automobile or hand held telephones or portable computers that the users use to send and receive calls. In order to successfully deliver an incoming call, the wireless network must keep track of the location of each mobile terminal continuously []. This process of tracking and locating MTs so that calls arriving for them can be directed to their current location is called location management [].

Location Management is different from the location services in routing. Routing is the act of moving information across networks from a source to a destination. Along the way, at least one intermediate node typically is encountered. Routing involves two basic activities: determining optimal routing paths and transporting information groups (typically called packets) through an internetwork. Location Management on the other hand deals with not only the tracking of the MTs but also the call arrival aspect of the delivery of calls.

2.1. Evolution of Cellular networks and the concepts involved:

Although commercial mobile telephone networks existed as early as the 1940’s many consider the analog networks of the late 1970’s to be the first generation (1G) wireless networks []. These networks were designed as fixed size networks, where an analog image of the sound was transmitted over the air and through the networks. The receiver and transmitter were tuned to the same frequency, and the voice that was transmitted was varied within a small band to create a pattern that the receiver could reconstruct, amplify and send to a speaker.

Join now!

 Although this was quite a revolution at that time, it suffered from a number of serious shortcomings.  For instance, there was only a certain amount of mobility, lack of efficiency (because very few callers could fit into the available spectrum) and since everything was analog, there was not much scope for optimisations like coding or compression and the components were big and expensive making the handsets seem quite huge.

The result of this and a number of other reasons led to digital transmission, which led to the 2G cellular networks. With 2G came lower power consumption, small equipment size, higher ...

This is a preview of the whole essay