Return to search

Computational Complexity and Delay Reduction for RLNC Single and Multi-hop Communications

Today’s communication network is changing rapidly and radically. Demand for low latency, high reliability and low energy consumption increases as well the variety of characteristics of the connected devices. It is also expected that the number of connected devices will be massive in coming years. Some devices will be connected to the new generation base stations directly, while some of them will be connected through other devices via multi-hops. Reliable communication between these massive devices can be done via re-transmission, repetition of packets several times or via Forward Error Correction (FEC). In re-transmission method, when packets are negatively acknowledged or the sender’s acknowledgment timer expires, packets are re-transmitted. In repetition method, every packet can be send several times. Both aforementioned methods can cause a huge delay, particularly, in multi-hop network. On the contrary of these methods, FEC methods are preferred for low latency applications. Source information are transmitted together with redundant information. Hence, the number of transmissions are reduced comparing to the methods mentioned above.
Random Linear Network Coding (RLNC) is a packet level erasure correcting codes which aims to reduce latency. Specifically, source packets are combined and these combinations or coded packets are sent to the destination. Lost packets do no need to be re-sent since another coded packet can be substituted to the lost coded packet. Hence, the feedback mechanism and re-sending process becomes unnecessary. There are many variations of RLNC. One variation is called sliding window RLNC which apples FEC mechanism. This coding scheme achieves low latency via interleaved coded packets in between source packets. Another variation of the RLNC is Fulcrum, which is a versatile code. Fulcrum provides three different decoding options. Received coded packets can be decoded with low, high or middle complexity. This is a very important feature since connected devices will have different computation capabilities and proving a versatile code will allow them flexibility.
Although the aforementioned coding schemes are well suited to error prone network, there are still remaining challenges need to be studied. For instance, Fulcrum RLNC has high encoding and decoding complexity which increase the computation time and energy consumption. Moreover, although original Fulcrum RLNC strengths the reliability, it needs to be improved for low latency applications. Another remaining challenges is that recoding strategy of RLNC is not optimal for low latency. Allowing the intermediate nodes to combine received packets is referred as recoding. As described earlier, data packets will pass many hops until they reach destination. Therefore, compute-and-forward paradigm will be preferred rather than store-and-forward. Although recoding capability of RLNC differs it from other coding schemes (Raptor, LT), the conventional way of recoding is not efficient for low latency. Hence, the aim of this thesis is to address the aforementioned remaining challenges.
One way to address the remaining challenges is to employ sparsity. In other words, a few source packets can be combined rather than a large set of source packets to generate coded packets. Particularly, a dynamic sparse mechanism is proposed to vary the number of combined source packets during the encoding without a signaling between sender and receiver for Fulcrum RLNC to speed up encoding and decoding process without increasing overhead amount. Then, two different sliding window schemes were integrated into Fulcrum RLNC to make Fulcrum RLNC gain the low latency property. Sending source packets systematically and then spreading sparse coded packets in between systematic source packets can be referred as systematic sparsity. Moreover, different sparse and systematic recoding strategies have been proposed in this thesis to lower the delay and computation time at the intermediate nodes and destination. Finally, one of the proposed recoding strategy has been applied to the vehicle platooning scenario to increase reliability. All proposed coding schemes were analyzed and performed on KODO which is well known network coding library.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:84146
Date20 March 2023
CreatorsTasdemir, Elif
ContributorsFitzek, Frank H. P., Schmeink, Anke, Pedersen, Morten, Technische Universität Dresden
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0023 seconds