Optimal management of distance-based location registration using embedded Markov chain

In this study, we deal with a Distance-Based Registration with Implicit Registration, which is an enhanced scheme of the Distance-Based Registration in mobile-cellular networks. In comparisons with other Location Registration schemes, various studies on the Distance-Based Registration scheme and performance have been performed. However, a real network hierarchy has not been properly reflected in the performance evaluation of the Distance-Based Registration. To accurately evaluate the registration and paging costs of the Distance-Based Registration, a real network hierarchy should reflect that a mobile network is made up of many Visitor Location Register areas. Furthermore, we use an embedded Markov-Chain model in the Visitor Location Register hierarchy, which can reflect not only the Implicit Registration effect of the outgoing calls of user equipment but also cell staying time of the user equipment that may follow a general distribution. Without consideration of the Visitor Location Register, the paging cost decreases due to a small paging area, but the location registration cost rises because of frequent inter Visitor Location Register. The numerical results according to the various conditions show an accurate evaluation of the Distance-Based Registration performance in a real network hierarchy and the general cell staying time. Generally, the total signaling cost will increase when we consider the Visitor Location Register. However, for more appropriate evaluation of the Distance-Based Registration performance, it is necessary to consider the Visitor Location Register hierarchy.


Introduction
Nowadays, a lot of users can send queries to get valuable information from various web objects through mobile devices in real world. 1 They receive many location-based services (such as navigation, gas station, hotel, and restaurant) through mobile devices. 2 With some technologies such as Big Data, Cloud Computing, and Internet of Things (IoT) in the mobile environment, tremendous amounts of data have been collected in databases and employed for the users. 3 Continuous mobility management for User Equipment (UE) is the core function of mobile communication. Location Registration (LR) is the process that allows an UE to register its location area on a network database like the Visitor Location Register (VLR) or the Home Location Register whenever the UE moves to new location area. When a call arrives at the UE, the mobile network must find the UE and identify its current cell to connect the call because a location area comprised many base stations (cells). This is called paging. Generally, the best trade-off exists between the registration and paging costs, which lead to optimal usage of the radio resources. [4][5][6] The numerous LR schemes have been proposed so far: zone-based, 4,5 movement-based, [7][8][9][10][11] timerbased, 8,11,12 distance-based, [13][14][15][16] and tracking area list (TAL)-based [17][18][19] registrations. In zone-based registration, UE registers a new location area on the network whenever it moves to a new zone. In movement-based registration, UE registers a new location area whenever the number of entering cells reaches the specified number. In timer-based registration, UE registers a new location area whenever its timer reaches the specified interval. In TAL-based registration, UE registers a new location area whenever it enters a new TAL area.
In our study, Distance-Based Registration (DBR), which is a typical dynamic LR, [13][14][15][16] is considered. DBR scheme is known to have sound performance. DBR is always superior to movement-based registration which is another typical dynamic LR. 14 Furthermore, in certain situations, DBR shows better performance than zone-based registration which is the most typical LR in most mobile-cellular networks. 20 In comparisons with other LR schemes, various studies on the DBR scheme and performance have been performed. [13][14][15][16] In the DBR scheme, when an UE enters a cell, the UE's location is updated if the distance from the last registered cell to current cell is equal to or greater than a predetermined distance threshold. Significant merits of the DBR scheme are that the UE registers its location less frequently compared to the movement-based registration scheme, and the ping-pong phenomenon, which is a main drawback of the zone-based registration scheme, is nonexistent. To reduce the registration cost of the DBR scheme, a DBR with implicit registration was proposed, and its performance was analyzed using stochastic models. 14 However, a real network hierarchy has not been properly reflected in the performance evaluation of the DBR. To perform a more realistic and exact evaluation of both the registration and paging costs of the DBR, a real network hierarchy should reflect that a mobile network is made up of many VLR areas. In addition, an embedded Markov-Chain (MC) model is adopted to consider the implicit registration effect of UE's outgoing calls and the general cell staying time.

