Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-09T06:04:30.156Z Has data issue: false hasContentIssue false
  • English
  • Français

A Random Multiple-Access Protocol with Spatial Interactions

Part of: Discrete mathematics in relation to computer science Special processes Operations research and management science

Published online by Cambridge University Press:  14 July 2016

Charles Bordenave ,
Serguei Foss  and
Vsevolod Shneer
Charles Bordenave*
Affiliation:
University of California
Serguei Foss*
Affiliation:
Heriot-Watt University and Sobolev Institute of Mathematics
Vsevolod Shneer*
Affiliation:
Eindhoven University of Technology and EURANDOM
*
∗Current address: CNRS UMR 5219, Institut de Mathématiques de Toulouse, 118 route de Narbonne, F-31062 Toulouse, France.
∗∗Postal address: Department of Actuarial Mathematics and Statistics, Heriot-Watt University, Edinburgh EH14 4AS, UK.
∗∗∗Postal address: EURANDOM, PO Box 513, 5600 MB Eindhoven, The Netherlands. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We analyse an ALOHA-type random multiple-access protocol where users have local interactions. We show that the fluid model of the system workload satisfies a certain differential equation. We obtain a sufficient condition for the stability of this differential equation and deduce from that a sufficient condition for the stability of the protocol. We discuss the necessary condition. Furthermore, for the underlying Markov chain, we estimate the rate of convergence to the stationary distribution. Then we establish an interesting and unexpected result showing that the main diagonal is locally unstable if the input rate is sufficiently small. Finally, we consider two generalisations of the model.

Keywords

ALOHA protocolspatial interactionstability of processesfluid limits

MSC classification

Secondary: 60K25: Queueing theory 90B15: Network models, stochastic 68R10: Graph theory (including graph drawing)
Type
Research Article
Information
Journal of Applied Probability , Volume 46 , Issue 3 , September 2009 , pp. 844 - 865
Copyright
Copyright © Applied Probability Trust 2009 

References

[1] Abramson, N. (1970). The ALOHA system – another alternative for computer communications. AFIPS Conf. Proc. 36, 295–298.Google Scholar
[2] Coddington, E. A. and Levinson, N. (1955). Theory of Ordinary Differential Equations. McGraw-Hill, New York.Google Scholar
[3] Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limits. Ann. Appl. Prob. 5, 49–77.CrossRefGoogle Scholar
[4] Dai, J. G. and Meyn, S. P. (1995). Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Automatic Control 40, 1889–1904.CrossRefGoogle Scholar
[5] Douc, R., Fort, G., Moulines, E. and Soulier, P. (2004). Practical drift conditions for subgeometric rates of convergence. Ann. Appl. Prob. 3, 1353–1377.Google Scholar
[6] Ephremides, A. and Hajek, B. (1998). Information theory and communication networks: an unconsummated union. IEEE Trans. Inf. Theory 44, 2416–2434.CrossRefGoogle Scholar
[7] Ephremides, A., Nguyen, G. B. and Wieselthier, J. E. (2005). Random access in overlapping cells. In Proc. 11th European Wireless Conf. (Cyprus, April 2005), pp. 659–665.Google Scholar
[8] Feller, W. (1971). An Introduction to Probability Theory and Its Applications, Vol. 2, 2nd edn. John Wiley, New York.Google Scholar
[9] Foss, S. G. (1992). Stochastic recursive sequences and their applications in queueing. , Institute of Mathematics, Novosibirsk, Russia.Google Scholar
[10] Foss, S. and Kovalevskii, A. (1999). A stability criterion via fluid limits and its application to a polling system. Queueing Systems 32, 131–168.CrossRefGoogle Scholar
[11] Hajek, B. (1982). Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Prob. 14, 502–525.CrossRefGoogle Scholar
[12] Meyn, S. P. (1995). Transience of multiclass queueing networks via fluid limit models. Ann. Appl. Prob. 5, 946–957.CrossRefGoogle Scholar
[13] Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability. Springer, London.CrossRefGoogle Scholar
[14] Mikhaĭlov, V. (1988). Geometric analysis of the stability of Markov chains in Rn_+ and its application to the calculation of the capacity of an adaptive random multiple access algorithm. Problems Inform. Transmission 24, 47–56.Google Scholar
[15] Roberts, L. G. (1975). ALOHA packet system with and without slots and capture. Comput. Commun. Rev. 5, 28–42.CrossRefGoogle Scholar
[16] Seneta, E. (1981). Nonnegative Matrices and Markov Chains. Springer, New York.CrossRefGoogle Scholar
[17] Stolyar, A. L. (1995). On the stability of multiclass queueing networks: a relaxed sufficient condition via limiting fluid processes. Markov Process. Relat. Fields 1, 491–512.Google Scholar
[18] Stolyar, A. L. (2008). Dynamic distributed scheduling in random access networks. J. Appl. Prob. 45, 297–313.CrossRefGoogle Scholar