Skip to main content
Springer Nature Link
Log in

Optimal aggregation factor and clustering under delay constraints in aggregate sequential group paging schemes

  • Published:
Wireless Networks Aims and scope Submit manuscript

Abstract

This paper considers several optimization problems of sequential paging with aggregation mechanism which has been shown to reduce significantly the paging cost of a wireless communication system. An important problem is to find the optimal aggregation factor subject to a constraint on the average paging delay. Another problem is, given a cost function that depends on both paging cost and paging delay, how to find the optimal aggregation factor to minimize that cost function. We have formulated and shown that these can be solved nicely due to the monotonicity and convexity of the average paging cost function and paging delay function. We demonstrate that the optimization problems of the aggregate factor and subnet clustering are not separable. This leads to joint optimization problems of aggregation factor and clustering that are investigated in this paper. The paper presents different algorithms to solve these joint optimization problems using the monotonicity in the aggregation factor and the number of clusters of the average paging cost and delay with the unconstrained optimal clustering and the structures of the constrained optimal clustering.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

References

  1. Perkins, C. E. (2002). Mobile IP. IEEE Communications Magazine, May 1997, updated version, IEEE Communications Magazine.

  2. Zhang, X., Castellanos, J., Campbell, A. (2002). Design and performance of mobile IP paging, ACM mobile networks and applications (MONET). Special Issue on Modeling Analysis and Simulation of Wireless and Mobile Systems, 7(2), 127–141.

    Google Scholar 

  3. Ramjee, R., Li, L., Porta, T. L., & Kasera, S. (2002). IP paging services for mobile hosts. Wireless Networks, 8, 427–441.

    Article  MATH  Google Scholar 

  4. Zhang, T., Li, S.-W., Ohba, Y., & Nakajima, T. (2002). A flexible and scalable IP paging protocol. Proceedings of IEEE GLOBECOM, 1, 630–635.

    Google Scholar 

  5. Gustafsson, E., Jonrsson, A., Perkin, C. (2000). Mobile IP regional registration. Internet Draft, draft-ietf-mobileip-reg-tunnel-02.txt, March.

  6. Haverinen, H., Malinen, J. (2000). Mobile IP regional paging. Internet Draft, draft-haverinen-mobileip-reg-paging-00.txt.

  7. Akyildiz, I. F., Xie, J., Mohanty, S. (2004). A survey of mobility management in next-generation all-IP-based wireless systems. IEEE Wireless Communications, 11(4), 16–28.

    Article  Google Scholar 

  8. Reinbold, P., & Bonaventure, O. (2003). IP micro-mobility protocols. IEEE Communications Survey and Tutorials, 5(1), 40–57.

    Article  Google Scholar 

  9. Liebsch, M., & Lamparter, B. (2005). A generic IP paging architecture and protocol. Computer Networks, 49, 427–448.

    Article  Google Scholar 

  10. Castellucia, C. (2001). Extending mobile IP with adaptive individual paging: A performance analysis. ACM Mobile Computing and Communication Review, 5(2), 14–26.

    Article  Google Scholar 

  11. Xie, H., Tabbane, S., Goodman, D. J. (1993). Dynamic location area management and performance analysis. In Proceedings of 43rd IEEE Vehicular Technology Conference, pp. 536–539.

  12. Varsamopoulos, G., & Gupta, S. K. S. (2004). Dynamically adapting registration areas to user mobility and call patterns for efficient location management in PCS networks. IEEE/ACM Transaction on Networking, 12(5), 837–850.

    Article  Google Scholar 

  13. Do, H. T., & Onozato, Y. (2005) IP paging scheme adaptive to mobile host parameters. IEICE Transactions on Fundamentals, E88-A(4), 948–953.

    Article  Google Scholar 

  14. Do, H. T., & Onozato, Y. (2007). A comparison of different paging mechanisms for mobile IP. ACM Journal of Wireless Networks, 13(3), 379–395.

    Article  Google Scholar 

  15. Xie, J. & Akyildiz, I. F. (2002). Novel distributed dynamic location management scheme for minimizing signaling costs in mobile IP. IEEE Transactions on Mobile Computing, 1(3), 163–175.

    Article  Google Scholar 

  16. Choi, T., Kim, L., Nah, J., & Song, J. (2004). Combinatorial mobile IP: A new efficient mobility management using minimized paging and local registration in mobile IP environments. Wireless Networks, 10(3), 311–321.

    Article  Google Scholar 

  17. Rose, C., & Yates, R. (1995). Minimizing the average cost of paging under delay constraints. ACM Journal of Wireless Networks (WINET), 1, 211–219.

    Article  Google Scholar 

  18. Krishnamachari, B., Gau, R.-H., Wicker, S., & Haas, Z. (2004). Optimal sequential paging in cellular wireless networks. ACM Journal of Wireless Networks (WINET), 10, 121–131.

    Article  Google Scholar 

  19. Hung, T. D. & Onozato, Y. (2005). Flexible and effective multi-step ip paging schemes. IEEE 62nd Vehicular Technology Conference (VTC2005-Fall), Vol. 2, pp. 831–835, Sep. 2005, Dallas, Texas, USA.

  20. Haverinen, H., & Malinen, J. (2006). Method and apparatus for mobile internet protocol regional paging. US Patent 7,142,520, issued Nov. 28, 2006.

  21. Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge: Cambridge University Press.

    MATH  Google Scholar 

  22. Shaked, M., & George Santhikumar, J. (2006). Stochastic orders (1st ed.). Berlin: Springer.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Operations Management, Purdue University, West Lafayette, IN, USA

    Hung Tuan Do

  2. Department of Computer Science, Graduate School of Engineering, Gunma University, Kiryu, 376-8515, Japan

    Yoshikuni Onozato & Ushio Yamamoto

