Κωδικοποίηση δικτύου με στιγμιαία αποκωδικοποίηση σε ασύρματα τηλεπικοινωνιακά συστήματα πολλαπλών δεκτών

Abstract

In this dissertation three problems in the area of wireless broadcast erasure networks with feedback are solved. Specifically, a multiple unicast system of one transmitter and three receivers - users is examined. This system is saturated, i.e. there is a predefined number of packets the transmitter needs to sends to each user. The problem is to achieve optimal throughput by using network coding that is solely based on XOR operations (Exclusive OR) and ensuring instant decodability. To solve this problem a network of virtual queues is created at the transmitter to store packets that need to be sent, in order to exploit the feedback information. The proposed algorithm is proved to be optimal for i.i.d. (independent and identically distributed) channels and for independent channels with erasure probability up to 8/9. The analysis is mainly theoretic using simple techniques. In the second problem a stochastic model is considered, i.e. the packets arrive randomly at the transmitter at any timeslot. The problem is to develop a systematic framework that uses network coding based only on XOR operations for arbitrary number of users, as well as achieving the optimal throughput by applying this framework in the case of four users. In order to achieve this, the virtual network of the previous problem is generalized for arbitrary number of users. This generalization concerns the virtual queues maintained as well as the rules that determine the packet movement among the queues. Moreover, a backpressure type algorithm is used, that determines the coding choice for every transmission based on instantaneous quantities instead of predefined choices. This problem is reduced to a linear programming problem, which is solved by using appropriate packets. The third problem concerns developing a suboptimal algorithm for transmitting packets using the system of the previous problem, which requires less overhead to be included in each packet. The proposed algorithm uses a subset of the coding choices in respect to the algorithm of the second problem. Determining the maximum transmission rate that can be achieved through this algorithm is again a linear programming problem, which is solved by using appropriate software, while loss of performance in respect to the channel capacity limit is examined.

Η παρούσα διδακτορική διατριβή εξετάζει και επιλύει τρία προβλήματα σε ασύρματα δίκτυα ευρείας εκπομπής με διαγραφές και ανάδραση (broadcast erasure channel networks). Συγκεκριμένα, εξετάζεται ένα σύστημα ενός πομπού και τριών δεκτών - χρηστών με πολλαπλές συνόδους (sessions) μοναδικού αποδέκτη (multiple unicast). Το σύστημα αυτό είναι κορεσμένο, δηλαδή υπάρχει ένας προκαθορισμένος αριθμός πακέτων τα οποία πρέπει να μεταδώσει ο πομπός σε κάθε χρήστη. Το πρόβλημα που τίθεται είναι να επιτευχθεί η βέλτιστη διαμεταγωγή (throughput) χρησιμοποιώντας κωδικοποίηση δικτύου που βασίζεται αποκλειστικά σε πράξεις XOR (Αποκλειστικό Ή - Exclusive OR) και εξασφαλίζοντας στιγμιαία αποκωδικοποίηση. Για την επίλυση του προβλήματος αναπτύχθηκε ένα δίκτυο εικονικών ουρών για την αποθήκευση των προς αποστολή πακέτων στον πομπό, με τη βοήθεια των οποίων αξιοποιείται η πληροφορία που παρέχει η ανάδραση. Ο αλγόριθμος που προτείνεται αποδεικνύεται ότι είναι βέλτιστος για κανάλια με ανεξάρτητες και όμοια κατανεμημένες διαγραφές (independent and identically distributed - i.i.d.), αλλά και για κανάλια με ανεξάρτητες διαγραφές και πιθανότητα διαγραφής μέχρι και 8/9 . Στο δεύτερο πρόβλημα το σύστημα που εξετάζεται διαφέρει στο ότι πρόκειται για στοχαστικό μοντέλο όπου τα πακέτα φτάνουν τυχαία στον πομπό σε οποιαδήποτε χρονοθυρίδα. Το πρόβλημα που τίθεται είναι η ανάπτυξη ενός συστηματικού πλαισίου που χρησιμοποιεί κωδικοποίηση δικτύου βασισμένη αποκλειστικά σε πράξεις XOR για αυθαίρετο αριθμό χρηστών, καθώς και η επίτευξη της βέλτιστης διαμεταγωγής εφαρμόζοντας το συγκεκριμένο πλαίσιο. Για το σκοπό αυτό γενικεύεται το εικονικό δίκτυο του προηγούμενου προβλήματος για αυθαίρετο αριθμό χρηστών, τόσο ως προς τις ουρές που διατηρούνται στον πομπό όσο και ως προς τους κανόνες που διέπουν τη μεταφορά των πακέτων ανάμεσα στις εικονικές ουρές. Επιπλέον, χρησιμοποιείται ένας αλγόριθμος αντίθλιψης (backpressure) που προσδιορίζει σε κάθε μετάδοση την επιλογή κωδικοποίησης με βάση στιγμιαίες ποσότητες αντί για προκαθορισμένες επιλογές. Το πρόβλημα που προκύπτει είναι ένα πρόβλημα γραμμικού προγραμματισμού το οποίο επιλύεται με τη χρήση αντίστοιχων πακέτων. Αποδεικνύεται ότι ο αλγόριθμος αυτός είναι ο βέλτιστος δυνατός για την περίπτωση των τεσσάρων χρηστών. Το τρίτο πρόβλημα έγκειται στην ανάπτυξη αλγορίθμων για τη μετάδοση πακέτων στο σύστημα του προηγούμενου προβλήματος, οι οποίοι απαιτούν την ενσωμάτωση λιγότερης πλεονάζουσας πληροφορίας σε κάθε πακέτο. Ο προτεινόμενος αλγόριθμος χρησιμοποιεί ένα υποσύνολο των επιλογών κωδικοποίησης σε σχέση με τον αλγόριθμο του δεύτερου προβλήματος. Ο υπολογισμός του μέγιστου ρυθμού μετάδοσης που μπορεί να επιτευχθεί με το συγκεκριμένο αλγόριθμο συνίσταται και πάλι σε ένα πρόβλημα γραμμικού προγραμματισμού το οποίο επιλύεται με τη βοήθεια αντίστοιχων πακέτων, ενώ στη συνέχεια υπολογίζεται η απώλεια σε σχέση με το βέλτιστο όριο χωρητικότητας του καναλιού και παρουσιάζεται γραφικά.