The idea surged thanks to a lab project in which we used ZigBee boards to implement the triangulation technique. In this project we used three of the boards as reference in order to calculate the unknown position of a third board based on the intensity of the received signal at each point. The idea is quite simple, knowing the signal attenuation through the space and the power of the emitted signal, you can calculate the distance that the signal has travelled through air measuring the power of the received signal. As you can see in the “*figure 1*“, knowing the distance of the object to three different reference points, we can trace three circles and locate the object as the intersection of these.

After researching the available technologies, measuring the RSSI (“*Received Signal Strength Indicator*“) is the most used technique to calculate the distance since it can be implemented with all the devices on the market. Errors on the estimated distance are frequent since signal attenuation is hard to estimate, there are manufacturing deviations and the signal suffers reflections. Therefore, is really improbable that our calculations will output the exact position of the object, we’ll have an estimate position that differs from the real one.

Although there are different methods to calculate the position, after several simulations and measuring errors, the Centroid and the Max-Min techniques returned the best accuracy. “*Figure 2 a)*” represents the Centroid technique which calculates the center of gravity of the triangle formed between the circles. “*Figure 2 b)*” represents the Max-Min technique which consists on calculating the center of gravity of the rectangular shape formed by the squares with the inscribed circles.

*Figure 2 a):*Centroid technique

*Figure 2 b)*: Max-Min technique

In “*figure 3*” we can see the absolute error of those two techniques based on the uncertainty of the path loss coefficient. We are representing the distance, in meters, between the original location and the estimated position versus the percentage error between the real signal attenuation and the considered signal attenuation.

*Figure 3*: Absolute position error versus considered path loss error for each technique

As you can see, the centroid technique is more accurate for small values of path loss error while the Max-Min method is appropriate for bigger values of path loss error. As a result, I have created a new method combination of both which outputs the smallest error in both circumstances, represented in green in the figure.

After generating the localization algorithm, we represent the absolute error outputted by it versus the amount of fixed nodes in the map, for several values of uncertainty. In “*figure *4″ we can see that the measured errors remains stable after implementing 100 fixed nodes in the map of 2500 square meters, this means a density of 1 node each 25 square meters.

*Figure 4:*Absolute position error versus density of fixed nodes in a map of 2500 square meters

Using this value as reference we realize several simulations for a real parking environment to discover big deviations between real location and the estimated position. Based on the simulations, a mesh of 180 nodes must be installed in a parking of 2700 square meters in order to achieve an efficient level of accuracy. This means that we need a density of one node each 15 square meters to implement the indoor localization system. We represent in “*figure 5*” the estimated trajectory (the line with stars) versus the real trajectory (the dotted line).

*Figure 5:*Simulation of vehicle trajectories estimation in garage

The results are quite satisfying and I consider that the real system can be implemented and tested with this density of nodes in the parking environment. To finalize the experiment, I calculate the cost of implementation of this system using XBee S2C modules, a 12V power supply for each fixed node, one central server and personalized emitter boards that are supplied to entering cars, at around €14000. Keeping in mind that this price is for a parking of 2500 square meters, it results a price of €5.6 per square meter.

To sum up the project, we conclude that the implementation of one system like this is feasible and cheap to be implemented in parking where profit form customers is obtained, like paid parking’s or shopping mall. Is also important to note that the bigger the parking is, the cheaper per square meter the implementation becomes. Lastly, as future investigation it will be nice to study how changing the distribution of the fixed nodes affects the accuracy of the system, this is, instead of installing them forming a square mesh, we may have better results installing a hexagonal or triangular mesh. It also would be useful to dynamically measure and adjust the loss coefficient alpha in different areas of the map.

Please find below the GitHub link to the code and the downloadable PDF file which is the original thesis I submitted to the faculty jury. Keep in mind that I studied at a Spanish university then the document is in Spanish and not translated.