ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΚΩΝ ΕΠΙΣΤΗΜΩΝ

TMHMA ΕΠΙΣΤΗΜΗΣ ΥΠΟΛΟΓΙΣΤΩΝ

Υποψήφιος Διδάκτωρ

Πλουμίδης Εμμανουήλ

Τίτλος Διδακτορικής Διατριβής

Βελτίωση της απόδοσης του δικτύου αξιοποιώντας πολλαπλά μονοπάτια σε ασύρματα δίκτυα πλέγματος

Επιβλέποντες

Επιβλέπων Καθηγητής : Τραγανίτης Απόστολος

Μέλη Επιτροπής :

(1) Τραγανίτης Απόστολος

(2) Τσακαλίδης Παναγιώτης

(3) Σύρης Βασίλειος

Στοιχεία Διατριβής

Έναρξη Διδακτορικής Έρευνας : 01/09/2010

Ημερομηνία Υποστήριξης Διδακτορικής Διατριβής: 13/03/2015

Εγκεκριμένος Π/Υ: 45.000

Περίληψη

Προκειμένου να ικανοποιηθούν οι αυξανόμενες απαιτήσεις για ποιότητα υπηρεσίας πάνω από ασύρματα δίκτυα πλέγματος, ένας μεγάλος αριθμός μελετών προτείνει την αξιοποίηση πολλαπλών μονοπατιών ταυτόχρονα με σκοπό να αθροιστούν οι πόροι τους. Υπάρχουν αρκετές διαφορετικές προσεγγίσεις αξιοποίησης πολλαπλών μονοπατιών οι οποίες περιλαμβάνουν σχήματα που πραγματοποιούν δρομολόγηση, δέσμευση πόρων, έλεγχο ροής και ευκαιριακή προώθηση κίνησης. Η ταυτόχρονη αξιοποίηση πολλαπλών μονοπατιών έχει αποδειχτεί επωφελής ως προς την καθυστέρηση, το ρυθμό διαμεταγωγής δεδομένων, την αξιοπιστία και την ισοκατανομή φόρτου κίνησης. Δύο διαδεδομένοι στόχοι είναι ο αυξημένος ρυθμός διαμεταγωγής δεδομένων και η αξιοπιστία. Προς επίτευξη της αξιοπιστίας συγκεκριμένα, η αξιοποίηση πολλαπλών μονοπατιών συνδυάζεται με πλεονασμό. Παρ' όλα αυτά, η αξιοποίηση πολλαπλών μονοπατιών στα ασύρματα δίκτυα είναι πιο περίπλοκη, από ότι στα ασύρματα καθώς μεταδόσεις σε μία ζεύξη παρεμβάλλουν γειτονικές ζεύξεις και μπορεί να οδηγήσουν σε μειωμένη δικτυακή απόδοση.

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

Στο πρώτο τμήμα της διατριβής, διαφορετικά σχήματα προώθησης κίνησης που αξιοποιούν πολλαπλά μονοπάτια και διαφορετικούς βαθμούς πλεονασμού συγκρίνονται ως προς την καθυστέρηση και το ρυθμό διαμεταγωγής δεδομένων. Αξιολογείται, μέσω προσομοιώσεων διαφόρων σεναρίων, στον προσομοιωτή δικτύων Ns2, ένα αναλυτικό πλαίσιο το οποίο εκφράζει την καθυστέρηση και το ρυθμό διαμεταγωγής δεδομένων για τα προαναφερθέντα σχήματα προώθησης κίνησης. Το συγκεκριμένο αναλυτικό πλαίσιο επεκτείνεται και αξιολογείται επίσης για την περίπτωση όπου η πιθανότητα λάθους μίας ζεύξης εκφράζεται μέσω του μοντέλου σηματοθορυβικής σχέσης.

