Projects:2016s1-145 Indoor localisation using Bluetooth LE for Event Advertising
Location based services is a developing area encompassing a variety of useful services depending on a person’s location, such as indoor navigation and advertising based on location. An indoor positioning system is required to determine a person’s location accurately within an indoor environment to be able to provide these services. This project consists of the research and development of a smartphone-based indoor positioning system that can be used to advertise information to a user based on their location. Our proposed solution was to create the Mobile Indoor Navigation Information System (MINIS), using Bluetooth and ultrasound technologies to determine the location of a user, along with a corresponding iOS smartphone application to present location and advertising information to each user of the system. The Bluetooth and ultrasound components of the system complement each due to the different performance attributes associated with each method.
A positioning accuracy of 75 cm was desired from the beginning of the project, based on the size of stalls to be found during the Ingenuity Expo final year project showcase, where the system is intended to be set up and available for use. System testing showed that an average positioning accuracy of 77 cm can be achieved by the system in ideal cases, which is very close to the desired accuracy. It was found that non-line-of-sight between the ultrasound beacons and the smartphone device and number of Bluetooth beacons were the main factors that influenced system performance. In poor non-ideal conditions, the positioning accuracy was found to be between 2 and 3 metres depending on the location within the testing environment. Overall, the final system was able to sufficiently satisfy the primary aims that the project was based around.
Group members:
- Daniel Webber
- James Donovan
Supervisors:
- Dr. Hong Gunn Chew
- Dr. Cheng Chew Lim
Contents
Introduction
Aims
“How can we provide advertising information to users based on their location within a crowded indoor environment?" was the leading research question associated with this project. The following three primary aims were identified initially to satisfy this question:
- To research and determine the best method to create a smartphone-capable indoor positioning system
- To develop an indoor positioning system capable of determining a user’s location within a crowded indoor environment
- To advertise information to the user based in their current location
Our proposed solution was to create the Mobile Indoor Navigation Information System (MINIS), using Bluetooth and ultrasound technologies to determine the location of a user, along with a corresponding iOS smartphone application to present location and advertising information to each user of the system.
By the end of the year, we intended to have a complete indoor position system capable of determining the user’s location within the final project exhibition hall, with a high enough precision to be able to differentiate the location of individual stalls. We also intended to have a fully functional application released on Apple’s App Store to allow public use of our system.
Significance
Location based services is a developing area encompassing a variety of useful services depending on a person’s location, such as indoor navigation and advertising based on location. A positioning system is required to determine a person’s location so that these services can become available. Currently, the most used positioning system is GPS (Global Positioning System), which is primarily used to provide the user with their current position for vehicle navigation purposes. GPS excels in large open areas due to the existing satellite infrastructure and ease of use, but a different solution is required when dealing with indoor environments.
GPS requires line-of-sight with the satellites to operate correctly, and also provides the user with a location that can have an error of anywhere between 2 to 60 metres. This is not useful within an indoor environment as there is no line-of-sight with the satellites, and locations of interest may be within a closer distance than the error in distances given by GPS measurements, making it difficult to accurately determine whether you have reached the correct destination.
Indoor positioning systems solve this issue as they are able to provide location information when indoors and with high precision. We have aimed to find and use the best methods available to us to produce an easy-to-use indoor positioning system that is accurate and can cover a large area.
Motivation
This project has been undertaken to attempt to develop a refined indoor positioning system that performs well in a crowded indoor environment. A well performing indoor positioning system will give future large-environment providers, such as event holders and shopping mall owners, a strong option to consider when choosing a suitable indoor positioning system for their environment.
Both the end-user and environment provider will benefit from a wide-scale indoor positioning system. The users of the system will be able to easily navigate the environment so that they are able to reach their destination promptly, as well as giving them easy access to an overview of the entire environment. The event providers will benefit from having a location based advertising solution, enabling them to send targeted advertising to customers walking past a shop, giving them the ability to pique their interest in a sale they would have otherwise not known about.
Technical Background
Our indoor positioning solution uses Bluetooth and ultrasound technologies to determine the position of a user as accurately as possible. Both enabling technologies complement each other, as Bluetooth systems typically have a longer range but lower accuracy, and ultrasound-based systems typically have a shorter range but higher accuracy. This section describes the enabling technologies, and provides an overview of the important methods that will be used to determine the user’s location within the operating environment.
Bluetooth LE and iBeacon
Bluetooth LE (Low Energy) is a recent Bluetooth standard that supports Bluetooth communication devices that can operate with a much lower energy consumption, in exchange for a smaller data transfer rate. Most modern smartphones support this technology, making it perfect for a beacon-based indoor positioning system.
iBeacons are small communication devices that use Bluetooth LE and are designed to offer proximity-based services. These devices follow Apple’s iBeacon protocol, allowing them to broadcast identification information and have minimal power consumption. This broadcast allows for the receiving device to determine the signal strength, which can be used to calculate distances from the receiving and transmitting devices.
Bluetooth iBeacons are advantageous for indoor positioning systems due to their low cost, availability in modern smartphones, and availability of commercial products that exist using this technology, requiring no hardware development. iBeacon devices also have a larger range than typical ultrasound systems, but this can vary depending on the transmit power.
Ultrasound
Ultrasound-based indoor positioning systems typically exploit the speed-of-sound to determine time-of-flight from measurements of received times of signals. This is due to the relatively low propagation speed of sound compared to available computing power, as it takes sound roughly 3 milliseconds to travel just one metre. The range depends on the transmit power and frequency, maximised with the highest transmit power and lowest frequency. These can both be entirely configured as we have full control over the transmission method.
Most modern smartphones are capable of sampling audio at 44 kHz, allowing us to operate in the ultrasound frequency ranges of 20-22 kHz, as the upper-limit of human hearing is 20 kHz.
An ultrasound component for our indoor positioning system is considered due to the complementing advantages of both Bluetooth and ultrasound-based systems. Indoor positioning systems based on ultrasound technology typically have sub-metre precision when determining a user’s location. Ultrasound systems are low cost, as they only require a microcontroller and ultrasound speaker to act as a transmitter, and no external peripherals are required for the receiving smartphone due to the built in microphone.
Ultrasound systems based on time-of-flight calculations are however affected heavily by multi-path waves that bounce off of walls, so reflected signals may be interpreted as the signal currently being expected. The range of ultrasound beacons are usually lower than the range of Bluetooth beacons. While transmit power can be changed, this can result in the a greater multi-path effect on the system. A method of precise synchronisation is also required for ultrasound systems due to the need for each beacon to broadcast at a specific time to achieve accurate time-of-flight measurements.
Trilateration
Trilateration is a method used to determine the position of an object based on the distances measured between an object of unknown location and beacons of known locations. The figure shows an object of unknown position, surrounded by three beacons. Once the distances between the object and each beacon has been determined, the location of the object can be found by finding the intersection point between circles plotted around each beacon, with a radius equal to the distance measured.
Distance Measurement Methods
Before we can actually find the location of a user, the distances between the user and each beacon must be determined. The following methods are used to calculate the distances between the beacon and receiving device for either the Bluetooth or ultrasound component.
Received Signal Strength Indication
Received Signal Strength Identification (RSSI) is used for the Bluetooth component of the system, and uses the received signal strength to determine the distance between the user and the beacon. The received signal strength to distance measurement follows a log-distance path loss trend model as depicted in the figure. In practice, RSSI values are typically differentiable to an extent up until roughly 10 metres. From then onwards, the signal strength starts to show only small changes when distance is increased. When long distance measurements are coupled with noise, the calculated distances start to become unreliable.
Time of Arrival
Time of Arrival (ToA) is the primary distancing method used with the ultrasound component of the positioning system. This is used when the transmission time of a signal is known, and consists of calculating the difference between the receive and transmit times to work out the distance travelled.
Time Difference of Arrival
Time Difference of Arrival (TDoA) is similar to ToA, but instead calculates the relative distances between the receiver and transmitters to determine the location of the receiver. This method is useful as it does not require the time of transmission to be known, and the final result can also be used to find the initial transmit time as the position of the user and beacons will be known. The differences in time are converted to difference in distances using the same method as in Time of Arrival.
System Design
This section describes the design of each major component of the system, along with a discussion of the evolution of some design components that were influenced by results found or project constraints. The system design is split into four major components: the ultrasound positioning system, Bluetooth positioning system, combined system, and the iOS smartphone application.
Ultrasound System
System Overview
This section outlines the process that the ultrasound system follows to determine the position of a user within the operating environment of the system. The ultrasound component of the system consists of at least three ultrasound beacons placed within the operating environment, with the locations of the beacons registered on the smartphone application. The smartphone uses its built-in microphone to listen to ultrasound pulses sent from the beacons, which are then used to determine the distances between each beacon and the receiver. After finding the distances, trilateration is performed to find the position of the user.
Each ultrasound beacon is synchronised using a Radio Frequency (RF) pulse from a synchronising device, with Time Division Multiple Access (TDMA) employed to share the limited range of ultrasound frequencies available for use. TDMA requires that each beacon transmits an ultrasound chirp at the start of their allocated time division to allow for precise Time-of-Flight (ToF) measurements and to provide a transmission channel with minimal interference.
Each ultrasound chirp is received by the smartphone with some delay from the original transmit time, depending on the distance between the beacon and receiver. The difference in distances of each beacon are calculated after determining the chirp receival times. The phone uses the TDoA method to determine the initial position, as well as the time at which each beacon initially transmits their signals as only the differences in distances are known. Once the transmit time is known, the less computationally expensive ToA algorithm is used to determine the user’s location as the absolute distances can now be found. If there is an unexpectedly high change or inconsistency in distance or position, the current results are discarded and the beacon transmit times are redetermined with the use of TDoA. This allows for a more robust system that can withstand errors in measurements, additionally providing the ability for users of the system to walk from one area being synchronised by one synchroniser, to another set of beacons being synchronised by another synchroniser that transmits RF pulses at different times.
Beacon Hardware
The final beacon design consists of an Atmel Atmega 328 microprocessor, three ultrasound speakers to cover a 360 degree angle, a wall clamp, a 433 MHz RF receiver, and a 9 Volt battery. The Atmega microprocessor was chosen as it is the same microprocessor used in the Arduino Uno prototype beacons, allowing for minimal code changes and testing when iterating from the initial prototype beacons. Each ultrasound speaker is powered by a half-H-bridge setup to reduce current draw from processor pins. Development of these beacons began after confirming that the system behaved sufficiently well during the Arduino Uno prototyping phase. We chose to make our own beacons to satisfy the budget constraints of the project, as the costs were lower to produce our own hardware than continuing to use and purchase more Arduino devices.
Bluetooth System
The Bluetooth component of the system primarily provides assistance with the ultrasound measurements, as well as being a backup for when erroneous results are obtained using the ultrasound system. Information is obtained using the Bluetooth LE protocol, allowing for a long beacon battery life and easy acquisition of data. See for a more in-depth discussion of more advanced techniques that were proposed for this system, but not implemented due to time and hardware constraints.
System Overview
The analysis of the received signal strength identification (RSSI) data is the primary issue for the Bluetooth component of the system. The flowchart outlines the process followed by the Bluetooth system to determine the user’s position.
The Bluetooth beacons send multiple packets per second to assist in the reduction of the effect of outliers when processing data. After extracting the RSSI value from the information packet, the distance between the receiver and beacon is found by the use of a static path-loss model. This curve was parametrised using the average RSSI values of various beacons over various distances, with the same parameters used for each beacon. While these parameters do differ per beacon, the operating environment also affects the model parameters. Due to time constraints and the complexity of this issue, a static model has been used that can satisfactorily determine the user’s location. The use of precise ultrasound position calculations to parametrise the propagation parameters would be a good future addition to the system to improve the accuracy of the Bluetooth system. The position is then calculated from the distances using trilateration.
Due to received RSSI values having a large number of outliers while continuously receiving values, it is necessary to process the data using Kalman filtering to reduce the effect of outliers.
Beacon Hardware
RadLogic’s RadBeacon Bluetooth LE devices shown below are used as the beacon hardware for the Bluetooth component of the system. These devices are pre-made and use the Bluetooth LE protocol, requiring no hardware development or manual signal processing to retrieve the data needed. These devices support a variable transmit power and packet rate.
Combined System
The Bluetooth and ultrasound results are combined to complement each system to increase the robustness of the system.
System Overview
The combination of the results is done in such a way that the best aspects of each positioning system component are considered to produce a more robust final position result. The flowchart outlines the processed followed to combine the Bluetooth and ultrasound results into a single position estimate.
After receiving a Bluetooth or ultrasound position update, if there has been no recent ultrasound or Bluetooth position updates, respectively, the received position update will be used as the final position update. If there are recent updates for both ultrasound and Bluetooth positions, the process of checking for distance errors is followed.
As ultrasound measurements are typically more accurate than the Bluetooth measurements in ideal conditions, The ultrasound position is used in precedence of the Bluetooth position calculation if there is a low difference error between recent Bluetooth and ultrasound positions. If there is a large discrepancy between Bluetooth and ultrasound position, it is assumed that the error is a result of the ultrasound system incorrectly interpreting noise as a chirp, resulting in the system accepting the Bluetooth position as the true position. This process provides a robust system that is accurate and precise in the best situation, but still available for use in the worst case scenarios.
Beacon Placement
The system aspects discussed in this section are the leading factors to consider when determining the placement of beacons. The placement of beacons is primarily determined by the results found during testing. These results show how noise, non-line-of-sight between beacons and the receiver, and other factors affect the accuracy and precision of the system.
In terms of the ultrasound beacon placement, it is important consider line-of-sight if high accuracy and precision is desired. The ultrasound system update speed is based in the background noise level in the operating environment, requiring the closeness of ultrasound beacons to be considered based on desired system performance.
The number of Bluetooth beacons and the spacing between them is the primary concern for Bluetooth positioning performance, along with the propagation characteristics needing to be set appropriately depending on the operating environment.
iOS Application
The iOS application is written in Objective C, and has been developed to provide users with access to the navigation and advertising information provided by the MINIS system.
As of the end of this project, the Mobile Indoor Navigation and Information System (MINIS) contains the following major features:
- Bluetooth, ultrasound and combined positioning system
- Map display that shows user, point of interest, and beacon locations
- Internet downloading of event data for external configuration of event data
- Webpage display when in proximity to registered point of interest
- Display of distancing and position information
Experimental Results and Analysis
This section describes the results achieved during the final stage of the project, with an analysis of the results also included.
Mezzanine Position Testing
The University of Adelaide Mezzanine was chosen as the initial testing venue due to the low noise level and large open space, allowing for an optimal testing setup with full line-of-sight between the beacons and receiver available.
Three ultrasound and Bluetooth beacon pairs were placed in a triangle to provide complete coverage of one cell. Five ultrasound and Bluetooth positions were recorded at each interval of 3 metres in the X and Y directions, from zero to nine for each coordinate, resulting in a total of 16 discrete positions measured.
Ultrasound System
The chart depicts the mean value and precision of each position measurement, with the expected position shown in the label of each position.
The size of each beacon represents the calculated precision of the five measurements relative to each other for each position, and the position represents the mean X and Y values of each set of position measurements. Note that each expected position is found at the intersection of the X and Y major grid lines.
[tab:mezzus]
| Mean Position Error (m) | Precision (m) | |
| Max | 1.33 | 3.20 |
| Min | 0.27 | 0.36 |
| Average | 0.77 | 1.10 |
Initial observations show that the ultrasound position measurements in this scenario closely line up with the true position they were measured from in most cases. Some points are very precise, as indicated by the small circle, and most points are around or within a metre of their expected location. In terms of numerical values, the average distance error between calculated and true position is very close to the desired accuracy of 75cm. The maximum mean error of 1.34cm is also fairly reasonable for the worst case result in this scenario. The precision values indicate that the results are consistent in most cases, although with some outliers that produce undesirable results.
In terms of qualitative properties of the ultrasound system during this testing, it was noted that inaccuracies sometimes occurred due to the orientation of the device. When standing close to a wall with the microphone oriented to be facing away from one beacon but not the other two, the reflection from the wall sometimes took precedence over the non-reflected pulse. Another observation included when moving at a reasonable walking speed, the position estimate sometimes appeared to have less precision than when standing still. Also, since the update speed is determined by the receival times of chirps, the update speed was a non-ideal one update per second.
Bluetooth System
The chart shows the accuracy and precision for the same positions as above but for the Bluetooth system.
[tab:mezzbt]
| Mean Position Error (m) | Precision (m) | |
| Max | 6.85 | 1.92 |
| Min | 1.24 | 0.22 |
| Average | 3.65 | 0.97 |
These results show that in the scenario of testing within one cell of three Bluetooth beacons, poor performance with mass clustering occurs. Position measurements on the boundary of the testing area were typically outside of the middle clustering, but still had errors of above three metres in some cases. The numerical results shown above indicate that the average minimum, and maximum position accuracy error values are largely above the desired value. The precision of the results is however an small improvement over the ultrasound measurements, possibly due to the Kalman filtering and lack of similar propagation issues that the ultrasound system faces.
In terms of responsiveness and update speed, the Bluetooth position updates are much smoother than the ultrasound results due to the much larger rate of input data acquired, providing a practical amount of data for effective Kalman filtering. Note that although adjusted for in this test, the log-distance model used to estimate distance from RSSI values may have been able to be improved to produce more accuracy results.
Combined System
As the ultrasound positioning system component was able to provide consist low error measurements, the combined system behaviour was not able to be tested effectively. It could however be observed that halting the RF synchronisation signal to the ultrasound beacons resulted in the Bluetooth system taking over as expected, due to the lack of ultrasound position updates. While the transition between systems is not discreet due to the differences in position acquisition behaviour as described in the ultrasound and Bluetooth sections above, the Bluetooth system does provide a backup that would otherwise result in a non-functioning system in some situations.
Project Lab Position Testing
The project lab used over the development of the project was the second venue used for testing. This area has large shelves on each bench, allowing this environment to be used to test the non-line-of-sight effects of the system. The project lab also had many students in it, allowing for a test to be performed with a louder environment.
The testing area covered is longer but less wide than the Mezzanine, allowing for different propagation characteristics. In this test, two cells were used for testing; one with ultrasound and Bluetooth beacons, and the other with only Bluetooth beacons. This allowed us to also test for ultrasound performance when not within the intended cell to be located within, and also to test how the Bluetooth component of the system behaves with more Bluetooth beacons.
Ultrasound System
The figure shows the accuracy and precision of the ultrasound position measurements within the project laboratory.
[tab:em307us]
| Mean Position Error (m) | Precision (m) | |
| Max | 7.88 | 6.70 |
| Min | 0.82 | 0.74 |
| Average | 3.07 | 2.56 |
These results show that obstacles in the environment that prevent line-of-sight between beacons and the receiver greatly degrade the performance of the system. As shown in the results table above, the average and maximum mean position error and precision are much larger than in the previous test, while still having reasonable minimum precision and mean values. The most precise position measurements were found for points that had line-of-sight of two or more beacons, either directly or through gaps in the shelves above the desks. The positions with lower differences between measured and true location was found to also have line-of-sight with at least one beacon, and in a location that is not heavily affected by multi-path waves, such as in the corner of the room.
The points affected by the the wall and room on the lower part of the testing area are shown to typically exhibit average precisions, but are very far off of the true position in most cases. The general trend of non-line-of-sight resulting in a larger distance can also be observed for most data points, with measurements on the bottom with no line-of-sight towards beacon 1 and 3 having a lower Y value than expected, and results taken along the X axis with no beacon 2 or 3 line-of-sight have a larger Y value than expected.
It should also be noted that with only three beacons, there is no large change in performance of positioning either within or outside of the cell of three beacons, indicating that as long as the beacons are placed far enough apart, the system will still perform as expected.
Bluetooth System
[tab:em307bt]
| Mean Position Error (m) | Precision (m) | |
| Max | 5.43 | 5.61 |
| Min | 1.03 | 0.57 |
| Average | 2.87 | 2.26 |
The accuracy of the Bluetooth system is improved slightly in this scenario when compared to the Mezzanine testing. The system is less precise than during the initial test, but has approximately the same precision and accuracy characteristics as the ultrasound system. While the performance of the system has only improved marginally from the original test, this larger testing environment with more beacons was able to demonstrate that the system is able to behave consistently over a larger area with more beacons, compared to the results found during the first test that primarily only showed undesirable clustering behaviour. These results show that the Bluetooth system is can sufficiently determine the user’s location within 3 metres in most cases due to the consistency of results over the large area tested. It can also be noted that the Bluetooth results are consistently closer to the center of the beacon setup, indicating that the log-distance model may have been able to be adjusted to improve results to an extent.
Combined System
The combined system behaviour was only able to be tested somewhat sufficiently when walking to the corner of the workshop room in the bottom-right side of the testing environment. Due to large distance errors caused by different chirps reflecting differently when entering the room, the position error was consistently high. Due to the high error, the Bluetooth system results were prioritised, resulting in a transition between ultrasound to Bluetooth measurements with similar precisions and accuracies.
Conclusions
In terms of the guiding research question of “How can we provide advertising information to users based on their location within a crowded indoor environment?", the project aim has been fulfilled as we have successfully undertaken research to determine the best way to advertise information to people within an indoor environment depending on their location. We have developed the Mobile Indoor Navigation Information System to provide users of the system with their location and relevant information depending on their location, using an underlying positioning system that uses Bluetooth and ultrasound beacons. Appropriate research was conducted to decide to add the ultrasound component into the system that was originally intended to only use Bluetooth for positioning. Due to the complementary natures of the two methods as discussed in section [sec:background], and the lack of external peripherals required for the smartphone receiving device, this was a well suited addition to the positioning system.
The completed system in ideal cases was on average able to achieve the desired accuracy of 75 cm in ideal conditions, while having an accuracy of 2 to 3 metres depending on the position when in a non-ideal environment as discussed in the results section.
Future Work
There are many possible features and improvements to continue and complete for future iterations of this project, as listed below:
- Implement multiple ID beacons support
- Find less interference-prone method of ultrasound beacon synchronisation
- Parametrise Bluetooth distance model based on ultrasound position
- Implement sensor fusion technique to combine Bluetooth and ultrasound measurements
- Implement list of points of interest and navigation assistance in smartphone application
- Reduce effect of non-line-of-sight and multi-path effects for the ultrasound system
- Improve robustness of distancing and positioning algorithms
- Support three-dimensional positioning
In addition to these features and improvements, possible future expansions could include creating a software platform that allows external parties register their own information with the event, and general refinement of hardware and software to provide a complete and reliable position system for public use.
References
S. Wang, J. Min, B. Yi, Location Based Services for Mobiles: Technologies and Standards, [Online]. Available: http://to.swang.googlepages.com/ICC2008LBSforMobilessimplifiedR2.pdf, [Accessed: 18.04.16]
S. Skone, M. El-Gizawy, S.M. Shrestha, Limitations in GPS Positioning Accuracies and Receiver Tracking Performance During Solar Maximum, Department of Geomatics Engineering, University of Calgary, Alberta, Canada
D. Stojanović, N. Stojanović, Indoor Localization and Tracking: Methods, Technologies and Research Challenges, Automatic Control and Robotics Vol. 13, No 1, 2014, pp. 57-72
P. Lazik, N. Rajagopal, B. Sinopoli and A. Rowe, Ultrasonic Time Synchronization and Ranging on Smartphones, Real-Time and Embedded Technology and Applications Symposium (RTAS), 2015 IEEE, Seattle, WA, 2015, pp. 108-117
P. Lazik, N. Rajagopal, B. Sinopoli and A. Rowe, ALPS: A Bluetooth and Ultrasound Platform for Mapping and Localization, Proceedings of the 13th ACM Conference on Embedded Networked Sensor, 2015, pp. 73-84
G. Anagnostopoulos, M. Deriaz, Accuracy Enhancements in Indoor Localization with the Weighted Average Technique, Institute of Services Science, University of Geneva, Geneva, Switzerland
T. Hao, R. Zhou, G. Xing, M. Mutka, WizSync: Exploiting Wi-Fi Infrastructure for Clock Synchronization in Wireless Sensor Networks, Department of Computer Science and Engineering, Michigan State University, East Lansing, USA
J. Liu, Survey of Wireless Based Indoor Localization Technologies, Department of Computer Science and Engineering, Washington University, Missouri, USA, 2014
I. Chan, Swept Sine Chirps for Measuring Impulse Response, Stanford Research Systems, Inc., California, USA, 2010
R. Faragher Understanding the Basis of the Kalman Filter Via a Simple and Intuitive Derivation, [Online]. Available: http://www.cl.cam.ac.uk/~rmf25/papers/Understanding%20the%20Basis%20of%20the%20Kalman%20Filter.pdf, [Accessed: 10.10.16]
