Evaluation of Dissimilarity-based Probabilistic Broadcasting Algorithms in VANETs

Broadcasting is an important dissemination mechanism in VANETs. It is widely used to spread out critical information among vehicles such as warning messages, traffic accident related information, and alternative traffic routes, among others. Although many broadcasting approaches have been proposed in the literature, none of them is the most optimal; since optimal algorithms such as connected dominated set or minimum spanning trees are NP-hard problems that cannot be solved without utilizing global information. Probabilistic algorithms are an attractive alternative in which nodes determine the forwarding probability based on local topological parameters. Among the possible parameters to be used, the Euclidean distance is one of the preferred. However, the Euclidean based approaches have some limitations. For instance, most of them determine the forwarding probability as the ratio between the relative Euclidean distance between two nodes and the node's radio transmission range. Nevertheless, knowing the real transmission range of nodes is an assumption that does not hold in real scenarios for several factors that cannot be controlled such as density of nodes, obstacles, interferences, etc. In this paper, we propose the use of dissimilarity metrics based on the relationships between the node's neighbors to determine the forwarding probability. We adapt several popular probabilistic algorithms based on the Euclidean distance to use dissimilarity metrics. The resulting algorithms do not have the limitations of the original ones. Finally, we evaluate the proposed algorithms in urban scenarios and compare their results with the results of other well-known approaches.