American Institute of Mathematical Sciences

Advanced
  • 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
January  2021, 17(1): 279-297. doi: 10.3934/jimo.2019111

Mean-field analysis of a scaling MAC radio protocol

Illés Horváth 1,, , Kristóf Attila Horváth 2, , Péter Kovács 1, and  Miklós Telek 3,

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

* Corresponding author

Received  November 2018 Revised  May 2019 Published  January 2021 Early access  September 2019

Fund Project: This work is supported by the OTKA 123914 project and the TUDFO/51757/2019-ITM grants

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.

Keywords: Population model, density dependent behavior, asymptotic limit, log-periodicity, positioning, ultra wideband, MAC, random access channel, exponential backoff.
Mathematics Subject Classification: Primary: 68M20, 60J20; Secondary: 90B20.
Citation: Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial and Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111
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.

Figure 1.  State transitions of a single user; $ p_i $ are constant, $ c_i $ depend on other users
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Convergence of $ w_0(t) $ and $ w_1(t) $ when $ \alpha $ is fixed and $ L\to\infty $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Simulation for $ N_{L+i}(Nt)/N $ versus numerical solution for $ z_i(t) $ for $ i = 0, 1, 2 $ (parameters are $ N = 2^{10}, \gamma = 2, L = 10, \alpha = 0 $)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Early rapid transition: $ z_i(t) $ for values of $ i $ considerably smaller than 0 ($ \alpha = 0 $ and $ \gamma = 2 $)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  The functions $ z(\gamma, \alpha, t) $ for $ \gamma = 20 $ and $ \alpha = 0 $ (thick line), $ 1/10, \dots, 9/10 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  The functions $ z(\gamma, \alpha, t) $ for $ \gamma = 2 $ and $ \alpha = 0, 1/10, \dots, 9/10 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  The values $ z_i(2, \alpha, 1) $ for $ \alpha = 0, 1/20, \dots, 19/20 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  The values $ z_i(20, \alpha, 1) $ for $ \alpha = 0, 1/20, \dots, 19/20 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  Mean of the scaled connection time for $ \gamma=20 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 10.  Mean of the scaled connection time for $ \gamma=2 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 11.  Mean of the scaled connection time as a function of $ \gamma $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 12.  Simulation for $1-\bar N_0(Nt)/N $ (red line) versus $\bar z(t) $ (dashed blue line); parameters are $ N=2^{10},\gamma=2,L=10,\alpha=0,t_0=0.5$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 13.  $z(t)$ (no switching, black line) versus $\bar z(t) $ (switching at time $t_0=0.72 $, optimal for $m_z $, dotted red line) versus $ \bar z'(t)$ (switching at time $ t_0=0.39$, optimal for the 99.9% quantile, dashed blue line). Parameters are $\gamma=2,L=10,\alpha=0 $
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Optimization of the switching time for a prescribed quantile ($ \alpha = 0 $)
switching mean time quantile
$ \gamma $ time $ t_0 $ to connect 0.9 0.95 0.99 0.999
2 $ \infty $ 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 $ \infty $ 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
Table Options

Download as excel

switching mean time quantile
$ \gamma $ time $ t_0 $ to connect 0.9 0.95 0.99 0.999
2 $ \infty $ 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 $ \infty $ 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]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy