AG Vernetzte Systeme Publikationen Jahr 2008 Nis08

 

M. Nissler

Diplomarbeit, Fachbereich Informatik, Technische Universität Kaiserslautern, 2008

Zusammenfassung

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 first part of this thesis defines 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 flows between pairs of nodes that are to be handled by the network) is defined 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 flows 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 flow 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 flow to take different paths through the network, is beneficial over the more restricted approach that uses a single path for all frames of a flow. Using multiple paths for a flow promises some advantages, such as better balancing of the load the network has to handle, thus possibly allowing the network to handle more data flows. 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 significant performance gains can be realized by using multi-paths instead of a single one. Then, topological network features are identified that influence the relative performance of multi-path and single-path solutions, respectively. Based on the system model developed in the first 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.

Vollversion

• pdf (885kb)

---

	Übergeordnete Seite: Jahr 2008

	Feedback
	Zu den Kontaktdetails des Verantwortlichen dieser Seite

	English
	This page in english. Diese Seite auf englisch.