Real time indoor location based
The purpose of this paper is to develop low cost and low power consumption Real Time Indoor Positioning System (RTIPS) and then integrate this RTIPS with a self-developed indoor GIS to form a indoor LBS prototype. Here we present the first part of the paper. The concluding part would be published in May issue
Today, mobile devices are not only tools for the communications but also personal assistants. People could use the mobile device built-in Global Positioning System (GPS) receiver to search for information based on his/her location, thus called Location Based Service (LBS). However, due to the GPS signal propagation limit, the positioning and navigation services are discontinued when the user enters the indoor environments. When users are in the indoor environments, how to continuously obtain their locations becomes a popular research topic. Therefore, this paper proposes a practical solution to build a Real Time Indoor Positioning System (RTIPS), and this RTIPS also integrates with an indoor Geographic Information System (GIS) to form an indoor LBS prototype. Considering the power consumption, the Wireless Sensor Network (WSN) based on the ZigBee radio is utilized to implement the indoor positioning system in this work.
According to the radio signal propagation theory, the signal strength will decay as the transmission distance increases, and this signal propagation characteristic can be used to determine the user position. Consequently, the indoor positioning algorithm applied in this paper is the fingerprinting method . The matching algorithms used in the fingerprinting method have significant impact on the performance of the RTIPS. The matching algorithms used in this work are the Nearest Neighbor (NN) algorithm , the K-Weighted Nearest Neighbors (KWNN) algorithm , and the probabilistic approach based on the kernel method . The positioning results with above matching algorithms are studied in this paper as well. Due to the indoor environment is a nonlinear system, some unexpected factors might affect the positioning results, and it would be difficult to estimate the real trajectories of the moving user based on the fingerprinting method alone. To further enhance the positioning accuracy and to smooth the indoor positioning results, an appropriate filter is needed. The suboptimal filtering algorithm, the particle filter , is used in this indoor positioning system to gain possible improvement on the positioning performance. However, the performance of a particle filter is proportional to the number of particles used in the filter, and this feature might be a problem when the particle filter is applied to the RTIPS. In other words, as increasing the number of particles used in the filter, the resulting computation load will increase as well. Consequently, the trade-off study between the positioning performance and the computation time is investigated as well.
The other branch of this work focuses on a rapid and practical procedure to develop a three-dimensional indoor GIS. In addition, the developed indoor GIS must have high flexibilities and be able to integrate with the Virtual Reality Markup Language (VRML) technique. The basic procedure of this indoor GIS is to design the indoor map by the Computer-Aided Design (CAD) software, then combine it with the programming language and finally integrate it with the VRML technique. The advantages of this developed indoor GIS are easy for update and maintenance for users, and it has a user friendly interface with the virtual reality concept. Finally, a RTIPS test bed for the Department of Aeronautics and Astronautics at National Cheng Kung University is constructed for the demonstration.
Figure 1: The proposed development procedures of the indoor GIS.
Figure 2: The snapshots of the 3D indoor GIS of the DAA building.
Accordingly, the reminder of this paper is organized as follows. The indoor positioning algorithms are described in “Indoor Positioning Algorithms”. The development procedures of an indoor 3D GIS will be explained in “Geographic Information System”. In “Expriment Results”, several positioning algorithms are applied to investigate their positioning results. The development of the RTIPS is illustrated in “Real Time Indoor Positioning System”. Finally, “Conclusions And Future Work” presents the concluding remarks and future work.
Indoor positioning algorithms
The indoor positioning algorithm used in this paper is the fingerprinting method  based on the received signal strength. The main concept of the fingerprinting method is to use the received signal strength as the location identifier. It requires two stages to implement the fingerprinting method, namely the calibration (training) stage and the positioning stage . The positioning data is collected in the training stage and then the matching algorithm is used to find the most likely user location in the positioning stage. The matching algorithms applied in this paper are the NN algorithm, the KWNN algorithm, and the probabilistic approach based on the kernel method. In addition, to improve the positioning results, the particle filter is used in this work. The details of the NN algorithm, the KWNN algorithm and the particle filter can be found in [7-8]. These algorithms are briefly illustrated in the following paragraphs.
The Nearest Neighbor (NN) Algorithm
The main concept of the NN algorithm is to compute the minimum distance between the current measurement and the prerecorded data in the positioning database, and the calibration point with the minimum distance is declared as the user location.
The K-Weighted Nearest Neighbors (KWNN) Algorithm
The KWNN algorithm selects more calibration points in the database to average the estimation results, and the selected calibration points have their specific weighting values according to the inverse of their distances. The calibration point with smaller distance has larger weighting value.
The Probabilistic Approach Based on the Kernel Method
Since the environmental uncertainties might cause severe fluctuations in the received signal strength, the received signal strength might not be the same even if the user stands at the same location. Specifically, the received signal strength is not constant even at the fixed location, and the distribution of the received signal strength could be approximated as a probabilistic distribution. The Gaussian model is commonly used to describe the distribution of the received signal strength, and this approach is also known as the kernel method . Additionally, the received signal strengths from different transmitters are assumed to be independent. Therefore, the probability density function of the received signal strength can be expressed as Equation (1).
The Particle Filter
Because the indoor environment is a complicated system, the received signal strength might be affected by several uncontrollable factors. It would be difficult to obtain the position estimations based on the matching process alone. Therefore, an appropriate filtering algorithm is needed. A common filtering algorithm is the Kalman filter, but the Kalman filter is suitable for a linear system. The indoor environment is a nonlinear system, the Kalman filter might not be a good option for the indoor positioning system. Thus, the particle filter is implemented for the indoor positioning system in this work. The particle filter used in this paper is the Sampling Importance Resampling (SIR) particle filter. The procedure of implementing SIR particle to the proposed indoor positioning system is detailed in [7-8].
Geographic Information System
One of the major challenges of constructing an indoor LBS is to build the indoor GIS and integrate it with the indoor positioning system. In general, we could utilize the program development tool (e.g., Visual C++) and the computer graphic technique (e.g., OpenGL) to develop the graphic system. However, if the requirements of the graphic system are complicated, it would be difficult to establish the graphic system by the approach mentioned above. In addition, the maintenance and update of this graphic system would also be time consuming. To reduce the workload of the developer, the CAD software, such as the AutoCAD and CATIA, would be a better tool for the rapid graphic construction. With the assistance of the CAD software, the developer could establish the graphic system efficiently. However, every CAD software has its own graphic format; therefore, the compatibility for different graphic formats needs to be taken into account. For that reason, the VRML graphic standard is used in this paper. A solution is proposed in this work to establish the indoor GIS by the CAD software and the VRML technique.
The development procedures of the GIS are as follows: the first step of the development is to set the goal of the GIS. After the setup of the goal, the next step is to collect the information required for this GIS, for instance, the building sizes and the location of the furniture in the room. In the next step, if the commercial GIS software meets the requirements of the system, the commercial GIS could be used to simplify the development process. On the other hand, the CAD software is utilized to construct the maps. In order to integrate this developed GIS with other applications, the format of the map has to be changed to fit the VRML standards. Additionally, to provide the real time update of the area of interest, the External Authoring Interface (EAI) technique is used to achieve this goal. Finally, we can use the program development tool (e.g., C++ Builder) to combine the developed GIS with the indoor positioning system. The 3D GIS is shown through the web browser (e.g., Internet Explorer) with the VRML player (e.g., the Cosmo Player). In addition, a GIS is also denoted as the integration of the cartography and database techniques; therefore, the GIS has the ability to provide query service of the useful information. The useful information could be saved into the Database Management System (DBMS) software (e.g., Microsoft SQL Server) and be connected by the ActiveX Data Objects (ADO) technique. The complete development procedures of the indoor GIS are summarized in Figure 1.
A 3D indoor GIS of the Department of Aeronautics and Astronautics (DAA) building of National Cheng Kung University (NCKU) is used as an example to illustrate the development procedure. In this paper the CATIA is used to draw the 3D map of the DAA building. We use the CATIA to transfer the map format to be in the VRML file, and the VRML viewer used in this paper is the Cosmo player. In this paper, we use C++ Builder to integrate the GIS with the indoor positioning system. To show the real time positioning results on the map, the EAI technique based on the VRML standard is used in this work. Several snapshots of the 3D indoor GIS of the DAA building are shown in Figure 2.
To be concluded in May 2011 issue.
Mark your calendar
INDUSTRY | LBS | GPS | GIS | REMOTE SENSING | GALILEO UPDATE