In this thesis, a variety of different approaches are proposed to study the energy restoration problem in wireless sensor networks by one or more robots. First, we introduce an on-demand decentralized strategy performed by a robot that visits the sensors in a predefined circular order. We study it both analytically and experimentally analyzing the impact of various network parameters on network coverage, disconnection time, and time sensors have to wait to be served. We then introduce an optimal centralized approach as a benchmark to assess how close to optimal our on-demand strategy is, and we discover that, for sufficiently large networks, the on-demand strategy is indeed optimal. We then propose an even simpler mechanism where the robot simply moves blindly along the circular order, which is experimentally shown to be as efficient as the other two. The results above apply to arbitrary sensor network; we then consider a common special topology: a linear arrangement of sensors, were we propose three restoring mechanisms. We compare them experimentally discovering, once again, that the simplest approach is also the best, in most cases. We finally consider the case of multiple robots. We propose two strategies where the network is portioned among the robots and each robot takes care of a portion, and we compare those with a collaborative strategy where all robots work on the global network. The main general result of this study is that simple solutions are often as good as more sophisticated ones. In fact, a totally blind strategy where a robot simply moves around restoring energy on its way turns out to be as efficient as the best possible centralized solution for most networks.

O presente trabalho investiga metodologias para se obter automaticamente planos de restabelecimento de energia em sistemas de distribuição de energia elétrica, contemplando-se múltiplos objetivos, sendo alguns conflitantes. A redução nos índices de interrupção de energia elétrica deve ser um alvo permanente das empresas de distribuição buscando a melhoria da qualidade de fornecimento. Por outro lado, as interrupções são inevitáveis, quer para a execução de obras de manutenção preventiva, quer para obras de manutenção corretiva em virtude da ocorrência de um defeito no sistema. Depois de uma falta ter sido identificada e isolada, um plano de restabelecimento deve ser encontrado em um curto período de tempo. Devido ao problema de explosão combinatorial, técnicas de programação matemática se tornam proibitivas para esse tipo de aplicação, principalmente em sistemas de tamanho real. Por outro lado, a proposta desenvolvida de algoritmos evolucionários utilizando cadeias de grafos, têm se mostrado capaz de obter planos de restabelecimento de energia em um sistema de tamanho real no menor tempo possível. Este trabalho investiga a utilização desta metodologia para redes de grande porte sem simplificações, isto é, incluindo todas as linhas, barras e chaves do sistema. Testes são realizados em três redes de tamanhos diferentes, considerando diversos objetivos a fim de avaliar a técnica proposta. / This work investigates methodologies to automatically obtain energy restoration plans in distribution systems, involving multiple objectives that are conflicting. The reduction energy interruption indices is a permanent objective of the distribution companies in order to improve power supply. Interruptions may be carried out for maintenance or may occur due to system faults. After a fault have been identified and isolated, a restoration plan is required in a short interval of time. Due to the combinatorial explosion problem it is not possible to apply mathematical programming techniques to produce restoration plans for large networks. On the other hand, an evolutionary algorithm utilizing graph, chain has shown to be able to obtain restoration plans for real-size networks in a short interval of time. Tests are performed for three different size networks, considering several objectives to evaluate the proposed technique.

No description available.

O presente trabalho investiga metodologias para se obter automaticamente planos de restabelecimento de energia em sistemas de distribuição de energia elétrica, contemplando-se múltiplos objetivos, sendo alguns conflitantes. A redução nos índices de interrupção de energia elétrica deve ser um alvo permanente das empresas de distribuição buscando a melhoria da qualidade de fornecimento. Por outro lado, as interrupções são inevitáveis, quer para a execução de obras de manutenção preventiva, quer para obras de manutenção corretiva em virtude da ocorrência de um defeito no sistema. Depois de uma falta ter sido identificada e isolada, um plano de restabelecimento deve ser encontrado em um curto período de tempo. Devido ao problema de explosão combinatorial, técnicas de programação matemática se tornam proibitivas para esse tipo de aplicação, principalmente em sistemas de tamanho real. Por outro lado, a proposta desenvolvida de algoritmos evolucionários utilizando cadeias de grafos, têm se mostrado capaz de obter planos de restabelecimento de energia em um sistema de tamanho real no menor tempo possível. Este trabalho investiga a utilização desta metodologia para redes de grande porte sem simplificações, isto é, incluindo todas as linhas, barras e chaves do sistema. Testes são realizados em três redes de tamanhos diferentes, considerando diversos objetivos a fim de avaliar a técnica proposta. / This work investigates methodologies to automatically obtain energy restoration plans in distribution systems, involving multiple objectives that are conflicting. The reduction energy interruption indices is a permanent objective of the distribution companies in order to improve power supply. Interruptions may be carried out for maintenance or may occur due to system faults. After a fault have been identified and isolated, a restoration plan is required in a short interval of time. Due to the combinatorial explosion problem it is not possible to apply mathematical programming techniques to produce restoration plans for large networks. On the other hand, an evolutionary algorithm utilizing graph, chain has shown to be able to obtain restoration plans for real-size networks in a short interval of time. Tests are performed for three different size networks, considering several objectives to evaluate the proposed technique.

The use of a mobile charger (MC) is a popular method to restore energy in wireless rechargeable sensor networks(WRSN), whose effectiveness depends critically on the recharging strategy employed by the MC. In this thesis, we propose a novel on-line recharging mechanism strategy, called Continuous Local Learning (CLL), which predicts the current energy level of the sensor nodes and dynamically updates the schedule to visit the nodes before their batteries get depleted. The strategy is based on simple computations done by the MC with little memory requirements, and the communication is strictly local (between the MC and neighbouring nodes). In spite of its simplicity, this strategy was experimentally shown to be highly effective in keeping the network perpetually operating, ensuring that the number of sensing holes (i.e., non-operational sensors due to battery depletion) and their duration are very small at any time, and achieving immortality (i.e., no node ever becoming nonoperational) under many settings even in large networks. We also studied the flexibility of CLL under a variety of network parameters, showing its applicability in various contexts. We particularly focused on network size, data rate, sensors’ battery-capacity, and speed of the MC, and studied their impact on operational size and disconnection time under a wide range of values. The experiments indicate the fact that the effectiveness of CLL holds under all considered settings. We then compared the proposed solution with the popular class of static strategies since they share with CLL the features of simplicity, strict local communication and small memory and computational requirements. Experimental results showed that CLL outperforms these strategies in effectiveness. Not only is the number of sensors that are operational at any time higher under CLL, but the average duration of a sensing hole is also significantly lower. Finally, we studied the adaptability of CLL to a network’s sudden changes, in particular changes in data rate, which we call spikes. We studied the impact of spikes parameters on the performance of CLL. Experimental results showed that CLL is capable of reacting and adapting to these sudden changes with only a slight increase in non-operational size and disconnection time.

O restabelecimento de energia em sistemas de distribuição de energia elétrica radiais geralmente envolve a reconfiguração de redes para restaurar eletricidade à(s) área(s) fora de serviço. As principais técnicas para restabelecimento de energia em sistemas de distribuição de grande porte têm sido os algoritmos evolutivos (AEs). Após a falta ter sido identificada e a zona em falta ter sido isolada do sistema, o algoritmo deve encontrar soluções em que: 1) supra com energia o maior número de consumidores possível, 2) minimize o número de operações de chaveamentos, 3) não viole restrições operacionais do sistema, 4) reduza o total de perdas resistivas, 5) a configuração da rede seja radial e, 6) obtenha tal solução em tempo real. Este projeto emprega uma nova estrutura de dados para manipular grafos produzindo exclusivamente configurações radiais e conexas, chamada representação nó-profundidade (RNP), garantindo que todas as soluções potenciais geradas pelo algoritmo satisfaçam os itens (1) e (5). Além disso, propõe-se um AE utilizando a RNP capaz de encontrar planos de restabelecimento adequados para sistemas de distribuição de larga-escala, com milhares de chaves e barras, em tempo real. / Energy restoration in radial distribution systems usually involves the network reconfiguration to restore the electricity to the out-of-service areas. The main approaches for energy restoration in large-scale distribution systems have been the evolutionary algorithms (EAs). After a fault has been identified and isolated, the algorithm must find solutions that: 1) supply energy to the larger number of consumers, 2) reduce the number of switching operations, 3) respect operational constraints of the system, 4) reduce the amount of power losses, 5) generate exclusively radial configurations and 6) find solutions in real time. This work uses a new data structure, called node-depth encoding (NDE), to manipulate graphs producing exclusively radial and connected configurations, and guaranteeing that all potential solutions generated by the algorithm satisfy items (1) and (5). Moreover, we propose an EA using the NDE that is capable of finding adequate restoration plans in real time for large-scale distribution systems, with thousands of switches and buses.

O trabalho proposto enfoca a obtenção de planos de restabelecimento de energia de forma automática para a reenergização de redes de distribuição de energia elétrica. Assim sendo, consideram-se situações que deixam regiões do sistema sem energia. A interrupção do serviço pode ser causada por falhas no circuito de distribuição ou pela necessidade de isolar zonas do mesmo para serviços de manutenção. O restabelecimento do fornecimento da energia aos consumidores é um problema com múltiplos objetivos, alguns deles conflitantes. O problema de restabelecimento envolve funções cujas características, em geral, dificultam o uso das técnicas de programação matemática para obter planos de restabelecimento. Além disso, as propostas usando tais metodologias de programação são afetadas intensamente pelo problema de explosão combinatória. Os Algoritmos Evolucionários (AEs) têm apresentado resultados animadores para esse problema. Contudo, tais algoritmos ainda apresentam dificuldades para a rápida obtenção de planos de restabelecimento para redes de tamanho real (grande porte) de maneira a tornar possível sua aplicação em tempo real. Este trabalho propõe uma nova técnica baseada em AEs para o problema de restabelecimento. Essa proposta envolve também um nova forma de representar computacionalmente as redes de distribuição e de modificar a configuração das mesmas. Também é proposto um fluxo de carga específico para ser utilizado com a nova representação. Diversos testes são apresentados utilizando redes com diferentes tamanhos, no intuito de se avaliar a potencialidade da técnica proposta. / The proposed research focus on the automatic elaboration of plans for service restoration in electrical distribution systems. So this research considers situations that leave network regions out-of-service. The service interruption may be caused by faults in the distribution circuit or by isolation of circuit zones for maintenance task. The restoration of the energy supply to the consumers is a multiobjective problem, with a certain degree of conflict. The restoration problem considers functions whose characteristics, in general, difficult the use of mathematical programming techniques to obtain restoration plans. Moreover, the approaches using such functions are intensively affected by the combinatorial explosion problem. The Evolutionary Algorithms have shown relevant results for this problem. Nevertheless, these techniques still have difficulties to obtain restoration plans, in a fast manner, for real size networks (i.e., large size). This work proposes a new methodology based on Evolutionary Algorithms. This approach involves also a new way to computationally represent distribution networks and to modify the network configurations. A specific load flow to be used with the new representation is also proposed. Severals tests are shown, using networks with different sizes, to evaluate the potential of the proposed technique.