DBR
In DBR, every time an UE registers, the distance between the current cell and the last-registered cell is equal to or greater than the threshold D. [13][14][15][16] The UE has not only the latitude and longitude (X r , Y r ) of the last-registered cell but also the latitude and longitude (X c , Y c ) of the current cell. The distance is computed by the difference between the latitudes and longitudes of those two cells.
In this study, for convenience sake, the distance between two cells is simply defined as the smallest number of cells to be crossed to reach one from the other. [13][14][15] Figure 1 shows a location area in the hexagonal cell configuration, given that the threshold D is 3, and a UE registers in the ring 0 cell.
According to the technical requirements, when an UE sends a page response message or an origination message successfully, the cell could find out the location of the UE. We call this implicit registration. [13][14][15] That is, when a call to/from the UE occurs successfully, the mobile network could realize the UE's cell by the page response message or the origination message without an actual LR message. In other words, if a network uses a DBR and implicit registration concurrently, the network could know the UE's cell without an actual registration process; therefore, it can establish a new location area, which reduces the number of LR. Thus, the LR cost of the DBR can be reduced through implicit registration. In this study, only the DBR with implicit registration which is an enhanced scheme of the original DBR is considered. Hereafter, DBR indicates the DBR with implicit registration.

Network architecture
A mobile-cellular network is composed of many mobile switching systems, and each switching system has network databases such as VLR and Home Location Register. In terms of the VLR, a mobile network is composed of VLRs as shown in Figure 2.
In this study, we assume that a mobile network is composed of square-shaped VLR areas, and each VLR area consists of the same-sized hexagonal cells. The followings are also assumed in this study.
When an UE enters a neighboring cell, the probability of choosing one of the neighboring cells is one-sixth for any neighboring cell. The incoming and outgoing calls are generated with the rates l ic and l oc , respectively. According to the Poisson processes and the staying time in a cell, T m is generally distributed with the mean 1=l m .
Note that with the addition of the Poisson processes, the incoming calls with the rate l ic and the outgoing calls with the rate l oc form overall calls with the rate l c (= l ic + l oc ). Figure 1 shows a location area of the DBR with the distance threshold D = 3. Generally, the location area for the distance threshold, D, depends on D rings (0, 1, ..., D 2 1). Figure 3 shows a VLR area which is made up of 10 3 10 hexagonal cells. In this hierarchy, an UE performs LR when it enters a new VLR as well as when its distance value is equal to or greater than the threshold, D. In other words, if an UE enters a neighboring VLR, it performs LR regardless of its current distance value, which will be explained later with the use of some examples in this article.

Random walk mobility model
We assume that a random walk mobility model 3,13,14,16 is employed in this study. In this model, the probability of choosing one of the neighboring cells is one-sixth when an UE enters a neighboring cell.
The Fluid-flow model was used in some studies 10,18,21 to obtain the rate at which an UE moves to another VLR. The authors suggested that as a cell staying time is exponentially distributed and further, the Fluid-flow model is adopted, then the location area staying time will also be exponentially distributed. However, this assertion is evidently incorrect since the location area staying time of the UE, which is composed of various combinations of cell staying times, generally cannot follow an exponential distribution. 22 Nevertheless, they analyzed the performance of some of the registration schemes by using their assertion. 10,18 In this study, the distribution of the cell staying time is not limited to an exponential distribution. It is feasible to use a general cell staying time; therefore, an incorrect assertion (such as, if the cell staying time is exponentially distributed and a fluid-flow model is adopted, then the location area staying time will also be exponentially distributed) is not needed.
The rate at which an UE moves to another VLR becomes different depending on the UE's position in  the VLR area. For instance, the probability of moving to another VLR is one-third, and the probability of the UE moving to another VLR regarding the center cell ''b'' is 0 if the UE is in the boundary cell ''a'' in Figure 3. Therefore, to accurately evaluate the registration cost, it is necessary to take into account these different characteristics depending on the UE's location in the VLR area.

