1.2. Localization Algorithms 3implemented to distribute the computational demanding search for the unknownparameters over an array of GPU-nodes. The procedure has been determined toyield adequate material parameters for the simulation of the signal distribution overthe 2 · 106voxel3resolution of the 8100 m2volume for UMIC scene.1.2 Localization AlgorithmsThe second topic of the thesis deploys these radio propagation models for the design,implementation and analysis of different localization algorithms. The algorithms ex-ploit the information provided by the propagation models and the available knowl-edge about the nature of the environment. For example, information about thestructure of the building is already available in the form of the scene geometry usedfor the PHOTON raytracer. From this geometry, for example the knowledge aboutunreachable zones in the location space can be derived. The algorithms were chosenby studying the related literature to this topic and by applying prior knowledgeof Bayesian pattern recognition principles to this field of research. The first of thethree analysed algorithms is a nearest neighbour based technique, named Least MeanSquared Error(LMSE), that was also used by the mentioned RADAR system. Thesecond is based on Hidden Markov Models(HMM ) and the third one uses a ParticleFilter(PF) based approach.All three techniques can be inferred from the Bayesian decision theory but only theHMM and the PF are conceptually related. The primary difference between theLMSE and the HMM/PF is rooted in its model assumptions that ignore the sequen-tial nature of the tracking problem. With respect to the scope of this thesis, thetracking problem is defined as follows: Given a sequence of RSSI readings the optimalsequence of locations has to be found. It is reasonable to assume that adjacent RSSIreadings are related due to constraints imposed by the physical world. Or spokenin the terms of probability theory: Temporal adjacent readings are not statisticallyindependent. The HMM and PF based approaches presented in this thesis makeexplicit use of these dependencies, whereas the LMSE does not and thereby retainsa simple structure4.The HMM and PF technique exploit the additional information contained in the timedriven sequentiality of the tracking problem. Both model the concept of movementfrom one location to another in successive steps. In terms of probability theory: Theyassume a conditional probability for moving to the location s under the conditionto come from location s which should be denoted as p( s| s)5. Furthermore, bothmake use of the radio propagation model to relate an RSSI measurement vector to alocation in space. This can be understood as the conditional probability to receivethe RSSI vector x at the location s. This probability is denoted as p( x| s). Andfinally, they combine these two probabilities iteratively for all measurements of theobserved sequence to predict the most probable sequence of positions. So where arethe differences, why care for both?3A 3D pixel, a discretized volume of space.4The simplicity of the LMSE makes it a valuable tool to evaluate the quality of radio propagationmodels with regard to the localization problem.5A location is understood to represent an abstract state from the search space of possiblelocations, therefore it is denoted as s instead of l.