Brief Announcement: Competitive Routing in Hybrid Communication Networks

Daniel Jung, Christina Kolb, Christian Scheideler, Jannik Sundermeier

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Routing is a challenging problem for wireless ad hoc networks, especially when the nodes are mobile and spread so widely that in most cases multiple hops are needed to route a message from one node to another. In fact, it is known that any online routing protocol has a poor performance in the worst case, in a sense that there is a distribution of nodes resulting in bad routing paths for that protocol, even if the nodes know their geographic positions and the geographic position of the destination of a message is known. The reason for that is that radio holes in the ad hoc network may require messages to take long detours in order to get to a destination, which are hard to find in an online fashion. In this short paper, we assume that the wireless ad hoc network can make limited use of long-range links provided by a global communication infrastructure like a cellular infrastructure or a satellite in order to compute an abstraction of the wireless ad hoc network that allows the messages to be sent along near-shortest paths in the ad hoc network. We present distributed algorithms that compute an abstraction of the ad hoc network in $\mathcalO łeft(łog ^2 n\right)$ time using long-range links, which results in c -competitive routing paths between any two nodes of the ad hoc network for some constant c if the convex hulls of the radio holes do not intersect.
Original languageEnglish
Title of host publicationSPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
EditorsChristian Scheideler, Jeremy T. Fineman
PublisherACM
Pages231-233
Number of pages3
ISBN (Print)9781450357999
DOIs
Publication statusPublished - 11 Jul 2018
EventSPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures - Vienna, Austria
Duration: 16 Jul 201818 Jul 2018
Conference number: 30
https://spaa.acm.org/2018/index.html

Conference

ConferenceSPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures
Country/TerritoryAustria
CityVienna
Period16/07/1818/07/18
Internet address

Fingerprint

Dive into the research topics of 'Brief Announcement: Competitive Routing in Hybrid Communication Networks'. Together they form a unique fingerprint.

Cite this