Blunavi: An indoor positioning and navigation system

Nội dung text: Blunavi: An indoor positioning and navigation system

1. BLUNAVI: AN INDOOR POSITIONING AND NAVIGATION SYSTEM Nguyễn Ngọc Khương Khoa Công nghệ thông tin Email: khuongnn@dhhp.edu.vn Ngày nhận bài: 15/6/2020 Ngày PB đánh giá: 12/9/2020 Ngày duyệt đăng: 25/9/2020 ABSTRACT: Indoor navigation systems have been in in- creasing demand since the introduction of smartphone technology; however, no standard system for indoor nav- igation has been established. An indoor navigation has many applications, for example, to help the 7.3 million visually impaired citizens in the US to navigate indoors. Due to the weaknesses of GPS and wireless signals indoors, the problem of localizing and tracking has proven to be difficult. Current approaches have utilized techniques such as fingerprinting and radio frequency propagation models for localization. This paper proposes BluNavi, a cost- efficient and widely deployable indoor navigation system. BluNavi implements and compares two modules: Wi-Fi fin- gerprinting and an extended Kalman Filter based on dead reckoning and bluetooth low energy beacon signals. Each module was evaluated for its accuracy. The fingerprinting system achieved a mean accuracy of 82.33% ± 3.07% with 95% confidence. The dead reckoning model obtained a mean accuracy of 3.88m ± 0.37m with 95% confidence. The propagation model had an accuracy of 5.91m ± 1.61m with 95% confidence. The extended Kalman Filter with sensor fusion had an accuracy of 10.22m ± 0.91m with 95% confidence. Keywords: Indoor navigation, BLE, Wi- Fifingerprinting, dead reckoning, propagation model, Kalman Filter HỆ THỐNG ĐỊNH VỊ VÀ ĐIỀU HƯỚNG TRONG NHÀ TÓM TẮT: Hệ thống định vị và điều hướng trong nhà đã và đang có nhu cầu ngày càng tăng với phát triển của công nghệ điện thoại thông minh. Tuy nhiên cho tới thời điểm hiện tại hầu như chưa có một hệ thống tiêu chuẩn nào đặt ra cho các hệ thống điều hướng trong nhà. Các hệ thống điều hướng trong nhà có nhiều tác dụng, có thể kể đến như điều hướng hỗ trợ cho 7.3 triệu công dân khiếm thị ở Mỹ. Xét trên quy mô toàn thế giới thì các hệ thống điều hướng kiểu này còn có tiềm năng lớn hơn rất nhiều lần. Do điểm yếu của công nghệ GPS và tín hiệu không dây trong nhà nên vấn đề định vị và theo dõi trong nhà đã được chứng minh là vấn đề khó khăn hơn so với điều kiện ngoài trời. Các phương pháp tiếp cận hiện nay đã và đang sử dụng hướng tiếp cập bằng các kỹ thuật như mô hình xác thực vân tay kết hợp tần số vô tuyến để định vị. Trong bài báo này chúng tôi đề xuất hệ thống BluNavi, một hệ thống điều hướng trong nhà hiệu quả và có thể triển khai rộng rãi. Hệ thống bao gồm hai mô đun chính là: lấy dấu vân tay Wi-Fi và Bộ lọc Kalman mở rộng dựa trên tín hiệu báo hiệu năng lượng thấp của bluetooth. Mỗi mô-đun được đánh giá độ chính xác riêng của nó. Hệ thống lấy dấu vân tay đạt độ chính xác trung bình là 82,33% ± 3,07% với độ tin cậy 95%. Mô hình tính toán góc chết đã thu được độ chính xác trung bình là 3,88m ± 0,37m với độ tin cậy 95%. Mô hình lan truyền có độ chính xác 5,91m± 1,61m với độ tin cậy 95%. Bộ lọc Kalman mở rộng với sử dụng cảm biến có độ chính xác 10,22m ± 0,91m với độ tin cậy 95 %. Từ khóa: Điều hướng trong nhà, BLE, Wi-Fi, Mô hình lan truyền ngược, Bộ lọc Kalman TẠP CHÍ KHOA HỌC, Số 44, tháng 01 năm 2021 129 ±
2. I. INTRODUCTION among others. This means that these indi- Indoor navigation systems have been in viduals need some form of help to find their increasing demand since the introduction desired destination in such structures. Many of smartphone technology. The sensors in methods for indoor localization have pre- smartphones can be used to provide accu- viously been explored. Examples of these rate localization in an outdoor environ- methods make use of GSM standards, ra- ment by using the Global Positioning Sys- dio frequency identification tags (RFID), tem, but so far, no standard indoor localiza- infrared beacons and receivers, and ultra- tion system has been implemented due to sonic sensors [3]–[7]. Un- fortunately, none inaccuracy and cost. of these approaches were adopted because of different drawbacks such as short detec- The problem with such a system per- tion ranges, high installation costs, and little tains to localizing and tracking the user in space for improvement. an indoor space. This problem has many challenges that must be solved. Mainetti, Other more practical solutions to the et al. [1] lists some of these challenges, localization problem use the Wi-Fi infra- including: the loss of signal precision of structure that is available in most buildings wireless systems due to Non-Line-of-Sight to reduce cost and installation times. The (NLOS) conditions and multipath effect, signal of the Wi-Fi Access Points (AP) can scaling the system for large spaces, and be used to approximate location using the complex environments. Received Signal Strength Indicator (RSSI). A practical, accurate and cost-efficient More recently, approaches that use indoor navigation system that solves these Bluetooth Low Energy (BLE) have been challenges has many beneficial ap- plica- tested. BLE is a technology that has recent- tions such as assisting firemen to navigate ly emerged that is used by many devices, a burning, smoke-filled building, locating including smartphones. BLE beacons are people in danger in emergency situations, great candidates for implementing indoor and navigation of public spaces such as localization due to their low energy con- malls, airports, and university buildings. sumption, compact size and affordability. One important but unconsidered appli- Recently, Google released Eddys- cation of an indoor navigation system is as- toneTM, an open BLE bea- con format that sistance for the visually impaired. In 2013, can be configured to send several different there was a reported 7.3 million people in types of payloads using the same packet the United States with some form of visual format [8]. Before Eddystone, iBeacon, a impairment [2]. With no form of eletronic proprietary protocol developed by Ap- ple, navigation assistance when in an indoor was the the de facto standard for BLE bea- setting, these individuals are hindered when cons. Eddystone is much more developer traversing public spaces, such as malls, uni- friendly and is becoming very popular due versities, airports and bus or train stations, to its compatibility with both Android and 130 TRƯỜNG ĐẠI HỌC HẢI PHÒNG
3. Apple mobile devices. The format can be RSSI measurements of the wireless signal used to create a contextually aware expe- to approximate the location of the device. rience for users by delivering proximity- Wi-Fi fingerprinting is a highly popu- based notifica- tions. lar technique in indoor localization [9], In this paper, we present BluNavi. Blu- [10]. This technique focuses on building a Navi implements a module to localize the signal strength map of a given area by cre- user by fusing data provided by Iner- tial ating reference points around it. On each Measurement Units (IMUs) and distance of these reference points, RSSI values are approximations calculated from BLE sig- gathered for each available access point nals. To further compare approaches, the found. These values are stored in a data- system implements a module for Wi-Fi fin- base and identified by the reference point gerprinting , a method which makes use of on which they were gathered. Localization APs by mapping their RSSI values to abso- is achieved by obtaining the signal strengths lute locations. Eddystone configured bea- of all available AP’s at the time of a scan cons will be used to drive our mobile, con- and matching the current values to the ones text based, indoor navigation application. in the pre-existing database. This method The system will communicate with the has many advantages due to the system user and the beacons/access points through being fully based on previously installed an Android application to estimate the ac- Wi- Fi APs and it does not incur in any curacies for real-time indoor navigation. extra hardware costs. Fingerprinting also With this approach we aim to provide a eliminates the need to use noisy wireless low-cost, widely deployable system while signals for distance approximation. In ad- still maintaining a high-level of accuracy. dition, algorithms such as Nearest Neigh- The rest of this paper is organized bor or the Hidden Markov Model can be as follows: Section II describes current applied to the current scans to improve ac- curacy. However, fingerprinting also has indoor localization research. Section III it’s shortcomings such as long scan times explains the methodology behind BluNavi and similar fingerprints. and section IV contains the evaluation of the experimental results. Lastly, Section V Wu, et al. [11] improves on Wi-Fi fin- details our conclusions and future work. gerprinting. A Particle Filter (PF) is used to fuse location estimations provided II. RELATED WORK by a dead reckoning model and Wi-Fi Wi-Fi based indoor localization has fingerprinting to provide a higher local- been a widely re- searched topic due to its ization accuracy. The PF is initialized availability, and the recent surge of BLE using a Random Sample Consensus model beacons has also spurred an interest in ap- which filters out the outliers of the Wi-Fi plying previous methods used in Wi-Fi and fingerprinting algorithm by comparing the other technologies to the advantages of estimations to the dead reckoning model, BLE. Most of these approaches use the thus reducing the chance of the PF initial- TẠP CHÍ KHOA HỌC, Số 44, tháng 01 năm 2021 131
4. izing in the wrong location. For the finger- used along with an extended Kalman Fil- printing, two methods are examined. The ter (EKF) on the fingerprint and propaga- first is a proba- bilistic approach using a tion model estimations to reduce noise and Gaussian distribution to approximate the improve accuracy. An improved approach distribution of RSSI values of an AP. The to building the radio map by updating the second approach is deterministic using a data while the system is online to reduce Support Vector Machine (SVM) for pat- time of off-line training was also used by tern recognition of online readings to the this approach. This system achieved dis- database values. The reported accuracy of tance estimations of less than 2.5m at the approach was less than 2.9 (m) with 90% of the time for a dense deployment of an average error distance of 1.2 (m). This beacons at 1 beacon every 9m. approach has good accuracy while not The previously mentioned approaches requiring any additional hardware, but it have unique solutions that have advanced also requires a lengthy off-line training indoor localization research, but can be phase for the fingerprint database. improved. In this paper, we present Blu- BLE signal fingerprinting is an alter- Navi, a system that aims to improve upon native to Wi-Fi AP fingerprinting. Using previous shortcomings to achieve higher BLE over Wi-Fi has the advantages of accuracies by maintaining a lower need faster scan times and lower power con- of hardware and thus incurring lower sumption. Faragher, et al. [12] established additional costs. The system makes use a grid and probabilities were distributed of implementations of fingerprinting and into cells using a Bayesian likelihood Kalman filters and compares their accura- function based on the results of a K-Near- cies as indoor location systems. est-Neighbor location estimation. Accu- racies of less than 2.6m at 90% of the time III. METHODOLOGY were reported with a deployment of 1 bea- BluNavi’s system is composed of two con per 30m2. This accuracy is better than key modules: Wi- Fi fingerprinting and Wi-Fi fingerprinting and uses less power, an extended Kalman Filter. The system however the system requires a dense de- uses the fingerprinting module during ployment of beacons. NLOS conditions, such as when the user BLE beacon fingerprinting can be is located in a room without a beacon. combined with a radio frequency propaga- This module is designed to achieve broad, tion model to increase the accuracy of a room-level localization. The purpose is system [13]. The model is built by using to reduce the cost and complexity of the the relationship be- tween signal strength system by not requiring beacons to be in- and distance. Because of the large levels stalled in every room of a building, but of noise in the signal strength, the distance rather just the central corridors and walk- approximation is subject to high levels of ways. The second module, the extended volatility. An outlier detection system is Kalman Filter, will be used during line of 132 TRƯỜNG ĐẠI HỌC HẢI PHÒNG
5. sight conditions, such as when the user and a propagation model to approximate is traversing a hallway where beacons are distance to a BLE beacon. The filter pro- deployed. The extended Kalman Filter has duces a state estimate that tracks the co- two sub-components: a dead reckoning ordinates and orientation of the user. The model to track orientation and movement, system diagram can be seen in Fig. 1. Data: Wi-Fi Scans Data Result: Fingerprint Database for i = 0 to N do scan for access points; for each available AP do store AP’s MAC address; store AP’s RSSI; store current reference point; end end Algorithm 1: Creating Fingerprint Database. Variable N represents the number of scans to be performed. Data: Wi-Fi Scans Data Result: User Location scan for access points; for i = 0 to N do for each ref. point containing the AP do if |RSSIAP – RSSIDB| <= X then increase weight of location; end end end return highest weight location; Algorithm 2: Estimating User Location. Variable X is a threshold due to how RSSI values vary. A. Fingerprinting TẠP CHÍ KHOA HỌC, Số 44, tháng 01 năm 2021 133
6. Figure 1: System Diagram The Wi-Fi Fingerprinting module will tion result from the user turning to face be used when NLOS conditions are de- a new direction. The IMU’s available in tected from all available beacons, or when most mobile devices are used to track both no beacons are in range of detection. To components. A gyroscope is used to track implement fingerprinting, a map with ref- changes in orientation. erence points needs to be created. At every Displacement of the user is estimated reference point, RSSI data for every avail- by calculating the length of the user’s cur- able access point needs to be collected. rent walk step. For this purpose, BluNavi’s The system makes use of the algorithm dead reckoning model uses measurements presented below to scan reference points provided by an accelerometer to calculate with a device. step length. The data is passed through a After this database is created, the low-pass filter to remove noise and smooth system can estimate the user’s location the curve. The filtered values are then through a weight based approach, where used in a formula derived from the one a weight is assigned to each reference used by Bao, et al. [14]. The equation can point based on the similarities between the be seen in Eq. 1. user’s current scans and the finger- print 1 4 (1) ln=−−( aa fh al) aa ch vl database. This is done through the algo- 8 rithm shown on algorithm 2. where n is the current step, ln is the B. Pedestrian Dead Reckoning Model length of step n, afh and afl are the high BluNavi uses a dead reckoning model (maximum) and low (mimimum) values to track two key local-ization components: of the accelerometers forward accelera- orientation and displacement (movement). tion axis during step n, respectively, and Displacement occurs when the user of the avh and avl are the high and low values of system takes a step. Changes in orienta- the accelerometer’s vertical axis during 134 TRƯỜNG ĐẠI HỌC HẢI PHÒNG
7. step n, respectively. K is a constant that Pd( )=−+ Pd ( ) 10γ log (d ) X (2) expresses the leg length of the user and is 0 10 σ determined through training. where P (d) represents the RSS at dis- tance d, P (d ) is the transmission power, Two methods can be used to determine 0 γ is the path-loss exponent, and X is a when a step has been completed. If a step σ detector is available in the mobile device, Gaussian random variable with zero mean then the data provided from it is used for and standard deviation of 4.11 found from step detection. Otherwise, a step detec- experimental analysis of BLE beacon sig- tion process begins when the vertical ac- nal strength. The model has acceptable ac- celeration values pass a set threshold. The curacy in open, line of sight environments threshold is used to avoid recording a false but suffers when used in enclosed places. peak during the begining of a step. Fig. 2 For this reason, an extended Kalman Filter demonstrates a threshold on accelerometer is used to increase the accuracy. data that was collected from a test where D. Extended Kalman Filter ten steps were taken. The peak is record- The extended Kalman Filter (EKF) is ed when the partial derivative of the data used in BluNavi to increase the localiza- changes from positive to negative. Then, tion accuracy of the system by fusing sen- the lowest value is recorded. When the next sor data provided by the dead reckoning peak is detected, the process is over and the model and the propagation model. The step length is calculated using equation 1. filter works in two steps: a prediction step and a correction step. The prediction step predicts the cur- rent state and the error of the prediction using a standard Kalman Filter process model and process covariance model. The process model estimates movement (or non-movement) through the indoor envi- ronment. The model is given by Eq. 3. xkp= Ax k−1 + Bu k (3) where x is the predicted state Figure 2: Vertical Acceleration Data kp vector at time k, A is the state tran- C. Propagation Model sition matrix, xk−1 is the previous state For indoor localization, distance from vector, B is the control input transition device to beacon is approximated using a matrix, and uk is the control input vec- radio frequency propagation model. Blu- tor. Control input will be step length esti- Navi uses the log-distance path loss model mations provided by the dead reckoning as described by Zhuang, et al [13]. The model. The state vector is defined as: model can be seen in Eq. 2 T xXY= [ ] (4) TẠP CHÍ KHOA HỌC, Số 44, tháng 01 năm 2021 135
8. the process covariance model is de- evaluated and a summary of the accura- T fined as: Pkp= AP k −1 A + Qk (5) cies can be seen in Fig. 3. where Pkp is the predicted process covariance matrix and Qk is the process noise covariance matrix. Next, after a BLE beacon signal is de- tected, the propagation model feeds in the distance estimate into the measurement Figurre 3: Table of Accuracies model of the filter, which is as follows: zk= Hx kk + v k (6) where zk is the measurement vector, Hk is the measurement transition matrix and vK is zero-mean, Gaussian white-noise caused by errors in the sensors. The next step is to update the state vector and process covariance matrix based on the process and measurement models. The models for this step can be defined as follows: Figure 4: Example Test Bed −1 TT Kk= PH kp k( HPH k kp k + R) (7) A. Fingerprinting System xk=+− x kp K k() z k Hx k kp (8) For the evaluation of the fingerprinting system, three diffferent hallway testbeds Pk =() I − KHk k K kp (9) were used. Fingerprints were created out where K is the kalman gain, R is k of three meter cells at each of the testbeds. the measurement noise covariance An LG G4 was used to scan for Wi-Fi matrix dervied from v , x is the k k APs. Five tests were conducted at each corrected current state estimate, and I is of the testbeds, and each test was per- the identity matrix. formed twice. Each test consisted of 20 3. EVALUATION estimations of the user’s location that the Experimental analysis was conducted system would make under various condi- in order to evaluate the accuracy of the tions. These tests involved different user proposed system. Multiple test beds were movements such as: straightforward alter- created in the hallways of the University of nations between cells, random alternations South Florida ENB II building. One meter between cells, at different orientations per cells were established in each of the hall- cell, at different positionswithin each cell, ways. An example of one of the test beds and for random movements within each can be seen in Fig. 4. The accuracies of cell. The accuracies of each test were cal- each module of BluNavi were tested and culated, providing 30 data points. A nor- 136 TRƯỜNG ĐẠI HỌC HẢI PHÒNG
9. mal distribution was assumed and tested no way to correct itself from the inaccura- for using the 30 data points, as shown in cies of the step length estimation. Fig. 5. For these evaluations, a confidence interval was calculated using this data set, which resulted in a 95% confidence of ± 3.07% from the mean accuracy of 82.33% for three meter cells. Figure 5: Distribution of Fingerprint System Accuracies B. Dead Reckoning Model The dead reckoning model was evalu- ated by walking the perimeter of a rectan- C. Figure 6: Traversals of the Dead Reck- gular hallway. A Nexus 5 was used for this oning Model and Extended Kalman Filter test. The ground truth was established Propagation Model by timestamps of the test when passing The evaluation of the propagation established reference points. Linear in- model took place in one of the previously terpolation was then used on this data to mentioned test beds. A BKON A1 set at a calculate the ground truth values between transmission power of 0 dbm and adver- reference points. During the test, the x tising interval of 500 ms was used for the and y coordinates of the system were re- test. The A1 can be seen in Fig. 7. A Nexus corded every 500 milliseconds along with 5 was used to scan for the BLE beacon. a timestamp. The error of each data point The test was conducted with line of sight was then found by using the distance for- conditions to the beacon. Ten signals were mula between ground truth value and dead recorded for each one meter interval from reckoning model estimate. The mean one meter up to ten meters for a total of 100 accuracy of the model was found to be data points. The signals were then passed 3.88m ± 0.37m with 95% confidence. A through the propagation model and the dis- comparison of the ground truth data points tance estimates recorded. The error of each and dead reckoning model can be seen in distance estimate was computed and the upper half of Fig. 6. From the figure, it is mean error of the data set was found to be clear that the dead reckoning model has a 5.91m ± 1.61m with 95% confidence. TẠP CHÍ KHOA HỌC, Số 44, tháng 01 năm 2021 137
10. propagation model and extended Kal- man filter. Each component was -evalu ated for accuracy. The fingerprinting sys- tem achieved a mean accuracy of 82.33% ± 3.07% with 95% confidence. The dead reckoning model obtained a mean accu- racy of 3.88m ± 0.37m with 95% con- fidence. The propagation model had an accuracy of 5.91m ±1.61m with 95% con- Figure 7: BKON A1 fidence. The extended Kalman Filter with D. Extended Kalman Filter sensor fusion had an accuracy of 10.22m The extended Kalman Filter was ± 0.91m with 95% confidence. The - fin evaluated similarly to the dead reckoning gerprinting system proved to be a viable model. Eight of the A1 models were used option for detecting users at room level for the test and placed around the same accuracies. The extended Kalman filter test bed used for the dead reckoning proved to suffer from cumulative errors, model evaluation. The Nexus 5 was also but points to possible advantages of com- used for this test. The extended Kalman bining with the fingerprinting system for Filter state estimate (position) was record- the sake of correcting estimations done by ed every 500 ms and 141 data points were the Kalman filter. As a future work, these collected. Ground truth timestamps were systems would be improved upon so as to recorded at the same reference points used further increase their accuracies. Possible in the dead reckoning evaluation and linear improvements include the implementation interpolation was used to find the ground of a correlation algorithm for the finger- truth positions. The distance error of the printing system, such as Hidden Markov, data points was calculated and the mean and further work on the extended Kalman error was found to be 10.22m ± 0.91m filter. These systems would also be- inte with 95% confidence. A comparison - be grated into one single application for the tween ground truth data points and the ex- sake collaboratively improving the overall tended Kalman Filter state estimates can accuracy, along with the implementation of be seen in the lower map of Fig. 6. From a line of sight detection module for aid in the results, it is clear that the system suf- deciding which system would be more ac- fers from a cumulative error problem. curate given the user’s current conditions. 4. CONCLUSIONS AND FUTURE WORK REFERENCE The research conducted brought about 1. L. Mainetti, L. Patrono, and I. Sergi, functional systems for indoor localization “A survey on indoor positioning systems,” in through the development of the fin- ger- Software, Telecommunications and Computer printing system, dead reckoning model, Networks (SoftCOM), 2014 22nd International Conference on. IEEE, 2014, pp. 111–120. 138 TRƯỜNG ĐẠI HỌC HẢI PHÒNG
11. 2. “National Federation of the Blind blindness 9. S. Chan and G. Sohn, “Indoor localization statistics”, accessed: using wi-fi based finger- printing and trilateration 2016-06-20. techiques for lbs applications,” International Archives 3. V. Otsason, A. Varshavsky, A. LaMarca, and of the Photogrammetry, Remote Sensing and Spatial E. De Lara, “Accurate gsm indoor localization,” in Informa- tion Sciences, vol. 38, p. 4, 2012. International conference on ubiquitous computing. 10. E. Navarro, B. Peuker, and M. Quan, Springer, 2005, pp. 141–158. “Wi-fi localization using rssi fin- gerprinting,” 4. N. Li and B. Becerik-Gerber, “Performance- Bachelor’s thesis, California Polytechnic State based evaluation of rfid- based indoor location University, 2010. sensing solutions for the built environment,” 11. Z. Wu, E. Jedari, R. Muscedere, and R. Advanced Engineering Informatics, vol. 25, no. 3, Rashidzadeh, “Improved particle filter based on pp. 535–546, 2011. wlan rssi fingerprinting and smart sensors for 5. J. Liu, “Survey of wireless based indoor indoor localization,” Computer Communications, localization technologies,” Dept. of Science & vol. 83, pp. 64–71, 2016. Engineering, Washington University, 2014. 12. R. Faragher and R. Harle, “Location 6. A. Ward, A. Jones, and A. Hopper, “A new fingerprinting with bluetooth low energy beacons,” location technique for the active office,” IEEE IEEE Journal on Selected Areas in Communications, Personal Communications, vol. 4, no. 5, pp. 42– vol. 33, no. 11, pp. 2418–2428, 2015. 47, 1997. 13. Y. Zhuang, J. Yang, Y. Li, L. Qi, and N. El- 7. C. Medina, J. C. Segura, and A. De la Torre, Sheimy, “Smartphone-based indoor localization “Ultrasound indoor positioning system based on a with bluetooth low energy beacons,” Sensors, vol. low-power wireless sensor network providing sub- 16, no. 5, p. 596, 2016. centimeter accuracy,” Sensors, vol. 13, no. 3, pp. 14. H. Bao and W.-C. Wong, “An indoor dead- 3501– 3526, 2013. reckoning algorithm with map matching,” in 2013 8. “Google beacons eddystone format,” 9th International Wireless Communications and Mobile Computing Conference (IWCMC). IEEE, accessed: 2016- 05-24. 2013, pp. 1534–1539. TẠP CHÍ KHOA HỌC, Số 44, tháng 01 năm 2021 139