Modeling and predicting mobility in wireless ad hoc networks

Wireless Ad Hoc Networks are a particular paradigm where wireless devices communicate in a decentralized fashion, without any centralized infrastructure or decision. In order to avoid a situation where nodes chaotically try to communicate, distributed and localized structures (graphs, trees, etc.) need to be built. Mobility brings challenging issues to the maintenance and to the optimality of such structures. In conventional approaches, structures are adapted to the current topology by each node periodically sending beacon messages, which is a significant waste of network resources. If each node can obtain some a priori knowledge of future topology configurations, it could decide to send maintenance messages only when a change in the topology effectively requires updating the structure. In this Doctoral Thesis, we investigate this approach and define the Kinetic Graphs, a novel paradigm regrouping mobility predictions for a kinetic mobility management, and localized and distributed graph protocols to insure a high scalability. The Kinetic Graph framework is able to naturally capture the dynamics of mobile structures, and is composed of four steps: (i) a representation of the trajectories, (ii) a common message format for the posting of those trajectories, (iii) a time varying weight for building the kinetic structures, (iv) an aperiodic neighborhood maintenance. By following this framework, we show that any structure-based ad-hoc protocol may benefit from the kinetic approach. A significant challenge of Kinetic Graphs comes from prediction errors. In order to analyze them, we illustrate the relationship between the prediction model and the mobility model. We decompose the prediction errors into three metrics: the adequacy between the prediction and the mobility models, the predicability of the mobility model, and the mobility model's realism. Following the framework, we define a kinetic model for the modeling of the trajectories and then analyze the extents of the effects of each error metric and develop solutions in order to reduce them. We finally adapt the Multipoint Relaying (MPR) protocol, used by the Optimized Link State Routing protocol (OLSR), and show the significant improvements that may be obtained by using the Kinetic Graph Framework, even on the very challenging vehicular networks.