Cette thèse cherche à lier les cycles économiques et la gestion de portefeuille. Le premier chapitre construit un cadre théorique entre les cycles économiques et les primes de risques. Il met en évidence l’importance des points de retournement du cycle de croissance, plus connu sous le nom d’écart de production. Les deux chapitres suivants ont pour objectif de détecter en temps réel ces points de retournement. La première approche se concentre sur une méthode non paramétrique d’apprentissage automatique simple et facilement compréhensible appelée quantification vectorielle adaptative. La seconde approche utilise des méthodes plus complexes d’apprentissage automatique, dites ensemblistes : les forêts aléatoires et le boosting. Les deux démarches permettent de créer des stratégies d’investissement performantes en temps réel. Enfin, le dernier chapitre élabore une méthode d’allocation d’actifs à partir de différents algorithmes de regroupement hiérarchique. Les résultats empiriques démontrent l’intérêt de cette tentative : les portefeuilles créés sont robustes, diversifiés et lucratifs. / A well-worked theory of macro-based investment decision is introduced. The theoretical influence of economic cycles on time-varying risk premiums is explained and exhibited. The importance of the turning points of the growth cycle, better known as the output gap, is outlined. To quickly and accurately detect economic turning points, probabilistic indicators are first created from a simple and transparent machine-learning algorithm known as Learning Vector Quantization. Those indicators are robust, interpretable and preserve economic consistency. A more complex approach is then evaluated: ensemble machine learning algorithms, referred to as random forest and as boosting, are applied. The two key features of those algorithms are their abilities to entertain a large number of predictors and to perform estimation and variable selection simultaneously. With both approaches investment strategies based on the models achieve impressive risk-adjusted returns: timing the market is thus possible. At last, exploring a new way of capital allocation, a hierarchical clustering based asset allocation method is introduced. The empirical results indicate that hierarchical clustering based portfolios are robust, truly diversified and achieve statistically better risk-adjusted performances than commonly used portfolio optimization techniques.

