Detection with Distributed Sensors-L0s.pdf

I. Introduction

Detection With

Distributed Sensors

In recent years there has been an increasing in-

\ terest in distributed sensor systems. This interest has

been sparked by the requirements of military sur-

veillance systems [1] and is reflected in the widespread

use of such terms as data fusion, correlation, and

multisensor integration.

The classical theory of optimal sensor signal pro-

cessing is based on statistical estimation and hy-

pothesis testing methods [2]. The motivation for this

theory has been the optimal detection and tracking of

targets using a single sensor such as a radar or sonar.

Thus all the sensor signals are implicitly assumed to

be available in one place for processing.

The situation is substantially more complicated in

the case of a distributed sensor network. If it were

possible to transmit all sensor signals to some central

location with negligible delay, then the classical theory

is in principle applicable, even though there may be a

myriad of interesting problems associated with the

disparate nature of the information sources.1

However, because of such considerations as cost,

reliability, survivability, communication bandwidth,

compartment-alization, sensors on platforms under

emission control, or even simply the problem of

flooding the fusion center with more information than

it can process, there is never total centralization of in-

formation in practice. Thus extensions are needed to

the classical framework of detection theory if it is to

be relevant to the design of distributed surveillance

systems. This paper attempts a modest step in the

direction of a detection theory for distributed sensors

by considering decentralized hypothesis testing.

While hypothesis testing is a well understood tech-

nique, its extension to a decentralized formulation

yields behavior more complex than might be initially

expected. In the case of total decentralization (Fig. 1),

one would expect each detector to operate indepen-

dently and base its decision on the familiar likelihood

ratio test. While this is true in special cases, it is un-

true in general. When the detectors choose their deci-

sions to achieve a system-wide optimization, they

often use different strategies than in cases where the

joint cost associated with their decisions separates into

a cost for each.

The problem of constructing decentralized hypo-

thesis testing rules can be viewed in the framework of

decentralized optimal control theory.2 Unlike most

decentralized control problems, the hypothesis testing

problem can be solved in a relatively straightforward

way. This is due principally to the fact that the deci-

sions made do not feed back into the system dynamics

ROBERT R. TENNEY, Member, IEEE

NILS R. SANDELL, JR., Member, IEEE

Abstract

The extension of classical detection theory to the case of distributed

sensors is discussed, based on the theory of statistical hypothesis

testing. The development is based on the formulation of a decen-

tralized or team hypothesis testing problem. Theoretical results con-

cerning the form of the optimal decision rule, examples, application

to data fusion, and open problems are presented.

Manuscript received November 13, 1979; revised September 25,

1980, and January 15, 1981.

This work was supported in part by a National Science Foundation

graduate fellowship and in part by the Office of Naval Research

under Contract N00014-77-C0532.

Authors' addresses: R. Tenney, Massachusetts Institute of

Technology, Laboratory for Information and Decision Systems,

Room 35-213, 77 Massachusetts Ave., Cambridge, MA 02139; N.R.

Sandell, Jr., Massachusetts Institute of Technology, Department of

Electrical Engineering and Computer Science, Cambridge, MA

02139.

'For example it may be necessary to correlate a radar return

with a report from a Naval attache.

0018-9251/81/0700-0501 $00.75 1981 IEEE

2See [3] for a survey with 156 references.

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. AES-17, NO.4 JULY 1981

501

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 10,2010 AT 19:09:07 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

show that the general theory developed for the decen-

tralized hypothesis testing problem of Fig. 1 can be

applied to the situation of Fig. 2 using an appropriate

definition of the cost function. Thus the performance

of the distributed detection system can be quan-

titatively compared with that of the centralized system

to evaluate the performance versus the communica-

tions tradeoff.

DECISION

II. Decentralized Hypothesis Testing

Fig. 1. Decentralized detection.

For the structure of Fig. 1, the problem of decen-

tralized (binary) hypothesis testing can be posed in its

most general form as follows. The two hypotheses are

HI or H', with a priori probabilities

Fig. 2. Fusion.

