Τα δίκτυα αισθητήρων είναι μια εξειδικευμένη κατηγορία κατανεμημένων δικτύων, η οποία τα τελευταία χρόνια έχει συγκεντρώσει το ενδιαφέρον της ερευνητικής κοινότητας, λόγω του ευρύτατου πεδίου εφαρμογών της. Τα δίκτυα αυτά αποτελούνται από συσκευές που διαθέτουν αισθητήρες (sensors) και ενδεχομένως μηχανισμούς δράσης (actuators) και είναι διασκορπισμένες στο χώρο, με δυνατότητα επικοινωνίας μεταξύ τους και επεξεργασίας σε ένα βαθμό της πληροφορίας που διακινούν στο δίκτυο. Στόχος των δικτύων αυτών είναι η παρακολούθηση της εξέλιξης ενός φαινόμενου, ή η ανίχνευση περιβαλλοντικών συνθηκών και η αποστολή των δεδομένων που συλλέγονται σε έναν κεντρικό κόμβο, το κέντρο ελέγχου. Οι δυνατότητες των συσκευών είναι κατά κανόνα περιορισμένες, λόγω του μικρού μεγέθους τους, του χαμηλού κόστους τους και ενίοτε του αναλώσιμου ρόλου τους. Οι εφαρμογές των δικτύων αυτών ποικίλουν, από εφαρμογές στην επιστήμη γεωργίας ακριβείας, στην πυρανίχνευση και την παρακολούθηση συνθηκών περιβάλλοντος σε κτιριακές εγκαταστάσεις, μέχρι εφαρμογές ανίχνευσης κίνησης των εχθρικών μονάδων σε πεδίο μάχης, ή παρακολούθησης φαινόμενου που εξελίσσεται σε δυσπρόσιτη περιοχή. Μερικές από τις βασικές προκλήσεις που προκύπτουν σε αυτά τα δίκτυα, λόγω της φύσης τους, είναι η βέλτιστη διαχείριση των ενεργειακών πόρων κάθε κόμβου, η αποδοτική συνδυαστική επεξεργασία των διακινούμενων μηνυμάτων και η αξιόπιστη δρομολόγηση της πληροφορίας που συλλέγεται προς το κέντρο ελέγχου, καθώς και η δυναμική και αυτόνομη οργάνωση του δικτύου. Η εξέλιξη των δικτύων αισθητήρων σε συνδυασμό με την επιθυμία υλοποίησης περίπλοκων και περισσότερο ολοκληρωμένων εφαρμογών, οδήγησε σε δίκτυα που περιέχουν ετερογενείς κόμβους, όπως για παράδειγμα κόμβους με διαφορετική αρχιτεκτονική, διαφορετικούς αισθητήρες, με διαφορετικές επεξεργαστικές και επικοινωνιακές ικανότητες ή και κόμβους με δυνατότητες κίνησης ή επιτέλεσης εργασιών (actuators) σε απόκριση εντολών που λαμβάνουν από το κέντρο ελέγχου. Επιπρόσθετα, σε πολλές εφαρμογές διαφαίνεται η ανάγκη για διασύνδεση πολλαπλών δικτύων αισθητήρων και διάδοση της πληροφορίας που συλλέγουν μέσω του διαδικτύου προς απομακρυσμένους εξυπηρετητές με αυξημένες επεξεργαστικές ικανότητες, προς βάσεις δεδομένων, συσκευές pda ή κινητά τηλέφωνα, σταθμούς εργασίας τελικών χρηστών και άλλες συσκευές. Δημιουργείται με αυτόν τον τρόπο ένα ευρύτερο ετερογενές δίκτυο επικάλυψης (overlay sensor network), η διαχείριση και αποδοτική χρήση του οποίου απαιτεί νέες αρχιτεκτονικές οργάνωσης των επιμέρους δικτύων, προσαρμοσμένα πρωτόκολλα διάδοσης πληροφορίας και πλατφόρμες που διευκολύνουν τον προγραμματισμό των δικτύων αυτών. Για το λόγο αυτό η επιστημονική κοινότητα επικεντρώνει το ενδιαφέρον της στο σχεδιασμό ειδικών περιβαλλόντων λογισμικού που μεσολαβούν ανάμεσα στον προγραμματιστή εφαρμογών και τα ετερογενή δίκτυα αισθητήρων, τα οποία ανήκουν στην κατηγορία των middleware. Τα περιβάλλοντα αυτά αναλαμβάνουν να διαχειριστούν θέματα χαμηλού επιπέδου ή και ανώτερων επιπέδων στα δίκτυα αισθητήρων, που δεν θα έπρεπε να απασχολούν τον προγραμματιστή κάθε φορά που επιθυμεί να υλοποιήσει μια εφαρμογή. Απώτερος σκοπός είναι να παρέχουν υπηρεσίες υψηλού επιπέδου και ομοιογενείς λογικές αφαιρέσεις πάνω στα ετερογενή δίκτυα, ενώ είναι επιθυμητή η αποδοτική λειτουργία τους σε παγκόσμια κλίμακα όπου πολλά γεωγραφικά διάσπαρτα δίκτυα συνεργάζονται για να παρέχουν τις υπηρεσίες τους με οργανωμένο και καλά ορισμένο τρόπο. Η δική μας συνεισφορά στην έρευνα του πεδίου αυτού, έγκειται πρώτα στη μελέτη ήδη διαθέσιμων προτάσεων middleware για τον προγραμματισμό και τη διασύνδεση πολλαπλών και ετερογενών δικτύων αισθητήρων, με σκοπό τον εντοπισμό των θεμάτων και προβλημάτων που αντιμετώπισαν κατά το σχεδιασμό τους, την ανάλυση της αρχιτεκτονικής τους και την αξιολόγηση της απόδοσής τους. Επιθυμώντας να δώσουμε τη δική μας πρόταση στο πεδίο των middleware για δίκτυα αισθητήρων και αξιοποιώντας τα συμπεράσματά μας από την μελέτη των άλλων προτάσεων, σχεδιάσαμε και υλοποιήσαμε το middleware σύστημα ShareSense II. Το σύστημα ShareSense II προέρχεται από τον επανασχεδιασμό τού αρχικού και απλούστερου ShareSense και ενσωματώνει το middleware jWebDust επεκτείνοντας κατά ένα τρόπο την αρχιτεκτονική του, ώστε να υποστηρίζει δίκτυα επικάλυψης (overlay sensor networks) μεγάλης κλίμακας. Η πλατφόρμα του ShareSense II σχεδιάστηκε για να παρέχει λογική αφαίρεση των δικτύων αισθητήρων, ώστε ο προγραμματιστής να μπορεί εύκολα να ρυθμίσει τις υπηρεσίες που παρέχει ένα δίκτυο επικάλυψης, να διαχειρίζεται τις λειτουργίες των επιμέρους δικτύων, να μπορεί να προγραμματίσει δυναμικά τη συμπεριφορά τους και να καθορίσει τον τρόπο παρουσίασης της χρήσιμης πληροφορίας που αποκομίζει από αυτά, στον τελικό χρήστη. Βασιζόμενοι στην ευέλικτη υποδομή των peer-to-peer δικτύων, προτείνουμε μια λύση για τη διασύνδεση πολλαπλών ετερογενών δικτύων αισθητήρων με συσκευές και σταθμούς εργασίας πάνω από το διαδίκτυο. Δώσαμε έμφαση στην επεκτασιμότητα της αρχιτεκτονικής ως προς τις υποστηριζόμενες υπηρεσίες και τύπους δικτύων, την αξιοποίηση και τη συνεργασία με υπάρχοντα middleware που διαχειρίζονται κάποια επιμέρους δίκτυα και την παροχή χρήσιμων διεπαφών για την εύκολη υλοποίηση πρακτικών εφαρμογών. Υλοποιήσαμε, τέλος, μια εφαρμογή η οποία στηρίζεται στην πλατφόρμα του ShareSense II για να τεκμηριώσουμε την επάρκεια της αρχιτεκτονικής του συστήματός μας και να εντοπίσουμε τα σημεία όπου απαιτείται βελτίωσή της. Η εφαρμογή χρησιμοποιεί το περιβάλλον του Google Earth για την παρακολούθηση των επιμέρους δικτύων που συμμετέχουν στο σύστημα, επιτρέποντας παράλληλα τη δυναμική υποβολή ερωτημάτων και την αντιστοίχιση των δικτύων σε τρισδιάστατα μοντέλα κτιρίων και άλλων περιοχών, ώστε να είναι άμεση και εύληπτη η παρουσίαση της πληροφορίας στον τελικό χρήστη. / Sensor networks are a special case of distributed networks, which in the recent years have become increasingly interesting to the scientific community, due to their wide range of applications. These networks are comprised of devices that have sensors attached to them and possibly even actuators, and are scattered in a field, being able to comminucate with each other and process -to a certain degree- information that they forward in the network. Among the goals of these networks are the monitoring of physical phenomena, the detection of special events or conditions and consequently the communication of the acquired information towards a control center. These devices usually have strict constraints on their capabilities due to their small size, their low production cost and quite often their expendable role. The applications of these networks vary, from applications in the precision agriculture field, fire detection and monitoring environmental conditions in buildings and offices, to applications for the detection of enemy units' movements in the battlefield or observing a physical phenomenon in a inaccessible location. Some of the important challeges that emerge for these networks are the optimal management of the power resources of each node, the efficient aggregation of the in-network messages and the reliable routing of information acquired towards the control center, as well as the autonomous and adaptive network operation. The evolution in the sensor netorks research in combination with the desire to implement even more sophisticated applications, has led to highly heterogeneous networks, where nodes belong to different architectures, they use various sensor models, and they have different processing and communicating capabilities. Additionally, in many applications there is the need to interconnect multiple sensor networks and to distribute the information collected locally towards remote servers, databases, pda devices or cell phones, workstations and other end user devices. Thus, a new type of networks, the overlay networks, emerges. The administration and effecient usage of these networks require new management architectures for the local networs, adaptive protocols for the distribution of information and new software platforms that simplify application programming. Following these developments, the scientific community has focused in designing middleware software for the sensor networks. Such software have the role of managing low level or intermediate level issues, that should not burden a programmer every time s/he needs to design and implement a new application. The main goal of middleware is to provide high level services and unified logical abstractions over heterogeneous sensor networks, and to perform well in a global scale where multiple geographically disparate networks cooperate to provide services in an organized and well defined manner. Our contribution to this field, is foremost to study the state of the art middleware projects for overlay sensor networks, in an effort to understand the issues and problems that were faced during their design, to analyze their architecure and evaluate their performance. We have used the results of this study to design and implement a new middleware architecture, which we have named ShareSense II. Our middleware comes from the redesign and expansion of its simpler predecessor, the original ShareSense middleware, and also integrates the jwebdust middleware, bringing the services of that middleware to the large scal overlay networks. The ShareSense II platfrom was designed to provide logical abstractions for sensor networks, so that the programmer is able to tweak their services, maange the resources of the local networks and build flexible applications. For our overlay netowrk we have embedded an efficient peer-to-peer infrastructure that performs well in networks with frequent and temporary node disconnections and large scale applications. Finally, we implemented an application that uses the ShareSense II middleware, in order to show the benefits of our design and also locate the parts of the architecture that need further optimization. Our application uses the Google Earth software to monitor geographically disparate networks that participate in ShareSense II, allowing the online issuing of queries, as well as matching 3d models of buildings (and other areas) to local networks, in order to display information to the end user in an interesting and exciting way.

