Field research of Bluetooth Low Energy use for indoor positioning on Android

I've started investigations and practical tests of the modern Bluetooth Low Energy (BLE) technology applicability for indoor positioning tasks. This technology has been built with many useful applications in mind from very beginning, including IPS of course. The main question was if the technology is mature enough and widely adopted to provide real value.

You may perform a quick search on Internet and find numerous papers with academic research on the subject. I did it as well, and most interesting and thorough article was "An Analysis of the Accuracy of Bluetooth Low Energy for Indoor Positioning Applications" by R. Faragher and R. Harle. It mentions almost all Pros and Cons of BLE, and provides practical results of a comparison between WiFi- and BLE-based positioning approaches. Most important conclusions that I made for myself after the reading are:

• a special non-connectable BLE devices are preferred for building IPS infrastructures because of their continuous discovery (connectable devices are reported only once per each scan request); as far as specific building environment may not comply with this requirement, a mobile application should explicitly repeat BLE scans in a loop, which may lead to additional resource consumption and occasional hangs (find more details below);
• BLE signal range is shorter than WiFi's one, and RSSI level of the same beacon may change significantly as a result of ad hoc switching between 3 frequency bands used by BLE internally (it can be a problem to sort out measurements by BLE channel using provided mobile APIs); thus, a special fingerprinting algorithm should be used with an emphasis on specific beacon existence instead of its RSSI, or deep smoothing should be applied, making processed RSSI values more inertial;
• a single BLE scan should be performed at least once at a second in order to provide 1-2 meter positioning accuracy; unfortunately this parameter can be hardly manageable and limited by hardware implementation specific to every manufacturer;
• according to the article, BLE scanning is negatively affected by enabled WiFi receiver, so for better results BLE should be used while WiFi is disabled, which may not be feasible for all use cases;
• for best result at least 5-6 beacons should be detectable in every spatial point; combining the fact with the fast decay of BLE signals one can deduce that a high density of beacons is required for good positioning performance;

Just as illustration of the issues mentioned in the 1-st and 3-rd points, here is a related discussion on the StackOverflow. To recap: BLE implementations may vary significantly between Android versions. This makes it difficult to build an application with consistent BLE behaviour on all variety of Android market, supporting BLE at the moment (70% of Android devices).

I added BLE scanning and fingerprinting in a test version of WiFiLine. One additional observation is that BLE is not yet widely used in local stores here in Moscow. Actually the number of BLE devices is 10-100 times less than WiFi hotspots. My thought is that BLE is not yet ready enough for efficient public use.

If you think you know a place with good BLE coverage and you're ready to play with the experimental version of WiFiLine, please, let me know and I'll send it to you.

OFF: how Google makes Android worse

Some days ago I got OTA update with Android 5.1. This version does probably improve something, but it apparently impairs other things as well. And because it's related to the system carousel - the list of running applications (on the so called "recents" screen) - which has bad design from the very beginning of Android 5, I couldn't help but writing about this miserable part of UI.

First, I must say that the carousel is constantly changing from one Android version to another between horizontal and vertical layout, as though Google's developers are uncertain themselves which variant is appropriate. The carousel is used intensively, so even a little flaw in its design brings big problems. I'm currently speaking about standard Android in general, and standard Android 5 in particular. Other customized firmware may be free of the issues I'm going to describe.

In Android 5, the carousel is always vertical on my pad. Well, it could be appropriate for portrait screen orientation, but the carousel remains vertical even in landscape mode. When you try to flip through the apps from bottom to top, you will constantly activate the central button of the navigation bar, floating in foreground (over the carousel!), especially because the button has an enlarged sweetspot, because it's Google button (it invokes "Google App" including quicksearchbox and other stuff). It took me a long time to get accustomed to the new - not so convenient - practice: in order to swipe apps from bottom to top, one should swipe from center! Otherwise you'll get into the Google app.

That's how it was since Android 5.0. In Android 5.1 they introduce new strange bug in the carousel. It does not work when you tap an app in it first time. After the first tap the carousel is closed and the launcher is shown. Only if you open the carousel second time, it works as expected.

I know, this is far from the main subject of the blog, but at last it's all about Android. And I'd prefer that Android would not prevent me from working with my applications.

