Construction et maintenance d'une dorsale virtuelle dans les reseaux ad hoc mobiles.

摘要

Mobile ad hoc networks are totally distributed which do not need a fixed infrastructure and terminals are free to move anywhere at anytime. The absence of an infrastructure requires collaboration of all the terminals to forward traffic from a source to a destination. Many routing protocols have been proposed to ensure the multi hop relaying, with either reactive, proactive or hybrid approach. However, the performance of these protocols degrades when mobility is present. In this thesis, a virtual backbone-based routing protocol is proposed and evaluated for mobile ad hoc networks.; A virtual backbone is a subset of selected nodes with each node having at least one neighbour in the backbone. Nodes forming the backbone should be stay connected even when the nodes move. Smaller the size of the backbone, the better the maintenance will be. A new algorithm to build the backbone based on the computation of the minimum connected dominating set (MCDS) is proposed. An ad hoc network is modelled by a graph has disc unit UDG (Unit Graph Disc). Finding MCDS in a graph UDG is a NP-Complete problem. In order to reduce the complexity, we divide the problem in two steps: the first step computes the minimum dominating set (MDS) using a linear programming formulation and the second step determines the spanning tree of the MDS set, then we deduce the MCDS. Simulation results show that the solution given by our algorithm is very close solution to the one given by analysis. Moreover, the size of the backbone is significantly lower compared with other proposed algorithms.; A distributed procedure for maintaining the connectivity of the backbone is also proposed. It is based on a simple exchange of the modified control message hello. A node which changes its position then will apply this procedure to be connected to the dorsal. A local maintenance of the backbone will be realized, only in the zone where the node is moved. Simulation results show the effectiveness and the reliability of this approach. Indeed, more than 90% of the nodes remain connected for a high mobility (average speed 30 m/s). Moreover, this procedure is not very sensitive to the scalability. The distributed nature makes maintenance procedure adapt well to the dynamic of the network structure caused by nodes movement.; In order to verify the improvement achieved by the presence of a backbone for routing protocols in mobile ad hoc networks. We make comparison of three existing protocols with and without a virtual backbone. Simulation results show that an improvement of 20% can be achieved for some protocols with high mobility.; In summary, this dissertation presents new results in many current problems regarding routing in wireless ad hoc networks.