Lokalizowanie na podstawie beaconów (BLE) – nabyte doświadczenia

W wyniku wdrożenia powstały aplikacje na urządzenia mobilne dla systemów operacyjnych Android i iOS, dzięki którym użytkownik może wyznaczyć swoją lokalizację na obiekcie, a także wyznaczyć trasę do wybranych punktów obiektu.

Tytułem wstępu

Wyznaczanie lokalizacji odbiornika sygnałów BLE (Bluetooth Low Energy), czyli w naszym przypadku smartfona działającego pod Android lub iOS, odbywa się na podstawie analizy mocy sygnałów odebranych od beaconów o znanych lokalizacjach. Znana lokalizacja oznacza, że aplikacja korzysta z bazy danej przestrzennej lokalizacji beaconów, gdzie każdy z nich ma wyznaczoną jednoznaczną lokalizację. Wraz z mocą sygnału odebranego od beacona pozyskiwane są następujące dane:

• moc nadajnika beacona, interpretowana jako moc referencyjna odebrana w odległości 1m,
• identyfikator w postaci zbioru danych, które umożliwiają jednoznaczne rozpoznanie urządzenia.

Podczas opracowania rozwiązania braliśmy pod uwagę trzy metody określania lokalizacji:

• “fingerprinting” – metoda polegająca na zebraniu danych referencyjnych w środowisku operacyjnym. Na podstawie zebranych danych wyznaczana jest lokalizacja. Opracowaliśmy własny wariant tej metody, wykorzystujący sygnały WiFi. Niezaprzeczalną wadą tej techniki jest fakt, że wymaga ona pracochłonnego procesu zbierania danych referencyjnych w środowisku docelowym. Ponadto cechuje się tzw. dryfem, który wymusza okresowe powtarzanie pomiarów odniesienia.
• przypisanie każdemu nadajnikowi indywidualnej strefy. Metoda ta wymaga najmniej zaawansowanego algorytmu, przy czym oferuje niską dokładność wyznaczania lokalizacji. Metoda ta najlepiej spisuje się, jeśli środowisko wdrożenia umożliwia montaż nadajników w regularnych odstępach. Zastosowaliśmy tę metodę w innym wdrożeniu, gdzie nie była wymagana taka dokładność, jak w opisywanym przypadku obiektu pasażerskiego.
• triangulacja, bazująca na informacjach o dystansie od nadajników. Metoda ta została wybrana przez nas podczas wdrożenia z następujących powodów: elastyczność w kwestii rozmieszczenia źródeł sygnału, teoretyczna możliwość osiągnięcia dokładniejszych rezultatów niż za pomocą wcześniej wymienionych metod.

W metodzie tej aplikacja odbiornika wykorzystuje dane o lokalizacji wszystkich beaconów opisanych w dwóch wymiarach. Moc odebrana z każdego beacona jest przeliczana na dystans, który przebył odebrany sygnał. Zbiór takich danych umożliwia określenie prawdopodobnego położenia odbiornika.

Wnioski z pracy nad implementacją algorytmu lokalizacyjnego na podstawie BLE

1. Zaimplementuj metodę obliczania odległości na podstawie sygnału BLE

Osiągnęliśmy wystarczającą dokładność lokalizacji implementując popularną metodę obliczania odległości od nadajnika dysponując wartością mocy nadawanej oraz odebranej.

Wzór ten pochodzi z biblioteki do obsługi beaconów „Android Beacon Library” dostępnej na licencji Apache 2.0: https://github.com/AltBeacon/android-beacon-library. Więcej informacji: http://stackoverflow.com/questions/20416218/understanding-ibeacon-distancing.

Głównym powodem, dla którego ta metoda została użyta jest fakt, że aplikacja ma być dostępna dla szerokiej grupy urządzeń, które to mają funkcjonować w różnorodnym środowisku. Na pewno możliwa była do opracowania lepsza i własna metoda liczenia odległości, ale musiałaby być dedykowana konkretnym telefonom oraz być stosowana w warunkach zbliżonych do tych, w których została opracowana. W praktyce charakterystyki urządzeń okazują się być zróżnicowane, a warunki w publicznie dostępnych miejscach daleko odbiegają od laboratoryjnych, o czym mowa w punkcie 2 naszych doświadczeń.

Na podstawie tej implementacji można łatwo stworzyć wykres zależność między odległością nadającego beacona, a mocą odebranego sygnału jak np. poniżej dla trzech różnych ustawień mocy nadajnika.

2. Metoda obliczania odległości od nadajnika daje tylko wartości przybliżone

Pierwszym wnioskiem, który powstaje po zaimplementowaniu i przetestowaniu w labie tej metody jest fakt, że metoda ta daje tylko bardzo przybliżone wartości. Rzeczywista zależność dystansu od mocy sygnału odebranego jest niedeterministyczną funkcją wielu czynników; niektóre z nich wymieniamy poniżej:

• Różne telefony mają różne anteny, których uzysk wpływa na dokładność obliczenia dokładności;
• Odebrana moc jest zależna od orientacji anteny odbierającej względem anteny nadającej. Wystarczy, że zmienimy orientację telefonu w przestrzeni, aby zmienił się pomiary mocy odebranej;
• Środowisko rozchodzenia się fal jest zmienne w czasie i zależy od wielu czynników takich jak właściwości pomieszczenia, w której się znajdujemy. Przykładowo jeśli pomieszczenie jest zbudowane z metalowych i szklanych elementów powoduje odbicie fal i ich nieprzewidywalność propagacji;
• Montaż beaconów na kolumnach pewnego typu skutkował kompletną zmianą zależności mocy odebranego sygnału od dystansu;
• Interferencja innych sygnałów. Pasmo sygnału BLE pokrywa się z częstotliwością sieci WiFi (2,4 GHz), co powoduje interferencje fal i wpływa na dokładność odczytywanej mocy;
• Liczba osób przebywających w danym pomieszczeniu. Człowiek składa się w większości z wody, która w dużej mierze absorbuje fale elektromagnetyczne o częstotliwościach zarezerwowanych dla WiFi oraz BLE. Fluktuacje sygnałów można już zaobserwować podczas przechodzenia grupy osób przez pomieszczenie;
• Architektura danego pomieszczenia. Dużo wysiłku kosztował nas odpowiedni dobór parametrów i lokalizacji beaconów dla hali, które posiadała tzw. antresolę. Antresola stanowi osobne piętro i de facto w układzie architektonicznym jest to osobna hala. Niestety nie jest to fakt dla propagacji fal elektromagnetycznych, dla których obiekt z antresolą stanowi jedno pomieszczenie. O ile na samej antresoli dało się obserwować przewidywany spadek mocy wraz z oddalaniem się od beaconów, o tyle poza nią nierzadko moc okazywała się tak silna, jakby odbiornik znajdował się nie tylko na antresoli, ale nawet całkiem blisko nadajnika.

3. Wymagana jest analiza serii próbek w celu wyznaczenia lokalizacji

Jeśli nadajnik i odbiornik sygnału BLE znajdują się w bezruchu, a środowisko propagacji sygnału nie zmienia się, obserwowane są nieustanne zmiany odbieranej mocy. Amplitudy zmian oraz ich dynamika uniemożliwiają określenie nawet przybliżonej odległości beacona na podstawie pojedynczej próbki. Kolejne odczyty mogą różnić się od siebie tak bardzo, że odległości wyznaczone na ich podstawie mogą odbiegać od siebie o 50%. Taka obserwacja uświadamia, jak bardzo trudne do osiągnięcia jest precyzyjne wyznaczanie lokalizacji odbiornika sygnału BLE. W tym przypadku w określaniu położenia odbiornika kluczową rolę odgrywała zaawansowana obróbka statystyczna serii próbek odbieranych sygnałów. Do wyznaczenia aktualnej odległości beacona konieczna jest analiza historii odebranych sygnałów. Opracowując rozwiązanie problemu, staje się przed wyborem między dokładniejszą precyzją określania dystansu, a szybkimi reakcjami na jego zmiany. Trzeba też pamiętać, że jest to tylko jeden z kilku etapów algorytmu i docelowe urządzenia dysponują ograniczoną mocą obliczeniową. Najlepiej zastosować możliwie najprostsze obliczenia. Jednocześnie pożądanym jest rozwiązanie, dla którego poprawa jakości wymaga wyraźnie większego zaawansowania obliczeniowego.

Wykres prezentujący moc próbek bez obróbki (linia biała) oraz moc próbek poddanych stabilizacji (linia czerwona).

Nasze rozwiązanie umożliwiło zredukowanie amplitud fluktuacji ponad trzykrotnie jak na załączonym wykresie. Równie korzystnie wpłynęło na szybkość zachodzących zmian, zachowując przy tym akceptowalną dynamikę zmiany mocy po obróbce w sytuacji rzeczywistej zmiany odległości beacona od odbiornika. Opracowując rozwiązanie poruszonego problemu ustaliliśmy, że istotne jest, aby beacony nadawały sygnał odpowiednio często. W przeciwnym przypadku zebranie serii próbek do ustalenia pojedynczego poziomu mocy po obróbce będzie trwać zbyt długo, aby zachować zadowalającą responsywność algorytmu. Nie zaleca się przekraczania interwału nadawania wynoszącego 300 ms. Odnotowaliśmy również, że seria próbek poddawanych analizie nie musi mieć stałej wielkości. Zastosowanie odczytów z akcelerometru telefonu po usunięciu przyśpieszenia ziemskiego umożliwia określenie, czy odbiornik pozostaje w bezruchu i czy konieczne jest zastosowanie większej serii do ustalania odebranej mocy. Trzeba przy tym pamiętać, że zmiany wielkości serii powinny odbywać się w sposób płynny, aby nie powodować nagłych zmian wynikowych mocy.

