The defense will take place on Tuesday 9th June (morning) in the Heidi Lamarr building (Amphi Chappe), Insa-Lyon, Villeurbanne.

Title

Exact and anytime heuristic search for the Time Dependent Traveling Salesman Problem with Time Windows

Abstract

The Time Dependent (TD) Traveling Salesman Problem (TSP) is a generalization of the TSP which allows one to take traffic conditions into account when planning tours in an urban context: travel times between points to visit depend on departure times instead of being constant. The TD-TSPTW further generalizes this problem by adding Time Window constraints, i.e., constraints on visit times. Existing exact approaches such as Integer Linear Programming and Dynamic Programming usually do not scale well; heuristic approaches scale better but provide no guarantees on solution quality.

In this thesis, we introduce a new exact and anytime solving approach for the TD-TSPTW which aims at quickly providing approximate solutions and gradually improving them until proving optimality. We first show how to reduce the TD-TSPTW to the search for a best path in a state-transition graph. We provide an overview of existing search algorithms, with a focus on exact and anytime extensions of A*, and introduce a new one by hybridizing two of them. We show how to combine these exact and anytime search algorithms with local search – in order to faster find solutions of higher quality – and with bounding and time window constraint propagation – in order to filter the search space. Finally, we provide extensive experimental results to (i) validate our main design choices, (ii) compare our approach to state-of-the-art solving approaches on various TD benchmarks with different degrees of realism and different temporal granularities and (iii) compare TD solving approaches to recent TSPTW solvers on constant benchmarks. These experimental results show us that our approach offers a good compromise between the time needed to find good solutions and the time needed to find optimal solutions and prove their optimality for both TD and constant TSPTW instances.

Jury

• • • Cédric PRALET, Directeur de Recherche, ONERA – Rapporteur
    • Pierre SCHAUS, Professeur des Universités, UC Louvain – Rapporteur
    • Romain BILLOT, Professeur des Universités, IMT Atlantique – Examinateur
    • Christine SOLNON Professeure des Universités, INSA Lyon – Directrice de thèse
    • Jilles S. DIBANGOYE, Maître de Conférences HDR, University of Groningen – Co-directeur de thèse

The defense will take place on Friday 24th May at 10AM in the Heidi Lamarr building, Insa-Lyon, Villeurbanne.

Title

Contributions to Wireless Sensor Networks for Air Quality Monitoring

Abstract

In this talk, I will present a summary of my research, which revolves around the design and evaluation of novel solutions for Wireless Sensor Networks to efficiently monitor physical phenomena. I have addressed several scientific and technical issues by adopting a global methodology combining theoretical solutions and experimental developments. Although our solutions can be easily adapted to different applications, the focus was on air quality monitoring, a major societal challenge where new low-cost sensing technologies offer a significant advantage over traditional solutions.

This talk focuses on our main contributions in this area of low-cost sensor networks for environmental monitoring. It is structured around three axes: i) static sensor networks for air quality monitoring in cities and on industrial sites; ii) participatory sensing of air quality and Urban Heat Islands; and iii) UAV fleets for monitoring highly dynamic phenomena. The common thread running through all our solutions is that they take into account both the physical domain knowledge and the characteristics of low-cost sensors such as the limited and heterogeneous measurement accuracy. I will conclude this talk by discussing some personal feedback and setting out some future perspectives.

Jury

• • Aline CARNEIRO VIANA, Directrice de recherche, INRIA, Reviewer
  • Andrzej DUDA, Professeur, Grenoble INP – Ensimag, Reviewer
  • Nathalie MITTON, Directrice de recherche, INRIA, Reviewer
  • André-luc BEYLOT, Professeur, Toulouse INP – ENSEEIHT, Examiner
  • Abdelmadjid BOUABDALLAH, Professeur, Université de Technologie de Compiègne, Examiner
  • Isabelle GUERIN-LASSOUS, Professeur, Université de Lyon 1, Examiner
  • Hervé RIVANO, Professeur, INSA-Lyon, Examiner (« Garant »)
  • Mouloud KOUDIL, Professeur, ESI-Alger, Guest Examiner

