Abstract :
[en] The number of electronic devices, equipped with a wireless interface hasexploded 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, theystill require an implicit agreement on the solution to use. Nevertheless, it isvery 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 beendemonstrated, for the routing, that each protocol has definite advantagesand disadvantages, in every different scenario, and is well suited for certainsituations.Yet, a salient feature of ad hoc networks is precisely that the panel ofsituations is very large. The ad hoc network conditions are influenced bythe 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 ofbuilding an overlay topology, before using their customised routing application.The rationale exploits the broadcast nature of ad hoc networks, and isqualified 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 simpleprotocol which estimates an appropriate neighbourhood range for overlayrouting applications. For the purpose of its evaluation, we define generalperformance criteria based on overlay flooding. Namely, these are the deliverypercentage, bandwidth consumption and time duration of flooding onthe overlay.The main drawback of the Reactive Overlay Approach is the amount ofbandwidth consumed during the flooding of overlay route requests. Hence,we also consider the Proactive Overlay Approach, which consists in buildingthe 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 hocnetworks is that the ad hoc nodes do generally own poor resources and thatoverlay routing consumes them even more than native routing.The feasibility study we conducted with the reactive approach and theevaluation 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.
