Η επιστημονική κοινότητα τα τελευταία χρόνια και κυρίως μετά το 1970 έχει δείξει τεράστιο ενδιαφέρον για τον τομέα της επεξεργασίας εικόνας και video σε συνδυασμό με τον έλεγχο κλειστού βρόγχου και όλα αυτά σε πραγματικό χρόνο. Γι’ αυτό και η οπτική παρακολούθηση (vision tracking) είναι και μία από τις πιο σημαντικές εφαρμογές στον τομέα του computer vision. Το συγκεκριμένο αντικείμενο [1] αποτελεί πρόκληση για πολλούς, εξαιτίας της μεγάλης δυσκολίας που έγκειται στο γεγονός της παράλληλης αναγνώρισης των κινούμενων στόχων με την ταυτόχρονη κίνηση της camera. Περίτρανη απόδειξη όλων των παραπάνω είναι η μεγάλη ποικιλία των σχετικών άρθρων που έχουν δημοσιευτεί σε διάφορα σχετικά με τον αντικείμενο περιοδικά, βιβλία καθώς και έχουν παρουσιαστεί σε διάφορα συνέδρια. To μεγαλύτερο πλεονέκτημα αυτών των αυτόματων συστημάτων παρακολούθησης (automatic surveillance systems) είναι η πολύ καλή αξιοπιστία και η αποδοτικότητα για παρακολούθηση από απόσταση (long distance surveillance) σε σύγκριση με αυτή που θα παρουσίαζαν εάν στη θέση τους υπήρχε ο ανθρώπινος παράγοντας. Τα συστήματα(3) που χρησιμοποιούνται για παρακολούθηση μπορούν αν περιλαμβάνουν radar, sonars ή ακόμη και lasers. Κύριο μειονέκτημα αυτών των συστημάτων είναι οι συσκευές σάρωσης που περιλαμβάνουν. Αυτές είναι ενδεχομένως αναξιόπιστες και καταναλώνουν μεγάλες ποσότητες ενέργειας, γεγονός μη επιθυμητό κυρίως σε διαστημικές εφαρμογές. Μία ενδιαφέρουσα εναλλακτική λύση αντί της χρήσης των παραπάνω συσκευών είναι να υιοθετηθούν vision συστήματα, τα οποία παρέχουν ακριβής χρονική και χωρική ανάλυση (spatiotemporal resolution). Στόχος της παρούσας διπλωματικής εργασίας είναι η εξομοίωση ενός ελεγκτή ο οποίος έχοντας στην διάθεση του κάθε χρονική στιγμή την θέση του στόχου προς παρακολούθηση στην εικόνα θα θα οδηγεί την κάμερα ετσι ώστε να κρατάει τον στόχο σε μια περιοχή γύρω από το κέντρο της. Μελλοντική εφαρμογή αυτης της διπλωματικής θα μπορούσε να είναι η ενσωμάτωση του συστήματος παρακολούθησης σε ένα σύστημα μονοκατευθυντικών κεραιων έτσι ώστε να επιτυγχάνεται η βέλτιστη επικοινωνία με τα αεροσκάφη. / -

Αντικείμενο της εργασίας αποτελεί η ανάπτυξη συστήματος βασισμένου σε DSP για τη λήψη και επεξεργασία εικόνας υψηλής ανάλυσης με δυνατότητα ρύθμισης της γωνίας λήψης μέσα στο χώρο μέσω πρωτότυπου μηχανισμού που κινείται με τη βοήθεια δύο βηματικών κινητήρων και ελέγχου της διάταξης από απόσταση μέσω σύνδεσης δικτύου με το πρωτόκολλο TCP. Η δικτυακή επικοινωνία, επεξεργασία, μεταφορά και αποθήκευση των δεδομένων εικόνας στηρίζονται στην κάρτα DSK TMS320C6416, που βασίζεται στον DSP 6416 της Texas Instruments, ενώ ο έλεγχος της κάμερας και η οδήγηση των βηματικών κινητήρων επιτυγχάνονται με τη χρήση της θυγατρικής κάρτας DSK-EYE Gigabit, πυρήνα της οποίας αποτελεί ένα FPGA της οικογένειας Cyclone II της ALTERA και περιλαμβάνει τον OV5610 αισθητήρα εικόνας 5.2 Megapixel. Ένα γραφικό περιβάλλον επιτρέπει στο χρήστη της εφαρμογής τον έλεγχο της διάταξης και τη ρύθμιση των παραμέτρων για τη λήψη και επεξεργασία εικόνας ανάμεσα στις οποίες είναι η ρύθμιση φωτεινότητας, κέρδους, ανάλυσης της εικόνας, κατεύθυνσης και γωνίας κίνησηςγια κάθε κινητήρα ξεχωριστά και επιλογή του αλγορίθμου επεξεργασίας της αρχικής εικόνας. / A remote controlled DSP-based system for high resolution image capturing and processing, featuring 2-axis rotational motion was developed using the TMS320C6416 DSK board, which is based on TMS320C6416T DSP. A prototype device holding a pair of bipolar stepper motors and a gear set providing proper gear ratio and holding torque, is used for motion transmission to the 5.2 Megapixel Omnivision OV5610 camera module, connected to the Bitec DSK-EYE Gigabit daughtercard, which is built around a FPGA of the ALTERA Cyclone II family. The remote operation of the whole system is carried out over a network connection via the dedicated Ethernet adapter of the DSK-EYE board, using the TCP/IP protocol. The device is controlled by means of a Graphical User Interface (GUI) which grants access to some key parameters of the image sensoring process, allowing for easy adjustment of gain and exposure values, stepper motor control and image processing algorithm selection

