Η δρομολόγηση και ανάθεση μηκών κύματος (routing and wavelength assignment - RWA) αποτελεί ένα πολύ σημαντικό πρόβλημα, που απασχολεί τους σχεδιαστές WDM οπτικών δικτύων και είναι γνωστό, πως είναι NP-πλήρες. Στην εργασία αυτή σχεδιάζουμε και υλοποιούμε έναν αλγόριθμο για το στατικό RWA, που βασίζεται σε έναν προτεινόμενο σχηματισμό (μη ακέραιου) γραμμικού προγραμματισμού (linear programming - LP). Ισχυριζόμαστε, πως ο σχηματισμός αυτός είναι σε θέση να παρέχει ακέραιες βέλτιστες λύσεις (παρά την εν γένει μη ακέραια φύση του) για ένα μεγάλο ποσοστό στιγμιότυπων εισόδου, οδηγώντας έτσι σε αντίστοιχες ακριβείς λύσεις του RWA. Η πολυπλοκότητα του αλγόριθμου κυριαρχείται από το χρόνο εκτέλεσης του αλγόριθμου Simplex, ο οποίος θεωρείται αποδοτικός για μια μεγάλη πλειοψηφία στιγμιότυπων εισόδου. Στα διαφανή (πλήρως οπτικά) δίκτυα, η ποιότητα του σήματος υπόκειται σε μια ποικιλία από φυσικές εξασθενήσεις, όπως είναι η διασπορά λειτουργίας πόλωσης (polarization mode dispersion - PMD), ο θόρυβος αυθόρμητης εκπομπής ενισχυτή (amplified spontaneous emission - ASE - noise) και η χρωματική διασπορά (chromatic dispersion - CD). Αυτές οι εξασθενήσεις μοντελοποιούνται γραμμικά και μπορούν να αντιμετωπιστούν αποτελεσματικά από ένα σύνολο αναλυτικών τύπων ως επιπρόσθετοι περιορισμοί στο RWA. Εφαρμόζουμε τον αλγόριθμό μας και εκτελούμε RWA βασισμένο σε περιορισμούς εξασθένησης, με σκοπό να παρατηρήσουμε συγκριτικά αποτελέσματα στην απόδοση ενός τυπικού μητροπολιτικού δικτύου υπό διάφορες παραμέτρους του δικτύου και των εξασθενήσεων, όπως είναι ο ρυθμός bit, ο τύπος και το κέρδος των ενισχυτών, η χρησιμοποιούμενη διάταξη διαμόρφωσης, κλπ. / Routing and wavelength assignment (RWA) is a very important problem concerning WDM optical network designers and is known to be NP-complete. In this work, we design and implement an algorithm for the static RWA, that is based on a proposed (not integer) linear programming formulation. We claim, that this formulation is able to provide integer optimal solutions (despite its non integral nature) for a large fraction of input instances, yielding thus to corresponding exact RWA solutions. The algorithm's complexity is dominated by the execution time of Simplex LP-solver, that is considered efficient in the great majority of all possible input instances. In transparent (all-optical) networks, the signal quality is subject to a variety of physical impairments, such as polarization mode dispersion (PMD), amplified spontaneous emission (ASE) noise and chromatic dispersion (CD). Those impairments are linearly modeled and are handled effectively by a set of analytical formulae as additional constraints on RWA. We apply our algorithm to perform impairment-constraint based RWA, in order to obtain comparative results of a typical metropolitan network's performance under various network and impairment parameters, such as bit rate, amplifier gain and type, modulation format used, etc.

