Introduction

Large-scale systems (LSS) present new challenges due to the large size of the plant and its resultant model [1,2]. Traditional supervision methods for LSS (including diagnosis and fault tolerant control) have been mostly developed assuming a centralized scheme that assumes to have the full information. In the same way, a global dynamical model of the system is considered to be available for supervision design (off-line). Moreover, all measurements must be collected in one location in a centralised way. When considering LSS, the centrality assumption usually fails to hold, either because gathering all measurements in one location is not feasible, or because a centralised high-performance computing unit is not available. These difficulties have recently led to research in fault diagnosis (and fault-tolerant control) algorithms that operate in either decentralised or distributed way. Depending on the degree of interaction of the diagnoser associated to the subsystems and their diagnosis process, they can be classified into decentralised and distributed diagnosis categories.

In the decentralised diagnosis, both a central coordination module and a local diagnoser for each subsystem that forms the whole supervision system are running in parallel. Some examples were presented in [3,4,5], where local diagnosers are communicated to a coordination process (supervisor), obtaining a global diagnosis. On the other hand, in the distributed approach, a set of local diagnosers share information by means of some communication protocol instead of requiring a global coordination process such as in a decentralised approach. In the related literature, there are several proposals where there is no centralised control structure or coordination process among diagnosers [6,7,8]. Every diagnoser shares information with the neighbouring diagnosers. In these systems the model is distributed, the diagnosis is locally generated and the consistency among the subsystems should be satisfied.

In this paper, the main contribution relies on the development of a decentralised fault diagnosis approach for LSS based on analytical redundancy relations (ARRs) and graph theory. The algorithm starts considering a set of ARRs and then stating an equivalent graph. From that graph, the problem of graph partitioning is then solved. The resultant partitioning consists of a set of non-overlapped subgraphs whose number of vertices is as similar as possible and the number of interconnecting edges between them is minimal. To achieve this goal, the partitioning algorithm applies a set of procedures based on identifying the highly connected subgraphs with balanced number of internal and external connections in order to minimize the degree of coupling among the resulting partitions (diagnosers). This algorithm is specially useful in systems where there is no a clear functional decomposition. Finally, a decentralised fault diagnosis strategy is introduced and applied over the resultant set of partitions, in a similar way to the one introduced in [5]. In order to illustrate the application of the proposed approach, a case study based on the Barcelona drinking water network (DWN) is used.

The remainder of this paper is organised as follows. Section 2 presents and discusses the overall problem statement. Section 3 presents the ARR graph partitioning methodology. Section 4 describes the proposed decentralised fault diagnosis approach. Section 5 shows both the considered case study and the way of implementing the proposed decentralised fault diagnosis approach. Finally, Section 6 draws the main conclusions.

Problem Statement

Fault Diagnosis using ARRs

Consider a dynamical system represented in general form by the state-space model

x + = g(x, u, d),(1a)y = h(x, u, d),(1b)

where x ∈ R n and x + ∈ R n are, respectively, the vectors of the current and successor system states (that is, at time instants k and k + 1, respectively if the model is expressed in discrete-time), u ∈ R m is the system input vector, d ∈ R p is the vector containing a bounded process disturbance and y ∈ R q is the system output vector. Moreover, g : R n × R m × R p → R is the states mapping function and h : R n × R m × R p → R q corresponds with the output mapping function.

The design of a model-based diagnosis system is based on utilizing the system model (1) in the construction of the diagnosis tests. According to [9], by means of the structural analysis tool and perfect matching algorithm, a set of ARRs, namely R, can be derived from (1). ARRs are constraints that only involve measured variables (y, u) and known parameters θ. The set of ARRs can be represented as

R = {r i | r i = Ψ i (y k , u k , θ k ), i = 1, . . . , n r },(2)

where Ψ i is the ARR mathematical expression and n r is the number of obtained ARRs. Then, fault diagnosis is based on identifying the set of consistent ARRs

R 0 = {r i |r i = Ψ i (y k , u k , θ k ) = 0, i = 1, . . . , n r },(3)

and inconsistent ARRs,

R 1 = {r i |r i = Ψ i (y k , u k , θ k ) = 0, i = 1, . . . , n r }, (4)

at time instant k when some inconsistency in (2) is detected [10]. Fault isolation task starts by obtaining the observed fault signature, where each single fault signal indicator φ i (k) is defined as follows:

φ i (k) = 0 if r i (k) ∈ R 0 , 1 if r i (k) ∈ R 1 . (5)

Fault isolation is based on the knowledge about the binary relation between the considered fault hypothesis set f 1 (k), f 2 (k), . . . , f n f (k) and the fault signal indicators φ i that are stored in the fault signature matrix M . An element of this matrix, namely m ij , is equal to 1 if the fault hypothesis f j is expected to affect the residual r i such that the related fault signal φ i is equal to 1 when this fault is affecting the monitored system. Otherwise, the element m ij is zero-valued. A column of this matrix is known as a theoretical fault signature. Then, the fault isolation task involves finding a matching between the observed fault signature with some of theoretical fault signatures.

Partitioning the Set of ARRs

In order to design a decentralised fault diagnosis system following the ARR approach recalled above, the set of ARRs in (2) should be decomposed into subsets with minimal degree of coupling. Each subset of ARRs will allow to implement a local diagnoser. With this aim, a graph representation of R in (2) is determined. The graph G(V, E) representing the set of ARRs is obtained considering that

• the ARRs are the graph vertices collected in a set V , and

• the measured input/output variables are the graph edges collected in a set E. The graph incidence matrix I M is obtained considering that, without loss of generality, the directionality of the edges are derived from the relation between ARRs (rows of I M ) and input/output variables (columns of I M ), in analog way as proposed by [11] (and references therein) for the partitioning of LSS 1 . Once I M has been obtained from the ARR graph, the problem consists in partitioning the graph R into subgraphs. Since such partitioning is oriented to the application of a decentralised fault diagnosis, it is convenient that the resultant subgraphs have the following features:

• nearly the same number of vertices;

• few connections between the subgraphs. These features guarantee that the obtained subgraphs have a similar size, fact that balances computations between local diagnosers and allows minimising communications with a supervisory diagnoser. Hence, the partitioning the ARR graph can be more formally established following the dual problem proposed in [13] as stated here in Problem 1. Problem 1 (ARR Graph Partitioning Problem). Given a graph G(V, E) obtained from a set of ARRs, where V denotes the set of vertices, E is the set of edges, and 4. the cut size, i.e., the number of edges with endpoints in different subsets V i , is minimised. Remark 2.1. Conditions 3 and 4 of Problem 1 are of high interest from the point of view of a decentralised scheme since they are related to the degree of interconnection between resultant subsystems and their size balance. Remark 2.2. The inclusion of additional specifications directly related to the FDI performance of each subsystem diagnoser will be addressed as a future extension of the proposed partitioning approach. Remark 2.3. The partitioning approach starts from a given set of ARRs obtained using the perfect matching algorithm. The selection of the best ARRs from the set of the all possible ARRs (that could be obtained using the available sensors and system structure) such that when applying the partitioning algorithm produces a set of diagnosers with good FDI performance could be considered as an additional future improvement.

p ∈ Z ≥1 , find p subsets V 1 , V 2 , . . . , V p of V such that 1. p i=1 V i = V , 2. V i ∩ V j = ∅, for i ∈ {1, 2, . . . , p}, j ∈ {1, 2, . . . , p}, i = j, 3. #V 1 ≈ #V 2 ≈ • • • ≈ #V p ,

In general, graph partitioning approaches are considered as N P-complete problems [2]. However, they can be solved in polynomial time for #V i = 2 (Kernighan-Lin algorithm); see, e.g., [14]. Since the latter condition is quite restrictive for large-scale graphs, alternatives for graph partitioning based on fundamental heuristics are properly accepted and broadly discussed.

Proposed Partitioning Approach

Starting from the system ARR graph obtained as described in Section 2, this section proposes a partitioning algorithm through which a decomposition of the set of system ARRs can be performed. This decomposition allows the splitting of a centralised diagnoser into local diagnosers. The philosophy of the proposed approach comes from the partitioning methodology reported in [13], where a dynamic system is decomposed into several subsystems following certain criteria towards fulfilling a set of design conditions. For completeness and full understanding of the proposed diagnosis methodology, that approach is explained below and suitably adapted if needed.

The algorithm is divided into the main kernel and auxiliary routines in order to refine the final result according to the nature of the system and the given criteria depending on the case. Here, the ARR graph is decomposed into subgraphs in the same way as a system would be divided into subsystems.

Main Kernel

This part performs the central task of defining how the equivalent ARR graph of the LSS is split into subgraphs. The steps of the algorithm are followed in the form of subroutines towards reaching the main goals outlined in Problem 1. Notice that the whole algorithm is used off-line, i.e., the partitioning of the ARR graph is not carried out dynamically on-line. Ongoing research is focused to adapt the proposed algorithm such that the partitioning could be performed on-line when some structural change of the network occurs. The different subroutines are briefly described next.

• The start-up routine, which requires the matrix-based definition of the graph, e.g., via the incidence matrix, in order to state the connections between the graph vertices.

• The preliminary partitioning routine, which performs a clustering-like procedure where all graph vertices are assigned to a particular subset according to predefined indices related to the resultant subgraph and its internal weight (defined as the number of vertices of a subgraph), its external weight (defined as the number of shared edges between subgraphs) and other statistical measures. The resultant amount of partitions at this stage is automatically obtained.

