Optimising Replication versus Redundancy in Window-Aware Opportunistic Routing

In this paper we address the replication versus redundancy optimisation problem for a class of intermittently-connected ad hoc networks with the following three characteristics: routing is performed by a store-carry-forward mechanism in an opportunistic manner, replication of custodian messages is used to increase the delivery ratio, and fragmentation combined with redundancy in the form of erasure coding is used to deal with large messages in short contact windows. We propose a novel mathematical model in which the merits of a high replication factor can be compared to a high level of redundancy in erasure coding. The purpose of the model is to identify the optimised level of replication and redundancy as a function of application-specific parameters like message size and time-to-live. Our model builds upon a component for message latency distribution that we have borrowed from earlier works (SprayAndWait) and that has been extended for erasure coding and constrained resources. The model is general and can be applied in different opportunistic settings using the following approach. First, we derive a set of equations that are demonstrated to identify the optimal replication and redundancy factor in a network with constrained resources. Then, the paper includes an extension that provides a tailor made latency distribution based on history profiling, thus making it applicable to any protocol that uses replication/redundancy in a similar network. By theoretical analysis and simulations, we demonstrate that using erasure coding together with replication offers an efficient yet flexible tradeoff between resource cost and protocol performance.