IEEE TRANSACTIONS ON SYSTEMS. MAN, AND CYBERNETICS, VOL. 21, NO. 5, SEPTEMBEWOCTOBER 1991
Decision Fusion Strategies in Multisensor Environments Belur V. Dasarathy, Senior Member, IEEE
Abstract-Efficient decision fusion strategies, for deriving optimal decisions in multisensor target recognitionltracking environments, are postulated and analyzed in this study. This fusion paradigm, which is designed for fusing decisions derived from a suite of parallel sensors, is embedded within a recursive system structure to achieve significant enhancement in the reliability of the fused decisions.
I. INTRODUCTION
T
HE STUDY OF distributed multisensor networks and the problem of intelligent integration of multisensor data [24] has gained immense popularity recently with the advent of vigorous sponsorship from DOD of the sensor fusion technology areas. The survey by Luo and Kay [24] that covers more than 200 papers, attempts to draw a distinction between the terms multisensor integration and fusion although in most literature these terms have often been used interchangeably. The distinction however remains murky even within this survey. In general, sensor fusion can be accomplished at different levels: data fusion, feature fusion and decision fusion. A variety of paradigms have been put forth for the study of the sensor fusion at all these levels and were extensively reviewed in a recent survey by Dasarathy [25]. Depending upon the specific sensors used, fusion at the data and feature levels may or may not always be practical. For example, data fusion would require compatible sensors that are appropriately registered to ' permit such data level integration. Further, decision fusion is deemed more robust than fusion at the lower levels, as failure of one of the sensors in the sensor suite does not signify total catastrophic failure of the entire system. These comparative aspects are discussed in more detail in the survey paper [25]. Here, this study addresses the limited problem of fusion at the highest level, namely decision fusion, which minimizes the amount of data to be transmitted between the individual sensors and the central fusion processor by limiting it to just the current decisions derived by the sensors. While there indeed have been a number of studies [1]-[23] in this decision fusion area over the past decade, the approach and the information processing structure developed here are significantly different from the previous studies. The objective of this study is to develop possible strategies for fusion of current decisions derived in parallel from the different sensors in order to ensure that the fused decision derived by the Manuscript received August 10, 1990; revised March I , 1991. This work was supported in part by U S . Army Strategic Defense Command under Contract DASG-60-89-C- 130. The author is with Dynetics, Inc., Huntsville, AL 35814-5050. IEEE Log Number 9102024. 0018-9472/$01.00
process is optimal for the environment and such a reliable fused decision is obtained at the earliest possible time. Tenney and Sandell [l] were one of the first to study the problem of detection with distributed sensors. The analysis follows classical Bayesian theory, and offers decentralized statistical hypothesis testing at each of the individual sensors in the distributed network to determine the optimal local detection rules. It did not however explicitly tackle the problem of fusion of these decisions in terms of development of optimal data fusion algorithms. Dasarathy [2] studied a limited version of the decision fusion problem in the context of multiple classifiers operating with a single sensor, using a recursive structure that could be viewed as a forerunner to the problem tackled here. Chair and Varshney [ 3 ] attempted the development of an optimal global decision rule through weighting the independent optimal decisions of the individual sensors, by their reliability rates known in terms of false alarm and miss rates, and comparing the weighted sum of these decision probabilities against a likelihood threshold to derive the global decision. The problem considered by them is essentially one of target detection, i.e., a two-class problem. A different type of generalization of the analysis in [l] was presented independently by Sadjadi [4] around the same time as the study by Chair and Varshney [3]. He offered an optimal solution for the general case of m-ary hypotheses testing for 'n sensors but again without explicit optimal fusion. A loss function is defined corresponding to each local decision and a mean loss function averaged over these individual loss functions is minimized resulting in sets of simultaneous inequalities involving the generalized likelihood ratios at the local detectors. The solutions to these inequalities define the optimal decision domains. The study by Reibman and Nolte [5] extended the previous study (31 by simultaneous optimization of the local detectors while deriving the overall optimal fusion design. This involves solution of coupled equations representing the performance of the local detectors and the global fusion processor. In essence, this study combined the ideas of local decision optimization of Tenney and Sandell with the fusion optimization proposed by Chair and Varshney [3]. The same scenario is handled in a more general way by Thomopoulos [6] et al., using the Neyman-Pearson (NP) test both at the individual sensor level as well as at the decision fusion level. The fused decision is shown to have a higher probability of detection than the individual one for cases with three or more sensors under a constant false alarm rate for all the sensors. The method also permits some quality information on each of the decisions to be taken into account. 0 1991 IEEE
DASARATHY: DECISION FUSION STRATEGIES
1141
In a second study, Reibman and Nolte [7] looked at the system decision space partitioning in multisensor environments. The performance in more detail than before. Thomopoulos et al. study investigates the benefits of transmitting reliability data in [8] revisited the problem of decision fusion in distributed addition to the traditional decision only transmission assumed sensor systems considered earlier with Neyman-Pearson test between the local sensors and the central processor in many at the fusion center as before but likelihood ratio tests at of the previous studies. This transmission is still limited to the individual sensors. Two specific computationally efficient just a few additional bits and not complete local likelihood but suboptimal algorithms were proposed and numerically ratio information that represents the other end of the spectrum. illustrated. Thomopoulos and Okello [9] presented an approach This compromise level of information transmission in effect to the problem of detection with consulting sensors and represents a partitioning of the local decision space and entails associated communication costs. Here, one of the two available an optimization of the partitioning problem. Demirbas [ 161 presented a nonparametric binary decision sensors, is viewed as the primary sensor and the other only as a consulting sensor, to be called upon only when deemed cost trees approach to the fusion problem, which could be viewed justifiable in view of the communication costs involved in the more as a feature fusion tool. In that sense, this is some what consultation process. Various random and non-random request outside the main stream of the studies discussed here, but does schemes are considered in their analysis along with some contain some interesting elements of possible extrapolatory numerical results for illustrating the principles. Demirbas [101 value. Thomopoulos et al. [17] provided some additional presented a new maximum a posteriori approach to this prob- results in terms of proofs of the combined NP test (at the lem of recognition in multisensor environments. He showed fusion center) and likelihood ratio criterion (at the individual that in an object detection environment, the maximum a pos- sensors) based solutions offered for the distributed decision teriori estimation approach minimizes the mean square error. problem considered earlier in [6], [8]. Recently, Hoballah and Viswanathan and Thomopoulos [ 111 considered the serial Varshney [ 181 investigated this problem from an information problem involving hand-over from one sensor to the other, theoretic point of view. They employ an entropy-based cost instead of the parallel decision fusion considered in their function for the optimization of the overall decision system, earlier studies, once again using the NP test. The j t h sensor which is intended to maximize the amount of information decision is dependent (and optimal in the NP sense) not only transfer from the input side to the output side. In another on its own observations but also on the optimal NP decision paper [19] in the same issue, they dealt with the problem of of the previous ( j - 1)th sensor. It is claimed that the serial deriving a global decision by combining local binary decisions scheme has a better performance than the parallel scheme in through a Bayesian formulation. A special case of identical certain cases of two-sensor suite. However, this is not true local detection sensors with independent observations is also if more than two sensors are deployed in the fusion process. considered. Some specific fusion scenarios were explored Also, such a serial configuration is more susceptible to overall recently by Polychronopoulos and Tsitsiklis [20]. A finite system failures caused by failures in one of the components valued function of the local observations is transmitted to the or the in-between links thereof. From this view point a fusion processor wherein the M-ary decision is to be made. combination of serial-parallel configuration may be worthy of The asymptotic scenario of very large number of sensors is further exploration. A distributed Bayesian hypothesis testing analyzed to conclude that large number of sensors transmitting approach with distributed data fusion was presented by Chair coarse (few bits of) information yield better result than fewer and Varshney [12]. This study, unlike earlier studies wherein number of sensors offering more detailed (large number of the fusion processing was limited to the central location, looks bits) data. This conclusion does not take into consideration at a system configuration that permits data fusion at each the cost of such large network of sensors. Very recently, Baraghimian and Klinger [21] proposed a local site. The analysis leads to multiple coupled nonlinear equations and solutions may involve multiple local minima. preferential voting scheme for the fusion process. This comes Identification of global minimum becomes compute intensive closest in terms of the concepts being presented here in and therefore the practicality of the approach in real world this study, in that the fusion process is based on a voting applications requires further careful consideration. Thomopou- scheme. However, it does not include the novel concept of 10s and Okello [13] dealt with the problem of detection with recursive structure (within which the voting is embedded) that mismatched sensors. This addresses a very specific type of is being offered here. A more recent example of these decision problem wherein the two sensors each have certain blind spots fusion studies is that of Krzysztofowicz and Long, once again in their field of view. There are numerous assumptions made in on a Bayesian detection model [22]. Three specific schemes the analysis such as known geometry of the visible and blind for fusing information are analyzed. They are: fusion of spot regions and the like. The study is therefore not of a general observations (data fusion), fusion of local decisions (decision nature, although some of the concepts may have applications fusion), and lastly fusion of probabilities (which can be looked in other specific contexts as well. This was followed by a study upon as partially decision fusion, with some data from the local by Barkat and Varshney [14] on the constant false alarm rate sensors also being taken into account in the fusion process). (CFAR) problem in the distributed sensor environment. The This study, unlike most of the earlier ones, attempts to relate study examines the scope for adaptive threshold techniques the analysis to non-DOD applications although in reality the instead of pre-fixed thresholds used in the earlier studies in extent of applicability of this study to other applications is order to assure a detection with constant false alarm rate. no more or no less than most of the prior studies in the Lee and Chao [15] presented an interesting study on optimum area. Unfortunately, the study does not clearly bring out its
1142
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS, VOL. 21, NO. 5, SEPTEMBERIOCTOBER 1991
TRffiER APPROPRIATE y ~ s ACTION C0NSlSTEN-r +
DECISION ACROSS THE SUITE?
Fig. 1. A recursive processing system structure for optimal decisions with a parallel sensor suite.
contribution relative to that made by the other studies cited here. The study by Tang et al. [23] represents the most recent of these efforts. They deal with the problem first enunciated by Tenney and Sandell [ l ] and relate their efforts to those of Chair and Varshney [3] as well as Reibman and Nolte [4]. However, none of the other efforts cited here [5]-[22] are included in their discussions. The analysis being presented here is most akin to studies on voting schemes [21] but goes further by offering a recursive structure for enhancing the results of such voting. This is a significant departure from the other studies, none of which looked at the scope for improving performance with a recursive structure triggered on the basis of results of decision fusion. In the study presented here, the problem is viewed as one of parallel fusion of the individual independent decisions with a recursive structure that permits enhancement of the reliability of the fused decision. Instead of a voting based fusion approach, this recursive structure can be combined with any one of the other optimal fusion techniques [1]-[23] as well. While these and other alternatives are still under investigation, an analysis based on a simple voting or consistency measure dependent fusion scheme is being presented here to mainly illustrate the recursive model and its benefits. In the problem environment considered here, it is assumed that if a reliable decision cannot be made at any given stage, then we seek a new set of decisions from the sensors and completely disregard the earlier decisions that are deemed suspect due to the lack of required degree of consistency. Accordingly, the fusion strategies developed here are based only on current decisions from the sensor suite rather than on all the cumulative decisions. However, a discussion of the cumulative strategy is included in the concluding section to illustrate the scope for widening the application potential of the concepts proposed here in this study. 11. A PARALLELSENSORS SUITEANALYSIS Fig. 1 portrays a general system structure of information fusion processing for optimal decision making in multi-sensor environments. The sensor suite consists of t sensors each of which generates a data set Zj processed by its own customized set of algorithms either locally in a distributed sense or in the centralized parallel processor (depending on the application environment and its constraints). The output Oj of each sensor-processor pair is a decision Dj with
an integer value in the range (1,m ) corresponding to a choice among m possible decisions. In the domain of target recognition/multi-target tracking problems, this output can be either a target identification or target data association label. The function of the fusion processor is to determine the consistency of the decisions across the sensor suite at a given time. While it is theoretically possible to visualize an alternative strategy of determining the consistency across the temporal scale, i.e., over a sequence of decisions by each of the sensors, the motivation here is mainly to determine the instantaneous consistency across the sensor suite. Accordingly, the strategy proposed here is to accept the resulting decision and end the recursions if such consistency is reached, or else discard the local decisions as suspect and continue the recursions till an acceptable level of consistent decision is attained. Various measures of consistency can be visualized ranging from consensus (i.e., all decisions are identical) to at least some s of the t sensors are in agreement. The model presented here permits recursive operations directed towards enhancement of the reliability of the derived decision. This is dictated by the decision fusion processor that evaluates the consistency of the decisions across the different sensors and sends a signal to continue the recursive process (of acquiring a new set of signals and reprocessing them) whenever a lack of consistency is detected by the processor. There is no cumulative record of these decisions to be maintained as the consistency assessment is only across the current set of local decisions. While the implications of the alternative strategy of a cumulative consistency check are briefly considered in the closing section, a detailed analysis of such alternatives is decidedly outside the scope of this study. For simplicity of presentation of the concepts and associated strategies, we shall consider the case wherein the output of each sensor-processor pair is a simple decision among a choice of m decisions, i.e., the output is an integer value in the range (1,m). Let (ej : j = 1,. . . , t ) represent the efficiency or probability of correctness of the decision Dj reached by sensor-processor pair j . Implicit in this statement is an assumption that the probability of correctness of the decision Dj is the same for all possible m values of D j . This assumption is being made mainly to keep the analysis simple without in anyway sacrificing its applicability. Even if this assumption were to be not strictly valid, one could approximate it by using the weighted average of the probabilities over all
1143
DASARATHY: DECISION FUSION STRATEGIES
decision choices corresponding to each sensor as a measure of e,j. This weighting would be as per the a priori probabilities of the decision choices available in the environment. The value (1 - e J ) can be used to represent the corresponding misrecognition or error rate for the sensor-processor pair assuming that it always provides a decision (right or wrong) i.e., no possibility of a neutral or unknown decision by an individual sensor is allowed under this scenario. Also, this error rate is the weighted average of both types of wrong decisions in the context of a target detection problem, namely false alarms and misses. The more general scenario, where the sensor-processor pair can have a "no decision" option, can also be analyzed in a fairly similar fashion. This is considered beyond the scope of this presentation in view of the publication space limitations and results of on going studies of this nature will be published in due course separately. Let pk, yk. and rk represent the incremental probabilities of the fused correct, incorrect and nondecisions at the kth stage of recursive process. By definition
+ + r1 = 1.
pl
41
(1)
this analysis is to explore the benefits of using multiple nonidentical sensors that may derive comparable decisions that are not necessarily based on the same type of information content in the environment. Accordingly, we concentrate on a recursive strategy involving multiple sensors, rather than a sequential strategy involving a single sensor. While a fusion based on all the local decisions accumulated thus far can be visualized under this multisensor scenario, the objective here is limited to fusion of current decisions at each stage, the implication being that whenever a reliable fused decision is not derived at any stage, the whole set of local decisions at that stage are considered suspect and disregarded. The current analysis is accordingly limited in principle to a noncumulative fusion strategy, with only limited discussions of the cumulative fusion strategy being included in the concluding section. Substitution of (9) and (10) in (8) (with IC incremented by 1) and use of (1) leads to rk+l
i.e., rk = r:
As only the undecided cases are reprocessed: P2
+ Y2 + 7-2 = r1.
(11)
=rkrl
(12) k
= p1
(2)
CrP-')
(13)
a=1
Generalizing (2) we get pk
k
+ qk + rk = Tk-1.
(3)
Using (3) recursively in (1) gives k
+rk
Err-').
(14)
a=1
Now,
k
CPz+CY* = 1 z=1
Q~ = q1
k
Er!'-')= (1- r f ) / ( 1- r l ) ;
(4)
z=1
i.e.,
0
5 r1 < 1
(15)
z=1
i.e.,
with
pk
= pl (1 - .:)/(I
- TI)
(16)
Qk
= ~ i (1 r:)/(1 - T I )
(17) (18)
+ Qk) + 41):
1 - (4 = 1- (p1
rk = r1
Qrc = i=l
Assuming e j 's are constant in the range of measurements made for a specific target, the instantaneous correct and incorrect fused decision rates, which are functions of e3 's, can be assumed to be also constant and hence the incremental rates can be written as
0
5 r1 < 1.
(19)
It is obvious from (16) and (17) that P k and Q k monotonically increase with k and Tk decreases monotonically with k unless r 1 is zero at the first stage itself. For the case of m = 2, i.e., a decision with only two choices (for example, a target detection problem), r1 can be zero if t is odd and a majority decision is used as the measure of consistency. This makes the recursive process a single shot affair. Examining (16) and (17) further, it can be observed that the asymptotic limit values (as k tends to infinity) of P k and Q k are given by Pklmax
= Pl/(Pl
+ 91)
(20)
Qkim,,
=Y
+~ Y I )
(21)
I
/
i.e., This assumes that local decisions from the same sensor are conditionally independent in time. Under such an assumption one could admittedly visualize a sequential test using multiple observations of a single sensor. However, the objective of
Use of ( 5 ) in (22) shows that the nondecision rate 7-k tends to zero asymptotically, i.e., eventually if we keep processing,
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS, VOL. 21, NO. 5 , SEPTEMBERIOCTOBER 1991
1144
we always will end up with a decision (be it correct or not). Comparing (20) and (21), we can see that the asymptotic fused correct decision rate will exceed the incorrect decision rate if and only if the initial correct decision rate pl is greater than initial incorrect decision rate 41. On the other hand, for the initial nonrecognition rate to be not less than the initial misrecognition rate, we can show that 41 I (1 - Pl)/2.
Pl = e 41 = 0 r1=1-e
(23)
We now examine the relationship of e3’s to pl and 41 by initially considering certain specific values of t, the number of sensors in the environment. While one could conceivably look at the general case directly, the specific cases are indeed of particular interest as in the real world one may have only very few sensors and the application engineer would be benefited from a thorough and detailed analysis of these special cases at a level that is not practical in the general case. Also, the start from the special cases makes the analysis easier to follow especially for those interested more in the results of specific scenarios than in the analytical elegance of generalities. A. Two Sensors Case (t = 2) Here, the consensus is given by an agreement between the decisions generated by the two sensor-processor pairs. Assuming independence of the probabilities of correct decisions arising under the two sensors (although this may not be strictly true, it permits estimation of bounds on the values of p l and 41 1
I 1 (24) 41 = (1 - e l ) ( l - e2)/(m - 1) 5 1 (25) T I = [ ( m - 2) (el e2) - mele2]/(m - 1) < 1. (26)
P I = e1e2
+ +
Here, if one were to permit nondecision rates or partial ignorance about sensor performance and employ an evidential reasoning approach, p l would be expressed in terms of cJ (correct recognition rates) sand 41 would be expressed in terms of w j (misrecognition rates) resulting in a similar but far more complex expression for T I and the subsequent analysis would also get correspondingly changed. These are deemed beyond the scope of this study and as such are not presented here. Reviewing (24) and (25), it is obvious that both the resultant initial correct and incorrect decision rates are bounded on the upper side by the lesser of the corresponding pairs of the individual sensor correct and incorrect decision rates, i.e., Pl I min(e11e2) 41 I min((1 - e l ) , (1 - e2)).
were ignorant as to which of the two is the perfect sensor at any given time but could expect that at least one of the two would be almost perfect most of the time (which is not an unreasonable assumption if redundancy approaches are employed in sensor system design), then expressions (24) through (26) would lead us to
(27) (28)
We shall now consider special cases that deal with interesting scenarios before returning to this general case of two sensors. These cases provide some useful insights into the decision fusion and associated recursive strategy. Subcase AI:-e, = 1 (1 5 i 5 2 ) : At this juncture, it would be interesting to consider the scenario wherein one of the two sensors is always perfect. Of course, if we were to know which sensor is the perfect one, then we could disregard the other sensor and accept the decision of the perfect one without sensor fusion even being required. However, if we
where e is the efficiency of the imperfect sensor. These are independent of the value of m. Use of these values of p l and q1 in (20) and (21) leads to
Expressions (32) and (33) denote that the fused decision asymptotically approaches the correct decision irrespective of number decision choices even though one of the sensors may remain imperfect throughout and further, the system (user) does not know as to which of these two sensors is the imperfect one. We next consider the opposite case of one sensor being always wrong. While this is definitely not a desirable state to be in, it is interesting from the view point of learning its consequences to the fusion process and hence the look at this special but unacceptable case. Subcase A2:-ei = 0 (1 5 i 5 2): Here, expressions (24) and (26) reduce to Pl = 0 41 = (1 - .)/(m - 1) TI = ( m- 2 e ) / ( m - 1)
+
(34) (35) (36)
where e is the efficiency of the other sensor. Under these initial conditions, the recursive fusion process leads to the asymptotic state
P/c1 max = 0 Q k 1 max
=1
(37) (38)
i.e., the fusion process leads to a total failure of the system under this scenario. It is therefore important to ensure that no totally faulty sensor is allowed to operate indefinitely in a two sensor fusion system of this type. Under this scenario, if the other sensor is perfect, i.e., e = I, (34)-(36) further reduce to Pl = 41 = 0 r1 = 1.
(39) (40)
Although the perfect sensor makes the misrecognition rate go to zero, the recognition rate remains to be zero because of the other faulty sensor, with the result no agreement is ever possible between the two sensors making nondecision as the only possible result with a probability 1. Subcase A3:-ei = e (V i : i = 1,2): For this case, (24) through (26) reduce to pl = e2 5 1
(41)
1 I45
DASARATHY: DECISION FUSION STRATEGIES 10
L
-
0.6
7
U
-
- 0.8
0.6
-
-06
0.4
-
-0.4
0.2
-
-02
-E"
m
-E
m U-
1
Q -
a
04
0.2
0.0 0.0
Fig. 2.
0.8
0.2
0.4
e
0.6
08
0.0
1.o
Fused correct, incorrect and nondecision rates versus individual sensor efficiency.
q1 = (1 - e)'/(m - 1) I 1 7-1 = (1 - e ) [ m ( l + e ) - 2 ] / ( m- 1) < 1.
(42) (43)
U
-
0.8
7
Differentiating
TI
with respect to e, we get
Q
0.6
d r l / d e = 2(1 - m e ) / ( m - 1).
(44)
-E ny
Setting the derivative to zero, the nondecision rate attains an extremum value at e = I/m.
(45)
Differentiating (44), the second derivative of r1 is a negative value independent of e and thus the extremum reached is a maximum. Substituting (45) in (43) the maximum value of T I is Tllmax
= ( m- l ) / m
(46)
attained at e = l / m . As m, the number of decision choices, increases the maximum value of T I , i.e., the maximum initial nondecision rate, increases and asymptotically approaches 1. This is because the error rate decreases with increase in the number of decision choices and with the correct decision rate remaining constant, the nondecision rate increases with m as the sum of these rates is always unity by definition. Further, for m = 2 under the subcase A3, (41) through (43) reduce to PI
= p l = e'
Q I = 41 = (1 - e)' r1 =
2e(l -e).
(47) (48) (49)
Fig. 2 shows the plot of p l , q 1 , and rlversus e. As e increases, p1 increases, 41 decreases, and 7-1 first increases and then decreases. As expected from the previous analysis, r1 peaks at e = l / m = 0.5 with a value of ( m - l ) / m = 0.5 for the case m = 2 . Fig. 3 shows the plot of the asymptotic values Pk 1 max and Qk 1 max (obtained by substituting (47) and (48) in (20) and (21)) versus e for this same case (the sum of the two is always unity as T k reaches zero asymptotically). The crossover point of the recognition and misrecognition rates is at e = 0.5 for m = 2 . The initial and the final (asymptotic) fused correct decision rates are shown superimposed
0.4
X
0.2
_ _0.0
nn
0 2
0 6
0 4
08
1 0
e
Fig. 4.
Initial and final fused decision rates versus individual sensor efficiency levels.
in Fig. 4 to bring out the effective benefits of the recursive process, Fig. 5(a) shows the progressive improvement in performance of with increasing values of k . It can be seen from this illustration that as early as the end of three recursions ( k = 4) the performance reaches close to asymptotic levels. Given the fact that the summed correct decision rate increases as the recursive process continues, it would be interesting to determine if this summed rate ever exceeds the initial individual sensor correct decision rate e. This corresponds to a 45 degree line through the origin in Figs. 3 and 5(a), i.e., this event can occur only for e > 0.5 ( l / m ) . (This is based on the assumption of zero nondecision rate for the individual sensor. Otherwise, the results are correspondingly different). Fig. 5(b) shows an alternative portrayal of the dependence of the fused decision rate Pk on k at different values of e. These would be of value in determining an optimal number of recursions for the process. Using (16) and (41) the condition when PI,exceeds e (although the general case itself can be analyzed, the special case of equally efficient sensors is considered here for simplicity of expressions derived by the analysis) can be written as
i.e.,
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS, VOL. 21, NO. 5, SEPTEMBER‘OCTOBER 1991
1146
10
-
-
1 .o
0.8
k=l
k=2 0.6
k=3
-
nr
e=0.2
e=0.3
e = 0.4 e=0.5
I e=0.6
04
P
e=0.7
e=0.8
02
0.0
00
U0
0 2
0 6
0 4
0 8
1 0
e
Fig. 5.
k
(a) Fused correct decision rate versus sensor efficiency at different stages of the recursion process. (b) Fused correct decision rate versus recursion number at different sensor efficiency rates.
Equation (51) can be rewritten using (43) (since
TI
< 1) as
IC 2 ln[(l - e)(me - l)/e(m - I)]
/ ln[(l - e)(m + me - 2)/(m - l)]
(52)
Thus, (52) (with e > l/m) gives the minimum number of recursions needed for the fused decision to be better than the decision of the individual sensor. Deriving the limiting values for Pk and Qk through substitution of (41) and (42) in (20) and (21)
Pk1 max = ( m - I)e2/(me2- 2e + I)
Q~I max = (1 - e)’/(me2
-
2e
+ 1)
(53) (54)
Fig. 6 shows a plot of this asymptotic correct fused decision rate as a function of the individual sensor efficiency e for different values of the number of decision choices m (target classes). As m increases, the system performance improves because the likelihood of fused incorrect decision rate drops off. For (53) to reach a value greater than e, it can be shown that (1 - e)(me - 1) > 0
(55)
i.e., l/m
< e < 1.
Substituting (41) and (42) in (57) and solving for e in terms of m gives elminas
(56)
This is also the range in which (52) leads to a positive value for k . These lower and upper bounds are consistent with the physical facts of the multisensor environment under consideration. The individual sensor correct decision rate has to be better than the success rate ( l / m ) obtainable under a purely random decision process with m decision choices. On the other hand, perfect sensors (e = 1) would obviate the need for the recursive process. The min value of e at which the correct fused decision rate Pk would exceed the incorrect fused decision rate Qk can be found (by comparing (16) and (17)) to be
Fig. 7 shows a plot of this minimum value of e (for which the correct fused decision rate would equal or exceed the incorrect fused decision rate) versus m. This once again is valid under the assumption of zero nondecision rate for the individual sensor. It also provides for comparison purposes the trend of e = l / m , the random-choice correct decision rate, at which the nondecision rate attains its maximum. At m = 2, the two values of e are equal. However, as m increases, the minimum value of e (for equal correct and incorrect fused decision rates) decreases but at a much slower pace than the correct decision rate obtained under random assignment. Substitution of this minimum value of e in (41)-(43) gives
+ 2(m - 1 p 2 ] TI = [(m- 2) + 2(m - l)”’]l/[m + 2(m - 1)’/2].
p1 = 41 = l / [ m
(59) (60)
For this value of e, as m increases both pl and 41 decrease and hence TI increases since from (1) their sum is always unity. Substitution of this minimum value of e (for which pk is equal to Qk for all values of k ) from (58) in (53) and (54) leads to the limiting values of both pk and & k as 1/2 which agrees perfectly with results derivable directly by setting (20) equal to (21) and using (22). General Case A4: Relaxing the assumption of equally efficient sensors, let
where a(5 1) is the ratio of the efficiency of the less perfect sensor to that of the better one. The case a = 1 represents the equally efficient sensors scenario discussed earlier (Subcase A3). Expressions (24) through (26) can be rewritten using
DASARATHY: DECISION FUSION STRATEGIES
1147
-
-
m=3 m=4
m=5 m=6
I m=7
m=E
0 0
0 2
0 6
0 4
0 8
1 0
Fig. 6. Asymptotic fused correct decision rate versus sensor efficiency for different number of decision choices.
rate, we can write using (63) and (64) in (20) and (21), as
2 (1 - e ) / e [ l + ( m - 2)eI.
(67)
amin
Since a 5 1 by definition, we can derive from (67) the condition
2
4
6
E
10
m Minimum required sensor efficiency versus number of decision choices.
Fig. 7.
(61) and (62) as
amin2 (1 - e)/.;
p l = ae2 5 1
51 m a e 2 ] / ( m - 1)
q1 = (1 - e ) ( l - ae)/(m- 1) TI
= [ ( m- 2 )
Equations (67) and (68) together represent the conditions for asymptotic fused recognition rate to be greater than the corresponding misrecognition rate. It is to be noted here that (68) is the same as the one obtained earlier for the special case of equally efficient sensors. This effectively supports the intuitive reasoning that the system performs optimally when both the sensors are equally efficient, i.e., a = 1. For the special case of m = 2 , i.e., for example, the detection problem, this condition reduces to
+ (1 + a ) e
-
/ ( m- ~
5
) ( ~ - l )1
(121)
j=1
The summed correct decision rate Pk can be derived and evaluated for the threshold at which it exceeds the individual rate e as Pk = e 2 ( 3- 2 e ) ( 1 - r;)/(l-
TI)
>e
(116)
from which an expression for IC can be derived in terms of e and m similar to (94). For m = 2 under the subcase B2d, the expressions (109) through (111) reduce to p l = e2(3 - 2e) 41 = T1
I -3 2
= 0.
+ 2e3
and T I is given by (19). As before, we consider some special subcases here also. Subcase C l -e, = 1 (1 5 i 5 t ) )The scenario of at least one perfect sensor under consensus leads to
(117) (118) (119)
which, when substituted into (20), leads to the conclusion that asymptotically the multisensor system performance reaches perfection as long as one sensor-processor pair in the system keeps deriving the correct decision (this is limited to the consensus strategy only). This demonstrates the benefits of the multisensor fusion process.
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS, VOL. 21, NO. 5, SEPTEMBEWOCTOBER 1991
1152
-
1 .o
0.8
-----b
I
0.6
X
E
v
e=02 e=03 e=04 e=o5 e=06
0.4 e=07 e=08
0.2
0.0 1
2
3
t
5
6
Fig. 14. Asymptotic fused decision efficiency versus number of sensor at different sensors efficiencies.
Subcase C2-e, = 0 (1 5 i 5 t ) ) The scenario of one totally faulty (wrong decision always!) sensor leads once again to the fusion process failure under the consensus strategy irrespective of the other sensors. If one of the other remaining sensors is perfect, this makes a consensus impossible and hence the nondecision rate reaches unity while both recognition and misrecognition rate become zero. This is strictly a result of the consensus strategy and hence is one of its main detractions requiring constant monitoring of sensors. A majority (or s out of t sensors) strategy would be beneficial under these circumstances. Subcase C3-ei = e (V i : i = 1 , .. . , t ) )For this case of equally imperfect sensors, the expressions (11l), (1 12), and (19) reduce to pl q1
r1
=et = (1 - e ) ' / ( m - I ) ( ~ - ' ) = 1 - et - ( 1 - e)'/(m - l)(t-l).
Differentiation of
7-1
(123) (124) (125)
As is to be expected, expression (128) reduces to (52) and (94) for t = 2 and t = 3 respectively. Again, the min value of e at which the correct fused decision rate exceeds the incorrect fused decision rate is determined (substituting (122) and (123) in (57)) as (130) As can easily be verified, (129) reduces to (58) and (95) for t = 2 and t = 3 respectively. As t increases, the minimum value of e tends closer and closer to l / m , the random-choice based correct decision rate. The gap between the two curves shown in Fig. 7 for t = 2 becomes smaller with increasing t values. This means that as more sensors are added to the decision process, less accurate they need to be for the correct fused decision rate to be better than incorrect fused decision rate. Substitution of this minimum value of e in (122) and (123) leads to
in (124) with respect to e gives
drl/de = -te(t-l)
+ t(1 - e ) ( t - l ) / ( m- l)(t-').
(126)
Setting (125) to zero gives the same value for extremum point as before: e = l / m . Substitution of this value of e in (124), after some algebraic simplification, gives
It is easy to check that for t = 2 and t = 3 , (126) reduces to (46) and (88) respectively thus confirming the analysis. As m, the number of decision choices, increases, the maximum value of the nonrecognition rate given by (126) approaches unity asymptotically but this maximum value occurs at lower and lower values of e approaching a value zero asymptotically. The summed correct decision rate can be derived as before and compared to the individual rate e as
As before increasing values of m decrease both p l and 41. Also increasing values of t decrease both p l and 41 at the minimum value of e. Instead of determining the minimum value of e at which the correct fused decision rate exceeds the incorrect fused decision rate, one could determine the minimum number of sensors required for this scenario to be true. This can be accomplished by again substituting (122) and (123) in (57) and solving for t (instead of e ) as
tlmin2 ln[m - 1]/1n[(m- l ) e / ( l - e ) ] ; m>2;
O
Comments
Report "Decision fusion strategies in multisensor environments "