Embedded MC model
We introduce an embedded MC model to reflect the network hierarchy, the general cell staying time, and the implicit registration effect of the outgoing calls. For the convenience of the explanation, we consider a very small VLR area that comprises 4 3 4 hexagonal cells, and it is assumed that D = 2, as shown in Figure  4. It is also assumed that each cell has its own ID from 1 to 16 (= 4 3 4).
In Figure 4, for an improved understanding, the same cell ID is used for different cells in the different neighboring VLRs. Note that cells 1 and 13 show the same probabilistic characteristics since both of them are border cells. Assuming D = 2, the location area of the UE registering in the cell 7 is composed of the cells 7, 8, 9, 10, 6, 2, and 1, as shown in Figure 4. The UE registers its location when it moves out of this location area. If the UE moves out of this location area from the cell 6, it registers in one of the cells 3, 5, and 11, which is called intra-VLR LR, since the UE registers in the same VLR. Let us consider the other case. If an UE moves out of this location area from the cell 2, and it registers in one of the two cells in the neighboring VLR, then this is called inter-VLR LR since the UE registers in a different VLR.
Intra-VLR LR: LR for areas which are within the same VLR when an UE registers. Inter-VLR LR: LR for areas which are in the different VLR when an UE registers.
Alternatively, note that location area of an UE registering in the cell 2 is composed of the cells 2, 1, 7, 6, and 3, as shown in Figure 4. If the UE in a cell 2 moves to the left cells in the neighboring VLR, the UE must perform the inter-VLR LR, even if his or her distance is less than 2.
Since the signaling cost of the inter-VLR LR is larger than the signaling cost of the intra-VLR LR, 10,23 to exactly evaluate the signaling cost of the LR, the inter-VLR LR and the intra-VLR LR must be analyzed separately, which is very complicated. Without considering the inter-VLR LR, an analysis of the LR cost is rather simple. 13,14 When the VLR hierarchy is considered, the following two factors help modeling through the MC theory in comparison with the case where the VLR hierarchy is not considered: The position of a cell in the VLR should be included in the state of an UE since the UE's movement to the neighboring cells may or may not cause a inter-VLR LR according to the position of the UE's cell.
The state of the UE should be defined so that it can reflect the distance change in a new cell when the UE moves to the neighboring cells.
For instance of Figure 4 where D = 2, if it is assumed that the distance of an UE in a cell 14 is 1 when the UE moves to the right cell, it performs the inter-VLR LR. If this UE then moves to the cell 15, does it register its location? The following two outcomes are possible: (1) If the UE's last registered cell is 11 or 13, then the UE in the cell 15 will register its location.
(2) Alternatively, if the UE's last registered cell is 10, then the UE in the cell 15 will not register its location.
From the above cases, it is evident that an UE's distance in a new cell depends on the cell where the UE finally registered. Therefore, it is necessary to define the UE's state in the current cell so that the UE can include the cell of the last registration since the UE's distance in a new cell is directly affected by the cell where it finally registered. Now, assuming D = 2, we show a MC model for the consideration of the inter-VLR LR. In the proposed model, the state (i, j) is defined as a state of an UE where the UE who last registered in the cell j and is now in the cell i.
Concerning an UE in one of the states (2, 7), (2, 6), or (2, 3), a similar state transition diagram can be obtained. In Figures 5 and 6, the transition probability to the state (2, 0) is 1 À m = 1 À P½T c .T m , and this means that a call to/from the UE generates before the movement to other cells occurs. We can obtain the probability that an UE moves to other cells before a call occurs as follows 4,5 The UE's staying time in a cell, T m , affects the transition probability. We assume that T m follows a Gamma distribution, the mean is 1=l m , and the variance is V . In this case, P½T c .T m is  Especially, when the T m follows an exponential distribution with the rate l m , then g = 1 and P½T c .T m is given as Note that, when an UE is in the state (2, 0), it can transfer to other states as shown in Figure 7. Since the state (2, 0) is a state where the current cell of the UE becomes the ring-0 cell through an incoming-or outgoing-call generation, the cell staying time in this state is the residual cell staying time of the UE when the UE stays in the current cell after a call generation, and this is denoted by R m in this article. Then, the transition probability from the state (2, 0) to other cells is expressed as P½T c .R m , and it can be derived as follows In addition, the transition probability from (2, 0) to (2, 0) itself is expressed by P½T c \R m = 1 À P½T c .R m = 1 À (1 À f Ã m (l c ))=r, which represents the probability that an incoming or outgoing call to/ from the UE generates before the UE moves to other cells.
Note that, even when we assume a 4 3 4-cell VLR area and D = 2, the number of states (\16 3 8) is too large to draw a state transition diagram for the whole states. However, it is possible to express the transitions among the states by using mathematical equations, and the Limiting Probability (for an MC) of each state can be obtained. A number of mathematical equations for the attainment of the Limiting Probability of each state will be explained, and they are used to calculate some performance measures like the LR and the paging costs.
Let p (i, j) be the Limiting Probability of (i, j) with the transition-probability matrix P. Then, we can derive the Limiting Probability of (i, j), p (i, j) , using the balanced equation 24 Now, let us obtain the total signaling cost using these Limiting Probabilities.

