Dissertations / Theses on the topic 'Capacity Maximization and Optimization'

User modeling enables in the computation of the traffic density in a cellular network, which can be used to optimize the placement of base stations and radio network controllers as well as to analyze the performance of resource management algorithms towards meeting the final goal: the calculation and maximization of network capacity and throughput for different data rate services. An analytical model is presented for approximating the user distributions in multi-cell third generation wideband code division multiple access (WCDMA) networks using 2-dimensional Gaussian distributions by determining the means and the standard deviations of the distributions for every cell. This model allows for the calculation of the inter-cell interference and the reverse-link capacity of the network. An analytical model for optimizing capacity in multi-cell WCDMA networks is presented. Capacity is optimized for different spreading factors and for perfect and imperfect power control. Numerical results show that the SIR threshold for the received signals is decreased by 0.5 to 1.5 dB due to the imperfect power control. The results also show that the determined parameters of the 2-dimensional Gaussian model match well with traditional methods for modeling user distribution. A call admission control algorithm is designed that maximizes the throughput in multi-cell WCDMA networks. Numerical results are presented for different spreading factors and for several mobility scenarios. Our methods of optimizing capacity and throughput are computationally efficient, accurate, and can be implemented in large WCDMA networks.

While the channel capacity of an isolated noise-limited wireless link is well-understood, the same is not true for the interference-limited wireless links that coexist in the same area and occupy the same frequency band(s). The performance of these wireless systems is coupled to each other due to the mutual interference. One such wireless scenario is modeled as a network of simultaneously communicating node pairs and is generally referred to as an interference channel (IC). The problem of characterizing the capacity of an IC is one of the most interesting and long-standing open problems in information theory. A popular way of characterizing the capacity of an IC is to maximize the achievable sum-rate by treating interference as Gaussian noise, which is considered optimal in low-interference scenarios. While the sum-rate of the single-band SISO IC is relatively well understood, it is not so when the users have multiple-bands and multiple-antennas for transmission. Therefore, the study of the optimal sum-rate of the multi-band MIMO IC is the main goal of this thesis. The sum-rate maximization problem for these ICs is formulated and is shown to be quite similar to the one already known for single-band MIMO ICs. This problem is reduced to the problem of finding the optimal fraction of power to be transmitted over each spatial channel in each frequency band. The underlying optimization problem, being non-linear and non-convex, is difficult to solve analytically or by employing local optimization techniques. Therefore, we develop a global optimization algorithm by extending the Reformulation and Linearization Technique (RLT) based Branch and Bound (BB) strategy to find the provably optimal solution to this problem. We further show that the spatial and spectral channels are surprisingly similar in a multi-band multi-antenna IC from a sum-rate maximization perspective. This result is especially interesting because of the dissimilarity in the way the spatial and frequency channels affect the perceived interference. As a part of this study, we also develop some rules-of-thumb regarding the optimal power allocation strategies in multi-band MIMO ICs in various interference regimes. Due to the recent popularity of Interference Alignment (IA) as a means of approaching capacity in an IC (in high-interference regime), we also compare the sum-rates achievable by our technique to the ones achievable by IA. The results indicate that the proposed power control technique performs better than IA in the low and intermediate interference regimes. Interestingly, the performance of the power control technique improves further relative to IA with an increase in the number of orthogonal spatial or frequency channels.
Master of Science

Conventional cellular systems have not taken full advantage of fractional frequency reuse and adaptive allocation due to the fixed cluster size and uniformed channel assignment procedures. This problem may cause more fatal consequences considering the cutting-edge 4G standards which have higher data rate requirements such as 3GPP-LTE and IEEE 802.16m (WiMAX). In this thesis, three different partitioning schemes for adaptive clustering with fractional frequency reuse were proposed and investigated. An overlaid cellular clustering scheme which uses adaptive fractional frequency reuse factors would provide a better end-user experience by exploiting the high level of signal to interference ratio (SIR). The proposed methods are studied via simulations and the results show that the adaptive clustering with different partitioning methods provide better capacity and grade of service (GoS) comparing to the conventional cellular architecture methodologies.

Thesis: S.M., Massachusetts Institute of Technology, Department of Mechanical Engineering, 2018.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 45-46).
In this work an algorithm for controlling the motion of an autonomous excavator arm during excavation is presented. To deal with the challenge, posed by modeling and planning trajectories through soil, a model-free method is proposed which aims at maximally harnessing the capabilities of the excavator by matching its internal characteristics to those of the environment. By maximizing the power output of specific actuators the machine is able to strike a balance between disadvantageous operating conditions where it is either getting stuck in the soil or simply not utilizing its full potential to move soil towards task oriented goals. The real-time optimization, which used methods from extremum seeking control, was implemented in simulation and then on a small scale simulation rig which validated the method. It was shown that power maximization as a strategy of trajectory adaptation for excavation was both well-grounded and feasible.
by Filippos Edward Sotiropoulos.
S.M.

In recent years, there has been a growing research interest in throughput optimization problems in a multi-hop wireless network. MIMO (multiple-input multiple-output), as an advanced physical layer technology, has been employed in multi-hop wireless networks to increase throughput with a given bandwidth or transmit power. It exploits the use of multiple antennas at the transmitter and receiver to increase spectral efficiency by leveraging its spatial multiplexing (SM) and interference cancellation (IC) capabilities. Instead of carrying complex manipulations on matrices, degree-of-freedom(DoF) based MIMO models, which require only simple computations, are widely used in networking research to exploit MIMO\'s SM and IC capabilities.
In this thesis, we employ a new DoF model, which can ensure feasible solution and achieve
a higher DoF region than previous DoF-based models. Based on this model, we study the DoF scheduling for a multi-hop MIMO network. Specifically, we aim to maximize the minimum rate among all sessions in the network. Some researches have been done based on this model to solve throughput optimization problems with the assumption that the route of each session is given priori. Although the fixed routing decreases the size of the problem, it also limits the performance of the network to a great extent.
The goal of this thesis is to employ this new model to solve the throughput maximization
problem by jointly considering flow routing, scheduling, and DoF allocation for SM and IC. We
formulate it as a mixed integer linear program (MILP), which cannot be solved efficiently by
commercial softwares even for moderate sized networks. Thus, we develop an efficient polynomial time algorithm by customizing the sequential fixing framework. Through simulation results, we show that this algorithm can efficiently provide near-optimal solutions for networks with different sizes.
Master of Science

El mundo de las telecomunicaciones está cambiando de un escenario donde únicamente las personas estaban conectadas a un modelo donde prácticamente todos los dispositivos y sensores se encuentran conectados, también conocido como Internet de las cosas (IoT), donde miles de millones de dispositivos se conectarán a Internet a través de conexiones móviles y redes fijas. En este contexto, hay muchos retos que superar, desde el desarrollo de nuevos estándares de comunicación al estudio de la viabilidad económica de los posibles escenarios futuros. En esta tesis nos hemos centrado en el estudio de la viabilidad económica de diferentes escenarios mediante el uso de conceptos de microeconomía, teoría de juegos, optimización no lineal, economía de redes y redes inalámbricas. La tesis analiza la transición desde redes centradas en el servicio de tráfico HTC a redes centradas en tráfico MTC desde un punto de vista económico. El primer escenario ha sido diseñado para centrarse en las primeras etapas de la transición, en la que ambos tipos de tráfico son servidos bajo la misma infraestructura de red. En el segundo escenario analizamos la siguiente etapa, en la que el servicio a los usuarios MTC se realiza mediante una infraestructura dedicada. Finalmente, el tercer escenario analiza la provisión de servicios basados en MTC a usuarios finales, mediante la infraestructura analizada en el escenario anterior. Gracias al análisis de todos los escenarios, hemos observado que la transición de redes centradas en usuarios HTC a redes MTC es posible y que la provisión de servicios en tales escenarios es viable. Además, hemos observado que el comportamiento de los usuarios es esencial para determinar la viabilidad de los diferentes modelos de negocio, y por tanto, es necesario estudiar el comportamiento y las preferencias de los usuarios en profundidad en estudios futuros. Específicamente, los factores más relevantes son la sensibilidad de los usuarios al retardo en los datos recopilados por los sensores y la cantidad de los mismos. También hemos observado que la diferenciación del tráfico en categorías mejora el uso de las redes y permite crear nuevos servicios empleando datos que, de otro modo, no se aprovecharían, lo cual nos permite mejorar la monetización de la infraestructura. También hemos demostrado que la provisión de capacidad es un mecanismo válido, alternativo a la fijación de precios, para la optimización de los beneficios de los proveedores de servicio. Finalmente, se ha demostrado que es posible crear roles específicos para ofrecer servicios IoT en el mercado de las telecomunicaciones, específicamente, los IoT-SPs, que proporcionan servicios basados en sensores inalámbricos utilizando infraestructuras de acceso de terceros y sus propias redes de sensores. En resumen, en esta tesis hemos intentado demostrar la viabilidad económica de modelos de negocio basados en redes futuras IoT, así como la aparición de nuevas oportunidades y roles de negocio, lo cual nos permite justificar económicamente el desarrollo y la implementación de las tecnologías necesarias para ofrecer servicios de acceso inalámbrico masivo a dispositivos MTC.
The communications world is moving from a standalone devices scenario to a all-connected scenario known as Internet of Things (IoT), where billions of devices will be connected to the Internet through mobile and fixed networks. In this context, there are several challenges to face, from the development of new standards to the study of the economical viability of the different future scenarios. In this dissertation we have focused on the study of the economic viability of different scenarios using concepts of microeconomics, game theory, non-linear optimization, network economics and wireless networks. The dissertation analyzes the transition from a Human Type Communications (HTC) to a Machine Type Communications (MTC) centered network from an economic point of view. The first scenario is designed to focus on the first stages of the transition, where HTC and MTC traffic are served on a common network infrastructure. The second scenario analyzes the provision of connectivity service to MTC users using a dedicated network infrastructure, while the third stage is centered in the analysis of the provision of services based on the MTC data over the infrastructure studied in the previous scenario. Thanks to the analysis of all the scenarios we have observed that the transition from HTC users-centered networks to MTC networks is possible and that the provision of services in such scenarios is viable. In addition, we have observed that the behavior of the users is essential in order to determine the viability of a business model, and therefore, it is needed to study their behavior and preferences in depth in future studios. Specifically, the most relevant factors are the sensitivity of the users to the delay and to the amount of data gathered by the sensors. We also have observed that the differentiation of the traffic in categories improves the usage of the networks and allows to create new services thanks to the data that otherwise would not be used, improving the monetization of the infrastructure and the data. In addition, we have shown that the capacity provision is a valid mechanism for providers' profit optimization, as an alternative to the pricing mechanisms. Finally, it has been demonstrated that it is possible to create dedicated roles to offer IoT services in the telecommunications market, specifically, the IoT-SPs, which provide wireless-sensor-based services to the final users using a third party infrastructure. Summarizing, this dissertation tries to demonstrate the economic viability of the future IoT networks business models as well as the emergence of new business opportunities and roles in order to justify economically the development and implementation of the new technologies required to offer massive wireless access to machine devices.
El món de les telecomunicacions està canviant d'un escenari on únicament les persones estaven connectades a un model on pràcticament tots els dispositius i sensors es troben connectats, també conegut com a Internet de les Coses (IoT) , on milers de milions de dispositius es connectaran a Internet a través de connexions mòbils i xarxes fixes. En aquest context, hi ha molts reptes que superar, des del desenrotllament de nous estàndards de comunicació a l'estudi de la viabilitat econòmica dels possibles escenaris futurs. En aquesta tesi ens hem centrat en l'estudi de la viabilitat econòmica de diferents escenaris per mitjà de l'ús de conceptes de microeconomia, teoria de jocs, optimització no lineal, economia de xarxes i xarxes inalàmbriques. La tesi analitza la transició des de xarxes centrades en el servici de tràfic HTC a xarxes centrades en tràfic MTC des d'un punt de vista econòmic. El primer escenari ha sigut dissenyat per a centrar-se en les primeres etapes de la transició, en la que ambdós tipus de tràfic són servits davall la mateixa infraestructura de xarxa. En el segon escenari analitzem la següent etapa, en la que el servici als usuaris MTC es realitza per mitjà d'una infraestructura dedicada. Finalment, el tercer escenari analitza la provisió de servicis basats en MTC a usuaris finals, per mitjà de la infraestructura analitzada en l'escenari anterior. Als paràgrafs següents es descriu amb més detall cada escenari. Gràcies a l'anàlisi de tots els escenaris, hem observat que la transició de xarxes centrades en usuaris HTC a xarxes MTC és possible i que la provisió de servicis en tals escenaris és viable. A més a més, hem observat que el comportament dels usuaris és essencial per a determinar la viabilitat dels diferents models de negoci, i per tant, és necessari estudiar el comportament i les preferències dels usuaris en profunditat en estudis futurs. Específicament, els factors més rellevants són la sensibilitat dels usuaris al retard en les dades recopilats pels sensors i la quantitat dels mateixos. També hem observat que la diferenciació del tràfic en categories millora l'ús de les xarxes i permet crear nous servicis emprant dades que, d'una altra manera, no s'aprofitarien, la qual cosa ens permet millorar la monetització de la infraestructura. També hem demostrat que la provisió de capacitat és un mecanisme vàlid, alternatiu a la fixació de preus, per a l'optimització dels beneficis dels proveïdors de servici. Finalment, s'ha demostrat que és possible crear rols específics per a oferir servicis IoT en el mercat de les telecomunicacions, específicament, els IoT-SPs, que proporcionen servicis basats en sensors inalàmbrics utilitzant infraestructures d'accés de tercers i les seues pròpies xarxes de sensors. En resum, en aquesta tesi hem intentat demostrar la viabilitat econòmica de models de negoci basats en xarxes futures IoT, així com l'aparició de noves oportunitats i rols de negoci, la qual cosa ens permet justificar econòmicament el desenrotllament i la implementació de les tecnologies necessàries per a oferir servicis d'accés inalàmbric massiu a dispositius MTC.
Sanchis Cano, Á. (2018). Economic analysis of wireless sensor-based services in the framework of the Internet of Things. A game-theoretical approach [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/102642
TESIS

As airspace congestion becomes increasingly more common, one of the primary places airspace congestion is felt today, and will only continue to increase, is in areas where more than one major airport interact. We will call these groups of interdependent airports a metroplex; a term originally coined to describe large metropolitan areas where more than one city of equal (or near equal) size or importance. These metroplex areas are of particular importance in understanding future capacity demands because many of these areas are currently experiencing problems with meeting the current demand, and demand is only projected to increase as air travel becomes more popular. Many of these capacity issues have been identified in the FAA's Future Airport Capacity Task (FACT). From the second FACT report, it is stated that "the FACT 1 analysis revealed that many of our hub airports and their associated metropolitan areas could be expected to experience capacity constraints (i.e. unacceptable levels of delay) by 2013 and 2020, even if the planned improvements envisioned at that time were completed." This analysis shows that the current methods of expanding airports will not scale with the growing demand. To address this growing demand, a three part solution is proposed. The first step is to properly identify the metroplex areas to be evaluated. While the FACT reports serve to identify areas where capacity growth does not meet demand, these areas are not grouped into metroplexes. To do this grouping, an interaction metric was developed based on airport distance and traffic volume. This interaction metric serves as a proxy for how the existence of a second airport impacts the operation of the first. This pairwise metric was then computed for all commercial airports in the US and were grouped into metroplexes using a clustering algorithm. The second obstacle was to develop a tool to evaluate each metroplex as new algorithms were tested. A discrete event based simulation was developed to model each link in the airspace structure for each aircraft that enters the TRACON. This program tracks the delay each aircraft is required to accumulate in holding patterns or traffic trombones. A third and final method discussed here was an optimization program that can be used to schedule aircraft that are entering the TRACON to perform small modifications in their speed while en route to reduce the overall delay (both en route and in the TRACON). While formal optimization methods for scheduling aircraft arrivals have been presented before, the computational complexity has greatly prevented such algorithms from being used to schedule many aircraft in a dense schedule. This is because mixed integer programming (MIP) is a NP-hard problem. Practically, this means that the solution time can grow exponentially as the problem size (number of aircraft) increases. To address this issue, a Benders' decomposition scheme was introduced that allows solutions to be computed in near real-time on commodity hardware. These solutions can be evaluated and compared against the currently used TMA algorithm to show surprising gains in high density traffic.

This research explores the idea of developing an optimal path generator that can be used in conjunction with a feedback steering controller to automate track testing experiment. This study specifically concentrates on applying optimization concepts to generate paths that meet two separate objective functions; minimum time and maximum tire forces.

A three-degree-of freedom vehicle model is used to approximate the handling dynamics of the vehicle. Inputs into the vehicle model are steering angle and longitudinal force at the tire. These two variables approximate two requirements that are essential in operating a vehicle. The Third order Runge-Kutta integration routine is used to integrate vehicle dynamics equations of motion. The Optimization Toolbox of Matlab is used to evaluate the optimization algorithm. The vehicle is constrained with a series of conditions, includes, a travel within the boundaries of the track, traction force limitations at the tire, vehicle speed, and steering.

The simulation results show that the optimization applied to vehicle dynamics can be useful in designing an automated track testing system. The optimal path generator can be used to develop meaningful test paths on existing test tracks. This study can be used to generate an accelerated tire wear test path, perform parametric study of suspension geometry design using vehicle dynamics handling test data, and to increase repeatability in generating track testing results.

Vita removed at author's request. GMc 3/13/2013
Master of Science

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management; and, (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science; in conjunction with the Leaders for Manufacturing Program, Massachusetts Institute of Technology, 2000.
Also available online at the MIT Theses Online homepage .
Includes bibliographical references (p. 85).
Assembly and Test Manufacturing (ATM) at Intel faces new challenges caused by increased competition, cost pressure, and segmented markets. These forces combine to present ATM with increasing line items and processes in the face of-extreme demand fluctuations over relatively short time periods. As a result, the factories are challenged with accurately planning capacity. Currently, ATM utilizes static, Excel-based models to plan capacity and perform what-if scenarios. The applicability of static models in the highly dynamic ATM environment is questionable. These static models neglect the inherent variability of each tool as well as the coupling of variability between tool sets caused by WIP flow. This prevents static models from predicting the values and variabilities of factory outputs and throughput times (TPT) with sufficient accuracy to optimize the business. Discrete event simulations have the inherent advantage of modeling factory dynamics. They allow for factory experimentation without risking actual production. Examples include availability and run rate improvement impacts, and changes to WIP management policies. Both static and dynamic approaches share a dependency on the accuracy of the input data. In ATM, a few performance parameters are accurately measured in Workstream including output, TPT, queue size, and yield. Tool performance data (availability, failure details, etc.) are not accurately measured because of the low priority placed on this type of data. Parameters such as utilization are back-calculated instead of being measured directly. No attempt is made to capture other important data like tool idle time. This thesis explores the development, validation, and application of a full factory simulation including the consequences of data inadequacies. Tool and factory performance data were gathered in the Costa Rica assembly and test factory for WW28- 34 1999, and were incorporated into a dynamic factory model. Results from simulation using this model underscored the need for automated tool data collection systems by highlighting the inaccuracies of the tool availability data and labor effectiveness. The model also proved useful for exploring WIP policy alternatives (CONWIP limits vs. drum-buffer-rope starts policies). Reduction of CONWIP limits from 4 days to 3 days appeared robust and generated a 20% decrease in TPT. Equipment protective capacity was optimized. The results indicate that the current gap policy of 10/15/20 is sub-optimal and leads to inefficient capital expenditures. The thesis also shows a logical methodology for optimizing protective capacity levels in factories where there are large capital cost differences among toolsets.
by Anthony W. Newlin.
S.M.

nÃo hÃ
One challenging task in multiple input multiple output (MIMO) systems design is to accommodate the multiple antennas in the mobile device without compromising the system capacity, due to spatial and electrical constraints. In this work, an experimental MIMO wireless channel characterization in an outdoor environment is performed in order to study the different factors that affect MIMO capacity. The data acquired during wideband channel measurement campaigns made in Stockholm, Sweden, were used in order to predict the impact of direction of arrival (DOA) distribution and polarization diversity on the channel capacity, choosing specific measurement routes and locations as well as different MIMO antenna array configurations. This thesis proposes a genetic algorithm (GA) to obtain the position and orientation of each MIMO array antenna that maximizes the ergodic capacity for a given propagation scenario. The simulations of the GA use the characterized experimental channel model, as a case of study, in order to evaluate the impact of different characteristics of the propagation environment in the capacity. Based on an interface between the antenna model and the propagation channel model, the ergodic capacity is considered as the objective function of the MIMO array optimization. Simulation results corroborate the importance of polarization and antenna pattern diversities for MIMO in small terminals. The results also show that the electromagnetic coupling effect can be exploited by the optimizer in order to decrease signal correlation and increase MIMO capacity. A comparison among uniform linear array (ULA), uniform circular array (UCA) and the GA-optimized array is also carried out, showing that the topology given by the optimizer is superior to that of the standard ULA and UCA arrays for the considered propagation channel. This work also presents a method for optimizing the capacity of MIMO antenna array systems with antenna selection, evolving the antenna array best suited for antenna selection in a given scenario. As a result of the proposed GA optimizer, different array configurations were obtained for cases with and without antenna selection, showing that true polarization diversity (TPD) schemes are particularly suited for antenna selection systems.
Uma questÃo bastante complicada no projeto de sistemas MIMO à acomodar as mÃltiplas antenas no dispositivo mÃvel sem comprometer a capacidade do sistema, devido a restriÃÃes elÃtricas e de espaÃo. Neste trabalho à desenvolvida a caracterizaÃÃo de um canal MIMO sem fio em ambiente externo para o estudo dos diferentes fatores que afetam a capacidade de comunicaÃÃo. Os dados adquiridos em campanhas de mediÃÃo feitas em Estocolmo foram utilizados para modelar o impacto da distribuiÃÃo de DOA e da diversidade de polarizaÃÃo na capacidade do canal, escolhendo rotas especÃficas de medida e diferentes configuraÃÃes de arranjos de antena. Essa tese propÃe um algoritmo genÃtico para obter a posiÃÃo e orientaÃÃo de cada antena do arranjo MIMO que maximizem a capacidade ergÃtica para um dado cenÃrio de propagaÃÃo. Baseando-se em uma interface entre o modelo de antena e o modelo de propagaÃÃo do canal, a capacidade ergÃdica à usada como funÃÃo objetivo da otimizaÃÃo do arranjo MIMO. Os resultados das simulaÃÃo indicam a importÃncia das diversidades de polarizaÃÃo e de padrÃo de antena para sistemas MIMO em terminais de pequeno porte. Os resultados tambÃm mostram que o efeito do acoplamento eletromagnÃtico pode ser explorado pelo otimizador para diminuir a correlaÃÃo do sinal aumentando assim a capacidade MIMO. TambÃm à feita uma comparaÃÃo entre arranjo linear uniforme(ULA), arranjo circular uniforme(UCA) e um arranjo otimizado pelo algoritmo genÃtico, mostrando que a topologia resultante do algoritmo genÃtico à superior tanto a ao arranjo ULA quanto ao arranjo UCA, para o canal de propagaÃÃo considerado. Este trabalho tambÃm apresenta um mÃtodo para otimizaÃÃo da capacidade de sistemas MIMO com seleÃÃo de antena, evoluindo um arranjo de antenas melhor adaptado para a seleÃÃo de antenas em um dado cenÃrio de propagaÃÃo. Como resultado do mÃtodo proposto, diferentes configuraÃÃes de arranjos foram obtidas para o caso com e sem seleÃÃo de antenas, mostrando que sistemas de diversidade de polarizaÃÃo(TPD) sÃo particularmente adequados para sistemas com seleÃÃo de antena.

A model is developed to identify the optimal capital expansion decisions for producers of s consumable products. The model features an optional selection of corporate level in a product tree hierarchy and a choice of several optimizing objective functions. The model assumes that intermediate product demand is directly dependent on demand for consumable products. Intermediate product demands are derived from demand for consumable products using a product tree similar to a bill of materials. Restrictions exist on the productive capacity of all products in the product tree, and interdependences exist between producers of the various products. Likewise, the availability of labor limits production capacities for all products in the product tree. The capital available for the capacity expansions can either be capital equity or corporate debt. The model identities the expansion strategy which optimizes the chosen economic objective function. A case study is analyzed with linear programming software to determine the optimal expansion strategy for a tire manufacturer given a hypothetical market demand for automobiles.
Master of Science

Le développement de comportements utiles pour les robots complexes, tel que des humanoïdes, s'avère difficile. La commande corps-complet à base de modèle allège en partie ces difficultés, en permettant la composition des comportements corps-complets complexes à partir de plusieurs tâches atomiques effectuées simultanément sur le robot. Cependant, des hypothèses et erreurs de modélisation, faites pendant la planification des tâches, peuvent produire des combinaisons infaisables/incompatibles quand exécutées sur le robot, créant des mouvements corps-complet imprévisibles, et probablement dangereux. L'objectif de ce travail est de mieux comprendre ce qui rend les tâches infaisables ou incompatibles et de développer des méthodes automatiques pour améliorer ces problèmes pour que les mouvements corps-complets puissent être accomplis comme prévu. Nous commençons par construire un formalisme permettant d'analyser quand les tâches sont faisables et compatibles étant données les contraintes de commande. En utilisant les métriques de faisabilité et compatibilité à base de modèle, nous démontrons comment optimiser les tâches avec des outils de commande prédictive non-linéaire ainsi que les inconvénients de cette approche. Afin de surmonter ces faiblesses, une boucle d'optimisation est formulée, qui améliore automatiquement la faisabilité et compatibilité des tâches via la recherche de politique sans modèle en conjonction avec la commande corps-complets à base de modèle. À travers une série d'expériences simulées et réelles, nous montrons que la simple optimisation de faisabilité et compatibilité des tâches nous permet de réaliser des mouvements corps-complets utiles
Producing useful behaviors on complex robots, such as humanoids, is a challenging undertaking. Model-based whole-body control alleviates some of this difficulty by allowing complex whole-body motions to be broken up into multiple atomic tasks, which are performed simultaneously on the robot. However, modeling errors and assumptions, made during task planning, often result in infeasible and/or incompatible task combinations when executed on the robot. Consequently, there is no guarantee that the prescribed tasks will be accomplished, resulting in unpredictable, and most likely, unsafe whole-body motions. The objective of this work is to better understand what makes tasks infeasible or incompatible, and develop automatic methods of improving on these two issues so that the overall whole-body motions may be accomplished as planned. We start by building a concrete analytical formalism of what it means for tasks to be feasible with the control constraints and compatible with one another. Using the model-based feasibility and compatibility metrics, we demonstrate how the tasks can be optimized using non-linear model predictive control, while also detailing the shortcomings of this model-based approach. In order to overcome these weaknesses, an optimization loop is designed, which automatically improves task feasibility and compatibility using model-free policy search in conjunction with model-based whole-body control. Through a series of simulated and real-world experiments, we demonstrate that by simply optimizing the tasks to improve both feasibility and compatibility, complex and useful whole-body motions can be realized

De nouveaux protocoles ont été standardisés afin d'intégrer les réseaux de capteurs sans fil (WSN) dans l'Internet. Parmi eux, RPL pour la couche routage et IEEE 802.15.4 pour la couche MAC. L'objectif de cette thèse est d'améliorer ces protocoles en prenant compte des contraintes énergétiques des dispositifs du WSN. Tout d'abord, nous avons conçu une nouvelle méthode de diffusion dans la norme IEEE 802.15.4, afin d'assurer une livraison fiable des paquets de contrôle des couches supérieures. Ensuite, nous avons fourni une évaluation exhaustive de RPL, en soulignant un problème d'instabilité qui génère une surcharge d'énergie importante. Compte tenu que la durée de vie des WSN est très limitée, nous avons aussi proposé une nouvelle métrique de routage qui identifie les goulets d'étranglement énergétiques afin de maximiser la durée de vie du réseau. Enfin, en couplant cette mesure avec une version multiparent de RPL, nous avons résolu le problème d'instabilité souligné précédemment
New protocols have been standardized in order to integrate Wireless Sensor Networks (WSN) in the Internet. Among them, the IEEE 802.15.4 MAC layer protocol, and RPL, the IPv6 Routing Protocol for Low-power and Lossy Networks. The goal of this thesis is to improve these protocols, considering the energy constraints of the devices that compose the WSN. First, we proposed a new MAC layer broadcast mechanism in IEEE 802.15.4, to ensure a reliable delivery of the control packets from the upper layers (especially from RPL). Then, we provided an exhaustive evaluation of RPL and highlighted an instability problem. This instability generates a large overhead, consuming a lot of energy. Since the lifetime of WSN is very limited, we proposed a new routing metric that identifies the energy bottlenecks and maximizes the lifetime of the network. Finally, by coupling this metric with a multipath version of RPL, we are able to solve the instability problem previously highlighted

Thesis (S.M. in Transportation)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering; and, (S.M.)--Massachusetts Institute of Technology, Technology and Policy Program, 2004.
Includes bibliographical references (p. 99-100).
The purpose of the National Airspace System Strategy Simulator is to provide the FAA with a decision support system to evaluate long-term infrastructure and regulatory strategies. The NAS strategy simulator consists of several modules representing the different entities within the NAS embedded in a system dynamics framework. The MIT Airline Scheduling Module is the module within the NAS Strategy Simulator that represents the decision making process of the airlines with respect to the schedules that they fly. The MIT Airline Scheduling Module is an incremental optimization tool to determine schedule changes from one time step to another that best meets demand using available resources. The optimization model combines an Integrated Schedule Design and Fleet Assignment model and a model, based on Passenger Decision Window model, that determines passenger preference for itineraries. We simultaneously establish frequency, departure times, fleet assignment, passenger loads and revenue within a competitive environment. Optimization methods often lead to extreme schedule decisions such as eliminating service to markets, often small markets, that are not financially profitable for the airlines. This is of grave concern to government policy makers as rural access to markets, goods and services is a politically charged subject. The issue is to understand what is likely to happen in small communities if the government doesn't respond in some way and how much subsidy, if any, would it be necessary to encourage airlines to maintain service in these markets. The approach we will use is based on economic policy and cost-benefit analysis.
by Flora A. Garcia.
S.M.
S.M.in Transportation

Emerging connected and autonomous vehicle technologies (CAV) provide an opportunity to improve highway capacity and reduce adverse impacts of stop-and-go traffic. To realize the potential benefits of CAV technologies, this study provides insightful methodological and managerial tools in microscopic and macroscopic traffic scales. In the macroscopic scale, this dissertation proposes an analytical method to formulate highway capacity for a mixed traffic environment where a portion of vehicles are CAVs and the remaining are human-driven vehicles (HVs). The proposed analytical mixed traffic highway capacity model is based on a Markov chain representation of spatial distribution of heterogeneous and stochastic headways. This model captures not only the full spectrum of CAV market penetration rates but also all possible values of CAV platooning intensities that largely affect the spatial distribution of different headway types. Numerical experiments verify that this analytical model accurately quantifies the corresponding mixed traffic capacity at various settings. This analytical model allows for examination of the impact of different CAV technology scenarios on mixed traffic capacity. We identify sufficient and necessary conditions for the mixed traffic capacity to increase (or decrease) with CAV market penetration rate and platooning intensity. These theoretical results caution scholars not to take CAVs as a sure means of increasing highway capacity for granted but rather to quantitatively analyze the actual headway settings before drawing any qualitative conclusion. In the microscopic scale, this study develops innovative control strategies to smooth highway traffic using CAV technologies. First, it formulates a simplified traffic smoothing model for guiding movements of CAVs on a general one-lane highway segment. The proposed simplified model is able to control the overall smoothness of a platoon of CAVs and approximately optimize traffic performance in terms of fuel efficiency and driving comfort. The elegant theoretical properties for the general objective function and the associated constraints provides an efficient analytical algorithm for solving this problem to the exact optimum. Numerical examples reveal that this exact algorithm has an efficient computational performance and a satisfactory solution quality. This trajectory-based traffic smoothing concept is then extended to develop a joint trajectory and signal optimization problem. This problem simultaneously solves the optimal CAV trajectory function shape and the signal timing plan to minimize travel time delay and fuel consumption. The proposed algorithm simplifies the vehicle trajectory and fuel consumption functions that leads to an efficient optimization model that provides exact solutions. Numerical experiments reveal that this algorithm is applicable to any signalized crossing points including intersections and work-zones. Further, the model is tested with various traffic conditions and roadway geometries. These control approaches are then extended to a mixed traffic environment with HVs, connected vehicles (CVs), and CAVs by proposing a CAV-based speed harmonization algorithm. This algorithm develops an innovative traffic prediction model to estimate the real-time status of downstream traffic using traffic sensor data and information provided by CVs and CAVs. With this prediction, the algorithm controls the upstream CAVs so that they smoothly hedge against the backward deceleration waves and gradually merge into the downstream traffic with a reasonable speed. This model addresses the full spectrum of CV and CAV market penetration rates and various traffic conditions. Numerical experiments are performed to assess the algorithm performance with different traffic conditions and CV and CAV market penetration rates. The results show significant improvements in damping traffic oscillations and reducing fuel consumption.

Thesis: M.B.A., Massachusetts Institute of Technology, Sloan School of Management, in conjunction with the Leaders for Global Operations Program at MIT, May, 2020
Thesis: S.M., Massachusetts Institute of Technology, Department of Mechanical Engineering, in conjunction with the Leaders for Global Operations Program at MIT, May, 2020
Cataloged from the official PDF of thesis.
Includes bibliographical references (pages 101-104).
Raytheon's Circuit Card Assembly (CCA) factory in Andover, MA is Raytheon's largest factory and the largest Department of Defense (DOD) CCA manufacturer in the world. With over 500 operations, it manufactures over 7000 unique parts with a high degree of complexity and varying levels of demand. Recently, the factory has seen an increase in demand, making the ability to continuously analyze factory capacity and strategically plan for future operations much needed. This study seeks to develop a sustainable strategic capacity optimization model and capacity visualization tool that integrates demand data with historical manufacturing data. Through automated data mining algorithms of factory data sources, capacity utilization and overall equipment effectiveness (OEE) for factory operations are evaluated. Machine learning methods are then assessed to gain an accurate estimate of cycle time (CT) throughout the factory. Finally, a mixed-integer nonlinear program (MINLP) integrates the capacity utilization framework and machine learning predictions to compute the optimal strategic capacity planning decisions. Capacity utilization and OEE models are shown to be able to be generated through automated data mining algorithms. Machine learning models are shown to have a mean average error (MAE) of 1.55 on predictions for new data, which is 76.3% lower than the current CT prediction error. Finally, the MINLP is solved to optimality within a tolerance of 1.00e-04 and generates resource and production decisions that can be acted upon.
by Hans Nowak II.
M.B.A.
S.M.
M.B.A. Massachusetts Institute of Technology, Sloan School of Management
S.M. Massachusetts Institute of Technology, Department of Mechanical Engineering

A robust simulation-based optimization approach is proposed for truck-shovel systems in surface coal mines to maximize the expected value of revenue obtained from loading customer trains. To this end, a large surface coal mine in North America is considered as case study. A data-driven modeling framework is developed and then applied to automatically generate a highly detailed simulation model of the mine in Arena. The framework comprises a formal information model based on Unified Modeling Language (UML), which is used to input mine structural as well as production information. Petri net-based model generation procedures are applied to automatically generate the simulation model based on the whole set of simulation inputs. Then, factors encountered in material handling operations that may affect the robustness of revenue are then classified into 1) controllable; and 2) uncontrollable categories. While controllable factors are trucks locked to routes, uncontrollable factors are inverses of summation over truck haul, and shovel loading and truck-dumping times for each route. Historical production data of the mine contained in a data warehouse is used to derive probability distributions for the uncontrollable factors. The data warehouse is implemented in Microsoft SQL, and contains snapshots of historical equipment statuses and production outputs taken at regular intervals in each shift of the mine. Response Surface Methodology is applied to derive an expression for the variance of revenue as a function of controllable and uncontrollable factors. More specifically, 1) first order and second order effects for controllable factors, 2) first order effects for uncontrollable factors, and 3) two factor interactions for controllable and uncontrollable factors are considered. Latin Hypercube Sampling method is applied for setting controllable factors and the means of uncontrollable factors. Also, Common Random Numbers method is applied to generate the sequence of pseudo-random numbers for uncontrollable factors in simulation experiments for variance reduction between different design points of the metamodel. The variance of the metamodel is validated using leave-one-out cross validation. It is later applied as an additional constraint to the mathematical formulation to maximize revenue in the simulation model using OptQuest. The decision variables in this formulation are truck locks only. Revenue is a function of the actual quality of coal delivered to each customer and their corresponding quality specifications for premiums and penalties. OptQuest is an optimization add-on for Arena that uses Tabu search and Scatter search algorithms to arrive at the optimal solution. The upper bound on the variance as a constraint is varied to obtain different sets of expected value as well as variance of optimal revenue. After comparison with results using OptQuest with random sampling and without variance expression of metamodel, it has been shown that the proposed approach can be applied to obtain the decision variable set that not only results in a higher expected value but also a narrower confidence interval for optimum revenue. According to the best of our knowledge, there are two major contributions from this research: 1) It is theoretically demonstrated using 2-point and orthonormal k-point response surfaces that Common Random Numbers reduces the error in estimation of variance of metamodel of simulation model. 2) A data-driven modeling and simulation framework has been proposed for automatically generating discrete-event simulation model of large surface coal mines to reduce modeling time, expenditure, as well as human errors associated with manual development.

