5th International Workshop on Spatial Stochastic Models for Wireless Networks

Research Article

Finite Random Geometric Graphs by Circular and Square Coverage

  • @INPROCEEDINGS{10.1109/WIOPT.2009.5291570,
        author={Chi-Kin Chau},
        title={Finite Random Geometric Graphs by Circular and Square Coverage},
        proceedings={5th International Workshop on Spatial Stochastic Models for Wireless Networks},
        publisher={IEEE},
        proceedings_a={SPASWIN},
        year={2009},
        month={10},
        keywords={Random Geometric Graphs Connectivity Coverage},
        doi={10.1109/WIOPT.2009.5291570}
    }
    
  • Chi-Kin Chau
    Year: 2009
    Finite Random Geometric Graphs by Circular and Square Coverage
    SPASWIN
    IEEE
    DOI: 10.1109/WIOPT.2009.5291570
Chi-Kin Chau1,*
  • 1: University of Cambridge & University College London, UK
*Contact email: Chi-Kin.Chau@cl.cam.ac.uk

Abstract

Random geometric graphs are widely-used for modelling wireless ad hoc networks, where nodes are randomly deployed with each covering a finite region. The fundamental properties of random geometric graphs are often studied in the literature, such as the probability of connectivity and random coverage area. While there are numerous asymptotic results that concern the related scaling laws in very large random geometric graphs, more accurate estimation for the finite cases with moderate-sized networks remains challenging. In this paper, we present a remarkably good approximation relationship for the probability of connectivity and random coverage area between the random geometric graphs induced by circular and square coverage models, under suitable normalisation. We also provide analytical results towards justifying the good approximation relationship. This relationship is then exploited, combining with the results from reliability studies, to obtain more accurate estimation for the probability of connectivity in finite random geometric graphs.