Forwarding Capacity in Large Wireless Multihop Networks - A Computational Approach

Abstract

Wireless multihop networks are networks without any fixed infrastructure. This thesis concentrates on a network consisting of a plethora of immobile nodes communicating with each other over a shared wireless channel. The intrinsic nature of the shared wireless channel makes it difficult to efficiently avoid interference between the transmissions, and the exact capacity of such a network is in many respects an open question.

At first, we characterize the capacity problem in a massively dense wireless network where a separation of scales emerges, and the problem can be separated into two different subproblems. The two subproblems loosely correspond to routing at the global scale and forwarding at the local scale. We focus on the latter one and study the microscopic level multidirectional forwarding capacity problem that considers an infinitely large network's capability to relay information. Because of the complexity of analyzing a large random network and wireless interference, the main approach is to construct algorithms that produce numerical bounds or estimates for the forwarding capacity, and simulate them for large network realizations. The methods used for studying the forwarding capacity are presented in two parts. The first part considers the instantaneous forwarding capacity. The instantaneous forwarding capacity can be achieved temporarily but cannot be maintained for a longer time period. It is a natural upper bound for the actual forwarding capacity and can be analyzed with more complex ways of modeling interference, such as the SINR-based models, in addition to the simple Boolean interference model. The actual forwarding capacity with multihop traffic under the Boolean interference model is considered in the second part. In this part, the upper bound provided by the instantaneous capacity is tightened for a small number of neighbor nodes, where it is less accurate. We also provide a lower bound that shows a notable improvement compared with previous results for uncoordinated opportunistic forwarding. Finally, an estimate is found for the forwarding capacity. The dependence of the estimate on the directional distribution of the traffic is studied to determine the possible gain from interleaving traffic in different directions compared with time sharing between the directions. Eventually, it is illustrated how the results for the forwarding capacity can be used with the macroscopic level results to obtain the total capacity of a large wireless network. The thesis hence makes it possible to calculate a numerical estimate for the total capacity.

Langattomat monihyppyverkot ovat verkkoja, joilla ei ole kiinteää rakennetta. Tämä työ tarkastelee verkkoa, joka koostuu suuresta joukosta liikkumattomia päätelaitteita, jotka kommunikoivat keskenään käyttäen yhteistä langatonta kanavaa. Tämä jaettu media tekee lähetysten välisten häiriöiden tehokkaan välttämisen vaikeaksi, ja kyseisen verkon tarkka kapasiteetti on siksi monelta osin avoin kysymys.

Aluksi työssä luonnehditaan kapasiteettiongelmaa massiivisen tiheässä langattomassa verkossa, jossa voidaan erottaa mikroskooppinen ja makroskooppinen mittakaava, ja verkon kapasiteetin maksimointi jakautuu kahdeksi erilliseksi ongelmaksi. Nämä kaksi aliongelmaa vastaavat löyhästi kokonaistason reititystä ja paikallisen tason välitystä. Tämä työ keskittyy jälkimmäiseen ja tutkii mikroskooppisen tason monisuuntaista välityskapasiteettiongelmaa, joka käsittelee äärettömän suuren verkon kykyä välittää informaatiota. Suurten satunnaisten verkkojen ja langattoman häiriön analysoinnin vaikeudesta johtuen ongelmaa on lähestytty konstruoimalla algoritmeja, jotka tuottavat numeerisia ylä- tai alarajoja tai estimaatteja väli-tyskapasiteetille, ja simuloimalla niitä suurissa verkkorealisaatioissa. Välityskapasiteetin tutkimisessa käytetyt menetelmät on esitetty kahdessa osassa. Ensim-mäinen osa käsittelee hetkellistä välityskapasiteettia. Hetkellinen välityskapasiteetti voidaan saavuttaa tilapäisesti, mutta sitä ei voida ylläpitää pidempiä ajanjaksoja. Se on luonnollinen yläraja todelliselle välityskapasiteetille, ja sitä voidaan analysoida myös monimutkaisemmilla häiriömalleilla, kuten signaalin ja häiriön suhteeseen perustuvilla malleilla, yksinkertaisen Boolen häiriömallin lisäksi. Toisessa osassa tarkastellaan todellista välityskapasiteettia monihyppyiselle liikenteelle, kun häiriömalliksi oletetaan Boolen malli. Tässä osassa hetkellisen kapasiteetin muodostamaa ylärajaa tiukennetaan naapurisolmujen lukumäärän ollessa pieni, jolloin se on löyhä. Lisäksi annetaan alaraja, joka on huomattava parannus verrattuna aikaisempiin tuloksiin koordinoi-mattomalle opportunistiselle välitykselle. Seuraavaksi työssä esitetään arvio välityskapasitee-tista. Arvion riippuvuutta liikenteen suuntajakaumasta tutkitaan, jotta voidaan määrittää erisuuntaisten liikennevirtojen yhdistämisestä saatava mahdollinen hyöty verrattuna aikaja-koon suuntien välillä. Lopuksi havainnollistetaan, kuinka välityskapasiteetille tuotetut tulokset voidaan yhdistää makroskooppisen tason tulosten kanssa suuren langattoman verkon koko-naiskapasiteetin määrittämiseksi. Työ siis paitsi valottaa kapasiteetin muodostumiseen vaikuttavia tekijöitä myös mahdollistaa numeerisen arvion laskemisen kokonaiskapasiteetille.