Η παρούσα διπλωματική εργασία αφορά την ανίχνευση και παρακολούθηση ανθρώπινων μορφών σε ακολουθίες βίντεο με μεθόδους μηχανικής όρασης. Οι ακολουθίες αυτές θεωρούμε πως έχουν ληφθεί από στατική κάμερα σε εσωτερικό ή εξωτερικό χώρο. Πιο συγκεκριμένα, το εν λόγω πρόβλημα υποδιαιρείται σε τρία κυρίως μέρη τα οποία μελετώνται, αναλύονται και υλοποιούνται σε ξεχωριστά κεφάλαια. Ξεκινάμε με το κομμάτι κατάτμησης κίνησης, συνεχίζουμε με την ταξινόμηση αντικειμένων ώστε να αναγνωριστούν οι άνθρωποι ανάμεσα στις κινούμενες οντότητες και τελειώνουμε με την παρακολούθηση των ανθρώπινων σιλουετών για καταγραφή της πορείας τους όση ώρα βρίσκονται στο πλάνο. Οι αλγόριθμοι που αναπτύχθηκαν λειτούργησαν ικανοποιητικά κάτω από διάφορες συνθήκες και τα αποτελέσματά τους μπορούν να περάσουν ως είσοδοι σε μια πληθώρα εφαρμογών υψηλότερου επιπέδου με σκοπό την αναγνώριση ανθρώπινης δραστηριότητας και την κατανόηση συμπεριφοράς. / The purpose of this thesis is to deal with the problem of human tracking in video sequences. We have divided the problem in three parts: motion segmentation, human tracking and object classification. Finally we have dedicate a whole chapter to optical flow techniques and the relevant methods that can be employed to solve the same problem.