Cette thèse examine la façon dont les choix stratégique des firmes multi-établissements affectent la performance de leurs filiales et contribuent aux débats récurrents liés à la pertinence et l’importance de la stratégie d’entreprise. Dans le premier chapitre, nous nous intéressons à savoir le poids relatif des décisions stratégiques des sièges sociaux sur la performance de leurs établissements. Nous montrons l’incapacité des méthodes traditionnelles à rendre compte efficacement des effets entreprises. Nous soutenons en effet que les études précédentes sous-estiment systématiquement les effets entreprises car elles ne tiennent pas compte de l’hétérogénéité de l’impact des décisions des sièges sociaux sur leurs filiales. Une filiale peut recevoir une part très différente des ressources de l’entreprise. Par conséquent, le fait d’étudier toutes les filiales comme s’il s’agissait d’un seul groupe sous-estime systématiquement les effets entrepris. Nous soutenons plutôt qu’il est important de tenir compte de la variance induite par l’entreprise sur la performance des filiales. Nous appelons cette variance induite « effet entreprise variant », et montrons qu’elle est tout aussi importante que la valeur des effets entreprise standards, à savoir « les effets entreprise invariants ». Dans le deuxième chapitre nous nous sommes intéressés au débat relatif à l’efficacité des marchés de capitaux internes, comme une des sources essentielles d’hétérogénéité de la performance des filiales. La question centrale du débat consiste à discuter les modalités d’allocation optimale du capital. Les études empiriques mettent en évidence des montants d’allocation très au-dessus des niveaux optimaux dans des filiales qui ont des niveaux de croissance apparemment relativement faibles. Tenant compte à la fois du degré d’incertitude auquel une firme est confrontée lorsqu’elle décide d’allouer son capital et du niveau d’interdépendance de ses filiales, nous distinguons « les déviations inefficaces » des « déviations non nécessairement inefficaces ». Nous expliquons que les déviations par rapport à la logique de sélection des gagnants dans les décisions d’allocation de capital peuvent simplement refléter des intentions stratégiques différentes plutôt que des inefficacités d’allocation. De plus, nous soulignons le rôle de l’ampleur de l’expérience antérieure des dirigeants dans le domaine des filiales, en tant que source de compétences en allocation de capital des firmes, dans l’atténuation des déviations inefficaces et l’augmentation de la valeur de la corporation grâce à de meilleures pratiques d’allocation du capital. Le troisième chapitre incorpore les ressources financières à la théorie de redéploiement des ressources. La théorie standard a exclu les ressources financières qui, par définition, peut être allouée et ré-allouées à tout type d’investissement sans contrainte. Nous soutenons toutefois que, lors de l’affectation vers l’une de ses filiales de ressources financières à des investissements imparfaitement fongibles ou divisibles, telles que le capital physique, tel que des usines ou des technologies, le siège social achète également l’option de redéploiement de ces mêmes ressources dans le futur. En effet, le choix d’investissement présent doit être réalisé en tenant compte des coûts de redéploiement éventuels dans le futur. Par conséquent, la direction des flux de capitaux actuels entre les filiales ne sera pas simplement réalisée en fonction des opportunités actuelles de croissance relative du marché, mais aussi en fonction des coûts d’ajustement due aux redéploiements éventuels entre les filiales dans les périodes ultérieures. Cette extension permet d’étendre le champ d’études empiriques de la théorie du redéploiement de ressources non-financier. En effet, les études empiriques dans ce domaine ont été rares jusqu'à présent en raison du défi que représentent l'observation et la mesure du redéploiement des ressources non financières. / This dissertation deals with how multi-business firms’ strategies affect the performance of subsidiary businesses and contributes to long standing debates in corporate strategy. Overall, each of my 3 dissertation essays are designed to, correspondingly, analyze the debated magnitude, efficiency, and mechanism of the effect of a multi-business firms’ strategies on the performance of its subsidiaries. In the first chapter, I address a root question in corporate level strategy; I question traditional methods to estimate corporate effects (the effect of corporate headquarters on subsidiary businesses’ performance). I argue that previous corporate effect studies fail to account for the uneven impact of corporate decisions on subsidiaries. A headquarters makes conscious and deliberate decisions that might induce performance heterogeneity among its subsidiaries. Consequently, considering all subsidiaries as a bundle will systematically underestimate the corporate effects. Rather, I argue that it is important to account for the firm’s induced variance on the subsidiaries’ performance. We connote this induced variance as “business-variant corporate effects”, and show that they are just as important in magnitude as the value of the standard corporate effects, namely “business-invariant corporate effects”, found in previous studies. In the second essay, I focus on corporate capital allocation as a critical dimension of corporate strategies that might contribute to, within-firm, subsidiaries’ performance heterogeneity. We particularly delve deeper into the internal capital market efficiency debate by extending current theories that aim to justify why headquarters provide more resources to subsidiaries with seemingly lower growth opportunities. Considering both the level of uncertainty a firm faces when making capital allocation decisions, and the level of interdependence among its subsidiaries, we disentangle between inefficient and not-necessarily-inefficient deviations from standard models’ prescription. We explain that higher investments in subsidiaries with seemingly lower growth opportunities may simply reflect different strategic intents rather than allocation inefficiencies. Furthermore, we highlight the role of the breadth of CEOs’ prior experience in subsidiaries’ domain, as a source of firms’ capital allocation competency, in attenuating inefficient deviations and enhancing corporate value through better capital allocation practices. In the third essay, I incorporate financial resources, as a perfectly fungible and divisible resource, within the scope of the resource redeployment theory. Indivisibility and imperfect fungibility of resources play a critical role in the theory and this is why the standard theory has excluded the financial resources from its boundaries. I, however, argue that when allocating financial resources, such as capital, to one of its subsidiaries to acquire non-financial assets such as plants or technology, a corporate headquarters also purchases the option to redeploy those same resources in subsequent periods. Therefore, the direction of current capital flow among subsidiary businesses will not merely be a function of their current relative market growth opportunities. Rather, it is a function of the adjustment costs of potential resource redeployments among the subsidiaries in subsequent periods. My extension of the resource redeployment theory to include intrafirm capital allocations paves the way for further empirical investigations of the theory; that have been scarce so far, due to the challenge of observing and measuring the redeployment of non-financial resources. In turn, studying intrafirm capital allocations through the lens of RR theory helps us further develop and offer novel predictions for the theory.

The value of cost allocation comes from its initial purpose; decision support. In other words, cost allocation is considered a vital part of management, as it generates valuable information concerning efficiency and profitability. By applying Time Driven Activity Based Costing (TDABC) in a financial service company, this pilot study aims to learn from the consequences of the application, and discuss the lessons learned. The application resulted in a two-step allocation using Traditional Cost Allocation in the first step and TDABC in the final step, wherethe overhead cost of four support departments were allocated down to products. To build the model, interviews were conducted with personnel and internal documents were used. The application's most important lessons are thedifficultyofidentifying and measuring activities, the model’s requirement of high-quality data and the complexity of the capacity measures.