In many important real world applications the initial representation of the data is inconvenient, or even prohibitive for further analysis. For example, in image analysis, text analysis and computational genetics high-dimensional, massive, structural, incomplete, and noisy data sets are common. Therefore, feature extraction, or revelation of informative features from the raw data is one of fundamental machine learning problems. Efficient feature extraction helps to understand data and the process that generates it, reduce costs for future measurements and data analysis. The representation of the structured data as a compact set of informative numeric features allows applying well studied machine learning techniques instead of developing new ones.. The dissertation focuses on supervised and semi-supervised feature extraction methods, which optimize the dependence structure of features. The dependence is measured using the kernel estimator of Hilbert-Schmidt norm of covariance operator (HSIC measure). Two dependence structures are investigated: in the first case we seek features which maximize the dependence on the dependent variable, and in the second one, we additionally minimize the mutual dependence of features. Linear and kernel formulations of HBFE and HSCA are provided. Using Laplacian regularization framework we construct semi-supervised variants of HBFE and HSCA. Suggested algorithms were investigated experimentally using conventional and multilabel classification data... [to full text]
Daugelis praktiškai reikšmingu sistemu mokymo uždaviniu reikalauja gebeti panaudoti didelio matavimo, strukturizuotus, netiesinius duomenis. Vaizdu, teksto, socialiniu bei verslo ryšiu analize, ivairus bioinformatikos uždaviniai galetu buti tokiu uždaviniu pavyzdžiais. Todel požymiu išskyrimas dažnai yra pirmasis žingsnis, kuriuo pradedama duomenu analize ir nuo kurio priklauso galutinio rezultato sekme. Šio disertacinio darbo tyrimo objektas yra požymiu išskyrimo algoritmai, besiremiantys priklausomumo savoka. Darbe nagrinejamas priklausomumas, nusakytas kovariacinio operatoriaus Hilberto-Šmidto normos (HSIC mato) branduoliniu ivertiniu. Pasiulyti šiuo ivertiniu besiremiantys HBFE ir HSCA algoritmai leidžia dirbti su bet kokios strukturos duomenimis, bei yra formuluojami tikriniu vektoriu terminais (tai leidžia optimizavimui naudoti standartinius paketus), bei taikytini ne tik prižiurimo, bet ir dalinai prižiurimo mokymo imtims. Pastaruoju atveju HBFE ir HSCA modifikacijos remiasi Laplaso reguliarizacija. Eksperimentais su klasifikavimo bei daugiažymio klasifikavimo duomenimis parodyta, jog pasiulyti algoritmai leidžia pagerinti klasifikavimo efektyvuma lyginant su PCA ar LDA.