Η ασύρματη επικοινωνία, στις μέρες μας, αποκτά ιδιαίτερη αξία σε μια χώρα όπως η Ελλάδα, όπου η μορφολογία του εδάφους, δεν επιτρέπει σε αρκετά γεωγραφικά διαμερίσματα την εγκατάσταση και χρήση ευρυζωνικών μέσων μετάδοσης όπως για παράδειγμα οι οπτικές ίνες. Ειδικότερα ο τομέας της κινητής τηλεφωνίας είναι ένας ταχύτατα εξελισσόμενος τομέας καθώς στις μέρες μας βιώνουμε το πέρασμα από τη δεύτερη γενιά συστημάτων κινητών τηλεπικοινωνιών προς την τρίτη. Στην εξέλιξη του τομέα αυτού συμβάλουν τα μέγιστα και οι απαιτήσεις των σύγχρονων καιρών για ένα ενοποιημένο και λειτουργικό σύστημα κινητής τηλεφωνίας με σκοπό την παροχή μιας πληθώρας υπηρεσιών στους συνδρομητές. Η διπλωματική αυτή έχει σαν σκοπό να μελετήσει την μετάδοση πολυμεσικών δεδομένων όπως εικόνα και ήχος μέσα από την έννοια του streaming, πάνω από ασύρματα δίκτυα 3ης γενιάς (UMTS). Λαμβάνοντας υπό όψη τις δυσκολίες που συνεπάγεται η ασύρματη μετάδοση δεδομένων, όπως απώλεια πακέτων εξαιτίας λαθών ή συμφόρησης στο δίκτυο, αλλά και την καθυστέρηση που πολλές φορές παρατηρείται, προτείνεται ένας μηχανισμός για τη δυνατότητα προσαρμογής του ρυθμού μετάδοσης των πολυμεσικών δεδομένων. Στόχος είναι η αντιμετώπιση των παραπάνω προβλημάτων, αλλά και η προσπάθεια για την όσο το δυνατόν ανεμπόδιστη λειτουργία της streaming υπηρεσίας ακόμα και σε μη ευνοϊκές δικτυακές συνθήκες. Ο έλεγχος του ρυθμού μετάδοσης αποτελεί ένα σημαντικό θέμα τόσο στα ενσύρματα όσο και στα ασύρματα δίκτυα μιας και σχετίζεται με τη σταθερότητα του δικτύου, συμβάλλει στη δίκαιη κατανομή του bandwidth μεταξύ των ροών δεδομένων και στην ομαλή μετάδοση πολυμεσικών δεδομένων. Μία μέθοδος ελέγχου και προσαρμογής του ρυθμού μετάδοσης δεδομένων πάνω από δίκτυα είναι γνωστή σαν TCP Friendly Rate Control (TFRC). Χρησιμοποιείται κυρίως στα ενσύρματα δίκτυα και σύμφωνα με αυτή, ο ρυθμός μετάδοσης δεδομένων είναι συνάρτηση κάποιων παραμέτρων οι οποίες αντιπροσωπεύουν την κατάσταση που επικρατεί στο δίκτυο. Οι παράμετροι αυτοί είναι το μέγεθος των πακέτων, ο ρυθμός απώλειας των πακέτων και το Round Trip Time (RTT). Η μέθοδος αυτή μπορεί να χρησιμοποιηθεί και στα ασύρματα δίκτυα με τη βοήθεια απαραίτητων τροποποιήσεων/παραλλαγών αλλά και υπό την προϋπόθεση ότι λαμβάνονται υπόψη οι ιδιαιτερότητες της ασύρματης μετάδοσης. Στα πλαίσια της έρευνας που έγινε στην εργασία αυτή, θα δείξουμε την ικανότητα που μπορεί να έχει ένας streaming server για έλεγχο και προσαρμογή του ρυθμού μετάδοσης πολυμεσικών δεδομένων σύμφωνα με τα προβλήματα που προαναφέρθηκαν και τις τρέχουσες συνθήκες του δικτύου. Βασικό στοιχείο στην προσπάθεια αυτή αποτέλεσε η λειτουργία του TFRC μηχανισμού σε συνδυασμό με τη χρήση του RTP πρωτοκόλλου. Το Real-Time Transport Protocol (RTP) παρέχει μια από άκρο σε άκρο υπηρεσία για αποστολή δεδομένων σε πραγματικό χρόνο. Εφαρμογές που χρησιμοποιούν το πρωτόκολλο αυτό είναι κυρίως υπηρεσίες για μετάδοση (streaming) ήχου (φωνή) και βίντεο. Παρόλο που το RTP πρωτόκολλο δεν παρέχει κάποια εγγύηση για την έγκαιρη παράδοση των πακέτων, εντούτοις περιέχει ένα μηχανισμό για την απεικόνιση της κατάστασης του δικτύου και των χαρακτηριστικών της σύνδεσης μεταξύ των δύο άκρων. Πρόκειται για το RTP Control Protocol (RTCP) το οποίο αποστέλλει πακέτα (αναφορές) μεταξύ του streaming server και ενός χρήστη, με πληροφορία όπως ο ρυθμός απώλειας πακέτων, η καθυστέρηση μετάδοσης και ο RTT χρόνος. Με τον τρόπο αυτό, και για τις ανάγκες της ασύρματης μετάδοσης βίντεο σε πραγματικό χρόνο από έναν server προς έναν κινητό χρήστη μπορεί να γίνει μια συνεργασία του TFRC μηχανισμού και των RTP και RTCP πρωτοκόλλων. Ο server, κατά τη διάρκεια αποστολής (streaming) πολυμεσικών δεδομένων σε πραγματικό χρόνο προς ένα κινητό χρήστη, θα μπορεί να γνωρίζει ανά πάσα στιγμή τα χαρακτηριστικά της ασύρματης σύνδεσης, βασιζόμενος στα RTCP πακέτα που θα του στέλνει ο χρήστης και στη συνέχεια με τη βοήθεια του TFRC να κάνει υπολογισμό ενός άνω φράγματος για τον επιτρεπτό ρυθμό μετάδοσης των δεδομένων. Η δυνατότητα για αλλαγή του ρυθμού μετάδοσης από τον server ανάλογα με τις δικτυακές συνθήκες, βασίζεται στο γεγονός της ικανότητας να επιλέγει το προς μετάδοση βίντεο μέσα από ένα σύνολο διαφορετικών κωδικοποιήσεων του βίντεο αυτού. Με άλλα λόγια, ο streaming server διατηρεί διάφορες εκδόσεις (αρχεία) του ίδιου βίντεο, με τη μόνη διαφορά ότι είναι κωδικοποιημένα σε διαφορετικούς ρυθμούς (Kbps) με βάση κάποιο πρότυπο (π.χ MPEG-2). Βέβαια είναι γεγονός, ότι ένας χαμηλός ρυθμός κωδικοποίησης της πολυμεσικής πληροφορίας, σε σχέση με ένα υψηλό ρυθμό, συνεπάγεται μια μέτρια ποιότητα στην εικόνα του βίντεο. Από την άλλη όμως πλευρά, η μετάδοση μέτριας ποιότητας (χαμηλού ρυθμού) βίντεο, συνδέεται με το χαμηλό ρυθμό στην μετάδοση των πολυμεσικών δεδομένων, γεγονός που είναι επιθυμητό σε περιπτώσεις όπου στο δίκτυο παρατηρείται συμφόρηση, μεγάλες καθυστερήσεις και απώλειες πακέτων. Κατά ανάλογο τρόπο, όταν στο δίκτυο δεν παρατηρούνται ιδιαίτερα προβλήματα, είναι επιθυμητή η μετάδοση από τον streaming server βίντεο υψηλού ρυθμού (καλής ποιότητας), καθώς το διαθέσιμο εύρος ζώνης είναι σε θέση να εξυπηρετήσει τις απαιτήσεις για μετάδοση πολυμεσικών δεδομένων με υψηλό ρυθμό. Για την επιβεβαίωση των όσων αναφέρθηκαν παραπάνω, έγιναν μια σειρά από πειράματα κάνοντας χρήση ενός εμπορικού δικτύου κινητής τηλεφωνίας βασισμένο στην τεχνολογία 3ης γενιάς. Κάποιες υποθέσεις που έγιναν σχετικά με το σενάριο αυτό, αφορούν το διαθέσιμο bandwidth του ασύρματου καναλιού, το ρυθμό απώλειας πακέτων, το μέγεθος των πακέτων και την κίνηση στο δίκτυο. Θα πρέπει να σημειωθεί ότι η απώλεια των πακέτων μπορεί να οφείλεται τόσο στο ενδεχόμενο να παρατηρείται μεγάλη κίνηση στους κόμβους του δικτύου αλλά και σε αυτό της μη σωστής λήψης, εξαιτίας των παραγόντων εκείνων που επηρεάζουν την ασύρματη μετάδοση. Για την υλοποίηση του παραπάνω σεναρίου και των πειραμάτων έγινε χρήση ενός φορητού υπολογιστή (laptop) ο οποίος είχε τον ρόλο του κινητού χρήστη εξοπλισμένος με μια κάρτα για την ασύρματη πρόσβαση σε 3G δίκτυο παρόχου κινητής τηλεφωνίας. Η αποστολή των δεδομένων και ο έλεγχος του ρυθμού μετάδοσης έγινε με την βοήθεια ενός RTSP Server, που υλοποιήθηκε, βασισμένος στις βιβλιοθήκες του open source project LIVE555 (www.live555.com), στο εργαστήριο Κατανεμημένων Συστημάτων και Τηλεματικής του τμήματος. Τέλος θα πρέπει να σημειωθεί ότι η ερευνητική διατριβή που έγινε στα πλαίσια της διπλωματικής εργασίας οδήγησε στην παρακάτω δημοσίευση σε διεθνές συνέδριο. An efficient mechanism for adaptive multimedia transmission in 3G networks. IADIS International Conference Wireless Applications and Computing 2007 (WAC 2007), Lisbon, Portugal, A. Alexiou, K. Barounis, C. Bouras, 6-8 July 2007. Αbstract: Η εργασία αυτή προτείνει ένα μηχανισμό για τον έλεγχο της συμφόρησης (congestion control) και την μετάδοση πολυμεσικής πληροφορίας (video) πάνω από το UMTS. Ο μηχανισμός αυτός εφαρμόζεται όταν ο κινητός χρήστης διαχειρίζεται πληροφορία πραγματικού χρόνου (real time), και παράλληλα υιοθετεί την θεωρία μίας ευρέως αποδεκτής μεθόδου για έλεγχο ου ρυθμού (rate control) στα ενσύρματα δίκτυα, γνωστή και ως equation based rate control. Σε αυτή την προσέγγιση, ο server προσαρμόζει τον ρυθμό μετάδοσης πολυμεσικής πληροφορίας λαμβάνοντας υπόψη τις εξής δικτυακές παραμέτρους: α) ρυθμός απώλειας πακέτων, β) round-trip χρόνος και γ) μέγεθος του πακέτου. Μέσα από μια σειρά εξομοιώσεων και πειραμάτων έγινε αξιολόγηση της ορθότητας και της επίδοσης του μηχανισμού. Αρχικά ο μηχανισμός αξιολογείται χρησιμοποιώντας το περιβάλλον του ns-2 εξομοιωτή, και στη συνέχεια γίνονται κάποια πειράματα σε δίκτυο UMTS εμπορικής χρήσης γνωστής τηλεπικοινωνιακής εταιρείας. / Wireless communication has become valuable, in a country like Greece, where the morphology of the ground does not allow the massive use of alternative means of communication like fiber optics. Especially, the field of mobile telecommunications has shown a remarkable growth over the past years, as we are now witnessing the pass from the second generation (2G) networks to the third generation (3G). However, this evolution can be regarded as the result of the demands for an integrated and functional mobile telecommunication system, with a plethora of new services offered to its users. The aim of this master thesis is to make a research in the transmission of multimedia content over a UMTS network, with the capability of adapting the transmission rate, depending on the network conditions. The control of the transmission rate is a very important aspect, not only in the wired networks, but also in the wireless networks, as it is responsible for the stability of the network, the fair sharing of the bandwidth between the traffic flows and the unaffected transmission of multimedia, like video and voice. One method for the control and the adaptation of the transmission rate over networks is known as TCP Friendly Rate Control (TFRC). This method is mainly used in wired networks and according to its function, the transmission rate is the outcome of various parameters across the network. These parameters are the size of the packets, the packet loss rate, and the Round Trip Time (RTT). This method can also be used in wireless networks as long as some modifications take place and that special needs of the wireless transmission have been taken into consideration. During this research, we can show how the TFRC mechanism and the Real-Time Transport Protocol (RTP) can be combined together for the needs of multimedia streaming over a wireless network. The RTP protocol provides end-toend delivery services for data with real-time characteristics such as interactive audio and video, while applications typically run RTP on top of UDP. RTP itself does not provide any mechanism to ensure timely delivery or other quality-ofservice guarantees. However, RTP consists of the RTP Control Protocol (RTCP), which monitors the quality of service like packet loss, delay, round trip time and conveys information about the participants in an on-going session. By this way, during a streaming session, the server would be able to have an image of the network conditions thanks to the RTCP information sent by the mobile client. Then, using the TFRC mechanism an upper bound for the transmission rate can be calculated in order to take advantage of the available bandwidth and to avoid causing network instability or abuse. The server would have the same video in different versions, depending on the coding in Kbits per second (Kbps) and then would have the capability of increasing or decreasing the transmission rate by switching the video files during the streaming session. In order to examine this scenario in real network conditions, some parameters will be taken into consideration, like the available bandwidth of the wireless network, the packet loss rate, the packet size and the network traffic. It must be noticed, that the packet loss could be caused by overloading the network or by those factors which can cause problems in the wireless transmission. For testing all the above, we perform some experiments using a laptop with a network card for having access in a 3G network as a mobile user, and a RTSP server for streaming the multimedia data to the client. The server is implemented, based on the Live555 (www.live555.com) libraries, where some extra functions are added in order to work according to the streaming scenario. Finally it should be mentioned that this thesis has been published on the IADIS International Conference, Wireless Applications and Computing 2007 with the title “An Efficient Mechanism for Adaptive Multimedia Transmission in 3G Networks” held in Lisbon, Portugal, July 6-8, 2007.