WiFiLine's synthetic probability algorithm revealed

As I promised, I'm posting a short explanation of the built-in "synthetic probability" location algorithm. To start with it let us consider how WiFi data looks like. When you scan a building you get a list of geographical points with WiFi measurements, each of them contains signals from several hotspots, and every hotspot signal is normally detected many times demonstrating varying levels - so called RSSI (Received Signal Strength Indication). All this data is stored in the map, and can be viewed - just switch to the "Scan and Edit" mode, open the list of points and expand any of them - you'll see the names of hotspots detected in this point. Tap a hotspot to open a dialog presenting this spot's RSSI distribution.

Usually it's bumpy, but the more scans you perform in a point the more smooth distribution you get. According to the Central Limit Theorem the distribution tends to be Normal (Gaussian), so one can estimate its mean and standard deviation. This is where the word "synthetic" in the algorithm name comes from: it implies that we can build a synthetic (near to real, yet artificial) probability distribution (mass) function from acquired WiFi data.

Of course, this is just a probability of getting specific signal level of a hotspot S in a point X. We need to combine all such probabilities somehow in order to calculate current user location. And here is the Bayes theorem comes in handy.

P(A | B) * P(B) = P(B | A) * P(A), where

• P(A) and P(B) are the probabilities (priors) of A and B independent of each other;
• P(A | B) is the conditional probability of A given that B is true;
• P(B | A) is the conditional probability of B given that A is true;

Now let us add some suffixes to bring it into our context:

P(As_i | Bx_j) * P(Bx_j) = P(Bx_j | As_i) * P(As_i), where

suffixes 's_i' and 'x_j' stand for i-th hotspot and j-th point respectively, so:

• P(As_i) is the prior probability of i-th hotspot;
• P(As_i | Bx_j) is the conditional probability of observing i-th hotspot in j-th point;
• P(Bx_j) is the prior probability of j-th point;
• P(Bx_j | As_i) is the conditional probability of being in j-th point provided that i-th hotspot signal is detected;

Apparently, it's the last probability which we are after:

P(Bx_j | As_i) = P(As_i | Bx_j) * P(Bx_j) / P(As_i)

In the right side of the equation, P(As_i) can be estimated as a percentage of points where the hotspot Si was detected. P(Bx_j) is initially 1/N for every point, where N is the total number of points, but later it can be refined by applying our knowledge about current user location and reducing N to a reasonable neighbourhood. At last P(As_i | Bx_j) is the probability obtained from the synthesized probability distribution of signals described above.

Having P(Bx_j | As_i) for different i-s in every point j, we should combine them by hotspots (by i) in order to get the total probability of point Xj. According to the formula of mutually non-exclusive events:

P(Xj) = P(Σi(Bx_j | As_i)) = 1 - Πi(1 - P(Bx_j | As_i))

The point with largest value (or an average of K points with largerst values) is most likely the current location of the user.

This is a simplified description of the "synthetic probability" algorithm. It does not cover many nuances such as signal level calibration and in-motion scanning but gives you an idea of how WiFiLine works behind the scenes.

New WiFiLine version has been released

New version of WiFiLine - 1.1.3 - has been just released. The main changes are:

• debug marks with current user position(s) detected by all built-in algorithms are now optional and disabled by default; in order to enable the marks, one should enter "debug:on" in the processing command line (described some time ago in the blog); "debug:off" disables the marks;
• the naive multiplier algorithm has been changed a bit, but it's still an experimental thing;

According to latest tests in fields, recommended methods are extended fingerprint and synthetic probability again, as they were before. Position accuracy is 10 meters. I plan to shed some light on the probabilistic method in a future. As for neural network, it requires manual finetuning of input data to get best results. For example, it could be worth removing some non-discriminative hotspots from the map.

Готовится новый выпуск WiFiLine

В разработке и тестировании находится следующая версия WiFiLine. Вот основные изменения:

• Отладочный вывод на карту меток с результатами работы всех алгоритмов позиционирования сделан опциональным; по-умолчанию, он отключен; чтобы его включить, необходимо ввести в командной строке "debug:on";
• слегка изменен алгоритм naive multiplier, он все еще является экспериментальным;

