- / -

Σε έναν κόσμο που κατακλύζεται από δεδομένα, καθίσταται αναγκαία η αποδοτική οργάνωσή τους και η μετέπειτα επεξεργασία τους, με σκοπό την εύρεση και την ανάκτηση πληροφορίας για λήψη αποφάσεων. Στα πλαίσια της προσπάθειας αυτής έχουν δημοσιευθεί διάφορες μελέτες που στοχεύουν στην ανεύρεση σχέσεων μεταξύ των δεδομένων, οι οποίες μπορούν να αναδείξουν άγνωστες μέχρι πρότινος εξαρτήσεις και να επιτρέψουν την πρόγνωση και την πρόβλεψη μελλοντικών αποτελεσμάτων και αποφάσεων. Στην εργασία αυτή μελετάμε τους πιο διαδεδομένους αλγορίθμους εύρεσης κανόνων συσχετίσεων και ακολούθως προτείνουμε ένα σχήμα που χρησιμοποιεί ως βασική δομή για την ανάκτηση πληροφορίας από βάσεις δεδομένων συναλλαγών τα αντεστραμμένα αρχεία. Στόχος μας είναι η εύκολη παραγωγή κανόνων συσχέτισης αντικειμένων, βασιζόμενη στην αποδοτική αποθήκευση και ανάκτηση των Συχνών Συνόλων Αντικειμένων (Frequent Itemsets). Αρχικά επικεντρωνόμαστε στον τρόπο εύρεσης και αποθήκευσης ενός ελάχιστου συνόλου συναλλαγών, εκμεταλλευόμενοι την πληροφορία που εμπεριέχουν τα Κλειστά Συχνά Σύνολα Αντικειμένων (Closed Frequent Itemsets) και τα Μέγιστα Συχνά Σύνολα Αντικειμένων (Maximum Frequent Itemsets). Στη συνέχεια, αξιοποιώντας την αποθηκευμένη πληροφορία στα MFI και με ελάχιστο υπολογιστικό κόστος, προτείνουμε τον αλγόριθμο MFI-drive που απαντάει σε ερωτήματα εύρεσης υπερσυνόλου και υποσυνόλου αντικειμένων, καθώς και συνόλων αντικειμένων με προκαθορισμένο βαθμό ομοιότητας σε σχέση με ένα δεδομένο σύνολο. / --

Το αντικείμενο της παρούσας διπλωματικής εργασίας αφορά την ανάλυση και τον έλεγχο κυβερνοφυσικών δικτυωμένων δυναμικών συστημάτων. Ειδικότερα, μελετώνται γραμμικά χρονικά αμετάβλητα συστήματα μίας εισόδου με περιορισμούς τόσο στην είσοδο όσο και στο διάνυσμα καταστατικών μεταβλητών και προτείνονται στρατηγικές ανταγωνιστικού ελέγχου. Συγκεκριμένα, ένας βέλτιστος ελεγκτής εξασφαλίζει θετική αμεταβλητότητα ενός φραγμένου κυρτού πολυεδρικού συνόλου ως προς το σύστημα και ταυτόχρονα σύγκλιση της τροχιάς του διανύσματος κατάστασης στο μηδέν το συντομότερο δυνατό. Υποθέτουμε ότι ένας «ανταγωνιστής » ελεγκτής επιτυγχάνει κατά διαστήματα να αναλάβει τον έλεγχο του συστήματος και αποστέλλει μέσω του δικτύου εσφαλμένα σήματα εισόδου στοχεύοντας να οδηγήσει το διάνυσμα κατάστασης εκτός του πολυεδρικού συνόλου το συντομότερο δυνατό. Προσομοιώσεις καταδεικνύουν ότι το διακοπτικό φαινόμενο που ανακύπτει από τη διαδοχική εφαρμογή των δύο παραπάνω ελεγκτών προκαλεί μία περιοδική τροχιά του διανύσματος κατάστασης. Τα θεωρητικά εργαλεία που χρησιμοποιήθηκαν για την εξαγωγή των αποτελεσμάτων προέρχονται από τη θεωρία ευστάθειας Lyapunov και τη θεωρία αμετάβλητων συνόλων. / This thesis addresses the analysis and control of networked cyber-physical dynamical systems. We are mostly concerned with the study of linear, time-invariant systems with single input. The systems evolve in the discrete time and are subject to both state and input constraints and a certain number of adversary control strategies are proposed. A time-optimal control law guarantees positive invariance of a bounded convex polyhedral set with respect to the given system, while contracting the state space vector to the origin. At times, an adversary controller succeeds in gaining control of the system and sends false control commands attempting to lead the state vector outside the polyhedral set at the maximum admissible rate. Simulation studies highlight that consecutively applying the above control laws results in a periodic motion of the state vector. The theoretic tools used to obtain our conclusions associate with Lyapunov stability and set theory.

