1 UVOD
Lokalizacija je postopek določanja lokacije ljudi, živali,
stvari in drugih objektov. Srednjeveške metode
določanje lokacije, ki so temeljile predvsem na uporabi
kompasa in neposredni vidljivosti objektov z znano
lokacijo, je skoraj povsem nadomestila lokalizacija na
podlagi radijskega signala, tj. radijska lokalizacija.
Glede na vrsto okolja, v katerem se nahaja subjekt, ki
mu želimo določiti lokacijo, ločimo dva osnovna tipa
lokalizacije, in sicer lokalizacijo v zunanjih okoljih in
lokalizacijo v notranjih okoljih. Satelitski navigacijski
sistemi, kot so Global Positioning System (GPS),
Glonass in Galileo, v večini primerov zadovoljivo
določijo lokacijo v zunanjih okoljih, medtem ko v
notranjosti objektov ni prevladala še nobena poznana
tehnologija. Različni pristopi za lokalizacijo v notranjih
okoljih se med seboj razlikujejo v natančnosti, ceni,
tehnologiji, razširljivosti, robustnosti in varnosti rešitev.
Ker imajo aplikacije različne zahteve in omejitve, je
treba izbrati aplikaciji primerne lokalizacijske pristope.
Za veliko problemov že obstaja primerna tehnologija [1,
2, 3].
Sistemi za lokalizacijo v notranjih okoljih omogočajo
določanje lokacije subjektov v realnem času [4].
Postopki določanja lokacije se uporabljajo za različne
aplikacije v stanovanjskih objektih, vključno z
Prejet 3. marec, 2017
Odobren 24. julij, 2017
156 HROVAT, MOHORČIČ, NOVAK, JAVORNIK
zaznavanjem in sledenjem predmetov, zagotavljanjem
asistence starejšim in invalidom pri njihovih
vsakodnevnih aktivnostih in za olajšano spremljanje
zdravstvenega stanja in vitalnih znakov [5]. V javnih
zgradbah se lokalizacijski sistemi uporabljajo za
vodenje slepih in slabovidnih, vodenje turistov v
muzejih, sledenje otrok itd. Pomembno področje
uporabe je tudi medicinska nega v bolnišnicah, kjer se
sistemi uporabljajo za sledenje pacientov in drage
opreme. Poleg tega so sistemi nujni pri reševalnih
operacijah policistov in gasilcev. Sledenje gasilca v
goreči stavbi je ključno za njegovo varnost in uspešno
upravljanje operacije. Uporablja se tudi za sledenje
policijskih psov pri iskanju eksploziva v stavbah,
lociranje ukradenih predmetov in iskanje zasilnih
izhodov v zadimljenih prostorih. Z razvojem
avtomatizacije in nadzora se lokalizacijski sistemi za
notranja okolja čedalje pogosteje uporabljajo tudi v
industriji (robotsko vodenje, pametne tovarne,
sodelovanje med roboti) [6, 7].
Radijska lokalizacija temelji na merjenju parametrov
sprejetega radijskega signala, kot so sprejeta moč, čas
potovanja signalov, fazni zamik sprejetega signala [8].
Notranje radijsko okolje drugače popači radijski signal
kot zunanje, zato se radijska lokalizacija v notranjih
okoljih močno razlikuje od radijske lokalizacije v
zunanjih okoljih. V primerjavi z zunanjim okoljem je
notranje okolje kompleksnejše, saj po navadi vsebuje
veliko objektov (kosi pohištva, stene, osebe), ki odbijajo
ali absorbirajo radijski signal, kar povzroča širjenje
radijskega signala po več poteh ter poveča njegovo
zakasnitev. Različni objekti pogosto ovirajo neposredno
pot med oddajnikom in sprejemnikom (LOS – Line-Of-
Sight), kar vodi do nedoslednih časovnih zakasnitev na
sprejemniku. Prisotnost objektov povzroča tudi visoko
slabljenje signalov in razpršitev. Poleg tega pa so v
notranjih okoljih prisotni tudi motilci (WiFi, Bluetooth,
ZigBee, brezžični telefoni, mikrovalovne pečice itd), ki
vnašajo napako pri zaznavanju parametrov radijskega
signala.
Notranje okolje je tudi časovno spremenljivo.
Spremeni se lahko tudi lokacija sidrnih (referenčnih)
vozlišč, zato morajo robustni lokalizacijski sistemi
zaznati te spremembe in se jim tudi prilagoditi. Po
navadi aplikacije za notranja okolja zahtevajo tudi
natančnejšo lokacijo v primerjavi z aplikacijami za
zunanja okolja. Dobro poznavanje geometrije in
elektromagnetih lastnosti notranjih okolij pa omogoča
lažje določanje lokacije.
Za lokalizacijske sisteme za notranja okolja obstaja
pet osnovnih metrik kakovosti: 1. natančnost sistema, 2.
pokritje in ločljivost, 3. zakasnitev pri posodabljanju
lokacije, 4. vpliv infrastrukture zgradbe in 5. vpliv
naključnih napak na sam sistem (napake zaradi
interference in odbojev) [9].
Preostanek prispevka ima naslednjo strukturo. V
drugem poglavju so opisani izzivi načrtovanja radijskih
lokalizacijskih algoritmov in merila za določanje
učinkovitosti posameznih rešitev. Tretjemu poglavju, v
katerem je podan kratek opis radijskih tehnologij, sledi
poglavje, ki podaja različne delitve in klasifikacije
tehnik radijske lokalizacije. Tehnike, ki določajo
lokacije vozlišč posredno, z merjenjem metrik
radijskega signala, se imenujejo triangulacijske in so
opisane v četrtem poglavju. Sledi poglavje z opisom
pristopov analize scene oziroma prstnega odtisa, ki
določajo lokacijo vozlišč s primerjanjem trenutne
izmerjene vrednosti z vrednostmi v podatkovnih bazah.
V omrežjih z nezadostnim številom vozlišč z znano
lokacijo se pogosto uporabljajo kooperativni
lokalizacijski pristopi, ki so opisani v sedmem poglavju.
Prispevek zaključimo z osmim poglavjem, ki vsebuje
sklepne ugotovitve.
2 IZZIVI IN UČINKOVITOST LOKALIZACIJSKIH
ALGORITMOV
Pri načrtovanju in implementaciji radijskih
lokalizacijskih algoritmov je treba upoštevati omejitve
uporabljene radijske tehnologije oziroma sistema. Poleg
tega se je treba zavedati, da je v večini primerov
podatek o lokaciji vhodni podatek osnovni aplikaciji in
da iskanje lokacije ne sme okrniti funkcionalnosti
osnovne aplikacije.
2.1 Izzivi načrtovanja lokalizacijskih
algoritmov
Pogosto so vozlišča, predvsem v senzorskih omrežjih, z
vidika zmogljivosti procesorja in razpoložljive energije
precej omejena, kar onemogoča izvajanje računsko
zahtevnih operacij. Komuniciranje ter zaznavanje in
obdelava podatkov porabljajo energijo in tako
skrajšujejo življenjsko dobo vozlišč. Senzorji pogosto
tvorijo velika omrežja z več sto/tisoč napravami, zato
morajo biti vozlišča poceni in preprosta za namestitev.
Po navadi lokalizacija ni glavni namen omrežij, je pa
pogosto zaželena lastnost in je v omrežjih potrebna za
podporo različnim funkcijam. Ker je funkcija
lokalizacije pogosto dodatek aplikaciji, mora biti kljub
še zadovoljivim rezultatom čim cenejša. Zato morajo
načrtovalci lokalizacijskih rešitev delati na algoritmih,
ki minimalno vplivajo na porabo energije, ne
potrebujejo dodatne strojne opreme ter jih je mogoče
namestiti na preprost način in brez pretiranih dodatnih
stroškov.
Natančnost lokalizacijskih algoritmov je po navadi
odvisna predvsem od gostote vozlišč. Na primer shema,
ki deluje na podlagi štetja skokov, zahteva visoko
gostoto vozlišč, saj je razdalja določena kot približek
števila skokov. Podobno velja tudi za algoritme, ki
delujejo na podlagi sidrnih vozlišč, saj rešitev ne deluje,
če sidrnih vozlišč na določenem območju ni dovolj.
Zato je treba pri načrtovanju in analiziranju algoritmov
upoštevati gostoto vozlišč, saj lahko visoka zahtevana
gostota vozlišč močno podraži sistem.
Lokalizacijski algoritmi se pogosto soočajo s
problemom določanja lokacije vozlišč na robu omrežja
RADIJSKA LOKALIZACIJA V NOTRANJIH OKOLJIH: PREGLED PRISTOPOV 157
oziroma območja pokritja. Vzrok tiči predvsem v
manjšem številu razpoložljivih meritev dosega, s
katerimi razpolagajo robna vozlišča, ki so lahko celo
pridobljene iz iste smeri robnega vozlišča. Torej, robna
vozlišča pomenijo težavo predvsem zaradi manjšega
števila in slabše kakovosti razpoložljivih informacij, ki
so potrebne za natančno določanje lokacije. Problem se
bistveno poveča pri nekonveksni obliki omrežja, saj
vozliščem, ki se nahajajo zunaj osnovnega konveksnega
jedra, pogosto ni mogoče določiti lokacije oziroma je
napaka lahko zelo velika.
2.2 Merila učinkovitosti
Mehanizmi za določanje lokacije v notranjih okoljih se
med seboj razlikujejo v ceni, natančnosti, uporabljeni
tehnologiji, razširljivosti, robustnosti in varnosti.
Nekatere aplikacije zahtevajo nizkocenovne rešitve,
medtem ko spet druge visoko natančnost (sledenje v
medicini, sledenje v industrijskem okolju, sistem
navigacije za slepe). Za določanje učinkovitosti
posameznih rešitev obstajajo različni kriteriji, ki so na
kratko opisani v nadaljevanju [2, 3, 7].
Natančnost je razlika razdalje med ocenjeno lokacijo
in dejansko lokacijo naprave – večja ko je natančnost,
boljši je sistem. Še vedno je razmeroma velik izziv in
zahteva kompromis med natančnostjo in preostalimi
merili učinkovitosti.
Razpoložljivost je definirana kot razpoložljivost
lokacijske storitve v času, po navadi podana kot
odstotek. Nanjo vplivajo različni dejavniki, kot sta
zasičenost komunikacije in redno vzdrževanje.
Odzivnost je merilo, ki podaja hitrost posodabljanja
lokacije premikajoče se tarče.
Pokritost je območje, ki ga pokriva storitev. Za
učinkovitost sistema določanja lokacije je določitev
pokritja na analiziranem območju zelo pomembna.
Pokritje je tesno povezano z natančnostjo in ga lahko
delimo na lokalno, razširljivo in globalno.
Spremembe v okolju lahko vplivajo na učinkovitost
lokalizacijskega sistema. Zmožnost prilagajanja sistema
na te spremembe se imenuje prilagodljivost.
Razširljivost določa stopnjo, do katere sistem
zagotavlja normalno funkcionalnost določanja lokacije
ob razširitvi v eni ali dveh dimenzijah (število
uporabnikov in geografsko). Je zaželena lastnost v
skoraj vseh sistemih in opisuje zmogljivost sistema pri
delovanju z večjim številom lokalizacijskih zahtev in
večjem pokritju.
Stroški-cena sistema za določanje lokacije se lahko
merijo v različnih dimenzijah: denar, čas, prostor in
energija. Pojavljajo se na različnih ravenh sistema:
namestitev in vzdrževanje sistema, infrastrukturne
komponente in naprave za določanje lokacije. Prihranki
so mogoči s souporabo dela obstoječe infrastrukture,
opreme in pasovne širine. Glede na samo zmogljivost
sistema je določanje lokacije treba uravnotežiti tudi s
kompleksnostjo obdelave signalov in algoritmov za
oceno lokacije.
Zasebnost je za uporabnike sistema zelo pomembna.
Zato je visok nadzor dostopa nad zbiranjem in uporabo
uporabniških zasebnih podatkov ključnega pomena. Za
izboljšanje zasebnosti uporabnikov morajo sistemi
vsebovati varnostne rešitve, ki preprečujejo zlorabo
podatkov.
3 RAZPOLOŽLJIVE BREZŽIČNE TEHNOLOGIJE
Pri izbiri tehnologije za lokalizacijo v notranjih okoljih
je treba najti ustrezno ravnotežje med kompleksnostjo in
zmogljivostjo rešitve [2, 4]. V preteklosti so
raziskovalci razporedili tehnologije za lokalizacijo v
notranjih okoljih na različne načine (glede na strojno
opremo, potrebo po obstoju omrežja, arhitekturo
sistema, osrednji medij za določanje lokacije,
predhodno poznavanje, tip senzorjev, odvisne in
neodvisne od zgradb). Slika 1 prikazuje
najpomembnejše brezžične tehnologije za lokalizacijo v
notranjih okoljih [3, 7, 10].
lokalizacijske
tehnologije
infrardeča radijske ultrazvočna
WLAN RFID Bluetooth ZigBee UWB FM Hibridne
Slika 1: Tehnologije za sisteme lokalizacije
Tehnologije za določanje lokacije v notranjih okoljih
je smiselno razdeliti glede na infrastrukturo
uporabljenega sistema. V osnovi jih lahko razdelimo na
odvisne od zgradbe, v kateri se bodo uporabljale
(uporabljajo namensko infrastrukturo ali pa
infrastrukturo že vgrajeno v zgradbe), in neodvisne od
zgradbe. Tehnologije, ki zahtevajo namensko
infrastrukturo, so radijskofrekvenčna identifikacija
(RFID), tehnologija ultraširokega pasu (UWB),
infrardeča (IR), ultrazvočna in ZigBee. Med
tehnologije, ki izrabljajo že obstoječo infrastrukturo v
zgradbah, pa spadajo WiFi, celična omrežja in
Bluetooth. Tehnologije, ki so popolnoma neodvisne od
zgradb, kot so računska navigacija (ang. dead
reckoning) in tehnologije na podlagi slik, ne potrebujejo
nikakršne namenske strojne opreme. Pri pristopu
računske navigacije lahko subjekt določi svojo trenutno
lokacijo na podlagi poznavanja predhodne lokacije,
hitrosti in smeri premikanja. Tehnologije na podlagi slik
pa temeljijo na kamerah in so lahko neodvisne (ne
potrebujejo podatkov o zgradbi) ali odvisne (uporabljajo
posebne znake v zgradbah ali načrte zgradb) od zgradb.
158 HROVAT, MOHORČIČ, NOVAK, JAVORNIK
4 PRISTOPI OCENJEVANJA LOKACIJE IN
ALGORITMI ZA LOKALIZACIJO
Radijska lokalizacija v notranjih okoljih se v osnovi deli
na lokalizacijo brez naprav (device-free) in lokalizacijo
na podlagi naprav (device-based) [11]. V prvem primeru
subjekt lokalizacije ne nosi namenske naprave in je
lociran oziroma sleden na podlagi svojih fizičnih
lastnosti, kot je motnja telesa na širjenje radijskega
signala. Pri drugem pristopu je subjekt lokalizacije
opremljen z napravo. Glavni prednosti pristopa sta
predvsem večja natančnost in cenejša namestitev.
Lokalizacijo na podlagi naprav delimo v štiri kategorije,
in sicer na podlagi infrastrukture, prstnega odtisa,
modelov razširjanja ter sočasne lokalizacije in
mapiranja (SLAM; Simultaneous Localization and
Mapping). Med naštetimi pristopi lahko lokalizacija na
podlagi prstnega odtisa izrabi največjo paleto dostopne
infrastrukture in ima največji potencial za obsežnejšo
uporabo.
Za določanje lokacije obstajajo štiri različne
topologije sistemov [12]. Prva temelji na mobilnem
oddajniku signala in več fiksnih sprejemnih enotah, ki
merijo oddani signal in pošiljajo meritve centralnemu
vozlišču, ki izračuna lokacijo oddajnika. Drugi je sistem
samolociranja, kjer merilna enota sprejema signal iz več
oddajnikov na poznanih lokacijah in na podlagi zbranih
meritev izračuna svojo lokacijo. Če je naprava
brezžično povezana s sistemom lociranja, lahko pošlje
svojo trenutno lokacijo na oddaljeno lokacijo. To se
imenuje posredno oddaljeno lociranje in pomeni tretjo
vrsto topologije sistema. Pri posrednem samo-lociranju,
ki je četrti tip topologije sistema, pa so mobilni enoti
rezultati meritev posredovani z brezžično povezave z
oddaljene lokacije.
Na splošno je radijska lokalizacija sestavljena iz dveh
delov, in sicer faze meritve in faze ocene lokacije [13].
Meritve obsegajo oddajo in sprejem signalov med
strojnimi komponentami sistema. Sistem za lokalizacijo
v notranjih okoljih je sestavljen vsaj iz dveh ločenih
fizičnih naprav: oddajnika in sprejemnika oziroma
merilne enote, ki po navadi vsebuje tudi večino
inteligence sistema. Večina lokalizacijskih algoritmov
za določanje lokacije uporablja meritve signala med
sosednjimi vozlišči. Med fazo meritev se med
sosednjimi vozlišči izmenjajo paketi. Iz radijskih
signalov, ki pripadajo tem paketom, sprejemnik z
merjenjem ali oceno ene ali več metrik signala pridobi
informacije o razdalji ali kotu. Na prvo fazo lokalizacije
vplivajo različni dejavniki, ki vnašajo naključne napake,
in sicer šum, širjenje signala po več poteh, blokada
signala, interferenca, napake pri sinhronizaciji vozlišč in
drugi vplivi okolja. Poleg naštetega vnaša dodatne
omejitve tudi izbrana tehnologija prenosa, od izbrane
modulacijske sheme in sheme sodostopov, časovne
sinhronizacije med vozlišči v omrežju, števila in vrste
uporabljenih sprejemnih in oddajnih anten, izbrane
nosilne frekvence, do omejitev virov napajanja na
oddajniku in sprejemniku itd. V drugi fazi vozlišča na
podlagi izmerjenih metrik sprejetih signalov iz
sosednjih vozlišč, lastnega stanja in stanja sosednjih
vozlišč z uporabo lokalizacijskih algoritmov ocenijo
svoje stanje.
Lokalizacijske algoritme delimo na [13,14]:
• Centralizirane oziroma porazdeljene. Pri
centraliziranem pristopu so vse lokacije vozlišč
določene na enem centralnem mestu. Le-to zbira
meritve tako od sidrnih vozlišč z znano lokacijo
kot tudi vozlišč z neznano lokacijo in izračuna
nepoznane lokacije vseh vozlišč. Pristopi z
uporabo centraliziranih algoritmov niso
razširljivi in so posledično neprimerni za večja
omrežja. Pri porazdeljenem pristopu vsako
vozlišče določa svojo lokacijo na podlagi lokalno
zbranih podatkov. Porazdeljeni algoritmi so
preprosto razširljivi in primerni tudi za večja
omrežja.
• Absolutne oziroma relativne. Absolutna
lokalizacija se nanaša na lokalizacijo v enem
samem vnaprej določenem koordinatnem
sistemu. Pri relativni lokalizaciji pa se
lokalizacija izvaja v okviru posameznih sosedov
oziroma lokalnega okolja, zato se lahko
koordinatni sistem spreminja od vozlišča do
vozlišča.
• Nekooperativne oziroma kooperativne. Pri
nekooperativnem pristopu vozlišča z neznano
lokacijo komunicirajo le s sidrnimi vozlišči. Ker
vsako vozlišče komunicira le z več sidrnimi
vozlišči, je bodisi potrebna visoka gostota sidrnih
vozlišč bodisi velik doseg sidrnih vozlišč. Pri
kooperativnem lokalizacijskem pristopu vozlišča
komunicirajo tudi med seboj in ni treba, da se
nahajajo v radijskem dosegu več sidrnih vozlišč.
Tako ni več potreb po visoki zgoščenosti
oziroma dolgem dosegu sidrnih vozlič. Ker lahko
vozlišča komunicirajo tako s sidrnimi kot tudi z
drugimi vozlišči v radijskem dosegu, pristop
omogoča večjo natančnost lokalizacije in širšo
pokritost območja.
Pristope radijske lokalizacije razdelimo tudi na
podlagi: 1. algoritmov za določanje lokacije oziroma
metod za določanje lokacije, ki izrabljajo različne vrste
meritev signalov, kot so čas potovanja, kot prihoda in
jakost signala, in 2. radijske infrastrukture za
lokalizacijo (brezžična tehnologija, uporabljena za
komunikacijo z/med napravami).
Razširjanje radijskega signala v notranjih okoljih je
razmeroma specifično in zahtevno za modeliranje, saj so
prisotni močan pojav širjenja signalov po več poteh,
interference, šuma, blokiranja signala in specifični
parametri posameznih fizičnih okolij. Poleg
tradicionalnih algoritmov na podlagi triangulacije so bili
za zmanjševanje napak meritev razviti različni
lokalizacijski pristopi na podlagi analize scene in
zaznavanja neposredne bližine. Posamezni algoritmi
imajo določene prednosti in slabosti ter so zato primerni
RADIJSKA LOKALIZACIJA V NOTRANJIH OKOLJIH: PREGLED PRISTOPOV 159
za uporabo v različnih ciljnih aplikacijah in storitvah.
Hkratna uporaba več vrst lokalizacijskih algoritmov
lahko pripomore k bistveno boljši natančnosti
lokalizacijske rešitve. Lokalizacijske tehnike lahko
razdelimo v tri osnovne kategorije (slika 2) [15, 16]:
• triangulacija – lokacija določen na podlagi
geometrijskih lastnosti trikotnika;
o lateracija; za ocenitev razdalje med dvema
vozliščema se uporablja metrika signala
(algoritmi na podlagi dosega) - uporabljene
metrike; sprejeta moč signala (RSS), čas
prihoda signala (ToA), časovna razlika
prihoda signala (TDoA), faza prihoda signala,
število radijskih skokov in čas obhoda
signala;
o angulacija (na podlagi signalne matrike
izračunajo nagib in azimut sprejemnega
radijskega žarka) – metrika signala; smer
prihoda signala (AoA);
• zaznavanje neposredne bližine (proximity
detection);
• analiza scene.
zaznavanje
lokacije
triangulacija
zaznavanje
neposredne
bližine
analiza scene
na osnovi smeri
(angulacija)
na osnovi
razdalje
(lateracija)
metode na
osnovi časa
metode na
osnovi lastnosti
signala
kotne metode
Slika 2: Klasifikacija lokalizacijskih algoritmov
5 TRIANGULACIJA
Za določanje lokacije pristop triangulacije izrablja
geometrijske lastnosti trikotnika. Ima dve izpeljanki:
lateracijo in angulacijo. Lateracija oceni lokacijo
vozlišča z merjenjem razdalje do več sidrnih vozlišč
[17, 18]. Imenuje se tudi tehnika merjenja razdalje.
Namesto neposrednega merjenja razdalje se po navadi
prek izmerjenih metrik signala, kot so jakost sprejetega
signala (RSS), čas prihoda signala (ToA) ali časovna
razlika prihoda signala (TDoA), izračuna slabljenje
oddanega signala, ali pa se prek množenja hitrosti
radijskega signala s časom potovanja določi razdalja do
neznanega vozlišča oziroma njegova lokacija. V
nekaterih sistemih se za določanje razdalje uporabljata
tudi čas obhoda signala (RToF) in faza prihoda signala.
Kotne metode določajo lokacijo vozlišča z
izračunavanjem kotov relativno na več sidrnih vozlišč.
5.1 Čas prihoda signala (ToA)
Razdalja med neznanim vozliščem in merilnim
vozliščem je neposredno proporcionalna času razširjanja
signala. Za določanje lokacije v dveh dimenzijah morajo
biti na voljo meritve ToA signala vsaj iz treh sidrnih
vozlišč [19]. V sistemih, ki temeljijo na ToA, je treba
izmeriti čas razširjanja signala le v eni smeri, na podlagi
tega je nato izračunana razdalja med oddajnikom in
merilnim vozliščem. Na splošno ima pristop dve
osnovni zahtevi; 1. vsi oddajniki in sprejemniki v
sistemu morajo biti sinhronizirani in 2. oddani signal
mora imeti časovni žig, ki merilnemu vozlišču omogoča
zaznavanje prepotovane razdalje signala. ToA je
mogoče meriti z različnimi tehnikami signala, kot sta
tehnika razpršenega spektra z neposrednim zaporedjem
(DSSS) [20] ali tehnika ultraširokega pasu (UWB) [21].
Najpreprostejši pristop za določanje presečišč
krožnic ToA, ki so določene na podlagi izračunanih
razdalj in pomenijo morebitno lokacijo neznanega
vozlišča, je geometrijska metoda. Lokacijo objekta je
mogoče izračunati tudi s postopkom minimizacije vsote
kvadratov nelinearne funkcije stroškov, imenovanim
tudi algoritem najmanjših kvadratov (LS – Least
Squares algorithm) [19, 22]. Algoritem predvideva, da
neznano vozlišče, ki se nahaja na (x0, y0), odda signal v
času t0 in N baznih postaj na lokacijah (x1, y1), (x2,
y2), . . . ,(xN, yN) sprejme signal v časih t1, t2, . . . , tN .
Kot merilo uspešnosti je funkcija stroškov
𝑭(𝒙) = ∑ 𝛼𝑖
2𝑓𝑖
2(𝒙)𝑁𝑖=1 , (1)
kjer αi pomeni zanesljivost signala, sprejetega na
merilnem vozlišču i, in je fi(x) podana s
𝑓𝑖(𝒙) = 𝑐(𝑡𝑖 − 𝑡) − √(𝑥𝑖 − 𝑥)
2 + (𝑦𝑖 − 𝑦)
2. (2)
V predhodni enačbi je c hitrost svetlobe, vektor x pa je
definiran kot (x,y,t)T. Ta funkcija se oblikuje za vsako
merilno vozlišče in je lahko z ustrezno izbiro x, y in t
tudi nič. Ocenjena lokacija je določena z
minimiziranjem funkcije stroškov F(x).
Za lokalizacijo v notranjih okoljih na podlagi ToA
obstajajo še nekateri drugi algoritmi, kot so algoritem
najbližjega soseda (CN – Closest-Neighbor) in
uteževanja razlike (RWGH – Residual WeiGHting)
[22]. Medtem ko algoritem CN za lokacijo uporabnika
privzame lokacijo najbližjega sidrnega vozlišča, je
algoritem RWGH nekakšen utežen algoritem
najmanjših kvadratov in je primeren za LOS, NLOS in
mešane LOS/NLOS radijske kanale. ToA je
najnatančnejša tehnika za lokalizacijo v notranjih
okoljih, saj omogoča izločitev vplivov več poti. Vendar
zahteva po natančni sinhronizaciji med oddajniki in
160 HROVAT, MOHORČIČ, NOVAK, JAVORNIK
sprejemniki močno poveča kompleksnost in posledično
tudi podraži sistem.
5.2 Časovna razlika prihoda signala (TDoA)
Pri določanju relativne lokacije neznanega oddajnika se
uporablja časovna razlika dospetja signala na več
različnih sidrnih vozliščih. Za vsako meritev TDoA
mora oddajnik ležati na hiperboloidu s konstantno
razliko razdalje med dvema sprejemnikoma. Enačba
hiperboloida je podana kot
𝑅𝑖,𝑗 = √(𝑥𝑖 − 𝑥)
2 + (𝑦𝑖 − 𝑦)
2 + (𝑧𝑖 − 𝑧)
2 −
√(𝑥𝑗 − 𝑥)
2 + (𝑦𝑗 − 𝑦)
2 + (𝑧𝑗 − 𝑧)
2, (2)
kjer (xi,yi,zi) in (xj,yj,zj) pomenita fiksna sprejemnika i
in j, (x,y,z) pa koordinate neznanega vozlišča, ki ga je
treba locirati. Eksaktno rešitev predhodne enačbe
dobimo prek nelinearne regresije, laže pa jo je
linearizirati prek razširitve Taylorjeve vrste in
iterativnega algoritma [23]. Presečišče več krivulj
določa morebitno lokacijo vozlišča.
Navadne metode za izračun ocene TDoA uporabljajo
korelacijske tehnike. TDoA se lahko oceni prek križne
korelacije med signaloma, ki sta sprejeta na paru
sprejemnikov. Če je oddani signal s(t) sprejeti signal na
sprejemniku i xi(t) in je pokvarjen s šumom ni(t) ter
zakasnjen za di, velja xi(t)=s(t-di)+ni(t). Podobno velja
za signal, ki dospe na sprejemnik j. Funkcija križne
korelacije teh dveh signalov je podana kot integracija
produktov dveh časovno zamaknjenih sprejetih signalov
prek časovne periode T:
�̂�𝑥𝑖𝑥𝑗(𝜏) =
1
𝑇
∫ 𝑥𝑖(𝑡)𝑥𝑗(𝑡 − 𝜏)𝑑𝑡
𝑇
0
. (4)
TDoA oceni vrednost τ, ki maksimizira razliko razdalj
Rxi,xj(τ). Za razrešitev časovnega žiga in določanje
lokacije ni potrebna sinhronizacija izvora oddajanja. Pri
uporabi pristopa TDoA je signal oddan ob neznanem
času in sprejet na več sprejemnikih, ki pa morajo biti
med seboj časovno sinhronizirani [24].
5.3 Jakost sprejetega signala (RSSI)
Predhodno opisana pristopa imata nekatere
pomanjkljivosti. V notranjih okoljih je prisotnost
neposredne vidljivosti med oddajnikom in
sprejemnikom redka. Radijski signal se v notranjih
okoljih po navadi širi po več poteh, kar popači čas in
smer prihoda signala ter posledično zmanjšuje
natančnost določanja lokacije. Alternativni način
določanja razdalje do neznane lokacije vozlišča je
merjenje slabljenja jakosti radijskega signala. Metode
na podlagi slabljenja signala s pomočjo modelov izgube
poti pretvorijo razliko med jakostjo oddanega in
sprejetega signala v ocenjeno razdaljo. Pristop je
razmeroma privlačen, saj po navadi ni treba nameščati
dodatne strojne opreme, ne vpliva na porabo moči
vozlišč in posledično tudi ne na stroške.
Zaradi večpotnega presiha in senčenja, ki sta v
notranjih okoljih močno prisotna, so modeli izgube poti
pogosto nenatančni. Parametri modelov so po navadi
odvisni od okolja razširjanja signala. Natančnost metode
je mogoče izboljšati z vnaprejšnimi meritvami jakosti
sprejetega signala na krogih s središčem v sprejemniku
ali z meritvami na več sidrnih vozliščih [25].
5.4 Čas obhoda signala (RToF)
Metoda meri čas potovanja signala od oddajnika do
merilnega vozlišča in nazaj. Pri pristopu ToA se
zakasnitev računa z uporabo dveh lokalnih taktov v
obeh vozliščih, medtem ko se pri pristopu RToF za
beleženje časov oddaje in sprejema uporablja le eno
vozlišče. Tako pristop do določene mere rešuje problem
sinhronizacije med vozlišči. Ena od slabosti je merjenje
oddaljenosti do več naprav, ki se mora pri tej metodi
izvajati zaporedno, kar vnaša negotovost v zakasnitev.
To je kritično predvsem v aplikacijah, kjer se naprave
hitro gibljejo. Dodatna slabost je tudi nepoznavanje časa
obdelave v odzivnem vozlišču, kar pride do izraza pri
sistemih kratkega dosega. Alternativen pristop je
uporaba koncepta moduliranega odboja [26], ki je
primeren le za sisteme kratkega dosega. ToA algoritmi
za določanje lokacije se lahko uporabljajo tudi pri RToF
pristopu [27].
5.5 Faza prihoda signala (PoA)
Metode na podlagi faze prihoda signala določijo
lokacijo vozlišča prek faze oziroma razlike faz signala
[28]. Ob predpostavki, da vsi oddajniki oddajajo čisti
sinusni signal iste frekvence f in brez faznega zamika,
morajo za določitev faze signala na ciljnem vozlišču vsi
signali imeti omejeno prehodno zakasnitev. Na sliki 3
so oddajniki, označeni z A do D, nameščeni v oglišča
kocke. Zakasnitev je izražena kot razmerje valovne
dolžine signala in je v enačbi Si(t)=sin(2πft+φi)
označena z φi=(2πfDi)/c, kjer je i∈(A,B,C,D) in c
hitrost svetlobe. Dokler je valovna dolžina oddanega
signala daljša od diagonale kocke (0<φi<2π), se razdalja
lahko oceni (Di=(cφi)/(2πf) ). Za določanje lokacije
vozlišča se lahko nato uporabljajo isti algoritmi kot za
metodo ToA.
lokacija oddajnika
lokacija neznanega vozlišča
Slika 3: Določanje lokacije na podlagi faze signala
RADIJSKA LOKALIZACIJA V NOTRANJIH OKOLJIH: PREGLED PRISTOPOV 161
Za natančnejše določanje lokacije v notranjih okoljih
je mogoče pristop uporabljati v kombinaciji z metodami
na podlagi ToA/TDoA oziroma RSS. Glavna slabost
metode je, da za natančno določanje lokacije potrebuje
neposredno vidljivost med oddajnikom in
sprejemnikom, kar je, zlasti v notranjem okolju, po
navadi težko zagotoviti.
5.6 Kotni pristopi – Smer prihoda signala
(AoA)
Pri AoA je lokacija neznanega vozlišča določena s
presekom več parov kotno usmerjenih linij. Za določitev
lokacije vozlišča v dveh dimenzijah sta potrebni vsaj
dve sidrni vozlišči in dve meritvi kotov [3]. Za
izboljšanje natančnosti se za določanje lokacije
uporablja tri ali več sidrnih vozlišč. Za določitev smeri
sprejetega signala se uporabljajo ozko usmerjene antene
ali polje anten.
Glavna prednost pristopa je, da je lokacijo mogoče
določiti že z dvema (2D) oziroma v primeru 3D
lokalizacije s tremi merilnimi vozlišči. Poleg tega pa ni
potrebna nikakršna časovna sinhronizacija med
merilnimi vozlišči. Pristop ima tudi nekatere
pomanjkljivosti, kot so dodatne antene za meritve smeri
prihoda signala, ki podražijo sistem. Poleg tega so
predvsem zaradi večpotnosti, NLOS radijskega kanala,
senčenja signala ter odbojev od sten in drugih objektov
metode na podlagi AoA v notranjih okoljih razmeroma
neuporabne. Omenjeni dejavniki lahko bistveno
spremenijo smer prihoda signala in posledično močno
zmanjšajo natančnost sistema za določanje lokacije v
notranjih okoljih.
6 ANALIZA SCENE
Predvsem v mestnih in notranjih okoljih obstaja velika
verjetnost blokade neposrednega žarka in širjenja
radijskih žarkov po več poteh. V takih okoljih algoritmi
za določanje lokacije na podlagi dosega niso
najprimernejši. Za taka okolja so bili razviti algoritmi
analize radijske scene oziroma radijskega okolja, ki jih
imenujemo tudi algoritmi prstnega odtisa [29, 30].
Pri pristopu na podlagi analize scene, ki je prikazan
na sliki 4, se v prvi fazi, imenovani tudi faza kalibracije
oziroma faza priprave scene, zberejo značilnosti (t. i.
prstni odtis) za vse mogoče lokacije na izbranem
območju. V vsaki izbrani točki analiziranega območja
se s pomočjo modelov širjenja radijskega signala
izračunajo ali izmerijo lastnosti radijskih signalov
sidrnih vozlišč (RV(i)(x,y)) in zapišejo kot vektor
(RSli(1), RSli(2),...,RSli(j),…, RSli(N)), kjer je li i-ta
lokacija, (j) j-to sidrno vozlišče in N število sidrnih
vozlišč. Sledi gradnja map radijskega okolja za izbrano
območje. Mapa radijskega okolja je podatkovna baza
vnaprej določenih koordinat z različnimi
karakteristikami radijskega signala (RSS, koti signala,
čas razširjanja signala, impulzni odziv kanala, profil
močnostne zakasnitve), ki se imenujejo prstni odtisi
signala. Za vsak prstni odtis mora biti na voljo meritev
oziroma izračunana vrednost, ki vključuje informacije o
vseh sidrnih vozliščih in njihovih karakteristikah
sprejetega signala. Med samim delovanjem sistema
lokalizacije, v drugi fazi lokalizacije, neznano vozlišče
izmeri lastnosti signala na neznani lokaciji. Za
ugotovitev trenutne lokacije se nato izmerjene vrednosti
jakosti radijskih signalov primerjajo z vrednostmi v
podatkovni bazi oziroma prstnim odtisom. Prstni odtis
najbliže izmerjenemu določa lokacijo vozlišča.
RV(1) (x,y)
RV(2)(x,y)
RV(3)(x,y)
RV(I)(x,y)
RS1, RS2,...RSn
RS1, RS2,...RSn
RS1, RS2,...RSn
RS1, RS2,...RSn
RS1, RS2,...RSn (x,y)
algoritem za
določanje položaja
mobilno vozlišče
položaj mobilnega
vozlišča
faza lokalizacije
faza priprava scene
mapa radijskega
okolja (podatkvna
baza)
Slika 4: Blok diagram metode prstnega odtisa
Pristop ne potrebuje namenske strojne opreme, niti
časovne sinhronizacije med vozlišči. V celoti je lahko
implementiran programsko, kar v primerjavi s
predhodno predstavljenimi sistemi na podlagi meritev
časov in kotov zmanjšuje kompleksnost in znižuje ceno
sistema. Glavna slabost pristopa je predvsem težaven in
dolgotrajen proces kalibracije oziroma gradnje
radijskega okolja. Pristop je izjemno občutljiv na
spremembe okolja, kot so premikanje objektov v
zgradbi (ljudi, opreme), ukloni in odboji, kar vpliva na
razširjanje radijskega signala. Za vzdrževanje
natančnosti je potreben proces kalibracije, ki obsega
ponovno preračunavanje vnaprej določenih map jakosti
signala oziroma meritev lastnosti radijskega signala,
periodično ponavljati. V ta namen se lahko uporabljajo
tehnike zaznavanja množice (crowdsourcing) [31], ki pa
ne morejo zajeti informacij o spremembah lokacij,
oddajnih močeh itd. sidrnih vozlišč.
Za primerjavo prstnih odtisov se uporabljajo različne
tehnike prepoznavanja vzorcev, vključno z metodo
najmanjše kvadratne napake, največje podobnosti ter
naprednejše metode na podlagi nevronskih mrež.
6.1 Deterministični pristopi
Določanje lokacije prek Evklidove razdalje [32] je
preprost pristop prstnega odtisa, ki izračuna razliko med
trenutno izmerjeno vrednostjo in vrednostjo na lokaciji
m v podatkovni bazi, podano z
𝐷𝐸(𝑋𝑡,𝑚, 𝑋𝑟) = |𝑋𝑡,𝑚̅̅ ̅̅ ̅̅ − 𝑋𝑟̅̅ ̅|, (5)
162 HROVAT, MOHORČIČ, NOVAK, JAVORNIK
kjer sta Xt,m and Xr vektorja prstnih odtisov iz
podatkovne baze oziroma trenutno izmerjeni prstni
odtis. Za ocenjeno lokacijo je izbrana lokacija z
najmanjšo razdaljo. Po navadi je ocenjena lokacija
dodana v nabor najbolje ocenjenih lokacij. Torej je
mogoče namesto ene same lokacije, ki pomeni najboljše
ujemanje med podatkovno bazo in trenutno meritvijo,
uporabiti k najbolje ocenjenih lokacij in jih povprečiti
ter tako oceniti končno najverjetnejšo lokacijo vozlišča.
Pristop, ki uporablja razširjen nabor najbolje ocenjenih
lokacij (prstnih odtisov), se imenuje metoda k najbližjih
sosedov (kNN – k Nearest Neighbours). Medtem ko je
pri uporabi neutežene kNN metode vsakemu prstnemu
odtisu, ki je izbran kot najboljši približek lokacije
dodeljena enaka utež, so pri uteženi kNN (WkNN –
Weighted kNN) metodi vsakemu prstnemu odtisu
dodeljene določene uteži [33]. V [34] je predlagan
algoritem, imenovan napovedovani kNN (PkNN –
Predicted kNN), ki za ocenitev trenutne lokacije
vozlišča poleg metode WkNN uporabi tudi njegovo
predhodno lokacijo in hitrost premikanja. V [35] so
izboljšali natančnost ocene lokacije uporabnika s
pristopom filtriranje grozdov kNN (CFK – Cluster
Filtered kNN), ki za določitev k najbližjih sosedov
uporablja tehnike grozdenja.
6.2 Verjetnostni pristopi
Deterministične metode, kot na primer metode kNN,
v fazi določanja lokacije za izračun razdalje uporabljajo
srednjo vrednost vzorcev. Na ta način surovi podatki
zbrani v fazi kalibracije niso upoštevani celovito.
Statistični oziroma verjetnostni pristopi učinkoviteje
izrabljajo vzorce meritev, zbranih med fazo kalibracije
[36]. Osnovna ideja verjetnostnih metod pri lokalizaciji
s prstnim odtisom je izračun pogojne funkcije gostote
verjetnosti (PDF – Probability Density Function) stanja
x pri podani meritvi lastnosti radijskega signala y. Z
upoštevanjem Bayesianovega pravila velja
𝑝(x|y) =
𝑝(x|y)𝑝(x)
𝑝(𝑦)
. (6)
Funkcija p(y/x) se imenuje funkcija verjetnosti meritve
y, p(x) pa se imenuje a prior in je neodvisna od meritve.
Rezultat deljenja zmnožka a prior in verjetnosti z
normalizirano konstanto p(y) je pogojna PDf p(x|y), ki
se imenuje posterior stanja x.
Za določanje verjetnostne funkcije se lahko
uporabljajo neparametrični pristopi, kot sta na primer
metoda histogramov in metoda jedra, in parametrični
pristopi, kjer je histogram aproksimiran z znano
funkcijo (Gaussovo ali log-normalno distribucijo).
Omenjeni pristopi se opirajo na model merjenja in
predvsem na neparametrično in parametrično
aproksimacijo normaliziranih histogramov prstnih
odtisov [37].
Obstajajo tudi pristopi, ki kot prstni odtis signala
uporabljajo profil močnostne zakasnitve (PDP – Power
Delay Profile). Ta vsebuje informacije o moči signala in
časih dospetja različnih poti žarkov med izbranim
oddajnikom in sprejemnikom. Pri sinhroniziranih
omrežjih prvi vrh izmerjenega PDP določa čas dospetja
(ToA) sprejetega signala, ki se uporablja v algoritmih
ToA. Poleg tega pristop prstnega odtisa na podlagi PDP
(s časovno referenco) izrablja celotni izmerjeni PDP
(celotno časovno raznolikost). Zato lahko sistem za
določitev lokacije uporabi samo podatke iz ene same
točke, čeprav je sprejemanje signala z več točk še vedno
zelo zaželeno. Pri nesinhroniziranih omrežjih (brez
časovne reference), kjer ToA ni poznan, se lahko
izmerjeni PDP ujema s katerokoli zakasnjeno verzijo
PDP iz podatkovne baze. V tem primeru je treba sprejeti
signal z več točk, saj je mogoče prek izmerjenih PDP
določiti TDoA med različnimi oddajniki.
Impulzni odziv kanala (CIR - Channel Impulse
Response) v celoti opiše večpotni radijski kanal in
ohranja lokacijsko odvisnost ter je zelo primerna
metrika signala za določanje lokacije s postopkom
prstnega odtisa [38]. Da bi bile storitve lokalizacije
dostopnejše uporabnikom obstoječih in prihajajočih
širokopasovnih tehnologij, so v [39] predlagali
aproksimacijo CIR iz rezultatov ocene kanala na
sprejemniku. V OFDM sistemih je lahko ocena kanala
predstavljena kot vektor N kompleksnih elementov, ki
opisujejo kanal v frekvenčnem prostoru, kjer vrednost N
pomeni število podnosilcev. CIR je v časovnem
prostoru določen kot inverzna Fourierova transformacija
(IFT – Inverse Fourier Transform) diskretnega vektorja
ocene kanala v frekvenčnem prostoru. Za radijske
kanale v notranjih okoljih velja, da je po navadi največja
zakasnitev razširjanja po navadi manjša od 500 ns, kar
ustreza določenemu številu vzorcev v CIR. Preostali
vzorci so nepomembni za lokalizacijo. Za določanje
lokacije mora biti vrednost SNR dovolj visoka. Ob
povečanju pasovne širine sistema se poveča tudi
časovna ločljivost in posledično število nepomembnih
časovnih vzorcev postaja manjše. Za dosego ustrezne
natančnosti in računske učinkovitosti je treba na podlagi
pasovne širine sistema določiti ustrezno število časovnih
vzorcev.
6.3 Nevronske mreže
Pri pristopu na podlagi nevronskih mrež se v fazi
zajemanja podatkov zbirajo meritve moči sprejetega
signala in pripadajoče lokacije. Moči sprejetega signala
se med učno fazo uporabijo kot vhodni podatki,
pripadajoče lokacije pa kot izhodni podatki, kjer se
določajo uteži povezav med nevroni v nevronski mreži
[40]. Za lokalizacijo z nevronskimi mrežami se po
navadi uporablja večplastni perceptron z eno skrito
plastjo. Vhodni vektor moči sprejetega signala se
pripelje na sinapse vhodne plasti večplastnega
perceptrona, kjer se pomnoži z utežmi, ki so bile
določene med učno fazo, naknadno pa se po potrebi na
nevronih vhodne plasti doda še enosmerni pribitek za
dodatno kompenzacijo vhodnega signala. Vhodni
RADIJSKA LOKALIZACIJA V NOTRANJIH OKOLJIH: PREGLED PRISTOPOV 163
nevroni nato na podlagi svoje prenosne funkcije
izračunajo izhodni signal, ki se pelje na vhode vseh
nevronov v skriti plasti večplastnega perceptrona. Izhod
sistema je definiran kot vektor z dvema elementoma ali
kot vektor s tremi elementi, kar je odvisno od tega, ali
iščemo oceno lokacije v dveh ali v treh dimenzijah.
7 KOOPERATIVNA IN NEKOOPERATIVNA
LOKALIZACIJA
Pri nekooperativnem lokalizacijskem pristopu
komunikacija obstaja samo med navadnimi in sidrnimi
vozlišči, ki imajo znano lokacijo. Vsako vozlišče mora
komunicirati z več sidrnimi vozlišči, kar zahteva
razmeroma veliko gostoto sidrnih vozlišč oziroma dolg
doseg sidrnih vozlišč. Pri gradnji brezžičnega sistema so
stroški gradnje in vzdrževanja omrežja ključnega
pomena. Zato je po navadi število sidrnih vozlišč z
znano lokacijo omejeno in razmeroma redko. Poleg tega
so vozlišča pogosto tudi energijsko omejena, zlasti v
senzorskih omrežjih, kar zmanjšuje doseg posameznih
vozlišč. Posledično veliko  vozlišč ne sprejema signala
iz zadostnega števila sidrnih vozlišč z znano lokacijo. V
takih primerih je mogoče lokacijo vozlišč določiti z
uporabe lokalizacije z več skoki oziroma kooperativne
lokalizacije. Kooperativna lokalizacija uporablja poleg
komunikacije med vozlišči in sidrnimi vozlišči tudi
neposredno komunikacijo med vozlišči, ki imajo
neznano lokacijo. Pri izrabljanju neposredne
komunikacije med vozlišči ni potrebno, da so vsa
vozlišča v dosegu več sidrnih vozlišč, kar posledično
pomeni manjšo potrebno gostoto sidrnih vozlišč in
manjši doseg. Poleg tega pa lahko dodatne meritve med
pari vozlišč bistveno izboljšajo natančnost določanja
lokacije in povečajo območje pokrivanja [13].
Formalna definicija problema kooperativne
lokalizacije v [41] predvideva omrežje S z m>0 sidrnimi
vozlišči z znano lokacijo, ki so označeni od 1 do m, in
n-m>0 dodatnimi vozlišči, ki so označeni z m+1 do n in
so navadna vozlišča. Na podlagi podane meritve ij
med dvema vozliščema si in sj ter znanimi lokacijami
sidrnih vozlišč se s postopkom kooperativne lokalizacije
določijo neznane koordinate običajnih vozlišč tako, da
so dodeljene koordinate navadnih vozlišč v skladu z
meritvami ij in s koordinatami sidrnega vozlišča. Slika
5 prikazuje primer kooperativnega omrežja in
pripadajoči graf strukture, kjer so vozlišča 1, 2 in 3
sidrna vozlišča. Ker imajo ta vozlišča znane lokacije in
je mogoče izračunati njihovo medsebojno oddaljenost
brez dodatnih meritev metrik radijskega signala, so v
grafu med seboj povezani z robovi.
Kooperativne lokalizacijske algoritme na splošno
delimo na centralizirane, ki zbirajo meritve na
centralnem vozlišču in se tam tudi obdelajo, in
porazdeljene, ki zahtevajo, da vozlišča delijo
informacije samo s svojimi sosedi na iterativni način.
S1 S7
S6
S3
S5
S4
S13
S14
S15
S12
S9
S11
S8
S2
S10
1
7
6
3
5
4
13
14
15
12
9
11
8
2
10
a) b)
Slika 5: Kooperativno senzorsko omrežje a) in pripadajoči
graf b)
Centralizirani algoritmi za kooperativno lokalizacijo
določajo lokacijo vseh vozlišč na centralnem procesorju
oziroma vozlišču. Ta zbira podatke sidrnih vozlišč in
tudi navadnih vozlišč ter izračuna lokacijo vseh
navadnih vozlišč. Centralizirani pristopi po navadi niso
razširljivi in posledično niso uporabni za večja omrežja.
Glavni motiv za njihovo implementacijo je predvsem v
zagotavljanju boljše natančnosti ocenjene lokacije v
primerjavi z distribuiranim pristopom. Obstajajo trije
osnovni pristopi za načrtovanje centraliziranih
kooperativnih algoritmov na podlagi razdalje:
večdimenzionalno stopnjevanje (MDS –
MultiDimensional Scaling), linearno programiranje in
pristopi stohastične optimizacije [41].
Če so podatki poznani in jih je mogoče dobro opisati
z določenim statističnim modelom, je mogoče
implementirati pristop ocene največje podobnosti (MLE
– Maximum Likelihood Estimation). Eden od razlogov
za uporabo tega pristopa je, da se njegova varianca
asimptotično približuje spodnji meji, ki je podana z
mejo Cramér-Rao (CRB) [42]. Kot pove že samo ime,
je treba najti najbolj podobno funkcijo. Pristop ima dve
ključni omejitvi, in sicer: 1. obstaja velika verjetnost, da
rešitev konvergira v lokalni in ne v globalni maksimum,
in 2. močna odvisnost pristopa od modela (če se meritve
bistveno razlikujejo od domnevnega modela, rezultati
niso več zanesljivi).
Za preprečitev problema lokalnega maksimuma je
bilo predlagano, da se lokalizacija obravnava kot
konveksni optimizacijski problem. V [43] so
predstavljene omejitve konveksnosti, ki določajo, da
mora biti ocenjena lokacija vozlišča znotraj radija r
in/oziroma v območju kota [α1, α2] drugega vozlišča.
Hiter način za grobo ocenitev lokacije vozlišča je
mogoč z linearnim programiranjem [42], ki je, podobno
kot tehnike SDP (SemiDefinite Programming), računsko
zelo zahteven. Bistveno znižanje računske
kompleksnosti je doseženo s porazdeljenim algoritmom
SDP [44].
Algoritmi večdimenzionalnega stopnjevanja
opisujejo lokalizacijo vozlišč iz meritev razdalj kot
problem najmanjših kvadratov (LS) [45]. Pri klasičnem
MDS pristopu je LS rešitev določena z lastno
dekompozicijo (eigen-decomposition), ki ni
164 HROVAT, MOHORČIČ, NOVAK, JAVORNIK
izpostavljena problemu lokalnega maksimuma. Za
linearizacijo lokalizacijskega problema klasična metoda
MDS uporablja kvadrat razdalj. Končni rezultat je
močno odvisen od napak merjenja razdalje. Druge
tehnike MDS, ki ne temeljijo na lastni dekompoziciji, so
robustnejše, saj dovoljujejo utežene meritve glede na
zaznano natančnost [46]. Medtem ko je kompleksnost
pristopa MDS O(N3), kjer je N=n+m celotno število
vozlišč, je kompleksnost preostalih metod
mnogovrstnega (manifold) učenja, ki tudi temelji na
lastni dekompoziciji, O(N2). V [47] so bile
predstavljene zmogljivosti mnogovrstnega učenja, ki za
lokacijsko informacijo uporablja zabeležene senzorske
podatke. Prav tako s področja statističnega učenja
nadzorovano učenje obravnava lokalizacijo kot serijo
problemov zaznavanja [48]. V obravnavanem pristopu
je območje pokritja razdeljeno na manjša prekrivajoča
se območja. Vsako območje na podlagi meritev zazna,
ali je vozlišče znotraj njegovih meja.
Pri porazdeljenih algoritmih za kooperativno
lokalizacijo ni centralnih nadzornikov in vsako vozlišče
določi svojo lokacijo na podlagi lokalno zbranih
informacij. Tako se izognemo potrebam po centralnih
vozliščih z veliko računsko močjo, preprečimo ozka
grla, ki po navadi nastanejo pri komunikaciji vozlišč s
centralnim nadzornikom, ter dosežemo uravnoteženo
porabo energije v vseh vozliščih. Porazdeljeni algoritmi
so razširljivi in primerni tudi za večja omrežja ter jih
lahko razvrstimo v dve skupini, in sicer
multilateracijske algoritme in algoritme zaporednega
približevanja.
Pri pristopu multilateracije vsako vozlišče oceni
večskokovno (multihop) razdaljo do najbližjega
sidrnega vozlišča. Ko vsako sidrno vozlišče razpolaga z
ocenjenimi razdaljami do več sidrnih vozlišč, se njegova
lokacija izračuna lokalno, prek postopka multilateracije.
Algoritmi zaporednega približevanja poskušajo
določiti optimum globalne cenovne funkcije. V to
skupino spadajo algoritmi najmanjših kvadratov (LS –
Least Square), uteženih najmanjših kvadratov (WLS –
Weighted Least Squares) oziroma največje verjetnosti
(ML - Maximum Likelihood). Vsako vozlišče oceni
svojo lokacijo in nato odda ta podatek svojim sosedom,
ki na podlagi prejete informacije preračunajo svojo
lokacijo in jo ponovno oddajo. Postopek poteka do
končne konvergence. Naprava, ki nima nobene
koordinate, lahko začne s svojim lokalnim koordinatnim
sistemom in ga pozneje združi s sosednjimi
koordinatnimi sistemi. Po navadi je mogoče s pristopi
zaporednega približevanja doseči boljše rezultate,
vendar je treba obravnavati vprašanje konvergence.
Najnovejše raziskovalne smeri na področju
porazdeljenih algoritmov vključujejo tako imenovane
pristope na podlagi filtriranja delcev (angl. particle
filters), kjer vsako vozlišče shrani delce, ki pomenijo
morebitne koordinate vozlišča in so uteženi glede na
njihovo podobnost. Metode se uporabljajo za natančno
lociranje in sledenje robotov ter v bodočih raziskavah
lokalizacijskih postopkov za senzorska omrežja. V [49]
so problem lokalizacije v senzorskih omrežjih
formulirali kot problem sklepanja na grafičnih modelih
in za določitev približne lokacije vozlišča uporabili
različico tehnike širjenja zaupanja (BP – Belief
Propagation), tako imenovani algoritem
neparametričnega širjenja zaupanja (NBP –
Nonparametric Belief Propagation). Pristop NBP je
implementiran kot algoritem za lokalno iterativno
izmenjavo sporočil. V vsakem koraku vozlišče določi
zaupanje svoje ocenjene lokacije in pošlje informacijo
zaupanja svojim sosedom, prejme koristne informacije
od sosedov ter nato iterativno posodobi svoje zaupanje.
Iterativni proces se prekine le, ko je konvergenčni
kriterij zaupanja in ocenjenih lokacij vozlišča v omrežju
dosežen. Glavni prednosti algoritma sta preprosta
porazdeljena implementacija in razmeroma majhno
število iteracij, potrebnih za dosego konvergence. Poleg
tega pristop zagotavlja tudi informacije o negotovosti
ocenjene lokacije. V [50] je Bayesianovo sklepanje
izvedeno prek iterativnega postopka lokalnega
posredovanja sporočil, ki temelji na širjenju prepričanja
in predstavitev sporočil s filtriranjem delcev.
Obstajajo tudi hibridni algoritmi, ki združujejo
značilnosti centraliziranih in porazdeljenih algoritmov
in tako zmanjšujejo porabo energije. Pri hibridnem
pristopu se celotno omrežje razdeli na več manjših gruč.
V vsaki gruči algoritem izbere centralno vozlišče za
ocenitev lokacij vozlišč v gruči. V naslednji fazi vsa
centralna vozlišča za združitev in optimizacijo lokalno
določenih lokacij uporabijo porazdeljene algoritme [51].
8 SKLEP
Lokacija uporabnikov v radijskem omrežju je postala
pomembna informacija za optimizacijo radijskih
omrežij in zagotavljanje lokacijsko odvisnih storitev,
zato je področje radijske lokalizacije pritegnilo izjemno
zanimanje raziskovalcev. S širjenjem aplikacij
brezžičnih senzorskih omrežij se je potreba po
preprostih in robustnih lokalizacijskih tehnikah še
povečala, predvsem v notranjosti objektov, kjer
lokalizacija s pomočjo satelitov odpove. Pričujoči
prispevek je obširen pregled lokalizacijskih tehnik in
algoritmov, ki so primerni predvsem za določanje
lokacije v notranjosti objektov oziroma na gostih
urbanih območjih.
V prispevku smo obravnavali različne izzive pri
načrtovanju lokalizacijskih tehnik. Določili smo vrsto
kriterijev za ocenjevanje lokalizacijskih tehnik, kot so
razpoložljivost, odzivnost, pokritost, cena,
kompleksnost itd. Pogosto je treba pri izbiri sistema
oziroma tehnike za določanje lokacije narediti
kompromis, na primer med kompleksnostjo in
natančnostjo rešitve, ki je po navadi odvisen od okolja
in namena uporabe aplikacije.
Po kratkem pregledu brezžičnih tehnologij smo
podali različne klasifikacije tehnik lokalizacije. Medtem
ko triangulacijske tehnike določajo lokacijo vozlišč na
RADIJSKA LOKALIZACIJA V NOTRANJIH OKOLJIH: PREGLED PRISTOPOV 165
podlagi posrednega merjenja razdalje prek različnih
metrik radijskega signala, pristopi analize scene,
imenovani tudi pristopi prstnega odtisa, temeljijo na
primerjanju trenutne meritve radijskega signala z
izmerjenimi oziroma izračunanimi podatki, ki so
shranjeni v podatkovni bazi oziroma radijski mapi
okolja. Izbira tehnologije in tehnike lokalizacije močno
vpliva na resolucijo in natančnost lokacijske
informacije.
Sodelovanje med vozlišči lahko bistveno izboljša
zmogljivost lokalizacije. Predvsem v omrežjih, kjer ni
na voljo zadostnega števila vozlišč z znano lokacijo, se
čedalje pogosteje uporabljajo kooperativni lokalizacijski
pristopi, katerih pregled smo podali v zadnjem delu
prispevka.
Kljub številnim obstoječim pristopom, ki rešujejo
problem lokalizacije v notranjih okoljih, trenutne rešitve
ne dosegajo potrebne ravni učinkovitosti oziroma
zmogljivosti, ki jih zahteva večina aplikacij. Z dosego
zahtev za različna aplikacijska okolja, kot so natančnost,
pokritje, razpoložljivost in minimalni stroški
namestitve, se ukvarja velik del raziskovalnih pristopov.
Trendi radijske lokalizacije za notranja okolja gredo
v smeri novih hibridnih rešitev za 5G omrežja, ki
temeljijo na razpoložljivih sistemih in tehnologijah,
kooperativni lokalizaciji in na novih inovativnih
aplikacijah za različne mobilne naprave, kjer bo
lokacijska informacija uporabljena za izboljšanje
kakovosti uporabniške izkušnje in tudi kot dodana
vrednost obstoječim storitvam brezžičnih operaterjev.
ZAHVALA
Projekt »L2-7664 Napredne tehnike sledenja žarkom za
karakterizacijo radijskega okolja in radijsko
lokalizacijo« je sofinancirala Javna agencija za
raziskovalno dejavnost Republike Slovenije.