Network coding for efficient communication in extreme networks

TLDR

Ad‑hoc networks operating in extremely performance‑challenged environments, such as very sparse mobile networks where nodes meet only occasionally or wireless sensor networks with energy‑saving sleep cycles, often lack reliable end‑to‑end connectivity. The authors propose a communication algorithm that significantly reduces the overhead of probabilistic routing, making it a suitable building block for delay‑tolerant network architectures. Their forwarding scheme uses network coding, allowing nodes to transmit coded combinations of multiple overheard packets rather than forwarding each packet individually. Simulation results demonstrate that the algorithm attains the reliability and robustness of flooding while incurring only a small fraction of its overhead.

Abstract

Some forms of ad-hoc networks need to operate in extremely performance-challenged environments where end-to-end connectivity is rare. Such environments can be found for example in very sparse mobile networks where nodes "meet" only occasionally and are able to exchange information, or in wireless sensor networks where nodes sleep most of the time to conserve energy. Forwarding mechanisms in such networks usually resort to some form of intelligent flooding, as for example in probabilistic routing.We propose a communication algorithm that significantly reduces the overhead of probabilistic routing algorithms, making it a suitable building block for a delay-tolerant network architecture. Our forwarding scheme is based on network coding. Nodes do not simply forward packets they overhear but may send out information that is coded over the contents of several packets they received. We show by simulation that this algorithm achieves the reliability and robustness of flooding at a small fraction of the overhead.