As illness becomes increasingly more common in the United States and across the globe, the need for better and faster medical treatment is greater than ever. The purpose of this work is to evaluate advanced polymers and polymer composites that will provide for increased fluid flow while maintaining outer dimensional, stiffness, and burst resistance characteristics when compared to a currently used material. A polymer configuration consisting of a proprietary formulation that has a durometer approximately 10% higher than the current material with an outer wall thickness of approximately .020" passed a series of tests involving tensile strength, stiffness, flexural fatigue resistance, vacuum lumen collapse resistance and hydraulic burst resistance. This material configuration passed the requirements for applicable test standards and had a tensile strength 13.4% less than the control group, was 52.7% stiffer, did not sustain any noticeable wear or defects during the flexural fatigue test, had a tensile strength 14.8% less that the control group during a post flex fatigue tensile test, did not burst when 150 psi was applied to it for 5 seconds, and is estimated to have a 43% higher flow rate capacity than the current material.

Multiple input multiple output (MIMO) systems are now a proven area in current and future telecommunications research. MIMO wireless channels, in which both the transmitter and receiver have multiple antennas, have been shown to provide high bandwidth efficiency. In this thesis, we cover MIMO communications technology with a focus on cellular systems and the MIMO broadcast channel (MIMO-BC). Our development of techniques and analysis for the MIMO-BC starts with a study of single user MIMO systems. One such single user technique is that of antenna selection. In this thesis, we discuss various flavours of antenna selection, with the focus on powerful, yet straightforward, norm-based algorithms. These algorithms are analyzed and the results of this analysis produce a powerful and flexible power scaling factor. This power scaling factor can be used to model the gains of norm-based antenna selection via a single signal-to-noise ratio (SNR)-based parameter. This provides a powerful tool for engineers interested in quickly seeing the effects of antenna selection on their systems. A novel low complexity power allocation scheme follows on from the selection algorithms. Named “Poor Man’s Waterfilling” (PMWF), this scheme can provide significant gains in low SNR systems with very little extra complexity compared to selection alone. We then compare a variety of algorithms for the MIMO-BC, ranging from selection to beamforming, to the optimal, yet complex, iterative waterfilling (ITWF) solution. In this thesis we show that certain algorithms perform better in different scenarios, based on whether there is shadow fading or not. A power scaling factor analysis is also performed on these systems. In the cases where the user’s link gains are widely varying, such as when shadowing and distance effects are present, user fairness is impaired when optimal and near optimal throughput occurs. This leads to a key problem in the MIMO-BC, the balance between user fairness and throughput performance. In an attempt to find a suitable balance between these two factors, we modify the ITWF algorithm by both introducing extra constraints and also by using a novel utility function approach. Both these methods prove to increase user fairness with only minor loss in throughput over the optimal systems. The introduction of MIMO systems to the cellular domain has been hampered by the effects of interference between the cells. In this thesis we move MIMO to the cellular domain, addressing the interference using two different methods. We first use power control, where the transmit power of the base station is controlled to optimize the overall system throughput. This leads to promising results using low complexity methods. Our second method is a novel method of collaboration between base stations. This collaboration transforms neighbouring cell sectors into macro-cells and this results in substantial increases in performance.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Civil and Environmental Engineering, 2018.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 113-119).
Feeding the world's growing population in an environmentally sustainable way is a complex social and engineering challenge. In this thesis, we develop a novel method for assessing the number of people that can be fed sustainably in a particular region for given natural resources and diet (the carrying capacity). A quantitative assessment of carrying capacity provides insight into the food security of the study region as well as the stress on the environmental system; in addition, this methodology can be used to assess the carrying capacity under a variety of policy interventions such as increasing yields, changing diets, or expanding irrigation infrastructure. The carrying capacity assessment uses optimization methods that find the cropping pattern that maximizes population subject to land, water, and diet constraints, considering a range of rainfed and irrigated crops. A data fusion procedure estimates the regional water and land resources needed to assess carrying capacity by combining measurements from diverse hydrologic and agronomic sources, including remote sensing data. Our carrying capacity methodology is illustrated with a case study of food security in China. China has historically been largely food self-sufficient, although its food imports have been increasing since the year 2000. We find that the population in China was well below the country's carrying capacity in the year 2000 given the diet and yields in that year. However, the population's changing diet - especially the growing preference for meat - is exacting a growing toll on land and water resources. We find that under a more recent diet (2013), China is not likely to be food self-sufficient, even with major investments in irrigated agriculture, without substantial increases in crop yield.
by Tiziana Smith.
Ph. D.

