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.
Keywords: Kinetic graphs ; mobility management ; mobility modeling ; mobility predictions ; multipoint relays (MPR) ; optimized link state routing (OLSR) ; broadcasting ; routing ; wireless ad hoc networks ; vehicular networks ; Graphe Cinétique ; gestion de mobilité ; modélisation de mobilité ; prédiction de mobilité ; relais multipoint (MPR) ; OLSR ; diffusion ; routage ; réseaux ad-hoc sans fil ; réseaux véhiculairesThèse École polytechnique fédérale de Lausanne EPFL, n° 3836 (2007)
Section des systèmes de communication
Faculté informatique et communications
Jury: Hannes Hartenstein, Jean-Yves Le Boudec, Mario Gerla
Public defense: 2007-6-22
Record created on 2007-05-02, modified on 2016-08-08