Coloring random graphs and maximizing local diversity

We study a variation of the graph coloring problem on random graphs of finite average connectivity. Given the number of colors, we aim to maximize the number of different colors at neighboring vertices (i.e. one edge distance) of any vertex. Two efficient algorithms, belief propagation and Walksat are adapted to carry out this task. We present experimental results based on two types of random graphs for different system sizes and identify the critical value of the connectivity for the algorithms to find a perfect solution. The problem and the suggested algorithms have practical relevance since various applications, such as distributed storage, can be mapped onto this problem.

Distributed routing algorithms for interconnected FDDI LANS

The Fibre Distributed Data Interface (FDDI) represents the new generation of local area networks (LANs). These high speed LANs are capable of supporting up to 500 users over a 100 km distance. User traffic is expected to be as diverse as file transfers, packet voice and video. As the proliferation of FDDI LANs continues, the need to interconnect these LANs arises. FDDI LAN interconnection can be achieved in a variety of different ways. Some of the most commonly used today are public data networks, dial up lines and private circuits. For applications that can potentially generate large quantities of traffic, such as an FDDI LAN, it is cost effective to use a private circuit leased from the public carrier. In order to send traffic from one LAN to another across the leased line, a routing algorithm is required. Much research has been done on the Bellman-Ford algorithm and many implementations of it exist in computer networks. However, due to its instability and problems with routing table loops it is an unsatisfactory algorithm for interconnected FDDI LANs. A new algorithm, termed ISIS which is being standardized by the ISO provides a far better solution. ISIS will be implemented in many manufacturers routing devices. In order to make the work as practical as possible, this algorithm will be used as the basis for all the new algorithms presented. The ISIS algorithm can be improved by exploiting information that is dropped by that algorithm during the calculation process. A new algorithm, called Down Stream Path Splits (DSPS), uses this information and requires only minor modification to some of the ISIS routing procedures. DSPS provides a higher network performance, with very little additional processing and storage requirements. A second algorithm, also based on the ISIS algorithm, generates a massive increase in network performance. This is achieved by selecting alternative paths through the network in times of heavy congestion. This algorithm may select the alternative path at either the originating node, or any node along the path. It requires more processing and memory storage than DSPS, but generates a higher network power. The final algorithm combines the DSPS algorithm with the alternative path algorithm. This is the most flexible and powerful of the algorithms developed. However, it is somewhat complex and requires a fairly large storage area at each node. The performance of the new routing algorithms is tested in a comprehensive model of interconnected LANs. This model incorporates the transport through physical layers and generates random topologies for routing algorithm performance comparisons. Using this model it is possible to determine which algorithm provides the best performance without introducing significant complexity and storage requirements.

Control of second-life hybrid battery energy storage system based on modular boost-multilevel buck converter

To fully utilize second-life batteries on the grid system, a hybrid battery scheme needs to be considered for several reasons: the uncertainty over using a single source supply chain for second-life batteries, the differences in evolving battery chemistry and battery configuration by different suppliers to strive for greater power levels, and the uncertainty of degradation within a second-life battery. Therefore, these hybrid battery systems could have widely different module voltage, capacity, and initial state of charge and state of health. In order to suitably integrate and control these widely different batteries, a suitable multimodular converter topology and an associated control structure are required. This paper addresses these issues proposing a modular boost-multilevel buck converter based topology to integrate these hybrid second-life batteries to a grid-tie inverter. Thereafter, a suitable module-based distributed control architecture is introduced to independently utilize each converter module according to its characteristics. The proposed converter and control architecture are found to be flexible enough to integrate widely different batteries to an inverter dc link. Modeling, analysis, and experimental validation are performed on a single-phase modular hybrid battery energy storage system prototype to understand the operation of the control strategy with different hybrid battery configurations.

A multi-modular second life hybrid battery energy storage system for utility grid applications

The modern grid system or the smart grid is likely to be populated with multiple distributed energy sources, e.g. wind power, PV power, Plug-in Electric Vehicle (PEV). It will also include a variety of linear and nonlinear loads. The intermittent nature of renewable energies like PV, wind turbine and increased penetration of Electric Vehicle (EV) makes the stable operation of utility grid system challenging. In order to ensure a stable operation of the utility grid system and to support smart grid functionalities such as, fault ride-through, frequency response, reactive power support, and mitigation of power quality issues, an energy storage system (ESS) could play an important role. A fast acting bidirectional energy storage system which can rapidly provide and absorb power and/or VARs for a sufficient time is a potentially valuable tool to support this functionality. Battery energy storage systems (BESS) are one of a range suitable energy storage system because it can provide and absorb power for sufficient time as well as able to respond reasonably fast. Conventional BESS already exist on the grid system are made up primarily of new batteries. The cost of these batteries can be high which makes most BESS an expensive solution. In order to assist moving towards a low carbon economy and to reduce battery cost this work aims to research the opportunities for the re-use of batteries after their primary use in low and ultra-low carbon vehicles (EV/HEV) on the electricity grid system. This research aims to develop a new generation of second life battery energy storage systems (SLBESS) which could interface to the low/medium voltage network to provide necessary grid support in a reliable and in cost-effective manner. The reliability/performance of these batteries is not clear, but is almost certainly worse than a new battery. Manufacturers indicate that a mixture of gradual degradation and sudden failure are both possible and failure mechanisms are likely to be related to how hard the batteries were driven inside the vehicle. There are several figures from a number of sources including the DECC (Department of Energy and Climate Control) and Arup and Cenex reports indicate anything from 70,000 to 2.6 million electric and hybrid vehicles on the road by 2020. Once the vehicle battery has degraded to around 70-80% of its capacity it is considered to be at the end of its first life application. This leaves capacity available for a second life at a much cheaper cost than a new BESS Assuming a battery capability of around 5-18kWhr (MHEV 5kWh - BEV 18kWh battery) and approximate 10 year life span, this equates to a projection of battery storage capability available for second life of >1GWhrs by 2025. Moreover, each vehicle manufacturer has different specifications for battery chemistry, number and arrangement of battery cells, capacity, voltage, size etc. To enable research and investment in this area and to maximize the remaining life of these batteries, one of the design challenges is to combine these hybrid batteries into a grid-tie converter where their different performance characteristics, and parameter variation can be catered for and a hot swapping mechanism is available so that as a battery ends it second life, it can be replaced without affecting the overall system operation. This integration of either single types of batteries with vastly different performance capability or a hybrid battery system to a grid-tie 3 energy storage system is different to currently existing work on battery energy storage systems (BESS) which deals with a single type of battery with common characteristics. This thesis addresses and solves the power electronic design challenges in integrating second life hybrid batteries into a grid-tie energy storage unit for the first time. This study details a suitable multi-modular power electronic converter and its various switching strategies which can integrate widely different batteries to a grid-tie inverter irrespective of their characteristics, voltage levels and reliability. The proposed converter provides a high efficiency, enhanced control flexibility and has the capability to operate in different operational modes from the input to output. Designing an appropriate control system for this kind of hybrid battery storage system is also important because of the variation of battery types, differences in characteristics and different levels of degradations. This thesis proposes a generalised distributed power sharing strategy based on weighting function aims to optimally use a set of hybrid batteries according to their relative characteristics while providing the necessary grid support by distributing the power between the batteries. The strategy is adaptive in nature and varies as the individual battery characteristics change in real time as a result of degradation for example. A suitable bidirectional distributed control strategy or a module independent control technique has been developed corresponding to each mode of operation of the proposed modular converter. Stability is an important consideration in control of all power converters and as such this thesis investigates the control stability of the multi-modular converter in detailed. Many controllers use PI/PID based techniques with fixed control parameters. However, this is not found to be suitable from a stability point-of-view. Issues of control stability using this controller type under one of the operating modes has led to the development of an alternative adaptive and nonlinear Lyapunov based control for the modular power converter. Finally, a detailed simulation and experimental validation of the proposed power converter operation, power sharing strategy, proposed control structures and control stability issue have been undertaken using a grid connected laboratory based multi-modular hybrid battery energy storage system prototype. The experimental validation has demonstrated the feasibility of this new energy storage system operation for use in future grid applications.

Adaptive control of hybrid battery energy storage systems under capacity fade

There is an increasing call for applications which use a mixture of batteries. These hybrid battery solutions may contain different battery types for example; using second life ex-transportation batteries in grid support applications or a combination of high power, low energy and low power, high energy batteries to meet multiple energy requirements or even the same battery types but under different states of health for example, being able to hot swap out a battery when it has failed in an application without changing all the batteries and ending up with batteries with different performances, capacities and impedances. These types of applications typically use multi-modular converters to allow hot swapping to take place without affecting the overall performance of the system. A key element of the control is how the different battery performance characteristics may be taken into account and the how the power is then shared among the different batteries in line with their performance. This paper proposes a control strategy which allows the power in the batteries to be effectively distributed even under capacity fade conditions using adaptive power sharing strategy. This strategy is then validated against a system of three different battery types connected to a multi-modular converter both with and without capacity fade mechanisms in place.

Control of cascaded DC-DC converter based hybrid battery energy storage systems - Part II:Lyapunov approach

A cascaded DC-DC boost converter is one of the ways to integrate hybrid battery types within a grid-tie inverter. Due to the presence of different battery parameters within the system such as, state-of-charge and/or capacity, a module based distributed power sharing strategy may be used. To implement this sharing strategy, the desired control reference for each module voltage/current control loop needs to be dynamically varied according to these battery parameters. This can cause stability problem within the cascaded converters due to relative battery parameter variations when using the conventional PI control approach. This paper proposes a new control method based on Lyapunov Functions to eliminate this issue. The proposed solution provides a global asymptotic stability at a module level avoiding any instability issue due to parameter variations. A detailed analysis and design of the nonlinear control structure are presented under the distributed sharing control. At last thorough experimental investigations are shown to prove the effectiveness of the proposed control under grid-tie conditions.

Control of cascaded DC-DC converter-based hybrid battery energy storage systems - Part I:stability Issue

There is an emerging application which uses a mixture of batteries within an energy storage system. These hybrid battery solutions may contain different battery types. A DC-side cascaded boost converters along with a module based distributed power sharing strategy has been proposed to cope with variations in battery parameters such as, state-of-charge and/or capacity. This power sharing strategy distributes the total power among the different battery modules according to these battery parameters. Each module controller consists of an outer voltage loop with an inner current loop where the desired control reference for each control loop needs to be dynamically varied according to battery parameters to undertake this sharing. As a result, the designed control bandwidth or stability margin of each module control loop may vary in a wide range which can cause a stability problem within the cascaded converter. This paper reports such a unique issue and thoroughly investigates the stability of the modular converter under the distributed sharing scheme. The paper shows that a cascaded PI control loop approach cannot guarantee the system stability throughout the operating conditions. A detailed analysis of the stability issue and the limitations of the conventional approach are highlighted. Finally in-depth experimental results are presented to prove the stability issue using a modular hybrid battery energy storage system prototype under various operating conditions.