System level test selection based on combinatorial dependency matrix

YANG Peng ,XIE Haoyu ,and QIU Jing

1.Science and Technology on Integrated Logistics Support Laboratory,School of Intelligence Science,National University of Defense Technology,Changsha 410073,China;2.Unit 91697 of the PLA,Qingdao 266000,China

Abstract:Test selection is to select the test set with the least total cost or the least total number from the alternative test set on the premise of meeting the required testability indicators.The existing models and methods are not suitable for system level test selection.The first problem is the lack of detailed data of the units’ fault set and the test set,which makes it impossible to establish a traditional dependency matrix for the system level.The second problem is that the system level fault detection rate and the fault isolation rate (referred to as "two rates") are not enough to describe the fault diagnostic ability of the system level tests.An innovative dependency matrix (called combinatorial dependency matrix) composed of three submatrices is presented.The first problem is solved by simplifying the submatrix between the units’ fault and the test,and the second problem is solved by establishing the system level fault detection rate,the fault isolation rate and the integrated fault detection rate (referred to as "three rates") based on the new matrix.The mathematical model of the system level test selection problem is constructed,and the binary genetic algorithm is applied to solve the problem,which achieves the goal of system level test selection.

Keywords:test selection,dependency matrix,fault detection rate,testability prediction,binary genetic algorithm.

1.Introduction

Test selection is one of the most important tasks in testability design for equipment,whose goal is searching for the optimal test set to satisfy the requirements of fault diagnosis indexes.The universal way to make test selection is as follows [1]:to analyze the object’s fault modes and preliminarily select tests at first,and then to construct a“0/1”type matrix which is called typical dependency matrix (TDM) to describe the relationship between equipment’s faults and tests,and based on the matrix to establish a mathematical model to describe the test selection problem,and to search out the optimal test set through optimization algorithms in the end.Test point selection is a special case of test selection.In addition to the above factors,the influence of the distribution of test points on the system under tests needs to be considered.Zhang [2],Meng [3] and Li [4] studied test point selection.Khanlari[5],Saeedi[6],Tang[7],Cui [8] and Luo[9]researched the test point selection approach for analog circuits.Sensor selection is a further refinement of test selection.Factors such as sensor types and test parameters need to be further considered.Namburu [10],Wang[11],Wang [12] and Yang [13] studied sensor optimal selection.Xu [14] and Qiu [15] further studied the optimal sensor selection aiming at the prognostics and health management (PHM).In addition,the problems of test selection in complex situations are also studied.Zhang [16]and Lei [17] studied test selection considering test uncertainty.Liu [18] studied test selection of system with multioperation modes.Ye [19] studied tests selection considering critical faults.Ma [20] studied tests selection considering the cost of alternative maintenance.The optimization algorithms for solving the test selection problem are widely researched.Golonek [21] studied the genetic algorithm.Yu [22] studied the improving radial basis function network method.Amati [23] studied the integer linear programming method,Wang [24] studied the odd and even space methods,Rahimi [25] studied the geometric method.Harkat [26] studied the nonlinear principal component analysis method.Zhu [27] studied the improved discrete particle swarm optimization algorithm. Deng[28] studied the heuristic particle swarm optimization approach. Chen [29] studied the hybrid binary particle swarm optimization (BPSO) and the genetic algorithm(GA). Lei [17] studied the quantum evolutionary algorithm. Mu [30] studied the chaotic binary bats algorithm.

In general,the above researches mainly focus on the optimization algorithm,however,the model and the method of system level test selection are not involved.Since modern equipment is designed for testability hierarchically,products at each level should take its testability indicators as constraints to carry out test selection.However,the existing models and methods are not hierarchical,so they are not suitable for system level test selection.In this regard,this paper first analyzes their common problems,and then proposes an improved model,namely combinatorial dependency matrix,and finally carries out case verification.

2.Background

Test selection is usually described as

where γFDand γFIare the required fault detection rate and the fault isolation rate,respectively.They are required testability indicators.Tis the candidate test set of the object,which should be complete to meet the required testability indicators.cjis the cost of testtj∈T,which can be design cost,application cost,maintenance cost or combination cost of the three.If the test cost cannot be determined,then letcj=1.T∗is the optimal test set selected fromT.For example,if the optimal tests aret1,t2,andt3,thenT∗={t1,t2,t3} .andare the predicted fault detection rate and the fault isolation rate,respectively.They are predicted test indicators.If the system’s faults obey exponential distribution,thencan be calculated by

