Abstract The application of optimization techniques for resource management in wireless communication networks is considered in this thesis. It is understood that a wide variety of resource management problems of recent interest, including power/rate control, link scheduling, cross-layer control, network utility maximization, beamformer design of multiple-input multiple-output networks, and many others are directly or indirectly reliant on the general weighted sum-rate maximization (WSRMax) problem. Thus, in this dissertation a greater emphasis is placed on the WSRMax problem, which is known to be NP-hard. A general method, based on the branch and bound technique, is developed, which solves globally the nonconvex WSRMax problem with an optimality certificate. Efficient analytic bounding techniques are derived as well. More broadly, the proposed method is not restricted to WSRMax. It can also be used to maximize any system performance metric, which is Lipschitz continuous and increasing on signal-to-interference-plus-noise ratio. The method can be used to find the optimum performance of any network design method, which relies on WSRMax, and therefore it is also useful for evaluating the performance loss encountered by any heuristic algorithm. The considered link-interference model is general enough to accommodate a wide range of network topologies with various node capabilities, such as singlepacket transmission, multipacket transmission, simultaneous transmission and reception, and many others. Since global methods become slow in large-scale problems, fast local optimization methods for the WSRMax problem are also developed. First, a general multicommodity, multichannel wireless multihop network where all receivers perform singleuser detection is considered. Algorithms based on homotopy methods and complementary geometric programming are developed for WSRMax. They are able to exploit efficiently the available multichannel diversity. The proposed algorithm, based on homotopy methods, handles efficiently the self interference problem that arises when a node transmits and receives simultaneously in the same frequency band. This is very important, since the use of supplementary combinatorial constraints to prevent simultaneous transmissions and receptions of any node is circumvented. In addition, the algorithm together with the considered interference model, provide a mechanism for evaluating the gains when the network nodes employ self interference cancelation techniques with different degrees of accuracy. Next, a similar multicommodity wireless multihop network is considered, but all receivers perform multiuser detection. Solutions for the WSRMax problem are obtained by imposing additional constraints, such as that only one node can transmit to others at a time or that only one node can receive from others at a time. The WSRMax problem of downlink OFDMA systems is also considered. A fast algorithm based on primal decomposition techniques is developed to jointly optimize the multiuser subcarrier assignment and power allocation to maximize the weighted sum-rate (WSR). Numerical results show that the proposed algorithm converges faster than Lagrange relaxation based methods. Finally, a distributed algorithm for WSRMax is derived in multiple-input single-output multicell downlink systems. The proposed method is based on classical primal decomposition methods and subgradient methods. It does not rely on zero forcing beamforming or high signal-to-interference-plus-noise ratio approximation like many other distributed variants. The algorithm essentially involves coordinating many local subproblems (one for each base station) to resolve the inter-cell interference such that the WSR is maximized. The numerical results show that significant gains can be achieved by only a small amount of message passing between the coordinating base stations, though the global optimality of the solution cannot be guaranteed. / Tiivistelmä Tässä työssä tutkitaan optimointimenetelmien käyttöä resurssienhallintaan langattomissa tiedonsiirtoverkoissa. Monet ajankohtaiset resurssienhallintaongelmat, kuten esimerkiksi tehonsäätö, datanopeuden säätö, radiolinkkien ajastus, protokollakerrosten välinen optimointi, verkon hyötyfunktion maksimointi ja keilanmuodostus moniantenniverkoissa, liittyvät joko suoraan tai epäsuorasti painotetun summadatanopeuden maksimointiongelmaan (weighted sum-rate maximization, WSRMax). Tästä syystä tämä työ keskittyy erityisesti WSRMax-ongelmaan, joka on tunnetusti NP-kova. Työssä kehitetään yleinen branch and bound -tekniikkaan perustuva menetelmä, joka ratkaisee epäkonveksin WSRMax-ongelman globaalisti ja tuottaa todistuksen ratkaisun optimaalisuudesta. Työssä johdetaan myös tehokkaita analyyttisiä suorituskykyrajojen laskentatekniikoita. Ehdotetun menetelmän käyttö ei rajoitu vain WSRMax-ongelmaan, vaan sitä voidaan soveltaa minkä tahansa suorituskykymetriikan maksimointiin, kunhan se on Lipschitz-jatkuva ja kasvava signaali-häiriö-plus-kohinasuhteen funktiona. Menetelmää voidaan käyttää minkä tahansa WSRMax-ongelmaan perustuvan verkkosuunnittelumenetelmän optimaalisen suorituskyvyn määrittämiseen, ja siksi sitä voidaan hyödyntää myös minkä tahansa heuristisen algoritmin aiheuttaman suorituskykytappion arvioimiseen. Tutkittava linkki-häiriömalli on riittävän yleinen monien erilaisten verkkotopologioiden ja verkkosolmujen kyvykkyyksien mallintamiseen, kuten esimerkiksi yhden tai useamman datapaketin siirtoon sekä yhtäaikaiseen lähetykseen ja vastaanottoon. Koska globaalit menetelmät ovat hitaita suurien ongelmien ratkaisussa, työssä kehitetään WSRMax-ongelmalle myös nopeita paikallisia optimointimenetelmiä. Ensiksi käsitellään yleistä useaa eri yhteyspalvelua tukevaa monikanavaista langatonta monihyppyverkkoa, jossa kaikki vastaanottimet suorittavat yhden käyttäjän ilmaisun, ja kehitetään algoritmeja, joiden perustana ovat homotopiamenetelmät ja komplementaarinen geometrinen optimointi. Ne hyödyntävät tehokkaasti saatavilla olevan monikanavadiversiteetin. Esitetty homotopiamenetelmiin perustuva algoritmi käsittelee tehokkaasti itsehäiriöongelman, joka syntyy, kun laite lähettää ja vastaanottaa samanaikaisesti samalla taajuuskaistalla. Tämä on tärkeää, koska näin voidaan välttää lisäehtojen käyttö yhtäaikaisen lähetyksen ja vastaanoton estämiseksi. Lisäksi algoritmi yhdessä tutkittavan häiriömallin kanssa auttaa arvioimaan, paljonko etua saadaan, kun laitteet käyttävät itsehäiriön poistomenetelmiä erilaisilla tarkkuuksilla. Seuraavaksi tutkitaan vastaavaa langatonta monihyppyverkkoa, jossa kaikki vastaanottimet suorittavat monen käyttäjän ilmaisun. Ratkaisuja WSRMax-ongelmalle saadaan asettamalla lisäehtoja, kuten että vain yksi lähetin kerrallaan voi lähettää tai että vain yksi vastaanotin kerrallaan voi vastaanottaa. Edelleen tutkitaan WSRMax-ongelmaa laskevalla siirtotiellä OFDMA-järjestelmässä, ja johdetaan primaalihajotelmaan perustuva nopea algoritmi, joka yhteisoptimoi monen käyttäjän alikantoaalto- ja tehoallokaation maksimoiden painotetun summadatanopeuden. Numeeriset tulokset osoittavat, että esitetty algoritmi suppenee nopeammin kuin Lagrangen relaksaatioon perustuvat menetelmät. Lopuksi johdetaan hajautettu algoritmi WSRMax-ongelmalle monisoluisissa moniantennilähetystä käyttävissä järjestelmissä laskevaa siirtotietä varten. Esitetty menetelmä perustuu klassisiin primaalihajotelma- ja aligradienttimenetelmiin. Se ei turvaudu nollaanpakotus-keilanmuodostukseen tai korkean signaali-häiriö-plus-kohinasuhteen approksimaatioon, kuten monet muut hajautetut muunnelmat. Algoritmi koordinoi monta paikallista aliongelmaa (yhden kutakin tukiasemaa kohti) ratkaistakseen solujen välisen häiriön siten, että WSR maksimoituu. Numeeriset tulokset osoittavat, että merkittävää etua saadaan jo vähäisellä yhdessä toimivien tukiasemien välisellä viestinvaihdolla, vaikka globaalisti optimaalista ratkaisua ei voidakaan taata.

