3.3.2 Ο αλγόριθμος Center Of Mass (COM algorithm)    (Περιεχόμενα)

Υπάρχουν δύο πολύ σημαντικά προβλήματα στη σχεδίαση δικτύων ραχοκοκαλιάς:

• Η τοποθέτηση των δικτυακών κόμβων
• Η συνδεσιμότητα της ραχοκοκαλιάς (backbone connectivity)

Υπάρχουν τέσσερις αλγόριθμοι οι οποίοι είναι χρήσιμοι στην εξαγωγή προτάσεων σχετικά με την τοποθέτηση των κόμβων του δικτύου της ραχοκοκαλιάς:

• Ο αλγόριθμος κέντρου μάζας - Center Of Mass algorithm (COM)
• Ο αλγόριθμος Add
• O αλγόριθμος Drop
• Ο αλγόριθμος Mentor

Εμείς θα μιλήσουμε μόνο για τον αλγόριθμο κέντρου μάζας. Για μια εκτενέστερη περιγραφή των υπόλοιπων αλγορίθμων, ο ενδιαφερόμενος αναγνώστης μπορεί να ανατρέξει στην [6].

Ο αλγόριθμος κέντρου μάζας - COM

Ο αλγόριθμος αυτός υποθέτει ότι οι παρακάτω πληροφορίες είναι δεδομένες:

• w_i βάρη βασισμένα στην κυκλοφορία που εισέρχεται και εξέρχεται από τον κάθε κόμβο i
• Το επιθυμητό μέγιστο συνολικό βάρος W_M για μια ομάδα κόμβων, το οποίο υπολογίζεται από το άθροισμα του βάρους w_i του κάθε κόμβου i που αποτελεί μέρος της ομάδας). Αυτό αντιπροσωπεύει ένα άνω όριο στο W το οποίο δε μπορεί να ξεπεραστεί.
• Το επιθυμητό ελάχιστο συνολικό βάρος W_m για μια ομάδα κόμβων, το οποίο υπολογίζεται από το άθροισμα του βάρους w_i του κάθε κόμβου i που αποτελεί μέρος της ομάδας). Αυτό αντιπροσωπεύει ένα κάτω όριο στο μήκος της ομάδας.
• Η επιθυμητή μέγιστη συνολική απόσταση D_M μεταξύ δύο ομάδων κόμβων που μπορούν να μελετηθούν για συγχωνεύση. Αυτό παριστάνει ένα άνω όριο στη DM, το οποίο δε μπορεί να ξεπεραστεί.
• Οι (x_i,y_i) συντεταγμένες για υποψήφιες τοποθεσίες κόμβων ραχοκοκαλιάς. Αυτές οι συντεταγμένες χρησιμοποιούνται για τον υπολογισμό της απόστασης μεταξύ δύο τοποθεσιών, χρησιμοποιώντας μιας τυποποιημένη εξίσωση για την απόσταση. Η απόσταση που υπολογίζεται χρησιμοποιείται για την εκτίμηση του κόστους του καναλιού που συνδέει τους κόμβους. Ως εκ τούτου, στη συζήτηση που ακολουθεί, το κόστος και η απόσταση θα θεωρούνται συνώνυμα στοιχεία.
• Επιθυμητό τελικό αριθμό ομάδων C.

Αν κατά τη διάρκεια της εκτέλεσης του αλγορίθμου υπάρξουν αντιθέσεις που οδηγούν στην επιβολή των περιορισμών W_M, W_m και D, τότε θα πρέπει να οριστεί μια συνάρτηση ανταλλαγής (trade-off function), για την επίλυση αυτών των διαφορών. Το πρόβλημα, τότε, θα πρέπει να λυθεί εκ νέου, χρησιμοποιώντας τη συνάρτηση ανταλλαγής.

Βήμα 1: Ξεκίνα με κάθε (x_i,y_i) εντός μιας ομάδας. Αυτό σημαίνει ότι αρχικά ο κάθε κόμβος θεωρείται ως μια ομάδα (cluster)

Βήμα 2: Το κόστος της σύνδεσης δύο κόμβων i και j θεωρείται ότι είναι ανάλογο της απόστασής τους. Η απόσταση μεταξύ κάθε ζεύγους κόμβων υπολογίζεται χρησιμοποιώντας την τυποποιημένη εξίσωση για την απόσταση που δίνεται παρακάτω:

Βήμα 3: Ταξινόμησε τα κόστη που υπολογίστηκαν από την (16) από το χαμηλότερο στο υψηλότερο για κάθε ζεύγος κόμβων.

Βήμα 4: Βρες τους δύο κοντινότερους κόμβους ως υποψήφιους για συγχώνευση

·        Αν δεν υπάρχουν υποψήφιοι συγχώνευσης, τότε έλεγξε αν έχει επιτευχθεί ο επιθυμητός τελικός αριθμός ομάδων, C. Αν δεν έχει βρεθεί, τότε σταμάτα τον αλγόριθμο με το μήνυμα «O COM δε μπορεί να βρει μια λύση». Αν ο επιθυμητός τελικός αριθμός C έχει επιτευχθεί και ικανοποιούνται όλοι οι υπόλοιποι περιορισμοί, τερμάτισε τον αλγόριθμο με το μήνυμα: «Τελική λύση βρέθηκε».

·        Αν παραβιάζονται οι περιορισμοί, τότε απέρριψε την ομάδα κόμβων και διέγραψέ την από τη λίστα υποψηφίων. Επέστρεψε στην αρχή του βήματος 4.

·        Αν δεν παραβιάζονται οι περιορισμοί, τότε προχώρα σε συγχώνευση των δύο ομάδων (i & j) που βρίσκονται κοντύτερα, έτσι ώστε να δημιουργηθεί μια νέα ομάδα, k. Η νέα ομάδα, k, εκλέγεται ως το κέντρο της μάζας με βάση την κυκλοφορία που ρέει στους i και j.

Βήμα 5: Διέγραψε τις ομάδες i και j από περαιτέρω θεώρηση. Πρόσθεσε την ομάδα k στη λίστα των ομάδων προς συγχώνευση. Επέστρεψε στο βήμα 2 και υπολόγισε την απόσταση μεταξύ των υπαρχουσών κόμβων και της νέας ομάδας k.