Riadh Ben Halima

Karim Guennoun
email: kguennou@laas.fr

Khalil Drira
email: khalil@laas.fr

Mohamed Jmaiel
email: mohamed.jmaiel@enis.rnu.tn

Providing Predictive Self-Healing for Web Services: A QoS Monitoring and Analysis-based Approach

Keywords: QoS, Self-healing, Web service, Monitoring, Analysis

Monitoring and analysis of QoS are crucial steps for the provisioning of self-healing web services and for managing web service-based distributed interactive applications. Dealing with these issues becomes even more challenging when applications are dynamically built by composition of distributed services involving different service providers. In this case, assuming access to the internal logic and its implementation within the composed web services is not realistic. In this paper, we propose an architectural framework for monitoring and analysis of QoS driven by models for QoS analysis. This framework has been implemented and experimented for the web service technology within the European WS-DIAMOND 1 project. We consider the general context where only SOAP messages between web services are monitored. The main novelty of our approach is, on the one hand, to provide a generic application-independent framework. On the other hand, we provide models allowing QoS deficiencies to be detected and considered as an indicator of the health degradation of the monitored web services.

Introduction

Building distributed applications by dynamically selecting and connecting web services constitutes a powerful adaptation and repair mechanism. This also leads to complex composite systems where design-time requirement analysis solutions are no more sufficient. Additional management is needed not only for deciding about the capability of a given service to satisfy a given set of requirements, but also for assessing continuously this capability during the exploitation of the services. It relies on observing and analyzing the behavior of the service. This is useful for providing selfhealing and self-optimizing web services and associated applications as addressed by autonomic computing and communication. Both functional and non functional properties may be analyzed through observation of exchanged messages between the interconnected web services. For QoS-like properties, analysis may rely on a 1 Web Services -DIAgnosability Monitoring and Diagnosis standard SLA verification. Observing mismatches is targeted, and exploited for a number of purposes such as billing negotiation, or future selection of services. Assuming the existence of a pre-defined SLA may not apply in practice for all situations, such as free or informal cooperation between web services. SLA may not be known or defined in many situations. In these situations observing QoS parameters such as response and execution times may be analyzed by run-time comparison with similar values. When SLA is not predefined, analysis may be conducted following a collaborative technique by comparing, during its exploitation, the QoS parameters of a given service to these of services of the same class, obtained from past or current observations. This is the approach we adopted in the WS-DIAMOND project for providing self-healing solution for web service-based distributed applications. In this project, both functional and QoS properties are managed. The functional-related analysis is implemented for monitoring a given process execution, providing the so-called instancelevel self-healing. The QoS-related analysis is implemented for monitoring multiple process executions, providing the socalled class-level self-healing. QoS parameters values are analyzed in their trends as indicators of a predictable degradation of the service health. For this purpose, we implemented a monitoring framework and defined a measurement approach for QoS parameters analysis. Our approach is application-independent and is applicable for any deployment context, both for the requester and the provider sides.

No assumption is required on the internal logic and the implementation details of web services. We rely on SOAPlevel interceptors that may be deployed on the requester-side only when access policies restrict access to the provider-side. The analysis and diagnosis accuracy may require information about the global architecture when dealing with orchestration or choreography between several services cooperating to provide a common global function. This is reasonable since it may be deduced by analyzing the business process of the implemented application.

In this paper, we present a self-healing framework able to manage web service-based distributed interactive applications. Our framework focuses on QoS monitoring and uses models for QoS analysis. It considers the communication level monitoring while intercepting exchanged SOAP messages and extending them with QoS parameter values. It is achieved using dynamically deployed handlers. The analysis of logged QoS parameter values allows the detection of QoS deficiencies and the identification of the deficient source. This is achieved based on statistical functions and time-related constraints which represent an indicator of the health degradation of the monitored web services. This paper is organized as follows. Section 2 presents the elaborated models for monitoring and for QoS degradation detection. Section 3 presents the analysis algorithm of the degradation source. Section 4 details the proposed architectural framework within the FoodShop application. Section 5 discusses related work. The last section concludes the paper.

Models for Monitoring and Detection

Monitoring software applications aims to observe their constituting components to estimate the current health level. We introduce, in this section, a QoS-driven approach to achieve this task for web service-oriented systems. It separates clearly the business logic of a web service from its monitoring functionality. In addition, we believe that laying on QoS characteristics observations is an efficient way to predict and prevent service breakdown. Indeed, a continuous increasing of the response time or a continuous decreasing of the admission rate is a significant indicator to a future denial of service. Hence, we monitor the evolution of a given QoS characteristic more than its absolute values. QoS values such as response time may differ from one context to another (e.g. deployment machine, available network bandwidth, etc.) while the evolution of these values within the same context is the real indicator of the service health. The general approach involves two complementary aspects. On the one hand, we use statistical functions (mean, max, min and standard deviation 2 ) to have reference values related to the normal functioning of the system. And on the other hand, we use temporal chronicles to monitor the evolution of QoS values in order to avoid considering transient QoS degradation. A temporal chronicle or pattern is a set of on-off events, interlinked by time constraints, and whose occurrence depends on the context [START_REF] Dousson | Situation recognition: Representation and algorithms[END_REF]. Considered events may correspond for instance to detect or not that a measured QoS value exceeds a given threshold. Time constraints correspond mainly to the occurrence or not of a given event within a given time lapse. Several QoS parameters may be considered, such as response time [START_REF] Rosenberg | Bootstrapping performance and dependability attributes ofweb services[END_REF][START_REF] Saddik | Performance measurements of web servicesbased applications[END_REF], throughput [START_REF] Menascé | QoS issues in web services[END_REF][START_REF] Thio | Automatic measurement of a qos metric for web service recommendation[END_REF] and accuracy [START_REF] Menascé | QoS issues in web services[END_REF][START_REF] Rosenberg | Bootstrapping performance and dependability attributes ofweb services[END_REF]. These QoS parameters are measured while considering the following four time values as shown in Figure 1; t1: the time at which the request has been issued by the service requester, t2: the time at which the request has been received by the service provider, t3: the time at which the response has been 2 The standard deviation of a set of values distribution is a measure of the spread of its values issued by the service provider, and t4: the time at which the response has been received by the service requester. Our approach is predictive. It is based on observing the evolution of runtime computed QoS values to detect QoS degradation considered as the symptom of a future deficiency. In the detection process, we target situations where measured QoS values continuously go beyond an (absolutely or a relatively) acceptable threshold rather than a transient QoS value mismatch. Such a situation corresponds to the so-called QoS degradation and is an indicator of the system health worsening. To take into account a reference behavior, we use pre-computed and/or on-the-fly-computed statistical indicators. Considered events may correspond for instance to detecting that a measured QoS value exceeds a given threshold. Time constraints correspond mainly to the occurrence or the absence of a given event within a given time lapse. Monitoring QoS aims to evaluating the health of a given service and not only a specific interaction within a given conversation. The degradation detection scope includes interactions between all requesters and providers. In our context, observing N response time increases, when dealing with several requests from distinct requesters, is considered as a QoS degradation in the same way as for N response time increases when dealing with several requests from the same requester. N is related to service accuracy and transition probability among service state, namely Violation and OK. It represents the number of successive violations before degradation happens. For instance, for each measured Tresp, the service state may be TrespV, corresponding to a measured response time higher than a threshold (maximal acceptable value), or TrespOK, corresponding to a measured value under the threshold. The tolerated threshold of acceptable values of each QoS parameter is equal to the QoS parameter Average

λ = 1 +
When we choose an N's value greater than the smallest one (more than λ + 1), we accurate the degradation detection rate.

