GPS has been a de-facto standard for outdoor positioning. For indoor positioning diferent systems exist. But there is no general solution to fit all situations. A popular choice among service provider is Bluetooth Low Energy (BLE) based Indoor Positioning System (IPS) . BLE has low cost, low power consumption, and it is compatible with newer smartphones. This paper introduces two ways for accuracy improvement i) a new algorithm for BLE-based IPS based on well-condition triangle and ii) fusion of BLE position estimates with IMU position estimates was implemented. Fusion generally gives better results but a noteworthy result from fusion was that the position estimates during turns were accurate. When used separately, both BLE and IMU estimates showed errors in turns. Fusion with IMU improved the accuracy of BLE based positioning.
People spend about 80 percent of their time indoors [
The main available positioning technologies –GNSS– are for outdoor scenarios. Unfavorably its accuracy in indoor environments is not enough. Due to advancement in technologies several other systems have emerged which can provide positioning and localization in indoor environments, or in those places where GNSS signals are weak or unavailable.
The indoor positioning market is predicted to be 10 billion USD by 2020 [
Smartphones are seen as the best platform for mass market indoor positioning due to their
ubiquity and convenience. The past decade witnessed major developments in smartphone
technology which usually come with wide array of sensors. These sensors can be leveraged for
position estimation. The Skyhook company provides “Precision Location” service using Wi-Fi,
GNSS and Cellular network signals [
IPS solutions based on only one technology are more prone to inaccuracies due to the sensor
noise [
BLE is a suitable alternative to Wi-Fi since it is more accurate [
For improving accuracy of BLE systems researchers have investigated diverse techniques.
Linearizing non-linear beacon readings [
In a beacons group, many permutations of beacons are possible but it is possible to choose a beacons permutation which provides the least possible error in the position estimate. According to a surveying concept, position estimation based on a well-conditioned triangle ensures least error[15]. To the author’s knowledge this concept has not been explored so far in IPS. So, one of the goals of this paper is to implement the concept of well-conditioned triangle for choosing beacons used in BLE position estimation.
The main contributions of this paper are: • To design and implement a positioning algorithm based on well-conditioned triangle for
BLE positioning and study its efects.
• To implement an integration of BLE positioning and inertial method.
Large eforts have been dedicated to find new solutions for indoor positioning in the last decade.
Various surveys shed light on state of art techniques in specific domains. Correa et al. [16]
focus on mass market applications, Dhobale et al. [17] reviews from user prospect, Diaz et al.
[18] narrows down on inertial sensors. Wi-Fi was the most prevalent technology followed by
light and Wi-Fi is predicted to remain dominant unless cheaper solution are found [
Low cost and smartphone based IPS solution have high demand[
Dead reckoning, nfigerprinting, trilateration, triangulation, proximity estimation, visual localization are popular techniques for indoor positioning. Combination of one or more of these techniques is also possible. Such systems are called hybrid systems, being LearnLoc, Kailos, Surround Sense some representative examples. A comprehensive discussion on hybrid systems is provided by Easson et al. [19]. Research landscape is focused on experimentation with diferent combinations of technologies.
Sensor fusion enables to control drift error in an IPS [
Two independent technologies have been used for postition determnation: BLE and IMU. The estimates from these two techologies have been fused to complement each other and improve accuracy. As for BLE estimates, weighted centroid (WC) algorithm was used and a new modification to WC algorithm has been proposed. The new modification is based on well-conditioned triangle. For IMU estimates stride-length and heading algorithm has been implemented. Overall method is presented in figure 1.
The experiment area is a wing of a university library. Measurements are carried out in the 5th
lfoor of the library where the BLE beacons had been deployed. This area is among bookshelves
which can block RSS signals. The beacons were placed in the top of the book shelves. They
are not visible from outside. 22 BLE beacons were deployed in the area. The deployment
resembles a dense distribution (1 beacon per 7.86 sq. m.). The area and device settings are
same from [
In trilateration error in position computation depends on the geometry formed by the three known points. The shape of triangle formed by those three points afect the accuracy [15].
In Figure 3, consider the known points (example BLE beacons) are represented by blue stars.
Two of the sides are of unit 2 and length of the third side is dependent on geometry. Suppose
that in ideal condition with no multipath and ideal path loss, the readings can be equally
trusted so they are given weights of [
Theoretically in an isosceles triangle with two angles of 56◦ 14’, change in any measurement (distance or angle) to unknown point will have least efect on the resulting position. Such a triangle is known as a well-conditioned triangle [15]. This value takes one side as base for computation. But a triangle can be solved from other sides as well so the best geometry is an equilateral triangle. In practice equilateral triangles are rare, so a well conditioned triangle is defined as a triangle in which no angle is less than 30 ◦ . Triangles having angles less than 30◦ are considered to be ill-conditioned and should not be used for position estimations. (a)
A Delaunay triangulation is a set of lines joining a set of points together such that each point is joined to its nearest neighbors. The set of lines form a triangular mesh. In this triangular mesh every circum-circle of a triangle does not contain any other points of the set within it. Delaunay condition states that the circum-circle of any triangle should not contain any other point inside it. Circum-circle is the circle that passes through the vertices of a triangle. A triangular mesh satisfying delaunay condition is called delaunay triangulation. For example, from a set of four points it is possible to form four diferent triangles. Among the four triangles only two triangles will satisfy Delaunay condition. It is a property of delaunay condition that the triangles are selected in such way that the minimum internal angles of the selected triangles are as large as possible. Due to this property, the member triangles are considered well shaped. This is important property as maximizing the minimum angle favors well-condition.
In Figure 4(a), the triangles satisfy the Delaunay condition as the circle does not have any points in them. In contrast to previous one, the circum-circles of the triangles in Figure 4(b) have points in them and hence these triangles do not satisfy the Delaunay condition. It can be observed that these triangles have sharper angles nodes V2 and V4 than the previous ones. There is always the possibility to convert this triangulation into Delaunay by replacing the edge V2-V4 with V1-V3 as this would increase the minimum internal angles and fulfillment of the Delaunay condition can be expected. Another property of Delaunay condition is it uses nearest-neighbor relation to connect the points. This enhances the implications of Delaunay triangulation in data interpolation as well. The concept of Delaunay triangulation for 3D is also similar, only the circum-circle is replaced by circum-sphere and triangulation by tetrahedrons.
BLE sensor registered advertisements anytime an advertisement is detected. Each BLE advertisement had its own timestamp value. Positioning requires analysing a group of advertisements that are closer in time. This made it necessary to group advertisements by time window. Two techniques of grouping window have been used namely i) Discrete Time Window and ii) Continuous Time Window.
(a) (b)
In the discrete time window technique, advertisements were collected in non-overlapping buckets for certain time, e.g. 1 second, 1.5 seconds, 3 seconds. Advertisements detected within a time window were grouped in same bucket. Then the advertisements in the bucket were used to compute position. After the time for a bucket expires, new bucket was created and the process was repeated.
Continuous time window features an extra update interval parameter on top of discrete window technique to allow having overlapping buckets. The update interval parameter dictates how often position is computed. In this technique, a bucket is created at set intervals e.g every 0.1 second or 0.5 second. Each bucket will collect advertisements for a certain time set by window size. Update interval is kept lower than window size so buckets overlap each other. An advertisement may fall in many buckets. When a bucket expires, position is computed from the advertisements collected in that bucket. In continuous time window technique the two latter advertisements get grouped into same window more times than the former two. This way simultaneous advertisements have more efect. This makes continuous window more sensitive than the discrete method. Disadvantage is that this technique runs more frequently and processes the same advertisement multiple times. It requires more computation resources than discrete technique so it may not be suitable for low end processors.
In both cases, it is possible that more than one advertisement from same beacon are observed in same bucket. In such case, those redundant advertisements need to be processed by computing the average value, keeping the highest value or just keeping the last value.
Weighted centroid method [24] is applicable where beacon positions (xi, yi) are known beforehand. The WC method uses k beacons detected with the highest RSS values in the BLE ifngerprint, where 1 ≤ k ≤ n n being the number of beacons deployed in the target area. The position estimate is given by the equation 1, using weights calculate by equation 2. where: ωi′ = weighting factor k = number of nearest beacons to consider for position estimate
k x = ∑︂ ωixi, i=1
k y = ∑︂ ωiyi i=1 (1) ωi = ∑︁kωi′ ′ j=1 ωj (2)
The weighing factor was computed using an existing empirical model developed for the test environment. The model exploits the reduction of signal strength during transmission. It converts an RSS value to a weight value. Higher signal strength get higher weight and lower signal strength get lower weights.
A new method was proposed to select beacons used in positioning. Due to the error in the RSS value, any calculations that use RSS values are prone to transfer the error. This method is based on the beacons layout. Known distance between beacons were more precise than distances computed using RSS values. Calculations based on precise distances should be more reliable than those based on less precise distances. The method works in following way. First, list of detected beacons in a window were arranged in descending order of RSS value. This was to arrange beacons in order of proximity. Signal strength decreases with increasing distance so higher RSS value correspond to closer source. After that, 3 nearest beacons were selected and checked for well-condition. If they satisfied well-condition then position was estimated as weighted average of the selected beacons. If the 3 selected beacons did not satisfy wellcondition, next proximal beacon was added to selection. It is possible to form four diferent triangle using combination of four points ((︁ 43)︁ = 4). With five points number of combination increases to 10 ((︁ 53)︁ = 10). An eficient way is required to reduce computation. Delaunay triangulation creates a triangular network that maximizes the minimum angle of any triangles in the network and the triangles do not overlap each other. This method is suitable to get well-conditioned triangles and reduce number of combinations. When multiple well-conditioned triangles were detected, weighted average of beacons in well-conditioned triangles was used as estimate. If no well-conditioned triangle are detected, next closest beacon is added.
Figure 6 shows the innovation of the proposed algorithm. The data is from library building
in the BLE open dataset [
Algorithm 1: Selection of beacons using well-conditioned triangle
Input: BLEscan = Detected Beacons, RSS, timestamp, major and minor Output: POsition Estimate Start; sort BLEscan in descending order of RSS; if number of detected beacons < 3 then output null; break; else selection = select first 3 beacons from BLEscan; /* Set list of well-conditioned triangles to empty WCTlist = []; while WCTlist is empty do
DT = DelaunayTriangulation(selection.location); // generate triangulation network from selected beacons location for triangle in DT do if triangle satisfy well-condition then add triangle to WCTlist; break; */ end else end if number of triangles in WCTlist = 1 then
compute position estimate; else if number of triangles in WCTlist > 1 then compute position estimate for each triangle; average position estimate; if all beacons used then output null; break; else end
add next beacon to selection end end end end
This method is based on the algorithm proposed by Weinberg [25]. When people move, there is vertical movement of body in each step. Weinberg [25] used vertical acceleration to detect step events and Stride-length for each step was computed by an empirical formula given in equation 3. Gyroscope was used to estimate heading at each step.
SL = 2∆ K ∗ (max(accmagstep) − min(accmagstep))1/4 */ (3) Algorithm 2: Stride-length and Heading Algorithm
Input: acc = Accelerometer data and gyr = Gyroscope Data Output: Stride-Lengths and Headings Start; /* Compute Stride-Lengths Compute magnitude of acceleration from all the components and store it -> accmag; Perform low-pass filter on the computed magnitude ; set lower and upper acceleration threshold; for each accmag do if accmag > lower threshold and accmag < upper threshold then
mark as motion start else else end else end end if accmag < - lower threshold then if previous state is in motion then mark as motion mark as motion stop mark as in motion end for each motion start do
Estimate Stride-length using Weinberg expression given by 3 end /* Compute Headings Calculate initial row, pitch and yaw values Create device to global rotation matrix for each gyr do
Update rotation matrix with gyr values */ end for each motion start do
compute heading from rotation matrix end
Output Computed Stride-Lengths and headings
Ka´lma´n filter is a popular method for sensor fusion. System variables are modelled as state variables, whereas the real observations modelled as observation state. Ka´lma´n filter works in two phases i) Predict Phase and ii) Update Phase. Predict phase applies a transition model to push one state to another state. This phase also computes the predicted co-variance in new state. In the update phase, newly computed states are combined with observation state using Ka´lma´n gain to output a filtered estimate. Ka´lma´n gain is a weighting factor calculated on basis of error co-variance of the transition model and the observation model. It tells how much to change the predicted state to reflect an observed state.
Position estimate from stride-length and heading are suitable for prediction phase as a new estimate is calculated from past estimates. Wi-Fi and BLE estimates are independent to previous estimates hence a transition model is not possible. This makes it unfit for prediction phase. On the other hand, position estimates from Wi-Fi and BLE are suitable for observation state as they provide a stable way to constraint error from prediction phase. The GetSensorData app collects IMU data in higher frequency than BLE and Wi-Fi data combined. This means that between two estimates from either of the network-based solutions, there are many position estimates provided by inertial-based solution. Hence, multiple prediction phases occur between two update phases. Ka´lma´n filter allows this but a mechanism to detect which phase to execute is required. A mechanism based on timestamp was devised to trigger correct phase execution.
Error is the euclidean distance between position estimate and true position. Position estimates are obtained from positioning methods described above. True positions are interpolated from the test track. All the readings have associated timestamp value. Exact start time, each direction change and exact end time are marked along with the sensor readings. Using the marks it is possible to interpolate true position at any intermediate timestamp. A script was made which take list of timestamps as input and output coordinates at those timestamps. BLE timestamps were derived from the window size and update interval values, for IMU timestamps of step detection were used. Now that estimated position and true position were known, error was calculated.
The evaluation area corresponds to the 5th floor of Universitat Jaume I library and covers an
area of around 176 m2, the area and device correspond to the the ones in [
The test data is captured with Samsung S6 smartphone (Model: SM-G920F) running on android version 7.0 and API Android version 24. The application used for data collection is GetSensorData version 2.1 which is also used by IPIN conference since 2016 [26]. The application captures data from android smartphone sensors and outputs them in a log-file. It supports capturing internal sensors accelerometer, gyroscope, magnetometer atmospheric pressure, ambient light, proximity, humidity as well as from attached external devices example RFID reader, XSsens IMU or LPMS-B IMU devices [26]. Since IMU measurements sufer from sensor bias, usually a calibration step is required where measurements are collected when the device is static and bias values are determined. GetSensorData app does not have a calibration option. But it has option to mark locations. A workaround devised was to stand still for some seconds before starting to walk
Figure 7 shows error distribution of the studied factors. On analysing the efect of each factor, it was observed that the choice of window technique had no drastic efect on accuracy. The average diference of average error was found to be 0.005m. Among the strategies for advertisement repeats, highest of the BLE repeats had the least error. It was followed by average of repeats. Last of the repeats had higher average error. Except on window size 3 using discrete window, error from highest of BLE was lower than other techniques. Proposed positioning method had similar result but lower variance than WC method. One-second window size fared higher errors than it’s counterparts. Window sizes of 2 and 3 seconds had improved results than 1 second. Window size influences efect of other factors on the error. It is reasonable to study afect of the factors independent to window size.
We considered two configurations for our final evaluation. First, the IMU Position estimates were fused with estimates from BLE on window size 2 seconds, continuous window grouping, highest of redundant advertisement and the proposed algorithm based on Delaunay Triangles. Second, the IMU Position estimates were fused with estimates from BLE on window size 3 seconds, continuous window grouping, average of redundant advertisement and the proposed algorithm based on Delaunay Triangles. The results are reported in Table 1 and Figure 8.
The results show that including the inertial data improve the positioning accuracy of the BLE model and viceversa. Moreover, additional experiments showed that the fused model based on WC –for BLE positioning– was around 15 cm worse in the third quartile, demonstrating that the proposed method for BLE positioning is more robust and less prone to very large errors.
Improving the positioning accuracy of Indoor Positioning Systems is attracting many researchers around the globe. Literature suggested that sensor fusion was one interesting approach for that purpose.
In this work, we considered to integrate IMU data with BLE readings since they available in most smartphones. Adding inertial data do not require to deploy additional infrastructure and no extra setups are required. Ka´lma´n filter ofered a simple, intuitive but powerful mechanism for fusion.
An experiment was designed for comparing accuracy before and after fusion. Existing system was used as baseline. Sensor fusion results were more accurate than BLE.
As future work we plan to include map-based filters as an additional source to improve the navigation experience.
The authors gratefully acknowledge funding from Ministerio de Ciencia, Innovacoi´n y Universidades (INSIGNIA, PTQ2018-009981) and Universitat Jaume I (PREDOC/2016/55)