where λiindicates the fault rate offi,firepresents the fault;Diindicates whetherfican be detected,which can be calculated by

wherebi,jis the element of the matrixDFT,and indicates the relationship between testtjand faultfi.DFTis the TDM of the object’s fault set and candidate test set,whose form is shown inTable 1.Iffican be detected bytj,then letbi,j=1,otherwise,letbi,j=0.DFT∗is the submatrix of the object’s fault set and optimal test set.For example,ifT∗={t1,t2,t3},then

Table 1 TDM

If the fault obeys exponential distribution,thencan be calculated by

whereIiindicates whetherfican be isolated,which can be calculated by

whereFiandFjrepresent theith row and thejth row ofDFT∗,respectively.The symbol " ⊕" is the Boolean exclusive or operation.

The optimal test set can be obtained by applying optimal search algorithms to solve (1).

Modern equipment generally makes design for testability hierarchically,i.e.,its products at each level should take their required testability indicators as constraints to carry out their test selection.Since unit level test selection is aimed at unit faults (internal fault of system component unit) diagnosis,which does not care system faults(such as cable fault and connector fault),its constraints are the unit level fault detection rate and the fault isolation rate,and the candidate test is only unit level test (led by the unit and implemented in the system integration state or decomposition state).The system level test selection is aimed at the whole system’s fault diagnosis.Since the whole system’s faults include unit faults and integrated faults (caused by abnormal connection between units or abnormal function between units during system integration,such as bus faults,cable faults,and connector faults),the candidate test is the system level test (led by the system and usually implemented in the system integration state),and its constraints include not only the system level fault detection rate and the fault isolation rate,but also the integrated fault detection rate.The integrated fault detection rate is defined as

where γFDxis the integrated fault detection rate. λxis the total fault rate of integrated fault (the integrated fault set is recorded asFx).λDxis the fault rate of the detectable integrated fault.The integrated fault detection rate can be obtained from testability allocation by the method proposed in [31].The above model and method are suitable for single-level systems (simple systems),but unsuitable for multi-level systems (complex systems).The reasons are as follows:

(i) Equation (1) cannot accurately describe system level test selection.As mentioned above,the system level test selection should not only satisfy the system level fault detection rate and the fault isolation rate,but also meet the integrated fault detection rate,i.e.,“three rates”,while (1) only specifies“two rates”.

(ii) The TDM is unsuitable for system level test selection.System level test selection needs to know unit faults,integrated faults,unit level tests,and system level tests,however,most systems typically adopt top-down testability design (it means system level test selection is before unit level test selection),so that the unit level test selection has not been made when the system level is making test selection,which causes difficulties to accurately obtain the unit faults and unit level tests.Therefore,it needs to make reasonable assumptions on the unit fault and the unit level test.Since they are assumed,the“0/1”type matrix is unsuitable to describe the uncertainty relationship between unit level tests and unit faults.

(iii) Equations (2) and (4) are unsuitable for testability prediction.These prediction formulas are based on the TDM.Since the TDM needs to be modified,the prediction formulas should be modified accordingly.

3.Combinatorial dependency matrix (CDM)

3.1 Matrix definition

First of all,several key words are defined as follows:

Definition 1System’s fault refers to the fault that causes the system to fail to perform specified functions,including unit fault and integrated fault.

Definition 2Unit fault refers to the fault occurred inside the component unit of the system.

Definition 3Integrated fault refers to the fault caused by abnormal connection or abnormal function between units during system integrating,such as cable fault between units and connector fault.

Definition 4Unit level test refers to the test led by the unit level in the system integration state or the decomposition state.The unit level test can be divided into selftest (which can only detect its own fault) and functional test (which can also detect other units’ faults and integrated faults).

Definition 5System level test refers to the test led by system level only in the system integration state.System level test is mainly used to check whether the system functions are normal,and they can detect multiple unit faults and integrated faults.

And then,two basic conditions for the proposed model are given as follows:

Condition 1The system is so complex that it needs to be designed hierarchically and accordingly,test selection should be carried out for system level and unit level separately.If the system is not designed hierarchically,the model and approach described in Section 2 is sufficient.

