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

Haerri, Jérôme;Bonnet, Christian;Filali, Fethi
MSWIM 2007, 10th ACM/IEEE Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, October 22- 26, 2007, Chania, Greece

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 alters the optimality of these localized structures, as the criteria dynamically varies 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


DOI
Type:
Conférence
City:
Chania
Date:
2007-10-22
Department:
Systèmes de Communication
Eurecom Ref:
2348
Copyright:
© ACM, 2007. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in MSWIM 2007, 10th ACM/IEEE Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, October 22- 26, 2007, Chania, Greece http://dx.doi.org/10.1145/1298275.1298294

PERMALINK : https://www.eurecom.fr/publication/2348