The process of municipal land allocations is not regulated by law in Sweden with the result that Swedish municipalities has developed their own approaches of land allocation and choice of developer. In the absence of rulings and standardized municipal use has led to that especially developers considered the land allocation process to be unpredictable and not transparent. The 1st of January 2015 the law of guidelines for municipal land allocations took effect. The law states that municipalities who carry out land allocations should adopt guidelines whose content should specify each municipality’s procedure for land allocation. The purpose of the law is to create transparency, increased clarity and predictability to the initial part of the building process. Our study aims to give an overlook of how the 50 largest municipalities work with the guidelines acquired by law. The project studies the application, availability and the content of the guidelines for land allocations. The investigation shows that about 75 % of the 50 largest municipalities in Sweden have adopted guidelines for land allocation. About 60 % of the municipalities have the guidelines available on their website. Our study also shows a wide spread in content and details and that the information mediated to interested developers through the guidelines may be considered too general to be able to achieve the purpose of the law. Municipalities do not benefit from specified guidelines and the law itself opens up for general formulations and their own interpretations while there are no sanctions. We wonder whether the law simply was written to quiet the critics that have existed in the area. / Markanvisningsprocessen är inte reglerad i lag vilket har gjort att kommunerna utformat sina egna tillvägagångssätt för markanvisningen och således valet av byggherre. Avsaknaden av dels styrande regler och dels en enhetlig kommunal praxis har medfört att framförallt byggherrar ansett att markanvisningsprocessen ofta är oförutsägbar och inte transparent. Den 1 januari 2015 trädde Lag (2014:899) om riktlinjer för kommunala markanvisningar i kraft. Konkret anger lagen att kommuner som genomför markanvisningar ska anta riktlinjer vars innehåll ska precisera respektive kommuns förfarande vilket ska leda till att skapa transparens och ökad tydlighet, samt förutsägbarhet i byggprocessens inledande skede. Undersökningens syfte är att försöka ge en översiktlig bild av hur Sveriges 50 största kommuner arbetar med de riktlinjer som lagstiftningen föreskriver. Mer konkret avser uppsatsen undersöka tillämpningen och tillgängligheten av kommunala riktlinjer för markanvisningar samt dess innehåll. Undersökningen visar att cirka 75 % av de 50 största kommunerna i Sverige har antagna riktlinjer för markanvisningar. Ungefär 60 % av kommunerna har riktlinjer tillgängliga via sin hemsida. Undersökningen visar även på en stor variation i utförligheten hos de kommunala riktlinjerna och den information som förmedlas till intresserade byggherrar genom riktlinjerna kan anses alltför generell för att kunna uppnå lagens syfte. Kommuner gynnas inte av att precisera sina riktlinjer närmre och lagen i sig öppnar upp för generella skrivelser och egna tolkningar samtidigt som ingen prövning finns. Vi ställer oss frågande till om lagen helt enkelt kom till för att stilla de kritiker som funnits på området.