O restabelecimento de energia em sistemas de distribuição de energia elétrica radiais geralmente envolve a reconfiguração de redes para restaurar eletricidade à(s) área(s) fora de serviço. As principais técnicas para restabelecimento de energia em sistemas de distribuição de grande porte têm sido os algoritmos evolutivos (AEs). Após a falta ter sido identificada e a zona em falta ter sido isolada do sistema, o algoritmo deve encontrar soluções em que: 1) supra com energia o maior número de consumidores possível, 2) minimize o número de operações de chaveamentos, 3) não viole restrições operacionais do sistema, 4) reduza o total de perdas resistivas, 5) a configuração da rede seja radial e, 6) obtenha tal solução em tempo real. Este projeto emprega uma nova estrutura de dados para manipular grafos produzindo exclusivamente configurações radiais e conexas, chamada representação nó-profundidade (RNP), garantindo que todas as soluções potenciais geradas pelo algoritmo satisfaçam os itens (1) e (5). Além disso, propõe-se um AE utilizando a RNP capaz de encontrar planos de restabelecimento adequados para sistemas de distribuição de larga-escala, com milhares de chaves e barras, em tempo real. / Energy restoration in radial distribution systems usually involves the network reconfiguration to restore the electricity to the out-of-service areas. The main approaches for energy restoration in large-scale distribution systems have been the evolutionary algorithms (EAs). After a fault has been identified and isolated, the algorithm must find solutions that: 1) supply energy to the larger number of consumers, 2) reduce the number of switching operations, 3) respect operational constraints of the system, 4) reduce the amount of power losses, 5) generate exclusively radial configurations and 6) find solutions in real time. This work uses a new data structure, called node-depth encoding (NDE), to manipulate graphs producing exclusively radial and connected configurations, and guaranteeing that all potential solutions generated by the algorithm satisfy items (1) and (5). Moreover, we propose an EA using the NDE that is capable of finding adequate restoration plans in real time for large-scale distribution systems, with thousands of switches and buses.

O trabalho proposto enfoca a obtenção de planos de restabelecimento de energia de forma automática para a reenergização de redes de distribuição de energia elétrica. Assim sendo, consideram-se situações que deixam regiões do sistema sem energia. A interrupção do serviço pode ser causada por falhas no circuito de distribuição ou pela necessidade de isolar zonas do mesmo para serviços de manutenção. O restabelecimento do fornecimento da energia aos consumidores é um problema com múltiplos objetivos, alguns deles conflitantes. O problema de restabelecimento envolve funções cujas características, em geral, dificultam o uso das técnicas de programação matemática para obter planos de restabelecimento. Além disso, as propostas usando tais metodologias de programação são afetadas intensamente pelo problema de explosão combinatória. Os Algoritmos Evolucionários (AEs) têm apresentado resultados animadores para esse problema. Contudo, tais algoritmos ainda apresentam dificuldades para a rápida obtenção de planos de restabelecimento para redes de tamanho real (grande porte) de maneira a tornar possível sua aplicação em tempo real. Este trabalho propõe uma nova técnica baseada em AEs para o problema de restabelecimento. Essa proposta envolve também um nova forma de representar computacionalmente as redes de distribuição e de modificar a configuração das mesmas. Também é proposto um fluxo de carga específico para ser utilizado com a nova representação. Diversos testes são apresentados utilizando redes com diferentes tamanhos, no intuito de se avaliar a potencialidade da técnica proposta. / The proposed research focus on the automatic elaboration of plans for service restoration in electrical distribution systems. So this research considers situations that leave network regions out-of-service. The service interruption may be caused by faults in the distribution circuit or by isolation of circuit zones for maintenance task. The restoration of the energy supply to the consumers is a multiobjective problem, with a certain degree of conflict. The restoration problem considers functions whose characteristics, in general, difficult the use of mathematical programming techniques to obtain restoration plans. Moreover, the approaches using such functions are intensively affected by the combinatorial explosion problem. The Evolutionary Algorithms have shown relevant results for this problem. Nevertheless, these techniques still have difficulties to obtain restoration plans, in a fast manner, for real size networks (i.e., large size). This work proposes a new methodology based on Evolutionary Algorithms. This approach involves also a new way to computationally represent distribution networks and to modify the network configurations. A specific load flow to be used with the new representation is also proposed. Severals tests are shown, using networks with different sizes, to evaluate the potential of the proposed technique.

