Complex Network Analysis of VANET Topology With Realistic Vehicular Traces

Recent years have witnessed growing interests in vehicular ad hoc network (VANET) topology. Existing works assume that the networks generated at each time are independent. In these works, the VANET topologies are formed based on simple traffic and communication models such as unit disk graph model. Interestingly, some works find that VANETs are scale-free ones characterized by strong connectivity and survivability, while some argue that they are not. This study analyzes VANETs in more realistic settings, trying to find the answer to the paradox. Specifically, in this paper we propose a Dynamically Evolving Networking (DEN) model and take as input realistic vehicular traces to make the research and results more practical. We consider the effect of node addition, node deletion and link loss due to node mobility and keep the network evolving by including preferential attachment and link compensation mechanisms. We find that the evolved VANET exhibits a scale-invariant feature under certain conditions. We also find that the emergence of such phenomenon has no relation to communication range if the range is large. Furthermore, we apply complex network theory to capture the dynamics of the VANET. Theoretically for the first time we show that VANET would evolve into the scale-free topology when the probability of node addition is relatively large or the probability of link compensation is properly set, the presence of which would help establish a strongly connected VANET topology.