Condition 2The system adopts a top-down testability design,that is to say,to make testability index allocation first,and then to make system level test selection and unit level test selection in turn.If the system adopts the bottom-up design process,i.e.,to make unit level test selection before system level test selection,then the traditional model and method should be applied.The conventional design process is top-down.

If the above two conditions are satisfied,the following assumptions should be made before the model in this paper is given.

Asumption 1The required system level fault detection rate,the fault isolation rate,the fault rate of the units and integrated faults are assumed to be known,and the unit level fault detection rate and the integrated fault detection rate are obtained by testability allocation [31].

Asumption 2The integrated fault set is obtained through fault mode and effect analysis (FMEA) and the candidate system level test set is obtained through the system function channel analysis and the observation points analysis.

Asumption 3Each unit is assumed to have only one fault and one test,since system level test selection should consider integrated faults,unit faults,system level tests,and unit level tests at the same time,yet the unit level test selection has not been made,so unit faults and unit level tests cannot be obtained accurately.

Asumption 4Each unit’s test is assumed to be selftest and only detects the unit’s fault with the detection rate equal to the allocated detection rate.Since the unit level test selection has not been made during system level test selecting,it is unknown whether the unit’s test can detect other units’ faults or not.

A new matrix is proposed,which is shown inTable 2.

InTable 2f1−fNindicate unit faults.fN+1−fN+Mindicate integrated faults.t1−tNindicate unit level tests,tN+1−tN+Windicate system level tests.The matrix is divided into three parts.

Table 2 CDM

Thirdly,the diagonal element ofis equal to the unit’s allocated fault detection rate.As it is assumed that each unit’s test is self-test,it can be deduced that the unit’s fault cannot be detected by any other unit’s test.In order to satisfy the unit’s allocated fault detection rate,the diagonal element should be equal to the unit’s allocated fault detection rate instead of“1”.

Since the proposed matrix defined above is composed of three parts,and the elements of the three parts are significantly different,it is named as CDM.

3.2 Matrix generation

The steps to generate a CDM are as follows:

Step 1Determine the row elements of the matrix.The row elements correspond to the whole system’s faults,including integrated faults and unit faults.The key point is to determine the integrated faults,which can be obtained by FMEA.

Step 3Determine the relationship between all faults and all tests.The submatrixis a diagonal matrix,and its elements on the diagonal can be obtained from testability allocation [31].The submatrixis a full“0”matrix.The submatrixcan be obtained by traditional methods [1].

3.3 Simulation case

The system shown inFig.1is applied to demonstrate the CDM generation process.The system is composed of four units (µ1−µ4),eight ports (ρ1−ρ8) and three cables(l1−l3).

Fig.1 Testability model of the case system

There are four units’ faults (f1−f4) and four unit level tests (t1−t4) according to Asumption 3.There are three integrated faults (f5−f7) belonging to the cablesl1−l3respectively,and three system level tests (t5−t7).The allocated units’ fault detection rates are 0.9,0.9,0.85,and 0.95,respectively.

According to Subsection 3.3,the CDM of the case system is obtained,as shown inTable 3.

Table 3 CDM of the case system in Fig.1

4.Indicators prediction

4.1 System level fault detection rate

Three rules to judge whether a fault can be detected are shown as follows:

Rule 1For a given faultfi,if at least one element in theith row is“1”,thenfiis considered as detectable,and its detection rate is equal to“1”.

Rule 2For a given faultfi,if there is only one element which is non“0”and a decimal in theith row,thenfiis detectable,and its detection rate is equal to the element.

They hid themselves in the wood through which the Prince had to pass on his way to the palace, and there fell on him, and, having beaten him to death, they carried off the golden horse and the golden bird

Rule 3For a given faultfi,if all elements in theith row are“0”,thenfiis considered as undetectable,and its detection rate is equal to“0”.

According to the above rules,the system level fault detection rate can be predicted as

whereDiis the detection rate offi,which can be calculated by

4.2 Integrated fault detection rate

The integrated fault detection rate can be calculated by

where γFDxis the detection rate of integrated faults. λxis the total fault rate of integrated faults.λDxis the total fault rate of detectable integrated faults.

4.3 System level fault isolation rate

In general,each unit is assumed to be a line replaceable unit (LRU),and all integrated faults are regarded as one LRU.The rules to judge whether a fault can be isolated to one LRU are as follows:

Rule 4For a given unit’s faultfi(1≤i≤N),it is divided into two parts to judge:the part with fault rate γFDi·λican be isolated to one LRU;the rest part with fault rate(1−γFDi)·λican be isolated to one LRU,only if at least one element in theith row is“1”,and if anykth(where 1≤k≤N+M,k≠i) row is different from theith row(to makebi,i=0 before comparison).

Rule 5For a given integrated faultfi(N+1≤i≤N+M),if theith row (to makebi,i=0 before comparison) is different from anykth (where 1≤k≤N) row,thenfican be isolated to one LRU.

Based on the above rules,the system level fault isolation rate can be calculated by

whereIiindicates the isolation rate offiwhich can be calculated by

whereFiandFjrepresent theith row and thejth row of the CDM,respectively. ⊕ is the Boolean exclusive or operation,and makebi,i=bj,j=0 (1 ≤i,j≤N) before the above calculation.

4.4 Simulation case

The simulation case in Subsection 3.3 is applied again to demonstrate the prediction process of the three rates.

Firstly,as shown inTable 3,the elements of column 7 are all“1”.According to (8),we can getD1=···=D7=1.Substitute it into (7),then we get γFDs=1.

Secondly,we can get γFDx=1 by the same way.

Finally,according to (11),we getI1=I2=0.9,I3=0.85,I4=0.95,I5=I6=I7=1.Then substitute them into(10),we get γFIs=0.94.

5.Selection algorithm

5.1 Mathematical description

The system level test selection can be mathematically descripted as

Although the impact of integrated faults is also included in the system fault detection rate,why should γFDxbe regarded as a separate constraint? This is because the system level test selection studied in this paper focuses on the integrated fault detection problem.If γFDxis not listed separately,the detection of integration faults may be ignored in system level test selection,which will further lead to over design of test items for units’ faults,and under design of test items for integration faults.

The integrated fault detection rate is the same as the allocation index of each airborne equipment,but it is used to restrict the system level testability design.Because this paper studies the system level test selection.As mentioned above,the key point of system level test selection is to solve the problem of integrated fault detection.To separate the integrated fault detection rate is to emphasize its constraint function.If it is not listed,the detection of integration faults may be ignored in system level test selection,resulting in over design of test items of airborne equipment in test selection,and under design of test items for integration faults.

5.2 Search algorithm

The binary genetic algorithm (BGA) is applied to solve the problem,since it has the following advantages.Firstly,the BGA can achieve greater operating space by coding parameters in practical optimization problems.Secondly,the BGA can achieve multi-objective optimization,parallel search,and multi-objective optimal search in the global scope.Thirdly,the demand for target parameters is not high,and the existing fitness function values and approximations are used.Fourthly,some uncertain rule algorithms can be used to achieve a more comprehensive optimization in the solution space.

5.2.1 Fitness function

The fitness function is the criterion to determine whether the candidate tests will be selected or not.The fitness function is defined as

whereCrepresents the total cost of the alternative test set,which can be calculated by (14). α,β,δ,and ν respectively represent the weights of γFDs,γFIs,γFDx,andC,which are usually assigned [2−5] as

5.2.2 Procedures

Step 1Initialize the parameters,including genetic population,“three rates”,cross mutation parameters,and iteration times.

Step 2Set up different fitness functions according to different weights.

Step 3Make crossover and mutation of the algorithm parameters.

Step 4Choose tests from the candidate test set,and calculate whether they satisfy the required test indicators.If yes,then turn to Step 5;if no,then turn to Step 2.

Step 5Under the constraints of the number of iterations and the indicators,obtain all solutions.

Step 6Output the optimal solution.

6.Case study

6.1 Simulation case

As shown inFig.2,the case system is composed of five units (µ1−µ5) and four cables (l1−l4).The required fault detection rate,the isolation rate and the integrated fault detection rate are 0.95,0.90,and 0.95,respectively.The units’ allocated fault detection rates are 0.9,0.8,0.75,0.85,and 0.95,respectively.The above method is applied to select system level tests for the case system.

Fig.2 Testability model of the case system

Step 1Determine the system’s faults,including units’faults (f1−f5,belonging to units µ1−µ5,respectively)and integrated faults (f6−f9,belonging to cablesl1−l4,respectively).

Step 2Determine the system test set,including units’test (t1−t5) and system level test set (t6−t18).

Step 3Generate the CDM,as shown inTable 4.The last row and the last column of the table are the test cost and the fault rate,respectively.

