The subject of this diploma thesis is the modelling and the analysis of mechanisms that enable multiagentsystems to establish communication relations and using them to control the interaction. With regards to the emergence of such symbol systems one groundwork of this paper is the realization that coordination problems aren't applicative to advance to evolution of "higher communication capabilities". With this in mind, this analysis uses a class of problems with explicit conflicts of interests between agents and the necessity of solving such interaction problems with the help of communication. The paper determines and discusses mechanisms and constraints that enable multiagentsystems to evolve such self-organisating social structures as well as preserving them. / Thema dieser Diplomarbeit ist die Modellierung und Untersuchung von Mechanismen, auf deren Grundlage Multiagentensysteme in der Lage sind, Kommunikationsbeziehungen aufzubauen und kommunikative Akte interaktionssteuernd zu verwenden. Hinsichtlich der Emergenz derartiger Symbolsysteme besteht eine wesentliche Erkenntnis, auf der diese Arbeit aufbaut, darin, dass Koordinationsprobleme als Kontext für MAS kein geeignetes experimentelles Umfeld für die Herausbildung "höherer kommunikativer Fähigkeiten" darstellen. Davon ausgehend werden für eine Klasse von Problemen, in denen die Abstimmung über eine Interaktion aufgrund von Interessenkonflikten einen expliziten Teil des kommunikativ zu lösenden Problems darstellt, Mechanismen und Constraints herausgearbeitet und diskutiert, die Agenten in die Lage versetzen, ein sich selbst organisierendes soziales Gefüge aufzubauen und zu erhalten.

Le récent développement des appareils portatifs possédant une interface Wi-Fi (smartphones, tablettes et « wearables ») s'accompagne d'une menace sur la vie privée de leurs utilisateurs, et sur la société toute entière. Ces appareils émettent en continu des signaux pouvant être capturés par un attaquant passif, à l'aide de matériel peu coûteux et de connaissances basiques. Ces signaux contiennent un identifiant unique appelé l'adresse MAC. Pour faire face à cette menace, les acteurs du secteur déploient actuellement une contre-mesure sur les appareils récents: le changement aléatoire de l'adresse MAC. Malheureusement, nous montrons que cette mesure, dans son état actuel, n'est pas suffisante pour empêcher le traçage des appareils. Pour cela, nous introduisons plusieurs attaques basées sur le contenu et la répartition temporelle des signaux. En complément, nous étudions les implémentations du changement aléatoire de l'adresse MAC sur des appareils récents, et trouvons un certain nombre de manquements limitant l'efficacité de ces implémentations à prévenir le traçage. En parallèle, nous effectuons deux études de terrain. La première s'attaque au développement des acteurs exploitant les problèmes cités plus haut afin d'installer des systèmes de traçage basés sur le Wi-Fi. Nous listons certaines de ces installations et examinons plusieurs aspects de ces systèmes : leur régulation, les implications en terme de vie privée, les questions de consentement et leur acceptation par le public. La seconde étude concerne la progression du changement aléatoire d'adresse MAC dans la population des appareils. Finalement, nous présentons deux outils : le premier est un système de traçage expérimental développé pour effectuer des tests et sensibiliser le public aux problèmes de vie privée liés à de tels systèmes. Le second estime l'unicité d'un appareil en se basant sur le contenu des signaux qu'il émet, même si leur identifiant est modifié. / The recent spread of everyday-carried Wi-Fi-enabled devices (smartphones, tablets and wearable devices) comes with a privacy threat to their owner, and to society as a whole. These devices continuously emit signals which can be captured by a passive attacker using cheap hardware and basic knowledge. These signals contain a unique identifier, called the MAC address. To mitigate the threat, device vendors are currently deploying a countermeasure on new devices: MAC address randomization. Unfortunately, we show that this mitigation, in its current state, is insufficient to prevent tracking. To do so, we introduce several attacks, based on the content and the timing of emitted signals. In complement, we study implementations of MAC address randomization in some recent devices, and find a number of shortcomings limiting the efficiency of these implementations at preventing device tracking. At the same time, we perform two real-world studies. The first one considers the development of actors exploiting this issue to install Wi-Fi tracking systems. We list some real-world installations and discuss their various aspects, including regulation, privacy implications, consent and public acceptance. The second one deals with the spread of MAC address randomization in the devices population. Finally, we present two tools: an experimental Wi-Fi tracking system for testing and public awareness raising purpose, and a tool estimating the uniqueness of a device based on the content of its emitted signals even if the identifier is randomized.

