Tài liệu Indoor localization with smartphone using ble ibeacon

VIETNAM NATIONAL UNIVERSITY UNIVERSITY OF ENGINEERING AND TECHNOLOGY Duong Ngoc Son INDOOR LOCALIZATION WITH SMARTPHONE USING BLE IBEACON MASTER THESIS IN ELECTRONICS AND TELECOMMUNICATIONS MAJOR : COMMUNICATION ENGINEERING CODE : 8510302.02 SUPERVISOR : PHD. DINH THI THAI MAI HANOI - 2020 Publication thesis option This thesis would consist of the following six articles: Paper 1: Thai-Mai Thi Dinh, Ngoc-Son Duong, Kumbesan Sandrasegaran, “Smartphonebased Indoor Positioning Using BLE iBeacon and Reliable Lightweight Fingerprint Map”, IEEE Sensors Journal, 2020. In press. https://doi.org/10.1109/JSEN.2020.2989411 Paper 2: Ngoc-Son Duong, Thai-Mai Dinh, “Develop a true real-time iBeacon-based indoor positioning system using smartphone”, to be submitted to IEEE Transactions on Instrumentation and Measurement . Paper 3: Ngoc-Son Duong, Thai-Mai Dinh, “Indoor Localization with lightweight RSS Fingerprint using BLE iBeacon on iOS platform”, in 19th International Symposium on Communications and Information Technologies (ISCIT), Vietnam, Sept. 2019. Paper 4: Thai-Mai Dinh, and Ngoc-Son Duong “Smartphone Indoor Positioning System based on BLE iBeacon and Reliable region-based position correction algorithm”, in International Conference on Advanced Technologies for Communications (ATC), Vietnam, Oct. 2019. Paper 5: Ngoc-Son Duong, Tuan-Anh Trinh Vu, and Thai-Mai Dinh, “Bluetooth Low Energy Based Indoor Positioning on iOS Platform”, in IEEE 12th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC), Vietnam, Dec. 2018. Paper 6: Ngoc-Son Duong, and Thai-Mai Dinh, “Smartphone Indoor Positioning Based on Enhanced BLE Beacon Multi-lateration”, TELKOMNIKA, submitted, in revision. Authorship “I hereby declare that the work contained in this thesis is of my own and has not been previously submitted for a degree or diploma at this or any other higher education institution. To the best of my knowledge and belief, the thesis contains no materials previously published or written by another person except where due reference or acknowledgement is made.” Hanoi, .........................2020 Student i Acknowledgment This thesis would never have been done without the support of many colleagues, friends, and my family. Firstly, I would like to thank my advisor, PhD. Dinh Thi Thai Mai, who has given me all the support and guidance I needed as a master student. I am very grateful to have had her trust in my ability, and I have often benefited from her insight and advice during the time I conducted my thesis work. I am grateful to other teachers and friends in Communication Systems Laboratory, Faculty of Electronics and Telecommunications, University of Engineering and Technology. I would like to also acknowledge my family and my beloved ones for cheering and supporting me during my six years at the university. Your sentimental values mean a lot to me. This work has been supported by Vietnam National University, Hanoi (VNU), under Project No. QG.19.25. ii Abstract Nowadays, in large cities, human activities tend to shift from outdoor to indoor environments. This has led to a growing need for services related to the indoor environment such as Location-Based Services (LBSs), Social Networking Services (SNSs), etc. Location accuracy is a measurement of service quality. GPS has done this well for outdoor environments. However, due to the obstruction of building materials, GPS signals can not work well in indoor environments. Therefore, many technologies are exploited to deploy indoor positioning systems (IPS) such as Wifi, RFID, Zigbee, etc. To overcome the limitations of previous technologies, a Bluetooth-Low-Energy-based (BLE-based) technology, iBeacon was introduced as a appropriate solution for IPS requirements due to the advantages such as low energy consumption, wide-coverage, easy deployment, and potential high accuracy. To achieve high location accuracy, this thesis proposes a real-time indoor positioning system which combines iBeacon technology and smartphone sensors. Two main techniques are used for positioning, i.e, Pedestrian Dead Reckoning (PDR) and Range-based using Least Square Estimation (LSE). These two methods help each other create a highly accurate system. Firstly, we offer a solution for Received-Signal-Strength-based (RSSbased) continuous positioning problem by investigating heterogeneity in RSS. Secondly, we propose a method of improving accuracy for LSE. We consider PDR-based position and improved LSE-based position both have a Gaussian uncertainty that comes from initial position plus drifting and RSS-to-distance conversion, respectively. Then, two kinds of Normal distribution will be fused by the Kalman filter to produce more precise positions. The method is intended to design a real-time system for locating moving target. The results show our proposed solution is not only highly accurate but also feasible in actual deployment. iii Contents Abbreviations vi List of Figures vii List of Tables viii 1 Introduction 1.1 Motivation . . 1.2 Approach . . 1.3 Contribution . 1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Background 2.1 Positioning Technology . . . . . . . . . . 2.1.1 Bluetooth Low Energy . . . . . . 2.1.2 Inertial sensor . . . . . . . . . . . 2.2 RSSI-based Positioning Techniques . . . 2.2.1 Fingerprinting Method . . . . . . 2.2.2 Range-based Method (Lateral) . . 2.3 Bayesian Filtering - From Kalman Filters 2.3.1 General Bayes Filtering problem . 2.3.2 Kalman Filter . . . . . . . . . . . 2.3.3 Particle Filter . . . . . . . . . . . 3 Proposed System 3.1 System overview and architecture . . . . 3.2 PDR subsystem . . . . . . . . . . . . . . 3.2.1 Embedded Sensor Block . . . . . 3.2.2 Sensor–based positioning method 3.2.3 Step Length Estimation . . . . . 3.3 LSE subsystem . . . . . . . . . . . . . . 3.3.1 RSS Uncertainty Analysis . . . . 3.3.2 RSSI-to-Distance Conversion . . . 3.3.3 Location Estimation . . . . . . . 3.4 Kalman Fusion . . . . . . . . . . . . . . 4 Evaluation 4.1 Experiment Setup . . . . . . 4.1.1 Device and Software 4.1.2 Experiment Setting . 4.2 Results and Discussion . . . . . . . . . . . . . . . . . . . iv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 3 3 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . to Particle Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 6 7 10 10 11 12 12 13 14 . . . . . . . . . . 18 18 19 19 19 19 20 20 25 26 27 . . . . 30 30 30 30 30 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 4.2.2 4.2.3 4.2.4 Ground Truth and Accuracy Comparisons . . . . . . . . . . . . Performance evaluation under impact of different velocity . . . . Performance evaluation under impact of different beacon density Compare to Fingerprinting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 32 32 34 5 Conclusion 36 5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 v Abbreviations Order No. Acronyms 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 a.k.a AOA BLE Eq. Fig. FM GPS i.e ID IMU INS IPS KF LBS LOS LS MD PAN PDR PF RF RFID RP RSS(I) Tab. SIR SIS SNS SSID TOA UUID UWB Wi-fi Description as known as Angle of Arrival Bluetooth Low Energy Equation Figure Frequency Modulation Global Positioning System that is Identification Inertial Measurement Unit Inertial Navigation System Indoor Positioning System Kalman Filter Location-Based Service Light of Sight Least Square Mobile Device Personal Area Network Pedestrian Dead Reckoning Particle Filter Radio Frequency Radio Frequency Identification Device Reference Point Received Signal Strength (Indicator) Table Sequential Importance Re-sampling Sequential Importance Sampling Social Networking Service Service Set Identifier Time of Arrival Universally Unique Identifier Ultra Wide Band Wireless Fidelity vi List of Figures 1.1 Comparison of different signals for smartphone-based indoor localization [18]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 Channel configuration of BLE . . . . . . . . . . . . . . . . . . BLE iBeacon protocol architecture. . . . . . . . . . . . . . . . INS axis system on iPhone (source: Apple) . . . . . . . . . . . Accelerometer measures changes in velocity along the x, y, and Gyrocopter measure rotation rate in the x, y, and z axes . . . Fingerprint Concept . . . . . . . . . . . . . . . . . . . . . . . Least square position algorithm of three beacons . . . . . . . . Comparison of raw RSS and KF-filtered RSS . . . . . . . . . . The estimated position using Kalman filter . . . . . . . . . . . Illustration of importance sampling method . . . . . . . . . . 3.1 3.2 3.3 System overview and architecture. . . . . . . . . . . . . . . . . . . . . . . Change of acceleration as the user moves . . . . . . . . . . . . . . . . . . RSS uncertainty at different distances. Legend: The bar charts represent observed data histograms at at different distances. Each environmental case at each distance includes 400 samples. Blue bar, light orange bar, purple bar, green bar denote LOS, 1 wall blocked, 1 column blocked, 2 wall blocked situation, respectively; The dashed lines represent fitted line from data specified by Normal distribution; The solid lines represent the fused distribution of possible cases. . . . . . . . . . . . . . . . . . . . . . . . . Linear approximations of distance path loss model . . . . . . . . . . . . . Visual view of our proposed method . . . . . . . . . . . . . . . . . . . . . Fusion of LSE-based position and PDR-based position . . . . . . . . . . 3.4 3.5 3.6 4.1 4.2 4.3 4.4 4.5 . . . z . . . . . . . . . . . . . . . axes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 6 8 8 9 9 10 11 15 15 15 . 18 . 20 . . . . 23 25 27 28 The position of the iBeacons and true path on the experiment area. . . . . Ground truth and accuracy comparisons. a) Distribution of corrective points. b) Trajectories of true path, PDR path and proposed method path. c) Cumulative localization error distributions of our proposed method. . . . Cumulative localization error distributions in 2 cases: running and walking Average localization error given different number of iBeacon . . . . . . . . Comparison between different positioning methods. a) Box-and-whisker plot of localization error for specific cases. b) Trade-off between positioning accuracy and efforts of calibration time . . . . . . . . . . . . . . . . . . . . 31 vii 32 33 33 34 List of Tables 1.1 1.2 Comparison between Wi-Fi or BLE Beacons for indoor location. . . . . . . Pros and cons of the positioning methods . . . . . . . . . . . . . . . . . . . 2 4 2.1 Classic Bluetooth vesus BLE . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1 3.2 Mean RSS and its standard deviation at different distances . . . . . . . . . 24 Distance calculation model for each RSSI range . . . . . . . . . . . . . . . 26 viii Chapter 1 Introduction 1.1 Motivation Micro Sound Accuracy Photo Magnetic Wi-Fi FM Source BLE GPS IMU Macro Low Cost High Figure 1.1: Comparison of different signals for smartphone-based indoor localization [18]. Since its inception, Global Positioning System (GPS) technology [35] has really changed the way people pinpoint the location and find their path on the planet. The ideal condition for GPS to achieve the highest accuracy is the Line-of-Sight (LOS) or few obstructions. However, the rapid development of the construction architecture somewhat hinders the reception of GPS signals, especially in the basement or deep hall. Position errors in these cases can be up to hundreds of meters. Therefore, Indoor Positioning System (IPS) has been studied to be able to locate objects or people in the indoor environment. Basically, the concept of Indoor Positioning System inherits the characteristics of the Global Positioning System. Receivers gathering information from the transmitter to get the location. The thing makes IPS different from GPS is the transmitter technology. Instead of using satellites, IPS utilizes other technologies based on radio frequency (RF-based) such as Wifi [3], Radio Frequency Identification (RFID) [4], Ultra-wideband (UWB) [5], FM source [16] or non-RF-based such as magnetic field (a.k.a geomagnetism or earth magnetic field) [36], photo-based (camera-based) [37], IMU-based [16]. The criteria for a proper IPS are high accuracy, low cost, high energy efficiency, high stability, and platform independence. 1 In order to have a clear view, Suining et al. [18] make a comparison of some technologies in terms of two most impact aspects, i.e, accuracy and cost in deployment, as shown in Fig. 1.1. This figure shows geomagnetism seems to be suitable for IPS but note that the magnetic field is time-varying and its change not following any law, this leads to not feasible in deployment. Other possible solutions lie in the center of the figure, such as Wi-fi and BLE. A detailed comparison between Wi-fi and BLE is shown in Tab. 1.1. Table 1.1: Comparison between Wi-Fi or BLE Beacons for indoor location. Accuracy Compatible with Android? BLE Beacon 1-5m Yes Compatible with iPhones? Yes Energy consumption Is it costly to install? Low Low cost Battery replacement process after 5 years Is maintenance required? Wi-fi 1 - 10 m Yes Yes, but iOS doesn’t support ranging for Wi-Fi. Consequently, positioning is difficult and inaccurate. High High cost Calibration process required and regular upkeep Out of these, BLE seems to be the best solution. We can make it possible to perform indoor positioning through received signal strength (RSS). There are two kinds of RSSIbased technique: Fingerprinting [42] and Lateral method (range-based method [45]). In the localization problem, Lateral method uses estimated distance from the path-loss model to estimate user’s position. Meanwhile, Fingerprinting relies on map survey step to build a RSS database of an interested area. Then, position decision is made based on online signals and offline database using a matching algorithm. Due to the instability of the BLE signal, indoor localization using only BLE beacon result in large errors. Thus, many studies have combined BLE beacon with other technologies and techniques to yield higher accuracy. In [6], sensors embedded in smartphones are exploited to combine with BLE beacons to determine the location of the object. In this work, the Pedestrian Dead Reckoning (PDR) is applied for localization using smartphone sensors and extended Kalman filter is chosen as a fusion algorithm. The user’s position is updated when a user moves into a three meters reliable calibration range. Exploiting WiFi access points, Zou et al. [7] introduced an indoor navigation and tracking system using built-in smartphone sensors. In this work, the authors use particle filter-based fusion, iBeacon measurements are only used to compute the particle’s weight when the user is in a poor Wi-Fi coverage area. Otherwise, if the user is in a good Wi-Fi coverage area, the Wi-Fi-based positions are used to compute the weight instead. Along with the particle filter, a group of authors in [8] introduced a map constraint-based method to improve this filter. In prediction phase, they leveraged MEMS sensors in smartphone to compute the new position of each particle. In observation phase, they used the position obtained from RSSI Least Squares - based position estimation method to update the weight of the particle. The key of this research is map constraints. According to their arguments, on the map, there are unreachable positions such as the wall, columns, etc. Therefore, the particles, which represent for user position, are absurd if they reside in those areas and then they must be removed. The same thing happens with the route. The weight of a particle is only updated when it is in an accessible area and on an accessible route. The 2 work in [9] is also a study on iBeacon and IMU-based indoor positioning systems using Fingerprinting. In the map matching algorithm, instead of applying conventional kNN, they applied Bayesian estimation as a probability method to encircle reference points that likely to be the exact position. Recent studies tend to apply machine learning into indoor positioning systems. [10] is one of the most detailed studies on the use of machine learning algorithms. Most machine learning and deep learning algorithms are reviewed. By using machine learning in combination with XBee, Wi-Fi, BLE technology and device’s sensor, research shows that the system can achieve high accuracy. In some senses, all of them provide high-precision systems but they are far removed from reality. Some of them get high complexity and does not seem to be appropriate for finite resources such as a phone [6, 10]. The others require a lot of time to collect data for reference points (high-resolution fingerprint) [10, 29]. In general, there are three limitations of previous works, i.e: i, can not provide real-time update ability. ii, only apply for static positioning. iii, not practical in actual implementation. Therefore, the key motivation of this work is originated from the problem associated with feasible realtime positioning solution for moving target with meter-level accuracy requirement. 1.2 Approach This work chooses BLE iBeacon – smartphone sensors fusion as the main approach for indoor positioning as well. For BLE iBeacon, we can use RSS to locate user position via range-based method or Fingerprinting-based method. For smartphone itself, we can also exploit embedded IMU to compute the phone displacement. We make comparison of three techniques in Tab. 1.2, where we can see both side - pros and cons of them. Since we wish to build a system with highly position update rate, PDR is the best solution. With known initial position, PDR provides quite high positioning accuracy. However, in long distance movement, PDR’s trajectory can be drift over time due to sensor noise so that it leads to a high cumulative error. Fortunately, this drawback can be compensated by using BLE signal. So, it is reasonable to have a combination of PDR and rangebased method or PDR and Fingerprinting. For Fingerprinting, it is a sort of supervised machine learning method include Offline phase (corresponding to training phase, labeling phase in ML) and Online phase (corresponding to testing phase in ML). That means computational ability might perform inefficiently in limited resource of mobile phone. In addition, Fingerprinting need a large of data base for ensuring high accuracy. Therefore, it would be unreasonable to save all data of radio map in a phone. Consequently, resulting in delay if data must send via network or directly handled in mobile phone. Of note that it is not about what we expect at our system. For real-time requirement, we wish all of data about the map and computational task must reside in the user’s smartphone. For this aspect, range-based method seems to be appropriate rather than Fingerprinting. Comparing to Fingerprinting, all of range-based method need is coordinates of the beacon. Since we only need to survey for distance model, time for data collection task of rangebased method is much shorter than Fingerprinting. Moreover, algorithm of range-based methods usually are simple so that computational ability can perform in phone directly. Subsequently, real-time requirement is satisfied. 1.3 Contribution In this thesis, we propose a real-time and highly accurate smartphone localization system for moving target using BLE iBeacon. This work aims to develop a fine-grained local3 4 PDR based) (IMU- Fingerprintingbased Range-based Method - Must known initial position in advance - Drift over time due sensor noise - Stable - Moderate Accuracy - High accuracy - High resolution - Good choice for continuous positioning Map survey is needed Time-consuming Maintain database Moderate computational cost (as quantity of data increase) Extra hardware requirement (for data storage) - Unstable in some sense - Moderate Error Disadvantages - Advantages - No require extra equipment - Low complexity - Low computional cost Table 1.2: Pros and cons of the positioning methods ization technique for wide range applications, for example, meter-level indoor navigation for both emergency and casual cases, proximity marketing, and potentially for robotic indoor mapping and navigation. In details, the main contributions of this work are listed as follows: • Creatively introduce heteroscedasticity phenomenon to measure the uncertainty of BLE RSSI. RSS is considered as a Gaussian random variable and its uncertainty linearly decrease as the RSS decreases. To ensure reliability, we only make use of a reliable RSS range for reliable position estimation. • Introduce a method to improve the accuracy of a hybrid system using Pedestrian Dead Reckoning and Least Square Estimation. Firstly, we proposed a method of improving the accuracy of the LSE algorithm by giving higher weights for iBeacon which has the highest RSS. Secondly, we apply fusion for the improved LSE-based and PDR-based position for producing a more accurate position. 1.4 Outline The rest of my thesis is organized as follows: Chapter 2 firstly presents overview the two of technologies which are used in the proposed system, i.e: BLE and IMU. Then, we briefly present two kinds of RSS-based techniques, i.e: Fingerprinting and Lateral. Finally, fundamental of Bayes filters are introduced. Chapter 3 presents the proposed indoor positioning system including PDR subsystem and LSE subsystem. In LSE subsystem, I discusses RSS measurement and its uncertainty in the first half. Then, a ranging scheme is presented in the rest. Chapter 4 presents experimental results and discussion. Finally, Chapter 5 concludes this thesis and suggests some ideas for the future work. 5 Chapter 2 Background 2.1 Positioning Technology 2.1.1 Bluetooth Low Energy Bluetooth Low Energy Overview Bluetooth technology [25], managed by Bluetooth SIG, has been a well-known wireless standard for short-range communication for over a decade. It has widely used in PAN as an alternative to wired communication, for example, replacing wired line in computer mouse or headset. With the demands of better technology, Bluetooth (a.k.a Bluetooth Classic) is replaced by intervention of Bluetooth Low Energy. BLE is intentionally designed for IoT purposes rather than for short-range devices communication. Compare to Bluetooth, BLE consumes less power, provide higher range communication, less latency and more security. Tab. 2.1 summarizes the key feature of Bluetooth Classic and BLE. BLE operates in the 2.4 GHz ISM spectrum band into 40 channels. In which, channel 37 (2.42 GHz), 38 (2.426 GHz) and 39 (2.48 GHz) serves for advertisement purposes and the rest for data exchange. When a BLE device work on channel 37–39, it is known as beacon. BLE beacon broadcasts its advertising packet periodically in constant time interval. The shorter the advertising interval, the more the packet can be broadcasted in one second. 37 0 1 2 3 4 5 6 7 8 9 10 38 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 39 Advertising Channel 2400 Frequency (MHz) Figure 2.1: Channel configuration of BLE 6 Data 2480 Table 2.1: Classic Bluetooth vesus BLE Feature Data rate Power consumption Throughput Connection Latency Channels Channel Bandwidth Range Security Comunication Mode Bluetooth Classic 1-3 Mbps 1W 0.7-2.1 Mbps 100 ms 79 1 MHz 100 m 56/128 bit One to One BLE 1 Mbps 0.01-0.5 W 305 kbps <6 ms 40 2 MHz >100 m 128 bit AES One to Many Usage of BLE in Indoor Positioning System Before BLE is introduced, Bluetooth-based indoor localization is not a reasonable idea because of its communication method (one-to-one communication). We only can make indoor positioning possible after its debut. With many advantages, BLE beacon seems to be better than Wi-fi in the indoor positioning field. It holds unique features that no IoT device has such as small, better power efficiency, wide range, cost-effective and so on. Currently, most BLE positioning methods typically use RSSI. Range-based IPS is designed using path-loss models to estimate the distance between smartphone and beacon. However, path-loss models could not work well in heterogeneous environments as indoor and then resulting error in positioning. To deal with this problem, we can use a well-known technique, called Fingerprint. The data set of Fingerprint for each reference point on map models the specific elements of structures in the indoor environment. The trade-off of this technique is time-consuming in the data collection task. iBeacon and iOS indoor positioning application With aims to seek a feasible solution for indoor positioning with high accuracy, Apple introduced iBeacon - a protocol running on a small, battery-powered device that uses Bluetooth Low Energy (BLE) technology for broadcasting its message to a compatible smartphone within its range. It holds very unique features that none of the technology can provide for indoor localization such as small size, high energy efficiency, low cost, and less interference. Beacons that use with iBeacon protocol promote their presence via three identifiers namely, UUID, Major, and Minor [1] (For brevity, in the rest of the thesis, iBeacon is implied as beacon using iBeacon protocol). As the name implies, an iBeacon device acts as a lighthouse. Instead of emitting light to provide navigation for ships, iBeacon device broadcasts BLE signals to let smart-phone know their location context. The signal needs to be read and converted into relevant information by applications running on smartphones. Some places that use iBeacon include Brooklyn Museum, Luton Airport, Los Angeles Zoo. 2.1.2 Inertial sensor Inertial navigation is the concept of only utilizing internal motion sensors to calculate the position. The favor approach is Pedestrian Dead Reckoning (PDR) [20, 22]. Accelerometer, gyrocopter and magnetometer are three types of sensor which are commonly used in 7 Preamble (1 byte) Access Address (4 bytes) CRC (3 bytes) PDU (2-39 bytes) Header (2 bytes) iBeacon Prefix (9 bytes) MAC (6 bytes) UUID (16 bytes) Data (up to 31 bytes) Major (2 bytes) Minor (2 bytes) Tx Power (1 byte) Figure 2.2: BLE iBeacon protocol architecture. 2D INS. Figure 2.3: INS axis system on iPhone (source: Apple) Accelerometer An accelerometer is responsible for measuring changes in velocity along one axis. Almost smartphones have a three-axis accelerometer, which provides acceleration values in each of the three axes (as shown in Fig. 2.3). Acceleration values may be positive or negative depending on the direction of the acceleration. Accelerometer has various application like measuring speed and distance travelled or gaming. An measurement of accelerometer in an iOS device is shown in Fig. 2.4. Gyroscope A gyroscope is responsible for measuring the rate at which a device rotates around a spatial axis. Rotation rate are measured in radians per second around the given axis 8 0.4 x-axis y-axis z-axis 0.3 0.2 Acceleration (m/s 2 ) 0.1 0 -0.1 -0.2 -0.3 -0.4 -0.5 -0.6 0 200 400 600 800 1000 1200 Time step (1/60s) Figure 2.4: Accelerometer measures changes in velocity along the x, y, and z axes (as shown in Fig. 2.3). Rotation values may be positive or negative depending on the direction of rotation. An measurement of rotation rate in iOS device is shown in Fig. 2.5. 0.4 0.2 Rotation rate 0 -0.2 Turn -0.4 Turn -0.6 Roll Pitch Yaw -0.8 Turn -1 0 200 400 600 800 1000 1200 Time step (1/60s) Figure 2.5: Gyrocopter measure rotation rate in the x, y, and z axes Magnetometer A magnetometer is responsible for measuring the orientation of the device with respect to the magnetic north. Values measured using this sensor is equal to the Earth’s geomagnetic field plus bias introduced from the device itself and its disturbances such as electronic devices and indoor structure. 9 2.2 RSSI-based Positioning Techniques In general, the approaches used in indoor localization can be classified into four categories: Time of Arrival (TOA), Angle of Arrival (AOA), Hybrid TOA/AOA and, Received Signal Strength Indicator (RSSI). This thesis aim to the most commonly method for indoor localization, RSSI [41]. 2.2.1 Fingerprinting Method (x1,y1;RSS11,...,RSS1q,…,RSS1Q) (x2,y2;RSS21,...,RSS2q,…,RSS2Q) … (xp,yp;RSSp1,...,RSSpq,…,RSSpQ) … (xP,yP;RSSP1,...,RSSPq,…,RSSPQ) User Offline Phase Reference Point Beacon Node Online Phase Online Received RSS Map Matching Algorithm RSS’1,…,RSS’q,…,RSS’Q Location Estimation Figure 2.6: Fingerprint Concept Fingerprinting is by the far the most favored positioning method for researching on indoor localization based on radio frequency. In Fingerprinting method, the position obtained from Fingerprinting must be pass through two phases: Offline/Training phase and Online/ Execution phase. In the Offline phase, the area is divided into grid point or reference point, then collect data for each one. These data are then saved in the form of vectors and stored in a database. Suppose we have Q beacons, and P reference points (RPs) in the area. We need to collect data for a location at RPs in the shape of a vector. Each vector normally has the form as following: Vp = {xp , yp ; RSSp1 , ..., RSSpq , ..., RSSpQ }, p ∈ [1, P ] , q ∈ [1, Q] (2.1) in which, {xp , yp } is coordinate of p th RP and RSSp1 , ..., RSSpq , ..., RSSpQ are RSS values from Q beacons respectively. All of these reference points will contribute to creating a radio map. The problem of Fingerprinting is estimating a position when RSS value measurement on-the-fly of an unknown position is available: Va = {RSS10 , ..., RSSq0 , ..., RSSQ0 }, q ∈ [1, Q] (2.2) This task will be done in Online phase by using a matching algorithm such as k-NN, SVM, Neural Network and so on. Fingerprinting’s advantage is not dependent on converting RSSI to distance. The stability of Fingerprinting is higher than range-based method because the position is fixed into reference points. Besides, the major problem of Fingerprinting is several reference points have similar data vectors. This lead to decrease the localization accuracy. Fingerprinting in combination with k-Nearest-Neighbor is also common method in indoor positioning research. Based on kNN algorithm, online vector 10