Le modèle de dimères, également connu sous le nom de modèle de couplage parfait, est un modèle probabiliste introduit à l'origine dans la mécanique statistique. Une configuration de dimères d'un graphe est un sous-ensemble des arêtes tel que chaque sommet est incident à exactement une arête. Un poids est attribué à chaque arête et la probabilité d'une configuration est proportionnelle au produit des poids des arêtes présentes. Dans cette thèse, nous étudions principalement deux modèles qui sont liés au modèle de dimères, et plus particulièrement leur comportements limites. Le premier est le modèle des forêts couvrantes enracinées sur des cycles (CRSF) sur le tore, qui sont en bijection avec les configurations de dimères via la bijection de Temperley. Dans la limite quand la taille du tore tend vers l'infini, la mesure sur les CRSF converge vers une mesure de Gibbs ergodique sur le plan tout entier. Nous étudions la connectivité de l'objet limite, prouvons qu'elle est déterminée par le changement de hauteur moyen de la mesure de Gibbs ergodique et donnons un diagramme de phase. Le second est le modèle de perles, un processus ponctuel sur $\mathbb{Z}\times\mathbb{R}$ qui peut être considéré comme une limite à l'échelle du modèle de dimères sur un réseau hexagonal. Nous formulons et prouvons un principe variationnel similaire à celui du modèle dimère \cite{CKP01}, qui indique qu'à la limite de l'échelle, la fonction de hauteur normalisée d'une configuration de perles converge en probabilité vers une surface $h_0$ qui maximise une certaine fonctionnelle qui s'appelle "entropie". Nous prouvons également que la forme limite $h_0$ est une limite de l'échelle des formes limites de modèles de dimères. Il existe une correspondance entre configurations de perles et (skew) tableaux de Young standard, qui préserve la mesure uniforme sur les deux ensembles. Le principe variationnel du modèle de perles implique une forme limite d'un tableau de Young standard aléatoire. Ce résultat généralise celui de \cite{PR}. Nous dérivons également l'existence d'une courbe arctique d'un processus ponctuel discret qui encode les tableaux standard, defini dans \cite{Rom}. / The dimer model, also known as the perfect matching model, is a probabilistic model originally introduced in statistical mechanics. A dimer configuration of a graph is a subset of the edges such that every vertex is incident to exactly one edge of the subset. A weight is assigned to every edge, and the probability of a configuration is proportional to the product of the weights of the edges present. In this thesis we mainly study two related models and in particular their limiting behavior. The first one is the model of cycle-rooted-spanning-forests (CRSF) on tori, which is in bijection with toroidal dimer configurations via Temperley's bijection. This gives rise to a measure on CRSF. In the limit that the size of torus tends to infinity, the CRSF measure tends to an ergodic Gibbs measure on the whole plane. We study the connectivity property of the limiting object, prove that it is determined by the average height change of the limiting ergodic Gibbs measure and give a phase diagram. The second one is the bead model, a random point field on $\mathbb{Z}\times\mathbb{R}$ which can be viewed as a scaling limit of dimer model on a hexagon lattice. We formulate and prove a variational principle similar to that of the dimer model \cite{CKP01}, which states that in the scaling limit, the normalized height function of a uniformly chosen random bead configuration lies in an arbitrarily small neighborhood of a surface $h_0$ that maximizes some functional which we call as entropy. We also prove that the limit shape $h_0$ is a scaling limit of the limit shapes of a properly chosen sequence of dimer models. There is a map form bead configurations to standard tableaux of a (skew) Young diagram, and the map is measure preserving if both sides take uniform measures. The variational principle of the bead model yields the existence of the limit shape of a random standard Young tableau, which generalizes the result of \cite{PR}. We derive also the existence of an arctic curve of a discrete point process that encodes the standard tableaux, raised in \cite{Rom}.

