Dissertations / Theses on the topic 'Parallel Random Access Machine'

Graph algorithms are concerned with the algorithmic aspects of solving graph problems. The problems are motivated from and have application to diverse areas of computer science, engineering and other disciplines. Problems arising from these areas of application are good candidates for parallelization since they often have both intense computational needs and stringent response time requirements. Motivated by these concerns, this thesis investigates parallel algorithms for these kinds of graph problems that have at least one of the following properties: the problems involve some type of dynamic updates; the sparsification technique is applicable; or the problems are closely related to communications network issues. The models of parallel computation used in our studies are the Parallel Random Access Machine (PRAM) model and the practical interconnection network models such as meshes and hypercubes. ¶ Consider a communications network which can be represented by a graph G = (V;E), where V is a set of sites (processors), and E is a set of links which are used to connect the sites (processors). In some cases, we also assign weights and/or directions to the edges in E. Associated with this network, there are many problems such as (i) whether the network is k-edge (k-vertex) connected withfixed k; (ii) whether there are k-edge (k-vertex) disjoint paths between u and v for a pair of given vertices u and v after the network is dynamically updated by adding and/or deleting an edge etc; (iii) whether the sites in the network can communicate with each other when some sites and links fail; (iv) identifying the first k edges in the network whose deletion will result in the maximum increase in the routing cost in the resulting network for fixed k; (v) how to augment the network at optimal cost with a given feasible set of weighted edges such that the augmented network is k-edge (k-vertex) connected; (vi) how to route messages through the network efficiently. In this thesis we answer the problems mentioned above by presenting efficient parallel algorithms to solve them. As far as we know, most of the proposed algorithms are the first ones in the parallel setting. ¶ Even though most of the problems concerned in this thesis are related to communications networks, we also study the classic edge-coloring problem. The outstanding difficulty to solve this problem in parallel is that we do not yet know whether or not it is in NC. In this thesis we present an improved parallel algorithm for the problem which needs [bigcircle]([bigtriangleup][superscript 4.5]log [superscript 3] [bigtriangleup] log n + [bigtriangleup][superscript 4] log [superscript 4] n) time using [bigcircle](n[superscript 2][bigtriangleup] + n[bigtriangleup][superscript 3]) processors, where n is the number of vertices and [bigtriangleup] is the maximum vertex degree. Compared with a previously known result on the same model, we improved by an [bigcircle]([bigtriangleup][superscript 1.5]) factor in time. The non-trivial part is to reduce this problem to the edge-coloring update problem. We also generalize this problem to the approximate edge-coloring problem by giving a faster parallel algorithm for the latter case. ¶ Throughout the design and analysis of parallel graph algorithms, we also find a technique called the sparsification technique is very powerful in the design of efficient sequential and parallel algorithms on dense undirected graphs. We believe that this technique may be useful in its own right for guiding the design of efficient sequential and parallel algorithms for problems in other areas as well as in graph theory.

Memory wall is becoming a more and more serious bottleneck of the processing speed of microprocessors. The mismatch between CPUs and memories has been increasing since three decades ago. SRAM was introduced as the bridge between the main memory and the CPU. SRAM is designed to be on the same die with CPU and stores temporary data and instructions that are to be processed by the CPU. Thus, the performance of SRAMs has a direct impact on the performance of CPUs. With the application of mass amount data to be processed nowadays, there is a great need for high-performance CPUs. Three dimensional CPUs and CPUs that are specifically designed for machine learning are gaining popularity. The objective of this work is to design high-performance SRAM for these two emerging applications. Firstly, a novel delay cell based on dummy TSV is proposed to replace traditional delay cells for better timing control. Secondly, a unique SRAM with novel architecture is custom designed for a high-performance machine learning processor. Post-layout simulation shows that the SRAM works well with the processing core and its design is optimized to work well with machine learning processors based on convolutional neural networks. A prototype of the SRAM is also tapped out to further verify our design.

Les protocoles de communications à accès aléatoires sont des candidats prometteurs pour les futurs systèmes de communications sans fil dédiés aux applications machine à machine (M2M). Ces méthodes d’accès sont généralement basées sur des techniques d'accès aléatoires mettant en œuvre des concepts simples de sondage de canal et de report de la transmission pour réduire les collisions, tout en évitant l'utilisation d'ordonnanceurs complexes. Parmi les différents protocoles, Carrier sense multiple access/collision avoidance with a Request-To-Send/Clear-To-Send (CSMA/CA-RTS/CTS) est un protocole qui pourrait être adopté pour les scénarios de M2M. Cette approche est efficace pour éviter les collisions entre les paquets de données. Cependant dans le cas d’un réseau très dense, les performances sont dégradées à cause de la forte probabilité de collisions. Pour atténuer cet effet, les collisions entre les messages de contrôles RTS doivent être réduites. Cette thèse propose de résoudre ce problème en divisant le canal commun en sous-canaux pour transmettre les messages de contrôle de demande d’accès au canal ; le canal commun est utilisé dans son ensemble pour la transmission de données. L’ajout d’un degré de liberté pour le message de demande d’accès permet de réduire la probabilité de collision, et donc d’améliorer les performances du système notamment dans des scénarios avec des nombres importants de nœuds souhaitant communiquer. Dans ce travail, nous dérivons ainsi une solution complète de méthode d’accès en s'appuyant sur le CSMA / CA - RTS / CTS et en multiplexant une configuration multi-canal pour les messages RTS et un canal unique pour la transmission de données. Une version améliorée, basée sur l'ordonnancement des utilisateurs, est également étudiée. Un modèle analytique a été développé, analysé et validé par simulations. Celui-ci est une extension du modèle Bianchi. Les performances en termes de débit saturé, de temps de transmission et de la probabilité de rejet de paquets sont discutées. Enfin, les impacts liés à la prise en compte d’une couche physique de type multi porteuses sont discutés dans le dernier chapitre<br>Opportunistic protocols are promising candidates for future wireless systems dedicated to machine to machine (M2M) communication. Such protocols are usually based on a random access with simple techniques of medium sensing and deferring to reduce collisions while avoiding the use of complex schedulers. Among different protocols, Carrier sense multiple access/collision avoidance with a Request-To-Send/Clear-To-Send (CSMA/CA-RTS/CTS) is an opportunistic protocol which could be adopted for M2M scenarios. Such approach is efficient to avoid collisions between data packets but in a very dense network, the random access used to send the RTS suffers itself from a high probability of collision which degrades the performance. In order to mitigate this effect, RTS collisions should be reduced. This thesis proposes to address this issue by splitting the common channel in sub-channels for transmitting the RTS messages. While the common channel is used as a whole for data transmission. Multiple nodes can then contend in time and frequency for these RTS sub-channels, thereby reducing RTS collisions and increasing overall efficiency. In this work, we thus derive a complete protocol solution relying on CSMA/CA - RTS/CTS multiplexing a multi-channel configuration for RTS messages and a unique channel for data transmission. An enhanced version based on users scheduling is integrated as well. In this thesis, the proposed protocol is investigated from a joint PHY-MAC point of view. This strategy is shown to provide better system performance particularly for loaded networks. An accurate analytical model derived as a straightforward extension of the Bianchi model is analyzed and validated by simulations. Performance in terms of saturation throughput, transmission delay and packet drop probability is discussed