The defense will take place on Tuesday 22th May at 10 AM in the East amphitheater of the humanities building, Insa-Lyon, Villeurbanne.

Title

Programming language abstractions for the Internet of Things era

Abstract

Jury

• • • Mme Stéphanie CHOLLET, Maître de conférences HDR – ESISAR Grenoble INP – Rapporteure
    • M. Stéphane DUCASSE, Directeur de Recherche – INRIA – Rapporteur
    • M. Philippe ROOSE, Professeur des Universités – Université de Pau et des Pays de l’Adour – Examinateur
    • M. Yannick LOISEAU, Maître de Conférences – Université Clermont Auvergne – Examinateur
    • M. Frédéric LE MOUËL, Professeur des universités – INSA Lyon – Directeur de thèse
    • M. Julien PONGE, Docteur – Red Hat – co-encadrant de thèse

The defense will take place on Tuesday 19th December at 2 PM in the Heidi Lamarr building (Amphi Chappe), Insa-Lyon, Villeurbanne.

Title

Navigation Among Movable Obstacles (NAMO) Extended to Social and Multi-Robot Constraints

Abstract

As robots become ever more commonplace in human environments, taking care of ever more tasks such as cleaning, security or food service, their current limitations only become more apparent. One such limitation is of their navigation capability in the presence of obstacles: they always avoid them, and freeze in place when avoidance is impossible.

This is what brought about the creation of Navigation Among Movable Obstacles (NAMO) algorithms, expected to allow robots to manipulate obstacles as to facilitate their own movement. However, these algorithms were designed under the hypothesis of a single robot per environment, biasing NAMO algorithms into only optimizing the single robot’s displacement cost – without any consideration for humans or other robots. While it is desirable to endow robots with the human capability of moving obstacles, they must however do so while respecting social norms and rules of humans.

We have thus extended the NAMO problem as to take into account these new social and multi-robots aspects. By relying on the concept of affordance spaces, we have developed a social occupation cost model allowing the evaluation of the impact of moved objects on the environment’s navigability. We implemented (and improved) reference NAMO algorithms, in our open source simulation tool, and modified them so that they may plan compromises between robot displacement cost and social occupation cost of moved obstacles – resulting in improved navigability. We also developed an implicit coordination strategy allowing the concurrent execution of these same algorithms by multiple robots as is, without any explicit communication requirements, while preserving the no-collision guarantee; verifying the relevance of our social occupation cost model in the actual presence of other robots. As such, this work constitutes the first steps towards a Social and Multi-Robot NAMO.

Jury

• • Philippe Mathieu , Professeur des Universités, Université de Lille, CRISTAL, Rapporteur
  • Fabien Michel, Maître de Conférences HDR, Université Montpellier 2, LIRMM, Rapporteur
  • Julie Dugdale, Professeur des Universités, Université de Grenoble, LIG, Examinatrice
  • Rachid Alami, Directeur de Recherche CNRS émérite, LAAS, Toulouse, Examinateur
  • Olivier Simonin, Professeur des Universités, INSA-Lyon, CITI, Directeur de thèse
  • Jacques Saraydaryan, Enseignant Chercheur, CPE Lyon, CITI, Co-encadrant

The defense will take place on Friday 29th December at 2 PM in the Heidi Lamarr building (Amphi Chappe), Insa-Lyon, Villeurbanne.

Title

Human and Network Mobility Management using Mobile Phone Data

Abstract

Over the past decade, the increasing use of smartphones has led to a significant rise in the volume of data exchanged through mobile networks of telecommunications operators. Each new generation of mobile network generates more data than its predecessor. By 2027, it is estimated that 289 EB of data will be exchanged per month, with 62% originating from the 5G mobile network. This vast availability of data has opened up new research perspectives, particularly in the study of mobility. Mobile data enables studies on larger populations and extended geographical areas.

