Probabilistic quota based adaptive routing in opportunistic networks

Abstract

Routing in an Opportunistic Network (OpNet) is challenging due to the absence of a complete end-to-end path from a source to a destination. Consequently, OpNet routing protocols use store and forward routing with multiple replicas of a message in the network to achieve higher delivery ratio. Although °ooding the network with many copies of a message improves the chances of message delivery, it causes higher network contention. Quota based routing protocols deal with this problem by placing an upper bound on the number of replicas per message in the network. However, this saving in terms of valuable network resources comes at the cost of delivery performance. In this thesis, we propose two novel quota based routing protocols, TBR and Pro- bRoute, which use the network resources e±ciently and achieves delivery ratios as high as that of the °ooding based protocols. TBR prioritizes both the schedule of messages to be forwarded to the neighbor and the schedule of messages to be dropped from the bu®er. These priorities are based on massage time to live (TTL), message hop count, message replication factor and message size. The TTL based message priority enhances the chance of message delivery by preferring to the messages with the earliest deadline. ProbRoute introduces a weighted probability metric, Contact Probability, to guide the messages ef- fectively in the network, and a Priority Queue, to rank the messages based on an adaptive message priority. Our simulation results show that both TBR and ProbRoute outperform all the existing quota based routing protocols in terms of delivery ratio and overhead ratio. Both protocols not only matches with the delivery ratios of °ooding based routing protocols but also achieves better delivery ratio than that of those routing protocols while incurring signi¯cantly less overhead and less latency. ProbRoute achieves slightly better delivery ratio compared to that of TBR at the cost of slightly more network overhead.