Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code (propriété de domination) et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code (propriété de séparation). Dans cette thèse, nous nous intéressons à des aspects combinatoires et algorithmiques relatifs aux codes identifiants.Pour la partie combinatoire, nous étudions tout d'abord des questions extrémales en donnant une caractérisation complète des graphes non-orientés finis ayant comme taille minimum de code identifiant leur ordre moins un. Nous caractérisons également les graphes dirigés finis, les graphes non-orientés infinis et les graphes orientés infinis ayant pour seul code identifiant leur ensemble de sommets. Ces résultats répondent à des questions ouvertes précédemment étudiées dans la littérature.Puis, nous étudions la relation entre la taille minimum d'un code identifiant et le degré maximum d'un graphe, en particulier en donnant divers majorants pour ce paramètre en fonction de l'ordre et du degré maximum. Ces majorants sont obtenus via deux techniques. L'une est basée sur la construction d'ensembles indépendants satisfaisant certaines propriétés, et l'autre utilise la combinaison de deux outils de la méthode probabiliste : le lemme local de Lovasz et une borne de Chernoff. Nous donnons également des constructions de familles de graphes en relation avec ce type de majorants, et nous conjecturons que ces constructions sont optimales à une constante additive près.Nous présentons également de nouveaux minorants et majorants pour la cardinalité minimum d'un code identifiant dans des classes de graphes particulières. Nous étudions les graphes de maille au moins 5 et de degré minimum donné en montrant que la combinaison de ces deux paramètres influe fortement sur la taille minimum d'un code identifiant. Nous appliquons ensuite ces résultats aux graphes réguliers aléatoires. Puis, nous donnons des minorants pour la taille d'un code identifiant des graphes d'intervalles et des graphes d'intervalles unitaires. Enfin, nous donnons divers minorants et majorants pour cette quantité lorsque l'on se restreint aux graphes adjoints. Cette dernière question est abordée via la notion nouvelle de codes arête-identifiants.Pour la partie algorithmique, il est connu que le problème de décision associés à la notion de code identifiant est NP-complet même pour des classes de graphes restreintes. Nous étendons ces résultats à d'autres classes de graphes telles que celles des graphes split, des co-bipartis, des adjoints ou d'intervalles. Pour cela nous proposons des réductions polynomiales depuis divers problèmes algorithmiques classiques. Ces résultats montrent que dans beaucoup de classes de graphes, le problème des codes identifiants est algorithmiquement plus difficile que des problèms liés (tel que le problème des ensembles dominants).Par ailleurs, nous complétons les connaissances relatives à l'approximabilité du problème d'optimisation associé aux codes identifiants. Nous étendons le résultat connu de NP-difficulté pour l'approximation de ce problème avec un facteur sous-logarithmique (en fonction de la taille du graphe instance) aux graphes bipartis, split et co-bipartis, respectivement. Nous étendons également le résultat connu d'APX-complétude pour les graphes de degré maximum donné à une sous-classe des graphes split, aux graphes bipartis de degré maximum 4 et aux graphes adjoints. Enfin, nous montrons l'existence d'un algorithme de type PTAS pour les graphes d'intervalles unitaires. / An identifying code is a set of vertices of a graph such that, on the one hand, each vertex out of the code has a neighbour in the code (domination property), and, on the other hand, all vertices have a distinct neighbourhood within the code (separation property). In this thesis, we investigate combinatorial and algorithmic aspects of identifying codes.For the combinatorial part, we first study extremal questions by giving a complete characterization of all finite undirected graphs having their order minus one as minimum size of an identifying code. We also characterize finite directed graphs, infinite undirected graphs and infinite oriented graphs having their whole vertex set as unique identifying code. These results answer open questions that were previously studied in the literature.We then study the relationship between the minimum size of an identifying code and the maximum degree of a graph. In particular, we give several upper bounds for this parameter as a function of the order and the maximum degree. These bounds are obtained using two techniques. The first one consists in the construction of independent sets satisfying certain properties, and the second one is the combination of two tools from the probabilistic method: the Lovasz local lemma and a Chernoff bound. We also provide constructions of graph families related to this type of upper bounds, and we conjecture that they are optimal up to an additive constant.We also present new lower and upper bounds for the minimum cardinality of an identifying code in specific graph classes. We study graphs of girth at least 5 and of given minimum degree by showing that the combination of these two parameters has a strong influence on the minimum size of an identifying code. We apply these results to random regular graphs. Then, we give lower bounds on the size of a minimum identifying code of interval and unit interval graphs. Finally, we prove several lower and upper bounds for this parameter when considering line graphs. The latter question is tackled using the new notion of an edge-identifying code.For the algorithmic part, it is known that the decision problem associated to the notion of an identifying code is NP-complete, even for restricted graph classes. We extend the known results to other classes such as split graphs, co-bipartite graphs, line graphs or interval graphs. To this end, we propose polynomial-time reductions from several classical hard algorithmic problems. These results show that in many graph classes, the identifying code problem is computationally more difficult than related problems (such as the dominating set problem).Furthermore, we extend the knowledge of the approximability of the optimization problem associated to identifying codes. We extend the known result of NP-hardness of approximating this problem within a sub-logarithmic factor (as a function of the instance graph) to bipartite, split and co-bipartite graphs, respectively. We also extendthe known result of its APX-hardness for graphs of given maximum degree to a subclass of split graphs, bipartite graphs of maximum degree 4 and line graphs. Finally, we show the existence of a PTAS algorithm for unit interval graphs.

Cette thèse a pour objectif de faire avancer l'état de l'art des communications basée sur Internet Protocol version 6 (IPv6) dans le domaine des réseaux véhiculaires, et ce dans le cadre des évolutions récentes de IP, notamment l'avènement du Future Internet. Le Future Internet (F.I.) définit un ensemble d'approches pour faire évoluer l'Internet actuel , en particulier l'émergence d'un Internet mobile exigeant en ressources. Les acteurs de ce domaine définissent les contraintes inhérentes aux approches utilisées historiquement dans l'évolution de l'architecture d'Internet et tentent d'y remédier soit de manière évolutive soit par une rupture technologique (révolutionnaire). Un des problèmes au centre de cette nouvelle évolution d'Internet est la question du nommage et de l'adressage dans le réseau. Nous avons entrepris dans cette thèse l'étude de ce problème, dans le cadre restreint des communications véhiculaires Internet.Dans ce contexte, l'état de l'art du Future Internet a mis en avant les distinctions des approches révolutionnaires comparées aux propositions évolutives basées sur IPv6. Les réseaux véhiculaires étant d'ores-et-déjà dotés de piles protocolaires comprenant une extension IPv6, nous avons entamé une approche évolutive visant à intégrer les réseaux véhiculaires au Future Internet. Une première proposition a été de convertir un identifiant présent dans le monde automobile (VIN, Numéro d'Identification de Véhicule) en un lot d'adresses réseau propres à chaque véhicule (qui est donc propriétaire de son adressage issu de son identifiant). Cette proposition étant centrée sur le véhicule, nous avons ensuite intégré ces communications basés dans une architecture globale Future Internet basée sur IPv6 (protocole LISP). En particulier, et avec l'adressage VIN, nous avons défini un espace d'adressage indépendant des fournisseurs d'accès à Internet où le constructeur automobile devient acteur économique fournissant des services IPv6 à sa flotte de véhicules conjointement avec les opérateurs réseau dont il dépend pour transporter son trafic IP. Nous nous sommes ensuite intéressés à l'entourage proche du véhicule afin de définir un nouveau mode de communication inter-véhiculaire à Internet: le V2V2I (Angl. Vehicle-to-Vehicle-to-Infrastructure). Jusqu'à présent, les modes de transmission de données à Internet dans le monde du véhicule consistaient en des topologies V2I, à savoir véhicule à Internet, où le véhicule accède à l'infrastructure directement sans intermédiaire. Dans le cadre des communications véhiculaires à Internet, nous proposons une taxonomie des méthodes existantes dans l'état de l'art. Les techniques du Future Internet étant récentes, nous avons étendu notre taxonomie par une nouvelle approche basée sur la séparation de l'adressage topologique dans le cluster de celui de l'infrastructure. Le leader du cluster s'occupe d'affecter les adresses (de son VIN) et de gérer le routage à l'intérieur de son cluster. La dernière contribution consiste en la comparaison des performances des protocoles de gestion de mobilité, notamment pour les réseaux de véhicules et des communications de type vehicule-à-Internet. Dans ce cadre, nous avons proposé une classification des protocoles de gestion de mobilité selon leur déploiement: centralisé (basé réseau ou host) et distribué. Nous avons ensuite évalué les performances en modélisant les durées de configurations et de reconfigurations des différents protocoles concernés. / After successfully connecting machines and people later (world wide web), the new era of In-ternet is about connecting things. Due to increasing demands in terms of addresses, mobility, scalability, security and other new unattended challenges, the evolution of current Internet archi-tecture is subject to major debate worldwide. The Internet Architecture Board (IAB) workshop on Routing and Addressing report described the serious scalability problems faced by large backbone operators in terms of routing and addressing, illustrated by the unsustainable growth of the Default Free Zone (DFZ) routing tables. Some proposals tackled the scalability and IP semantics overload issues with two different approaches: evolutionary approach (backward com-patibility) or a revolutionary approach. Several design objectives (technical or high-level) guided researchers in their proposals. Mobility is definitely one of the main challenges.Inter-Vehicle Communication (IVC) attracts considerable attention from the research com-munity and the industry for its potential in providing Intelligent Transportation Systems (ITS) and passengers services. Vehicular Ad-Hoc Networks (VANETs) are emerging as a class of wire-less network, formed between moving vehicles equipped with wireless interfaces (cellular and WiFi) employing heterogeneous communication systems. A VANET is a form of mobile ad-hoc network that provides IVC among nearby vehicles and may involve the use of a nearby fixed equipment on the roadside. The impact of Internet-based vehicular services (infotainment) are quickly developing. Some of these applications, driver assistance services or traffic reports, have been there for a while. But market-enabling applications may also be an argument in favor of a more convenient journey. Such use cases are viewed as a motivation to further adoption of the ITS standards developed within IEEE, ETSI, and ISO.This thesis focuses on applying Future Internet paradigm to vehicle-to-Internet communica-tions in an attempt to define the solution space of Future Vehicular Internet. We first introduce two possible vehicle-to-Internet use cases and great enablers for IP based services : eHealth and Fully-electric Vehicles. We show how to integrate those use cases into IPv6 enabled networks. We further focus on the mobility architectures and determine the fundamental components of a mobility architecture. We then classify those approaches into centralized and distributed to show the current trends in terms of network mobility extension, an essential component to vehicular networking. We eventually analyze the performance of these proposals. In order to define an identifier namespace for vehicular communications, we introduce the Vehicle Identification Numbers are possible candidates. We then propose a conversion algorithm that preserves the VIN characteristics while mapping it onto usable IPv6 networking objects (ad-dresses, prefixes, and Mobile Node Identifiers). We make use of this result to extend LISP-MN protocol with the support of our VIN6 addressing architecture. We also apply those results to group IP-based communications, when the cluster head is in charge of a group of followers.

Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.