In this thesis, we demonstrate that the events described in mobile data can also be found in other data sources. Through comparisons between mobile data and sensors detecting human presence, we observe a reasonable correlation. However, certain events, such as synchronization of peak presence or end-of-day activity, exhibit less similarity. We also utilize mobile data to examine the impact of the COVID-19 lockdowns imposed by the French government on land usage in Paris. Our findings indicate that the first lockdown had a profound impact on mobility patterns and land utilization, while the second and third lockdowns had a lesser impact. Lastly, we leverage this data for the reconfiguration of the mobile network in managing user micro-mobility, known as handover. The eNodeBs, which constitute the access network, can have different profiles and categories. By distinguishing between mobile and stationary users, we can optimize resource allocation through network reconfiguration. Dynamic network reconfiguration, employing various eNodeB profiles, also enables resource savings for mobile users.

Jury

• • Marco FIORE, Directeur de Recherche, IMDEA Networks, Rapporteur
  • Vania CONAN, Habilité à Diriger des Recherches, Thales, Rapporteur
  • Aline CARNEIRO VIANA, Directeur de Recherche, INRIA, Examinatrice
  • Sahar HOTEIT, Maître de Conférences, Université Paris Saclay, Examinatrice
  • Stefano SECCI, Professeur des Universités, CNAM, Examinateur
  • Hervé RIVANO, Professeur des universités, INSA-Lyon, Directeur de thèse
  • Razvan STANICA, Maître de conférences HDR, INSA-Lyon, Co-directeur de thèse

The defense will take place on Friday 16th December at 10 AM in the est amphi of the Humanities building, Insa-Lyon, Villeurbanne.

Title

Resilient IoT-based Monitoring System for the Nigerian Oil and Gas Industry

Abstract

Pipeline failures in crude oil transportation occur due to ageing infrastructure, third-party interferences, equipment defects and naturally occurring failures. Consequently, hydrocarbons are released into the environment resulting in environmental pollution, ecological degradation, and unprecedented loss of lives and revenue. Hence, multiple leakage detection and monitoring systems (LDMS) are employed to mitigate such failures. More recently, these LDMS include Wireless Sensor Networks (WSN) and Internet of Things (IoT)-based systems. While they are proven more efficient than other LDMS, many challenges exist in their adoption for pipeline monitoring. These include fault tolerance, energy consumption, accuracy in leakage detection and localisation, and high false alarms, to cite a few.

Therefore, our work seeks to address some of these challenges in implementing IoT-based systems for crude oil pipelines in a resilient end-to-end manner. Specifically, we consider the aspect of accurate leakage detection and localisation by introducing a unique node placement strategy based on fluid propagation for sensitive and multi-sized leakage detection. We also propose a new distributed leakage detection technique (HyDiLLEch) in the WSN layer. It is based on a fusion of existing leakage detection techniques such as the negative pressure wave method, gradient-based method, and pressure point analysis. With HyDiLLEch, we efficiently eliminate single points of failure.

Furthermore, we implement fault-tolerant data and service management in the fog layer utilising the Nigerian National Petroleum Corporation (NNPC) pipeline network as a use case. The problem is modelled as a regionalised data-driven game against nature on the NNPC pipelines. Our proposed regionalised solution (R-MDP) using reinforcement learning optimises accuracy and fault tolerance while minimising energy consumption.

Overall, our system guarantees resiliency to failures and efficiency in terms of detection and localisation accuracy and energy consumption.

Jury

• Stolf, Patricia, Professeur des Universités, Université de Toulouse, Rapporteure
• Guidec, Frédéric, Professeur des Universités, Université Bretagne Sud, Rapporteur
• Menaud, Jean-Marc, Professeur des Universités, IMT-Atlantique, Examinateur
• Caron, Eddy, Maître de Conférences, ENS Lyon, Examinateur
• Takruri-Rizk, Haifa, Professeur des Universités, University of Salford, Examinatrice
• Silva, Bhagya Nathali, Senior Lecturer, University of SriJayawardenepura, Examinatrice
• Le Mouël, Frédéric, Professeur des Universités, INSA Lyon, Directeur de thèse
• Stouls, Nicolas, Maître de Conférences, INSA Lyon, Co-Directeur de thèse
• Yusuf, Kabir, Docteur en gestion des ressources environnementales, PTDF/SAPZ, Invité

