Efficient message dissemination in vehicular ad-hoc networks (VANETs) is crucial for supporting communication among vehicles and also between users and the Internet, with minimal delay and overhead but maximum reachability. To improve the message dissemination in these networks, we show the need to study the graph-theoretic properties of VANETs, since they neither follow the small-world nor the scale-free network characteristics often found in large self-organized networks. We consider three fundamental properties: connectivity, node degree, and clustering coefficient. For each property, we develop and validate analytical models for both the urban and highway scenarios, building an extensive graph structure perspective on VANETs. With this, we see how connectivity changes with network density, that VANETs exhibit truncated Gaussian node degree distributions, and that network clustering coefficients do not depend on the network’s size or density. We then show how these results can be used to generate individual behavior favorable to the whole network using local information. The usefulness of this new approach is demonstrated by proposing new mechanisms to enhance the urban vehicular broadcasting protocol UV-CAST. Our results show that these new mechanisms lead to excellent performance while reducing the overhead in the UV-CAST protocol.