Στο δεύτερο μέρος της διατριβής, εξερευνάται το θέμα της αξιοποίησης πολλαπλών μονοπατιών με σκοπό την αύξηση του μέσου αθροιστικού ρυθμού διαμεταγωγής δεδομένων, για τον προαναφερθέντα τύπο δικτύων. Προτείνεται ένα κατανεμημένο σχήμα κατανομής ροής, το οποίο μεγιστοποιεί τον μέσο αθροιστικό ρυθμό διαμεταγωγής δεδομένων για όλες τις ροές, ενώ ταυτόχρονα, παρέχει πεπερασμένη καθυστέρηση. Δεν χρησιμοποιείται κανενός είδους πλεονασμός. Για τους σκοπούς του συγκεκριμένου σχήματος, η κατανομή ροής σε πολλαπλά μονοπάτια διατυπώνεται σαν ένα πρόβλημα βελτιστοποίησης. Το προτεινόμενο σχήμα βασίζεται σε ένα απλό μοντέλο για το μέσο αθροιστικό ρυθμό διαμεταγωγής δεδομένων, το οποίο εκφράζει τις παρεμβολές από γειτονικά μονοπάτια, αλλά και τις παρεμβολές από κόμβους του ίδιου μονοπατιού, μέσω του μοντέλου σηματοθορυβικής σχέσης. Αναφορικά με τις παρεμβολές, εξετάζονται δύο εκδοχές του προτεινόμενου σχήματος κατανομής ροής. Στην πρώτη εκδοχή, η παρεμβολή σε μία ζεύξη προσεγγίζεται λαμβάνοντας υπόψη μόνο τους σημαντικότερους παρεμβολείς. Στη δεύτερη εκδοχή, οι παραλήπτες εφαρμόζουν την τεχνική της διαδοχικής απαλοιφής παρεμβολών. Για την διαδικασία αξιολόγησης, αξιοποιούνται προσομοιώσεις, τόσο ενδεικτικών όσο και τυχαίων ασύρματων σεναρίων, χρησιμοποιώντας τον προσομοιωτή δικτύων Ns2. Το προτεινόμενο σχήμα κατανομής ροής συγκρίνεται με άλλα απλά σχήματα κατανομής ροής, τόσο ως προς την καθυστέρηση όσο και ως προς το ρυθμό διαμεταγωγής δεδομένων.

Λέξεις κλειδιά

Δρομολόγηση πολλαπλών μονοπατιών, ασύρματα δίκτυα πλέγματος, routingmetric, links, ζεύξεις, ExpectedTransmissionCount –ETX, ExpectedTransmissionTime, «βαθμολόγηση» μονοπατιών (pathrating), performanceanomaly, crosslayerfeedback, regression

Παραδοτέα - Δημοσιεύσεις

1) Μ. Ploumidis, N. Pappas, V. A. Siris, and A. Traganitis. “Short Term Wireless Channel State Prediction Using Markov Models and Supervised Learning”. In Euro ‐NF International Workshop on Traffic and Congestion Control for the Future Internet (EURONF TCCFI), 2011

2) Μ. Ploumidis, V. A. Siris, and A. Traganitis. “A Machine Learning Approach to Throughput Prediction in Multi‐hop Wireless Networks”. In Euro ‐NF International Workshop on Traffic and Congestion Control for the Future Internet (EURONF TCCFI), 2011

3) Μ. Ploumidis, N. Pappas, V. A. Siris, and A. Traganitis. Evaluating Forwarding Schemes Exploiting Path Diversity and Degrees of Redundancy in a Realistic Wireless Environment. 17th IEEE International Workshop Computer-Aided Modeling Analysis and Design of Communication Links and Network (CAMAD)

4) M. Ploumidis, N. Pappas, A. Traganitis. A Flow Allocation Scheme for Maximum Throughput for Random Access Wireless Multi-hop Networks - 4th Nordic Workshop on System and Network Optimization for Wireless (SNOW)

5) M. Ploumidis, N. Pappas, A. Traganitis. Throughput Optimal Flow Allocation on Multiple Paths for Random Access Wireless Multi-hop Networks - 9th IEEE BWA Workshop, co-located with IEEE GLOBECOM 2013

6) M. Ploumidis, N. Pappas, A. Traganitis. On the Delay of a Throughput Optimal Flow Allocation Scheme for Random Access WMNs. 19th IEEE International Workshop on Computer-Aided Modeling Analysis and Design of Communication Links and Networks (CAMAD), 2014

7) Μ. Ploumidis, N. Pappas, V. A. Siris, and A. Traganitis. On the performance of network coding and forwarding schemes with different degrees of redundancy for wireless mesh networks - Elsevier Computer Communications, May 2015

8) M. Ploumidis, N. Pappas, A. Traganitis. Performance of Flow Allocation with Successive Interference Cancelation for Random Access WMNs. - IEEE GC Workshop on Optimizing Heterogeneous Networking Technologies for the Internet of Things, 2015

9) M. Ploumidis, N. Pappas, A. Traganitis. Flow Allocation for Maximum Throughput and Bounded Delay on Multiple Disjoint Paths for Random Access Wireless Multihop Networks. Submited in IEEE Transactions on Vehicular Technology