Abstract The use of multiple antennas is a fundamental requirement in future wireless networks as it helps to increase the reliability and spectral efficiency of mobile radio links. In this thesis, we study convex optimization based radio resource allocation methods for the downlink of multi-antenna systems. First, the problem of admission control in the downlink of a multicell multiple-input single-output (MISO) system has been considered. The objective is to maximize the number of admitted users subject to a signal-to-interference-plus-noise ratio (SINR) constraint at each admitted user and a transmit power constraint at each base station (BS). We have cast the admission control problem as an ℓ0 minimization problem; it is known to be combinatorial, NP-hard. Centralized and distributed algorithms to solve this problem have been proposed. To develop the centralized algorithm, we have used sequential convex programming (SCP). The distributed algorithm has been derived by using the consensus-based alternating direction method of multipliers in conjunction with SCP. We have shown numerically that the proposed admission control algorithms achieve a near-to-optimal performance. Next, we have extended the admission control problem to provide fairness, where long-term fairness among the users has been guaranteed. We have focused on proportional and max-min fairness, and proposed dynamic control algorithms via Lyapunov optimization. Results show that these proposed algorithms guarantee fairness. Then, the problem of admission control for the downlink of a MISO heterogeneous networks (hetnet) has been considered, and the proposed centralized and distributed algorithms have been adapted to find a solution. Numerically, we have illustrated that the centralized algorithm achieves a near-to-optimal performance, and the distributed algorithm’s performance is closer to the optimal value. Finally, an algorithm to obtain the set of all achievable power-rate tuples for a multiple-input multiple-output hetnet has been provided. The setup consists of a single macrocell and a set of femtocells. The interference power to the macro users from the femto BSs has been kept below a threshold. To find the set of all achievable power-rate tuples, a two-dimensional vector optimization problem is formulated, where we have considered maximizing the sum-rate while minimizing the sum-power, subject to maximum power and interference threshold constraints. This problem is known to be NP-hard. A solution method is provided by using the relationship between the weighted sum-rate maximization and weighted-sum-mean-squared-error minimization problems. The proposed algorithm was used to evaluate the impact of imposing interference threshold constraints and the co-channel deployments in a hetnet. / Tiivistelmä Monen antennin käyttö on perusvaatimus tulevissa langattomissa verkoissa, koska se auttaa lisäämään matkaviestinyhteyksien luotettavuutta ja spektritehokkuutta. Tässä väitöskirjassa tutkitaan konveksiin optimointiin perustuvia radioresurssien allokointimenetelmiä moniantennijärjestelmien alalinkin suunnassa. Ensiksi on käsitelty pääsynvalvonnan ongelmaa alalinkin suuntaan monen solun moni-tulo yksi-lähtö (MISO) -verkoissa. Tavoitteena on maksimoida hyväksyttyjen käyttäjien määrä, kun hyväksytyille käyttäjille on asetettu signaali-häiriö-kohinasuhteen (SINR) rajoitus, ja tukiasemille lähetystehon rajoitus. Pääsynvalvonnan ongelma on muotoiltu ℓ0-minimointiongelmana, jonka tiedetään olevan kombinatorinen, NP-vaikea ongelma. Ongelman ratkaisemiseksi on ehdotettu keskitettyjä ja hajautettuja algoritmeja. Keskitetty optimointialgoritmi perustuu sekventiaaliseen konveksiin optimointiin. Hajautettu algoritmi pohjautuu konsensusoptimointimenetelmään ja sekventiaaliseen konveksiin optimointiin. Ehdotettujen pääsynvalvonta-algoritmien on numeerisesti osoitettu saavuttavan lähes optimaalinen suorituskyky. Lisäksi pääsynvalvontaongelma on laajennettu takaamaan pitkän aikavälin oikeudenmukaisuus käyttäjien välillä. Työssä käytetään erilaisia määritelmiä oikeudenmukaisuuden takaamiseen, ja ehdotetaan dynaamisia algoritmeja pohjautuen Lyapunov-optimointiin. Tulokset osoittavat, että ehdotetuilla algoritmeilla taataan käyttäjien välinen oikeudenmukaisuus. Tämän jälkeen käsitellään heterogeenisen langattoman MISO-verkon pääsynvalvonnan ongelmaa. Edellä ehdotettuja keskitettyjä ja hajautettuja algoritmeja on muokattu tämän ongelman ratkaisemiseksi. Työssä osoitetaan numeerisesti, että sekä keskitetyllä että hajautetulla algoritmilla saavutetaan lähes optimaalinen suorituskyky. Lopuksi on laadittu algoritmi, jolla löydetään kaikki saavutettavissa olevat teho-datanopeusparit heterogeenisessä langattomassa moni-tulo moni-lähtö (MIMO) -verkossa. Verkko koostuu yhdestä makrosolusta ja useasta piensolusta. Piensolutukiasemista makrokäyttäjiin kohdistuvan häiriön teho on pidetty tietyn rajan alapuolella. Kaikkien saavutettavien teho-datanopeusparien löytämiseksi on laadittu kaksiulotteinen vektorioptimointiongelma, jossa maksimoidaan summadatanopeus pyrkien minimoimaan kokonaisteho, kun enimmäisteholle ja häiriökynnykselle on asetettu rajoitukset. Tämän ongelman tiedetään olevan NP-vaikea. Ongelman ratkaisemiseksi käytetään painotetun summadatanopeuden maksimointiongelman, ja painotetun keskineliövirheen minimointiongelman välistä suhdetta. Ehdotettua algoritmia käytettiin arvioimaan häiriörajoitusten ja saman kanavan käyttöönoton vaikutusta heterogeenisessä langattomassa verkossa.

