Modeling and Analysis of Optimal Slot Allocations in Wireless Ad-Hoc Networks
Diplomarbeit, Fachbereich Informatik, Technische Universität Kaiserslautern, 2008
In this thesis, the problem of multi-hop data transmissions through a wireless network, possibly via several paths, is considered. Transmissions are coordinated network-wide through time division multiple access (TDMA). Time is split into intervals called slots, which can be reserved for transmissions. The reservations are made in a way such that concurrent transmissions in a slot do not interfere with each other.
The ﬁrst part of this thesis deﬁnes the mathematical model that allows a formal treatment of the networks under consideration. A graph structure provides the network topology, i.e. potential links between the network nodes. Whether transmissions actually succeed is determined by a noninterference model which formalizes conditions that have to be met for a transmission to be received successfully in the situation that concurrent transmissions are being performed in the network. The noninterference model is exchangeable; three different possible models are introduced that differ in the precision they capture the underlying physical effects. A formal notion of scenarios (i.e. sets of data ﬂows between pairs of nodes that are to be handled by the network) is deﬁned and the conditions that must be met by a set of slot reservations to solve a scenario are developed. In the prospect of evaluating the relative performance, the model allows solutions to handle data ﬂows via a single path or multiple paths. Finally, metrics that allow to compare the performance of solutions w.r.t. different aspects such as the end-to-end delay a ﬂow experiences when handled by a solution or the amount of energy that is consumed under a given solution are introduced.
An important aspect of our TDMA-based network model is that the effects of queueing and indeterminism at the medium access layer are largely avoided. On the one hand, this allows to capture important system parameters such as throughput and end-to-end latency in a mathematically exact way. On the other hand, this reduced indeterminism is a very desirable property for applications that have stringent Quality-of-Service requirements, since the system allows to give guarantees on throughput and latency bounds.
The second part of this thesis examines the question whether multi-path routing, i.e. allowing data frames belonging to the same ﬂow to take different paths through the network, is beneﬁcial over the more restricted approach that uses a single path for all frames of a ﬂow. Using multiple paths for a ﬂow promises some advantages, such as better balancing of the load the network has to handle, thus possibly allowing the network to handle more data ﬂows. Furthermore, multi-path routing can be used to improve the reliability of the data transmissions by adding redundancy as well as enhancing throughput and latency by avoiding hot spots in the network. First, some constructed example networks are investigated which prove that there are situations in which signiﬁcant performance gains can be realized by using multi-paths instead of a single one. Then, topological network features are identiﬁed that inﬂuence the relative performance of multi-path and single-path solutions, respectively. Based on the system model developed in the ﬁrst part of this thesis, the performance of the approaches is evaluated by studying algorithmically obtained optimal solutions to a large number of randomly generated scenarios.
- pdf (885kb)
|Superordinated page: Year 2008|
|Go to the contact details of the person in charge of this page|
|This page in german. Diese Seite auf deutsch.|