In this paper, a decentralised fault diagnosis approach for large-scale systems is proposed. This approach is based on obtaining a set of local diagnosers using the analytical redundancy relation (ARRs) approach. The proposed approach starts with obtaining the set of ARRs of the system yielding into an equivalent graph. From that graph, the graph partitioning problem is solved obtaining a set of ARRs for each local diagnoser. Finally, a decentralised fault diagnosis strategy is proposed and applied over the resultant set of partitions and ARRs. In order to illustrate the application of the proposed approach, a case study based on the Barcelona drinking water network (DWN) is used.
Large-scale systems (LSS) present new challenges due to
the large size of the plant and its resultant model [
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 [
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 [
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. 2 2.1
Consider a dynamical system represented in general form by the state-space model x+ = g(x, u, d), y = h(x, u, d), (1a) (1b) where x ∈ Rn and x+ ∈ Rn 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 ∈ Rm is the system input vector, d ∈ Rp is the vector containing a bounded process disturbance and y ∈ Rq is the system output vector. Moreover, g : hRn: ×RRnm××RRmp×7→RpR7 →is thReqsctaotrersesmpoanpdpsinwgitfhunthcteioonutapnudt 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 = {ri | ri = Ψi(yk, uk, θk), i = 1, . . . , nr}, (2) where Ψi is the ARR mathematical expression and nr is the number of obtained ARRs. Then, fault diagnosis is based on identifying the set of consistent ARRs
R0 = {ri|ri = Ψi(yk, uk, θk) = 0, i = 1, . . . , nr}, (3) and inconsistent ARRs,
R1 = {ri|ri = Ψi(yk, uk, θk) 6= 0, i = 1, . . . , nr}, (4)
at time instant k when some inconsistency in (2) is
detected [
Fault isolation is based on the knowledge about the binary relation between the considered fault hypothesis set f1(k), f2(k), . . . , fnf (k) and the fault signal indicators φi that are stored in the fault signature matrix M . An element of this matrix, namely mij , is equal to 1 if the fault hypothesis fj is expected to affect the residual ri such that the related fault signal φi is equal to 1 when this fault is affecting the monitored system. Otherwise, the element mij 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. 2.2
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 IM is obtained considering that,
without loss of generality, the directionality of the edges are
derived from the relation between ARRs (rows of IM ) and
input/output variables (columns of IM ), in analog way as
proposed by [
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 [
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 p ∈ Z≥1, find p subsets V1, V2, . . . , Vp of V such that
p 1. S Vi = V ,
i=1 2. Vi ∩ Vj = ∅, for i ∈ {1, 2, . . . , p}, j ∈ {1, 2, . . . , p}, i 6= j, 3. #V1 ≈ #V2 ≈ · · · ≈ #Vp, 4. the cut size, i.e., the number of edges with endpoints in different subsets Vi, 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.
In general, graph partitioning approaches are considered
as N P-complete problems [
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 [
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. 3.1
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 subgraphs2.
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 = (
Gi, i = 1, 2, . . . , p : [ Gi = G ) .
(6) p i=1 3.2
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
2Two subgraphs are called neighbours if they are contiguous
and share edges (see, e.g., [
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 Di 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 followinglocal 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 D2 and D4. 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 DC 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 . . . . . . y1,S4 y28,S4
D4
DC
D2 . . . . . . y29,S4 y32,S4 y5,S2 y12,S2 . . . y1,S2 y4,S2 a result of the global diagnosis based on the involved ARRs with shared variables, a fault in these variables could be diagnosed or alternative excluded. In case of exclusion, local diagnosers sharing a given ARR whose shared variable has been considered non-faulty continue reasoning now with all ARRs, i.e., all the involved ones, proposing a fault candidate using the local fault signature. 5
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.
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 [
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 [
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 xk+1 = Axk + Γνk, E1νk = E2,
yk = Cxk, with Γ = [B Bp], νk = [ukT dkT ]T , where x ∈ Rn is the state vector corresponding to the water volumes of the n tanks, u ∈ Rm represents the vector of manipulated flows (7a) (7b) (7c) through the m actuators (pumps and valves), d ∈ Rq corresponds to the vector of the q water demands (sectors of consume) and y ∈ Rn 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, Bp, C, E1 and E2 are system matrices of suitable dimensions dictated by the network topology. 5.3
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 Di. 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. ACast8 bCast8 d115CAST c115CAST
aPouCast VCR_27
CCA_3
CB_4 ApotLL1 c100LLO bPouCast_24
aPousE bPousE_23 n100LLO_22 vAdd_48
VSJD _29 c80GAVi80CAS x3 d54REL _8
CGIV_5 d80GAVi80CAS 85CRO_6
VCA_28 n70LLO_23 c70LLO
CPLANTA50 _7
CPLANTA70 _6 u7 dPLANTA _7 vAdd_308 vAdd_309
PLANTA10 _10
ApotA aMS bMS_21 u3 vAdd u1
In order to easyly understand how the proposed decentralised fault diagnosis approach would work, it will be explained focusing on subsystems S1 and S4 presented in Figure 3 in red lines that corresponds to the subsystems in green (S1) and in blue (in S4) in Figure 2. In particular, considering the set of ARRs corresponding to S1 as r1S,1k = y1,k − y1,k−1 − Δt[u1,k−1 + u2,k−1 − d1,k−1], r2S,1k = u1,k − u2,k − d2,k, r3S,1k = y2,k − y2,k−1 − Δt[u5,k−1 − d3,k−1], r4S,1k = u3,k − u4,k − u5,k − u6,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 D1 is able to isolate when a fault activates any of the ARRs ri,k, i = 1, 2, 3, since those ARRs only involve local variables. However, if the resiual r4,k is activated, it is necessary that a global diagnoser interacts with D1 discriminating whether the corresponding ARR in S4, defined here as r1S,4k, was also activated. If this is the case, the element
c135SCG c101MIR d101MIR_18 vAdd_55
AportT nAportT_32 vAdd_312 AportT
n135SCG 1 r1S,4k . . .
fu5 . . . contain shared variables between both S1 and S4 is presented. There, r4S,1k corresponds with the fourth ARR of S1 (last row of Table 3), while r1S,4k = x3,k − x3,k−1 − Δt[u7,k−1 + u8,k−1
+ u6,k−1 − u9,k−1] corresponds with the first defined ARR forS4. Notice that the global diagnoser should decide by looking at the ARR activations occurred in this fault signature matrix and then interact with the different local diagnosers if needed. 6
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.
This work has been partially supported by the EFFINET grant FP7-ICT-2012-318556 of the European Commission and the Spanish project ECOCIS (Ref. DPI2013-48243-C21-R).