Τα δεδομένα εικόνων που προκύπτουν από την χρήση βιο-ιατρικών μηχανημάτων είναι από την φύση τους ασαφή, χάρη σε μια σειρά από παράγοντες ανάμεσα στους οποίους οι περιορισμοί στον χώρο, τον χρόνο, οι παραμετρικές αναλύσεις καθώς και οι φυσικοί περιορισμοί που επιβάλλει το εκάστοτε μηχάνημα. Όταν το αντικείμενο ενδιαφέροντος σε μια τέτοια εικόνα έχει κάποιο μοτίβο φωτεινότητας ευκρινώς διαφορετικό από τα μοτίβα των υπόλοιπων αντικειμένων που εμφανίζονται, είναι εφικτή η κατάτμηση της εικόνας με έναν απόλυτο, δυαδικό τρόπο που να εκφράζει επαρκώς τα όρια των αντικειμένων. Συχνά ωστόσο σε τέτοιες εικόνες υπεισέρχονται παράγοντες όπως η ανομοιογένεια των υλικών που απεικονίζονται, θόλωμα, θόρυβος ή και μεταβολές στο υπόβαθρο που εισάγονται από την συσκευή απεικόνισης με αποτέλεσμα οι εντάσεις φωτεινότητας σε μια τέτοια εικόνα να εμφανίζονται με έναν ασαφή, βαθμωτό, «μη-δυαδικό» τρόπο. Μια πρωτοπόρα τάση στην σχετική βιβλιογραφία είναι η αξιοποίηση της ασαφούς σύνθεσης των αντικειμένων μιας τέτοιας εικόνας, με τρόπο ώστε η ασάφεια να αποτελεί γνώρισμα του εκάστοτε αντικειμένου αντί για ανεπιθύμητο χαρακτηριστικό: αντλώντας από την θεωρία ασαφών συνόλων, τέτοιες προσεγγίσεις κατατμούν μια εικόνα με βαθμωτό, μη-δυαδικό τρόπο αποφεύγοντας τον μονοσήμαντο καθορισμό ορίων μεταξύ των αντικειμένων. Μια τέτοια προσέγγιση καταφέρνει να αποτυπώσει με μαθηματικούς όρους την ασάφεια της θολής εικόνας, μετατρέποντάς την σε χρήσιμο εργαλείο ανάλυσης στα χέρια ενός ειδικού. Από την άλλη, το μέγεθος της ασάφειας που παρατηρείται σε τέτοιες εικόνες είναι τέτοιο ώστε πολλές φορές να ωθεί τους ειδικούς σε διαφορετικές ή και αντικρουόμενες κατατμήσεις, ακόμη και από το ίδιο ανθρώπινο χέρι. Επιπλέον, το παραπάνω έχει ως αποτέλεσμα την οικοδόμηση βάσεων δεδομένων στις οποίες για μια εικόνα αποθηκεύονται πολλαπλές κατατμήσεις, δυαδικές και μη. Μπορούμε με βάση μια κατάτμηση εικόνας να ανακτήσουμε άλλες, παρόμοιες τέτοιες εικόνες των οποίων τα δεδομένα έχουν προέλθει από αναλύσεις ειδικών, χωρίς σε κάποιο βήμα να υποβαθμίζουμε την ασαφή φύση των αντικειμένων που απεικονίζονται; Πως επιχειρείται η ανάκτηση σε μια βάση δεδομένων στην οποία έχουν αποθηκευτεί οι παραπάνω πολλαπλές κατατμήσεις για κάθε εικόνα; Αποτελεί κριτήριο ομοιότητας μεταξύ εικόνων το πόσο συχνά θα επέλεγε ένας ειδικός να οριοθετήσει ένα εικονοστοιχείο μιας τέτοιας εικόνας εντός ή εκτός ενός τέτοιου θολού αντικειμένου; Στα πλαίσια της παρούσας εργασίας προσπαθούμε να απαντήσουμε στα παραπάνω ερωτήματα, μελετώντας διεξοδικά την διαδικασία ανάκτησης τέτοιων εικόνων. Προσεγγίζουμε το πρόβλημα θεωρώντας ότι για κάθε εικόνα αποθηκεύονται στην βάση μας περισσότερες της μίας κατατμήσεις, τόσο δυαδικής φύσης από ειδικούς όσο και από ασαφείς από αυτόματους αλγορίθμους. Επιδιώκουμε εκμεταλλευόμενοι το χαρακτηριστικό της ασάφειας να ενοποιήσουμε την διαδικασία της ανάκτησης και για τις δυο παραπάνω περιπτώσεις, προσεγγίζοντας την συχνότητα με την οποία ένας ειδικός θα οριοθετούσε το εκάστοτε ασαφές αντικείμενο με συγκεκριμένο τρόπο καθώς και τα ενδογενή χαρακτηριστικά ενός ασαφούς αντικειμένου που έχει εξαχθεί από αυτόματο αλγόριθμο. Προτείνουμε κατάλληλο μηχανισμό ανάκτησης ο οποίος αναλαμβάνει την μετάβαση από τον χώρο της αναποφασιστικότητας και του ασαφούς στον χώρο της πιθανοτικής αναπαράστασης, διατηρώντας παράλληλα όλους τους περιορισμούς που έχουν επιβληθεί στα δεδομένα από την πρωταρχική ανάλυσή τους. Στην συνέχεια αξιολογούμε την διαδικασία της ανάκτησης, εφαρμόζοντας την νέα μέθοδο σε ήδη υπάρχον σύνολο δεδομένων από το οποίο και εξάγουμε συμπεράσματα για τα αποτελέσματά της. / Image data acquired through the use of bio-medical scanners are by nature fuzzy, thanks to a series of factors including limitations in spatial, temporal and parametric resolutions other than the physical limitations of the device. When the object of interest in such an image displays intensity patterns that are distinct from the patterns of other objects appearing together, a segmentation of the image in a hard, binary manner that clearly defines the borders between objects is feasible. It is frequent though that in such images factors like the lack of homogeneity between materials depicted, blurring, noise or deviations in the background pose difficulties in the above process. Intensity values in such an image appear in a fuzzy, gradient, “non-binary” manner. An innovative trend in the field of study is to make use of the fuzzy composition of objects in such an image, in a way in which fuzziness becomes a characteristic feature of the object instead of an undesirable trait: deriving from the theory of fuzzy sets, such approaches segment an image in a gradient, non-binary manner, therefore avoiding to set up a clear boundary between depicted objects. Such approaches are successful in capturing the fuzziness of the blurry image in mathematical terms, transforming the quality into a powerful tool of analysis in the hands of an expert. On the other hand, the scale of fuzziness observed in such images often leads experts towards different or contradictory segmentations, even drawn by the same human hand. What is more, the aforementioned case results in the compilation of image data bases consisting of multiple segmentations for each image, both binary and fuzzy. Are we able, by segmenting an image, to retrieve other similar such images whose segmented data have been acquired by experts, without downgrading the importance of the fuzziness of the objects depicted in any step involved? How exactly are images in such a database storing multiple segmentations of each retrieved? Is the frequency with which an expert would choose to either include or exclude from a fuzzy object a pixel of an image, a criterion of semblance between objects depicted in images? Finally, how able are we to tackle the feature of fuzziness in a probabilistic manner, thus providing a valuable tool in bridging the gap between automatic segmentation algorithms and segmentations coming from field experts? In the context of this thesis, we tackle the aforementioned problems studying thoroughly the process of image retrieval in a fuzzy context. We consider the case in which a database consists of images for which exist more than one segmentations, both crisp, derived by experts’ analysis, and fuzzy, generated by segmentation algorithms. We attempt to unify the retrieval process for both cases by taking advantage of the feature of fuzziness, and by approximating the frequency with which an expert would confine the boundaries of the fuzzy object in a uniform manner, along with the intrinsic features of a fuzzy, algorithm-generated object. We propose a suitable retrieval mechanism that undertakes the transition from the field of indecisiveness to that of a probabilistic representation, at the same time preserving all the limitations imposed on the data by their initial analysis. Next, we evaluate the retrieval process, by implementing the new method on an already existing data-set and draw conclusions on the effectiveness of the proposed scheme.

