Hidden Markov Models - Traffic Modeling and Subspace Methods

Sofia Andersson

Centre for Mathematical Sciences
Mathematical Statistics
Lund Institute of Technology
2002

ISBN 91-628-5253-1
LUTFMS--1018--2002

Abstract:

The main motivation for this thesis, however not the only one, is the search for models for traffic in telecommunication networks. Traffic characterization and modeling are of great importance in the analysis and dimensioning of communication systems. During the last decades we have experienced an explosive growth of our telecommunication networks. New important properties, both on macroscopic and microscopic time scales, have been revealed. These new features have a profound impact on network performance and thus needs to be taken into consideration. In Paper A we study the microdynamics of some data sets of traffic on the link level. Our approach is Poissonification, a kind of random local smoothing of a point process. The idea is to use Poissonification on empirical data materials in order to find the (small) time scale where the process switch from a doubly stochastic to a homogeneous behavior.

The models used and studied are hidden Markov models (HMMs). In Paper B we study specifically the Markov-modulated Poisson process (MMPP). In fitting an MMPP to some sets of observed traffic we concentrate on maximum likelihood (ML) methods, but also use moment methods. The ML methods are computationally more complex but concerning performance they prove to be superior to moment methods.

As a possible candidate for a method to combine the simplicity of the moment methods, and the accuracy of the likelihood methods, we have subspace methods. To be able to use subspace methods for HMMs the process needs to be represented in state space form. In Paper C of this thesis we show that it is possible to represent an HMM as a state space system in innovation form. This reformulation is complicated by the non-minimality within the state space representation of the HMM. The reformulation involves deriving solutions to algebraic Riccati equations which are usually treated under minimality assumptions.

In Paper D we develop a subspace identification algorithm especially designed for HMMs. Some of the crucial assumptions on the system, needed for the subspace methods to work, fail to be met by HMMs and thus commonly used methods are not directly applicable. Therefore we need to consider each of the steps in existing algorithms with regard to the specific conditions of the HMM and in this way develop a new algorithm. Consistency is proved of this algorithm. However, we manage to estimate the system parameters only seen as a projection on a certain subspace and only up to a similarity transformation.

Keywords:

hidden Markov model, Markov-modulated Poisson process, traffic analysis, Poissonification, likelihood estimation, state space

representation, Riccati equation, subspace identification