Les protocoles de consensus ont gagné beaucoup d’intérêt ces dernières années. Dans cette thèse, nous étudions les problèmes d’optimisation, de contrôle, et de théorie de jeu qui se posent dans ces protocoles. Tout d’abord, nous étudions les techniques d’optimisation pour des problèmes de sélection de poids permettant ainsi d’augmenter la vitesse de convergence de protocoles de consensus dans les réseaux. Nous proposons de sélectionner les poids en appliquant un algorithme d’approximation: minimisation de la norme p de Schatten de la matrice de poids. Nous caractérisons l’erreur induite par cette approximation et nous montrons que l’algorithme proposé a l’avantage qu’il peut être soit résolu de façon distribuée. Ensuite, nous proposons un cadre conceptuel d’analyse des jeux d’adversaire qui peut ajouter du bruit aux poids utilisés par l’algorithme de consensus de moyenne afin d’éloigner le système de consensus. Nous analysons également la performance des algorithmes de consensus de moyenne où les informations échangées entre les agents voisins sont soumises à la quantification uniforme déterministe (les valeurs réelles envoyées par les nœuds de leurs voisins sont tronquées). Le problème de la terminaison des protocoles de consensus s’avère difficile dans le cadre distribué. Nous proposons un algorithme distribué pour la terminaison des protocoles de consensus. L’algorithme réduit la charge de communication tout en garantissant la convergence vers un consensus. Enfin, nous proposons une mesure de similarité qui évalue la qualité d’un regroupement (clustering) des nœuds dans un réseau. Un algorithme local de clustering basé sur cette métrique est donné. / Consensus protocols have gained a lot of interest in the recent years. In this thesis, we study optimization, control, and game theoretical problems arising in consensus protocols. First, we study optimization techniques for weight selection problems to increase the speed of convergence of discrete-time consensus protocols on networks. We propose to select the weights by applying an approximation algorithm: minimizing the Schatten p-norm of the weight matrix. We characterize the approximation error and we show that the proposed algorithm has the advantage that it can be solved in a totally distributed way. Then we propose a game theoretical framework for an adversary that can add noise to the weights used by averaging protocols to drive the system away from consensus. We give the optimal strategies for the game players (the adversary and the network designer) and we show that a saddle-point equilibrium exists in mixed strategies. We also analyze the performance of distributed averaging algorithms where the information exchanged between neighboring agents is subject to deterministic uniform quantization (e.g., when real values sent by nodes to their neighbors are truncated). Consensus algorithms require that nodes exchange messages persistently to reach asymptotically consensus. We propose a distributed algorithm that reduces the communication overhead while still guaranteeing convergence to consensus. Finally, we propose a score metric that evaluates the quality of clusters such that the faster the random walk mixes in the cluster and the slower it escapes, the higher is the score. A local clustering algorithm based on this metric is proposed.