По итогам полевого тестирования, рекомендуемыми по-прежнему являются методы расширенного отпечатка и синтетической вероятности. Точность позиционирования - 10 метров. В одной из следующих публикаций я расскажу более подробно о вероятностном методе. Что же касается нейронной сети, то для получения с ней хороших результатов, требуется тонкая ручная подготовка исходных данных, в частности, удаление некоторых хотспотов с малоинформативными сигналами из карты.

ОФФ: коллективное гипертекстовое литературное творчество

Не так давно я опубликовал один свой проект, никак не связанный с темой навигации, и чтобы не заводить отдельный блог по нему, решил дать краткий анонс здесь - все-таки автор один и тот же. Проект был начат много лет назад и, что называется, "лежал под сукном".

Это веб-сервис для коллективного гипертекстового литературного творчества. Если кратко, то он предназначен для коллективного написания и чтения гипертекстовых произведений с разветвленными альтернативными сюжетами, динамическим перестроением персональной версии произведения по запросу пользователя, и голосованиями по любому фрагменту, по результатам которых на лету получается наиболее популярная версия.

В отличие от систем класса wiki, единицей редактирования является не статья, а предложение (фрагмент). Выбор последовательности предложений осуществляется подсчетом их голосов (версия сообщества) или пользователем (персональная версия), а не путем долгих обсуждений каждой правки на отдельной странице.

Сам сервис расположен по адресу hyperfiction-orienteer.rhcloud.com, а более подробное описание - на отдельной странице. Но одна картинка, как известно, стоит сотни слов, поэтому вот краткая презентация:

Каковы общие тенденции рынка в этом направлении? И в печатной литературе, и в электронной форме имеется много произведений с коллективным авторством. Также в интернете выложены многочисленные гипертекстовые произведения, в которых можно менять поток чтения с помощью переходов по гиперссылкам. Интерес к подобным экспериментам находится на подъеме. Интернет, проникший во все сферы жизни, подсказывает пути развития литературы в сторону её социализации (использование социальных сетей) и проактивного отношения к сюжету. Имеются многочисленные примеры форумных ролевых игр, принцип которых заключается в пошаговом описании каждым пользователем действий своего героя в ответ на описания действий героев других пользователей. Известны случаи написания произведений в виде постов в социальных сетях, включая Твиттер. В общем, существует тенденция "интернетизации" литературных форм, что включает коллективное творчество, публичную оценку, многовариантность мнений, интерактивность.

В чем слабые места вышеназванных конкурирующих инструментов? Форумным ролевым играм мешает в развитии использование неприспособленных под их специфику форумных движков. Статическим гипертекстовым произведениям не хватает интерактивности и гибкости. Закрытые коллективы авторов не позволяют пользователям самим принимать участие в творчестве и влиять на произведение хотя бы в виде оценки фрагментов. Все элементы предлагаются разрозненно, и полноценной системы для коллективного, интерактивного, многовариантного создания произведений не существует. Ну или не существовало.

Данный проект - одно из возможных решений.

New map visualization feature is available in version 1.1.2

New version 1.1.2 of WiFiLine has been just released. It introduces new map visualization. In the Location mode, a map can now automatically rotate according to user's "view" direction. This makes it easier for user to take his or her bearing, but may create some difficulties in reading labels on the map.

New feature can be enabled in the context menu of the main screen. By default it's disabled, and maps are shown in the standard way: floorplan is static, and user's current bearing is indicated by a green sector inside the compass. When the feature is enabled, there is no a green sector in the compass, because user's "viewing direction" is always forward (up on the screen), and the compass shows only blue and red sectors for the North and the South.

The rotation of a map is performed around the point of user's current location. If current location is unknown (which is possible if navigation was not started, or the algorithm failed due to incomplete or irrelevant WiFi data), map remains static in its default orientation.

In other modes - Scan and Edit, Hotspot signals - the new visualization made intentionally unavailable, otherwise it would be hard for user to edit and analyze the map.

Режим отображения карты с изменяющимся азимутом

