Multi-agent systems rely heavily on coordination and cooperation to achieve a variety of tasks. It is often assumed that these agents will be fully cooperative, or have reliable and equal performance among group members. Instead, we consider cooperation as a spectrum of possible interactions, ranging from performance variations within the group to adversarial agents. This thesis examines several scenarios where cooperation and performance are not guaranteed. Potential applications include sensor coverage, emergency response, wildlife management, tracking, and surveillance. We use geometric methods, such as Voronoi tessellations, for design insight and Lyapunov-based stability theory to analyze our proposed controllers. Performance is verified through simulations and experiments on a variety of ground and aerial robotic platforms. First, we consider the problem of Voronoi-based coverage control, where a group of robots must spread out over an environment to provide coverage. Our approach adapts online to sensing and actuation performance variations with the group. The robots have no prior knowledge of their relative performance, and in a distributed fashion, compensate by assigning weaker robots a smaller portion of the environment. Next, we consider the problem of multi-agent herding, akin to shepherding. Here, a group of dog-like robots must drive a herd of non-cooperative sheep-like agents around the environment. Our key insight in designing the control laws for the herders is to enforce geometrical relationships that allow for the combined system dynamics to reduce to a single nonholonomic vehicle. We also investigate the cooperative pursuit of an evader by a group of quadrotors in an environment with no-fly zones. While the pursuers cannot enter the no-fly zones, the evader moves freely through the zones to avoid capture. Using tools for Voronoi-based coverage control, we provide an algorithm to distribute the pursuers around the zone's boundary and minimize capture time once the evader emerges. Finally, we present an algorithm for the guaranteed capture of multiple evaders by one or more pursuers in a bounded, convex environment. The pursuers utilize properties of the evader's Voronoi cell to choose a control strategy that minimizes the safe-reachable area of the evader, which in turn leads to the evader's capture.

Η παρούσα διπλωματική εργασία, πραγματεύεται την υλοποίηση ενός περιβάλλοντος εξομοίωσης Grid δικτύων ως μια υπολογιστική πλατφόρμα πάνω στην οποία τίθενται σε σύγκριση κάποιοι scheduling αλγόριθμοι. Η τεχνολογία Grid προϋποθέτει την ύπαρξη ενός δικτύου που κάποιοι από τους κόμβους του διαθέτουν υπολογιστικούς πόρους ενώ κάποιοι χρήστες ζητούν πρόσβαση σε αυτούς. Για τον ομαλό διαμοιρασμό των πόρων απαιτούνται κάποιοι scheduling αλγόριθμοι οι οποίοι λαμβάνοντας υπόψη την διαθεσιμότητα των πόρων, δρομολογούν κατάλληλα τις εργασίες. Σκοπός της εργασίας είναι να παρουσιάσει αποτελέσματα και να συγκρίνει την απόδοση αλγορίθμων και αρχιτεκτονικών χρονοπρογραμματισμού, που μελετήσαμε πάνω στην υπολογιστική πλατφόρμα που υλοποιήθηκε. / This diploma thesis discus the implementation of a Grid network simulation environment, as computational platform in order to compare scheduling algorithms. The Grid technology presupposes a network where some of the nodes … computational resources and some users request access to them. For an efficient distribution of the network resources, some scheduling algorithms are necessary in order to route the tasks taking into consideration the availability of the resources. The objective of this master thesis is to present results and compare the efficiency of scheduling algorithms and architectures tested over the computational platform implemented.

In this thesis, we look into the problem of forming and maintaining good committees that can represent a distributed network. The solution to this problem can be used as a sub-routine for Byzantine Agreement that only costs sub-quadratic message complexity. Most importantly, we make no cryptographic assumptions such as the Random Oracle assumption and the existence of private channels. However, we do assume the network to be peer-to-peer, where a message receiver knows who the message sender is. Under the synchronous full information model, our solution is to utilize an approximating disperser for selecting a good next committee with high probability, repeatedly. We consider several existing theoretical constructions (randomized and deterministic) for approximating dispersers, and examine the practical applicability of them, while improving constants for some constructions. This algorithm is robust against a semi-adaptive adversary who can decide the set of nodes to corrupt periodically. Thus, a new committee should be selected before the current committee gets corrupted. We also prove some constructions that do not work practically for our scenario. / Graduate

