
-
Previous Article
Optimal customer behavior in observable and unobservable discrete-time queues
- JIMO Home
- This Issue
-
Next Article
Optimal financing and operational decisions of capital-constrained manufacturer under green credit and subsidy
Mean-field analysis of a scaling MAC radio protocol
1. | MTA-BME Information Systems Research Group, H-1117 Budapest, Magyar Tudosok krt. 2 |
2. | Budapest University of Technology and Economics, Department of Networked Systems and Services, H-1117 Budapest, Magyar Tudosok krt. 2 |
3. | MTA-BME Information Systems Research Group, Budapest University of Technology and Economics, Department of Networked Systems and Services, H-1117 Budapest, Magyar Tudosok krt. 2 |
We examine the transient behavior of a positioning system with a large number of tags trying to connect to the infrastructure with an exponential backoff policy in case of unsuccessful connection. Using a classic mean-field approach, we derive a system of differential equations whose solution approximates the original process. Analysis of the solution shows that both the solution and the original system exhibits an unusual log-periodic behavior in the mean-field limit, along with other interesting patterns of behavior. We also perform numerical optimization for the backoff policy.
References:
[1] |
A.-L. Barabási, R. Albert and H. Jeong, Mean-field theory for scale-free random networks, Physica A: Statistical Mechanics and its Applications, 272 (1999), 173-187. Google Scholar |
[2] |
G. Ben Arous, A. Fribergh, N. Gantert and Al an Hammond,
Biased random walks on Galton-Watson trees with leaves, Ann. Probab., 40 (2012), 280-338.
doi: 10.1214/10-AOP620. |
[3] |
J. I. Capetanakis,
Tree algorithms for packet broadcast channels, IEEE Transactions on Information Theory, 25 (1979), 505-515.
doi: 10.1109/TIT.1979.1056093. |
[4] |
V. Claesson, H. Lonn and N. Suri, An efficient TDMA start-up and restart synchronization approach for distributed embedded systems, IEEE Transactions on Parallel and Distributed Systems, 15 (2004), 725-739. Google Scholar |
[5] |
Federal Communications Commission et al, Title 47-Telecommunication: Chapter I-Federal Communications Commission: Subchapter A-General: Part 15-radio frequency devices, Federal Communications Commission Regulatory Information, (2009). Google Scholar |
[6] |
S. N. Ethier and T. G. Kurtz, Characterization and Convergence, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1986.
doi: 10.1002/9780470316658. |
[7] |
International Organization for Standardization, Information technology-Radio frequency identification for item management-Part 6: Parameters for air interface communications at 860 MHz to 960 MHz General, ISO/IEC standard, (2013). Google Scholar |
[8] |
C. Kipnis and S. R. S. Varadhan,
Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions, Comm. Math. Phys., 104 (1986), 1-19.
doi: 10.1007/BF01210789. |
[9] |
T. Komorowski, C. Landim and S. Olla, Fluctuations in Markov Processes: Time Symmetry and Martingale Approximation, Grundlehren der mathematischen Wissenschaften, 325. Springer Berlin Heidelberg, 2012.
doi: 10.1007/978-3-642-29880-6. |
[10] |
T. G. Kurtz,
Solutions of ordinary differential equations as limits of pure jump Markov processes, Journal of Applied Probability, 7 (1970), 49-58.
doi: 10.2307/3212147. |
[11] |
B.-J. Kwak, N.-O. Song and L. E. Miller, On the stability of exponential backoff, Journal of research of the National Institute of Standards and Technology, 108 (2003), 289-297. Google Scholar |
[12] |
B.-J. Kwak, N.-O. Song and L. E. Miller, Performance analysis of exponential backoff, IEEE/ACM Trans. Netw., 13 (2005), 343-355. Google Scholar |
[13] |
V. Bansaye and S. Méléard, Stochastic Models for Structured Populations: Scaling Limits and Long Time Behavior, Springer International Publishing, 2015.
doi: 10.1007/978-3-319-21711-6. |
[14] |
Y. Shen, H. Wymeersch and M. Z. Win,
Fundamental limits of wideband localization-part II: Cooperative networks, IEEE Trans. Inform. Theory, 56 (2010), 4981-5000.
doi: 10.1109/TIT.2010.2059720. |
[15] |
G. W. Shi and Y. Ming, Survey of indoor positioning systems based on ultra-wideband (UWB) technology, Wireless Communications, Networking and Applications, (2016), 1269–1278.
doi: 10.1007/978-81-322-2580-5_115. |
[16] |
M. Shurman, B. Al Shua'b, M. Alsaedeen, M. F. Al-Mistarihi and K. Darabkh, N-BEB: New backoff algorithm for IEEE 802.11 MAC protocol, In 37th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), (2014), 540–544.
doi: 10.1109/MIPRO.2014.6859627. |
[17] |
IEEE Computer Society, Low-Rate Wireless Personal Area Networks (LR-WPANs), IEEE Standard, 2011. Google Scholar |
[18] |
L. Y. Song, H. L. Zou and T. T. Zhang, A low complexity asynchronous UWB TDOA localization method, International Journal of Distributed Sensor Networks, 11 (2015). Google Scholar |
[19] |
D. Stauffer and D. Sornette,
Log-periodic oscillations for biased diffusion on random lattice, Physica A, 252 (1998), 271-277.
doi: 10.1016/S0378-4371(97)00680-8. |
[20] |
W. Steiner and M. Paulitsch, The transition from asynchronous to synchronous system operation: An approach for distributed fault-tolerant systems, Proceedings 22nd International Conference on Distributed Computing Systemspages, (2002), 329–336.
doi: 10.1109/ICDCS.2002.1022270. |
show all references
References:
[1] |
A.-L. Barabási, R. Albert and H. Jeong, Mean-field theory for scale-free random networks, Physica A: Statistical Mechanics and its Applications, 272 (1999), 173-187. Google Scholar |
[2] |
G. Ben Arous, A. Fribergh, N. Gantert and Al an Hammond,
Biased random walks on Galton-Watson trees with leaves, Ann. Probab., 40 (2012), 280-338.
doi: 10.1214/10-AOP620. |
[3] |
J. I. Capetanakis,
Tree algorithms for packet broadcast channels, IEEE Transactions on Information Theory, 25 (1979), 505-515.
doi: 10.1109/TIT.1979.1056093. |
[4] |
V. Claesson, H. Lonn and N. Suri, An efficient TDMA start-up and restart synchronization approach for distributed embedded systems, IEEE Transactions on Parallel and Distributed Systems, 15 (2004), 725-739. Google Scholar |
[5] |
Federal Communications Commission et al, Title 47-Telecommunication: Chapter I-Federal Communications Commission: Subchapter A-General: Part 15-radio frequency devices, Federal Communications Commission Regulatory Information, (2009). Google Scholar |
[6] |
S. N. Ethier and T. G. Kurtz, Characterization and Convergence, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1986.
doi: 10.1002/9780470316658. |
[7] |
International Organization for Standardization, Information technology-Radio frequency identification for item management-Part 6: Parameters for air interface communications at 860 MHz to 960 MHz General, ISO/IEC standard, (2013). Google Scholar |
[8] |
C. Kipnis and S. R. S. Varadhan,
Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions, Comm. Math. Phys., 104 (1986), 1-19.
doi: 10.1007/BF01210789. |
[9] |
T. Komorowski, C. Landim and S. Olla, Fluctuations in Markov Processes: Time Symmetry and Martingale Approximation, Grundlehren der mathematischen Wissenschaften, 325. Springer Berlin Heidelberg, 2012.
doi: 10.1007/978-3-642-29880-6. |
[10] |
T. G. Kurtz,
Solutions of ordinary differential equations as limits of pure jump Markov processes, Journal of Applied Probability, 7 (1970), 49-58.
doi: 10.2307/3212147. |
[11] |
B.-J. Kwak, N.-O. Song and L. E. Miller, On the stability of exponential backoff, Journal of research of the National Institute of Standards and Technology, 108 (2003), 289-297. Google Scholar |
[12] |
B.-J. Kwak, N.-O. Song and L. E. Miller, Performance analysis of exponential backoff, IEEE/ACM Trans. Netw., 13 (2005), 343-355. Google Scholar |
[13] |
V. Bansaye and S. Méléard, Stochastic Models for Structured Populations: Scaling Limits and Long Time Behavior, Springer International Publishing, 2015.
doi: 10.1007/978-3-319-21711-6. |
[14] |
Y. Shen, H. Wymeersch and M. Z. Win,
Fundamental limits of wideband localization-part II: Cooperative networks, IEEE Trans. Inform. Theory, 56 (2010), 4981-5000.
doi: 10.1109/TIT.2010.2059720. |
[15] |
G. W. Shi and Y. Ming, Survey of indoor positioning systems based on ultra-wideband (UWB) technology, Wireless Communications, Networking and Applications, (2016), 1269–1278.
doi: 10.1007/978-81-322-2580-5_115. |
[16] |
M. Shurman, B. Al Shua'b, M. Alsaedeen, M. F. Al-Mistarihi and K. Darabkh, N-BEB: New backoff algorithm for IEEE 802.11 MAC protocol, In 37th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), (2014), 540–544.
doi: 10.1109/MIPRO.2014.6859627. |
[17] |
IEEE Computer Society, Low-Rate Wireless Personal Area Networks (LR-WPANs), IEEE Standard, 2011. Google Scholar |
[18] |
L. Y. Song, H. L. Zou and T. T. Zhang, A low complexity asynchronous UWB TDOA localization method, International Journal of Distributed Sensor Networks, 11 (2015). Google Scholar |
[19] |
D. Stauffer and D. Sornette,
Log-periodic oscillations for biased diffusion on random lattice, Physica A, 252 (1998), 271-277.
doi: 10.1016/S0378-4371(97)00680-8. |
[20] |
W. Steiner and M. Paulitsch, The transition from asynchronous to synchronous system operation: An approach for distributed fault-tolerant systems, Proceedings 22nd International Conference on Distributed Computing Systemspages, (2002), 329–336.
doi: 10.1109/ICDCS.2002.1022270. |