Для следующей версии WiFiLine готовится новый способ отображения карты в режиме навигации. В нем карта постоянно поворачивается в соответствии с текущим направлением "взгляда" пользователя. Это позволяет проще ориентироваться на местности, однако может затруднить чтение надписей на карте.

Режим переключается из контекстного меню главного экрана. По-умолчанию он выключен, и поведение карты аналогично прежним версиям программы, то есть отображение плана статично, а текущее направление "взгляда" пользователя обозначается подвижным зеленым сегментом в компасе. Если новый режим включен, карта будет целиком поворачиваться синхронно с поворотом пользователя на местности, а компас отображается без зеленого сегмента (только синий и красный сегменты с направлениями на север и юг), поскольку "взгляд" всегда направлен вперед (вверх экрана).

Следует отметить, что автоматический поворот карты производится относительно последнего определенного местоположения пользователя, поэтому если точка еще не найдена (например, если навигация вовсе не запускалась или определить местоположение просто не удалось), карта остается статичной.

В режиме редактирования и анализа WiFi сигналов данный способ ориентации недоступен, чтобы не осложнять пользователю работу с функциями редактирования.

Processing commands for WiFi maps

In the previous post I have started a story about built-in processing commands for WiFi maps. But the story came out too long for a single post, so I have only managed to cover the starting phase: how to open the command line and how does it look like. Today I'll describe the commands themselves. You can enter several commands in a row delimiting them by spaces. The commands will be executed in the same order as they occur in the editbox.

• clear:name - clears names of all points
• clear:neighbors - clears all neighbors (links between points); can be useful after attempt to generate neighbors with inappropriate neighborhood radius
• clear:signals - clears detailed WiFi measurements (scans) stored in points, but leaves information about detected hotspots and their average signal levels in each point - this may help to shrink map size but prevents probabilistic location algorithm from functioning
• lineup:IDs-IDe - aligns a series of successive points with identificators IDs-IDe to the starting point IDs; IDs can be larger than IDe or vice versa; alignment is performed in direction with longest distance between points IDs and IDe, for example, if delta in X coordinate is 1000 and delta in Y coordinate is 100 the points will be aligned in a horizontal line with Y equal to Y of the starting point IDs and preserved X coordinates
• stretch:IDs-IDe-PERCENTS - expands or squeezes a series of points in direction from IDs to IDe; again IDs can be larger than IDe or vice versa; the PERCENTS is the added fraction of initial distance between the starting point and every other point till the point IDe; for example, if PERCENTS is 10, all points will be moved by 1/10 part of their corresponent distances from IDs; both X and Y directions will be affected
• shift:IDs-IDe-DX-DY - shifts the points from IDs to IDe by the specified number of image logical pixels in X and Y axes correspondingly

Here is the example of processing command executed on the Kaleidoscope map:

clear:name lineup:1-116 lineup:117-221 lineup:478-462 lineup:435-461 lineup:479-499 lineup:412-434 lineup:385-411 lineup:355-384 stretch:479-499-12 shift:550-575-5-0

The same commands can be executed automatically during XML-map loading. For this purpose a new XML-tag was added to the map specification: preprocess. The tag is optional. The map header example:

<place xmlns="http://weborienteer.com/wifiline">
  <desc>
    <header>
      <id>RU.MM.SZAO.KA</id>
      <name>Kaleidoscope Shopping Center</name>
      <date>2015-01-10 10:10:10</date>
      <coordinates longitude="37.4446" latitude="55.850567" />
      <format>1.2</format>
      <images default="1" scale="85">
        <image floor="1" svgfile="k1.svg" azimuth="155.0"></image>
      </images>
      <preprocess>clear:name lineup:1-116 lineup:117-221 lineup:478-462 lineup:435-461 lineup:479-499 lineup:412-434 lineup:385-411 lineup:355-384 stretch:479-499-12 shift:550-575-5-0</preprocess>
    </header>
  </desc>
  ...

This new feature will hopefully help to refine WiFiLine maps and make them good looking.

Secret command line for WiFi maps postprocessing

