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

Authors: Hossein Jafari, Xiangfang Li, Lijun Qian, Alexander Aved, Timothy Kroecker

Abstract:

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.

Keywords: CUSUM, evidence theory, KL divergence, quickest change detection, time series data.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1131213

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.