Evidence Theory Enabled Quickest Change Detection Using Big Time-Series Data from Internet of Things

Traditionally in sensor networks and recently in the
Internet of Things, numerous heterogeneous sensors are deployed
in distributed manner to monitor a phenomenon that often can be
model by an underlying stochastic process. The big time-series
data collected by the sensors must be analyzed to detect change
in the stochastic process as quickly as possible with tolerable
false alarm rate. However, sensors may have different accuracy
and sensitivity range, and they decay along time. As a result,
the big time-series data collected by the sensors will contain
uncertainties and sometimes they are conflicting. In this study, we
present a framework to take advantage of Evidence Theory (a.k.a.
Dempster-Shafer and Dezert-Smarandache Theories) capabilities of
representing and managing uncertainty and conflict to fast change
detection and effectively deal with complementary hypotheses.
Specifically, Kullback-Leibler divergence is used as the similarity
metric to calculate the distances between the estimated current
distribution with the pre- and post-change distributions. Then mass
functions are calculated and related combination rules are applied to
combine the mass values among all sensors. Furthermore, we applied
the method to estimate the minimum number of sensors needed to
combine, so computational efficiency could be improved. Cumulative
sum test is then applied on the ratio of pignistic probability to detect
and declare the change for decision making purpose. Simulation
results using both synthetic data and real data from experimental
setup demonstrate the effectiveness of the presented schemes.

Authors:

• Hossein Jafari
• Xiangfang Li
• Lijun Qian
• Alexander Aved
• Timothy Kroecker

Keywords:

• CUSUM
• evidence theory
• KL divergence
• quickest change detection
• time series data.

References:

[1] Basseville, M. and Nikiforov, I. V. Detection of Abrupt Change Theory
and Application, Englewood Cliffs, NJ: Prentice Hall, 1993.
[2] Poor, H. V. and Hadjiliadis, O. Quickest Detection, New York: Cambridge
University Press, 2008.
[3] Page, E. S. Continuous inspection schemes, Biometrika, 1954.
[4] Shiryaev, A. N. On Optimum Methods in Quickest Detection Problems,
Theory of Probability and Its Applications 8: 22–46, 1963.
[5] A. G. Tartakovsky, B. Rozovskii, R. Blazek, and H. Kim, A Novel
Approach to Detection of Intrusions in Computer Networks via Adaptive
Sequential and Batch-Sequential Change-point Detection Methods, IEEE
Trans. Sig. Proc., vol. 54, no. 9, pp. 3372–3382, Sep. 2006.
[6] J. S. Baras, A. Cardenas, and V. Ramezani, Distributed Change Detection
for Worms, DDOS and Other Network Attacks, Proc. American Cont.
Conf. (ACC), Boston, MA, pp. 1008–1013, 2004.
[7] Husheng Li, Chengzhi Li and Huaiyu Dai, Quickest spectrum sensing in
cognitive radio, Information Sciences and Systems. CISS. 42nd Annual
Conference on, Princeton, NJ, pp. 203–208, 2008.
[8] B. Khaleghi, A. Khamis, F. O. Karray, and S. N. Razavi, Multisensor
data fusion: A review of the state-of-the-art, Information Fusion, vol. 14,
no. 1, pp. 28–44, 2013.
[9] Tartakovsky, A. G. and Veeravalli, V. V. Asymptotically optimal quickest
change detection in distributed sensor systems, Sequential Anal. 27 pp.
441–475, 2008.
[10] Mei, Y. Efficient scalable schemes for monitoring a large number of
data streams, Biometrika 97 pp. 419–433, 2010.
[11] Yao Xie and David Siegmund. Sequential multi-sensor change-point
detection, in The Annals of Statistics, Vol. 41, No. 2, pp. 670–692, 2013.
[12] G. Shafer, Perspectives on the theory and practice of belief functions,
International Journal of Approximate Reasoning, vol. 4, no. 5, pp.
323–362, 1990.
[13] F. Smarandache and J. Dezert, Advances and Applications of DSmT for
Information Fusion, in American Research Press, Rehoboth, vol. 1-2,
2006.
[14] R. R. Yager and L. Liu, Classic Works of the Dempster-Shafer Theory
of Belief Functions, in American Research Press, Rehoboth, vol. 2, ch. 1,
pp. 3–68, 2006.
[15] P. Smets, Constructing the pignistic probability function in a context of
uncertainty, Uncertainty in Artificial Intelligence, Vol. 5, pp. 29–39, Aug
2004.
[16] J. Sudano, Yet Another Paradigm Illustrating Evidence Fusion (YAPIEF),
Proc. of Fusion, Florence, July 2006.
[17] T. L. Lai, Information bounds and quick detection of parameter changes
in stochastic systems, in IEEE Transactions on Information Theory, vol.
44, no. 7, pp. 2917–2929, Nov 1998.
[18] I. F. Akyildiz, W. Lee, M. C. Vuran, and S. Mohanty, Next
generation/dynamic spectrum access/cognitive radio wireless networks:
A survey, Comput. Netw., vol. 50, no. 13, pp. 21272159, Sep. 2006.
[19] S. Haykin, Cognitive Radio: Brain-Empowered Wireless
Communications, IEEE JSAC, vol.23, no.2, pp.201-20, Feb. 2005.
[20] T. Yucek and H. Arslan, A survey of spectrum sensing algorithms
for cognitive radio applications, in IEEE Communications Surveys &
Tutorials, vol. 11, no. 1, pp. 116-130, First Quarter 2009.