Table 4 CDM of the case system in Fig.2

Step 4Set the parameters:let α=5,β=2,δ=3,ν=2,the population size be 50,the genetic algebra be 2000,the crossover probability be 0.8,and the mutation probability be 0.1.

Step 5Start the BGA,and get the optimal test results={t12,t17}.The predicted“three rates”are 0.9567,0.9805,and 0.9333,respectively.The fitness function and the iteration degree curve are shown inFig.3.

Fig.3 Fitness function and iterations curve

The algorithm has fast speed and high precision,which can achieve the optimization goal within 100 iterations.It shows that BGA has a strong ability to solve system level test optimization.

Five results are listed inTable 5to make comparisons.

Table 5 Comparison among test selection results of the case system in Fig.2

Result 1 takes“three rates”as constraints,and the result shows that the three rates are satisfied.Result 2 takes“one rate”as the constraint,and the result shows that two rates are satisfied except the system level fault isolation rate.Result 3 takes“two rates”as constraints,and the result shows that only the integrated fault detection rate is unsatisfied.Result 4 takes“three rates”as constraints without considering unit level tests,and the result shows that the three rates are satisfied,but the total cost is the highest among all results.Result 5 takes“three rates”as constraints without considering system level tests,and the result shows that only the system level fault isolation rate is satisfied.Comprehensively considering indicators satisfaction and test cost,Result 1 is the best choice.

From the case,two conclusions can be drawn as follows:firstly,considering three rates is better than considering a single rate or two rates to constrain the test selection;secondly,the combination of unit level tests and system level tests can obtain better testability or lower test cost than only unit level tests or only system level tests.

6.2 Real case

A real case system is composed of nine units:automatic flight control computer (AFCC),automatic flight control unit (AFCU),Joystick actuator (BDA-A),wheel actuator(BDA-B),pedal actuator (BDA-C),principal flight control computer (PFCC),inertial navigation system (INS),flight management computer (FMC) and air data computer (ADC).The system has three kinds of cables:hard line,1553B bus and ARINC429 bus.Its testability model is shown inFig.4.

Fig.4 Testability model of the case system

It is known that the“three rates”are:the fault detection rate is 0.90,the fault isolation rate (isolated to one unit) is 0.90,and the integrated fault detection rate is 0.94.The CDM is shown inTable 6.

The above method is applied to select the system level tests for the system.Five results are listed inTable 7to make comparisons.

Table 6 CDM of the case system in Fig.4

Table 7 Comparison among test selection results of the case system in Fig.4

Result 1 takes“three rates”as constraints,and the result shows that three rates are all satisfied,although its test cost is the highest.Result 2 takes“one rate”as the constraint,and shows that two rates are satisfied except the integrated fault detection rate.Result 3 takes“two rates”as constraints,and shows that two rates are satisfied,and the integrated fault detection rate is a little higher than Result 2.Result 4 takes“three rates”as constraints and not considers unit level tests,and shows that all system level tests are selected,but the fault isolation rate is unsatisfied.Result 5 takes“three rates”as constraints and not considers system level tests,and the result shows that only the fault isolation rate is satisfied.Comprehensively consider indicators satisfaction and test cost,and Result 1 is the best choice.

7.Conclusions

The system level test selection model and method are studied,and the conclusions are drawn as follows.

(i) The dependency matrix is very important for test selection.Since the TDM does not satisfy the system level test selection requirements,a novel dependency matrix composed of three submatrices is created.Aiming at the problem of lacking detailed data of units’ fault and test,which are necessary to generate the TDM,it is assumed that each unit has one fault and one test and each unit is self-test,and then the matrix is obtained successfully.It is proved that these assumptions are more reasonable than the ones not considering unit faults and tests.

(ii) In the existed mathematical model of test selection,the fault detection rate and the fault isolation rate are considered as constraints,which are not enough to describe the detection ability of system level test to integrated faults.Aiming at this problem,a new testability indicator,namely integrated fault detection rate is presented.Besides,the prediction formula of“three rates”are presented based on the CDM.

(iii) Based on the proposed CDM and "three rates" formulas,a mathematical model of system level test selection is constructed,which is solved by applying the BGA.Simulation case and real case are applied to verify the proposed method,and the results show that under the condition of“three rates”,the algorithm can get the least set of system level test items quickly and achieve the goal of system level test selection better.