Dans cette thèse, on s'intéresse à des algorithmes d'analyse de données utilisant des marches aléatoires sur des graphes de voisinage, ou graphes géométriques aléatoires, construits à partir des données. On sait que les marches aléatoires sur ces graphes sont des approximations d'objets continus appelés processus de diffusion. Dans un premier temps, nous utilisons ce résultat pour proposer un nouvel algorithme de partitionnement de données flou de type recherche de modes. Dans cet algorithme, on définit les paquets en utilisant les propriétés d'un certain processus de diffusion que l'on approche par une marche aléatoire sur un graphe de voisinage. Après avoir prouvé la convergence de notre algorithme, nous étudions ses performances empiriques sur plusieurs jeux de données. Nous nous intéressons ensuite à la convergence des mesures stationnaires des marches aléatoires sur des graphes géométriques aléatoires vers la mesure stationnaire du processus de diffusion limite. En utilisant une approche basée sur la méthode de Stein, nous arrivons à quantifier cette convergence. Notre résultat s'applique en fait dans un cadre plus général que les marches aléatoires sur les graphes de voisinage et nous l'utilisons pour prouver d'autres résultats : par exemple, nous arrivons à obtenir des vitesses de convergence pour le théorème central limite. Dans la dernière partie de cette thèse, nous utilisons un concept de topologie algébrique appelé homologie persistante afin d'améliorer l'étape de "pooling" dans l'approche "sac-de-mots" pour la reconnaissance de formes 3D. / In this thesis, we study data analysis algorithms using random walks on neighborhood graphs, or random geometric graphs. It is known random walks on such graphs approximate continuous objects called diffusion processes. In the first part of this thesis, we use this approximation result to propose a new soft clustering algorithm based on the mode seeking framework. For our algorithm, we want to define clusters using the properties of a diffusion process. Since we do not have access to this continuous process, our algorithm uses a random walk on a random geometric graph instead. After proving the consistency of our algorithm, we evaluate its efficiency on both real and synthetic data. We then deal tackle the issue of the convergence of invariant measures of random walks on random geometric graphs. As these random walks converge to a diffusion process, we can expect their invariant measures to converge to the invariant measure of this diffusion process. Using an approach based on Stein's method, we manage to obtain quantitfy this convergence. Moreover, the method we use is more general and can be used to obtain other results such as convergence rates for the Central Limit Theorem. In the last part of this thesis, we use the concept of persistent homology, a concept of algebraic topology, to improve the pooling step of the bag-of-words approach for 3D shapes.

L’émergence récente de grands réseaux, surtout réseaux sociaux en ligne (OSN), a révélé la difficulté de crawler le réseau complet et a déclenché le développement de nouvelles techniques distribuées. Dans cette thèse, nous concevons et analysons des algorithmes basés sur les marches aléatoires et la diffusion pour l'échantillonnage, l'estimation et l'inférence des fonctions des réseaux. La thèse commence par le problème classique de trouver les valeurs propres dominants et leurs vecteurs propres de matrices de graphe symétriques, comme la matrice Laplacienne de graphes non orientés. En utilisant le fait que le spectre est associé à une équation de type différentiel Schrödinger, nous développons des techniques évolutives à l’aide de la diffusion sur le graphe. Ensuite, nous considérons l’échantillonnage des fonctions de réseau (comme somme et moyenne) en utilisant les marches aléatoires sur le graphe. Afin d'éviter le temps «burn-in» de marche aléatoire, avec l'idée de régénération à un nœud fixe, nous développons un estimateur de la fonction de somme qui est non asymptotiquement non-biaisé et dérivons une approximation à la postérieure Bayésienne. La dernière partie de la thèse étudie l'application de la théorie des valeurs extrêmes pour faire une inférence sur les événements extrêmes à partir des échantillons stationnaires des différentes marches aléatoires pour l’échantillonnage de réseau / The recent emergence of large networks, mainly due to the rise of online social networks, brought out the difficulty to gather a complete picture of a network and it prompted the development of new distributed techniques. In this thesis, we design and analyze algorithms based on random walks and diffusion for sampling, estimation and inference of the network functions, and for approximating the spectrum of graph matrices. The thesis starts with the classical problem of finding the dominant eigenvalues and the eigenvectors of symmetric graph matrices like Laplacian of undirected graphs. Using the fact that the eigenspectrum is associated with a Schrödinger-type differential equation, we develop scalable techniques with diffusion over the graph and with gossiping algorithms. They are also adaptable to a simple algorithm based on quantum computing. Next, we consider sampling and estimation of network functions (sum and average) using random walks on graph. In order to avoid the burn-in time of random walks, with the idea of regeneration at its revisits to a fixed node, we develop an estimator for the aggregate function which is non-asymptotically unbiased and derive an approximation to its Bayesian posterior. An estimator based on reinforcement learning is also developed making use of regeneration. The final part of the thesis deals with the use of extreme value theory to make inference from the stationary samples of the random walks. Extremal events such as first hitting time of a large degree node, order statistics and mean cluster size are well captured in the parameter “extremal index”. We theoretically study and estimate extremal index of different random walk sampling techniques

Nous nous penchons sur les fluctuations des marches dans plusieurs modèles de marches aléatoires en milieux aléatoires. En particulier, le résultat principal de ce mémoire est de prouver qu'il existe un théorème central limite trempé pour la marche aléatoire sur un arbre de Galton-Watson infini avec feuilles équipé de biais aléatoires plus grand que 1. Un tel théorème a été prouvé dans le cas où le biais est constant dans [1]; il s'agit donc de généraliser ce théorème. / We examine the fluctuations of walks in multiple models of random walks in random environments. In particular, the primary result of this dissertation is to prove there exists a quenched central limit theorem for the random on an infinite Galton-Watson tree with leaves equiped with random biases greater than 1. Such a theorem has already been proven in the case where the bias is constant in [1]; this is a generalization of that theorem.