In one of my previous posts I have introduced new WiFiLine map. This is a demo map created for a shopping center in Moscow, this is why it was announced in Russian only. The most important thing about the map is that it was scanned using new continuous scanning mode. And if you look at the screenshot of the map (in this post), you may wonder how it became possible to line up all measurement points in horizontal and vertical axes. If you ever tried to scan a map in WiFiLine you may know that points appear at shaky locations because they follow your touches, and these manual operations can hardly be perfectly aligned.

Of course, one could export the map into XML-file and edit coordinates of the points manually, but this would be a lot of work. Fortunately, new WiFiLine provides a convenient way for polishing maps in semi-automatic manner. Let me describe how to unlock some features hidden by default.

First, make sure that Scan and edit mode is enabled. Then open right-side panel with the list of scan points. Touch the header "Points" with one finger and hold it, then tap the header with another finger. This will open an additional panel with command line at the bottom of the screen, similar to what is shown on the following screenshot.

Please notice there is a 2-state button S/n in the right corner. If you press it, the list of points will be switched to an alternative view, where every point is expanded with its neighbors (only identificators of neighboring points are shown).

In this view, a tap on a link will bring a confirmation dialog for deletion of this link. Press OK to confirm or No to cancel this action. Don't forget that links can be (and usually are) bidirectional, that is point N2 is listed as a neighbor in the point N1 and vice versa. By removing a neighbor in one of the points (for example, N2 from N1) you do not automatically remove the symmetrical link in opposite direction (N1 from N2). If you want to remove both links you should delete corresponding neighbors in both points. It can be necessary to delete the link if both directions if there is a wall between the points. And it makes sense to delete a link only in one direction and keep it for another if the points are connected by a one-way escalator.

Why do you need to delete some links? Well, because it's very usefull to generate a mass of links between points automatically by means of the command Generate neighbors. It will take current Neighborhood radius from the Settings and bind every two points with a distance less than the given number of meters between them. Of course, this is fast and justified, but this is also a bit straightforward, in the sense that any real-world obstacles are not taken into account. This is why it's normally required to remove impossible links between automatically generated neighbors.

By pressing the button s/N once more you revert the list of points to its initial view with hotspot signals inside every point.

Well, finally we get to the command line itself, and I'd like to write you about fancy postprocessing commands, but this post does already look like a fat one. So let divide it into 2 parts. So I'm writing here:

To be continued...

Опубликована новая демо-карта

На сервер добавлена новая карта навигации для торгово-развлекательного центра "Калейдоскоп" (её изображение уже было опубликовано в сообщении More details about future version of WiFiLine: part III). Это демо-версия - в ней имеется лишь первый этаж, причем без детализации о конкретных торговых объектах и без поиска. Однако она позволяет оценить навигацию по холлам.

Карта была получена с использованием нового режима сканирования в движении. Именно поэтому точек сканирования так много, и они расположены по прямым линиям. После сканирования были использованы встроенные функции "Генерации соседей" и "Генерации дополнительных измерений" (об этой возможности рассказывалось в анонсе версии 1.0.18).

Вас может удивить, что линии серий сканирования в большинстве своем идут строго по горизонтали или вертикали, чего трудно было бы добиться в ручном режиме. Действительно, они были отредактированы с помощью специальных функций постобработки карты, о которых я расскажу в одном из будущих постов.

Выпущена новая основная версия WiFiLine

Я рад сообщить, что выпущена версия WiFiLine 1.1.0. Приложение значительно переработано.

Главные изменения:

* Современный интерфейс пользователя с выдвижными панелями с левой и правой границ экрана;
* Новый режим навигации - наивный умножитель;
* Многочисленные новые функции (например, удаление хотспота, отмена последнего сканирования и пр.);

Некоторые из новых возможностей уже описывались в этом блоге. О других еще будет рассказано.

Логотип программы также изменился. К сожалению в Андроиде есть давнишний баг: иконки обновленных программ не "подхватываются" системой. Поэтому Вы можете не увидеть новую иконку, если не удалите и не переустановите программу заново.

Обратите внимание, что WiFiLine - полнофункциональное приложение для навигации и создания карт: Вам не нужно использовать WiFiLine Редактор. WiFiLine Редактор не был обновлен, поэтому его можно использовать, если возникают какие-либо специфические проблемы с этой новой версией.

New major release of WiFiLine is out