- / -

Στη διατριβή αυτή θα ασχοληθούμε με την Μπουλιανή ανάλυση σαν μια κατ'ευθείαν γενίκευση της μη συμβατικής ανάλυσης του Robinson, δηλ. της θεωρίας των Υπεργινομένων και τις εφαρμογές της στη θεωρία των Ασαφών συνόλων. / --

Στην παρούσα διπλωματική εργασία παρουσιάζονται Ατομιστικά Μοντέλα Διακριτών και Ενοποιημένων Ατόμων, τα οποία μπορούν να αποτελέσουν το πρώτο σημαντικό βήμα για τη μελέτη της βιολογικής μεμβράνης ή και ακόμα τη μελέτη συστημάτων μεμβρανών με πρωτεΐνες, σάκχαρα κ.α. Τέτοιες προσομοιώσεις θα μας δώσουν στοιχεία για μακροσκοπικές ιδιότητες της μεμβράνης (π.χ. διαχυτότητα) παρουσία συγκεκριμένων άλλων μακρομορίων. Αρχικά μελετάται σε ατομιστικό επίπεδο, με τα μοντέλα Διακριτών και Ενοποιημένων Ατόμων, τήγμα παλμιτικού οξέος (383Κ). Η καταλληλόλητα του νέου μοντέλου που εισήχθη για την περίπτωση των Ενοποιημένων Ατόμων εξετάζεται με βάση τις ιδιότητες διαμόρφωσης (λ.χ. κατανομές γωνιών) που εξάγονται από το μοντέλο Διακριτών Ατόμων. Στο μοντέλο Διακριτών Ατόμων χρησιμοποιήθηκε το αναλυτικότερο δυνατό δυναμικό (COMPASS). Τα αποτελέσματα ήταν άκρως ικανοποιητικά. Έχοντας ένα αξιόπιστο μοντέλο Ενοποιημένων Ατόμων προχωρήσαμε στο επόμενο βήμα. Επόμενο βήμα ήταν η μελέτη συστήματος παλμιτικού οξέος ανάμεσα από στρώμα νερού. Σημαντικό μειονέκτημα του μοντέλου Διακριτών Ατόμων για ένα τόσο μεγάλο σύστημα αποτελεί η περιορισμένη χρονική κλίμακα. Φαινόμενα σχηματισμού διπλοστοιβάδας παλμιτικού οξέος παρουσία νερού, είναι πολύ δύσκολο να μελετηθούν με χρήση μοντέλου Διακριτών Ατόμων λόγω των πολύ μικρών χρόνων που καλύπτουν. Επομένως, κρίνεται αναγκαία η χρήση μοντέλου Ενοποιημένων Ατόμων για το σύστημα PLM – νερό. Χρησιμοποιήσαμε το μοντέλο Ενοποιημένων Ατόμων που οι ίδιοι αναπτύξαμε, όπως και για την περίπτωση του τήγματος, για την περιγραφή του παλμιτικού οξέος, και το μοντέλο SPCE για το νερό, το οποίο είναι ευρέως αποδεκτό από την επιστημονική κοινότητα. Πέραν της σύγκρισης των μοντέλων Ενοποιημένων και Διακριτών Ατόμων που έγινε για το τήγμα του παλμιτικού οξέος, πραγματοποιήθηκαν και διάφοροι υπολογισμοί που αφορούν τη σταθεροποίηση του συστήματος (Autocorrelation faction of end-to-end distance vector), δομικές ιδιότητες (Radial Distribution Function), ιδιότητες διαμόρφωσης (angle distribution, radius of gyration, end-to-end distance vector) και θερμοδυναμικές ιδιότητες (density). Υπολογίστηκαν επίσης ο συντελεστής αυτοδιάχυσης (self diffusion coefficient) καθώς και το πλήθος δεσμών υδρογόνου. / This diploma thesis presents Atomistic Models of Discrete and Integrated atoms, which can be an important first step to study the biological membrane or even studying membrane systems with proteins, sugars, etc. Such simulations will give us data on macroscopic membrane properties (eg diffusivity) in the presence of certain other macromolecules. Initially we study melt palmitic acid (383K)in atomistic level. The suitability of the new model, introduced for the case of the Consolidated Atoms is examined by checking the configuration properties (eg angles distributions) derived from the model of Discrete Atoms. In the model of discrete atoms the disaggregated possible dynamic (COMPASS)was used. The results were highly satisfactory. Having a reliable model for Unified atoms we move to the next step. Next step was to study the system of palmitic acid between waterbed. Major drawback of the model of Discrete atoms for such a large system is the limited time scale. Phenomena of bilayer formation of palmitic acid in the presence of water is very difficult to be studied using discrete atoms model because of very short times covered. Therefore, it is necessary to use a model of integrated atoms for the system PLM - water. We used the model of Unified atoms we ourselves have developed, as in the case of the melt, for the description of palmitic acid, and the SPCE model for water, which is widely accepted by the scientific community. Beyond the comparison of models of integrated and discrete atoms made for the melt of palmitic acid, various calculations for the stabilisation the system (Autocorrelation faction of end-to-end distance vector), structural properties (Radial Distribution Function), properties configuration (angle distribution, radius of gyration, end-to-end distance vector) and thermodynamic properties (density)were made. The self-diffusion coefficient (self diffusion coefficient) and the number of hydrogen bonds were also calculated.