p(H0) = p° p(H') = p'.

(1)

For each hypothesis the sensor observations have

known joint probability distributions

Local Decision 2

P (Yl , Y2 HO); p (yl , y2 HI). (2)

(The subscripts indicate the sensor location to which a

variable is associated; we will consider only the case

of two locations.) The yi are random vectors resulting

from preprocessing of the original sensor signals.

The crux of the distributed hypothesis testing pro-

blem is to derive decision rules of the form

0, H0 is declared to have been detected

ui =

and thus affect the information of other decision

makers. For example, we will be able to prove that in

the important special case where signals are indepen-

dent when conditioned on the hypotheses, each detec-

tor uses an independent, local likelihood ratio test,

but with thresholds determined via a coupled com-

putation. The computation of thresholds decouples

only in those special cases where the payoff function

separates.

However, even in the case of independent observa-

tions, several types of unusual behavior can occur.

The threshold computations can yield locally optimal

thresholds which are far from the globally optimal

values. Moreover, even when identical sensors and a

symmetric cost function are considered, the optimal

thresholds need not be equal; the two detectors must

hedge their decisions in nonidentical ways.

As described above, the motivation for this study

is for distributed systems in which data is being

generated at geographically dispersed sensors, and

local processing is to be used to reduce the com-

munications bandwidth required between the sensor

stations and a fusion center (Fig. 2). The performance

of such a system is suboptimal in comparison with a

completely centralized processing scheme due to the

loss of information in the local processes. We will

1, HI is declared to have been detected

where ui depends only on the observation yi. The

decision rule can be defined by the conditional pro-

bability distribution function

p(ui = Olyi)

which defines a randomized decision rule.

The optimality criterion will be a function

J: {O, 1} x (0, 1} x {H0,HI} - IR (3)

with J(u1, u2, Hi) being the cost incurred for detector

J(0, 0, H0) = J(1A 1, HI) = 0

J(0, 1, H) = J(1, 0, H1) = J(O, 1, H1)

= J(AI 0, IH) = 1

J(O,0,H') = J(1, 1,1H0) = 2.

(4)

502

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. AES-17, NO.4 JULY 1981

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 10,2010 AT 19:09:07 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

1 choosing u1, and detector 2 choosing u2, when Hi is

true.

For example, the minimum error cost function Jm

This function is separable,

Jm(u,, U2, Hi) = J,(u,, H') + J2(U2, H9) (5)

observations (y1, Y2) for each hypothesis (or eqUivalently,

the ratio ofaposteriori likelihood of the hypotheses given

the observations) and t is a precomputed threshold; and

c) the threshold

where

t = [J(O, H1) - J(l, Hl)]/[J(1, HO) - J(O, H0)]

(1 1)

JO u= =O,H=H°oruj =1,H=IP

1, else

A u

provided

(6)

J(1, H0) > J(O, H0).

is the usual minimum probability of error cost func-

tion associated with detector j.

The objective of the decision strategy will be to

minimize the expected penalty incurred

The decentralized solution can be derived in a

manner parallel to that used in the centralized case.

Begin by expanding (7) explicitly; the function to be

minimized is

E f p(Ul,u2y1,Y2,H)J(ul,U2,H)

min E [J(u,, uL, H]

(7)

HUI,U2 Ynx

= - f P(H)p(Y,Y2 H)p(Ully,)p(u2ly2)

where the minization is over the (randomized) decision

rules of each detector.

In summary we have the following.

Problem (Decentralized Binary Hypothesis

Testing): Given p°, pI, the distribution p(y1, Y2 Hi), i

= 0, 1, and the cost function J, find the decision

strategies for each detector (expressed as functions

p(ui yi) of the corresponding observation only)

which minimize the expected cost.

The familiar centralized case is similar, but with a

crucial difference:

Problem (Centralized Binary Hypothesis Testing):

Given pO, pI, the distributions p(yI, y2 H%), i = 0, 1,

H,uI,U2 Y1t2

* J(u,u2,H)

(12)

by invoking appropriate independence assumptions.

Explicitly summing over u, gives

If p(H)P(u2lY2)P(Yl,Y21H) (P(Ul = OjyJ)

*J(O,u2,H) + (1 - p(U, = OJY1)) J(1,u2,H)] (13)

and the cost function J, find the decision strategy (ex-

pressed as a functionp(u y,, Y2) of both observations)

which minimizes the expected cost.

The solution of the centralized problem is, of course,

well known.

Theorem 1: The solution to the centralized binary

hypothesis testing problem is a) deterministic, so that the

decision rule is a function

One obtains the following equivalent function to

minimize by ignoring a constant term:

f P(U1 = O1YO) 72 fP(H) P(t2lY2)P(yl, y21 H)

[J(O, u2,I) - J(1, u2, H)].

(14)

This is minimized by choosing

P(u, = Ojy,) =

0, if I- f P(H) p(u2Iy2) P(Yl,Y21H)

y: Y1 x Y2 1{0, 1}

(8)

with u = i interpreted as choosing Hi; b) a likelihood

ratio test

H, u2 Y2

[J(O, U2,H) - HI1, U2,H)] > 0

