32 2. BackgroundThe Tracking problem, the search for the best matching sequence sT1for a given x1T,has been shown to be addressable with a number of different algorithms. The firstone shown, was derived from the concepts of Hidden Markov Models . The modelassumptions of a HMM , especially the memorylessnes due to the Markov property,make use of efficient dynamic programming algorithms for finding s1Tpossible. Thecomputations in the Viterbi Algorithm were further simplified by moving the prob-abilities into logspace and assuming a constant pooled variance on the emissionprobabilities. The final computations contain only summations, memory lookupsfor stored probabilities and a distance calculation between xtand the stored RSSIvalues of the radio propagation model. Since the computations for Q( s, t) are sim-ple, the implemented system can process around 5 · 106Q( s, t) per second on currenthardware. The proposed Pruning technique leads to a further speed-up of aroundone order of magnitude.The other two presented algorithms are the LMSE and the Particle Filter. Thelatter is similar to the HMM as it is also derived from the state space model offigure 2.11. Whereas, the LMSE approach ignores the additional knowledge givenby the history of the RSSI readings, the HMM/PF respect the sequential natureof the problem by modelling transition probabilities. As becomes observable duringthe later evaluation of the three algorithms, that incorporating this knowledge aboutthe stochastic process leads to significantly reduced localization error rates.The Positioning problem will be understood as a special case of the Tracking prob-lem. The same algorithmic designs are used for finding solutions. Although in theworst case, a positioning attempt contains only data from one time frame withoutexploitable history. In this special case the LMSE approach does represent the mostefficient solution. But it can be assumed, that in the presented use-case of Wi-Fibased positioning, the signal stream is easily adaptable to employ sequential data.