abstract: ABSTRACT This dissertation introduces a real-time topology monitoring scheme for power systems intended to provide enhanced situational awareness during major system disturbances. The topology monitoring scheme requires accurate real-time topology information to be effective. This scheme is supported by advances in transmission line outage detection based on data-mining phasor measurement unit (PMU) measurements. A network flow analysis scheme is proposed to track changes in user defined minimal cut sets within the system. This work introduces a new algorithm used to update a previous network flow solution after the loss of a single system branch. The proposed new algorithm provides a significantly decreased solution time that is desired in a real- time environment. This method of topology monitoring can provide system operators with visual indications of potential problems in the system caused by changes in topology. This work also presents a method of determining all singleton cut sets within a given network topology called the one line remaining (OLR) algorithm. During operation, if a singleton cut set exists, then the system cannot withstand the loss of any one line and still remain connected. The OLR algorithm activates after the loss of a transmission line and determines if any singleton cut sets were created. These cut sets are found using properties of power transfer distribution factors and minimal cut sets. The topology analysis algorithms proposed in this work are supported by line outage detection using PMU measurements aimed at providing accurate real-time topology information. This process uses a decision tree (DT) based data-mining approach to characterize a lost tie line in simulation. The trained DT is then used to analyze PMU measurements to detect line outages. The trained decision tree was applied to real PMU measurements to detect the loss of a 500 kV line and had no misclassifications. The work presented has the objective of enhancing situational awareness during significant system disturbances in real time. This dissertation presents all parts of the proposed topology monitoring scheme and justifies and validates the methodology using a real system event. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2015

El presente trabajo consiste en el modelamiento hidrológico e hidráulico de la quebrada Cashahuacra ubicada en el distrito de Santa Eulalia con el fin de proponer la estructura de un sistema de alerta temprana que integre estos modelos para evitar la pérdida, primordialmente, de vidas humanas. Se presenta una síntesis de los principales eventos de flujo de detritos ocurridos en dicho lugar así como un marco teórico que aborda conceptos básicos relacionados al estudio de la hidrología e hidráulica. Para el modelo hidrológico, se llevó a cabo la caracterización de la quebrada Cashahuacra y se obtuvo sus parámetros principales, así también, fue necesario la adquisición de los datos históricos de precipitación. De esta manera, el modelo hidrológico fue realizado con el software HEC-HMS versión 4.2 en colaboración con ArcGIS versión 10.2.1. y su extensión HEC-GeoHMS. Así, se pudo determinar los caudales máximos bajo los periodos de retorno de 5, 10, 20, 50, 100, 200 y 500 años. El modelo hidráulico fue desarrollado con el software FLO-2D versión PRO. Tuvo como parámetros de entrada al hidrograma calculado por el modelo hidrológico, a la topografía digital del terreno, y a parámetros reológicos como la viscosidad y el esfuerzo de cedencia. Luego, fueron obtenidas las velocidades y profundidades máximas de los periodos de retorno mencionados líneas arriba. Finalmente, se ha integrado estas dos modelaciones en la estructura de un sistema de alerta temprana frente a huaycos y se ha sugerido la implementación de un radar meteorológico para la quebrada en estudio. / The present work consists of hydrological and hydraulic modeling of the Cashahuacra stream located in the Santa Eulalia district in order to propose the structure of an early warning system that integrates these models to avoid the loss, primarily of human lives. A synthesis of the main debris flow events occurring in that place is presented as well as a theoretical framework that addresses basic concepts related to the study of hydrology and hydraulics. For the hydrological model, the characterization of the Cashahuacra stream was carried out and its main parameters were obtained, as well as the acquisition of the historical precipitation data. In this way, the hydrological model was made with the HEC-HMS software version 4.2 in collaboration with ArcGIS version 10.2.1. and its HEC-GeoHMS extension. Thus, it was possible to determine the maximum flow rates under the return periods of 5, 10, 20, 50, 100, 200 and 500 years. The hydraulic model was developed with the FLO-2D PRO version software. It had as input parameters to the hydrograph calculated by the hydrological model, to the digital topography of the land, and to rheological parameters such as viscosity and yield strength. Then, the maximum speeds and depths of the return periods mentioned above were obtained. Finally, these two models have been integrated into the structure of an early warning system against hurricanes and the implementation of a meteorological radar for the stream under study has been suggested. / Tesis