A elaboração de planos de restabelecimento de energia (PRE) de forma rápida, para re-energização de sistemas de distribuição radiais (SDR), faz-se necessária para lidar com situações que deixam regiões dos SDR sem energia. Tais situações podem ser causadas por faltas permanentes ou pela necessidade de isolar zonas dos SDR para serviços de manutenção. Dentre os objetivos de um PRE, destacam-se: (i) reduzir o número de consumidores interrompidos (ou nenhum), e (ii) minimizar o número de manobras; que devem ser atendidos sem desrespeitar os limites operacionais dos equipamentos. Conseqüentemente, a obtenção de PRE em SDR é um problema com múltiplos objetivos, alguns conflitantes. As principais técnicas desenvolvidas para obtenção de PRE em SDR baseiam-se em algoritmos evolutivos (AE). A limitação da maioria dessas técnicas é a necessidade de simplificações na rede, para lidar com SDR de grande porte, que limitam consideravelmente a possibilidade de obtenção de um PRE adequado. Propõe-se, neste trabalho, o desenvolvimento e implantação computacional de um algoritmo para obtenção de PRE em SDR, que consiga lidar com sistemas de grande porte sem a necessidade de simplificações, isto é, considerando uma grande parte (ou a totalidade) de linhas, barras, cargas e chaves do sistema. O algoritmo proposto baseia-se em um AE multi-objetivo e na estrutura de dados, para armazenamento de grafos, denominada representação nó-profundidade (RNP), bem como em dois operadores genéticos que foram desenvolvidos para manipular de forma eficiente os dados armazenados na RNP. Em razão de se basear em um AE multi-objetivo, o algoritmo proposto possibilita uma investigação mais ampla do espaço de busca. Por outro lado, fazendo uso da RNP, para representar computacionalmente os SDR, e de seus operadores genéticos, o algoritmo proposto aumenta significativamente a eficiência da busca por adequados PRE. Isto porque aqueles operadores geram apenas configurações radiais, nas quais todos os consumidores são atendidos. Para comprovar a eficiência do algoritmo proposto, várias simulações computacionais foram realizadas, utilizando o sistema de distribuição real, de uma companhia brasileira, que possui 3.860 barras, 635 chaves, 3 subestações e 23 alimentadores. / An elaborated and fast energy restoration plan (ERP) is required to deal with steady faults in radial distribution systems (RDS). That is, after a faulted zone has been identified and isolated by the relays, it is desired to elaborate a proper ERP to restore energy on that zone. Moreover, during the normal system operation, it is frequently necessary to elaborate ERP to isolate zones to execute routine tasks of network maintenance. Some of the objectives of an ERP are: (i) very few interrupted customers (or none), and (ii) operating a minimal number of switches, while at the same time respecting security constraints. As a consequence, the service restoration is a multiple objective problem, with some degree of conflict. The main methods developed for elaboration of ERP are based on evolutionary algorithms (EA). The limitation of the majority of these methods is the necessity of network simplifications to work with large-scale RDS. In general, these simplifications restrict the achievement of an adequate ERP. This work proposes the development and implementation of an algorithm for elaboration of ERP, which can deal with large-scale RDS without requiring network simplifications, that is, considering a large number (or all) of lines, buses, loads and switches of the system. The proposed algorithm is based on a multi-objective EA, on a new graph tree encoding called node-depth encoding (NDE), as well as on two genetic operators developed to efficiently manipulate a graph trees stored in NDEs. Using a multi-objective EA, the proposed algorithm enables a better exploration of the search space. On the other hand, using NDE and its operators, the efficiency of the search is increased when the proposed algorithm is used generating proper ERP, because those operators generate only radial configurations where all consumers are attended. The efficiency of the proposed algorithm is shown using a Brazilian distribution system with 3,860 buses, 635 switches, 3 substations and 23 feeders.