Citation
Detection of change in acting stochastic processes with respect to fusion center structure

Material Information

Title:
Detection of change in acting stochastic processes with respect to fusion center structure
Creator:
Rao, Savitha
Publication Date:
Language:
English
Physical Description:
v, 74 leaves : illustrations ; 28 cm

Subjects

Subjects / Keywords:
Stochastic processes ( lcsh )
Stochastic processes ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 73-74).
General Note:
Department of Electrical Engineering
Statement of Responsibility:
by Savitha Rao.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
166253830 ( OCLC )
ocn166253830
Classification:
LD1193.E54 2006m R36 ( lcc )

Full Text

DETECTION OF CHANGE IN ACTING STOCHASTIC PROCESSES WITH
RESPECT TO FUSION CENTER STRUCTURE
B. S., University of Mysore. 2001
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Electrical Engineering
By
Savitha Rao
2006


This thesis for the Master of Science
Degree by
Savitha Rao
has been approved
By
A
Dr. Titsa Papantoni
Date


Rao, Savitha (Master of Science, Electrical Engineering)
Detection Of Change In Acting Stochastic Processes With Respect To Fusion Center
Structure
Thesis directed by Professor Titsa Papantoni.
ABSTRACT
The performance analysis of the distributed detection algorithm for a fusion center
model with feedback is considered. The performance analysis is carried out to check
the reliability of the process detection by the fusion center. The fusion center model is
a distributed structure where the fusion center is connected to the locally distributed
sensors. Sensors are distributed in the identical stochastic environment. The
physically distributed sensors in the fusion center model collect the local data and
send sensors decisions to the fusion center. The fusion center collects the decisions
from all the sensors and decides the occurrence of //, > nj shift, where
= 1,2..., m -1 are the stochastic processes. Based on the results of the fusion
center decision, the average time T[ and the probability r'kn statistics are plotted to
study the performance of the distributed detection algorithm for the fusion center
model.
Approved By:
Dr. Titsa Papantoni


TABLE OF CONTENTS
List of Figures.........................................................................v
1. Introduction........................................................................1
2. Algorithms for Detecting Changes in Acting Stochastic Processes....................3
2.1 Introduction:......................................................................3
2.2 One-Sided Process Inspection Scheme................................................3
2.3 Stopping Algorithm:................................................................6
2.4 An Algorithm for detecting a change:...............................................9
2.5 Extension of the Algorithm to Detect Change.......................................11
3. Distributed Detection..............................................................14
3.1 Introduction......................................................................14
3.2 Distributed Detection System with Bayesian Performance Criterion..................14
3.3 Distributed Detection System with Neyman-Pearson Performance Criterion............18
3.4 Distributed Detection System with Feedback........................................19
4. Detection Algorithm for Fusion Center Distributed Structure.......................23
4.1 Introduction:.....................................................................23
4.2 Fusion Center Structure:..........................................................23
4.3 The Algorithmic System............................................................24
5. Simulation........................................................................30
5.1 Introduction......................................................................30
5.3 MATLAB Simulation.................................................................33
5.4 Flow Diagram for Fusion Center Simulation.........................................37
5.5 Numerical Results.................................................................44
6. Conclusion........................................................................50
Appendix
7.1 MATLAB Program....................................................................51
7.1.1 MATLAB program to calculate False Alarm probability.............................51
7.1.2 MATLAB program to calculate Power probability...................................52
7.2 C++ Simulation Program..........................................................54
References
73


List of Figures
3.1 Decision Fusion with feedback
5.1 Alpha and beta plot for threshold = 3.07
5.2 Alpha and beta plot for threshold = 3.5
5.3 Alpha and beta plot for threshold = 3.92
5.4 Fusion center structure from simulation point of view
5.5 Message flow diagram when fusion center sends stop signal
5.6 Message flow diagram when sensors stop and wait for fusion center to stop
5.7 Plot of average time Tk for different thresholds
5.8 Plot of probability for different thresholds
5.9 Plot of correct decision Tlk verses wrong decision Tlk
5.10 Plot of correct decision r^ verses wrong decision
v


1. Introduction
This chapter gives a brief over view of a Distributed Detection Problem
implemented by a Fusion Center architecture. With increasing interest in science
and technology, there is always demand for fast responding, survivable and
reliable systems. In the field of computers, new faster computers constantly arise,
facilitating ever increasing reliability and speed in data transfer. In parallel, the
distributed data is frequently imposed by the constraints of the environment, while
distributed data processing increases system reliability. In this thesis, a distributed
scheme for detecting a change in the data environment is presented and discussed.
The Distributed Detection Problem discussed here collects the data from
physically distributed locations. At each location, a sensor processes local data
together with feedback from the central processor, called Fusion Center. Each
local sensor sends its decision to the Fusion Center. The Fusion Center collects all
the decisions from all the sensors and makes the final decision. The alternative to
this distributed detection scheme is the optimal centralized scheme. In the optimal
centralized scheme, the data are collected from physically distributed locations
and are then sent to a central processor for processing. Since the raw data are
transmitted to the central processor, the communication cost may be unreasonably
high. In addition, the centralized system is vulnerable, while the distributed
system induces increased survivability. With respect to reliability issues, the
centralized decision scheme is influenced profoundly by a single data outlier,
while the influence of data outliers is further defused in the distributed
architecture environment.
The concept discussed above can be better understood with few real life
examples. First, consider military surveillance. When a target is initially detected,
its adversarial nature has to be confirmed before it is hit. Confirmation requires a
reliable system. If data outliers are suppressed by a robust decision algorithm, then
1


the centralized detection scheme may be used to detect the target with high
confidence. But the central processor involved is then highly vulnerable. Increased
sensor survivability suggests transition to a distributed detection scheme, which is
implemented by geographically distributed sensors. Secondly, consider the
example of quality assurance. In an ongoing series production there may be some
quality metrics that may be temporarily violated, with no global effect to the over
all production. Stopping the production as a result of such temporal violations
may be very costly. Hence, the process which detects persisting quality violations
must be designed carefully. The detection process should be reliable with fast
response time, pointing to the selection of a high performance distributed
detection scheme.
The focus of the thesis is the discussion of a distributed detection scheme
with feedback using a Fusion Center architecture. The algorithm used to detect the
change of data process per sensor is discussed in chapter-2; the Distributed
Detection Scheme is discussed in chapter-3; the Distributed Detection Scheme
with feedback using a Fusion Center is discussed in Ch-4; the results for the later
architecture are presented in chapter-5. In chapter-6, conclusions are presented.
The references are given in the Appendix.
2


2. Algorithms for Detecting Changes in Acting Stochastic
Processes
2.1 Introduction:
The main purpose of this chapter is to discuss the background of the problem of
Detecting a Change in the acting Stochastic Process using a Fusion Center
Structure. Five different journal papers concerned with the detection of a change
in stochastic process are referred to in the discussion. The authors of the papers
(under consideration) are Page [1] [2], Lorden [3], Bansal and Papantoni-Kazakos
[4], and Burrell and Papantoni-Kazakos [5]. Page and Lorden have addressed the
problem considering memoryless processes, while Bansal and Papantoni-Kazakos
have addressed the problem for processes with memory. Burrell and Papantoni-
Kazakos extended the latter work to include reoccurrences and reinitialization. A
brief summary of the above papers is given below. The concept of Detecting a
Change in Stochastic Process is further extended to include a Fusion Center
model in chapter 4.
2.2 One-Sided Process Inspection Scheme
A One-sided process inspection scheme is a type of continuous inspection scheme
A One-sided test detects the change in only one direction, i.e; the value of the test
can be checked for values either above a single threshold or below this threshold.
A One-sided process inspection scheme was first suggested by Page.
The problem of interest is to detect a change in a parameter 0. The data are tested
continuously for the parameter change, and action is taken when the change in
parameter is detected. For example, consider the production of shafts for motors,
which are tested for their length. For every 50 pieces of shaft produced, 20 pieces
3


of shaft are tested at random for the length increase. If the increase in length is
detected, then the production of shaft is stopped and appropriate action is taken.
The scheme used to detect a change is a control chart scheme, where the statistics
of the output samples are plotted on a control chart. The action is taken if the
output falls outside the control limit in a control chart at any point of time.
Therefore the action taken depends on the definition of Average Run Length,
which is defined as When the quality remains constant the Average Run Length
(A.R.L) of a process inspection scheme is the expected number of articles
sampled before action is taken (Page [1]). Since the control chart scheme uses
only part of the data for detecting a change, there could be problems with
efficiency of the result and the optimality of the detection. Hence a scheme which
uses all the observed data is considered for detecting a change in parameter; such
schemes include a One-Sided Scheme.
The process inspection schemes that are designed to detect deviations in 0 in only
one direction will be called a One-Sided Scheme. (Page [1]) Under a One-Sided
Scheme there are two other schemes: Transition Scheme and Sequential Scheme.
In Transition Scheme, samples of the observations are collected and, after each
sample is collected, they are checked to make the decision. The decision is made
based on the plot of the cumulative sum of the sample scores. The graph is
downward if the quality is satisfactory, and the graph is upward if the quality is
poor. A similar criterion for controlling the parameter of other distributions when
deviations in only one direction are important is provided by the following rule:
Rule 1: Take samples of fixed size n at regular intervals; assign a score to the
n
kh sample and plot the cumulative score Sn = ^ jt* on a chart:
*=i
Take action if 5 min S, >h (Page [1]) (2.1)
0 4


In Sequential Scheme, all the observations are considered for decision-making.
After each observation is recorded, observations are checked and the decision is
made. The rule for the Sequential Scheme is derived by modifying Rule 1.
Rule 2: Take observations at regular intervals; assign a score Xk to the kth
n
observation and plot the cumulative score S = ^ xk on a chart:
*=i
Take action if S min S, >h (Page [1]) (2.1)
0 These Rules 1 and 2 can be used when the change in parameter has to be detected.
When the condition in (2.1) is satisfied the process stops and the action is taken to
rectify the defect in the process.
Page [1 ] presented one more paper to test the change in parameter, based on
Rule2. As seen in Rule2 Xk is the score of the k01 observation. In the present paper
of Page [2], these observations are from the same hypothesis or from different
hypotheses, which means that there are two distributions: F(x|0) and F(x|0 ). The
observations will be from F(x|0) initially, and at some point of time the
observations will be generated from F(x|0 ). The objective of the paper is to find
the point at which the distribution changes from F(x|0) to F(x|0 ).
The scheme for detecting a change from one process to another process is as in
Rule2. It is assumed that 0 is known and the point m at which the process
changes, is to be detected. The change is detected and action is taken if (2.1) is
satisfied. The test to detect a change is then:
Test 1: Given the observations xi, \2,......, xn. It is required to test the
hypothesis that the mean is constantly 0. Use as the test statistics
r
m max{Sr min .S.} where S = V (x, 0), So = 0,
(KrSn 0 J= 1
taking large values as significant, i.e., reject the hypothesis if m>h. (Page [2]).
5


Consider the test for the general case using binomial variables, then Test 1
becomes.
Test 2: Given the observations xj, X2,........, x. It is required to test the
hypothesis that the mean is constantly 0. Let yi=a if Xj- 0>O and yi=-b if x;- 0 and choose a,b(>0) so that E(yj 0)=O(i=l, n). Use as the test statistics
T
m = max(5r min S,} where S = V (x. 9), S0 = 0,
0 i=i
Taking large values as significant, i.e., reject the hypothesis if m>h. (Page [2]).
2.3 Stopping Algorithm:
In this section the problem of optimal stopping, as soon as the change is detected
is studied. Consider xi, X2,.as independent random variables. Let xi, X2,
....,xm_i be generated by distribution Fo and xm, xm+i, .... be generated by the
distribution Fi ^ Fo. The distribution Fo and Fi are known, but the point m at
which the distribution changes from Fo to Fi is unknown. Let N be the stopping
variable, at which the algorithm stops. And Pm be the distribution of the sequence
xj, X2,...under which xm is the first term with distribution function Fj. Let Em
denote the expectation under Pm, therefore
£, N = sup ess sup En [(N m + 1)+ | A,,.. Xm_, ]
m> 1
Em[N-{m-1)| X, =xx.........,Xm_, =xm_x] The smallest possible Ex N is determined asymptotically as r> and shown to be
attained asymptotically by the following procedure due to Page [1]; stop the first
time
Tn = Z *g 2l0g
1=1
M*,)
i=l
W.t)
'MX,)
> r-----------(2.2)
The recursive form is
T. -
Tn-1 + l0§
Uxn)
MX*).
Y
--------(2.3)
6


Page also pointed out that the procedure in (2.2) is equivalent to Sequential
Probability Ratio Test (SPRT) of fo vs fi with log boundaries 0 and r, and
repeating the test on successive new observations until a decision in favor of fi is
reached.
By Walds equation:
E0N = cT'E0N----------(2.4)
where, N* time for single SPRT to stop,
a -> Po(decide fi)
EXN = (]-/3y'ElN----------(2.5)
Where, p Pi (decide fo).
Replace the distribution Fi by a family of distributions Fe, where 0 is unknown.
The expectation is that the minimization of all 0 simultaneously is not possible.
Hence, simultaneously each 0 will minimize. The Theorems 1 and 2 below
indicate that simultaneously each 0 will minimize asymptotically as r -> 0 for a
wide class of problems. Theorem 1 establishes bounds on the performance of
reaction procedures constructed from a One-Sided test.
Theorem 1: Let N be an extended stopping variable w.r.t. xi, X2.such that
Po(N For k = 1, 2, ... let Nit denote the stopping variable obtained by applying N to Xk,
Xk+i, ... and define
N' = min{Aft+*-l|Jt = l,2,....}
Then N* is an extended stopping variable,
E0N* > a'1
And for any alternative distribution Fi,
Ex N < EXN---------(2.6) (Lorden [3])
7


The asymptotic performance of Theorem 1 is then given by Theorem 2 below.
Theorem 2: Let n(r) be the infimum of £, N as N ranges over the class of
extended stopping variables satisfying EoN > r. If /, = £, log1-- < , then
fo(X)
l02 K
n(r) ~ as r > ---------(2.7) (Lorden [3])
f i
To handle composite {Fe}, use a One-Sided Sequential Test of Fo vs {F} and
apply One-Sided Sequential Test to xk, xk+], ... for each k = 1, 2, ... stopping the
first time one of these test stops, which is the result of the Theorem 3 below.
Theorem 3: Suppose there exists a class of One-Sided Tests (i.e. extended
stopping variable) (N(a), 0 Po(N(a) and V0e 0
EgN(a) ~
| log cr |
1(0)
-(2.8)
where 1(0) = Eg log <
f0(x)
For r>l let a = r'1 and define N'(r) = miniNt (a) + k -11, where Nk(a) is N(a)
*>i
applied to xk, xk+i, ..., then N*(r) is a stopping variable.
£0;V*(r)>r----------(2.9)
And for all 0 0 { N*(r), r >1} minimizes Eg N'(r) asymptotically subject to
(2.9), by virtue of the relation
EgN'(r) = j^)------------(2.10)(Lorden [3])
8


The expected stopping variable in the asymptotic sense is as in (2.10) for a
memoryless process. Now consider the paper of Bansal and P. Papantoni-Kazakos
[4] for processes with memory.
2.4 An Algorithm for detecting a change:
Two stationary stochastic processes with memory are considered. The main
objective is to detect the change from one process to another as accurately and fast
as possible. This problem for a memoryless case has been analyzed previously in
sections 2.2 and 2.3. In this section the processes with memory is discussed.
Consider two stationary stochastic processes with memory, [po, X, R] and [pi, Y,
R]. Let po be the initial process. The objective is to detect the change from po to
pi. The point of time when the change occurs is unknown. Hence, the test we
consider should be sequential. Let nfbe the sequence of observed data wi, W2, ...,
wn, and m be the time when there is a change; then
< => Generated by po "i
w^+l => Generated by pi J for m: 1 < m < n + 1.
The stopping variable is
Aj(w) = inf{n : Tn(w") > S}---------(2.11)
where 5 is the threshold.
7')= max
lS*Sn+l
2>g-
/.
fo
W;r
V / wk J
W.
V/ J
-------(2.12)
Given w, the Sequential Test stops at Ns(vv), and is decided that the change has
occurred.
Lorden [3] has proved that the Sequential Test determined by the stopping
variable Ng(vv) is asymptotically optimal for a memoryless process. The
9


asymptotic optimality of the process with memory is proved in Theorem 4.
Theorem 4 below is parallel to Theorem 1 (Lorden [3]) which establishes the
upper bound on One-Sided Sequential Tests.
Theorem 4: Let andju be two stationary and ergodic processes. Let w = Wj,
W2, ... be an infinite data sequence, and let N be an extended stopping variable
with respect to w such that
P^iN < ) < a
where 0 For k=l, 2, ... let N* denote the stopping variable obtained by applying N to Wk,
Wk+i, .... and define
JV* = min{Nt+Jfc-l|ifc = l,2.}
Then, N* is an extended stopping variable and
£A{N}>)<(l + or-1)>(2rl----------(2.13)
Also
EUt {N } < EMi {N] (P. Papantoni-Kazakos [4])
for any stationary and ergodic //j where E {N*} is defined as before. Now from
Theorem 5 it is shown that the stopping variable Ng(vv) is optimum asymptotically
with appropriate assumptions as :
For a stationary ergodic process
/10 = lim
/01=lim
n

n 1 log
log
n' log
/)
/o)_
/oK)
/,).
/.)
/oK)
----(2.14)
< v
10


Pon^') = Pt
A>
log
/,K)
< V
-(2.15)
if l]o and Im exist
01
Ao = E,(Ao) a.s.(PMi)
^01 ^o(/oi) a-S-(Pfio)
For v (0, Iio)
lim npin(v) 0
n*
limPo,n(v) =
and Z Pi* < 00 n>l (A)
and Z Po,n < n> 1 (A)
Theorem 5: Let g*s be the class of all extended stopping variables N* that satisfy
the conditionE^(N') > s/2. Let n*(5) be defined as
nV)=inf EMi{N'}----------(2.16)
Let the conditions of (A) be satisfied and let Iio be as in (2.14). Then
n (S) ~ -----...asS > -------(2.17) (P. Papantoni-Kazakos [4])
This proves that the stopping variable Ng(w) is asymptotically optimum among all
the stopping variables N* that satisfy the condition E (A*) > s/2
2.5 Extension of the Algorithm to Detect Change
In this section, the extension of the algorithm in section 2.4 as stated by A. Burrell
and P. Papantoni-Kazakos[5] is discussed. Let the initial process be go- The
objective of the algorithm is to detect the shift from p0 to p;, i=l, ...., m-1 and also
to find the process pi for which po changed. The point of time when the process
changes and the process to which po changed are both unknown. The detection of
11


the change and the process should be as timely and as accurate as possible. Due to
this extension, the algorithm is modified as:
Extended Algorithm:
1. Select a threshold S0 > 0.
II. Have m-1 parallel algorithms operating. The ith algorithm; i=l, ..., m-1 is
monitoring a /z0 > juj shift. T (x") denotes the operating value of the i1*1
algorithm at time n, given the observation sequence x". The operating
value
T (*;) is updated as follows:
Tq = 0
CU")=max 0.7-,(jt,-')+log
ur1)
\\
-----(2.18)
JJ
./(*. ur'),
III. The algorithm system stops the first time n when either one of the m-1
parallel algorithms crosses the common threshold^. If the i"1 algorithm is
the one that first crosses the threshold, then it is declared that a
ju0 shift has occurred.
Let N oi denote the extended stopping variable given as:
N oi = inf {n : T (.r") > S0 } A. Burrell and P. Papantoni-Kazakos [5]
Then the equations parallel to (2.14) and (2.15) is given as:
f ,(<)'
ly ~ lim
n log
/,K)
P(v) = P

; 1,7 = 0,1,...., m-1
n~ log

fiW
and the equations A and A are given as:
l,j; i, j = 0,1,...,m -1 exist and
ly = E(Iy |Mj) aMPrt) (B)
;*,7=0,1,...m-1 -----(2.19)
12


for i, j = 0,1,....,m -1 and for v e (0, lj})
lim/zpf (v) = 0 and J]pf(v)<<------------------------(B )
A. Burrell and P. Papantoni-Kazakos then state a theorem and corollary and derive
the result in (2.20) and (2.21) below.
As 5
, fj/VoK-r) | //,}:
7=0,1..m-1
/=!...m-1
>2-'J ;i//,
--(2.20)
As S > , £"{/V oi (a:) J /z .70] log £:
Trjjv 0i (jc) I flj}~ [/0; fj J-1 log S\
Vi*j:I0i>I
[Vi*j:ifI0j Expressions (2.13), (2.20) and (2.21) represent the asymptotic performance of the
Centralized system, where m-1 parallel algorithms as in (2.18) operate, with the
common threshold 5. The first algorithm that crosses the threshold determines the
decision of the system and the algorithmic system stops.
13


3. Distributed Detection
3.1 Introduction
The objective of this chapter is to discuss the Distributed Detection System
with the help of Fusion Center architecture. Before the Distributed Detection was
introduced, all detections were using the Centralized Scheme. In the Centralized
Scheme all the observations are sent to a processor where all the data is processed
and the decision is taken. In the Centralized Scheme, even though the performance
of the detection is good and reliable, processing large amounts of data is not
practical since large amounts of data require large bandwidth and more processing
time. These disadvantages lead to the Distributed Detection which is well suited
for applications with increased survivability and short response time.
In the Distributed Detection scheme the optimum design is sought under
both the Bayes and the Neyman-Pearson performance criterion. Six different
journals are referred to in the discussion of the Distributed Detection Scheme
below. The authors of the journals are Tenney and Sadell [6], Chair and Varshney
[7], Z. B. Tang, K. R. Pattipati and D. L. Kleinman [8], J. N. Tsitsiklis and M.
Athans [9], D. Kazakos and P. Papantoni Kazakos [10], C. C. Lee and J. J. Chao
[11], and D. Pados, K. W. Halford, D. Kazakos and P. Papantoni Kazakos [12],
The journals [6], [7], and [8] discuss the Distributed Detection Problem with
respect to the Bayesian performance criterion. The later journal discusses the
Distributed Detection Problem with respect to the Neyman-Pearson performance
criterion. A brief summary of all the journals [6] through [12] is discussed in the
upcoming section.
3.2 Distributed Detection System With Bayesian Performance Criterion
The Distributed Detection was first studied by Tenney and Sadell [6], Tenney
and Sadell considered the Fusion Center structure and optimized the local
14


detectors in the Bayesian sense. Tenney and Sadell went about the Distributed
Detection theory by extending the classical detection theory. Tenney and Sadell
stated theorems parallel to the Centralized Detection theory as:
Theorem 1; The solution to the decentralized binary hypothesis testing problem
is a) deterministic
c) the thresholds ti and t2 satisfy
ti = fi(t2) ; t2 = fi(ti).
Note that the key difference between the Centralized and the Decentralized case is
that in the Centralized case a single decision is made, and is based on both the
observations. In the Decentralized case two decisions are made, each based on
only one observation.
Tenney and Sadell also stated that the computation of thresholds couples
the choice of local decision rules so that system-wide performance is optimized,
rather than the performance of each individual detector. Considering an example
of exponentially distributed observations, Tenney and Sadell concluded that the
solutions of the computations above may be locally optimal but not globally.
Finally when the Centralized and the Distributed Decisions were compared;
Tenney and Sadell deduced that the trade off is between communication and
performance.
After Tenney and Sadell [6] proposed the Distributed Detection theory for
Fusion Center structure and optimized the local detectors in the Bayesian sense,
given the Fusion Center decision rule, Chair and Varshney [7] optimized the
Fusion Center given the local detectors. Chair and Varshney viewed the Fusion
^ : r, ^ {0,1}; y2:T2-M0,l}
b) a likelihood ratio test for each detector
15