Οι αλγόριθμοι μηχανικής μάθησης είναι επιθυμητό να είναι σε θέση να γενικεύσουν για οποιασδήποτε κλάση με ίδια ακρίβεια. Δηλαδή σε ένα πρόβλημα δύο κλάσεων - θετικών και αρνητικών περιπτώσεων - ο αλγόριθμος να προβλέπει με την ίδια ακρίβεια και τα θετικά και τα αρνητικά παραδείγματα. Αυτό είναι φυσικά η ιδανική κατάσταση. Σε πολλές εφαρμογές οι αλγόριθμοι καλούνται να μάθουν από ένα σύνολο στοιχείων, το οποίο περιέχει πολύ περισσότερα παραδείγματα από τη μια κλάση σε σχέση με την άλλη. Εν γένει, οι επαγωγικοί αλγόριθμοι είναι σχεδιασμένοι να ελαχιστοποιούν τα σφάλματα. Ως συνέπεια οι κλάσεις που περιέχουν λίγες περιπτώσεις μπορούν να αγνοηθούν κατά ένα μεγάλο μέρος επειδή το κόστος λανθασμένης ταξινόμησης της υπερ-αντιπροσωπευόμενης κλάσης ξεπερνά το κόστος λανθασμένης ταξινόμησης της μικρότερη κλάση. Το πρόβλημα των ανομοιογενών συνόλων δεδομένων εμφανίζεται και σε πολλές πραγματικές εφαρμογές όπως στην ιατρική διάγνωση, στη ρομποτική, στις διαδικασίες βιομηχανικής παραγωγής, στην ανίχνευση λαθών δικτύων επικοινωνίας, στην αυτοματοποιημένη δοκιμή του ηλεκτρονικού εξοπλισμού, και σε πολλές άλλες περιοχές. Η παρούσα διπλωματική εργασία με τίτλο ‘Μηχανική Μάθηση με Ανομοιογενή Δεδομένα’ (Machine Learning with Imbalanced Data) αναφέρεται στην επίλυση του προβλήματος αποδοτικής χρήσης αλγορίθμων μηχανικής μάθησης σε ανομοιογενή/ανισοκατανεμημένα δεδομένα. Η διπλωματική περιλαμβάνει μία γενική περιγραφή των βασικών αλγορίθμων μηχανικής μάθησης και των μεθόδων αντιμετώπισης του προβλήματος ανομοιογενών δεδομένων. Παρουσιάζεται πλήθος αλγοριθμικών τεχνικών διαχείρισης ανομοιογενών δεδομένων, όπως οι αλγόριθμοι AdaCost, Cost Senistive Boosting, Metacost και άλλοι. Παρατίθενται οι μετρικές αξιολόγησης των μεθόδων Μηχανικής Μάθησης σε ανομοιογενή δεδομένα, όπως οι καμπύλες διαχείρισης λειτουργικών χαρακτηριστικών (ROC curves), καμπύλες ακρίβειας (PR curves) και καμπύλες κόστους. Στο τελευταίο μέρος της εργασίας προτείνεται ένας υβριδικός αλγόριθμος που συνδυάζει τις τεχνικές OverBagging και Rotation Forest. Συγκρίνεται ο προτεινόμενος αλγόριθμος σε ένα σύνολο ανομοιογενών δεδομένων με άλλους αλγόριθμους και παρουσιάζονται τα αντίστοιχα πειραματικά αποτελέσματα που δείχνουν την καλύτερη απόδοση του προτεινόμενου αλγόριθμου. Τελικά διατυπώνονται τα συμπεράσματα της εργασίας και δίνονται χρήσιμες ερευνητικές κατευθύνσεις. / Machine Learning (ML) algorithms can generalize for every class with the same accuracy. In a problem of two classes, positive (true) and negative (false) cases-the algorithm can predict with the same accuracy the positive and negative examples that is the ideal case. In many applications ML algorithms are used in order to learn from data sets that include more examples from the one class in relationship with another class. In general inductive algorithms are designed in such a way that they can minimize the occurred errors. As a conclusion the classes that contain some cases can be ignored in a large percentage since the cost of the false classification of the super-represented class is greater than the cost of false classification of lower class. The problem of imbalanced data sets is occurred in many ‘real’ applications, such as medical diagnosis, robotics, industrial development processes, communication networks error detection, automated testing of electronic equipment and in other related areas. This dissertation entitled ‘Machine Learning with Imbalanced Data’ is referred to the solution of the problem of efficient use of ML algorithms with imbalanced data sets. The thesis includes a general description of basic ML algorithms and related methods for solving imbalanced data sets. A number of algorithmic techniques for handling imbalanced data sets is presented, such as Adacost, Cost Sensitive Boosting, Metacost and other algorithms. The evaluation metrics of ML methods for imbalanced datasets are presented, including the ROC (Receiver Operating Characteristic) curves, the PR (Precision and Recall) curves and cost curves. A new hybrid ML algorithm combining the OverBagging and Rotation Forest algorithms is introduced and the proposed algorithmic procedure is compared with other related algorithms by using the WEKA operational environment. Experimental results demonstrate the performance superiority of the proposed algorithm. Finally, the conclusions of this research work are presented and several future research directions are given.