Currently there is a high demand for housing in Sweden, especially in the metropolitan areas. The municipalities own a major part of the land intended for new construction. Through a land allocation the land can be allocated to developers, which in turn develops the area. Thus, land allocation is a vital tool for the housing development in Sweden. Currently there are no regulations concerning how the land allocation should be carried out. Consequently, the implementations differ significantly between different municipalities and projects. The purpose of this master thesis is to describe and compare different approaches of municipal land allocations in larger development projects. Furthermore, the aim is to analyze pros and cons of the different approaches and recommend which components that should be used in land allocations of larger development projects. When the different approaches have been described and compared the particular method has been studied, what criteria that have been used during the selection of developers and how the assessment has been carried out. Other than that the duration, pricing and regulation of rent and tenure have been investigated. Furthermore, questions regarding zoning have also been considered in the study. The four projects that has been investigated is Frihamnen (Göteborg), Årstafältet (Stockholm), Södra Ladugårdsängen (Örebro) and Vallastaden (Linköping). The objective of the study has been achieved through a literature review and a case study of the four projects. The case study is based on written documents and conducted interviews with involved parties from the municipalities and developers. The study has shown that all approaches of land allocation studied differ depending on the project conditions and objectives. In all projects a tender process has been the base for selection of developers. Price was the driving factor in Årstafältet, while other criterias were in focus in the other projects. The study shows that a selection based on other criterias then price is good in order to promote quality and diversity in the project. However, a tender based only on price is a simple and relatively cheap method. Regarding detail plans, it is concluded that it can be an advantage for smaller municipalites to prepare the detail plan before a land allocation takes place in order to attract developers. This approach is something that especially promotes smaller developers since preparation of a plan is costly and time-consuming. In addition, it is concluded that it always should occur some type of coordination and planning among the municipality and the selected developers in order to obtain optimal overall solutions for the area. / Det råder i Sverige idag en stor efterfrågan på bostäder, speciellt i storstadsregionerna. En stor del av marken för nyproduktion ägs av Sveriges kommuner som via en markanvisning kan fördela marken till byggherrar för exploatering av marken. Markanvisning är därmed tillsammans med planmonopolet ett viktigt instrument för bostadsutvecklingen. Någon reglering för hur fördelning av markanvisning bör ske finns inte och tillämpningen skiljer sig därmed väsentligt mellan kommun och projekt. Syftet med detta examensarbete är att beskriva och jämföra tillvägagångssätten vid kommunal markanvisning inom större exploateringsprojekt. Detta för att kunna observera skillnader, analysera för- och nackdelar samt att ge förslag på komponenter som bör tillämpas vid markanvisning av större exploateringsområden. Med tillvägagångssätt menas bland annat vilken tilldelningsmetod som använts, vilka kriterier som val av byggherrar grundats på samt hur denna bedömning gått till. Vidare har även processens gång, prissättning och eventuell reglering av hyra och upplåtelseformer undersökts. Hur och när detaljplan framtagits berörs även i studien. De fyra projekt som ingår i studien är Frihamnen (Göteborg), Årstafältet (Stockholm), Södra Ladugårdsängen (Örebro) och Vallastaden (Linköping). Syftet med studien har uppnåtts via en litteraturstudie samt en fallstudie över de fyra projekten. Inom fallstudien har dels material studerats och dels intervjuer med kommunala tjänstemän samt deltagande byggherrar genomförts. Studien har visat på att samtliga studerade tillvägagångssätt skiljer sig åt beroende på förutsättningar och mål med projekten. Inom samtliga projekt har anbudsanvisning tillämpats och inom samtliga projekt förutom Årstafältet har urvalet grundats på andra kriterier än pris. Att genomföra bedömningen på andra kriterier än pris är något som studien kommit fram till är lämpligt för att främja kvalitet och mångfald i projektet. Däremot är ett anbud baserat endast på pris en enkel och mindre resurskrävande metod att tilldela markanvisning samt erhålla ett marknadspris på. Avseende framtagande av detaljplan kan detta i vissa mindre kommuner vara fördelaktigt att ta fram innan markanvisning för att locka fler byggherrar. Detta tillvägagångssätt är även något som främjar mindre byggherrar då ett detaljplanearbete är resurs- och tidskrävande. Någon slags samordning och planering bör däremot alltid ske mellan kommun och tilldelade byggherrar för att erhålla en optimal helhetslösning för området.

Med den takt som nya områden behöver växa fram för att täcka kommunernas bostadsbehov är det viktigt att komma ihåg de värden som skapar trivsel och trygghet i vistelsemiljöerna. Markanvisningsprocessen, som innebär en förhandling där byggherrar förhandlar med kommunen om att få köpa kommunalt ägd mark för nybyggnation, är en komplex process som påverkas av många faktorer. Nya områden som utgör bostäder för invånarna är ett resultat av hur kommunens arbetssätt och strategier ser ut och studien fokuserar på strategierna samt dess påverkan på gestaltningen i den byggda miljön. Genom intervjuer med kommunanställda, stadsarkitekter och en arkitekt samt litteraturstudier och fallstudier av tre nybyggda områden i tre olika kommuner, utreds samband mellan markanvisningsprocessen och hur väl gestaltningen i områdena har tagit tillvara på arkitektoniska värden som är viktiga för trygghet och trivsel. Studien visar att det finns brister i processen som gör att de ursprungliga målen med områdena inte alltid uppnås fullt ut. Den visar även att det kan vara viktigt att de gestaltningsmässiga värdena kommuniceras och tas tillvara tidigt i processen för att de ska följa med hela vägen till det färdiga resultatet, det vill säga den byggda miljön. / The rate in which new residential areas need to be produced to meet the municipalities need for housing, it is important to remember the architectural values that creates comfort and security in the habitats. The land allocation process, meaning developers negotiation with the municipalities regarding the purchase of the land owned by the municipalities, is a complex process affected by many factors. New areas constituting residences of the inhabitants are the results of the municipal strategies, and the study focuses on the strategies and their impact on the design of the built environment. By interviews with municipal employees and city architects as well as an architect, literature studies and case studies of three recently built-up areas, the connection between the land allocation process and the amount of architectural values enhancing the security and comfort in the areas are being investigated. The study indicates that there are shortages in the process causing the original goals with the areas not always entirely are being fulfilled. It also points at the importance of that the architectural values are communicated and taken into account early in the process, to be followed through the whole implementation until the results, i.e. the built environment.

