More Web Proxy on the site http://driver.im/

research-article

Estimating the Transmission Probability in Wireless Networks with Configuration Models

Authors:

Paola Bermolen,

Matthieu Jonckheere,

Federico Larroca,

Pascal MoyalAuthors Info & Claims

ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), Volume 1, Issue 2

Article No.: 9, Pages 1 - 23

https://doi.org/10.1145/2858795

Published: 21 April 2016 Publication History

Abstract

We propose a new methodology to estimate the probability of successful transmissions for random access scheduling in wireless networks, in particular those using Carrier Sense Multiple Access (CSMA). Instead of focusing on spatial configurations of users, we model the interference between users as a random graph. Using configuration models for random graphs, we show how the properties of the medium access mechanism are captured by some deterministic differential equations when the size of the graph gets large. Performance indicators such as the probability of connection of a given node can then be efficiently computed from these equations. We also perform simulations to illustrate the results on different types of random graphs. Even on spatial structures, these estimates get very accurate as soon as the variance of the interference is not negligible.

References

[1]

François Baccelli and Bartlomiej Blaszczyszyn. 2009a. Stochastic geometry and wireless networks, volume 1: Theory. Foundations and Trends in Networking 3, 3--4 (2009), 249--449.

Digital Library

[2]

François Baccelli and Bartlomiej Blaszczyszyn. 2009b. Stochastic geometry and wireless networks, volume 2: Applications. Foundations and Trends in Networking 4, 1--2 (2009), 1--312. 10.1561/1300000026

Digital Library

[3]

Paola Bermolen, Matthieu Jonckheere, and Pascal Moyal. 2013. The Jamming Constant of Random Graphs. (2013). http://arxiv.org/abs/1310.8475 Submitted.

[4]

G. Bianchi. 2000. Performance analysis of the IEEE 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communications 18, 3 (September 2000), 535--547. 10.1109/49.840210

Digital Library

[5]

B. Bollobas. 2001. Random Graphs. Cambridge University Press, Cambridge, UK.

[6]

Charles Bordenave, David McDonald, and Alexandre Proutiere. 2012. Asymptotic stability region of slotted Aloha. IEEE Transactions on Information Theory 58, 9 (2012), 5841--5855.

Digital Library

[7]

S. C. Borst, M. Jonckheere, and L. Leskelä. 2008. Stability of parallel queueing systems with coupled service rates. Discrete Event Dynamic Systems 18, 4 (2008), 447--472.

Digital Library

[8]

Pierre Bremaud. 1999. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, New York.

[9]

F. Cecchi, S. C. Borst, and J. S. H. van Leeuwaarden. 2014. Throughput of CSMA networks with buffer dynamics. Performance Evaluation 79, 0 (2014), 216--234. Special Issue: Performance 2014.

[10]

D. A. Dawson 1991. Measure-Valued Processes, Stochastic Partial Differential Equations, and Interacting Systems. Vol. 5. American Mathematical Society, Providence, Rhode Island.

[11]

R. Durrett. 2007. Random Graph Dynamics. Cambridge University Press, Cambridge, UK.

Digital Library

[12]

M. Durvy and P. Thiran. 2006. A packing approach to compare slotted and non-slotted medium access control. In Proceedings of the 25th IEEE International Conference on Computer Communications. Proceedings (INFOCOM 2006). IEEE, Barcelona, Spain, 1--12.

[13]

Dave Evans. 2011. The Internet of Things: How the Next Evolution of the Internet Is Changing Everything. Technical Report. Cisco. http://www.cisco.com/web/about/ac79/docs/innov/IoT_IBSG_0411FINAL.pdf.

[14]

P. Gupta and P. R. Kumar. 2000. The capacity of wireless networks. IEEE Transactions on Information Theory 46, 2 (Mar 2000), 388--404.

Digital Library

[15]

IEEE. 2012. 802.11-2012 - IEEE Standard for information technology--Telecommunications and information exchange between systems. Local and metropolitan area networks--Specific requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. (2012).

[16]

Federico Larroca and Fernanda Rodríguez. 2014. An overview of WLAN performance, some important case-scenarios and their associated models. Wireless Personal Communications 79, 1 (2014), 1--54.

Digital Library

[17]

M. Molloy and B. Reed. 1995. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms 6 (1995), 161--180.

Digital Library

[18]

H. Q. Nguyen, F. Baccelli, and D. Kofman. 2007. A stochastic geometry analysis of dense IEEE 802.11 networks. In Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM 2007). IEEE, Anchorage, 1199--1207.

[19]

M. D. Penrose. 2001. Random parking, sequential adsorption, and the jamming limit. Communications in Mathematical Physics 218, 1 (2001), 153--176.

[20]

M. D. Penrose and A. Sudbury. 2005. Exact and approximate results for deposition and annihilation processes on graphs. Annals of Applied Probability 15, 1B (2005), 853--889.

[21]

Dietrich Stoyan and Helga Stoyan. 1985. On one of Matérn’s hard-core point process models. Mathematische Nachrichten 122, 1 (1985), 205--214.

