Spatial mean-field limits for ultra-dense random-access networks

F. Cecchi, S.C. Borst, J.S.H. van Leeuwaarden, P.A. Whiting

Research output: Contribution to journalConference articleAcademicpeer-review

Abstract

Random-access algorithms such as the CSMA protocol provide a popular mechanism for distributed medium access control in wireless networks. In saturated-buer scenarios the joint activity process in such random-access networks has a product-form stationary distribution which provides useful throughput estimates for persistent traffic flows. However, these results do not capture the relevant performance metrics in unsaturated-buer scenarios, which in particular arise in an IoT context with highly intermittent traffic sources. Mean-field analysis has emerged as a powerful approach to obtain tractable performance estimates in such situations, and is not only mathematically convenient, but also relevant as wireless networks grow larger and denser with the emergence of IoT applications. A crucial requirement for the classical mean-field framework to apply however is that the node population can be partitioned into a finite number of classes of statistically indistinguishable nodes. The latter condition is a severe restriction since nodes typically have dierent locations and hence experience dierent interference constraints. Motivated by the above observations, we develop in the present paper a novel mean-field methodology which does not rely on any exchangeability property. Since the spatio-temporal evolution of the network can no longer be described through a finite-dimensional population process, we adopt a measure-valued state description, and prove that the latter converges to a deterministic limit as the network grows large and dense. The limit process is characterized in terms of a system of partial-dierential equations, which exhibit a striking local-global-interaction and time scale separation property. Specifically, the queueing dynamics at any given node are only aected by the global network state through a single parsimonious quantity. The latter quantity corresponds to the fraction of time that no activity occurs within the interference range of that particular node in case of a certain static spatial activation measure. Extensive simulation experiments demonstrate that the solution of the partial-dierential equations yields remarkably accurate approximations for the queue length distributions and delay metrics, even when the number of nodes is fairly moderate.

Original languageEnglish
Pages (from-to)123-136
Number of pages14
JournalPerformance Evaluation Review
Volume45
Issue number3
DOIs
Publication statusPublished - 20 Mar 2018
Event35th International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP WG 7.3 Performance 2017) - New York, United States
Duration: 13 Nov 201717 Nov 2017
Conference number: 35
http://performance17.cs.columbia.edu/

Fingerprint

Wireless networks
Carrier sense multiple access
Medium access control
Chemical activation
Throughput
Network protocols
Experiments
Internet of things

Keywords

  • CSMA
  • Mean-field limits
  • Measure-valued state description
  • Random-access networks

Cite this

@article{a023b308eee2468fa101a5751c64f958,
title = "Spatial mean-field limits for ultra-dense random-access networks",
abstract = "Random-access algorithms such as the CSMA protocol provide a popular mechanism for distributed medium access control in wireless networks. In saturated-buer scenarios the joint activity process in such random-access networks has a product-form stationary distribution which provides useful throughput estimates for persistent traffic flows. However, these results do not capture the relevant performance metrics in unsaturated-buer scenarios, which in particular arise in an IoT context with highly intermittent traffic sources. Mean-field analysis has emerged as a powerful approach to obtain tractable performance estimates in such situations, and is not only mathematically convenient, but also relevant as wireless networks grow larger and denser with the emergence of IoT applications. A crucial requirement for the classical mean-field framework to apply however is that the node population can be partitioned into a finite number of classes of statistically indistinguishable nodes. The latter condition is a severe restriction since nodes typically have dierent locations and hence experience dierent interference constraints. Motivated by the above observations, we develop in the present paper a novel mean-field methodology which does not rely on any exchangeability property. Since the spatio-temporal evolution of the network can no longer be described through a finite-dimensional population process, we adopt a measure-valued state description, and prove that the latter converges to a deterministic limit as the network grows large and dense. The limit process is characterized in terms of a system of partial-dierential equations, which exhibit a striking local-global-interaction and time scale separation property. Specifically, the queueing dynamics at any given node are only aected by the global network state through a single parsimonious quantity. The latter quantity corresponds to the fraction of time that no activity occurs within the interference range of that particular node in case of a certain static spatial activation measure. Extensive simulation experiments demonstrate that the solution of the partial-dierential equations yields remarkably accurate approximations for the queue length distributions and delay metrics, even when the number of nodes is fairly moderate.",
keywords = "CSMA, Mean-field limits, Measure-valued state description, Random-access networks",
author = "F. Cecchi and S.C. Borst and {van Leeuwaarden}, J.S.H. and P.A. Whiting",
year = "2018",
month = "3",
day = "20",
doi = "10.1145/3199524.3199545",
language = "English",
volume = "45",
pages = "123--136",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery, Inc",
number = "3",

}