No description available.

Collecting data from sensor nodes to designated sinks is a common and challenging task in a wide variety of wireless sensor network (WSN) applications, ranging from animal monitoring to security surveillance. A number of approaches exploiting sink mobility have been proposed in recent years: some are proactive, in that sensor nodes push their read- ings to storage nodes from where they are collected by roaming mobile sinks, whereas others are reactive, in that mobile sinks pull readings from nearby sensor nodes as they traverse the sensor network. In this thesis, we point out that deciding which data collection approach is more energy-efficient depends on application characteristics, includ- ing the mobility patterns of sinks and the desired latency of collected data. We introduce novel adaptive data collection schemes that are able to automatically adjust to changing sink visiting patterns or data requirements, thereby significantly easing the deployment of a WSN. We illustrate cases where combining proactive and reactive modes of data collection is particularly beneficial. This motivates the design of TwinRoute, a novel hybrid algorithm that can flexibly mix the two col- lection modes at appropriate levels depending on the application sce- nario. Our extensive experimental evaluation, which uses synthetic and real-world sink traces, allows us to identify scenario characteristics that suit proactive, reactive or hybrid data collection schemes. It shows that TwinRoute outperforms the pure approaches in most scenarios, achiev- ing desirable tradeoffs between communication cost and timely delivery of sensor data.

Made available in DSpace on 2016-04-25T20:20:57Z (GMT). No. of bitstreams: 1 Pedro Malina.pdf: 1037064 bytes, checksum: 35f53cc3c16eee2d1571a091d7c1965f (MD5) Previous issue date: 2013-05-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation establishes as an exploratory study, trying to bring new elements to Wikipedia s analysis within the political science field. This work analysis Wikipedia as a distributed network, a way of functioning that brings many elements from control society. In order to achieve that, it initially puts the main rules of Wikipedia and how they establish a play of forces, where consensus, verifiability, and neutrality are main elements. Besides that, through the genealogical method, presents the forces relations implied in the articles elaboration procedures based on the presentation of three talk pages from Wikipedia / Esta dissertação estabelece-se como um estudo exploratório, tentando trazer novos elementos para a análise da Wikipedia dentro do campo da ciência politica. Este trabalho analisa a Wikipedia como uma rede distribuída, um modo de funcionamento que traz diversos elementos da sociedade de controle. Para isso, coloca inicialmente as regras centrais da Wikipedia e como estas estabelecem um jogo de forças, onde consenso, verificabilidade e neutralidade são elementos centrais. Além disso, através do método genealógico, apresenta as relações de força implicadas nos procedimentos de elaboração dos verbetes a partir da apresentação de três talk pages da Wikipedia

Made available in DSpace on 2016-04-26T14:54:06Z (GMT). No. of bitstreams: 1 Pedro Malina.pdf: 1037064 bytes, checksum: 35f53cc3c16eee2d1571a091d7c1965f (MD5) Previous issue date: 2013-05-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation establishes as an exploratory study, trying to bring new elements to Wikipedia s analysis within the political science field. This work analysis Wikipedia as a distributed network, a way of functioning that brings many elements from control society. In order to achieve that, it initially puts the main rules of Wikipedia and how they establish a play of forces, where consensus, verifiability, and neutrality are main elements. Besides that, through the genealogical method, presents the forces relations implied in the articles elaboration procedures based on the presentation of three talk pages from Wikipedia / Esta dissertação estabelece-se como um estudo exploratório, tentando trazer novos elementos para a análise da Wikipedia dentro do campo da ciência politica. Este trabalho analisa a Wikipedia como uma rede distribuída, um modo de funcionamento que traz diversos elementos da sociedade de controle. Para isso, coloca inicialmente as regras centrais da Wikipedia e como estas estabelecem um jogo de forças, onde consenso, verificabilidade e neutralidade são elementos centrais. Além disso, através do método genealógico, apresenta as relações de força implicadas nos procedimentos de elaboração dos verbetes a partir da apresentação de três talk pages da Wikipedia

