4.3. Positioning and Tracking 49Figure 4.3 Overview over the different subcomponents of the Localizer and theinteractions with the devices. The Localizer can either use a HMM , a PF or LMSEfor the core algorithmics.Collecting measurements and evaluating them has been done asynchronously duringevaluation of the system. This means, that the measurement sequences were storedto form an evaluation corpus that was afterwards analysed. In the online trackingmode, the measurements are synchronously processed and the incrementally reportedsequence of locations is temporarily stored. The devices will pull their correspondinglocalization result by accessing the Webservice-API and visualize them in a browser.4.3.1 Hidden Markov Model The localization problem under the HMM approach is given by finding the most likelysequence of hidden states in a HMM for the observed sequence of measurement. Ahidden state of the HMM represents the unknown location of the device for a giventime frame. The observed emission of such a state is given by a set of RSSI readingsfor that time frame.There are a large number of possible location sequences. If the number of measure-ments is given by T and the number of possible locations or hidden states is given byS then there are STpossible location sequences that are possible localization results.At the utilized raytracer resolution in the UMIC scene with a voxel size of 20 cm,the rasterization of the 3D-space leads to 2 · 106Voxels that represent the maximumresolution of the hidden state space. So with T= 10, this leads to around 1063pos-sible localization results. The number of hidden states can be reduced by combiningthem into larger cubes leading to a state space with a lower resolution. This can bedone by combining a number of adjacent voxels for each dimension to a hidden statewith a larger edge size. But a brute force search for the most likely sequence of 10hidden states combined of 3 voxels with an edge size of 60 cm still needs to inspect1048candidate sequences. And that remains an intractable computational problem.Therefore, the problem is reduced to a first-order Markov Model and the Viterbialgorithm is utilized for finding the most probable state sequence efficiently. Byusing a first-order Markov Model the Viterbi algorithm processes S states for each