<div>In recent years, the amount of data in the information processing systems has significantly increased, which is also referred to as big-data. The design of systems handling big-data calls for a scalable approach, which brings distributed systems into the picture. In contrast to centralized systems, data are spread across the network of agents in the distributed system, and agents cooperatively complete tasks through local communications and local computations. However, the design and analysis of distributed systems, in which no central coordinators with complete information are present, are challenging tasks. In order to support communication among agents to enable multi-agent coordination among others, practical communication constraints should be taken into consideration in the design and analysis of such systems. The focus of this dissertation is to provide design and analysis of distributed network processing using finite-rate communications among agents. In particular, we address the following open questions: 1) can one design algorithms balancing a graph weight matrix using finite-rate and simplex communications among agents? 2) can one design algorithms computing the average of agents’ states using finite-rate and simplex communications? and 3) going beyond of ad-hoc algorithmic designs, can one design a black-box mechanism transforming a general class of algorithms with unquantized communication to their finite-bit quantized counterparts?</div><div><br></div><div>This dissertation addresses the above questions. First, we propose novel distributed algorithms solving the weight-balancing and average consensus problems using only finite-rate simplex communications among agents, compliant to the directed nature of the network topology. A novel convergence analysis is put forth, based on a new metric inspired by the</div><div>positional system representations. In the second half of this dissertation, distributed optimization subject to quantized communications is studied. Specifically, we consider a general class of linearly convergent distributed algorithms cast as fixed-point iterate, and propose a novel black-box quantization mechanism. In the proposed mechanism, a novel quantizer preserving linear convergence is proposed, which is proved to be more communication efficient than state-of-the-art quantization mechanisms. Extensive numerical results validate our theoretical findings.</div>