Sensor Fusion is an essential framework in many Engineering fields. It is a relatively new paradigm for integrating data from multiple sources to synthesize new information that in general would not have been feasible from the individual parts. Within the wireless communications fields, many emerging technologies such as Wireless Sensor Networks (WSN), the Internet of Things (IoT), and spectrum sharing schemes, depend on large numbers of distributed nodes working collaboratively and sharing information. In addition, there is a huge proliferation of smartphones in the world with a growing set of cheap powerful embedded sensors. Smartphone sensors can collectively monitor a diverse range of human activities and the surrounding environment far beyond the scale of what was possible before. Wireless communications open up great opportunities for the application of sensor fusion techniques at multiple levels. In this dissertation, we identify two key problems in wireless communications that can greatly benefit from sensor fusion algorithms: Automatic Modulation Classification (AMC) and indoor localization and mapping based on smartphone sensors. Automatic Modulation Classification is a key technology in Cognitive Radio (CR) networks, spectrum sharing, and wireless military applications. Although extensively researched, performance of signal classification at a single node is largely bounded by channel conditions which can easily be unreliable. Applying sensor fusion techniques to the signal classification problem within a network of distributed nodes is presented as a means to overcome the detrimental channel effects faced by single nodes and provide more reliable classification performance. Indoor localization and mapping has gained increasing interest in recent years. Currently-deployed positioning techniques, such as the widely successful Global Positioning System (GPS), are optimized for outdoor operation. Providing indoor location estimates with high accuracy up to the room or suite level is an ongoing challenge. Recently, smartphone sensors, specially accelerometers and gyroscopes, provided attractive solutions to the indoor localization problem through Pedestrian Dead-Reckoning (PDR) frameworks, although still suffering from several challenges. Sensor fusion algorithms can be applied to provide new and efficient solutions to the indoor localization problem at two different levels: fusion of measurements from different sensors in a smartphone, and fusion of measurements from several smartphones within a collaborative framework. / Ph. D. / Sensor Fusion is an essential paradigm in many Engineering fields. Information from different nodes, sensing various phenomena, is integrated to produce a general synthesis of the individual data. Sensor fusion provides a better understanding of the sensed phenomenon, improves the application or system performance, and helps overcome noise in individual measurements. In this dissertation we study some sensor fusion applications in wireless communications: (i) cooperative modulation classification and (ii) indoor localization and mapping at different levels. In cooperative modulation classification, data from different wireless distributed nodes is combined to generate a decision about the modulation scheme of an unknown wireless signal. For indoor localization and mapping, measurement data from smartphone sensors are combined through Pedestrian Dead Reckoning (PDR) to re-create movement trajectories of indoor mobile users, thus providing high-accuracy estimates of user’s locations. In addition, measurements from collaborating users inside buildings are combined to enhance the trajectories’ estimates and overcome limitations in single users’ system performance. The results presented in both parts of this dissertation in different frameworks show that combining data from different collaborative sources greatly enhances systems’ performances, and open the door for new and smart applications of sensor fusion in various wireless communications areas.