Authors
  1. Hung Tuan Do
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yoshikuni Onozato
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ushio Yamamoto
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ushio Yamamoto.

Appendices

Appendices

1.1 Proof of proposition 2

The problem to be considered is as follows.

Suppose we have two partition vectors v = (|g 1|,…,|g m |) and v ′ = (|g′ 1|,…,|g′ m |) in which g i  ≡ g′ i for i ≠ j, l such that 1 ≤ j< l ≤ m and P G (g j ) ≤ P G (g l ). In partition v ′, g j and g l are swapped, all other elements of v and v ′ are the same. We want to see if C(k,v) ≥ C(k,v ′) and L(k,v) ≥ L(k,v ′).

1.1.1 Average paging cost function

$$ \begin{aligned} C(k,{\user2{v}}) \ge & C(k,{\user2{v}}\prime ) \\ \Leftrightarrow & \sum\limits_{i = 1}^{m} {\left( {A_{i}^{k} - A_{i - 1}^{k} } \right)B_{i} } \le \sum\limits_{i = 1}^{m} {\left( {A_{i}^{\prime k} - A_{i - 1}^{\prime k} } \right)B_{i} } \\ \Leftrightarrow & \sum\limits_{i = 1}^{j - 1} {\left( {A_{i}^{k} - A_{i - 1}^{k} } \right)B_{i} } + \left( {A_{j}^{k} - A_{j - 1}^{k} } \right)B_{j} + \sum\limits_{i = j + 1}^{l - 1} {\left( {A_{i}^{k} - A_{i - 1}^{k} } \right)B_{i} } + \left( {A_{l}^{k} - A_{l - 1}^{k} } \right)B_{l} + \sum\limits_{i = l + 1}^{m} {\left( {A_{i}^{k} - A_{i - 1}^{k} } \right)B_{i} } \\ \le & \sum\limits_{i = 1}^{j - 1} {\left( {A_{i}^{\prime k} - A_{i - 1}^{\prime k} } \right)B_{i} } + \left( {A_{j}^{\prime k} - A_{j - 1}^{\prime k} } \right)B_{j} + \sum\limits_{i = m + 1}^{l - 1} {\left( {A_{i}^{\prime k} - A_{i - 1}^{\prime k} } \right)B_{i} } + \left( {A_{l}^{\prime k} - A_{l - 1}^{k} } \right)B_{l} \\ & + \sum\limits_{i = l + 1}^{m} {\left( {A_{i}^{'k} - A_{i - 1}^{'k} } \right)B_{i} } \\ \Leftrightarrow & \left( {A_{j}^{k} - A_{j - 1}^{k} } \right)B_{j} + \sum\limits_{i = j + 1}^{l - 1} {\left( {A_{i}^{k} - A_{i - 1}^{k} } \right)B_{i} } + \left( {A_{l}^{k} - A_{l - 1}^{k} } \right)B_{l} \\ \le & \left( {A_{j}^{'k} - A_{j - 1}^{'k} } \right)B_{j} + \sum\limits_{i = j + 1}^{l - 1} {\left( {A_{i}^{'k} - A_{i - 1}^{'k} } \right)B_{i} } + \left( {A_{l}^{'k} - A_{l - 1}^{'k} } \right)B_{l} \\ \Leftrightarrow & \left( {A_{j}^{k} - A_{j}^{'k} } \right)B_{j} + \left( {A_{l - 1}^{'k} - A_{l - 1}^{k} } \right)B_{l} + \sum\limits_{i = j + 1}^{l - 1} {\left( {\left( {A_{i}^{k} - A_{i - 1}^{k} } \right) - \left( {A_{i}^{'k} - A_{i - 1}^{'k} } \right)} \right)B_{i} } \ge 0 \\ \end{aligned} $$
(16)