• The uncoarsening routine, which is applied for reducing the number of resultant subgraphs if their internal weight is unbalanced, which would produce partitions with large differences of amount of vertices. This routine defines a design parameter ϕ max for determining the variance of the internal weight for all the resultant subgraphs.

• The refining routine, which aims at reducing the cut size of the resultant subgraphs, i.e., the number of edges they share. This routine is based on the connectivity of the vertices of a subgraph with other vertices in the same subgraph and in neighbouring subgraphs 2 .

Applying the aforementioned routines to the entire ARR graph, the expected result consists of a set of subgraphs that determines a particular decomposition. This set P is finally defined as

P = G i , i = 1, 2, . . . , p : p i=1 G i = G . (6)

Auxiliary Routines

Although the decomposition algorithm yields to an automatic partitioning of a given graph, it does not imply that the resultant set P follows the pre-established requirements stated in Problem 1. Therefore, complementary routines enhance the partitioning routine depending on their tune 2 Two subgraphs are called neighbours if they are contiguous and share edges (see, e.g., [15] among many others).

for the particular case study. Additional auxiliary routines might be designed in such a way that the diagnosis performance that would be achieved when used in decentralised or distributed fault diagnosis is taken into account. These auxiliary routines are:

• The pre-filtering routine, which lightens the start-up routine by merging all these vertices with single connection to those to which they are connected. It allows to have a smaller initial graph and then performing faster clustering of vertices.

• The post-filtering routine, which adds a tolerance parameter δ in such a way that the uncoarsening routine yields in less subgraphs when two of them may be conveniently merged but the numerical constraints does not allow to do so. This routine might increase the complexity since the internal weight of some subgraphs would also increase, unbalancing the resultant set of partitions.

• The anti-oscillation routine, which leads to solve a possible issue when the refining (external balance) routine is run since it defines a maximum number of iterations ρ that the refining routine is executed.

Decentralised Fault Diagnosis

Once a partitioned set of ARRs has been obtained by means of the algorithm presented in Section 3, the decentralised fault diagnosis approach is introduced. In order to explain how the proposed fault diagnosis approach works, it is concentrated on faults affecting the sensors measuring the input/output variables implied in the ARRs. The approach could be easily extended to other type of faults, but in order to keep the explanation simpler, it is restricted to the discussion about the set of considered faults. In this way, a fault can be associated to each measured input/output variable. Each subset of ARRs will allow to implement a local diagnoser D i in the way described in Section 2.1. The ARRs associated to a local diagnoser can be split in two groups. The first group, named in the following local ARRs, is composed of ARRs that do not involve shared variables with other ARRs in a different local diagnoser. On the other hand, the second group, named shared ARRs, is composed by ARRs that involve shared variables. Figure 1 shows two sets of ARRs associated to two local diagnosers, named D 2 and D 4 . These two diagnosers share some variables (in this case only outputs, but can be both inputs and outputs). This set of shared variables allows to define the set of shared ARRs, named D C in the figure. The remaining ARRs, which do not share variables, are local ARRs.

Similarly, faults in the fault signature matrix M of the local diagnoser that only involve local ARRs can be locally diagnosed. Thus, the local diagnoser works in a decentralised manner regarding those faults. On the other hand, faults that involve ARRs with shared variables in different subgraphs can not be locally diagnosed. On the contrary, a global diagnoser that evaluates the involved ARRs is used. This diagnoser has a fault signature matrix M collecting the involved ARRs with shared variables between local diagnosers and faults that should be globally diagnosed. When local diagnosers evaluate an ARR composed of shared variables, they send the result of the consistency check to the global diagnoser, which proceeds with the global diagnosis using a fault signature matrix that contains the involved ARRs. As

Application to a Case Study

This section briefly describes a case study in order to exemplify the application of the proposed decentralised diagnosis approach in a real LSS. In particular, the transport infrastructure of the Barcelona Drinking Water Network (DWN) is used.

Case Study Description

The Barcelona DWN, managed by Aguas de Barcelona, S.A. (AGBAR), supplies drinking water to Barcelona city and its metropolitan area through four drinking water treatment plants: the Abrera and Sant Joan Despí plants, which extract water from the Llobregat river, the Cardedeu plant, which extracts water from Ter river, and the Besòs plant, which treats the underground flows from the aquifer of the Besòs river. All source together provide a total amount of flow of around 7 m 3 /s. The water flow from each source is limited, what implies different water prices depending on water treatments and legal extraction canons. See [16] for further information about this system and [17] for further details about its modelling and management criteria.

Monitoring-oriented Model

