A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks
share
In this work, we present a new approach for competitive routing in wireless ad hoc networks. With respect to the length of routing paths, it is well-known that any online routing strategy performs very poor in the worst case. The main difficulty are sparse regions of 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 even more difficult, i.e., forwarded messages in direction to the destination might stuck at a dead end or are routed on very long detours, when there is no knowledge about the ad hoc network. To obtain knowledge about the position and shape of radio holes, we consider the Hybrid Communication Network. This network consists of the ad hoc network itself and a 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 only takes place in the ad hoc network. More precisely, in this work, we consider bounding boxes as hole abstractions. 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 case of non-intersecting bounding boxes. In 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.
READ FULL TEXT