Efficient routing through discretization of overlapped road segments in VANETs

Routing in vehicular ad-hoc networks (VANETs) is based on the contacts through vehicle-to-vehicle communications. Due to the high probability and long duration, contacts on the overlapped trajectories among vehicles play an important role during routing. However, both the stochastic vehicular mobilities and non-ignorable road distances lead to high spatio-temporal fluctuations for the probabilistic contacts on the overlapped trajectories, which can diversify routing decisions. In this paper, we propose a novel Sampling-based Estimation Scheme (SES), which discretizes the probabilistic contacts on the overlapped roads into a small number of segments, and abstracts each segment as a sample. The contact duration between two vehicles moving in opposite directions on their overlapped road is lower, but their contact probability is higher. By contrast, the duration of the contact between two vehicles moving in the same direction on their overlapped road is higher, but their contact probability is lower. The proposed SES can achieve efficient routing by considering the above properties of stochastic contacts. Furthermore, we investigate the content transmission among the probabilistic contacts, through the flow model with probabilistic capacities. Extensive experiments validate the competitive performance of the proposed SES with the probabilistic contacts in VANETs.