Details

Autor(en) / Beteiligte

• Kolb, Christina
• Scheideler, Christian[Akademischer Betreuer]
• Meyer auf der Heide, Friedhelm[Akademischer Betreuer]

Titel

Competitive routing in hybrid communication networks and message efficient SetCover in Ad Hoc networks

Ort / Verlag

Paderborn

Erscheinungsjahr

2022

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 09.03.2022
• ger: Routing ist in drahtlosen Ad-Hoc Netzwerken eine große Herausforderung, vor allem, wenn Knoten mobil sind und so weit auseinander liegen, dass entweder viele Hops oder lange Wege benötigt werden, um eine Nachricht von einem Knoten zu einem anderen zu senden. In der Tat ist bekannt, dass jedes Online-Routing-Protokoll im worst-case sehr schlecht performt, genau in dem Sinne, dass es eine Verteilung der Knoten gibt, die zu einem schlechten Routingpfad für das Protokoll führt, sogar dann, wenn Knoten zwar ihre geographische Position kennen, aber die des Nachrichtenziels unbekannt ist. Der Grund hierfür sind Funklöcher im Ad-Hoc Netzwerk: Diese erfordern große Routingumwege bis eine Nachricht ihr Ziel erreicht und die nur sehr schwer mit einem Online-Routing-Ansatz zu finden sind. Die Annahme in dieser Doktorarbeit ist ein schnurloses Ad-Hoc Netzwerk, das begrenzt long-range-links nutzen kann, welche über eine globale Kommunikationsinfrastruktur, wie zum Beispiel eine zellulare Infrastruktur oder einen Satelliten, zur Verfügung gestellt wird. Das Ziel ist hierdurch eine Abstraktion des drahtlosen Ad-Hoc Netzwerks zu berechnen, um möglichst kurze Routingwege im Ad-Hoc Netzwerk zu finden. Wir präsentieren einen verteilten Algorithmus, der eine Abstraktion des Ad-Hoc Netzwerk in O(log^2 n) Runden mit Hilfe von long-range-links berechnet. Das Resultat sind c-kompetative Routingpfade zwischen Knotenpaaren des Ad-Hoc Netzwerks für eine Konstante c. Wir nehmen in diesem Fall an, dass sich die konvexen Hüllen der Funklöcher nicht überschneiden. Des Weiteren zeigen wir, dass der dafür benötigte Speicher nur von er Anzahl der Knoten und der Größe des Funklochs abhängt und komplett unabhängig von der Gesamntanzahl der Knoten des Ad-Hoc Netzwerks.
• eng: Competitive routing is a challenging problem for wireless ad hoc networks, for example, when the nodes are mobile, spread so widely, and in the most cases multiple hops and long paths are needed to route a message from a source node to a target. It is known that any online routing algorithm has a poor performance in the worst case, i.e., there is a distribution of nodes resulting in bad routing paths for that algorithm. This happens even if the nodes know their geographic positions and the geographic position of the destination of a message. This is because radio holes in the ad hoc network require messages to route via long detours in order to get to a destination. This is hard to find in an online fashion. In this thesis, we assume that a wireless ad hoc network makes limited use of long-range links. The long-range links are provided by a global communication infrastructure which can be a cellular infrastructure or a satellite. The global communication infrastructure helps to compute an abstraction of the wireless ad hoc network. The abstraction allows the messages to be sent along short paths in the ad hoc network. We present distributed algorithms which compute an abstraction of the ad hoc network in O(log ^2 n) time with the help of long-range links, which provides c-competitive routing paths between any two nodes of the ad hoc network for some constant c for the case that the convex hulls of the radio holes do not intersect. We show that the storage that is needed for the abstraction is dependent on the number and the size of the radio holes in the wireless ad hoc network. It is independent of the total number of nodes and that information just has to be known to a few nodes for the routing to work. In addition to convex hulls, we also compute a bounding box abstraction of the radio holes in the ad hoc network.