Τα Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) αποτελούν μία αρκετά πρόσφατη και πολλά υποσχόμενη νέα τεχνολογία που βρίσκει πληθώρα εφαρμογών. Λόγω της ευρύτατης εφαρμοσιμότητάς της και της προφανούς θέσης που βρίσκει στο σύγχρονο κατανεμημένο υπολογιστικό κόσμο, η επιστημονική τυπική θεμελίωση των νόμων που διέπουν αυτή τη νέα τεχνολογία καθίσταται απαραίτητη. Έτσι, έχουν προταθεί πολλά νέα υπολογιστικά μοντέλα για ΑΔΑ. Μία ειδική κατηγορία τέτοιων συστημάτων είναι τα Πρωτόκολλα Πληθυσμών (ΠΠ). Αυτά διέπονται από τρία ιδιαίτερα χαρακτηριστικά: Οι κόμβοι αίσθησης (πράκτορες) κινούνται παθητικά, δηλαδή δε μπορούν να ελέγξουν την κίνηση στην οποία υπόκεινται, η διαθέσιμη μνήμη κάθε κόμβου είναι πολύ περιορισμένη και οι πράκτορες αλληλεπιδρούν κατά ζεύγη. Έχει αποδειχθεί ότι ένα κατηγόρημα είναι υπολογίσιμο από το μοντέλο των ΠΠ εάν και μόνο εάν είναι ημιγραμμικό. Η κλάση των ημιγραμμικών κατηγορημάτων αποτελεί μία αρκετά μικρή κλάση. Στην παρούσα εργασία, βασικός μας στόχος είναι η επέκταση του μοντέλου των πρωτοκόλλων πληθυσμών με σκοπό το κέρδος σε υπολογιστική ισχύ. Πρώτα κάνουμε την παραδοχή ότι, πέρα των κόμβων αίσθησης, και οι ακμές του γραφήματος μπορούν να διατηρούν περιορισμένες καταστάσεις. Έτσι, σε ένα πλήρες γράφημα 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).

The localization of the sensor nodes is a fundamental issue in the area of wireless sensor networks (WSNs). An attractive way for estimating the location of mobile or static wireless objects is by using the received signal strength (RSS) attenuation with the distance, which does not require any additional hardware. This is possible due to the fact that in most sensor nodes radios the received signal strength indicator (RSSI) is a standard feature and can be obtained automatically by the received messages. On the other hand the RSS is known for being noisy, unstable, variable and difficult to use in practice. For achieving a better understanding of the nature of these difficulties and limitations, and for identifying the range of applicability of the RSS in localization and tracking scenarios, a thorough study about the RSS and its dependence on the various factors and environmental conditions is essential. The present doctoral dissertation investigates the feasibility of sensor node localization and target tracking with the resources of the WSN technology, when using only the RSS of the exchanged messages. Moreover, it offers experimental support to the hypothesis that proper modeling of the RSS behavior and appropriate selection of the topology parameters are essential for the applicability of WSN in real world conditions. In brief, the present doctoral dissertation concerns with: (i) identifying the main factors that influence the accuracy, the variability and the reliability of the obtained RSS, (ii) modeling the RF signal propagation in the context of WSNs, and (iii)defining the basic deployment constraints and evaluation of the topology parameters that can guarantee successful localization and tracking. For assessing the practical value of various RF-models, experiments using Tmote Sky and TelosB sensor nodes in real-field outdoor environment were carried out. The impact of a number of factors, such as the operating frequency of the radio, the transmitter–receiver distance, the variation of transceivers hardware due to manufacturing tolerances, the antenna orientation, and the environmental conditions, on the RSS was investigated. The influence of the various factors that affect the RF signal propagation and some constraints imposed by the WSN nature was accounted in order to design practical models, suitable for outdoor unobstructed and outdoor tree-obstructed environments. A pre-deployment simulation framework has been introduced and in its context a RF signal propagation-based connectivity strategy (RFCS) has been developed to fulfill three deployment provisions: (i) discovering the most appropriate height from the ground and distances for the sensor nodes, (ii) reducing the transmission power, and (iii) minimizing the interference from non-neighbor nodes. The RFCS uses a RF signal propagation model to predict the RSS in order to identify the most appropriate communication-based deployment parameters, i.e. T-R distance, height from the ground and transmission power. The localization and tracking considerations, by means of localization and tracking techniques, topology parameters and factors influencing the localization and tracking accuracy, are combined in illustrative simulation examples to evaluate their significance concerning the performance of the localization and tracking task. Furthermore, the propagation model and the topology parameters being identified were validated in real outdoor sensor node localization and target tracking tests. / -

Η διπλωματική εργασία διαπραγματεύεται την εφαρμοσιμότητα του 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.

