In todays heterogeneous network environment, there is a growing demand for distrusted parties to jointly execute distributed algorithms on private data whose secrecy needed to be safeguarded. Platforms that support such computation on image processing purposes are called secure image processing protocols. In this thesis, we propose a new security model, called quasi information theoretic (QIT) security. Under the proposed model efficient protocols on two basic image processing algorithms linear filtering and thresholding are developed. For both problems we consider two situations: 1) only two parties are involved where one holds the data and the other possesses the processing algorithm; 2) an additional non-colluding third party exists. Experiments show that our proposed protocols improved the computational time significantly compared with the classical cryptographical couterparts as well as providing reasonable amount of security as proved in the thesis

This thesis presents the design, development, and testing of a multi-agent systems laboratory that will enable the experimental investigation of Networked Control Systems. Networked Control Systems (NCS) are integrations of computation, networking, and physical dynamics, in which embedded devices are networked to sense, monitor, execute collaborative tasks, and interact with the physical world. As the potential for applications of NCS has increased, so has the research interest in this area. Possible applications include search and rescue, scientific data collection, and health care monitoring systems. One of the primary challenges in applying NCS is designing distributed algorithms that will enable the networked devices to achieve global objectives. Another challenge is in ensuring that distributed algorithms have the necessary robustness to achieve those global objectives in dynamic and unpredictable environments. A multi-agent systems laboratory provides the researcher with a means to observe the behavior and performance of distributed algorithms as they are executed on a set of networked devices. Through this observation, the researcher may discover robustness issues that were not present in computer simulation. The objective of this research is to design and implement the infrastructure for a multi-agent systems laboratory to observe distributed algorithms implemented on networked devices.