Worst-case analysis is often meaningless in practice. Some problems never reach the anticipated worst-case complexity. Other solutions get bogged down with impractical constants during implementation, despite having favorable asymptotic running times. In this thesis, we investigate these contrasts in the context of finding maximum flows in planar digraphs. We suggest analytic techniques that adapt to the problem instance, and present a structural property that concludes equivalence between shortest paths and maximum st-flow in planar graphs. The best known algorithm for maximum st-flow in directed planar graphs is an augmenting- paths algorithm with O(n) iterations. Using dynamic trees, each iteration can be implemented in O(log n) time. Long before, Itai and Shiloach showed that when s and t are on the boundary of a common face, the O(n)-iteration augmenting-paths algorithm is equivalent to Dijkstra's algorithm in the graph���s dual: the max st-planar st-flow problem can be solved with one single-source shortest-path computation. In this thesis we show that (a) when s and t are separated by p faces, the max st-flow can be found with at most 2p single-source shortest-path computations, which, using the linear-time shortest-paths algorithm for planar graphs, results in an O(np)-time algorithm, and (b) that the equivalence between augmenting-paths and Dijkstra's extends to the most general non-st-planar digraphs, using their half-infinite universal cover graph. / Graduation date: 2013

As structure and size of electric power distribution systems are getting more complex, distribution automation schemes become more attractive. One of the features that is desirable in an automated system is feeder reconfiguration for loss reduction. Loss reduction can make considerable savings for a utility and results in released system capacity. There is also improved voltage regulation in the system as a result of reduced feeder voltage drop. In this thesis, multi branch exchange algorithm is introduced to solve the network reconfiguration for loss reduction problem. The proposed technique is based on heuristic techniques applied to constraint satisfaction optimization problems. A critical review of earlier methods related with feeder reconfiguration is presented. A computer program was developed using Matlab to simulate this algorithm and results of simulations demonstrate its advantages over single branch exchange method. Moreover, the results show that the final configuration is independent of the initial configuration and give assurance that any solution offered will have a radial configuration with all loads connected.

In this thesis, we proposed a delay limited routing scheme in wireless ad hoc networks. When nodes transmit packets in wireless ad hoc networks, most people think the one-hop way is better than the multi-hop way in reducing the delay time. Since most cases in wireless ad hoc networks are not single sources, we should consider at least two sources transmitting packets at the same time and then use the multi-hop way in order to reduce the energy consumption. We want to maximize the throughput with limited delay. Our contribution is to transform the optimal scheduling problem in wireless ad hoc networks to the classic maximum flow problem. The maximum flow approach does maximize the throughput and can get the optimal solution.

The objective of this work is to investigate the algorithm design and the programming model of multi-threaded computing. Designing multi-threaded algorithms is very challenging - when multiple threads need to communicate or coordinate with each other, efficient synchronization support is needed. However, synchronizations are known to be expensive on the emerging multi-/many-core processors, especially when the number of threads increases. To fully unleash the power of such processors, carefully investigations are needed in both algorithm design and programming models for multi-threaded systems. In this dissertation, we first present an asynchronous multi-threaded algorithm for the maximum network flow problem. This algorithm is based on the classical push-relabel algorithm and completely removes the use of locks and barriers from its original parallel version. While this algorithmic method shows effectiveness, it is challenging to generalize the success to other multi-threaded problem. We next focus on improving the transactional memory, a promising mechanism to construct multi-threaded programs. A queuing-theory-based model is developed to analyze the performance of different transactional memory systems. Based on the results of the model, we emphasize on the contention management mechanism of transactional memory systems. A profiling-based adaptive contention management scheme is finally proposed to cope with the problem that none of the static contention management schemes can keep good performance on all platforms for all types of workload. From this research, we show that it is necessary and worthwhile to explore both the algorithm design aspect and the programming model aspect for multi-thread computing.

