15.3 Other Paging Schemes

15.3 Other Paging Schemes

Assume that each LA consists of the same number N of cells in the system. ^[12] The worst-case paging delay is considered as delay bound, D, in terms of polling cycle. When D is equal to 1, the system should find the called MT in one polling cycle, requiring all cells within the LA to be polled simultaneously. The paging cost, C, which is the number of cells polled to find the called MT, is equal to N. In this case, the average paging delay is at its lowest, which is one polling cycle, and the average paging cost is at its highest, C = N. On the other hand, when D is equal to N, the system will poll one cell in each polling cycle and search all cells one by one. Thus, the worst case occurs when the called MT is found in the last polling cycle, which means the paging delay would be at its maximum and equal to N polling cycles. ^[13] However, the average paging cost may be minimized if the cells are searched in decreasing order of location probabilities. ^[14]

Consider the partition of PAs given that 1 ≤ D ≤ N, which requires grouping cells within an LA into the smaller PAs under delay bound D. Suppose, at a given time, the initial state P is denned as P = [p₁p₂...,p_j...,p_N], where p_j is the location probability of the j-th cell to be searched in decreasing order of probability. Thus the time effect is reflected in the location probability distribution. We use triplets PA*_P (i, q_i, n_i) to denote the PAs under the paging scheme P in which i is the sequence number of the PA, q_i is the location probability that the called MT can be found within the i-th PA, and n_i is the number of cells contained in this PA. In Figure 15.2, an LA is divided into D PAs because the delay bound is assumed to be D. Thus, the worst-case delay is guaranteed to be D polling cycles. The system searches the PAs one after another until the called MT is found. Three paging schemes are discussed in this section.

Figure 15.2: Partition of location area in paging areas.

15.3.1 Reverse Paging

This scheme is designed for a situation where the called MT is most probably to be found in a few cells. Consider the first (D - 1) highest probability cells as the first (D - 1) PAs to be searched. Each of these (D - 1) PAs consists of only one cell. It is then lumped with the remaining (N - D + 1) lower probability cells to be the last PA, i.e., the D-th PA. The newly formed PAs become PA^*_r (1, p₁, 1), PA^*_r (2, p₂, 1), ..., PA^*_r (D -1, p_D-1, 1), PA^*_r (D, q_D, N - D + 1), where r denotes the reverse paging scheme.

15.3.2 Semireverse Paging

Because the average paging cost can be minimized by searching cells in decreasing order of location probability if a delay bound D is not applied, ^[15] intuitively the paging cost can be reduced by searching the PAs in decreasing order of probability. Under a semireverse paging scheme, a set of PAs is created in a nonincreasing order of location probabilities. Combine first the two cells with the lowest location probabilities into one PA, and then reorder all PAs in nonincreasing order of location probabilities. Keep combining the two lowest probabilities PAs and reorder them until the total number of PAs is equal to D. If two PAs have the same probability, the PA with fewer cells has higher priority, i.e., its sequence number is smaller. The semireverse paging scheme guarantees that the location probability of each PA is in a nonincreasing order. However, the cell with lower probability may be searched before the cell with higher probability because the initial sequence of the cells is reordered during the semireverse paging procedure.

15.3.3 Uniform Paging

Under this scheme, the LA is partitioned into a series of PAs in such a way that all PAs consist of approximately the same number of cells. The uniform paging procedure is as follows:

• Calculate the number of cells in each PA as n₀ = ⌊N/D⌋, where N = n₀D + k.

• Determine a series of PAs as PA^*_u (1, p₁, 1), PA^*_u (2, p₂, 1),..., PA^*_u (D, q_D, n_D). Note that there are n₀ cells in each of the first (D - k) PAs and there are n₀ + 1 cells in each of the remaining PAs. This means n₁ = n₂ = ... = n_D-k = n₀, and n_D-k+1 = ... = n_D = n₀ + 1. For example, the first PA consists of n₀ cells and the last PA, i.e., D-th PA, consists of n₀ + 1 cells.

• The network polls one PA after another sequentially until the called MT is found.

^[12]Wang, W., Akyildiz, I.F., and St ber, G.L., Effective paging schemes with delay bounds as QoS constraints in wireless systems, Wireless Networks, 7, 455–466, 2001.

^[13]Wang, W., Akyildiz, I.F., and St ber, G.L., Reducing the paging costs under delay bounds for PCS networks, Proc. of IEEE WCNC'2000, Sept. 2000.

^[14]Rose, C. and Yates, R., Minimizing the average cost of paging under delay constraints, Wireless Networks, 1, 211–219, 1995.

^[15]Rose, C. and Yates, R., Minimizing the average cost of paging under delay constraints, Wireless Networks, 1, 211–219, 1995.