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  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 & 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.   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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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]

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]

Copyright © 2020 American Institute of Mathematical Sciences