Στη Διδακτορική Διατριβή μελετώνται 3 κατηγορίες επιθέσεων άρνησης εξυπηρέτησης (Denial-of-Service). Η πρώτη κατηγορία αφορά επιθέσεις τύπου SYN Flood, μια επίθεση που πραγματοποιείται σε χαμηλό επίπεδο και αποτελεί την πιο διαδεδομένη ίσως κατηγορία. Για την αναγνώριση των επιθέσεων αυτών εξήχθησαν 9 στατιστικές παράμετροι οι οποίες τροφοδότησαν τους εξής ταξινομητές: ένα νευρωνικό δίκτυο ακτινικών συναρτήσεων, ένα ταξινομητή κ-κοντινότερων γειτόνων και ένα εξελικτικό νευρωνικό δίκτυο. Ιδιαίτερη σημασία στο σύστημα αναγνώρισης έχουν οι παράμετροι που χρησιμοποιήθηκαν. Για την κατασκευή και επιλογή των παραμέτρων αυτών, προτάθηκε μια νέα τεχνική η οποία χρησιμοποιεί ένα γενετικό αλγόριθμο και μια γραμματική ελεύθερης σύνταξης για να κατασκευάζει νέα σύνολα παραμέτρων από υπάρχοντα σύνολα πρωτογενών χαρακτηριστικών. Στη δεύτερη κατηγορία επιθέσεων, μελετήθηκαν επιθέσεις άρνησης εξυπηρέτησης στην υπηρεσία του παγκόσμιου ιστού (www). Για την αντιμετώπιση των επιθέσεων αυτών προτάθηκε η χρήση υπερσυνδέσμων-παγίδων οι οποίοι τοποθετούνται στον ιστοχώρο και λειτουργούν σαν νάρκες σε ναρκοπέδιο. Οι υπερσύνδεσμοι-παγίδες δεν περιέχουν καμία σημασιολογική πληροφορία και άρα είναι αόρατοι στους πραγματικούς χρήστες ενώ είναι ορατοί στις μηχανές που πραγματοποιούν τις επιθέσεις. Στην τελευταία κατηγορία επιθέσεων, τα μηνύματα ηλεκτρονικού ταχυδρομείου spam, προτάθηκε μια μέθοδος κατασκευής ενός πολύ μικρού αριθμού παραμέτρων και χρησιμοποιήθηκαν για πρώτη φορά νευρωνικά δίκτυα για την αναγνώριση τους. / The dissertation analyzes 3 categories of denial-of-service attacks. The first category concerns SYN Flood attacks, a low level attack which is the most common. For the detection of this type of attacks 9 features were proposed which acted as inputs for the following classifiers: a radial basis function neural network, a k-nearest neighbor classifier and an evolutionary neural network. A crucial part of the proposed system is the parameters that act as inputs for the classifiers. For the selection and construction of those features a new method was proposed that automatically selects constructs new feature sets from a predefined set of primitive characteristics. This new method uses a genetic algorithm and a context-free grammar in order to find the optimal feature set. In the second category, denial-of-service attacks on the World Wide Web service were studied. For the detection of those attacks, the use of decoy-hyperlinks was proposed. Decoy hyperlinks, are hyperlinks that contain no semantic information and thus are invisible to normal users but are transparent to the programs that perform the attacks. The decoys act like mines on a minefield and are placed optimally on the web site so that the detection probability is maximized. In the last type of attack, the email spam problem, a new method was proposed for the construction of a very small number of features which are used to feed a neural network that for the first time is used to detect such attacks.