A Bussgang based blind deconvolution algorithm called self-correcting multi-channel Bussgang (SCMB) blind deconvolution algorithm was proposed. Unlike the original Bussgang blind deconvolution algorithm where the probability density function (pdf) of the signal being recovered is assumed to be completely known, the proposed SCMB blind deconvolution algorithm relaxes this restriction by parameterized the pdf with a Gaussian mixture model and expectation maximization (EM) algorithm, an iterative maximum likelihood approach, is employed to estimate the parameter side by side with the estimation of the equalization filters of the original Bussgang blind deconvolution algorithm. A feedback loop is also designed to compensate the effect of the parameter estimation error on the estimation of the equalization filters. Application of the SCMB blind deconvolution framework for binary image restoration, multi-pass synthetic aperture radar (SAR) autofocus and inverse synthetic aperture radar (ISAR) autofocus are exploited with great results.

In this thesis we study two discrete optimization problems: Traffic Light Synchronization and Location with Customers Orderings. A widely used approach to solve the synchronization of traffic lights on transport networks is the maximization of the time during which cars start at one end of a street and can go to the other without stopping for a red light (bandwidth maximization). The mixed integer linear model found in the literature, named MAXBAND, can be solved by optimization solvers only for small instances. In this manuscript we review in detail all the constraints of the original linear model, including those that describe all the cyclic routes in the graph, and we generalize some bounds for integer variables which so far had been presented only for problems that do not consider cycles. Furthermore, we summarized the first systematic algorithm to solve a simpler version of the problem on a single street. We also propose a solution algorithm that uses Tabu Search and Variable Neighbourhood Search and we carry out a computational study. In addition we propose a linear formulation for the shortest path problem with traffic lights constraints (SPTL). On the other hand, the simple plant location problem with order (SPLPO) is a variant of the simple plant location problem (SPLP) where the customers have preferences on the facilities which will serve them. In particular, customers define their preferences by ranking each of the potential facilities. Even though the SPLP has been widely studied in the literature, the SPLPO has been studied much less and the size of the instances that can be solved is very limited. In this manuscript, we propose a heuristic that uses a Lagrangean relaxation output as a starting point of a semi-Lagrangean relaxation algorithm to find good feasible solutions (often the optimal solution). We also carry out a computational study to illustrate the good performance of our method. Last, we introduce the partial and stochastic versions of SPLPO and apply the Lagrangean algorithm proposed for the deterministic case to then show examples and results.