Αντικείμενο της παρούσας διπλωματικής εργασίας είναι αρχικά η καταγραφή της ανθρώπινης κίνησης με κάποια συσκευή παρακολούθησης και κατόπιν η δημιουργία ενός αντιπροσωπευτικού μοντέλου, ώστε να μπορεί να μελετηθεί η δυναμική του συμπεριφορά. Ως συσκευή καταγραφής χρησιμοποιήθηκε ο αισθητήρας Kinect της Microsoft. Το μοντέλο που αναπτύχθηκε αφορά κυρίως τα κάτω άκρα του ανθρώπου και επιπλέον διαθέτει μυοσκελετική δομή με 86 μύες. Στα πλαίσια των αναλύσεων χρησιμοποιήθηκαν διάφορες τεχνικές για την εξαγωγή των αποτελεσμάτων, όπως είναι η αντίστροφη κινηματική, αντίστροφη δυναμική, υπολογισμός μυϊκών διεγέρσεων και ορθή δυναμική και προτείνουμε μια στρατηγική για την ανάλυση και την εξαγωγή αποτελεσμάτων. / The research developed in this thesis first deal with the problem of capturing the human body motion and then concentrates on the creation of musculoskeletal models, which can capture and accurately study its dynamical behavior. The Microsoft's Kinect sensor was utilized to capture the human motion. The model used for the simulations is the human lower extremity with 86 attached muscles. For the analysis phase we used some common methods such as inverse kinematics, inverse dynamics, computed muscle control and forward dynamics and we showed a general pipeline strategy for generating correct results.

Στην εργασία αυτή γίνεται μια αναφορά αρχικά στα GSM δίκτυα κινητής τηλεφωνίας (χαρακτηριστικά-λειτουργίες). Στη συνέχεια περιγράφεται ο τρόπος υπολογισμού της κυτταρικής ακτίνας με βάση τα μοντέλα Okumura-Hata και Ikegami. Τέλος αναφέρονται παραδείγματα υπολογισμού της ακτίνας των κυττάρων αλλά και διαστασιοποίησης των καναλιών σε αυτά ώστε να εξυπηρετείται συγκεκριμένη τηλεπικοινωνιακή κίνηση. / The purpose of this project is to examine the major steps in cell planning process such as cell coverage, frequency planning and calculations of traffic and channel needs for the given areas.

Η διατριβή αυτή εξετάζει την χρήση γενετικών αλγορίθμων (ΓΑ) για την επίλυση του προβλήματος του σχεδιασμού κίνησης ρομποτικών συστημάτων τα οποία εκτελούν εργασίες εφοδιαστικής (όπως εργασίες λήψης και μεταφοράς από σημείο σε σημείο, μετακίνησης υλικών επί συνεχούς διαδρομής, κ.α.) στα πλαίσια λειτουργίας τους εντός ενός ευέλικτου συστήματος παραγωγής (ΕΣΠ). Το πρόβλημα του σχεδιασμού κίνησης (ΠΣΚ) είναι ένα υπολογιστικά άλυτο συνδυαστικό πρόβλημα βελτιστοποίησης (έχει αποδειχτεί PSPACE-hard) το οποίο μπορεί να οριστεί ως εξής: «Πως μπορεί ένα ρομπότ να αποφασίσει ποιες κινήσεις πρέπει να αποδώσει προκειμένου να εκτελέσει με επιτυχία επιθυμητές εργασίες στο περιβάλλον εργασίας του;» Προς τον σκοπό αυτό αναπτύχθηκε ένας αριθμός νέων, πρωτότυπων αλγορίθμων εμπνευσμένων από τη Βιολογία των οποίων η απόδοση μετρήθηκε τόσο μέσω πειραμάτων προσομοιωμένων σε υπολογιστή, όσο και σε πραγματικά ρομποτικά περιβάλλοντα στο εργαστήριο του Τμήματος. Συγκρινόμενοι με τις κλασσικές από τη βιβλιογραφία μεθόδους επίλυσης του ΠΣΚ, οι ΓΑ βρέθηκαν ανώτεροι τόσο από πλευράς ποιότητας των λύσεων που παρήγαγαν, όσο και από πλευράς ταχύτητας σύγκλησης (δηλαδή του χρόνου που χρειάστηκαν για τον εντοπισμό αυτών των λύσεων). Επιπρόσθετα, εξετάστηκαν και αντιμετωπίστηκαν με επιτυχία πολύπλοκα προβλήματα κινηματικής που αναφύονται κατά τον σχεδιασμό κίνησης ρομποτικών βραχιόνων σε ένα ΕΣΠ, όπως: Το αντίστροφο κινηματικό πρόβλημα ρομποτικών βραχιόνων με πλεονάζοντες βαθμούς ελευθερίας, η μεγιστοποίηση της επιδεξιότητας του ρομπότ κατά την εκτέλεση των εργασιών του και η παραγωγή με το άκρο εργασίας του ρομπότ ασφαλών και αξιόπιστων τροχιών επί προκαθορισμένων επιθυμητών διαδρομών. Η επίλυση αυτών των προβλημάτων είναι πολύ σημαντική σε πολλές πραγματικές βιομηχανικές εφαρμογές όπως εργασίες συγκόλλησης, βαψίματος ή επάλειψης με ψεκασμό, λείανσης, κ.α. / The use of genetic algorithms (GAs) for the solution of motion planning of robotic systems which perform logistics operations within a flexible manufacturing system (FMS), as well as, logistics tasks in indoors hazardous environments was investigated. Robot motion planning (RMP) is a PSPACE-hard combinatorial problem loosely stated as: How can a robot decide what motions to perform in order to achieve desired tasks in its environment? A number of new biological-inspired approaches were implemented and evaluated on computer simulated environments, as well as, on real industrial environments. In comparison to existing RMP methods, GAs were found superior in terms of both solutions quality and speed of convergence. Furthermore, focusing on RMP of robot manipulators, the proposed approaches tackled with high success difficult kinematics problems such as: the inverse kinematics for robots with redundant degrees of freedom, the maximization of robot’s manipulability, the path following by the robot’s end-effector on demanded trajectories.

