1 |
Online Optimization for Edge Computing under Uncertainty in Wireless NetworksLee, Gilsoo 24 April 2020 (has links)
Edge computing is an emerging technology that can overcome the limitations of centralized cloud computing by enabling distributed, low-latency computation at a network edge. Particularly, in edge computing, some of the cloud's functionalities such as storage, processing, and computing are migrated to end-user devices called edge nodes so as to reduce the round-trip delay needed to reach the cloud data center. Despite the major benefits and practical applications of using edge computing, one must address many technical challenges that include edge network formation, computational task allocation, and radio resource allocation, while considering the uncertainties innate in edge nodes, such as incomplete future information on their wireless channel gains and computing capabilities. The goal of this dissertation is to develop foundational science for the deployment, performance analysis, and low-complexity optimization of edge computing under the aforementioned uncertainties. First, the problems of edge network formation and task distribution are jointly investigated while considering a hybrid edge-cloud architecture under uncertainty on the arrivals of computing tasks. In particular, a novel online framework is proposed to form an edge network, distribute the computational tasks, and update a target competitive ratio defined as the ratio between the latency achieved by the proposed online algorithm and the optimal latency. The results show that the proposed framework achieves the target competitive ratio that is affected by the wireless data rate and computing speeds of edge nodes. Next, a new notion of ephemeral edge computing is proposed in which edge computing must occur under a stringent requirement on the total computing time period available for the computing process. To maximize the number of computed tasks in ephemeral edge networks under the uncertainty on future task arrivals, a novel online framework is proposed to enable a source edge node to offload computing tasks from sensors and allocate them to neighboring edge nodes for distributed task computing, within the limited total time period. Then, edge computing is applied for mobile blockchain and online caching systems, respectively. First, a mobile blockchain framework is designed to use edge devices as mobile miners, and the performance is analyzed in terms of the probability of forking event and energy consumption. Second, an online computational caching framework is designed to minimize the edge network latency. The proposed caching framework enables each edge node to store intermediate computation results (IRs) from previous computations and download IRs from neighboring nodes under uncertainty on future computation. Subsequently, online optimization is extended to investigate other edge networking applications. In particular, the problem of online ON/OFF scheduling of self-powered small cell base stations is studied, in the presence of energy harvesting uncertainty with the goal of minimizing the operational costs that consist of energy consumption and transmission delay of a network. Such a framework can enable the self-powered base stations to be functioned as energy-efficient edge nodes. Also, the problem of radio resource allocation is studied when a base station is assisted by self-powered reconfigurable intelligent surfaces (RIS). To this end, a deep reinforcement learning approach is proposed to jointly optimize the transmit power, phase shifting, and RIS reflector's ON/OFF states under the uncertainties on the downlink wireless channel information and the harvested energy at the RIS. Finally, the online problem of dynamic channel allocation is studied for full-duplex device-to-device (D2D) networks so that D2D users can share their data with a low communication latency when users dynamically arrive on the network. In conclusion, the analytical foundations and frameworks presented in this dissertation will provide key guidelines for effective design of edge computing in wireless networks. / Doctor of Philosophy / Smart cities will rely on an Internet of Things (IoT) system that interconnects cars, drones, sensors, home appliances, and other digital devices. Modern IoT systems are inherently designed to process real-time information such as temperature, humidity, or even car navigational data, at any time and location. A unique challenge in the design of such an IoT is the need to process large volumes of data over a wireless network that consists of heterogeneous IoT devices such as smartphones, vehicles, home access points, robots, and drones. These devices must perform local (on-device or so-called edge) processing of their data without relying on a remote cloud. This vision of a smart city seen as a mobile computing platform gives rise to the emerging concept of edge computing using which smartphones, sensors, vehicles, and drones can exchange and process data locally on their own devices. Edge computing allows overcoming the limitations of centralized cloud computation by enabling distributed, low-latency computation at the network edge.
Despite the promising opportunities of edge computing as an enabler for smart city services such as autonomous vehicles, drones, or smart homes, one must address many challenges related to managing time-varying resources such as energy and storage, in a dynamic way. For instance, managing communication, energy, and computing resources in an IoT requires handling many uncertain factors such as the intermittent availability of wireless connectivity and the fact that the devices do not know a priori what type of tasks they need to process. The goal of this dissertation is to address the fundamental challenges in edge computing under uncertainty in an IoT. In particular, this dissertation introduces novel mathematical algorithms and frameworks that exploit ideas from the fields of online optimization, machine learning, and wireless communication to enable future IoT services such as smart factories, virtual reality, and autonomous systems. In this dissertation, holistic frameworks are developed by designing, analyzing, and optimizing wireless communications systems with an emphasize on emerging IoT applications. To this end, various mathematical frameworks and efficient algorithms are proposed by drawing on tools from wireless communications, online optimization, and machine learning to yield key innovations. The results show that the developed solutions can enable an IoT to operate efficiently in presence of uncertainty stemming from time-varying dynamics such as mobility of vehicles or changes in the wireless networking environment. As such, the outcomes of this research can be used as a building block for the large deployment of smart city technologies that heavily rely on the IoT.
|
2 |
Peak-seeking control of propulsion systemsCazenave, Timothee 10 July 2012 (has links)
Propulsion systems like Turboprop engines are generally designed to operate at a narrow range of optimum steady state performance conditions. However, these conditions are likely to vary in an unpredictable manner according to factors such as components aging, structural damages or even the operating environment. Over time, inefficiencies could add up and can lead to expensive fuel consumption or faster component aging. This thesis presents a self-optimizing control scheme, referred as Peak-seeking control, applied to propulsion systems similar to Turboprop engines. Using an extended Kalman filter, the Peak-seeking method is able drive the system to an optimal condition based only on measurements. No prior knowledge of the engine dynamics is required which make the Peak-seeking technique easy to implement and also allow for modularity in the engine design.
This study is performed on both a turboprop and a DC motor driving a variable pitch propeller and considers several performance functions to optimize.
|
3 |
Current Sharing To Minimize Power Losses In Parallel Converters Using PsoLi, Dan 11 December 2009 (has links)
The Power Electronic Building Block (PEBB) concept leads to multifunctional converter systems, which provide robustness and flexibility in heavily power electronics based power systems. Systems comprised of flexible modular converters may have multiple possible operation conditions with respect to individual converters that meet the overall system goals. In this thesis, an optimization method for such flexible online power electronic systems is developed to minimize power losses of the overall group of converters in the system. Here the objective is to allocate sharing such that compensation objectives are met while the power loss of the entire parallel group of compensators is minimized. Considering optimization of an online power electronic system, convergence time and running in the feasible region should be taken into account. This thesis is
|
4 |
Deployment of Autonomous Electric Taxis with Consideration for Charging StationsManickavasagam, Sounthar 30 May 2017 (has links)
Autonomous electric vehicles are set to replace most conventional vehicles in the near future. Extensive research is being done to improve efficiency at the individual and fleet level. There is much potential benefit in optimizing the deployment and rebalancing of Autonomous Electric Taxi Fleets (AETF) in cities with dynamic demand and limited charging infrastructure. We propose a Fleet Management System with an Online Optimization Model to assign idle taxis to either a region or a charging station considering the current demand and charging station availability. Our system uses real-time information such as demand in regions, taxi locations and state of charge (SoC), and charging station availability to make optimal decisions in satisfying the dynamic demand considering the range-based constraints of electric taxis. We integrate our Fleet Management System with MATSim, an agent-based transport simulator, to simulate taxis serving real on-demand requests extracted from the San Francisco taxi mobility dataset. We found our system to be effective in rebalancing and ensuring efficient taxi operation by assigning them to charging stations when depleted. We evaluate this system using different performance metrics such as passenger waiting time, fleet efficiency (taxi empty driving time) and charging station utilization by varying initial SoC of taxis, frequency of optimization and charging station capacity and power.
|
5 |
Deployment of Autonomous Electric Taxis with Consideration for Charging StationsManickavasagam, Sounthar 30 May 2017 (has links)
Autonomous electric vehicles are set to replace most conventional vehicles in the near future. Extensive research is being done to improve efficiency at the individual and fleet level. There is much potential benefit in optimizing the deployment and rebalancing of Autonomous Electric Taxi Fleets (AETF) in cities with dynamic demand and limited charging infrastructure. We propose a Fleet Management System with an Online Optimization Model to assign idle taxis to either a region or a charging station considering the current demand and charging station availability. Our system uses real-time information such as demand in regions, taxi locations and state of charge (SoC), and charging station availability to make optimal decisions in satisfying the dynamic demand considering the range-based constraints of electric taxis. We integrate our Fleet Management System with MATSim, an agent-based transport simulator, to simulate taxis serving real on-demand requests extracted from the San Francisco taxi mobility dataset. We found our system to be effective in rebalancing and ensuring efficient taxi operation by assigning them to charging stations when depleted. We evaluate this system using different performance metrics such as passenger waiting time, fleet efficiency (taxi empty driving time) and charging station utilization by varying initial SoC of taxis, frequency of optimization and charging station capacity and power.
|
6 |
Algorithmes d’optimisation pour un service de transport partagé à la demande / Optimization algorithms for a shared transport serviceVallée, Sven 10 July 2019 (has links)
L'objectif de cette thèse est de proposer des algorithmes d'optimisation efficaces pour un système de tranport en commun à la demande proposé par Padam Mobility, une start-up Parisienne. Après avoir modélisé le problème comme un DARP dynamique, trois modules d'optimisation sont présentés : un module online destiné à répondre aux requêtes en temps réel, un module de réinsertion pour insérer les requêtes rejetées par le module online et enfin un module offline basé sur une métaheuristique permettant d'optimiser en continue les itinéraires. / The purpose of this thesis is to propose efficient optimization algorithms for an on-demand common transportation system operated by Padam Mobility, a Parisian company. Formalised as a dynamic DARP, we propose three optimisation modules to tackle the underlying problem : an online module to answer real-time requests, a reinsertion module to re-insert rejected requests and a metaheuristic-based offline module to continuously optimize the rides. The proposed methods are directly implemented in the company system and extensively tested on real instances.
|
7 |
Randomized Approximation and Online Algorithms for Assignment ProblemsBender, Marco 23 April 2015 (has links)
No description available.
|
8 |
Online Resource ManagementTiedemann, Morten 16 April 2015 (has links)
No description available.
|
9 |
Models and algorithms for fleet management of autonomous vehicles / Modèles et algorithmes de gestion de flottes de véhicules autonomesBsaybes, Sahar 26 October 2017 (has links)
Résumé indisponible. / The VIPAFLEET project aims at developing a framework to manage a fleet of IndividualPublic Autonomous Vehicles (VIPA). We consider a fleet of cars distributed at specifiedstations in an industrial area to supply internal transportation, where the cars can beused in different modes of circulation (tram mode, elevator mode, taxi mode). The goalis to develop and implement suitable algorithms for each mode in order to satisfy all therequests either under an economic point aspect or under a quality of service aspect, thisby varying the studied objective functions.We model the underlying online transportation system as a discrete event basedsystem and propose a corresponding fleet management framework, to handle modes,demands and commands. We consider three modes of circulation, tram, elevator andtaxi mode. We propose for each mode appropriate online algorithms and evaluate theirperformance, both in terms of competitive analysis and practical behavior by computationalresults. We treat in this work, the pickup and delivery problem related to theTram mode and the Elevator mode the pickup and delivery problem with time windowsrelated to the taxi mode by means of flows in time-expanded networks.
|
10 |
Allocation de puissance en ligne dans un réseau IoT dynamique et non-prédictible / Online power allocation in a dynamic and umpredictable iot networkMarcastel, Alexandre 21 February 2019 (has links)
L’Internet des Objets (IoT) est envisagé pour interconnecter des objets communicants et autonomes au sein du même réseau, qui peut être le réseau Internet ou un réseau de communication sans fil. Les objets autonomes qui composent les réseaux IoT possèdent des caractéristiques très différentes, que ce soit en terme d’application, de connectivité, de puissance de calcul, de mobilité ou encore de consommation de puissance. Le fait que tant d’objets hétérogènes partagent un même réseau soulève de nombreux défis tels que : l’identification des objets, l’efficacité énergétique, le contrôle des interférences du réseau, la latence ou encore la fiabilité des communications. La densification du réseau couplée à la limitation des ressources spectrales (partagées entre les objets) et à l’efficacité énergétique obligent les objets à optimiser l’utilisation des ressources fréquentielles et de puissance de transmission. De plus, la mobilité des objets au sein du réseau ainsi que la grande variabilité de leur comportement changent la dynamique du réseau qui devient imprévisible. Dans ce contexte, il devient difficile pour les objets d’utiliser des algorithmes d’allocation de ressources classiques, qui se basent sur une connaissance parfaite ou statistique du réseau. Afin de transmettre de manière efficace, il est impératif de développer de nouveaux algorithmes d’allocation de ressources qui sont en mesure de s’adapter aux évolutions du réseau. Pour cela, nous allons utiliser des outils d’optimisation en ligne et des techniques d’apprentissage. Dans ce cadre nous allons exploiter la notion du regret qui permet de comparer l’efficacité d’une allocation de puissance dynamique à la meilleure allocation de puissance fixe calculée à posteriori. Nous allons aussi utiliser la notion de non-regret qui garantit que l’allocation de puissance dynamique donne des résultats asymptotiquement optimaux . Dans cette thèse, nous nous sommes concentrés sur le problème de minimisation de puissance sous contrainte de débit. Ce type de problème permet de garantir une certaine efficacité énergétique tout en assurant une qualité de service minimale des communications. De plus, nous considérons des réseaux de type IoT et ne faisons donc aucune hypothèse quant aux évolutions du réseau. Un des objectifs majeurs de cette thèse est la réduction de la quantité d’information nécessaire à la détermination de l’allocation de puissance dynamique. Pour résoudre ce problème, nous avons proposé des algorithmes inspirés du problème du bandit manchot, problème classique de l’apprentissage statistique. Nous avons montré que ces algorithmes sont efficaces en terme du regret lorsque l’objet a accès à un vecteur, le gradient ou l’estimateur non-biaisé du gradient, comme feedback d’information. Afin de réduire d’avantage la quantité d’information reçue par l’objet, nous avons proposé une méthode de construction d’un estimateur du gradient basé uniquement sur une information scalaire. En utilisant cet estimateur nous avons présenté un algorithme efficace d’allocation de puissance. / One of the key challenges in Internet of Things (IoT) networks is to connect numerous, heterogeneous andautonomous devices. These devices have different types of characteristics in terms of: application, computational power, connectivity, mobility or power consumption. These characteristics give rise to challenges concerning resource allocation such as: a) these devices operate in a highly dynamic and unpredictable environments; b) the lack of sufficient information at the device end; c) the interference control due to the large number of devices in the network. The fact that the network is highly dynamic and unpredictable implies that existing solutions for resource allocation are no longer relevant because classical solutions require a perfect or statistical knowledge of the network. To address these issues, we use tools from online optimization and machine learning. In the online optimization framework, the device only needs to have strictly causal information to define its online policy. In order to evaluate the performance of a given online policy, the most commonly used notion is that of the regret, which compares its performance in terms of loss with a benchmark policy, i.e., the best fixed strategy computed in hindsight. Otherwise stated, the regret measures the performance gap between an online policy and the best mean optimal solution over a fixed horizon. In this thesis, we focus on an online power minimization problem under rate constraints in a dynamic IoT network. To address this issue, we propose a regret-based formulation that accounts for arbitrary network dynamics, using techniques used to solve the multi-armed bandit problem. This allows us to derive an online power allocation policy which is provably capable of adapting to such changes, while relying solely on strictly causal feedback. In so doing, we identify an important tradeoff between the amount of feedback available at the transmitter side and the resulting system performance. We first study the case in which the device has access to a vector, either the gradient or an unbiased estimated of the gradient, as information feedback. To limit the feedback exchange in the network our goal is to reduce it as mush as possible. Therefore, we study the case in which the device has access to only a loss-based information (scalar feedback). In this case, we propose a second online algorithm to determine an efficient and adaptative power allocation policy.
|
Page generated in 0.1238 seconds