Le point de départ pour les systèmes décentralisés a été l’échange des fichiers, en utilisant cet approche i) pour distribuer la bande passante entre tous les nœuds concernés et ii) pour augmenter la robustesse en éliminant autant que possible les points individuels de défaillance et de contrôle et iii) en partageant également les responsabilités entre les nœuds. Si les approches le plus décentralisés sont très efficaces en termes de résilience aux pannes, pour la même raison, les performances sont limités et difficiles à analyser quand on observe plusieurs réseaux interconnectés entre eux, configurations qui peuvent être analysés à travers des outils de simulation, souvent peu efficaces dans l’analyse de l’espace de possibilités. Dans cette thèse on a développé un modèle mathématique pour la modélisation de l’interconnexion des réseaux en permettant l’étude et l’exploration d’équilibres qui grâce à l’abstraction du modèle peuvent s’appliquer à l’interconnexion des réseaux de communications, réseaux de distribution de marchandise ou réseaux de distribution d’eau. La thèse se focalise aussi sur les réseaux décentralisés MANET, ou` la communication entre nœuds mobiles est purement ≪ ad-hoc ≫ (ex: deux voitures communiquant entre eux quand ils sont proches) en utilisant i) des ≪ rateless coding ≫ pour augmenter la robustesse et minimiser la perte ou la corruption de données causées par la non fiabilité du moyen de transmission et ii) des algorithmes de ≪ pollution détection ≫, par exemple de détection de nœuds malveillants ou de paquets corrompus, cette détection et prévention étant très difficile dans des environnements fortement distribués. / The original “selling point” for decentralized networks has been file exchange, using the decentralized approach to diffuse the bandwidth cost between all the participating nodes, augmenting the robustness by avoiding single point of failures and control by sharing the responsibility between all nodes. While the most decentralized approaches are very efficient in terms of resilience they are, by the same reason, more performance limited and harder to analyze. This analysis is usually the sole realm of simulation tools, a quite in- efficient way to analyze the possibility space. We thus developed and present here a mathematical model for network interconnection, enabling the study and exploration of equilibriums and, by virtue of the abstraction of the model, perfectly applicable to any interconnection of networks, be them communication networks, social networks or, for example, water distribution networks. We also focused on decentralized networks, called MANETs, where communication between mobile nodes is purely ad-hoc based (eg.: two cars passing each other and communicating while in range), exploit- ing rateless coding to increase their robustness by minimizing data loss due to transmission unreliability, and detecting malicious nodes sending corrupted packets, a hard to detect and prevent problem in a strongly distributed environments, using SIEVE, a custom developed algorithm.

This thesis focuses on novel approaches to distributed and parallel computing that are inspired by the mechanism and functioning of biological cells. We refer to this concept as cellular distributed and parallel computing which focuses on three important principles: simplicity, parallelism, and locality. We first give a parallel polynomial-time solution to the constraint satisfaction problem (CSP) based on a theoretical model of cellular distributed and parallel computing, which is known as neural-like P systems (or neural-like membrane systems). We then design a class of simple neural-like P systems to solve the fundamental maximal independent set (MIS) selection problem efficiently in a distributed way, by drawing inspiration from the way that developing cells in the fruit fly become specialised. Building on the novel bio-inspired approach to distributed MIS selection, we propose a new simple randomised algorithm for another fundamental distributed computing problem: the distributed greedy colouring (GC) problem. We then propose an improved distributed MIS selection algorithm that incorporates for the first time another important feature of the biological system: adapting the probabilities used at each node based on local feedback from neighbouring nodes. The improved distributed MIS selection algorithm is again extended to solve the distributed greedy colouring problem. Both improved algorithms are simple and robust and work under very restrictive conditions, moreover, they both achieve state-of-the-art performance in terms of their worst-case time complexity and message complexity. Given any n-node graph with maximum degree Delta, the expected time complexity of our improved distributed MIS selection algorithm is O(log n) and the message complexity per node is O(1). The expected time complexity of our improved distributed greedy colouring algorithm is O(Delta + log n) and the message complexity per node is again O(1). Finally, we provide some experimental results to illustrate the time and message complexity of our proposed algorithms in practice. In particular, we show experimentally that the number of colours used by our distributed greedy colouring algorithms turns out to be optimal or near-optimal for many standard graph colouring benchmarks, so they provide effective simple heuristic approaches to computing a colouring with a small number of colours.