Έστω $V$ ένα σύνολο $n$ κορυφών και έστω ${\cal M}$ ένα πεπερασμένα αριθμήσιμο σύνολο $m$ ετικετών. Ένα γράφημα ετικετών προκύπτει αν αντιστοιχήσουμε σε κάθε κορυφή $v \in V$ ένα υποσύνολο $S_v$ του ${\cal M}$ και στη συνέχεια ενώσουμε όποιες κορυφές έχουν κοινά στοιχεία στα αντίστοιχα σύνολα ετικετών τους. Η παρούσα διδακτορική διατριβή ασχολείται με την εξέταση συνδυαστικών ιδιοτήτων και το σχεδιασμό και ανάλυση αλγορίθμων που σχετίζονται με δυο μοντέλα τυχαίων γραφημάτων που προκύπτουν από την επιλογή των συνόλων $S_v$ με βάση συγκεκριμένες κατανομές. Το πρώτο από αυτά τα μοντέλα ονομάζεται \emph{Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών} ${\cal G}_{n, m, p}$ (\textlatin{random intersection graphs model}) και κάθε σύνολο ετικετών $S_v$ διαμορφώνεται επιλέγοντας ανεξάρτητα κάθε ετικέτα με πιθανότητα $p$. Το δεύτερο μοντέλο ονομάζεται \emph{Ομοιόμορφο Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών} ${\cal G}_{n, m, \lambda}$ (\textlatin{uniform random intersection graphs model}) και κάθε σύνολο ετικετών $S_v$ επιλέγεται (ανεξάρτητα για κάθε κορυφή) ισοπίθανα ανάμεσα σε όλα τα υποσύνολα του ${\cal M}$ μεγέθους $\lambda$. Τα μοντέλα αυτά μπορούν να χρησιμοποιηθούν για να μοντελοποιήσουν καταστάσεις που αφορούν θέματα ασφάλειας σε δίκτυα αισθητήρων, αλλά και για την αναπαράσταση των συγκρούσεων (\textlatin{conflicts}) που δημιουργούνται σε περιπτώσεις διαμοιρασμού πόρων. Ακόμα, μπορούν να χρησιμοποιηθούν για τη μοντελοποίηση κοινωνικών γραφημάτων (\textlatin{social graphs}) στα οποία δυο οντότητες συνδέονται όταν έχουν κάποιο κοινό χαρακτηριστικό. Στο Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών ${\cal G}_{n, m, p}$ μελετάμε καταρχήν το πρόβλημα της ύπαρξης κύκλων \textlatin{Hamilton}. Συγκεκριμένα, αποδεικνύουμε ένα άνω φράγμα για την πιθανότητα επιλογής ετικετών $p$ έτσι ώστε κάθε στιγμιότυπο του ${\cal G}_{n, m, p}$ να περιέχει ένα κύκλο \textlatin{Hamilton} με πιθανότητα που τείνει στο 1 καθώς το $n$ τείνει στο άπειρο. Ακόμα, αναλύουμε δυο πιθανοτικούς αλγορίθμους που, για ορισμένες τιμές των παραμέτρων $m, p$ του μοντέλου, καταφέρνουν να κατασκευάσουν ένα κύκλο \textlatin{Hamilton} με πιθανότητα που τείνει στο 1, δηλαδή σχεδόν πάντα. Επίσης, δείχνουμε ότι σχεδόν κάθε στιγμιότυπο του ${\cal G}_{n, m, p}$ έχει καλή επεκτασιμότητα (\textlatin{expansion}), ακόμα και για $p$ πολύ κοντά στο κατώφλι συνεκτικότητας του μοντέλου. Στη συνέχεια, δίνουμε βέλτιστα άνω φράγματα (που ισχύουν με πιθανότητα που τείνει στο 1 σε ένα ευρύ πεδίο τιμών των παραμέτρων του μοντέλου) για σημαντικές ποσότητες που αφορούν τυχαίους περιπάτους σ ε στιγμιότυπα του ${\cal G}_{n, m, p}$ όπως ο χρόνος μίξης (\textlatin{mixing time}) και ο χρόνος κάλυψης (\textlatin{cover time}). Στο Ομοιόμορφο Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών ${\cal G}_{n, m, \lambda}$ μελετάμε την ύπαρξη κύκλων \textlatin{Hamilton} σε ένα ορισμένο πεδίο τιμών των παραμέτρων $m, \lambda$ του μοντέλου. Τέλος, υπολογίζουμε με τη βοήθεια της Πιθανοτικής Μεθόδου το κατώφλι ύπαρξης ανεξάρτητων συνόλων κορυφών. / Let $V$ be a set of $i$ vertices and let ${\cal M}$ be a finite set of $m$ labels. An intersection graph is then constructed by assigning to each vertex $v \in V$ a subset $S_v$ of ${\cal M}$ and then connecting every pair of vertices that have common labels in their corresponding label sets. This thesis concerns the study of combinatorial properties, as well as the design and analysis of algorithms on two kinds of random intersection graphs models that arise from different choices of the distribution that we use to construct the sets $S_v$. In the first of these models, called \emph{Random Intersection Graphs Model} ${\cal G}_{n, m, p}$, each set of labels $S_v$ is constructed by choosing independently each label with probability $p$. In the second model, called \emph{Uniform Random Intersection Graphs Model} ${\cal G}_{n, m, \lambda}$, each label set $S_v$ is selected equiprobably (and independently for each vertex $v$) among all subsets of ${\cal M}$ of size $\lambda$. These models can be used to abstract situations that concern the efficient and secure communication in sensor networks, but can also be used to model the conflicts that occur in oblivious resource sharing in distributed settings. Moreover, random intersection graph models can be used to model social graphs, in which two entities are connected when they have a common feature. In the Random Intersection Graphs Model ${\cal G}_{n, m, p}$, we first study the existence and efficient construction of Hamilton cycles. More specifically, we give an upper bound for the probability $p$ that is needed for almost every random instance $G_{n, m, p}$ of the model to have a Hamilton cycle. We also present two polynomial time, randomized algorithms for constructing Hamilton cycles in a wide range of the parameters $m, p$. Moreover, we show that almost every random instance of the ${\cal G}_{n, m, p}$ model is an expander, even for $p$ very close to the connectivity threshold. Finally, we give close to optimal bounds (that hold with probability that goes to 1 for a wide range of the parameters of the model) for important quantities (like the mixing time and the cover time) concerning random walks on random instances of ${\cal G}_{n, m, p}$. In the Uniform Random Intersection Graphs Model ${\cal G}_{n, m, \lambda}$ we study the existence of Hamilton cycles for a ce rtain range of the parameters $m, \lambda$. Finally, by using the probabilistic method we compute the independence number of ${\cal G}_{n, m, \lambda}$.

