TY - GEN
T1 - Competitive Routing in Hybrid Communication Networks
AU - Jung, Daniel
AU - Kolb, Christina
AU - Scheideler, Christian
AU - Sundermeier, Jannik
N1 - Funding Information:
This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Center ‘On-The-Fly Computing’ (SFB 901).
Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019/2/15
Y1 - 2019/2/15
N2 - 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.
AB - 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.
KW - ad hoc networks
KW - c-competitiveness
KW - convex hulls
KW - greedy routing
U2 - 10.1007/978-3-030-14094-6_2
DO - 10.1007/978-3-030-14094-6_2
M3 - Conference contribution
AN - SCOPUS:85063439405
SN - 9783030140939
VL - 11410
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 15
EP - 31
BT - Algorithms for Sensor Systems - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018, Revised Selected Papers
A2 - Hughes, Danny
A2 - Gilbert, Seth
A2 - Krishnamachari, Bhaskar
PB - Springer
T2 - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018
Y2 - 23 August 2018 through 24 August 2018
ER -