Le prochain séminaire du D3 aura lieu le mardi 4 mai à 11h sur Teams.
Atef Jaballah post-doctorant dans l’équipe Optimist, fera une présentation intitulée « Modélisation et optimisation de planification de réseaux RFID à grande échelle ».
Résumé :
La croissance énorme des sociétés industrielles nécessite le déploiement des réseaux RFID à grande échelle. Ce qui nécessite l’installation d’un grand nombre de composants RFID (lecteurs, étiquettes, middleware et autres). En conséquence, le coût et la complexité des réseaux RFID augmentent en raison du grand nombre de lecteurs RFID à installer. Ma thèse s’est intéressée à des problèmes liés au déploiement optimisé des réseaux RFID. En particulier, nous nous sommes focalisés sur les trois problèmes suivants : (1) le problème de la planification d’un réseau RFID (RFID Network Planning — RNP) , (2) le problème de l’arrangement des lecteurs RFID tout en maximisant la couverture et minimisant les collisions, et (3) le problème du profilage de la taille des étiquettes dans les systèmes RFID.
Le problème RNP a été prouvé NP-difficile par analogie avec le problème du positionnement d’antennes dans les réseaux cellulaires. C’est un problème d’optimisation multi-objectif avec un espace de solutions très large et bruité, pour lequel les approches méta-heuristiques conviennent le mieux. Nous proposons une nouvelle variante de l’algorithme de recherche coucou (Cuckoo Search – CS), dénommé auto-adaptative CS algorithme (Self Adaptive Cuckoo Search-SACS) où les paramètres de contrôle de l’algorithme CS sont adaptés en temps réel, selon l’avancement du processus d’optimisation pour résoudre ce problème. Ensuite, nous intéressons au problème d’ordonnancement des lecteurs RFID afin de réduire les chevauchements des régions couvertes par les lecteurs et minimiser les collions. Ce problème est connu sous le nom de problème RCCAA (Reader Coverage Collision Avoidance Arrangement). Pour résoudre ce problème, nous proposons un algorithme d’approximation qui est capable de résoudre le problème RCCAA en évitant les différents types de collisions.
Le dernier problème abordé dans ma thèse est le problème du profilage de la taille des étiquettes dans les systèmes RFID ou (Tag Size Profiling -TSP problem). Le problème du TSP consiste à estimer les tailles des sous-régions du système RFID couvertes par plusieurs lecteurs. La résolution du problème TSP permet de déterminer l’ordonnancement optimal des lecteurs qui maximise le débit d’identification des étiquettes. Nous prouvons que la construction de système linéaire optimale adéquat pour résoudre le problème TSP est une tâche est NP difficile. Ensuite, nous développons un nouvel algorithme approximatif qui est capable de résoudre une telle tâche en un temps raisonnable.
Abstract:
Radio Frequency IDentification (RFID ) is a key technology of the Internet of Things (IoT). RFID has the possibility of enabling machines to identify, control and localize the physical objects through networks in real time. Due to its low cost, small size and ability to communicate in different environments (liquids, gas…) without power source, RFID is frequently used in different sectors : supply chain management, electronic security, retail marketing, smart university, military and health-care. RFID is a system composed by tags sensitive to electromagnetic fields created bya reader antenna. Each tag encapsulate a unique identification and can be attached to objects in order to monitor them. However, many challenges remain to be addressed before RFID can reach its full potential in the IoT. Particularly, readers scheduling and RFID network planning (RNP) are among these most important challenges. Essentially, the readers scheduling avoids collision and the RNP assures the most suitable quality of service and cost efficiency.
Owing to the limited interrogation range of RFID readers, multiple readers should be deployed to ensure full tag coverage. The arbitrary deployment of readers causes several problems: wastage of readers, collision and load imbalance between readers. Finding the optimal number of readers to deploy so as obtain full tag coverage, the optimal placement of these readers and the optimal configuration of their parameters is known as an RNP problem. The RNP problem is a multiobjective optimization problem with a large number of variables and uncertain parameters. This dissertation presents a new variant of the cuckoo search algorithm to plan large-scale RFID networks and overcome the deployment challenges described above. In some cases, a good planning can not completely eliminate overlap between readers, hence the necessity of readers scheduling to activate the neighbors readers in a different time to avoids collisions. In this context, a particular problem known as the Reader-Coverage Collision Avoidance Arrangement (RCCAA) problem has received great attention in the literature. The RCCAA problem consists in activating RFID readers and adjusting their interrogation ranges in order to cover the maximum number of tags without collision. In this manuscript, we propose the maximum-weight-independent-set-based algorithm II to solve the RCCAA problem. Another important problem that has great importance in readers scheduling is to know the Tag Size Profile (TSP) of the system. TSP consists in estimating the size of sub-regions in an RFID system covered by several readers. In order to achieve this goal, the sub-regions are considered as variable and the adequate linear system is constructed by these variables and solve them. In this dissertation, we show that the determination of the minimal set of schedule instances to construct an adequate linear system is NP-hard, and we propose a time-efficient approximate algorithm based on a k-partial set cover to solve it.