Figure 2 presents examples of temporal chronicles involving the response time QoS characteristic. The chronicles show two ways to compute the threshold of the maximal acceptable value using either pre-computed or on-the-fly computed values. For these chronicles, considered events relate to the occurrence or not of TrespOK and TrespV events at a given moment or a given interval. The first chronicle is triggered when three occurrences of event TrespV (t1, t2 and t3 in figure 2) are observed while no occurrence of event TrespOK is observed. The second chronicle is detected when three occurrences of event TrespV (t1', t2' and t3' in figure 2) are observed in a time interval I1. The third chronicle is triggered when three successive increases of the response time (t1", t2" and t3" in figure 2) are observed.

The chronicle based on an on-the-fly computed threshold may not be significant when increasing progressively the Tresp, because it increases the acceptable value interval and affects the service level agreement. Also, the chronicle based on a pre-computed threshold does not take into account the context of the running application and the Tresp measurement may be unsatisfactory. However, combining the two chronicles is more related to the context thanks to the on-runtime measured values, and more robust while avoiding the case of progressive and continuously increasing thanks to large scale values already measured. More complex chronicles may be designed for robust reasoning about QoS degradation.

We have developed algorithms for degradation detection, which trigger alarms when N successive violations happen (represented by Max_Nbr_Succ_Violation in Table 1 and Table 2).

As illustrated in Table 1, on each measured QoS parameter value (line 6), the algorithm increases the number of received violations (Nb_Received_Violation, in line 8) if the new value exceeds the max acceptable value (line 7). In case of non-successive violations (line 9), the execution will jump to the initialization at line 4. Otherwise, it increments the [START_REF] Saddik | Performance measurements of web servicesbased applications[END_REF]. In this algorithm, the Average and the Tolerated Delay, are pre-computed and deduced from a large scale experiment (lines 2,3).

In the algorithm presented in Table 2, the Average and the Tolerated Delay, are computed and deduced on-the-fly (lines 5,6), after each new measured QoS parameter value (line 4). Non-successive violations re-initialize the algorithm (line 9). In case of degradation, alarms are sent to the analysis service (line 12).

Models for Analysis

The analysis task lays on the monitoring and the detection of deficiency patterns. Indeed, QoS degradation may have several sources and may be triggered by one or many services of the application. For implementing effective selfhealing, we need to locate the deficient services and to reason about the degradation source. For instance, combining different QoS parameter values such as response time and execution time allows discriminating network and processing deficiencies while reasoning about architectural dependencies allows eliminating QoS degradation propagation that are irrelevant for repair.

Let's consider a pair of provider/requester for which alarms revealing QoS degradation on Tresp are raised, as shown in Table 3 at line 3. This algorithm discriminates between network (Communication) and processing (Execution) deficiencies. Three cases are distinguished.

In the first case (lines 3,4), the Texec value does not exceed the maximal acceptable value (Average + Tolerated Delay).

Since the response time is composed of execution time and communication time, we deduce that the degradation is located at the network level. In the second case (lines 5,6,7), only the Texec exceeds the maximal value and its delay (Delay Texec ) is the origin of the Tresp degradation raise. The degradation comes from the processing level. In the third case (lines 8,9), both communication time and execution time exceed the maximal acceptable values and the degradation is at both levels: processing and network.

After locating the degradation level, we start the reasoning about its source. -The Repair component: It switches requesters to substitutable providers using a dynamic binding connector. This architecture is deployed between each provider and its requesters. The Monitoring component is composed of several monitors; ReqSideMon, deployed one on each requester side and a unique monitor, ProvSideMon, deployed on the provider side. The Monitoring component intercepts request/response messages and extends them with metadata describing the involved QoS parameters and the related values obtained at runtime. These parameters may need to be processed on the provider side (as the execution time), or on the requester side (as the response time), or on both sides (as the communication time). In a local context, we deal separately with each provider and

Texec WS2 Texec WS1 Requester Delay WS2 Task Request Subtask Response WS1 WS2
Max acceptable execution time its requesters. For each web service provider, we deploy a monitor and for each requester, we deploy a monitor per web service. Additional components for logging, detecting and analyzing QoS degradation are implemented as web services. We deploy an instance of these components for each web service provider and its requesters. In a global context, we need to connect the components implementing the analysis in order to exchange the pertinent information. This allows the identification of the source of the QoS degradation through the whole set of involved web services, on the basis of the received alarms from the distributed detection components. Two different techniques are used to implement monitors. In, the first, we used a SOAP handler within the web service container, which intercepts SOAP envelop of each request and each response [START_REF] Ben Halima | A qos-driven reconfiguration management system extending web services with selfhealing properties[END_REF]. In the second, we used a HTTP proxy, which intercepts HTTP messages of the exchanged data between providers and requesters [START_REF] Pegoraro | A framework for monitoring and runtime recovery of web service-based applications[END_REF].

Application

We consider, here, the instantiation of the QoS manager to the FoodShop scenario of the WS-DIAMOND project. The FoodShop example is concerned with a web servicebased company that sells and delivers food. The company has an online Shop, several warehouses (WH1, ..., WHn) responsible for stocking imperishable goods. Customers (C1, ..., Ck) interact with the Shop in order to make their orders, pay the bills and receive their goods. In case of perishable items, that cannot be stocked, or in case of out-of-stock items, the warehouses must interact with several suppliers (SUP1, ..., SUPm). In this application, the shop acts as a requester who, for example, orders cereal and milk from the warehouse. The cereals are an imperishable product available at the warehouse, the request is served locally. The milk is a perishable product, not available locally and will be orders by the warehouse from the supplier. Hence the warehouse acts simultaneously as a provider and a requester. Figure 4 shows the QoS manager deployment details between each pair of requester/provider from the three considered actors: the FoodShop, Shop, the warehouse, WH1, and the supplier, SUP1. Grouping the analysis WSs as illustrated by the dashed box of Figure 4, allows comparing execution time of the two involved web services, WH1 and SUP1. This makes possible to diagnosis correctly the QoS degradation and to decide, for instance, substituting only SUP1, considered as the only deficient web service. More precisely, we consider the global QoS-related dependencies between these three services showing the importance of the global monitoring and analysis for efficient reconfiguration actions. In the first phase, these dependencies are given as assumptions for the Analysis web services. This requires the knowledge of the all possible interactions between web services which are not easy to fix. In the second phase, we used WS-Addressing [START_REF] Weerawarana | Web Services Platform Architecture: SOAP, WSDL, WS-Policy, WS-Addressing, WS-BPEL, WS-Reliable Messaging and More[END_REF] in order to associate together requests of both synchronous and asynchronous invocations (using the message headers MessageId and RelatesTo) and to handle dependent services (using the message header Source). Doing so, we deduced automatically the structural dependencies from the monitoring data.

Figure 5. QoS degradation propagation

For instance, we consider the case of repeated violations between "ordering milk and cereals" and "receiving these products", detected inWH1 and SUP1 web services. In this situation, the first QoS manager which monitors interactions between the Shop and the WH1 and the second QoS manager which monitors between the WH1 and the SUP1 web services, detect QoS degradation (using algorithm showed in Table 2). Then, it locates the deficient level, and identifies the degradation source (see Figure 3 for more details). Texec WH1 and Texec SUP1 exceed the maximal acceptable values and the detection services trigger alarms. The QoS manager analysis services identify that the degradation is coming from Texec SUP1 , and that Texec WH1 deficiency is a degradation propagation. SUP1 is substituted. Figure 5 details the developed prototype of the FoodShop

SUP1

Delay Injector application 3 . The consumer acts as a requester of the Shop web service which starts a new process. Between each requester and each provider, we deploy the QoS manager. We use a Delay Injector to simulate QoS degradations. As a result, the Detection and Analysis web services detect and identify the degradation. The Repair web service asked for recovery, substitutes SUP1 by SUP2 in a seamless way to both the requester and the provider. We use Apache Tomcat5.9 as a web server, Axis1.4 as a web service container, ActiveBPEL2.1 as a BPEL engine, soapUI1.5 as a client, MySQL5 as a database management system, and Java as a programming language. We computed the N value (see section 2), in order to estimate after how much successive violations we trigger a substitution operation. The used values and probabilities are deduced from past execution experiments under the French Grid5000 At the level of the A, we inject degradation and we follow the behavior of QoS manager. After three successive violations, the QoS manager detects a degradation (red curve in figure 6), and reacts by substituting the SUP1 web service at point B. After rerouting requesters to the new supplier (SUP2), the response time regains the normal behavior (blue curve in figure 6). In order to estimate the monitor overload, we conduct a large scale experiments under the gird5000 to measure the response time of web services while varying the requester's number from 1 to 500. We obtained the two curves shown in Figure 7. In the first, the monitoring is achieved using the ReqSideMon and the ProvSideMon (monitoring components). In the second, the measurement is done in the client code and without using monitors. We can see for Details about the experiments are available at http://www.laas.fr/~khalil/TOOLS/QoS-4-SHWS/grid5000experiment.pdf instance that for less than 50 concurrent clients, both curves are similar and the overload of monitors is negligible. For the largest requester's number (500), the overload is smaller than 0.5s.

Related Work

In this section, we first present different QoS monitoring approaches compared to our work. However, the monitoring may be performed differently at three levels, namely: service level [START_REF] Mani | Understanding quality of service for web services[END_REF][START_REF] Rosenberg | Bootstrapping performance and dependability attributes ofweb services[END_REF], communication level [START_REF] Ben Halima | A qos-driven reconfiguration management system extending web services with selfhealing properties[END_REF][START_REF] Thio | Automatic measurement of a qos metric for web service recommendation[END_REF][START_REF] Repp | A crosslayer approach to performance monitoring of web services[END_REF] (as our approach) and orchestration level [START_REF] Barbon | Run-time monitoring of instances and classes of web service compositions[END_REF][START_REF] Bianculli | Monitoring conversational web services[END_REF]. The service level monitoring considers the basic monitoring approach. It inserts the monitoring code within the web service requesters/providers code. Such monitoring may be achieved while inserting directly, for instance, a timer within the client code [START_REF] Mani | Understanding quality of service for web services[END_REF], or encapsulating it in an aspect, which is merged into the functional code using the Aspect Oriented Programming (AOP) [START_REF] Rosenberg | Bootstrapping performance and dependability attributes ofweb services[END_REF]. The communication level monitoring intercepts exchanged messages between web service providers and requesters. Such approach targets only the interactions where a given service is involved and do not need access to its internal state which is generally hidden due to security reasons. This approach may be applied at the SOAP level while using standard XML parsing libraries [START_REF] Ben Halima | A qos-driven reconfiguration management system extending web services with selfhealing properties[END_REF][START_REF] Thio | Automatic measurement of a qos metric for web service recommendation[END_REF], or at the HTTP level while using proxies [START_REF] Repp | A crosslayer approach to performance monitoring of web services[END_REF]. The orchestration level monitoring supervises orchestrated services as BPEL using handlers provided by the orchestration engine such as Active BPEL. Such approach may observe its behavior by intercepting the input/output messages that are received/sent by the processes [START_REF] Barbon | Run-time monitoring of instances and classes of web service compositions[END_REF]. The approach presented in [START_REF] Bianculli | Monitoring conversational web services[END_REF] monitors behaviors of orchestrated web services with respect to an already expected behavior which is specified formally with algebraic notations and saved in a registry. The monitoring is achieved using the AOP inside the BPEL engine. The analysis of a web service behavior may be performed at instance level that deals with the execution of a single instance [START_REF] Ardissono | Enhancing web services with diagnostic capabilities[END_REF] from a specific requester, either at class level that considers all instances like our work. The work in [START_REF] Barbon | Run-time monitoring of instances and classes of web service compositions[END_REF] deals with boolean and time related properties at instance and class levels. In [START_REF] Ardissono | Enhancing web services with diagnostic capabilities[END_REF], authors propose an instance level and hierarchical analysis for complex services. They deploy local analyzer on each basic service, and a global one associated with the workflow that collects local analysis and reasons about faults in current running activity. However, web services are usually multi-providers, which do not allow modifying their services in order to interact with an external component, like the local analyzer. But, in our approach, no assumptions are required. Robinson [START_REF] Robinson | Monitoring web service requirements[END_REF] presents a goal-driven methodology for monitoring requirements using temporal logic and KAOS. It uses agents with specific patterns in order to inspect the observable system events. Contrarily to our approach, this approach is not generic for web service-based applications. It supposes that it can access to provider sites in order to deploy monitors to track web services. But, this is not realistic when involving different service providers.

Conclusion

In this paper, we presented an application-independent framework to monitor, detect and analyze QoS degradation for web services. Our framework relies on logging and appropriately analyzing web service conversations using SOAP messages header information. It applies to both situations where a reference model of QoS values is available and situations where such a model has to be built dynamically on the fly during the execution of the application.

Acting at the communication level by intercepting conversations allowed us to handle web services as black boxes. Two prototypes have been implemented at the SOAP and HTTP levels using service container handlers (Axis) and HTTP proxies, respectively. Our implementation exploits header information to manage both synchronous and asynchronous interactions for which QoS values are computed differently. Two application scenarios have been successfully experimented. The first scenario implements a collaborative review process using massively interacting services [START_REF] Ben Halima | A qos-driven reconfiguration management system extending web services with selfhealing properties[END_REF]. The second, discussed in the paper, implements a supplier chain-like scenario where several web services acts simultaneously as providers and requesters of each others with highly interlocked conversations.

Our future work includes extending and improving our framework by implementing more advanced detection and analysis algorithms that can learn from previous execution traces to choose the best decision. Our approach was successfully experimented with an orchestrated web servicebased distributed application using a centralized QoS manager. Managing choreographed web services may also be implemented by a distributed deployment of replicated copies of the QoS manager. Our interceptor-based framework has also been used to experiment dynamic routing between a requester and a collection of equivalent web services providers. Managing communications at the HTTP level showed more powerfulness for handling statesensitive cooperation scenarios. Such situations may be encountered when handling choreographed between two or more orchestrated collections of web services. In such hybrid scenarios state preservation is necessary when a new provider is used to substitute a degraded provider.

Figure 1 .

 1 Figure 1. Measured times for QoS Monitoring The considered QoS parameters are: • The Response Time: defined as the time elapsed between sending a request and receiving its response; Tresp = t4 -t1, • The Execution Time: defined as the time elapsed for processing a request; Texec = t3 -t2, • The Communication Time: defined as the round trip time of a request and its response; Tcomm = Tresp -Texec, • The Throughput: defined as the amount of requests that can be processed in a specified period of time; Throughput = Number of requests/period of time, and • The Accuracy: defined as the the success rate produced by the service; Accuracy = Number of successful responses/Total number of requests. Failed responses correspond to exceptions on the requester side.Our approach is predictive. It is based on observing the evolution of runtime computed QoS values to detect QoS degradation considered as the symptom of a future deficiency. In the detection process, we target situations where measured QoS values continuously go beyond an (absolutely or a relatively) acceptable threshold rather than a transient QoS value mismatch. Such a situation corresponds to the so-called QoS degradation and is an indicator of the system health worsening. To take into account a reference behavior, we use pre-computed and/or on-the-fly-computed statistical indicators. Considered events may correspond for instance to detecting that a measured QoS value exceeds a given threshold. Time constraints correspond mainly to the occurrence or the absence of a given event within a given time lapse. Monitoring QoS aims to evaluating the health of a given service and not only a specific interaction within a given conversation. The degradation detection scope includes interactions between all requesters and providers. In our context, observing N response time increases, when dealing with several requests from distinct requesters, is considered as a QoS degradation in the same way as for N response time increases when dealing with several requests from the same requester. N is related to service accuracy and transition probability among service state, namely Violation and OK. It represents the number of successive violations before degradation happens. For instance, for each measured Tresp, the service state may be TrespV, corresponding to a measured response time higher than a threshold (maximal acceptable value), or TrespOK, corresponding to a measured value under the threshold. The tolerated threshold of acceptable values of each QoS parameter is equal to the QoS parameter Average

  and the Tolerated Delay (TD) which is proportional to the standard deviation. It can be pre-computed, on the basis of already achieved experiments, or computed on-the-fly from current measured values. N is equal to the number of successive violations leading to the service invocation failure. In order to determinate a relevant value of N, we use the following expression, which corresponds to the probability of N successive TrespV less than the mean probability of the failed request measured experimentally (1-Accuracy): P[N successive TrespV] ≤ (1 -Accuracy) In addition, the probability that "the next state is TrespV", is equal to the probability of being in state TrespOk multiplied by the probability of going from this state to the state TrespV added to the probability of being in state TrespV multiplying the probability of staying in this state for the next invocation: P[any state → TrespV] = P[TrespOK] * P[TrespOK → TrespV] + P[TrespV] * P[TrespV → TrespV] The probability of obtaining N successive violations is equal to the probability to reach a TrespV state, after leaving any state, multiplied by the probability of staying in TrespV state (N-1) times: P[N successive TrespV] = P[any state → TrespV] * P[TrespV → TrespV] N-1 . When replacing the probability P[N successive TrespV] in the first inequality, we obtain the following expression providing the lower bound for N: P[any state → TrespV] P[TrespV → TrespV]N-1 ≤ (1 -Accuracy) N ≥ λ, where:

Figure 2 .

 2 Figure 2. Examples of chronicle detection models

5 else 6 if 7 Degradation_Levels=

 567 Delay Texec = Texec -(AvgTexec+ TDTexec) (Tresp -Delay Texec ≤ AvgTresp + TDTresp) then We implemented a QoS manager providing a self-healing architecture in the context of the WS-DIAMOND project. It includes four main components [3]: -The Monitoring component: It includes observing and storing relevant QoS parameter values entities. It is composed of: • The Requester-Side Monitor which implements the QoS monitoring at the requester side (in short: ReqSideMon), and • The Provider-Side Monitor which implements the QoS monitoring at the provider side (in short: ProvSideMon) • The Logging Manager which manages QoS monitoring data. -The Detection component: It inspects the service behavior and detects QoS degradation. -The Analysis component: It reasons about the degradation by exploiting the QoS values stored by the monitoring and identifies the deficiency source. Then, it sends the analysis to the Repair component for possible reconfiguration.

Figure 4 .

 4 Figure 4. Details of QoS manager applied to the FoodShop scenario

  4 . P[any state → TrespV ] = 0.78 0.13 + 0.23 0.09 = 0.1221 With P[TrespOK] = 0.78, P[TrespV ] = 0.23, P[TrespOK → TrespV ] = 0.13, and P[TrespV → TrespV ] = 0.09. 0.1221 0.09N-1 ≤ 0.04, With Accuracy= 0.96. N ≥ 2.115 That means, N must at least be equal to 3.

Figure 6 .

 6 Figure 6. Runtime recovering of degradationFigure6illustrates the whole self-healing cycle applied to the Foodshop application. The QoS manager monitors response time at runtime of the SUP1. It detects degradation according the first chronicle showed in Figure2, with N=3. The green curve represents the normal execution of SUP1. At the level of the A, we inject degradation and we follow the behavior of QoS manager. After three successive violations, the QoS manager detects a degradation (red curve in figure6), and reacts by substituting the SUP1 web service at point B. After rerouting requesters to the new supplier (SUP2), the response time regains the normal behavior (blue curve in figure6). In order to estimate the monitor overload, we conduct a large scale experiments under the gird5000 to measure the response time of web services while varying the requester's number from 1 to 500. We obtained the two curves shown in Figure7. In the first, the monitoring is achieved using the ReqSideMon and the ProvSideMon (monitoring components). In the second, the measurement is done in the client code and without using monitors. We can see for

Figure 7 .

 7 Figure 7. Overload of monitoring

Table 1 .

 1 Degradation detection Algorithm on response time (Pre-computed average) number of obtained violation until triggering alarms (line

Table 2 .

 2 The analysis is not limited to interactions between a single pair of requester/provider. It includes the interactions of the web service with multiple other web services of the global application. This global view of the system gives us the possibility to identify the source of the degradation, and to optimize the repair effort by avoiding over-reactions and useless reconfiguration actions. Such a situation occurs for QoS degradation due to delay propagation. Degradation detection Algorithm on response time (On-the fly computed average).

	For considering structural dependencies, the monitoring is
	targeting global QoS parameters belonging to several pairs of
	providers and requesters. Typically, we consider execution
	time related to a request sent to two different providers
	involved in the same orchestration or in the same
	choreography.
	Let's consider the scenario of interlocked communication
	depicted in Figure 3. WS2 execution time exceeds the
	maximal acceptable value. It is deficient. Monitoring and
	detection mechanisms related to service WS1 also detects
	execution time degradation due to the propagation
	phenomena. Not detecting that the second deficiency is a
	simple propagation of the first one may lead to useless
	reconfiguration actions.
	As illustrated in Figure 3, the requester's message is
	processed by WS1, which calls WS2 to achieve a part of the
	required task. Texec WS1 represents the execution time of the
	first pair Requester/WS1 and Texec WS2 represents the
	execution time of the second pair WS1 (as a requester)/WS2.
	WS2 generates an important delay (Delay WS2 ) during the
	processing of each request leading to a high overhead for
	both Texec WS1 and Texec WS2 values. The two detection
	processes, related to Texec WS1 and Texec WS2 trigger alarms.

In the case of naive analysis, two independent analysis processes are considered. The first is related to WS2 web service. It compares the response time and the communication time with the maximal acceptable values. It deduces that the problem comes from the processing level. It decides, for instance, to substitute WS2 by an equivalent web service. Similarly, the local analysis related to WS1 also

Demonstrator is available at http://www.laas.fr/~khalil/TOOLS/QoS-4-SHWS/Video.html

detects a QoS degradation. It decides also to substitute WS1 by an equivalent web service.

Figure 3. QoS degradation propagation

When the analysis is made locally and the degradations of WS1 and WS2 are considered separately, each analysis leads to the verdict of a local deficiency: Local_Analysis(WS1, degradation) WS1 deficiency and Local_Analysis(WS2, degradation) WS2 deficiency. When this analysis verdict is handled by repair functionalities, reconfiguration actions would substitute each one of the two services: Substitute(WS1,WS1′), where WS1' is equivalent to WS1. and Substitute(WS2,WS2′), where WS2' is equivalent to WS2. When considering global architectural dependencies, analysis is more accurate. It makes possible to identify that only WS2 is the source of degradation. Detected degradation of WS1 is correctly analyzed as a propagation manifestation.

Global_Analysis(WS1,WS2, degradation, degradation) ≡ Local_Analysis(WS1, degradation) Local_Analysis(WS2, degradation) (Texec WS1 -Delay

WS2 deficiency WS1 uses a deficient WS With WS1 degradation is due to a degradation propagation. The corresponding reconfiguration sequence is more efficient and requires only substituting WS2: Substitute(WS2,WS2′) where WS2' is equivalent to WS2. Different analysis situations may be distinguished as follows: 1-First case: WS2 responses come with delay and WS1 responses come with delay after eliminating the WS2's delay propagation. Both services are deficient. In this case, the global analysis is equivalent to the local analysis of WS1 and WS2. Both services have to be substituted.

Global_Analysis(WS1,WS2, degradation, degradation) ≡ Local_Analysis(WS1, degradation) Local_Analysis(WS2, degradation) (Texec WS1 -DelayWS2 ≥ AvgTexecWS1+TDTexecWS1)

WS1 deficiency WS2 deficiency 2-Second case: WS2 responses come with delay and if we eliminate the WS2's propagated delay, WS1 responses would not come with delay. Both services seem to be deficient, but the WS2 is the source of degradation, and the delay engendered by this degradation (Delay WS2 ) propagates and affects the WS1. The global analysis identifies the degradation source, and requests for WS2 substitution. and design of correctness properties including testability, robustness, adaptability and reconfiguration. He is or has been involved in several national and international projects in the field of distributed and concurrent communicating systems. He is author of more than 150 regular and invited papers in international conferences and journals. He is or has been initiator of different national and international projects and collaborations in the field of networked services and distributed and communicating systems. Khalil DRIRA is or has been member of the programme committees of international and national conferences. He is member of the editorial board of different international journals in the field of software architecture and communicating and distributed systems. Khalil DRIRA has been editor of a number of proceedings, books and journal issues in these fields. More details are available on his wiki: http://www.laas.fr/~khalil/wiki. He published regular and invited papers in international conferences and journals, and has co-edited four conferences proceedings and three journals special issues on these subjects.

Global_Analysis(WS1,WS2, degradation, degradation) ≡ Local_Analysis(WS1, degradation) Local_Analysis(WS2, degradation) (Texec

Mohamed


Lazhar Labiod

Mohamed Nadif

Power Attributed Graph Embedding and Clustering

Keywords: Attributed graph, Embedding, Clustering, Spectral rotation

Representation learning is a central problem of Attributed Networks data analysis in a variety of fields. Given an attributed graph, the objectives are to obtain a representation of nodes and a partition of the set of nodes. Usually these two objectives are pursued separately via two tasks that are performed sequentially, and any benefit that may be obtained by performing them simultaneously is lost. In this paper we propose a Power Attributed Graph Embedding and clustering (PAGEC for short) in which the two tasks, embedding and clustering, are considered together. To jointly encode data affinity between node links and attributes, we use a new powered proximity matrix. We formulate a new matrix decomposition model to obtain node representation and node clustering simultaneously. Theoretical analysis shows the close connections between the new proximity matrix and the random walk theory on a graph. Experimental results demonstrate that the PAGEC algorithm performs better, in terms of clustering and embedding, than stateof-the-art algorithms including deep learning methods designed for similar tasks in relation to attributed network datasets with different characteristics.

I. INTRODUCTION

Attributed Networks (AN) [START_REF] Qi | Exploring context and content links in social media: A latent space method[END_REF] have been used to model a wide variety of real-world networks, such as academic and healthcare networks, where both node links and attributes/features are available for analysis. In contrast to plain networks that contain only node links and dependencies, in AN each node is associated with a valuable set of features.

More recently, representation learning has become an important objective in applications including social networks, academic citation networks and protein-protein interaction networks. Attributed Network Embedding (ANE) [START_REF] Cai | A comprehensive survey of graph embedding: Problems, techniques, and applications[END_REF] seeks to obtain a continuous low-dimensional matrix representation of the nodes in a network that preserves the topological structure and node attribute proximity of the original network.

Although Network Embedding (NE) has given rise to a number of approaches such as [START_REF] Yu | Selfattentive attributed network embedding through adversarial learning[END_REF], research on ANE has so far received little attention [START_REF] Chang | Heterogeneous network embedding via deep architectures[END_REF]. Unlike NE, which learns from plain networks, ANE seeks to utilize information relating both to node proximity and to the affinity of node attributes within the network. Since the two information sources are not the same, it is difficult for existing NE algorithms to be directly applied to ANE.

Learned representations have been shown to be helpful in many learning tasks such as network clustering [START_REF] Wang | Mgae: Marginalized graph autoencoder for graph clustering[END_REF], node visualization [START_REF] Dai | Adversarial network embedding[END_REF], node classification [START_REF] Huang | Label informed attributed network embedding[END_REF], and link prediction [START_REF] Pan | Adversarially regularized graph autoencoder for graph embedding[END_REF], and as a consequence ANE is becoming a pressing topic for research in which challenging issues of high-dimensionality, sparsity and nonlinearity need to be addressed.

Existing AN clustering methods have been applied widely, but they often perform poorly because of (1) the likelihood that an approximate continuous embedding solution will deviate significantly from a good discrete clustering, and (2) a loss of information between the independent stages, namely continuous embedding generation and embedding discretization.

II. RELATED WORK

Learning a low-dimensional vector representation for each vertex of a network data is a good way to analyze the network. This task attracted the attention of several authors [START_REF] Yu | Learning deep network representations with adversarially regularized autoencoders[END_REF] for different purposes such as detection anomalies in dynamic networks [START_REF] Yu | Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks[END_REF]. Recently, various models have been proposed for attributed networks showing that jointly learning network representations with network topology information and vertex attributes enhance the performance on various tasks including clustering; in [START_REF] Guo | Cfond: consensus factorization for co-clustering networked data[END_REF] the authors demonstrated the benefits of clustering. In this regard, a number of approaches have been developed, based on matrix decomposition, graph clustering, and deep representation learning. Most of the work that we consider in our comparisons in Section V are the following. Spectral Clustering [START_REF] Tang | Leveraging social media networks for classification[END_REF] is a widely used approach for learning social embedding. With the advent of deep learning, several works have tackled the same problem. Graph Encoder [START_REF] Tian | Learning deep representations for graph clustering[END_REF] learns graph embedding for spectral graph clustering, while DNGR [START_REF] Cao | Deep neural networks for learning graph representations[END_REF] trains a stacked denoising autoencoder for graph embedding. [START_REF] Perozzi | Deepwalk: Online learning of social representations[END_REF] developed DeepWalk, a network representation approach which encodes social relations into a continuous embedding space. [START_REF] Kipf | Variational graph auto-encoders[END_REF] proposed GAE, using an autoencoder-based unsupervised framework for attributed network data embedding, and VGAE, a variational graph autoencoder approach for graph embedding with both node link and node attribute information. [START_REF] Wang | Mgae: Marginalized graph autoencoder for graph clustering[END_REF] presented MGAE, a marginalized graph autoencoder for graph clustering. [START_REF] Pan | Adversarially regularized graph autoencoder for graph embedding[END_REF] proposed ARGA, which is the most recent adversarially regularized autoencoder algorithm using a graph autoencoder to learn the embedding, while the ARVGA [START_REF] Pan | Adversarially regularized graph autoencoder for graph embedding[END_REF] algorithm uses a variational graph autoencoder to learn the embedding. More recently, [START_REF] Zhang | Attributed graph clustering via adaptive graph convolution[END_REF] developed a new attributed graph clustering algorithm AGC based on adaptive graph convolution. In [START_REF] Wang | Attributed graph clustering: A deep attentional embedding approach[END_REF] a deep attentional embedding approach DAEGC for attributed graph clustering is proposed.

The sequential process in which a learned representation is obtained before clusters are then obtained using a clustering method is a source of problems. The two tasks do not share the same objective and are carried out separately. For this reason, simultaneous embedding and clustering are frequently used to improve representation learning by making use of structure information from the clusters. A number of approaches have been proposed for the representation learning and clustering tasks [START_REF] Yamamoto | A general formulation of cluster analysis with dimension reduction and subspace separation[END_REF], [START_REF] Allab | Simultaneous spectral data embedding and clustering[END_REF]. However, none of these approaches has attempted to integrate available information contained within a network, which can be seen as a deficiency. In order to overcome this, we propose a novel simultaneous ANE and clustering scheme which simultaneously (1) learns embedding from information on network topology and on attributes, and (2) learns continuous embedding and discrete clustering labels. Specifically, we explicitly enforce a discrete transformation on the intermediate continuous labels (embedding), which leads to a tractable optimization problem with a discrete solution. The key challenge is knowing how to integrate the information on both node links and attributes in order to carry out node representation learning and discrete node clustering at the same time. To compensate for the information loss when sequential clustering is relaxed, and to obtain a discrete clustering solution, we use a smooth transformation (e.g., rotation) from the relaxed continuous embedding to a discrete solution. In this sense, the continuous embedding only serves as an intermediate product.

To the best of our knowledge, simultaneous attributed network embedding and clustering in a unified learning framework has not so far been adequately investigated. The goal of the present work is to look at this issue by considering matrix decomposition as the embedding framework.

III. PROPOSED METHOD

In this section we describe the Simultaneous Attributed Network Embedding and Clustering method that we have called PAGEC. We present the formulation of an objective function and an effective algorithm for data embedding and clustering. But we begin by describing the construction of two matrices S and M integrating both types of information -content and structure information -that we use to achieve our objective.

A. Content and Structure information

An attributed network G = (V, E, X) consists of the set of nodes V , the set of links E ⊆ V ×V, and X = [x 1 , x 2 , . . . , x n ] where n = |V| and x i ∈ R d is the feature/attribute vector of the node v i . Formally, the graph can be represented by two types of information, namely the content information X ∈ R n×d and the structure information A ∈ R n×n , where A is an adjacency matrix of G and a ij = 1 if e ij ∈ E otherwise 0; we consider that each node is a neighbor of itself, then we set a ii = 1 for all nodes. We therefore model node proximity by an (n × n) transition matrix W given by W = D -1 A, where D is the degree matrix of A defined by

d ii = n i =1 a i i .
In order to utilize additional information about node similarity from X, we first preprocess the above dataset X to produce similarity graph input W X of size (n × n); we then construct a K-Nearest-Neighbor (KNN) graph. To this end we use the heat kernel and L 2 distance, KNN neighborhood mode with a given K and we set the width of the neighborhood σ = 1. Note that any appropriate distance or dissimilarity measure can be used. Finally we combine node proximity from both content information X and structure information W in an (n × n) matrix S. We thus propose perturbing the similarity W by adding the similarity from W X ; we choose to define S as follows S = W + W X . In Figure 1 multidimensional scaling is applied to W and S in order to illustrate the impact of W X . Note that with S, the sparsity is overcome by the presence of W X . Later we will see the interest of using W X in S. Since clustering is our main objective, we propose integrating S in the formulation of a new data representation by assuming that nodes with the same label tend to similar social relations and similar node attributes. This reflects the fact that labels are strongly influenced by both content and structure information and are inherently correlated to the two information sources, and we are reminded of the idea underlying Canonical Discriminant Analysis (CDA), which is a dimension-reduction technique related to principal component analysis (PCA) and canonical correlation [START_REF] Goodfellow | Deep learning[END_REF]. Given groups of observations with measurements on attributes, CDA derives the linear combination of variables that has the highest possible multiple correlation with the groups. It can be seen as a particular kind of PCA in which the observations belonging to a same group are replaced by their centroid. The new data representation M = (m ij ) of size (n × d) can be considered as a multiplicative integration of W and X replacing each node by the centroid of its neighborhood (barycenter): i.e, m ij = n k=1 w ik x kj , ∀i, j or M = WX. Since W is a transition matrix, in order to make better use of the random walk properties we use W p to explore the structure of W, where a random walk includes multiple steps instead of only one. M is then given by M = W p X where p ∈ N + .

(

) 1
This modification is simple to describe and leads to a refinement of the feature matrix X, creating what can be seen as a smooth version with each row of M converging to the prototype of its class. M will therefore be more helpful in the clustering task. In Figure 2 it is interesting to visualize the impact of W in the formulation of M. To this end we apply CDA on X and M and indicate the seven true clusters of the Cora dataset. This reveals clusters separated with M = WX and, even better, separated with M = W 8 X, showing the impact of W p , which can be seen already to do a good job independently of clustering.

B. Definition of the model and Optimisation

Let k be the number of clusters and also the number of components into which the data is embedded. With M and S, our PAGEC method seeks to obtain the maximally informative embedding with respect to the clustering structure Tr(S t ) where Tr(.) denotes Trace(.). We have respectively 2.58%, 5.41% and 10.52%.

in the attributed network data. The proposed objective function F(B, Z, Q, G) to be minimized is consequently given by

M -BQ 2 + λ S -GZB 2 s.t. B B = I, Z Z = I, G ∈ {0, 1} n×k (2)
where G = (g ij ) of size (n × k) is a cluster membership matrix, B = (b ij ) of size (n × k) is the embedding matrix, and Z = (z ij ) of size (k×k) is an orthonormal rotation matrix which most closely maps B to G ∈ {0, 1} n×k . Q ∈ R d×k is the features embedding matrix. Finally, the parameter λ is a non-negative value and can be viewed as a regularization parameter.

The idea behind factorizing M and S is so that nodes with similar proximity, those with greater similarity in the two matrices, will have closer representations in the latent space given by B. This way, optimizing (2) leads to a clustering of the nodes into k clusters given by G. Note that both tasksembedding and clustering -are performed simultaneously and supported by Z; this is the key to attaining good embedding while taking the clustering structure into account.

The first term of PAGEC can be seen as a generalization of canonical discriminant analysis in which the partition of nodes is replaced by a more general graph structure defined a priori on the set of nodes. To infer the latent factor matrices Z, B, Q and G from M = W p X and S = W + W X , we derive an alternating optimization algorithm. To this end, we make use of the following proposition.

Proposition 1. Given S ∈ R n×n , G ∈ {0, 1} n×k , Z ∈ R k×k , B ∈ R n×k , we have S -GZB 2 = S -SBB 2 + SB -GZ 2 (3)
Proof. First, since B B = I and Tr(AB) = Tr(BA) we have

GZB 2 = Tr(BZ G GZB ) = Tr(Z G GZ) = GZ 2 .
Similarly we have SBB 2 = SB 2 . This leads to

(a) S -GZB 2 = S 2 + GZ 2 -2Tr(SGZB ). (b) S -SBB 2 = S 2 + SBB 2 -2Tr(SBB S ) = ||S|| 2 + ||SB|| 2 -2||SB|| 2 since S = S = ||S|| 2 -||SB|| 2 . (c) SB -GZ 2 = SB 2 + GZ 2 -2Tr(SGZB ).
Summing (b) and (c) (the right terms of ( 3)) leads to (a).

Below we detail the different steps involved in inferring Z, Q, B and G.

Compute Z. By fixing G and B we reduce the problem that arises in (2) to min Z S -GZB 2 . From proposition 1, we deduce that

min Z S -GZB 2 ⇔ min Z SB -GZ 2 (4)
which can be reduced to max Z Tr(G SBZ) s.t. Z Z = I. It was shown (page 29) in [START_REF] Berge | Least squares optimization in multivariate analysis[END_REF], with UΣV the SVD for G SB, that

Z = UV . (5)
This problem turns out to be similar to the well-known orthogonal Procrustes problem [START_REF] Schönemann | A generalized solution of the orthogonal procrustes problem[END_REF].

Compute Q. Given G, Z and B, (2) is reduced to

min Q M -BQ
2 , and we get

Q = M B. (6)
It is therefore possible for Q to be seen as an embedding of attributes.

Compute B. Given G, Q and Z, (2) is equivalent to max B Tr((M Q + λSGZ)B ) s.t. B B = I. Similarly to when computing Z, let Û Σ V be the SVD for (M Q+λSGZ), and we get

B = Û V . (7)
It is important to emphasize that at each step, B makes use of the information from the matrices Q, G, and Z. This highlights one of the aspects of a simultaneous embedding and clustering.

Compute G: Finally, given B, Q and Z, the problem (2) is equivalent to min G SB -GZ 2 since from (2) and (3) G is present only in SB -GZ . Thereby, we are faced with an assignment step like that case of the k-means algorithm where G is a cluster membership matrix. Therefore, it is computed as follows. We first fix Q, Z, B, let B = SB we then compute

g ik = 1 if k = arg min k || bi -z k || 2 0 otherwise. ( 8
)
A the (t+1)th iteartion, this leads to

B(t) -G (t) Z (t) 2 ≥ B(t) -G (t+1) Z (t) 2 .
The steps of the PAGEC1 algorithm that uses S, which we will refer to as PAGEC S , are outlined in Algorithm 1. The convergence of PAGEC S is guaranteed due to analytical solutions of Q, Z, B (refitting step ) and assignment step carried out by G. However, according to the initialization it will reach only a local optimum. We therefore started the algorithm several times and selected the best result minimizing the objective function [START_REF] Cai | A comprehensive survey of graph embedding: Problems, techniques, and applications[END_REF]. IV. POWERED PROXIMITY MATRIX Before assessing the Algorithm 1, we shall first present some theoretical reasons to explain why the proposed PAGEC model is able to outperform recent state-of-the-art methods proposed for the purpose. Let us recall that the key elements when employing this model are, first, designing an affinity (or proximity) matrix that can jointly encode information from the structure W and attributes X, and, secondly, embedding and clustering AN simultaneously so that there is a mutual reinforcement between B and G.

With the PAGEC model, we use a powered proximity matrix to harness the benefits of a random walk process. The idea behind using W p is to be able to explore the structure of W when a random walk includes multiple steps instead of just one. We know from the theory of Markov chains that W p (where p is any positive integer ) is obtained by multiplying W by itself p times, and consequently, if W = VΛV , then we have W p = VΛ p V , where V is the matrix whose n th column is v n . The eigensystem of W is therefore constituted by λ n , v n , while the eigensystem of W p is constituted by λ p , v n .

In a prior work [START_REF] Meila | Learning segmentation by random walks[END_REF], it was noted that for many natural problems, W is an approximately block stochastic matrix, and hence the first k left eigenvectors of W are approximate piecewise constant over the k almost invariant subsets of rows. The iterative random walk process converges to the approximated data W p , where each row and each column moves towards its prototype. In other words, this process converges to an equilibrium (steady) state. The matrix W is composed of k << n quasi-similar rows, where each row is represented by its prototype; see Figure 3.

Let us consider W p , the p th order transition matrix, as the affinity matrix. The cell w m,n in W p gives the total probability that a random walk x j beginning at m will end up in n after p steps, considering all possible paths between the nodes. We would expect this probability w m,n to be high if there is a good path between m and n, and low otherwise, the intended outcome being a block diagonal matrix suitable for clustering data [START_REF] Meila | Learning segmentation by random walks[END_REF]. However, in practice we usually observe that W p behaves differently according to the value of p. If data points i, j are in the same cluster there are values of p for which the i th and j th rows of W p become very similar. Consequently, if data points i, j are similar, then after a sufficient number of steps we can expect that particles that begin a random walk in each of them will have the same distribution for their locations after p steps. We also remark that by varying the number of steps p we explicitly explore similarities at different scales in the data, and as p increases we would expect to find a coarser structure. Note that, since W p is a stochastic matrix (transition matrix) the construction of M as illustrated in Figure can be viewed as an iterative process W p X; when p = 0 we have M = X. This process will converge to the approximated data W p X where each row moves towards its prototype. In other words, this process converges to an equilibrium state. With g denoting the number of eigenvalues of W p equal to 1, the matrix W p X is composed of g << n quasi-similar rows where each row is represented by its prototype (Figure 4). At first sight this power iterative process appears to be of little interest, since it eventually leads to a data matrix in which rows coincide for any starting point. However, our practical experience shows that the data quickly give rise to row blocks and that these blocks move towards each others relatively slowly. If we stop the process at this point, the refined affinity matrix M can be useful for clustering. Thus, this process can be seen as a refining of the feature matrix X into a matrix structured into blocks, which is beneficial in relation to both the embedding and the clustering tasks.

W

V. NUMERICAL EXPERIMENTS

Our focus in this work is on different clustering methods. Below we compare the PAGEC algorithm with some competitive methods, including recent deep learning methods.

A. Characteristics of datasets and Compared methods

The performances of clustering methods are evaluated using datasets commonly tested with ANE where the clusters are known. The experiments were conducted using four public citation network datasets, namely Citeseer, Cora, Wiki, and Pubmed, which contain a sparse bag-of-words feature vector for each document, together with a list of citation links between documents. Each document has a class label. For our purposes the documents are the nodes and the citation links are the edges. The characteristics of the datasets are summarized in Table I. The balance coefficient is defined as the ratio of the number of documents in the smallest class to the number of documents in the largest class, while nz denotes the percentage of sparsity. We compare PAGEC with embedding-based methods and with other methods that are explicitly for graph clustering. In our comparison we include standard methods and also recent deep learning methods; these differ in the way they use available information. Some of them (such as K-means) use only X as the baseline, while others use more recent algorithms based on X and W. All the compared methods are also mentioned in Section II above: Graph Encoder [START_REF] Tian | Learning deep representations for graph clustering[END_REF], DNGR [START_REF] Cao | Deep neural networks for learning graph representations[END_REF], DeepWalk [START_REF] Perozzi | Deepwalk: Online learning of social representations[END_REF], Spectral Clustering [START_REF] Tang | Leveraging social media networks for classification[END_REF], while spectral-f denotes a traditional spectral clustering applied on W X , spectral-g is applied on W. Using X and W we evaluated GAE and VGAE [START_REF] Kipf | Variational graph auto-encoders[END_REF], MGAE [START_REF] Wang | Mgae: Marginalized graph autoencoder for graph clustering[END_REF], ARGA and ARVGA [START_REF] Pan | Adversarially regularized graph autoencoder for graph embedding[END_REF], AGC [START_REF] Zhang | Attributed graph clustering via adaptive graph convolution[END_REF] and DAEGC [START_REF] Wang | Attributed graph clustering: A deep attentional embedding approach[END_REF].

B. Sensitivity analysis of λ and p

With the PAGEC model, the parameter λ controls the role of the second term ||S -GZB || 2 in (2). To measure its impact on the clustering performance of PAGEC S , we vary λ in {0, 10 -6 , 10 -3 , 10 -1 , 10 0 , 10 1 , 10 3 } and p from 1 to 12. The performances in terms of accuracy (ACC), Normalized Mutual Information (NMI) and F1 measure are illustrated only on Cora dataset in Figure 5, due to lack of space; a high ACC, NMI or F1 corresponds to a better clustering result. First, we note that with λ = 0 we are relying only on poor results in terms of quality of clustering, which is an indication of the impact of the second term in [START_REF] Cai | A comprehensive survey of graph embedding: Problems, techniques, and applications[END_REF]. Quality increases as λ increases, and with only small values of λ a better performance is obtained on all datasets. We have noted that around 10 -2 the clustering result becomes stable and less sensitive to λ. With values of λ greater than 10 -1 the performance of PAGEC degrades sharply. This can be explained by the fact that the initialization of G is random, and thus can often be a long way from the real solution. As we can observe in Figure 5, the best results are obtained with λ = 10 -3 and p = 5.

C. Attributed network clustering

Evaluating clustering results is not a trivial task. Clustering accuracy is not always a reliable measure when clusters are not balanced and the number of clusters is high. As a better indication of the quality of our approach, below we have chosen to retain, in addition to accuracy, two measures that are widely used in assessing the quality of clustering, namely Normalized Mutual Information, and the F1 measure. The F1 measure takes both precision and recall into account in computing the score, F1 being the harmonic mean of the precision and recall. Intuitively, NMI quantifies to what extent the estimated clustering is informative about the true clustering, while F1 is more oriented towards measuring the effectiveness of a clustering algorithm. The higher the ACC/NMI/F1, the better the clustering, and so in our experiments clustering performance in relation to the true available clusters is assessed in terms of ACC, NMI and F1. If one clustering algorithm performs better than other clustering algorithms on a number of these measures, then we can have some confidence that it is truly the best clustering algorithm for the situation being evaluated.

We repeated the experiments 50 times and the averages (mean) and standard-deviations (sd) are reported in Table II; the best performance for each dataset is highlighted in bold. First, we observe the good performances of methods that integrate information from W. The methods that include deep learning algorithms relying on M and W are better still. Regarding PAGEC, for the versions based respectively on W (PAGEC W ) and on S (PAGEC S ), we note good performances for all the datasets. In the case of PAGEC S we remark the impact of W X ; it learns low-dimensional representations in agreement with the clustering structure.

D. Attributed network embedding

The PAGEC model, through B, offers an embedding into clusters from which a 2d or 3d structure can also be observed. To illustrate the quality of embedding, we consider the four attributed network datasets above and focus on the R-square=

Tr(S b )

Tr(St) ratio, where S b is the between-class scatter matrix and S t is the total scatter matrix. To evaluate the separability of true classes, we computed this ratio from X, M and B respectively (Table III). VI. CONCLUSION AND PROSPECTS In unsupervised learning, representation learning and clustering are generally studied by two distinct machine learning communities. In our contribution we argue that bringing the two disciplines together can improve representation learning. Behind the design of representation-learning algorithms of this kind is the all-encompassing quest for Artificial Intelligence.

This paper is concerned with both learning representation and clustering. We have proposed a novel matrix decomposition framework for simultaneous attributed network data embedding and clustering. Unlike existing methods that combine the objective function of ANE and the objective function of clustering separately, our proposed method PAGEC S capitalizes on learning representation and clustering simultaneously.

The proposed framework suggests a number of prospects for further investigation. Following several KNN experiments relating to the choice of the number of neighbors, we have noted that given the sparsity a large number of neighbors (more than 30) is necessary. However, there are other points that warrant in-depth evaluation, such as the choice of λ and p.

In the future we are planning to improve upon our proposed method in several respects. First, we would like to be able to measure the impact of each matrix W and W X in the construction of S by considering two different weights for W and W X as follows: S = αW + βW X . Secondly, we wish to address the problem of assessing the number of clusters, which remains a challenge in unsupervised learning, and specifically in relation to ANE.

Fig. 1 .

 1 Fig. 1. MDS on W (left) and S (right) (K = 35): Cora dataset where W of size (2708 × 2708) with true 7 clusters.

Fig. 2 .

 2 Fig. 2. Cora dataset (2708 × 1433) with true 7 clusters: CDA on X (left), M = WX (middle) and M = W 8 X (right). To evaluate the separability of different classes, we rely on the ratio between-class scatter matrix S b and total-class scatter St defined by R-square = Tr(S b )

Algorithm 1 :

 1 PAGEC S algorithm Input: M and S from structure matrix W and content matrix X, k, p and λ ; Initialize: B, Q and Z with arbitrary orthonormal matrix; repeat (a) -Compute G using (8) (b) -Compute B using (7) (c) -Compute Q using (6) (d) -Compute Z using (5) until convergence Output: G: clustering matrix, Z: rotation matrix, B: node embedding matrix and Q: attribute embedding matrix.

Fig. 4 .

 4 Fig. 4. Random walk process. Evolution of singular values and patterns according X, WX and W 8 X.

Fig. 5 .

 5 Fig. 5. Cora dataset: Sensitivity analysis according to (left) λ and (right) p.

TABLE II CLUSTERING

 II PERFORMANCES (ACC % , NMI % AND F1 % ) ON CORA, CITESEER, WIKI AND PUBMED DATASETS. (-) REFERS TO THE NON-AVAILABILITY OF ACC IN[START_REF] Wang | Attributed graph clustering: A deep attentional embedding approach[END_REF].

								Datasets
	Methods	Input		Cora			Citeseer			Wiki			Pubmed
			Acc	NMI	F1	Acc	NMI	F1	Acc	NMI	F1	Acc	NMI	F1
	K-means	X	34.65	16.73	25.42	38.49	17.02	30.47	33.37	30.20	24.51	57.32	29.12	57.37
	Spectral-f	W X	36.26	15.09	25.64	46.23	21.19	33.70	41.28	43.99	25.20	59.91	32.55	58.61
	Spectral-g	W	34.19	19.49	30.17	25.91	11.84	29.48	23.58	19.28	17.21	39.74	3.46	51.97
	DeepWalk	W	46.74	31.75	38.06	36.15	09.66	26.70	38.46	32.38	25.74	61.86	16.71	47.06
	DNGR	W	49.24	37.29	37.29	32.59	18.02	44.19	37.58	35.85	25.38	45.35	15.38	17.90
	GAE	X, W	53.25	40.69	41.97	41.26	18.34	29.13	17.33	11.93	15.35	64.08	22.97	49.26
	VGAE	X, W	55.95	38.45	41.50	44.38	22.71	31.88	28.67	30.28	20.49	65.48	25.09	50.95
	ARGE	X, W	64.0	44.90	61.90	57.3	35.0	54.60	41.40	39.502	38.27	59.12	23.17	58.41
	ARVGE	X, W	63.8	45.0	62.70	54.4	26.1	52.90	41.55	40.01	37.80	58.22	20.62	23.04
	MGAE	X, W	63.43	45.57	38.01	63.56	39.75	39.49	50.14	47.97	39.20	43.88	8.16	41.98
	DAEGC	X, W	70.04	52.8	68.2	67.2	39.7	63.6	-	-	-	67.1	26.6	65.9
	AGC	X, W	68.92	53.68	65.61	67.00	41.13	62.48	47.65	45.28	40.36	69.78	31.59	68.72
	PAGEC W,p=p *	X, W	70.09	53.56	66.56	66.66	40.80	62.77	50.38	43.57	41.44	69.56	30.76	68.95
		sd	.0040	.0016	.0004	.0007	.00015	.0005	.0079	.0023	.0097	.00	.00	.00
	PAGEC S,p=p *	X, S	72.25	55.21	67.94	68.31	43.04	63.69	55.30	51.27	45.96	72.20	33.64	71.51
		sd	.0010	.0012	.0009	.0009	.0007	.0004	.0037	.0019	.0020	.00	.0028	.00

TABLE III EVALUATION

 III OF SEPARABILITY BETWEEN CLASSES GIVEN THE TRUE PARTITION AND DATA REPRESENTATIONS X, M AND B.

			Rsquare in %
	datasets	X	M	B
	Cora	2.58	5.41	44.43
	Citeseer	1.73	3.92	40.6
	Wiki	5.73	17.69	34.04
	Pubmed	1.99	2.02	31.14

From now on, in order to distinguish between a model and its derived algorithm, we will use typewriter font for an algorithm. Consequently, PAGEC is the model and PAGEC its derived algorithm.


Lucas Albuquerque
email: albuquerque@laplace.univ-tlse.fr

Fabien Lacressonnière

Xavier Roboam
email: xavier.roboam@laplace.univ-tlse.fr

Christophe Forgez
email: christophe.forgez@utc.fr

Incremental Capacity Analysis as a diagnostic method applied to second life Li-ion batteries

published or not. The documents may come

Incremental Capacity Analysis as a diagnostic method

applied to second life Li-ion batteries

Introduction

The increasing number of batteries produced and consumed nowadays can be attributed to the rise of electric vehicles (EVs) into the market. However, this step towards transport decarbonization created a problem of its own: what to do with these batteries after they are not suitable anymore to power said EVs? The answer to this question is either recycling or ending up in a landfill, creating another environ-mental problem in itself. Nonetheless, there are innovative projects nowadays, like ELSA [START_REF]ELSA project[END_REF] and Batteries2020 [START_REF]Batteries2020 project[END_REF], that are striving to give a second life to these batteries. Offering a second chance to these batteries would mean lowering their environmental impacts during their life cycle.

The end of an EV battery life is defined by the US Advanced Battery Consortium as a 20% drop of cell capacity from the rated value, or a 20% drop from rated power density at 80% depth of discharge (DoD) [START_REF] Hossain | A comprehensive review on second-life batteries: Current state, manufacturing considerations, applications, impacts, barriers potential solutions, business strategies, and policies[END_REF]. In other cases, the battery end of life can be considered achieved when its resistance has doubled in value. Yet, after being used in an EV, these batteries can still be useful in other applications and can be selected and rebuilt for a new purpose, such as Energy Storage Systems (ESS) for stationary applications [START_REF] Tong | Demonstration of reusing electric vehicle battery for solar energy storage and demand side management[END_REF].

In order to have a homogeneous battery selection issued from various first lives, it is important to characterize the cells of a battery pack with respect to State of Health (SoH). However, in this study the Incremental Capacity Analysis (ICA) was here used to give a more intimate diagnosis of the batteries, pursuing a more precise characterization of the cells or modules for the assembly of the second life battery. This refine selection means a more homogeneous battery, in which the cells would age similarly during the second life.

This paper is organized as follows. In the second part, a few diagnostic methods are presented and the feasibility of their use in second life applications is discussed. The third part presents the ICA as a diagnostic tool to determine with accuracy the battery DMs. The experimental procedure is detailed and the results are explained and compared to other studies. To further visualize the effects of degradation, the fourth part presents the results of a Hybrid Pulse Power Characterization (HPPC) test. The fifth and last part confirms the experimental results with a simulation toolbox for battery degradation called Alawa.

Diagnostic methods for second life batteries

There exist many diagnostic methods for Li-ion batteries, but some are better suited than others to characterize the cell for a possible second life. They mainly give as outputs the SoH in terms of capacity [START_REF]ELSA project[END_REF] or impedance (2) [START_REF] Hossain | A comprehensive review on second-life batteries: Current state, manufacturing considerations, applications, impacts, barriers potential solutions, business strategies, and policies[END_REF][START_REF] Quinard | Fast electrical characterizations of high-energy second life lithium-ion batteries for embedded and stationary applications[END_REF].

SoH(Q)[%] = 100 * Q present Q nominal (1) SoH(Z)[%] = 100 * 2 - Z present Z nominal ( 2
)
Where Q is the battery capacity in Ah and Z is the impedance in Ohms. Precise methods based on machine learning are employed in Battery Management Systems (BMS), but they track the battery usage since their beginning of life to estimate the SoH [START_REF] Harting | State-of-health identification of lithium-ion batteries based on nonlinear frequency response analysis: First steps with machine learning[END_REF]. In a situation where the previous usage is unknown, these methods would lack precision or not be applicable due to the small sample or nonexistence of first life data. Other methods such as the electrochemical impedance spectroscopy have been proven to be precise and capable of determining the DMs occurring inside the battery [START_REF] Pastor-Fernández | A comparison between electrochemical impedance spectroscopy and incremental capacity-differential voltage as li-ion diagnostic techniques to identify and quantify the effects of degradation modes within battery management systems[END_REF], but it requires specialised equipment capable of exciting the cells in order to extract their reaction to the applied frequency spectrum.

Since Li-ion battery degradation has been proven to be path dependent [START_REF] Ma | Investigation of path dependence in commercial lithium-ion cells for pure electric bus applications: Aging mechanism identification[END_REF], meaning that their first life will influence the longevity and performance during their second life, two batteries can present the same SoH but have different degradation patterns. That is why, for a second life application, a diagnostic technique such as the ICA can be better suited to determine these degradation patterns in a battery cell or module. This method can be applied with simple laboratory equipment such as a power supply or an electronic load. With this technique, it is possible to estimate the Loss of Lithium Inventory (LLI) and the Loss of Active Material (LAM) in the positive and the negative electrodes of a Li-ion cell. These DMs are a better representation of the battery first life when compared to a simple capacity measurement.

Incremental Capacity Analysis

Principle

The ICA and Differential Voltage Analysis (DVA) are two similar methods that give an intimate view of the electrochemical processes inside the cell. Many papers have been previously published on these methods, but most of them focus on the estimation of the SoH during the first life [START_REF] Riviere | Innovative incremental capacity analysis implementation for c/lifepo4 cell state-of-health estimation in electrical vehicles[END_REF][START_REF] Yuan | Efficient state of health estimation of li-ion battery under several ageing types for aeronautic applications[END_REF][START_REF] Plattard | Combining a fatigue model and an incremental capacity analysis on a commercial nmc/graphite cell under constant current cycling with and without calendar aging[END_REF]. In [START_REF] Riviere | Innovative incremental capacity analysis implementation for c/lifepo4 cell state-of-health estimation in electrical vehicles[END_REF], it is possible to see how the Open Circuit Voltage (OCV) plateaus, which represent the convolution of the phase transitions inside the electrodes when being lithiated or delithiated, become peaks in the IC curve by applying equation (3) [START_REF] Riviere | Innovative incremental capacity analysis implementation for c/lifepo4 cell state-of-health estimation in electrical vehicles[END_REF]. In which the tips represents the existence of just one phase in one of the electrodes.

IC = dQ cell [Ah] dV cell [V ] (3)
Where dQ cell is the variation in capacity with respect to the voltage dV cell . As illustrated in [START_REF] Birkl | Degradation diagnostics for lithium ion cells[END_REF], the effects of the DMs can be translated in a shift between the electrode potentials, in the case of LLI, or a contraction in the case of LAM, which can happen separately in each electrode (LAM PE or LAM NE ). These changes in the electrode OCV curves are ultimately going to change the overall signature of the IC curve and the amplitude and shift of the peaks can be used to estimate said DMs.

In order to acquire the IC curve, it is necessary to measure the OCV for each State of Charge (SoC) value of the battery. However, to obtain this measurement, it is necessary to charge or discharge the battery with low currents. Lower currents improve the precision of the measurement by preventing high diffusion effects inside the electrode materials and thus the precision of the IC curve. These diffusion effects can mix the electrode phase transitions into one single indistinguishable curve, as seen in [START_REF] Fly | Rate dependency of incremental capacity analysis (dq/dv) as a diagnostic tool for lithium-ion batteries[END_REF]. This study concludes that C/6 is a good compromise between time and precision, but there are studies that go as far as C/2, like [START_REF] Schaltz | Incremental capacity analysis applied on electric vehicles for battery state-of-health estimation[END_REF].

Experimental tests

Two NMC/Graphite Li-ion batteries were studied in this work. One module is composed of 12 cells connected in series which had been used in an EV. The second battery is a single cell similar to the ones used in the module and it has also been used in an EV. The nominal capacity of the module and the cell is equal to 25 Ah, according to the manufacturer's datasheet. Fig. 1 shows the cell used in the module. First of all, several charge and discharge cycles were done with the module and the cell in order to determine and compare their discharged capacities. During the tests, they were both placed in a climate chamber at 25°C. The charge protocol used was a CC-CV profile, in which a constant current (CC) is applied until the battery has reached its maximum allowed voltage (4.2 V per cell), then the power supply switches to constant voltage (CV) regulation until a low current of C/50 (0.5 A) is reached. The discharging process was stopped when the voltage across a cell was equal to 2.7V (the discharge voltage limit).

During the experimental tests, the twelve cells of the module were equilibrated (the voltage response for each cell was the same). Hence, in this study, the diagnosis of the module was based on one particular cell of the module (noted cell m in this study). Fig. 2 shows the discharge curves in volts by ampere-hours for the cell m and the single cell. As shown, the discharge capacity of the module is equal to 27.5 Ah whereas it is equal to 23 Ah for the single cell, evidencing that this last has a lower SoH. Moreover, it is clearly visible that the phase transition voltage plateaus and the overall curves shift towards lower voltages, which indicates ageing and a resistance increase. These observations support the interest in using the ICA and a resistance measurement as diagnostic tools to understand the DM effects on the single cell. In order to obtain the DMs in both the cell m and the single cell, the IC curve was plotted. As a first step to obtain the curve, a filtering on the voltage measurements is necessary before the derivative is calculated. As previously done in [START_REF] Li | A quick on-line state of health estimation method for li-ion battery with incremental capacity curves processed by gaussian filter[END_REF], the first filter applied to the voltage measurement was a moving average filter, giving a rough outline of the IC curve. Then the result was further smoothed by a Gaussian filter, in which the values of the averaging window are weighted with a Gaussian curve, where the center values have a bigger impact on the averaged value and the ones in the extremities have a lesser impact. The size of the av-eraging window is increased to smoothen the curve until its peaks start decreasing in amplitude.

Interpretations

As previously said, the interest of the ICA is to analyze and identify the battery degradation phenomena intimately. To further understand and visualise the effects of ageing in the NMC/Graphite technology, the ICA method was applied to the single cell in order to compare its signature with cell m . Fig. 3 shows both IC curves from a voltage measurement during the charging process. Several differences on the IC curves appear. These differences could be governed by ageing processes in the single cell. The analysis of the IC curves demands an understanding of both the graphite and NMC electrodes behaviour simultaneously. Since the pair of curves presented on Fig. 3 comes from the charge profile, starting from the lowest voltages where the graphite is almost fully delithiated until the end of the first peak (2.7 V until 3.55 V for cell m or 3.6 V for the single cell): the negative electrode passes from C 6 to LiC 72 (diluted phases), then LiC 36 and finally transitioning to LiC 18 . At this point, the mentioned graphite intercalation stages coexist, especially under high currents where diffusion effects are intensified.

The second big peak between 3.6 V and 3.75 V is mainly due to a NMC specific phase transition, where its structure changes from a hexagonal to monoclinic (H1 to M) lattice [START_REF] Jung | Oxygen release and its effect on the cycling stability of LiNixMnyCozO2(NMC) cathode materials for li-ion batteries[END_REF]. While so, the graphite transitions from LiC 18 towards LiC 12 corresponding to the end of the plateau between stage 3 and 2 in the graphite charge curve observed in the literature [START_REF] Rahul | Thermodynamics of lithium intercalation in randomly oriented high graphene carbon[END_REF]. The third and last visible peak between 3.75 V and 4.1 V (shifted on the single cell IC curve) is primarily a result of the last phase change in the graphite electrode from LiC 12 to LiC 6 . This transition is the longest of all (kinetically slower).

Due to the lack of a peak indicating the phase transition H2 to H3 (hexagonal to hexagonal accompanied by a rapid volume contraction) towards the end of the charge, reported in Ni rich NMC cathodes, the NMC cathode present in the batteries is presumed to have a relatively good reversibility and this is translated into a good overall stability of the electrode [START_REF] Noh | Comparison of the structural and electrochemical properties of layered li[nixcoymnz]o2 (x = 1/3, 0.5, 0.6, 0.7, 0.8 and 0.85) cathode material for lithium-ion batteries[END_REF], so in a first moment, LAM PE does not seem to be the main cause of ageing. However, the lower first peak (3.5 V) amplitude can indicate small traces of active material loss of the positive electrode LAM PE .

Moreover, as a result of LLI, the cut off voltage (low SoC) of the positive electrode becomes higher as the lithium is consumed and it shifts both electrode potential curves away from each other. This means that at the end of a discharge or the beginning of a charge cycle, the positive electrode cannot reach lower voltage potentials due to the voltage limits (as in figure 8 from [START_REF] Tobias | Nonlinear aging of cylindrical lithium-ion cells linked to heterogeneous compression[END_REF]). So, instead of having a strong peak between 3.6 and 3.75 V, its amplitude is considerably reduced. This indicates that LLI is the most prominent degradation mode at this stage of ageing. The consumption of lithium can also explain the overall shift of the IC curve towards higher voltages, since it is probably consumed during the thickening process of the SEI (Solid Electrolyte Interphase) layer.

C-rate influence on the ICA

A study to further understand the influence of the C-rate on the IC curve was also conducted. Fig. 4 shows IC curves plotted for several C-rates. The applied filters follow the same rule as explained in section 3.2. It was checked that the peak amplitudes were not equally affected by the charge or discharge regimes. The influence of the C-rate on the IC curve can be explained by the difference in kinetics of charge transfer and diffusion reactions in the electrodes for the different current values. This corroborates to choose a lower C-rate, in order to obtain an accurate IC plot. Hence, the choice of the C-rate has to be a compromise between the accuracy of the IC curve and the duration of the test for a rapid evaluation of the second life Li-ion batteries.

The analysis of two peaks from the IC curve (charge regime) for different C-rates was carried out and the results are summarized in Tab. 1. When the C-rate increases, the peak amplitudes are reduced and they shift toward higher voltages due to the voltage drop governed by the internal resistance. A reduction of peak areas is proportional to the number of exchanged amperes-hours during the charging process.

HPPC profile characterization

As a complement to the ICA tests, a Hybrid Pulse Power Characterization (HPPC) test was carried out with both the module and the single cell in order to measure their internal resistances. One HPPC cycle profile consists on constant current charge and discharge pulses, followed by a 10% SoC constant current discharge and a 30 minute pause between cycles. The cycles are repeated until 10% SoC. One sequence of the HPPC profile is shown in Fig. 5 where several current rates were imposed at 0.1C, 0.2C, 0.5C, 1C, 1.5C and 2C. The duration of the pulses was fixed at 10 seconds and the internal resistance was calculated by Ohm's law. Fig. 6 presents the internal resistances measured for several SoC values. These values were calculated for cell m and the single cell for a discharge current of 1C. As depicted from Fig. 6, the single cell internal resistance is higher than the cell m in a ratio of 1.7, regardless of the SoC value. This internal resistance increase may be associated with ageing mechanisms taken place in the single cell and can explain the overall shift of the IC curve for the aged cell (Fig. 3), as mentioned previously, and may be linked mainly to the growth of the SEI layer. In order to simulate the degradation as close as possible to the experimental results, a few parameters such as the electrode ratio, the initial resistance and the SEI offset were chosen. This last one is responsible for the initial shift between the electrode curves, consuming lithium-ions. These parameters were modified until the obtained IC profile was close to the experimental one from cell m . The same methodology was applied to simulate the DMs. The optimal result was found when the toolbox was set to simulate 0.032% of LLI and 0.01% of LAM PE per cycle during 500 cycles. These DMs result in a total of 16% of capacity loss and it is in accordance with the experimental value of 83.3% of SoH when dividing the capacity of cell m to the aged one. The total amount of capacity loss is due to LLI (16%), but the active material loss from the positive electrode has an influence on the IC curve as this electrode capacity has been reduced. Generally, the lower voltages are limited by the negative electrode and the higher voltage is limited by the positive electrode. Tab. 2 summarizes the simulations results with Alawa and compares them with the real measured values.

The results presented in Tab. 2 show that with regard to peak degradation, the simulation with both LLI and LAM PE combined are the closest to the experimental results, also supported by Fig. 7. The first peak is greatly reduced in the simulation with LAM NE , as this peak is due to the first few phase transitions in the graphite, as mentioned in section 3. The peak translation in volts show close results in all of the cases, mainly due to the formation of the SEI as previously said. However, the differences are minimal, thus the peak amplitudes seem to be more adequate to judge the accuracy of the simulations.

Conclusions

In this paper, several tests were performed on a Li-ion module composed of 12 cells connected in series in order to estimate their state of health. These tests were also done with a single Li-ion cell. The capacity and internal resistance measurements allowed to distinguish a more important degradation for the single cell. An ICA was carried out to determine the degradation modes in the cell. It has been shown that the accuracy of the IC curves depends on the C-rate (amplitudes of the peaks decrease with the C-rate). To determine the degradation modes in the cell, the 'Alawa toolbox was used. A comparison between the IC curves (simulated and measured) showed that the major degradation mode in the cell is the loss of lithium inventory and the loss of active material of the positive electrode. In the future, this study will be extended in order to develop an experimental method, based on the ICA, to determine with accuracy (and rapidly) the degradation modes in Li-ion modules. This diagnostic method will be applied in order to have a homogeneous module selection to develop a second life battery.

Fig. 1 A

 1 Fig. 1 A NMC/G Li-ion cell tested in this work. The module consists of twelve of these cells in series.

Fig. 2

 2 Fig. 2 Discharge curves (with a C-rate of 0.2C) for a cell issued from the module and the single cell.

Fig. 3

 3 Fig. 3 Comparison between the IC curve of cell m (from the module) and the single cell.

Fig. 4

 4 Fig. 4 Comparison between different C-rates in charging and discharging modes for the cell m .

Fig. 5

 5 Fig. 5 Current pulses and the voltage reactions during one sequence of the HPPC profile.

Fig. 6

 6 Fig. 6 Internal resistance comparison between cell m and the single cell.

Fig. 7

 7 Fig. 7 IC curves from Alawa simulation of 0.032% of LLI and 0.01% of LAM PE per cycle (top) and IC curves from both the single cell and cell m (bottom). %Q is the percentage of the initial battery capacity Q in Ah.

Table 1

 1 Comparison of peak amplitude and shift depending on the Crates.

		IC peaks for different C-rates in charging mode
	C-	1st peak:	1st peak:	2nd peak:	2nd peak:
	rates	Amplitude	Voltage		Amplitude	Voltage
	0.2C	66.4 Ah/V	3.5 V		96.76	3.64 V
					Ah/V
	0.5C	55.4 Ah/V	3.51	V	89.91	3.65	V
		(-16.6%)	(+11 mV)	Ah/V	(+14 mV)
					(-7.1%)
	C	51.8 Ah/V	3.54	V	91.22	3.67	V
		(-22%)	(+46 mV)	Ah/V	(+35 mV)
					(-5.7%)

Table 2

 2 Comparison of the Alawa simulations and the measurements. Note that LLI has been set to 0.032% per cycle and LAM PE and LAM NE were set to 0.01% per cycle.

			DMs simulation and measured values
	Case		Degradation	Degradation	Translation	Translation
			1st peak	2nd peak	1st peak	2nd peak
	Experimental	10.52%	37.83%	0.035 V	0.049 V
	results
	LLI		18.30%	44.27%	0.027 V	0.045 V
	LLI	+	14.10%	39.97%	0.022 V	0.038 V
	LAM PE
	LLI	+	20.75%	40.54%	0.028 V	0.043 V
	LAM NE

Acknowledgements This work is funded by the B2LIVE project (Batteries de 2 nd vie au Lithium Ion à Vieillissement caractérisé par Experimentation). This work has been supported by the OCCITANIE Region.