DANTAS, Allberson Bruno de Oliveira. Uma Interface de Programação Distribuída para Aplicações em Otimização Combinatória. 2011. 79 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Programa de Pós-Graduaçõa em Ciência da Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T16:25:19Z No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T16:27:03Z (GMT) No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Made available in DSpace on 2016-05-24T16:27: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.

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2016-10-25T21:55:38Z No. of bitstreams: 1 FACHINI_Elizeu_2016.pdf: 7355773 bytes, checksum: 57880fc3ade64c5d25c3ec2901d87e9b (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2016-10-25T21:55:54Z (GMT) No. of bitstreams: 1 FACHINI_Elizeu_2016.pdf: 7355773 bytes, checksum: 57880fc3ade64c5d25c3ec2901d87e9b (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2016-10-25T21:56:04Z (GMT) No. of bitstreams: 1 FACHINI_Elizeu_2016.pdf: 7355773 bytes, checksum: 57880fc3ade64c5d25c3ec2901d87e9b (MD5) / Made available in DSpace on 2016-10-25T21:56:15Z (GMT). No. of bitstreams: 1 FACHINI_Elizeu_2016.pdf: 7355773 bytes, checksum: 57880fc3ade64c5d25c3ec2901d87e9b (MD5) Previous issue date: 2016-02-24 / Não recebi financiamento / Monitoring is the act of collecting information concerning the characteristics and status of resources of interest. It can be used to the management and allocation of resources, detection and correction of failures and also to the evaluation of performance parameters. To automatically accomplish the monitoring a tool is needed that has functionalities related the acquiring, processing, distributing and presenting of monitoring events. In this work we are interested in a monitoring system to give support to the experimental execution of distributed algorithms, with the objective of correlating the device status with the execution data and, this way, make possible an analysis of cluster resources used by the application. Then, it’s needed a tool with particular characteristics, such as the ability to collect data with a small time period, with low intrusiveness and making the full data available. As was not possible find in the literature a tool with the features required, we developed a new monitoring tool named MSPlus. The features of this tool were evaluated through experiments with the isolated tool and comparing it with other tool. Additionally, we apply the tool in a distribucted system to monitor a distribucted algorithm. / O monitoramento é o ato de coletar informações referentes às características e estado dos recursos de interesse. Ele pode ser utilizado para gerência e alocação de recursos, detec- ção e correção de falhas e também para avaliação de parâmetros de desempenho. Para realizar o monitoramento de modo automático é necessário a utilização de ferramentas, que tem funcionalidades referentes a captação, processamento, distribuição e apresentação dos eventos de monitoramento. Neste trabalho temos interesse em um sistema de monitoramento para dar suporte à execução experimental de algoritmos distribuídos, com o objetivo de relacionar o estado dos dispositivos com os dados da execução e, desta forma, permitir uma análise do uso de recursos do aglomerado pela aplicação. É necessário então uma ferramenta com características particulares como fazer a coleta de informações com pequeno intervalo de tempo, com baixa intrusividade e realizar o armazenamento total dos dados. Como não foi possível encontrar na literatura uma ferramenta com as características desejadas, desenvolvemos uma nova ferramenta de monitoramento chamada MSPlus. As características dessa nova ferramenta foram analisadas através de experimentos de forma isolada e em comparação a outra ferramenta. Adicionalmente, aplicamos a ferramenta em um sistema distribuído monitorando um algoritmo distribuído.

Made available in DSpace on 2015-04-11T14:02:57Z (GMT). No. of bitstreams: 1 Afonso.pdf: 820074 bytes, checksum: 796ca447ff3c69734519173f92044438 (MD5) Previous issue date: 2013-03-27 / Wireless Sensor Networks (WSNs) can be used in environmental conservation applications and studies due to its wireless communication, sensing, and monitoring capabilities. In the Ecology context, amphibians are used as bioindicators of ecosystemic changes of a region and can early indicate environmental problems. Thus, biologists monitor the anuran (frogs and toads) population in order to establish environmental conservational strategies. Anuran were chosen because the sounds they emit allow classification by using microphones and signal processing. In this work we propose and evaluate some distributed algorithms for anuran classification based on their calls (vocalizations) in the habit using WSNs. This method is interesting because it is not intrusive and it allows remote monitoring. Our solution builds cluster of nodes whose acoustic collected measurements are correlated. The nodes of the same group are combined to generate local classification decisions. Then, these decisions are combined to generate a global decision. We use k-means algorithm for clustering nodes with correlated measurements, which groups instances by similarity. Experiments show that, in comparison with other literature algorithms, the error rate of our solution were 26 pp (percentage points) lower. / As Redes de Sensores Sem Fios (RSSFs) podem ser utilizadas em aplicações de conservação e estudo ambiental devido à sua capacidade de sensoriamento, monitoramento e comunicação sem fio. Dentro do contexto da Ecologia, os anfíbios são utilizados como bioindicadores de mudanças no ecossistema de uma região e podem precocemente indicar problemas ambientais. Desta forma, os biólogos monitoram a população de anuros (sapos e rãs) a fim de estabelecer estratégias de conservação do meio ambiente. Os anuros são escolhidos por causa sons que emitem (coaxar), que permitem a identificação dessas espécies por meio de microfones e processamento do sinal. Portanto, neste trabalho propomos e avaliamos alguns algoritmos distribuídos para classificação de anuros baseados em suas vocalizações em seu habitat usando RSSF. Este método é interessante pois não é intrusivo e permite o monitoramento remoto. Nossa solução cria grupos de nós sensores cujas medidas acústicas coletadas estão correlacionadas. Os dados dos nós de um mesmo grupo são combinados para gerar decisões de classificação locais. Essas decisões são então combinadas para formar uma decisão global. Para agrupar os nós com medidas correlacionadas, utilizamos o algoritmo k-means, que agrupa instâncias similares. Os experimentos mostram que, em comparação com outros algoritmos da literatura, a taxa de erro da nossa solução chegou ser até 26 pp (pontos percentuais) menor.

Les algorithmes distribués de consensus sont des algorithmes itératifs de faible complexité où les nœuds de capteurs voisins interagissent les uns avec les autres pour parvenir à un accord commun sans unité coordinatrice. Comme les nœuds dans un réseau de capteurs sans fil ont une puissance de calcul et une batterie limitées, ces algorithmes distribués doivent parvenir à un consensus en peu de temps et avec peu d’échange de messages. La première partie de cette thèse s’est basée sur l’étude et la comparaison des différents algorithmes de consensus en mode synchrone et asynchrone en termes de vitesse de convergence et taux de communications. La seconde partie de nos travaux concerne l’application de ces algorithmes de consensus au problème de la détection de trous de couverture dans les réseaux de capteurs sans fil.Ce problème de couverture fournit aussi le contexte de la suite de nos travaux. Il se décrit comme étant la façon dont une région d’intérêt est surveillée par des capteurs. Différentes approches géométriques ont été proposées mais elles sont limitées par la nécessité de connaitre exactement la position des capteurs ; or cette information peut ne pas être disponible si les dispositifs de localisation comme par exemple le GPS ne sont pas sur les capteurs. À partir de l’outil mathématique appelé topologie algébrique, nous avons développé un algorithme distribué de détection de trous de couverture qui recherche une fonction harmonique d’un réseau, c’est-à-dire annulant l’opérateur du Laplacien de dimension 1. Cette fonction harmonique est reliée au groupe d’homologie H1 qui recense les trous de couverture. Une fois une fonction harmonique obtenue, la détection des trous se réalise par une simple marche aléatoire dans le réseau. / Distributed consensus algorithms are iterative algorithms of low complexity where neighboring sensors interact with each other to reach an agreement without coordinating unit. As the nodes in a wireless sensor network have limited computing power and limited battery, these distributed algorithms must reach a consensus in a short time and with little message exchange. The first part of this thesis is based on the study and comparison of different consensus algorithms synchronously and asynchronously in terms of convergence speed and communication rates. The second part of our work concerns the application of these consensus algorithms to the problem of detecting coverage holes in wireless sensor networks.This coverage problem also provides the context for the continuation of our work. This problem is described as how a region of interest is monitored by sensors. Different geometrical approaches have been proposed but are limited by the need to know exactly the position of the sensors; but this information may not be available if the locating devices such as GPS are not on the sensors. From the mathematical tool called algebraic topology, we have developed a distributed algorithm of coverage hole detection searching a harmonic function of a network, that is to say canceling the operator of the 1-dimensional Laplacian. This harmonic function is connected to the homology group H1 which identifies the coverage holes. Once a harmonic function obtained, detection of the holes is realized by a simple random walk in the network.

We consider a wireless communication system in which there are N transmitter-receiver pairs and each transmitter wants to communicate with its corresponding receiver. This is modelled as an interference channel. We propose power allocation algorithms for increasing the sum rate of two and three user interference channels. The channels experience fast fading and there is an average power constraint on each transmitter. In this case receivers use successive decoding under strong interference, instead of treating interference as noise all the time. Next, we u se game theoretic approach for power allocation where each receiver treats interference as noise. Each transmitter-receiver pair aims to maximize its long-term average transmission rate subject to an average power constraint. We formulate a stochastic game for this system in three different scenarios. First, we assume that each user knows all direct and crosslink channel gains. Next, we assume that each user knows channel gains of only the links that are incident on its receiver. Finally, we assume that each use r knows only its own direct link channel gain. In all cases, we formulate the problem of finding the Nash equilibrium(NE) as a variational in equality problem. For the game with complete channel knowledge, we present an algorithm to solve the VI and we provide weaker sufficient conditions for uniqueness of the NE than the sufficient conditions available in the literature. Later, we present a novel heuristic for solving the VI under general channel conditions. We also provide a distributed algorithm to compute Pare to optimal solutions for the proposed games. We use Bayesian learning that guarantees convergence to an Ɛ-Nash equilibrium for the incomplete information game with direct link channel gain knowledge only, that does not require knowledge of the power policies of other users but requires feedback of the interference power values from a receiver to its corresponding transmitter. Later, we consider a more practical scenario in which each transmitter transmits data at a certain rate using a power that depends on the channel gain to its receiver. If a receiver can successfully receive the message, it sends an acknowledgement(ACK), else it sends a negative ACK(NACK). Each user aims to maximize its probability of successful transmission. We formulate this problem as a stochastic game and propose a fully distributed learning algorithm to find a correlated equilibrium(CE). In addition, we use a no regret algorithm to find a coarse correlated equilibrium(CCE) for our power allocation game. We also propose a fully distributed learning algorithm to find a Pareto optimal solution. In general Pareto points do not guarantee fairness among the users. Therefore we also propose an algorithm to compute a Nash bargaining solution which is Pareto optimal and provides fairness among the users. Finally, we extend these results when each transmitter sends data at multiple rates rather than at a fixed rate.

Atualmente, muitas redes com características dinâmicas estão em funcionamento (por exemplo MANETs, DTNs, redes oportunistas, etc). Neste trabalho, estudamos um modelo para estas redes chamado de Grafos Evolutivos, que permite expressar a dinamicidade das conexões entre nós por meio de uma simples extensão da estrutura comum de grafos. Esta modelagem é utilizada no arcabouço proposto por Casteigts et al. para definir algoritmos distribuídos em redes dinâmicas, que utiliza grafos evolutivos para representar a topologia da rede e renomeação de rótulos para expressar a comunicação entre os nós. Utilizamos esta abordagem para estudar o problema da exclusão mútua distribuída em redes dinâmicas e diversos algoritmos propostos para ele, a fim de definir e validar suas condições necessárias e suficientes de conectividade em redes dinâmicas. Além da formalização de algoritmos, o modelo de grafos evolutivos também pode ser utilizado para analisar redes dinâmicas. Rastros de redes dinâmicas reais são amplamente utilizados na literatura para estudos de algoritmos pois estes geram resultados mais realísticos do que redes simuladas com padrões de movimento. A partir dos detalhes de cada conexão entre nós de um destes rastros, é possível construir um grafo evolutivo, do qual se pode extrair dados como jornadas ótimas entre nós, variação da conectividade no tempo, estabilidade, e periodicidade. Com as informações mencionadas, um pesquisador pode observar com maior precisão as características do rastro, o que facilita na escolha da rede mais apropriada para sua necessidade. Além disso, o conhecimento prévio de tais características de uma rede auxilia no estudo do comportamento de algoritmos executados sobre ela e provém uma validação para suposições geralmente feitas pelos pesquisadores. Para fornecer estas informações, desenvolvemos uma ferramenta Web que analisa rastros de redes dinâmicas e agrega os dados em um formato de fácil visualização. Descrevemos, neste trabalho, a implementação e a utilidade de todos os serviços da ferramenta. / Lately, several networks with dynamic properties (for instance MANETs, DTNs, opportunistic networks, etc) are functioning. In this work, we studied a model for these networks called Evolving Graphs, which allows the expression of the dynamicity of the conections between nodes through a simple extension of the common graph structure. This model is used by the framework proposed by Casteigts et al. to define distributed algorithms in dynamic networks, which uses evolving graphs to represent the network topology and graph relabelling to express the communication between nodes. Using this approach, we study the distributed mutual exclusion problem in dynamic networks and several algorithms proposed to solve it, in order to define and validate their necessary and sufficient connectivity conditions. Apart from the formalization of algorithms, the evolving graphs model can also be used to analyze dynamic networks. Dynamic network traces are widely used in the literature in order to study algorithms, as they generate better results than simulated networks with movement patterns. From the details of every connection between nodes in a trace, it is possible to build an evolving graph, from which a large amount of information can be extracted, such as optimal journeys between nodes, variation of the conectivity over time, stability and periodicity. With the aforementioned information, a researcher might observe the characteristics of a trace more precisely, which facilitates the process of choosing the most appropriate trace for his needs. Furthermore, the early knowledge of such characteristics of a network helps in the study of the behavior of the algorithms exected over it and provides a validation for the assumptions usually made by the researchers. In order to provide this information, we developed a web tool which analyzes dynamic network traces and aggregates the data in an easily readable format. In this work, we describe the implementation and usefulness of every service in the tool.

This master’s thesis deals with the distributed computing and mathematical tools for modelling the distributed systems. Firstly, my attention is focused on a description of the distributed algorithms, characteristic failures for the distributed systems, and mathematical tools for an analysis of the distributed systems.The experimental part is concerned with the impact of stochastic link failures on the chosen parameters of the protocol Push-sum, namely the deviation of the final states from the average value, the convergence rate of the protocol, the distribution of the final states, and the distribution of the convergence rates. My intention is demonstrated using Matlab on a tree, a ring, a line, a star, and a fully-connected mesh topology. Was analyzed two functionalities of the protocol Push-sum, namely an estimation of the average value and an estimation of sum.

Cette thèse étudie l'interaction technico-économique entre véhicules électriques et réseaux d'électricité. Le développement récent de la mobilité électrique invite en effet à analyser les impacts potentiels de la recharge de ces véhicules sur les réseaux électriques, mais aussi le soutien que ceux-ci pourraient apporter dans les réseaux du futur. Ce travail s'inscrit résolument dans le cadre des réseaux d'électricité intelligents ; la plupart des résultats de cette thèse s'appliquent tout aussi bien à un lave-linge, un chauffe-eau, une télévision tant que l'on leur prête la capacité d'intelligence ! Dès lors que les décisions des consommateurs électriques flexibles interagissent, ce cadre d'étude offre un terrain de jeu propice aux outils de théorie des jeux. Ceux-ci ont un apport direct lorsque le problème considéré a un fondement stratégique, mais leur application permet aussi de proposer des solutions sur des aspects où la théorie des jeux n'est pas forcément attendue : algorithmique, dans l'échange d'information entre acteurs, etc. La description de cet apport est l'objet principal de ce travail de thèse et se décompose en trois parties. En fil rouge, le cas des profils de charge rectangulaires – soutenus par de nombreux arguments pratiques mais souvent délaissés par les chercheurs – est analysé. En premier lieu, des questions algorithmiques se posent pour coordonner la charge de véhicules électriques dans un même périmètre du système électrique. Proposant et étudiant un algorithme de coordination, il est montré comment les propriétés fondamentales de celui-ci - sa convergence, l'efficacité de ses points de convergence – peuvent être déduite d'un jeu auxiliaire sous-jacent. L'analyse de ce jeu est faite en montrant qu'il appartient à la classe des jeux de potentiel, sous des hypothèses physiques et économiques très générales. Sur le plan de l'échange d'information, un modèle est proposé pour réfléchir à la bonne communication entre un opérateur du réseau et un véhicule. Ces deux agents ont intérêt à communiquer pour planifier la charge intelligente du véhicule électrique, mais ont des objectifs distincts. Ce cadre est très proche du Cheap-talk en théorie des jeux, mais aussi de la problématique de la quantification en traitement du signal. Ce travail tisse au passage des liens entre ces sujets. Il propose aussi une méthode pour que l'agent du réseau et le véhicule s'accordent hors-ligne sur un bon mécanisme d'échange d'information. Enfin, la théorie des jeux est appliquée dans un cadre plus habituel, pour analyser le jeu des acteurs. Ceci est fait quand des ensembles de véhicules de taille importante, vus comme des flottes, cohabitent avec des véhicules individuels. Ceci offre un terrain de jeu applicatif aux outils très récents des jeux composites. Dans ces trois directions de recherche, des simulations sont effectuées dans le cadre d'un réseau de distribution d'électricité, maille du système électrique qui pourrait vivre des impacts significatifs si la charge est non-coordonnée. En particulier, elles montrent la robustesse des méthodes proposées face aux incertitudes sur les données lorsque des profils de charge rectangulaires sont considérés. / This thesis studies the technical and economical interaction between electric vehicles and electrical networks. The recent development of electric mobility leads to the analysis of potential impacts of electric vehicle charging on the electrical networks, but also to the possible support that these particular electric consumers could provide in the future smart grids. In this direction, most of the results given in this thesis also apply to a washing machine, a water-heater, a TV, as soon as these equipments are capable of being smart! When the decisions of flexible electric consumers interact, the considered framework naturally offers a unique exercise area for the tools of game-theory. The interpretation is straightforward when the considered problem is strategic by definition, but these tools allow also shedding light on other aspects: algorithmic coordination, information exchange, etc. The description of the benefits of using game-theory in this context is the aim of this work. This is done according to three aspects. In these three directions, a particular attention is drawn to the case of rectangular charging profiles, which are very practical, but often ignored by the literature. First, algorithmic issues arise when coordinating the charging of electric vehicles in a same area of the electrical network. A charging algorithm is proposed and analyzed. This is done by studying an underlying auxiliary game. This game is proved to belong to the class of potential games under very general physical and economic assumptions. In turn, it inherits from the strong properties of this class of games, namely convergence and an efficiency result in the case of a large number of electric vehicles. Considering information exchange, a model is proposed to design a good communication scheme between an operator of the electrical system and an electric vehicle. Both agents have an interest in exchanging information to schedule optimally the charging profile of the electric vehicle but they do not share the same objective. This framework is closely related to Cheap-talk in game theory and to quantization in signal processing. Amongst others, this work explains interesting connections between both topics. Furthermore, a method, which is used offline, is given to obtain a good communication mechanism between both agents. Finally, game theory is used in its traditional form, studying the strategic interaction when groups of a large number of electric vehicles – seen as fleets – coexist with individual vehicles. This allows the application of the very recent concept of composite games. In the three parts of the work, simulations are conducted in a French realistic distribution network, which could be the first part of the electrical system severely impacted by a non-coordinated charging. This highlights the robustness of rectangular charging profiles against forecasting errors on the parameters of the models.

No description available.

No description available.