Recently, many new types of wireless networks have emerged for both civil and military applications, such as cognitive radio networks, MIMO networks. There is a strong interest in exploring the optimal performance of these new emerging networks, e.g., maximizing the network throughput, minimizing network energy consumption. Exploring the optimal performance objectives of these new types of wireless networks is both important and intellectual challenging. On one hand, it is important for a network researcher to understand the performance limits of these new wireless networks. Such performance limits are important not only for theoretical understanding, but also in that they can be used as benchmarks for the design of distributed algorithms and protocols. On the other hand, due to some unique characteristics associated with these networks, existing analytic techniques may not be applied directly to obtain the optimal performance. As a result, new theoretical results, along with new mathematical tools, need to be developed. The goal of this dissertation is to make a fundamental advance on network performance optimization via exploring a series of optimization problems. Based on the scale of the underlying wireless network, the works in this dissertation are divided into two parts. In the first part, we study the asymptotic capacity scaling laws of different types of wireless networks. By "asymptotic", we mean that the number of nodes in the network goes to infinity. Such asymptotic capacity scaling laws offer fundamental understandings on the trend of maximum user throughput behavior when the network size increases. In the second part of this dissertation, we study several optimization problems of finite-sized wireless networks. Under a given network size, we accurately characterize some performance limits (e.g., throughput, energy consumption) of wireless networks and provide solutions on how to achieve the optimal objectives. The main contributions of this dissertation can be summarized as follows, where the first three problems are on asymptotic capacity scaling laws and the last three problems are optimization problems of finite-sized wireless networks. 1. Capacity Scaling Laws of Cognitive Radio Ad Hoc Networks. We first study the capacity scaling laws for cognitive radio ad hoc networks (CRNs), i.e., how each individual node's maximum throughput scales as the number of nodes in the network increases. This effort is critical to the fundamental understanding of the scalability of such network. However, due to the heterogeneity in available frequency bands at each node, the asymptotic capacity is much more difficult to develop than prior efforts for other types of wireless networks. To overcome this difficulty, we introduce two auxiliary networks ζ and α to analyze the capacity upper and lower bounds. We derive the capacity results under both the protocol model and the physical model. Further, we show that the seminal results developed by Gupta and Kumar for the simple single-channel single-radio (SC-SR) networks are special cases under the results for CRNs. 2. Asymptotic Capacity of Multi-hop MIMO Ad Hoc Networks. Multi-input multi-output (MIMO) is a key technology to increase the capacity of wireless networks. Although there has been extensive work on MIMO at the physical and link layers, there has been limited work on MIMO at the network layer (i.e., multi-hop MIMO ad hoc network), particularly results on capacity scaling laws. In this work, we investigate capacity scaling laws for MIMO ad hoc networks. Our goal is to find the achievable throughput of each node as the number of nodes in the network increases. We employ a MIMO network model that captures spatial multiplexing (SM) and interference cancellation (IC). We show that for a MIMO network with n randomly located nodes, each equipped with γ antennas and a rate of W on each data stream, the achievable throughput of each node is Θ(γW/√ n ln n). 3. Toward Simple Criteria for Establishing Capacity Scaling Laws. Capacity scaling laws offer fundamental understanding on the trend of user throughput behavior when the network size increases. Since the seminal work of Gupta and Kumar, there have been tremendous efforts developing capacity scaling laws for ad hoc networks with various advanced physical layer technologies. These efforts led to different custom-designed approaches, most of which were intellectually challenging and lacked universal properties that can be extended to address scaling laws of ad hoc networks with a different physical layer technology. In this work, we present a set of simple yet powerful general criteria that one can apply to quickly determine the capacity scaling laws for various physical layer technologies under the protocol model. We prove the correctness of our proposed criteria and validate them through a number of case studies, such as ad hoc networks with directional antenna, MIMO, cognitive radio, multi-channel and multi-radio, and multiple packet reception. These simple criteria will serve as powerful tools to networking researchers to obtain throughput scaling laws of ad hoc networks under different physical layer technologies, particularly those to appear in the future. 4. Exploiting SIC forMulti-hopWireless Networks. There is a growing interest on exploiting interference (rather than avoiding it) to increase network throughput. In particular, the so-called successive interference cancellation (SIC) scheme appears very promising, due to its ability to enable concurrent receptions from multiple transmitters and interference rejection. However, due to some stringent constraints and limit, SIC alone is inadequate to handle all concurrent interference. We advocate a joint interference exploitation and avoidance approach, which combines the best of interference exploitation and interference avoidance, while avoiding each's pitfalls. We discuss the new challenges of such a new approach in a multi-hop wireless network and propose a formal optimization framework, with cross-layer formulation of physical, link, and network layers. This framework offers a rather complete design space for SIC to squeeze the most out of interference. The goal of this effort is to lay a mathematical foundation for modeling and analysis of a joint interference exploitation and avoidance scheme in a multi-hop wireless network. Through modeling and analysis, we develop a tractable model that is suitable for studying a broad class of network throughput optimization problems. To demonstrate the practical utility of our model, we conduct a case study. Our numerical results affirm the validity of our model and give insights on how SIC can optimally interact with an interference avoidance scheme. 5. Throughput Optimization with Network-wide Energy Constraint. Conserving network wide energy consumption is becoming an increasingly important concern for network operators. In this work, we study network-wide energy conservation problem which we hope will offer insights to both network operators and users. Specifically, we study how to maximize network throughput under a network-wide energy constraint for a general multi-hop wireless network. We formulate this problem as a mixed-integer nonlinear program (MINLP). We propose a novel piece-wise linear approximation to transform the nonlinear constraints into linear constraints. We prove that the solution developed under this approach is near optimal with guaranteed performance bound. 6. Bicriteria Optimization in Multi-hop Wireless Networks. Network throughput and energy consumption are two important performance metrics for a multi-hop wireless network. Current state-of-the-art is limited to either maximizing throughput under some energy constraint or minimizing energy consumption while satisfying some throughput requirement. However, the important problem of how to optimize both objectives simultaneously remains open. In this work, we take a multicriteria optimization approach to offer a systematic study on the relationship between the two performance objectives. We show that the solution to the multicriteria optimization problem characterizes the envelope of the entire throughput energy region, i.e., the so-called optimal throughput-energy curve. We prove some important properties of the optimal throughput-energy curve. For case study, we consider both linear and nonlinear throughput functions. For the linear case, we characterize the optimal throughput-energy curve precisely through parametric analysis, while for the nonlinear case, we use a piece-wise linear approximation to approximate the optimal throughput-energy curve with arbitrary accuracy. Our results offer important insights on exploiting the trade-off between the two performance metrics.
Ph. D.

