A New Approach to the Directed Connectivity in Two-Dimensional Lattice Networks

摘要

The connectivity of ad hoc networks has been extensively studied in the literature. Most recently, researchers model ad hoc networks with two-dimensional lattices and apply percolation theory for connectivity study. On the lattice, given a message source and the bond probability to connect any two neighbor vertices, percolation theory tries to determine the critical bond probability above which a giant connected component appears. This paper studies a related but different problem, directed connectivity: what is the exact probability of the connection from the source to any vertex following certain directions? The existing studies in math and physics only provide approximation or numerical results. In this paper, by proposing a recursive decomposition approach, we can obtain a closed-form polynomial expression of the directed connectivity of square lattice networks as a function of the bond probability. Based on the exact expression, we have explored the impacts of the bond probability and lattice size and ratio on the lattice connectivity, and determined the complexity of our algorithm. Further, we have studied a realistic ad hoc network scenario, i.e., an urban VANET, where we show the capability of our approach on both homogeneous and heterogeneous lattices and how related applications can benefit from our results.