Η διατριβή πραγματεύεται το αντικείμενο της Υπολογιστικής Νοημοσύνης στην Οικονομική και Χρηματοοικονομική επιστήμη. Στο πρώτο μέρος της διατριβής αναπτύσσονται μέθοδοι ομαδοποίησης και υπολογιστικής νοημοσύνης για τη μοντελοποίηση και πρόβλεψη χρονολογικών σειρών ημερησίων συναλλαγματικών ισοτιμιών. Η προτεινόμενη μεθοδολογία κατασκευάζει τοπικούς προσέγγιστές, με τη μορφή νευρωνικών δικτύων, για ομάδες προτύπων στο χώρο εισόδων που αναγνωρίζονται από μη-επιβλεπόμενους αλγόριθμους ομαδοποίησης. Στη συνέχεια κατασκευάζονται τεχνικοί κανόνες συναλλαγών απευθείας από τα δεδομένα με τη χρήση γενετικού προγραμματισμού. Η επίδοση των νέων κανόνων συγκρίνεται με αυτή των γενικευμένων κανόνων κινητού μέσου. Το δεύτερο μέρος της διατριβής πραγματεύεται την εφαρμογή εξελικτικών αλγορίθμων για τον υπολογισμό και την εκτίμηση του πλήθους σημείων ισορροπίας σε προβλήματα από τη θεωρία παιγνίων και τη νέα οικονομική γεωγραφία. Πιο συγκεκριμένα, αξιολογείται η ικανότητα των εξελικτικών αλγορίθμων να εντοπίσουν σημεία ισορροπίας κατά Nash σε πεπερασμένα στρατηγικά παίγνια και προτείνονται τεχνικές για τον εντοπισμό περισσοτέρων του ενός σημείων ισορροπίας. Τέλος εφαρμόζονται κριτήρια από τη θεωρία υπολογισμού σταθερών σημείων και τη θεωρία τοπολογικού βαθμού για τη διερεύνηση της ύπαρξης και της υπολογιστικής πολυπλοκότητας του υπολογισμού βραχυχρόνιων σημείων ισορροπίας σε μοντέλα νέας οικονομικής γεωγραφίας. / The thesis investigates Computational Intelligence methods in Economics and Finance. The first part of the thesis is devoted to computational intelligence methods and unsupervised clustering methods for modeling and forecasting daily exchange rate time series. A methodology is proposed that relies on local approximation, using artificial neural networks, for subregions of the input space that are identified through unsupervised clustering algorithms. Furthermore, we employ genetic programming to construct novel trading rules directly from the data. The performance of the novel rules is compared to that of generalised moving average rules. In the second part of the thesis we employ evolutionary algorithms to compute and to estimate the number of equilibria in finite strategic games and new economic geography models. In particular, we investigate the capability of evolutionary and swarm intelligence algorithms to compute Nash equilibria and propose an approach for the computation of more than one equilibria. Finally we employ criteria from the theory on computation of fixed points and topological degree theory to investigate the existence and the computational complexity of computing short run equilibria in new economic geography models.