In order to obtain a monitoring-oriented model of the DWN, the constitutive network elements (i.e., tanks, actuators, water demand sectors, nodes and sources) as well as their basic relationships should be stated [16]. By considering the mass balance at tanks and the static relations at α network nodes, the monitoring-oriented discrete-time state-space model of the DWN can be written as

x k+1 = Ax k + Γν k ,(7a)E 1 ν k = E 2 ,(7b)y k = Cx k ,(7c) withΓ = [B B p ], ν k = [u T k d T k ] T

, where x ∈ R n is the state vector corresponding to the water volumes of the n tanks, u ∈ R m represents the vector of manipulated flows through the m actuators (pumps and valves), d ∈ R q corresponds to the vector of the q water demands (sectors of consume) and y ∈ R n are the vector of measured water volumes of the n tanks. In this case, the difference equations in (7a) describe the dynamics of the storage tanks, the algebraic equations in (7b) describe the static relations (i.e., mass balance at junction nodes) in the network and in (7c) describe the relation between the physical and measured tank volumes. Moreover, A, B, B p , C, E 1 and E 2 are system matrices of suitable dimensions dictated by the network topology.

Implementation of the Proposed Approach

This section discusses the way the proposed decentralised fault diagnosis approach is implemented in the considered real case study. Figure 2 corresponds to the aggregate model of the Barcelona DWN, which is a simplification of the complete model, where groups of elements have been aggregated (not discarded) in single nodes to reduce the size of the whole network model. Using this aggregate model, the ARR graph of the Barcelona DWN has been derived after generating the set of ARRs from the mathematical model ( 7) by using the perfect matching algorithm [9] that aims to find a causal assignment which associates unknown system variables with the system constraints from which they can be calculated. Applying the partitioning algorithm to this graph, five groups of ARRs are obtained, which corresponds to five diagnosers that monitor a different part of the Barcelona DWN represented with different colors in Figure 2. Table 2 collects the descriptions of the resultant subgraphs, their number of ARRs and shared variables (manipulated flows through actuators) represented using circles in Figure 2. At this point it should be recalled that one of the goals of the partitioning algorithm is to reduce as much as possible the number of shared edges between subgraphs obtaining a graph decomposition as less interconnected as possible and with similar number of vertices for each subsystem (internal weight). This will allow an easier global diagnosis configuration, not only with respect to the number of distributed diagnosers but also with respect to the complexity of each local diagnoser D i . Thus, the application of the approach to the Barcelona DWN implies the design of five decentralised diagnosers together with a centralised/supervisory one, which is in charge of the coupled relations within the corresponding fault signature matrix of the whole system. For this example, it is important to highlight that ARRs have been obtained by considering the following assumption. In order to easyly understand how the proposed decentralised fault diagnosis approach would work, it will be explained focusing on subsystems S 1 and S 4 presented in Figure 3 in red lines that corresponds to the subsystems in green (S 1 ) and in blue (in S 4 ) in Figure 2. In particular, considering the set of ARRs corresponding to S 1 as

r S1 1,k = y 1,k − y 1,k−1 − ∆t[u 1,k−1 + u 2,k−1 − d 1,k−1 ], r S1 2,k = u 1,k − u 2,k − d 2,k , r S1 3,k = y 2,k − y 2,k−1 − ∆t[u 5,k−1 − d 3,k−1 ], rS1

4,k = u 3,k − u 4,k − u 5,k − u 6,k , the fault signature matrix presented in Table 3 can be obtained. From this table, it is possible to identify the shadowed part, which corresponds to the faults that the local diagnoser D 1 is able to isolate when a fault activates any of the ARRs r i,k , i = 1, 2, 3, since those ARRs only involve local variables. However, if the resiual r 4,k is activated, it is necessary that a global diagnoser interacts with D 1 discriminating whether the corresponding ARR in S 4 , defined here as r S4 1,k , was also activated. If this is the case, the element In Table 4, the fault signature matrix for the ARRs that

Conclusions

In this paper, a decentralised fault diagnosis approach for large-scale systems based on graph-theory has been presented. The algorithm starts with the translation of the system model into a graph representation. Then, applying the perfect matching algorithm, a set of analytical redundancy relations is obtained. From the analytical redundancy relation graph, the problem of graph partitioning is then solved. The resultant partition consists of a set of non-overlapped subgraphs whose number of vertices is as similar as possible and the number of interconnecting edges between them is minimal. To achieve this goal, the partitioning algorithm applies a set of procedures based on identifying the highly connected subgraphs with balanced number of internal and external connections. Finally, a decentralised fault diagnosis strategy is introduced and applied over the resultant set of partitions. In order to illustrate and discuss the use and application of the proposed approach, a case study based on the Barcelona DWN has been used. As further research, the partitioning algorithm will be improved by acting directly on the system model and not on the set of ARRs in order to generate a set of ARRs for each local diagnoser with enhanced fault diagnosis properties.