Connectivity and Reliability in Ad Hoc Networks
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology |
Diplomityö
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Authors
Date
2003
Department
Major/Subject
Tietoverkkotekniikka
Mcode
S-38
Degree programme
Language
en
Pages
vi + 48
Series
Abstract
Ad hoc -verkko on viime aikoina kasvavaa kiinnostusta herättänyt tutkimuskonsepti. Sillä tarkoitetaan langattomien päätelaitteiden keskenään muodostamaa verkkoa, joka on täysin riippumaton kiinteästä verkkoinfrastruktuurista. Tällaisille verkoille on lukuisia sovellusmahdollisuuksia, joista erilaiset istunnot, sotilasverkot ja pelastusviranomaisten hätätilanteissa muodostamat verkot ovat vain muutamia esimerkkejä. Vaikka ad hoc -verkkoja on tutkittu jo kauan, ensimmäinen käytännön toteutus antaa vielä odottaa itseään: ad hoc -verkkoihin liittyy monta haastavaa ongelmaa. Eräs niistä on verkon yhteydellisyys eli vaatimus siitä, että verkon kaikki solmut saavat yhteyden toisiinsa. Tämä riippuu solmujen keskinäisistä etäisyyksistä ja suoran viestinnän kantamasta. Tässä työssä lähestytään yhteydellisyysongelmaa mallintamalla verkko satunnaisgraafina. Olettamalla kaikille verkon solmuille yhtä suuri kantama (tai yleisemmin suurin saavutettava kantama) määritellään verkon yhteydellisyyden rajakantama satunnaismuuttujaksi. Tämän käyttäytymistä tutkitaan simuloimalla olettaen, että solmujen sijainnit noudattavat tasajakaumaa, ja käyttäen apuna graafialgoritmia, joka määrittää rajakantaman annetusta solmujoukosta. Simulointidatan analyysin tuloksena saadaan tilastollisia malleja, jotka kytkevät toisiinsa tarvittavan solmujen lukumäärän ja/tai kantaman sekä sallitun pinta-alan, jolle solmut ovat hajaantuneet, siten että satunnainen verkko on yhteydellinen (graafiteorian termein yhtenäinen) suurella todennäköisyydellä. Tarkastelua laajennetaan yleisempään k-yhtenäisyyden käsitteeseen. Verkko joka on k-yhtenäinen pysyy yhtenäisenä, kun siitä poistetaan mitkä tahansa k - 1 solmua, millä on tärkeä merkitys verkon luotettavuuden kannalta. Rajakantaman määritelmä voidaan suoraan yleistää k-yhtenäisyyteen. Työssä kehitetään 2- ja 3-yhtenäisyyden rajakantamat etsivät algoritmit, ja simulointidataan sovitetaan tilastolliset mallit samaan tapaan kuin yksinkertaisen yhtenäisyyden tapauksessa. Lisäksi tehdään vertailevaa analyysiä eri yhtenäisyyden asteisiin tarvittavien kantamien välillä.Description
Supervisor
Aalto, SamuliThesis advisor
Virtamo, JormaKeywords
Ad hoc networks, Ad hoc -verkot, connectivity, yhteydellisyys, reliability, yhtenäisyys, random graphs, luotettavuus, graph algorithms, satunnaisgraafit, statistical models, graafialgoritmit, tilastolliset mallit