Darbo apimtis: magistrantūros studijų baigiamasis darbas 46 puslapių, 25 paveikslai, 11 lentelių, 37 literatūros šaltiniai. Tiriamojo darbo objektas: Mituvos upės baseinas. Tiriamojo darbo tikslas: atlikti preliminarų potvynių rizikos įvertinimą, nustatyti maksimalius debitus, esant skirtingoms potvynių tikimybėms bei nustatyti Mituvos upės slėnio teritorijas, kurios gali būti užtvindytos atitinkamų tikimybių potvynio metu. Tiriamojo darbo uždaviniai: 1. surinkti Mituvos upės baseino hidrologinių stebėjimų duomenis; 2. aptarti hidrologiniams skaičiavimams ir modeliavimui naudojamą programinę įrangą ir pasirinkti tiriamam atvejui tinkamiausią; 3. nustatyti maksimalius debitus naudojant programinę įrangą; 4. apskaičiuoti tarpinius maksimalius debitus naudojant empirines formules; 5. sukurti Mituvos upės dalies hidrodinamikos (1D) modelį ir sumodeliuoti užliejamas teritorijas, esant skirtingų tikimybių potvyniams. Tiriamojo darbo metodika: Mituvos upės hidrologiniai duomenys surinkti iš Lietuvos hidrometeorologijos tarnybos (LHMT) (1986 – 2010 metų) ir hidrologijos metraščių nuo 1954 iki 1985 metų. Literatūros apžvalgos skyrius rašomas, analizuojant praeityje vykusius potvynius bei šiuo metu taikomus metodus, siekiant sumažinti jų padaromą žalą. Išsamiai išanalizuojama naudojama programinė įranga, apskaičiuojami maksimalūs debitai, susisteminami gauti rezultatai, parengiamos išvados. Tiriamojo darbo rezultatai: 1. Naudojant programinę įrangą „HYFRAN“ nustatyti maksimalūs... [toliau žr. visą tekstą] / Final work of University Master thesis: 46 pages, 25 figures, 11 tables, 37references sources. Object of the research: Mituva river basin. Aim of the research: to perform a preliminary flood risk assessment: determine the maximum flow rate of different return period (10, 100 and 1000 year), develop 1D hydrodinamic model for flood mapping of part of Mituva river. Objectives of the research: 1. Create annual peak flow time series using of gauging stations on Mituva river; 2. Review the general methods and software for processing of hydrological data series; 3. Determine the maximum flow rate for different return periods using data series; 3. Calculate intermediate maximum flow rate along river using the empirical formulas; 5. Develop 1D hydrodynamic model and perform river flow modeling for flood mapping purposes. Methods of the research: Mituva of the river hydrologic data collected from the Lithuanian Hydrometeorological Service (LHS) (1986 - 2010 years) and hydrological yearbooks from 1954 to 1985. Literature review section describes the analysis of a history of flooding, and the methods used to minimize the damage caused. For detailed analysis the software to calculate the maximum flow is used, the results obtained are systemized, the conclusions drawn. Results of the research: 1. Using software HYFRAN the maximum Mituva river flow rates at Žindaičiai and Vertimai VMS- by Q0,1%= 135 m3/s and Q0,1%= 176 m3/s, Q1%= 101 m3/s and Q1%= 132 m3/s, irQ10%= 65,7 m3/s and Q10%= 86... [to full text]

Throughout United States and world history, disasters have caused not only significant loss of life, property but also enormous financial loss. The tsunami that occurred on December 26, 2004 is a telling example of the devastation that can occur unexpectedly. This unexpected natural event never happened before in this area. In addition, there was a lack of an emergency response plan for events of that magnitude. Therefore, this event resulted not only in a natural catastrophe for the people of South and Southeast Asia, but it is also considered one of the greatest natural disasters in world history. After the giant wave dissipated, there were more than 230,000 people dead and more than US$10 billion in property damage and loss. Another significant event was the terrorist incident on September 11, 2001 (commonly referred to as 9/11) in United States. This event was unexpected and an unnatural, i.e., man-made event. It resulted in approximately 3,000 lives lost and about US$21 billion in property damage. These and other unexpected (or unanticipated) events give emergency management officials short- or no-notice to prevent or respond to the situation. These and other facts motivate the need for better emergency evacuation route planning (EERP) approaches in order to minimize the loss of human lives and property in short- or no-notice emergency situations. This research considers aspects of evacuation routing that have received little attention in research and, more importantly, in practice. Previous EERP models only either consider unidirectional evacuee flow from the source of a hazard to destinations of safety or unidirectional emergency first responder flow to the hazard source. However, in real-life emergency situations, these heterogeneous, incompatible flows occur simultaneously over a bi-directional capacitated lane-based travel network, especially in short- and no-notice emergencies. After presenting a review of the work related to the multiple flow EERP problem, mathematical formulations are presented for the EERP problem where the objective for each problem is to identify an evacuation routing plan (i.e., a traffic flow schedule) that maximizes evacuee and responder flow and minimizes network clearance time of both types of flow. In addition, we integrate the general human response behavior flow pattern, where the cumulative flow behavior follows different degrees of an S-shaped curve depending upon the level of the evacuation order. We extend the analysis to consider potential traffic flow conflicts between the two types of flow under these conditions. A conflict occurs when flow of different types occupy a roadway segment at the same time. Further, with different degrees of flow movement flow for both evacuee and responder flow, the identification of points of flow congestion on the roadway segments that occur within the transportation network is investigated.