L'apprentissage des matrices de rang faible est un problème de grande importance dans les statistiques, l'apprentissage automatique, la vision par ordinateur et les systèmes de recommandation. En raison de sa nature NP-difficile, une des approches principales consiste à résoudre sa relaxation convexe la plus étroite : la minimisation de la norme de trace. Parmi les différents algorithmes capables de résoudre cette optimisation, on peut citer la méthode de Frank-Wolfe, particulièrement adaptée aux matrices de grande dimension. En préparation à l'utilisation d'infrastructures distribuées pour accélérer le calcul, cette étude vise à explorer la possibilité d'exécuter l'algorithme de Frank-Wolfe dans un réseau en étoile avec le modèle BSP (Bulk Synchronous Parallel) et à étudier son efficacité théorique et empirique. Concernant l'aspect théorique, cette étude revisite le taux de convergence déterministe de Frank-Wolfe et l'étend à des cas non déterministes. En particulier, il montre qu'avec le sous-problème linéaire résolu de manière appropriée, Frank-Wolfe peut atteindre un taux de convergence sous-linéaire à la fois en espérance et avec une probabilité élevée. Cette contribution pose la fondation théorique de l'utilisation de la méthode de la puissance itérée ou de l'algorithme de Lanczos pour résoudre le sous-problème linéaire de Frank-Wolfe associé à la minimisation de la norme de trace. Concernant l'aspect algorithmique, dans le cadre de BSP, cette étude propose et analyse quatre stratégies pour le sous-problème linéaire ainsi que des méthodes pour la recherche linéaire. En outre, remarquant la propriété de mise à jour de rang-1 de Frank-Wolfe, il met à jour le gradient de manière récursive, avec une représentation dense ou de rang faible, au lieu de le recalculer de manière répétée à partir de zéro. Toutes ces conceptions sont génériques et s'appliquent à toutes les infrastructures distribuées compatibles avec le modèle BSP. Concernant l'aspect empirique, cette étude teste les conceptions algorithmiques proposées dans un cluster Apache SPARK. Selon les résultats des expériences, pour le sous-problème linéaire, la centralisation des gradients ou la moyenne des vecteurs singuliers est suffisante dans le cas de faible dimension, alors que la méthode de la puissance itérée distribuée, avec aussi peu qu'une ou deux itérations par époque, excelle dans le cas de grande dimension. La librairie Python développée pour les expériences est modulaire, extensible et prête à être déployée dans un contexte industriel. Cette étude a rempli sa fonction de preuve de concept. Suivant le chemin qu'il met en place, des solveurs peuvent être implémentés pour différentes infrastructures, parmi lesquelles des clusters GPU, pour résoudre des problèmes pratiques dans des contextes spécifiques. En outre, ses excellentes performances dans le jeu de données ImageNet le rendent prometteur pour l'apprentissage en profondeur. / Learning low-rank matrices is a problem of great importance in statistics, machine learning, computer vision, recommender systems, etc. Because of its NP-hard nature, a principled approach is to solve its tightest convex relaxation : trace norm minimization. Among various algorithms capable of solving this optimization is the Frank-Wolfe method, which is particularly suitable for high-dimensional matrices. In preparation for the usage of distributed infrastructures to further accelerate the computation, this study aims at exploring the possibility of executing the Frank-Wolfe algorithm in a star network with the Bulk Synchronous Parallel (BSP) model and investigating its efficiency both theoretically and empirically. In the theoretical aspect, this study revisits Frank-Wolfe's fundamental deterministic sublinear convergence rate and extends it to nondeterministic cases. In particular, it shows that with the linear subproblem appropriately solved, Frank-Wolfe can achieve a sublinear convergence rate both in expectation and with high probability. This contribution lays the theoretical foundation of using power iteration or Lanczos iteration to solve the linear subproblem for trace norm minimization. In the algorithmic aspect, within the BSP model, this study proposes and analyzes four strategies for the linear subproblem as well as methods for the line search. Moreover, noticing Frank-Wolfe's rank-1 update property, it updates the gradient recursively, with either a dense or a low-rank representation, instead of repeatedly recalculating it from scratch. All of these designs are generic and apply to any distributed infrastructures compatible with the BSP model. In the empirical aspect, this study tests the proposed algorithmic designs in an Apache SPARK cluster. According to the experiment results, for the linear subproblem, centralizing the gradient or averaging the singular vectors is sufficient in the low-dimensional case, whereas distributed power iteration, with as few as one or two iterations per epoch, excels in the high-dimensional case. The Python package developed for the experiments is modular, extensible and ready to deploy in an industrial context. This study has achieved its function as proof of concept. Following the path it sets up, solvers can be implemented for various infrastructures, among which GPU clusters, to solve practical problems in specific contexts. Besides, its excellent performance in the ImageNet dataset makes it promising for deep learning.