Center problem as the two hypothesis problem. The result of the Fusion Center
rule is presented through a Theorem as:
Theorem 2: Given n detectors we have
log
P{HX |)
P(H0\u)
= 1g-^+Z
1 -Pu
s+
PF
+
y.
M
l ~PF
---(3.2)
Where S+ is the set of all i such that Uj = +1 and S. is the set of all i such that u, = -
1.
Therefore we may express the data fusion rule as:

-1, otherwise
--(3.3)
P.
where a0 = log
r0
1 -p
a, log
Pf
1 -PF
a, = log ifu
PM
Hence Chair and Varshney concluded that the individual detector responses are
weighted according to their reliability, i.e the weights are functions of probability
of false alarm and probability of miss.
Z. B. Tang, K. R. Pattipati and D. L. Kleinman [8] proposed a paper with
regard to Distributed Detection Problem. Z. B. Tang, K. R. Pattipati and D. L.
Kleinman derived the conditions for person-by-person optimal rules for primary
and subordinate decision makers, and proposed an iterative algorithm to find the
corresponding optimal decision thresholds. The optimal decision rules of primary
decision makers and the subordinate decision makers are given by Theorems 3
and 4 respectively.
Theorem 3: Given the decision rules of the subordinate decision makers DMj,
i=l,...,N, the optimal decision strategy for the primary decision maker DMo is a
likelihood ratio test given by
16


--(3.4)
P(y o !*/,)>
^(y0 l^o) <
W0
--------
np(,. | //,)
/=)
o/k/ x = p0[y(i,//0)-y(o,//o)]
P, [7(0,//,)-7(1,//,)]
--(3.5)
where P(ui |Hj) is the probability that a subordinate DMi makes the decision u;
G(0,1) given that the true hypothesis is Hj, j=0,l.
Theorem 4: Given the decision rules of the primary decision maker ro and of the
other subordinate decision makers Tj, j^l, the optimal strategy r, for subordinate
decision maker DMj 1 < i < N is a likelihood ratio test given by
Pt-y. !,)>
Pb'JH.X '
Wq
--(3.6)
heren, = X ^ = I P<"? = 1 j < (3.7)-
P(u0 = 11II, -1, //,) P(u0 = 11 u, 0, //,)
Z. B. Tang, K. R. Pattipati and D. L. Kleinman[8] then presented a Gauss-
Sedel cyclic coordinate descent algorithm for determining the thresholds nj in
Theorem4 for each subordinate decision maker. DMi, i=l,2,....,N. The algorithm
works as follows:
STEP1: Initialize the algorithm with thresholds ni(k), 1 < i < N, corresponding to
any arbitrary decision rule for DMi and compute the concomitant Pk(Uj|Hj), j=0,l.
Set iteration index k=0.
STEP2: {Main Iteration}
a) Implement the decision strategy ro of DMo based on Pk(Ui|Hj), j=0,l. Compute
the coupling functions Pk(uo=l|ui, Hj> for u;=0,l; j=0,l; and 1 < i < N. Compute
the expected team cost Ck(0).
b) For i=l,2,...,N, each subordinate decision maker DM, updates his decision
threshold nj(k+l) by recomputing the coupling functions Pk(uo=l|ui, Hj) for Uj=0,l;
and j=0,l using updated Pk+i(um|Hj), m STEP3: If the set of thresholds {nj(k)} have converged, stop. Else, set k=k+l and
return to step2
17


Z. B. Tang, K. R. Pattipati and D. L. Kleinman finally concluded that the
optimality is attained at the local level but not necessary at the global level with
the presented optimal rules.
Tsitsiklis and M. Athans[9] discussed the complexity of the Decentralized
problems which showed that the global optimization problem of the Decentralized
decision making is Non-Polynomial (NP) complete. Tsitsiklis and M. Athans
showed that the Decentralized decision problems are different from the
Centralized decision problems. The complexity of Decentralized decision problem
is discussed in two steps. First the problem is formalized to decide whether any
communications are necessary for the Decentralized system as:
Problem PS: Given finite sets Yi,....,Ym, Ui,....,Um and a function S:
Yix....xYm 2U,X"'"*U" are there functions y*: Y, Uj, i=l,....,M such that
(7i(>iX.yM(y*,))e 5(>y.....Jm) (3-8)
V(y,yM )e T, x......x YM ?"
With some restriction and with only 2 processors, the problem can be
solved in polynomial time. In general the Problem DS is N-P complete. In other
words the simplest problems of Decentralized decision making are hard from
algorithmic viewpoint. Once the conditional independence in (3.9) is removed, the
detection problem will become hard.
P(yi, y2| Hi) = P(y,| Hi) P(y2| H;); I = 1,2 --(3.9)
With the help of an example, Tsitsiklis and M. Athans concluded that the
team decision problem is in general a hard combinatorial problem.
3.3 Distributed Detection System with Neyman-Pearson Performance
Criterion
Consider Lee and Chao [11] which studies the optimization of the multi-bit
local decision. It is showed by Lee and Chao that the multi-bit local decision will
lead the system to out perform the system that uses hard decisions. First Lee and
Chao derived the Distribution Detection Scheme based on the two-bit local
decisions. Then the scheme was extended to the m-bit local decisions. Lee and
18


Chao studied the performance of the system with the hard decision, 2-bit and the
m-bit local decision. Results of the study show that the Distributed system using
the 2-bit local decisions significantly outperforms the 1-bit decision, and is close
to the optimum centralized system performance. Study also shows that m=3 is
much closer to Centralized system performance when compared to m=2.
Therefore, the performance of the distributed system monotonically increases with
mfnumber of bots per local decision).
3.4 Distributed Detection System with Feedback
The standard Centralized Detection Theory states that if the probability
density functions of the two hypotheses overlap in region of non-zero measure,
then infinitely many data are needed to reveal the active hypothesis with power
probability p=l. But practically speaking, we can neither equip a physical detector
with infinite processing capability nor wait infinitely long to receive its decision.
These ideas led to the feedback equipped detector as discussed by D. Pados, K. W.
Halford, D. Kazakos and P. Papantoni Kazakos [12], In D. Pados, K. W. Halford,
D. Kazakos and P. Papantoni Kazakos [12] have considered two structures with
feedback. From the thesis point of view, only the Fusion Center structure as in
figure (3.1) will be discussed.
19


Some basic assumptions that govern the development of [12] are:
a) The external observations {Xjn }i.n are statistically independent under both
hypotheses.
b) Each detector is memoryless.
c) At each time instant n, every local detector receives a single scalar external
measurement Xin.
Next, D. Pados, K. W. Halford, D. Kazakos and P. Papantoni Kazakos
developed a optimal Neyman-Pearson design for Fusion Center structure. The
objective is to maximize the power probability induced by the final decision
makers subject to a given false alarm rate a. Based on the conclusion of journals
[6] [11], the Fusion Center element o is optimized independently of the top
elements 1 through N.
First the power probability of the top element is derived as:
20


/() = E[U I H,) = P,


A, (a) = E{l/J ,}=&..,(>/>
*>2
.Og^
(1 Ao.,-1 ()) A
fw(X)
log M
/(*>
-----(3.10)
+

-----(3.11)
The conclusion from (3.11) is, as /?0n() increases, so does the power
included by each top element.
Now consider element o' of the Fusion Center structure. The power
probability of element o is derived as:
A>1 () = z ^ A* (a)0 A (a))N~k +r{^ ]a,m (a){ 1 A (or))"'
*>, v* y
v^.y
-----(3.12)
#>()= X
"22 i>M
(V'
> +
N
Ao.,-1 ()?.* (^, - ()[l <7. (Mn ~ Wn +
(\-Po^{a))qkx(Mn)V-qMn)Tk
Ao()?" (/C * (a)[l 9, (Mr - +
(1 Ao.,-1 (ff)tel' (/*, )[! ----(3.13)
D. Pados, K. W. Halford, D. Kazakos and P. Papantoni Kazakos have
discussed the performance characteristics of the Fusion Center structure. The
comparisons are in terms of the Asymptotic Relative Efficiency (ARE), defined
as:
Asymptotic Relative Efficiency (ARE) in comparison to the optimal
Centralized Scheme, is the ratio of the number of data needed by the Fusion
Center structure over the number of data needed by the Centralized Scheme, to
attain the same false alarm and power probabilities for the same hypotheses,
subject to close to each other hypotheses and to subsequently asymptotically
many data collected by both the Fusion Center structure and the Centralized
Scheme.
21


The result shows that the total number of data needed by Fusion Center
structure, say D(2>, to attain the specific (a=0.5, P) performance at time instance
the same performance level at time instant one.
Based on the numerical results, it is concluded that when N is sufficiently
large and the two hypotheses are not asymptotically close to each other, the
contribution of the feedback becomes practically insignificant. Finally it was
concluded that the power increase contributed by feedback decreases
exponentially as the signal-to-noise ratio or the number N of local detectors
increases.
two, is less than An
r
times the number of data needed, say D(i) to attain

22


4. Detection Algorithm for Fusion Center Distributed
Structure
4.1 Introduction:
The Detection Algorithm chapter discusses the Detection Algorithm with
respect to the Fusion Center structure with feedback. The Detection Algorithm
and the Fusion Center structure with feedback are discussed respectively in
chapter-2 and chapter -3. For the discussion in chapter -2 and chapter -3, different
journal papers are referred. In chapter -4 the results of chapter -2 and chapter -3
are combined and a new concept is studied. This concept was first developed by
Burrell and Papantoni-Kazakos [13]. As a result of this concept, the Detection
Algorithm will be of great help in Radars, Sonar etc to detect the targets with
increase survivability and short response time.
4.2 Fusion Center Structure:
The Fusion Center structure that is considered for the discussion here is as
in Fig(3.1). The sensors 1,.M are all in identical stochastic environment; that
is, possible changes of the local data generating processes occur simultaneously at
all sensor sites. Each sensor uses the Detection Algorithm to detect the shift. Once
the shift is detected the sensors communicate their decision to the Fusion Center.
Receiving the decision of the sensors, the Fusion Center makes the final decision
with help of the same Detection Algorithm.
The sensors 1, ..., M collect the local data xj, ...., xn denoted as Xi" and
the feedback from the Fusion Center {Vn} at each point of time n. The feedback
{Vn} from the Fusion Center is same for all sensors. The output of the sensors is
denoted by uin, which is also the input to the Fusion Center. Let {pj; i-0,1,.., m-1}
denote the measure of m distinct and parametrically defined stochastic processes.
Then the problem under consideration is defined as:
23


Problem 1: Consider a Decentralized system with discrete time memoryless
process. The initial process is and at some point of time the change in process,
i.e, go > pi is detected and pj is decided as the acting process.
Problem 1 states that initially the observation sequence is generated by the
process go. Then the shift from ^ p;, i = 1, ...., m-1 may occur at any point of
time. If the po * p; shift is detected, then the process pi is active thereafter. The
objective of the problem is to Detect the occurrence of a p > pj shift as
accurately and as timely as possible, including the detection of the process pi
which po changed to.
It is known that xin(i) is the input sequence to sensor i and un(j) is the
output of sensor j and input to the Fusion Center from sensor j. There will be no
transmission from sensors to the Fusion Center till the sensor decides a Po pj
shift at time n. Hence for the time 1< n-1 the sensor has not decided in favor of p
pi shift and u^ = 0 is deduced by the Fusion Center. Then at time n when the
sensor decides the p > pj shift, then un()) = i is transmitted to the Fusion Center.
Similarly the feedback is transmitted from the Fusion Center Vn = 0 for all time n
before the shift. The feedback is not transmitted to the sensors before the shifted is
detected, instead Vn = 0 is deduced by the sensors. Once the Fusion Center
decides the shift, then the feedback Vn 4- 0 is transmitted to stop the sensors.
4.3 The Algorithmic System
We assume identical sensors collecting mutually independent local data.
We denote by xn(i) the n1*1 local datum at the ith sensor. We denote by xin l(i) the
(n-l)lh dimensional data sequence collected locally at sensor i from time 1 to time
n-1. The algorithms deployed by the sensors are identical, and utilize conditional
densities or distributions. In addition to its local data, each sensor also utilizes the
implicit fusion centers feedbacks {vk = 0 }k throughout its operation. Let
= 0| jc1n_l(/),{vt = 0}lsisn_,) denote the conditional density or
distribution of the data at sensors i, given that the acting data process is pj. It is
24


clearly seen that the {Vn} sequence is a Markov Chain and that the data sequence
xi"(i) is independent of {Vn)- We can thus write,
fj k (0, V = 01 <' (/),{V* = 0}lstS)I_,) = fj (v = 01 v_, = 0,x (/))/,. k (/) | xr (*))-
We observe that the {vk} sequence is based only on the {uk(l)} sequences of the
sensor outputs rather than the data sequences collected by the sensors. We thus
substitute /, (v = 01 vB_, = 0, x" (i))by f. (v = 01 v_, = 0, u= o). Since the
sensors are identical we drop the index i and we write,
Ik,,.-, )= =0|v,_U, = 0)/_(-(. 1.1,"') =
= I , ,
fA-,=o\.=o)f[XJX' <4-
, =0| -C'.K 11,m-i)
fo(XnVn =0Ul" .{V* }!<*<-! )
/, (y, I ) , fj(Vn =0|, =) , /;(Vl =0|, =0)________
g/ok 1-0 g /o(v = o I un = 0) g /ok., =0|n =0)
The expression in (4.3) represents the updating step of the po Pj shift detecting
algorithm in (2.18) at time n, at any one of the M sensors, where Xi" are the locally
collected data. As compared to the centralized scheme, the terms
, /,k=oK=o) /;k-i =ln =o)
log^r------:------r and-log-
7ok =0|m =0)
7ok-i =o| =o)
are added to the updating step. Due to the latter terms, the algorithmic systems
across the different sensors are mutually dependent, while the locally collected
data are mutually independent instead.
At the fusion center m-1 parallel algorithms are operating, with a common
threshold T, each monitoring a po * pj possible shift, for j = 1,.m-1. These
algorithms utilize the vectors U = k\. where un(l) is the output of
sensor i at time n. If at time n the sensor has not made a decision yet, then un(l) = 0.
If at time n the sensor decides in favor of the process shift p pj, then un(l) = j,
and this value remains unchanged for all times after n. Due to the above discussed
evolution of the { un(l)} outputs, it is clear that the process jt7} is a Markov
-(4.1)
25


Chain. Thus, /.((/ | Ut ,1 < < n -1)= fj(Un \ Un-i), where, in addition, the
conditional probability /,.((/ | U-\) is determined solely by the transitions of the
zero-valued components of U n-\. In fact, due to the identical nature of the
sensors, /.([/ | t/-i) is determined by the number of sensors whose algorithms
are still running at the time n-1, and among them, from the numbers which
transition to the states un = 1, m-1, at time n. For sensor i, let us denote the
variable dn(l) as, dn(l) = 0 if un0) = 0 and dn(l) = 1 if un(l) = 1,2,.m-1. Let Dn be
the vector whose components are dn(l); i = 1, 2.... M. Then, we can first write
fj (t7 |C/,-l)= fj (tin | Dn-l)= fj[Un \ Dn, D.-1 )/, (d | D-, )
, f$n\Un-i) /7(f7|Dn,D-,) /,(Dn|Dn-,)
f0(Un\Un-i) f0[Un |D,D-,) / (D | D.-, )
and,
--(4.4)
From the discussion above, it is evident that the sufficient statistics for the term
l0g i arC M Z dnn (* dn\ )and M Z (! dn] K1 dn-l )- As tO the
J0\L>n I L)n-\j i=l 1=1
conditional probability /y^7 | Dn,D-\\ j = 0, 1, ..., m-1, it represents the
probability of the number of sensors deciding in favor of the go * gf k = 1, ...,
m-1 shifts at time n, given that their algorithmic systems stop at time n; this
probability equals 1 if m=2, since then, Dn = U n. The sufficient statistics for the
f \ /ilJn | Dn,Dn-\)
probability fj\Un \ Dn,Dn-i j and the term log / -r in (4.4) are,
f0\fJ n\Dn,Dn-\)
M ) ]~[ (m*0 -k\ 1 < / < m. The expression in (4.4) represents the
r=1 1 l<*£m-l
k*l
updating step of the go > gj shift detecting algorithm in (2.17) and (2.18) at time
n, as implemented by the fusion center. Let us denote:
26


Pi
Pik
Pi
a
n
The probability that the algorithmic system at a sensor stops at time n
(the common threshold is first crossed at time n), given that the data
generating process is pj.
The probability that, given the data generating process pj, the
algorithmic system at a sensor stops at time n, where the p * pj
shift detecting algorithm is the one that first crosses the threshold at
n.
The probability that the algorithmic system at a sensor stops before
or at time n, given that the data generating process is pj.
The probability that the algorithmic system at a sensor stops before
or at time n, given that the data generating process is po.
We note that pJn = pJnk; if m = 2. Also, pn = j5n Pi_x; j =1,..............m-1 and
Pn = --
Theorem 1: Let the probabilities /. (vn = 01 un = 0); j = 1..m-1 and
/0(v = 01 un = 0) be such that there exist constants no, Cj; j = 1, m-1 and Co
such that
fj(Vn = 01 = 0)
/;(v i =K-i =0)
fo(v =Qln =0)
fo(Vn-l = 0 I -! = 0)
= Cj\ j = 1.,m-\yn > nQ
= c0;Vw > n0---(4.5)
Then, the algorithmic systems across different sensors are mutually independent
for all n>no. In addition, if the pj; j = 0, 1, m-1 processes are stationary,
ergodic and satisfying conditions (A) and (A) in CH-2 as well as Lais (1977)
mixing conditions, then the performances of the sensors algorithmic systems are
asymptotically (n>no) identical and as in (2.20) and (2.21). Finally, the updating
step of the po * Pj shift detecting algorithm at the fusion center in (4.4) takes then
the following form:
27


Pnlf Pn
1=1
l k*l

t=l
(i-A'VO-A'-i).
-a,-,)'
;>h0-------(4.6)
Where (/() =
l;n > 0
0;n > 0
The expected value of the updating step in (4.6), subject to the generating process
being gi is found by straight substitution as follows:
|//J=f/(m-2)|;^flog
ph/pl
/=l,...,m-l
+ -
Pn
+
1=1 Pn Pni/Pn ^ ~ Pn
(i-fl) (i-flV(i-flL,)
,og4f^J+
p"/0
;><,--(4.7)
iP'n
E{sSU.}=V"-2)I-£F'g£f/ .
/-I Pnl/Pn
+ -

1 or.
-log
+

(i-O 0-J/0-
pjfo-PL)
Pn/0--l)
-----(4.8)
For asymptotically many sensors (M oo) the updating step in (4.6) converges to
the expected values in (4.7) and (4.8), depending on the acting data generating
process. Let K(p|q) denote the Kullback-Leibler information number of a
Bernoulli trial with parameter p, with respect to a Bernoulli trial with parameter q.
Let A'({p/}ls;sm | ) denote the Kullback-Leibler number of a distribution
with probabilities {/j;}lsJSm l, with respect to a distribution with
probabilities {^;}1S/Sm l. Then, from expressions (4.7) and (4.8), we easily deduce
the expressions (4.9) and (4.10) below.
28


E{s%\n}=U{m-2)
j'=l....m-1
+ K
(r 'i
-2) K
{[PnU
1-/ z
\-P L
i\
\ f
-K

-K
o;
i-/c,
i-a:
4)
. P" J l fzil
k'J
1 1-^:
------(4.9)
i V
|//0}=t/(m-2)A'
fzll
ul

Pn/1
. P" J l<; -K
l-or
i-A'
1 or,
fi-1
'-PL
-----(4.10)
We note that the quantities ; i = 0, 1, ...., m-1, 1 = 1, ...., m-1
1 P" J l<; and in (4.9) and (4.10) all represent performance metrics per single
0-0
sensor. We now state the following theorem.
I ; i = 0, 1, ..... m-1, I = 1, ..... m-1 and
Theorem 2: Let the
pI J

l-fi-
Y-----4- converge asymptotically. Then, the algorithmic svstem at the fusion
0-0
T
center has the following asymptotic performance characteristics, where N0j
denotes the stopping variable of the po > (ij shift monitoring algorithm in the
system when the common threshold is T, and where e{sjfs | /uk }= lim e{s^s \ juk}.
AsT > ,
AsT > oo,
E-'is^ogT-Jf £H^}>0
1 *2"r; if e{s{s\Mi}<0
e{ntoJ \Mj }< \fij }ti*j - (4.12)
--(4.11)
In addition, the conditions in theorem 1 for mutual independence across the
various sensors hold for asymptotically many sensors.
29


5. Simulation
5.1 Introduction
In the previous chapters the sequential detection algorithm was discussed in detail
and various journal papers have been referenced. In chapter 4, the updating step
for the sequential algorithm evolving from the fusion center architecture was
developed. In this chapter, the sequential algorithm for fusion center structure is
simulated using MATLAB and C++ programming techniques. First the false
alarm and the power values per sensor are calculated and plotted in MATLAB.
Later C++ programming is used to simulate the algorithm for the fusion center
structure. The simulation procedure is explained in detail below.
5.2 Simulation Model
The sequential algorithm developed in chapter 4, is simulated using MATLAB
and C++. The model used for simulation is discussed in this section. Consider two
non-composite hypotheses Hi and Ho described by the Bernoulli processes, i.e, the
generated sequence is either zero or one. Consider that the element one occurs
with probability q under hypothesis Hi, and with probability p under hypothesis
Ho. Then the logarithm of the ratio of density functions is:
log
Mxi)
= log
9*0-*r
^*0-p),_
= log -- + .V, log
1 -p p(\-q)
Now the Wald test function is given as:
= log + (1 Xf) log-J
p 1 -p
T(xn) =log
f0(xn)

- log
r q(\-p)^
P( 1-9)
V-1 i 1 q
2Jxi +nlog--------
i=\ 1 ~P
= T(xn~') + xn log
r qiy-p)''
p( 1-9)
+ log
1-9
1 ~P
30


T(xn) = T(xn-') + zn------(5.1)
where zn = xn + /(p,q)-------(5.2)
Yip,q) =
< 1 -q '
log---
1 ~P
log
q{\- p)
----(5.3)
P(\~q)
This algorithmic model is used in the simulation program to detect the change in
parameter p Bernoulli process to parameter q Bernoulli process. Then the
sequential test in (2.18) is applied (where i=2 for Bernoulli process) with the
assumption p get
T(0) = 0, T(xn) = max(0, T(xn-') + z) (5.4)
where zn is given by (5.2). Then the change from one Bernoulli process to another
Bernoulli process is detected when T(xn) > 5. The false alarm and the power
characteristics as induced by the algorithm for the given threshold 5 is studied. Let
us define the probability as:
Pr.s(n): The probability that the threshold 8 is first crossed at the time instant n,
under the condition that the p to q change actually occurred just after the datum xr.
--(5.5)
The false alarm is a probability, which show how probable is the crossing of the
threshold at different time instants n when the p to q change never occurs. The
false alarm set is represented as {Poo.o(n); n > 1}. The power is a probability which
shows how probable is the detection of change in process when the threshold is
crossed at different time instances n where the acting Bernoulli process is the
process with parameter q. The power set is represented as {P0.s(r>); n > 1}. The
false alarm and the power curves can be computed numerically. For efficiency in
such computations, the expression in (5.3) is approximated as:
Y(p,q) = -
l_
s
--(5.6)
31


where 1 < s and 1 and s are both natural numbers. Then the (5.4) can be written
as:
Select the threshold t. Decide the change has occurred as soon as T'(xn) > t, where
t is a natural number. Then,
T'(0) = 0, T'(xn) = max(0, T'(xn_l )+yn) -(5.7)
yn = sx-l (5.8)
The probability in (5.5) can be represented as Pr,t(n) which can be applied to (5.7)
and (5.8). It is possible to obtain the recursive expressions for computing the
probabilities { Pr.t(n); n>l} via a Markov chain formulation as given in [10] by
Papantoni-Kazakos. The key element in the later formulation is the probability
Pr.t(n,j) that T'(xk) < t V k < n and T'(xn) = j given that the p to q change occurs
just after the datum, xr. The algorithm as given in [10] is:
i. If t-1 > s > 1+1
Pr l {n,0) = (1 v)£ pr,t (n ~ i)
i=Q
Prl(n,j) = (\-v)Prl(n-l,j + l) 1 prJ (, j) = (1 v)Prl (n -1,; + /) + vPrt (n-\,j-s + l) s-l < j pr.t (j) = vPr,< (n-\,j-s + l) t -1 / < j < t -1
ii. If t-1 > s = 1+1
/
Prl (n,0) = (1 v)X Pr,i ( -0
1=0
Pr.t (. j) = 0 v)pr,, (n -1J +1) + vprJ (n-\,j-\) 1 < j pr,(n,j) = vPrl(n-l,j-\) t-\-l where
v\p ifn \q if n> r
--(5.11)
Pr,t () = V J] Pr ,r ( 1, j) t~l>S>l + ]
(5.12)
J=t-S+l
The recursive expressions in (5.9) and (5.10) allow for the efficient computation
of the probability Pr.t(n) in (5.12) for every r and every n. The false alarm and
power probabilities can also be computed recursively as:
32


a(p,q,n,t) = ^l\t{i)-------(5.13)
n
fi(p,q,n,t) = Y,PoA)--------(5.14)
These recursive expressions are simulated in MATLAB to calculate and plot a,
the false alarm probability and P the power probability.
The problem of detecting a change in process with respect to fusion center
structure as explained in chapter 3 and 4 is simulated with C++ and thread
programming. As explained previously in chapter 4, the sensors are in identical
stochastic environment. The sensors and the fusion center run the same algorithm
at time n to detect the change from parameter p Bernoulli process to parameter q
Bernoulli process. The updating step is added to the test function at the end of
each time step n. The updating step of sensors is different from the updating step
on the fusion center since the fusion center has to consider the output of the
sensors as its input. The updating step for the sensors is given by (5.2) for the
Bernoulli process. The updating step for fusion center is given by (4.6). The
updating step in (4.6) can be simplified when Bernoulli processes are considered
as:
The simulation in MATLAB and C++ are discussed in detail with the control flow
diagram in section 5.3.1 and 5.3.2 respectively.
5.3 MATLAB Simulation
The sequential algorithm was discussed in chapter 2 and 4 in detail and is given
by the equation (5.7). The recursive expression for calculating the false alarm and
power based on the sequential algorithm is as given by the equations (5.9) -
(5.12). These recursive expressions are implemented by MATLAB programming
and the false alarm (a) and the power probability (P) values are calculated. The
--(5.15)
33


MATLAB code is given in the appendix. The plots of alpha and beta are discussed
below.
Figure 5.1: Alpha and beta plots for threshold = 3.07
34


Figure 5.2: Alpha and Beta plots for Threshold = 3.5
35


Figure 5.3: Alpha and Beta plots for Threshold = 3.92
The False alarm and power plots are as plotted above for variations in threshold,
parameter p and parameter q values. As can be observed from the above plots, as
the threshold increases, both the false alarm and power plots move to the right.
This implies that the time taken for saturation is more. It can also be noticed that
36


for smaller sample size, the probability of false alarm is low and the probability of
power is high.
When the probability p and q values of the Bernoulli process is varied the plot
shows significant difference. As the probabilities are far enough, the power and
false alarm plots are far away. If the probabilities are close to each other, the false
alarm and power plots are also close for the same threshold values.
5.4 Flow Diagram for Fusion Center Simulation
After calculating the alpha and beta values in MATLAB, the sequential algorithm
as applied to the Fusion Center structure is simulated using C++ programming.
The Fusion Center structure is as in fig 3.1. The back ground of all the Fusion
Center structure and the distributed detection is discussed in detail in Chapter 3.
The thread programming feature of C++ programming is used to implement the
Fusion Center structure. The whole program can be divided into 3 sections: first is
the main program which implements the Fusion Center structure; second part
which implements the functionality of the Fusion Center; and lastly the part which
implements the functionality of the sensors. The overview of the program is
discussed in detail in the previous sections. In the following section, the
simulation model as implemented by C programming is discussed by the help of a
block diagram.
The functional diagram highlights the design and functional aspects of the fusion
center (FC) and the sensor(s) relationship in the simulation program. Both the
fusion center and the sensor thread components utilize the common resources like
processes shared memory, and the data structures to simulate real-time scenarios.
The simulation program is written in C++ and UNIX platform. Used POSIX
system calls for synchronization and communication among multiple sensors and
the fusion center threads.
37


ProcessMain
ALPHA Values
Fusion Center
1
i
BETA Values
Figure 5.4: Fusion Center Structure from simulation point of view
A fusion center and multiple sensors threads represent the individual building
blocks within a process ProcessMain. The fusion center and sensors threads are
independent building blocks and run concurrently by sharing the common process
segment, data segment, and stack segment. POSIX system calls shall be used to
synchronize sensor functionality and the simultaneous communication among
multiple sensors and the fusion center (FC) threads. The thread (interchangeably
used as fusion center and sensor) synchronization block shall be used to serialize
all the sensor thread requests at a given clock time and forwards the request to the
fusion center thread. The fusion center thread calculates the updating step (5.15)
and then the test function (5.7) based on the sensors thread output and sends the
feedback to the sensor threads. The change shall be detected by fusion center
thread and/or sensor(s) thread at any given clock time.
If the fusion center thread detects the change, requests all the active sensor threads
to stop and exits. If a sensor thread detects the change, sensor thread will wait
until it receives Fusion Center Response STOP message.
38


CASE 1:
Figure 5.5: Message flow diagram when Fusion Center sends Stop signal
1. The processMain is the main function of the process. processMain read all
the configuration parameters and spawns as many sensors threads as
configured and a fusion center thread. All threads run independently and
concurrently. Upon the creation of all the threads, processMain will enter
into wait state and waits for all threads (Fusion Center and all Sensors) to
exit.
39


2. If sensor threads are up, all sensor threads wait for fusion center threads
Ready to Start signal. All sensor threads will start at the same time
irrespective of the initialization. The fusion center thread triggers all the
sensor threads and waits for the sensor thread requests. The fusion center
thread expects the request from all sensor threads at a given clock time.
3. Upon the receipt of the start signal from the fusion center thread, sensor
threads calculate test function values. The sensor threads run the sequential
algorithm to calculate the new test function value. The algorithm is as
given below in (5.7). Based on the algorithm in (5.7), the sensor thread
detects the change in Bernoulli process at the first time n when T (x" )> t,
where t is the selected threshold.
4. Once the test function value is calculated, all the sensor threads shall send
the calculated test function values in a Sensor-Request message to fusion
center thread. The values sent as a Sensor-Request message contains the
current and the previous test function values. After sending the request to
the fusion center thread, all the sensor threads wait for the fusion center
thread response to calculate the next test function value.
5. Receiving the sensor thread request, the fusion center thread calculates the
test function value which is based on the sensor test function values. To
calculate the test function value, the fusion center thread runs the
sequential algorithm as in step 3. The algorithm is as given in (5.7) but the
updating step y for the fusion center is given as in (5.15). Once the test
function is calculated, fusion center thread follows the same step as the
sensor thread to detect the change. Based on the result of the detection, the
fusion center thread sends its decision of STOP or CONTINUE to the
sensor threads.
6. The process of Sensor-Request and Fusion Center Response will go on
until the fusion center thread decides to stop. The process of request and
response can go on for 1 time to 1000s of time depending on the input
data to the sensor threads.
40


7. When the fusion center thread detects the process change, the Stop
response is sent to all sensor threads. Receiving the Stop response from
fusion center thread, all the sensor threads exits. The fusion center thread
will print the decision and exit from the thread. The programMain receives
the sensor threads and fusion center threads exit report and end the
program.
41


CASE 2:
pigure 5.6: Message flow diagram when Sensors stop and waits for Fusion Center to stop
The flow diagram in Fig 5.6 displays the different scenario of the same problem
discussed in Fig 5.5. The steps from 1 to 5 are same as in case 1 above. The steps
6 and 7 describe the different functionality of FC and sensor(s) thread
relationship.
6. The process of request-response will continue till the fusion center thread
requests sensor threads to STOP. Meanwhile the sensor thread could detect the
change and exit from the thread. All sensor threads might not detect a change
42


during the process. When 2 sensors are present, one sensor thread could exit at
time 20 and the other sensor thread could exit at time 48 and the fusion center
thread will exit. One more scenario is that, one sensor thread detects the
change and exit the loop and the fusion center thread detects the change when
the other sensor thread is still running. Any combination will work. When one
or many sensor thread detects the change, sensor threads will wait for the
fusion center thread to exit the thread. The sensor threads will not run through
the loop. The sensor thread which is waiting for fusion center detection will
send the request as soon as the fusion center thread sends the response.
7. When the fusion center thread detects the process change, the Stop response
is sent to all sensor threads. Receiving the Stop response from the fusion
center thread, all the sensor threads including the one which has detected the
change will exit from their thread.
Fusion Center thread will log the decision and exit from the thread. The
programMain receives the sensor threads and fusion center thread exit report and
end the program.
The easel and case 2 basically explains the control flow in the C program. From
the above case discussion we can also see that the fusion center structure is
implemented completely by POSIX threads.
The results of the simulation are tabulated below. The tables are created for
different combinations of threshold, parameter p and parameter q values. The
columns of the table are the thresholds, p is parameter p value, q is parameter q
value, iteration is the number of iteration, FC time is the time taken by the fusion
center to detect the change in process, SI time is the time taken by the sensor 1 to
detect the change in process, S2 time is the time taken by the sensor 2 to detect the
change in process, change time is the time at which the parameter p Bernoulli
process changed to parameter q Bernoulli process and FA is showing whether the
detection is a false alarm or not.
Based on the results in table 1 it can be seen that, as the difference between
parameter p and parameter q increases, the time taken to detect the process change
43


decreases. There is a delay between the actual process change and the detection of
process change. The rate of false alarm is also less.
5.5 Numerical Results
From the Fusion Center algorithm in (5.15) the computation of the average time
7^ and the probability r/n are plotted as a part of the numerical results. Using
the logarithm function in the algorithm (5.15) the threshold of the fusion center is
calculated. The threshold of the sensor is also calculated beforehand. The sensor
threshold is 2000 and the thresholds of the fusion center are {2, 2.5, 5, and 10}.
Once the thresholds are selected, the average time and the probability values of
the fusion center can be calculated. The definitions are:
h1^ : Given that the data at the sensors are generated by process ju,, the
percentage of simulation runs that let the fusion center to decide at time n
that juk started acting.
Tlk : The average time to decide in favor of process juk, given that the data
generating process is //,, where the decision is by the fusion center.
r^ : Given that the data generating process at the sensors is //,, the probability
that the fusion center decides in favor of process juk before or at time n.
and where (m-1) sets of simulations are run, each corresponding to one of the
processes//,; / = 1, 2, ...., m-1 that generate the actual data at each sensor.
For the numerical results of this thesis the processes //,; 1 = {1,2} and the
simulation is run for (m-1) = 10,000 iterations. Based on the results of the


--(5.16)
where,
r,'=Z< <5.17)
44


simulation, Tk and r^ values are calculated and the same is plotted which are as
shown below.
The figure (5.7) is the plot of 7/ for both correct detection (i.e, power) and wrong
decision (i.e, false alarm). The plot converges almost at the same time.
The figure (5.8) is the plot of r^ for both correct detection (i.e, power) and wrong
decision (i.e, false alarm). The convergences of r^ plot for different thresholds
are very close. If the plots are observed closely, it can be noticed that the space
between the false alarm and power probability plots decreases as the threshold of
the fusion center increases.
From figures (5.9) and (5.10) it can be noticed that, as the false alarm value
increases the power value also increases. The percentage increase of power values
is much higher than the false alarm values. The value (power value or false alarm
value) is a reference to either average time T or probability r calculations.
45


Figure 5.7: Plot of Average Time Tk for different thresholds.
T(kl)-Bi->j(xxxx,y): Tk calculated from correct decisions, for process i
to j change with sensor threshold xxxx ami fusion center threshold y.
T(kl) -Ai->j(xxxx,y): Tlk calculated from wrong decisions, for process i to
j change with sensor threshold xxxx and fusion center threshold y
i
I
46


Propability "r" plot for different thresholds
s co ra o r> n n
_SOOO)t-(NCOV
r-ri-t-NMM(N
Figure 5.8: Plot of Probability for different thresholds
r(knl) -Bi->j(xxxx,y): calculated from correct decisions, for
process i to j change with sensor threshold xxxx and fusion center
threshold y
r(knl) -Ai-> j(xxxx,y): calculated from wrong decisions, for
process i to j change with sensor threshold xxxx and fusion center
threshold v
47


T plot for FC threshold S
100 150
T alpha
T plot for FC threshold 10
100 T alpha 150
Figure 5.9: Plot of correct decision 7/ verses wrong decision 7/
48


Figure 5.10: Plot of correct decision r^ verses wrong decision r^
49


6. Conclusion
The performance analysis determines the reliability of Distributed Detection
Algorithm for a fusion center architecture with feedback. The theoretical model
of the fusion center was effectively implemented. The simulation was successfully
conducted to derive the performance analysis. The false alarm convergence is
quicker and faster than power convergence. With the increase in thresholds of
fusion center in fig5.7 and fig5.8, the power and false alarm plots will be closer.
There is very little variation in the performance statistics. As the threshold of the
fusion center increases the T and r plots in fig 5.9 and fig 5.10 become smoother
and wider.
The problem considered can be further extended by implementing the simulation
for the problem model with more than 2 processes i.e ju0 > /it; / = 1,2,.m -1.
In the same direction of the problem explained, the process change with Poisson
process will be a good extension. The second extension will be to implement the
re-initialization algorithm.
50


Appendix
7.1 MATLAB Program
7.1.1 MATLAB program to calculate False Alarm probability
%Thesis : Program of Exercise 8.5 for false alarm and power ratio
%ac time n and n-1.
delta(1) = 2.0; %threshold.
fid = fopen('FILE_NAME.txt','w');
p = 0.01; %priori probability,
q = 0.05; %priori probability.
L = 25;
s = 1000;
t = delta(1) s; %threshold
PetPrev = zeros(t-l, 1);%Initializing the recursive
probability
PetNext = zeros(t-1, 1);
PetZeroPrev = 1-p;
PetZeroNext =0; %
PetPrev(s-L) = p;
for n = 2 : le6 %iterations
% sets next value to previous values.
AlphaPrev = Alpha;
if (s > (L+l)) && (s <= (t-1)) % i-case of the algorithm
%First step in the i-case of algorithm.
sumFA = sum(PetPrev(1:L));
PetZeroNext = (1-p) (sumFA + PetZeroPrev);
%Second step in the i-case of algorithm.
PetNext(1:(s-L-1)) = (1-p) PetPrev(L+l:s-1);
51


%Third step in the i-case of algorithm.
PetNext(s-L) = (1-p)*PetPrev(s) + p*PetZeroPrev;
PetNext(s-L+1 : t-L-1) = (1-p)*PetPrev(s+l:t-l) +
p*PetPrev(1:t-s-1);
%Fourth step in the i-case of algorithm.
PetNext(t-L:t-l) = p*PetPrev(t-s:t-s+L-1);
elseif (t-1 >= s) && (s == L+l) % ii-case of the
algorithm
%First step in the ii-case of algorithm.
sumFA = sum(PetPrev(1:L));
PetZeroNext = (1-p) (sumFA + PetZeroPrev);
%Second step in the ii-case of algorithm.
PetNext(1) = (1-p)*PetPrev(L+l) + p*PetZeroPrev;
PetNext(2:(t-L-1)) = (1-p)*PetPrev(2:t-1) +
p*PetPrev(l:t-L-2);
%Third step in the ii-case of algorithm.
PetNext(t-L:t-l) = p*PetPrev(t-L-1:t-2);
end %End of if statement.
if ((t-1) >= s) && (s >= ( Lm- 1) ) %calculates the
probability at n
x = sum(PetPrev(t-s+L:t-1));
FalseAlarmProbAtTime_n = p x;
%testFA(n) = FalseAlarmProbAtTime_n(-
end
%calculates the power and false alarm probabilities
Alpha = AlphaPrev + FalseAlarmProbAtTime_n;
%Stores the Alpha value into a file
PRINT TO FILE
%sets the next value of recursive probability to the
previous value.
PetPrev(1:t-1) = PetNext(1:t-1) ;
PetZeroPrev = PetZeroNext;
end % End of for loop of n the iterations,
fclose(fid);
7.1.2 MATLAB program to calculate Power probability
%Thesis : Program of Exercise 8.5 for false alarm and power ratio
52


%at time n and n-1.
delta(1) = 2.0; %threshold.
fid = fopen(FILE_NAME.txt1,'w');
p = 0.01; %priori probability
q = 0.05; %priori probability
L = 25;
s = 1000;
t = delta(1) s; %threshoid
PotPrev = zeros(t-l, 1);%Initializing the recursive
probability
PotNext = zeros(t-1, 1);
PotZeroPrev = 1-q;
PotZeroNext =0; %
PotPrev(s-L) = q;

for n = 2 : le6 %iterations
% sets next value to previous values.
BetaPrev = Beta;
if (s > (L+l)) && (s <= (t-1)) % i-case of the algorithm
%First step in the i-case of algorithm.
sumP = sum (PotPrev(1:L));
PotZeroNext = (1-q) (sumP + PotZeroPrev);
%Second step in the i-case of algorithm.
PotNext(1:(s-L-1)) = (1-q) PotPrev(L+l:s-1);
%Third step in the i-case of algorithm.
PotNext(s-L) = (1-q)*PotPrev(s) + q*PotZeroPrev;
PotNext(s-L+1 : t-L-1) = (1-q)*PotPrev(s+l:t-l) +
q*PotPrev(l:t-s-l);
%Fourth step in the i-case of algorithm.
PotNext(t-L:t-l) = q*PotPrev(t-s:t-s+L-1);
elseif (t-1 >= s) && (s == L+l) % ii-case of the
algorithm
%First step in the ii-case of algorithm.
sumP = sum(PotPrev(1:L));
53


PotZeroNext = (1-q) (sumP + PotZeroPrev);
%Second step in the ii-case of algorithm.
PotNext(l) = (1-q)*PotPrev(L+l) + q*PotZeroPrev;
PotNext(2:(t-L-1)) = (1-q)*PotPrev(2:t-l) +
q*PotPrev(1:t-L-2) ;
%Third step in the ii-case of algorithm.
PotNext(t-L:t-l) = q*PotPrev(t~L-l:t-2);
end %End of if statement.
if ( (t-1) >= s) && (s >= (L+l)) %calculates the
probability at n
x = sum(PotPrev(t-s+L:t-1));
FalseAlarmProbAtTime_n = q x;
%testFA(n) = FalseAlarmProbAtTime_n,-
end
%calculates the power and false alarm probabilities
Beta = BetaPrev + FalseAlarmProbAtTime_n;
%Stores the Beta value into a file
PRINT TO FILE
%sets the next value of recursive probability to the
previous value.
PotPrev(1:t-1) = PotNext(1:t-1);
PotZeroPrev = PotZeroNext;
end % End of for loop of n the iterations,
fclose(fid);
7.2 C++ Simulation Program
7.2.1 Global variables and Configuration parameters:
The variables and the parameter in the window below are used by both Fusion
Center and Sensors. Few variables are used to do calculation and few are used to
maintain the synchronization between the Fusion Center and the Sensor.
54


The following variables are used in both Fusion Center and Sensor algorithms.
float PROCESS_P = 0.01;
float PROCESS_Q = 0.05;
#define MUE 0.08
int FUSION_CENTER_CONTROL_REQ = 1;
int FOSION_CENTER_CONTROL_RESP_CONTINUE = 2;
int FUSION_CENTER_CONTROL_RESP_STOP = 3;
static int fusionControllerRequestValue = -1;
int g_timer = 0; //Digital clock variable
float g_Process = PROCESS_P; //Initial process
#define g_maxNumberOfSensors 2 // Number of Sensors connected to FC
static int fusionControllerResponseValue[g_maxNumberOfSensors+1];
//Array to store the test function values calculated by the Sensor
double sensorValue[g_maxNumberOfSensors];
double sensorPrevValue[g_maxNumberOfSensors];
static int sensorExitStateCounter = 0;
static int FcExitState= -1;
static int sensorCounter = -1;
typedef struct
{
int s_thrNumber;
} DATA;
void resetFcRespValue()
{
for (int i = 1; i <= g_maxNumberOfSensors; i++)
{
fusionControllerResponseValue[i] = -1;
}
return;
}
7.2.2 Method reportToFusionCenter
The reportToFusionCenter function is called by all Sensors. This function
counts the Sensors that have completed the test function calculation at time n
and is ready to send their output to Fusion Center. Once all the Sensors
55


complete the calculation at time n, the function sends the Sensors request to
Fusion Center by changing the parameter value. In this function, MUTEX lock
feature of the POSIX platform is used so that all the Sensors do not access the
counter variable at the same point on time. The MUTEX lock function blocks
static bool reportToFusionCenter(int arglnstanceNumber)
{
pthread_mutex_lock(Sdocker);
if (counter < g_maxNumberOfSensors)
{
counter++;
}
else
{
counter = 1;
resetFcRespValue();
while (fusionControllerRequestValue != -1);
fusionControllerRequestValue = FUSION_CENTER_CONTROL_REQ;
}
pthread_mutex_unlock(&locker);
return true;
J____________________________________________________________________
all sensors (thread) at a time until the locked Sensor unlocks the MUTEX lock.
The MUTEX lock feature will not allow other Sensor(s) to access the counter
variable. When one Sensor is locked, all other Sensors will be waiting for the
mutex lock to be released.
7.2.3 Method reportToSensors
The reportToSensors function is used by Fusion Center to send the Fusion Center
response (feedback) to all the Sensors at the same time. Once the Fusion Center
calls this function it releases all the Sensors from wait and Sensors will start
calculation. When all the sensors start the next cycle, then Fusion Center will go
to wait state.
56


static bool reportToSensors(int argSensorValue)
{
for (int i = 1; i <= g_maxNumberOfSensors; i++)
{ while(fusionControllerResponseValue[i] != -1); }
for (i = 1; i <= g_maxNumberOfSensors; i++)
{
if (fusionControllerResponseValue[i] == -1)
{
fusionControllerResponseValue[i] = argSensorValue;
} else {
while(fusionControllerResponseValue[i] != -1) ;
} }
return true;
}
7.2.4 Method waitForFusionCenterResponse
static bool waitForFusionCenterResponse(int argSensorNumber)
{
pthread_mutex_lock(&syncLocker);
if (sensorCounter == -1)
{
sensorCounter = 1;
for (int i = 1; i <= g_maxNumberOfSensors; i++)
{
sensorSync[i] = 0;
}
}
pthread_mutex_unlock(&syncLocker);
while(sensorSync[argSensorNumber] == 1);
pthread_mutex_lock(&locker);
57


while(fusionControllerResponseValue_temp[argSensorNumber] == -1);
if (sensorCounter < g_maxNumberOfSensors)
{
if (sensorS yncfargSensorNumber] == 0)
{
sensorCounter++;
sensorSync[argSensorNumber] = 1;
}
else
{
while(sensorS yncfargSensorNumber] == 1);
sensorS yncfargSensorNumber] = 0;
}
}
else
{
if (fusionControllerResponseValue_temp[argSensorNumber] !=
FUSION_CENTER_CONTROL_RESP_STOP)
{
fiisionControllerResponseValue_temp[argSensorNumber] = -1;
}
for (int i = 1; i <= g_maxNumberOfSensors; i++)
{
sensorS yncfi] = 0;
}
}
pthread_mutex_unlock(&locker);
}
58


7.2.5 Method reportSensorExitToFc
void reportSensorExitToFc(int argSensorNumber)
{
static pthread_mutex_t syncLocker;
pthread_mutex_lock(&syncLocker);
sensorExitStateCounter++;
pthread_mutex_unlock (&syncLocker)
#endif
59


case 1:
{
if (loopCounter == 0)
{
pthread_mutex_lock(&syncLocker) ;
for (int i = 1; i <= g_maxNumberOfSensors; i++)
{
fusionControllerResponseValue[i] = -1;
}
fusionControllerRequestValue =
FUSION_CENTER_CONTROL_REQ;
loopCounter++;
pthread_mutex_unlock(&syncLocker) ;
}
if (fusionControllerResponseValue[argSensorNumber] ==
FUS I ON_CENTER_CONTROL_RES P_STOP)
{
return;
}
continue;
}
} // switch
} // whiled)
return;
)_________________________________________________________________________
7.2.6 Method waitForSensorsResponse
The waitForSensorsResponse function is called by Fusion Center. This function
waits till all the Sensors sends their request at time n and then transfers the control
to Fusion center at time n for further calculation.
bool waitForSensorsResponse()
{
while(fusionControllerRequestValue == -1) ;
fusionControllerRequestValue = -1;
return true;
7.2.7 Method getRandomNumber
The getRandomNumber function will return the random number as generated by
the inbuilt rand function.
60


//Generated and returns a random number for uniform distribution.
double getRandomNumber()
{
static pthread_mutex_t locker;
pthread_mutex_lock(&locker);
if (checkFlag == false)
{
checkFlag = true;
seed = time();
srand(seed);
}
randomNumber = (double)((double) rand()/(double) (RAND_MAX));
printf("\nRand Max [%d] and Random Number [%d]",
RAND_MAX,randomNumber);
return randomNumber;
}//End of getRandomNumber().
7.2.8 Method getProcessChangeValue
The input data to the Sensors are generated initially by PROCESS_P and after
some point of time the data generating process changes to PROCESS_Q. The
process change from PROCESS_P to PROCESS_Q is random and is created by
the function getProcessChangeValue.
long getProcessChangeValue()
{
static long processChange = -1;
if (processChange == -1)
{
processChange = (long)-((1/MUE) log(l getRandomNumber()));
}
return processChange;
7.2.9 Method sensor Function
The sensorFunction method implements the functionality of the Sensors. This
function calculates the test function value as given by 5.1. The calculation will go
on till the sensor detects the change in process. At each loop cycle the sensor
reports to Fusion Center and waits for its response. If the sensor decides for
61


process change, it exist the loop and waits for Fusion Center to decide. If the
Fusion Center detects the change before the Sensors, then the Sensor stops its
calculation in-between and exits upon getting the stop response from the Fusion
Center. This function will be running in parallel on many threads (as many as the
number of Sensors). If one of the thread (Sensor) exit the loop by detecting the
change in process, then other threads (Sensors) will continue with their calculation
till they detect the change. This kind of programming has helped to create
independent identical sensors placed in identical stochastic environments. Once
the change has been detected by Sensors and Fusion Center, the Sensor will print
the values of the final decision results of all the Sensors.
//Returns the decision of the sensor after running the algorithm,
void* sensorFunction(void* argDataPtr)
{
DATA* dataPtr = (DATA*)argDataPtr;
int threadNumber = dataPtr->s_thrNumber;
printf("\nSensors [%d]Threshold Value :%d", threadNumber,threshold);
retVal = waitForFusionCenterResponse(threadNumber);
cout << endl << "Sensor::Ready to Start Sensor Functionality. "
<< "Sensor Number : << threadNumber << endl;
62


while(testFunction[index] < threshold)
{
sensorValue[threadNumber] = testFunction[index];
retVal = reportToFusionCenter(threadNumber);
if (retVal != true)
{
cout << endl << "Sensor::Failed to Send FC Request. "
<< "Sensor Number : << threadNumber << endl;
}
else
{
retVal = waitForFusionCenterResponse(threadNumber);
{
if (fusionControllerResponseValue [threadNumber] ==
FUSION_CENTER_CONTROL_RESP_STOP)
{ break; }
index++;
if(getRandomNumber() < g_Process)
x = 1;
else
x = 0 ;
float updateStep = 0.0;
float newTestFunction = 0.0;
updateStep = (VARIABLE_S_VALUE x) VARIABLE_L_VALUE ;
newTestFunction = testFunction[index-1] + updateStep;
if(newTestFunction > 0)
testFunction[index] = newTestFunction;
else
testFunction[index] = 0;
sensorValue[threadNumber] = testFunctionfindex];
sensorPrevValue[threadNumber] = testFunction[index-1];
}//End of While.
63


cout << endl << "Sensor::A11 Sensors exited. Recieved STOP from
FC. "
< < endl;
pthread_exit(0);
}//End of sensorFunction().
7.2.10 Method getAlphaValue and getBetaValue
The false alarm (alpha) and power (beta) values were calculated using the matlab
program in the previous sections. The alpha and beta values are used to calculate
the updating step in Fusion Center as can be evident from 4.6. The alpha and beta
values is stored in a text file by matlab program which is accessed to read the
values for calculations.
bool getAlphaValue(
doubles argAlphaValue, doubles argAlphaPrevValue,
const bool argCloseOpenFile)
{
if ((argCloseOpenFile == true) SS (fdStatus != 0))
{
fileFd.close();
argAlphaValue = alphaValue;
argAlphaPrevValue = alphaPrevValue;
return true;
}
64


bool getBetaValue( doublet argBetaValue, doublet argBetaPrevValue,
const bool argCloseOpenFile)
{
if ((argCloseOpenFile == true) tt (fdStatus != 0))
{
fileFd.close();
argBetaValue = betaValue;
argBetaPrevValue = betaPrevValue;
return true;
}
7.2.11 Method getSummationOfProductl and getSummationOfProduct2
65


The updating step is split in to many parts and each part is calculated separately so
that the implementation as well as the picture will be clear. The
getSummationOfProductl and getSummationOfProduct2 functions calculate
^dlnl){l-d(n^)and ^(l-rf^Xl-rf^,) summations respectively.
;-i i-i
double getSummationOfProductl()
{
double sumOfProduct = 0.0;
for(int i=l; i<=g_maxNumberOfSensors; i++)
{
double sensorValuel = (double) (sensorValue [i]);
double sensorValue2 = (double)(1.0 sensorPrevValue[i]);
cout << endl << "FC::SensorValue and SensorPrevValue : "
<< sensorValuel << " " << sensorValue2 << endl;
sumOfProduct += (double)(sensorValuel sensorValue2);
}
return sumOfProduct ;
}
double getSummationOfProduct2()
{
double sumOfProduct=0;
for(int i=l; i<=g_maxNumberOfSensors; i++)
{
double sensorValuel = (double)(1.0 sensorValue[i]);
double sensorValue2 = (double)(1.0 sensorPrevValue[i]);
sumOfProduct += (double)(sensorValuel sensorValue2);
}
return sumOfProduct ;
}
66


7.2.12 Method FusionCenterLogValue
This function gets the alpha and beta value from getAlphaValue and getBetaValue
functions respectively and calculate the log part of the updating step as:
log
f Pi,

\ f
and log
(i-a')i(i-^r
Pn 10-0,
where pJn = # -; j = 1 -1 and pn=an-an_}.
This function is called by Fusion Center function during the calculation of the
updating step.
bool FusionCenterLogValue(doubles argResult, const int
argLogValueCheck)
{
if(argLogValueCheck == 1)
{
if (getAlphaValue(alpha, alphaPrev, false) == false)
{
argResult = -1;
return false;
}
if (getBetaValue(beta, betaPrev, false) == false)
{
argResult = -1;
return false;
}
argResult = (double)(((beta betaPrev)/(1.0 betaPrev)) /
((alpha alphaPrev)/(1.0 alphaPrev)));
}
if(argLogValueCheck == 2)
{
argResult = (double)(((1.0 beta)/(1.0 betaPrev)) /
((1.0 alpha)/(1.0 alphaPrev)));
}
return true;
}
7.2.13 Method createProcessChange
The process change from PROCESS_P to PROCESSQ is carried out by this
function. The getProcessChange function would have calculated the time when
the process will change. This process will be running continuously till the process
67


change time is reached and at the calculated process change time, the
PROCESS_P is changed to PROCESS_Q.
7.2.14 Method getFirstTermOfUpdateStep and getSecondTermOfUpdateStep
The updating step is split in to 3 parts. The first part is zero since the number of
Sensors considered is 2, the second and third part is calculated in the
getFirstTermOfUpdateStep and the getSecondTermOfUpdateStep functions.
These functions call the FusionCenterLogValue, getSumationOfProductl and
getSumationOfProduct2 functions and calculate the second and third part of the
update step of Fusion Center.
bool getFirstTermOfUpdateStep(doubled argFirstTermOfUpdateStep)
{
double loglResult = 0.0;
if (FusionCenterLogValue(loglResult, 1) == false)
{
return false;
}
double numbSensorFraction = (double)(1.0/g_maxNumberOfSensors);
double summationOfProductl = (double)getSummationOfProductl0;
double loglValue = (double)loglO(loglResult);
argFirstTermOfUpdateStep = (double)(numbSensorFraction *
summationOfProductl loglValue);
return true;
}
68


bool getSecondTermOfUpdateStep(doubled argSecondTermOfUpdateStep)
{
double log2Result = 0.0;
if (FusionCenterLogValue(log2Result, 2) == false)
{
return false;
}
double numbSensorFraction = (double)(1.0/g_maxNumberOfSensors);
double summationOfProduct2 = (double)getSummationOfProduct2();
double log2Value = (double)loglO(log2Result) ;
argSecondTermOfUpdateStep = (double)(numbSensorFraction *
summationOfProduct2 log2Value);
return true;
}
7.2.15 Method fusionCenter
The fusionCenter function is started by the Main program. As the thread for fusion
center is started it sends the start response to all sensors so that all the Sensors will
start at the same point of time. After all the Sensors sent the request to the Fusion
Center, the Fusion Center starts calculating the test function at time n. Once the
calculation is complete at time n, the Fusion Center sends the response of
continue/stop depending on the decision Fusion Center took at time n to the
Sensors. When the Fusion Center decides the process has changed, it send the
response to stop the Sensors and exit the thread printing the result of the Fusion
Center decision on the screen. The result of the decision can be a false alarm too.
Hence the details of the decision is displayed.
69


void* fusionCenter(void* argPtr)
{
resetFcRespValue();
double updateStepOfShift;
double firstTermOfUpdateStep;
double secondTermOfUpdateStep;
int sensorRespValue = FUSION_CENTER_CONTROL_RESP_CONTINUE;
createProcessChange() ;
reportToSensors(sensorRespValue);
float testFunctionOfFC = 0.0;
float fusionCenterValue = 0.0;
float fusionCenterPrevValue = 0.0;
int x = 0 ;
static long threshold = THRESHOLD_VALUE;
while(testFunctionOfFC < threshold) { if (sensorExitStateCounter != g maxNumberOfSensors) { waitForSensorsResponse() ; }
fusionCenterValue = testFunctionOfFC;
if(getRandomNumber() < g_Process) x = 1; else x = 0;
float updateStepOfShift = 0.0; float newTestFunctionOfFC = 0.0;
if (getFirstTermOfUpdateStep(firstTermOfUpdateStep) != { break; } true)
if (getSecondTermOfUpdateStep(secondTermOfUpdateStep) { break; } = true)
updateStepOfShift = firstTermOfUpdateStep + secondTermOfUpdateStep; newTestFunctionOfFC = fusionCenterPrevValue + updateStepOfShift;
70


if(newTestFunctionOfFC > 0)
testFunctionOfFC = newTestFunctionOfFC;
else
testFunctionOfFC = 0;
fusionCenterPrevValue = fusionCenterValue;
fusionCenterValue = testFunctionOfFC;
int sensorRespValue = FUSION_CENTER_CONTROL_RESP_CONTINUE;
if (sensorExitStateCounter != g_maxNumberOfSensors)
{
reportToSensors(sensorRespValue);
}
} //End of While.
reportToSensors(FUSION_CENTER_CONTROL_RESP_STOP);
cout<< endl << "FC:iprocess acting is : " << g_Process << endl
<< Process Q is : << PROCESS_Q;
if (g_Process == PROCESS_Q)
{
printf("\nFC::Process was changed at timer %d and it was detected \
at time %d\n", getProcessChangeValue(),g_timer);
} else {
printf("\nFC::Detection is a FALSE ALARM.\n");
}
printf("\nFC::Change detected by FC at test function value: %f",
testFunctionOfFC) ;
printf("\nFC::Time at detection is: %d\n", g_timer);
cout << endl << "Exiting Fusion Center." << endl;
FcExitState = 1;
pthread_exit(0) ;
return NULL;
}
7.2.16 Main Program
The Main is the heart of the detection program. The Main creates the Fusion
Center and all the Sensor threads. Main also maintains that all the threads run
parallel to each other. The threads will report to Main before exiting. When all the
threads exit, the Main will end the program.
71


int main(int argc, char* argv[])
{
pthread_t tid[g_maxNumberOfSensors+1];
pthread_attr_t tattr;
int retVal = -1;
DATA dataBuf[g_maxNumberOfSensors+1]; // FC + Sensors
retVal = pthread_attr_init(&tattr);
int i = 0;
int policy = SCHED_FIFO; // SCHED_FIFO; SCHED_RR;
struct sched_param param;
param.sched_priority = 3;
pthread_attr_setdetachstate(&tattr,PTHREAD_CREATE_JOINABLE);
retVal = pthread_create (Sctid [i] &tattr,
fusionCenter, (void*) SidataBuf [i] ) ;
pthread_setschedparam(tid(i], policy, ¶m);
for (i = 1; i <= g_maxNumberOfSensors; i++)
{
dataBuf[i].s_thrNumber = i;
pthread_attr_setdetachstate(&tattr,PTHREAD_CREATE_JOINABLE);
retVal = pthread_create (&tid [i] Sctattr,
sensorFunction, (void*) SidataBuf [i] ) ;
pthread_setschedparam(tid[i], policy, ¶m);
}
int status[g_maxNumberOfSensors+l];
for (i = 0; i < g_maxNumberOfSensors+1; i++)
{
pthread_join (tid [i] (void**) Scstatus (i]) ;
}
printf("\nAll threads exited.\n");
}//End of main().
72


References
[1] E. S. Page, Continuous Inspection Schemes, Biometrika, Vol. 41, pp. 100-
115, 1954.
[2] E. S. Page, A Test for a Change in a Parameter occurring at an unknown
point, Biometrika, Vol. 42, pp. 523-527, 1955.
[3] G. Lorden, Procedures for Reacting to a Change in Distribution, Ann. Math.
Statist., vol. 42, pp. 1897-1908, 1971.
[4] Rakesh K. Bansal and P. Papantoni-Kazakos. An Algorithm for Detecting a
Change in a Stochastic Process, IEEE Trans. Commun., vol. IT-32, No. 2, pp.
227-235, 1986.
[5] Anthony Burrell and P. Papantoni-Kazakos. Extended Sequential Algorithms
for Detecting changes in Acting Stochastic Processes, IEEE Trans. On Systems,
Man, and Cybernetics, Vol. 28, No. 5, Sept. 1998, pp. 703-710.
[6] R.R. Tenney and N.R. Sandell, Jr., Detection with distributed sensors, IEEE
trans. Aerospace Electron. Syst., vol. AES-17, no. 4, pp. 501-510, July 1981.
[7] Z. chair and P.K. Varshney, Optimal data fusion in multiple sensor detection
systems, IEEE Trans. Aerospace Electron. Syst., vol. AES-22, no. 1, pp. 98-101,
Jan. 1986.
[8] Z.B. Tang, K.R. Pattipati, and D.L. Kleinman, An algorithm for determining
the decision thresholds in a distributed detection problem, IEEE Trans. Syst. Man
Cybem., vol. SMC-21, no. 1, pp. 231-237, Jan./Feb. 1991.
[9] J.N. Tsitsiklis and M. Athans, On the complexity of decentralized decision
making and detection problems, IEEE Trans. Automatic Contr., vol. AC-30, no.
5, pp. 440-446, May 1985.
[10] D. Kazakos and P. Papantoni-Kazakos, Detection and Estimation. New York:
Computer Science Press, 1990.
73


[11] C.C. Lee and J.J. Chao, Optimum local decision space partitioning for
distributed detection, IEEE Trans. Aerospace Electron. Syst., vol. AES-24, no. 4,
pp. 366-376, July 1988.
[12] D. Pados, K.W. Halford, D. Kazakos, and P.Papantoni-Kazakos, Distributed
Binary Hypothesis testing with feedback, IEEE
[13] Anthony Burrell and P. Papantoni-Kazakos, Data Fusion in the Sequential
Detection of change, CISS 2006, Proceedings, Princeton, N. J., March 2006.
74