Περιληπτικά, στη συγκεκριμένη διδακτορική διατριβή μελετήθηκαν οι θεωρίες της βελτιστοποίησης και των κατανεμημένων αλγορίθμων με σκοπό την χρήση τους σε ένα διομότιμο σύστημα σύγχρονου διαμοιρασμού αντικειμένων. Επιπλέον μελετήθηκε το περιβάλλον και οι συνθήκες λειτουργίας ενός τέτοιου συστήματος. καθώς και τα χαρακτηριστικά του. Αποτέλεσμα της μελέτης αυτής είναι η εξαγωγή συμπερασμάτων σχετικά με τις απαιτήσεις που πρέπει να πληρούνται κατά τη δημιουργία ενός διομότιμου συστήματος σύγχρονου διαμοιρασμού αντικειμένων και οι τεχνικοί στόχοι που πρέπει αυτό να ικανοποιεί. Με αυτά τα κριτήρια σχεδιάστηκε η αρχιτεκτονική του συστήματος και ορίστηκαν τα προβλήματα που πρέπει να επιλυθούν. Για την λειτουργία ενός τέτοιου συστήματος ορίστηκαν οι ακόλουθες απαιτήσεις: • Μεγιστοποίηση της χρήσης από το σύστημα του διαθέσιμου εύρους ζώνης των συμμετεχόντων κόμβων. Φυσικά, οι κόμβοι έχουν ετερογενείς τιμές του διαθέσιμου εύρους ζώνης και, μάλιστα, με μεγάλη διασπορά. • Ελαχιστοποίηση της καθυστέρησης από τη στιγμή δημιουργίας ενός αντικειμένου μέχρι τον διαμοιρασμό του σε κάθε συμμετέχοντα κόμβο. • Ομοιόμορφη διαρκής κατανομή του συνολικού εύρους ζώνης του συστήματος στους συμμετέχοντες κόμβους. • Ανεκτικότητα του συστήματος στη δυναμική συμπεριφορά των χρηστών που προκαλείται από εισόδους και εξόδους των χρηστών στο σύστημα σε μη προκαθορισμένες χρονικές στιγμές. • Ικανότητα κλιμάκωσης του συστήματος σε αριθμό συμμετεχόντων χρηστών κάτι που επάγει την κατανεμημένη διαχείριση του συστήματος. • Προσαρμογή του σχεδιαζόμενου συστήματος στην κίνηση του δικτύου στο οποίο αυτό επικάθεται και ανεκτικότητά του στις μεταβολές του εύρους ζώνης των συμμετεχόντων κόμβων. • Ελαχιστοποίηση του φορτίου το οποίο εισάγει η λειτουργία του συστήματος στο δίκτυο. Για τη λειτουργία του προτεινόμενου συστήματος απαιτείται η δημιουργία ενός γράφου διασύνδεσης. Ως γράφος διασύνδεσης ορίζεται ο γράφος που προκύπτει αν κάθε κόμβος συνδεθεί με ένα μικρό υποσύνολο των συμμετεχόντων κόμβων που ονομάζονται και γείτονες του κόμβου. Για την ικανοποίηση των προαναφερθεισών απαιτήσεων. μελετήθηκαν τα χαρακτηριστικά του γράφου διασύνδεσης και προέκυψε ότι κάθε κόμβος: α) πρέπει να έχει γείτονες με όσο το δυνατόν μικρότερη δικτυακή καθυστέρηση μεταξύ τους, β) πρέπει να έχει αριθμό εξερχόμενων συνδέσεων ανάλογο με το εύρος ζώνης του, γ) οι συνδέσεις αυτές πρέπει να κατανέμονται ομοιόμορφα στους συμμετέχοντες κόμβους για την ικανοποίηση των αναγκών όλων των κόμβων, δ) οι κόμβοι με σχετικά μεγάλο εύρος ζώνης πρέπει να ομαδοποιούνται στο γράφο με σκοπό την γρήγορη αρχικά διάχυση του αντικειμένου και ε) ο γράφος διασύνδεσης πρέπει να αναδιατάσσεται δυναμικά έτσι ώστε να διατηρεί τις ιδιότητες αυτές στο δυναμικό δικτυακό περιβάλλον που επικάθεται και για δυναμική συμπεριφορά των συμμετεχόντων κόμβων. Για την ικανοποίηση αυτών των τεχνικών στόχων αναπτύχθηκε μία δομή του γράφου που ικανοποιεί αυτά τα χαρακτηριστικά. Η βελτιστοποίηση του γράφου γίνεται μέσω αλγορίθμων κατά την λειτουργία των οποίων κάθε κόμβος επιλέγει περιοδικά ένα τυχαίο κόμβο ο οποίος είναι γείτονάς του στον γράφο διασύνδεσης. Μεταξύ των δύο αυτών κόμβων εκτελείται ανακατανομή των γειτόνων τους με σκοπό την εξισορρόπηση του αριθμού των γειτόνων που κάθε ένας από αυτούς διαθέτει. αλλά και την ελαχιστοποίηση της μέσης καθυστέρησης που έχουν αθροιστικά οι κόμβοι από τους γείτονές τους. Οι αλλαγές στον γράφο διασύνδεσης που προκύπτουν από κάθε εκτέλεση του αλγορίθμου αυτού μεταβάλλουν και τους γείτονες ενός υποσυνόλου κόμβων εκτός των δύο συμμετεχόντων στον αλγόριθμο εναλλαγής. Οι αλλαγές αυτές επιφέρουν άλλες αλλαγές με την σειρά τους και έτσι προκύπτει τελικά ένας γράφος διασύνδεσης όπου κάθε κόμβος έχει τον προκαθορισμένο αριθμό γειτόνων και. παράλληλα. ελαχιστοποιείται το άθροισμα των μέσων δικτυακών καθυστερήσεων που έχουν οι συμμετέχοντες κόμβοι με τους γείτονές τους. Για τον διαμοιρασμό του αντικειμένου ο δημιουργός του το τεμαχίζει σε τεμάχια (μπλοκ). Τα τεμάχια προωθούνται σε ένα πολύ μικρό σύνολο κόμβων και αποτελούν τις λογικές μονάδες δεδομένων που ανταλλάσσονται μεταξύ των κόμβων. Σκοπός είναι ο διαμοιρασμός του κάθε τεμαχίου σε κάθε κόμβο μέσα σε ένα προκαθορισμένο χρονικό διάστημα. Για την ανταλλαγή τεμαχίων μεταξύ των γειτόνων του γράφου διασύνδεσης του προς διαμοιρασμού αντικειμένου μεταξύ των συμμετεχόντων κόμβων αναπτύχθηκε ένας Κατανεμημένος Χρονοπρογραμματιστής Ανταλλαγής Τεμαχίων (ΚΧΑΤ). Τεχνικοί στόχοι της ανάπτυξης του ΚΧΑΜ αποτέλεσαν α) ο χρονισμός διαπραγμάτευσης αποστολής τεμαχίων μεταξύ κάθε αποστολέα και παραλήπτη, β) η γρήγορη διάδοση πρόσφατα παραγόμενων τεμαχίων και σπάνιων σε μία γειτονία του γράφου διασύνδεσης (τεμάχια που δημιουργήθηκαν μεταγενέστερα από άλλα ευνοούνται από το χρονοπρογραμματιστή αρχικά για την επιτυχή και γρήγορη διάδοσή τους σε μία κρίσιμη μάζα από κόμβους), γ) η τροφοδότηση όλων των κόμβων με ομοιόμορφο και σταθερό ρυθμό, δ) η προτεραιότητα σε κόμβους με μεγάλο εύρος ζώνης, ε) η αποφυγή μετάδοσης του ίδιου τεμαχίου από δύο αποστολείς προς τον ίδιο παραλήπτη και στ) η αποφυγή μιας κατάστασης όπου αποστολέας και παραλήπτης δεν έχουν τεμάχια προς ανταλλαγή. Ο χρονισμός του ΚΧΑΜ που αναπτύχθηκε αποτελείται από τρείς φάσεις. Στην πρώτη φάση που εκτελείται περιοδικά από κάθε αποστολέα εκδίδεται και αποστέλλεται στους πιθανούς παραλήπτες ένα σύνολο από «κουπόνια» μεγέθους ανάλογου με το εύρος ζώνης του αποστολέα. Στη δεύτερη φάση ο εκάστοτε παραλήπτης ζητά προκαταβολικά ένα τεμάχιο στην περίπτωση που επιλεγεί από τον αποστολέα για μετάδοση τεμαχίου. Στην τρίτη φάση ο αποστολέας επιλέγει τον παραλήπτη ακριβώς πριν την μετάδοση κάθε τεμαχίου και αποστέλλει το τεμάχιο που έχει ζητηθεί. Ο αλγόριθμος ο οποίος προτείνεται για τη δημιουργία κουπονιών έχει ως στόχο τη μεγιστοποίηση της χρήσης του εύρους ζώνης όλων των κόμβων και την ικανοποίηση των αναγκών κάθε συμμετέχοντα κόμβου. Είναι αυτός που, στην ουσία, καθορίζει τις ροές δεδομένων μεταξύ των γειτόνων του γράφου διασύνδεσης. Η χρησιμότητά του αναδεικνύεται σε περιπτώσεις όπου ο ρυθμός αναπαραγωγής του προς διαμοιρασμό αντικειμένου είναι παρόμοιος με το μέσο εύρος ζώνης του συστήματος. Οι απαιτήσεις του αλγορίθμου ζήτησης τεμαχίων μοντελοποιούνται μέσω της γραμμικής βελτιστοποίησης και διασφαλίζεται η γρήγορη και αποτελεσματική διάχυση των τεμαχίων ελαχιστοποιώντας την ύπαρξη ανενεργών πόρων. Τέλος, ο αλγόριθμος επιλογής γείτονα είναι αυτός που ρυθμίζει την ομοιόμορφη κατανομή του εύρους ζώνης στους συμμετέχοντες κόμβους, αλλά και δίνει προτεραιότητα στους κόμβους με μεγάλο εύρος ζώνης έτσι ώστε να επιτευχθεί ο γρήγορος διαμοιρασμός κάθε τεμαχίου και η ελαχιστοποίηση της καθυστέρησης του συστήματος. Η αξιολόγηση της προτεινόμενης αρχιτεκτονικής, της τοπολογίας του γράφου διασύνδεσης και του ΚΧΑΜ, έγινε μέσω προσομοίωσης σε προσομοιωτή δικτυακών συστημάτων. Μοντελοποιήθηκε το εύρος ζώνης των συμμετεχόντων κόμβων και δικτυακές καθυστερήσεις χρησιμοποιώντας πραγματικά δεδομένα από διομότιμα συστήματα.. Το σύστημα που αναπτύχθηκε μοντελοποιήθηκε πλήρως σε επίπεδο πακέτου. Εξετάστηκαν αρκετά σενάρια αξιολόγησης του συστήματος τα οποία, μεταξύ άλλων, περιλαμβάνουν, ευαισθησία του συστήματος σε παραμέτρους των προτεινόμενων αλγορίθμων, δυναμικά σενάρια όσον αφορά τη συμπεριφορά των χρηστών και του δικτύου και σενάρια εύρεσης των ορίων του προτεινόμενου συστήματος. Η αξιολόγηση των αποτελεσμάτων έδειξε ότι ικανοποιούνται οι απαιτήσεις που τέθηκαν για τη δημιουργία του συστήματος, καθώς και βελτίωση της συμπεριφοράς του συστήματος σε σχέση με αντίστοιχα συστήματα της διεθνούς βιβλιογραφίας με τα οποία συγκρίθηκε. / Peer-to-peer live streaming is a network application, where peers (users) contribute their upload bandwidth for the real time distribution of a video stream. The objective of this work is the optimization of this data diffusion with a distributed and self-organized architecture. Peers have heterogeneous and dynamic uploading bandwidth. This fact combined with the characteristics of the topology of the underlying network and the dynamic traffic conditions e.g. latency create a volatile and complex environment for P2P live streaming delivery, which strongly affect the success of a P2P system measured by a number of performance metrics. The first important factor is the uploading bandwidth utilization that corresponds to the ability of the system to exploit as much as possible of the overall uploading bandwidth of the participating peers. The maximization of the upload bandwidth utilization increases the video playback delivery rate and ensures the stability of the distribution. Equally important parameter is the setup time defined as the time interval between the generation of a block from an origin server and its delivery to every peer in the system. Furthermore, a P2P live streaming system has to remain stable and its delivery rate must remain high in a dynamic environment, where peers arrive and depart randomly. .Finally, fairness among nodes indicates the ability of the system to distribute continuously and uniformly the aggregate uploading bandwidth to the participating peers. This ensures that every peer will acquire a percentage of blocks above a critical threshold for an “affordable” video playback regardless the aggregate uploading bandwidth is not sufficient for the complete delivery of the video stream. For the development of the proposed system is required the creation of a content diffusion overlay (CDO). For every peer, CDO defines the graph which includes the subset of adjacent participating peers (neighbors) that are connected with it. For the fulfillment of the aforementioned requirements CDO must ensure the following features: • Each peer must have neighbors close to it in the underlying network. • The number of the neighbors has to be proportional to its upload bandwidth. • The number of the neighbors from which each peer receives data has to be balanced among participating peers. • In the CDO, peers with high upload bandwidth must be clustered for the fast diffusion of each video block to a critical mass of peers. • The CDO has to be adapted dynamically according to the underlying network conditions and the behavior of the participating peers. The optimization of the CDO and the fulfillment of these technical objectives is done with the use of a distributed optimization and maintenance algorithm (DOMA) that reorganizes the “neighborhoods” of CDO and so it keeps almost stable the attributes of the graph during peer arrivals and departures. It also ensures the high levels of bandwidth utilization. The algorithm based on a cost function, denoted as energy function between two nodes and can represent for example the network latency between two nodes. DOMA is executed between two neighbors that we note as initiators and their neighbors that we called satellites. Its purpose is to minimize the sum of the energy functions between initiators and satellites under the constraints on the number of neighbors that the graph structure implies. In p2p live streaming every user and/or content provider that generates a multimedia block stream is indicated as source. A P2P block exchange scheduling algorithm (P2P-BESA) ensures the distribution of each block to every user and with low latency. P2P-BESA focuses on the following properties: • The consistent message sequence between two peers for the negotiation of the transmission of a video block. • The fast diffusion of blocks that are recently produced. • The transmission of blocks to every peer with a stable and equal rate among the peers. • The prioritization of transmission to peers with relatively high upload bandwidth. • The avoidance of block retransmission. • The avoidance of content bottleneck between two peers. The decision for the transmission of a block is done in three phases. In the first phase, every peer acting as block sender issues tokens periodically proportional with its upload bandwidth. This ensures the maximization of the upload bandwidth of the participating peers and determines the data flows between participating peers. In the second phase, each peer periodically is acting as receiver and requests a different block from each one of its potential senders. As potential senders we define the set of peers that have recently sent a token to it. This algorithm ensures the fast and complete diffusion of every block by also minimizing the idle bandwidth resources in the systems. Finally in the third phase, before the transmission of each block each sender selects the destination peer according to the blocks that it misses and its upload bandwidth capabilities. The evaluation of the proposed system is done with a network simulator. A detailed packet level P2P live streaming simulator models the bandwidth of the participating peers, the network latency between them, peer arrivals and departures and finally dynamic changes in the underlying network. The evaluation of the system shows that: • It achieves very high levels of bandwidth utilization (around 95%) • low latency in the diffusion of its video block (2-4 seconds) • system is almost immune to peer arrivals and departures • very tolerant to underlying network changes Finally the proposed system outperforms when it is compared with other recently proposed systems in the international bibliography.