Cette thèse porte essentiellement sur l'étude d'algorithmes d'optimisation. Les problèmes de programmation intervenant en apprentissage automatique ou en traitement du signal sont dans beaucoup de cas composites, c'est-à-dire qu'ils sont contraints ou régularisés par des termes non lisses. Les méthodes proximales sont une classe d'algorithmes très efficaces pour résoudre de tels problèmes. Cependant, dans les applications modernes de sciences des données, les fonctions à minimiser se représentent souvent comme une espérance mathématique, difficile ou impossible à évaluer. C'est le cas dans les problèmes d'apprentissage en ligne, dans les problèmes mettant en jeu un grand nombre de données ou dans les problèmes de calcul distribué. Pour résoudre ceux-ci, nous étudions dans cette thèse des méthodes proximales stochastiques, qui adaptent les algorithmes proximaux aux cas de fonctions écrites comme une espérance. Les méthodes proximales stochastiques sont d'abord étudiées à pas constant, en utilisant des techniques d'approximation stochastique. Plus précisément, la méthode de l'Equation Differentielle Ordinaire est adaptée au cas d'inclusions differentielles. Afin d'établir le comportement asymptotique des algorithmes, la stabilité des suites d'itérés (vues comme des chaines de Markov) est étudiée. Ensuite, des généralisations de l'algorithme du gradient proximal stochastique à pas décroissant sont mises au point pour resoudre des problèmes composites. Toutes les grandeurs qui permettent de décrire les problèmes à résoudre s'écrivent comme une espérance. Cela inclut un algorithme primal dual pour des problèmes régularisés et linéairement contraints ainsi qu'un algorithme d'optimisation sur les grands graphes. / This thesis mainly studies optimization algorithms. Programming problems arising in signal processing and machine learning are composite in many cases, i.e they exhibit constraints and non smooth regularization terms. Proximal methods are known to be efficient to solve such problems. However, in modern applications of data sciences, functions to be minimized are often represented as statistical expectations, whose evaluation is intractable. This cover the case of online learning, big data problems and distributed computation problems. To solve this problems, we study in this thesis proximal stochastic methods, that generalize proximal algorithms to the case of cost functions written as expectations. Stochastic proximal methods are first studied with a constant step size, using stochastic approximation techniques. More precisely, the Ordinary Differential Equation method is adapted to the case of differential inclusions. In order to study the asymptotic behavior of the algorithms, the stability of the sequences of iterates (seen as Markov chains) is studied. Then, generalizations of the stochastic proximal gradient algorithm with decreasing step sizes are designed to solve composite problems. Every quantities used to define the optimization problem are written as expectations. This include a primal dual algorithm to solve regularized and linearly constrained problems and an optimization over large graphs algorithm.

