IMPROVED PROPHET ROUTING ALGORITHM

The Delay Tolerant Network paradigm was proposed to address communication issues in challenged environments with sparse intermittent or no end-to-end connectivity. In Vehicular Delay Tolerant networks, some nodes follow a fixed path while others follow a random path.
In our thesis, a new protocol was proposed by making changes in PRoPHET Routing Algorithm to maximize the delivery probability while minimizing the number of messages dropped as well as the overhead ratio.

Introduction to PRoPHET Routing

PRoPHET is a probabilistic routing protocol that uses the history of previous encounters with the other nodes. A probabilistic metric called ‘Delivery Predictability’ P (a, b) is established at every node ‘a’ for each known destination ‘b’. On encounter, nodes exchange the summary vector & probability value for the destination node.
If Delivery Probability of the latter node is better than the former, the message is transmitted.

The DP metric is updated whenever 2 nodes encounter each other, and therefore the nodes that are frequently encountered have a high DP.

P (a, b) = P (a, b)_old + ( 1−P (a, b)_old ) × Pinit
where Pinit is the initialization constant.

The Delivery Predictability ages when a pair of nodes does not encounter each other for a long time.

P (a, b) = P (a, b)_old × γ^k
where γ [0, 1) is the aging constant,
and k is the #time units elapsed since the last time the metric aged.

Proposed Method

In the real world, some nodes move around in predictable path while some nodes tend to move randomly.
Consider this simulation environment where different classes of nodes interact and relay messages.
1. Pedestrians (P)
2. Cars, buses and trucks (C)
3. Trams and trains (T)



Delay tolerant network simulation in One Simulator

The trams and trains use Map-based Mobility for moving in the Simulator and hence have a predictable path; while other groups like pedestrians and cars use Shortest Path Map-based movements, routes for which vary with the destination.
So, the probability of a random node meeting the tram node is higher than that of two random nodes coming into the communication range of each other. Hence, we proposed changing the value of the initialization and the aging constant for the nodes with predictable path to factor in this predictability.

We devided the groups in two sets –
1. Opportunistic: The nodes that do not have a predictable path like pedestrians and cars.
2. Predictable: The nodes that do have a predictable path like the trams.

While Opportunistic nodes use the original constants, the metrics for Predictable group is updated as
P (a, b) = P (a, b)_old + ( 1−P (a, b)_old ) × Pinit_new
P (a, b) = P (a, b)_old × γ_new^k

Pinit_new and γ_new can be derived through a genetic algorithm method involving various simulations, seeded at an interval of 0.01.
Commonly used PRoPHET implementations 0.75 and 0.98 as the initialization & aging constants. Our simulations proved that the delivery probabilities give the best results with 0.85 and 0.99 for predictable groups.

Results

Fig. 1 shows the comparison of Delivery Probability as a function of Bundles Time-to-live
and Fig. 2 shows the comparison of Delivery Probabilities as a function of Buffer size



Overhead is the ratio between the total number of transmissions over the number of delivered messages
Fig. 3 shows the comparison of Overhead as a function of Bundles Time-to-live
and Fig. 4 shows the comparison of Overhead as a function of Buffer size.