# Paging and Location Management in IEEE 802.16j Multihop Relay Network

Authors: Kuan-Po Lin; Hung-Yu Wei
Journal: Journal of Computer Systems, Networks, and Communications
 (2010)

---

## Abstract

IEEE 802.16j is an emerging wireless broadband
networking standard that integrates infrastructure base stations
with multihop relay technology. Based on the idle mode operation
in IEEE 802.16j, we propose a novel location management and
paging scheme. It integrates the paging area-based and the
timer-based location update mechanism. In paging area-based
scheme, an idle mode mobile station updates when it moves to
a new paging area. In timer-based scheme, an idle mode MS
updates when the location update timer expires. In this work, we
formulate the mathematical model to evaluate the performance of
the proposed paging scheme. A new random walk mobility model
that is suitable for modeling in multihop relay network is created.
Optimization of location update timer is also investigated.


---

## Body

## 1. Introduction

IEEE 802.16 standard [1] (or WIMAX) is an emerging broadband wireless access system to provide users with high-speed multimedia services. The IEEE 802.16e standard provides mobility support for WiMAX system. Mobile Stations (MSs) are usually powered by battery. Paging mechanism and MS idle mode operation are defined to save power in mobile IEEE 802.16e system. Recently, the IEEE 802.16j Multihop Relay (MR) standard is proposed to support for multihop relay communications with Relay station (RS) [2–4]. IEEE 802.16j standard provides better network coverage and enhance system throughput performance. In 802.16j network, the base station is called Multihop Relay BS (MR-BS). Relay Stations (RSs) relay signaling and data messages between the MR-BS and the MS.In WiMAX system, MS enters idle mode to save power when there is no data to transmit or to receive. Whenever an incoming data message arrives, the network applies paging mechanism to wake up the dormant MS. During idle mode operation, MS still needs to update its location occasionally so that network only needs to perform broadcast paging in selected cells when a data message arrives. Tradeoff between signaling cost and location precision of idle mode MS is the main design issue in paging and location update protocol design.Conventional cellular network paging and location management design could be categorized as follows(1) Location-based paging area schemes [5]: users update when they move across the border between different paging areas. Paging area might be overlapping or nonoverlapping. (2) Time-based schemes [6]: users update periodically when the update timer expires. (3) Distance-based schemes [7–9]: users update when moving a fixed distance away from the last updating location. (4) Movement-based schemes: users update based on the number of passing stations. (5) Velocity-based schemes: users update based on the velocity. (6) Profile-based schemes [10]: users update according to their behaviors. Some schemes apply an integrated approach to reduce the signaling cost [11]. Paging for microcell/macrocell overlay is also studied [12]. Pipeline paging technique could be applied to reduce the paging delay [13].In this paper, we propose a novel paging and location update algorithm that integrates timer-based scheme and location-based paging area scheme for IEEE 802.16j system. For performance evaluation, we investigate a random walk mobility model that is suitable to evaluate the mobility issue in multihop relay cellular network like 802.16j, as base stations and relay stations operate differently but coexist in this type of network. The mobility model is described and validated in Section2. The paging scheme design is presented in Section 3. In Section 4, we evaluate the system performance analytically. The optimization of location update period is presented in Section 5. Performance results are presented in Section 6. Finally, we conclude the paper in Section 7.


## 2. Mobility Model

Random walk model is widely used for modelling mobility in cellular networks [6, 11, 14, 15]. Markov chain formulation is used to compute the probability that MS movement. Labelling and grouping cells based on geometric symmetry reduces the complexity of the model. Akyildiz et al. proposed a random walk model for MS mobility in cellular networks [14]. In this model, MSs move in the hexagonal cell. The probability that MS moves to an adjacent hexagonal cell is a system parameter. When the MS moves to an adjacent cell, it has the uniform probability to move to one of the 6 adjacent hexagonal cells. The cellular random walk model is no longer applicable in multihop relay network as some cells are base stations and some are relay stations.In the proposed model, the probability of MS movement from arbitrary celli to arbitrary cell j could be computed while computational complexity is limited. The goals of the proposed random walk mobility model for multihop relay networks are to (1) uniquely identify the relay station cells and (2) simplify the mathematical model based on the symmetric property.An MR-BS (multihop relay base station) or an RS (relay station) is located in the center of a hexagonal cell. Random walk mobility model is applied to characterize the movement of mobile stations (MSs). The Absolute Geographical Location is applied to uniquely identify the hexagonal cells. The Relative Moving Distance is applied to reduce the complexity of the random walk mathematical model. Rules of mapping between Absolute Geographical Location and Relative Moving Distance will also be described in this section.


### 2.1. Absolute Geographical Location Model

The Absolute Geographical Location is used to uniquely identify the geographical location of each hexagonal cell. Unlike the random mobility model described in [14], hexagonal cells have to be uniquely labelled to distinguish MR-BS and RS. As shown in Figure 1, we apply oblique coordinates with axis x1 and x2 to label the hexagonal cells. Each cell is uniquely identified as A(x1=i,x2=j). The origin of the oblique coordinate is A(0,0), where MR-BS is usually located.Figure 1
Absolute Geographical Location Model:A(x1;x2).


### 2.2. Relative Moving Distance Model

As described previously, the Absolute Geographical LocationA(i,j) indicates the geographical cell location. Due to the symmetric property of random walk mobility model, the probability of an MS moving from cell A(i,j) to new cell A(m,n) is the same as moving from cell A(0,0) to A(m-i,n-j). Thus, in terms of moving probability between cells, we can model that the moving probability by considering the probability of an MS moves from the origin R(0,0) to R(u,k) in the Relative Moving Distance model. The MS moving probability PR(u,k) in the Relative Moving Distance model is the same as PA(i,j)→A(m,n) and PA(0,0)→A(m-i,n-j) in the Absolute Geographical Location model.The Relative Moving Distance model is consisted ofnr tiers of hexagonal cells. A 5-tier Relative Moving Distance model is shown in Figure 2. In the boundary of the wireless network, an MS may enter an outer cell and does not come back to the network. In the Markov Chain models, those outer cells will be modeled as absorbing states. The outer cells are the fifth tier of the network, which is denoted as out, as shown in Figure 2.Figure 2
Relative Moving Distance Model:R(u,k).There are three axes (v1, v2, and v3) across the origin R(0,0), and the network is divided into six regions. A hexagonal cell is labelled as R(u,k). The (u,k) tuple is labelled based on the oblique coordinate system with axes v1=(0,1) and v2=(1,0). Note that, for the cells in the same tier, the sum of u and k is the same and is equal to the tier number nr. Cells in Relative Moving Distance model are symmetric. This model provides mobility information for Absolute Geographical Location. An MS movement from (i,j) to (m,n) in the Absolute Geographical Location model will be transformed to an MS movement from (0,0) to (|m-i|,|n-j|) in the Relative Moving Distance model. Notice that the u,k in Relative Moving Distance model are all nonnegative integer; hence, absolute value operation is taken during the transformation.


### 2.3. Simplified Moving Distance Model

Since the six regions in the Relative Moving Distance model shown in Figure2 are symmetric in terms of MS moving probability, we could further simplify the moving distance model. Figure 3 illustrates the Simplified Moving Distance model, which is actually the Region I of the original Relative Moving Distance model. The cell in the Simplified Moving Distance model is denoted as R′(u,k), where u,k are non-negative integers and u≥k.Figure 3
Simplified Moving Distance Model:R′(u,k).


### 2.4. Rules of Mapping

