Distributed weight balancing in directed topologies
View/ Open
Date
2018-05Publisher
Πανεπιστήμιο Κύπρου, Πολυτεχνική Σχολή / University of Cyprus, Faculty of EngineeringPlace of publication
CyprusGoogle Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Ένα κατανεμημένο σύστημα ή δίκτυο μπορεί να θεωρηθεί ως ένα σύνολο υποσυστημάτων που μπορούν να μοιράζονται πληροφορίες μέσω διασυνδέσεων, οι οποίες αποτελούν μια κατευθυνόμενη τοπολογία επικοινωνίας. Τα κατανεμημένα συστήματα αποδεικνύονται ζωτικής σημασίας για την αποτελεσματικότητα της εκτέλεσης διαφόρων καθηκόντων στους τομείς του συνεταιριστικού ελέγχου, του κατανεμημένου συντονισμού και του ελέγχου των συστημάτων πολλαπλών χρηστών. Αυτή η διδακτορική διατριβή αφορά νέους κατανεμημένους αλγόριθμους για εξισορρόπηση βάρους σε κατευθυνόμενες (επικοινωνιακές) τοπολογίες. Μια κατευθυνόμενη τοπολογία (κατευθυνόμενος γράφος) με μη αρνητικά (ή θετικά) βάρη που αποδίδονται σε κάθε άκρη είναι ισορροπημένη εάν, για κάθε κόμβο, το άθροισμα των βαρών των εισερχόμενων άκρων ισούται με το άθροισμα των βαρών των εξωτερικών άκρων. Οι νέοι αλγόριθμοι που παρουσιάζονται σε αυτή τη διατριβή μπορούν να διευκολύνουν την ανάπτυξη στρατηγικών για την παραγωγή ισορροπημένων κατευθυνόμενων γράφων, με κατανεμημένο τρόπο, και να βρουν πολυάριθμες εφαρμογές στον συντονισμό και τον έλεγχο των συστημάτων πολλαπλών στοιχείων.
Στο πρώτο μέρος αυτής της διπλωματικής εργασίας, αντιμετωπίζουμε το πρόβλημα της εξισορρόπησης βάρους σε ένα σύστημα πολλαπλών στοιχείων. Παρουσιάζουμε ένα νέο κατανεμημένο αλγόριθμο που λειτουργεί πάνω από μια στατική τοπολογία και λύνει το πρόβλημα εξισορρόπησης βάρους όταν τα βάρη περιορίζονται σε μη αρνητικούς ακέραιους αριθμούς. Ο προτεινόμενος αλγόριθμος αποδεικνύεται ότι συγκλίνει σε ένα γράφο με ισορροπημένο βάρος μετά από έναν πεπερασμένο αριθμό επαναλήψεων που αυστηρά υπολογίσαμε. Αυτός ο αλγόριθμος μπορεί επίσης να θεωρηθεί ως μια κατανεμημένη μέθοδος για την απόκτηση ενός συνόλου ακέραιων ροών που εξισορροπούν ένα δίκτυο ροής.
Στο δεύτερο μέρος της εργασίας, εξετάζουμε το πρόβλημα της εξισορρόπησης βάρους σε ένα σύστημα πολλαπλών στοιχείων κάτω από μια κατευθυνόμενη (στατική) τοπολογία διασύνδεσης παρουσία περιορισμένων ή απεριόριστων καθυστερήσεων (απώλεια πακέτων) στους συνδέσμους επικοινωνίας. Συγκεκριμένα, παρουσιάζουμε έναν νέο κατανεμημένο αλγόριθμο ο οποίος επιλύει το πρόβλημα εξισορρόπησης βάρους σε πεπερασμένο αριθμό βημάτων με την παρουσία αυθαίρετων χρονικών καθυστερήσεων που μπορεί να επηρεάσουν τη μετάδοση σε μια συγκεκριμένη σύνδεση σε μια συγκεκριμένη χρονική στιγμή. Στη συνέχεια, παρουσιάζουμε μια έκδοση βασισμένη σε συμβάντα του προτεινόμενου πρωτοκόλλου, στον οποίο κάθε κόμβος αποφασίζει αυτόνομα όταν πρέπει να πραγματοποιηθούν ενημερώσεις επικοινωνίας και ελέγχου. Παρουσιάζοντας πτώσεις πακέτων πάνω από τους συνδέσμους επικοινωνίας, ο αλγόριθμος μπορεί να τροποποιηθεί για να συγκλίνει σε ένα σύνολο βαρών που σχηματίζουν ένα ισορροπημένο γράφημα μετά από έναν πεπερασμένο αριθμό επαναλήψεων (με πιθανότητα ένα). Σε όλες τις παραπάνω περιπτώσεις, ο προκύπτων ισορροπημένος γράφος φαίνεται να είναι μοναδικός και ανεξάρτητος από τον τρόπο με τον οποίο εμφανίζονται οι καθυστερήσεις ή οι σταγόνες πακέτων κατά την εκτέλεση του αλγορίθμου.
Στο τρίτο μέρος αυτής της εργασίας εξετάζουμε το πρόβλημα της εξισορρόπησης βάρους σε ένα σύστημα πολλαπλών στοιχείων κάτω από μια στατική κατευθυνόμενη τοπολογία διασύνδεσης παρουσία κατώτερων και ανώτατων ορίων περιορισμού στα άκρα των άκρων. Παρουσιάζουμε έναν καινοτόμο κατανεμημένο αλγόριθμο για τη λήψη αποδεκτών και ισορροπημένων ακέραιων βαρών για την περίπτωση όταν υπάρχουν κατώτεροι και ανώτεροι περιορισμοί βάρους στους συνδέσμους επικοινωνίας. Σε σύγκριση με τους κατανεμημένους αλγορίθμους, ο πρόσθετος περιορισμός εδώ είναι ότι κάθε βάρος άκρου πρέπει να βρίσκεται μέσα σε ένα δεδομένο διάστημα, ενώ οι ανταλλαγές επικοινωνίας (αλλά όχι απαραίτητα η αντιστοίχιση βαρών) μεταξύ γειτονικών κόμβων θεωρούνται αμφίδρομες.
Στο τέταρτο μέρος αυτής της εργασίας εξετάζουμε το πρόβλημα της εξισορρόπησης του βάρους σε ένα σύστημα πολλαπλών στοιχείων πάνω σε μια κατευθυνόμενη (στατική) τοπολογία διασύνδεσης, κάτω από περιορισμούς στις κατώτατες και ανώτερες τιμές στα άκρα των άκρων, παρουσία περιορισμένων ή απεριόριστων καθυστερήσεων (πτώση πακέτων) στις συνδέσεις επικοινωνίας. Συγκεκριμένα, παρουσιάζουμε έναν καινοτόμο κατανεμημένο αλγόριθμο ο οποίος επιλύει το πρόβλημα εξισορρόπησης του βάρους του σε ακέραιο αριθμό επαναλήψεων κάτω από κατώτερους και ανώτερους περιορισμούς βάρους πάνω στους συνδέσμους επικοινωνίας για την περίπτωση όπου αυθαίρετες χρονικές καθυστερήσεις επηρεάζουν τη μετάδοση σε συγκεκριμένο σύνδεσμο σε συγκεκριμένο χρόνο. Επιπλέον, παρουσιάζουμε μια έκδοση βασισμένη σε συμβάντα του προτεινόμενου πρωτοκόλλου, στον οποίο κάθε κόμβος αποφασίζει αυτομάτως όταν θα πρέπει να πραγματοποιηθούν ενημερώσεις επικοινωνίας και ελέγχου, έτσι ώστε οι προκύπτουσες εκτελέσεις δικτύου να έχουν ως αποτέλεσμα ένα γράφο με ισορροπημένο βάρος και όλοι οι κόμβοι να σταματήσουν τελικά να εκτελούν μεταδόσεις. Στη συνέχεια, επεκτείνουμε την εφαρμογή του προτεινόμενου αλγορίθμου στην περίπτωση όπου πιθανές πτώσεις πακέτων επηρεάζουν τους συνδέσμους επικοινωνίας. A distributed system or network can be viewed as a set of subsystems that can share information via interconnection links, which form a generally directed communication topology. Distributed systems prove to be of vital importance for the effectiveness of performing various tasks in the areas of cooperative control, distributed coordination, and control of multicomponent systems. This doctoral thesis concerns novel distributed algorithms for weight balancing over directed (communication) topologies. A directed topology (digraph) with nonnegative (or positive) weights assigned on each edge is weight-balanced if, for each node, the sum of the weights of in-coming edges equals the sum of the weights of out-going edges. The novel algorithms introduced in this thesis can facilitate the development of strategies for generating weight balanced digraphs, in a distributed manner, and find numerous applications in coordination and control of multi-component systems.
In the first part of this thesis, we address the problem of integer weight balancing in a multi-component system. We introduce a novel distributed algorithm that operates over a static topology and solves the weight balancing problem when the weights are restricted to be nonnegative integers. The proposed algorithm is shown to converge to a weight balanced digraph after a finite number of iterations that we explicitly bound. This algorithm can also be viewed as a distributed method for obtaining a set of integer flows that balance a flow network.
In the second part of the thesis, we investigate the problem of integer weight balancing in a multi-component system under a directed (static) interconnection topology in the presence of bounded or unbounded delays (packet drops) in the communication links. Specifically, we present a novel distributed algorithm which solves the integer weight balancing problem in the presence of arbitrary (time-varying and inhomogeneous) time delays that might a affect the transmission at a particular link at a particular time. Then, we present an event-based version of the proposed protocol in which each node autonomously decides when communication and control updates should occur. In the presence of packet drops over the communication links, the algorithm can be modified to converge to a set of weights that form a balanced graph after a finite number of iterations (with probability one). In all the above cases, the resulting weight balanced digraph is shown to be unique and independent on how delays or packet drops manifest themselves during the execution of the algorithm.
In the third part of this thesis, we investigate the problem of integer weight balancing in a multi-component system under a static directed interconnection topology in the presence of lower and upper limit constraints on the edge weights. We present a novel distributed algorithm for obtaining admissible and balanced integer weights for the case when there are lower and upper weight constraints on the communication links. Compared with the distributed algorithms mentioned earlier, the additional constraint here is that each edge weight has to lie within a given interval, whereas communication exchanges (but not necessarily the assignment of weights) between neighboring nodes are assumed to be bidirectional.
In the fourth part of this thesis we investigate the problem of integer weight balancing in a multi-component system over a directed (static) interconnection topology, under lower and upper limit constraints on the edge weights, in the presence of bounded or unbounded delays (packet drops) in the communication links. Specifically, we present a novel distributed algorithm which solves the integer weight balancing problem under lower and upper weight constraints over the communication links for the case where arbitrary (time-varying and inhomogeneous) time delays affect the transmission at a particular link at a particular time. Furthermore, we present an event-based version of the proposed protocol in which each node autonomously decides when communication and control updates should occur so that the resulting network executions still result in a weight balanced digraph and all nodes eventually stop performing transmissions. Then, we extend the applicability of the proposed algorithm to the case where possible packet drops affect the communication links.