En la actualidad, la Internet de las Cosas (Internet of Things, IoT) es una tecnología esencial para la próxima generación de sistemas inalámbricos. La conectividad es la base de IoT, y el tipo de acceso requerido dependerá de la naturaleza de la aplicación. Uno de los principales facilitadores del entorno IoT es la comunicación machine-to-machine (M2M) y, en particular, su enorme potencial para ofrecer conectividad ubicua entre dispositivos inteligentes. Las redes celulares son la elección natural para las aplicaciones emergentes de IoT y M2M. Un desafío importante en las redes celulares es conseguir que la red sea capaz de manejar escenarios de acceso masivo en los que numerosos dispositivos utilizan comunicaciones M2M. Por otro lado, los sistemas celulares han experimentado un tremendo desarrollo en las últimas décadas: incorporan tecnología sofisticada y nuevos algoritmos para ofrecer una amplia gama de servicios. El modelado y análisis del rendimiento de estas redes multiservicio es también una tarea desafiante que podría requerir un gran esfuerzo computacional. Para abordar los desafíos anteriores, nos centramos en primer lugar en el diseño y la evaluación de las prestaciones de nuevos mecanismos de control de acceso para hacer frente a las comunicaciones masivas M2M en redes celulares. Posteriormente nos ocupamos de la evaluación de prestaciones de redes multiservicio y proponemos una nueva técnica analítica que ofrece precisión y eficiencia computacional. Nuestro principal objetivo es proporcionar soluciones para aliviar la congestión en la red de acceso radio cuando un gran número de dispositivos M2M intentan conectarse a la red. Consideramos los siguientes tipos de escenarios: (i) los dispositivos M2M se conectan directamente a las estaciones base celulares, y (ii) forman grupos y los datos se envían a concentradores de tráfico (gateways) que les proporcionan acceso a la infraestructura. En el primer escenario, dado que el número de dispositivos añadidos a la red aumenta continuamente, esta debería ser capaz de manejar el considerable incremento en las solicitudes de acceso. El 3rd Generation Partnership Project (3GPP) ha propuesto el access class barring (ACB) como una solución práctica para el control de congestión en la red de acceso radio y la red troncal. El ajuste correcto de los parámetros de ACB de acuerdo con la intensidad del tráfico es crítico, pero cómo hacerlo de forma dinámica y autónoma es un problema complejo cuya solución no está recogida en las especificaciones del 3GPP. Esta tesis doctoral contribuye al análisis del rendimiento y al diseño de nuevos algoritmos que implementen efectivamente este mecanismo, y así superar los desafíos introducidos por las comunicaciones masivas M2M. En el segundo escenario, dado que la heterogeneidad de los dispositivos IoT y las arquitecturas celulares basadas en hardware imponen desafíos aún mayores para permitir una comunicación flexible y eficiente en los sistemas inalámbricos 5G, esta tesis doctoral también contribuye al diseño de software-defined gateways (SD-GWs) en una nueva arquitectura propuesta para redes inalámbricas definidas por software que se denomina SoftAir. Esto permite manejar tanto un gran número de dispositivos como el volumen de datos que estarán vertiendo en la red. Otra contribución de esta tesis doctoral es la propuesta de una técnica novedosa para el análisis de prestaciones de redes multiservicio de alta capacidad que se basa en un nuevo enfoque del modelizado analítico de sistemas que operan a diferentes escalas temporales. Este enfoque utiliza el análisis del transitorio de una serie de subcadenas absorbentes y lo denominamos absorbing Markov chain approximation (AMCA). Nuestros resultados muestran que para un coste computacional dado, AMCA calcula los parámetros de prestaciones habituales de un sistema con mayor precisión, en comparación con los resultados obtenidos por otr<br>Nowadays, Internet of Things (IoT) is an essential technology for the upcoming generation of wireless systems. Connectivity is the foundation for IoT, and the type of access required will depend on the nature of the application. One of the leading facilitators of the IoT environment is machine-to-machine (M2M) communication, and particularly, its tremendous potential to offer ubiquitous connectivity among intelligent devices. Cellular networks are the natural choice for emerging IoT and M2M applications. A major challenge in cellular networks is to make the network capable of handling massive access scenarios in which myriad devices deploy M2M communications. On the other hand, cellular systems have seen a tremendous development in recent decades; they incorporate sophisticated technology and algorithms to offer a broad range of services. The modeling and performance analysis of these large multi-service networks is also a challenging task that might require high computational effort. To address the above challenges, we first concentrate on the design and performance evaluation of novel access control schemes to deal with massive M2M communications. Then, we focus on the performance evaluation of large multi-service networks and propose a novel analytical technique that features accuracy and computational efficiency. Our main objective is to provide solutions to ease the congestion in the radio access or core network when massive M2M devices try to connect to the network. We consider the following two types of scenarios: (i) massive M2M devices connect directly to cellular base stations, and (ii) they form clusters and the data is forwarded to gateways that provide them with access to the infrastructure. In the first scenario, as the number of devices added to the network is constantly increasing, the network should handle the considerable increment in access requests. Access class barring (ACB) is proposed by the 3rd Generation Partnership Project (3GPP) as a practical congestion control solution in the radio access and core network. The proper tuning of the ACB parameters according to the traffic intensity is critical, but how to do so dynamically and autonomously is a challenging task that has not been specified. Thus, this dissertation contributes to the performance analysis and optimal design of novel algorithms to implement effectively this barring scheme and overcome the challenges introduced by massive M2M communications. In the second scenario, since the heterogeneity of IoT devices and the hardware-based cellular architectures impose even greater challenges to enable flexible and efficient communication in 5G wireless systems, this dissertation also contributes to the design of software-defined gateways (SD-GWs) in a new architecture proposed for wireless software-defined networks called SoftAir. The deployment of these SD-GWs represents an alternative solution aiming at handling both a vast number of devices and the volume of data they will be pouring into the network. Another contribution of this dissertation is to propose a novel technique for the performance analysis of large multi-service networks. The underlying complexity of the network, particularly concerning its size and the ample range of configuration options, makes the solution of the analytical models computationally costly. However, a typical characteristic of these networks is that they support multiple types of traffic flows operating at different time-scales. This time-scale separation can be exploited to reduce considerably the computational cost associated to determine the key performance indicators. Thus, we propose a novel analytical modeling approach based on the transient regime analysis, that we name absorbing Markov chain approximation (AMCA). For a given computational cost, AMCA finds common performance indicators with greater accuracy, when compared to the results obtained by other approximate methods proposed in the literature.<br>En l'actualitat, la Internet de les Coses (Internet of Things, IoT) és una tecnologia essencial per a la propera generació de sistemes sense fil. La connectivitat és la base d'IoT, i el tipus d'accés requerit dependrà de la naturalesa de l'aplicació. Un dels principals facilitadors de l'entorn IoT és la comunicació machine-to-machine (M2M) i, en particular, el seu enorme potencial per oferir connectivitat ubiqua entre dispositius intel · ligents. Les xarxes mòbils són l'elecció natural per a les aplicacions emergents de IoT i M2M. Un desafiament important en les xarxes mòbils que actualment está rebent molta atenció és aconseguir que la xarxa siga capaç de gestionar escenaris d'accés massiu en què una gran quantitat de dispositius utilitzen comunicacions M2M. D'altra banda, els sistemes mòbils han experimentat un gran desenvolupament en les últimes dècades: incorporen tecnologia sofisticada i nous algoritmes per oferir una àmplia gamma de serveis. El modelatge i análisi del rendiment d'aquestes xarxes multiservei és també un desafiament important que podria requerir un gran esforç computacional. Per abordar els desafiaments anteriors, en aquesta tesi doctoral ens centrem en primer lloc en el disseny i l'avaluació de les prestacions de nous mecanismes de control d'accés per fer front a les comunicacions massives M2M en xarxes cel · lulars. Posteriorment ens ocupem de l'avaluació de prestacions de xarxes multiservei i proposem una nova tècnica analítica que ofereix precisió i eficiència computacional. El nostre principal objectiu és proporcionar solucions per a alleujar la congestió a la xarxa d'accés ràdio quan un gran nombre de dispositius M2M intenten connectar-se a la xarxa. Considerem els dos tipus d'escenaris següents: (i) els dispositius M2M es connecten directament a les estacions base cel · lulars, i (ii) formen grups i les dades s'envien a concentradors de trànsit (gateways) que els proporcionen accés a la infraestructura. En el primer escenari, atès que el nombre de dispositius afegits a la xarxa augmenta contínuament, aquesta hauria de ser capaç de gestionar el considerable increment en les sol · licituds d'accés. El 3rd Generation Partnership Project (3GPP) ha proposat l'access class barring (ACB) com una solució pràctica per al control de congestió a la xarxa d'accès ràdio i la xarxa troncal. L'ajust correcte dels paràmetres d'ACB d'acord amb la intensitat del trànsit és crític, però com fer-ho de forma dinàmica i autònoma és un problema complex, la solució del qual no està recollida en les especificacions del 3GPP. Aquesta tesi doctoral contribueix a l'anàlisi del rendiment i al disseny de nous algoritmes que implementen efectivament aquest mecanisme, i així superar els desafiaments introduïts per les comunicacions massives M2M en les xarxes mòbils actuals i futures. En el segon escenari, atès que l'heterogeneïtat dels dispositius IoT i les arquitectures cel · lulars basades en hardware imposen desafiaments encara més grans per permetre una comunicació flexible i eficient en els sistemes sense fil 5G, aquesta tesi doctoral també contribueix al disseny de software-defined gateways (SD-GWS) en una nova arquitectura proposada per a xarxes sense fils definides per programari que s'anomena SoftAir. Això permet gestionar tant un gran nombre de dispositius com el volum de dades que estaran abocant a la xarxa. Una altra contribució d'aquesta tesi doctoral és la proposta d'una tècnica innovadora per a l'anàlisi de prestacions de xarxes multiservei d'alta capacitat que es basa en un nou enfocament del modelitzat analític de sistemes que operen a diferents escales temporals. Aquest enfocament utilitza l'anàlisi del transitori d'una sèrie de subcadenes absorbents i l'anomenem absorbing Markov chain Approximation (AMCA). Els nostres resultats mostren que per a un cost computacional donat, AMCA calcula els paràmetres de prestacions habituals d<br>Tello Oquendo, LP. (2018). Design and Performance Analysis of Access Control Mechanisms for Massive Machine-to-Machine Communications in Wireless Cellular Networks [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/107946<br>TESIS