DANTAS, Allberson Bruno de Oliveira. Uma interface de programação distribuída para aplicações em otimização combinatória. 2011. 86 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T17:57:51Z No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:23:03Z (GMT) No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Made available in DSpace on 2016-07-13T12:23:03Z (GMT). No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) Previous issue date: 2011 / This work was motivated by the need of exploiting the potential of distributed paralelism in combinatorial optimization applications. propose a distributed programming interface, To achieve this goal, we in which we cherish two main requirements: e ciency and reuse. The rst stems from the need of HPC (High applications require maximum possible performance. Performance Computing) Therefore, we specify our interface as an extension of the MPI library, which is assumed to be e cient for distributed applications. The reuse requirement must make compatible two important features: asynchronism and collective operations. Asynchronism must be present at our interface, once most of combinatorial optimization applications have an asynchronous nature. Collective operations are features that should be available in the interface, so that they can be used by applications in their execution. In order reach the reuse requirement, we based this interface on the Event- and Pulse-driven Models of Distributed Computing, once they are asynchronous and allow the incorporation of collective operations. We implemented partially the interface de ned in this work. In order to validate the use of the inteface by combinatorial optimization applications, we selected two applications and implemented them using our interface. They are the Branch-and-Bound technique and the Maximum Stable Set Problem (MSSP). We also provide some experimental results. / Este trabalho foi motivado pela necessidade da exploração do potencial do paralelismo distribuído em aplicações em Otimização Combinatória. Para tanto, propomos uma interface de programação distribuída, na qual prezamos dois requisitos principais: eficiência e reuso. O primeiro advém da necessidade de aplicações de CAD exigirem máximo desempenho possível. Assim sendo, especificamos esta interface como uma extensão da biblioteca MPI, a qual é assumida como eficiente para aplicações distribuídas. O requisito reuso deve tornar compatíveis duas características importantes: assincronismo e operações coletivas. O assincronismo deve estar presente na interface, uma vez que as aplicações em Otimização Combinatória, em sua maioria, possuem uma natureza assíncrona. Operações coletivas são funcionalidades que devem estar disponíveis na interface, de modo que possam ser utilizadas por aplicações em suas execuções. Tendo em vista atender o requisito reuso, baseamos esta interface nos Modelos de Computação Distribuída Dirigidos por Eventos e por Pulsos, pois os mesmos são assíncronos e permitem a incorporação de operações coletivas. Implementamos parcialmente a inteface definida neste trabalho. Tendo em vista validar uso desta inteface por aplicações em Otimização Combinatória, selecionamos duas aplicações e as implementamos utilizando a interface. São elas a técnica Branch-and-Bound e o Problema do Conjunto Independente Máximo (CIM). Fornecemos também alguns resultados experimentais.

