  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 $\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.
