×

Continuum modeling and control of large nonuniform wireless networks via nonlinear partial differential equations. (English) Zbl 1273.35280

Summary: We introduce a continuum modeling method to approximate a class of large wireless networks by nonlinear partial differential equations (PDEs). This method is based on the convergence of a sequence of underlying Markov chains of the network indexed by \(N\), the number of nodes in the network. As \(N\) goes to infinity, the sequence converges to a continuum limit, which is the solution of a certain nonlinear PDE. We first describe PDE models for networks with uniformly located nodes and then generalize to networks with nonuniformly located, and possibly mobile, nodes. Based on the PDE models, we develop a method to control the transmissions in nonuniform networks so that the continuum limit is invariant under perturbations in node locations. This enables the networks to maintain stable global characteristics in the presence of varying node locations.

MSC:

35Q93 PDEs in connection with control and optimization
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
93C20 Control/observation systems governed by partial differential equations
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zhang, Y.; Chong, E. K. P.; Hannig, J.; Estep, D. J., Continuum limits of Markov chains with application to network modeling
[2] Zhang, Y.; Chong, E. K. P.; Hannig, J.; Estep, D., On continuum limits of markov chains and network modeling, Proceedings of the 49th IEEE Conference on Decision and Control (CDC ’10) · doi:10.1109/CDC.2010.5716965
[3] Chong, E. K. P.; Estep, D.; Hannig, J., Continuum modeling of large networks, International Journal of Numerical Modelling, 21, 3, 169-186 (2008) · Zbl 1138.90342 · doi:10.1002/jnm.651
[4] Burch, N. J., Continuum modeling of stochastic wireless sensor networks [M.S. thesis] (2008), Colorado State University
[5] Burch, N.; Chong, E.; Estep, D.; Hannig, J., Analysis of routing protocols and interference-limited communication in large wireless networks, Journal of Engineering Mathematics, 1-17 (2012)
[6] Kushner, H. J., Approximation and Weak Convergence Methods for Random Processes, with Applications to Stochastic Systems Theory. Approximation and Weak Convergence Methods for Random Processes, with Applications to Stochastic Systems Theory, MIT Press Series in Signal Processing, Optimization, and Control, 6, xvii+269 (1984), Cambridge, Mass, USA: MIT Press, Cambridge, Mass, USA · Zbl 0551.60056
[7] Robbins, H.; Monro, S., A stochastic approximation method, Annals of Mathematical Statistics, 22, 400-407 (1951) · Zbl 0054.05901 · doi:10.1214/aoms/1177729586
[8] Kiefer, J.; Wolfowitz, J., Stochastic estimation of the maximum of a regression function, Annals of Mathematical Statistics, 23, 462-466 (1952) · Zbl 0049.36601 · doi:10.1214/aoms/1177729392
[9] Benaïm, M., Dynamics of stochastic approximation algorithms, Séminaire de Probabilités, XXXIII. Séminaire de Probabilités, XXXIII, Lecture Notes in Mathematics, 1709, 1-68 (1999), Berlin, Germany: Springer, Berlin, Germany · Zbl 0955.62085 · doi:10.1007/BFb0096509
[10] Lai, T. L., Stochastic approximation, The Annals of Statistics, 31, 2, 391-406 (2003) · Zbl 1039.62077 · doi:10.1214/aos/1051027873
[11] Kurtz, T. G., Solutions of ordinary differential equations as limits of pure jump Markov processes, Journal of Applied Probability, 7, 49-58 (1970) · Zbl 0191.47301 · doi:10.2307/3212147
[12] Darling, R. W. R., Fluid limits of pure jump Markov processes: a practical guide
[13] McVinish, R.; Pollett, P., The deterministic limit of heterogeneous density dependent Markov chains · Zbl 1263.92039
[14] Ethier, S. N.; Kurtz, T. G., Markov Processes: Characterization and Convergence. Markov Processes: Characterization and Convergence, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, x+534 (1986), New York, NY, USA: John Wiley & Sons Inc., New York, NY, USA · Zbl 1089.60005 · doi:10.1002/9780470316658
[15] Billingsley, P., Convergence of Probability Measures. Convergence of Probability Measures, Wiley Series in Probability and Statistics: Probability and Statistics, x+277 (1999), New York, NY, USA: John Wiley & Sons, New York, NY, USA · Zbl 0944.60003 · doi:10.1002/9780470316962
[16] Gupta, P.; Kumar, P. R., The capacity of wireless networks, IEEE Transactions on Information Theory, 46, 2, 388-404 (2000) · Zbl 0991.90511 · doi:10.1109/18.825799
[17] Grossglauser, M.; Tse, D. N. C., Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking, 10, 4, 477-486 (2002) · doi:10.1109/TNET.2002.801403
[18] Herdtner, J. D.; Chong, E. K. P., Throughput-storage tradeoff in ad hoc networks, Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’05)
[19] Benaïm, M.; Boudec, J.-Y. L., A class of mean field interaction models for computer and communication systems, Performance Evaluation, 11-12 (2008)
[20] Caines, P. E., Bode lecture: mean field stochastic control, Proceedings of the 48th IEEE Conference on Decision and Control
[21] Dawson, D. A.; Tang, J.; Zhao, Y. Q., Balancing queues by mean field interaction, Queueing Systems, 49, 3-4, 335-361 (2005) · Zbl 1080.90026 · doi:10.1007/s11134-005-6971-z
[22] Graham, C.; Robert, P., Self-adaptive congestion control for multiclass intermittent connections in a communication network, Queueing Systems, 69, 3-4, 237-257 (2011) · Zbl 1236.90022 · doi:10.1007/s11134-011-9260-z
[23] Chang, C. S., Sample path large deviations and intree networks, Queueing Systems, 20, 1-2, 7-36 (1995) · Zbl 0844.60066 · doi:10.1007/BF01158430
[24] Duffield, N. G., A large deviation analysis of errors in measurement based admission control to buffered and bufferless resources, Queueing Systems, 34, 1-4, 131-168 (2000) · Zbl 0942.90022 · doi:10.1023/A:1019152918746
[25] Ahn, S.; Jeon, J., Analysis of \(G / D / 1\) queueing systems with inputs satisfying large deviation principle under \(\text{weak}^*\) topology, Queueing Systems, 40, 3, 295-311 (2002) · Zbl 1169.90331 · doi:10.1023/A:1014763513810
[26] Blount, D., Law of large numbers in the supremum norm for a chemical reaction with diffusion, The Annals of Applied Probability, 2, 1, 131-141 (1992) · Zbl 0747.60033 · doi:10.1214/aoap/1177005774
[27] Huang, C.-f.; Pagès, H., Optimal consumption and portfolio policies with an infinite horizon: existence and convergence, The Annals of Applied Probability, 2, 1, 36-64 (1992) · Zbl 0749.60039 · doi:10.1214/aoap/1177005770
[28] Xu, G.-L.; Shreve, S. E., A duality method for optimal consumption and investment under short-selling prohibition. II. Constant market coefficients, The Annals of Applied Probability, 2, 2, 314-328 (1992) · Zbl 0773.90017 · doi:10.1214/aoap/1177005706
[29] Burger, M.; Markowich, P. A.; Pietschmann, J.-F., Continuous limit of a crowd motion and herding model: analysis and numerical simulations, Kinetic and Related Models, 4, 4, 1025-1047 (2011) · Zbl 1347.35128 · doi:10.3934/krm.2011.4.1025
[30] Chen, H.; Whitt, W., Diffusion approximations for open queueing networks with service interruptions, Queueing Systems, 13, 4, 335-359 (1993) · Zbl 0783.60088 · doi:10.1007/BF01149260
[31] Harrison, J. M.; Nguyen, V., Brownian models of multiclass queueing networks: current status and open problems, Queueing Systems, 13, 1-3, 5-40 (1993) · Zbl 0781.60090 · doi:10.1007/BF01158927
[32] Chen, H.; Kella, O.; Weiss, G., Fluid approximations for a processor-sharing queue, Queueing Systems, 27, 1-2, 99-125 (1997) · Zbl 0892.90073 · doi:10.1023/A:1019105929766
[33] Chen, R.-R.; Meyn, S., Value iteration and optimization of multiclass queueing networks, Queueing Systems, 32, 1-3, 65-97 (1999) · Zbl 0949.90020 · doi:10.1023/A:1019182903300
[34] Hampshire, R. C.; Harchol-Balter, M.; Massey, W. A., Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates, Queueing Systems, 53, 1-2, 19-30 (2006) · Zbl 1117.60083 · doi:10.1007/s11134-006-7584-x
[35] Piera, F. J.; Mazumdar, R. R.; Guillemin, F. M., Existence and characterization of product-form invariant distributions for state-dependent stochastic networks in the heavy-traffic diffusion limit, Queueing Systems, 58, 1, 3-27 (2008) · Zbl 1136.60369 · doi:10.1007/s11134-007-9056-3
[36] Guenther, R. B.; Lee, J. W., Partial Differential Equations of Mathematical Physics and Integral Equations, xii+562 (1996), Mineola, NY, USA: Dover, Mineola, NY, USA · Zbl 0879.35001
[37] He, J.-H., Asymptotic Methods for Solitary Solutions and Compactons, Abstract and Applied Analysis, 2012 (2012) · Zbl 1257.35158 · doi:10.1155/2012/916793
[38] Liu, G. R.; Quek, S. S., The Finite Element Method: A Practical Course (2003), Butterworth-Heinemann · Zbl 1027.74001
[39] Mitchell, A. R.; Griffiths, D. F., The Finite Difference Method in Partial Differential Equations, xii+272 (1980), Chichester, UK: John Wiley & Sons, Chichester, UK · Zbl 0417.65048
[40] Robinson, J. C., An Introduction to Ordinary Differential Equations, xiv+399 (2004), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 1053.34001 · doi:10.1017/CBO9780511801204
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.