Dans cette thèse, nous étudions le problème de l'allocation de ressources dans le cadre des réseaux 4G LTE. La méthode d'accès OFDMA qui est utilisée partage les ressources radios à la fois dans le domaine fréquentiel et temporel. En raison des déficiences du canal, les utilisateurs ne bénéficient pas toujours des mêmes débits d'émission/réception sur chacune des ressources. Dans ce cadre, notre problème consiste à distribuer ces ressources radios aux mobiles afin de leur permettre de transmettre/recevoir des données. L'algorithme utilisé pour allouer les ressources a une importance fondamentale sur les performances du système. La norme LTE ajoute des contraintes supplémentaires à ce problème et rend l'exploitation de la diversité fréquentielle et de la diversité multi-utilisateurs plus difficile. En effet, sous ces contraintes, nous montrons que le problème de l'allocation de ressources fait alors partie de la classe des problèmes « difficiles ». Par conséquent, les algorithmes classiques de la littérature sont souvent inadaptés à un réseau LTE réel. Nous proposons des algorithmes d'allocation de ressources à la fois pour le sens montant et descendant de LTE. Les contraintes de la norme sont rigoureusement prises en compte afin de construire des solutions efficaces. De plus, les algorithmes proposés sont génériques et peuvent donc s'adapter à une grande variété d'objectifs. En particulier, nous nous attachons à prendre en charge les trafics multimédias dont les débits et les besoins en qualité de service sont très hétérogènes (taux d’erreurs binaires, retard, gigue, etc.). En effet, l'augmentation progressive des débits et la forte popularité des équipements mobiles intelligents amènent à une utilisation toujours plus massive des applications multimédias. Tous nos algorithmes sont validés par simulation. Par ce biais, nous montrons que la prise en compte des contraintes de LTE est essentielle à l'obtention de performances élevées. / In this thesis, we study the resource allocation problem within the framework of 4G LTE networks. The OFDMA access method divides the radio resources both in the frequency and time domains. Due to channel impairments, users do not always have the same transmit/receive rates on each resource. In this context, our problem is to share the radio resources between users and enable them to transmit/receive data. The algorithm used to allocate resources is of fundamental importance on system performance. The LTE standard adds constraints to this problem and makes harder the exploitation of the frequency and the multi-user diversity. Indeed, under these constraints, we show that the resource allocation problem becomes part of the « most difficult » problems. Therefore, the conventional algorithms are often not adapted to a real LTE network. We provide resource allocation algorithms for both the uplink and downlink of LTE. The constraints of the standard are rigorously taken into account in order to build effective solutions. In addition, the proposed algorithms are generic and can adapt to a wide variety of objectives. In particular, we focus on the support of multimedia traffic with heterogeneous quality of service requirements (bit error rate, delay, jitter, etc.). Indeed, the gradual increase of the offered throughput and the strong popularity of smart mobile devices lead to a massive use of multimedia applications. Our algorithms are validated through extensive simulation. By this means, we show that the inclusion of LTE constraints is essential to achieving high performance.