Ανέκαθεν, η ανάγκη του ανθρώπου για πληροφορία ήτανε μια από αυτές που φρόντιζε να ικανοποιήσει όσο το δυνατόν πληρέστερα. Η πληροφορία είναι σε όλες τις περιπτώσεις ένα πολύτιμο εργαλείο στην λήψη αποφάσεων και οι άνθρωποι γρήγορα αντιλήφθηκαν την σημασία της, ειδικότερα μάλιστα στην σύγχρονη εποχή στην οποία μέσω της επιστήμης της Πληροφορικής δόθηκε η δυνατότητα σε μεγάλο μέρος του κοινού να έχει πρόσβαση σε τεράστιο όγκο δεδομένων, τα οποία μέσω της σωστής επεξεργασίας μετατρέπονται σε πληροφορία. Αυτό που πλέον αποτελεί πρόκληση, η οποία μας καλεί σαν επιστήμονες της Πληροφορικής να αντιμετωπίσουμε, είναι η εύρεση και στην συνέχεια η εφαρμογή καινούργιων μεθόδων γρήγορης και ανέξοδης συλλογής, αποδοτικής αποθήκευσης και εποικοδομητικής ανάλυσης δεδομένων, έτσι ώστε να γίνουν πληροφορία ποιοτική, πλούσια και με σημαντική χρηστική αξία. Στις μέρες μας, η ανάπτυξη του κλάδου τόσο των κατανεμημένων συστημάτων όσο και του διαδικτύου, μας έχουνε δώσει την δυνατότητα να χρησιμοποιούνται χαμηλοί σε απαιτήσεις υπολογιστικοί πόροι για να επεξεργάζονται παράλληλα μεγάλο όγκο δεδομένων. Ο κλάδος της Πληροφορικής που ασχολείται εκτενώς με αυτά τα συστήματα είναι τα ομότιμα συστήματα ή αλλιώς p2p συστήματα και ο κατανεμημένος υπολογισμός. Η παρούσα διπλωματική εργασία έχει ως στόχο να βρίσκει σε κατανεμημένο περιβάλλον σημεία στις δύο διαστάσεις. Ορίζεται, δηλαδή, ένας χώρος από κ – διαστάσεις που είναι το πλέγμα (grid), στον οποίο ο χρήστης προσπαθεί να εντοπίσει σημεία που τον ενδιαφέρουν δημιουργώντας έτσι ερωτήματα εύρους. Το σύστημα θα ψάχνει να βρει το αποτέλεσμα στο ερώτημα αυτό για να καταλήξει σε ποιο από τα άλλα ορθογώνια τμήματα του πλέγματος εμπλέκεται και στην συνέχεια αυτά (τα τμήματα) θα επιστρέφονται. Πιο συγκεκριμένα, το πλέγμα μας χωρίζεται σε τετράγωνες περιοχές και κάθε κόμβος του κατανεμημένου δικτύου αναλαμβάνει να φιλοξενήσει τα σημεία της κάθε τετράγωνης περιοχής. Όλοι αυτοί οι κόμβοι οργανώνονται σε ένα hadoop cluster και τα δεδομένα εισάγονται στην κατανεμημένη βάση δεδομένων HBase που βασίζεται στην αρχιτεκτονική του BigTable της Google File System. Ο τρόπος που οργανώνονται τα δεδομένα στην HBase είναι κατανεμημένος και γίνεται χρήση των B+ -δέντρων. Η χρησιμότητα των B+ -δέντρων σε συνδυασμό με το κατανεμημένο πλαίσιο εργασίας του Hadoop, έγκειται στο γεγονός ότι με την χρήση των απαραίτητων εργαλείων τόσο της HBase όσο και του Hadoop FS, μπορούμε να γνωρίζουμε σε ποιόν κόμβο του hadoop cluster είναι αποθηκευμένοι οι ζητούμενοι κόμβοι του B+ -δέντρου και έτσι να επιτυγχάνεται η γρήγορη ανάκτηση των αποτελεσμάτων σε ένα ερώτημα εύρους. Η διάρθρωση της εργασίας έχει ως εξής: Στο πρώτο κεφάλαιο γίνεται μια εισαγωγή στις έννοιες του κατανεμημένου υπολογισμού πάνω σε κατανεμημένα περιβάλλοντα. Στο δεύτερο γίνεται μια αναφορά στα ομότιμα δίκτυα (p2p) και πιο συγκεκριμένα αναλύεται το δίκτυο επικάλυψης του BATON που έχει δενδρική δομή όμοια με αυτή του Β+ -δέντρου. Στο τρίτο κεφάλαιο αναφέρεται μια υλοποίηση δεικτοδότησης και απάντησης σε ερωτήματα εύρους στο Νέφος Υπολογιστών με χρήση βασικών δομών δεδομένων B+ -δέντρου. Επίσης, η ART Autonomous Range Tree δομή παρουσιάζεται η οποία μπορεί να υποστηρίξει ερωτήματα εύρους σε τόσο ευρείας κλίμακας σε μη κεντρικοποιημένα περιβάλλοντα και μπορεί να κλιμακώνεται σε σχέση με τον αριθμό των κόμβων, καθώς και με βάση τα στοιχεία που είναι αποθηκευμένα. Η ART δομή ξεπερνά τις πιο δημοφιλείς μη κεντρικοποιημένες δομές, συμπεριλαμβανομένου του Chord (και μερικοί από τους διαδόχους του), του ΒΑΤΟΝ (και τον διάδοχό του) και των Skip-Graphs. Στο τέταρτο και πέμπτο κεφάλαιο, αντίστοιχα, γίνεται μια αναφορά στα βασικότερα σημεία της αρχιτεκτονικής και της λειτουργίας του Hadoop Framework και της HBase. Στο έκτο κεφάλαιο, βρίσκεται η περιγραφή της υλοποίησης της παρούσης διπλωματικής εργασίας μαζί με τους αλγορίθμους και τον τρόπο λειτουργίας τους. Στο επόμενο γίνεται η αξιολόγηση των πειραματικών αποτελεσμάτων της παρούσης διπλωματικής εργασίας καθώς, και το τι συμπεράσματα προκύπτουν μέσα από την αξιολόγηση. Τέλος, στο τελευταίο και όγδοο κεφάλαιο γίνεται η αποτίμηση της διπλωματικής εργασίας, καθώς αναφέρονται τα βασικά της μέρη, όπως επίσης και πιθανές προεκτάσεις που θα βελτίωναν την απόδοση του συστήματος. / Traditionally, the human need for information was one of those seeking to satisfy as much as possible. Information is in every way a valuable tool in decision making and people quickly realized its importance, especially in modern times, when the Information Technology gave the public access to the vast volume of data, which can be further processed into information. What seems to be now a challenge that IT specialists have to face is finding and implementing new methods of fast and inexpensive data collection, efficient storing of data and constructive data analysis, in order to turn them into quality, rich and useful information. Nowadays, the devel-opment of both the field of distributed systems and the Internet gave us the possibility of using computational resources with low requirements for simultaneous processing of large amounts of data. The IT field that deals extensively with these systems are peer-to-peer systems (p2p) and distributed computing. The present dissertation aims at finding points in a distributed environment in the two-dimensional space. A space of k – dimensions is defined, i.e. the grid, in which the user tries to identify points of interest creating range queries. The system will search to find the result in this question to come up with the rectangular section of the grid that is involved and then these sections will be returned. More specifically, the grid is divided into square areas, and each node of the distributed network will accommodate points of each square area. All these nodes are organized into a hadoop cluster and the data is imported into the HBase distributed database based on BigTable architecture of the Google File System. In HBase data is organized in a distributed way and B+ -trees are used. The utility of B+ -trees in conjunction with the distributed framework of Hadoop lies on the fact that using the necessary tools of both HBase and Hadoop FS we can know in which hadoop cluster node the requested B+ -tree nodes are stored and thus achieve fast results retrieval in a range query. The structure of the project is as follows: The first chapter is an introduction to the concepts of distributed computing over distributed environments. The second is a reference to peer-to-peer networks (p2p) and more specifically the BATON overlay network, which has a tree structure similar to that of the B+ -tree, is analyzed. The third chapter deals with an indexation and answering implementation on range queries in the Computer Cloud using B+ -tree basic data structures. Also, ART Autonomous Range Tree structure is presented which can support range queries in such large-scale decentralized environments and can scale in terms of the number of nodes as well as in terms of the data items stored. ART outperforms the most popular decentralized structures, including Chord (and some of its successors), BATON (and its successor) and Skip-Graphs. In the fourth and fifth chapter respectively a reference is made to the main points of Hadoop Framework and HBase architecture and operation. The sixth chapter is the description of the implementation of this dissertation together with the algorithms and how they operate. The next chapter is the evaluation of the experimental results of this dissertation and of the conclusions that derive from the evaluation. Finally, the eighth and last chapter is an overview of the dissertation, mentioning its basic parts, as well as possible extensions that would improve the system performance.