Menschliche Systeme werden seit einiger Zeit modelliert und analysiert auf der Basis der Theorie komplexer Netzwerke. Dies erlaubt es quantitativ zu untersuchen, welche strukturellen und zeitlichen Merkmale eines Systems Ausbreitungsprozesse beeinflussen, z.B. von Informationen oder von Infektionskrankheiten. Im ersten Teil der Arbeit wird untersucht, wie eine modular-hierarchische Struktur von statischen Netzwerken eine schnelle Verbreitung von Signalen ermöglicht. Es werden neue Heuristiken entwickelt um die Random-Walk-Observablen “First Passage Time” und “Cover Time” auf lokal geclusterten Netzwerken zu ermitteln. Vergleiche mit der Approximation eines gemittelten Mediums zeigen, dass das Auftreten der beobachteten Minima der Observablen ein reiner Netzwerkeffekt ist. Es wird weiterhin dargelegt, dass nicht alle modular-hierarchischen Netzwerkmodelle dieses Phänomen aufweisen. Im zweiten Teil werden zeitlich veränderliche face-to-face Kontaktnetzwerke auf ihre Anfälligkeit für Infektionskrankheiten untersucht. Mehrere Studien belegen, dass Menschen vornehmlich Zeit in Isolation oder kleinen, stark verbundenen Gruppen verbringen, und dass ihre Kontaktaktivität einem zirkadianen Rhythmus folgt. Inwieweit diese beiden Merkmale die Ausbreitung von Krankheiten beeinflussen, ist noch unklar. Basierend auf einem neuen Modell wird erstmals gezeigt, dass zirkadian variierende Netzwerke Trajektorien folgen in einem Zustandsraum mit einer strukturellen und einer zeitlichen Dimension. Weiterhin wird dargelegt, dass mit zunehmender Annäherung der zeitlichen Dimension von System und Krankheit die systemische Infektionsanfälligkeit sinkt. Dies steht in direktem Widerspruch zu Ergebnissen anderer Studien, die eine zunehmende Anfälligkeit vorhersagen, eine Diskrepanz, die auf die Ungültigkeit einer weit verbreiteten Approximation zurückzuführen ist. Die hier vorgestellten Ergebnisse implizieren, dass auf dem Gebiet die Entwicklung neuer theoretischer Methoden notwendig ist. / Human systems have been modeled and analyzed on the basis of complex networks theory in recent time. This abstraction allows for thorough quantitative analyses to investigate which structural and temporal features of a system influence the evolution of spreading processes, such as the passage of information or of infectious diseases. The first part of this work investigates how the ubiquitous modular hierarchical structure of static real-world networks allows for fast delivery of messages. New heuristics are developed to evaluate random walk mean first passage times and cover times on locally clustered networks. A comparison to average medium approximations shows that the emergence of these minima are pure network phenomena. It is further found that not all modular hierarchical network models provide optimal message delivery structure. In the second part, temporally varying face-to-face contact networks are investigated for their susceptibility to infection. Several studies have shown that people tend to spend time in small, densely-connected groups or in isolation, and that their connection behavior follows a circadian rhythm. To what extent both of these features influence the spread of diseases is as yet unclear. Therefore, a new temporal network model is devised here. Based on this model, circadially varying networks can for the first time be interpreted as following trajectories through a newly defined systemic state space. It is further revealed that in many temporally varying networks the system becomes less susceptible to infection when the time-scale of the disease approaches the time-scale of the network variation. This is in direct conflict with findings of other studies that predict increasing susceptibility of temporal networks, a discrepancy which is attributed to the invalidity of a widely applied approximation. The results presented here imply that new theoretical advances are necessary to study the spread of diseases in temporally varying networks.

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

