A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks

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.