Kinetic graphs: a framework for capturing the dynamics of mobile structures in MANET

In Mobile Ad Hoc Networks (MANET), structures are built in order to improve network resource for broadcast or routing. Inspired by graph theory, most of those structures are built using fixed criteria, such as degree or distance, yet based only on local information. However, mobility is altering the optimality of these localized structures, as the criteria is dynamically varying with time. Since those criteria do not change homogeneously, a periodic maintenance wastes network resource, as it inefficiently acquires new values in an disorganized way. In this paper, we introduce the concept of Kinetic Graphs as a method to capture the dynamics of mobile structures and accordingly develop an efficient maintenance. Unlike the static counterpart, kinetic graphs are assumed to be continuously changing and edges are represented by time-varying weights. Kinetic graphs are a natural extension of static graphs and provide solutions to similar problems, such as convex hulls, spanning trees or connected dominating sets, but for continuously mobile networks. We therefore propose a framework for implementing Kinetic Graphs for topology management in MANET, which consists of four steps: (i) a natural representation of the trajectories, (ii) a common message format for the posting of those trajectories, (iii) a time varying weight for building the kinetic graphs, (iv) an aperiodic neighborhood maintenance. In particular, we propose two time-varying weights which could be used to directly adapt graph theory algorithms to the kinetic aspect, and also illustrate two successful applications to broadcasting and topology control for MANET.