Statistical physics algorithms for wireless communication networks

Abstract

This thesis is devoted to the application of some well known mathematical tools, developed in the field of theoretical physics, to the performance analysis of wireless communication systems. The optimization problems, formulated in terms of the statistical mechanics framework, are solved via the widely known message passing algorithm. Specifically, the message passing algorithm was modified and applied to random networks, modeled as bipartite acyclic graphs. Special emphasis was given to sparse graphs due to the low probability of presence of cycles and the consequent ease of converting them into trees, such as Cayley trees. These specific graphs can accurately represent the properties of wireless networks with random connectivity and serve as a tool for modeling cognitive radio-enabled IoT (Internet of Things) networks. In summary, techniques from the theory of spin glasses in statistical physics were applied to construct iterative algorithms for detecting and locating multiple emitting sources from secondary wireless sensors. The main goal of this thesis was to address the problem in a simple semi-analytical way. Additionally, the representation of bipartite graphs in network topologies was examined for cases where there is no cooperation between different network elements (primary sources, secondary users). The problem mentioned above focused on algorithms for message passing between different entities. The first part of this research, concerning such an architecture, was presented in [1], where analytical expressions for the density of sources (primary and secondary) were initially generated in the form of a closed set of equations and solved using the population dynamics algorithm. Furthermore, the case of random connectivity between nodes in a Rayleigh fading channel was studied through extensive simulations. After comparing the two algorithms in multiple implementations of random two-dimensional networks, their results were shown to be almost identical. Finally, the convergence speed of the message passing algorithm was also studied and found to be linear with the number of sources. In the second part of this study, the detection of sources was examined using the Replica Symmetry Method, producing results similar to the Bethe free energy method. The probability of false source detection was derived as a function of two iterative equations, including cases where sources are out of the range of the secondary sources/sensors. The work in [2] included analytical expressions for the Replica Symmetry Method, a comparison of the average communication energy for the message passing algorithm with a nearest neighbor algorithm, a comparison of the message passing algorithm with myopic algorithms and a detailed comparison of the message passing algorithm with other multiple source detection methods. Thus, this study provided an analytical methodology for detecting the state of multiple sources in a network with secondary users/sensors in the presence of noise. In the final part of this thesis, the focus is on the study of multi-hop communication networks with relays in cases of limited infrastructure for potential use of networks with extended coverage. Specifically, the capacity and the probability of successful signal transmission were calculated and signal reception models were analyzed using tools from stochastic geometry [3, 4]. This analysis focused on simultaneous (orthogonal or coexisting) transmission for asymptotic regions with nodes distributed according to a Poisson distribution and in regions with low bit error rate.

