
-
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.
|
[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.
|
[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). |
[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). |
[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.
|
[12] |
B.-J. Kwak, N.-O. Song and L. E. Miller,
Performance analysis of exponential backoff, IEEE/ACM Trans. Netw., 13 (2005), 343-355.
|
[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. |
[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). |
[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.
|
[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.
|
[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). |
[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). |
[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.
|
[12] |
B.-J. Kwak, N.-O. Song and L. E. Miller,
Performance analysis of exponential backoff, IEEE/ACM Trans. Netw., 13 (2005), 343-355.
|
[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. |
[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). |
[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] |
Shengzhu Jin, Bong Dae Choi, Doo Seop Eom. Performance analysis of binary exponential backoff MAC protocol for cognitive radio in the IEEE 802.16e/m network. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1483-1494. doi: 10.3934/jimo.2017003 |
[2] |
Chuangxia Huang, Hua Zhang, Lihong Huang. Almost periodicity analysis for a delayed Nicholson's blowflies model with nonlinear density-dependent mortality term. Communications on Pure and Applied Analysis, 2019, 18 (6) : 3337-3349. doi: 10.3934/cpaa.2019150 |
[3] |
Wanbiao Ma, Yasuhiro Takeuchi. Asymptotic properties of a delayed SIR epidemic model with density dependent birth rate. Discrete and Continuous Dynamical Systems - B, 2004, 4 (3) : 671-678. doi: 10.3934/dcdsb.2004.4.671 |
[4] |
Jianwei Yang, Peng Cheng, Yudong Wang. Asymptotic limit of a Navier-Stokes-Korteweg system with density-dependent viscosity. Electronic Research Announcements, 2015, 22: 20-31. doi: 10.3934/era.2015.22.20 |
[5] |
Keng Deng, Yixiang Wu. Asymptotic behavior for a reaction-diffusion population model with delay. Discrete and Continuous Dynamical Systems - B, 2015, 20 (2) : 385-395. doi: 10.3934/dcdsb.2015.20.385 |
[6] |
Dongxue Yan, Xianlong Fu. Asymptotic behavior of a hierarchical size-structured population model. Evolution Equations and Control Theory, 2018, 7 (2) : 293-316. doi: 10.3934/eect.2018015 |
[7] |
Eunju Hwang, Kyung Jae Kim, Bong Dae Choi. Delay distribution and loss probability of bandwidth requests under truncated binary exponential backoff mechanism in IEEE 802.16e over Gilbert-Elliot error channel. Journal of Industrial and Management Optimization, 2009, 5 (3) : 525-540. doi: 10.3934/jimo.2009.5.525 |
[8] |
Zhipeng Qiu, Jun Yu, Yun Zou. The asymptotic behavior of a chemostat model. Discrete and Continuous Dynamical Systems - B, 2004, 4 (3) : 721-727. doi: 10.3934/dcdsb.2004.4.721 |
[9] |
Jishan Fan, Tohru Ozawa. An approximation model for the density-dependent magnetohydrodynamic equations. Conference Publications, 2013, 2013 (special) : 207-216. doi: 10.3934/proc.2013.2013.207 |
[10] |
Giuseppe Da Prato, Arnaud Debussche. Asymptotic behavior of stochastic PDEs with random coefficients. Discrete and Continuous Dynamical Systems, 2010, 27 (4) : 1553-1570. doi: 10.3934/dcds.2010.27.1553 |
[11] |
Chaoying Li, Xiaojing Xu, Zhuan Ye. On long-time asymptotic behavior for solutions to 2D temperature-dependent tropical climate model. Discrete and Continuous Dynamical Systems, 2022, 42 (3) : 1535-1568. doi: 10.3934/dcds.2021163 |
[12] |
Dohyun Kim. Asymptotic behavior of a second-order swarm sphere model and its kinetic limit. Kinetic and Related Models, 2020, 13 (2) : 401-434. doi: 10.3934/krm.2020014 |
[13] |
Sofía Nieto, Guillermo Reyes. Asymptotic behavior of the solutions of the inhomogeneous Porous Medium Equation with critical vanishing density. Communications on Pure and Applied Analysis, 2013, 12 (2) : 1123-1139. doi: 10.3934/cpaa.2013.12.1123 |
[14] |
Meng Liu, Ke Wang. Population dynamical behavior of Lotka-Volterra cooperative systems with random perturbations. Discrete and Continuous Dynamical Systems, 2013, 33 (6) : 2495-2522. doi: 10.3934/dcds.2013.33.2495 |
[15] |
Hunseok Kang. Asymptotic behavior of a discrete turing model. Discrete and Continuous Dynamical Systems, 2010, 27 (1) : 265-284. doi: 10.3934/dcds.2010.27.265 |
[16] |
Genni Fragnelli, A. Idrissi, L. Maniar. The asymptotic behavior of a population equation with diffusion and delayed birth process. Discrete and Continuous Dynamical Systems - B, 2007, 7 (4) : 735-754. doi: 10.3934/dcdsb.2007.7.735 |
[17] |
Cecilia Cavaterra, Maurizio Grasselli. Asymptotic behavior of population dynamics models with nonlocal distributed delays. Discrete and Continuous Dynamical Systems, 2008, 22 (4) : 861-883. doi: 10.3934/dcds.2008.22.861 |
[18] |
Chufen Wu, Dongmei Xiao, Xiao-Qiang Zhao. Asymptotic pattern of a migratory and nonmonotone population model. Discrete and Continuous Dynamical Systems - B, 2014, 19 (4) : 1171-1195. doi: 10.3934/dcdsb.2014.19.1171 |
[19] |
Toshikazu Kuniya, Mimmo Iannelli. $R_0$ and the global behavior of an age-structured SIS epidemic model with periodicity and vertical transmission. Mathematical Biosciences & Engineering, 2014, 11 (4) : 929-945. doi: 10.3934/mbe.2014.11.929 |
[20] |
Francisco Guillén-González, Mamadou Sy. Iterative method for mass diffusion model with density dependent viscosity. Discrete and Continuous Dynamical Systems - B, 2008, 10 (4) : 823-841. doi: 10.3934/dcdsb.2008.10.823 |
2020 Impact Factor: 1.801
Tools
Article outline
Figures and Tables
[Back to Top]