Cette thèse s'intéresse aux problèmes d'allocations des ressources et de puissance dans les réseaux cellulaires de quatrième génération (4G). Pour faire face à la demande continuellement croissante en débit des utilisateurs mobiles, les opérateurs n'ont d'autre choix que de densifier leurs infrastructures d'accès au réseau radio (RAN), afin de maximiser l'utilisation de la bande passante disponible dans l'espace. Un des défis de cette nouvelle architecture est la coexistence de nombreuses cellules voisines et la gestion des interférences co-canal qu'elles génèrent entre elles. De telles contraintes ont amené la communauté scientifique à s'intéresser aux réseaux auto-organisés et auto-optimisés (SON), qui permettent aux réseaux de s'optimiser localement via des décisions décentralisées (sans planification statique). L'intérêt principal de tels réseaux est le passage à l'échelle des algorithmes distribués et la possibilité de s'adapter dynamiquement à de nouveaux environnements. Dans cette optique, nous proposons l'étude de deux problèmes d'allocation de ressources. La première partie de cette thèse se concentre sur l'optimisation de l'usage des ressources, dans un contexte de transmission coordonnée par plusieurs stations de base (CoMP). Les performances de la coordination de stations de base sont évaluées, selon le critère de capacité uniforme, ainsi que le compromis entre l'efficacité spectrale et l'équité entre les utilisateurs. Nous proposons également une méthode généralisée et distribuée de sélection de l'ensemble de stations en coopération, afin d'optimiser le compromis efficacité-équité. Dans une seconde partie, nous nous intéressons à l'optimisation de l'allocation des ressources et de puissance, dans le but de minimiser la consommation électrique du réseau. Nous présentons deux algorithmes dont les décisions sont décentralisées. Le premier est basé sur une optimisation stochastique (via l'échantillonneur de Gibbs) et permet une optimisation globale du système. Le second quant à lui est basé sur l'adaptation de la théorie du contrôle et utilise des modèles prédictifs et la poursuite de cibles pour allouer les ressources et les puissances dans un contexte de canaux et d'interférences dynamiques. Dans de nombreux cas, plusieurs objectifs concurrents sont à considérer pour évaluer les performances d'un réseau (capacité totale, équité, consommation électrique, etc.). Dans le cadre de cette thèse, nous nous efforçons à présenter les résultats sous la forme de compromis multi-objectifs. / This thesis focuses on resources and power allocation problem in the fourth generation (4G) of cellular networks. To face the continuous growth of mobile users capacity requirements, operators need to densify their radio access network (RAN) infrastructure, to maximize the use of the available bandwidth in space. One of the major issues of this new architecture is the proximity of many base stations (BS) and the management of the interference they generate on each other's cell. Such constraints makes scientific community focus on Self-Optimized, Self-Organized Networks (SON) that allow network elements to optimize them-selves through decentralized decisions (no static network planning is required). A major interest of SON is their capability to scale to large and non-organized networks, as well as being able to adapt them-selves dynamically, by using distributed algorithms. In this context, this thesis proposes the study of two resource allocation problems. The first part of this thesis focuses on the optimisation of resource sharing, in the context of coordinated multi-points transmissions (CoMP). Performances of BS coordination are evaluated, using the uniform capacity criterion, as well as the trade-off between total capacity and fairness among users. We also propose a generalized and distributed method to select the set of coordination of BS, to optimize the capacity-fairness trade-off. In the second part of this thesis, we focus on optimizing the transmit power and resource allocation, in order to reduce electric consumption. We present two distributed algorithms: the first one is based on a stochastic optimisation (using Gibbs sampling), and tries to reach the global optimum state through decentralized decision. The second one is based on control theory, and uses target tracking as well as model predictive control to allocate resources and power in a dynamic channel scenario. In many cases, trade-offs are to be maid between opposite objectives when evaluating network performances (total throughput, fairness, energy consumption, etc.). In this thesis, we present most of the network performances using multi-objectives evaluations.