Σε αυτή τη διατριβή παρουσιάζονται διάφορες εφαρμογές για ανάλυση της επίδοσης ασυρμάτων δικτύων με τη βοήθεια κάποιων ευρέως διαδεδομένων μαθηματικών εργαλειών που έχουν αναπτυχθεί στο τομέα της θεωρητικής φυσικής. Επιλύονται προβλήματα βελτιστοποίησης μέσω του ευρέως διαδεδομένου αλγόριθμου διαβίβασης μηνυμάτων μέσω της μοντελοποίησης τους στο πλαίσο της στατιστικής φυσικής. Συγκεκριμένα τροποποίηθηκε και εφάρμοστηκε ένας αλγόριθμος διαβίβασης μηνυμάτων (message passing) σε τυχαία δίκτυα, που μοντελοποιήθηκαν σαν διμερείς ακυκλικοί γράφοι. Ιδιαίτερη έμφαση δόθηκε σε αραιούς γράφους, λόγω της πολύ μικρής πιθανότητας εύρεσης κύκλων και συνεπώς της εύκολης μετατροπής τους σε δέντρα, όπως για παράδειγμα τα δέντρα Cayley. Οι συγκεκριμένοι γράφοι, μπορούν να αποδώσουν με εξαιρετική ακρίβεια τις ιδιότητες ασύρματων δικτύων με τυχαία συνδεσιμότητα και αποτελούν εργαλείο για τη μοντελοπίηση γνωσιακών δικτύων IoT (Cognitive Radio-enabled IoT). Συνοπτικά, εφάρμοστηκαν τεχνικές από τη θεωρία των spin-glasses στην Στατιστική Φυσική για την κατασκευή επαναληπτικών αλγορίθμων με σκοπό την ανίχνευση και τον εντοπισμό πολλαπλών ασύρματων πηγών από ασύρματους αισθητήρες. Ο απώτερος σκοπός της μελέτης αυτής ήταν να διαστατοποιηθεί το πρόβλημα με απλό ημιαναλυτικό τρόπο. Παράλληλα, μελετήθηκε και η απεικόνιση διμερών γράφων σε τοπολογίες δικτύων για τις περιπτώσεις που δεν υπάρχει συνεργασία μεταξύ των διαφορετικών δικτυακών στοιχείων (κύριες πηγές, δευτερεύοντες χρήστες). Το προαναφερθέν πρόβλημα εστιάζει σε αλγορίθμους μεταβίβασης μηνυμάτων διαφορετικών οντοτήτων. Το πρώτο μέρος αυτής της έρευνας που αφορά μια τέτοια αρχιτεκτονική έχει παρουσιαστεί και στο [1], όπου αρχικά παρήχθησαν αναλυτικές εκφράσεις με τη μορφή κλειστού συνόλου εξισώσεων για την πυκνότητα των πηγών (κυρίων και δευτερευόντων) οι οποίες και λύθηκαν με τη χρήση του αλγορίθμου της πληθυσμιακής δυναμικής (population dynamics). Μελετήθηκε επίσης - μέσω εκτενών προσομοιώσεων - η περίπτωση της τυχαίας συνδεσιμότητας μεταξύ κόμβων σε κανάλι διαλείψεων Rayleigh όπου μετά τη σύγκριση των δύο αλγοριίθμων σε πολλαπλές υλοποιήσεις τυχαίων δισδιάστατων δικτύων, αποδείχθηκε η σχεδόν ταύτιση των αποτελεσμάτων τους. Τέλος, μελετήθηκες και η ταχύτητα σύγκλισης του αλγόριθμου μεταβίβασης μηνυμάτων η οποία αποδείχθηκε γραμμική σε συνάρτηση με τον αριθμό των πηγών. Στο δεύτερο μερός αυτής της μελέτης, εξετάστηκε η εύρεση της σωστής ανίχνευσης πηγών με τη βοήθεια της μεθόδου της συμμετρίας των αντιγράφων (Replica Symmetry Method) η οποία είχε ίδια αποτελέσματα με την μέθοδο της ελεύθερης ενέργειας Bethe. Η πιθανότητα εσφαλμένης ανίχνευσης πηγών εξήχθη σαν συνάρτηση δυο επαναληπτικών εξισώσεων ενσωματώνοντας και περιπτώσεις όπου οι πηγές είναι εκτός της εμβέλειας των δευτερευόντων πηγών/αισθητήρων. Στην εργασία [2], συμπεριλήφθησαν οι αναλυτικές εκφράσεις της μεθόδου της συμμετρίας των αντιγράφων, η σύγκριση της μέσης ενέργειας επικοινωνίας γιατην περίπτωση του αλγορίθμου μεταβίβασης μηνυμάτων με έναν αλγόριθμο πλησιέστερου γείτονα (nearest neighbour) όπου και αποδείξαμε σχεδόν όμοια αποτελέσματα για πολύ πυκνά δίκτυα, η σύγκριση του αλγορίθμου μεταβίβασης μηνυμάτων με μυωπικούς αλγόριθμους οι οποίοι παρ’όλη την απλότητας τους δεν έχουν την ίδια απόδοση και τέλος η λεπτομερής σύγκριση του του αλγορίθμου μεταβίβασης μηνυμάτων με άλλε μεθόδους ανίχνευσης πολλαπλών πηγών. Η παραπάνω μελέτη παρέδωσε μία αναλυτική μεθοδολογία για την ανίχνευση της κατάστασης πολλαπλών πηγών σε ένα δίκτυο με δευτερεύοντες χρήστες/αισθητήρες παρουσιά θορύβου. Στο τελευταίο μέρος αυτής της διατριβής εστίαζει στη μελέτη πολυ-βηματικών (multihop) δικτύων επικοινωνιών με αναμεταδότες σε περιπτώσεις περιορισμένης υποδομής για πιθανή μελλοντική χρήση δικτύων με επέκταση ακτίνας κάλυψης. Συγκεκριμένα, υπολόγιζεαι η χωρητικότητα και η πιθανότητα επιτυχούς μετάδοσης σήματος και ανέλυονται τα συγκεκριμένα μοντέλα λήψης σήματος με εργαλεία από τη στοχαστική γεωμετρία [3,4]. H ανάλυση αυτή επικεντρώθηκε σε ταυτόχρονη μετάδοση (είτε ορθογώνια είτε συνυπάρχουσα) για ασυμπτωτικές περιοχές με κόμβους κατανεμημένους κατά Poisson και σε περιοχές με χαμηλό BER.