
-
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] |
Linlin Li, Bedreddine Ainseba. Large-time behavior of matured population in an age-structured model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2561-2580. doi: 10.3934/dcdsb.2020195 |
[2] |
Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055 |
[3] |
M. Grasselli, V. Pata. Asymptotic behavior of a parabolic-hyperbolic system. Communications on Pure & Applied Analysis, 2004, 3 (4) : 849-881. doi: 10.3934/cpaa.2004.3.849 |
[4] |
Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493 |
[5] |
Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53 |
[6] |
Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258 |
[7] |
Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034 |
[8] |
Seung-Yeal Ha, Jinwook Jung, Jeongho Kim, Jinyeong Park, Xiongtao Zhang. A mean-field limit of the particle swarmalator model. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021011 |
[9] |
Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931 |
[10] |
Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269 |
[11] |
Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $ \Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109 |
[12] |
Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206 |
[13] |
Simone Calogero, Juan Calvo, Óscar Sánchez, Juan Soler. Dispersive behavior in galactic dynamics. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 1-16. doi: 10.3934/dcdsb.2010.14.1 |
[14] |
Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 |
[15] |
Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365 |
[16] |
Jon Aaronson, Dalia Terhesiu. Local limit theorems for suspended semiflows. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6575-6609. doi: 10.3934/dcds.2020294 |
[17] |
Brandy Rapatski, James Yorke. Modeling HIV outbreaks: The male to female prevalence ratio in the core population. Mathematical Biosciences & Engineering, 2009, 6 (1) : 135-143. doi: 10.3934/mbe.2009.6.135 |
[18] |
Elena Bonetti, Pierluigi Colli, Gianni Gilardi. Singular limit of an integrodifferential system related to the entropy balance. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1935-1953. doi: 10.3934/dcdsb.2014.19.1935 |
[19] |
Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems - A, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25 |
[20] |
Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]