Τα ασύρματα δίκτυα αισθητήρων (WSNs) είναι πολύ αναγνωρισμένα στις μέρες μας και γύρω από αυτά έχουν αναπτυχθεί χιλιάδες εφαρμογές που με χρήση άλλης τεχνολογίας ήταν σχεδόν ακατόρθωτες. Ένα WSN αποτελείται από κόμβους οι οποίοι είναι προγραμματισμένοι να επικοινωνούν και να συλλέγουν πληροφορίες μέσω των αισθητήρων που είναι αναρτημένοι πάνω τους. Οι πληροφορίες ή σύνολο των πληροφοριών καταλήγουν τελικά στους κόμβους που είναι προγραμματισμένοι ως τερματικοί κόμβοι ή βάσεις. Οι βάσεις είναι συνήθως συνδεδεμένες με ένα υπολογιστή και μεταφέρουν τα δεδομένα του δικτύου σε αυτόν. Τα κύρια χαρακτηριστικά των ασύρματων δικτύων αισθητήρων είναι η χαμηλή κατανάλωση ενεργείας των συσκευών-κόμβων (motes), η σταθερότητα και η απλότητα του κώδικα καθώς και η μεγάλη αξιοπιστία. Μερικές εφαρμογές των WSNs είναι για παράδειγμα η μέτρηση της υγρασίας στον τάπητα ενός γηπέδου γκολφ, η παρακολούθηση των κρίσιμων μεγεθών σε μεγάλες κατασκευές (π.χ. οι τάσεις των νημάτων μιας κρεμμαστης γέφυρας ή η παρακολούθηση της καταπόνησης των δοκών ενός ουρανοξύστη). Στα πλαίσια της διπλωματικής εργασίας αυτής παρουσιάζουμε ένα ασύρματο δίκτυο αισθητήρων όπου οι αισθητήρες είναι έξυπνες κάμερες! Παρουσιάζει μεγάλο ενδιαφέρον η μελέτη ενός τέτοιου δικτύου καθώς και η ανάπτυξη εφαρμογών γύρω από αυτό. / Wireless Sensor Networks (WSNs) are very much recognized these days, and thousands of applications have been developed in relation to them, which, would have been impossible if other technologies were used. A WSN is made up of nodes programmed to collect information through sensors attached to them and transmit them. The information ends up finally to the nodes which are programmed as terminal nodes or base-stations. These base-stations are usually connected to a computer and transfer the data that have been retrieved from the network to it. The main features of a WSN is the low energy consumption by the node equipment (motes), the stability and simplicity of the code as well as their great reliability. Some applications of the WSNs are, for example, the measurement of humidity in a golf course, the monitoring of the crucial sizes in great constructions (e.g. the tensions of the fibers in a suspension bridge, the monitoring of the strains of girders in a skyscraper) Within the context of this thesis, we present a WSN where the sensors are smart cameras! The study of such a network presents great interest as well as the development of applications based on it.

