| Positioning | |
Real time indoor location based service test bed
The purpose of this paper is to develop low cost and low power consumption Real Time Indoor Positioning
|
|
 |
|
|||||
 |
|
|||||
 |
|
|||||
EXPRIMENT RESULTS
This section conducts the static and dynamic experiments of the indoor positioning algorithms mentioned above, and these results are used to find the best indoor positioning algorithm for the RTIPS. To implement the indoor positioning tests, the classroom 5834 of the DAA building of NCKU is chosen as the experiment place. In this paper, the fingerprinting method based on the RSS is utilized to estimate the user location. Several positioning results are investigated by applying different matching algorithms, including the NN algorithm, the KWNN algorithm, and the probabilistic approach based on the kernel method. In addition, the particle filter is applied to improve the positioning performance, and furthermore the trade-off study between the positioning performance and the computation time are conducted as well.
To implement the indoor positioning system, the first step is to collect and build the positioning database for the positioning system. In this work, we attach 9 IRIS motes developed by Crossbow Inc. on the ceiling of classroom 5834 as the transmitters and divide the floor into 25 grid points. The size of each grid is 137.25 cm by 152.5 cm, and the separation distance between each sensor attached on the ceiling is 274.5 cm. The setup is shown in Figure 3.
Figure 3: The arrangement of the experimental setup.
In the static experiment, we visit all the grid points sequentially to perform the positioning test, and the number of the test samples is 67500 samples. The Cumulative Distribution Functions (CDFs) of the positioning errors by the NN algorithm and the KWNN algorithm with to 4 are shown in Figure 4.
Figure 4: The CDFs of the positioning errors by the NN algorithm and the KWNN algorithms for the static experiment.
In Figure 4, the NN algorithm has a 12% probability to make an exact estimation; however, it also has the worst performance in the maximum error bound. In this case, the maximum error of the NN algorithm is about 8.3 meters. If the indoor positioning system has higher accuracy requirement, then the NN algorithm would not be an appropriate option. In contrast, although the KWNN algorithm cannot make the exact estimation, the maximum error of the KWNN algorithm is less than that of the NN algorithm. For instance, as the value of K is set to 2, the maximum error is about 5.7 meter. As shown in Figure 4, one notes that the maximum error is reduced as the value of K increases, but the improvement diminishes as the value of K increases. Ni [9] and Wang [10] suggested that the or 4 yielded the best positioning results. Our experiment results are in accordance with the conclusions in [9] and [10]. To investigate the positioning performance improvement gained from the SIR particle filter, we choose K = 4 case to be integrated with the SIR particle filter; the estimations obtained by the KWNN algorithm are used as the input measurements of the SIR particle filter; the number of particles used in this experiment is 1,000. In Figure 4, the maximum positioning error is reduced to 4.3 meters by the use of the SIR particle filter. As a result, the SIR particle filter significantly improves the indoor positioning performance.
This paper also applies the probabilistic approach based on the kernel method to analyze the CDFs of the indoor positioning errors. The CDFs of the positioning errors with the probabilistic approach based on the kernel method are shown in Figure 5.
Figure 5: The CDFs of the positioning errors by the kernel method for the static experiment.
As shown in Figure 5, the exact estimations raises to 15% by applying the probabilistic approach based on the kernel method, and the maximum error is about 6.3 meters. According to the experiment results, the probabilistic approach based on the kernel method yields better positioning accuracy than the use of the NN algorithm. In addition, we use the concept similar to the KWNN algorithm to select more candidates and average them according to the probability of each candidate. In Figure 5, there is no notable improvement by selecting more candidates. If we integrate the probabilistic approach with the SIR particle filter, the positioning result is similar to the use of the KWNN algorithm. The velocities and accelerations used in the
Table 1 shows the standard deviations of the positioning errors of the dynamic test by the KWNN algorithm and the KWNN algorithm with the SIR particle filter for different values of K. As illustrated in Figure 6, the positioning error is the difference between the positioning result and the true trajectory (i.e., the straight line from grid point 3 to grid point 23). From Table 1, the KWNN algorithm ( ) has the largest standard deviation, and one notes that when the value of K is larger than 1 or the SIR particle is used, the positioning results yield smaller standard deviations. In this case, has the better positioning result. In addition, the standard deviations of the positioning errors by the SIR particle filter are smaller than that of the KWNN algorithm alone. As a result, the SIR particle filter can enhance the positioning performance as the user is in motion.
We also compare the positioning results by the kernel method and the kernel method with the SIR particle filter. Table 2 shows the standard deviations of the indoor positioning errors by the kernel method and the kernel method with the SIR particle filter. From Table 2, there is no significant improvement for the kernel method with more candidates; these positioning results are consistent with the static experiment analysis shown in Figure 7. When the SIR particle filter is applied, the positioning results are smoother than the cases without the SIR particle filter.
By the static and dynamic experiment results, it’s obvious that the use of the particle filter can improve the indoor positioning results. However, the particle filter is a high computation load algorithm, and it usually requires a large number of particles for its computation to get more accurate results. If a large number of particles is needed, it would be challenging to apply it to a real time application. For an optimal design, the trade-off between the particle number (i.e., the computation load) and the positioning accuracy must be investigated. This paper utilizes the particle number of , 30, 100, 1000 and 2000 to evaluate their positioning performance. Figure 7 shows the CDFs of the positioning errors of these positioning results.
Figure 7: The CDFs of the positioning errors for different particle numbers.
In Figure 7, there is a limit in positioning performance improvement when increasing the number of particles. When the particle numbers approach to 100, the improvement on the positioning performance becomes lesser. In the other words, there is no significant improvement as the value of N increases from 100 to 2000. The computation load of the particle filter with different particle numbers is also an important issue. Thus, the trade-off study between the positioning error and the computation time for different particle numbers is conducted and the result is shown in Figure 8.
Figure 8: The trade-off study between the positioning error and the computation time for different particle numbers.
As shown in Figure 8, the 95% positioning error bound is reduced from 447.5 to 380.2 cm as the particle number is increased from 5 to 100. However, as we continue to increase the particle number, the positioning results are not significantly improved, and the computation time increases as the particle number increases. The CPU used in this work is the Intel Pentium 4 3.0 GHz. As indicated in Figure 8, to 100 might be the optimal design. When the sizes of the buildings are different, the required optimal particle number for the area of interest has to be considered. Table 3 shows the computation time, the 95% positioning error bounds and the particle densities for different values of N. This paper defines the particle density as the total particle numbers distributed in one square meter. Table 3 shows that the particle densities in the range of 0.9 to 2.99 (1/m2) yield the better indoor positioning results. The evaluation result indicates that the combination of the KWNN algorithm with 4 candidates and the particle filter with 2.99 particle density is the best for the proposed RTIPS.
Table 3: The comparison of performance for different particle numbers
REAL TIME INDOOR POSITIONING SYSTEM
In order to demonstrate the proposed indoor LBS test-bed, the Real Time Indoor Positioning System (RTIPS) of the DAA building at NCKU is developed. The Borland C++ Builder 6.0 is used to build this RTIPS. The main objective of the RTIPS is to provide the real time indoor positioning services on a 3D indoor GIS. In addition, the RTIPS is integrated with the Microsoft SQL Server to provide the classroom search function. This developed RTIPS is composed of the real time positioning and the information search services.
Figure 9 shows an example of the real time indoor positioning test at the classroom 5834 of the DAA building. To implement the indoor positioning system based on the fingerprinting method, the positioning database has to be loaded first. As shown in Figure 9, block 1 provides the positioning database and the associated coordinate system selection. When the positioning database is loaded, the RSS values of the database are shown in block 3. Block 2 is the parameters determination of the positioning algorithm. Users can choose different K values of the KWNN algorithm, and the default value is 4. In addition, the particle filter is utilized to further enhance the positioning performance. The default particle number of the particle filter is 100. The particle number can be changed by users as well, and the velocity Vx and Vy are determined by the empirical data. Block 4 is the display of the current RSS values of the incoming signals of each transmitter, and block 5 is integration of the indoor positioning results and the developed 3D indoor GIS.
Figure 9: The real time indoor positioning test at the classroom 5834 of the NCKU DAA building.
This RTIPS also provides the search service to complete the indoor LBS. In Figure 10, block 2 is the course table information. When users double click the course table, the course information is shown in the text box of block 1. In block 3, users could click the “Search” button, and the search result will be presented in the 3D indoor GIS. Figure 10 shows an example 3D indoor GIS with the integration of the cartography and database techniques.
Figure 10: An example 3D indoor GIS with the integration of the cartography and database techniques.
CONCLUSIONS AND FUTURE WORK
This paper utilized a Wireless Sensor Network (WSN) based on the ZigBee radio to implement an indoor positioning system. The positioning algorithm used in this paper is the fingerprinting method. According to the experiment results, the K-Weighted Nearest Neighbors (KWNN) algorithm with K=3 or 4 could obtain the better positioning results. This paper then combined the fingerprinting method with the Sampling Importance Resampling (SIR) particle filter to enhance the positioning performance. However, if the particle filter is applied in the real time application, the trade-off between the particle number and the positioning performance must be considered. According to the analysis result presented in this paper, the particle density in the range of 0.9 to 2.99 (1/m2) would be a better design.
In addition, this paper successfully demonstrated a rapid and practical procedure to develop the local Geographic Information System (GIS) which applied the Computer-Aided Design (CAD) software and the Virtual Reality Modeling Language (VRML) technique. This paper combined the indoor GIS, the indoor positioning system, and Microsoft SQL Server to complete an indoor Location Based Service (LBS) test bed. Finally, the Real Time Indoor Positioning System (RTIPS) of Department of Aeronautics and Astronautics building at National Cheng Kung University was developed to demonstrate its capabilities. This example RTIPS also provides the course search function, and the search results are presented on the developed 3D indoor GIS.
Because the indoor environment is a complicated system, the uncertainties would have some influence on the positioning accuracy. How to build a more robust indoor positioning system to overcome these uncertainties would be another interesting research topic. Furthermore, the protection level of the indoor positioning system will be investigated in the future to provide users indoor positioning services with safety concerns.
ACKNOWLEDGMENT
The paper is supported by Taiwan National Science Council under NSC-96-2221-E-006-187. The authors gratefully thank for the support.
REFERENCES
[1]. P. Prasithsangaree, P. Krishnamurthy, P. K. Chrysanthis, “On Indoor Position Location with Wireless LANs,” IEEE Personal, Indoor and Mobile Radio Communication, 2002.
[2]. P. Bahl, V. N. Padmanabhan, “RADAR: An in-building RF-based user location and tracking system,” IEEE infocom 2000, Tel Aviv, Israel, 26-30 Mar 2000.
[3]. B. Li, Y. Wang, H. K. Lee, A. Dempster, C. Rizos, “Method for Yielding a Database of Location Fingerprints in WLAN,” IEE Proc.-Commun, 2005, 152, 580-586.
[4]. T. Roos, P. Myllymaki, H. Tirri, P. Misikangas, J. Sievanen, “A Probabilistic Approach to WLAN User Location Estimation,” International Journal of Wireless Information Networks, 2002.
[5]. M. S. Arulampalam, S. Maskell, N. Gordon, T. Clapp, “A Tutorial on Particle filters for Online Nonlinear/Non-Gaussian Bayesian Tracking,” IEEE Signal Processing, 2002.
[6]. D. Qiu, D. D. Lorenzo, S. Lo, D. Boneh, P. Enge, “Physical Pseudo Random Function in Radio Frequency Sources for Security,” Proceeding of ION GNSS, 2009.
[7]. W. M. Tsai, L. T. Hsu, S. S Jan, “The Development of an Indoor Location Based Service Test Bed,” Proceeding of ION GNSS, 2009.
[8]. S.S. Jan, L.T Hsu and W.M. Tsai, “Development of an Indoor Location Based Service Test Bed and Geographic Information System with a Wireless Sensor Network”. Sensors 10(4), 2957-2974.
[9]. L. M. NI, Y. H. LIU, Y. C. LAU, A. P. PATIL “LANDMARC: Indoor Location Sensing Using Active RFID,” Wireless Networks, Kluwer Academic Publishers, 2004.
[10]. B. Li, Y. Wang, H. K. Lee, A. Dempster, C. Rizos, “Method for Yielding a Database of Location Fingerprints in WLAN,” IEE Proc.-Commun, 2005, 152, 580-58
[11]. 6.
My Coordinates |
EDITORIAL |
|
Mark your calendar |
MAY 2011 TO AUGUST 2011 |
|
News |
INDUSTRY | LBS | GPS | GIS | REMOTE SENSING | GALILEO UPDATE |
(4 votes, average: 2.25 out of 5)
Loading...
Leave your response!