Y*(Yl,Y2) =

0, if lr(y1,y2) > t

1i, else.

1, if lr(yl,Y2) < t

(9)

(15)

where

Ir (Y1, Y2) = [P(Yi, Y2 H0) Po]/[P(Yl, Y2 I H') p'l

= p(Ho YI, Y2)/P(H' Y1, Y2)

Notice that, regardless of the forms of p(y,, Y2 H),

J, orp(u2jY2),

p(U, = Ojyi) E (0, 1}

(10)

so we have

Lemma 1: The decision rule used by each detector

is the ratio of the a priori likelihood of the received

TENNEY/SANDELL: DETECTION WITH DISTRIBUTED SENSORS

503

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 10,2010 AT 19:09:07 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

H, U2 Y 1 V2

is deterministic and can be expressed as a function yi:

Yi -- {0, I } define

and its companion form (for the rule for u2) would in-

volve solving for the entire functions yi (.) and Y2 (-)

through the coupled equations. Thus the optimal solu-

tion is not a likelihood ratio test in general.3

Fortunately matters simplify greatly if we make

assumption 2.

Assumption 2: The observations yl and Y2 are

statistically independent:

P(Y2 IY1, H) = p(y21H)

P(YlIY2, H) = p(y, IH).

if P(Uj = °Iy') = 1

else.

This gives the decision rule for detector 1 as

I f p(H) p(y1, Y21 H) p(u2 IY2) [J(O,U2,H)

- J(1,u2,H) 1>0

(17)

(20)

where the notation

This assumption is appropriate for the "known signal

in noise" case characteristic of most radar problems.

It is inappropriate for the "unknown signal in noise"

case that arises in sonar problems, for example.

Assumption 2 removes the dependence of the right-

hand side of (19) on yi, so it becomes

Aix) <O y

indicates

Ut = 1,

choose either,

U, = 0,

iff(x) >y

if f (x) = y

if (x) < y.

Ir (yi) >1 fl(Y2 ( )^tl

which indicates that the likelihood ratio for Yi is com-

pared with a constant threshold t,, which can be com-

puted as a function f, of the decision rule Y2 (') for u2

[expressed as p(u2 1Y2)]. Thus we have the following

lemma.

Lemma 2: Assumptions I and 2 imply that the

solution to the decentralized hypothesis testing pro-

blem has each detector implementing a likelihood

ratio test, using a threshold derivable from the deci-

8) sion rule ofthe other detector.

The final step towards solution of this problem is

taken by noticing that the decision function yi (-) is

characterized by the threshold ti and the likelihood

ratio. For example, knowing t2 one can find

P(U, = oly', = 37 f p (y2l H)p(H)

Expanding the sum over H,

U2 Y2

- J(1, U2,H0)] > f p(HI)

<0 u2 Y2

* P(YV,Y2IH1) P(U2IY2) [J(0, U2JHA)]

- J(1, U2, HI)].

(1v

By making the assumption 1, (20) becomes

[P0P(Y11 H )]/[P1P(Y11HI)]><O{EJ P(Y2 1Y1J

* P(U2IY2) [J(O, U2,H1) - J(1,U2,)I)]I}/{I U2

* f P(Y21y1,HO)P(U2IY2) VJ(1, U2,H°)

H Y2:lr{y2)>t2

and thus

- J(, U2,H°)]}

(19) t, = f P(YyHII) {[J(O,1,II) - J(A,1,IP)]

Assumption 1: J(1, u2, H°) > J(O, u2, H°), or it is

more costly for detector 1 to err than for it to be cor-

rect when H° occurs, regardless of the decision of

detector 2.

The form of the decision rule expressed in (19) is

interesting as the left-hand side is the likelihood ratio

for Yi. However the right-hand side is not a simple

threshold constant due to the existence of the condi-

tional density p(y2 Lyi, Hi), and it requires knowledge

of the entire decision function for u2, namely, p(u2L2)

[or equivalently y2 (yv2)] in order to be evaluated. This

causes significant difficulty, as any solution of (19)

+ P(u2 = 0°Y2) [J(O,0,H') - J(1,OH,I)

- J(0,1,IH) + J(A,l,H)]}/

(21)

rJP(Y2 l1Ho) {[J(1,1,Ho) - J(0,1,H°)]

+ p(u2=0Oy2) [J(1,0,H°) - J(0,0,H°)

- J(l,1,1H°) + J(0,1,IH°)]} =fi(t1) (22)

30r equivalently, the optimal solution is a likelihood ratio test

but with a data dependent threshold.

504

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. AES-17, NO.4 JULY 1981

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 10,2010 AT 19:09:07 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

u2,H Y2

I f p(H0) p(y1,Y21 HO) P(U2 IY2) [J(O, U2,H0)J

(19) ~~l =

Equation (22) and its companion

i = ai' + 0 5 a>O, PER

(26)

t2 = f ) (t)

(23) which do not affect the solution, to

provide simultaneous equations, not for the solution

for the functions y, (.), but for the parameters t, and

t2 which characterize them.

It is important to note that (22) and (23) are

necessary conditions which must be satisfied if a pair

(t,, t2) is to be an optimal solution to this problem,

but are not sufficient. They define locally optimal

solutions in that no threshold can be changed

unilaterally to improve the solution. There may be

several local minima; each must be checked to assure

that the global minimum is found.

The foregoing development can be summarized by

the following theorem.

J(O, 0, HI) = J(1, 1, HI) = 0 (O errors)

J(O, 1, H") = J(l, 0, H0) = J(O, 1, H) = 1(1, 0, H')

= 1 (1 error)

J(l, 1, 10) = J(O, 0, HI) = k (2 errors).

(27)

Notice that, when k = 2, this becomes the minimum

error cost function JmP Also, assumption 1 of

Theorem 2 requires

J(1, 0, H0) > J(0, 0, If)

Theorem 2: The solution to the decentralized

binary hypothesis testing problem is a) deterministic

(Lemma 1)

J(1, 1,R 0)>J(0, 1,I ) (28)

the latter of which requires k > 1. This means simply

that double errors are penalized at least as much as

single errors.

Substituting this cost function into (21), the equa-

tion for t,, yields

yi: Yl {0, 1}; Y2: Y2 -' {O, 1}

b) a likelihood ratio test for each detector;

if Ir, (yi) > t,

tl = fP(Y2 H) [1 + (k - 2)p(u2 = 0 Y2YI/

(24)

Y*~(yi) =

if Iri (yi) < ti

.fp(y2 IF) [(k 1) (k

with lri (ye) = pop(y1I H')/p1p(y,I HI) (Lemma 2), pro-

vided assumptions I and 2 hold; and c) the thresholds

t1 and t2 satisfy

= 0 y2)J (29)

from which Theorem 3 can be immediately deducted.

tl= f (ti2); t2 = f (ti)

(25)

Theorem 3: If J = Jm, then for any observation

distributions p (yi Hi), the threshold computations

decouple and yield the thresholds which result from

each detector using the optimal centralized minimum

error decision rule.

Proof: If J = Jm, then the coefficient ofp(u2 = 01

y2) in (27) goes to zero, eliminating the dependence of

t1 on y, (-). This produces t, = t2 = 1 as the solution,

which is also the solution for each detector using the

cost function Ji (ui, H) defined in (6).

The importance of this theorem is that Jm is a

rather special case; in general the computations do not

decouple.

For the class of cost functions introduced above, it

would be expected that as k decreases from 2 to 1, the

thresholds would change in a way which increases the

probability of error, as double errors are discounted

relative to single ones. As k increases from 2, double

errors become prohibitively expensive, so it is to be

expected that some mechanism will emerge to reduce

their likelihood.. Thus in the following, the limiting

cases k = 1 and k = X are of special interest.

wheref' is given in (21) andfisasymmetricform

obtained by interchanging the roles of y, and y2 and

of u1 and U2.

Note the similarities of Theorems 1 and 2. The key

difference is that in the centralized case a single deci-

sion is made, and it is based on both observations. In

the decentralized case two decisions are made, each

based on only one observation. It is important to em-

phasize that the decentralized decision rules are not in

general the same as those that would be derived using

classical theory independently for each detector. The

computation of thresholds couples the choice of local

decision rules so that system-wide performance is op-

timized, rather than the performance of each in-

dividual detector. There is a case, however, in which

the detectors can be treated separately.

Begin by defining the cost function j to be sym-

metric in u, and u, and to penalize all cases of n er-

rors, n = 0, 1, 2, by the same amount. Any such

function can be reduced, using affine transformations

TENNEY/SANDELL: DETECTION WITH DISTRIBUTED SENSORS

505

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 10,2010 AT 19:09:07 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: