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.
The approach we extend in this work makes use of global information as well @cite_2 . The global information is gathered via a Hybrid Communication Network. In a Hybrid Communication Network, nodes can communicate with other nodes in their ad hoc range for free. In addition, they can use long-range links to communicate with any other node of the network. These long-range links, the Cellular Infrastructure, are costly. The solution they propose is to compute an Overlay Network in which holes are represented by their convex hulls. It is assumed that the convex hulls of the holes do not intersect. The storage requirements for some nodes are asymptotically in the size of the sum of all holes. In this work, we aim to reduce the storage requirements for these nodes and investigate also the challenging question of @math -competitive routing through intersections of hole abstractions.
@cite_2
2102457283
How much information can one send through a random ad hoc network of n nodes, if overlaid with a cellular architecture of m base stations? This network model is commonly referred to as hybrid wireless networks and our paper analyzes the above question by characterizing its throughput capacity. Although several research efforts related to throughput capacity exist in the area of hybrid wireless networks, most of these solutions under-explore the capacity analysis. Their results particularly indicate that one can realize only a less than log or no gain on capacity, as compared to pure ad hoc networks, when ?? scales slower than some threshold. This unsatisfying capacity gain is due to the fact that the base stations were not properly exploited while formulating the capacity analysis. Moreover, these research efforts also assume an one-hop wireless uplink between a node and its associated base station. Nevertheless, with those power-constrained wireless nodes, this assumption clearly indicates an unrealistic scenario. In this paper, we establish the bounds on capacity and delay by resolving the issues in existing efforts and at the heart of our analysis lies a simple routing policy known as same cell routing policy. Our findings particularly stipulate that whether m = O(n over log n) or Ω(n over log n), each node can realize a throughput that scales, sublinearly or linearly, with m. This is in fact a significant result as opposed to previous efforts which claims that if m grows slower than some threshold, the benefit of augmenting those base stations to the original ad hoc network is insignificant. Our analysis also shows that for a maximum per node throughput Λ(n,m), the average end-to-end delay in a hybrid network can be bounded by Θ(Λ(n,m)n over m), which has an inverse relationship to m.