Τα Δίκτυα Αισθητήρων αποτελούνται από ένα μεγάλο αριθμό μικρών αυτόνομων συσκευών, που αλληλεπιδρούν με το άμεσο περιβάλλον τους μέσω αισθητήρων, συλλέγουν δεδομένα και τα προωθούν προς ένας σταθερό, συνήθως, κέντρο ελέγχου, με αναμεταδόσεις στους ενδιάμεσους κόμβους. Η διαδικασία αυτή έχει ως αποτέλεσμα τη μεγάλη κατανάλωση ενέργειας στις συσκευές, ιδιαίτερα σε αυτές που βρίσκονται κοντά στο κέντρο ελέγχου, αφού πρέπει να αναμεταδίδουν και τα δεδομένα που φτάνουν από το υπόλοιπο δίκτυο προς το κέντρο ελέγχου. Για την επίτευξη μιας πιο ισορροπημένης και αποδοτικής διαδικασίας συλλογής δεδομένων, τα τελευταία χρόνια έχει υιοθετηθεί μια νέα προσέγγιση, όπου το κέντρο ελέγχου είναι κινητό. Η βασική ιδέα είναι ότι το κέντρο ελέγχου διαθέτει σημαντικά και εύκολα ανανεώσιμα αποθέματα ενέργειας, επομένως μπορεί να κινείται στην περιοχή όπου έχει αναπτυχθεί το δίκτυο αισθητήρων, αναλαμβάνοντας να συλλέξει τα δεδομένα από τους κόμβους με πολύ μικρό κόστος. Ωστόσο, η μετάδοση των δεδομένων μπορεί να παρουσιάζει σημαντικές καθυστερήσεις. Συλλογή δεδομένων με προσαρμοστικούς χρόνους αναμονής: Στην παρούσα διατριβή αναπτύχθηκαν πρωτόκολλα ελέγχου της κίνησης ενός κέντρου ελέγχου σε δίκτυο αισθητήρων με ανομοιογενή ανάπτυξη των κόμβων αισθητήρων, με στόχο την αποδοτική, ως προς την ενέργεια και τον χρόνο παράδοσης, συλλογή των δεδομένων. Πιο συγκεκριμένα, αρχικά παρουσιάζεται ένα πρωτόκολλο με βάση το οποίο το κέντρο ελέγχου διαιρεί νοητά το δίκτυο σε περιοχές τις οποίες και επισκέπτεται διαδοχικά, σταματώντας σε κάθε περιοχή για ένα συγκεκριμένο χρονικό διάστημα, ώστε να συλλέξει τα δεδομένα. Προτείνουμε δύο τρόπους κίνησης του κέντρου ελέγχου, ντετερμινιστικό και τυχαίο. Στην τυχαία κίνηση, η επιλογή της επόμενης περιοχής την οποία θα επισκεφτεί το κέντρο ελέγχου γίνεται με τυχαίο τρόπο, εισάγοντας όμως ένα όρο μεροληψίας, έτσι ώστε να προτιμούνται περιοχές που έχουν δεχτεί λιγότερες επισκέψεις. Επιπλέον η μέθοδός μας αποφασίζει το χρόνο παύσης σε κάθε περιοχή λαμβάνοντας υπόψιν κάποιες βασικές παραμέτρους του δικτύου, όπως τα αρχικά αποθέματα ενέργειας των κόμβων αισθητήρων και την πυκνότητα της κάθε περιοχής, έτσι ώστε να παραμένει περισσότερο χρόνο σε περιοχές με μεγαλύτερη πυκνότητα, άρα και μεγαλύτερη ποσότητα πληροφορίας. Με τον τρόπο αυτό επιτυγχάνεται η γρήγορη κάλυψη όλου του δικτύου, καθώς επίσης και η δίκαιη εξυπηρέτηση των επιμέρους περιοχών του δικτύου. Προσαρμοστικοί τυχαίοι περίπατοι Στη συνέχεια, μελετάται η χρήση τυχαίων περιπάτων κατά την κίνηση του κέντρου ελέγχου σε δίκτυα αισθητήρων με στόχο την επίτευξη ενός ικανοποιητικού σημείου ισορροπίας μεταξύ κατανάλωσης ενέργειας και καθυστέρησης στην παράδοση των μηνυμάτων. Για την ικανοποίηση του στόχου αυτού, προτείνουμε τρεις νέους τυχαίους περιπάτους, τους α) Τυχαίος Περίπατος με Αδράνεια, κατά τον οποίο το κινούμενο αντικείμενο τείνει να διατηρεί την ίδια κατεύθυνση στην κίνησή του όσο ανακαλύπτει κόμβους αισθητήρων που δεν έχει επισκεφτεί και αλλάζει την κατεύθυνσή του όταν φτάνει σε κόμβους που έχει ξαναεπισκεφτεί, β) Explore-and-Go, κατά τον οποίο το κινούμενο αντικείμενο τείνει να εκτελεί μια Brownian κίνηση γύρω από την περιοχή του όσο υπάρχουν κόμβοι που δεν έχουν δεχτεί επίσκεψη, γ) Curly Random Walk, όπου το κινούμενο αντικείμενο διαπερνάει όλη την περιοχή του δικτύου ξεκινώντας από το κέντρο και επεκτείνοντας την κίνησή του με συνεχόμενες κυκλικές κινήσεις προς τα έξω. Για την εφαρμογή των τυχαίων περιπάτων χρησιμοποιούμε ένα νοητό πλέγμα ώστε να καλύπτουμε την περιοχή του δικτύου αισθητήρων• οι περίπατοι κινούνται πάνω στους κόμβους του πλέγματος. Αν και στις περισσότερες περιπτώσεις οι τυχαίοι περίπατοι μελετώνται σε Gn,p και Grid γράφους, τα δίκτυα αισθητήρων μοντελοποιούνται με μεγαλύτερη ακρίβεια χρησιμοποιώντας το μοντέλο των Random Geometric Graphs (RGG), εφόσον έτσι αναπαρίσταται καλύτερα η χωρική εγγύτητα του δικτύου. Οι παραπάνω τυχαίοι περίπατοι δεν δίνουν τα επιθυμητά αποτελέσματα όταν τρέχουν σε RGG. Έτσι οδηγηθήκαμε στο σχεδιασμό ενός νέου τυχαίου περιπάτου, του γ-Stretched Random Walk, η βασική ιδέα του οποίου είναι να μεροληπτεί υπέρ της επίσκεψης των πιο μακρινών γειτόνων του τρέχοντος κόμβου έτσι ώστε να μειώσει στο ελάχιστο τις επικαλύψεις στις επισκέψεις. Αλγόριθμοι που λαμβάνουν υπόψιν την ηλεκτρομαγνητική ακτινοβολία στο δίκτυο: Εκτός από τη μελέτη της κίνησης του κέντρου ελέγχου σε δίκτυα αισθητήρων, στη διατριβή αυτή παρουσιάζεται μια πρώτη προσπάθεια μελέτης θεμάτων σχετικά με την επίγνωση της εκπομπή ακτινοβολίας σε περιβάλλοντα όπου λειτουργούν πολλαπλά ετερογενή ασύρματα δίκτυα. Ως ακτινοβολία σε ένα σημείου του τρισδιάστατου χώρου καλούμε τη συνολική ποσότητητα ηλεκτρομαγνητικής ακτινοβολίας που δέχεται το σημείο αυτό. Έτσι, καταρχάς μελετάμε σε αναλυτικό επίπεδο την ακτινοβολία σε διάφορες γνωστές τοπολογίες (τυχαίες, πλέγματα) και κατόπιν επικεντρώνουμε το ενδιαφέρον μας στην εύρεση ενός μονοπατιού ελάχιστης ακτινοβολίας το οποίο ακολουθείται από κάποιο άτομο που κινείται στην περιοχή που καλύπτεται από ένα ασύρματο δίκτυο αισθητήρων. Προτείνουμε τρεις ευρετικές μεθόδους για την εύρεση του μονοπατιού καθώς το άτομο κινείται, ενώ υπολογίζουμε και την οffline λύση χρησιμοποιώντας τον αλγόριθμο ελάχιστου μονοπατιού. Κατόπιν, εξετάζουμε το θεμελιώδες πρόβλημα της διάδοσης των δεδομένων σε ασύρματα δίκτυα αισθητήρων, προσπαθώντας τόσο να παραμείνει γρήγορη η διαδικασία παράδοσης των μηνυμάτων, παράλληλα όμως και η συνολική ηλεκτρομαγνητική ακτινοβολία που παράγεται από τις συνεχείς ασύρματες μεταδόσεις να διατηρηθεί σε χαμηλά επίπεδα. Αυτό επιτυγχάνεται αρχικά χρησιμοποιώντας κάποιες άπληστες ευρετικές μεθόδους που όμως λαμβάνουν υπόψιν την ακτινοβολία. Επιπλέον, οι μέθοδοι αυτοί συνδυάζονται με μεθόδους που πραγματοποιούν back-off στο χρόνο, χρησιμοποιώντας τοπικές ιδιότητες του δικτύου (όπως ο αριθμός γειτόνων, η απόσταση από το κέντρο ελέγχου), έτσι ώστε «απλωθεί» κατά κάποιο τρόπο η ακτινοβολία τόσο ως προς το χρόνο αλλά και ως προς το χώρο. Τα προτεινόμενα πρωτόκολλα αξιολογήθηκαν πειραματικά μέσω προσομοίωσης, χρησιμοποιώντας ποικίλες τιμές για βασικές παραμέτρους του δικτύου και σύγκρινοντάς τα με σχετικές υπάρχουσες ευρέως αποδεκτές μεθόδους. Συστημικές Εφαρμογές: Τέλος, στη διατριβή παρουσιάζονται κάποιες συστημικές εφαρμογές ασύρματων δικτύων αισθητήρων σε κτίρια. Συγκεκριμένα, η πρώτη εφαρμογή αναλαμβάνει σε περίπτωση ανίχνευσης φωτιάς, την εύρεση του ελάχιστου μονοπατιού μακριά από το σημείο όπου έγινε η ανίχνευση. Επιπλέον, παρέχει καθοδήγηση στους ενοίκους του κτιρίου (οι οποίοι μοντελοποιούνται από ένα κινούμενο ρομπότ) έτσι ώστε να εγκαταλείψουν με ασφάλεια το κτίριο. Η επόμενη εφαρμογή παρουσιάζει τη δυνατότητα της απρόσκοπτης διασύνδεσης αυτοματισμών έξυπνων κτιρίων, αποτελούμενων από ενσωματωμένα συστήματα, στο διαδίκτυο και την αφαιρετικοποίησή τους ως απλά web services. Η προσέγγιση αυτή έχει στόχο την δημιουργία ενός ευέλικτου, εύκολα κλιμακώσιμου συστήματος που είναι προσβάσιμο και ελεγχόμενο απομακρυσμένα. Η προσέγγιση που ακολουθήθηκε και παρουσιάζεται στην παρούσα διατριβή περιλαμβάνει την ανάπτυξη ενός αριθμού αισθητήρων μέσα σε ένα κτίριο, οι οποίοι αποκτούν IPv6 διεύθυνση ώστε να είναι προσβάσιμοι διαδικτυακά, ενώ παράλληλα διασυνδέονται με ηλεκτρικές συσκευές του κτιρίου για σχηματισμό αυτοματισμών. Τέλος αναπτύχθηκε μία web εφαρμογή για απομακρυσμένη διαχείριση του δικτύου και του κτιρίου γενικότερα. / Wireless Sensor Networks consist of a large number of small, autonomous devices, that are able to interact with their environment by sensing and collaborate to fulfill their tasks, as, usually, a single node is incapable of doing so; and they use wireless communication to enable this collaboration. The collected data is disseminated to a static control point – data sink in the network, using node to node - multi-hop data propagation. However, sensor devices consume significant amounts of energy in addition to increased implementation complexity, since a routing protocol is executed. Also, a point of failure emerges in the area near the control center where nodes relay the data from nodes that are farther away. Recently, a new approach has been developed that shifts the burden from the sensor nodes to the sink. The main idea is that the sink has significant and easily replenishable energy reserves and can move inside the area the sensor network is deployed, in order to acquire the data collected by the sensor nodes at very low energy cost. However, the need to visit all the regions of the network may result in large delivery delays. Data collection with biased stop times: In this work we have developed protocols that control the movement of the sink in wireless sensor networks with non-uniform deployment of the sensor nodes, in order to succeed an efficient (with respect to both energy and latency) data collection. More specifically, we first propose a protocol, where the sink partitions the network area in equal square regions and then performs a network traversal by visiting each area sequentially. Also, it pauses in each area for a certain amount of time, in order to collect the data. Two network traversal methods are proposed, a deterministic and a random one. When the sink moves in a random manner, the selection of the next area to visit is done in a biased random manner depending on the frequency of visits of its neighbor areas. Thus, less frequently visited areas are favored. Moreover, our method locally determines the stop time needed to serve each region with respect to some global network resources, such as the initial energy reserves of the nodes and the density of the region, stopping for a greater time interval at regions with higher density, and hence more traffic load. In this way, we achieve accelerated coverage of the network as well as fairness in the service time of each region. Besides randomized mobility, we also propose an optimized deterministic trajectory without visit overlaps, including direct (one-hop) sensor-to-sink data transmissions only. Adaptive random walks: Afterwards, in order to achieve satisfactory energy-latency trade-offs the use of random walks for the sink' s motion pattern is studied. Towards this direction three new random walks evaluated on a grid overlaying the wireless sensor network are proposed. The first one is the Random Walk with Inertia where the sink tends to keep the same direction as long as it discovers new nodes, while changing direction when it encounters already visited ones. The second one is the Explore-and-Go Random Walk, where as long as there are undiscovered nodes on the nearby sub-regions of the network it tends to make a Brownian-like motion until all this area is covered. When no new sensors are discovered, it performs a more or less straight-line walk in order to move to a different, possibly unvisited area. The last one is the Curly Random Walk where the sink traverses the network area beginning from the center and expanding its traversal to the entire network area with consecutive circular-like moves. In random walk studies the Gn,p and Grid graph models are well established. However, wireless sensor networks are more accurately modeled via Random Geometric Graphs (RGG), as RGG better capture certain characteristics of WSN's such as link existence dependencies of neighbouring nodes due to geometric proximity. The above mentioned random walks do not behave well on this particular graph model, thus a new random walk was defined, the so called γ-stretched random walk. Its basic idea is to favour visiting distant neighbours of the current node towards reducing node overlap. Radiation-aware algorithms: Except for the issue of mobility in wireless sensor networks, in this work we also attempt (probably for the first time from a distributed networking perspective) to investigate the aspect of electromagnetic radiation in modern and future heterogeneous wireless networks. We call “radiation” at a target elementary surface the total amount of electromagnetic quantity (in terms of energy or power density) it is exposed to. Thus, we first evaluate, both mathematically and by simulation, the radiation in well known sensor network topologies (random, grid) and then focus on the minimum radiation path problem of finding low radiation trajectories for a person moving in a sensor network. We propose three online heuristics and then we identify the (offline) optimum path given by the shortest paths' algorithm. Afterwards, we focus on the fundamental problem of efficient data propagation in wireless sensor networks, trying to keep latency low while maintaining at low levels the radiation cumulated by wireless transmissions. We first propose greedy and oblivious routing heuristics that are radiation aware. We then combine them with temporal back-off schemes that use local properties of the network (e.g. number of neighbours, distance from sink) in order to “spread” radiation in a spatio-temporal way. Al the proposed protocols were evaluated via simulation, in diverse network settings and comparatively to related state of the art solutions. Systems and applications: Finally, in this work we present two applications of wireless sensor networks in buildings. More specifically, the first application, in the event of a fire inside a monitored building, uses the information from the deployed sensor network in order to find the shortest safest path away from the emergency and provides navigation guidance to the occupants (modelled by a mobile robot), in order to safely evacuate the building. The second application addresses networked embedded systems enabling the seamless interconnection of smart building automations to the Internet and their abstractions as web services, using the latest technologies based on IPv6, such as 6LOWPAN, COAP and RESTLess Architecture.