Note that in the above derivation, we use B i  = B i ′ for i and Aj−1 = A′ j−1 , A l  = A′ l .

For k = 1, we have A i  − A i−1=P G (g i ) = P G (g′ i ) = A′ i−1, so the above (16) becomes simply the following:

$$ \begin{array}{ll} &\left( {A_{j} - A\prime_{j} } \right)B_{j} + \left( {A\prime_{l - 1} - A_{l - 1} } \right)B_{l} \ge 0 \hfill \\ &\quad\Leftrightarrow \left( {P_{G} (g_{j} ) - P_{G} (g_{l} )}\right)B_{j} + \left( {P_{G} (g_{l} ) - P_{G} (g_{j} )} \right)B_{l} \ge 0 \hfill \\&\quad\Leftrightarrow \left( {P_{G} (g_{l} ) - P_{G} (g_{j} )} \right)\left( {B_{l} - B_{j} } \right) \ge 0 \hfill \\\end{array} $$

This inequality obviously holds.

In general, the inequality is not simplified as for k = 1, and hence more difficult to verify.

Instead of considering the above inequality, we consider the case where l = j + 1, i.e. two groups are adjacent. All unordered partition can be transformed to the descent order partition using this basic swap operation as in the bubble-sorting algorithm. Thus, it suffices to show the inequality for adjacent groups.

Notice that we can write A i  = a i  + P G (g j ), A′ i  = a i  + P G (g l ) for j ≤ i ≤ l − 1 where

$$ a_{i} = A_{j - 1} + \sum\nolimits_{t = j + 1}^{i} {P_{G} (g_{t} )} . $$
$$ \begin{gathered} \Leftrightarrow \left( {\left( {a_{j} + P_{G} (g_{j} )} \right)^{k} - \left( {a_{j} + P_{G} (g_{l} )} \right)^{k} } \right)B_{j} + \left( {\left( {a_{l - 1} + P_{G} (g_{l} )} \right)^{k} - \left( {a_{l - 1} + P_{G} (g_{j} )} \right)^{k} } \right)B_{l} \hfill \\ + \sum\limits_{t = j + 1}^{l - 1} {\left( {\left( {\left( {a_{t} + P_{G} (g_{j} )} \right)^{k} - \left( {a_{t - 1} + P_{G} (g_{j} )} \right)^{k} } \right) - \left( {\left( {a_{t} + P_{G} (g_{l} )} \right)^{k} - \left( {a_{t - 1} + P_{G} (g_{l} )} \right)^{k} } \right)} \right)B_{t} } \ge 0 \hfill \\ \end{gathered} $$

For l = j + 1, the above becomes:

$$ \begin{gathered} \left( {\left( {a_{j} + P_{G} (g_{j} )} \right)^{k} - \left( {a_{j} + P_{G} (g_{l} )} \right)^{k} } \right)B_{j} + \left( {\left( {a_{j} + P_{G} (g_{l} )} \right)^{k} - \left( {a_{j} + P_{G} (g_{j} )} \right)^{k} } \right)B_{l} \ge 0 \hfill \\ \Leftrightarrow \left( {\left( {a_{j} + P_{G} (g_{l} )} \right)^{k} - \left( {a_{j} + P_{G} (g_{j} )} \right)^{k} } \right)\left( {B_{l} - B_{j} } \right) \ge 0 \hfill \\ \end{gathered} $$

This also obviously holds.

1.1.2 Average paging delay function

The average paging delay function consists of an affine function of k, which is not dependent on partition v, and a function dependent on v, but independent of k. The proof is essentially the same as for k = 1.

