Network coding based multicast in delay tolerant networks

Abstract

Delay Tolerant Networks (DTN) are sparse ad hoc networks in which no contemporaneous path exists between source and destination most of the time. In DTN, connectivity graph of the network changes over time either due to mobility or sleepwakeup cycles of the nodes. Mobile Ad hoc Network routing protocols such as AODV, DSR etc. fail in such scenario because they try to find end-to-end path before data transmission which is non-existent in DTN. So, routing protocols proposed for DTN follow ‘store-carry-forward’ paradigm in which two nodes exchange messages with each other only when they come into contact. In the process, ‘Single-copy’ schemes maintain only one copy of the message in the network at any time while ‘Multi-copy’ schemes spread more than one copy of the message. While Multi-copy schemes improve chances of delivery, communication overhead and buffer occupancy are quite high for these schemes. We propose Multi-copy routing protocol for multicasting in DTN called “Multicast In Delay TOlerant NEtworks (MIDTONE)” which uses ‘Network coding’ to reduce this overhead without impacting the performance. Network coding is a mechanism in which nodes encode two or more incoming packets and forward encoded packets instead of forwarding them as it is. We also propose a novel packet purging scheme which takes advantage of features of network coding to increase buffer efficiency. As simulation results suggest, our protocol achieves significantly less delay to deliver all the packets in infinite buffer case and higher delivery ratio in finite buffer case compared to non-network coding based Multi-copy scheme.