Η παρούσα διατριβή κινείται στο χώρο των Ασύρματα Δικτυωμένων Συστημάτων και έχει ως αντικείμενο τη μελέτη και τη σύνθεση μηχανισμών που βελτιώνουν τη λειτουργία τους. Ο όρος Ασύρματα Δικτυωμένα Συστήματα αναφέρεται στα συστήματα των οποίων τα δομικά στοιχεία συνδέονται μέσω ασύρματων δικτύων, με την έμφαση να δίνεται στα αυτό-οργανωμένα δίκτυα και στα δίκτυα αισθητήρων. Η βελτιστοποίηση και ο έλεγχος ενός Ασύρματα Δικτυωμένου Συστήματος γίνεται με γνώμονα την Ποιότητα των παρεχόμενων Υπηρεσιών του δικτύου, η οποία χρησιμοποιείται ως μέτρο αξιολόγησης και επαναπροσδιορισμού των παραμέτρων λειτουργίας αυτού. Προσεγγίζοντας το θέμα από την οπτική γωνία του δικτύου, οι μηχανισμοί που είναι υπεύθυνοι για τη βελτιστοποίηση της λειτουργίας των Ασύρματα Δικτυωμένων Συστημάτων, αποστασιοποιούνται από την ανάπτυξη νέων πρωτοκόλλων για τα διάφορα επίπεδα του μοντέλου αναφοράς Ανοιχτής Διασύνδεσης Συστημάτων. Για τον λόγο αυτό, αναφορικά με το μοντέλο αναφοράς Ανοιχτής Διασύνδεσης Συστημάτων, το ζήτημα της βελτιστοποίησης της λειτουργίας των Ασύρματα Δικτυωμένων Συστημάτων προσεγγίζεται από τα ακραία επίπεδα της στοίβας πρωτοκόλλων, και συγκεκριμένα από την οπτική γωνία του Επιπέδου Εφαρμογής και του Φυσικού Επιπέδου. Στο Επίπεδο Εφαρμογής το ενδιαφέρον επικεντρώνεται στην διασφάλιση των περιθωρίων ευστάθειας για τα Ασύρματα Δικτυωμένα Συστήματα Ελέγχου. Η διασφάλιση της ομαλής λειτουργίας του συστήματος κλειστού βρόχου βασίζεται σε διακοπτικές δομές ελέγχου, των οποίων οι παράμετροι λειτουργίας καθορίζονται από την Ποιότητα Υπηρεσίας του δικτύου, και συγκεκριμένα από το ποσοστό των επιτυχώς ληφθέντων πακέτων. Στο Φυσικό Επίπεδο εξετάζεται αρχικά το πρόβλημα αποκατάστασης της συνδεσιμότητας μεταξύ των μελών ενός Ασύρματα Δικτυωμένου Συστήματος και στην συνέχεια το πρόβλημα επαναπροσδιορισμού της ποιότητας των ασύρματων ζεύξεων. Οι κεντρικοποιημένοι και κατανεμημένοι μηχανισμοί που αναπτύσσονται για τη βελτιστοποίηση των παραμέτρων της Ποιότητας Υπηρεσίας των Ασύρματα Δικτυωμένων Συστημάτων στο Φυσικό Επίπεδο βασίζονται σε εργαλεία της Υπολογιστικής Γεωμετρίας, συνδυάζοντας τα χωρικά χαρακτηριστικά ενός Ασύρματα Δικτυωμένου Συστήματος με δημοφιλή μοντέλα διάδοσης μεγάλης κλίμακας. Τέλος, η αξιολόγηση των μεθόδων ελέγχου και βελτιστοποίησης της λειτουργίας των Ασύρματα Δικτυωμένων Συστημάτων πραγματοποιείται με την εφαρμογή τους σε κατάλληλες πειραματικές διατάξεις και σε ένα καθορισμένο σύνολο σεναρίων εξομοίωσης. / The primary objective of the present PhD thesis is the analysis and the synthesis of mechanisms and algorithms that optimize the operation of Wireless Networked Systems. The term Wireless Networked Systems is used to describe the distributed systems, whose components are interconnected over wireless networks. Referring to wireless networking, the emphasis is given at the self-organized Ad-hoc and Sensor Networks. The effort made is focused on the reconfiguration of the Quality of Service of the underlying network. From such a perspective, the mechanisms responsible for improving the Quality of Service differentiate from the design of novel, specialized communication protocols. More specifically, with respect to the Open Systems Interconnection Reference Model (OSI-RM), the optimization issues of the Wireless Networked Systems’ operation are examined at the Application and Physical Layer. At the Application Layer, problems related to the guarantee of the stability margins for Wireless Networked Controlled Systems are studied. More precisely, the assurance of the desired performance for the closed-loop controlled system is based on switching control techniques. The optimization decision variables are determined by the network’s Quality of Service parameters. At the Physical Layer the objective is twofold: (a) to establish the physical connectivity among the members of the Wireless Networked System and (b) to optimize of the wireless link’s quality. Based on the combination of the spatial characteristics of the Wireless Networked Systems with large-scale radio propagation models, the centralized and distributed mechanisms, synthesized for the optimization of the network’s Quality of Service at the Physical Layer, exploit effectively concepts adopted by the Computational Geometry. Finally, properly developed experimental testbeds and network simulation scenaria are utilized to examine the efficiency of the synthesized mechanisms for the control and optimization of the operation of Wireless Networked Systems at the Application and Physical Layer.

