TKK | Tietoverkkolaboratorio | Julkaisut

Henri Koskinen: Connectivity and Reliability in Ad Hoc Networks

Abstract of Master's Thesis

Despite a long history of research, the first ad hoc network is yet to be implemented: the nature of ad hoc networks poses several challenging
problems. One of them is that of connectivity, namely, the requirement that the network connect every pair of network nodes. This property depends
on the pairwise node distances and the range of communication of the nodes.

This study addresses the connectivity problem by modelling the network as a geometric random graph. Assuming a common communication range for the
network nodes (or, more generally, limit for the range), the threshold value of this range for connectivity is defined as a random variable.
Utilizing a graph algorithm that finds this threshold range from a given set of nodes, extensive simulations are carried out assuming uniform
spatial distribution of the nodes. Analysis of the simulation data results in statistical models that bind together the required number of nodes
and/or communication range and the allowed area spanned by the network so that a random network is connected with a high probability.

The scope of the study is extended to the more general concept of k-connectivity. A k-connected network retains connectivity after the removal
of any k-1 nodes, which bears significance in terms of network reliability. The definition of the threshold range can readily be generalized to
k-connectivity. Algorithms for finding the threshold ranges for 2- and 3-connectivity are developed, and statistical models are fitted to
simulation data in the same way as in the case of simple connectivity. In addition, some comparative analysis between the communication ranges
required for the different degrees of connectivity is made.
 

Keywords:

Ad hoc networks, connectivity, reliability, random graphs, graph algorithms, statistical models

Henri Koskinen: Ad hoc -verkkojen yhteydellisyys ja luotettavuus

Diplomityön tiivistelmä

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ä.
 

Avainsanat:

Ad hoc -verkot, yhteydellisyys, yhtenäisyys, luotettavuus, satunnaisgraafit, graafialgoritmit, tilastolliset mallit

Tietoverkkolaboratorio on nyt osa Tietoliikenne- ja tietoverkkotekniikan laitosta. Tällä sivulla oleva tieto voi olla vanhentunutta.