16 2. Background2.3 TrackingTracking is the generalization of the Positioning problem. Whereas Positioning is de-fined as a stationary localization problem, Tracking drops the immobility constraintby allowing the receiving device to move over time. The simplest approach for Track-ing is therefore the sequential execution of a Positioning algorithm with disregardto any structural dependency between the information at different timestamps. Butdoing so, does surely yield an inferior localization result, as the sequential nature ofthe tracking problem is a source of valuable information. Prior knowledge like themaximum walking speed, that is usable as a constraint on the maximum distancebetween two successive positioning results, can easily be exploited.It is also required to incorporate this source of information in order to offset for themuch larger search-space that is given by the Tracking problem. The search-spacefor the Positioning problem is linearly dependent on the resolution and the size ofthe modelled space. In the worst case that is a high resolution 3D space as usedin the UMIC scene, with around 2 · 106solutions representing cubes with edge size20 cm. In contrast, the solutions for the Tracking problem are sequences of locationswith an additional measurement specific resolution that determines the length ofthat sequence. This length T has an exponential impact on the size of the search-space. An input sequence of signal vectors x with T timeframes, represented as xT1,leads to a solutions sequence sT1. And if the representation of the space is made of Sdisjunct positions, this would induce STpossible solution sequences. Consequently,a brute force search, probably computationally tractable for the singular positioningproblem, has to be excluded as an algorithmic attempt for the Tracking case.There are two approaches to model the state space of possible locations. Either thespace is assumed to be rasterized or segmented into"spaces" of interest with someresolution factor for adjusting the granularity, or space is assumed to be dense withreal values for the two or three possible dimensions. The first approach leads modelsbased on Markov chains like Hidden Markov Models(HMM ). Since such models havea finite number of states, the computation of a solution involves making decisionsbetween different states by relying on the evaluation of their properties. A majorpart of this thesis studies different aspects of HMM based models.In contrast, in the second approach a position, given in real values, is updatedby some function configured with prior knowledge of the environment or of thebehaviour of the moving person. The evaluation of this function results in the next-best real valued position. Examples of this approach can be found in the form ofParticle Filters or in the different forms of Kalman Filters .2.3.1 Mobility ModelsThe different approaches for tackling the sequential nature of the tracking problemhave in common, that they use prior information of the shape of the environment orprior knowledge of the rules that a moving device has to obey. There are multiplesources for extracting such information.A deterministic mobility model can be employed, if the speed and acceleration of amoving device are available. Combining such information with the laws of physics,