Optimal Distribution of a Given Number of Checkpoints among the Devices of a Radio-Electronic Complex

V. M. Razin, N. I. Sablin

(Presented by the scientific seminar of the Department of Computer Engineering)

In the development and operation of radio-electronic complexes, the problem arises of distributing a given number of checkpoints among the complex devices that make up these complexes in such a way that the automatic monitoring system (AMS) detects, with maximum probability, a fault that has occurred in the complex.

Let the radio-electronic complex consist of \(n\) devices. We shall assume that these devices are sufficiently complex and require, at a minimum, that at least one checkpoint be placed on each of them. If the total number of checkpoints is \(m\), then this condition can be written in the form of the inequality

\[ m \geqslant n \ldots \tag{1} \]

We assume known the probabilities \(P_i \{i = 1, \overline{n}\}\) of fault-free operation of each device and the probabilities \(\gamma_i \{i = 1, \overline{n}\}\) that the automatic monitoring system will detect a fault in the \(i\)-th device when there is one checkpoint in it. It is required to distribute \(m\) checkpoints among the \(n\) devices of the complex in such a way that the probability of detecting a fault in the complex by means of the AMS is maximal.

Introduce the following notation:

Event \(A\)—detection of a fault by the AMS in the complex; it is assumed that the AMS is absolutely reliable.

Hypothesis \(H_i \{K = 1, \overline{n}\}\)—the fault has occurred in the \(i\)-th device. We assume that, when the fact of a fault in the complex has been established, the fault is single, i.e., it is present in only one device; in this case, obviously,

\[ \sum_{i=1}^{n} P(H_i) = 1. \]

In this case the probability \(P(A)\) of detecting a fault by the AMS in the complex is determined by the following relation:

\[ P(A) = \sum_{i=1}^{n} P(H_i) P(A/H_i) \ldots \tag{2} \]

\(P(H_i)\) is equal to the a priori probability that the \(i\)-th device has failed, and is determined by relation (3):

\[ P(H_i)=1-P_i^*=\frac{\dfrac{1-P_i}{P_i}}{\displaystyle\sum_{i=1}^{n}\frac{1-P_i}{P_i}} . \tag{3} \]

Suppose that on the first \(n-1\) devices there are placed \(m_i\{i=1,\overline{n-1}\}\) checkpoints; then on the \(n\)-th device there will be placed

\[ m_n=m-\sum_{i=1}^{n-1}m_i \]

checkpoints; in this case the total number of checkpoints is equal to

\[ \sum_{i=1}^{n}m_i=m. \]

Assume that on the \(i\)-th unit there are placed \(m_i\) identical checkpoints having one and the same effect. Then the probability of detecting, by the SAC, a fault in the \(i\)-th device is equal to

\[ P(A;H_i)=1-(1-\gamma_i)^{m_i}\ldots \tag{4} \]

Expression (4) gives the dependence of the probability of detecting a fault in the complex under the condition that the \(i\)-th device, on which \(m_i\) (\(m_i\) is a variable quantity) checkpoints are placed, has failed.

Substituting relations (3) and (4) into (2), we obtain:

\[ P(A)=(1-P_n^*)\left[1-(1-\gamma_n)^{\,m-\sum_{i=1}^{n-1}m_i}\right] +\sum_{i=1}^{n-1}(1-P_i^*)\left[1-(1-\gamma_i)^{m_i}\right]\ldots \tag{5} \]

or, taking into account that \(\sum_{i=1}^{n}(1-P_i^*)=1\), we finally have

\[ P(A)=1-(1-P_n^*)(1-\gamma_n)^{\,m-\sum_{i=1}^{n-1}m_i} -\sum_{i=1}^{n-1}(1-P_i^*)(1-\gamma_i)^{m_i}\ldots \tag{6} \]

The probability \(P(A)\) depends substantially on the distribution of checkpoints among the devices of the complex. In our case it is necessary to find such a set \(\{m_1,m_2,\ldots,m_n\}\) that maximizes

\[ P(A)=f(m_1,m_2,\ldots,m_n)\to \max . \]

To determine the optimal \(m_i\{i=1,\overline{n-1}\}\) and, consequently,

\[ m_n=m-\sum_{i=1}^{n-1}m_i, \]

the set of which maximizes \(P(A)\), we differentiate expression (6) successively with respect to \(m_i\{i=1,\overline{n-1}\}\). Equating the obtained partial derivatives to zero, we obtain a system of \(n-1\) equations:

\[ \left\{ \begin{aligned} &(1-P_1^*)(1-\gamma_1)^{m_1}\ln(1-\gamma_1) -(1-P_n^*)(1-\gamma_n)^{\,m-\sum_{i=1}^{n-1}m_i}\ln(1-\gamma_n)=0,\\ &(1-P_2^*)(1-\gamma_2)^{m_2}\ln(1-\gamma_2) -(1-P_n^*)(1-\gamma_n)^{\,m-\sum_{i=1}^{n-1}m_i}\ln(1-\gamma_n)=0,\\ &\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \end{aligned} \right. \tag{7} \]

\[ \left\{ \begin{aligned} &(1-P_i^*)(1-\gamma_i)^{m_i}\ln(1-\gamma_i) -(1-P_n^*)(1-\gamma_n)^{\,m-\sum_{i=1}^{n-1}m_i}\ln(1-\gamma_n)=0,\\ &\ldots\\ &(1-P_{n-1}^*)(1-\gamma_{n-1})^{m_{n-1}}\ln(1-\gamma_{n-1})\\ &\qquad -(1-P_n^*)(1-\gamma_n)^{\,m-\sum_{i=1}^{n-1}m_i}\ln(1-\gamma_n)=0. \end{aligned} \right. \]

The solution of system (7)

\[ \left\{m_1^*,\,m_2^*,\,\ldots,\,m_i^*,\,\ldots,\,m_{n-1}^*,\,m-\sum_{i=1}^{n-1}m_i^*\right\} \]

optimally distributes the \(m\) checkpoints among the devices of the complex.

The system of equations (7) with respect to \(m_i\) is easily solved analytically by moving one of the terms in the difference of the left-hand sides of the equations of the system to the right-hand side, followed by taking logarithms of both sides; after this we obtain a system of ordinary linear equations, which is solved by known methods. Consider a hypothetical example. Let the complex under study consist of \(n=3\) devices with \((1-P_1^*)=0.25\), \((1-P_2^*)=0.30\), and \((1-P_3^*)=0.45\), and let \(\gamma_i\{i=1,\overline{3}\}=\gamma=0.8\). It is required to distribute \(m=5\) checkpoints. On the basis of the above procedure we obtain a system of two equations:

\[ \left\{ \begin{aligned} &0.25\cdot 0.2^{m_1}-0.45\cdot 0.2^{5-m_1-m_2}=0,\\ &0.30\cdot 0.2^{m_2}-0.45\cdot 0.2^{5-m_1-m_2}=0. \end{aligned} \right. \tag{8} \]

Having solved system (8) and restricted ourselves to integer values (the nearest integer is taken) of \(m_i\), we obtain the following optimal distribution:

\[ \{m_1=1;\quad m_2=2;\quad m_3=2\}. \]

In this case

\[ P(A)=1-0.25\cdot 0.2^1-0.30\cdot 0.2^2-0.45\cdot 0.2^2=0.92. \]

The method set out above for the optimal distribution of \(m\) checkpoints among \(n\) devices of a complex may also be interpreted, when \(m=n\), as the determination of the optimal multiplicities of polling all devices of the complex in order to increase the reliability of monitoring.

The proposed method also makes it possible, for a prescribed probability \(P^*[A]\) of detecting a fault in the complex by the automatic monitoring system, to determine the minimum value of \(m\), characterizing the depth of monitoring of the complex under study. The algorithm for determining \(m\) is very simple:

1st step. Set \(m=n\) and compute \(P(A/m)\). If \(P(A/m)<P^*(A)\), proceed to the second step.

2nd step. Take \(m+1\) checkpoints and compute \(P(A/m+1)\). If \(P(A/m+1)<P^*(A)\), proceed to the 3rd step, and so on.

The process terminates at the \(k-m\) step; in this case the number of checkpoints is equal to \(m+k\), and

\[ P(A/m+k)\simeq P^*(A). \]

In the present case, in passing from step to step the number of checkpoints is increased by \(\Delta m=1\). To speed up the computation process, it is advisable to take \(\Delta m>1\) until the first exceedance \(P(A/m+k)>P^*(A)\), and then to take \(\Delta m=-1\) until the relation \(P(A/m+k-j\cdot\Delta m)\simeq P^*(A)\) is obtained, where \(j\) is the number of steps with \(\Delta m=-1\).