I'm glad to inform you that WiFiLine 1.1.0 has been released. The app is reworked thoroughly.

Main changes are:

* New modern user interface with drawers sliding from the left and from the right sides of the screen;
* New location mode - naive multiplier;
* Numerous new functions (delete a hotspot, last scanning undo and others);

Some of the new features have been already covered in the blog. The others will be described in future.

Please note that the app's logo is also updated. Unfortunately Android has an old bug: the icons of updated apps are not refreshed correctly. So you may not see the new icon in the launcher unless you completely remove and then reinstall the app.

Also please note that WiFiLine is a fully functional navigation app: you have no need to use WiFiLine Editor anymore. WiFiLine Editor has not been updated - you may use it if you experience some problems with the new major release.

More details about future version of WiFiLine: part IV

Today I'm finally posting short and descriptive answer to the question that has been left open in one of my previous posts regarding new version of WiFiLine .

I think it was easy to guess that while in the location mode WiFiLine shows the search dialog in the right-side drawer.

Of course, all searching functionality is left intact (including full text search, category search, and shortest path computation) but now it's easily accessible just inside the main window.

More details about future version of WiFiLine: part III

From the very beginning WiFiLine has been using fullscreen mode in the main window. This was a feature added to maximize visible area of a map - you know, mobile screens are small and it's hard to fit navigation tips and context in the limited space.

New WiFiLine makes the fullscreen mode even more "fully screened" ;-). Latest Android version starting from KitKat (4.4) allows applications to hide the navigation bar at the bottom of the screen. This is a horizontal bar with 3 buttons - back, home, and recents. It takes a lot of space and it's almost empty itself. WiFiLine utilizes this space for maps. Look at the screenshot below - there is no the navigation bar.

Of course, you can temporary restore the status bar and navigation bar by a swipe gesture from top of the screen. This is a built-in Android feature. It will show semitransparent overlays of the status bar and the navigation bar on top of the WiFiLine window. They will be hidden again by timeout.

But if you don't like the fullscreen mode, WiFiLine allows you to switch it off now. There is an option in the context menu of the main window.

More details about future version of WiFiLine: part II

Main idea behind the new version of WiFiLine is to provide better usability. It comprises many things, and user iterface counts in the first place. New look and feel of the app is supposed to be more logical than before.

As you already know, quick and easy swipe gesture from the left edge of the screen opens now the panel with settings, that includes an option to select one of three supported modes: navigation, scan and edit, and hotspot signals density.

But there is more for swiping in the app. At every moment a swipe from the right edge of the screen opens additional panel with appropriate content (don't worry - the panels do not interfere with each other - if a user swipes out a panel from the right, the left side panel is pulled in, and vise versa - if a user swipes from the left, the right side panel is pulled in).

The content of the right side panel depends from currently selected mode. For example, in the Scan and Edit mode the panel shows a list of points with measurements. And in the hotspot signals density mode, the panel shows a list of hotspots. And even more - if a map consists of several floors, by default the panels show partial lists of points or hotspots that belong to the current floor only. You may click Show all button to get entire listing. When you zoom in the map the list of points is restricted even more to contain only points from currently visible area.

You may wonder what will be shown in the right panel while in the navigation mode. I'll let you to guess, and give the answer in future posts. Stay tuned.

More details about future version of WiFiLine

Today I'm posting a screen with a map in the updated edit mode. It now provides a grid with logical image coordinates (the ones defined in your SVG image viewBox tag, as you may recall they are used during measurements), and 10 meter scale in the bottom right corner (it's shown only if your map contains a valid scale attribute in the image tag of the map).

The next screen demonstrates new progress indicator shown during continuous scanning. It let you know that WiFi-scanning is actually running (unfortunately, it may occasionally freeze somewhere inside Android system or even hardware), and overall number of aquired measurements is counting in the center.

New WiFiLine version is under development

I decided to post a small piece of news regarding WiFiLine. Mostly it's intended to let you know that I'm working on a new version of WiFiLine. The app will be reworked considerably. Among most important features are: more simple yet modern looking user interface, new location algorithm, some other improvements in functionality. Take a look at the screens.

I'm planning to share info on the progress with you.