In this work, we present a new approach for competitive geometric routing in wireless ad hoc networks. In general, it is well-known that any online routing strategy performs very poor in the worst case. The main difficulty are 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 even more difficult, i.e., forwarded messages in direction to the destination might get stuck in a dead end or are routed along 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 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. In order 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 @math -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. Finally, we also present a routing strategy that is @math -competitive in case of pairwise intersecting bounding boxes.
@cite_13: Many algorithms for routing in sensor networks exploit greedy forwarding strategies to get packets to their destinations. We study a fundamental difficulty such strategies face: the "local minimum phenomena" that can cause packets to get stuck. We give a definition of stuck nodes where packets may get stuck in greedy multi-hop forwarding, and develop a local rule, the TENT rule, for each node in the network to test whether a packet can get stuck at that node. To help the packets get out of stuck nodes, we describe a distributed algorithm, BOUNDHOLE, to build routes around holes, which are connected regions of the network with boundaries consisting of all the stuck nodes. We show that these hole-surrounding routes can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest.
@cite_7: Several anomalies can occur in wireless sensor networks that impair their desired functionalities i.e., sensing and communication. Different kinds of holes can form in such networks creating geographically correlated problem areas such as coverage holes, routing holes, jamming holes, sink black holes and worm holes, etc. We detail in this paper different types of holes, discuss their characteristics and study their effects on successful working of a sensor network. We present state-of-the-art in research for addressing the holes related problems in wireless sensor networks and discuss the relative strengths and short-comings of the proposed solutions for combating different kinds of holes. We conclude by highlighting future research directions.
In addition to the just mentioned local routing, there are also routing strategies that use a portion of global knowledge about the network. BoundHole @cite_13 , for instance, uses a preprocessing phase at each node which is located at the boundary of a hole. These hole nodes send out a packet which is routed using the right hand rule around the perimeter of the hole until it reaches the source of the message. On the way, the packet collects information about the boundary of the hole. With knowledge about the boundary, the authors are able to find better paths than strategies which only use local information. For a survey on all mentioned strategies, we refer the reader to @cite_7 .