Οι πρόσφατες εξελίξεις στις ασύρματες επικοινωνίες και στα ηλεκτρονικά κυκλώματα έχουν επιτρέψει την ανάπτυξη υπολογιστικών διατάξεων χαμηλού κόστους και χαμηλής κατανάλωσης ισχύος, οι οποίες ενσωματώνουν δυνατότητες μέτρησης (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.

Στην παρούσα διπλωματική εργασία θα γίνει μελέτη και εφαρμογή μεθόδων επίλυσης του προβλήματος αναγνώρισης γεωμετρικών χαρακτηριστικών ανθρώπινων ερυθρών αιμοσφαιρίων από προσομοιωμένες εικόνες σκέδασης ΗΜ ακτινοβολίας ενός He-Ne laser 632.8 μm. Στο πρώτο κεφάλαιο γίνεται μια εισαγωγή στις ιδιότητες και τα χαρακτηριστικά του ερυθροκυττάρου καθώς, επίσης, παρουσιάζονται διάφορες ανωμαλίες των ερυθροκυττάρων και οι μέχρι στιγμής χρησιμοποιούμενοι τρόποι ανίχνευσής των. Στο δεύτερο κεφάλαιο της εργασίας γίνεται μια εισαγωγή στις ιδιότητες της ΗΜ ακτινοβολίας, περιγράφεται το φαινόμενο της σκέδασης και παρουσιάζεται το ευθύ πρόβλημα σκέδασης ΗΜ ακτινοβολίας ανθρώπινων ερυθροκυττάρων. Το τρίτο κεφάλαιο αποτελείται από δύο μέρη. Στο πρώτο μέρος γίνεται εκτενής ανάλυση της θεωρίας των τεχνητών νευρωνικών δικτύων και περιγράφονται τα νευρωνικά δίκτυα ακτινικών συναρτήσεων RBF. Στη συνέχεια, αναφέρονται οι μέθοδοι εξαγωγής παραμέτρων και, πιο συγκεκριμένα, δίνεται το θεωρητικό και μαθηματικό υπόβαθρο των μεθόδων που χρησιμοποιήθηκαν οι οποίες είναι ο αλογόριθμος Singular Value Decomposition (SVD), o Angular Radial μετασχηματισμός (ART) και φίλτρα Gabor. Στο δεύτερο μέρος περιγράφεται η επίλυση του αντίστροφου προβλήματος σκέδασης. Παρουσιάζεται η μεθοδολογία της διαδικασίας επίλυσης όπου εφαρμόστηκαν ο αλογόριθμος συμπίεσης εικόνας SVD, o περιγραφέας σχήματος ART και ο περιγραφέας υφής με φίλτρα Gabor για την εύρεση των γεωμετρικών χαρακτηριστικών και νευρωνικό δίκτυο ακτινικών συναρτήσεων RBF για την ταξινόμηση των ερυθροκυττάρων. Στο τέταρτο και τελευταίο κεφάλαιο γίνεται δοκιμή και αξιολόγηση της μεθόδου και συνοψίζονται τα αποτελέσματα και τα συμπεράσματα που εξήχθησαν κατά τη διάρκεια της εκπόνησης αυτής της διπλωματικής. / In this thesis we study and implement methods of estimating the geometrical features of the human red blood cell from a set of simulated light scattering images produced by a He-Ne laser beam at 632.8 μm. Ιn first chapter an introduction to the properties and the characteristics of red blood cells are presented. Furthermore, we describe various abnormalities of erythrocytes and the until now used ways of detection. In second chapter the properties of electromagnetic radiation and the light scattering problem of EM radiation from human erythrocytes are presented. The third chapter consists of two parts. In first part we analyse the theory of neural networks and we describe the radial basis function neural network. Then, we describe the theoritical and mathematical background of the methods that we use for feature extraction which are Singular Value Decomposition (SVD), Angular Radial Transform and Gabor filters. In second part the solution of the inverse problem of light scattering is described. We present the methodology of the solution process in which we implement a Singular Value Decomposition approach, a shape descriptor with Angular Radial Transform and a homogenous texture descriptor which uses Gabor filters for the estimation of the geometrical characteristics and a RBF neural network for the classification of the erythrocytes. In the forth and last chapter the described methods are evaluated and we summarise the experimental results and conclusions that were extracted from this thesis.

Τα Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) αποτελούν μία αρκετά πρόσφατη και πολλά υποσχόμενη νέα τεχνολογία που βρίσκει πληθώρα εφαρμογών. Λόγω της ευρύτατης εφαρμοσιμότητάς της και της προφανούς θέσης που βρίσκει στο σύγχρονο κατανεμημένο υπολογιστικό κόσμο, η επιστημονική τυπική θεμελίωση των νόμων που διέπουν αυτή τη νέα τεχνολογία καθίσταται απαραίτητη. Έτσι, έχουν προταθεί πολλά νέα υπολογιστικά μοντέλα για ΑΔΑ. Μία ειδική κατηγορία τέτοιων συστημάτων είναι τα Πρωτόκολλα Πληθυσμών (ΠΠ). Αυτά διέπονται από τρία ιδιαίτερα χαρακτηριστικά: Οι κόμβοι αίσθησης (πράκτορες) κινούνται παθητικά, δηλαδή δε μπορούν να ελέγξουν την κίνηση στην οποία υπόκεινται, η διαθέσιμη μνήμη κάθε κόμβου είναι πολύ περιορισμένη και οι πράκτορες αλληλεπιδρούν κατά ζεύγη. Έχει αποδειχθεί ότι ένα κατηγόρημα είναι υπολογίσιμο από το μοντέλο των ΠΠ εάν και μόνο εάν είναι ημιγραμμικό. Η κλάση των ημιγραμμικών κατηγορημάτων αποτελεί μία αρκετά μικρή κλάση. Στην παρούσα εργασία, βασικός μας στόχος είναι η επέκταση του μοντέλου των πρωτοκόλλων πληθυσμών με σκοπό το κέρδος σε υπολογιστική ισχύ. Πρώτα κάνουμε την παραδοχή ότι, πέρα των κόμβων αίσθησης, και οι ακμές του γραφήματος μπορούν να διατηρούν περιορισμένες καταστάσεις. Έτσι, σε ένα πλήρες γράφημα n κόμβων είναι σα να έχουμε προσθέσει Ο(n^2) επιπλέον θέσεις μνήμης οι οποίες διαβάζονται και γράφονται μόνο από τα άκρα της αντίστοιχης ακμής. Αποδεικνύουμε ότι το νέο μοντέλο, το οποίο καλούμε μοντέλο Πρωτοκόλλων Πληθυσμών με Διαμεσολαβητή, μπορεί να λειτουργήσει ως μία κατανεμημένη ανταιτιοκρατική μηχανή Turing (ΜΤ) που χρησιμοποιεί όλη τη διαθέσιμη μνήμη. Η μόνη διαφορά από μία συνήθη ΜΤ είναι ότι η συγκεκριμένη μηχανή υπολογίζει μόνο συμμετρικές γλώσσες. Πιο τυπικά, δείχνουμε ότι ένα κατηγόρημα είναι υπολογίσιμο από το νέο μοντέλο εάν και μόνο εάν είναι συμμετρικό και ανήκει στην NSPACE(n^2). Επιπλέον, μελετάμε και τη δυνατότητα του νέου μοντέλου να διαγιγνώσκει γλώσσες γραφημάτων (για γενικά γραφήματα). Εν συνεχεία, αγνοούμε τις καταστάσεις των ακμών και δίνουμε μία νέα βελτίωση και πάλι απευθείας απ' το μοντέλο των ΠΠ. Η υπόθεση που κάνουμε τώρα είναι ότι οι πράκτορες είναι πολυταινιακές ΜΤ με άπειρη μνήμη, που μπορούν τόσο να εκτελούν εσωτερικό υπολογισμό όσο και να αλληλεπιδρούν με άλλους πράκτορες και ορίζουμε χωρικά φραγμένους υπολογισμούς. Καλούμε το νέο αυτό μοντέλο, μοντέλο Παθητικά κινούμενων Μηχανών. Αποδεικνύουμε ότι αν χρησιμοποιείται σε κάθε πράκτορα μνήμη το πολύ f(n) για f(n)=Ω(log n) τότε ένα κατηγόρημα είναι υπολογίσιμο από το νέο μοντέλο εάν και μόνο εάν είναι συμμετρικό και ανήκει στην NSPACE(nf(n)). Δείχνουμε επίσης ότι αυτό δεν ισχύει για f(n)=o(log n). Βασιζόμενοι σε αυτά, δείχνουμε ότι για f(n)=Ω(log n) υπάρχει μία χωρική ιεραρχία ακριβώς όπως και για τις συνήθεις (συμμετρικές) ΜΤ. Δείχνουμε επίσης ότι αυτό δεν ισχύει για f(n)=o(loglog n), καθώς στην τελευταία περίπτωση η αντίστοιχη κλάση καταρρέει μέσα στην κλάση των ημιγραμμικών κατηγορημάτων, και τέλος ότι για f(n)=Ω(loglog n) η κλάση γίνεται αυστηρά μεγαλύτερη των ημιγραμμικών κατηγορημάτων. Αφήνουμε ανοικτό το πρόβλημα του τι ακριβώς συμβαίνει για χωρικά φράγματα f(n) τέτοια ώστε f(n)=Ω(loglog n) και f(n)=o(log n). / Wireless Sensor Networks (WSNs) constitute a recent and promising new technology that is widely applicable. Due to the applicability of this technology and its obvious importance for the modern distributed computational world, the formal scientific foundation of its inherent laws becomes essential. As a result, many new computational models for WSNs have been proposed. Population Protocols (PPs) are a special category of such systems. These are mainly identified by three distinctive characteristics: the sensor nodes (agents) move passively, that is, they cannot control the underlying mobility pattern, the available memory to each agent is restricted, and the agents interact in pairs. It has been proven that a predicate is computable by the PP model iff it is semilinear. The class of semilinear predicates is a fairly small class. In this work, our basic goal is to enhance the PP model in order to improve the computational power. We first make the assumption that not only the nodes but also the edges of the communication graph can store restricted states. In a complete graph of n nodes it is like having added O(n^2) additional memory cells which are only read and written by the endpoints of the corresponding edge. We prove that the new model, called Mediated Population Protocol model, can operate as a distributed nondeterministic Turing machine (TM) that uses all the available memory. The only difference from a usual TM is that this one computes only symmetric languages. More formally, we establish that a predicate is computable by the new model iff it is symmetric and belongs to NSPACE(n^2). Moreover, we study the ability of the new model to decide graph languages (for general graphs). The next step is to ignore the states of the edges and provide another enhancement straight away from the PP model. The assumption now is that the agents are multitape TMs equipped with infinite memory, that can perform internal computation and interact with other agents, and we define space-bounded computations. We call this the Passively mobile Machines model. We prove that if each agent uses at most f(n) memory for f(n)=Ω(log n) then a predicate is computable iff it is symmetric and belongs to NSPACE(nf(n)). We also show that this is not the case for f(n)=o(log n). Based on these, we show that for f(n)=Ω(log n) there exists a space hierarchy like the one for classical symmetric TMs. We also show that the latter is not the case for f(n)=o(loglog n), since here the corresponding class collapses in the class of semilinear predicates and finally that for f(n)=Ω(loglog n) the class becomes a proper superset of semilinear predicates. We leave open the problem of characterizing the classes for f(n)=Ω(loglog n) and f(n)=o(log n).