La prise de conscience générale de l'importance de vérifier plus scrupuleusement les programmes a engendré une croissance considérable des efforts de vérification formelle de programme durant cette dernière décennie. Néanmoins, le code qu'exécute l'ordinateur, ou code exécutable, n'est pas le code écrit par le développeur, ou code source. La vérification formelle de compilateurs est donc un complément indispensable à la vérification de code source.L'une des tâches les plus complexes de compilation est l'allocation de registres. C'est lors de celle-ci que le compilateur décide de la façon dont les variables du programme sont stockées en mémoire durant son exécution. La mémoire comporte deux types de conteneurs : les registres, zones d'accès rapide, présents en nombre limité, et la pile, de capacité supposée suffisamment importante pour héberger toutes les variables d'un programme, mais à laquelle l'accès est bien plus lent. Le but de l'allocation de registres est de tirer au mieux parti de la rapidité des registres, car une allocation de registres de bonne qualité peut conduire à une amélioration significative du temps d'exécution du programme.Le modèle le plus connu de l'allocation de registres repose sur la coloration de graphe d'interférence-affinité. Dans cette thèse, l'objectif est double : d'une part vérifier formellement des algorithmes connus d'allocation de registres par coloration de graphe, et d'autre part définir de nouveaux algorithmes optimisants pour cette étape de compilation. Nous montrons tout d'abord que l'assistant à la preuve Coq est adéquat à la formalisation d'algorithmes d'allocation de registres par coloration de graphes. Nous procédons ainsi à la vérification formelle en Coq d'un des algorithmes les plus classiques d'allocation de registres par coloration de graphes, l'Iterated Register Coalescing (IRC), et d'une généralisation de celui-ci permettant à un utilisateur peu familier du système Coq d'implanter facilement sa propre variante de cet algorithme au seul prix d'une éventuelle perte d'efficacité algorithmique. Ces formalisations nécessitent des réflexions autour de la formalisation des graphes d'interférence-affinité, de la traduction sous forme purement fonctionnelle d'algorithmes impératifs et de l'efficacité algorithmique, la terminaison et la correction de cette version fonctionnelle. Notre implantation formellement vérifiée de l'IRC a été intégrée à un prototype du compilateur CompCert.Nous avons ensuite étudié deux représentations intermédiaires de programmes, dont la forme SSA, et exploité leurs propriétés pour proposer de nouvelles approches de résolution optimale de la fusion, l'une des optimisations opéréeslors de l'allocation de registres dont l'impact est le plus fort sur la qualité du code compilé. Ces approches montrent que des critères de fusion tenant compte de paramètres globaux du graphe d'interférence-affinité, tels que sa largeur d'arbre, ouvrent la voie vers de nouvelles méthodes de résolution potentiellement plus performantes. / The need for trustful programs led to an increasing use of formal verication techniques the last decade, and especially of program proof. However, the code running on the computer is not the source code, i.e. the one written by the developper, since it has to betranslated by the compiler. As a result, the formal verication of compilers is required to complete the source code verication. One of the hardest phases of compilation is register allocation. Register allocation is the phase within which the compiler decides where the variables of the program are stored in the memory during its execution. The are two kinds of memory locations : a limited number of fast-access zones, called registers, and a very large but slow-access stack. The aim of register allocation is then to make a great use of registers, leading to a faster runnable code.The most used model for register allocation is the interference graph coloring one. In this thesis, our objective is twofold : first, formally verifying some well-known interference graph coloring algorithms for register allocation and, second, designing new graph-coloring register allocation algorithms. More precisely, we provide a fully formally veri ed implementation of the Iterated Register Coalescing, a very classical graph-coloring register allocation heuristics, that has been integrated into the CompCert compiler. We also studied two intermediate representations of programs used in compilers, and in particular the SSA form to design new algorithms, using global properties of the graph rather than local criteria currently used in the litterature.