Au cours des dernières décennies, le besoin pour des communications multimédia en mobilité est devenu indéniable dans les réseaux de type IP, ainsi la gestion de la mobilité et la continuité de session est depuis plusieurs années un problème de recherche très important aussi bien pour le milieu académique qu’industriel. Comme l'hétérogénéité des réseaux d’accès est en perpétuelle évolution, l'intégration des différents types de réseaux sans fil au niveau de la couche IP est devenue un domaine de recherche difficile et inévitable. L'un des problèmes les plus importants liés à l'exécution de la gestion de la mobilité concerne le fait que la couche d'application souffre de la modification d'adresses IP au cours du mouvement du nœud mobile alors que celle-ci construit sa session sur la base de l’adresse IP de connexion au réseau. Une nouvelle approche d'amélioration de la prise en charge de la mobilité propose de séparer l'identification de session et l'identification de l’emplacement ou l’attachement au réseau. Donc, par la séparation de ces deux concepts, les sessions ne sont pas identifiés par les adresses IP qui elles sont dynamiques puisque la mobilité dans le réseau impose le changement d’adresse IP, mais les nouveaux identificateurs uniques qui définissent un nœud et qui ne change pas à cause de la mobilité ce qui offrirait une stabilité pour le niveau applicatif. Selon ces concepts, Host Identity Protocol (HIP) est l'une des solutions dominantes en recherches qui est proposé par l'IETF et l’IRTF. Dans cette thèse, le protocole HIP est principalement examiné et de nouvelles améliorations de la mobilité sur la base de ce protocole ont été conçues et mises en place / Over the last decades, with rapid and tremendous growth of IP networks in mobile and wireless environments, mobility management and session continuity has become a more important issue. As the heterogeneity increases in network environments and gradual spread of Internet of Things wave, the integration of different types of wireless networks in the IP layer became a challenging and inevitable research area. One of the most important issues related to mobility management is related to the fact that the application layer suffers from the changing of IP addresses during the movement of the mobile node. It is expected the network layer and above layers to be aware of movement of mobile nodes. New wave in the improvement ideas on this concept is separating the session identification and the location identification. This avoids the applications to suffer when the IP address changes during the mobility. This new approach needs to introduce a new layer in the TCP/IP protocol stack, on top of the IP layer that will handle the new identifiers correspondent with the current IP address or new complete architecture designs which are inheriting locator/identifier separation idea. According to these concepts, Host Identity Protocol (HIP) is one of the dominant and prominent researches that is proposed by IETF and IRTF. This protocol proposes to solve the locator/identifier split problem by also including the security support. In this thesis, predominantly HIP protocol is examined and new mobility enhancements based on this protocol have been designed and introduced