This Record of Study contains the details of an optimization model developed for Shell Oil Co. This model will be used during the strategic design process of a supply chain for a new technology commercialization. Unlike traditional supply chain deterministic optimization, this model incorporates different levels of uncertainty at suppliers' nominal capacity. Because of the presence of uncertainty at the supply stage, the objective of this model is to define the best diversification and safety stock level allocated to each supplier, which minimize the total expected supply chain cost. We propose a Monte Carlo approach for scenario generation, a two-stage non-linear formulation and the Sample Average Approximation (SAA) procedure to solve the problem near optimality. We also propose a simple heuristic procedure to avoid the nonlinearity issue. The sampling and heuristic optimization procedures were implemented in a spreadsheet with a user's interface. The main result of this development is the analysis of the impact of diversification in strategic sourcing decisions, in the presence of stochastic supply disruptions.

La gestion des revenus d’un réseau de compagnies aériennes, un des problèmes le plus critiques dans le secteur du transport aérien, a reçu une attention significative depuis ces dernière décennies. Cependant, de nombreuses problématiques doivent encore être traitées. Cette thèse étudie quatre nouveaux problèmes de la gestion des revenus dans un réseau de compagnies aériennes. D'abord, un problème de dimensionnement de capacité du réseau avec alliances concurrentes est étudié. Dans ce problème, les concurrences horizontales et verticales sont considérées et la demande est supposée déterministe. L’objectif est de maximiser les revenus globaux de l’alliance en déterminant la capacité (en nombre de places) dans les vols pour chaque classe tarifaire de chaque compagnie. Le problème est formulé en programmation linéaire en nombres entiers et résolu à l’aide du solveur CPLEX. Deuxièmement, un problème intégrant la localisation de p-hub médian et le dimensionnement des capacités (places) est étudié pour maximiser une combinaison du bénéfice moyen et du bénéfice au pire cas. Pour ce problème, un seul hub à capacité illimitée est considéré. De plus, les incertitudes sur la demande sont représentées à l’aide d’un ensemble fini des scénarios. Le problème est formulé en programmation stochastique à deux étapes. Ensuite, un algorithme génétique (GA) est proposé pour résoudre le problème pour chaque scénario. Les résultats numériques montrent que la méthode est meilleure que celles dans la littérature qui considèrent uniquement le bénéfice moyen. Le troisième problème étudié est une extension naturelle du deuxième dans lequel la capacité de hub à localiser est limitée et les perturbations qui peuvent impacter la capacité du hub, telles que des conditions météorologiques, sont prises en compte. Deux formulations du problème sont proposées : (1) une programmation stochastique à deux étapes sur la base des scénarios, et (2) optimisation hybride de programmation stochastique à deux étapes à l’aide de pondération. Ensuite, l’approximation moyenne par échantillonnage (SAA) et le GA sont appliqués pour résoudre le problème, respectivement. Les résultats numériques montrent que la SAA est plus performante que le GA. Le quatrième problème est aussi une extension du deuxième problème où la compagnie aérienne doit respecter le niveau d'émissions de CO2 imposé. Le problème est modélisé en programmation stochastique à deux étapes sur la base des scénarios. De plus, une méthode SAA est proposée pour sa résolution
As one of critical problems in aviation industry, airline network revenue management has received significant attention in recent decades. However, many issues still need to be addressed. This thesis investigates four new airline network revenue management problems. Firstly, a network capacity allocation problem with competitive alliances is studied. In this problem, horizontal and vertical competitions and deterministic demand are considered. The aim is to maximize the global alliance revenue by determining the (seat) capacities in flights for each fare class of each airline. The problem is formulated into a mixed integer programming and is solved by a commercial solver CPLEX. Secondly, an integrated p-hub median location and (seat) capacity allocation problem is investigated to maximize the combined average-case and worst-case profits of an airline. For this problem, an uncapacitated hub is considered and uncertain demand is represented by a finite set of scenarios. The studied problem is formulated based on a two-stage stochastic programming framework. Then a Genetic Algorithm (GA) is proposed to solve the problem for each scenario. Computational results show that the proposed method outperforms those in the literature only considering average-case profit. The third studied problem is a generalization of the second one in which the capacity of hub to be located is limited and disruptions which can impact airline hub capacity, such as adverse weather, are considered. Two formulations of the problem are proposed based on : (1) a scenario-based two-stage stochastic programming, and (2) a weight-based hybrid two-stage stochastic programming-robust optimization framework. Then a Sample Average Approximation (SAA) method and a GA are applied to solve them, respectively. Computational results show that the SAA is more effective than the GA. The fourth problem is also an extension of the second one where an airline is subjected to a CO2 emission limit. The problem is modeled into a scenario-based two-stage stochastic programming. And a SAA method is proposed to solve it