The proposed dissertation research investigates Optimization and Control for Microgrid and Power Electronic Converters. The research has two major parts: i- Microgrid Operation and Control, ii- Power Electronic Converter Control and Optimization. In the first part, three focuses are investigated. First, a completely distributed algorithm is developed for dc optimal power flow problem for power distribution systems as one of the necessary functions considered in unit-commitment problem in day-ahead markets. This method is derived based upon the partial primal-dual representation of the economic dispatch problem, which is finally translated to DC-OPF problem. Second, the optimal interaction between the utility and communities will be studied, due to its improtance in real-time markets. The objective of this section will be to develop an iterative agent-based algorithm for optimal utility-community control. The algorithm will consider the AC power system constraints to maintain power system stability. In this algorithm, a simplified model of microgrid is considered. In the third focus, a comprehensive model of microgrid is taken into account. The optimal operation of the microgrid considering energy storage systems and renewable energy resources is investigated. The interaction of such microgrids with the main grid to define the optimal operation of the entire embedded system is studied through two iterative methods. In the microgrid's internal problem, a moving-horizon algorithm is considered to define the optimal dispatch of all distributed energy resources while considering the time-correlated constraints of energy storage systems. A thorough analysis of the effects of the size of storage systems on energy and reserve market parameters are also performed. In the second part, the focus of research is to develop optimal control strategies for Power Electronic Converters. A Model Predictive Control (MPC) switching method is proposed for Modular Multilevel Converters (MMC). The optimal solution of MPC problem is then represented as an optimization problem. Due to lack of efficient algorithms to seek the optimal solution, a fast algorithm will be proposed in this research. The method proposed reduces the number of possible solutions and computation efforts dramatically.