4. Wieloetapowość wyznaczanie algorytmu lokalizacji poprzez wprowadzenie metod korekcji

Algorytm wyznaczania lokalizacji jest wieloetapowy, gdzie jednym z etapów jest analiza serii próbek w celu estymacji odległości każdego „widocznego” nadajnika BLE. Następnie wykonywana jest selekcja próbek. Na jakość rezultatu końcowego silny wpływ ma prawidłowe określenie, jakie próbki niosą ze sobą cenne informacje. Wstępny wybór polega na filtrowaniu próbek stosując kryterium czasu, w jakim zostały od danego beacona odebrane. Następnie usuwane są próbki o sygnale zbyt słabym, które mogą pochodzić od beacona odległego lub bliskiego, ale zasłoniętego jakimiś przeszkodami. Praktyczne próby wykazały, że ustalenie stałej progowej wartości mocy jest pozbawione sensu. Opracowaliśmy metodę wyboru najmocniejszych sygnałów, która jest w stanie adaptować się do sytuacji. Oznacza to, że moc progowa jest zależna od aktualnego układu „widocznych” beaconów. Następnym krokiem jest określenie piętra, na jakim znajduje się odbiornik. W najczęstszej sytuacji, ze względu na silne tłumienie podłogi, proces ten nie wymaga komplikacji. Jednakże nasz algorytm musiał radzić sobie ze wskazywaniem, czy użytkownik przebywa na antresoli, a więc miejscem gdzie nie ma barier dla sygnałów pochodzących z miejsc znajdujących się obok i poniżej.

Planowaliśmy zastosowanie triangulacji, ale okazało się że jej użycie wiąże się z utratą sporej części cennych informacji. Ostatecznie zastosowaliśmy inną, własną metodę wyznaczania położenia na podstawie odległości od określonych punktów. Jej wyróżnikiem jest nadawanie wag sygnałom w zależności od ich mocy. Zabieg ten wprowadziliśmy, wiedząc że istnieje zależność między mocą sygnału a ufnością, jaką powinno się go darzyć. Ostatnim etapem jest korekcja polegająca na wyeliminowaniu łatwo dostrzegalnych błędów, w tym:

• położenie poza granicą pomieszczeń. W tym celu należy w algorytmie wziąć pod uwagę kształt pomieszczeń i wykluczyć lokalizacje nieosiągalne np.: pozycjonowanie na ścianie lub za nią;
• zbyt duża odległość między kolejno wyznaczonymi położeniami użytkownika. Korekcja polega na obliczeniu prędkości, z jaką musiał przemieścić się odbiornik, aby znaleźć się w nowej lokalizacji i wyklucza przypadki „teleportacji”;
• lokalizacja na złym piętrze. Użytkownikowi zajmie określony kwant czasu, aby zmienić piętro i należy wykluczyć nierealne zmiany piętra w zbyt krótkim czasie.

Podsumowanie

Jak okazało się podczas wdrożenia lokalizacji na podstawie 1500 beaconów w przestrzeni publicznej o powierzchni ponad 100 000 mkw na wielu poziomach, należy zaprojektować wieloetapowy algorytm wyznaczania lokalizacji. Ważnymi krokami tworzenia tego algorytmu są etapy obróbki serii próbek sygnału beaconów, selekcja danych istotnych, zastosowanie dla nich wag, a także wprowadzenie niezbędnych korekt. Istotnymi elementami w algorytmie korekcji jest położenie użytkownika względem stałej infrastruktury budynku, a także wykorzystanie czujnika inercyjnego.

Najtrudniejszym elementem wdrożenia był krok kompensacji wpływu środowiska na sygnał emitowany przez beacony tj.: fale odbite od powierzchni szklanych i metalowych, interferencja z sygnałem WiFi, czy też wpływ przechodzących grup ludzi. Ważnym wnioskiem jest, że implementacja oraz testy algorytmu w warunkach laboratoryjnych w firmie mogą dawać zupełnie inne wyniki, niż w środowisku rzeczywistym.

Najważniejszą informacją jest fakt potwierdzający, że zastosowana technologia jest praktyczna i sensowna do wykorzystana w celu geolokalizacji w obiektach zamkniętych.

W razie dalszych pytań ad algorytmu lokalizacji prosimy o kontakt bezpośredni z autorami artykułu: office@inovatica.com.

Darek i Bogumił / Inovatica