| Nimeke: | Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs |
| Muu nimeke: | Optimointiongelmat langattomissa anturiverkoissa: paikallisia algoritmeja ja paikallisia verkkoja |
| Tekijä: | Suomela, Jukka |
| Muu tekijä: | Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, tietojenkäsittelytieteen laitos Helsingfors universitet, matematisk-naturvetenskapliga fakulteten, institutionen för datavetenskap University of Helsinki, Faculty of Science, Department of Computer Science Helsinki Institute for Information Technology HIIT |
| Päiväys: | 2009-06-13 |
| Taso: | Väitöskirja (artikkeli) |
| Tiivistelmä: | Hajautettu järjestelmä koostuu tietoa käsittelevistä laitteista sekä laitteiden välisistä tiedonsiirtoyhteyksistä. Tuttuja esimerkkejä laajoista hajautetuista järjestelmistä ovat Internet ja matkapuhelinverkot. Hajautettuihin järjestelmiin liittyy lukuisia optimointiongelmia: tietoverkon rajallisista resursseista halutaan saada mahdollisimman paljon hyötyä verkon käyttäjille. Tässä väitöskirjatyössä tutkitaan tehokkaita algoritmeja tällaisten optimointiongelmien ratkaisemiseksi.
Tässä työssä keskitytään erityisesti yhteen esimerkkiin hajautetuista järjestelmistä: langattomiin anturiverkkoihin. Anturiverkon laitteet ovat tyypillisesti pieniä, paristokäyttöisiä mittalaitteita, joiden tuottamat tiedot halutaan kerätä yhteen paikkaan tallennettavaksi ja analysoitavaksi. Anturiverkkoa voidaan käyttää esimerkiksi säähavaintojen tekemiseen tai teollisuuslaitosten valvontaan. Langattomassa anturiverkossa tietoa välitetään radioyhteyksien avulla. Jos etäisyydet mittalaitteiden ja tiedon tarvitsijan välillä ovat pitkiä, tietoa voidaan joutua välittämään useamman linkkisolmun kautta. Yksi keskeinen paristokäyttöisiin anturiverkkoihin liittyvä optimointiongelma on verkon eliniän maksimointi: halutaan, että verkko on toimintakykyinen mahdollisimman pitkään ennen kuin mittalaitteiden paristot joudutaan lataamaan uudestaan. Koska radiolähetykset kuluttavat paljon energiaa, yksi keskeinen haaste on valita energiankulutuksen kannalta parhaat mahdolliset reitit, joita pitkin tietoa välitetään anturilaitteilta tiedon tarvitsijalle. Jos laitteet voivat käyttää useita eri linkkisolmuja tiedon välittämiseen, ei välttämättä valita linkkisolmuista joka kerta lähintä, vaan pyritään hyödyntämään solmujen kokonaiskapasiteetti mahdollisimman tehokkaasti. Tällaiset reititysongelmat voidaan muotoilla matemaattisesti ns. max-min-lineaariohjelmina. Yksi väitöskirjatyön päätuloksista koskee juuri max-min-lineaariohjelmien ratkaisemista tehokkaasti hajautetussa järjestelmässä. Työssä tarkastellaan erityisesti paikallisia algoritmeja eli vakioaikaisia hajautettuja algoritmeja. Paikallisessa algoritmissa verkon jokainen laite tekee päätöksiä pelkästään laitteen lähiympäristössä olevan tiedon perusteella näinkin rajoitetulla laskennan mallilla on mahdollista löytää ratkaisuita, jotka ovat lähellä globaalia optimia. Tässä työssä esitetään mm. paikallinen algoritmi eräiden max-min-lineaariohjelmien likimääräiseen ratkaisemiseen; työssä myös todistetaan, että tämän paikallisen approksimointialgoritmin takaama approksimointisuhde on paras mahdollinen. Muita tarkasteltavia optimointiongelmia ovat solmujen toiminnan aikatauluttaminen ja solmujen määrän minimointi. Nämä ovat laskennallisesti vaikeita ongelmia yleisessä tapauksessa, mutta työssä osoitetaan, että näiden ongelmien likimääräinen ratkaiseminen onnistuu tehokkaasti, jos hyödynnetään realistisia oletuksia tiedonsiirtoverkon rakenteesta. Tällaisia oletuksia voidaan kuvata esimerkiksi ns. paikallisilla verkoilla. |
| Avainsanat: | tietojenkäsittelytiede |
| Näytä kaikki kuvailutiedot | |