Le système immunitaire adaptatif est capable de produire une réponse spécifique contre presque tous le pathogènes qui agressent notre organisme. Ceci est dû aux anticorps qui sont des protéines secrétées par les cellules B. Les molécules qui provoquent cette réaction sont appelées antigènes : pendant une réponse immunitaire, les cellules B sont soumises à un processus d’apprentissage afin d’améliorer leur capacité à reconnaitre un antigène donne. Ce processus est appelé maturation d’affinité des anticorps. Nous établissons un cadre mathématique très flexible dans lequel nous définissons et étudions des modelés évolutionnaires simplifies inspirés par la maturation d’affinité des anticorps. Nous identifions les éléments constitutifs fondamentaux de ce mécanisme d’évolution extrêmement rapide et efficace : mutation, division et sélection. En commençant par une analyse rigoureuse du mécanisme de mutation dans le Chapitre 2, nous procédons à l’enrichissement progressif du modelé en ajoutant et analysant le processus de division dans le Chapitre 3 ,puis des pressions sélectives dépendantes de l’affinité dans le Chapitre 4. Notre objectif n’est pas de construire un modèle mathématique très détaillé et exhaustif de la maturation d’affinité des anticorps, mais plutôt d’enquêter sur les interactions entre mutation, division et sélection dans un contexte théorique simplifie. On cherche à comprendre comment les différents paramètres biologiques influencent la fonctionnalité du système, ainsi qu’à estimer les temps caractéristiques de l’exploration de l’espace d’états des traits des cellules B. Au-delà des motivations biologiques de la modélisation de la maturation d’affinité des anticorps, l’analyse de ce processus d’apprentissage nous a amenée à concevoir un modèle mathématique qui peut également s’appliquer à d’autres systèmes d’évolution, mais aussi à l’étude de la propagation de rumeurs ou de virus. Notre travail théorique s’accompagne de nombreuses simulations numériques qui viennent soit l’illustrer soit montrer que certains résultats demeurent extensibles a des situations plus compliquées. / The adaptive immune system is able to produce a specific response against almost any pathogen that could penetrate our organism and inflict diseases. This task is assured by the production of antigen-specific antibodies secreted by B-cells. The agents which causes this reaction are called antigens: during an immune response B-cells are submitted to a learning process in order to improve their ability to recognize the immunizing antigen. This process is called antibody affinity maturation. We set a highly flexible mathematical environment in which we define and study simplified mathematical evolutionary models inspired by antibody affinity maturation. We identify the fundamental building blocks of this extremely efficient and rapid evolutionary mechanism: mutation, division and selection. Starting by a rigorous analysis of the mutational mechanism in Chapter 2, we proceed by successively enriching the model by adding and analyzing the division process in Chapter 3 and affinity-dependent selection pressures in Chapter 4. Our aim is not to build a very detailed and comprehensive mathematical model of antibody affinity maturation, but rather to investigate interactions between mutation, division and selection in a simplified theoretical context. We want to understand how the different biological parameters affect the system’s functionality, as well as estimate the typical time-scales of the exploration of the state-space of B-cell traits. Beyond the biological motivations of antibody affinity maturation modeling, the analysis of this learning process leads us to build a mathematical model which could be relevant to model other evolutionary systems, but also gossip or virus propagation. Our method is based on the complementarity between probabilistic tools and numerical simulations.

