Περίληψη |
Η κωδικοποίηση δικτύου είναι ένας νέος ερευνητικός τομέας που παρουσιάζει ενδιαφέρουσες εφαρμογές όχι μόνο στη θεωρία πληροφοριών και κωδικοποίησης, αλλά και στα συστηματα δικτυων της πραξης. Η κωδικοποίηση δικτύου επεκτείνει τη λειτουργικότητα των δικτύων πέρα από την παραδοσιακή δρομολόγηση ή τις τεχνικές αποθήκευσης και προώθησης, εισάγωντας την μαθηματική επεξεργασία των δεδομένων (κωδικοποίηση) μέσα στα δίκτυα. Ο Ahlswede κ.ά. μελέτησαν την πολυεκπομπή σε ένα δίκτυο χωρίς απώλειες συνδέσμων και έδειξαν ότι η επίτευξη της χωρητικότητας της πολυεκπομπής απαιτεί γενικά τη χρήση ενός κώδικα δικτύου. Περαιτέρω εργασίες έδειξαν τρόπους σχεδίασης κωδίκων δικτύου και επίσης μελέτησαν αρκετές ιδιότητές τους όπως η κατανεμημένη σχεδίασή τους. Στα πλαίσια αυτής της εργασίας εξετάζουμε διάφορα θεωρητικά και πρακτικά ζητήματα της κωδικοποίησης δικτύου. Ξεκινάμε τη μελέτη μας με την εξέταση μερικών δικτύων από την άποψη του κέρδους που έχουμε με τη χρήση της κωδικοποίησης δικτύου. Σε μερικές περιπτώσεις, η κωδικοποίηση δικτύου μπορεί να διπλασιάσει την χωρητικότητα και εν γένει εξοικονομεί ενέργεια σε ένα ασύρματο δίκτυο λόγω των λιγότερων μεταδόσεων που απαιτούνται. Παρουσιάζουμε έναν απλό αλλά επαρκή συγκεντρωτικό αλγόριθμο για την κατασκευη κώδικα δικτύου, ο οποίος εφαρμόζεται σε ένα ακυκλικό δίκτυο πολυεκπομπής μιας πηγής. Στη συνέχεια μελετάμε το πρόβλημα του μεγέθους του αλφάβητου ενός κώδικα δικτύου. Η μνήμη καθώς και η υπολογιστική πολυπλοκότητα που απαιτούνται εξαρτώνται σε μεγάλο βαθμό από το μέγεθος του αλφαβήτου του κώδικα που χρησιμοποιούμε. Επίσης, παρουσιάζουμε μια μέθοδο για την εύρεση του μεγέθους του αλφάβητου χρησιμοποιώντας μόνο τα εξερχόμενα κανάλια από την πηγή. Τέλος, παρουσιάζουμε μια μέθοδο για να μειώσουμε το μέγεθος αλφάβητου για τα δίκτυα συνδυασμού.
|