Les avancées récentes de la recherche dans le domaine de la virtualisation des réseaux ainsi que l'émergence de nouveaux acteurs, ont beaucoup motivé la recherche et le développement de nouvelles approches et techniques permettant de relever les défis de l'Internet du Futur. Cette thèse a été motivée par ces avancées et par le besoin de concevoir une architecture d'allocation de réseaux virtuels à la demande à partir d'une infrastructure physique partagée. L'objectif de la thèse était, par conséquent, de concevoir et développer des algorithmes d'optimisation et des méthodes d'allocation de ressources virtuelles pour composer et créer des réseaux virtuels selon les besoins des utilisateurs et les conditions du réseau physique partagé. Ce travail suppose l'existence d'un acteur tiers «broker», appelé fournisseur de réseau virtuel, responsable de négocier et d'allouer des ressources virtuelles, offertes comme des services par des fournisseurs d'infrastructures, et de créer et offrir des réseaux virtuels à la demande pour des utilisateurs. L'objectif de la thèse est donc de développer des mécanismes et des algorithmes de découverte (ou «matching»), de correspondance (ou «mapping») et d'instanciation de réseaux virtuels tout en optimisant l'utilisation des ressources du substrat d'une part, et en réduisant, d'autre part, le coût pour les fournisseurs. Dans une première partie, l'analyse et la comparaison de plusieurs algorithmes d'allocation de réseau virtuel proposés dans la littérature ont été menées. Les différentes phases d'allocation de réseaux virtuels comprenant le matching, le mapping et l'instanciation sont définies et explorées en considérant la présence de plusieurs fournisseurs d'infrastructures (multi-domaine). La deuxième partie de cette thèse porte sur la conception, le développement et l'évaluation des algorithmes heuristiques de découverte (matching) permettant la recherche de correspondance entre les besoins spécifiés par les requêtes de réseau virtuel et les propriétés fonctionnelles (ou statiques) des ressources disponibles du substrat physique. Des techniques de regroupement conceptuel sont utilisées pour faciliter et accélérer la découverte et le matching des ressources virtuelles. Des solutions de partitionnement exactes et heuristiques, basées sur des algorithmes de max-flow/min-cut et des techniques de programmation linéaire, sont également proposées et évaluées pour partitionner les requêtes de réseaux virtuels entre plusieurs fournisseurs d'infrastructures tout en réduisant les coûts. La troisième partie de la thèse se focalise sur la conception, le développement et l'évaluation des algorithmes de mapping heuristiques et exacts qui consistent à extraire un graphe de réseau virtuel à partir d'un graphe de substrat physique d'une manière optimale. Un algorithme de mapping heuristique et distribué, basé sur l'approche multi-agents, est développé et évalué permettant d'améliorer le passage à l'échelle et d'assurer une distribution de charge. Un autre algorithme de mapping exact est également modélisé comme étant un programme linéaire afin d'assurer une sélection optimale des ressources tout en réduisant les coûts et maximisant le taux d'acceptation des requêtes. Dans la dernière partie, des algorithmes d'allocation adaptative de réseaux virtuels sont proposés, développés et évalués pour maintenir des réseaux virtuels suite à des changements dynamiques au niveau des services demandés ou bien au niveau des infrastructures physiques. / Recent advances in computer and network virtualisation combined with the emergence of new actors and business models motivated much research and development of new approaches to face the challenges of future Internet architectures. This thesis was motivated by these advances and by the need for efficient algorithms and frameworks to allocate virtual resources and create on demand virtual networks over shared physical infrastructures. The objective of the thesis has consequently been to conceive and develop provisioning algorithms and methods to set up and maintain virtual networks according to user needs and networking conditions. The work assumes the existence of virtual network providers acting as brokers that request virtual resources, on behalf of users, from multiple infrastructure providers. The investigation and research objective is to explore how virtual resources, offered as a service by infrastructure providers, are allocated while optimising the use of substrate resources and reducing the cost for providers. This thesis starts off with the analysis and comparison of several virtual network provisioning approaches and algorithms proposed in the literature. Provisioning phases are defined and explored including resource matching, embedding and binding. The scenario where multiple infrastructure providers are involved in the virtual network provisioning is addressed and a mathematical model of the VN provisioning problem is formulated. The second part of this thesis provides the design, implementation and evaluation of exact and heuristic matching algorithms to search, find and match virtual network requests with available substrate resources. Conceptual clustering techniques are used to facilitate finding and matching of virtual resources in the initial provisioning phases. Exact and heuristic algorithms are also proposed and evaluated to efficiently split virtual network requests over multiple infrastructure providers while reducing the matching cost. The request splitting problem is solved using both max-flow min-cut algorithms and linear programming techniques. The third part of this thesis presents the design, implementation and evaluation of exact and heuristic embedding algorithms to simultaneously assign virtual nodes and links to substrate resources. A distributed embedding algorithm, relying on a multi-agent based approach, is developed for large scale networks. An exact embedding algorithm, formulated as a mixed integer program, is also proposed and evaluated to ensure optimal node and link mapping while reducing cost and increasing the acceptance ratio of requests. Finally, this thesis presents the design and development of adaptive provisioning frameworks and algorithms to maintain virtual networks subject to dynamic changes in services demands and in physical infrastructures. Adaptive matching and embedding algorithms are designed, developed and evaluated to repair resource failures and dynamically optimize substrate networks utilisation.