The next-generation electric power system, known as smart grid, relies on a robust and reliable underlying communication infrastructure to improve the efficiency of electricity distribution. Cellular networks, e.g., LTE/LTE-A systems, appear as a promising technology to facilitate the smart grid evolution. Their inherent performance characteristics and well-established ecosystem could potentially unlock unprecedented use cases, enabling real-time and autonomous distribution grid operations. However, cellular technology was not originally intended for smart grid communication, associated with highly-reliable message exchange and massive device connectivity requirements. The fundamental differences between smart grid and human-type communication challenge the classical design of cellular networks and introduce important research questions that have not been sufficiently addressed so far. Motivated by these challenges, this doctoral thesis investigates novel radio access network (RAN) design principles and performance analysis for the seamless integration of smart grid traffic in future cellular networks. Specifically, we focus on addressing the fundamental RAN problems of network scalability in massive smart grid deployments and radio resource management for smart grid and human-type traffic. The main objective of the thesis lies on the design, analysis and performance evaluation of RAN mechanisms that would render cellular networks the key enabler for emerging smart grid applications. The first part of the thesis addresses the radio access limitations in LTE-based networks for reliable and scalable smart grid communication. We first identify the congestion problem in LTE random access that arises in large-scale smart grid deployments. To overcome this, a novel random access mechanism is proposed that can efficiently support real-time distribution automation services with negligible impact on the background traffic. Motivated by the stringent reliability requirements of various smart grid operations, we then develop an analytical model of the LTE random access procedure that allows us to assess the performance of event-based monitoring traffic under various load conditions and network configurations. We further extend our analysis to include the relation between the cell size and the availability of orthogonal random access resources and we identify an additional challenge for reliable smart grid connectivity. To this end, we devise an interference- and load-aware cell planning mechanism that enhances reliability in substation automation services. Finally, we couple the problem of state estimation in wide-area monitoring systems with the reliability challenges in information acquisition. Using our developed analytical framework, we quantify the impact of imperfect communication reliability in the state estimation accuracy and we provide useful insights for the design of reliability-aware state estimators. The second part of the thesis builds on the previous one and focuses on the RAN problem of resource scheduling and sharing for smart grid and human-type traffic. We introduce a novel scheduler that achieves low latency for distribution automation traffic while resource allocation is performed in a way that keeps the degradation of cellular users at a minimum level. In addition, we investigate the benefits of Device-to-Device (D2D) transmission mode for event-based message exchange in substation automation scenarios. We design a joint mode selection and resource allocation mechanism which results in higher data rates with respect to the conventional transmission mode via the base station. An orthogonal resource partition scheme between cellular and D2D links is further proposed to prevent the underutilization of the scarce cellular spectrum. The research findings of this thesis aim to deliver novel solutions to important RAN performance issues that arise when cellular networks support smart grid communication.<br>Las redes celulares, p.e., los sistemas LTE/LTE-A, aparecen como una tecnología prometedora para facilitar la evolución de la próxima generación del sistema eléctrico de potencia, conocido como smart grid (SG). Sin embargo, la tecnología celular no fue pensada originalmente para las comunicaciones en la SG, asociadas con el intercambio fiable de mensajes y con requisitos de conectividad de un número masivo de dispositivos. Las diferencias fundamentales entre las comunicaciones en la SG y la comunicación de tipo humano desafían el diseño clásico de las redes celulares e introducen importantes cuestiones de investigación que hasta ahora no se han abordado suficientemente. Motivada por estos retos, esta tesis doctoral investiga los principios de diseño y analiza el rendimiento de una nueva red de acceso radio (RAN) que permita una integración perfecta del tráfico de la SG en las redes celulares futuras. Nos centramos en los problemas fundamentales de escalabilidad de la RAN en despliegues de SG masivos, y en la gestión de los recursos radio para la integración del tráfico de la SG con el tráfico de tipo humano. El objetivo principal de la tesis consiste en el diseño, el análisis y la evaluación del rendimiento de los mecanismos de las RAN que convertirán a las redes celulares en el elemento clave para las aplicaciones emergentes de las SGs. La primera parte de la tesis aborda las limitaciones del acceso radio en redes LTE para la comunicación fiable y escalable en SGs. En primer lugar, identificamos el problema de congestión en el acceso aleatorio de LTE que aparece en los despliegues de SGs a gran escala. Para superar este problema, se propone un nuevo mecanismo de acceso aleatorio que permite soportar de forma eficiente los servicios de automatización de la distribución eléctrica en tiempo real, con un impacto insignificante en el tráfico de fondo. Motivados por los estrictos requisitos de fiabilidad de las diversas operaciones en la SG, desarrollamos un modelo analítico del procedimiento de acceso aleatorio de LTE que nos permite evaluar el rendimiento del tráfico de monitorización de la red eléctrica basado en eventos bajo diversas condiciones de carga y configuraciones de red. Además, ampliamos nuestro análisis para incluir la relación entre el tamaño de celda y la disponibilidad de recursos de acceso aleatorio ortogonales, e identificamos un reto adicional para la conectividad fiable en la SG. Con este fin, diseñamos un mecanismo de planificación celular que tiene en cuenta las interferencias y la carga de la red, y que mejora la fiabilidad en los servicios de automatización de las subestaciones eléctricas. Finalmente, combinamos el problema de la estimación de estado en sistemas de monitorización de redes eléctricas de área amplia con los retos de fiabilidad en la adquisición de la información. Utilizando el modelo analítico desarrollado, cuantificamos el impacto de la baja fiabilidad en las comunicaciones sobre la precisión de la estimación de estado. La segunda parte de la tesis se centra en el problema de scheduling y compartición de recursos en la RAN para el tráfico de SG y el tráfico de tipo humano. Presentamos un nuevo scheduler que proporciona baja latencia para el tráfico de automatización de la distribución eléctrica, mientras que la asignación de recursos se realiza de un modo que mantiene la degradación de los usuarios celulares en un nivel mínimo. Además, investigamos los beneficios del modo de transmisión Device-to-Device (D2D) en el intercambio de mensajes basados en eventos en escenarios de automatización de subestaciones eléctricas. Diseñamos un mecanismo conjunto de asignación de recursos y selección de modo que da como resultado tasas de datos más elevadas con respecto al modo de transmisión convencional a través de la estación base. Finalmente, se propone un esquema de partición de recursos ortogonales entre enlaces celulares y D2