Media streaming over the Internet is becoming increasingly popular. Currently, most media is delivered using global content-delivery networks, providing a scalable and robust client-server model. However, content delivery infrastructures are expensive. One approach to reduce the cost of media delivery is to use peer-to-peer (P2P) overlay networks, where nodes share responsibility for delivering the media to one another. The main challenges in P2P media streaming using overlay networks include: (i) nodes should receive the stream with respect to certain timing constraints, (ii) the overlay should adapt to the changes in the network, e.g., varying bandwidth capacity and join/failure of nodes, (iii) nodes should be intentivized to contribute and share their resources, and (iv) nodes should be able to establish connectivity to the other nodes behind NATs. In this work, we meet these requirements by presenting P2P solutions for live media streaming, as well as proposing a distributed NAT traversal solution. First of all, we introduce a distributed market model to construct an approximately minimal height multiple-tree streaming overlay for content delivery, in gradienTv. In this system, we assume all the nodes are cooperative and execute the protocol. However, in reality, there may exist some opportunistic nodes,  free-riders, that take advantage of the system, without contributing to content distribution. To overcome this problem, we extend our market model in Sepidar to be effective in deterring free-riders. However, gradienTv and Sepidar are tree-based solutions, which are fragile in high churn and failure scenarios. We present a solution to this problem in GLive that provides a more robust overlay by replacing the tree structure with a mesh. We show in simulation, that the mesh-based overlay outperforms the multiple-tree overlay. Moreover, we compare the performance of all our systems with the state-of-the-art NewCoolstreaming, and observe that they provide better playback continuity and lower playback latency than that of NewCoolstreaming under a variety of experimental scenarios. Although our distributed market model can be run against a random sample of nodes, we improve its convergence time by executing it against a sample of nodes taken from the Gradient overlay. The Gradient overlay organizes nodes in a topology using a local utility value at each node, such that nodes are ordered in descending utility values away from a core of the highest utility nodes. The evaluations show that the streaming overlays converge faster when our market model works on top of the Gradient overlay. We use a gossip-based peer sampling service in our streaming systems to provide each node with a small list of live nodes. However, in the Internet, where a high percentage of nodes are behind NATs, existing gossiping protocols break down. To solve this problem, we present Gozar , a NAT-friendly gossip-based peer sampling service that: (i) provides uniform random samples in the presence of NATs, and (ii) enables direct connectivity to sampled nodes using a fully distributed NAT traversal service. We compare Gozar with the state-of-the-art NAT-friendly gossip-based peer sampling service, Nylon, and show that only Gozar supports one-hop NAT traversal, and its overhead is roughly half of Nylon’s.   / QC 20110517

Fueled by the rapid advancement in digital and wireless technologies, the ever-increasing capabilities of wireless devices have placed upon us a tremendous challenge - how to put all of this capability to effective use. Individually, wireless devices have outpaced the ability of users to optimally configure them. Collectively, the complexity is far more daunting. Research in cognitive networks seeks to provide a solution to the diffculty of effectively using the expanding capabilities of wireless networks by embedding greater degrees of intelligence within the network itself. In this dissertation, we address some fundamental questions related to cognitive networks, such as "What is a cognitive network?" and "What methods may be used to design a cognitive network?" We relate cognitive networks to a common artificial intelligence (AI) framework, the multi-agent system (MAS). We also discuss the key elements of learning and reasoning, with the ability to learn being the primary differentiator for a cognitive network. Having discussed some of the fundamentals, we proceed to further illustrate the cognitive networking principle by applying it to two problems: multichannel topology control for dynamic spectrum access (DSA) and routing in a mobile ad hoc network (MANET). The multichannel topology control problem involves confguring secondary network parameters to minimize the probability that the secondary network will cause an outage to a primary user in the future. This requires the secondary network to estimate an outage potential map, essentially a spatial map of predicted primary user density, which must be learned using prior observations of spectral occupancy made by secondary nodes. Due to the complexity of the objective function, we provide a suboptimal heuristic and compare its performance against heuristics targeting power-based and interference-based topology control objectives. We also develop a genetic algorithm to provide reference solutions since obtaining optimal solutions is impractical. We show how our approach to this problem qualifies as a cognitive network. In presenting our second application, we address the role of network state observations in cognitive networking. Essentially, we need a way to quantify how much information is needed regarding the state of the network to achieve a desired level of performance. This question is applicable to networking in general, but becomes increasingly important in the cognitive network context because of the potential volume of information that may be desired for decision-making. In this case, the application is routing in MANETs. Current MANET routing protocols are largely adapted from routing algorithms developed for wired networks. Although optimal routing in wired networks is grounded in dynamic programming, the critical assumption, static link costs and states, that enables the use of dynamic programming for wired networks need not apply to MANETs. We present a link-level model of a MANET, which models the network as a stochastically varying graph that possesses the Markov property. We present the Markov decision process as the appropriate framework for computing optimal routing policies for such networks. We then proceed to analyze the relationship between optimal policy and link state information as a function of minimum distance from the forwarding node. The applications that we focus on are quite different, both in their models as well as their objectives. This difference is intentional and signficant because it disassociates the technology, i.e. cognitive networks, from the application of the technology. As a consequence, the versatility of the cognitive networks concept is demonstrated. Simultaneously, we are able to address two open problems and provide useful results, as well as new perspective, on both multichannel topology control and MANET routing. This material is posted here with permission from the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of Virginia Tech library's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this material, you agree to all provisions of the copyright laws protecting it. / Ph. D.