We will describe a set of mapping rules that transforms the relative moving distance to the absolute geographical location. Because of the Markov property, the future MS movement depends only on the current location state. In the Relative Moving Distance model, a mobile station always starts fromR(0,0) as we proposed this relative mobility model for movement from the current location of the MS. The coordinate space is considered to be shifted so that the origin of the coordinate space is centered at the current MS location.We observe the geometric property of the hexagonal topology to create 3 mapping rules to simplify the model. We classify the 6 regions in Figure2 based on the geometric properties. Region I and IV will apply Mapping Rule I. In Regions I and IV, we find that (m-i)(n-j)≥0 is always true. Regions II and V will apply Mapping Rule II. In Regions II and V, we find that (m-i)(n-j)<0 and |m-i|≥|n-j| is always true. Regions II and VI will apply Mapping Rule III. In Regions II and VI, we find that (m-i)(n-j)<0 and |m-i|<|n-j| is always true. Based on the geometric property, these 3 classifications of mapping rules will be discussed in Theorems 1, 2, and 3, respectively.Moving fromA(i,j) to A(m,n) in a given time interval is transformed to moving between R(0,0) and R(u,k) in the same time interval. If a user starts at A(i,j) and locates in A(m,n) after i unit time, the probability is equal to that of moving from R(0,0) to R(u,k) after i unit time. We define PR(u,k)i as the probability that an MS moves from R(0,0) to R(u,k) after i unit time:(1)PA(i,j)→A(m,n)i=PA(0,0)→A(m-i,n-j)i=PR(u,k)i.In the Relative Moving Distance model, three axes divide the network into six regions. As the Relative Moving Distance model applies an MS-centric view that considers relative movement from the starting location, the MS movement is always starting fromR(0,0). The MS movement in the original Absolute Geographical Location from A(i,j) to A(m,n) is equivalent to the transformed MS movement from R(0,0) to R(m-i,n-j). The movement to R(m-i,n-j) could be classified based on values of m-i and n-j. The classification of the mapping rules also corresponds to the mobile movement in the six regions shown in Figure 2.All cells in Regions I and IV have the property(m-i)(n-j)≥0. The relative movement vector (m-i,n-j) can be denoted as a linear composition of two axes v1=(0,1) and v2=(1,0) with integer coefficients a and b:(2)a·v1+b·v2=a·(0,1)+b·(1,0)=(m-i,n-j).In the Simplified Moving Distance modelR′(u,k), u and k are non-negative integers. We solve the above equation and derive the non-negative solution by taking absolute values a=|n-j|, b=|m-i|. Since u≥k in the Simplified Moving Distance model, as shown in Figure 4, u is the larger one among a and b while the smaller one is k.Figure 4
Mapping example.For example, as shown in Figure4,  A(1,3) can be decomposed as the linear combination of v1 and v2. Notice that the moving probability from A(0,0) to A(1,3) is the same as the moving probability from R′(0,0) to R′(3,1):(3)(1,3)=a·v1+b·v2=a·(0,1)+b·(1,0)⇒a=3,b=1.From observation, the Mapping Rule I maps the absolute geographical location to the relative moving distance model in Regions I and IV, as shown in Figure2. Notice that the relative moving values (m-i) and (n-j) are both positive values (in Region I) or both negative values (in Region IV).Theorem 1 (Mapping Rule I).
While(m-i)(n-j)≥0,(4)PA(i,j)→A(m,n)i={PR′(|m-i|,|n-j|)i,if|m-i|≥|n-j|,PR′(|n-j|,|m-i|)i,if|m-i|<|n-j|.If an MS moves to cells in Region II or V in Figure2, the following two properties hold: (m-i)(n-j)<0 and |m-i|≥|n-j|. The relative movement vector (m-i,n-j) can be denoted as a linear combination of v2=(1,0) and v3=(1,-1). We can get a=|m+n-i-j|, b=|n-j| by solving the equation:(5)a·v2+b·v3=a·(1,0)+b·(1,-1)=(m-i,n-j).Theorem 2 (Mapping Rule II).
While(m-i)(n-j)<0 and |m-i|≥|n-j|,(6)PA(i,j)→A(m,n)i={PR′(|n-j|,|m+n-i-j|)iif|n-j|≥|m+n-i-j|,PR′(|m+n-i-j|,|n-j|)iif|n-j|<|m+n-i-j|.If an MS moves to Region III or VI, the following two properties hold:(m-i)(n-j)<0 and |m-i|<|n-j|. The relative movement vector (m-i,n-j) can be denoted as a linear combination of -v1=(0,-1), and v3=(1,-1).  We can get a=|m-i|, and b=|m+n-i-j| by solving the equation:(7)a·v3+b·(-v1)=a·(1,-1)+b·(0,-1)=(m-i,n-j).Theorem 3 (Mapping Rule III).
While(m-i)(n-j)<0 and |m-i|<|n-j|,(8)PA(i,j)→A(m,n)i={PR′(|m-i|,|m+n-i-j|)iif|m-i|≥|m+n-i-j|,PR′(|m+n-i-j|,|m-i|)iif|m-i|<|m+n-i-j|.An example of mapping movement to Region III is shown in Figure5. The left part of the figure is the Absolute Geographical Location. An MS moves from A(-1,2) to A(1,-2). The right part of figure is the equivalent Relative Moving Distance. Considering the starting point A(1,-2) as the center of the map, the destination A(-1,2) is in Region III. Applying Theorem 3 and setting (i,j)=(-1,2) and (m,n)=(1,-2), we can obtain PA(-1,2)→A(1,-2)i=PR'(2,2)i.Figure 5
Mapping example.


### 2.5. Calculation of User Movement Probability

The user movement is modelled by the random walk mobility model. As described previously, the computation of MS movement could be simplified by the transformation and mapping to the Simplified Moving Distance ModelR′(u,k). The mobile network model has nr tiers of cells. The value of nr must be large enough so that the probability of users moving outside is small. Depending on the requirements of modelling various mobility protocols, the value of nr should be selected accordingly.To further simplify the notation, we map each cellR′(u,k) in Simplified Moving Distance Model to a new state Sx, as shown in Figure 6. The states are relabelled from inner cells toward outer cells. For example, the origin R′(0,0) is denoted as S1. Likewise, the R′(1,0) is denoted as S2, and so forth. As we observed, the relabeling based on geometrical symmetry could be used to simplify the following mobility model formulation. A discrete-time Markov Chain model, as shown in Figure 7, is created to compute the MS movement probability. We denote the probability that an MS stays in the same cell in the next time slot as p. The probability that an MS moves to a neighboring cell in the next time slot is thus 1-p, which is denoted as q. In the random walk model, the MS has probability p to stay in the same cell and q/6 to move to another adjacent cell (notice that there are 6 neighboring cells). By observation of the geometric properties of the hexagonal topology, the random walk mobility could be formulated as the Markov Chain shown in Figure 6.Figure 6
Relabelling the Markov Chain statesSx.Figure 7
Markov Chain model.We define the matrixOi to represent the probability that an MS is in state Sx after i unit time slots. The size of an nr-tier network is denoted as S(nr). Hence, the size of Oi is 1 by S(nr):(9)Oi=(PS1iPS2iPS3iPS4i…)1×S(nr)=(PR(0,0)iPR(1,0)iPR(2,0)iPR(1,1)i…)1×S(nr).In the relative moving model, the initial location of an MS is at the origin at time 0. The initial stateO0 is described as follows:(10)O0=(10000…)1×S(nr)The probabilistic transition matrix in the Markov Chain model is denoted asTs. It is an S(nr) by S(nr) matrix. As shown in Figure 2, the number of tiers in the hexagonal topology is symmetric. We derive the value of S(nr) based on observing the geometric property of the hexagonal network topology:
(11)S(nr)={nr2+2nr+54,ifnrisodd,nr2+2nr+44,ifnriseven.By observing the mobility symmetry in Figure6, the Markov Chain state transition diagram is drawn in Figure 7. Now, we will write down the state transition probability of the Markov Chain model of Figure 7 in matrix form. An element in Ts is the probability of moving from one state to another state during one unit time in the Markov Chain model:(12)Ts=(pq000…0q6p+q3q6q30…00q6pq3q6…00q3q3p0…000q60p…0⋮⋮⋮⋮⋮⋮⋮0000001)S(nr)×S(nr),Oi+1=OiTs.Based on the state diagram shown in Figure7, the elements of Ts can be obtained. From the definition, the Markovian state probability in time slot i could be computed by iteratively multiply the current state probability with transition matrix. We can then calculate Oi with Ts iteratively:(13)O1=O0Ts=(pq000…)1×S(nr),O2=O1Ts=(p2+16q2pq+q(p+13q)16q213q20)1×S(nr),⋮Oi=O0(Ts)i.The movement probability could be computed with (13). It multiplies Ts by i times. To reduce the computational complicity, we can diagonalize the matrix Ts and derive matrix D and V.   D is the diagonal matrix of eigenvalues. V consists of the eigenvectors of Ts. We can obtain the state probability quicker by applying  (16):(14)Ts=VDV-1,(15)(Ts)i=VDiV-1,(16)Oi=O0VDiV-1.


### 2.6. Validation of the Mobility Model

Similar to the previous work [14], we validate the mathematical model by simulation. The network tier nr is 3, and two mobility scenarios p=0.8 or p=0.9 are simulated. The movement probability values after 100 time slots are shown in Table 1. Math 1 method is the result of O0Ts100 computation based on (13). Math 2 method is the results of diagonalized computation based on(16)Table 1
The simulation and the math calculation.
p=0.8R(0,0)R(1,0)R(2,0)R(1,1)outsideSimulation0.0030450.0147370.0066240.0087700.966824Math 10.0030210.0147180.0066170.0087590.966883Error10.78%0.25%0.11%0.11%0.01%Math 20.0030410.0146600.0065800.0088270.966891Error20.13%0.15%0.63%0.89%0.01%p=0.9R(0,0)R(1,0)R(2,0)R(1,1)outsideSimulation0.0211030.1018350.0457060.0604560.770900Math 10.0210090.1020530.0456360.0605030.770799Error10.45%0.21%0.15%0.08%0.01%Math 20.0211610.1016460.0453630.0610280.770801Error20.27%0.19%0.75%0.95%0.01%Table 2
Paging and Idle Mode Related Signaling Messages.
Message nameMessage descriptionDREG-REQSS De-registration messageDREG-CMDDe/Re-register CommandMOB_PAG-ADVBS broadcast paging messageRNG-REQRanging RequestRNG-RSPRanging ResponseThe initial state probability matrixO0 is 1 for the center cell and 0 for other cells:(17)O0=(10000)1×S(3).The transition matrixTs is(18)Ts=(pq000q6p+q3q6q300q6pq3q20q3q3pq300001)S(3)×S(3).The diagonal matrixD is(19)D=(1000001-0.188q000001-0.795q000001-1.270q000001-1.412q)S(3)×S(3)..The transpose of matrixOi is shown as the following:(20)OiT=(0.140*(1-0.188q)i+0.362(1-0.795q)i+0.496(1-1.270q)i0.678*(1-0.188q)i+0.275(1-0.795q)i-0.954(1-1.270q)i0.304*(1-0.188q)i-0.897(1-0.795q)i+0.592(1-1.270q)i0.408*(1-0.188q)i-0.537(1-0.795q)i+0.129(1-1.270q)i1-1.532*(1-0.188q)i+0.795(1-0.795q)i-0.263(1-1.270q)i)S(3)×1.We implement the Monte Carlo simulation in C++ to model the random walk mobility model in the hexagonal topology. Each MS has probabilityp to stay in the same cell and probability (1-p)/6 to move to any adjacent hexagonal cell. Totally 1000000 simulation runs are conducted. The uniformly random walk mobility simulation results are compared with the Markov Chain analysis results. As shown in Table 1, the differences between the mathematical models and simulation results are always less than 1%. In addition, we observe that the diagonalized method effectively reduces the computation time.


## 2.1. Absolute Geographical Location Model

The Absolute Geographical Location is used to uniquely identify the geographical location of each hexagonal cell. Unlike the random mobility model described in [14], hexagonal cells have to be uniquely labelled to distinguish MR-BS and RS. As shown in Figure 1, we apply oblique coordinates with axis x1 and x2 to label the hexagonal cells. Each cell is uniquely identified as A(x1=i,x2=j). The origin of the oblique coordinate is A(0,0), where MR-BS is usually located.Figure 1
Absolute Geographical Location Model:A(x1;x2).


## 2.2. Relative Moving Distance Model

As described previously, the Absolute Geographical LocationA(i,j) indicates the geographical cell location. Due to the symmetric property of random walk mobility model, the probability of an MS moving from cell A(i,j) to new cell A(m,n) is the same as moving from cell A(0,0) to A(m-i,n-j). Thus, in terms of moving probability between cells, we can model that the moving probability by considering the probability of an MS moves from the origin R(0,0) to R(u,k) in the Relative Moving Distance model. The MS moving probability PR(u,k) in the Relative Moving Distance model is the same as PA(i,j)→A(m,n) and PA(0,0)→A(m-i,n-j) in the Absolute Geographical Location model.The Relative Moving Distance model is consisted ofnr tiers of hexagonal cells. A 5-tier Relative Moving Distance model is shown in Figure 2. In the boundary of the wireless network, an MS may enter an outer cell and does not come back to the network. In the Markov Chain models, those outer cells will be modeled as absorbing states. The outer cells are the fifth tier of the network, which is denoted as out, as shown in Figure 2.Figure 2
Relative Moving Distance Model:R(u,k).There are three axes (v1, v2, and v3) across the origin R(0,0), and the network is divided into six regions. A hexagonal cell is labelled as R(u,k). The (u,k) tuple is labelled based on the oblique coordinate system with axes v1=(0,1) and v2=(1,0). Note that, for the cells in the same tier, the sum of u and k is the same and is equal to the tier number nr. Cells in Relative Moving Distance model are symmetric. This model provides mobility information for Absolute Geographical Location. An MS movement from (i,j) to (m,n) in the Absolute Geographical Location model will be transformed to an MS movement from (0,0) to (|m-i|,|n-j|) in the Relative Moving Distance model. Notice that the u,k in Relative Moving Distance model are all nonnegative integer; hence, absolute value operation is taken during the transformation.


## 2.3. Simplified Moving Distance Model

Since the six regions in the Relative Moving Distance model shown in Figure2 are symmetric in terms of MS moving probability, we could further simplify the moving distance model. Figure 3 illustrates the Simplified Moving Distance model, which is actually the Region I of the original Relative Moving Distance model. The cell in the Simplified Moving Distance model is denoted as R′(u,k), where u,k are non-negative integers and u≥k.Figure 3
Simplified Moving Distance Model:R′(u,k).


## 2.4. Rules of Mapping

We will describe a set of mapping rules that transforms the relative moving distance to the absolute geographical location. Because of the Markov property, the future MS movement depends only on the current location state. In the Relative Moving Distance model, a mobile station always starts fromR(0,0) as we proposed this relative mobility model for movement from the current location of the MS. The coordinate space is considered to be shifted so that the origin of the coordinate space is centered at the current MS location.We observe the geometric property of the hexagonal topology to create 3 mapping rules to simplify the model. We classify the 6 regions in Figure2 based on the geometric properties. Region I and IV will apply Mapping Rule I. In Regions I and IV, we find that (m-i)(n-j)≥0 is always true. Regions II and V will apply Mapping Rule II. In Regions II and V, we find that (m-i)(n-j)<0 and |m-i|≥|n-j| is always true. Regions II and VI will apply Mapping Rule III. In Regions II and VI, we find that (m-i)(n-j)<0 and |m-i|<|n-j| is always true. Based on the geometric property, these 3 classifications of mapping rules will be discussed in Theorems 1, 2, and 3, respectively.Moving fromA(i,j) to A(m,n) in a given time interval is transformed to moving between R(0,0) and R(u,k) in the same time interval. If a user starts at A(i,j) and locates in A(m,n) after i unit time, the probability is equal to that of moving from R(0,0) to R(u,k) after i unit time. We define PR(u,k)i as the probability that an MS moves from R(0,0) to R(u,k) after i unit time:(1)PA(i,j)→A(m,n)i=PA(0,0)→A(m-i,n-j)i=PR(u,k)i.In the Relative Moving Distance model, three axes divide the network into six regions. As the Relative Moving Distance model applies an MS-centric view that considers relative movement from the starting location, the MS movement is always starting fromR(0,0). The MS movement in the original Absolute Geographical Location from A(i,j) to A(m,n) is equivalent to the transformed MS movement from R(0,0) to R(m-i,n-j). The movement to R(m-i,n-j) could be classified based on values of m-i and n-j. The classification of the mapping rules also corresponds to the mobile movement in the six regions shown in Figure 2.All cells in Regions I and IV have the property(m-i)(n-j)≥0. The relative movement vector (m-i,n-j) can be denoted as a linear composition of two axes v1=(0,1) and v2=(1,0) with integer coefficients a and b:(2)a·v1+b·v2=a·(0,1)+b·(1,0)=(m-i,n-j).In the Simplified Moving Distance modelR′(u,k), u and k are non-negative integers. We solve the above equation and derive the non-negative solution by taking absolute values a=|n-j|, b=|m-i|. Since u≥k in the Simplified Moving Distance model, as shown in Figure 4, u is the larger one among a and b while the smaller one is k.Figure 4
Mapping example.For example, as shown in Figure4,  A(1,3) can be decomposed as the linear combination of v1 and v2. Notice that the moving probability from A(0,0) to A(1,3) is the same as the moving probability from R′(0,0) to R′(3,1):(3)(1,3)=a·v1+b·v2=a·(0,1)+b·(1,0)⇒a=3,b=1.From observation, the Mapping Rule I maps the absolute geographical location to the relative moving distance model in Regions I and IV, as shown in Figure2. Notice that the relative moving values (m-i) and (n-j) are both positive values (in Region I) or both negative values (in Region IV).Theorem 1 (Mapping Rule I).
While(m-i)(n-j)≥0,(4)PA(i,j)→A(m,n)i={PR′(|m-i|,|n-j|)i,if|m-i|≥|n-j|,PR′(|n-j|,|m-i|)i,if|m-i|<|n-j|.If an MS moves to cells in Region II or V in Figure2, the following two properties hold: (m-i)(n-j)<0 and |m-i|≥|n-j|. The relative movement vector (m-i,n-j) can be denoted as a linear combination of v2=(1,0) and v3=(1,-1). We can get a=|m+n-i-j|, b=|n-j| by solving the equation:(5)a·v2+b·v3=a·(1,0)+b·(1,-1)=(m-i,n-j).Theorem 2 (Mapping Rule II).
While(m-i)(n-j)<0 and |m-i|≥|n-j|,(6)PA(i,j)→A(m,n)i={PR′(|n-j|,|m+n-i-j|)iif|n-j|≥|m+n-i-j|,PR′(|m+n-i-j|,|n-j|)iif|n-j|<|m+n-i-j|.If an MS moves to Region III or VI, the following two properties hold:(m-i)(n-j)<0 and |m-i|<|n-j|. The relative movement vector (m-i,n-j) can be denoted as a linear combination of -v1=(0,-1), and v3=(1,-1).  We can get a=|m-i|, and b=|m+n-i-j| by solving the equation:(7)a·v3+b·(-v1)=a·(1,-1)+b·(0,-1)=(m-i,n-j).Theorem 3 (Mapping Rule III).
While(m-i)(n-j)<0 and |m-i|<|n-j|,(8)PA(i,j)→A(m,n)i={PR′(|m-i|,|m+n-i-j|)iif|m-i|≥|m+n-i-j|,PR′(|m+n-i-j|,|m-i|)iif|m-i|<|m+n-i-j|.An example of mapping movement to Region III is shown in Figure5. The left part of the figure is the Absolute Geographical Location. An MS moves from A(-1,2) to A(1,-2). The right part of figure is the equivalent Relative Moving Distance. Considering the starting point A(1,-2) as the center of the map, the destination A(-1,2) is in Region III. Applying Theorem 3 and setting (i,j)=(-1,2) and (m,n)=(1,-2), we can obtain PA(-1,2)→A(1,-2)i=PR'(2,2)i.Figure 5
Mapping example.


## 2.5. Calculation of User Movement Probability

The user movement is modelled by the random walk mobility model. As described previously, the computation of MS movement could be simplified by the transformation and mapping to the Simplified Moving Distance ModelR′(u,k). The mobile network model has nr tiers of cells. The value of nr must be large enough so that the probability of users moving outside is small. Depending on the requirements of modelling various mobility protocols, the value of nr should be selected accordingly.To further simplify the notation, we map each cellR′(u,k) in Simplified Moving Distance Model to a new state Sx, as shown in Figure 6. The states are relabelled from inner cells toward outer cells. For example, the origin R′(0,0) is denoted as S1. Likewise, the R′(1,0) is denoted as S2, and so forth. As we observed, the relabeling based on geometrical symmetry could be used to simplify the following mobility model formulation. A discrete-time Markov Chain model, as shown in Figure 7, is created to compute the MS movement probability. We denote the probability that an MS stays in the same cell in the next time slot as p. The probability that an MS moves to a neighboring cell in the next time slot is thus 1-p, which is denoted as q. In the random walk model, the MS has probability p to stay in the same cell and q/6 to move to another adjacent cell (notice that there are 6 neighboring cells). By observation of the geometric properties of the hexagonal topology, the random walk mobility could be formulated as the Markov Chain shown in Figure 6.Figure 6
Relabelling the Markov Chain statesSx.Figure 7
Markov Chain model.We define the matrixOi to represent the probability that an MS is in state Sx after i unit time slots. The size of an nr-tier network is denoted as S(nr). Hence, the size of Oi is 1 by S(nr):(9)Oi=(PS1iPS2iPS3iPS4i…)1×S(nr)=(PR(0,0)iPR(1,0)iPR(2,0)iPR(1,1)i…)1×S(nr).In the relative moving model, the initial location of an MS is at the origin at time 0. The initial stateO0 is described as follows:(10)O0=(10000…)1×S(nr)The probabilistic transition matrix in the Markov Chain model is denoted asTs. It is an S(nr) by S(nr) matrix. As shown in Figure 2, the number of tiers in the hexagonal topology is symmetric. We derive the value of S(nr) based on observing the geometric property of the hexagonal network topology:
(11)S(nr)={nr2+2nr+54,ifnrisodd,nr2+2nr+44,ifnriseven.By observing the mobility symmetry in Figure6, the Markov Chain state transition diagram is drawn in Figure 7. Now, we will write down the state transition probability of the Markov Chain model of Figure 7 in matrix form. An element in Ts is the probability of moving from one state to another state during one unit time in the Markov Chain model:(12)Ts=(pq000…0q6p+q3q6q30…00q6pq3q6…00q3q3p0…000q60p…0⋮⋮⋮⋮⋮⋮⋮0000001)S(nr)×S(nr),Oi+1=OiTs.Based on the state diagram shown in Figure7, the elements of Ts can be obtained. From the definition, the Markovian state probability in time slot i could be computed by iteratively multiply the current state probability with transition matrix. We can then calculate Oi with Ts iteratively:(13)O1=O0Ts=(pq000…)1×S(nr),O2=O1Ts=(p2+16q2pq+q(p+13q)16q213q20)1×S(nr),⋮Oi=O0(Ts)i.The movement probability could be computed with (13). It multiplies Ts by i times. To reduce the computational complicity, we can diagonalize the matrix Ts and derive matrix D and V.   D is the diagonal matrix of eigenvalues. V consists of the eigenvectors of Ts. We can obtain the state probability quicker by applying  (16):(14)Ts=VDV-1,(15)(Ts)i=VDiV-1,(16)Oi=O0VDiV-1.


## 2.6. Validation of the Mobility Model

Similar to the previous work [14], we validate the mathematical model by simulation. The network tier nr is 3, and two mobility scenarios p=0.8 or p=0.9 are simulated. The movement probability values after 100 time slots are shown in Table 1. Math 1 method is the result of O0Ts100 computation based on (13). Math 2 method is the results of diagonalized computation based on(16)Table 1
The simulation and the math calculation.
p=0.8R(0,0)R(1,0)R(2,0)R(1,1)outsideSimulation0.0030450.0147370.0066240.0087700.966824Math 10.0030210.0147180.0066170.0087590.966883Error10.78%0.25%0.11%0.11%0.01%Math 20.0030410.0146600.0065800.0088270.966891Error20.13%0.15%0.63%0.89%0.01%p=0.9R(0,0)R(1,0)R(2,0)R(1,1)outsideSimulation0.0211030.1018350.0457060.0604560.770900Math 10.0210090.1020530.0456360.0605030.770799Error10.45%0.21%0.15%0.08%0.01%Math 20.0211610.1016460.0453630.0610280.770801Error20.27%0.19%0.75%0.95%0.01%Table 2
Paging and Idle Mode Related Signaling Messages.
Message nameMessage descriptionDREG-REQSS De-registration messageDREG-CMDDe/Re-register CommandMOB_PAG-ADVBS broadcast paging messageRNG-REQRanging RequestRNG-RSPRanging ResponseThe initial state probability matrixO0 is 1 for the center cell and 0 for other cells:(17)O0=(10000)1×S(3).The transition matrixTs is(18)Ts=(pq000q6p+q3q6q300q6pq3q20q3q3pq300001)S(3)×S(3).The diagonal matrixD is(19)D=(1000001-0.188q000001-0.795q000001-1.270q000001-1.412q)S(3)×S(3)..The transpose of matrixOi is shown as the following:(20)OiT=(0.140*(1-0.188q)i+0.362(1-0.795q)i+0.496(1-1.270q)i0.678*(1-0.188q)i+0.275(1-0.795q)i-0.954(1-1.270q)i0.304*(1-0.188q)i-0.897(1-0.795q)i+0.592(1-1.270q)i0.408*(1-0.188q)i-0.537(1-0.795q)i+0.129(1-1.270q)i1-1.532*(1-0.188q)i+0.795(1-0.795q)i-0.263(1-1.270q)i)S(3)×1.We implement the Monte Carlo simulation in C++ to model the random walk mobility model in the hexagonal topology. Each MS has probabilityp to stay in the same cell and probability (1-p)/6 to move to any adjacent hexagonal cell. Totally 1000000 simulation runs are conducted. The uniformly random walk mobility simulation results are compared with the Markov Chain analysis results. As shown in Table 1, the differences between the mathematical models and simulation results are always less than 1%. In addition, we observe that the diagonalized method effectively reduces the computation time.


## 3. IEEE 802.16j Multihop Paging

### 3.1. IEEE 802.16j Idle Mode

Idle mode operation reduces control signaling cost and MS energy consumption. An MS in idle mode periodically listens to the downlink broadcasting paging messages without registering to a specific BS. RSs relay all paging messages between MS and MR-BS. In this paper, we consider nontransparent mode operation in 802.16j system. Idle mode and paging operations are illustrated in Figure8.Figure 8
Active mode and idle mode operation.


#### 3.1.1. Entering Idle Mode

Before entering idle mode, an MS sends Deregistration message (DREG-REQ) to the MR-BS. Then the MR-BS replies De/Reregister Command message (DREG-CMD) to MS. These two signaling messages are used to synchronize the paging listening time. For an MS serving by the relay stations, the access RS will relay all deregistration messages and paging messages between the MR-BS and the MS. Notice that the control signaling cost is multiplied by the number of relay hops in this scenario.


#### 3.1.2. Idle Mode Operation

As shown in Figure9, there are two types of time intervals in idle mode operation: MS Paging Unavailable Interval and MS Paging Listening Interval. During MS Paging Unavailable Interval, an MS turns down radio interface to save power. In MS Paging Listening Interval, an MS listens to the downlink broadcast of paging advertisement messages (MOB_PAG-ADV). The listening interval has a period of PAGING_CYCLE. The PAGING_OFFSET parameter is used to separate MSs in different paging groups. An MS is synchronized to the periodic listening intervals based on the PAGING_CYCLE and PAGING_OFFSET given in a MOB_PAG-ADV message.Figure 9
Signaling flow and signaling costNU1, NP1.


#### 3.1.3. Termination of Idle Mode

At the end of MS listening interval, an MS must decide whether to leave idle mode or not. If an MS would like to transmit data, it must leave idle mode and enter active mode for normal operation. When an MS decides to terminate the idle mode, it will start the network reentry process by first sending Ranging Request (RNG-REQ) message to MR-BS. Then MR-BS will reply with Ranging Response (RNG-RSP) message to the MS. Then the MS can send the location update message and start the normal active mode operation. Relay stations will forward signaling messages, such as RNG-REQ and RNG-RSP, between MS and MR-BS when needed.The paging operation is initiated when the system wants to find an MS. For example, a new data packet is arrived and is to be delivered to the MS. The network will check the paging information database that records the associated paging group of the to-be-paged MS. All MR-BS and access relay stations in the paging group will send broadcast paging messageMOB_PAG-ADV with the MS's MAC address. Once the MS receives the broadcast paging message, it will terminate the idle mode and go back to normal mode. The MOB_PAG-ADV broadcasting is initiated from the MR-BS and is forwarded through relay stations.


### 3.2. Paging Methods

In the network topology, MR-BS and RS are assumed to be located at the center of hexagonal cells. A cell is consisted of 1 MR-BS and 6 RSs as shown in Figure10. Packets are either directly transmitted from MR-BS to MS, if an MS is located in the central cell, or forwarded through two-hop-relay transmission. When the network is going to page an MS, the paging message is forward from the MR-BS to the six RSs. Then the MR-BS and the 6 RSs will broadcast paging messages to MS (i.e., 7 transmissions are needed). Thus, the total signaling cost in one paging event isFigure 10
IEEE 802.16j multihop cellular structure: base stations and relay stations.(21)NP1=NP1(Relay)+NP1(Broadcast)=6+7=13.Our paging scheme includes both paging area-based update mechanism and timer-based update mechanism. Several cells are grouped into one paging area. An MS roams between different paging areas and sends an update when it moves across the border. If a message arrives, the network only broadcasts the messages in one paging area to find the user. For example, the paging areas can be allocated as shown in Figure11. There are totally 14 paging areas shown in this figure. In this example, one cell includes one base station and six relay stations, as shown in Figure 10. Notice that a hexagon that labelled with number has a base station, and other neighboring hexagons without number have relay stations, as shown in Figure 11.Figure 11
Example of paging area topology with 13 paging areaaj,j=1,…,13. Base stations are located in hexagons with labelled numbers (Paging Area ID). Relay stations are located in hexagons without number.Before an MS enters idle mode, the serving base station exchanges DREG-REQ and DREG-CMD messages with it. The last serving cell will be denoted as paging areas 1 as shown in Figure11. In idle mode, an MS still needs to listen to paging-related information periodically. During every MS Listening interval, the MS listens to broadcast messages, which contains paging-related information. From this information, if the MS detects that it moves to a different paging area, it must notify the network about the paging area change. We call this update the Paging Area Notification (PA Notification). Hence, when a data message arrives, the network knows the right paging area to find the idle mode MS. When an MS moves to a new paging area, the MS will always first send update to the RS and then forwarded the signaling message to BS. In PA Notification, there are totally NU1 signaling cost, which is defined by the number of signaling message transmitted weighed by the number of hops to be forwarded. In the 2-hop multihop cellular structure, as shown in Figure 10, the PA Notification signaling cost is(22)NU1=messages×relay=4×2=8.In the proposed paging scheme, the paging area topology is MS-centric. When an MS updates the exact cell location to the network, the system recomputes the paging area, and the current cell becomes the centralized cell in the paging area, which is labelled with1 as shown in Figure 11. Paging areas will only be reset in two circumstances: (1) data message arrival (and system create paging message to locate the MS) or (2) timer-based update (timer expires after t).The first case occurs after the data messages arrive, and the network starts the broadcast paging procedure. All cells in the paging area, where the MS located, will send broadcast paging messages. The second case is timer-based location update. If no message arrives aftert time slots, the MS must update its location to avoid losing track of its location. After timer expires, the MS goes into active mode, updates its location, and resets the paging area (set the current cell as paging area 1) before it enters idle mode again.


## 3.1. IEEE 802.16j Idle Mode

Idle mode operation reduces control signaling cost and MS energy consumption. An MS in idle mode periodically listens to the downlink broadcasting paging messages without registering to a specific BS. RSs relay all paging messages between MS and MR-BS. In this paper, we consider nontransparent mode operation in 802.16j system. Idle mode and paging operations are illustrated in Figure8.Figure 8
Active mode and idle mode operation.


### 3.1.1. Entering Idle Mode

Before entering idle mode, an MS sends Deregistration message (DREG-REQ) to the MR-BS. Then the MR-BS replies De/Reregister Command message (DREG-CMD) to MS. These two signaling messages are used to synchronize the paging listening time. For an MS serving by the relay stations, the access RS will relay all deregistration messages and paging messages between the MR-BS and the MS. Notice that the control signaling cost is multiplied by the number of relay hops in this scenario.


### 3.1.2. Idle Mode Operation

As shown in Figure9, there are two types of time intervals in idle mode operation: MS Paging Unavailable Interval and MS Paging Listening Interval. During MS Paging Unavailable Interval, an MS turns down radio interface to save power. In MS Paging Listening Interval, an MS listens to the downlink broadcast of paging advertisement messages (MOB_PAG-ADV). The listening interval has a period of PAGING_CYCLE. The PAGING_OFFSET parameter is used to separate MSs in different paging groups. An MS is synchronized to the periodic listening intervals based on the PAGING_CYCLE and PAGING_OFFSET given in a MOB_PAG-ADV message.Figure 9
Signaling flow and signaling costNU1, NP1.


### 3.1.3. Termination of Idle Mode

At the end of MS listening interval, an MS must decide whether to leave idle mode or not. If an MS would like to transmit data, it must leave idle mode and enter active mode for normal operation. When an MS decides to terminate the idle mode, it will start the network reentry process by first sending Ranging Request (RNG-REQ) message to MR-BS. Then MR-BS will reply with Ranging Response (RNG-RSP) message to the MS. Then the MS can send the location update message and start the normal active mode operation. Relay stations will forward signaling messages, such as RNG-REQ and RNG-RSP, between MS and MR-BS when needed.The paging operation is initiated when the system wants to find an MS. For example, a new data packet is arrived and is to be delivered to the MS. The network will check the paging information database that records the associated paging group of the to-be-paged MS. All MR-BS and access relay stations in the paging group will send broadcast paging messageMOB_PAG-ADV with the MS's MAC address. Once the MS receives the broadcast paging message, it will terminate the idle mode and go back to normal mode. The MOB_PAG-ADV broadcasting is initiated from the MR-BS and is forwarded through relay stations.


## 3.1.1. Entering Idle Mode

Before entering idle mode, an MS sends Deregistration message (DREG-REQ) to the MR-BS. Then the MR-BS replies De/Reregister Command message (DREG-CMD) to MS. These two signaling messages are used to synchronize the paging listening time. For an MS serving by the relay stations, the access RS will relay all deregistration messages and paging messages between the MR-BS and the MS. Notice that the control signaling cost is multiplied by the number of relay hops in this scenario.


## 3.1.2. Idle Mode Operation

As shown in Figure9, there are two types of time intervals in idle mode operation: MS Paging Unavailable Interval and MS Paging Listening Interval. During MS Paging Unavailable Interval, an MS turns down radio interface to save power. In MS Paging Listening Interval, an MS listens to the downlink broadcast of paging advertisement messages (MOB_PAG-ADV). The listening interval has a period of PAGING_CYCLE. The PAGING_OFFSET parameter is used to separate MSs in different paging groups. An MS is synchronized to the periodic listening intervals based on the PAGING_CYCLE and PAGING_OFFSET given in a MOB_PAG-ADV message.Figure 9
Signaling flow and signaling costNU1, NP1.


## 3.1.3. Termination of Idle Mode

At the end of MS listening interval, an MS must decide whether to leave idle mode or not. If an MS would like to transmit data, it must leave idle mode and enter active mode for normal operation. When an MS decides to terminate the idle mode, it will start the network reentry process by first sending Ranging Request (RNG-REQ) message to MR-BS. Then MR-BS will reply with Ranging Response (RNG-RSP) message to the MS. Then the MS can send the location update message and start the normal active mode operation. Relay stations will forward signaling messages, such as RNG-REQ and RNG-RSP, between MS and MR-BS when needed.The paging operation is initiated when the system wants to find an MS. For example, a new data packet is arrived and is to be delivered to the MS. The network will check the paging information database that records the associated paging group of the to-be-paged MS. All MR-BS and access relay stations in the paging group will send broadcast paging messageMOB_PAG-ADV with the MS's MAC address. Once the MS receives the broadcast paging message, it will terminate the idle mode and go back to normal mode. The MOB_PAG-ADV broadcasting is initiated from the MR-BS and is forwarded through relay stations.


## 3.2. Paging Methods

In the network topology, MR-BS and RS are assumed to be located at the center of hexagonal cells. A cell is consisted of 1 MR-BS and 6 RSs as shown in Figure10. Packets are either directly transmitted from MR-BS to MS, if an MS is located in the central cell, or forwarded through two-hop-relay transmission. When the network is going to page an MS, the paging message is forward from the MR-BS to the six RSs. Then the MR-BS and the 6 RSs will broadcast paging messages to MS (i.e., 7 transmissions are needed). Thus, the total signaling cost in one paging event isFigure 10
IEEE 802.16j multihop cellular structure: base stations and relay stations.(21)NP1=NP1(Relay)+NP1(Broadcast)=6+7=13.Our paging scheme includes both paging area-based update mechanism and timer-based update mechanism. Several cells are grouped into one paging area. An MS roams between different paging areas and sends an update when it moves across the border. If a message arrives, the network only broadcasts the messages in one paging area to find the user. For example, the paging areas can be allocated as shown in Figure11. There are totally 14 paging areas shown in this figure. In this example, one cell includes one base station and six relay stations, as shown in Figure 10. Notice that a hexagon that labelled with number has a base station, and other neighboring hexagons without number have relay stations, as shown in Figure 11.Figure 11
Example of paging area topology with 13 paging areaaj,j=1,…,13. Base stations are located in hexagons with labelled numbers (Paging Area ID). Relay stations are located in hexagons without number.Before an MS enters idle mode, the serving base station exchanges DREG-REQ and DREG-CMD messages with it. The last serving cell will be denoted as paging areas 1 as shown in Figure11. In idle mode, an MS still needs to listen to paging-related information periodically. During every MS Listening interval, the MS listens to broadcast messages, which contains paging-related information. From this information, if the MS detects that it moves to a different paging area, it must notify the network about the paging area change. We call this update the Paging Area Notification (PA Notification). Hence, when a data message arrives, the network knows the right paging area to find the idle mode MS. When an MS moves to a new paging area, the MS will always first send update to the RS and then forwarded the signaling message to BS. In PA Notification, there are totally NU1 signaling cost, which is defined by the number of signaling message transmitted weighed by the number of hops to be forwarded. In the 2-hop multihop cellular structure, as shown in Figure 10, the PA Notification signaling cost is(22)NU1=messages×relay=4×2=8.In the proposed paging scheme, the paging area topology is MS-centric. When an MS updates the exact cell location to the network, the system recomputes the paging area, and the current cell becomes the centralized cell in the paging area, which is labelled with1 as shown in Figure 11. Paging areas will only be reset in two circumstances: (1) data message arrival (and system create paging message to locate the MS) or (2) timer-based update (timer expires after t).The first case occurs after the data messages arrive, and the network starts the broadcast paging procedure. All cells in the paging area, where the MS located, will send broadcast paging messages. The second case is timer-based location update. If no message arrives aftert time slots, the MS must update its location to avoid losing track of its location. After timer expires, the MS goes into active mode, updates its location, and resets the paging area (set the current cell as paging area 1) before it enters idle mode again.


## 4. Paging Performance Analysis

Signaling cost in wireless network paging design is critical. In this section, we will investigate the signaling cost in the proposed paging scheme. The 802.16j paging cycle strucutre is shown in Figure12. MS Paging unavailable interval and MS Paging Listening Interval appear alternatively. In MS Paging unavailable interval, the MS enters idle mode and does not receive packets from the network. In MS Paging Listening Interval, the MS listens to the paging channel to find whether paging messages are sent. The process could be modeled as discrete events including MS movement and paging arrival occur at the MS Paging Listening Interval. For performance evaluation, we compute the probabilities of the MS movement events and paging arrival events accordingly.Figure 12
IEEE 802.16j paging cycle.


### 4.1. Interrupted Versus Uninterrupted Idle Periods

We denote the overall time duration asT. During this time, we could further categorize the time period into two types: interrupted idle period and uninterrupted idle period.


#### 4.1.1. Interrupted Idle Period

A paging message arrives and terminates an interrupted idle period. We calculate theNi, the number of interrupted Idle periods during the total duration T, and Nu, the number of uninterrupted idle periods during T. The paging message arrival follows Poisson random process with rate λ. Hence, the expected number of paging message arrival during time T is λT. The number of interrupted idle periods is(23)Ni≅λT.


#### 4.1.2. Uninterrupted Idle Period

No paging messages arrive during an uninterrupted idle period. An uninterrupted idle period is terminated due to the timer-based forcing update. The mobile-centric location area is reset after timer-based paging area update periodt. One additional cycle for active mode operation for the location area reset is needed. Thus, the length of an uninterrupted idle period is t+1 cycles. We denote the time duration from entering idle mode to the paging arrival time as tp. The expected value of tp is denoted as tp¯.During total durationT, the expected interrupted time periods is λTtp¯  cycles. So the number of uninterrupted idle periods is the remaining uninterrupted time during T divided by the duration of an uninterrupted idle period. The expected number of uninterrupted idle periods is(24)Nu=E[T-λT(tp¯+1)]E[t+1].In an interrupted idle period, the signaling messages include paging and location updating. In an uninterrupted idle period, the signaling messages only include location updating at the end of the period.


### 4.2. Broadcast Paging

Broadcast paging event only occurs during an interrupted period. If the call arrives betweeni-1 and i cycle, the system broadcasts a paging message to the paging area where the MS locates. We can derive the probability of the MS in a paging area from the probability computation in Section 2.The total paging signaling cost of one MS at cyclei is “the probability of the MS in paging area aj” multiplied by “the signaling cost in paging area aj.” We have calculated the paging signaling cost in one multihop cell, NP1, in (21). Thus, the total paging signaling cost is (the probability of the MS in paging area aj) ×NP1× (the number of multihop cells in paging area aj).Based on the mobility model described in Section2, we can readily compute the probability of an MS in an paging area after time tp. For example, the paging area a1 shown in the center of Figure 11 has 1 multihop relay cell, which includes 1 BS hexagonal cell marked with 1 and 6 RS hexagonal cells surrounding the BS. The probability of an MS is located with the paging area a1 after time tp is Otp[1,1,0,0,…]S(n)×1′. The mobility matrix that corresponds to paging area a1[1,1,0,0,…]S(n)×1′ is denoted as Sp1. Similarly, Spj is the matrix corresponding to paging area aj. Notice that Spj only depends on the paging area topology and is independent of tp. Considering the whole wireless networks, we have Sp:(25)Sp=∑∀iSpi.According to the random walk mobility model, the MS location state probability isOtp. For each paging event, the signaling cost is NP1OtpSp. The cost of paging signaling during total time duration T is(26)Paging_signaling=NiNP1OtpSp.Similar to [9], we will compute tp. The Poisson arrival is(27)P(np,Δt)=e-λΔt(λΔt)npnp!.The number of arrived paging message is denoted asnp. If np=0,P(np=0,Δt)=e-λΔt, it implies that no message arrives. If np≠0,P(np≠0,Δt)=1-e-λΔt, it implies that at least one message arrives. The probability that paging message arrival time tp falls between i-1 and i, as shown in Figure 12, is(28)Pti=∏j=0i-2P(np=0,j≤tp<j+1)P(np≠0,i-1≤tp<i)=e-λ(i-1)(1-e-λ).Then, wheni-1≤ti<i, we calculate ti¯, the expected value of a message arrival time that falls between i-1 and i [16]:(29)ti¯=∫i-1iλxe-λxdx∫i-1iλe-λxdx=i+-eλeλ-1+1λ.The average valuetp¯ is(30)tp¯=∑i=1t[Ptiti¯]=(1-e-λ)∑i=1tie-λ(i-1)+(1-e-λt)(-eλeλ-1+1λ)=1λ(1-e-λt)-te-λt.Thus, from (26), the overall paging signaling cost is(31)Paging_signaling=NiNP1∑i=1tOiSpPti∑i=1tPti.


### 4.3. Paging Area Notification (PA Notification)

If the MS moves across the border between two different paging areas, the MS must notify the network about the PA change. The MS update signaling cost of each PA Notification event is denoted asNU1. The corresponding PA notification probability between cycle i and i+1 is the summation of the probability across the paging area border, according to the previously described random walk mobility model and the paging area topology. There are totally NU1=4×2=8  signaling message transmissions when an MS updates.Similar to theSpi formulation, the mobility matrix for PA notification event, in which an MS moves away from paging area ai, is denoted as Sui. Similarly, when we consider the whole network, we have Su as follows:(32)Su=∑∀iSui.


#### 4.3.1. Uninterrupted Idle Period

The update signaling during timei to i+1 is NU1OiSu. In an uninterrupted idle period, there are totally t MS Paging listening intervals, since an uninterrupted idle period is terminated by the timer-based update after time t. In each MS Paging listening interval, the MS checks if PA changes. The expected PA Notification signaling cost in one uninterrupted idle period is:(33)NU1(∑i=0t-1OiSu+12).
During the total duration T, the number of uninterrupted idle periods Nu is(34)Nu=∑i=1tPti(T-λT(ti¯+1))∑i=1tPti(t+1)=∑i=1tPtiT-λT(tp¯+Pti)∑i=1tPti(t+1).The total update singling cost in all uninterrupted idle periods will be(35)Update_signaling_un=NuNU1(∑i=0t-1OiSu+12).


#### 4.3.2. Interrupted Idle Period

In an interrupted idle period, there are totallytp-1 cycles, since an interrupted idle period is terminated by message arrival at time tp. The expected PA Notification signaling cost in an interrupted idle period is(36)NU1(∑i=0t-1OiSuPti∑i=0t-1Pti+12).
During the total time duration T, the number of interrupted idle period is Ni. The total update singling cost in all interrupted idle periods will be(37)Update_signaling_in=NiNU1(∑i=0t-1(OiSu+(1/2))Pti∑i=0t-1Pti+12).


### 4.4. Timer-Based Paging Area Update

Timer-based paging area update (Timer-Based PA Update) occurs when the update timert expires. The system recomputes the MS-centric paging area, as shown in Figure 11. In addition, the same MS-centric paging area recomputation occurs when an MS goes into active mode, which happens after a data message arrives. During T, the expected data message arrival is λT. As the signaling message flow is the same in the timer-based PA update and the paging due to data arrival, we will lump together the signaling cost into one term in this subsection.The number of total PA update, which includes both Timer-Based PA Update and PA update due to data arrival, is(∑i=1tPtiT-λT(tp¯+Pti))/∑i=1tPti(t+1). For each PA update, the signaling cost is denoted as NA:(38)NA=messages×relay=4×2=8.
Notice that the NA timer-based PA update signaling messages are the same as the PA notification signaling messages NU1, since similar signaling message flow is applied.So the total timer-based PA update signaling cost is(39)Timer_signaling=λTNA+∑i=1tPtiT-λT(tp¯+Pti)∑i=1tPti(t+1)NA.From (23), (31), (34), (35), (37), and (39) the total signaling cost is(40)S_total=λTNP1∑i=1tOiSpPti∑i=1tPti+λTNU1(∑i=0t-1OiSuPti∑i=0t-1Pti+12)+∑i=1tPtiT-λT(tp¯+Pti)∑i=1tPti(t+1)NU1(∑i=0t-1OiSu+12)+λTNA+∑i=1tPtiT-λT(tp¯+Pti)∑i=1tPti(t+1)NA.


## 4.1. Interrupted Versus Uninterrupted Idle Periods

We denote the overall time duration asT. During this time, we could further categorize the time period into two types: interrupted idle period and uninterrupted idle period.


### 4.1.1. Interrupted Idle Period

A paging message arrives and terminates an interrupted idle period. We calculate theNi, the number of interrupted Idle periods during the total duration T, and Nu, the number of uninterrupted idle periods during T. The paging message arrival follows Poisson random process with rate λ. Hence, the expected number of paging message arrival during time T is λT. The number of interrupted idle periods is(23)Ni≅λT.


### 4.1.2. Uninterrupted Idle Period

No paging messages arrive during an uninterrupted idle period. An uninterrupted idle period is terminated due to the timer-based forcing update. The mobile-centric location area is reset after timer-based paging area update periodt. One additional cycle for active mode operation for the location area reset is needed. Thus, the length of an uninterrupted idle period is t+1 cycles. We denote the time duration from entering idle mode to the paging arrival time as tp. The expected value of tp is denoted as tp¯.During total durationT, the expected interrupted time periods is λTtp¯  cycles. So the number of uninterrupted idle periods is the remaining uninterrupted time during T divided by the duration of an uninterrupted idle period. The expected number of uninterrupted idle periods is(24)Nu=E[T-λT(tp¯+1)]E[t+1].In an interrupted idle period, the signaling messages include paging and location updating. In an uninterrupted idle period, the signaling messages only include location updating at the end of the period.


## 4.1.1. Interrupted Idle Period

A paging message arrives and terminates an interrupted idle period. We calculate theNi, the number of interrupted Idle periods during the total duration T, and Nu, the number of uninterrupted idle periods during T. The paging message arrival follows Poisson random process with rate λ. Hence, the expected number of paging message arrival during time T is λT. The number of interrupted idle periods is(23)Ni≅λT.


## 4.1.2. Uninterrupted Idle Period

No paging messages arrive during an uninterrupted idle period. An uninterrupted idle period is terminated due to the timer-based forcing update. The mobile-centric location area is reset after timer-based paging area update periodt. One additional cycle for active mode operation for the location area reset is needed. Thus, the length of an uninterrupted idle period is t+1 cycles. We denote the time duration from entering idle mode to the paging arrival time as tp. The expected value of tp is denoted as tp¯.During total durationT, the expected interrupted time periods is λTtp¯  cycles. So the number of uninterrupted idle periods is the remaining uninterrupted time during T divided by the duration of an uninterrupted idle period. The expected number of uninterrupted idle periods is(24)Nu=E[T-λT(tp¯+1)]E[t+1].In an interrupted idle period, the signaling messages include paging and location updating. In an uninterrupted idle period, the signaling messages only include location updating at the end of the period.


## 4.2. Broadcast Paging

Broadcast paging event only occurs during an interrupted period. If the call arrives betweeni-1 and i cycle, the system broadcasts a paging message to the paging area where the MS locates. We can derive the probability of the MS in a paging area from the probability computation in Section 2.The total paging signaling cost of one MS at cyclei is “the probability of the MS in paging area aj” multiplied by “the signaling cost in paging area aj.” We have calculated the paging signaling cost in one multihop cell, NP1, in (21). Thus, the total paging signaling cost is (the probability of the MS in paging area aj) ×NP1× (the number of multihop cells in paging area aj).Based on the mobility model described in Section2, we can readily compute the probability of an MS in an paging area after time tp. For example, the paging area a1 shown in the center of Figure 11 has 1 multihop relay cell, which includes 1 BS hexagonal cell marked with 1 and 6 RS hexagonal cells surrounding the BS. The probability of an MS is located with the paging area a1 after time tp is Otp[1,1,0,0,…]S(n)×1′. The mobility matrix that corresponds to paging area a1[1,1,0,0,…]S(n)×1′ is denoted as Sp1. Similarly, Spj is the matrix corresponding to paging area aj. Notice that Spj only depends on the paging area topology and is independent of tp. Considering the whole wireless networks, we have Sp:(25)Sp=∑∀iSpi.According to the random walk mobility model, the MS location state probability isOtp. For each paging event, the signaling cost is NP1OtpSp. The cost of paging signaling during total time duration T is(26)Paging_signaling=NiNP1OtpSp.Similar to [9], we will compute tp. The Poisson arrival is(27)P(np,Δt)=e-λΔt(λΔt)npnp!.The number of arrived paging message is denoted asnp. If np=0,P(np=0,Δt)=e-λΔt, it implies that no message arrives. If np≠0,P(np≠0,Δt)=1-e-λΔt, it implies that at least one message arrives. The probability that paging message arrival time tp falls between i-1 and i, as shown in Figure 12, is(28)Pti=∏j=0i-2P(np=0,j≤tp<j+1)P(np≠0,i-1≤tp<i)=e-λ(i-1)(1-e-λ).Then, wheni-1≤ti<i, we calculate ti¯, the expected value of a message arrival time that falls between i-1 and i [16]:(29)ti¯=∫i-1iλxe-λxdx∫i-1iλe-λxdx=i+-eλeλ-1+1λ.The average valuetp¯ is(30)tp¯=∑i=1t[Ptiti¯]=(1-e-λ)∑i=1tie-λ(i-1)+(1-e-λt)(-eλeλ-1+1λ)=1λ(1-e-λt)-te-λt.Thus, from (26), the overall paging signaling cost is(31)Paging_signaling=NiNP1∑i=1tOiSpPti∑i=1tPti.


## 4.3. Paging Area Notification (PA Notification)

If the MS moves across the border between two different paging areas, the MS must notify the network about the PA change. The MS update signaling cost of each PA Notification event is denoted asNU1. The corresponding PA notification probability between cycle i and i+1 is the summation of the probability across the paging area border, according to the previously described random walk mobility model and the paging area topology. There are totally NU1=4×2=8  signaling message transmissions when an MS updates.Similar to theSpi formulation, the mobility matrix for PA notification event, in which an MS moves away from paging area ai, is denoted as Sui. Similarly, when we consider the whole network, we have Su as follows:(32)Su=∑∀iSui.


### 4.3.1. Uninterrupted Idle Period

The update signaling during timei to i+1 is NU1OiSu. In an uninterrupted idle period, there are totally t MS Paging listening intervals, since an uninterrupted idle period is terminated by the timer-based update after time t. In each MS Paging listening interval, the MS checks if PA changes. The expected PA Notification signaling cost in one uninterrupted idle period is:(33)NU1(∑i=0t-1OiSu+12).
During the total duration T, the number of uninterrupted idle periods Nu is(34)Nu=∑i=1tPti(T-λT(ti¯+1))∑i=1tPti(t+1)=∑i=1tPtiT-λT(tp¯+Pti)∑i=1tPti(t+1).The total update singling cost in all uninterrupted idle periods will be(35)Update_signaling_un=NuNU1(∑i=0t-1OiSu+12).


### 4.3.2. Interrupted Idle Period

In an interrupted idle period, there are totallytp-1 cycles, since an interrupted idle period is terminated by message arrival at time tp. The expected PA Notification signaling cost in an interrupted idle period is(36)NU1(∑i=0t-1OiSuPti∑i=0t-1Pti+12).
During the total time duration T, the number of interrupted idle period is Ni. The total update singling cost in all interrupted idle periods will be(37)Update_signaling_in=NiNU1(∑i=0t-1(OiSu+(1/2))Pti∑i=0t-1Pti+12).


## 4.3.1. Uninterrupted Idle Period

The update signaling during timei to i+1 is NU1OiSu. In an uninterrupted idle period, there are totally t MS Paging listening intervals, since an uninterrupted idle period is terminated by the timer-based update after time t. In each MS Paging listening interval, the MS checks if PA changes. The expected PA Notification signaling cost in one uninterrupted idle period is:(33)NU1(∑i=0t-1OiSu+12).
During the total duration T, the number of uninterrupted idle periods Nu is(34)Nu=∑i=1tPti(T-λT(ti¯+1))∑i=1tPti(t+1)=∑i=1tPtiT-λT(tp¯+Pti)∑i=1tPti(t+1).The total update singling cost in all uninterrupted idle periods will be(35)Update_signaling_un=NuNU1(∑i=0t-1OiSu+12).


## 4.3.2. Interrupted Idle Period

In an interrupted idle period, there are totallytp-1 cycles, since an interrupted idle period is terminated by message arrival at time tp. The expected PA Notification signaling cost in an interrupted idle period is(36)NU1(∑i=0t-1OiSuPti∑i=0t-1Pti+12).
During the total time duration T, the number of interrupted idle period is Ni. The total update singling cost in all interrupted idle periods will be(37)Update_signaling_in=NiNU1(∑i=0t-1(OiSu+(1/2))Pti∑i=0t-1Pti+12).


## 4.4. Timer-Based Paging Area Update

Timer-based paging area update (Timer-Based PA Update) occurs when the update timert expires. The system recomputes the MS-centric paging area, as shown in Figure 11. In addition, the same MS-centric paging area recomputation occurs when an MS goes into active mode, which happens after a data message arrives. During T, the expected data message arrival is λT. As the signaling message flow is the same in the timer-based PA update and the paging due to data arrival, we will lump together the signaling cost into one term in this subsection.The number of total PA update, which includes both Timer-Based PA Update and PA update due to data arrival, is(∑i=1tPtiT-λT(tp¯+Pti))/∑i=1tPti(t+1). For each PA update, the signaling cost is denoted as NA:(38)NA=messages×relay=4×2=8.
Notice that the NA timer-based PA update signaling messages are the same as the PA notification signaling messages NU1, since similar signaling message flow is applied.So the total timer-based PA update signaling cost is(39)Timer_signaling=λTNA+∑i=1tPtiT-λT(tp¯+Pti)∑i=1tPti(t+1)NA.From (23), (31), (34), (35), (37), and (39) the total signaling cost is(40)S_total=λTNP1∑i=1tOiSpPti∑i=1tPti+λTNU1(∑i=0t-1OiSuPti∑i=0t-1Pti+12)+∑i=1tPtiT-λT(tp¯+Pti)∑i=1tPti(t+1)NU1(∑i=0t-1OiSu+12)+λTNA+∑i=1tPtiT-λT(tp¯+Pti)∑i=1tPti(t+1)NA.


## 5. Optimized Timer-Based Location Updatet*

In the previous section, we derive the signaling cost given parametersp, λ, T, and t. In this section, we will optimize the timer-based update period t to minimize the overall signaling cost. The total time duration T, which is just an observation time period, does not affect the optimization results. We will normalize the formulation by defining S0=S_total/T. After normalization of (40), we have(41)S0=λNP1∑i=1tOiSpPti∑i=1tPti+λNU1(∑i=0t-1OiSuPti∑i=0t-1Pti+12)+∑i=1tPti-λ(tp¯+Pti)∑i=1tPti(t+1)NU1(∑i=0t-1OiSu+12)+λNA+∑i=1tPti-λ(tp¯+Pti)∑i=1tPti(t+1)NA.TheTs matrix is an S(nr) by S(nr) matrix. After diagonizing the matrix, the matrix Oi is composed of eiganvalues e1 to eS(nr) and some constant values. To simplify the S0 notation, we define Eui and Epi as follows:(42)Eui=OiSu=∑k=1S(nr)ukeki,Epi=OiSp=∑k=1S(nr)pkeki.
Notice that the parameters uk and pk are constants, for all k∈[1,S(nr)]. Then, the normalized signaling cost is(43)S0=λNP1∑i=1tEpiPti∑i=1tPti+λNU1∑i=0t-1EuiPti∑i=0t-1Pti+λNU12+∑i=1tPti-λ(tp¯+Pti)∑i=1tPti(t+1)NU1(∑i=0t-1Eui+12)+λNA+∑i=1tPti-λ(tp¯+Pti)∑i=1tPti(t+1)NA.After substituting (28) and (30) for Pti and tp and some computation, we could obtain(44)S0=λNP1∑k=1S(nr)pkek(1-eλ)(ekt-eλt)(1-eλt)(ek-eλ)+λNU1∑k=1S(nr)uk(1-eλ)(ekt-eλt)(1-eλt)(ek-eλ)+λNU12+λ(1-eλt+t)(eλt-1)(t+1)NU1(∑k=1S(nr)uk(ekt-1)ek-1+12)+λNA+λ(1-eλt+t)(eλt-1)(t+1)NA.To find the optimizedt, we take the first-order derivatives:(45)dS0dt=∑k=1S(nr){1+λt+λt2-eλt(eλt-1)2(t+1)2λ(NP1ekpk+NU1uk)×(1-eλ)(eλt-1)2(λekteλt-λeλt+𝔄)(ek-eλ)+NU1λuk(t+1)(ek-1)(eλt-1)×[(log(ek)ekt-λ(ekt-1)eλt(eλt-1)-(ekt-1)(t+1))(1-λeλt)(ekt-1)+(t-eλt+1)×(log(ek)ekt-λ(ekt-1)eλt(eλt-1)-(ekt-1)(t+1))]-(NU12+NA)λeλt1+λt+λt2-eλt(eλt-1)2(t+1)2}=0,
where 𝔄 denotesektlog(ek)-eλtektlog(ek).By solvingdS0/dt=0, we will get the optimal paging area update timer t*.


## 6. Performance Evaluation

The PA Notification signaling cost decreases ast increases because, in our paging area topology, the size of paging area near the center is smaller than the size of paging area away from the center. As expected, the timer-based PA update signaling cost decreases as t increases. As t increases, the low PA update frequency reduces the signaling cost; however, the location tracking of MS becomes coarser. The broadcast paging signaling cost depends on the data message arrival rate λ. In addition, if an MS goes to outside state of the paging area, mostly due to infrequent paging area update, the network needs to broadcast the whole network to locate the MS. Tradeoffs between frequency of paging area update and the broadcasting cost could be observed in the figures.


### 6.1. Finding Optimized Location Update Timer

In Figures13, 14, 15, and 16, we illustrate the signaling cost of the proposed IEEE 802.16j paging scheme in different mobility scenarios and paging arrival scenarios. In each figure, the three signaling cost components, PA Notification, Broadcast Paging, and Timer-Based PA Update, are shown, respectively. The optimal value of the total signaling cost S0 is also labelled.Figure 13
Signaling cost: high mobility and low message arrival rate.Figure 14
Signaling cost: high mobility and high message arrival rate.Figure 15
Signaling cost: low mobility and low message arrival rate.Figure 16
Signaling cost: low mobility and high message arrival rate.Figures13 and 14 show the performance differences between a high message arrival rate (λ) scenario and a low message arrival rate scenario. In the three signaling cost components, the broadcast paging cost changes the most. With small λ, the signaling cost grows more steeply as t increases. The reason is that the broadcast paging signaling cost becomes large when the MS location is updated infrequently. When an MS receives a message more frequently, it goes into active mode more frequently. When an MS goes into active mode and then reenters the idle mode, the paging area is updated. Consequently, the MS less likely goes to outside area.Comparing Figures13 and 15, the mobility parameter p differs. Notice that a high p indicates the low mobility scenario since p defines the probability that an MS stays in the same cell during unit time. When MS mobility is high, the optimal t* is smaller to keep the needed precision of location tracking.In Figure16, as the MS mobility is low and the data message arrival rate is high, the probability that an MS stays in the central region of the paging area is high. The probability of an MS that moves out of the paging areas is low; hence, the cases of network-wide broadcasting to find MS rarely occur. The signaling cost of Broadcast Paging component is relative flat, compared with the other three figures. Hence, the overall signaling cost is related flat when t is large.


### 6.2. Comparing to Pure Timer-Based Scheme

In addition to update the paging area topology when an MS does not update its location for timet, an MS notifies the network when an MS moves across the border of paging areas in the proposed paging scheme. On the contrary, a pure timer-based paging algorithm might only update the location of an MS only when the t timer expires. In Figure 17, we compare the proposed scheme and the pure timer-based scheme. The proposed scheme has a lower signaling cost than the pure timer-based scheme as shown in the figure.Figure 17
Comparison to timer-based scheme.


## 6.1. Finding Optimized Location Update Timer

In Figures13, 14, 15, and 16, we illustrate the signaling cost of the proposed IEEE 802.16j paging scheme in different mobility scenarios and paging arrival scenarios. In each figure, the three signaling cost components, PA Notification, Broadcast Paging, and Timer-Based PA Update, are shown, respectively. The optimal value of the total signaling cost S0 is also labelled.Figure 13
Signaling cost: high mobility and low message arrival rate.Figure 14
Signaling cost: high mobility and high message arrival rate.Figure 15
Signaling cost: low mobility and low message arrival rate.Figure 16
Signaling cost: low mobility and high message arrival rate.Figures13 and 14 show the performance differences between a high message arrival rate (λ) scenario and a low message arrival rate scenario. In the three signaling cost components, the broadcast paging cost changes the most. With small λ, the signaling cost grows more steeply as t increases. The reason is that the broadcast paging signaling cost becomes large when the MS location is updated infrequently. When an MS receives a message more frequently, it goes into active mode more frequently. When an MS goes into active mode and then reenters the idle mode, the paging area is updated. Consequently, the MS less likely goes to outside area.Comparing Figures13 and 15, the mobility parameter p differs. Notice that a high p indicates the low mobility scenario since p defines the probability that an MS stays in the same cell during unit time. When MS mobility is high, the optimal t* is smaller to keep the needed precision of location tracking.In Figure16, as the MS mobility is low and the data message arrival rate is high, the probability that an MS stays in the central region of the paging area is high. The probability of an MS that moves out of the paging areas is low; hence, the cases of network-wide broadcasting to find MS rarely occur. The signaling cost of Broadcast Paging component is relative flat, compared with the other three figures. Hence, the overall signaling cost is related flat when t is large.


## 6.2. Comparing to Pure Timer-Based Scheme

In addition to update the paging area topology when an MS does not update its location for timet, an MS notifies the network when an MS moves across the border of paging areas in the proposed paging scheme. On the contrary, a pure timer-based paging algorithm might only update the location of an MS only when the t timer expires. In Figure 17, we compare the proposed scheme and the pure timer-based scheme. The proposed scheme has a lower signaling cost than the pure timer-based scheme as shown in the figure.Figure 17
Comparison to timer-based scheme.


## 7. Conclusion

In this work, we investigated the paging and location management scheme in the IEEE 802.16j multihop relay networks. The paging scheme is compatible with the idle mode operation in the IEEE 802.16j standard and integrates with the paging area design and timer-based location update mechanism scheme. We propose a generalized random walk mobility model that is suitable for investigating user mobility in multihop cellular relay system, for example, IEEE 802.16j. The analytical mobility model is shown to match the simulation results. We applied this random walk mobility model to analyze the proposed paging scheme. The proposed scheme performs well compared to naive timer-based scheme. In addition, the proposed paging area update optimization has been shown to minimize the signaling cost effectively. In the future, we plan to further invest age advanced paging and location update algorithms to further enhance the signaling cost and paging delay. Moreover, nonrandom-walk mobility model for IEEE 802.16j is an interesting future work item to study. Advanced paging and location update scheme over generalized user mobility model will play a critical role in optimization the IEEE 802.16j relay network.



---

*Source: 916569-2010-03-29.xml*