Competitive Routing in Hybrid Communication Networks

Daniel Jung, Christina Kolb*, Christian Scheideler, Jannik Sundermeier

*Corresponding author for this work

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 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 O(log2n) 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. We also show that the storage needed for the abstraction just depends on the number and size of the radio holes in the wireless ad hoc network and is independent on the total number of nodes, and this information just has to be known to a few nodes for the routing to work.

Original languageEnglish
Title of host publicationAlgorithms for Sensor Systems - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018, Revised Selected Papers
EditorsDanny Hughes, Seth Gilbert, Bhaskar Krishnamachari
PublisherSpringer-Verlag
Pages15-31
Number of pages17
Volume11410
ISBN (Print)9783030140939
DOIs
Publication statusPublished - 15 Feb 2019
Event14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018 - Helsinki, Finland
Duration: 23 Aug 201824 Aug 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11410 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018
Country/TerritoryFinland
CityHelsinki
Period23/08/1824/08/18

Keywords / Materials (for Non-textual outputs)

  • ad hoc networks
  • c-competitiveness
  • convex hulls
  • greedy routing

Fingerprint

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

Cite this