Συντάχθηκε 09-01-2026 09:31
Τόπος:
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 16/01/2026 12:45
Λήξη: 16/01/2026 13:45
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Κωνσταντίνου Καββάδη
με θέμα
Μελέτη της Κατανομής Καθυστερήσεων των Πακέτων σε Πρωτόκολλα Τυχαίας Προσπέλασης με Ελεγχόμενη Πρώτη Πρόσβαση των Πακέτων στο Κανάλι
Evaluation of Packet Delay Distribution in Blocked Random Access Channel Protocols
Εξεταστική Επιτροπή
Καθηγητής Μιχαήλ Πατεράκης (επιβλέπων)
Καθηγητής Αθανάσιος Λιάβας
Καθηγητής Θρασύβουλος Σπυρόπουλος
Περίληψη
Τα πρωτόκολλα πολλαπλής πρόσβασης είναι κατανεμημένοι αλγόριθμοι, οι οποίοι επιτρέπουν σε ένα σύνολο από γεωγραφικά διασκορπισμένους κόμβους, καθένας εκ των οποίων έχει μια ουρά πακέτων προς μετάδοση, να επικοινωνήσουν χρησιμοποιώντας ένα κοινό κανάλι εκπομπής.
Ως αλγόριθμος επίλυσης συγκρούσεων (collision resolution algorithm, CRA) ορίζεται ένας αλγόριθμος που οργανώνει την επαναμετάδοση των πακέτων που συγκρούονται με τέτοιο τρόπο ώστε κάθε πακέτο να μεταδίδεται τελικά με επιτυχία με πεπερασμένη καθυστέρηση.
Στόχος της διπλωματικής εργασίας είναι η μελέτη δύο αντιπροσωπευτικών αλγορίθμων τυχαίας πολλαπλής πρόσβασης με ελεγχόμενη πρώτη πρόσβαση των πακέτων στο κανάλι (blocked random access), προκειμένου να προκύψουν χρήσιμα συμπεράσματα σχετικά με την αποδοτικότητα της λειτουργίας τους.
Τα πρωτόκολλα που αναλύθηκαν και προσομοιώθηκαν είναι ο αλγόριθμος Δυαδικού Δένδρου και ο αλγόριθμος First-Come First-Serve. Και οι δύο επιτυγχάνουν ευσταθή λειτουργία, υψηλά throughputs και χαμηλές μέσες καθυστερήσεις πακέτων. Παρουσιάζονται οι βελτιώσεις των δύο αλγορίθμων με τις οποίες αυξάνεται η απόδοση τους και τα αποτελέσματα της προσομοίωσης τους για διάφορες τιμές του Poisson συνολικού ρυθμού άφιξης πακέτων στο σύστημα, λ, έως και πολύ κοντά στο μέγιστο throughput του κάθε αλγορίθμου.
Η σύγκριση της απόδοσης των αλγορίθμων βασίζεται στο μέγιστο throughput κάθε πρωτοκόλλου και στην συμπεριφορά τόσο της μέσης τιμής, όσο και της αθροιστικής συνάρτησης κατανομής της καθυστέρησης πακέτου σαν συνάρτηση του συνολικού ρυθμού άφιξης πακέτων στο σύστημα, λ. Η προσομοίωση των αλγορίθμων υλοποιήθηκε στο περιβάλλον της MATLAB.
Abstract
Multiple access protocols are distributed algorithms that enable a set of geographically dispersed nodes, each maintaining a queue of packets for transmission, to communicate over a shared broadcast channel.
A collision resolution algorithm (CRA) is defined as an algorithm that organizes the retransmission of colliding packets in such a way that each packet is eventually transmitted successfully within a finite delay.
The objective of this thesis is the analysis of two representative blocked random-access algorithms, in order to derive useful conclusions regarding their operational efficiency.
The protocols analyzed and simulated are the Binary Tree algorithm and the First-Come First-Serve algorithm. Both achieve stable operation, high throughput, and low average packet delays. Improvements to both algorithms that enhance their performance are presented, along with simulation results for various values of the total Poisson packet arrival rate to the system, λ, up to values very close to the maximum throughput of each algorithm.
The performance comparison of the algorithms is based on their maximum throughput and on the behavior of both the mean value and the cumulative distribution function of packet delay as a function of the total packet arrival rate to the system, λ. The simulation of the algorithms was implemented in the MATLAB environment.
