Research Area:  Mobile Ad Hoc Networks

Abstract:

   In this thesis, we are interested in research questions that pertain respectively to temporal graphs, to mobility, as well as to the interaction between the two. The problem we consider on temporal graphs is motivated by a 20-year old open question, namely what the analog definition of a spanning tree in temporal graphs is. Our main result in this topic is to show that, even though sparse spanners do not exist in general temporal graphs, sparse spanners exist in significant particular cases. On the other end of the field of dynamic networks, we study the design of physical movements, which led us to consider a discrete model of acceleration called racetrack and to revisit the traveling salesperson problem (TSP). The questions of movement design on one hand, and temporal graphs on the other, end up being in strong interaction when considering the execution of distributed algorithms in a MANET scenario. In this context, the third contribution consists of a software package proposing mobility models that induce temporal graph properties in the resulting communication network.

Name of the Researcher:  Jason Schoeters

Name of the Supervisor(s):  Arnaud Casteigts

Year of Completion:  2021

University:  University Of Bordeaux

Thesis Link:   Home Page Url