Low Computational Complexity Network Coding For Mobile Networks

Janus Heide

Research output: PhD thesis

891 Downloads (Pure)

Abstract

Network Coding (NC) is a technique that can provide benefits in many types
of networks, some examples from wireless networks are: In relay networks,
either the physical or the data link layer, to reduce the number of transmissions.
In reliable multicast, to reduce the amount of signaling and enable cooperation
among receivers. In meshed networks, to simplify routing schemes
and to increase robustness toward node failures.
This thesis deals with implementation issues of one NC technique namely
Random Linear Network Coding (RLNC) which can be described as a highly
decentralized non-deterministic intra-flow coding technique. One of the key
challenges of this technique is its inherent computational complexity which
can lead to high computational load and energy consumption in particular
on the mobile platforms that are the target platform in this work.
To increase the coding throughput several simplifications have been considered,
such as decreasing field size, density, and coding systematically. In
order to increase the benefits of these simplifications we considered different
decoding algorithms. From a practical point of view we identified the conflict
between recoding and a compact coding vector representation. This problem
is relevant as the total overhead due to RLNC stems from the probability of
linear dependent symbols but also from including the coding vector of the
transmitted coded symbol. Finally, we present an approach that mitigates
these problems and enable a significantly higher coding throughput. The
approach is based on random but non-uniform combination of symbols in a
generation. Unlike approaches that adapts the ideas from Fountain codes
the presented proposal is not based on a degree distribution. The eorts and
experience stemming from this work have been incorporated in the Kodo
library and will be available for researchers and students in the future.
Chapter 1 introduces motivating examples and the state of art when this
work commenced. In Chapter 2 selected publications are presented and how
their content is related. Chapter 3 presents the main outcome of the work and
briefly new important progresses in the state of the art. The final conclusions
are drawn in Chapter 4.
Original languageEnglish
Print ISBNs978-87-92328-87-8
Publication statusPublished - 9 Aug 2012

Cite this