Made available in DSpace on 2015-03-04T18:51:17Z (GMT). No. of bitstreams: 1 dissertacao_raqueline.pdf: 1022175 bytes, checksum: 12f505a41f92171e321e1b57c568631a (MD5) Previous issue date: 2010-03-05 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / In Computer Science, random walks are used in randomized algorithms, specially in search algorithms, where we desire to find a marked state in a Markov chain.In this type of algorithm,it is interesting to study the Hitting Time, which is associated to its computational complexity. In this context, we describe the classical theory of Markov chains and random walks,as well as their quantum analogue.In this way,we define the Hitting Time under the scope of quantum Markov chains. Moreover, analytical expressions calculated for the quantum Hitting Time and for the probability of finding a marked element on the complete graph are presented as the new results of this dissertation. / Em Ciência da Computação, os caminhos aleatórios são utilizados em algoritmos randômicos, especialmente em algoritmos de busca, quando desejamos encontrar um estado marcado numa cadeia de Markov. Nesse tipo de algoritmo é interessante estudar o Tempo de Alcance, que está associado a sua complexidade computacional. Nesse contexto, descrevemos a teoria clássica de cadeias de Markov e caminhos aleatórios, assim como o seu análogo quântico. Dessa forma, definimos o Tempo de Alcance sob o escopo das cadeias de Markov quânticas. Além disso, expressões analíticas calculadas para o tempo de Alcance quântico e para a probabilidade de encontrarmos um elemento marcado num grafo completo são apresentadas como os novos resultados dessa dissertação.