Στη μελέτη αυτή δεχόμεθα ως βασικές έννοιες την έννοια του συνόλου, την έννοια της συνάρτησης και την έννοια των φυσικών αριθμών. Ορίζουμε και αποδεικνύουμε ό,τι χρειάζεται από την θεωρία των συνόλων για να κατασκευάσουμε το σύστημα των ακεραίων αριθμών, το σύστημα των ρητών και τελικά το σύστημα των πραγματικών αριθμών. Σε όλα τα παραπάνω συστήματα ορίζεται η έννοια της διάταξης και αποδεικνύεται ότι το σύστημα των ρητών αριθμών είναι ένα Αρχιμήδειο σώμα που είναι πυκνό υποσύνολο του σώματος των πραγματικών αριθμών. Εν συνεχεία αποδεικνύονται οι χαρακτηριστικές ιδιότητες του σώματος των πραγματικών αριθμών, δηλαδή η ιδιότητα της πληρότητας (κάθε ακολουθία Cauchy συγκλίνει) και η ιδιότητα του άνω φράγματος (κάθε μή κενό υποσύνολο ,που είναι φραγμένο εκ των άνω, έχει ένα ελάχιστο άνω φράγμα (supremum). Όλα τα παραπάνω και πολλά σχετικά με αυτά περιέχονται στα κεφάλαια 1 ως και 7. Το κεφάλαιο 8 περιέχει μία συλλογή αποτελεσμάτων σχετικά με τους πληθικούς αριθμούς, οι οποίοι ορίζονται και μελετώνται στο κεφάλαιο 3. Πολλά από τα αποτελέσματα αυτά αφορούν στον πληθικό αριθμό των πραγματικών αριθμών. Στο κεφάλαιο 9 ορίζονται όλες οι έννοιες που χρειάζονται για να γίνουν κατανοητά τα αποτελέσματα σχετικά με την θεωρία των καλώς διατεταγμένων συνόλων και την θεωρία των διατακτικών αριθμών (ordinal numbers). Των κεφαλαίων 1, 2, 3 προτάσσεται ιστορικό σημείωμα που αφορά τις έννοιες που αναπτύσσονται σε αυτά. Ανάλογο ιστορικό σημείωμα προτάσσεται των υπολοίπων κεφαλαίων. / In this study, I acknowledge as basic meanings, the meaning of the set, the meaning of the function and the meaning of natural numbers. We define and prove whatever is needed from the theory of sets in order to construct the system of integral numbers, the system of rational numbers and ultimately the field of real numbers. In all the above systems the meaning of arrangement is defined and it is proven that the system of rational numbers is an Archimedean field which is a dense subset of the field of real numbers. Next, the characteristic properties of the field of real numbers are proven, i.e. the property of compactness (each sequence Cauchy converges)and the property of the upper bound (each non empty subset, which is bounded from above , has a minimum upper bound (supremum). All of the above and many other things related to this are contained in chapters 1 to 7. Chapter 8 contains a selection of results relating to cardinal numbers, which are defined and studied in chapter 3 Many of these results relate to cardinal number of reals numbers. In chapter 9, all the meanings which are needed in order for the results relating to the theory of the well-ordered sets and the theory of ordinal numbers, to become understood are included. Preceeding chapters 1, 2, 3 there is a historic note relating to the meanings which are developed in them. There is a corresponding historic note preceeding the rest of the chapters.

Οι πρόσφατες εξελίξεις στις ασύρματες επικοινωνίες και στα ηλεκτρονικά κυκλώματα έχουν επιτρέψει την ανάπτυξη υπολογιστικών διατάξεων χαμηλού κόστους και χαμηλής κατανάλωσης ισχύος, οι οποίες ενσωματώνουν δυνατότητες μέτρησης (sensing), επεξεργασίας και ασύρματης επικοινωνίας. Οι διατάξεις αυτές, οι οποίες έχουν ιδιαίτερα μικρό μέγεθος, καλούνται κόμβοι αισθητήρες. Ένα ασύρματο δίκτυο κόμβων αισθητήρων αποτελείται από ένα πλήθος κόμβων οι οποίοι έχουν αναπτυχθεί σε κάποια περιοχή ενδιαφέροντος προκειμένου να μετρούν κάποια μεταβλητή του περιβάλλοντος. Ανάμεσα σε πολλές εφαρμογές, ο εντοπισμός και η παρακολούθηση των θέσεων πηγών οι οποίες εκπέμπουν κάποιο σήμα (π.χ. ακουστικό, ηλεκτρομαγνητικό) αποτελεί ένα πολύ ενδιαφέρον θέμα, το οποίο μάλιστα μπορεί να χρησιμοποιηθεί και ως βάση για τη μελέτη άλλων προβλημάτων τα οποία εμφανίζονται στα ασύρματα δίκτυα αισθητήρων. Οι περισσότερες από τις υπάρχουσες τεχνικές εντοπισμού θέσης μιας πηγής από μια συστοιχία αισθητήρων μπορούν να ταξινομηθούν σε δυο κατηγορίες: (α) Τις τεχνικές οι οποίες χρησιμοποιούν μετρήσεις διεύθυνσης άφιξης (Direction of Arrival, DOA) και (β) τις τεχνικές οι οποίες χρησιμοποιούν μετρήσεις διαφοράς χρόνων άφιξης (Time Difference of Arrival, TDOA). Ωστόσο, οι τεχνικές αυτές απαιτούν υψηλό ρυθμό δειγματοληψίας και ακριβή συγχρονισμό των κόμβων και δε συνάδουν έτσι με τις περιορισμένες ικανότητες των κόμβων αισθητήρων. Για τους λόγους αυτούς, το ενδιαφέρον έχει στραφεί σε μια τρίτη κατηγορία τεχνικών οι οποίες χρησιμοποιούν μετρήσεις ισχύος (Received Signal Strength, RSS). Το πρόβλημα του εντοπισμού θέσης χρησιμοποιώντας μετρήσεις ισχύος είναι ένα πρόβλημα εκτίμησης, όπου οι μετρήσεις συνδέονται με τις προς εκτίμηση παραμέτρους με μη-γραμμικό τρόπο. Στα πλαίσια της Διδακτορικής Διατριβής ασχολούμαστε αρχικά με την περίπτωση όπου επιθυμούμε να εκτιμήσουμε τη θέση και την ισχύ μιας πηγής χρησιμοποιώντας μετρήσεις ισχύος οι οποίες φθίνουν με βάση το αντίστροφο του τετραγώνου της απόστασης ανάμεσα στην πηγή και το σημείο μέτρησης. Για το πρόβλημα αυτό, προτείνουμε έναν εκτιμητή ο οποίος δίνει τις παραμέτρους της πηγής ως λύση ενός γραμμικού προβλήματος ελαχίστων τετραγώνων. Στη συνέχεια, υπολογίζουμε κατάλληλα βάρη και προτείνουμε έναν εκτιμητή ο οποίος δίνει τις παραμέτρους της πηγής ως λύση ενός προβλήματος ελαχίστων τετραγώνων με βάρη. Ακόμα, τροποποιούμε κατάλληλα τον τελευταίο εκτιμητή έτσι ώστε να είναι δυνατή η κατανεμημένη υλοποίησή του μέσω των προσαρμοστικών αλγορίθμων Least Mean Square (LMS) και Recursive Least Squares (RLS). Στη συνέχεια, εξετάζουμε την περίπτωση όπου ενδιαφερόμαστε να εκτιμήσουμε τη θέση μιας πηγής αλλά δεν έχουμε καμιά πληροφορία σχετικά με το μοντέλο εξασθένισης της ισχύος. Έτσι, υποθέτουμε πως αυτό περιγράφεται από μια άγνωστη γνησίως φθίνουσα συνάρτηση της απόστασης. Αρχικά, προσεγγίζουμε το πρόβλημα εκτίμησης κάνοντας την υπόθεση πως οι θέσεις των κόμβων αποτελούν τυχαία σημεία ομοιόμορφα κατανεμημένα στο επίπεδο. Χρησιμοποιώντας την υπόθεση αυτή, υπολογίζουμε εκτιμήσεις για τις αποστάσεις ανάμεσα στους κόμβους και την πηγή, και αναπτύσσουμε έναν αλγόριθμο εκτίμησης της θέσης της πηγής. Στη συνέχεια, προσεγγίζουμε το πρόβλημα εκτίμησης χωρίς την υπόθεση περί ομοιόμορφης κατανομής των θέσεων των κόμβων στο επίπεδο. Προτείνουμε μια κατάλληλη συνάρτηση κόστους για την περίπτωση αυτή, και δείχνουμε την ύπαρξη μιας συνθήκης υπό την οποία η βέλτιστη λύση μπορεί να υπολογιστεί. Η λύση αυτή είναι εσωτερικό σημείο ενός κυρτού πολυγώνου, το οποίο ονομάζουμε ταξινομημένο τάξης-K κελί Voronoi. Έτσι, δίνουμε αλγορίθμους υπολογισμού της λύσης αυτής, καθώς και κατανεμημένους αλγορίθμους οι οποίοι βασίζονται σε προβολές σε κυρτά σύνολα. Ακόμα, ασχολούμαστε με τις ιδιότητες των κελιών αυτών στην περίπτωση όπου οι θέσεις των κόμβων αισθητήρων είναι ομοιόμορφα κατανεμημένες στο επίπεδο και υπολογίζουμε κάποια φράγματα για το εμβαδόν τους. Τέλος, ασχολούμαστε με την περίπτωση όπου ενδιαφερόμαστε να εκτιμήσουμε τις θέσεις πολλαπλών πηγών με γνωστό μοντέλο εξασθένισης της ισχύος. Για το πρόβλημα αυτό, αρχικά προτείνουμε έναν αλγόριθμο διαδοχικής εκτίμησης και ακύρωσης της συνεισφοράς κάθε πηγής, προκειμένου να υπολογιστούν σταδιακά οι θέσεις όλων των πηγών. Ο αλγόριθμος αυτός, αποτελείται από τρία βήματα κατά τα οποία πρώτα υπολογίζεται μια προσεγγιστική θέση για την πηγή, στη συνέχεια εκτιμάται ένα σύνολο κόμβων το οποίο δέχεται μικρής έντασης παρεμβολή από τις υπόλοιπες πηγές, και τέλος επιχειρείται μια λεπτομερέστερη εκτίμηση της θέσης κάθε πηγής. Στη συνέχεια, επεκτείνοντας την τεχνική αυτή, προτείνουμε έναν επαναληπτικό αλγόριθμο εκτίμησης ο οποίος βασίζεται στον αλγόριθμο εναλλασσόμενων προβολών (Alternating Projections). Εξετάζουμε επίσης μεθόδους οι οποίες οδηγούν στη μείωση της υπολογιστικής πολυπλοκότητας του αλγορίθμου αυτού. / Technology advances in microelectronics and wireless communications have enabled the development of small-scale devices that integrate sensing, processing and short-range radio capabilities. The deployment of a large number of such devices, referred to as sensor nodes, over a territory of interest, defines the so-called wireless sensor network. Wireless sensor networks have attracted considerable attention in recent years and have motivated many new challenges, most of which require the synergy of many disciplines, including signal processing, networking and distributed algorithms. Among many other applications, source localization and tracking has been widely viewed as a canonical problem of wireless sensor networks. Furthermore, it constitutes an easily perceived problem that can be used as a vehicle to study more involved information processing and organization problems. Most of the source localization methods that have appeared in the literature can be classified into two broad categories, according to the physical variable they utilize. The algorithms of the first category utilize “time delay of arrival”(TDOA) measurements, and the algorithms of the second category use “direction of arrival” (DOA) measurements. DOA estimates are particularly useful for locating sources emitting narrowband signals, while TDOA measurements offer the increased capability of localizing sources emitting broadband signals. However, the methods of both categories impose two major requirements that render them inappropriate to be used in wireless sensor networks: (a) the analog signals at the outputs of the spatially distributed sensors should be sampled in a synchronized fashion, and (b) the sampling rate used should be high enough so as to capture the features of interest. These requirements, in turn, imply that accurate distributed synchronization methods should be implemented so as to keep the remote sensor nodes synchronized and that high frequency electronics as well as increased bandwidth are needed to transmit the acquired measurements. Due to the aforementioned limitations, source localization methods that rely upon received signal strength (RSS) measurements - originally explored for locating electromagnetic sources - have recently received revived attention. In this Thesis, we begin our study by considering the localization of an isotropic acoustic source using energy measurements from distributed sensors, in the case where the energy decays according to an inverse square law with respect to the distance. While most acoustic source localization algorithms require that distance estimates between the sensors and the source of interest are available, we propose a linear least squares criterion that does not make such an assumption. The new criterion can yield the location of the source and its transmit power in closed form. A weighted least squares cost function is also considered, and distributed implementation of the proposed estimators is studied. Numerical results indicate significant performance improvement as compared to a linear least squares based approach that utilizes energy ratios, and comparable performance to other estimators of higher computational complexity. In the sequel, we turn our attention to the case where the energy decay model is not known. For solving the localization problem in this case, we first make the assumption that the locations of the nodes near the source can be well described by a uniform distribution. Using this assumption, we derive distance estimates that are independent of both the energy decay model and the transmit power of the source. Numerical results show that these estimates lead to improved localization accuracy as compared to other model-independent approaches. In the sequel, we consider the more general case where the assumption about the uniform deployment of the sensors is not required. For this case, an optimization problem that does not require knowledge of the underlying energy decay model is proposed, and a condition under which the optimal solution can be computed is given. This condition employs a new geometric construct, called the sorted order-K Voronoi diagram. We give centralized and distributed algorithms for source localization in this setting. Finally, analytical results and simulations are used to verify the performance of the developed algorithms. The next problem we consider is the estimation of the locations of multiple acoustic sources by a network of distributed energy measuring sensors. The maximum likelihood (ML) solution to this problem is related to the optimization of a non-convex function of, usually, many variables. Thus, search-based methods of high complexity are required in order to yield an accurate solution. In order to reduce the computational complexity of the multiple source localization problem, we propose two methods. The first method proposes a sequential estimation algorithm, in which each source is localized, its contribution is cancelled, and the next source is considered. The second method makes use of an alternating projection (AP) algorithm that decomposes the original problem into a number of simpler, yet also non-convex, optimization steps. The particular form of the derived cost functions of each such optimization step indicates that, in some cases, an approximate form of these cost functions can be used. These approximate cost functions can be evaluated using considerably lower computational complexity. Thus, a low-complexity version of the AP algorithm is proposed. Extensive simulation results demonstrate that the proposed algorithm offers a performance close to that of the exact AP implementation, and in some cases, similar performance to that of the ML estimator.