Les objets numériques 3D sont utilisés dans de nombreux domaines, les films d'animations, la visualisation scientifique, l'imagerie médicale, la vision par ordinateur.... Ces objets sont généralement représentés par des maillages à faces triangulaires avec un nombre énorme de triangles. La simplification de ces objets, avec préservation de la géométrie originale, a fait l'objet de nombreux travaux durant ces dernières années. Dans cette thèse, nous proposons un algorithme de simplification qui permet l'obtention d'objets simplifiés de grande précision. Nous utilisons des fusions de couples de sommets avec une relocalisation du sommet résultant qui minimise une métrique d'erreur. Nous utilisons deux types de mesures quadratiques de l'erreur : l'une uniquement entre l'objet simplifié et l'objet original (Accurate Measure of Quadratic Error (AMQE) ) et l'autre prend aussi en compte l'erreur entre l'objet original et l'objet simplifié ((Symmetric Measure of Quadratic Error (SMQE)) . Le coût calculatoire est plus important pour la seconde mesure mais elle permet une préservation des arêtes vives et des régions isolées de l'objet original par l'algorithme de simplification. Les deux mesures conduisent à des objets simplifiés plus fidèles aux originaux que les méthodes actuelles de la littérature. / Complex 3D digital objects are used in many domains such as animation films, scientific visualization, medical imaging and computer vision. These objects are usually represented by triangular meshes with many triangles. The simplification of those objects in order to keep them as close as possible to the original has received a lot of attention in the recent years. In this context, we propose a simplification algorithm which is focused on the accuracy of the simplifications. The mesh simplification uses edges collapses with vertex relocation by minimizing an error metric. Accuracy is obtained with the two error metrics we use: the Accurate Measure of Quadratic Error (AMQE) and the Symmetric Measure of Quadratic Error (SMQE). AMQE is computed as the weighted sum of squared distances between the simplified mesh and the original one. Accuracy of the measure of the geometric deviation introduced in the mesh by an edge collapse is given by the distances between surfaces. The distances are computed in between sample points of the simplified mesh and the faces of the original one. SMQE is similar to the AMQE method but computed in the both, direct and reverse directions, i.e. simplified to original and original to simplified meshes. The SMQE approach is computationnaly more expensive than the AMQE but the advantage of computing the AMQE in a reverse fashion results in the preservation of boundaries, sharp features and isolated regions of the mesh. For both measures we obtain better results than methods proposed in the literature.

Nous développons une méthode générique semi-automatique multi-objet de segmentation d'image par coupure de graphe visant les usages médicaux de routine, allant des tâches impliquant quelques objets dans des images 2D, à quelques dizaines dans celles 3D quasi corps entier. La formulation souple de la méthode permet son adaptation simple à une application donnée. En particulier, le modèle d'a priori de proximité que nous proposons, défini à partir des contraintes de paires du plus court chemin sur le graphe d'adjacence des objets, peut facilement être adapté pour tenir compte des relations spatiales entre les objets ciblés dans un problème donné. L'algorithme de segmentation peut être adapté aux besoins de l'application en termes de temps d'exécution et de capacité de stockage à l'aide d'une partition de l'image à segmenter par une tesselation de Voronoï efficace et contrôlable, établissant un bon équilibre entre la compacité des régions et le respect des frontières des objets. Des évaluations et comparaisons qualitatives et quantitatives avec le modèle de Potts standard confirment que notre modèle d'a priori apporte des améliorations significatives dans la segmentation d'objets distincts d'intensités similaires, dans le positionnement précis des frontières des objets ainsi que dans la robustesse de segmentation par rapport à la résolution de partition. L'évaluation comparative de la méthode de partition avec ses concurrentes confirme ses avantages en termes de temps d'exécution et de qualité des partitions produites. Par comparaison avec l'approche appliquée directement sur les voxels de l'image, l'étape de partition améliore à la fois le temps d'exécution global et l'empreinte mémoire du processus de segmentation jusqu'à un ordre de grandeur, sans compromettre la qualité de la segmentation en pratique. / We develop a generic Graph Cut-based semiautomatic multiobject image segmentation method principally for use in routine medical applications ranging from tasks involving few objects in 2D images to fairly complex near whole-body 3D image segmentation. The flexible formulation of the method allows its straightforward adaption to a given application.\linebreak In particular, the graph-based vicinity prior model we propose, defined as shortest-path pairwise constraints on the object adjacency graph, can be easily reformulated to account for the spatial relationships between objects in a given problem instance. The segmentation algorithm can be tailored to the runtime requirements of the application and the online storage capacities of the computing platform by an efficient and controllable Voronoi tessellation clustering of the input image which achieves a good balance between cluster compactness and boundary adherence criteria. Qualitative and quantitative comprehensive evaluation and comparison with the standard Potts model confirm that the vicinity prior model brings significant improvements in the correct segmentation of distinct objects of identical intensity, the accurate placement of object boundaries and the robustness of segmentation with respect to clustering resolution. Comparative evaluation of the clustering method with competing ones confirms its benefits in terms of runtime and quality of produced partitions. Importantly, compared to voxel segmentation, the clustering step improves both overall runtime and memory footprint of the segmentation process up to an order of magnitude virtually without compromising the segmentation quality.