Percolation and connectivity in the intrinsically secure communications graph

Abstract—The ability to exchange secret information is critical to many commercial, governmental, and military networks. The intrinsically secure communications graph (-graph) is a random graph which describes the connections that can be securely estab-lished over a large-scale network, by exploiting the physical prop-erties of the wireless medium. This paper aims to characterize the global properties of the -graph in terms of 1) percolation on the infinite plane, and 2) full connectivity on a finite region. First, for the Poisson -graph defined on the infinite plane, the existence of a phase transition is proven, whereby an unbounded component of connected nodes suddenly arises as the density of legitimate nodes is increased. This shows that long-range secure communication is still possible in the presence of eavesdroppers. Second, full connec-tivity on a finite region of the Poisson -graph is considered. The exact asymptotic behavior of full connectivity in the limit of a large density of legitimate nodes is characterized. Then, simple, explicit expressions are derived in order to closely approximate the prob-ability of full connectivity for a finite density of legitimate nodes. These results help clarify how the presence of eavesdroppers can compromise long-range secure communication. Index Terms—Connectivity, percolation, physical-layer security, stochastic geometry, wireless networks