switching | mean time | quantile | ||||
time |
to connect | 0.9 | 0.95 | 0.99 | 0.999 | |
2 | 2.722 | 5.306 | 7.171 | 12.91 | 25.47 | |
2 | 0.718 | 2.198 | 3.738 | 4.522 | 6.791 | 11.57 |
2 | 0.607 | 2.230 | 3.687 | 4.369 | 6.328 | 10.44 |
2 | 0.534 | 2.321 | 3.732 | 4.344 | 6.089 | 9.730 |
2 | 0.453 | 2.561 | 3.954 | 4.486 | 5.983 | 9.094 |
2 | 0.387 | 3.019 | 4.448 | 4.912 | 6.201 | 8.877 |
1.65 | 2.628 | 4.746 | 6.050 | 9.776 | 17.20 | |
1.65 | 1.008 | 2.321 | 3.782 | 4.439 | 6.213 | 9.634 |
1.65 | 0.838 | 2.361 | 3.748 | 4.313 | 5.825 | 8.729 |
1.65 | 0.777 | 2.408 | 3.775 | 4.307 | 5.719 | 8.428 |
1.65 | 0.677 | 2.563 | 3.916 | 4.390 | 5.637 | 8.017 |
1.65 | 0.573 | 2.940 | 4.325 | 4.737 | 5.805 | 7.833 |
switching | mean time | quantile | ||||
time |
to connect | 0.9 | 0.95 | 0.99 | 0.999 | |
2 | 2.722 | 5.306 | 7.171 | 12.91 | 25.47 | |
2 | 0.718 | 2.198 | 3.738 | 4.522 | 6.791 | 11.57 |
2 | 0.607 | 2.230 | 3.687 | 4.369 | 6.328 | 10.44 |
2 | 0.534 | 2.321 | 3.732 | 4.344 | 6.089 | 9.730 |
2 | 0.453 | 2.561 | 3.954 | 4.486 | 5.983 | 9.094 |
2 | 0.387 | 3.019 | 4.448 | 4.912 | 6.201 | 8.877 |
1.65 | 2.628 | 4.746 | 6.050 | 9.776 | 17.20 | |
1.65 | 1.008 | 2.321 | 3.782 | 4.439 | 6.213 | 9.634 |
1.65 | 0.838 | 2.361 | 3.748 | 4.313 | 5.825 | 8.729 |
1.65 | 0.777 | 2.408 | 3.775 | 4.307 | 5.719 | 8.428 |
1.65 | 0.677 | 2.563 | 3.916 | 4.390 | 5.637 | 8.017 |
1.65 | 0.573 | 2.940 | 4.325 | 4.737 | 5.805 | 7.833 |
[1] |
Yang Liu. Global existence and exponential decay of strong solutions to the cauchy problem of 3D density-dependent Navier-Stokes equations with vacuum. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1291-1303. doi: 10.3934/dcdsb.2020163 |
[2] |
José Luiz Boldrini, Jonathan Bravo-Olivares, Eduardo Notte-Cuello, Marko A. Rojas-Medar. Asymptotic behavior of weak and strong solutions of the magnetohydrodynamic equations. Electronic Research Archive, 2021, 29 (1) : 1783-1801. doi: 10.3934/era.2020091 |
[3] |
Mengting Fang, Yuanshi Wang, Mingshu Chen, Donald L. DeAngelis. Asymptotic population abundance of a two-patch system with asymmetric diffusion. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3411-3425. doi: 10.3934/dcds.2020031 |
[4] |
Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020464 |
[5] |
Tong Tang, Jianzhu Sun. Local well-posedness for the density-dependent incompressible magneto-micropolar system with vacuum. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020377 |
[6] |
Jiannan Zhang, Ping Chen, Zhuo Jin, Shuanming Li. Open-loop equilibrium strategy for mean-variance portfolio selection: A log-return model. Journal of Industrial & Management Optimization, 2021, 17 (2) : 765-777. doi: 10.3934/jimo.2019133 |
[7] |
Wei Feng, Michael Freeze, Xin Lu. On competition models under allee effect: Asymptotic behavior and traveling waves. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5609-5626. doi: 10.3934/cpaa.2020256 |
[8] |
Mugen Huang, Moxun Tang, Jianshe Yu, Bo Zheng. A stage structured model of delay differential equations for Aedes mosquito population suppression. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3467-3484. doi: 10.3934/dcds.2020042 |
[9] |
Qiwei Wu, Liping Luan. Large-time behavior of solutions to unipolar Euler-Poisson equations with time-dependent damping. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021003 |
[10] |
Hui Zhao, Zhengrong Liu, Yiren Chen. Global dynamics of a chemotaxis model with signal-dependent diffusion and sensitivity. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2021011 |
[11] |
Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075 |
[12] |
Yongxiu Shi, Haitao Wan. Refined asymptotic behavior and uniqueness of large solutions to a quasilinear elliptic equation in a borderline case. Electronic Research Archive, , () : -. doi: 10.3934/era.2020119 |
[13] |
Hoang The Tuan. On the asymptotic behavior of solutions to time-fractional elliptic equations driven by a multiplicative white noise. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1749-1762. doi: 10.3934/dcdsb.2020318 |
[14] |
Thazin Aye, Guanyu Shang, Ying Su. On a stage-structured population model in discrete periodic habitat: III. unimodal growth and delay effect. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2021005 |
[15] |
Ran Zhang, Shengqiang Liu. On the asymptotic behaviour of traveling wave solution for a discrete diffusive epidemic model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1197-1204. doi: 10.3934/dcdsb.2020159 |
[16] |
Mohammad Ghani, Jingyu Li, Kaijun Zhang. Asymptotic stability of traveling fronts to a chemotaxis model with nonlinear diffusion. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021017 |
[17] |
Luca Battaglia, Francesca Gladiali, Massimo Grossi. Asymptotic behavior of minimal solutions of $ -\Delta u = \lambda f(u) $ as $ \lambda\to-\infty $. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 681-700. doi: 10.3934/dcds.2020293 |
[18] |
Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304 |
[19] |
Björn Augner, Dieter Bothe. The fast-sorption and fast-surface-reaction limit of a heterogeneous catalysis model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 533-574. doi: 10.3934/dcdss.2020406 |
[20] |
Divine Wanduku. Finite- and multi-dimensional state representations and some fundamental asymptotic properties of a family of nonlinear multi-population models for HIV/AIDS with ART treatment and distributed delays. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021005 |
2019 Impact Factor: 1.366
Tools
Article outline
Figures and Tables
[Back to Top]