Browsing by Subject "Graph Theory"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Fast Detection and Mitigation of Cascading Outages in the Power System(2012-02-14) Pang, ChengzongThis dissertation studies the causes and mechanism of power system cascading outages and proposes the improved interactive scheme between system-wide and local levels of monitoring and control to quickly detect, classify and mitigate the cascading outages in power system. A novel method for evaluating the vulnerability of individual components as well as the whole power system, which is named as weighted vulnerability analysis, is developed. Betweenness centrality is used to measure the importance of each bus and transmission line in the modeled power system network, which is in turn used to determine the weights for the weighted vulnerability index. It features fast reaction time and achieves higher accuracy when dealing with the cascading outage detection, classification and mitigation over the traditional methods. The overload problem due to power flow redistribution after one line tripped is a critical factor contributing to the cascading outages. A parallel corridor searching method is proposed to quickly identify the most vulnerable components after tripping a transmission line. The power system topology model can be simplified into state graph after searching the domains for each generator, the commons for each bus, and links between the commons. The parallel corridor will be determined by searching the links and commons in system topology graph for the given state of power system operation. During stressed operating state, either stable or unstable power swing may have impacts on distance relay judgment and lead to relay misoperation, which will result in the power system lines being tripped and as a consequence power system operating state becoming even more stressful. At the local level, an enhanced fault detection tool during power system swing is developed to reduce the chance of relay misoperation. Comprehensive simulation studies have been implemented by using the IEEE 39-bus and 118-bus test systems. The results are promising because: The results from weighted vulnerability analysis could provide better system situational awareness and accurate information about the disturbance; The results form parallel corridor search method could identify the most vulnerable lines after power re-distribution, which will give operator time to take remedial actions; The results from new travelling wave and wavelet transform based fault detection could reduce the impact of relay misoperation.Item Network Based Approaches for Clustering and Location Decisions(2012-10-19) Verma, AnuragThe objective of this dissertation is to study commonly occurring location and clustering problems on graphs. The dissertation is presented as a collection of results in topics including finding maximum cliques in large graphs, graph clustering in large scale graphs, determining location of facilities for pre-positioning emergency relief supplies, and selecting nodes to form a virtual backbone in a wireless sensor network. To begin with, a new clique relaxation called a k-community is defined as a connected subgraph such that endpoints of every edge have at least k common neighbors within the subgraph. It is used to develop scale reduction techniques to obtain the maximum clique on very large scale real life networks. Analytically, the technique is been shown to be very effective on power-law random graphs. Experimental results on real life graph instances (Collaboration networks, P2P networks, Social networks, etc.) show our procedure to be much more effective than a regular k-core peeling approach. Next, a general purpose network clustering algorithm based on the clique relaxation concept of k-community is presented. A salient feature of this approach is that it does not use any prior information about the structure of the network. By defining a cluster as a k-community, the proposed algorithm aims to provide a clustering of a network into k-communities with varying values of k. Even though the algorithm is not designed to optimize any particular performance measure, the computational results suggest that it performs well on a number of criteria that are used in literature to evaluate the quality of a clustering. The third topic deals with choosing the locations of disaster response facilities for the storage of emergency supplies, which is critical to the quality of service provided in a large scale emergency like an earthquake. In the existing literature, large scale emergency facility location models have either assumed that disaster response facilities will always be functioning and available when required, or that the functioning of a facility is independent of a particular disaster scenario. In this paper new location models are presented that explicitly take into consideration the stochastic nature of the impact a disaster can have on the disaster response facilities and the population centers in surrounding areas. A comparison of the results obtained using our models with those from models available in literature using a case study suggests that the locations suggested by the model in this paper significantly reduce the expected cost of transportation of supplies when we consider the damage a disaster causes to the disaster response facilities and areas near it. Lastly, a distributed approximate algorithm for forming the communication backbone in wireless sensor networks is presented. Some of the most popular routing protocols for wireless sensor networks require a virtual backbone for efficient communication be- tween the sensors. Connected Dominating Sets (CDS) have been studied as a method of choosing nodes to be in the backbone. The traditional approach is to assume that the transmission range of each node is given and then minimize the number of nodes in the CDS representing the backbone. A recently introduced alternative strategy is based on the concept of k-bottleneck connected dominating set (k-BCDS), which, given a positive integer k, minimizes the transmission range of the nodes that ensures a CDS of size k exists in the network. This paper provides a 6-approximate distributed algorithm for the k-BCDS problem. The results of empirical evaluation of the proposed algorithm are also included.Item Using graph theory to resolve state estimator issues faced by deregulated power systems(2009-05-15) Lei, JianshengPower industry is undergoing a transition from the traditional regulated environment to the competitive power market. To have a reliable state estimator (SE) in the power market environment, two major challenges are emerging, i.e. to keep SE running reliably even under a contingency and to run SE over a grid with extremely large size. The objective of this dissertation is to use graph theory to address the above two challenges. To keep SE running reliably under a contingency, a novel topological approach is first proposed to identify critical measurements and examine network observability under a contingency. To advance the classical topological observability analysis, a new concept of contingency observability graph (COG) is introduced and it is proven that a power system network maintains its observability under a contingency if and only if its COG satisfies some conditions. As an application of COG, a two-stage heuristic topological approach is further developed based on the new concept of qualified COG (QCOG) to minimize the number of measurements and RTUs under the constraint that the system remains observable under any single contingency. To overcome the disadvantages of existing SE over extremely large networks, a textured distributed state estimator (DSE), which consists of the off-line textured architecture design and the on-line textured computation, is proposed based on COG and a new concept of Bus Credibility Index (BCI). The textured DSE is non-recursive, asynchronous and avoids central controlling node. Numerical tests verify that the performance of the new textured DSE algorithm improves greatly compared with existing DSE algorithms in respect of bad data detection and identification. Furthermore, the software implementation for DSE is formulated as an information integration problem over regional power markets, and is very challenging because of its size and complexity. A new concept of semantic knowledge warehouse (SKW), together with the proposed concepts of semantic reasoning software component (SRSC) and deduction credibility, is developed to implement such an information integration system.