1,721,018 research outputs found
Contents through Networks: wireless access, caching, social diffusion
No full textThis report presents the main findings of my scientific research after my PhD Thesis and especially in the last 8 years. During this period I have worked on three major topics, which span a wide spectrum of networking aspects: Cloud-RAN architecture for cellular networks, wireless edge-caching, and information diffusion in online social platforms. These relate to breakthroughs in communication networks during the last decade, considering the evolution towards 5G cellular networks and the proliferation of on-line social platforms. My research has resulted in original contributions in all three areas that advance the state of the art. In C-RAN architectures novel base station clustering mechanisms are proposed and the performance benefits from collaborative transmission is quantified for very large networks. In edge-caching new cache management policies are introduced that profit from multi-coverage, while user association and mobility is taken into account. Finally, in social networks an original mathematical model combines user posting activity with graph structure to exactly describe user influence inside online platforms. This research was made possible with the collaboration of several PhD and Master students
How to group wireless nodes together?: A survey on Matchings and Nearest Neighbour Graphs
No full textThis is a survey on grouping methods for Point Processes. It contains some original material as well.This report presents a survey on how to group together in a static way planar nodes, that may belong to a wireless network (ad hoc or cellular). The aim is to identify appropriate methods that could also be applied for Point Processes. Specifically matching pairs and algorithms are initially discussed. Next, specifically for Point Processes, the Nearest Neighbour and Lilypond models are presented. Properties and results for the two models are stated. Original bounds are given for the value of the so-called generation number, which is related to the size of the nearest neighbour cluster. Finally, a variation of the nearest neighbour grouping is proposed and an original metric is introduced, named here the ancestor number. This is used to facilitate the analysis of the distribution of cluster size. Based on this certain related bounds are derived. The report and the analysis included show clearly the difficulty of working in point processes with static clusters of size greater than two, when these are defined by proximity criteria
Modellierung und Analyse von drahtlosen Kommunikationssystemen mit Automatischen Wiederholungsanfrage Protokollen
No full textThe focus of the current thesis is on the modeling, analysis and control of Automatic Retransmission reQuest (ARQ) protocols as part of a wireless communications system. The function of these protocols is the detection and correction of errors. To achieve this the receiver informs the transmitter over the result of packet decoding using a binary control signal ACK/NACK. The NACK triggers a retransmission of the erroneous packet, while an ACK informs the transmitter that the packet has been correctly received and the next packet awaiting in the buffer is prepared. A significant performance measure related to such protocols is the goodput, defined as the rate of correctly transmitted packets over the wireless link. Typically goodput is expressed as the product of scheduled transmission rate times the success probability, which results from renewal-reward theory assuming fixed probability distribution and ergodicity of the fading process. Alternative goodput measures for short term communications are suggested which are more appropriate in case the number of packets to be transmitted is finite. Fixing the success probability values per retransmission, by selecting a priori a retransmission policy, the evolution of an ARQ protocol can be described as a success run. A definition of reliability in communications is provided, which is related to the notion of delay limited capacity. It is proven that an ARQ protocol is reliable if and only if its transition probability matrix is ergodic. Conditions for ergodicity and non-ergodicity result in a categorization of ARQ protocols (and subsequently of power allocation policies per retransmission), into reliable and unreliable. Since in practical communications the ARQ protocols are always truncated and a packet dropping occurs when the maximum number of retransmissions is exceeded, the problem of optimal truncation has been investigated. The method utilizes optimal stopping arguments where the successful transmission of a packet is related to a reward, whereas the delay and power consumption are modeled as generalized costs. The system incurs additionaly a penalty when the packet is dropped. Optimal truncation length has resulted from the sequential analysis which provides a rule combining all the above costs and rewards into a simple inequality. ARQ protocols are of course related to queuing. Incorporating a retransmission protocol at the server of a queue brings additional delay to the buffered packets so that reliability of transmission can be guaranteed. To reduce delay certain packets can be dropped by interrupting the retransmission process. Applying dynamic programming the optimal dropping policy is derived. The decision to drop depends on the system state which is the pair of queue length and current retransmission effort. The resulting policies are optimal in the sense of minimizing the time average of a linear combination of queue length and number of dropped packets. A next step in the analysis is the power control of ARQ protocols in a downlink system. Data destined to a certain number of users are buffered at the base station. Each buffer uses the retransmission protocol to achieve reliablity, while the base station has a specific total power budget to divide among users at each time slot. Considering fixed transmission rate per user and taking interference into account, the stability region of the system is derived. A power allocation policy is shown to achieve this stability region and algorithms to compute the power per user are applied and compared. The work concludes with an investigation of an ad hoc wireless network, where data enter in different source nodes and should be routed through the system nodes to their destination. Errors occur per hop due to fading and interference. Each node is again equiped with an ARQ protocol for error correction. The stability region of the system is derived. Each data flow is related to a utility function and a network utility maximization problem with stability constraints is formulated. Its solution provides the optimal per slot congestion control, routing and power allocation policy to maximize the sum of utilities while keeping all buffers in the system finite. The requirement that the power allocation policies should be implemented in a decentralized manner can be fulfilled if cooperation between nodes is allowed and at the same time each node performs measurements to estimate its interference level. Applying game theory and using the above information, each node can choose an optimal power to transmit
SlateFree: a Model-Free Decomposition for Reinforcement Learning with Slate Actions
No full textWe consider the problem of sequential recommendations, where at each step an agent proposes some slate of N distinct items to a user from a much larger catalog of size K >> N. The user has unknown preferences towards the recommendations and the agent takes sequential actions that optimise (in our case minimise) some user-related cost, with the help of Reinforcement Learning. The possible item combinations for a slate is N-over-K, an enormous number rendering value iteration methods intractable. We prove that the slate-MDP can actually be decomposed using just K item-related Q functions per state, which describe the problem in a more compact and efficient way. Based on this, we propose a novel model-free SARSA and Q-learning algorithm that performs N parallel iterations per step, without any prior user knowledge. We call this method SlateFree, i.e. free-ofslates, and we show numerically that it converges very fast to the exact optimum for arbitrary user profiles, and that it outperforms alternatives from the literature
Cooperative communications in very large cellular networks
No full textDivers études ont abordé le problème de la coopération d’un réseau cellulaire, dont certaines considèrent aléatoirement le positionnement des antennes. Plusieurs auteurs étudient le cas où l’utilisateur choisit les antennes qui le serviront. Pourtant, cette hypothèse n'est pas réaliste. En conséquence, d’autres auteurs proposent former les groupes d'antennes de façon statique. Pour que ces méthodologies soient optimales, ces groupes statiques devraient être formés par rapport à la proximité entre les nœuds. Nous proposons une méthodologie statique basée sur le modèle du plus proche. À l'aide de celle-ci, nous formons des singletons et des paires de nœuds coopératives. Nous fournissons alors une analyse des caractéristiques structurelles et de l'interférence produite par ces deux derniers processus ponctuels. Lorsque le positionnement des antennes suit une loi de Poisson, les processus de singletons de paires associées ne suivent pas une loi de Poisson. Nous pouvons, cependant, rapprocher des métriques de performance du modèle original à l'aide de la superposition de deux processus de Poisson. L’évaluation numériques montre des gains de couverture allant jusqu’à 15 %, en comparaison du modèle non coopératif. Pour que la coopération entre les antennes soit significative, chacune devrait avoir un nombre de ressources suffisante, en plus d'être suffisamment proches. La relation de voisin le plus proche est, alors, redéfinie avec une nouvelle métrique. Les résultats de notre analyse montrent que les gains d’un réseau coopératif dépendent fortement de la distribution des ressources disponibles dans tout le réseau.Recent studies have set the problem of base station cooperation within the framework of stochastic geometry, where the irregularity of the base station positions can be considered. Some authors study the case when the user can dynamically choose the set of stations cooperating for its service. This assumption is not realistic. Instead, other authors propose to form the groups in a static way. To be optimal, these static methodologies should consider proximity between the base stations to form the groups. We propose a grouping method based on the nearest neighbor model. We allow the formation of singles and pairs of nodes. We derive structural characteristics for these two processes and analyse the resulting interference fields. When the node positions are modelled by a Poisson point process, the processes of singles and pairs are not Poisson, complicating the corresponding analysis. The performance of the original model, however, can be approximated by the superposition of two Poisson point processes. Numerical evaluation shows coverage gains from different signal cooperation that can reach up to 15%, compared with the standard noncooperative case. For the cooperation to be meaningful, each station in a group should have sufficient resources to share, besides being close to each other. Thus, we redefine the nearest neighbors with a metric. The results of our analysis illustrate that cooperation gains strongly depend on the distribution of the available resources over the network
Stochastic modeling and data analysis for information dissemination in online social platforms
No full textLe marketing d'influenceurs est devenu une industrie florissante dont la valeur du marché mondial devrait atteindre 15 milliards de dollars d'ici 2022. Le problème publicitaire auquel ces agences sont confrontées est le suivant : compte tenu d'un budget monétaire, trouver un ensemble d'influenceurs appropriés qui peuvent créer et publier des posts de différents types (par exemple, texte, image, vidéo) pour la promotion d'un produit cible. L'objectif de la campagne est de maximiser à travers une ou plusieurs plateformes sociales en ligne une certaine mesure d'impact d'intérêt, par exemple le nombre d'impressions, les ventes (ROI), ou la portée de l'audience. Dans cette thèse, nous créons des formulations continues originales du problème du marketing d'influence budgétisé par deux cadres, un statique et un dynamique, basés sur la connaissance de l'annonceur de la métrique d'impact, et la nature des décisions de l'annonceur sur un horizon temporel. Le modèle statique est formulé comme un programme convexe, et nous proposons un algorithme itératif efficace basé sur la méthode de Frank-Wolfe, qui converge vers l'optimum global et présente une faible complexité de calcul. Nous suggérons également une règle empirique quasi-optimale plus simple, qui peut donner de bons résultats dans de nombreux scénarios pratiques. En raison de la nature du modèle dynamique, nous ne pouvons plus résoudre un problème de maximisation de l'utilité du réseau, puisque le retour sur investissement est inconnu, éventuellement bruyant, continu et coûteux à évaluer pour l'annonceur. Cette approche implique une exploration et nous cherchons donc à nous assurer qu'il n'y a pas d'exploration destructive, et que chaque décision séquentielle de l'annonceur améliore le résultat du ROI au fil du temps. Dans cette approche, nous proposons un nouvel algorithme et une nouvelle implémentation, basés sur le cadre d'optimisation bayésienne pour résoudre notre problème de marketing d'influence budgétisé sous des décisions séquentielles de l'annonceur sur un horizon temporel. En outre, nous proposons une observation empirique pour éviter la malédiction de la dimensionnalité. Nous testons notre modèle statique, l'algorithme et l'heuristique contre plusieurs alternatives de la littérature d'optimisation ainsi que des méthodes de sélection de graines standard et nous validons la performance supérieure de Frank-Wolfe en temps d'exécution et en mémoire, ainsi que sa capacité à s'adapter à des problèmes avec un très grand nombre (millions) d'utilisateurs sociaux. Enfin, nous évaluons notre modèle dynamique sur une trace réelle de données et nous concluons à la faisabilité de notre modèle et au soutien empirique de notre observation formulée.Influencer marketing has become a thriving industry with a global market value expected to reach 15 billion dollars by 2022. The advertising problem that such agencies face is the following: given a monetary budget find a set of appropriate influencers that can create and publish posts of various types (e.g. text, image, video) for the promotion of a target product. The campaign's objective is to maximize across one or multiple online social platforms some impact metric of interest, e.g. number of impressions, sales (ROI), or audience reach. In this thesis, we create original continuous formulations of the budgeted influence marketing problem by two frameworks, a static and a dynamic one, based on the advertiser's knowledge of the impact metric, and the nature of the advertiser's decisions over a time horizon. The static model is formulated as a convex program, and we further propose an efficient iterative algorithm based on the Frank-Wolfe method, that converges to the global optimum and has low computational complexity. We also suggest a simpler near-optimal rule of thumb, which can perform well in many practical scenarios. Due to the nature of the dynamic model we cannot solve any more a Network Utility Maximisation problem since that the ROI is unknown, possibly noisy, continuous and costly to evaluate for the advertiser. This approach involves exploration and so, we seek to ensure that there is no destructive exploration, and that each sequential decision by the advertiser improves the outcome of the ROI over time. In this approach, we propose a new algorithm and a new implementation, based on the Bayesian optimization framework to solve our budgeted influence marketing problem under sequential advertiser's decisions over a time horizon. Besides, we propose an empirical observation to avoid the curse of dimensionality. We test our static model, algorithm and the heuristic against several alternatives from the optimization literature as well as standard seed selection methods and validate the superior performance of Frank-Wolfe in execution time and memory, as well as its capability to scale well for problems with very large number (millions) of social users. Finally, we evaluate our dynamic model on a real Twitter data trace and we conclude the feasibility of our model and empirical support of our formulated observation
- …