Τα ασύρματα δίκτυα αισθητήρων αποτελούν μία πρωτοποριακή τεχνολογία που ήρθε στο προσκήνιο πριν από μία περίπου δεκαετία. Η καινοτομία της τεχνολογίας αυτής έγκειται στη συνεργασία μεγάλου αριθμού κόμβων περιορισμένων πόρων χαμηλής κατανάλωσης ισχύος σε μία μόνο εφαρμογή. Η εργασία αυτή ασχολείται με θέματα ενδιάμεσου λογισμικού σε ασύρματα δίκτυα αισθητήρων. Συγκεκριμένα, μελετάται το πρωτόκολλο Deluge που αποτελεί τη βασική επιλογή για ασύρματο προγραμματισμό δικτύων αισθητήρων που «τρέχουν» το λειτουργικό σύστημα πραγματικού χρόνου TinyOS. Παρέχοντας έναν αξιόπιστο και αποδοτικό μηχανισμό διάδοσης δεδομένων μέσω της δυαδικής εικόνας του κώδικα, το Deluge κατέχει ρόλο-κλειδί στη βαθμίδα ενδιάμεσου λογισμικού των ασύρματων δικτύων αισθητήρων. Η μελέτη και κατανόηση του πρωτοκόλλου αυτού επέτρεψε την υλοποίηση σε nesC ενός απλούστερου πρωτοκόλλου που αξιοποιεί τα βασικά χαρακτηριστικά του μηχανισμού μετάδοσης δεδομένων του Deluge. Σε συνέχεια αυτής της υλοποίησης, αξιολογήθηκε εκ νέου η διαδικασία μετάδοσης πραγματοποιώντας δοκιμές τόσο σε πραγματικές τοπολογίες κόμβων αισθητήρων (motes) που υποστηρίζουν το πρότυπο ασύρματης επικοινωνίας IEEE 802.15.4 όσο και σε περιβάλλον προσομοίωσης (TOSSIM). Τα προκύπτοντα αποτελέσματα επιβεβαιώνουν την αποδοτική μετάδοση δεδομένων σε δίκτυα αισθητήρων αξιοποιώντας το πρωτόκολλο Deluge. Η παρούσα εργασία αποτελείται από έξι κεφάλαια. Το πρώτο κεφάλαιο παρέχει πληροφορίες για το γνωστικό αντικείμενο της εργασίας. Στο δεύτερο κεφάλαιο παρουσιάζεται μία μελέτη στην ερευνητική περιοχή των ασύρματων δικτύων αισθητήρων και στο τρίτο κεφάλαιο εξετάζονται τα βασικά χαρακτηριστικά ενός κόμβου αισθητήρων που υποστηρίζει το πρότυπο IEEE 802.15.4. Στο τέταρτο κεφάλαιο παρουσιάζεται η έννοια του ασύρματου προγραμματισμού στα δίκτυα αισθητήρων και μελετάται εκτενώς το πρωτόκολλο Deluge. Στο πέμπτο κεφάλαιο περιγράφεται η υλοποίηση που έλαβε χώρα και η αξιολόγηση αυτής με τους μηχανισμούς που αναφέρθηκαν παραπάνω. Τέλος, στο έκτο κεφάλαιο παρατίθενται τα συμπεράσματα που εξήχθησαν από την εκπόνηση της εν λόγω εργασίας και δίνονται ορισμένες κατευθύνσεις για μελλοντική ενασχόληση με το Deluge και με το ενδιάμεσο λογισμικό στα δίκτυα αισθητήρων γενικότερα. / Wireless sensor networks (WSNs) emerged about a decade ago, representing a new class of computing with large numbers of resource-constrained computing nodes cooperating on a single application. This thesis deals with middleware issues in wireless sensor networks. Specifically, we study Deluge that suggests the de facto over-the-air programming protocol for WSNs working under TinyOS. Providing a reliable and efficient data dissemination mechanism via the binary image of the program code, Deluge plays a key role in the middleware layer of WSNs. Gaining insight into Deluge, we implemented in the nesC programming language a simplified protocol that incorporates the main features of Deluge data dissemination mechanism. This implementation allowed us to evaluate further the propagation procedure of Deluge using a two-mechanism evaluation framework. Carrying out experiments both in real-world deployments being compatible with IEEE 802.15.4 radio and in a simulation environment (TOSSIM), we verified the efficient data propagation in WSNs, using Deluge. This dissertation follows a structure of six chapters. In the first chapter, we give a piece of information about the subject field of this thesis. In the second chapter, we present an overall survey of the research area of WSNs and in the third chapter we examine the basic features of a sensor node (mote) whose wireless communication is based on an IEEE 802.15.4 compliant radio. In the fourth chapter, we discuss network programming in WSNs and we analyze the data dissemination mechanism of Deluge. In the fifth chapter, we discuss our implementation and its evaluation. Finally, in the sixth chapter, we conclude the thesis emphasizing the experience derived from that and we give some directions for future work with Deluge and middleware in WSNs generally.