Αρχική
Dual graph partitioning of cellular networks : inferring and quantifying the graph properties that guarantee a partition result
Αποτελέσματα - Λεπτομέρειες
|
||||
| Κωδικός Πόρου | 000337669 | |||
| Τίτλος | Dual graph partitioning of cellular networks : inferring and quantifying the graph properties that guarantee a partition result | |||
| Άλλος τίτλος | Εντοπισμός και ποσοτικοποίηση των ιδιοτήτων γράφου που εγγυώνται ένα αποτέλεσμα διαμέρισης | |||
| Συγγραφέας | Μουδάτσος, Μιχαήλ Νικολάου | |||
| Σύμβουλος διατριβής | Τόλλης, Ιωάννης | |||
| Περίληψη |
Η διαμέριση ή αλλιώς, τμηματοποίηση γράφων είναι ένα απο τα πιο ενδιαφέροντα τρέχοντα προβλήματα της κλάσεως NP-Hard, λόγω της εφαρμογής του στα δίκτυα. Ο στόχος του προβλήματος είναι να δημιουργηθεί ένας καθορισμένος αριθμός συνόλων από αντικείμενα του εκάστοτε προβλήματος, ελαχιστοποιώντας το κόστος επικοινωνίας μεταξύ των συνόλων αυτων, το οποίο ισούται με το άθροισμα των βαρών των ακμών των οποίων οι κόμβοι ανήκουν σε διαφορετικά σύνολα. Ειδικότερα στα ασύρματα δίκτυα κυψελών, το κόστος επικοινωνίας ορίζεται ως τον αριθμό λειτουργιών επικοινωνίας μεταξύ κυψελών. Οι διεπαφές επικοινωνίας των κυψελών συνδέονται με μεταγωγείς, οι οποίοι με τη σειρά τους συνδέονται με δρομολογητές. Η επικοινωνία μετξύ κυψελών που ανήκουν σε διαφορετικούς μεταγωγείς ή δρομολογητές απαιτεί την εκτεταμένη χρήση λειτουργικών σημάτων, καθυστερώντας την όλη διαδικασία. Η τμηματοποίηση γράφων βοηθάει στην ανάθεση κυψελών σε σύνολα μεταγωγέων και δρομολογητών, ελαχιστοποιώντας το πλήθος των επικοινωνιών μεταξύ συνόλων. Συνεπώς, τα ζεύγη κυψελών που είναι λιγότερο πιθανά να επικοινωνήσουν υπόκεινται του επιπλέον κόστους σήμανσης. Υπάρχουν εκτεταμένες μελέτες στην βιβλιογραφία, που προτείνουν ευρεστικές λύσεις και συγκρίνουν τα αποτελέσματά τους, σχετικά με την τμηματοποίηση γράφων. Οι περισσότερες λύσεις αφορούν επαναληπτικούς αλγόριθμους, των οποίων η επίδοση καθορίζεται απο την ποιότητα της διαμέρισης. Στην παρούσα εργασία αναλύεται ένας υπάρχων αλγόριθμος τμηματοποίησης. Ο προτεινόμενος αλγόριθμος τερματίζει σε πολυωνυμικό χρόνο, αποτελώντας μια γρηγορότερη λύση τμηματοποίησης σε σχέση με τους επαναληπτικούς αλγόριθμους, με το κόστος της χαμηλότερης ποιότητας του αποτελέσματος. Ο αλγόριθμος Τμηματοποίησης μέσω Δυικού Γράφου (DGP) εκμεταλλεύεται συγκεκριμένες ιδιότητες του δυικού, ενός επίπεδου γράφου. Οποιοδήποτε μονοπάτι μεταξύ δύο κόμβων που βρίσκονται στο εξωτερικό σύνορο του δυικού γράφου (συνοριακοί κόμβοι), αντιστοιχεί σε ένα σύνολο από ακμές στον αρχικό γράφο. Η αφαίρεση αυτών των ακμών οδηγεί στην δημιουργία δυο αποσυνδεμένων υπογράφων. Αυτή η διαμέριση ονομάζεται διχοτόμιση. Ο αλγόριθμος DGP ψάχνει όλα τα συντομότερα μονοπάτια μεταξύ συνοριακών κόμβων και επιλέγει το ελάχιστο από αυτά που χωρίζουν τον γράφο σε δύο περίπου ίσα μέρη, σύμφωνα με μια δεδομένη μέγιστη επιτρεπτή απόκλιση στο μέγεθος. Εν τούτοις, δεν υπάρχει εγγύηση ότι θα υπάρχει πάντα ένα συντομότερο μονοπάτι μεταξύ συνοριακών κόμβων (διασυνοριακό μονοπάτι) που θα διχοτομεί τον αρχικό γράφο. Στόχος της παρούσης εργασίας είναι να ερευνήσει τα χαρακτηριστικά ενός γράφου που επηρεάζουν την επιτυχή εύρεση διαμέρισης απο τον αλγόριθμο, εφαρμόζοντας μια σειρά απο διαμερίσεις σε τεχνητούς εξαγωνικούς γράφους. Το μοντέλο κίνησης PRAGMA χρησιμοποιήθηκε για την εξαγωγή ενός δείγματος κατανομής των βαρών των ακμών. Οι τεχνητοί γράφοι παράχθηκαν χρησιμοποιώντας παρόμοια κατανομή βαρών. Τα αποτελέσματα έδειξαν ότι η χωρική κατανομή των υψηλών και χαμηλών βαρών στο γράφο επηρεάζει τη διαδρομή των διασυνοριακών συντομότερων μονοπατιών και συνεπώς, το αν διχοτομούν το γράφο με ένα επιθυμητό λογο των μεγεθών των τμημάτων που προέκυψαν. Η χωρική κατανόμή όπως και η κατανομή των τιμών των βαρών μοντελοποιήθηκε με την έννοια των «κέντρων πληθυσμού». Τα βάρη των ακμών μειώνονται αντιστρόφως ανάλογα με την απόστασή τους από τον κοντινότερο κόμβο-κέντρο πληθυσμού. Η κατανομή των τιμών των αποστάσεων μεταξύ των κέντρων πληθυσμού και του εξωτερικού συνόρου του γράφου βοηθάει στην αναγνώριση των γράφων που μπορούν να διχοτομηθούν επιτυχώς από τον DGP. Επίσης, παρουσιάζεται μια παραλλαγή του αλγορίθμου που εγγυάται την εύρεση μιας διαμέρισης, με το κόστος της μεγαλύτερης χρονικής πολυπλοκότητας. Η ποιότητα διαμέρισης του αλγορίθμου συγκρίνεται με αυτή των επαναληπτκών τεχνικών, εφαρμόζοντας τον αλγόριθμο σε γράφους που χρησιμοποιούνται στη βιβλιογραφία. |
|||
| Φυσική περιγραφή | xv, 107 σ. : εικ. ; 30 cm. | |||
| Γλώσσα | Αγγλικά | |||
| Ημερομηνία έκδοσης | 2008-12-04 | |||
| Συλλογή | Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης | |||
| Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης | ||||
| Εμφανίσεις | 474 | |||
| Ψηφιακά τεκμήρια | |
|---|---|
|
Κατέβασμα Εγγράφου |