La quinta generación de redes móviles (5G) se encuentra a la vuelta de la esquina. Se espera provea de beneficios extraordinarios a la población y que resuelva la mayoría de los problemas de las redes 4G actuales. El éxito de 5G, cuya primera fase de estandarización ha sido completada, depende de tres pilares: comunicaciones tipo-máquina masivas, banda ancha móvil mejorada y comunicaciones ultra fiables y de baja latencia (mMTC, eMBB y URLLC, respectivamente). En esta tesis nos enfocamos en el primer pilar de 5G, mMTC, pero también proveemos una solución para lograr eMBB en escenarios de distribución masiva de contenidos. Específicamente, las principales contribuciones son en las áreas de: 1) soporte eficiente de mMTC en redes celulares; 2) acceso aleatorio para el reporte de eventos en redes inalámbricas de sensores (WSNs); y 3) cooperación para la distribución masiva de contenidos en redes celulares. En el apartado de mMTC en redes celulares, esta tesis provee un análisis profundo del desempeño del procedimiento de acceso aleatorio, que es la forma mediante la cual los dispositivos móviles acceden a la red. Estos análisis fueron inicialmente llevados a cabo por simulaciones y, posteriormente, por medio de un modelo analítico. Ambos modelos fueron desarrollados específicamente para este propósito e incluyen uno de los esquemas de control de acceso más prometedores: access class barring (ACB). Nuestro modelo es uno de los más precisos que se pueden encontrar en la literatura y el único que incorpora el esquema de ACB. Los resultados obtenidos por medio de este modelo y por simulación son claros: los accesos altamente sincronizados que ocurren en aplicaciones de mMTC pueden causar congestión severa en el canal de acceso. Por otro lado, también son claros en que esta congestión se puede prevenir con una adecuada configuración del ACB. Sin embargo, los parámetros de configuración del ACB deben ser continuamente adaptados a la intensidad de accesos para poder obtener un desempeño óptimo. En la tesis se propone una solución práctica a este problema en la forma de un esquema de configuración automática para el ACB; lo llamamos ACBC. Los resultados muestran que nuestro esquema puede lograr un desempeño muy cercano al óptimo sin importar la intensidad de los accesos. Asimismo, puede ser directamente implementado en redes celulares para soportar el tráfico mMTC, ya que ha sido diseñado teniendo en cuenta los estándares del 3GPP. Además de los análisis descritos anteriormente para redes celulares, se realiza un análisis general para aplicaciones de contadores inteligentes. Es decir, estudiamos un escenario de mMTC desde la perspectiva de las WSNs. Específicamente, desarrollamos un modelo híbrido para el análisis de desempeño y la optimización de protocolos de WSNs de acceso aleatorio y basados en cluster. Los resultados muestran la utilidad de escuchar el medio inalámbrico para minimizar el número de transmisiones y también de modificar las probabilidades de transmisión después de una colisión. En lo que respecta a eMBB, nos enfocamos en un escenario de distribución masiva de contenidos, en el que un mismo contenido es enviado de forma simultánea a un gran número de usuarios móviles. Este escenario es problemático, ya que las estaciones base de la red celular no cuentan con mecanismos eficientes de multicast o broadcast. Por lo tanto, la solución que se adopta comúnmente es la de replicar e contenido para cada uno de los usuarios que lo soliciten; está claro que esto es altamente ineficiente. Para resolver este problema, proponemos el uso de esquemas de network coding y de arquitecturas cooperativas llamadas nubes móviles. En concreto, desarrollamos un protocolo para la distribución masiva de contenidos, junto con un modelo analítico para su optimización. Los resultados demuestran que el modelo propuesto es simple y preciso, y que el protocolo puede reducir el con<br>La cinquena generació de xarxes mòbils (5G) es troba molt a la vora. S'espera que proveïsca de beneficis extraordinaris a la població i que resolga la majoria dels problemes de les xarxes 4G actuals. L'èxit de 5G, per a la qual ja ha sigut completada la primera fase del qual d'estandardització, depén de tres pilars: comunicacions tipus-màquina massives, banda ampla mòbil millorada, i comunicacions ultra fiables i de baixa latència (mMTC, eMBB i URLLC, respectivament, per les seues sigles en anglés). En aquesta tesi ens enfoquem en el primer pilar de 5G, mMTC, però també proveïm una solució per a aconseguir eMBB en escenaris de distribució massiva de continguts. Específicament, les principals contribucions són en les àrees de: 1) suport eficient de mMTC en xarxes cel·lulars; 2) accés aleatori per al report d'esdeveniments en xarxes sense fils de sensors (WSNs); i 3) cooperació per a la distribució massiva de continguts en xarxes cel·lulars. En l'apartat de mMTC en xarxes cel·lulars, aquesta tesi realitza una anàlisi profunda de l'acompliment del procediment d'accés aleatori, que és la forma mitjançant la qual els dispositius mòbils accedeixen a la xarxa. Aquestes anàlisis van ser inicialment dutes per mitjà de simulacions i, posteriorment, per mitjà d'un model analític. Els models van ser desenvolupats específicament per a aquest propòsit i inclouen un dels esquemes de control d'accés més prometedors: el access class barring (ACB). El nostre model és un dels més precisos que es poden trobar i l'únic que incorpora l'esquema d'ACB. Els resultats obtinguts per mitjà d'aquest model i per simulació són clars: els accessos altament sincronitzats que ocorren en aplicacions de mMTC poden causar congestió severa en el canal d'accés. D'altra banda, també són clars en què aquesta congestió es pot previndre amb una adequada configuració de l'ACB. No obstant això, els paràmetres de configuració de l'ACB han de ser contínuament adaptats a la intensitat d'accessos per a poder obtindre unes prestacions òptimes. En la tesi es proposa una solució pràctica a aquest problema en la forma d'un esquema de configuració automàtica per a l'ACB; l'anomenem ACBC. Els resultats mostren que el nostre esquema pot aconseguir un acompliment molt proper a l'òptim sense importar la intensitat dels accessos. Així mateix, pot ser directament implementat en xarxes cel·lulars per a suportar el trànsit mMTC, ja que ha sigut dissenyat tenint en compte els estàndards del 3GPP. A més de les anàlisis descrites anteriorment per a xarxes cel·lulars, es realitza una anàlisi general per a aplicacions de comptadors intel·ligents. És a dir, estudiem un escenari de mMTC des de la perspectiva de les WSNs. Específicament, desenvolupem un model híbrid per a l'anàlisi de prestacions i l'optimització de protocols de WSNs d'accés aleatori i basats en clúster. Els resultats mostren la utilitat d'escoltar el mitjà sense fil per a minimitzar el nombre de transmissions i també de modificar les probabilitats de transmissió després d'una col·lisió. Pel que fa a eMBB, ens enfoquem en un escenari de distribució massiva de continguts, en el qual un mateix contingut és enviat de forma simultània a un gran nombre d'usuaris mòbils. Aquest escenari és problemàtic, ja que les estacions base de la xarxa cel·lular no compten amb mecanismes eficients de multicast o broadcast. Per tant, la solució que s'adopta comunament és la de replicar el contingut per a cadascun dels usuaris que ho sol·liciten; és clar que això és altament ineficient. Per a resoldre aquest problema, proposem l'ús d'esquemes de network coding i d'arquitectures cooperatives anomenades núvols mòbils. En concret, desenvolupem un protocol per a realitzar la distribució massiva de continguts de forma eficient, juntament amb un model analític per a la seua optimització. Els resultats demostren que el model proposat és simple i precís<br>The 5th generation (5G) of mobile networks is just around the corner. It is expected to bring extraordinary benefits to the population and to solve the majority of the problems of current 4th generation (4G) systems. The success of 5G, whose first phase of standardization has concluded, relies in three pillars that correspond to its main use cases: massive machine-type communication (mMTC), enhanced mobile broadband (eMBB), and ultra-reliable low latency communication (URLLC). This thesis mainly focuses on the first pillar of 5G: mMTC, but also provides a solution for the eMBB in massive content delivery scenarios. Specifically, its main contributions are in the areas of: 1) efficient support of mMTC in cellular networks; 2) random access (RA) event-reporting in wireless sensor networks (WSNs); and 3) cooperative massive content delivery in cellular networks. Regarding mMTC in cellular networks, this thesis provides a thorough performance analysis of the RA procedure (RAP), used by the mobile devices to switch from idle to connected mode. These analyses were first conducted by simulation and then by an analytical model; both of these were developed with this specific purpose and include one of the most promising access control schemes: the access class barring (ACB). To the best of our knowledge, this is one of the most accurate analytical models reported in the literature and the only one that incorporates the ACB scheme. Our results clearly show that the highly-synchronized accesses that occur in mMTC applications can lead to severe congestion. On the other hand, it is also clear that congestion can be prevented with an adequate configuration of the ACB scheme. However, the configuration parameters of the ACB scheme must be continuously adapted to the intensity of access attempts if an optimal performance is to be obtained. We developed a practical solution to this problem in the form of a scheme to automatically configure the ACB; we call it access class barring configuration (ACBC) scheme. The results show that our ACBC scheme leads to a near-optimal performance regardless of the intensity of access attempts. Furthermore, it can be directly implemented in 3rd Generation Partnership Project (3GPP) cellular systems to efficiently handle mMTC because it has been designed to comply with the 3GPP standards. In addition to the analyses described above for cellular networks, a general analysis for smart metering applications is performed. That is, we study an mMTC scenario from the perspective of event detection and reporting WSNs. Specifically, we provide a hybrid model for the performance analysis and optimization of cluster-based RA WSN protocols. Results showcase the utility of overhearing to minimize the number of packet transmissions, but also of the adaptation of transmission parameters after a collision occurs. Building on this, we are able to provide some guidelines that can drastically increase the performance of a wide range of RA protocols and systems in event reporting applications. Regarding eMBB, we focus on a massive content delivery scenario in which the exact same content is transmitted to a large number of mobile users simultaneously. Such a scenario may arise, for example, with video streaming services that offer a particularly popular content. This is a problematic scenario because cellular base stations have no efficient multicast or broadcast mechanisms. Hence, the traditional solution is to replicate the content for each requesting user, which is highly inefficient. To solve this problem, we propose the use of network coding (NC) schemes in combination with cooperative architectures named mobile clouds (MCs). Specifically, we develop a protocol for efficient massive content delivery, along with the analytical model for its optimization. Results show the proposed model is simple and accurate, and the protocol can lead to energy savings of up to 37 percent when compared to the traditional approach.<br>Leyva Mayorga, I. (2018). On reliable and energy efficient massive wireless communications: the road to 5G [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/115484<br>TESIS

Graph algorithms are concerned with the algorithmic aspects of solving graph problems. The problems are motivated from and have application to diverse areas of computer science, engineering and other disciplines. Problems arising from these areas of application are good candidates for parallelization since they often have both intense computational needs and stringent response time requirements. Motivated by these concerns, this thesis investigates parallel algorithms for these kinds of graph problems that have at least one of the following properties: the problems involve some type of dynamic updates; the sparsification technique is applicable; or the problems are closely related to communications network issues. The models of parallel computation used in our studies are the Parallel Random Access Machine (PRAM) model and the practical interconnection network models such as meshes and hypercubes. ¶ ...

碩士<br>國立中山大學<br>資訊工程學系研究所<br>103<br>In 1980s, Yao proposed a secure computation which can allow two parties, one of which has a function f(⋅) and the other one has data x, to compute f(x) without revealing anything about f and x. Garbled circuits got numerous applications. But every time we want to garble a program, we need to convert it into a circuit first. In 2013, Lu and Ostrovsky proposed the garbled random-access machines, which can garble a RAM program directly. They constructed garbled RAM based on the pseudo-random functions and the Beaver-Micali-Rogaway paradigm in the semi-honest model. In Lu-Ostrovsky construction, the garbled data is reusable, but the garbled programs are not reusable. Therefore, we propose a reusable garbled RAM with both the reusable data and programs. Our first construction is designed in the semi-honest model for less computational cost. The second construction is based on the approach of Lindell and Pinkas, which used the cut-and-choose technique to resist the malicious adversary.

碩士<br>國立中央大學<br>資訊工程學系<br>106<br>With the popularity of smart mobile devices, surfing the Internet anytime, anywhere has become a kind of necessity for modern life. How to combine the mobile communication technologies with other technologies to support more services in mobile networks is one of major issues. In current LTE-A network, the base station (eNB) only schedules the channel resource for the devices (UE) which has established the radio resource control (RRC) connections. For the UE staying in IDLE mode, it has to perform the random access procedure (RAP) in order to establish RRC connection with the eNB. The motivation of this thesis is based on the observations from the behavior and performance of RAP in machine type communications. When the number of UEs performing RAP excesses a certain threshold, collisions may occur and result in remarkable resource wastage and delay. In other words, a UE randomly selects one preamble and transmit it on the specified channel resource. The preamble is a specified sequence of a certain length and the system provides a number of orthogonal preambles for RAP. The eNB searches the preamble(s) and allocate uplink resource to UE(s) for each detected preamble. The corresponding UE then transmits RRC connection setup request message to the eNB on the uplink resource. If more than one UE sends the same preamble to eNB, their following messages will collide with each other and the eNB cannot decode any one of them. Then, the eNB utilizes the Hybrid Automatic Repeat Request (HARQ) feedback to notify UE(s) to retransmit message again. The collisions cannot be resolved and retransmissions will be lasted to the maximal HARQ retries. After then, all involved UEs restart RAP again. Obviously, the collision probability is linearly proportional to the number of UEs and more collisions will prolong the access delay and waste power and bandwidth. Due to 5G network has included the massive MTC (mMTC) usage case, how to efficiently reduce the collision probability in mMTC scenario could be an important and patentable technology. This project aims to deal with the contemporary mobile network system and try to integrate the RAP with the random backoff solution adopted in WiFi networks in order to minimize the interference among UEs. We also emphasize that the proposed scheme will not only reduce collision probability in RAP but also consider the full compatibility with current specifications.

碩士<br>國立臺灣科技大學<br>電子工程系<br>105<br>Machine-type communication (MTC) can generate numerous connection requests and bring explosive load within small time interval. A massive amount of simultaneous random access attempts results in a high collision probability and intolerable access delay because more devices contend in shared random access channels (RACH) with limited capacity. Thus, this thesis addressed a novel mechanism, denoted as two-phase random access (TPRA) procedure, for MTC in mobile networks to relieve the load of RACH. The proposed TPRA reduces probability of collision among the MTC devices when accessing radio resources by separation of the massive number of devices into small groups. The proposed concept allows a base station to adjust the number of additional access channels according to their current load. Furthermore, we propose an analytical model to evaluate the performance of the proposed TPRA by estimating the access success probability and average access delay. The simulations results validate the accuracy of the performance metrics derived analytically.

碩士<br>國立交通大學<br>電信工程研究所<br>101<br>Machine-to-machine (M2M) communication is a type of communication. It makes the automatic information exchange between a machine and other machine or a machine and a machine type communication (MTC) server by integrating various wireless communication techniques to satisfy requirements of many applications. Because M2M communication can provide various automatic applications and open a new market, M2M communication is received public attention. But M2M communication needs to deploy a large number of machines everywhere, and bring the current 4G wireless communication system many challenges to be solved. In this thesis, we propose an energy efficient random access control (E2RAC) in which the fine access quality is provided through estimating the number of machines. As we separate access resources for different types of communication, different orders of the service quality can be provided. Simulation results show that the E2RAC scheme provide the better quality of service than the conventional scheme.

碩士<br>國立臺灣科技大學<br>電子工程系<br>105<br>Distributed queueing (DQ)-based random access (RA) is an access protocol which can efficiently deal with the massive collision to support machine type communication in LTE cellular network. In DQ-based RA, there is a trade-off between the reduced collision and the increased access delay. To analyze the worst delay condition, it is necessary for the cellular network to guarantee the access delay bound. Thus, the maximum access delay is one important performance index in DQ-based RA. This thesis develops an analytical model to estimate the maximum access delay for DQ-based RA in a finite-users multi-channel slotted ALOHA system. The proposed model can be used to evaluate the performance of group paging using DQ-based RA for machine-type communication (MTC) in LTE. Numerical results show that the proposed models can accurately analyze the simulation results.

博士<br>國立臺灣科技大學<br>電子工程系<br>106<br>One scenario in internet of things (IoT) is called massive machine-type communication (mMTC). mMTC is commonly characterized with massive number of devices with small and infrequent data transmission. mMTC can be served with cellular technology such as LTE-Advanced (LTE-A) and Narrowband IoT (NB-IoT). In both of them, each device wanting to send their data needs to complete random access (RA) procedure. The RA procedure in LTE-A and NB-IoT is based on multi-channel slotted ALOHA system, which has very low throughput under high load. This is serious bottleneck for mMTC. In the first part of this thesis, we consider an LTE-A network serving mMTC services with different priorities. With the said bottleneck, low access success probability and high access delay is likely to be experienced by all access classes (ACs), regardless of their priority. To alleviate this problem, we propose a generalized preamble allocation scheme to manage the priority of the ACs and fulfill their QoS requirement. A model is presented to estimate the performance metrics. We demonstrated that the proposed scheme is able to manage the prioritization and fulfill the requirement of the ACs under limited number of available. In the second part of this thesis, we consider an NB-IoT with up to 3 coverage enhancement (CE) levels. It introduces new level of complexity to optimally configure their RA parameters to yield the optimal performance. For this problem, we propose a method to configure up to 10 parameters in NB-IoT’s RA procedure with up to 3 CE levels to achieve the highest access success probability under certain access delay constrain. The optimized parameters are number of CE levels, maximum number of preamble transmission of each UE, maximum number of preamble transmission in each CE level, backoff window in each CE level, and number of preamble in each CE level. A model is firstly presented to estimate the performance metrics, and is utilized to derive the optimization strategies. The effectiveness of this optimization is verified via computer simulation and exhaustive search, and is proved to work well under various situations. In the third part of this thesis, we discussed the requirement of a very high detection probability for each transmitted preamble in NB-IoT, which is achieved by considerably high number of repetitions. We doubt that such requirement is required. We investigated the optimal number of repetitions and (re)transmissions to achieve certain requirement of access success probability. A model is firstly presented estimate the performance metrics, and is utilized to identify the preferred situations of ‘repetition’ and ‘retransmission’ technique. We demonstrate that for mMTC, fewer repetitions and more retransmission can achieve higher access success probability.

碩士<br>國立臺北大學<br>通訊工程研究所<br>107<br>As 5G technology developing further, the requirements of different applications become clear. There are three types of use cases. Enhanced mobile broadband(eMBB),ultra-reliable and low latency communications(URLLC) and massive machine-type communications(mMTC). First is eMBB, which is used for wider bandwidth applications like mobile broadband service. And URLLC applications require a more reliable and low latency connection. Like factory automation and remote surgery. The last one, mMTC, is the focus of this thesis. mMTC is used in a scenario that has a large amount of devices and few data transmission. In this type of application, it is waste to establish a connection before every transmission. Sometimes resource that used for connection are more than for transmission. So, uncoordinated multiple access(UMA) is applied. Traditional UMA like traditional slotted ALOHA can transmit data without establishing a connection. But it can only achieve 37% of efficiency the most. In G. Liva, “Graph-based analysis and optimization of contention resolution diversity slotted ALOHA”, Liva proposed an IRSA technique base on slotted ALOHA, which using probability distribution that is well designed to decide number of retransmission times. Also, at receiver, applying successive interference cancellation(SIC) to deal with packets collision issue. IRSA technique was proofed that can achieve 100% efficiency if choosing a well-designed probability distribution. In this thesis, we try to apply IRSA on mMTC scenarios, which usually contain many types of heterogeneous users in a transmission time. And we also introduce the concept of non-orthogonal multiple access(NOMA) into IRSA to realize intra-slot SIC. This could greatly improve the efficiency of the system. To analyze efficiency of IRSA with NOMA, we proposed a new type of Tanner graph to represent for IRSA with NOMA. Also, a novel density evolution that is multi-dimensional instead. Then we can use linear programming to optimize the probability distribution. Final, we did a series of simulations to verify our analysis. Results confirm that IRSA with NOMA can easily achieve 100% efficiency in mMTC that contain heterogeneous users.

碩士<br>長庚大學<br>資訊工程學系<br>103<br>Machine-type communication (MTC) has raised significant interests in recent years. However, due to the massive number of machine type communication devices that are anticipated to communicate using cellular networks, there is a major problem on efficient accommodation of the heavy Random Access (RA) loads from the MTC devices. Use of small cells has been specified to provide network denazification by 3GPP. By searching several references [3-9] about controlling devices under an eNB efficiently, we acquire that group paging is an appropriate solution for us to solve the problem. Group paging is a pull-based random-access (RA) mechanism for machine-type communications (MTC) in the long-term evolution advanced (LTE-A) networks. Due to the RA process, MTC devices of a group may delay until the time point of the next polling of another groups and lead to a serious access delay problem. To solve this problem, in this thesis, we investigate a dynamic backoff indicator (BI) assignment (DBA) algorithm that lets the delayed MTC devices speed up to finish their RA within an expected period of time. The proposed method also realizes the crucial concept of cyber-physical systems (CPS). Simulation results and analyses validate the effects of CPS on reducing collision probability in large-scale MTC.

碩士<br>國立臺灣科技大學<br>電機工程系<br>106<br>With the rapid development of wireless communication technology, the concept of IoT has been emerge in people's lives and makes us more convenient and intelligent application services. In the Internet of Things, machine-type communication (MTC) technology has become one of the key technological development. It has several features such as low power consumption and cost, low data volume, low or no mobility, and high coverage. Automated decision-making and transmission between machine and machine eliminates the need for human-controlled communication technology. So many features make MTC receive much attention in IoT. The 3rd Generation Partnership Project (3GPP) aims to meet the needs of the Internet of Things and proposes a new standard for Long Term Evolution-Machine type communication (LTE-M) for machine-to-machine communication applications. In the environment of the Internet of Things, within the coverage of a base station, it can be expected that in addition to user equipment (UE) and a large number of MTC devices will use random access to joining base station. When the random access procedure makes a request to the base station, due to limited resources of the physical random access channel, the addition of a large number of devices will cause channel congestion, increase the probability of random access collision, and increase the response time of the base station. This thesis mainly focuses on the congestion problem of the random access channel of the physical entity, proposes an improved method without modifying the contention-based random access procedure, dynamically adjusts the clustering and assigns different PRACH Configuration Index parameters through the detected collision factors. After a large number of MTC devices are dispersed in three groups, random access requests are sent in different RA-slots, thereby reducing the problem of congestion of random access channels in the physical entities. The simulation results show that in the urban area, when a large number of MTC devices send access requests in a short period of time, the proposed dynamic adjustment and grouping mechanism can effectively disperse the devices different groups and in different RA-slot, which improves the congestion problem of the physical random access channel.

碩士<br>國立宜蘭大學<br>電子工程學系碩士班<br>106<br>The ever-increasing data rate with limited resources has led to the introduction of new schemes to improve the user experience. Traditionally a low number of connections with high data requirements are achieved over a network dealing with the limited amount of connections established between the device and the Base Station (BS) before the device can transmit its data packet. But emerging technologies such as Machine-to-Machine (M2M) communication features present a significant challenge to cellular networks, whose radio access requirement is high. LTE-A involves a high amount of signaling overhead. Therefore, in 3GPP it was proposed an approach to optimize the connection establishment by reducing signaling overhead using filtering system and also to arrange the connection requests from the devices to base station and to avoid the collision at the base station. We present a random-access method inspired on cuckoo filters that are found to better suited for Massive Machine-Type Communications (mMTC) than other filter schemes. Each accessing device sends a signature during the contention process. A signature is constructed using the cuckoo filtering insert hash method and contains information about the device identity and the connection establishment requirements. A Cuckoo filter-based signatures also allows devices seeking permission to access the base station dramatically with high performance by allowing faster signature generation. We conclude that the method proposed has a better average goodput than other methods and can be applied to the massive machine type devices over the 5G technology. The connection established between the base station and the user is made feasible without loss of data and it also minimizes the congestion at the base station during the RRC (Radio Resource Control) stage.

博士<br>國立臺灣科技大學<br>電子工程系<br>101<br>Multichannel slotted ALOHA is a widely used protocol for random-access channels (RACH) in cellular networks. Existing studies of multichannel slotted ALOHA were developed for investigating the performance of a light-load system with steady-state analysis based on the assumptions of constant-rate Poisson arrivals for voice or low data rate service . Machine-type communication (MTC) services are expected to generate huge and bursty access attempts in a short period of time and thus, congest the RACH which do not reserve enough resources. The short-term congestion may block the access attempts from existing human-to-human communication services. New analytical models are urgently needed to evaluate the transient-performance of the overloaded system and since the assumptions used in existing studies are not valid anymore during the congestion period. LTE cellular networks is a candidate for providing the MTC service. This thesis aims to develop analytical models to analyze the transient-performance of an overloaded multi-channel slotted ALOHA system. In the first part of this thesis, we considered fixed number of machine devices contend for fixed number channels in a multichannel slotted ALOHA system. We proposed approximation formulas to estimate the number of success and collided channels for one-shot random access. We further developed a recursive contending-users estimation (RCE) method and demonstrated that RCE can be used to estimate the number of contending and success devices, and to investigate the transient-performance of a simplified group paging scheme, such as collision probability. In the second part of this thesis, we extended the RCE to analyze the transient-performance of a generalized group scheme by considering the implementation constraints of LTE random access procedure such as the backoff policy; limitation of the access grant channel; the power-ramping effect; the transmission delay resulted from HARQ mechanism. In the third part of this thesis, we extend the analytical model to investigate the transient-performance of the RACHs with fix number of devices bursty arrivals with any kind of probability density function in a specific time interval. The transient-performance metrics in the second and third part of this thesis such as the average collision probability, access success probability, average access delay, and CDF of the number of preamble transmissions and average access delay for the successfully accessed devices were successfully derived. In the future, we can modify the RCE method to investigate and optimize the performance of the RACH under different kind of overload control scheme.

Research Doctorate - Doctor of Philosophy (PhD)<br>A robust communication infrastructure is the touchstone of a Smart Grid that differentiates it from the conventional electrical grid by transforming it into an intelligent and adaptive energy delivery network. To cope with the rising penetration of renewable energy sources and expected widespread adoption of electric vehicles, the future Smart Grid needs to implement efficient monitoring and control technologies to improve its operational efficiency. However, legacy communication infrastructures in the existing grid are quite insufficient, if not incapable of meeting the diverse communication requirements of the Smart Grid. Being one of the two available 4G technologies in the world, the IEEE 802.16- based WiMAX (Worldwide Interoperability for Microwave Access) networks can significantly extend the reach of a Smart Grid by allowing fast and reliable communications over a wide coverage area. However, the unique characteristics of machine-to-machine (M2M) communications in the Smart Grid pose a number of interesting challenges to the conventional telecommunications networks, including WiMAX. Hence, considerable uncertainties exist about the applicability of WiMAX in a Smart Grid environment. The aim of this thesis is to offer an in-depth study of M2M communications over a WiMAX network in the Smart Grid. To fulfill this aim, it first conducts a detailed, technology agnostic review on the application characteristics and traffic requirements of several major Smart Grid applications and highlights their key communication challenges. Based on this review, it develops a range of traffic models for some key Smart Grid traffic sources, namely, smart meters, synchrophasors, and protective relays. Through a series of simulation studies, it then highlights a number of quality of service (QoS) and capacity issues that these applications may face within a conventional WiMAX network. A key observation from these studies is that the random access plane is the key bottleneck for supporting many of these M2M applications over a conventional WiMAX network. To further analyse the performance of the random access plane, this thesis develops a comprehensive analytical model that incorporates all the key features of the code division multiple access (CDMA) based random access mechanism, such as multi-user multi-code transmission, parallel code detection, and back-off and retransmissions. Through this model, it formulates a number of solutions, such as an enhanced random access scheme to detect a large number of random access codes, a differentiated random access strategy to provide QoS-aware access service to various M2M devices, and an adaptive radio resource management scheme to ensure an efficient utilisation of the random access resources. Moreover, it proposes and investigates a heterogeneous network (HetNet) architecture to reap maximum benefits from aWiMAX network by improving its coverage and allowing flexible data aggregation. Finally, it presents a number of application-specific optimisations to reduce radio resource utilisation and/or improve the performance of a WiMAX-based Smart Grid communications network. Many of the WiMAX specific analyses, results, and solutions in this thesis can be applied to other M2M applications beyond the Smart Grid. In addition, most of the traffic models developed and application-specific optimisations performed are technology agnostic; therefore, they are equally applicable to other wireless technologies, such as the 3GPP (3rd Generation Partnership Project) based LTE (Long Term Evolution).

碩士<br>國立臺灣大學<br>電子工程學研究所<br>99<br>In this thesis, the first part is the model and physical mechanism of Resistive random access memory (RRAM). RRAM is one of the many types nonvolatile memory, which is the most promising candidate to replace traditional flash memory. External voltage is added on RRAM to switch the device between low resistance state (LRS) and high resistance state (HRS), and recorded to Logic 0 or 1. RRAM has advantages of low power consumption and low operation voltage (write voltage &amp;lt;3V, read voltage ~0.1V), a simple structure (a transition metal oxide layer between top and bottom layer electrode), multilevel operation (can dramatically increase memory density), very fast read and write speed (&amp;lt;10ns), high durability (>10yrs). Our device is prepared by Industrial Technology Research Institute (ITRI), some measurements are done in ITRI, and others and done in NTU. We have did different experiment test on RRAM, such as different current compliance, maximum negative voltage Vstop, and analysis of series operation of two RRAM cell. We discover for series SET test, there will be so-called floating terminal effect; we will propose a model for thi phenomenon, and a way to prevent this. The second part is the physical analysis on Thin-Film Transistor (TFT). The device is prepared by AU Optronics Corp.(AUO), and measured at National Nano Device Laboratories (NDL). We will first start from the analysis of physics of McWhorter Model compare with other two models in the literature. Next, we will further discuss and explain the physical mechanism from the measurement results. The third part is the low frequency analysis of α-IGZO, where the device is prepared by Chimei Innolux Corporation (CMO), and measured at National Nano Device Laboratories (NDL). Since there are little research on this topic, we hope with the analysis of low frequency noise, we can learn more about the physical mechanism of α-IGZO.

This master thesis focuses on the Random Forests algorithm analysis and implementation. The Random Forests is a machine learning algorithm targeting data classification. The goal of the thesis is an implementation of the Random Forests algorithm using techniques and technologies of parallel programming for CPU and GPGPU and also a reference serial implementation for CPU. A comparison and evaluation of functional and performance attributes of these implementations will be performed. For the comparison of these implementations various data sets will be used but an emphasis will be given to real world data obtained from astronomical observations of stellar spectra. Usefulness of these implementations for stellar spectra classification from the functional and performance view will be performed. Powered by TCPDF (www.tcpdf.org)