$$ \begin{aligned} L(k,v) = & \sum\limits_{i = 1}^{m} {P_{G} (g_{i} )i} + {\frac{{L_{\text{aggr}} }}{2}} = \sum\limits_{i = 1}^{m} {\left( {A_{i} - A_{i - 1} } \right)i} + {\frac{{L_{{_{\text{aggr}} }} }}{2}} \\ \ge & L(k,v') = \sum\limits_{i = 1}^{m} {P_{G} (g'_{i} )i} + {\frac{{L'_{\text{aggr}} }}{2}} = \sum\limits_{i = 1}^{m} {\left( {A'_{i} - A'_{i - 1} } \right)i} + {\frac{{L'_{{_{\text{aggr}} }} }}{2}} \\ \Leftrightarrow & \left( {A_{j} - A_{j - 1} } \right)j + \left( {A_{l} - A_{l - 1} } \right)l \ge \left( {A'_{j} - A'_{j - 1} } \right)j + \left( {A'_{l} - A'_{l - 1} } \right)l \\ \Leftrightarrow & \left( {A_{j} - A'_{j} } \right)j + \left( {A'_{l - 1} - A_{l - 1} } \right)l \ge 0 \\ \Leftrightarrow & \left( {P_{G} (g_{l} ) - P_{G} (g_{j} )} \right)\left( {l - j} \right) \ge 0 \\ \end{aligned} $$

Proof of Proposition 3

Consider the function C(x), where x is a positive real number, we will show that it is convex in x.

Let x 1, x 2 be positive real numbers and x = αx 1 + (1 − α)x 2, where α ∈ [0,1]. We need to show that C(x) ≤ α C(x 1) + (1 − α) C(x 2).

$$ \begin{aligned} C(x) = & C(\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} ) \\ = & {\frac{1}{{\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} }}}\left( {\sum\limits_{i = 1}^{m} {\left( {A_{i}^{{\alpha x_{1} + (1 - \alpha )x_{2} }} - A_{i - 1}^{{\alpha x_{1} + (1 - \alpha )x_{2} }} } \right)B_{i} } } \right) \\ \le & {\frac{\alpha }{{x_{1} }}}\sum\limits_{i = 1}^{m} {\left( {A_{i}^{{x_{1} }} - A_{i - 1}^{{x_{1} }} } \right)B_{i} } + {\frac{1 - \alpha }{{x_{2} }}}\sum\limits_{i = 1}^{m} {\left( {A_{i}^{{x_{2} }} - A_{i - 1}^{{x_{2} }} } \right)B_{i} } \\ \Leftrightarrow & LHS \le {\frac{1}{{x_{1} x_{2} }}}\left( {\sum\limits_{i = 1}^{m} {\left( {A_{i}^{{x_{1} }} - A_{i - 1}^{{x_{1} }} } \right)\alpha x_{2} B_{i} + \sum\limits_{i = 1}^{m} {\left( {A_{i}^{{x_{2} }} - A_{i - 1}^{{x_{2} }} } \right)\left( {1 - \alpha } \right)x_{1} B_{i} } } } \right) \\ = & {\frac{1}{{x_{1} x_{2} }}}\sum\limits_{i = 1}^{m} {\left( {\left( {\alpha x_{2} A_{i}^{{x_{1} }} + \left( {1 - \alpha } \right)x_{1} A_{i}^{{x_{2} }} } \right) - \left( {\alpha x_{2} A_{i - 1}^{{x_{1} }} + (1 - \alpha )x_{1} A_{i - 1}^{{x_{2} }} } \right)} \right)} B_{i} \\ \Leftrightarrow & x_{1} x_{2} \sum\limits_{i = 1}^{m} {\left( {A_{i}^{{\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} }} - A_{i - 1}^{{\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} }} } \right)B_{i} } \\ \le & \left( {\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} } \right)\sum\limits_{i = 1}^{m} {\left( {\left( {\alpha x_{2} A_{i}^{{x_{1} }} + (1 - \alpha )x_{1} A_{i}^{{x_{2} }} } \right) - \left( {\alpha x_{2} A_{i - 1}^{{x_{1} }} + (1 - \alpha )x_{1} A_{i - 1}^{{x_{2} }} } \right)} \right)} B_{i} \\ \Leftrightarrow & \sum\limits_{i = 1}^{m} {x_{1} x_{2} A_{i}^{{\alpha x_{1} + (1 - \alpha )x_{2} }} B_{i} } - \sum\limits_{i = 1}^{m} {x_{1} x_{2} A_{i - 1}^{{\alpha x_{1} + (1 - \alpha )x_{2} }} B_{i} } \\ \le & \sum\limits_{i = 1}^{m} {\left( {\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} } \right)\left( {\alpha x_{2} A_{i}^{{x_{1} }} + (1 - \alpha )x_{1} A_{i}^{{x_{2} }} } \right)B_{i} } - \sum\limits_{i = 1}^{m} {(\alpha x_{1} + (1 - \alpha )x_{2} )\left( {\alpha x_{2} A_{i - 1}^{{x_{1} }} + (1 - \alpha )x_{1} A_{i - 1}^{{x_{2} }} } \right)B_{i} } \\ \Leftrightarrow & \sum\limits_{i = 1}^{m} {\left( {x_{1} x_{2} A_{i}^{{\alpha x_{1} + (1 - \alpha )x_{2} }} - \left( {\alpha x_{1} + (1 - \alpha )x_{2} } \right)\left( {\alpha x_{2} A_{i}^{{x_{1} }} + \left( {1 - \alpha } \right)x_{1} A_{i}^{{x_{2} }} } \right)} \right)} B_{i} \\ \le & \sum\limits_{i = 1}^{m} {\left( {x_{1} x_{2} A_{i - 1}^{{\alpha x_{1} + (1 - \alpha )x_{2} }} - \left( {\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} } \right)\left( {\alpha x_{2} A_{i - 1}^{{x_{1} }} + (1 - \alpha )x_{1} A_{i - 1}^{{x_{2} }} } \right)} \right)B_{i} } \\ \end{aligned} $$
(17)