Dans les systèmes de communications sans fils, l'allocation de ressources reste toujours un défi considérable afin de satisfaire les demandes des utilisateurs et de fournir de bonnes performances avec une perpétuelle demande en applications gourmandes en ressources. Les techniques multiporteuses essentiellement les techniques dérivant de l'OFDM sont généralement utilisées pour transmettre les données dans des sous-porteuses orthogonales. De plus, de nouvelles stratégies de relayage sont proposées pour améliorer les performances en bordures de cellules. Plusieurs types de relais peuvent être sollicités comme les relais fixes faisant partie de l'infrastructure du système ou les relais mobiles qui ne nécessitent pas un coût additionnel de déploiement.Dans cette thèse, nous étudions principalement l'allocation des ressources pour le sens montant d'un système cellulaire OFDMA assurant les exigences de qualité de service et l'équité entre les utilisateurs. Les algorithmes d'allocation de ressources les plus utilisés sont présentés et un nouvel algorithme se basant sur l'équité proportionnelle pondérée (WPF) est proposé afin d'approcher les bornes supérieures de débit et d'équité. L'algorithme WPF propose un poids variable par utilisateur permettant d'allouer un nombre plus élevé de sous-porteuses au centre de la cellule qu'en bordure tout en gardant une bonne équité entre les utilisateurs. Nous établissons une étude théorique afin de comparer l'algorithme proposé à l'algorithme classique d'équité proportionnelle (PF). Nous étendons ensuite l'algorithme WPF à un système multi-cellulaire où l'interférence inter-cellulaire (ICI) dégrade les performances du système. Enfin, nous étudions les stratégies d'annulation de l'ICI et proposons une nouvelle méthode pour réduire l'ICI en se basant sur la coopération entre les stations de base (BSs) et sur les indicateurs d'interférence. Nous proposons un nouvel indicateur d'interférence (EII) à valeurs entières échangé par les BSs pour indiquer les niveaux d'interférence des sous-porteuses. En prenant en compte les valeurs de EII échangées, chaque BS alloue dynamiquement les sous-porteuses de manière à éviter de fortes valeurs d'ICI.Dans un deuxième temps, nous étudions la communication coopérative en utilisant des relais mobiles. Pour cela, de simples utilisateurs mobiles ayant des positions avantageuses peuvent relayer d'autres utilisateurs en bordure de cellule en plus de transmettre leurs propres données. Un relai utilisant le protocole DF multiplexe ainsi ses propres données aux données relayées avant de transmettre à la BS. L'allocation de ressource est formulée sous forme d'un problème d'optimisation dont le but est de minimiser la puissance totale d'émission du système tout en assurant un débit cible par utilisateur. Dans un premier temps, nous proposons une méthode de sélection des relais comme phase d'initialisation et offrons une heuristique itérative pour optimiser l'allocation de puissance et des blocs de ressources radio (RBs). Dans un second temps, nous traitons la sélection des relais comme une variable d'optimisation additionnelle. Pour la résolution, la décomposition de Lagrange et la méthode duale sont utilisées et le problème global est divisé en sous problèmes résolus de manière itérative afin d'approcher la solution optimale. Enfin, nous étendons ce modèle coopératif à un modèle à antennes multiples (MIMO) afin d'étudier l'influence des antennes multiples sur la puissance totale de transmission. Les paramètres à optimiser sont la sélection des relais, l'allocation des puissances et l'allocation des RBs. Afin d'allouer la puissance sur les antennes d'un utilisateur, nous avons étudié la répartition égale des puissance (EPA) et le beamforming. Les expressions théoriques correspondantes sont établies et les résultats de simulation sont présentés pour comparer le modèle avec EPA et le modèle avec beamforming au modèle non coopératif. / In wireless systems, resource allocation is still an important challenge to satisfy user requirements and to ensure good system performances with always greedy data applications. Multicarrier techniques especially the Orthogonal Frequency Division Multiplexing (OFDM) techniques are generally used to carry data into orthogonal subcarriers. Furthermore, relaying strategies are used to enhance cell edge performances. Many types of relays can be investigated as fix relays being part of the network infrastructure or mobile relays without additional deployment cost.In this thesis, we mainly consider the resource allocation for an uplink Orthogonal Frequency Division Multiple Access (OFDMA) system for a cellular system model ensuring Quality of Service (QoS) requirements and fairness between users. The most used resource allocation algorithms are presented and a novel Weighted Proportional Fair (WPF) algorithm is proposed to approach upper bounds of both throughput and fairness. The WPF algorithm considers user weights to allocate more subcarriers in the cell center than in the cell edge keeping sufficient fairness between users. We establish a theoretical analysis to compare the behavior of the proposed WPF algorithm to the classical Proportional Fair (PF) algorithm. Then, we extend this WPF algorithm to a multi-cell system model where the Inter-Cell Interference (ICI) limits the system performance. Moreover, we study ICI mitigation strategies and propose a novel method to reduce the ICI based on Base Station (BS) cooperation and interference indicators. We propose the Enhanced Interference Indicator (EII) with integer values to be exchanged by the BSs indicating interference levels for the subcarriers. Function of these communicated EII values, each BS allocates dynamically subcarriers in order to reduce the ICI. Our contributions in the multi-cell system model are the WPF and the EII.Moreover, we investigate in this dissertation the cooperative communication using mobile relays and propose multiple contributions. For this, simple mobile users with advantageous positions can relay cell edge users to carry data to the BS in addition to their own data. A Decode and Forward (DF) relay multiplex then its own data and relayed data before transmitting to the BS. The resource allocation is formulated as an optimization problem aiming to minimize the system transmit power and respecting a required target data rate per user constraint. In a first time, we propose an initialization method for the paring step to associate source-relay pairs and propose an iterative heuristic to optimize both power and Resource Blocks (RB) allocations. In a second time, we consider the relay selection as an optimization variable in addition of power and RB allocations. For resolution, Lagrangian decomposition and Dual method are used and the global problem is divided into subproblems iterativelly resolved to approach the optimal solution. Finally, we extend this cooperative system model to a Multiple Input Multiple Output (MIMO) system model to study the influence of multiple antennas on the system transmit power. The features to optimize are relay selection, power and RBs allocation. Moreover, to allocate power in the different antennas for each user, both Equal Power Allocation (EPA) and beamforming are studied. Theoretical expressions are established and simulations results are presented to compare EPA, beamforming and non-cooperative system.