We present a new approach for competitive geometric routing in wireless ad hoc networks. We design a routing strategy that finds c-competitive paths for a positive constant c: i.e., paths which have a length at most c times the length of a shortest path. It is well-known that this cannot be achieved by online routing strategies which only consider the local neighborhood of a node for their routing decisions [17]. The main difficulty is uncovered regions within the wireless ad hoc network, which we denote as radio holes. Complex shapes of radio holes, for example zig-zag-shapes, make local geometric routing difficult: i.e., forwarded messages in direction to the destination might get stuck in a dead end or could be routed along very long detours. To be able to find c-competitive paths, additional knowledge about the position and shape of radio holes is needed. In order to gather the knowledge efficiently, we make use of a hybrid network approach. This approach assumes that we can not just make use of the ad hoc network but also of some cellular infrastructure, which is used to gather knowledge about the underlying ad hoc network. Communication via the cellular infrastructure incurs costs as cell phone providers are involved. Therefore, we use the cellular infrastructure only to compute routing paths in the ad hoc network. The actual data transmission takes place in the ad hoc network. To find good routing paths we aim at computing an abstraction of the ad hoc network in which radio holes are abstracted by bounding boxes. The advantage of bounding boxes as hole abstraction is that we only have to consider a constant number of nodes per hole. We prove that bounding boxes are a suitable hole abstraction that allows us to find c-competitive paths in the ad hoc network in the case of non-intersecting bounding boxes. In the case of intersecting bounding boxes, we show via simulations that our routing strategy significantly outperforms the so far best online routing strategies for wireless ad hoc networks. Finally, we also present a routing strategy that is c-competitive in the case of pairwise intersecting bounding boxes.

In this paper we present two major results: First, we introduce the first self-stabilizing version of a supervised overlay network (as introduced in [1]) by presenting a self-stabilizing supervised skip ring. Secondly, we show how to use the self-stabilizing supervised skip ring to construct an efficient self-stabilizing publish-subscribe system. That is, in addition to stabilizing the overlay network, every subscriber of a topic will eventually know all of the publications that have been issued so far for that topic. The communication work needed to processes a subscribe or unsubscribe operation is just a constant in a legitimate state, and the communication work of checking whether the system is still in a legitimate state is just a constant on expectation for the supervisor as well as any process in the system.

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.