Tummalla pohjalla valkoisten viivojen verkosto.

Väittelijä kehitti uusia keinoja verkossa paikantamiseen (Väitös: FM Anni Hakanen, 18.6.2021, matematiikka)

FM Anni Hakanen selvitti väitöskirjatutkimuksessaan, miten verkkomaisissa rakenteissa useiden kohteiden samanaikaista paikannusta voidaan tehdä etäisyyksien avulla. Hakasen kehittämiä uusia paikannuskeinoja on mahdollista hyödyntää esimerkiksi robottien ohjaamisessa tai tunkeilijoiden jäljittämisessä tietoverkoissa. 
 

Monia rakenteita ja ilmiöitä voidaan mallintaa verkkomaisella rakenteella. Verkko koostuu toisiinsa viivoilla yhdistetyistä pisteistä. Esimerkiksi tietoliikenneverkkoa mallinnettaessa tietokoneita ja reitittimiä voidaan kuvata pisteillä ja niiden välisiä yhteyksiä viivoilla. Anni Hakanen tutkii väitöskirjassaan, miten verkossa voidaan paikantaa sen pisteissä sijaitsevia kohteita verkkoon sijoitettujen etäisyysanturien avulla. 

– Paikannettavan kohteen voidaan ajatella olevan vaikkapa robotti tehtaassa tai tunkeilija tietoverkossa. Kohteen sijaintitiedon avulla voidaan esimerkiksi opastaa robotti liikkumaan oikeaan suuntaan tai pysäyttää tunkeilijat, Hakanen kertoo.

Paikannusta varten verkosta valitaan pisteet, joihin etäisyyttä mittaavat anturit laitetaan. Jokainen anturi ilmoittaa etäisyyden itsensä ja paikannettavan kohteen välillä. Annettujen etäisyyksien avulla päätellään paikannettavan kohteen sijainti verkossa. 

–  Taustalla oleva ajatus on siis täsmälleen sama kuin GPS-paikannuksessa. Kolmiulotteisen maailman sijaan tarkastellaan verkkoa, jossa etäisyyttä mitataan eri tavalla. Senttien ja metrien sijaan lasketaan yhteyksien lukumäärää. Toisiinsa viivalla yhdistetyt pisteet ovat etäisyydellä yksi toisistaan. Jos taas pisteestä toiseen pitää kulkea käyttämällä vaikkapa kolmea yhteyttä eli viivaa, pisteiden välinen etäisyys on kolme, Hakanen selventää.

Väitöskirjatutkimuksessa pääpaino on usean kohteen samanaikaisella paikantamisella. Paikannusta verkoissa etäisyyksien avulla on tutkittu jo 1970-luvulta lähtien. Aiempi tutkimus on kuitenkin keskittynyt vain yhden kohteen paikantamiseen kerrallaan. 

–  Muissa samankaltaisissa verkoissa käytettävissä paikannusmalleissa yleistys useaan paikannettavaan on tehty jo aiemmin. Etäisyyksillä paikantamisessa olikin selvä aukko, jota oli luontevaa lähteä tutkimaan, Hakanen sanoo. 

Hakasen mukaan aiempaa vain yhden kohteen paikantavaa mallia ei voi sinällään käyttää tilanteissa, joissa paikannettavien kohteiden lukumäärä ei ole paikantajan hallinnassa. Näin voi olla esimerkiksi silloin kun paikannettavat kohteet ovat tunkeilijoita. 

– Pahimmillaan kaksi tunkeilijaa voivat yhteistoimin hämätä paikantajan luulemaan, että verkossa on vain yksi tunkeilija paikassa, jossa tunkeilijoita ei ole lähimainkaan. Väitöskirjassa tarkasteltujen paikantamisen mallien avulla useampiakin tunkeilijoita voidaan paikantaa luotettavasti.

Verkon rakenteesta riippuen jotkin verkon pisteet ovat elintärkeitä paikantamisen onnistumiselle 

Hakanen havaitsi tutkimuksessaan, että verkon rakenne voi toisinaan olla sellainen, että on olemassa pisteitä, joihin on pakko laittaa anturit usean kohteen paikantamiseksi. 

–  Tällaisten pisteiden tapauksessa ei auta vaikka laittaisimme anturit kaikkiin paitsi tähän yhteen tiettyyn verkon pisteeseen. Usean kohteen samanaikainen paikantaminen ei kerta kaikkiaan onnistu. Näiden pisteiden karakterisointi onkin yksi väitöskirjani kohokohdista. Kun pakolliset anturien paikat ovat tiedossa etukäteen, anturien sijoittaminen helpottuu huomattavasti, Hakanen täsmentää. 

Anturien optimaalisen sijoittelun määrittäminen on laskennallisesti vaikeaa, jos verkon rakennetta ei rajoiteta. Pakolliset anturien paikat on helppo havaita, ja näin anturien lukumäärälle saadaan alaraja. Anturien sijoittaminen vain pakollisiin paikkoihin ei kuitenkaan aina riitä paikantamisen onnistumiseen, vaan antureita täytyy olla enemmän.

– Muiden kuin pakollisten anturien sijoittaminen onkin sitten vaikeampaa. Optimaalisia tapoja sijoittaa anturit voi olla useita, ja ne voivat erota toisistaan suurestikin. Pakollisten paikkojen löytyminen helpottaa jo suuresti, mutta helppoa optimaalisen sijoittelun määrittäminen ei vieläkään ole, Hakanen kertoo.

***

FM Anni Hakanen esittää väitöskirjansa ”On Using Distances to Locate Vertices: Resolving Sets and Metric Bases of Graphs, Two Generalisations and Their Forced Vertices” julkisesti tarkastettavaksi Turun yliopistossa perjantaina 18.6.2021 klo 12. 

Väitöstilaisuutta voi seurata etänä 
Passcode: 553274

Vastaväittäjänä toimii apulaisprofessori Cristina Dalfó (Universitat de Lleida, Katalonia, Espanja) ja kustoksena professori Tero Laihonen (Turun yliopisto). Tilaisuus on englanninkielinen. Väitöksen alana on matematiikka.

Turun yliopisto seuraa aktiivisesti koronavirustilannetta ja viranomaisten ohjeita. Yliopisto päivittää ohjeitaan tilanteen mukaan. Ohjeet ja linkit löytyvät osoitteesta: utu.fi/koronavirus

Väittelijän yhteystiedot: anehak@utu.fi
 

 

Luotu 16.06.2021 | Muokattu 16.06.2021