Orientador: Lee Luan Ling / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-20T02:24:35Z (GMT). No. of bitstreams: 1 YakovNae_M.pdf: 7990917 bytes, checksum: 122c511d9ba839a2f1464fbe7fca09b4 (MD5) Previous issue date: 2011 / Resumo: Gerência de armazenamento em Redes de Sensores Sem Fio (RSSF) é uma questão muito crítica. Além da RSSFs conter uma vasta quantidade de armazenamento agregada, ela não pode ser usada inteiramente. Portanto, o sistema inteiro falha quando o primeiro sensor tem sua capacidade de armazenamento esgotada, deixando uma grande capacidade de armazenamento inutilizada. Sugere-se que os sensores devem-se ser capazes de detectar as capacidades de armazenamentos inutilizadas, para prolongar as suas funcionalidades. Entretanto, em RSSF de larga escala isso pode ser muito difícil uma vez que os sensores podem não ter conhecimento da existência dos outros. Neste trabalho apresenta-se duas principais contribuições: otimização da capacidade total de armazenamento para RSSF em grande escala e uma nova abordagem de roteamento - Deterministic "Random" Walk (Passeio "Aleatório" Determinístico). Apresenta-se um novo modelo de armazenamento via construção "sob demanda" de Cadeias de Armazenamento Distribuídas ( Distributed Storage Chains (DSC). Estas cadeias representam parcerias entrem os sensores que podem compartilhar suas capacidades de armazenamento. Resultando, os sensores não estão sujeitos às suas limitações de armazenamento, mas para à capacidade total de armazenamento disponível no sistema. Constrói-se estas cadeia via passeio determinístico sobre a topologia sugerida. Todavia, mostra-se que estes passeios apresentam um comportamento aleatório que é muito eficiente em termos de localização de capacidade de armazenamento disponível / Abstract: Storage management of Wireless Sensor Networks (WSN) is a very critical issue in terms of system's lifetime. While WSNs host a vast storage capacity on the aggregate, that capacity cannot be used entirely. Eventually, the entire network may fail when the first sensor has its own storage capacity depleted, leaving behind a large amount of unutilized storage capacity. We suggest that sensors should be able to detect unutilized storage capacity in order to prolong their functionality. However, for large scale WSNs this can be a difficult task, since sensors may not be aware of the existence of others. This work has two main contributions: an optimization of the overall storage capacity for large scale WSNs and a novel routing approach of deterministic "random" walk. We present a new storage model by building "on - demand" Distributed Storage Chains (DSC). These chains represent partnership between sensors that share their storage capacity. As a result, sensors are no longer subjected to their own storage limitations but to the total amount of available storage in the WSN. We construct these chains via deterministic walks over our suggested topology. However, we show that these walks resemble the behavior of random walks and are therefore highly efficient in terms of locating available storage / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Wireless sensor networks (WSNs) allow us to instrument the physical world in novel ways, providing detailed insight that has not been possible hitherto. Since WSNs provide an interface to the physical world, each sensor node has a location in physical space, thereby enabling us to associate spatial properties with data. Since WSNs can perform periodic sensing tasks, we can also associate temporal markers with data. In the environmental sciences, in particular, WSNs are on the way to becoming an important tool for the modelling of spatially and temporally extended physical phenomena. However, support for high-level and expressive spatial-analytic tasks that can be executed inside WSNs is still incipient. By spatial analysis we mean the ability to explore relationships between spatially-referenced entities (e.g., a vineyard, or a weather front) and to derive representations grounded on such relationships (e.g., the geometrical extent of that part of a vineyard that is covered by mist as the intersection of the geometries that characterize the vineyard and the weather front, respectively). The motivation for this endeavour stems primarily from applications where important decisions hinge on the detection of an event of interest (e.g., the presence, and spatio-temporal progression, of mist over a cultivated field may trigger a particular action) that can be characterized by an event-defining predicate (e.g., humidity greater than 98 and temperature less than 10). At present, in-network spatial analysis in WSN is not catered for by a comprehensive, expressive, well-founded framework. While there has been work on WSN event boundary detection and, in particular, on detecting topological change of WSN-represented spatial entities, this work has tended to be comparatively narrow in scope and aims. The contributions made in this research are constrained to WSNs where every node is tethered to one location in physical space. The research contributions reported here include (a) the definition of a framework for representing geometries; (b) the detailed characterization of an algebra of spatial operators closely inspired, in its scope and structure, by the Schneider-Guting ROSE algebra (i.e., one that is based on a discrete underlying geometry) over the geometries representable by the framework above; (c) distributed in-network algorithms for the operations in the spatial algebra over the representable geometries, thereby enabling (i) new geometries to be derived from induced and asserted ones, and (ii)topological relationships between geometries to be identified; (d) an algorithmic strategy for the evaluation of complex algebraic expressions that is divided into logically-cohesive components; (e) the development of a task processing system that each node is equipped with, thereby with allowing users to evaluate tasks on nodes; and (f) an empirical performance study of the resulting system.

Distributed Approximation is a new and rapidly developing discipline that lies at the crossroads of various well-established areas of Computer Science - Distributed Computing, Approximation Algorithms, Graph Theory and often, Computational Geometry. This thesis focuses on the design and analysis of distributed algorithms to solve optimization problems that usually arise in large-scale, heavily dynamic, resource constrained networks, e.g. wireless ad-hoc and sensor networks, P2P systems, mobile networks etc. These problems can often be abstracted by variations of well-known combinatorial optimization problems, such as topology control, clustering etc. Many of these problems are known to be hard (NP-complete). But we need fast and light-weight distributed algorithms for these problems, that yield near-optimal solutions. The results presented in this thesis can be broadly divided in two parts. The first part contains a set of results that obtain improved solutions to the classic problem of computing a sparse "backbone" for Wireless Sensor Networks (WSNs). In graph-theoretic terms, the goal is to compute a spanning subgraph of the input graph, that is sparse, lightweight and has low stretch. The term "low stretch" indicates that in spite of dropping many edges, the distance between any two nodes in the graph is not increased by much. We model WSNs as geometric graphs - unit ball graphs, quasi-unit ball graphs etc. in Euclidean spaces, as well as in more general metric spaces of low doubling dimension. We identify and exploit a variety of geometric features of those models to obtain our results. In the second part of the thesis we focus on distributed algorithms for clustering problems. We present several distributed approximation algorithms for clustering problems (e.g., minimum dominating set, facility location problems) that improve on best known results so far. The main contribution here is the design of distributed algorithms where the running time is a "tunable" parameter. The advent of distributed systems of unprecedented scale and complexity motivates the question of whether it is possible to design algorithms that can provide non-trivial approximation guarantees even after very few rounds of computation and message exchanges. We call these algorithms "k-round algorithms". We design k-round algorithms for various clustering problems that yield non-trivial approximation factors even if k is a constant. Additionally, if k assumes poly-logarithmic values, our algorithms match or improve on the best-known approximation factors for these problems.

Les automates distribués sont des machines à états finis qui opèrent sur des graphes orientés finis. Fonctionnant comme des algorithmes distribués synchrones, ils utilisent leur graphe d'entrée comme un réseau dans lequel des processeurs identiques communiquent entre eux pendant un certain nombre (éventuellement infini) de rondes synchrones. Pour la variante locale de ces automates, où le nombre de rondes est borné par une constante, Hella et al. (2012, 2015) ont établi une caractérisation logique par des formules de la logique modale de base. Dans le cadre de cette thèse, nous présentons des caractérisations logiques similaires pour deux classes d'automates distribués plus expressives.La première classe étend les automates locaux avec une condition d'acceptation globale et la capacité d'alterner entre des modes de calcul non-déterministes et parallèles. Nous montrons qu'elle est équivalente à la logique monadique du second ordre sur les graphes.En nous restreignant à des transitions non-déterministes ou déterministes, nous obtenons également deux variantes d'automates strictement plus faibles pour lesquelles le problème du vide est décidable.Notre seconde classe adapte la notion standard d'algorithme asynchrone au cadre des automates distribués non-locaux. Les machines résultantes sont prouvées équivalentes à un petit fragment de la logique de point fixe, et plus précisément, à une variante restreinte du μ-calcul modal qui autorise les plus petits points fixes mais interdit les plus grands points fixes. Profitant du lien avec la logique, nous montrons aussi que la puissance expressive de ces automates asynchrones est indépendante du fait que des messages puissent être perdus ou non.Nous étudions ensuite la décidabilité du problème du vide pour plusieurs classes d'automates non-locaux. Nous montrons que le problème est indécidable en général, en simulant une machine de Turing par un automate distribué qui échange les rôles de l'espace et du temps. En revanche, le problème s'avère décidable en LOGSPACE pour une classe d'automates oublieux, où les nœuds voient les messages reçus de leurs voisins, mais ne se souviennent pas de leur propre état. Finalement, à titre de contribution mineure, nous donnons également de nouvelles preuves de séparation pour plusieurs hiérarchies d'alternance de quantificateurs basées sur la logique modale. / Distributed automata are finite-state machines that operate on finitedirected graphs. Acting as synchronous distributed algorithms, they use their input graph as a network in which identical processors communicate for a possibly infinite number of synchronous rounds. For the local variant of those automata, where the number of rounds is bounded by a constant, Hella et al. (2012, 2015) have established a logical characterization in terms of basic modal logic. In this thesis, we provide similar logical characterizations for two more expressive classes of distributed automata.The first class extends local automata with a global acceptance condition and the ability to alternate between non deterministic and parallel computations. We show that it is equivalent to monadic second-order logic on graphs. By restricting transitions to be non deterministic or deterministic, we also obtain two strictly weaker variants for which the emptiness problem is decidable.Our second class transfers the standard notion of asynchronous algorithm to the setting of non local distributed automata. There sulting machines are shown to be equivalent to a small fragment of least fixpoint logic, and more specifically, to a restricted variantof the modal μ -calculus that allows least fixpoints but forbids greatest fixpoints. Exploiting the connection with logic, we additionally prove that the expressive power of those asynchronous automata is independent of whether or not messages can be lost.We then investigate the decidability of the emptiness problem forseveral classes of nonlocal automata. We show that the problem isundecidable in general, by simulating a Turing machine with adistributed automaton that exchanges the roles of space and time. Onthe other hand, the problem is found to be decidable in logspace for a class of forgetful automata, where the nodes see the messages received from their neighbors but cannot remember their own state. As a minor contribution, we also give new proofs of the strictness of several set quantifier alternation hierarchies that are based on modallogic.

We investigate diverse aspects of the performance of wireless networks, including throughput, delay and distributed complexity. <br />One of the main challenges for optimizing them arises from radio interference, an inherent factor in wireless networks.<br />Graph-based interference models represent a large class of interference models widely used for the study of wireless networks,<br />and suffer from the weakness of over-simplifying the interference caused by wireless signals in a local and binary way.<br />A more sophisticated interference model, the physical interference model, based on SINR constraints,<br />is considered more realistic but is more challenging to study (because of its non-linear form and non-local property).<br />In this dissertation, we study the connections between the two types of interference models -- graph-based and physical interference models --<br />and tackle a set of fundamental problems under the physical interference model;<br />previously, some of the problems were still open even under the graph-based interference model, and to those we have provided solutions under both types of interference models.<br /><br />The underlying interference models affect scheduling and power control -- essential building blocks in the operation of wireless networks -- that directly deal with the wireless medium; the physical interference model (compared to graph-based interference model) compounds the problem of efficient scheduling and power control by making it non-local and non-linear.<br />The system performance optimization and tradeoffs with respect to throughput and delay require a ``global\'\' view across<br />transport, network, media access control (MAC), physical layers (referred to as cross-layer optimization)<br />to take advantage of the control planes in different levels of the wireless network protocol stack.<br />This can be achieved by regulating traffic rates, finding traffic flow paths for end-to-end sessions,<br />controlling the access to the wireless medium (or channels),<br />assigning the transmission power, and handling signal reception under interference.<br /><br />The theme of the dissertation is<br />distributed algorithms and optimization of QoS objectives under the physical interference model.<br />We start by developing the first low-complexity distributed scheduling and power control algorithms for maximizing the efficiency ratio for different interference models;<br />we derive end-to-end per-flow delay upper-bounds for our scheduling algorithms and our delay upper-bounds are the first network-size-independent result known for multihop traffic.<br />Based on that, we design the first cross-layer multi-commodity optimization frameworks for delay-constrained throughput maximization by incorporating the routing and traffic control into the problem scope.<br />Scheduling and power control is also inherent to distributed computing of ``global problems\'\', e.g., the maximum independent set problems in terms of transmitting links and local broadcasts respectively, and the minimum spanning tree problems.<br />Under the physical interference model, we provide the first sub-linear time distributed solutions to the maximum independent set problems, and also solve the minimum spanning tree problems efficiently.<br />We develop new techniques and algorithms and exploit the availability of technologies (full-/half-duplex radios, fixed/software-defined power control) to further improve our algorithms.<br />%This fosters a deeper understanding of distributed scheduling from the network computing point of view.<br /><br /><br />We highlight our main technical contributions, which might be of independent interest to the design and analysis of optimization algorithms.<br />Our techniques involve the use of linear and mixed integer programs in delay-constrained throughput maximization. This demonstrates the combined use of different kinds of combinatorial optimization approaches for multi-criteria optimization.<br />We have developed techniques for queueing analysis under general stochastic traffic to analyze network throughput and delay properties.<br />We use randomized algorithms with rigorously analyzed performance guarantees to overcome the distributed nature of wireless data/control communications.<br />We factor in the availability of emerging radio technologies for performance improvements of our algorithms.<br />Some of our algorithmic techniques that would be of broader use in algorithms for the physical interference model include:<br />formal development of the distributed computing model in the SINR model, and reductions between models of different technological capabilities, the redefinition of interference sets in the setting of SINR constraints, and our techniques for distributed computation of rulings (informally, nodes or links which are well-separated covers).<br /> / Ph. D.