Η διπλωματική εργασία διαπραγματεύεται την εφαρμοσιμότητα του peer-to-peer υπολογισμού και τεχνικών στα ασύρματα κινητά ad-hoc δίκτυα και στα δίκτυα αισθητήρων. Παρουσιάζεται μια παραλλαγή ενός νέου P2P πρωτοκόλλου (Energy Level Distributed Tree) που σαν κύρια λειτουργία του έχει την αύξηση του προσδόκιμου λειτουργίας ενός δικτύου αισθητήρων. Επίσης, γίνεται αναφορά στα πιο δημοφιλή εργαλεία προσομοίωσης για P2P πρωτόκολλα δρομολόγησης και παρουσιάζεται ένα νέο εργαλείο, d-p2p-sim, με δυνατότητα προσομοίωσης εκατομμυρίων κόμβων. Τέλος, εξετάζουμε την απόδοση ενός νέου P2P πρωτοκόλλου δρομολόγησης, του Nested Balanced Distributed Tree, που απαντά με βέλτιστο τρόπο ερωτήμα ακριβούς ταιριάσματος και ερωτήματα διαστήματος παρουσιάζοντας παράλληλα δύο νέους αλγορίθμους αναζήτησης για αυτό. / In this master thesis we study the applicability of the peer-to-peer computing and techniques on wireless ad-hoc networks and sensor-nets. We propose a simplified mapping of an optimal P2P protocol (NBDT) onto sensor-nets, the so called Energy Level Distributed Tree (ELDT), which has one main operation: the life expectancy of a sensor-net. Furthermore, are examined the most popular Peer-to-Peer simulators and is presented a new distributed simulator for P2P routing algorithms. The key feature of the proposed simulator is the ability to simulate millions of peers. Finally, is presented a revised version of the NBDT protocol which is hot-spot free and achieves a better load distribution introducing a negligible routing overhead.