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.
In @cite_19 , also greedy routing with a modification of face routing is used. To overcome potential bottlenecks which avoid a guaranteed delivery, a restricted flooding procedure is used. In a slightly different setting, namely nodes on the grid, a packet is routed along multiple paths and is hence comparable to a restricted flooding procedure @cite_3 . In their model, alive node and crashed nodes exist on the grid. The crashed nodes behave like obstacles on the grid which have to be avoided by routing paths.
@cite_19 @cite_3
2165983440 2170526908
It was recently reported that all known face and combined greedy-face routing variants cannot guarantee message delivery in arbitrary undirected planar graphs. The purpose of this article is to clarify that this is not the truth in general. We show that specifically in relative neighborhood and Gabriel graphs recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. A prominent approach is to visit a sequence of faces which are intersected by the line connecting the source and destination node. Whenever encountering an edge which is intersecting with this line, the critical part is to decide if face traversal has to change to the next adjacent one or not. Failures may occur from incorporating face routing procedures that force to change the traversed face at each intersection. Recently observed routing failures which were produced by the GPSR protocol in arbitrary planar graphs result from incorporating such a face routing variant. They cannot be constructed by the well known GFG algorithm which does not force changing the face anytime. Beside methods which visit the faces intersected by the source destination line, we discuss face routing variants which simply restart face routing whenever the next face has to be explored. We give the first complete and formal proofs that several proposed face routing, and combined greedyface routing schemes do guarantee delivery in specific graph classes or even any arbitrary planar graphs. We also discuss the reasons why other methods may fail to deliver a message or even end up in a loop. Flooding-based approaches are incorporated in reactive routing protocols as the fundamental strategy for route discovery. They overtly affect traffic as the frequency of route discovery increases along with the mobility of users in a mobile ad hoc network (MANET). This paper presents a scheme for reducing overall traffic and end-to-end delay in highly MANET networks. Firstly a new routing algorithm is proposed to reduce the frequency of flood requests by elongating the link duration of the selected paths. In order to increase the path duration, non-disjoint paths are also considered. This concept is a novel approach in route discovery as previous reactive routing protocols seek only disjoint paths. Secondly another novel approach is presented to estimate the link expiration time without the need for global positioning system (GPS) devices. To prevent broadcast storms that may be intrigued during the path discovery operation, another scheme is also introduced. The basic concept behind the proposed scheme is to broadcast only specific and well-defined packets, referred to as "best packets" in the paper. The new protocol is simulated with regard to traffic overhead. Although our main aim in this paper is to reduce the net control traffic in a MANET network, there are other benefits arising from the proposed schemes, namely the increase in link duration, reduction in the end-to-end communication delay, less disruption in data flow, and fewer path setups.