Efficient multi-hop connectivity analysis in urban vehicular networks

Vehicle to Vehicle (V2V) communication provides a flexible and real-time information dissemination mechanism through various applications of Intelligent Transportation Systems (ITS). Achieving seamless connectivity through multi-hop vehicular communication with sparse network is a challenging issue. In this paper, we have studied this multi-hop vehicular connectivity in an urban scenario using GPS traces obtained from San Francisco Yellow cabs. Our current work describes a new algorithm for the analysis of topological properties like connectivity and partitions for any kind of vehicular or mobile computing environment. The novel approach uses bitwise manipulation of sparse matrix with an efficient storage technique for determining multi-hop connectivity. The computation mechanism can be further scaled to parallel processing environment. The main contribution of this research is threefold. First, developing an efficient algorithm to quantify multi-hop connectivity with the aid of bitwise manipulation of sparse matrix. Second, investigating the time varying nature of multi-hop vehicular connectivity and dynamic network partitioning of the topology. Third, deriving a mathematical model for calculating message propagation rate in an urban environment.