The defense will take place on Friday 16th December at 10 AM in the west amphi of the Humanities building, Insa-Lyon, Villeurbanne.

Title

Contributions to the development of passive RFID tag-to-tag communications for the Internet of Things

Abstract

With the emergence of cognitive sensor networks, and in particular the IoT (Internet of Things), passive RFID (Radio Frequency Identification) UHF (Ultra High Frequency) technology is evolving with new functionalities. New types of applications going beyond the classics such as logistics, security and traceability are being developed. Still benefiting from unitary identification, new types of tags, called augmented tags, are appearing integrating new capacities such as environmental sensitivity, cognitive behaviour, data processing, communication between tags, etc. In this context, the objective of this thesis is to propose strategies and methods to optimize communications between tags, called tag-to-tag “tag-to-tag” (T2T) communications. This new type of radio link, between directly communicating tags, relies on the presence of an external radio frequency (RF) source and is based on the principle of retro-modulation. In particular, the scenarios analyzed are projected within the framework of the Spie ICS – INSA Lyon chair, which focuses on the IoT.

This thesis more specifically targets the application domain of UHF RFID for which the concept of T2T communications has been proposed and demonstrated since 2011, but with relatively little work done so far. In a T2T RFID system, two RFID tags (passive or semi- passive) communicate with each other directly without going through the reader. One of the tags plays the role of “reader tag”: in the presence of an RF source (for example an RFID reader) in its vicinity, it emits binary information by retro-modulation (or backscatter by switching charges), by switching the load seen by its antenna on two distinct impedances, thus reflecting two distinct power levels (modulation here considered in amplitude). The other tag plays the role of “receiver tag”: it receives the information transmitted and demodulates it.

In the traditional case of UHF RFID, the reader emits, in accordance with the standard, a modulated signal with a high modulation depth in order to facilitate the detection of the message transmitted by the tag. The tag responds by retro modulation and the signal it returns is then a signal where the two levels of information (in the case of amplitude modulation) are not very distinct and noisy. However, the player’s demodulator is very efficient, based on quadrature synchronous demodulation, it has very good sensitivity. In the case of T2T communication, a fundamental difference is that the detection is here performed by the second tag which is in the vicinity of the reader tag. Consequently, on the one hand, the performance of the receiver (that of a “simple” RFID tag) is much more limited, while the modulated signal is not necessarily at high modulation depth. And on the other hand, the two tags interact. This inter-tag electromagnetic coupling impacts in particular radiation patterns and impedances, and moreover, it depends on the mutual positions of the two tags, more precisely on their antennas (distance separating them, relative orientation, etc.), which leads to high variability the characteristics of the T2T system (and therefore its performance). In addition, there is the impact of the relative position of the external RF source with the pair of tags, which significantly modifies the characteristics of the retro-modulated signals.

The main challenge of the thesis is to determine a framework that can take into account all the factors (signal, component, circuit and system) impacting T2T communication with the aim of evaluating performance, particularly in terms of communication rate. binary error, a metric conventionally used in the field of telecommunications.

Keywords: Backscattering, passive tags, tag to tag communications, UHF RFID

Jury

• Bergeret Emmanuel Professor Université Clermont Auvergne Reviewer
• Breard Arnaud Professor Ecole Centrale de Lyon Examiner
• Lepage Anne-Claire Associate Professor Telecom Paris Examiner
• Lienard Martine Professor Université de Lille Examiner
• Vena Arnaud Associate Professor HDR Université de Montpellier Reviewer
• Villemaud Guillaume Associate Professor HDR INSA-Lyon Thesis director
• Hutu Florin-Doru Associate Professor INSA-Lyon Co-director
• Duroc Yvan Professor Université Claude Bernard Lyon 1 Co-director