[22]

Wojciech Szpankowski. 1983. Packet switching in multiple radio channels: Analysis and stability of a random access system. Computer Networks 7 (1983), 17--26.

[23]

Remco van der Hofstad. 2013. Random Graphs and Complex Networks. (2013). Lecture Notes.

[24]

Nguyen Tien Viet and François Baccelli. 2012a. Generating Functionals of Random Packing Point Processes: From Hard-Core to Carrier Sensing. (2012). http://arxiv.org/abs/1202.0225.

[25]

Nguyen Tien Viet and François Baccelli. 2012b. On the spatial modeling of wireless networks by random packing models. In Proceedings of the IEEE INFOCOM 2012. IEEE, Orlando, 28--36.

[26]

Nicholas C. Wormald. 1995. Differential equations for random processes and random graphs. Annals of Applied Probability 5, 4 (1995), 1217--1235.

[27]

Nicholas C. Wormald. 1999. Models of Random Regular Graphs. Cambridge University Press, Cambridge, UK, 239--298.

Cited By

Aoudi MMoyal PRobin V(2022)Markovian Online Matching Algorithms on Large Bipartite Random GraphsMethodology and Computing in Applied Probability10.1007/s11009-022-09973-y24:4(3195-3225)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11009-022-09973-y
Rattaro CAspirot LMordecki EBelzarena P(2020)QoS Provision in a Dynamic Channel Allocation Based on Admission Control DecisionsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33727865:1(1-29)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3372786
González-Ambriz SRivero Angeles MMenchaca-Méndez RMenchaca-Méndez R(2019)Control de Acceso al Medio basado en Entropía para S-ALOHA en Redes Inalámbricas Ad-HocRevista Iberoamericana de Automática e Informática industrial10.4995/riai.2018.1039816:2(178)Online publication date: 20-Mar-2019
https://doi.org/10.4995/riai.2018.10398
Show More Cited By

Index Terms

Estimating the Transmission Probability in Wireless Networks with Configuration Models
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Random graphs
  2. Probability and statistics
    1. Stochastic processes
2. Networks
  1. Network performance evaluation
    1. Network performance analysis
    2. Network performance modeling

Recommendations

Performance of multichannel wireless ad hoc networks

This paper addresses the design of Medium Access Control (MAC) protocols for wireless ad hoc networks that derive benefits from using multiple orthogonal channels for data transmission. Each node is assumed to have a single half-duplex transceiver that ...
Sequencing technique: an enhancement to 802.11 medium access control to improve the performance of wireless networks

This paper presents a technique known as sequencing on MAC layer for wireless networks. MAC layer issues are very important while accessing channel over wireless networks. Normally, communication uses Request To Send/Clear To Send (RTS/CTS) mechanism to ...
CSMA/IC: a new paradigm for medium access control in wireless LANs and ad hoc wireless networks

In this paper, we present a new Medium Access Control (MAC) protocol Carrier Sense Medium Access/ID Countdown (CSMA/IC) for multihop ad hoc wireless networks that differs from CSMA/CA. CSMA/IC can achieve virtually 100% collision-free performance by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Performance Evaluation of Computing Systems

ACM Transactions on Modeling and Performance Evaluation of Computing Systems Volume 1, Issue 2

June 2016

112 pages

ISSN:2376-3639

EISSN:2376-3647

DOI:10.1145/2928293

Editors:
Don Towsley
University of Massachusetts--Amherst, USA
,
Carey Williamson
University of Calgary, Canada

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 April 2016

Accepted: 01 December 2015

Revised: 01 October 2015

Received: 01 November 2014

Published in TOMPECS Volume 1, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
165
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)3

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aoudi MMoyal PRobin V(2022)Markovian Online Matching Algorithms on Large Bipartite Random GraphsMethodology and Computing in Applied Probability10.1007/s11009-022-09973-y24:4(3195-3225)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11009-022-09973-y
Rattaro CAspirot LMordecki EBelzarena P(2020)QoS Provision in a Dynamic Channel Allocation Based on Admission Control DecisionsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33727865:1(1-29)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3372786
González-Ambriz SRivero Angeles MMenchaca-Méndez RMenchaca-Méndez R(2019)Control de Acceso al Medio basado en Entropía para S-ALOHA en Redes Inalámbricas Ad-HocRevista Iberoamericana de Automática e Informática industrial10.4995/riai.2018.1039816:2(178)Online publication date: 20-Mar-2019
https://doi.org/10.4995/riai.2018.10398
Rattaro CLarroca FBermolen PBelzarena P(2017)Estimating the medium access probability in large cognitive radio networksAd Hoc Networks10.1016/j.adhoc.2017.05.00363(1-13)Online publication date: Aug-2017
https://doi.org/10.1016/j.adhoc.2017.05.003
Bermolen PJonckheere MSanders J(2017)Scaling Limits and Generic Bounds for Exploration ProcessesJournal of Statistical Physics10.1007/s10955-017-1902-z169:5(989-1018)Online publication date: 27-Oct-2017
https://doi.org/10.1007/s10955-017-1902-z

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents