Laurent Garnier
email: laurentgarnier@cea.fr

Daniel Chatroux

AC or DC fast charging solutions?

Standard charge for electric vehicle is an AC charge for some kilowatts. For fast charging, DC charge with an external charger is frequently developed. The investments for the deployment of DC chargers can be supported by car manufacturers as TESLA or by collectivities. The major aim of this paper is to present the results and conclusions of two projects about the question of AC or DC fast charging solutions. The first one, ElLiSup (bus application) is a national project in France, the second project is ESPRIT (electric vehicles application), an H2020 European project. The second goal is to compare the different existing fast charging solutions and to propose new potential solutions for the next years.

Context

The CEA (Commissariat à l'Energie Atomique et aux Energies Alternatives) is an energy technological research center in France dedicated to research and development in two domains: nuclear energy and renewable energy. Some of the research interests in Grenoble LITEN institute from CEA are hybrid and electrical vehicles. All the value chain is concerned for the research activities from raw material to battery systems integration in the applications: materials for Lithium ion accumulators, accumulator and battery packs design, battery management systems, electric vehicle integration, hybridization with fuels cells and monitoring of vehicles.

Projects experience return 1.1 ElliSup project (DC charging station)

ElLiSup [2] was a national research project in France to develop notably a pure electric bus with fast charge at the end of the line. The main idea of the concept was to limit the embedded battery size thanks to a 5 minutes "fast and partial" charge of the battery at the end of the line. This concept allows embedding only 1 ton of battery instead of 3 tons for classical solution.

To test this concept, a 350 kW station has been studied and realized.

Regarding power, only two cables (DC voltage) are connected to the bus thanks a pantograph.

The charger is connected to the AC grid through a high voltage transformer (15kV/400V). , filter, and nine buck converters in parallel to charge the bus. The power electronics cabinet (Fig. 2), located in a charging station is constituted of 9 bidirectional DC-DC converters set in parallel. After years, we continue to ask questions about the best solution for the fast charge of the bus. Another solution is the use of a 3-phase and earth connection pantograph with integrated chargers on the bus. For some topologies, it is possible to minimize the cost of the embedded chargers by the reuse of the motors inverters to provide the charging function. The earth link and the control of this earth connection is necessary to ensure safety. With this solution, the charging infrastructure is a much lower cost and higher reliability one because it is limited to an AC distribution network without power electronic converters. .

ESPRIT project (AC charging station)

ESPRIT European project aims to develop small car sharing electric vehicles able to be connected together as a road train with singletrack behavior (all the wheels of vehicles are in the same line). The goal of this road train is to redistribute vehicles at the good place at the good time to maximize the usage. Driving in road train is very simple thanks to single-track behavior. Two cars connected have the same size as a small car making easier the parking in urban area where ground surface is expensive.

Energy exchanges are possible between vehicles (Fig. 6) to have more energy in the first vehicle of the train, because it will be the first vehicle for the future run.

Only one charging station is used to charge the complete road train. Initially, at the beginning of the project, DC charging has been chosen. The initial concept was to charge the train on existing 50 kW DC charger for cars. For the deployment of the solution, the cost of the standard DC fast charge station appears as a limitation for cities who wanted only to use the existing AC charging stations and not to pay additional DC charging stations. Activities about electric architectures for cars and car in train are still in evolution in this project, but AC charge is definitively chosen because of the much lower infrastructure costs.

Standard and fast charging 3.1. Main questions about charging

To choose the right and best charging solution, there are several questions to address:

 Is fast charging really necessary for the application and if yes which level of power do we need exactly?  Is insulation required?  Is bidirectionality required?  What kind of intelligence do we need?

(power adaptation depending on battery and electricity network capabilities)  And finally what is the best solution: AC or DC input? In the following chapters, we will mainly deal with the last question concerning AC or DC inputs.

Standardization of charging

Electric vehicles charging solutions are split in four modes ( [START_REF] Das | Electric vehicles standards, charging infrastructure, and impact on grid integration : a technological review[END_REF], [START_REF] Hanauer | Mode 2 charging -Testing and certification for Internationnal market access : May 2028[END_REF]). The main differences concerning input, power, communication and protections are reported in the following table and graph on Fig. 8.

Standard charging

Standard charge of electric vehicles is usually based on an isolated embedded charger of some kilowatts. For example, single phase 3kW charger can be used for a standard plug connection (mode 1 or 2) or 22kW three phases charger for a wallbox plug connection. For standard plug connection, an interface is used inside the cable to provide additional protections. For wallbox the interface electronic is included in the wallbox. The main function is the control of the earth connection link of the vehicle.

This electronic communicates with the vehicle by the cable. A contactor isolates the plug from the main and is activated only after some safety controls: vehicle detection, cable earth connection to the vehicle, earth current level. The value of the maximum power available from the network is transmitted to the embedded charger in order to adapt the charging current at the right level. The IEC 61851-1:2000 standard describes the J1772 protocol.

Classically, standard chargers are isolated ones to minimize the part of the vehicle connected to the grid. Then the over-voltages and spikes that could occur are not directly transmitted to the battery, the powertrain inverter and auxiliaries. Besides, common mode Y capacitors of EMC filters connected to powertrain inverters and auxiliaries do not create earth line current. The value of these capacitors are not anymore limited by earth connection maximum current constraint.

Fast charging

For fast charging, the order of magnitude is twenty to hundreds of kilowatts to charge the battery in some tens of minutes which is in accordance with Lithium-ion batteries capacities. For example, the Li-ion batteries handheld power tools have a charging time of 20 to 30 minutes. An important question is the impact of the rate of charge on battery lifetime. This impact is very dependent of the temperature. It is well known than Lithium-ion accumulator lifetime decreases at high temperature, especially in the range above 35-45°C. But also charges at low temperature have a big impact. In battery domain low temperatures start below 0°C or +5°C depending on the technologies [START_REF] Chatroux | Electrochemical Battery Managements and Applications, Key Note paper PCIM[END_REF]. Since the battery temperature rises when charged at high power and To avoid lifetime problems, thermal management systems are frequently used to adjust the temperature during fast charging sequences.

Standard DC fast charging

For DC current fast charging (mode 4), the two battery poles are connected to the plug or to another connection contacts as pantographs for buses or trucks. The additional components on vehicles are only contactors and safety electronic functions. All the main functions are in the charging station. It's necessary to provide a regulated DC current limited to the maximum battery one. The maximum battery current depends on the technology, state of charge and temperature of the battery. This information is provided by the BMS (Battery Management System) to the charging station. Charging station are also usually isolated. The output current is isolated from the main in order to be adapted with all the vehicles, independently of the insulation performances and filter capacitors on the vehicle side. Main's over-voltages and spikes are limited by the electro technical solutions or power electronics components installed on the primary side of the transformer, so the secondary voltage is protected. The advantage of this solution is that the fast charger is outside of the vehicle, thus there is no overweight and over-cost to embed inside the vehicle. But the main drawback is the cost (ratio between 5 and 10 between AC and DC charging station) of infrastructure which has to be supported by collectivity or private companies. Because of all the power electronic, the reliability is much lower with greater impact. The failure of the charger affects the charging station and all the vehicles around, and not only one vehicle. Another drawback, less important but still significant, is the weight of the plug. In fact with three poles (AC solution), it is much easier to transfer high currents than with two poles (DC solution).

Standard AC fast charging

With standard AC fast charging (mode 3), the charger is embedded inside the vehicle, to provide the DC controlled and regulated current to the battery. The main drawback is the high power converter embedded inside the vehicle, increasing cost and weight. AC fast charging is the standard solution for fast charge within the range of some tens of kilowatts. Classical solution is a 3 phases AC to DC 22kW isolated embedded charger. .

Other AC fast charging solutions

Since almost ten years, car manufacturers and their suppliers try to find solutions in order to perform fast charge without integrating a high power charger with high cost. The main idea is to re-use the inverter and motors inductances to provide a high power charging function. Indeed, the maximum power of the inverter is usually in the range of what we need for fast charging.

Thus it is a very attractive solution because it could allow to remove a high power converter. Nevertheless, despite Renault which has already integrated this kind of solution, it seems that on the market there is no other electric vehicles manufacturers making the same kind of choice.

Renault solution

In ZOE electric car from Renault [3], the charger is a not isolated one. Power electronics charger is based on the reused of a part of the inverter and electric motor of the power train. There is no communication on this patented technology used. The electrical architecture seems to be based on a controlled rectifier with IGBT in series with diodes to supply the three motor inductances by the common point of this inductances, and the IGBT bridges of the inverter used as a boost. The only added part to provide the global charging function is the controlled rectifier.

One first drawback of this circuit is capacitors on the alternative input. At low power, for example for a 3 kW charge, the reactive current in the input capacitors is important. Because of the wide power range of the converter a poor efficiency at low power was observed on the first generation of the ZOE. For the second generation of the vehicle, maximum charge power decreased from 44 kW to 22kW, which improved its performances during lower power charge.

Valeo solution (SOFRACI structure)

Fig 11 shows the VALEO solution. If the number of switches rises and the motor design is complicated due to middle point on motor inductances, it offers some advantages. The structure provides a better power factor correction thanks to the full bridge and is bidirectional. This last point is a mandatory requirement for the next years to reuse the batteries of the cars for energy storage, for V2G and V2H applications.

New proposals for fast charging

In the last chapter, two solutions, which use inverters in traction and charging mode, have been presented. These solutions are very interesting because they allow the re-use of power electronics components. But the common mode parasitic capacitances of the motor create high level of electromagnetic perturbations that are difficult to manage.

In CEA laboratories, a simple single stage solution is currently studied. Motor inductances aren't re-used which decreases drastically the parasitic capacitance but also makes the use of an added filter mandatory. With SiC inverter the size of this filter can be reduced. Contactors are also necessary for isolation of the motor or the battery pack. It is a very simple one but which obliges to work with higher voltage battery packs. This last presented solution is also very interesting but various disadvantages have to be overcomed. The BMS is bigger due to higher voltage; thermal and aging impacts of high frequency currents in the battery have to be precisely evaluated; electromechanical contactors to disconnect the battery to the inverter seem to be necessary. Nevertheless, if all drawbacks are taken into account and if intelligent mitigation solutions are implemented, we have a very attractive single stage converter, which simplifies drastically the global architecture and reduce the global cost of electric vehicle with a bidirectional charger.

Conclusion

Standard charge is based on AC charging embedded in vehicle, mainly by isolated chargers. Direct Current charge is simple from vehicle side but the cost of the charger is transfer to an external infrastructure. Then, the question is to know who wants to pay this cost and to provide the maintenance for years. For our point of view, in most of applications, the cost of those infrastructures will drive vehicle manufacturers in the direction of AC fast charging. This conclusion becomes much more relevant if power electronics community finds efficient solutions to combine inverter and charger. Until now, only few solutions have been tested but they were not completely accepted as standard for electric vehicle. The challenge of combining inverter and charger is high because that would enable to remove a high power converter from the Bill of Material of the electric vehicle. In such case, we could also imagine having higher power AC fast charging solutions, if of course there is no impact or limited impact on the aging of the battery.

Fig. 1 :

 1 Fig. 1: ElliSup project

Fig. 2 :

 2 Fig. 2: Power Electronis Cabinet

Fig. 4 :Fig. 5 :

 45 Fig. 4: ESPRIT concept

Fig. 3 :Fig. 6 :

 36 Fig. 3: Power electronics architecture

Fig. 9 :

 9 Fig. 9: Mennekes cable

Fig. 7 :

 7 Fig. 7: Different charging modes

Fig. 10 :Fig. 12 :

 1012 Fig. 10: Renault patent [3] -Non isolated charger with sharing of inverter bridge


Landy Andriamampianina
email: landy.andriamampianina@activus-group.fr

Directeur De Thèse

Toward a generic approach to capture the temporal evolution in graphs

Keywords: temporal graphs, historization mechanism, evolution types. MOTS-CLÉS : graphes temporels, mécanisme d'historisation, types d'évolution

Introduction

Many domains, such as -computer networks, social networks, communication networks, biological networks etc. -are modelled as a graph as its flexible structure allows naturally representing complex relations among interconnected entities. In its most basic form, a graph is a collection of nodes with directed or undirected edges connecting them. The basic graph form is static, that is, it only reflects the snapshot1 of a graph at a given time. However, real-world graph-based applications evolve constantly over time. Static graphs fail to represent, manage and trace their changes through time. Some studies have introduced the concept of temporal graphs to model the temporal evolution of graphs. Compared to static graphs, temporal graphs allow to model some evolution types in some specific applications. The purpose of our work is to propose a generic solution to manage any type of temporal evolution for any graph-based application.

State of the Art

A temporal graph is a graph representing nodes and edges, as well as all other parameters that the graph can have according to a model, that can be modified over time. The temporal evolution of a graph refers to the changes on its parameters over time, namely (i) its topology2 and (ii) data3 [START_REF] Zaki | Comprehensive Survey on Dynamic Graph Models[END_REF].

The temporal evolution of graph topology is discussed in the literature through the addition and deletion of nodes and edges over time [START_REF] Kostakos | Temporal graphs[END_REF]. Regarding the temporal evolution of graph data, it is discussed in the literature through changes in the attributes value of nodes [START_REF] Desmier | Cohesive co-evolution patterns in dynamic attributed graphs[END_REF] or edges [START_REF] Zhao | Temporal paths discovery with multiple constraints in attributed dynamic graphs[END_REF] over time.

The standard temporal graph model in the literature is the sequence of graph snapshots4 . It consists in splitting time into slices and then create a snapshot of the graph for each time slice [START_REF] Fard | Towards Efficient Query Processing on Massive Time-Evolving Graphs[END_REF]. Other studies model the temporal evolution of the graph by attaching to nodes and edges their presence times instead of attaching time to the whole graph [START_REF] Latapy | Stream Graphs and Link Streams for the Modeling of Interactions over Time[END_REF].

In a nutshell, according to their applications, current modelling solutions include the temporal evolution of topology or data or both to track the temporal evolution of a graph. Most of them are based on the snapshot-based approach to keep temporal evolution traces.

Research questions

The first problem we want to address in our research is the representation of multiple types of the temporal evolution of a graph-based application. The state of the art shows that existing temporal graph models capture partially the temporal evolution of a graph. To the best of our knowledge, they do not capture the temporal evolution of graph data structure. Yet, this evolution type is a new information source that can enrich the evolution analysis of an application. As an example, we consider a social network where users and their relationships are respectively represented by nodes and edges in a temporal graph. Nodes and edges have attributes to describe users and their relationships characteristics. When a user adds a new friend, it creates a new edge in the graph modifying the graph topology and it updates the value of the attribute "friends list" of the user. When a user gets a job for the first time, a new attribute called "job status" should be added to its attributes set. This information can be new knowledge to understand evolution trends in the social network. For instance, the time when an important increase in the number of friends of a user may be correlated with the time when he added its job status, meaning that he possibly made new professional relationships. Therefore, some applications may require the complete aspect of temporal evolution i.e. the temporal evolution of graph topology, graph data and graph data structure. In this context, the first research question we want to answer is how to extend and generalize existing temporal graph concepts to be generic enough for capturing any evolution type and be reusable in any temporal graph based application.

The second problem we want to address in our research is the historization mechanism of temporal graph models. The snapshots-based model is the most used approach but it does not provide a straightforward solution to track and keep changes in a graph.

To ensure the extraction of significant information on temporal evolution, it requires on the one hand to choose relevant time slice durations, which is a research topic itself [START_REF] Ribeiro | Quantifying the effect of temporal resolution on time-varying networks[END_REF]. On the other hand, it requires observing differences between two snapshots of the graph. Then it is difficult to track the individual temporal evolution of nodes and edges. The drawbacks of snapshots-based approaches are due to the fact that the temporal evolution is treated at the level of the entire graph. In this context, the second research question we want to answer is how to track and keep evolution traces at different graph levels (node, edge and graph) contrary to existing snapshot-based approaches.

Proposition and future actions

The objective of this thesis is to design concepts and formalisms for the development of applications based on temporal graphs. To do so, we study two research axis: the modelling and the manipulation of temporal graphs.

First of all, we focused on the modelling of temporal graphs. To meet the shortcomings of the state of the art, our objective is to propose a modelling solution based on the concepts of temporal entities, temporal relationships, instances and states. We give an outline of our model in the following paragraph.

We define a temporal graph as representing evolving entities and relationships in time called respectively temporal entities and temporal relationships. To track and keep evolution traces of the latter, we model them at two levels of abstraction: the state level to describe their attributes set called schema, and the instance level to describe their attributes value. At each time there is a change in the schema of a temporal entity or relationship, a new state is created. At each time there is change in the attributes value, a new instance of the state is created. We affect to each state and each instance a time value depicting the time when it is valid. Thus, a temporal entity or relationship is composed by a set of states and each state is composed by a set of instances.

Compared to existing temporal graph models, our model has several advantages. First, it manages temporal evolution at a finer granularity level by affecting time values to entities and relationships rather than the entire graph as in snapshot-based approaches. Then, it embeds a complete information about the temporal evolution of entities and relationships. Indeed, the affected time values to temporal entities and relationships capture when the addition of new entity or relationship and new attribute(s) in the schema of an entity or relationship, when the deletion of an entity or relationship and attribute(s) in the schema of an entity or relationship and, when the change in the attributes value of an entity or relationship are made in the graph.

Our next plan is the manipulation of our previously defined temporal graph model. Our objective for this part is to define a high-level language for querying our temporal graph combining different principles: extension and adaptation to our context of (i) database query languages based on versions [START_REF] Ozsoyoglu | Temporal and real-time databases: a survey[END_REF], (ii) specific operators of temporal graphs [START_REF] Moffitt | Temporal graph algebra[END_REF] and (iii) inference of new components in the graph [START_REF] Fang | Graph embedding framework for link prediction and vertex behavior modeling in temporal social networks[END_REF].

We will validate our modelling as well as its manipulation using data of real-world applications provided by the Activus Group company. We have already identified two implementation alternatives of our model in two data stores based on property graph model: Neo4j and OrientDB. We have defined translation rules to convert our model concepts into the property graph model.

an image of the entire graph at a given time.

the way in which the nodes and edges are arranged within a graph.

the attributes value of nodes and edges.

denoted G 1 , G 2 , ..., G T where G i is an image of the entire graph at the time i and [1; T ] is the lifetime of the graph.


Landy Andriamampianina

Franck Ravat

Nathalie Vallès-Parlangeau

Towards an efficient approach to manage graph data evolution: conceptual modelling and experimental assessments

Keywords: Temporal graph, Graph snapshots, Temporal evolution, Graph data stores

This paper describes a new temporal graph modelling solution to organize and memorize changes in a business application. To do so, we enrich the basic graph by adding the concepts of states and instances. Our model has first the advantage of representing a complete temporal evolution of the graph, at the level of: (i) the graph structure, (ii) the attribute set of entities/relationships and (iii) the attributes' value of entities/relationships. Then, it has the advantage of memorizing in an optimal manner evolution traces of the graph and retrieving easily temporal information about a graph component. To validate the feasibility of our proposal, we implement our proposal in Neo4j, a data store based on property graph model. We then compare its performance in terms of storage and querying time to the classical modelling approach of temporal graph. Our results show that our model outperforms the classical approach by reducing disk usage by 12 times and saving up to 99% queries' runtime.

Introduction

In the real world, entities (i.e. objects, concepts, things with an independent existence) and the relationships between them change over time so information about them also changes. They can evolve over time in terms of (i) their topology (how entities are linked, when entities/relationships are present or absent), (ii) their inherent features (the attributes set that describes an entity or a relationship) and (iii) their status (the values of the set of descriptive attributes at a particular time). Finding and analyzing these evolutions enable to get a deeper understanding of an application notably to exploit temporal correlations and causality [START_REF] Holme | Temporal networks[END_REF][START_REF] Beheshti | Temporal Provenance Model (TPM): Model and Query Language[END_REF], to make simulations [START_REF] Hartmann | GreyCat: Efficient what-if analytics for data in motion at scale[END_REF] or to make predictions [START_REF] Li | Predicting path failure in time-evolving graphs[END_REF]. It is therefore necessary to be able to manage the temporal evolution of data to exploit them. The management of evolving data implies the following challenges: (i) the formalization of a conceptual model to capture the three aspects of evolution of an application that we mentioned before, (ii) the implementation of the conceptual model into a data store and (iii) the efficient querying of the temporal aspects of an application.

Regarding the first challenge, a growing part of the literature proposes conceptual models, called temporal graphs, based on graphs because of their flexible nature. It incorporates time dimension in graphs and captures the temporal evolution of graph data. The basic representation of temporal graphs is the sequence of graph snapshots 3 . However, existing snapshots-based solutions focus on specific evolution aspects according to an application's needs. Particularly, they do not capture the addition or deletion of entities and relationships' attributes over time. Regarding the second challenge, to our knowledge, no works formalize translation rules of a conceptual model of temporal graphs into a data store [START_REF] Yang | Mining most frequently changing component in evolving graphs[END_REF][START_REF] Aslay | Mining Frequent Patterns in Evolving Graphs[END_REF][START_REF] Rossi | Modeling dynamic behavior in large evolving graphs[END_REF]. Regarding the third challenge, to exploit temporal graphs efficiently, some works propose optimization methods to reduce data redundancy generated by snapshots but they are not effective enough [START_REF] Kosmatopoulos | An Overview of Methods for Handling Evolving Graph Sequences[END_REF][START_REF] Xiangyu | An Efficient Snapshot Strategy for Dynamic Graph Storage Systems to Support Historical Queries[END_REF][START_REF] Zaki | Comprehensive Survey on Dynamic Graph Models[END_REF]. Other works focus on the performance of graph data stores supporting temporal graphs [START_REF] Cattuto | Time-varying social networks in a graph database: a Neo4j use case[END_REF][START_REF] Huang | TGraph: A Temporal Graph Data Management System[END_REF][START_REF] Roussakis | A flexible framework for understanding the dynamics of evolving RDF datasets[END_REF][START_REF] Pernelle | RDF data evolution: automatic detection and semantic representation of changes[END_REF].

In response to the previous issues, our contribution is three-fold: (i) a generic conceptual model to capture a complete temporal evolution of graph data, (ii) that is directly convertible into a graph data store through formalized translation rules (iii) and that supports efficiently the querying of multiple evolution aspects of a graph. In this paper, first, we discuss the challenges posed by existing works on the management of graph data evolving over time (Section 2). Second, we propose novel concepts of the temporal graph to overcome the limits of existing concepts (Section 3). Finally, we implement our model in a graph data store, namely Neo4j, and compare its performance to the classical snapshot-based implementation and an optimized snapshot-based implementation (Section 4).

Related Works

In this section, we analyze existing approaches to manage the evolution of graph data at three levels: conceptual, logical, and physical levels. Then, we present our contributions in relation to existing works.

At the conceptual level, the classical approach to model graph data evolving over time is the sequence of snapshots [START_REF] Kosmatopoulos | An Overview of Methods for Handling Evolving Graph Sequences[END_REF]. It generally consists in sampling graph data periodically to obtain snapshots at a fixed time interval (e.g. per hour, day, month or year) [START_REF] Moffitt | Towards sequenced semantics for evolving graphs[END_REF]. The advantages of this modelling approach are that it is simple and that it represents accurately the state of the graph at a specific time instance [START_REF] Moffitt | Towards sequenced semantics for evolving graphs[END_REF]. Nevertheless, existing works based on this approach are limited in taking into account evolution. The evolution of the graph topology 4 , i.e. the addition and deletion of edges only [START_REF] Yang | Mining most frequently changing component in evolving graphs[END_REF][START_REF] Aslay | Mining Frequent Patterns in Evolving Graphs[END_REF] or both nodes and edges [START_REF] Rossi | Modeling dynamic behavior in large evolving graphs[END_REF] over time, is the most studied evolution type. To meet more complex needs, some models include attributes of nodes [START_REF] Desmier | Cohesive co-evolution patterns in dynamic attributed graphs[END_REF][START_REF] Fournier-Viger | Mining Attribute Evolution Rules in Dynamic Attributed Graphs[END_REF] or both edges and nodes' attributes [START_REF] Khurana | Efficient snapshot retrieval over historical graph data[END_REF] to capture the temporal evolution in their values. In the previous cited works, they generally consider the attribute set of nodes or edges as fixed while it can evolve over time in real-world applications. Indeed, some applications require to model evolution that happened at all levels in a graph [START_REF] Brunsmann | Semantic Exploration of Archived Product Lifecycle Metadata under Schema and Instance Evolution[END_REF]. To the best of our knowledge, there is no modelling solutions of temporal graphs including all evolution types in order to be used in any desired application. Last but not least, some works propose a modelling approach of evolving graphs completely in break with snapshots [START_REF] Kosmatopoulos | Hinode: implementing a vertexcentric modelling approach to maintaining historical graph data[END_REF][START_REF] Maduako | STVG: an evolutionary graph framework for analyzing fast-evolving networks[END_REF]. They attach a valid time interval to each graph component (i.e. node or edge) to track the graph evolution. However, as snapshots, they focus on specific evolution types.

At the logical level, property-graph and RDF data models are commonly used in the graph domain. Traditionally, the transformation between the conceptual level and the logical level is done in an automatic way such as in the relational databases domain. However, to our knowledge, this automation is not studied in the domain of graphs. The works that propose a conceptual model completely ignore the formalization of translation rules from the conceptual model to the logical model [START_REF] Yang | Mining most frequently changing component in evolving graphs[END_REF][START_REF] Aslay | Mining Frequent Patterns in Evolving Graphs[END_REF][START_REF] Rossi | Modeling dynamic behavior in large evolving graphs[END_REF]. No standard is defined at the present time to guarantee a compliant implementation of a conceptual model of temporal graphs at the logical level.

At the physical level, existing works try to maximize the implementation and query efficiency of temporal graphs. We distinguish two research axis in existing works: data redundancy reduction and performance improvement. Regarding data redundancy reduction, snapshots inevitably introduce data redundancy since consecutive snapshots share in common nodes and edges that do not change over time [START_REF] Kosmatopoulos | An Overview of Methods for Handling Evolving Graph Sequences[END_REF]. There exist optimization techniques to partially reduce data redundancy. For instance, [START_REF] Xiangyu | An Efficient Snapshot Strategy for Dynamic Graph Storage Systems to Support Historical Queries[END_REF] proposes a strategy to determine which snapshots should be materialized based on the distribution of historical queries. [START_REF] Khurana | Efficient snapshot retrieval over historical graph data[END_REF] introduces an in-memory data structure and a hierarchical index structure to retrieve efficiently snapshots of an evolving graph. [START_REF] Ren | On querying historical evolving graph sequences[END_REF] proposes a framework to construct a small number of representative graphs based on similarity. These techniques are unfortunately not effective enough.

Regarding the performance improvement, some works focus on the performance of graph data stores supporting evolving graphs via experimental assessments. Some experiments are based on property-graph based NoSQL databases. For instance, [START_REF] Cattuto | Time-varying social networks in a graph database: a Neo4j use case[END_REF] uses Neo4j to store time-varying networks and to retrieve specific snapshots. The authors in [START_REF] Huang | TGraph: A Temporal Graph Data Management System[END_REF] have developed a graph database management system based on Neo4j to support graphs changing in the value of nodes and edges' properties but with a static structure. Other experiments rely on RDF triple stores, such as Virtuoso5 or TDB-Jena6 , to store the evolution of Linked Open Data (LOD) in the Semantic Web area [START_REF] Roussakis | A flexible framework for understanding the dynamics of evolving RDF datasets[END_REF][START_REF] Pernelle | RDF data evolution: automatic detection and semantic representation of changes[END_REF]. It is already known that property-graph based NoSQL databases are more efficient than RDF triple stores when querying RDF data [START_REF] Ravat | Improving the performance of querying multidimensional RDF data using aggregates[END_REF]. It is necessary to see if property-graph based databases are as efficient in the context of temporal graphs.

Contributions. We propose a complete solution to manage the evolution of graph data. From a conceptual point of view, we propose a graph-based modelling that does better than snapshots by capturing temporal evolution at all levelsthe graph topology, the attributes' set and the value of attributes -in order to be implemented in any desired application (Section 3). From a logical point of view, we propose translation rules between our conceptual model and a graph data store to automate the implementation of our model (Section 4). We have decided to focus on a property-graph data store as it provides a more efficient environment for analytical queries than RDF triple stores. From a physical point of view, to highlight the advantage of using our model instead of snapshots, we present a comparative study of the implementation of both models using Neo4j as a property-graph data store. On the one hand, we compare the creation time and space requirements to evaluate the proportion of data redundancy in both models. On the other hand, we compare the querying performance of these implementations based on benchmark queries highlighting the temporal evolution concepts proposed by our model and using the native query language of Neo4j (Section 4).

Proposition

In this section, we present our modelling solution of a temporal graph. We keep the concepts of entities and relationships as in basic graphs. We incorporate the notion of time to represent the evolution of entities and their relationships. We model time as linear and discretized according to a time unit. A time unit is a partition of the timeline into a set of disjoint contiguous time intervals. Definition 1. A time interval defines a set of instants between two instant limits. We denote it T = [t begin , t end ]. An instant defines a point on a timeline, that is T = [t begin , t end ] where t begin = t end .

In order to respond to the current needs for capturing multiple evolution types of an application (change in the topology of entities/relationships, in the attributes set of entities/relationships or in the attribute values of entities/relationships), we cannot rely on the current works in the literature. To overcome this limitation, we propose a new model capable of capturing three types of temporal evolution of entities and relationships in an unique representation. In our model, an entity or relationship that evolves over time is modelled through three levels of abstraction: (i) the topology level to capture its presence and absence over time (ii) the state level to capture the evolution in its attributes set and (iii) the instance level to capture the evolution in the value of its attributes.

Instead of attaching time to an entire graph as in snapshots, we attach a valid time interval to each abstraction level of entities/relationships. This valid time interval expresses the validity and existence of the information associated to each abstraction level of entities/relationships inside a certain time interval. This time management method allows to keep the strict and necessary data and then avoid data redundancy. Definition 2. A temporal entity, called e i ∈ E, is defined by T ei , id ei , S ei where T ei is the valid time interval of e i , id ei is the identifier of e i and S ei = {s ei 1 , ..., s ei m } is the non-empty set of states of e i . Each state s ei j ∈ S ei is defined by T sj , A sj , I sj where:

-T sj is the valid time interval of s ei j .

-A sj = {a ei 1 ; ...; a ei n } is the non-empty set of attributes of s ei j during T sj . It is called the schema of e i during T sj .

-

I sj = {i sj 1 ; ...; i sj p } is the non-empty set of instances of s ei j during T sj . Each instance i sj k ∈ I sj is defined by T i k , V i k where: • T i k is the valid time interval of i sj k . • V i k = {v(a ei 1 ); ...; v(a ei n )} is a non-empty set of attributes' values. Each v(a ei q ) ∈ V i k is the value of each attribute a ei q ∈ A sj during T i k .
The highest abstraction level of a temporal entity e i is the topology level. At this level, a temporal entity evolves only according to its presence or absence in the application reflected by the change of its valid time T ei over time.

The middle abstraction level of a temporal entity e i is the state level under which its schema, denoted A sj , can evolve. At this level, two states of the same entity have different schemas. When a new attribute is added or removed from an entity, a new state is created instead of overwriting the old state version.

The lowest abstraction level of a temporal entity e i is the instance level. It captures the evolution in the value V i k of its attributes A sj . At this level, between two instances of the same entity, the schema is the same but the values of its attributes are different. When the values of an entity's attributes change, a new instance is created instead of overwriting the old instance version.

The changes at the topology and state levels impact the instance level. At the topology level, when an entity is present/absent at a particular time, this translates by the presence/absence of its states and the instances that composed them at this particular time. At the state level, when there is a change in the schema of an entity, a new state is created. Moreover, at least one instance of this state is created. At each change on an abstraction level, this ends the valid time of the last instance at the time of the change and starts the valid time of the new created instance at the time of the change. So the valid times of the abstraction levels higher than the instance level are deduced by calculation as described in following definition. Definition 3. The valid time interval of each instance of a temporal entity i sj k ∈ I sj is defined by T i k = [t begin , t end ] where t begin = ∅ and t end = ∅. There is only one case where an instance has not yet got a pre-defined ending time: if some instances under the current state s ei m are current in the application. The valid time interval of each state of a temporal entity s ei j ∈ S ei is obtained by calculation:

T sj = ∪ k=p k=1 T i k where i k ∈ I sj (1)
The valid time interval of each temporal entity e i ∈ E is obtained by calculation :

T ei = ∪ j=m j=1 T sj where s j ∈ S ei (2)
The temporal evolution of relationships includes the evolution in the graph topology, in their attribute set and in the value of their attributes. We use the same evolution mechanisms as in temporal entities for relationships. In fact, a temporal relationship is also modelled through the concepts of states and instances. Definition 4. A temporal relationship, called r i , is defined by T ri , S ri where T ri is the valid time interval of r i and S ri = {s ri 1 , ..., s ri u } is the non-empty set of states of r i . A state s ri b ∈ S ri is defined by T s b , A s b , I s b where:

-T s b is the valid time interval of s ri b . -A s b = {a ri 1 ; ...; a ri w } is the non-empty set of attributes of s ri b during T s b . It is called the schema of r i during T s b . -I s b = {i s b 1 ; ...; i s b x } is the non-empty set of instances of s ri b during T s b . Each instance i s b c ∈ I s b is defined by T ic , V ic where: • T ic is the valid time interval of i s b c . • V ic = {v(a ri
1 ); ...; v(a ri w )} is a non-empty set of attributes' values. Each v(a ri d ) ∈ V ic is the value of each attribute a ri d ∈ A s b during T ic . Definition 5. A temporal relationship is defined based on the same concepts as a temporal entity. The valid time of each state s ri b ∈ S ri , denoted T s b , is obtained by calculation as in Definition 3. The valid time of each temporal relationship r i ∈ R, denoted T ri , is obtained by calculation as in Definition 3. The particularity of a temporal relationship is that it does not have an independent existence contrary to temporal entities. This implies in our modelling that:

-An instance i s b c ∈ I s b is a relationship between a couple of instances (i h , i l ) belonging respectively to entities e i and e j .

-The valid time of each instance i s b c ∈ I s b is defined by T ic = [t begin , t end ] where t begin = ∅ and t end = ∅. There is only one case where it has not yet got a pre-defined ending time: if some instances under the current state s ri u are current in the application and both connected entities' instances i h and i l do not have yet a pre-defined ending time.

- 7 where T i h is the valid time of an instance i h of e i and T i l is the valid time of an instance i l of e j . (T Example 1. We propose in this example an application to show the implementation of our modelling concepts. We consider two entities: a store and an item. At the creation of the application at the month 01/2020, the store and the item are characterized by the following set of attributes: an identifier (denoted id) and a type (denoted type). In addition, the store is described by the number of its employees (denoted nb_employees) and a name (denoted name). The item is also described by a price (denoted current_price) and the category to which it belongs (denoted category). These two entities are linked by the sale of the item by the store. This sale is characterized by a type (denoted type) and the quantity sold of the item by the store (denoted quantity_sold). The store is identified by "S1" and named "Lidl". Its type is "Store". It has 40 employees. The item is identified by "I1". Its type is "Item". It has a price of 27.02$. Its category is "Books". The type of the sale between of I1 by S1 is "Sale". The quantity sold of the latter is 50.

T ic d(T i h ∩ T i l )
i h ∩ T i l ) = ∅ because (T i h • T i l ) 8 .
Since the application creation, both entities have not evolved until 02/2020. However, the quantity sold of I1 by S1 has decreased by 40 at the month 02/2020. At the month 03/2020, several evolutions took place. The store S1 has recruited 5 employees. The item I1 is described by a new attribute called class. The item I1 has been affected to the class "parenting". The quantity sold of I1 by S1 has increased by 10. Since the month 03/2020, both entities have not evolved anymore. At the month 04/2020, the sale of I1 by S1 is described by the new attribute net_prof it. It is the net profit made by S1 on I1. Its value is 1510.2$. Finally, there is no sale of I1 by S1 since the month 05/2020. To answer the need of capturing these evolutions, we show in Figure 1 the implementation of our modelling concepts to manage the temporal evolution of the application. The sale of I1 by S1 corresponds to a relationship between the two entities. An instance is illustrated graphically by a node for entities and by an edge for relationships in Figure 1. Similarly, a state is illustrated graphically by a set of nodes for entities and a set of edges for relationships in Figure 1.

Both entities have not changed from 01/2020 to 02/2020 neither in terms of their presence/absence nor their schema nor their attributes' value. At the level of our model, this is translated by one state of S1 with the schema {id, type, nb_employees, name}. One instance of this state is created to initialize the value of S1's attributes. The latter is illustrated by the node A in Figure 1. Moreover, one state of I1 is created with the schema {id, type, current_price, category}. One instance of this state is created to initialize the value of I1's attributes. It is illustrated by the node C in Figure 1. Instances A and C have a valid time starting from 01/2020 and ending at 02/2020 during which they did not change.

The first sale of I1 by S1 generates at the level of our model one state of the relationship between both entities with the schema {type, quantity_sold}. One instance of this state, illustrated by the edge E in Figure 1, is created to initialize the value of the sale's attributes. At the month 02/2020, the value of the attribute quantity_sold of the sale of I1 by S1 has decreased under the same schema of the instance E. This generates in our model a new instance, labelled F in Figure 1, with the updated value of quantity_sold under the same state in which the instance E belongs. The valid time of F begins at the time of the change it captures i.e. 02/2020. At the month 03/2020, S1 experienced an increase in the value of the attribute nb_employees under the same schema of its instance A. This creates at the level of our model a new instance of S1, labelled B in Figure 1, with the updated value of nb_employees under the state in which the instance A belongs. As S1 does not change anymore since 03/2020, the valid time of instance B is starting from 03/2020 but its ending date is not specified. It is worthy to notice that S1 has never experienced a change in its schema. It has only one state with the schema {id, type, nb_employees, name} and which gathers the instances A and B.

Moreover, at the month 03/2020, the attribute class has been added to the schema of I1. From our modelling point of view, this generates a new state with the new schema {id, type, current_price, category, class}. A new instance of this state is created to specify the value of I1's attributes. It is illustrated by the node D in Figure 1. As I1 does not change anymore since 03/2020, the valid time of instance D is starting from 03/2020 but its ending date is not specified. To sum up, I1 has two states: one with the schema {id, type, current_price, category} and composed of the instance C and another one with the schema {id, type, current_price, category, class} and composed of the instance D.

Last but not least, also at the month 03/2020, the value of the attribute quantity_sold describing the sale of I1 by S1 has increased under the same schema of instances E and F . This is translated in our model by the creation of a new instance G in Figure 1 with the updated value of quantity_sold. This instance belongs to the state composed of instances E and F . The valid time of G starts at the time of the change it captures i.e. 03/2020. At 04/2020, the attribute net_prof it has been added to the schema of the relationship. From our modelling point of view, this generates a new state of the relationship with the new schema {type, quantity_sold, net_prof it}. A new instance of this state is created to specify the value of the relationship's attributes. It is illustrated by the edge H in Figure 1. To sum up, the relationship between I1 and S1 has two states: one with the schema {type, quantity_sold} and composed of three instances (E, F and G) and another one with the schema {type, quantity_sold, net_prof it} and composed of one instance (H). Finally, there is no sale of I1 by S1 since the month 05/2020. This corresponds in our model to the absence of relationship between I1 and S1 at the month 05/2020. Consequently, no instance or state of this relationship with a valid time including the month 05/2020 is created.

In a nutshell, our model translates the different evolutions of the application into 1 graph with 4 nodes and 4 edges. We present in Figure 2 the representation of the same application if we would have adopt the snapshot-based approach to manage the temporal evolution. We would have 5 graph snapshots with 10 nodes and 4 edges.

As a result of the previous definitions, our temporal graph is defined as follows: Definition 6. A Temporal Graph, called G, is defined by L, E, R where:

-L is the timeline of the temporal graph, -E = {e 1 , ..., e g } is a non-empty set of temporal entities, -R = {r 1 , ..., r h } is a non-empty set of temporal relationships. Definition 7. The timeline L of a temporal graph G only depends on the valid times of temporal entities as they have an independent existence. L is obtained by calculation:

L = ∪ i=g i=1 T ei where e i ∈ E (3)

Experimental evaluation

In this section, we present an experimental comparison of three approaches for modelling an evolving graph: the classical sequence of snapshots, an optimized sequence of snapshots and our temporal graph. As we have discussed in Section 2, the classical snapshots consists in sampling of graph data at a regular time period (here we chose a month). Our optimized snapshots approach consists in creating snapshots only if they differ. In other terms, we create a snapshot only if it includes a change compared to a previous snapshot. This experiment has two goals: (i) to study the feasibility of our model, i.e. illustrate if our modelling is easily implementable (stored and queried) in a graph-oriented data store and (ii) to study the efficiency of our model by comparing its storage and query performance to the classical sequence of snapshots and the optimized sequence of snapshots.

In Section 4.1, we present the technical environment of our experiment. Then, in Section 4.2, we present the datasets we used for the three implementations. We stored these datasets in Neo4j based on defined translation rules of our model presented in Section 4.3. Finally, we query the three approaches according to different querying criteria and compare their runtime in Section 4.4. We present the details of our experiment at the following web page https://gitlab.com/ 2573869/temporal_graph_modelling.

Technical environment

The hardware configuration is as follows: PowerEdge R630, 16 CPUs x Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40Ghz, 63.91 GB. One virtual machine is installed on this hardware. This virtual machine has 6GB in terms of RAM and 100GB in terms of disk size. We installed on this virtual machine Neo4j (community version 4.1.3) as a data store for our datasets.

Datasets

To run our experimental comparison, we needed a dataset that reflect realistic applications with temporal evolutions. We therefore used a dataset from a reference benchmark namely TPC-DS and allow us to find all the three types of evolution mentioned in Section 3. We transformed the dataset provided by TPC-DS into three datasets having the temporal graph, the classical snapshots and the optimized snapshots representations.

All transformation details of the TPC-DS dataset into the three representations are available on the website https://gitlab.com/2573869/temporal_graph_ modelling. In Table 1, we found as a result of the transformation steps, the number of nodes, edges and snapshots of the dataset used for each implementation.

Translation of temporal graph into Neo4j

To evaluate the feasibility of our modelling solution, we searched for translation rules to map our conceptual model of temporal graph into the graph data model supported by Neo4j, the property graph model [START_REF] Rodriguez | Constructions from Dots and Lines[END_REF]. In Table 2, we define the translation rules between our model and the property graph. The concepts of our temporal graph are directly translatable into the property graph of Neo4j. An instance of an entity or relationship in our model can be represented respectively by a node and an edge in Neo4j. The value of the attributes set and valid times of instances correspond to the key-value properties in Neo4j. An entity, relationship or state is composed of instances. Then, they are represented by a set of nodes or edges in Neo4j. Schemas and valid times of a state, an entity or relationship can be retrieved by query in Neo4j.

For each implementation, we stored the relative dataset in a database instance of Neo4j. Table 3 shows the size (in GB) and the creation time (in seconds) of each database instance in Neo4j. The two snapshots approaches use a different time management method than our model which leads to larger sizes of their database instances. Our model reduces respectively 12 times and 9 times the size of database instance storing classical snapshots and optimized snapshots. To load the datasets into Neo4j, we designed a program based on the CSV importing system of Neo4j. Again, the datasets based on snapshots approaches require more time to be imported since they contain more nodes and edges than our model (Table 1).

Query performance

To evaluate the efficiency of our model, we compare its querying performance with the classical snapshots and the optimized snapshots based implementations.

Our model's concepts

Neo4j's concepts an instance of an entity state i by query a schema of an entity state A s j by query a schema of a relationship state A s b by query an entity ei a set of nodes (with different valid times) a relationship ri a set of edges (with different valid times) an attribute of an entity a e i q a property an attribute of a relationship a r i d a property a temporal entity's identifier id e i a property valid time of an entity T e i by query valid time of a relationship T r i by query To do so, we created benchmark queries that cover a large range of scenarios to get insights about the temporal aspects of a graph (Table 4). We classified them into the following criteria: the entity scope, the time scope, the temporal evolution type and the operations type [START_REF] Khurana | Storing and Analyzing Historical Graph Data at Scale[END_REF][START_REF] Koloniari | On Graph Deltas for Historical Queries[END_REF]. Then, we translated these benchmark queries in the native query language of Neo4j: Cypher. Finally, we recorded for each benchmark query its execution time which is the elapsed time in seconds for processing the query (Figure 3). We run each query ten times and take the mean time of all runs as final execution time. To avoid any bias in the disk management and querying performance, we do not use any customized optimization techniques but rely on default tuning of Neo4j.

Observations. In Figure 3, we observe that queries Q1-Q6 are instantaneous (close to 0) for all three implementations. Q17-Q21 and Q27 record execution spikes for the two snapshots implementations. Moreover, we notice that the runtimes of Q28 explode for the snapshots and the temporal graph implementations. The rest of benchmark queries (Q7-Q16 and Q22-Q26) does not exceed 6 seconds for the three approaches. Overall, the execution query times of the temporal graph are more stable than both snapshot-based approaches.

Graph component Evolution type

Time scope Operation type

Q1

The descriptive attributes of a store at the month X SE S SP Q2

The descriptive attributes of a store at the months X and Y SE S MP Q3

The changes that occurred on the descriptive attributes of a store between the months X and Y SE S MP C Q4

The descriptive attributes of a store from the month X to the month Y SE S SI Q5

The descriptive attributes of a store every year of a period SE S MI Q6

The changes that occurred on descriptive attributes of a store from the month X to the month Y SE S SI C Q7

The price of an item at the month X SE I SP Q8

The The customers that shopped in a store at the month X SU T SP Q13

The customers that shopped in a store at the months X and Y SU T MP Q14

Count the number of customers that shopped in a store at the month X SU T SP A Q15

Count the number of customers that shopped in a store at the months X and Y SU T MP A Q16

The customers that shopped in a store from the month X to the month Y SU T SI Q17

The customers that shopped in a store every year of a period SU T MI Q18

Count the number of customers in a store every year of a period SU T MI A Q19

The household attributes of a customer at the month X SU S SP Q20

The household attributes of a customer at the months X and Y SU S MP Q21

The changes that occurred on the household characteristics of a customer between the months X and Y SU S MP C Q22

The household attributes of a customer from the month X to the month Y SU S SI Q23

The changes that occurred on the household characteristics of a customer from the month X to the month Y SU S SI C Q24

The sold quantity of an item by a store at the month X SU I SP Q25

The sold quantity of an item by a store at the months X and Y SU I MP Q26

The sold quantity of an item by a store from the month X to the month Y SU I SI Q27

Measure the average sold quantity of an item by a store every year of a period SU I MI A Q28

The historical state of the store sales at the month X EG SP Discussion. The gap between the temporal graph and the two snapshots based implementations is partly due to difference in the volume of data involved in queries. As we can see in Table 1, the classical snapshots based implementation results in 66 times more nodes and 2 times more edges than the temporal graph. The optimized snapshots based implementation enables to reduce significantly the number of nodes but still it counts 47 times more nodes than the temporal graph. Inevitably, both snapshots approaches use more disk space and require more time to process during querying.

Queries' runtime are also impacted by their types. First, we analyze the querying performance of the temporal graph according to the entity scope, that is requesting information about the history of the graph at the level of a single entity (Q1-Q11) or a set of entities (subgraph) (Q12-Q27) or the entire graph (Q28). Most queries on a single entity are instantaneous as they involve the least data for the three approaches. The temporal graph approach outperforms the classical and the optimized snapshots approaches on querying a subgraph by respectively reducing their runtimes by 58%-99% and 74%-99%. The same trend is observed on querying the entire graph. The temporal graph saves 35% of the classical snapshots' runtime. Neo4j was not able to process Q28 for the optimized snapshots approach due to main memory limitations. Second, we analyze the impact of evolution type over queries' runtime: the evolution of schemas (Q1-Q6 and Q19-Q23), instances (Q7-Q11 and Q24-Q27) or topology (Q12 to Q18). The retrieval tasks relative to this scope enable to evaluate the cost of retrieving a specific information about graph changes. Excluding instantaneous queries, the gap between the two snapshots and the temporal graph implementations is the largest when querying schema. Indeed, queries on schema involve one specific operator 10 . Particularly, the temporal graph decreases the runtimes of Q19-Q23 in both classical and optimized snapshots by 98%-99%.

Third, we focus on the impact of time scope over queries' runtime to evaluate the cost of time travelling in the graph: querying a single time point (Q1, Q7, Q12, Q14, Q19, Q24 and Q28), a single interval (Q4, Q6, Q10, Q16, Q22, Q23 and Q26), multiple time points (Q2, Q3, Q8, Q9, Q13, Q15, Q20, Q21 and Q25) or multiple time intervals (Q5, Q11, Q17, Q18 and Q27). On the one hand, we observe that for queries with a complex time view (i.e. concerning multiple time points or multiple time intervals) the execution time explodes for both snapshots approaches while our model is still effective. Particularly, queries Q17-Q18 and Q27, involving multiple time intervals, reach respectively 10s and 31s for the two snapshots approaches. Our temporal graph allows to reduce those runtimes by 79%-95%. Moreover, queries Q20-Q21, involving multiple time points, exceed 10s for the two snapshots approaches. Our temporal graph enables to save 99% of both snapshots approaches on those queries. On the other hand, surprisingly, we notice that some queries' runtimes with the optimized snapshots such as Q7, Q8, Q9 or Q21 are higher than the classical snapshots even if they involve less data. Indeed, the translation of these queries into Cypher differs between the three implementations. As the time management method differs in the three models, the predicate on valid times differs even if they answer to the same business insights. Particularly, the translation of queries on a single time and multiple time points in Cypher for the optimized snapshots is more complex. These queries imply a sub-query to search for the snapshot that is the closest to the requested time instance.

Last but not least, we focus on the impact of operation types over queries' runtime: (i) comparison queries aiming at evaluating how does a graph component change over time with respect to a temporal evolution type (Q3, Q6, Q9, Q21 and Q23), (ii) aggregation queries aiming at evaluating an aggregate function (Q11, Q14, Q15, Q18 and Q27). Excluding instantaneous queries, both snapshots approaches perform the worst runtimes on aggregation and comparison queries. The temporal graph based implementation allows to save 61%-99% of classical snapshots' runtimes and 80%-99% of optimized snapshots' runtimes.

Implications. The choice of a data model to manage evolving graph data impacts significantly the storage and querying efficiency. Our model has a double advantage. First, it allows to get rid of data redundancy. So it saves a significant amount of space on the disk compared to snapshots. Second, it supports efficiently a wide range of queries while keeping the query runtime low and stable. In particular, querying an entire graph snapshot (Q28), which is the basic task in the literature, is costly in snapshots approaches. The implementation with our model allows to save 35% of runtime compared to the classical snapshots implementation.

Conclusion and future works

This paper has presented a complete solution to manage graph data evolution. The power of our solution lies on the proposition of a conceptual modelling and experimental assessments to illustrate its feasibility and efficiency.

Our conceptual modelling proposes concepts allowing representing the evolution of a graph at different levels: the graph topology, the attributes' set and the attributes' value of entities and relationships. Thus, it is generic enough to be compatible with any desired applications. Moreover, it does not introduce data redundancy thanks to a different time method from snapshot-based approaches. Time is attached to each individual graph component while it is attached to the entire graph in snapshots.

To validate the feasibility of our model, we implemented it in Neo4j based on a dataset containing temporal evolution. We showed that our model is directly convertible to the data model of Neo4j based on a set of translation rules we formalized. Then, we implemented several queries. We were able to query the evolution types proposed by our model using the native querying language of Neo4j.

To highlight the efficiency of our model, we made a comparative study of its implementation with the traditional sequence of snapshots and an optimized version of snapshots based on the same dataset. We observed that our model performs better than the sequence of snapshots by reducing 12 times disk usage and by saving up to 99% on queries' execution time. In comparison to the optimized sequence of snapshots, our model reduces 9 times disk usage and saves until 99% on queries' runtime. In a nusthell, our model is an efficient solution for storing and querying a dataset with temporal evolution.

In our future works, we will extend our experiments to other types of data stores such as relational data stores since they can outperform both NoSQL graph stores and RDF triples stores [START_REF] Ravat | Efficient querying of multidimensional RDF data with aggregates: Comparing NoSQL, RDF and relational data stores[END_REF]. This will require to extend the translation rules between the conceptual and logical level to be applicable to relational data stores. Then, we will compare the performance of these data stores in terms of storage and querying with different query languages than Cypher.

Fig. 1 :

 1 Fig. 1: Management of the temporal evolution of the application in Example 1 with our modelling solution.

Fig. 2 :

 2 Fig. 2: Management of the temporal evolution of the application in Example 1 with the snapshots-based solution.

  time of an entity instance T i k two properties * valid time of a relationship instance T ic two properties * a state of an entity s e i j a set of nodes (with different valid times) a state of a relationship s r i b a set of edges (with different valid times) valid time of an entity state T s j by query valid time of a relationship state T s b

  price of an item at the months X and Y SE I MP Q9 Measure the change in the price of an item between the months X and Y SE I MP C Q10 The price(s) of an item from the month X to the month Y SE I SI Q11 Measure the average price of an item every year of a period SE I MI A Q12

  SE = Single Entity, SU = Subgraph, EN = Entire Graph, S = Schema, I = Instance, T = Topology, SP = Single Point, MP = Multiple Points, SI = Single Interval, MI = Multiple Intervals, C = Comparison, A = Aggregation.

Fig. 3 :

 3 Fig. 3: Execution times of 28 benchmark queries.

Table 1 :

 1 9 . Temporal evolutions exist in this benchmark Characteristics of datasets.

	Implementations	# Nodes # Edges # Snapshots
	Temporal graph	112.897	1.693.623 N/A
	Classical snapshots	7.405.461 4.207.657 60
	Optimized snapshots 5.347.477 4.044.481 53

Table 2 :

 2 Translation rules of our model into Neo4j.

	Implementations	Size (in GB)	Creation time (in
			sec)
	Temporal graph	0,3	15,795
	Classical Snapshots	3,7	56,529
	Optimized snapshots	2,8	45,827

* start_valid_time and end_valid_time.

Table 3 :

 3 Size and creation time of graph database instances.

Table 4 :

 4 Benchmark queries.

https://virtuoso.openlinksw.com/

https://jena.apache.org/documentation/tdb/

d is an ALLEN temporal operator to express that a time interval X occurs "during" a time interval Y, i.e. XdY[START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF].

• is an ALLEN temporal operator to express that a time interval X "overlaps" a time interval Y, i.e. X • Y[START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF].

http://www.tpc.org/tpc_documents_current_versions/pdf/tpc-ds_v2.13.0. pdf

The operator keys allows to extract the schema of a node or an edge. https:// neo4j.com/docs/cypher-manual/current/functions/list/


Daniel Chatroux
email: daniel.chatroux@cea.fr

Lithium ion batteries balancing

Standard aqueous batteries need no balancing electronic circuit. Balancing circuit is a specific need for lithium ion batteries. The first goal of this presentation is to compare the technologies differences between aqueous batteries and Lithium ion to explain the advantages and disadvantages about current losses in storage and for balancing circuit specifications. The second goal is to describe some passive and active, dissipative or not balancing circuits.

Context

The CEA (Commissariat à l'Energie Atomique et aux Energies Alternatives) is an energy research center in France dedicated to research and development in nuclear applications and in renewable energies. Two of the main research fields of LITEN Institute, part of CEA in Grenoble, are fuel cells and lithium batteries (from components to systems).

The LITEN masters the whole lithium-ion batteries production line: materials for Lithium ion accumulators, accumulator conception, production, battery packs design, battery management systems conception, electric vehicle integration and monitoring of vehicles.

In different project, we replace existing Lead acid, NiCd or NimH battery packs by Lithium ion batteries. Unlike lead acid batteries, NiCd or NimH ones who don't need any electronic balancing circuit, each Lithium ion accumulator needs a voltage monitoring and a balancing circuit in order to provide safety and long term reliability of the batteries.

Differences between aqueous and lithium ion technologies

2.1.

Aqueous batteries

The three main aqueous technologies (lead acid, NiCd and NimH) have a lot of parasitic electrochemical reactions in parallel with the main one. These parasitic reactions have different electrochemical potentials, and so have different chemical kinetics depending of the accumulator voltage.

One first impact of these parasitic reactions is self-discharge phenomenon.

At nominal voltage, these parasitic reactions are still active. It's a consumption of energy with a discharge rate of some weeks or months. This is a disadvantage. The second impact is intrinsic voltage clamping at the end of the charge.

For example, at the end of the charge for a lead acid battery, the main electrochemical reaction is finished, so the voltage drops up to the water dissociation voltage. If the charge goes on, the current generates heat and gas from the water dissociation but the voltage stay the same: it's the voltage clamping behavior of the accumulator cell which can be simulated by a "zener diode", as in the figure 1. This parasitic reaction is an advantage: when charging multiple cells connected in series (= a battery), as all cells are not identical and in the same state of charge, a cell will end its charge first. As other cells are not fully charged, the current is maintained to charge these cells. The first cell stays fully charged and produce heat and water dissociation: it's a natural balancing that allows the end of charge for other cells.

Thanks to the parasitic reaction, there is an intrinsic voltage clamping with the possibility to balance the different accumulators in series only by the prolongation of the charging phase. However, balancing phase duration has to be minimized because of its great impact on battery life time and charge efficiency.

Lithium ions batteries

The composition of Lithium ion accumulator is for standard design: a copper foil with graphite layers (the two faces) for the negative electrode, a separator with electrolyte impregnation, a positive electrode with aluminum foil and layers of a positive active material. The electrochemical reaction is based on Lithium ion insertion (intercalation) in graphite or in positive active material for charge and discharge. The reaction mechanism of lithium-ion batteries is presented in the Figure 2. The positive and negative materials usually have a layered structure to facilitate lithium ions insertion. The main effect of the charge and discharge reaction is the back and forth movement of lithium ions between the electrodes, matched by a corresponding flow of electrons in the external circuit. This electrochemical process is sometimes called a "rocking-chair" mechanism. The Lithium ion electrochemistry is a dry one.

Because water is a pollutant in this chemistry, the accumulators are built in dry room. Except long term ageing, there is no parasitic reaction, so: No discharge current o Good quality Lithium ion accumulator stores energy for years. It's a great advantage in the application to get the battery charged.

No intrinsic voltage clamping reaction

o There is no natural balancing, and an external balancing circuit is added when accumulators are connected in series

Comparison

The faradic efficiency is the ratio between the charge extracted from the battery in discharge compared and the charge injected.

For aqueous battery, the faradic efficiency is about 90% because of the loss of electrons in parasitic reaction and in the overcharge during the balancing phase.

For Lithium accumulator, the Faradic efficiency is near 100%.

The energy efficiency takes into account the faradic efficiency and the energy losses in the serial resistance: it's the reason why the energy efficiency is directly linked with the levels of charge and discharge currents.

For lithium accumulator, energy efficiency is higher than 90% (95% for example), typically 10 to 20% higher than aqueous ones.

Usefulness of a balancing circuit

With perfect Lithium ion accumulators is series, there is no need of balancing circuit, but:

In reality, there are residual parasitic phenomena: Dispersion of leakage current, simulated by a parallel resistance, Faradic efficiency less than 100%, with some dispersion, Discharge by external leakage current due to moisture or voltage measurement electronic circuit These parasitic phenomena depend on the technology and the manufacturing quality of the accumulators. For example, water pollution creates some leakage current; accumulator ageing has an impact on Faradic efficiency. Because of the difference of discharge by the parasitic elements, after a long time or a succession of charges and discharges, the different accumulators in series don't have exactly the same energy stored so it's necessary to have a balancing circuit to compensate. Good quality accumulators are nearly perfect, so it's not necessary to balance after each charge. For example, after a fast charge, the unbalance is about 0.4%, so the impact on the range of electric car designed for 100 km is only 400 m. But because it's a cumulative phenomenon, it's necessary to balance regularly.

Balancing circuit with Zener diode for LiFePO4 batteries

A first solution is to copy the intrinsic clamping circuit in aqueous electro-chemistries: adding zener diode in parallel of each cell to have balancing by a clamping circuit (Figure 1). For zener diodes of 6V or more, the physical phenomenon is avalanche clamping, not zener effect. The leakage current under the clamping voltage is very low. After the specified voltage, clamping is effective with a low serial resistance: curves are almost vertical in Figure 3.

Below six volts, the physical phenomenon is zener effect. The depleted zone is very thin. Quantic effects are active, so an electron but without the energy level has some probability to cross the potential barrier. The leakage current is high, clamping is very soft. Zener diodes below 6 volts aren't good clamping components.

For Lithium phosphate accumulators based on iron phosphate (LiFePO4), the end of charge voltage is 3.6V for the same maximum voltage of 4.5V. Because of this high voltage safety margin, zener diode tolerances may be accepted.

For some specific applications we used LiFePO4 batteries with 7.5V Zener clamping for each two accumulators in series.

Dissipative active balancing circuits

The main advantage of a zener clamping circuit is the simplicity and the price, but there is no reporting of cells voltages data. For safety and long life performances, a voltage monitoring of the cells, not to overcharge or over-discharge, the accumulators is essential. Main balancing circuits are based on a voltage monitoring circuit on each cells and an electronic switch in series with a resistance to dissipate the current if necessary. At the end of the charge, it's possible to discharge the highest voltage cells to balance all the cells at the same voltage, so the same state of charge. For a power electronic engineer point of view, this dissipative solution seems to be a waste of energy, but because unbalancing is a slow phenomenon with very low energy involved, this solution is suited for good quality accumulators. For 400V 40Ah commercial batteries, the levels of discharge currents are from 250mA (CEA) to some tens of mA (automotive). The very low current for balancing allows having all the balancing circuits on only one PCB for cost minimization. An example of dissipative solution is the LTC6802 from Linear Technology [START_REF]Managing high-voltage lithium-ion batteries in HEVs[END_REF]. In our laboratory, the main balancing circuits are designed with LTC6802. For state of charge calculation with very good precision a current measurement by shunt is used. Because of the low power dimensioning, balancing circuit are not suited for initial balancing after battery manufacture. To minimize the initial unbalancing, the accumulator has to be at the same state of charge. This point is not a problem and don't have any additional cost.

In battery manufacturing, accumulators are built, electrolyte is added, and the final step is a succession of charge and discharge for accumulator forming. This last step is necessary to provide the performances and to create passivation on graphite on negative electrode. To have the same state of charge, the manufacturer has only to stop the last cycle at the same level. A state of charge between 20% and 80% is suited for shipping and storage for a long time with low lifetime impact. Best manufacturer can produce accumulators with the same state of charge at the production line output and with a low self-discharge, so shipping and storage have low impact. In this case, initial unbalancing may be compensated only by the internal balancing circuit without previous recharge of the accumulator or high power external balancing circuit.

6.

Non dissipative active balancing circuit

Non dissipative active balancing circuits have an interest only if they add a low overcost. That's the line we follow to develop a solution with only some bulky central components and some low cost CMS ones for each accumulator stages in series [START_REF]Charge Equalization system for batteries[END_REF]. The inverter provides pulse with low duty cycle, for example 10% with pulses of 1µs. To carry out this solution, we drive the MOSFET by the LTC6802, as a dissipative circuit with the adapted strategy.

At the end of the charge, the LTC6802 balancing algorithm stop the charge of the accumulators by the charger, and accumulators which are not fully charged are finished to charge by the active non-dissipative balancing circuit, by closing the MOSFET of the accumulator stage. The Figure 13 shows the charge of 6 cells in series with different initial state of charge.

Figure 13: end of charge voltages Cell 5 is fully charged after about 25 minutes, and begins to balance. At the end of charge, the voltages dispersion is limited at 14 mV.

Compensation circuit of capacitance dispersion

The balancing circuit function is to compensate the difference of state of charge between cells in series in a battery. The energy involved is low and we have time to do this operation.

The goal of a non-dissipative balancing circuit is to compensate the unbalance of state of charge and not to compensate the difference of capacity between the accumulators in series.

The capacity of accumulators in series is the one which has the lowest value of capaciy. So in the end of a discharge, there is some remaining energy in the accumulators with the biggest capacities. To optimize this situation, a good solution seems to be to exchange energy between the accumulators in the discharge phase. The design of the circuit may be the same as balancing ones but with ten times more current for example. In practice, the cost and space of the power electronic for the compensation of the differences of capacity is often prohibitive. The dispersion of capacity decreases when production volume rises up. So at level of quality of production, capacity compensation becomes not necessary.

It's very important to precise the two different cases of capacity difference compensation and balancing circuit because of the classic confusion between the two different problems with great difference of dimensioning and cost.

Conclusion

Classic aqueous electrochemical accumulators have parasitic reactions with the disadvantage of self-discharge in some weeks or months, and the advantage of doing natural balancing of accumulators in series only by a phase of overcharge. Lithium-ion accumulators have no parasitic electrochemical reaction, so self-discharge may be very low and the battery offer the possibility to keep the battery charged for years. The disadvantages are the needs to have a balancing circuit. Zener solution provides voltage balancing but only for Lithium ion technology with voltage safety margin as LiFePO4.

Active dissipative balancing circuits are adapted for all the Lithium ion technologies, for example the LTC6802 circuit. An active non dissipative circuit optimized for a low over-cost compared with dissipative solution is proposed. The design is based on inductance in discontinuous mode for all the accumulator voltage range, to control the currents of all the outputs without a control circuit per accumulator stages.

Figure 1 :

 1 Figure 1: parasitic reactions simulation in aqueous batteries technologies

Figure 2 :

 2 Figure 2: Lithium ion technologies

Figure 3 :

 3 Figure 3: voltage versus current of different zener diodes

Figure 4: LTC6802 Figure 5 :

 LTC68025 Figure 4: LTC6802

Figure 6 :

 6 Figure 6: shunt and central microcontroller Figure 7: balancing card for battery module

Figure 8 :

 8 Figure 8: low cost non dissipative balancing circuit

Figure 9

 9 Figure 9: inverter voltage Figure 10: inductance current

Figure 11 :

 11 Figure 11: six outputs Figure 12: balancing circuit and control in test

  For most technologies of Lithium ion batteries, this solution doesn't work because of the precision needed. For Lithium ion accumulators based on Cobalt or manganese oxide, the end of charge voltage is 4.2V, very close to the 4.5V maximum voltage. An overvoltage can cause catastrophic failure with a risk of fire and explosion. The 5% precision of zeners are not adapted for theses chemistries. The other problem of Zener diodes is leakage current for low voltage ones.

	Zener diodes with	Avalanche clamping
	high leakage current	phenomenon	Chosen one for 2
			LiFePo4 cells in
			series

9.

References:


Laurent Garnier
email: laurent.garnier@cea.fr

An innovative balancing solution used to supply the 12V auxiliary network of an electric vehicle

In a Lithium Ion battery pack, it is necessary to balance the pack in order to guarantee that at the end of the charge, all cells are fully charged. This step is necessary, otherwise the available energy stored will decrease continuously charge after charge. There are traditional ways to achieve it: an active balancing dissipative method, or a non-dissipative balancing method (energy converters) with higher level of energy saving. Both ways work to compensate the dispersion of farad efficiency (balancing) but a non-dissipative solution can also compensate dispersion of capacity of the accumulators in series. There are other solutions, which could be named "smart balancing with direct energy use" solutions, because the energy involved in balancing is used instead of being transferred between accumulators. The goal of this presentation is to describe this innovative solution, to explain its main advantages and to show how it works.

Introduction

In LIGE laboratory of CEA, we design and manufacture Li-Ion battery pack for different kinds of transport applications. We always integrate a BMS (Battery Management System) in those battery packs. BMS's main functions could be organized in the following priority order:

• ensure the safety of the pack and the user,

• calculate the state of charge (or others like State of Energy, State of Health)

• balance the pack and communicate information to an external part • and sometimes manage the temperature of the pack.

After a brief summarize of the different known balancing solutions, we will focus this paper on the presentation of a new and innovative balancing solution (6 patents have been registred on the subject), which can be used in different electric or hybrid vehicle.

Balancing system -different known solutions

New and innovative solutions

Fourth solution -smart balancing with direct energy use

The main and original idea of a new solution is to use more energy on the cells with the highest state of charge to supply the auxiliaries' network. For example, a higher state of charge could be a consequence of dispersion of capacity, appearing after manufacturing or after ageing, or a dispersion of faradic efficiency, or a consequence of the replacement of an old module with a new one, presenting higher capacity.

In standard solutions, balancing energy is dissipated or transferred from cell to cell. Here, we transfer the power from the selected cells directly to the auxiliaries' network (typically 12Vdc bus), like on figure 1.

Dissipative method

Non-dissipative method New method applied on each cell The main difficulty with the "smart balancing with direct energy use" method is the need of a specific isolated converter, on each level of the battery pack. Let see the example, of an electric vehicle supplied with 160Vdc high voltage battery pack (48 cells in series), which needs 12Vdc-1kW low voltage bus network for auxiliaries. To apply our solution, we have to use 48 converters of about 20W each, with an input voltage of 3,2V and an output voltage of 12V. Due to the low input voltage of the converter, the efficiency will be only around 80% or less. To implement this solution, we would need a high number of converters, with protections against short circuit on each one, and a difficult thermal management system has to be designed.

If we compare this solution with the others on same criteria, we obtain:

Fifth solution -application of this solution to module

To avoid a high number of converters and a low efficiency, the solution can be applied to each module, which are already an association of cells in series and parallels (see Figure 2). The Figure 2 presents a powerful solution, able to offset the dispersion of capacities between modules: 12Vdc bus can be fed mainly, by the module with the highest state of charge.

Inside each module, we usually use accumulators with low dispersion of capacities. That is why a low cost active dissipative balancing circuit is usually sufficient. The dispersion of the capacities between modules are more important because the temperature, the age, between modules can be different.

If we compare this solution with the others on same criteria, we obtain:

The three main advantages of this last solution

The "smart balancing with direct energy use applied to each module" is not only useful to balance a pack and offset the dispersion of capacities. It presents also other advantages:

• First advantage: no energy losses in balancing process and maximum energy use of each module (increase the range of the car).

The DC/DC converter (Vin = 160V, Vout = 12V, 1kW) is replaced by four small converters (Vin = 40V, Vout = 12V, 250W) placed on each battery module. The efficiency at maximum power is nearly the same. With an intelligent management of theses converters, we can supply the 12V DC bus (and so offset the dispersion of capacities) when maximum energy comes from the highest state of charge module.. Compared to standard solutions, there are no additional losses to provide the balancing process in this new electrical architecture. That is the reason why we can say we can perform a "module balancing efficiency of 100%". Consequently, in case of dispersion of capacities between modules, we can use the maximum energy from each module, and thus increase the range of the car.

• Second advantage: possibility of removing the low voltage battery (or decrease the size).

At the output of each converter, we have added an "ORing Diode" (see Figure 2). In case of fault on one converter, we can always continue to supply the 12Vdc bus thanks to the redundancy. If we choose DC/DC converters with higher power on each module, we can remove the low voltage battery without derating. If we accept a small derating, we can continue to supply the auxiliary network, even if one converter is in fault.

• Third advantage: DCDC converters used in high efficiency area.

In an electrical vehicle, the mean power needed on the 12Vdc bus is usually low in comparison with the peak power of few consumers like power steering system, vehicle's headlight, … Consequently, the efficiency of the main converter isn't very good because most of the time, it is working with low load (maximum efficiency of a DCDC converter is performed between 50% and 100% load).

The difference increases with the number of modules: a comparison of efficiency between a single converter solution and a 8 small converters solution is presented on Figure 3. With paralleled converters, in order to optimize the consumption of energy, the power supplied can be adapted to the needs of the 12Vdc bus. Consequently, we can improve the whole efficiency of the system.

Strategy used to control some converters in parallel

The main difficulties to design and implement the last presented solution are, first evaluate separately the state of charge of each module, and second choose and turn ON the right modules during discharge.

An algorithm (triggered every second or more for example) consists in:

-calculate the maximum load current absorbed by the auxiliary bus -calculate the state of charge of each module -classify the modules from the highest to the lowest SOC in order to turn ON, firstly modules with highest SOC -turn ON the right number of modules in order to optimize the system efficiency This algorithm improves system efficiency and allows to balance modules with different SOC. Practically, the different modules are not always turn ON or OFF whenever the load current changes: an analog regulation allows provides current from modules with the highest SOC. Each module converter is voltage regulated with a current limitation, but the level of regulation voltage is a little bit different for each converter. Like it is presented on figure 5, we can see that the current is drawing from the module with the highest level of voltage regulation. This kind of regulation is possible because the auxiliary network of a vehicle allows a wide bus voltage range, usually from 12V to 16V.

Figure 4 presents the high level schematics of the simulation with 4 converters in parallel. We apply different voltage set points and analyze on figure 5 which module provides the current at different load current levels. We can see that the output voltage decreases when the current increases, not only because of the serial resistance, but mainly because the current limitation of 25A is reached on the first two modules (module 1 and 2) We can also see that it is possible to change the priority between two modules (1 and 4).

Tests performed on an electric vehicle

The last solution presented was tested in real configuration on an electric vehicle. We worked with 160V-40Ah battery pack composed by four 40V modules with about 5% of difference of capacity. We removed the 12Vdc battery. During tests, we follow 2 objectives:

• The first one was to ensure that the 12Vdc bus was correctly supplied even with the 12V battery removed. • The second one was to confirm the simulation's results and evaluate the gain of energy we could obtain with a battery pack built with different module capacities.

On the Figure 6 below, is represented with dark blue color the voltage on the bus (12V here), with pink color the total load current, with yellow color the current of the highest state of charge module (module #1) and in light blue color the current in the module #2. The electric load is made up of steering system, headlights, electric windows, windscreen wipers, and warning lights which have been successively started and stopped.

As we can see, the 12V voltage is quite stable and balancing management works great: the module with the highest capacity (module #1) produces its maximum current. It's better to use the module #1 in priority, because it has the highest energy. In order to show the advantage of the new architecture, in term of vehicle range, we performed two comparative complete discharges with the same configuration (5570W on power bus and 300W on auxiliary bus), like it is presented in Figure :

• First discharge with module balancing OFF (blue curve)

• Second discharge with module balancing ON (red curve)

The end of discharge was activated when one cell of the battery pack was under 3 V. We can verify that the smart strategy allows to recover some Wh (exactly 5570W*(3120s-3020s) = 154Wh), which represent about 3% of the available energy of the whole pack.

Conclusion

In this paper we have presented an innovative balancing solution also used to supply the 12V auxiliary network of an electric vehicle.

During the design of the vehicle's architecture: o we can remove the 12V battery o we replace the main DC/DC converter by several small converters (one per module). This allows us to:

o Perform a module balancing with a 100% of efficiency when other solutions have 0% up to 80%. o Increase the efficiency of DC/DC conversion, using several small converters instead of a big one. o Offset the dispersion of capacities between modules (best use of the energy of each module), thus increase range of the vehicle, especially with a battery pack presenting dispersion of capacities between modules, for example after maintenance. o And remove the low voltage battery and these advantages with a low impact on the cost, thanks to the 12V battery removing

Litterature

[1] Davide Andrea nBattery Management Systems for large lithium-ion battery packs", Publisher, Artech House, 2010

  to cell Energy is transferred from highest state of charge cell directly to low voltage DC bus. Standard solutions need a DCDC converter from high voltage to low voltage to supply the 12Vdc bus.

Figure 1 -

 1 Figure 1 -smart balancing with direct energy use

Figure 2 -

 2 Figure 2 -smart balancing with direct energy use -method applied to each module

Figure 3 -

 3 Figure 3 -DC/DC converter efficiency comparison of the 2 solutions

Figure 4 -

 4 Figure 4 -Simulation of 4 parallel converters

Figure 6 -

 6 Figure 6 -Current and voltage on auxiliary network

Figure 7 -

 7 Figure 7 -End of discharge with (red) or without (blue) cell's module balancing activated

21. First solution -zener or programmable zener

	Active/passive	Passive (no intelligence)
	Dissipative or not?	Yes
	Electronic used	zener or programmable zener
	Balancing time	End of charge
	Efficiency of balancing	0 % (no energy recovery from balancing
	Main Advantage	process) Simple
	Main Disadvantage	no cell's voltage measurement

22. Second solution -programmable resistances

	Active/passive	Active
	Dissipative or not?	Yes
	Electronic used	component like LT6802
	Balancing time	End of charge
	Efficiency of balancing	0 %
	Main Advantage	Simple, robust
	Main Disadvantage	Can't compensate dispersion of capacities
	23. Third solution -converters
	Electronic used	Isolated DCDC converters
	Balancing time	during charge or discharge
	Efficiency of balancing	estimated at about 80%
	Main Advantage	efficiency,	capable	to	compensate
	Main Disadvantage	dispersion of capacities cost, complexity

Active/passive

Active Dissipative or not?

No : Energy is transferred to other cells