research-article

Connectivity in obstructed wireless networks: from geometry to percolation

Authors:

Marcelo G. Almiron,

Olga Goussevskaia,

Antonio A.F. Loureiro,

Jose RolimAuthors Info & Claims

MobiHoc '13: Proceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing

Pages 157 - 166

https://doi.org/10.1145/2491288.2491306

Published: 29 July 2013 Publication History

Abstract

In this work, we analyze an alternative model for obstructed wireless networks. The model is based on a grid structure of one-dimensional street segments and two-dimensional street intersections. This structure provides a realistic representation of a variety of network scenarios with obstacles and, at the same time, allows a simple enough analysis, which is partly based on percolation theory and partly based on geometric properties. We propose three different ways of modeling the geometric part of the network and derive analytical bounds for the connectivity probability and the critical transmission range for connectivity in the network. Finally, we present extensive simulations that demonstrate that our analytical results provide good approximations, especially for high density scenarios.

References

[1]

M. G. Almiron, O. Goussevskaia, A. C. Frery, and A. A. Loureiro. Modeling and connectivity analysis in obstructed wireless ad hoc networks. In Proceedings of the 15th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), pages 195--202, 2012.

Digital Library

[2]

B. Bollobás, S. Janson, and O. Riordan. Line-of-sight percolation. Combinatorics, Probability & Computing, 18(1--2):83--106, 2009.

Digital Library

[3]

O. Dousse, P. Thiran, and M. Hasler. Connectivity in ad-hoc and hybrid networks. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), volume 2, pages 1079--1088, 2002.

[4]

M. Franceschetti and R. Meester. Random Networks for Communication: From Statistical Physics to Information Systems. Statistical and Probabilistic Mathematics. Cambridge University Press, 2007.

[5]

A. M. Frieze, J. M. Kleinberg, R. Ravi, and W. Debany. Line-of-sight networks. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 968--977, 2007.

Digital Library

[6]

A. Ghasemi and S. Nader-Esfahani. Exact probability of connectivity in one-dimensional ad hoc wireless networks. IEEE Communications Letters, 10(4):251--253, 2006.

[7]

O. Goussevskaia, M. M. Halldàrsson, R. Wattenhofer, and E. Welzl. Capacity of arbitrary wireless networks. In Proceedings of the 32nd IEEE International Conference on Computer Communications (INFOCOM), pages 1872--1880, 2009.

[8]

G. Grimmett. Percolation. Springer-Verlag, second edition, 1999.

[9]

P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming, pages 547--566, 1998.

[10]

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

Digital Library

[11]

M. Haenggi and R. K. Ganti. Interference in large wireless networks. Foundations and Trends in Networking, 3(2):127--248, 2009.

Digital Library

[12]

R. Meester and R. Roy. Continuum percolation. Cambridge tracts in mathematics. Cambridge University Press, 1996.

[13]

M. Nekoui and H. Pishro-Nik. A geometrical analysis of obstructed wireless networks. In Proceedings of the IEEE Information Theory Workshop (ITW), pages 589--593, 2009.

[14]

M. Penrose. Random geometric graphs. Oxford studies in probability. Oxford University Press, 2003.

[15]

M. D. Penrose. On k-connectivity for a geometric random graph. Random Structures & Algorithms, 15(2):145--164, Sep 1999.

Digital Library

[16]

P. Santi and D. Blough. The critical transmitting range for connectivity in sparse wireless ad hoc networks. IEEE Transactions on Mobile Computing, 2(1):25--39, 2003.

Digital Library

[17]

S. Shakkottai, R. Srikant, and N. Shro. Unreliable sensor grids: Coverage, connectivity and diameter. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), volume 2, pages 1073--1083, 2003.

Cited By

Bian CZhao TLi XYan W(2015)Boosting named data networking for efficient packet forwarding in urban VANET scenariosThe 21st IEEE International Workshop on Local and Metropolitan Area Networks10.1109/LANMAN.2015.7114718(1-6)Online publication date: Apr-2015
https://doi.org/10.1109/LANMAN.2015.7114718
Giles AGeorgiou ODettmann C(2015)Connectivity of Soft Random Geometric Graphs over AnnuliJournal of Statistical Physics10.1007/s10955-015-1436-1162:4(1068-1083)Online publication date: 29-Dec-2015
https://doi.org/10.1007/s10955-015-1436-1
Bian CZhao TLi XDu XYan W(2015)Theoretical analysis on caching effects in urban vehicular ad hoc networksWireless Communications and Mobile Computing10.1002/wcm.265116:13(1759-1772)Online publication date: 25-Nov-2015
https://doi.org/10.1002/wcm.2651
Show More Cited By

Index Terms

Connectivity in obstructed wireless networks: from geometry to percolation
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Modeling and connectivity analysis in obstructed wireless ad hoc networks
MSWiM '12: Proceedings of the 15th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems

Connectivity properties of wireless networks in open space are typically modeled using geometric random graphs and have been analyzed in depth in different studies. Such scenarios, however, do not often represent situations encountered in practice, like ...
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 ...
On high-throughput and fair multi-hop wireless ad hoc networks with MIMO
Mobility '06: Proceedings of the 3rd international conference on Mobile technology, applications & systems

Nowadays, the prevalence of multimedia applications mandates that wireless networks provide higher throughput and increased spatial efficiency. Aimed primarily at achieving this goal, the first IEEE 802.11n draft was recently approved. In the draft, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '13: Proceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing

July 2013

322 pages

ISBN:9781450321938

DOI:10.1145/2491288

General Chairs:
A. Chockalingam
IISc Bangalore
,
D. Manjunath
IIT Bombay
,
Program Chairs:
Massimo Franceschetti
University of California, San Diego
,
Leandros Tassiulas
University of Thessaly

Copyright © 2013 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 the author(s) 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].

Sponsors

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiHoc '13

Sponsor:

SIGMOBILE

MobiHoc '13: The Fourteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing

July 29 - August 1, 2013

Bangalore, India

Acceptance Rates

MobiHoc '13 Paper Acceptance Rate 42 of 234 submissions, 18%;

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
360
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bian CZhao TLi XYan W(2015)Boosting named data networking for efficient packet forwarding in urban VANET scenariosThe 21st IEEE International Workshop on Local and Metropolitan Area Networks10.1109/LANMAN.2015.7114718(1-6)Online publication date: Apr-2015
https://doi.org/10.1109/LANMAN.2015.7114718
Giles AGeorgiou ODettmann C(2015)Connectivity of Soft Random Geometric Graphs over AnnuliJournal of Statistical Physics10.1007/s10955-015-1436-1162:4(1068-1083)Online publication date: 29-Dec-2015
https://doi.org/10.1007/s10955-015-1436-1
Bian CZhao TLi XDu XYan W(2015)Theoretical analysis on caching effects in urban vehicular ad hoc networksWireless Communications and Mobile Computing10.1002/wcm.265116:13(1759-1772)Online publication date: 25-Nov-2015
https://doi.org/10.1002/wcm.2651
Almiron MGoussevskaia OFrery ALoureiro A(2014)Connectivity at crossroads2014 IEEE 25th Annual International Symposium on Personal, Indoor, and Mobile Radio Communication (PIMRC)10.1109/PIMRC.2014.7136394(1437-1441)Online publication date: Sep-2014
https://doi.org/10.1109/PIMRC.2014.7136394

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents