Uppsala universitet
Change Point Detection with Applications to Wireless Sensor Networks

Markus Eriksson

PhD Thesis, Uppsala University, ISBN 978-91-513-0580-6,
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1777, 102 pages.

Dissertation in Electrical Engineering with specialization in Signal Processing, publicly examined in Room 80101, Ångström Laboratory, Uppsala on Friday May 10, 2019 at 08.30.

Thesis Opponent: Professor Idris Eckley, Lancaster University, GB.


Abstract and full-text in DIVA database


Paper copies of the thesis can be obtained from Signals and Systems Group, Uppsala University, Box 534, SE-75121 Uppsala, Sweden.


Abstract:
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.


| Entry in publ. list |
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors. All persons copying this information are expected to adhere to the terms and constraints invoked by each authors copyright. This work may not be reposted without the explicit permission of the copyright holders.