Total signaling cost
The total signaling cost consists of the LR and the paging costs. A number of notions that are used to calculate the signaling cost are defined as follows: : probability that UE performs the intra-VLR LR when he or she moves to a cell from the state (i, j) p 2 (i, j) : probability that UE performs the inter-VLR LR when he or she moves to a cell from the state (i, j). p 0 (i, j) : probability that UE does not perform the LR when he or she moves to a cell from the state (i, j). N(j) : the number of paged cells when UE is in the state (Á , j) or (j, 0) Then, for instance, the following values can be obtained: p 1 (3, 2) = 1=3 (when UE moves to the cell 4 or 5) p 2 (3, 2) = 1=3 (when UE moves to the cell 13 or 14) p 0 (3, 2) = 1=3 (when UE moves to the cell 2 or 6) p 1 (7, 2) = 1=2 (when UE moves to the cell 8, 9, or 10) p 2 (7, 2) = 0 p 0 (7, 2) = 1=2 (when UE moves to the cell 1, 2, or 6) If an UE is in the state (3, 2), (7, 2), or (2, 0), the number of paged cells is N (2) = 5, and, if an UE is in the state (6, 7), (7, 7), or (7, 0), the number of paged cells is N (7) = 7.
Suppose that U is the LR cost for one registration and Dist½i, j is the distance between cell i and cell j. Then, the LR cost per an incoming call C dbr U can be given as follows where n is the number of cells that form one side of a VLR area (i.e. n = 4 in Figure 4). In the above equation, it is assumed that the inter-VLR LR cost is three times of the intra-VLR LR cost. 10,23 The number of paged cells is 1 + 3D(D À 1) since most mobile networks adopt simultaneous paging. 10,13,14,18 However, in this study, wherein the VLR hierarchy is considered, the number of paged cells decreases when an UE is around the boundary of the VLR. In the example, if the UE last registered in the cell 2, the number of cells to be paged is not 7 but 5. Therefore, considering the VLR, the decrease in the number of cells to be paged should be considered.
By letting V be the paging cost for one cell, we can obtain the paging cost per an incoming call as follows where p j = P i, Dist½i, j ł D p (i, j) + p (j, 0) . In this example (4 3 4-cell VLR area and D = 2), the paging cost is given as follows f3 Á (p 4 + p 16 ) + 4 Á (p 1 + p 8 + p 12 + p 13 ) + 5 Á (p 2 + p 3 + p 14 + p 15 ) + 6 Á (p 5 + p 9 ) where p j = P i, Dist½i, j ł 2 p (i, j) + p (j, 0) . Finally, the total signaling cost is obtained by Numerical results For the numerical results, a 12 3 12 VLR area is assumed with the following assumptions U = 10, V = 1, l m = 1, l c = l ic + l oc = 0:5 + 0:5 = 1:0 It is supposed that both an incoming call and an outgoing call generate according to the Poisson processes with the rates l ic and l oc , respectively. Also, it is assumed that the staying time of an UE follows a Gamma distribution with a shape parameter of 0.5 and a scale parameter of 2.
The total signaling costs for various thresholds are shown in Figure 8. The total signaling cost is made up of the LR and paging costs. Generally, as the distance threshold increases, the LR cost decreases because of the infrequency of the registrations, but the paging cost increases due to the large paging area. Finally, in this example, the optimal threshold D is 2 that minimizes the total signaling cost. The optimal threshold D that results in the minimal signaling cost can be derived for any other circumstance. Figure 8 shows the total signaling costs for two different conditions (in consideration of the VLR or not). Note that C u is the LR cost, C p is the paging cost, and C t is the total signaling cost for each incoming call. When the threshold D is small such as D = 1;3, the total signaling cost with the VLR hierarchy is larger than the cost without the VLR hierarchy. This is mainly because the number of LR increases especially around the VLR boundary with the VLR hierarchy. Note that, since the paging area around the VLR boundary decreases, the expected paging cost with the VLR hierarchy is less than the cost without the VLR hierarchy. However, in this example, it is evident that when the threshold D is small such as D = 1;3, the rise of the LR cost is more crucial than the reduction of the paging cost.
Alternatively, when the threshold D is large such as D = 4, the total signaling cost without the VLR hierarchy is larger than the cost with the VLR hierarchy. This is because the expected paging cost without the VLR hierarchy for a large D increases sharply. However, the cost with the VLR hierarchy does not increase significantly compared to the case where the VLR hierarchy is not considered due to the decreased paging area around the VLR boundary. Figure 9 shows the LR costs of different VLR sizes for various thresholds. Generally, because of the infrequency of the registrations, the more the distance threshold is, the less the LR cost is. In addition, it is clear that as the VLR size decreases, the LR cost increases since the inter-VLR LR also increases. Figure 10 shows the paging costs of different VLR sizes for various thresholds. In general, as the distance threshold increases, the paging cost increases very sharply due to the large paging area. Furthermore, as the VLR size decreases, the paging cost decreases due to the small paging area around the VLR boundary. Figure 11 shows the total signaling costs for different VLR sizes. In the circumstances, regardless of the VLR size, the optimal threshold D that results in a minimal signaling cost is always 2. Also, it is evident that, in Figure 11, if the optimal threshold D = 2 becomes the focus, a consideration of the VLR hierarchy results in an incremental increase of the total signaling cost, regardless of the VLR size. Figure 12 shows the total signaling costs for various VLR sizes when D = 2. Note that C u is the LR cost, C p is the paging cost, and C t is the total signaling cost for each incoming call. Obviously, if the optimal threshold D = 2 becomes the focus, the total signaling cost for a small VLR is larger than the cost for a large VLR.
Therefore, the total signaling cost is less than that of any VLR sizes if the VLR hierarchy is ignored (no VLR). In other words, if the VLR hierarchy is ignored, the total signaling cost for real mobile networks is underestimated; that is, when the VLR hierarchy is ignored, its performance seems to be better than its actual performance. Figure 13 shows the signaling costs for different Call-to-Mobility Ratios (CMR = l ic =l m ) when D = 2. It is evident that, as the CMR increase (in other words, as a call generates frequently), the paging cost increases sharply, but the registration cost decreases gradually. As a result, the total signaling cost increases almost proportionally to the CMR. Figure 14 shows the signaling costs for different cell staying time of an UE when D = 2 and l oc = l ic = 1.
It is shown that, as the cell staying time increases (in other words, as the number of cell entrance decreases), the registration cost decreases sharply, but the paging cost is unchanged. As a result, the total signaling cost decreases steeply especially when cell staying time is small compared to the paging interval.    From the various results, the following findings are evident: (1) The consideration of a real network hierarchy results in an incremental increase of the total signaling cost and (2) there exists the optimal threshold that minimizes the total signaling cost, since the best tradeoff is between the registration cost and the paging cost.
Even if the total signaling cost rises due to the network hierarchy, VLR hierarchy should be necessary considered to obtain a more accurate performance evaluation of the DBR in the real world.

Conclusion
In our study, we dealt with a DBR with implicit registration, which is an enhanced scheme of the DBR. For an accurate analysis of the registration and paging costs of the DBR, the real network hierarchy where a mobilecellular network is made up of VLRs should be considered. In addition, an embedded MC model is adopted to consider the implicit registration effect of the outgoing calls and the general cell staying time.
The various numerical results for diverse conditions show that the consideration of a real network hierarchy results in an incremental increase of the total signaling cost. That is, the rise of the registration cost is larger than the reduction of the paging cost compared to the simple case where the VLR hierarchy is not considered. Even if the total cost rises due to consideration of the network hierarchy, it is necessary to take into account the VLR hierarchy to accurately analyze the performance of the DBR in the real world.

Declaration of conflicting interests
The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.