Optimisation et application du codage réseau dans l'architecture des futurs réseaux sans fils

摘要

Network coding (NC) is a new technique in which transmitteddata is encoded and decoded by the nodes of the network inorder to enhance throughput and reduce delays. Usingalgebraic algorithms, encoding at nodes accumulates varioustransmissions in fewer ones and decoding restores thesetransmissions. NC requires fewer transmissions to transmit allthe data but more processing at the nodes. NC can be appliedat any of the ISO layers. However, the focus is mainly on thenetwork layer level.In this work, we introduce novelties to the NC paradigm with theintent of building easy to implement NC protocols in order toimprove bandwidth usage, enhance QoS and reduce the impactof losing packets in lossy networks. Several challenges wereraised by this thesis concerning details in the coding anddecoding processes and all the related mechanisms used todeliver packets between end nodes. Notably, questions like thelife cycle of packets in coding environment, cardinality of codedmessages, number of byte overhead transmissions andbuffering time duration were inspected, analytically counted,supported by many theorems and then verified throughsimulations. When the packet loss problem was addressed,methods used in this thesis to closely investigate the behaviorof the network as a response to the loss led to the proposition ofnovel mechanisms to overcome this loss and to help reducingthe overhead caused by packet loss.In the first part of the thesis, an overview of NC is conductedsince triggered by the work of Alshwede et al. NC techniquesare then detailed with the focus on linear and binary NC. Thesetechniques are elaborated and embellished with examplesextracted from different scenarios to further help understandingthe advantages and disadvantages of each of these techniques.In the second part, a new address correlated NC (ACNC)protocol is presented and two approaches using ACNC protocolare introduced, the centralized approach where decoding isconducted at end nodes only and the distributed decodingapproach where each node in the network participates in thedecoding process. Centralized decoding is elaborated by firstpresenting its decision models and the detailed decoding at endnodes procedure. Moreover, the cardinality of received codedmessages and the buffering requirements at end nodes areinvestigated and the concepts of aging and maturity wereintroduced. The distributed decoding approach is presented asa solution to reduce the overhead on end nodes by distributingthe decoding process and buffering requirements tointermediate nodes.Loss and recovery in NC are examined for both centralized anddistributed approaches. For the centralized decoding approach,two mechanisms to limit the impact of loss are presented. Tothis effect, the concept of closures and covering sets areintroduced and the covering set discovery is conducted onundecodable messages to find the optimized set of packets torequest from the sender in order to decode all received packets.For the distributed decoding, a new hop-to-hop reliabilitymechanism is proposed that takes advantage of the NC itselfand depicts loss without the need of an acknowledgementmechanism.