The number of electronic devices, equipped with a wireless interface has exploded over the last decades. Unfortunately, their usage is often restricted to the connection to a wired infrastructure, even for local communications. That is quite surprising as the research area of infrastructureless, or ad hoc, networks has flourished for years. The literature on ad hoc networks is very rich, but their usage almost inexistent. Potential users have plenty of solutions at hand, but do not exploit them. Even if ad hoc networks allow us to get rid of the infrastructure, they still require an implicit agreement on the solution to use. Nevertheless, it is very dicult to pick in the rich panel of protocols the best one, that would fit any ad hoc user in any ad hoc network. As an example, it has been demonstrated, for the routing, that each protocol has definite advantages and disadvantages, in every different scenario, and is well suited for certain situations. Yet, a salient feature of ad hoc networks is precisely that the panel of situations is very large. The ad hoc network conditions are influenced by the number of ad hoc users, their relative positions, their capabilities, their mobility pattern, the applications they use, the traffic load and type, and so forth. Moreover, the users may themselves be heterogeneous, with different hardware and software capabilities, mobile behaviour and communication needs. Hence, there is a particular need in ad hoc networking for flexible techniques. We contribute to this problem by studying the feasibility of overlay routing and giving some hints in that direction. We explain how the overlay members can avoid the expensive process of building an overlay topology, before using their customised routing application. The rationale exploits the broadcast nature of ad hoc networks, and is qualified as a Reactive Overlay Approach. We also detail an elementary reactive overlay routing application and test it, by simulations, in a variety of conditions, including the network and overlay densities. This performance study shows the feasibility and the efficiency of overlay routing applications developed according to the Reactive Overlay Approach. It also evidences the impact of using an appropriate value for the neighbourhood range, defined as the maximum number of hops between two overlay neighbours. Hence, we detail the critical neighbourhood range (CNR) problem, which, in short, consists in determining the minimum neighbourhood range value that generates a connected overlay. We solve it in the asymptotic case, i.e. when the number of nodes in the underlay or the size of the field tends to infinity. The mathematical results are interesting in the sense that they can be useful for a better understanding of the interaction between various typical characteristics of a connected overlay topology on an ad hoc network. However, the theoretical, asymptotic, CNR is not adequate in practice. We thus also explore heuristics for estimating the CNR. We present a simple protocol which estimates an appropriate neighbourhood range for overlay routing applications. For the purpose of its evaluation, we define general performance criteria based on overlay flooding. Namely, these are the delivery percentage, bandwidth consumption and time duration of flooding on the overlay. The main drawback of the Reactive Overlay Approach is the amount of bandwidth consumed during the flooding of overlay route requests. Hence, we also consider the Proactive Overlay Approach, which consists in building the overlay topology before the emission of any overlay broadcast message, and maintaining it. We compare the quality of various overlay topologies in the static case. We finally describe and evaluate the Overlay Topology Control (OTC) protocol, that maintains, in a mobile context, the overlay topology as close as possible to the overlay topology evaluated as the best. The main objection that would arise against overlay routing on ad hoc networks is that the ad hoc nodes do generally own poor resources and that overlay routing consumes them even more than native routing. The feasibility study we conducted with the reactive approach and the evaluation of OTC, designed in the context of the proactive overlay approach, confirm that the consumption of resources must be handled carefully. Nevertheless, they show that this problem is not insurmountable.

No description available.