Σε αυτή την Διπλωματική εργασία μελετήσαμε με ποιο τρόπο μπορούν να εφαρμοστούν οι διάφορες τεχνικές Εξόρυξης Γνώσης (Data Mining) στην εκπαίδευση. Αυτός ο επιστημονικός τομέας o οποίος ερευνά και αναπτύσσει τεχνικές προκειμένου να ανακαλύψει γνώση από δεδομένα τα οποία προέρχονται από την εκπαίδευση ονομάζεται Εξόρυξη Γνώσης από Εκπαιδευτικά Δεδομένα (Educational Data Mining –EDM. Στην εργασία αυτή εκτός από την θεωρητική μελέτη των αλγορίθμων και των τεχνικών που διέπουν την εξόρυξη γνώσης από δεδομένα γενικά, έγινε και μια λεπτομερέστερη μελέτη και παρουσίαση της κατηγορίας των αλγορίθμων κατηγοριοποίησης (Classification), διότι αυτοί οι αλγόριθμοι χρησιμοποιήθηκαν στην φάση της υλοποίησης/αξιολόγησης. Στην συνέχεια η εργασία επικεντρώθηκε στον τρόπο με τον οποίο μπορούν να εφαρμοστούν αυτοί οι αλγόριθμοι σε εκπαιδευτικά δεδομένα, τι εφαρμογές έχουμε στην εκπαίδευση, ενώ αναφερόμαστε και σε μια πληθώρα ερευνών που έχουν πραγματοποιηθεί πάνω στο συγκεκριμένο αντικείμενο. Στην συνέχεια διερευνήσαμε την εφαρμογή τεχνικών κατηγοριοποίησης στην πρόγνωση της επίδοσης μαθητών Δευτεροβάθμιας Εκπαίδευσης στα μαθήματα της Γεωγραφίας Α’ και Β’ Γυμνασίου. Συγκεκριμένα υλοποιήσαμε και θα αξιολογήσαμε έξι αλγορίθμους οι οποίοι ανήκουν στην ομάδα των αλγορίθμων κατηγοριοποίησης(Classification) και είναι αντιπροσωπευτικοί των σημαντικότερων τεχνικών κατηγοριοποίησης. Από την οικογένεια των ταξινομητών με χρήση δένδρων απόφασης (Decision Tree Classifiers) υλοποιήσαμε τον J48, από τους αλγορίθμους κανόνων ταξινόμησης (Rule-based Classification ) τον Ripper, από τους αλγόριθμους στατιστικής κατηγοριοποίησης τον Naïve Bayes, από την μέθοδο των Κ πλησιέστερων γειτόνων (KNN) τον 3-ΝΝ, από την κατηγορία των τεχνητών νευρωνικών δικτύων τον Back Propagation και τέλος από τις μηχανές διανυσμάτων υποστήριξης (Support Vector Machines SVM) τον SMO (Sequental Minimal Optimazation). Όλες οι παραπάνω υλοποιήσεις και αξιολογήσεις έγιναν με το ελεύθερο λογισμικού Weka το οποίο είναι υλοποιημένο σε Java και το οποίο προσφέρει μια πληθώρα αλγορίθμων μηχανικής μάθησης για να κάνουμε εξόρυξη γνώσης. / In this work we will study the way the misc data mining techniques can be applied to the misc fields of the education. This new scientific field is commonly named Educational Data Mining. In this study we will study the theoretical analysis of the data mining techniques focussing to the classification techniques as those are the most commonly used for prediction purpose. We also intend to predict student performance in secondary education using data mining techniques. The data we collect are concerned the class of Geography and we apply to them six data mining models with the help of the open source machine learning software Weka. We use supervised machine learning algorithms from the Classification field (Decision Tree Classifiers, Rule-based Classification, Neural Networks, k-Nearest Neighbour Algorithm, Bayesian and Support Vector Machines). After we have evaluate the algorithms we build a java tool, that uses the 3-KNN algorithm, to help us predict the performance of a student at the end of the year.

Η Β-χρόνια Λεμφογενής Λευχαιμία (Β-ΧΛΛ) αποτελεί τον πιο κοινό τύπο λευχαιμίας στο Δυτικό κόσμο. Η πρόγνωσή της θεωρείται ως ένα από τα πιο ενδιαφέροντα προβλήματα απόφασης στην κλινική έρευνα και πρακτική. Για διάφορους κλινικούς και εργαστηριακούς δείκτες είναι γνωστό ότι σχετίζονται με την εξέλιξη της νόσου. Για τις παραμέτρους, όμως, που εξάγονται με ανάλυση κυτταρομετρίας ροής, οι οποίες αποτελούν τον ακρογωνιαίο λίθο της διαδικασίας διάγνωσης της νόσου, το αν προσφέρουν επιπρόσθετη προγνωστική πληροφορία αποτελεί ανοιχτό πρόβλημα. Στη διατριβή αυτή προτείνουμε ένα σύστημα υποβοήθησης για τις αποφάσεις των ειδικών του πεδίου, το οποίο πραγματοποιεί πολυπαραμετρική πρόγνωση ασθενών με Β-ΧΛΛ, συνδυάζοντας τη χρήση ποικίλων ετερογενών προγνωστικών δεικτών (κλινικών, εργαστηριακών και κυτταρομετρίας ροής) που σχετίζονται με τη νόσο. Η διάγνωση της Β-ΧΛΛ βασίζεται κυρίως στη μελέτη του αντιγονικού φαινότυπου των κυττάρων των ασθενών, η οποία διενεργείται με κυτταρομετρία ροής. Αν και η διαδικασία που ακολουθείται κατά την ανάλυση αυτή είναι σαφώς ορισμένη, ο τρόπος με τον οποίο οι εργαστηριακοί υπεύθυνοι την πραγματοποιούν παραδοσιακά χαρακτηρίζεται από ανακρίβεια και υποκειμενικότητα. Καθώς η τεχνολογία της κυτταρομετρίας ροής εξελίσσεται ραγδαία, γίνεται όλο και πιο επιτακτική η ανάγκη για την ανάπτυξη αυτοματοποιημένων μεθόδων ανάλυσης των δεδομένων που παράγει. Σε αυτά τα πλαίσια, παρουσιάζουμε ένα χρήσιμο παράδειγμα αυτοματοποιημένης ανάλυσης κυτταρομετρικών δεδομένων, η οποία δεν απαιτεί την άμεση επίβλεψη των ειδικών, για τη διάγνωση ασθενών με Β-ΧΛΛ. Οι τιμές των χαρακτηριστικών παραμέτρων που εξάγονται με εφαρμογή της προτεινόμενης μεθοδολογίας, ενσωματώνονται κατόπιν στο προαναφερθέν προγνωστικό σύστημα. Ανάγοντας το πρόβλημα της πρόγνωσης της Β-ΧΛΛ σε ένα στιγμιότυπο ταξινόμησης προτύπων, καθώς και προσομοιώνοντας κάθε ένα από τα βήματα της διαδικασίας της διάγνωσης της νόσου με ένα στιγμιότυπο συσταδοποίησης δεδομένων, αντιμετωπίσαμε τα δύο προβλήματα εφαρμόζοντας τεχνικές στατιστικής μάθησης. Εστιάσαμε σε μεθοδολογίες δικτύων πεποίθησης, χρησιμοποιώντας συγκεκριμένα το naïve-Bayes μοντέλο και για τις δύο περιπτώσεις, στην επιβλεπόμενη και στη μη επιβλεπόμενη εκδοχή του, αντίστοιχα. Τα χαρακτηριστικά και η φύση των δεδομένων (κυρίως των κυτταρομετρικών) που παράγονται από έναν παθολογικό υποκείμενο μηχανισμό, όπως αυτός της νόσου, δεν ευνοούν την απευθείας εφαρμογή του παραπάνω μοντέλου στο εκάστοτε στιγμιότυπο. Για το λόγο αυτό, συνδυάσαμε την εφαρμογή του naïve-Bayes μοντέλου με κατάλληλες ευρετικές αλγοριθμικές διαδικασίες, για την επίτευξη καλύτερων αποτελεσμάτων, με κριτήριο βέλτιστου όχι μόνο κάποιες συχνά χρησιμοποιούμενες μετρικές αποτίμησης αλγόριθμων, αλλά και τη γνώμη των αιματολόγων. Χάρη στην ιδιότητά τους να ενσωματώνουν την έμπειρη γνώση των ειδικών ως εκ των προτέρων πληροφορία αρχικοποίησης των μεθόδων μάθησής τους, οι Bayesian μεθοδολογίες κρίνονται ως οι πλέον κατάλληλες για την εφαρμογή τους σε τέτοιου τύπου προβλήματα. / B-Chronic Lymphocytic Leukemia (B-CLL) is known to be the most common type of leukemia in the Western world. Its prognosis remains one of the most interesting decision problems in clinical research and practice. Various clinical and laboratory factors are known to be associated with the evolution of the disease. However, for the parameters obtained by flow cytometry analysis, that are traditionally utilized as the cornerstone during the diagnosis procedure of the disease, whether they offer additional prognostic information is an open issue. In this dissertation, we propose a decision support system to the hematologists, that provides multiparametric B-CLL patients’ prognosis, combining the usage of diverse heterogeneous factors (clinical, laboratory and flow cytometry) associated with the disease. B-CLL diagnosis is primarily derived from the study of the antigenic phenotype of the patients’ blood cells, which is held with flow cytometry analysis. Despite the fact that the method of the analysis is well defined, the process traditionally followed by the laboratory experts is characterized by amounts of inexactness and subjectivity. As flow cytometry technology advances rapidly, the need for adequate automated (computer-assisted) analysis methodologies on the data it produces is accordingly increasing. In this context, we present a useful paradigm of automated analysis of flow cytometry data, that does not require the direct supervision of the expert, for B-CLL patients’ diagnosis. The values of the flow cytometry characteristic parameters extracted by applying the proposed methodology are afterward incorporated to the prognostic system for B-CLL mentioned above. By reducing the B-CLL prognosis problem to an instance of the pattern classification problem, as well as by simulating each step of the B-CLL diagnosis procedure with an instance of the data classification problem, we proceeded with applying statistical learning techniques. We focused on Bayesian network methodologies and utilized the naïve-Bayes model for both cases, in its supervised and unsupervised version, respectively. The characteristics of the data (especially of the flow cytometry ones) generated by a pathological underlying mechanism, like the disease’s one, did not encourage the direct use of the above model. Therefore, we combined the naïve-Bayes model with a set of suitable heuristic algorithmic procedures to obtain better results, not only with respect to some commonly used algorithmic optimality metrics, but also by considering the experts’ opinion. Due to their ability of incorporating the expert knowledge as a priori initial information to their learning methods, Bayesian methodologies are considered as the most appropriate ones to make use of in such types of applications.