---
_id: '4563'
abstract:
- lang: eng
  text: "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.\r\n\r\nIn
    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 $\\mathcal{O}\\left(\\log ^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. 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.\r\n"
author:
- first_name: Daniel
  full_name: Jung, Daniel
  id: '37827'
  last_name: Jung
- first_name: Christina
  full_name: Kolb, Christina
  id: '43647'
  last_name: Kolb
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Jannik
  full_name: Sundermeier, Jannik
  id: '38705'
  last_name: Sundermeier
citation:
  ama: 'Jung D, Kolb C, Scheideler C, Sundermeier J. Competitive Routing in Hybrid
    Communication Networks. In: <i>Proceedings of the 14th International Symposium
    on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) </i>. Springer;
    2018.'
  apa: 'Jung, D., Kolb, C., Scheideler, C., &#38; Sundermeier, J. (2018). Competitive
    Routing in Hybrid Communication Networks. In <i>Proceedings of the 14th International
    Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) </i>.
    Helsinki: Springer.'
  bibtex: '@inproceedings{Jung_Kolb_Scheideler_Sundermeier_2018, title={Competitive
    Routing in Hybrid Communication Networks}, booktitle={Proceedings of the 14th
    International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)
    }, publisher={Springer}, author={Jung, Daniel and Kolb, Christina and Scheideler,
    Christian and Sundermeier, Jannik}, year={2018} }'
  chicago: Jung, Daniel, Christina Kolb, Christian Scheideler, and Jannik Sundermeier.
    “Competitive Routing in Hybrid Communication Networks.” In <i>Proceedings of the
    14th International Symposium on Algorithms and Experiments for Wireless Networks
    (ALGOSENSORS) </i>. Springer, 2018.
  ieee: D. Jung, C. Kolb, C. Scheideler, and J. Sundermeier, “Competitive Routing
    in Hybrid Communication Networks,” in <i>Proceedings of the 14th International
    Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) </i>,
    Helsinki, 2018.
  mla: Jung, Daniel, et al. “Competitive Routing in Hybrid Communication Networks.”
    <i>Proceedings of the 14th International Symposium on Algorithms and Experiments
    for Wireless Networks (ALGOSENSORS) </i>, Springer, 2018.
  short: 'D. Jung, C. Kolb, C. Scheideler, J. Sundermeier, in: Proceedings of the
    14th International Symposium on Algorithms and Experiments for Wireless Networks
    (ALGOSENSORS) , Springer, 2018.'
conference:
  end_date: 2018-08-24
  location: Helsinki
  name: '14th International Symposium on Algorithms and Experiments for Wireless Networks
    (ALGOSENSORS) '
  start_date: 2018-08-23
date_created: 2018-10-02T07:06:05Z
date_updated: 2022-01-06T07:01:11Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2019-01-11T10:32:38Z
  date_updated: 2019-01-11T10:32:38Z
  file_id: '6621'
  file_name: 23hybrid.pdf
  file_size: 349034
  relation: main_file
  success: 1
file_date_updated: 2019-01-11T10:32:38Z
has_accepted_license: '1'
keyword:
- greedy routing
- ad hoc networks
- convex hulls
- c-competitiveness
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: 'Proceedings of the 14th International Symposium on Algorithms and Experiments
  for Wireless Networks (ALGOSENSORS) '
publisher: Springer
status: public
title: Competitive Routing in Hybrid Communication Networks
type: conference
user_id: '38705'
year: '2018'
...