Το Διαδίκτυο αναμφίβολα αποτελεί την μεγαλύτερη ανακάλυψη στον τομέα διάδοσης της πληροφορίας από την εποχή του Γουτεμβέργιου και της τυπογραφίας, έχοντας ριζικά αλλάξει τον τρόπο επικοινωνίας και αλληλεπίδρασης των ανθρώπων. Στον πυρήνα του Διαδικτύου βρίσκονται τεχνολογίες οι οποίες αναπτύχθηκαν με σκοπό την επίτευξη επικοινωνίας ανάμεσα σε ετερογενή συστήματα και δίκτυα. Με αυτό τον τρόπο, ενώ το Διαδίκτυο αρχικά αποτελείτο αποκλειστικά από δίκτυα υπολογιστών, στην συνέχεια ενσωματώθηκαν σε αυτό και άλλοι τύποι δικτύων όπως τα σταθερά τηλεφωνικά δίκτυα, τα δίκτυα κινητής τηλεφωνίας, τα δορυφορικά δίκτυα, κ.α. Πλέον το Διαδίκτυο αποτελεί ένα μετα-δίκτυο δικτύων το οποίο συνεχίζει να επεκτείνεται και οι αντίστοιχες υποστηρικτικές τεχνολογίες συνεχίζουν να εξελίσσονται. Στο ορατό μέλλον, στο Διαδίκτυο θα προστεθούν και τα ενσωματωμένα συστήματα ελέγχου πραγματώνοντας με αυτό τον τρόπο το όραμα του Διαδικτύου των Αντικειμένων (Internet of Things). Η κύρια υποστηρικτική τεχνολογία για το Διαδίκτυο των Αντικειμένων είναι τα Ασύρματα Δίκτυα Αισθητήρων (Α.Δ.Α.). Τα Ασύρματα Δίκτυα Αισθητήρων αποτελούν μία ειδική κατηγορία κατανεμημένων και αυτό-οργανούμενων δικτύων τα οποία υπόσχονται να γεφυρώσουν το χάσμα ανάμεσα στον φυσικό και τον ψηφιακό κόσμο. Αποτελούνται από μικρές αυτόνομες συσκευές, περιορισμένων υπολογιστικών δυνατοτήτων, εξοπλισμένες με ψηφιακούς αισθητήρες. Οι συσκευές αυτές συλλέγουν δεδομένα και δουλεύοντας συνεργατικά μεταξύ τους, τα διαδρομούν μέσω πολύ-βηματικών μεταδόσεων. Με αυτό τον τρόπο, αν και ο κάθε κόμβος του δικτύου χαρακτηρίζεται από σημαντικούς περιορισμούς (στην υπολογιστική ισχύ, την ενέργεια, την ασύρματη επικοινωνία, κ.α.) τα δίκτυα τα οποία συντίθενται είναι σε θέση να φέρουν εις πέρας δύσκολα υπολογιστικά προβλήματα, παράγοντας και διακινώντας μεγάλες ποσότητες πληροφορίας. Η διατριβή που κρατάτε στα χέρια σας αποτελεί προϊόν πρωτότυπης έρευνας σε ζητήματα αποδοτικής συλλογής δεδομένων από Ασύρματα Δίκτυα Αισθητήρων, ενώ έχει παρουσιαστεί σε γνωστά επιστημονικά περιοδικά και ανταγωνιστικά συνέδρια διεθνούς κύρους. Το κείμενο είναι οργανωμένο σε τρεις ενότητες. Στην πρώτη ενότητα μελετώνται θέματα κίνησης στα Ασύρματα Δίκτυα Αισθητήρων. Πιο συγκεκριμένα προτείνεται μια οικογένεια ευρετικών αλγορίθμων για την γρήγορη και αποδοτική συλλογή δεδομένων από δίκτυα τα οποία χαρακτηρίζονται από έντονη και δυναμική κινητικότητα των κόμβων. Επιπλέον, μελετώνται οι τυχαίοι περίπατοι ως απλές, αποδοτικές στρατηγικές κίνησης κέντρων ελέγχου για την συλλογή δεδομένων σε δίκτυα αισθητήρων με στατικούς κόμβους. Για την αναπαράσταση των δικτύων χρησιμοποιούνται τα μοντέλα του πλέγματος και των τυχαίων γεωμετρικών γράφων. Στην δεύτερη ενότητα μελετώνται δύο πρόσφατα θεμελιωμένα προβλήματα στα Ασύρματα Δίκτυα Αισθητήρων (σχετιζόμενα με πρόσφατες τεχνολογικές εξελίξεις) και παρουσιάζονται αντίστοιχες πρωτότυπες προσεγγίσεις. Το πρώτο πρόβλημα εξετάζει την διαδρόμηση δεδομένων με πρωτόκολλα χαμηλής ηλεκτρομαγνητικής ακτινοβολίας υπό το πρίσμα των Ασύρματων Δικτύων Αισθητήρων. Ωστόσο, πρέπει να σημειωθεί ότι το πρόβλημα ανάγεται ευρύτερα σε ετερογενή ασύρματα δίκτυα. Το δεύτερο πρόβλημα εξετάζει την διαχείριση ενέργειας σε Ασύρματα Δίκτυα Αισθητήρων στα οποία μία ειδική μονάδα κινούμενη μέσα στο δίκτυο επαναφορτίζει τους κόμβους μέσω ασύρματης μετάδοσης ενέργειας. Στην τρίτη ενότητα παρουσιάζονται μια σειρά πρότυπων συστημάτων και εφαρμογών του Μελλοντικού Διαδικτύου, που αναπτύχθηκαν στα πλαίσια της παρούσας διατριβής. Τα συστήματα συνδυάζουν τα Ασύρματα Δίκτυα Αισθητήρων με την νέας γενιάς στοίβα πρωτοκόλλων επικοινωνίας IPv6 καθιστώντας δυνατή την απρόσκοπτη και διαφανή επικοινωνία των κόμβων του δικτύου με το Διαδίκτυο και τον έξω κόσμο. Οι εφαρμογές των συστημάτων περιλαμβάνουν την ανάπτυξη ενός έξυπνου/πράσινου δωματίου και αντίστοιχων σεναρίων χρήσης του με δυνατότητες απομακρυσμένου ελέγχου μέσω Διαδικτύου (προσωποποίηση της συμπεριφοράς του δωματίου στον χρήστη, αλληλεπίδραση του δωματίου στην φυσική παρουσία, ασφαλής εκκένωση κτηρίου σε συνθήκες κινδύνου, κ.α.), την ανάπτυξη πρότυπου συστήματος έξυπνης άρδευσης, τον εντοπισμό θέσης με υψηλή ακρίβεια σε εσωτερικό χώρο, καθώς και την επεξεργασία κοινωνικής σηματοδότησης κατά την διάρκεια ανθρώπινων αλληλεπιδράσεων. Με την παρούσα διδακτορική διατριβή κλείνει ένας κύκλος έρευνας που διήρκεσε κάτι λιγότερο από πέντε χρόνια. Ωστόσο, αρκετά θέματα θα αποτελέσουν και στο μέλλον πεδίο έντονης ερευνητικής δραστηριότητας. Η εκπεμπόμενη ηλεκτρομαγνητική ακτινοβολία κατά την διάρκεια ασύρματων μεταδόσεων δεδομένων είναι ένα αμφιλεγόμενο ζήτημα από την πλευρά της ασφάλειας της δημόσιας υγείας. Πιστεύουμε όμως ότι αξίζει να μελετηθεί και από τον κλάδο της Επιστήμης των Υπολογιστών καθώς το πλήθος των ασύρματων δικτύων και η πυκνότητα της περιρρέουσας ακτινοβολίας στην καθημερινή μας ζωή ολοένα και αυξάνεται. Ένα δεύτερο πεδίο έρευνας αναδύεται από την πραγμάτωση του Διαδικτύου των Αντικειμένων και τις δυνατότητες που αυτό παρέχει στα πλαίσια του Μελλοντικού Διαδικτύου. Ενδεικτικά αναφέρεται η ανάδειξη νέων μοντέλων δικτύων στα πρότυπα των κοινωνικών δικτύων, τα οποία θα περιλαμβάνουν αλληλεπιδράσεις ανάμεσα σε ανθρώπους και σε αντικείμενα. Καλή Ανάγνωση. / The Internet is undoubtedly the biggest breakthrough in dissemination of information since the era of Gutenberg and the printing press that has radically changed the way of communication and interaction among people. At the core of the Internet lie technologies which are developed to achieve communication between heterogeneous systems and networks. In this way, while the Internet initially consisted exclusively of computer networks, it then incorporated other types of networks as well, such as land line telephone networks, cellular networks, satellite networks, social networks and so on. Nowadays, the Internet is a meta-network of networks which continues to expand and relevant enabling technologies continue to evolve. In the foreseeable future, the Internet will also include embedded control systems, thus realizing the vision of the Internet of Things. The main enabling technology of the Internet of Things vision is Wireless Sensor Networks (WSNs). Wireless Sensor Networks are a special class of distributed and self-organized networks which promise to bridge the gap between the physical and digital world. A WSN consists of small autonomous devices with minimal computational capabilities that are equipped with digital sensors. These devices collect data from their immediate environment and working collaboratively with each other, propagate them via multi-hop transmissions. In this way, although each node of the network is characterized by significant limitations (in terms of computational power, energy reserves, wireless communication capabilities, etc.) the formed networks are able to carry out difficult computational problems and thus to generate and route large amounts of information. The dissertation that you hold in your hands is the product of original and novel research on several aspects of efficient data collection from Wireless Sensor Networks. Corresponding research findings have been published in prestigious scientific journals and competitive, peer-reviewed international conferences. The dissertation is organized into three parts. In the first part mobility aspects of Wireless Sensor Networks are studied. More specifically, a family of heuristic algorithms is proposed for fast and efficient data collection in networks that are characterized by diverse and dynamic node mobility. Moreover, random walks are studied as simple, efficient mobility strategies for data collection in sensor networks in which sensor motes are stationary. Sensor networks are modeled either as Grids or as Random Geometric Graphs. In the second part two recently acquired problems in Wireless Sensor Networks (associated with recent technological advances) are studied. The first problem examines data routing protocols that yield low electromagnetic radiation in the context of Wireless Sensor Networks. The second problem examines energy management in Wireless Sensor Networks in which a special unit (namely the Charger) traverses the network area and is able to recharge sensor motes via wireless energy transfer. In the third part a series of prototype systems and applications for the Future Internet that have been developed in the context of this dissertation are presented. These systems combine Wireless Sensor Networks with the new generation, IPv6 Internet protocol stack, thus allowing seamless and transparent communication between sensor motes and the rest of the Internet world. These systems include the development of a smart / green room and corresponding use-case scenarios (room adaptation to human presence, safe evacuation in emergency conditions, etc.), the development of a prototype smart irrigation system, fine grained in-door localization, and social signal processing. This dissertation concludes a research cycle, which lasted a little less than five years. However, there is more than enough space for future research. The emitted electromagnetic radiation during wireless data transmissions is a controversial issue in terms of public health. However, we believe that it worth’s to be studied from an ICT point of view as the number of wireless networks in our everyday life keeps growing. A second area of research emerges from the realization of the Internet of Things vision and the opportunities it provides as part of the Future Internet; for instance the emergence of a new social network paradigm, that will capture interactions between humans and objects.