Spatial mean-field limits for ultra-dense random-access networks. / Cecchi, F.; Borst, S.C.; van Leeuwaarden, J.S.H.; Whiting, P.A.

In: Performance Evaluation Review, Vol. 45, No. 3, 20.03.2018, p. 123-136.

Research output: Contribution to journalConference articleAcademicpeer-review

TY - JOUR

T1 - Spatial mean-field limits for ultra-dense random-access networks

AU - Cecchi, F.

AU - Borst, S.C.

AU - van Leeuwaarden, J.S.H.

AU - Whiting, P.A.

PY - 2018/3/20

Y1 - 2018/3/20

N2 - Random-access algorithms such as the CSMA protocol provide a popular mechanism for distributed medium access control in wireless networks. In saturated-buer scenarios the joint activity process in such random-access networks has a product-form stationary distribution which provides useful throughput estimates for persistent traffic flows. However, these results do not capture the relevant performance metrics in unsaturated-buer scenarios, which in particular arise in an IoT context with highly intermittent traffic sources. Mean-field analysis has emerged as a powerful approach to obtain tractable performance estimates in such situations, and is not only mathematically convenient, but also relevant as wireless networks grow larger and denser with the emergence of IoT applications. A crucial requirement for the classical mean-field framework to apply however is that the node population can be partitioned into a finite number of classes of statistically indistinguishable nodes. The latter condition is a severe restriction since nodes typically have dierent locations and hence experience dierent interference constraints. Motivated by the above observations, we develop in the present paper a novel mean-field methodology which does not rely on any exchangeability property. Since the spatio-temporal evolution of the network can no longer be described through a finite-dimensional population process, we adopt a measure-valued state description, and prove that the latter converges to a deterministic limit as the network grows large and dense. The limit process is characterized in terms of a system of partial-dierential equations, which exhibit a striking local-global-interaction and time scale separation property. Specifically, the queueing dynamics at any given node are only aected by the global network state through a single parsimonious quantity. The latter quantity corresponds to the fraction of time that no activity occurs within the interference range of that particular node in case of a certain static spatial activation measure. Extensive simulation experiments demonstrate that the solution of the partial-dierential equations yields remarkably accurate approximations for the queue length distributions and delay metrics, even when the number of nodes is fairly moderate.

AB - Random-access algorithms such as the CSMA protocol provide a popular mechanism for distributed medium access control in wireless networks. In saturated-buer scenarios the joint activity process in such random-access networks has a product-form stationary distribution which provides useful throughput estimates for persistent traffic flows. However, these results do not capture the relevant performance metrics in unsaturated-buer scenarios, which in particular arise in an IoT context with highly intermittent traffic sources. Mean-field analysis has emerged as a powerful approach to obtain tractable performance estimates in such situations, and is not only mathematically convenient, but also relevant as wireless networks grow larger and denser with the emergence of IoT applications. A crucial requirement for the classical mean-field framework to apply however is that the node population can be partitioned into a finite number of classes of statistically indistinguishable nodes. The latter condition is a severe restriction since nodes typically have dierent locations and hence experience dierent interference constraints. Motivated by the above observations, we develop in the present paper a novel mean-field methodology which does not rely on any exchangeability property. Since the spatio-temporal evolution of the network can no longer be described through a finite-dimensional population process, we adopt a measure-valued state description, and prove that the latter converges to a deterministic limit as the network grows large and dense. The limit process is characterized in terms of a system of partial-dierential equations, which exhibit a striking local-global-interaction and time scale separation property. Specifically, the queueing dynamics at any given node are only aected by the global network state through a single parsimonious quantity. The latter quantity corresponds to the fraction of time that no activity occurs within the interference range of that particular node in case of a certain static spatial activation measure. Extensive simulation experiments demonstrate that the solution of the partial-dierential equations yields remarkably accurate approximations for the queue length distributions and delay metrics, even when the number of nodes is fairly moderate.

KW - CSMA

KW - Mean-field limits

KW - Measure-valued state description

KW - Random-access networks

UR - http://www.scopus.com/inward/record.url?scp=85046656951&partnerID=8YFLogxK

U2 - 10.1145/3199524.3199545

DO - 10.1145/3199524.3199545

M3 - Conference article

AN - SCOPUS:85046656951

VL - 45

SP - 123

EP - 136

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 3

ER -