01
Μαρ
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΣΤΑΥΡΟΥ ΜΗΤΡΟΛΑΡΗ
με θέμα
Κατανεμημένος Συμπερασμός σε Ασύρματα Δίκτυα με Περιορισμούς Καθυστέρησης
Delay-Constrained Distributed Inference in Wireless Networks
Εξεταστική Επιτροπή
Καθηγητής Άγγελος Μπλέτσας (επιβλέπων)
Καθηγητής Διονύσιος Χριστόπουλος
Καθηγητής Αντώνιος Δεληγιαννάκης
Abstract
Belief propagation (BP)-based algorithms are powerful message-passing algorithms that exploit the conditional independences of specific variables on a carefully crafted graph and efficiently compute marginal distributions or maximum a posteriori (MAP) estimates (of the involved variables). Motivated by the convergence guarantees of Gaussian belief propagation (GBP) under high-order factorization and asynchronous scheduling, we study how this algorithm can be utilized by resource-limited wireless networks for in-network processing. We show that there are cases where a particular asynchronous variant of GBP converges in theory but diverges when transmission delays are included. A simple solution is proposed, based on a coordinator, and its performance in terms of convergence time is examined, through simulations; optimized resource allocation is performed, including the bottleneck assignment problem (BAP) formulation, taking into account transmission delays, as well as bandwidth-limited wireless channels and external interference. Next, we study the max-product BP algorithm, as a distributed solver of BAP, i.e., a matching problem between tasks and agents, with the objective of minimizing the costliest pairing, for which only a couple of distributed algorithms currently exist. We examine a line of work which addresses this problem, provided that a unique solution exists and simplify the message calculations; specifically, we propose new BP message expressions, with linear complexity (as opposed to quadratic of prior art). Furthermore, we provide an asynchronous variant and study its convergence and correctness guarantees, using the notion of generalized computation trees. Simulations results show convergence of both the synchronous and asynchronous variant.