×

Mean-field analysis of a scaling MAC radio protocol. (English) Zbl 1476.90076

Summary: 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.

MSC:

90B18 Communication networks in operations research
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
68U35 Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.)
90B20 Traffic problems in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.-L. Barabási; R. Albert; H. Jeong, Mean-field theory for scale-free random networks, Physica A: Statistical Mechanics and its Applications, 272, 173-187 (1999)
[2] G. Ben Arous; A. Fribergh; N. Gantert; Al an Hammond, Biased random walks on Galton-Watson trees with leaves, Ann. Probab., 40, 280-338 (2012) · Zbl 1239.60091 · doi:10.1214/10-AOP620
[3] J. I. Capetanakis, Tree algorithms for packet broadcast channels, IEEE Transactions on Information Theory, 25, 505-515 (1979) · Zbl 0414.94019 · doi:10.1109/TIT.1979.1056093
[4] V. Claesson; H. Lonn; N. Suri, An efficient TDMA start-up and restart synchronization approach for distributed embedded systems, IEEE Transactions on Parallel and Distributed Systems, 15, 725-739 (2004)
[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. · Zbl 0592.60049
[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; S. R. S. Varadhan, Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions, Comm. Math. Phys., 104, 1-19 (1986) · Zbl 0588.60058 · 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. · Zbl 1396.60002
[10] T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes, Journal of Applied Probability, 7, 49-58 (1970) · Zbl 0191.47301 · doi:10.2307/3212147
[11] B.-J. Kwak; N.-O. Song; L. E. Miller, On the stability of exponential backoff, Journal of research of the National Institute of Standards and Technology, 108, 289-297 (2003)
[12] B.-J. Kwak; N.-O. Song; L. E. Miller, Performance analysis of exponential backoff, IEEE/ACM Trans. Netw., 13, 343-355 (2005)
[13] V. Bansaye and S. Méléard, Stochastic Models for Structured Populations: Scaling Limits and Long Time Behavior, Springer International Publishing, 2015. · Zbl 1333.92004
[14] Y. Shen; H. Wymeersch; M. Z. Win, Fundamental limits of wideband localization-part II: Cooperative networks, IEEE Trans. Inform. Theory, 56, 4981-5000 (2010) · Zbl 1366.94417 · 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.
[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.
[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; D. Sornette, Log-periodic oscillations for biased diffusion on random lattice, Physica A, 252, 271-277 (1998) · 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.