Distributed optimization over multi-agent networks has become an increasingly popular research topic as it incorporates many applications from various areas such as consensus optimization, distributed control, network resource allocation, large scale machine learning, etc. Parallel distributed solution algorithms are highly desirable as they are more scalable, more robust against agent failure, align more naturally with either underlying agent network topology or big-data parallel computing framework. In this dissertation, we consider a multi-agent optimization formulation where the global objective function is the summation of individual local objective functions with respect to local agents' decision variables of different dimensions, and the constraints include both local private constraints and shared coupling constraints. Employing and extending tools from the monotone operator theory (including resolvent operator, operator splitting, etc.) and fixed point iteration of nonexpansive, averaged operators, a series of distributed solution approaches are proposed, which are all iterative algorithms that rely on parallel agent level local updates and inter-agent coordination. Some of the algorithms require synchronizations across all agents for information exchange during each iteration while others allow asynchrony and delays. The algorithms' convergence to an optimal solution if one exists are established by first characterizing them as fixed point iterations of certain averaged operators under certain carefully designed norms, then showing that the fixed point sets of these averaged operators are exactly the optimal solution set of the original multi-agent optimization problem. The effectiveness and performances of the proposed algorithms are demonstrated and compared through several numerical examples.<br>

De nos jours, les informations liées au déplacement et à la mobilité dans un réseau de transport représentent sans aucun doute un potentiel important.Ces travaux visent à mettre en œuvre un Système d’Information de Service d’Aide à la Mobilité Urbaine (SISAMU).Le SISAMU doit pouvoir procéder par des processus de décomposition des requêtes simultanées en un ensemble de tâches indépendantes. Chaque tâche correspond à un service qui peut être proposé par plusieurs fournisseurs d’information en concurrence, avec différents coûts, temps de réponse et formats. Le SISAMU est lié à un Réseau informatique Etendu et distribué de Transport Multimodal (RETM) qui comporte plusieurs sources d’information hétérogènes des différents services proposés aux utilisateurs de transport. L’aspect dynamique, distribué et ouvert du problème, nous a conduits à adopter une modélisation multi-agent pour assurer au système une évolution continue et une flexibilité pragmatique. Pour ce faire, nous avons proposé d’automatiser la modélisation des services en utilisant la notion d’ontologie. Notre SISAMU prend en considération les éventuelles perturbations sur le RETM.Ansi, nous avons créé un protocole de négociation entre les agents. Le protocole de négociation proposé qui utilise l’ontologie de la cartographie se base sur un système de gestion des connaissances pour soutenir l'hétérogénéité sémantique. Nous avons détaillé l’Algorithme de Reconstruction Dynamique des Chemins des Agents (ARDyCA) qui est basé sur l’approche de l’ontologie cartographique. Finalement, les résultats présentés dans cette thèse justifient l’utilisation de l’ontologie flexible et son rôle dans le processus de négociation / Nowadays, information related on displacement and mobility in a transport network represents certainly a significant potential. So, this work aims to modeling, to optimize and to implement an Information System of Services to Aid the Urban Mobility (ISSAUM).The ISSAUM has firstly to decompose each set of simultaneous requests into a set of sub-requests called tasks. Each task corresponds to a service which can be proposed different by several information providers with different. An information provider which aims to propose some services through our ISSAUM has to register its ontology. Indeed, ISSAUM is related to an Extended and distributed Transport Multimodal Network (ETMN) which contains several heterogeneous data sources. The dynamic and distributed aspects of the problem incite us to adopt a multi-agent approach to ensure a continual evolution and a pragmatic flexibility of the system. So, we proposed to automate the modeling of services by using ontology idea. Our ISSAUM takes into account possible disturbance through the ETMN. In order to satisfy user requests, we developed a negotiation protocol between our system agents. The proposed ontology mapping negotiation model based on the knowledge management system for supporting the semantic heterogeneity and it organized as follow: Negotiation Layer (NL), the Semantic Layer (SEL), and the Knowledge Management Systems Layer(KMSL).We detailed also the reassignment process by using Dynamic Reassigned Tasks (DRT) algorithm supporting by ontology mapping approach. Finally, the experimental results presented in this thesis, justify the using of the ontology solution in our system and its role in the negotiation process