Doctor of Philosophy
Department of Electrical and Computer Engineering
Balasubramaniam Natarajan
In recent years, there has been a rapid expansion in the development and use of low-power, low-cost wireless modules with sensing, computing, and communication functionality. A wireless sensor network (WSN) is a group of these devices networked together wirelessly. Wireless sensor networks have found widespread application in infrastructure, environmental, and human health monitoring, surveillance, and disaster management. While there are many interesting problems within the WSN framework, we address the challenge of energy availability in a WSN tasked with a cooperative objective. We develop approximation algorithms and execute an analysis of concave utility maximization in resource constrained systems. Our analysis motivates a unique algorithm which we apply to resource management in WSNs. We also investigate energy harvesting as a way of improving system lifetime. We then analyze the effect of using these limited and stochastically available communication resources on the convergence of decentralized optimization techniques. The main contributions of this research are: (1) new optimization formulations which explicitly consider the energy states of a WSN executing a cooperative task; (2) several analytical insights regarding the distributed optimization of resource constrained systems; (3) a varied set of algorithmic solutions, some novel to this work and others based on extensions of existing techniques; and (4) an analysis of the effect of using stochastic resources (e.g., energy harvesting) on the performance of decentralized optimization methods. Throughout this work, we apply our developments to distribution estimation and rate maximization. The simulation results obtained help to provide verification of algorithm performance. This research provides valuable intuition concerning the trade-offs between energy-conservation and system performance in WSNs.

This dissertation presents several novel accomplishments in the research area of Wireless Body Area Networks (WBANs), including in vivo channel characterization, optimization and game theoretical approaches for energy efficiency in WBANs. First, we performed the in vivo path loss simulations with HFSS human body model, built a phenomenological model for the distance and frequency dependent path loss, and also investigated angle dependent path loss of the in vivo wireless channel. Simulation data is produced in the range of 0.4−6 GHz for frequency, a wide range of distance and different angles. Based on the measurements, we produce mathematical models for in body, on body and out of body regions. The results show that our proposed models fit well with the simulated data. Based on our research, a comparison of in vivo and ex vivo channels is summarized. Next, we proposed two algorithms for energy efficiency optimization in WBANs and evaluated their performance. In the next generation wireless networks, where devices and sensors are heterogeneous and coexist in the same geographical area creating possible collisions and interference to each other, the battery power needs to be efficiently used. The first algorithm, Cross-Layer Optimization for Energy Efficiency (CLOEE), enables us to carry out a cross-layer resource allocation that addresses the rate and reliability trade-off in the PHY, as well as the frame size optimization and transmission efficiency for the MAC layer. The second algorithm, Energy Efficiency Optimization of Channel Access Probabilities (EECAP), studies the case where the nodes access the medium in a probabilistic manner and jointly determines the optimal access probability and payload frame size for each node. These two algorithms address the problem from an optimization perspective and they are both computationally efficient and extensible to 5G/IoT networks. Finally, in order to switch from a centralized method to a distributed optimization method, we study the energy efficiency optimization problem from a game theoretical point of view. We created a game theoretical model for energy efficiency in WBANs and investigated its best response and Nash Equilibrium of the single stage, non-cooperative game. Our results show that cooperation is necessary for efficiency of the entire system. Then we used two approaches, Correlated Equilibrium and Repeated Game, to improve the overall efficiency and enable some level of cooperation in the game.

Air traffic flow management is a critical component of air transport operations because at some point in time, often very frequently, one of more of the critical resources in the air transportation network has significantly reduced capacity, resulting in congestion and delay for airlines and other entities and individuals who use the network. Typically, these “bottlenecks” are noticed at a given airport or terminal area, but they also occur in en route airspace. The two-stage combinatorial optimization framework for air traffic flow management under constrained capacity that is presented in this thesis, represents a important step towards the full consideration of the combinatorial nature of air traffic flow management decision that is often ignored or dealt with via priority-based schemes. It also illustrates the similarities between two traffic flow management problems that heretofore were considered to be quite distinct. The runway systems at major airports are highly constrained resources. From the perspective of arrivals, unnecessary delays and emissions may occur during peak periods when one or more runways at an airport are in great demand while other runways at the same airport are operating under their capacity. The primary cause of this imbalance in runway utilization is that the traffic flow into and out of the terminal areas is asymmetric (as a result of airline scheduling practices), and arrivals are typically assigned to the runway nearest the fix through which they enter the terminal areas. From the perspective of departures, delays and emissions occur because arrivals take precedence over departures with regard to the utilization of runways (despite the absence of binding safety constraints), and because arrival trajectories often include level segments that ensure “procedural separation” from arriving traffic while planes are not allowed to climb unrestricted along the most direct path to their destination. Similar to the runway systems, the terminal radar approach control facilities (TRACON) boundary fixes are also constrained resources of the terminal airspace. Because some arrival traffic from different airports merges at an arrival fix, a queue for the terminal areas generally starts to form at the arrival fix, which are caused by delays due to heavy arriving traffic streams. The arrivals must then absorb these delays by path stretching and adjusting their speed, resulting in unplanned fuel consumption. However, these delays are often not distributed evenly. As a result, some arrival fixes experience severe delays while, similar to the runway systems, the other arrival fixes might experience no delays at all. The goal of this thesis is to develop a combined optimization approach for terminal airspace flow management that assigns a TRACON boundary fix and a runway to each flight while minimizing the required fuel burn and emissions. The approach lessens the severity of terminal capacity shortage caused by and imbalance of traffic demand by shunting flights from current positions to alternate runways. This is done by considering every possible path combination. To attempt to solve the congestion of the terminal airspace at both runways and arrival fixes, this research focuses on two sequential optimizations. The fix assignments are dealt with by considering, simultaneously, the capacity constraints of fixes and runways as well as the fuel consumption and emissions of each flight. The research also develops runway assignments with runway scheduling such that the total emissions produced in the terminal area and on the airport surface are minimized. The two-stage sequential framework is also extended to en route airspace. When en route airspace loses its capacity for any reason, e.g. severe weather condition, air traffic controllers and flight operators plan flight schedules together based on the given capacity limit, thereby maximizing en route throughput and minimizing flight operators' costs. However, the current methods have limitations due to the lacks of consideration of the combinatorial nature of air traffic flow management decision. One of the initial attempts to overcome these limitations is the Collaborative Trajectory Options Program (CTOP), which will be initiated soon by the Federal Aviation Administration (FAA). The developed two-stage combinatorial optimization framework fits this CTOP perfectly from the flight operator's perspective. The first stage is used to find an optimal slot allocation for flights under satisfying the ration by schedule (RBS) algorithm of the FAA. To solve the formulated first stage problem efficiently, two different solution methodologies, a heuristic algorithm and a modified branch and bound algorithm, are presented. Then, flights are assigned to the resulting optimized slots in the second stage so as to minimize the flight operator's costs.

The primary goal of artificial intelligence research is to develop a machine capable of learning to solve disparate real-world tasks autonomously, without relying on specialized problem-specific inputs. This dissertation suggests that such machines are realistic: If No Free Lunch theorems were to apply to all real-world problems, then the world would be utterly unpredictable. In response, the dissertation proposes the information-maximization principle, which claims that the optimal optimization methods make the best use of the information available to them. This principle results in a new algorithm, evolutionary annealing, which is shown to perform well especially in challenging problems with irregular structure.
text

碩士
國立臺灣科技大學
資訊管理系
95
Recently, an efficient reversible data hiding algorithm by Ni et al. was presented. Their algorithm can recover the original image without any distortion and its PSNR lower bound is higher than that of all existing reversible data hiding algorithms. Based on dynamic programming approach, this paper presents an improved data hiding algorithm which achieves the capacity maximization requirement. Under the CorelDraw X3 testing images, experimental results demonstrate that our proposed improved data hiding algorithm has maximal capacity improvement ratio, 2%, and has same image quality when compared to the previous algorithm by Ni et al.

This paper presents an optimal method and a heuristic approach which aims at maximizing the profit when responding to a set of customer enquiries under limited capacity. The model takes into consideration the quantity of available-to-promise (ATP) which measures the capability to fill customer orders, along with enquiry quantity and product price. The optimal method and the heuristic approach are tested using ATP, product price and enquiry quantity each at their different levels. From the example conducted, it is found that (1) the optimal model can help to make appropriate decision for selecting a subset of enquiries, and (2) the heuristic approach can produce a result within 5% from the optimum achieved by optimal method for most parameter settings.
Singapore-MIT Alliance (SMA)

碩士
國立中山大學
通訊工程研究所
98
In a CR network, the maximum SUs throughput is desired generally. In this thesis, We investigate and formulate the problem of the secondary users’ throughput maximization in cognitive radio systems under channel capacity constrain. By using KKT theorem, an objec- tive function is developed to obtain an optimal solution for the SU throughput maximization problem. An numerical example is also presented for illustration. The most important results revealed in the example show that the maximum SU throughput is achieved by cooperating an optimal number of SU pairs instead of cooperating all the SU pairs.