Erasure-coding based routing for opportunistic networks

TLDR

Routing in Delay Tolerant Networks with unpredictable mobility is challenging due to frequent disconnections and limited network knowledge, and existing redundant transmission approaches suffer either high overhead or long delays. The paper proposes a novel forwarding algorithm that uses erasure coding to improve routing in DTNs. Erasure coding enables many relays while keeping overhead constant, reducing long delays; simulations using a real‑world wildlife mobility trace compare this approach to four other forwarding categories. Simulations show that the erasure‑coding algorithm achieves the best worst‑case delay for a fixed overhead, and an analytical model confirms its delay advantages.

Abstract

Routing in Delay Tolerant Networks (DTN) with unpredictable node mobility is a challenging problem because disconnections are prevalent and lack of knowledge about network dynamics hinders good decision making. Current approaches are primarily based on redundant transmissions. They have either high overhead due to excessive transmissions or long delays due to the possibility of making wrong choices when forwarding a few redundant copies. In this paper, we propose a novel forwarding algorithm based on the idea of erasure codes. Erasure coding allows use of a large number of relays while maintaining a constant overhead, which results in fewer cases of long delays.We use simulation to compare the routing performance of using erasure codes in DTN with four other categories of forwarding algorithms proposed in the literature. Our simulations are based on a real-world mobility trace collected in a large outdoor wild-life environment. The results show that the erasure-coding based algorithm provides the best worst-case delay performance with a fixed amount of overhead. We also present a simple analytical model to capture the delay characteristics of erasure-coding based forwarding, which provides insights on the potential of our approach.