Seja $\\mathcal X=\\{\\mathcal X_t:\\, t\\geq0,\\, \\mathcal X_0=0\\}$ um passeio aleatório $\\beta$-estável em $\\mathbb Z$ com média zero e com taxas de saltos não-homogêneas $\\{\\tau_i^: i\\in\\mathbb Z\\}$, com $\\beta\\in(1,2]$ e $\\{\\tau_i: i\\in\\mathbb Z\\}$ sendo uma família de variáveis aleatórias independentes com distribuição marginal comum na bacia de atração de uma lei $\\alpha$-estável, com $\\alpha\\in(0,2]$. Nesta tese, obtemos resultados sobre o comportamento do processo $\\mathcal X_t$ para tempos longos, em particular, obtemos seu limite de escala. Quando $\\alpha\\in(0,1)$, o limite de escala é um processo $\\beta$-estável mudado de tempo pela inversa de um outro processo, o qual envolve o tempo local do processo $\\beta$-estável e um independente subordinador $\\alpha$-estável; chamamos o processo resultante de processo quase-estável. Para o caso $\\alpha\\in[1,2]$, o limite de escala é um ordinário processo $\\beta$-estável. Para $\\beta=2$ e $\\alpha\\in(0,1)$, o limite de escala é uma quase-difusão com medida de velocidade aleatória estudada por Fontes, Isopi e Newman (2002). Outros resultados sobre o comportamento de $\\mathcal X$ para tempos longos são envelhecimento e localização. Nós obtemos resultados de envelhecimento integrado e não-integrado para $\\mathcal X$ quando $\\alpha\\in(0,1)$. Relacionado à esses resultados, e possivelmente de interesse independente, consideramos o processo de armadilha definido por $\\{\\tau_{\\mathcal X_t}: t\\geq0\\}$, e obtemos seu limite de escala. Concluímos a tese com resultados sobre localização de $\\mathcal X$. Mostramos que ele pode ser localizado quando $\\alpha\\in(0,1)$, e que não pode ser localizado quando $\\alpha\\in(1,2]$, assim estendendo os resultados de Fontes, Isopi e Newman (1999) para o caso de passeios simples simétricos. / Let $\\mathcal X=\\{\\mathcal X_t:\\, t\\geq0,\\, \\mathcal X_0=0\\}$ be a mean zero $\\beta$-stable random walk on $\\mathbb Z$ with inhomogeneous jump rates $\\{\\tau_i^: i\\in\\mathbb Z\\}$, with $\\beta\\in(1,2]$ and $\\{\\tau_i: i\\in\\mathbb Z\\}$ is a family of independent random variables with common marginal distribution in the basin of attraction of an $\\alpha$-stable law with $\\alpha\\in(0,2]$. In this thesis we derive results about the long time behavior of this process, in particular its scaling limit. When $\\alpha\\in(0,1)$, the scaling limit is a $\\beta$-stable process time-changed by the inverse of another process, involving the local time of the $\\beta$-stable process and an independent $\\alpha$-stable subordinator; the resulting process may be called a quasistable process. For the case $\\alpha\\in[1,2]$, the scaling limit is an ordinary $\\beta$-stable process. For $\\beta=2$ and $\\alpha\\in(0,1)$, the scaling limit is a quasidiffusion with random speed measure studied by Fontes, Isopi and Newman (2002). Other results about the long time behavior of $\\mathcal X$ concern aging and localization. We obtain integrated and non integrated aging results for $\\mathcal X$ when $\\alpha\\in(0,1)$. Related to these results, and possibly of independent interest, we consider the trap process defined as $\\{\\tau_{\\mathcal X_t}: t\\geq0\\}$, and derive its scaling limit. We conclude the thesis with results about localization of $\\mathcal X$. We show that it localizes when $\\alpha\\in(0,1)$, and does not localize when $\\alpha\\in(1,2]$, extending results of Fontes, Isopi and Newman (1999) for the simple symmetric case.