Στην παρούσα διατριβή παρουσιάζονται παράλληλοι αλγόριθμοι και εφαρμογές σε πολυπύρηνες μονάδες επεξεργασίας γραφικών. Πιο συγκεκριμένα, εξετάζονται οι μέθοδοι σχεδίασης ενός παράλληλου αλγορίθμου για την επίλυση τόσο απλών και κοινών προβλημάτων, όπως η ταξινόμηση, όσο και υπολογιστικά απαιτητικών προβλημάτων, έτσι ώστε να εκμεταλλευτούμε πλήρως την τεράστια υπολογιστική δύναμη που προσφέρουν οι σύγχρονες μονάδες επεξεργασίας γραφικών. Πρώτο πρόβλημα που εξετάστηκε είναι η ταξινόμηση, η οποία είναι ένα από τα πιο συνηθισμένα προβλήματα στην επιστήμη των υπολογιστών. Υπάρχει σαν εσωτερικό πρόβλημα σε πολλές εφαρμογές, επομένως πετυχαίνοντας πιο γρήγορη ταξινόμηση πετυχαίνουμε πιο καλή απόδοση γενικότερα. Στο Κεφάλαιο 3 περιγράφονται όλα τα βήματα σχεδιασμού για την εκτέλεση ενός αλγορίθμου ταξινόμησης για ακεραίους, της count sort, σε μια μονάδα επεξεργασίας γραφικών. Σημαντική επίδραση στην απόδοση είχε η αποφυγή του συγχρονισμού των νημάτων στο τελευταίο βήμα του αλγορίθμου. Στη συνέχεια παρουσιάζονται εφαρμογές παράλληλων αλγορίθμων σε υπολογιστικά απαιτητικά προβλήματα. Στο Κεφάλαιο 4, εξετάζεται το πρόβλημα χρονοπρογραμματισμού εξετάσεων Πανεπιστημίων, το οποίο είναι ένα πρόβλημα συνδυαστικής βελτιστοποίησης. Για την επίλυσή του χρησιμοποιείται ένας υβριδικός εξελικτικός αλγόριθμος, ο οποίος εκτελείται εξ' ολοκλήρου στην μονάδα επεξεργασίας γραφικών. Η τεράστια υπολογιστική δύναμη της GPU και ο παράλληλος προγραμματισμός δίνουν τη δυνατότητα χρήσης μεγάλων πληθυσμών έτσι ώστε να εξερευνήσουμε καλύτερα τον χώρο λύσεων και να πάρουμε καλύτερα ποιοτικά αποτελέσματα. Στο επόμενο κεφάλαιο γίνεται επίλυση του προβλήματος σχεδιασμού κίνησης για υποθαλάσσια οχήματα με βραχίονα. Εξετάζεται το πρόβλημα τόσο του ολικού σχεδιασμού όσο και του τοπικού. Στην πρώτη περίπτωση είναι σημαντική η καλή λύση και η ακρίβεια και ο παράλληλος αλγόριθμος που χρησιμοποιείται για την αναπαράσταση του περιβάλλοντος εργασίας σε μια Bump-επιφάνεια βοηθάει προς αυτή την κατεύθυνση. Στη δεύτερη περίπτωση, το πρόβλημα είναι πρόβλημα πραγματικού χρόνου και μας ενδιαφέρει η ταχύτητα εύρεσης της επόμενης θέσης του οχήματος. Ο παράλληλος προγραμματισμός και η GPU βοηθούν σημαντικά σε αυτό. Τελευταία εφαρμογή που εξετάστηκε είναι η μελέτη ενός συστήματος ημιφθοριωμένων αλκανίων με την μοριακή προσομοίωση Monte Carlo. Η παραλληλοποίηση ενός μέρους, του πιο χρονοβόρου, του αλγορίθμου έδωσε τη δυνατότητα εξέτασης ενός πολύ μεγαλύτερου συστήματος σε αποδεκτό χρόνο. Σε γενικές γραμμές, γίνεται φανερό ότι ο παράλληλος προγραμματισμός και οι σύγχρονες πολυπύρηνες αρχιτεκτονικές, όπως οι μονάδες επεξεργασίας γραφικών, δίνουν νέες δυνατότητες στην αντιμετώπιση καθημερινών προβλημάτων, προβλημάτων πραγματικού χρόνου και προβλημάτων συνδυαστικής βελτιστοποίησης. / In this thesis, parallel algorithms and applications in manycore graphics processing units are presented. More specifically, we examine methods of designing a parallel algorithm for solving both simple and common problems such as sorting, and computationally demanding problems, so as to fully exploit the enormous computing power of modern graphics processing units (GPUs). First problem considered is sorting, which is one of the most common problems in computer science. It exists as an internal problem in many applications. Therefore, sorting faster, results in better performance in general. Chapter 3 describes all design options for the implementation of a sorting algorithm for integers, count sort, on a graphics processing unit. The elimination of thread synchronization in the last step of the algorithm had a significant effect on the performance. Chapter 4 addresses the examination timetabling problem for Universities, which is a combinatorial optimization problem. A hybrid evolutionary algorithm, which runs entirely on GPU, was used to solve the problem. The tremendous computing power of GPU and parallel programming enable the use of large populations in order to explore better the solution space and get better quality results. In the next chapter, the problem of motion planning for underwater vehicle manipulator systems is examined. In the gross motion planning problem, it is important to achieve a good solution with high accuracy. The parallel algorithm used for the representation of the working environment in a Bump-surface is a step towards this direction. In the local motion planning problem, which is a real-time problem, the time needed to find the next configuration of the vehicle is crucial. Parallel programming and the GPU greatly assist in this online problem. Last application considered is the atomistic Monte Carlo simulation of semifluorinated alkanes. The parallelization of part of the algorithm, the most time-consuming, enabled the study of a much larger system in an acceptable execution time. In general, it becomes obvious that parallel programming and new novel manycore architectures, such as graphics processing units, give new capabilities for solving everyday problems, real time and combinatorial optimization problems.