Let \( h\left( {A_{i} } \right) = x_{ 1} x_{ 2} A_{i}^{{\alpha x 1 + (1 - \alpha )x^{2} }} - \left( {\alpha x_{ 1} ( 1- \alpha )x_{2} } \right)\left( {\alpha x_{ 2} A_{i}^{{x^{1} }} + \left( { 1- \alpha } \right)x_{ 1} A_{i}^{{x^{2} }} } \right), \) then it is easy to see that the following is a sufficient condition for the above (17):

$$ \sum\limits_{i = 1}^{m} {\left( {h(A_{i} ) - h(A_{i - 1} )} \right)} \le 0 $$
(18)

Again we investigate the first derivative of h(A i ):

$$ \begin{aligned} {\frac{{{\text{d}}h(A_{i} )}}{{{\text{d}}A_{i} }}} = & x_{1} x_{2} \left( {\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} } \right)A_{i}^{{\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} - 1}} - \alpha x_{1} x_{2} \left( {\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} } \right)A_{i}^{{x_{1} - 1}} \\ & - \left( {\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} } \right)\left( {1 - \alpha } \right)x_{1} x_{2} A_{i}^{{x_{2} - 1}} \\ = & {\frac{{x_{1} x_{2} \left( {\alpha x_{1} + \left( {1 - \alpha } \right)x_{2} } \right)}}{{A_{i} }}}\left( {A_{i}^{{\theta x_{1} + \left( {1 - \theta } \right)x_{2} }} - \left( {\alpha A_{i}^{{x_{1} }} + \left( {1 - \alpha } \right)A_{i}^{{x_{2} }} } \right)} \right) \\ \end{aligned} $$

Note that the function a x is convex in x for a ∈ (0,1], so by definition, we have

$$ A_{i}^{{\alpha x_{1} + (1 - \alpha )x_{2} }} \le \alpha A_{i}^{{x_{1} }} + \left( {1 - \alpha } \right)A_{i}^{{x_{2} }} $$

This implies that \( {\frac{{{\text{d}}h(A_{i} )}}{{{\text{d}}A_{i} }}} \le 0 \). Consequently, h(A i ) is non-increasing function. As A i−1 < A i , we have (18). This implies that (17) holds, and consequently, C(x) is convex in x.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Do, H.T., Onozato, Y. & Yamamoto, U. Optimal aggregation factor and clustering under delay constraints in aggregate sequential group paging schemes. Wireless Netw 16, 1427–1446 (2010). https://doi.org/10.1007/s11276-009-0212-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11276-009-0212-z

Keywords

Search

Navigation