Em virtude da existência de falhas em séries históricas hidrológicas ou até mesmo da não existência de dados monitorados nas bacias de interesse, a regionalização hidrológica se configura como uma ferramenta propícia para preencher essa lacuna, tornando-se útil para o conhecimento e a gestão dos recursos hídricos. Existe na literatura da hidrologia uma gama de metodologias que abordam a regionalização de dados ambientais, como a análise de agrupamento, a curva de permanência, a regressão múltipla, entre outros. No entanto, o objetivo do presente trabalho foi regionalizar vazões máximas a partir do hidrograma unitário instantâneo geomorfológico em bacias embutidas, com inserção da geometria hidráulica e geometria fractal. Para tal, propõe-se uma metodologia, inserindo ao modelo do Hidrograma Unitário Instantâneo Geomorfológico (GIUH), novos parâmetros de “entrada”, a geometria hidráulica (GH), a geometria fractal (GF) e a precipitação média anual (Pma). Aplicou-se esta metodologia na bacia do rio Ijuí, localizada na região noroeste do Estado do Rio Grande do Sul. Para isto, foram necessárias as seguintes etapas de trabalho: determinar o comportamento pluviométrico da bacia em estudo; determinar as relações matemáticas (expoentes e coeficientes) da GH na seção transversal do exutório de cada bacia; determinar os valores da GF para cada bacia e inserir as informações da GH e da GF no GIUH. Os dados utilizados no presente estudo (dados de precipitações diárias, perfil topobatimétrico das seções, dados diários de cota, e dados diários de vazões e medições de vazões medidas em campo) foram observados e medidos em nove sub-bacias embutidas à bacia do rio Ijuí, monitoramento realizado por CPRM e IPH-UFRGS. Estes dados foram utilizados para determinar a precipitação média anual, parâmetros (expoentes e coeficientes) de GH e de GF. Com dados observados de sete eventos, ocorridos simultaneamente nas respectivas bacias, calibrou-se o modelo GIUH. Após calibrado o modelo, através de uma regressão multivariada, foram ajustadas equações lineares e potenciais que relacionam (velocidade) com parâmetros de GH, GF e Pma, visando regionalizar que é um parâmetro de entrada para a geração do GIUH. Com a inserção destes novos parâmetros validou-se o modelo, aplicando-o em outro evento distinto, no qual se pode observar que o modelo apresentou bons resultados quando comparado com os valores observados. / Because of the lack in hydrological time series or even the shortage of monitored data in the basins of interest, hydrological regionalization is configured as a good tool to fill this shortage, making it useful for water resource understanding and its management. In hydrology, there are methodologies that address the regionalization of environmental data, such as cluster analysis, the flow duration curve, multiple regression, etc. However, the main objective of this study is to develop a method of regionalization to estimate peak flows in watersheds. Thus, a method to use the model Geomorphological Instant Unit Hydrograph (GIUH), with the insertion of new input parameters, that is, hydraulic geometry (HG), fractal geometry (FG) and mean annual rainfall (Pma) was proposed. As a case study, this method was applied to the Ijuí river basin, located in the northwestern region of Rio Grande do Sul State. For this, several specific objectives were: Verification of the spatial homogeneity of the rainfall regime in the basin; determination of the mathematical relationships of HG in the cross section of outfall of each basin; determination of FG values for each basin; insertion of HG and FG information into GIUH. The data used in this study (daily rainfall data, cross sections profile, daily water-level data, daily discharge data) were observed and measured in nine embedded sub-basins inside the Ijuí river basin. The monitoring was carried out by CPRM and IPH-UFRGS. These data were used to determine the Pma, parameters (exponents and coefficients) of HG and FG. With data observed in seven events, occurred simultaneously in the respective basins, the GIUH model was calibrated. After the model calibration, linear and potential equations relating (speed) with parameters of HG, FG and Pma, that aimed to regionalize which is an input parameter for the generation of GIUH, were adjusted through a multivariate regression. With the insertion of these new parameters, the model was validated in another distinct event occurred in the basin, in which it can be observed the model showed good results when compared with observed values.

Em virtude da existência de falhas em séries históricas hidrológicas ou até mesmo da não existência de dados monitorados nas bacias de interesse, a regionalização hidrológica se configura como uma ferramenta propícia para preencher essa lacuna, tornando-se útil para o conhecimento e a gestão dos recursos hídricos. Existe na literatura da hidrologia uma gama de metodologias que abordam a regionalização de dados ambientais, como a análise de agrupamento, a curva de permanência, a regressão múltipla, entre outros. No entanto, o objetivo do presente trabalho foi regionalizar vazões máximas a partir do hidrograma unitário instantâneo geomorfológico em bacias embutidas, com inserção da geometria hidráulica e geometria fractal. Para tal, propõe-se uma metodologia, inserindo ao modelo do Hidrograma Unitário Instantâneo Geomorfológico (GIUH), novos parâmetros de “entrada”, a geometria hidráulica (GH), a geometria fractal (GF) e a precipitação média anual (Pma). Aplicou-se esta metodologia na bacia do rio Ijuí, localizada na região noroeste do Estado do Rio Grande do Sul. Para isto, foram necessárias as seguintes etapas de trabalho: determinar o comportamento pluviométrico da bacia em estudo; determinar as relações matemáticas (expoentes e coeficientes) da GH na seção transversal do exutório de cada bacia; determinar os valores da GF para cada bacia e inserir as informações da GH e da GF no GIUH. Os dados utilizados no presente estudo (dados de precipitações diárias, perfil topobatimétrico das seções, dados diários de cota, e dados diários de vazões e medições de vazões medidas em campo) foram observados e medidos em nove sub-bacias embutidas à bacia do rio Ijuí, monitoramento realizado por CPRM e IPH-UFRGS. Estes dados foram utilizados para determinar a precipitação média anual, parâmetros (expoentes e coeficientes) de GH e de GF. Com dados observados de sete eventos, ocorridos simultaneamente nas respectivas bacias, calibrou-se o modelo GIUH. Após calibrado o modelo, através de uma regressão multivariada, foram ajustadas equações lineares e potenciais que relacionam (velocidade) com parâmetros de GH, GF e Pma, visando regionalizar que é um parâmetro de entrada para a geração do GIUH. Com a inserção destes novos parâmetros validou-se o modelo, aplicando-o em outro evento distinto, no qual se pode observar que o modelo apresentou bons resultados quando comparado com os valores observados. / Because of the lack in hydrological time series or even the shortage of monitored data in the basins of interest, hydrological regionalization is configured as a good tool to fill this shortage, making it useful for water resource understanding and its management. In hydrology, there are methodologies that address the regionalization of environmental data, such as cluster analysis, the flow duration curve, multiple regression, etc. However, the main objective of this study is to develop a method of regionalization to estimate peak flows in watersheds. Thus, a method to use the model Geomorphological Instant Unit Hydrograph (GIUH), with the insertion of new input parameters, that is, hydraulic geometry (HG), fractal geometry (FG) and mean annual rainfall (Pma) was proposed. As a case study, this method was applied to the Ijuí river basin, located in the northwestern region of Rio Grande do Sul State. For this, several specific objectives were: Verification of the spatial homogeneity of the rainfall regime in the basin; determination of the mathematical relationships of HG in the cross section of outfall of each basin; determination of FG values for each basin; insertion of HG and FG information into GIUH. The data used in this study (daily rainfall data, cross sections profile, daily water-level data, daily discharge data) were observed and measured in nine embedded sub-basins inside the Ijuí river basin. The monitoring was carried out by CPRM and IPH-UFRGS. These data were used to determine the Pma, parameters (exponents and coefficients) of HG and FG. With data observed in seven events, occurred simultaneously in the respective basins, the GIUH model was calibrated. After the model calibration, linear and potential equations relating (speed) with parameters of HG, FG and Pma, that aimed to regionalize which is an input parameter for the generation of GIUH, were adjusted through a multivariate regression. With the insertion of these new parameters, the model was validated in another distinct event occurred in the basin, in which it can be observed the model showed good results when compared with observed values.