Change Point Detection with Applications to Wireless Sensor Networks

Sammanfattning: In this thesis work we develop a new algorithm for detecting joint changes in statistical behavior of multiple, simultaneously recorded, signals. Such signal analysis is commonly known as multivariate change point (CP) detection (CPD) and is of interest in many scientific and engineering applications.First we review some of the existing CPD algorithms, where special attention is given to the Bayesian methods. Traditionally, many of the previous works on Bayesian CPD have focused on sampling based methods using Markov Chain Monte Carlo (MCMC). More recent work has shown that it is possible to avoid the computationally expensive MCMC methods by using a technique that is reminiscent of the forward-backward algorithm used for hidden Markov models. We revisit that technique and extend it to a multivariate CPD scenario where subsets of the monitored signals are affected at each CP. The extended algorithm has excellent CPD accuracy, but unfortunately, this fully Bayesian approach quickly becomes intractable when the size of the data set increases.For large data sets, we propose a two-stage algorithm which, instead of considering all possible combinations of joint CPs as in the fully Bayesian approach, only computes an approximate solution to the most likely combination. In the first stage, the time series are processed in parallel with a univariate CPD algorithm. In the second stage, a dynamic program (DP) is used to search for the combination of joint CPs that best explains the CPs detected by the first stage. The computational efficiency of the second stage is improved by incorporating a pruning condition which reduces the search space of the DP. To motivate the algorithm, we apply it to measurements of radio channels in factory environments. The analysis shows that certain subsets of radio channels often experiences simultaneous changes in channel gain.In addition, a detailed statistical study of the radio channel measurements is presented, including empirical evidence that radio channels exhibit statistical dependencies over long time horizons which implies that it is possible to design predictors of future channel conditions.