Article Contents
Article Contents

# Mean-field analysis of a scaling MAC radio protocol

• * Corresponding author

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.

Mathematics Subject Classification: Primary: 68M20, 60J20; Secondary: 90B20.

 Citation:

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

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

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 4.  Early rapid transition: $z_i(t)$ for values of $i$ considerably smaller than 0 ($\alpha = 0$ and $\gamma = 2$)

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

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

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

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

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

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

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

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 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$

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
•  [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.

Figures(13)

Tables(1)