Time-Series Change Detection with Big IoT Data: An Evidence Theory Approach

—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 I. INTRODUCTION HE Internet of Things (IoT) is the internet-working of many physical devices such as smart sensors and vehicles, and providing them the capability of sending and receiving data. As a result, big time-series data are collected and exchanged. The collected data may be analyzed to detect changes and anomalies in the physical world that can be modeled as stochastic processes mathematically. Change point detection is a well-developed method to detect a change along a stochastic process [1]. Let us assume a sequence of observation from one sensor with known distribution. At unknown time an event happens and distribution of observation changes. The goal of change point detection is to detect and announce the true change with minimum delay subject to constraint that the rate of false alarm be small. This is also called Quickest Detection (QD) [2]. The early works of QD are done in quality control to detect a failure in manufacturing systems [3], [4]. So after detection of change, production line can stop to fix the problem and prevent the loss. There are many QD applications including intrusion detection in computer networks and security systems [5], [6], tracking, surveillance, health care (patient falling as an example), spectrum sensing in cognitive radio [7] and so on. These applications benefit from data fusion of multi sensors [8], where observations from several sensors aggregated and cooperated in different methods to detect an event. In reality, sensors are not perfect. In the sensor field, where the sensors installed to monitor an event, sensors provided by several manufacturers have different specifications, accuracy and sensitivity range. And their functionalities decay along the years. So we may not be certain about the value measured by those sensors. Finally besides all sensors related uncertainty metrics, environmental interference and noise can affect their accuracy and measurement. Based on [3] for sequence of observation from single sensor, cumulative sum test (CUSUM) can detect change in distribution with minimum delay while keeping false alarm rate low. Similarly for the multisensor applications that stream of data generated by sensors, several works are done based on QD to detect the change [9]–[11]. In this paper, we focus on stream of independent observations from N sensors aggregated in data fusion center as shown in Fig. 1. Maximum Likelihood Estimation (MLE) method is applied to estimate the distribution parameters of each sensor independently based on their most recent W observations (W called the sliding window size). Then Kullback-Leibler (KL) divergence method is used to find the distance between estimated distribution with pre- and post-change distributions. Following, related mass function values are calculated based on those distance values for each sensor and then to manage uncertainty, Dempster-Shafer combination rule (DST) is applied to combine the mass values among all N sensors [12]. In the case of high conflict value, Dezert-Smarandache combination rule (DSmT) is applied for more accuracy [13]. However, to improve the computational efficiency, we applied the method to estimate the minimum number of sensors needed to combine. In QD framework, instead of likelihood ratio in computing CUSUM test, we used ratio of related pignistic probabilities. These CUSUM values are compared to the predefined threshold value and the result is used as a metric to detect and announce the change point. We show that the presented method outperforms the traditional QD methods when uncertainties are high in practical situations. We start at Section II with presenting our model, including all the assumptions. In Section III, we give background information about KL divergence, Dempster-Shafer theory of evidence and Dezert-Smarandache theory (DSmT) of plausible and paradoxical reasoning. Then, we explain their related combination rules, belief, plausibility and pignistic probability. Following, we present the modified version of CUSUM test and estimation of minimum number of sensors needed to combine. Section IV shows simulation results for different models and compare their performance. For real data analysis section, Section V explains spectrum sensing application. At the end, Section VI concludes the paper and explains some of our ongoing researches to extend this work. II. MODEL In this work, it is assumed that there are N sensors monitoring an underlying stochastic process and they generate streams of data in parallel. It is also assumed that the observations from each sensor are independent and identically distributed (i.i.d.) with Gaussian distribution. Furthermore, we assume that the observations between different sensors are mutually independent as well. In this paper, we consider two cases with "ideal sensors" and "practical sensors", respectively. For the first case with "ideal sensors", we assume that sensor readings are accurate and all sensors have large sensitivity range and they are affected by the change [9]. As in most of the works of change detection in the literature [9]–[11], the distributions before change (p0) and after change (p1) are assumed to be known. Without loss of generality, p0 is Gaussian distribution with zero mean and unit variance, p0 ∼ N(0,1), and p1 has the same variance but different mean, p1 ∼ N(1,1). This case will serve as the benchmark to gauge the performance of the presented method for the "practical sensors" case. Although here we assumed that the variance does not change, but as we will explain in Section III, KL divergence considers change in both mean and variance as it is the case in practical applications. For the "practical sensors", we assume that the sensors are heterogeneous and their readings are inaccurate. Because the empirical data are available and the sensor readings can be calibrated, it is reasonable to assume that the distribution before change (p0) is known, p0 ∼ N(0,1). However, due Fig. 2 Hypotheses distributions including null, alternative and uncertainty to the heterogeneity of the sensors and the uncertainties in sensors' measurements, it is assumed that each sensor n after change may have different mean p1 ∼ N(μn,1) [11] (and generally different variance), although all the sensors are within their sensitivity range and the mean value μn is bounded. The null hypothesis (H0) is defined as no change in the distribution of the underlying random process, while the alternative hypothesis H1 denotes that change happens. The corresponding distributions are p0(x) ∼ N(μ0,σ02) and p1(x) ∼ N(μ1,σ12), respectively. In order to facilitate the uncertainties due to "practical sensors", we define p1/2(x) ∼ where μ1/2 = (μ0 + μ1)/2 and (σ02+σ12)/4. This new proposed hypothesis is a union between the two hypotheses H0 and H1 (H0 ∪H1). According to Fig. 2, p1/2(x) maximizes when p0(x) and p1(x) are equal and it diminishes when one of p0(x) or p1(x) dominates the other one. III. PROPOSED ALGORITHM AND ANALYTICAL STUDY In this section, the detailed procedures of the framework are illustrated and the corresponding analysis are given. A. Proposed Algorithm Fig. 1 shows the data flow from sensor field to data fusion center. In the sensor field, N sensors monitor an underlying random process independently and send their observations/readings to the fusion center. In the fusion center, firstly MLE method is applied to estimate mean and variance values. Then distance values are calculated based on or (1) Although KL divergence is asymmetric function ( D(q||p)), we use symmetric version defined by DKL(p||q): Sample readings from five sensors out of N sensors and the sliding window are shown in Fig. 3. At each time t, for each sensor i, MLE method is used to estimate the parameters of the observation distribution based on the most recent W data samples between t − W + 1 and t, where W is the sliding window size. W plays a major role and must be chosen carefully to address the tradeoff between estimation accuracy and detection delay. The estimated mean and variance based on W data samples y can be shown as: (4) (5) C. Combination of Data As stated in Section II, we consider two hypotheses H0, H1, and their union H0∪H1. The union hypothesis, H0∪H1, is called ignorance and

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.