Competitive routing in hybrid communication networks and message efficient SetCover in Ad Hoc networks

Competitive routing is a challenging problem for wireless ad hoc networks, for example, when the nodes are mobile, spread so widely, and in the most cases multiple hops and long paths are needed to route a message from a source node to a target. It is known that any online routing algorithm has a poor performance in the worst case, i.e., there is a distribution of nodes resulting in bad routing paths for that algorithm. This happens even if the nodes know their geographic positions and the geographic position of the destination of a message. This is because radio holes in the ad hoc network require messages to route via long detours in order to get to a destination. This is hard to find in an online fashion. In this thesis, we assume that a wireless ad hoc network makes limited use of long-range links. The long-range links are provided by a global communication infrastructure which can be a cellular infrastructure or a satellite. The global communication infrastructure helps to compute an abstraction of the wireless ad hoc network. The abstraction allows the messages to be sent along short paths in the ad hoc network. We present distributed algorithms which compute an abstraction of the ad hoc network in O(log ^2 n) time with the help of long-range links, which provides c-competitive routing paths between any two nodes of the ad hoc network for some constant c for the case that the convex hulls of the radio holes do not intersect. We show that the storage that is needed for the abstraction is dependent on the number and the size of the radio holes in the wireless ad hoc network. It is independent of the total number of nodes and that information just has to be known to a few nodes for the routing to work. In addition to convex hulls, we also compute a bounding box abstraction of the radio holes in the ad hoc network.