UMD Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/3
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a given thesis/dissertation in DRUM.
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
9 results
Search Results
Item Dynamic Traffic Management of Highway Networks(2022) Alimardani, Fatemeh; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Efficient operation of traffic networks via management strategies can guarantee overall societal benefits for both the humans and the environment. As the number of vehicles and the need for transportation grows, dynamic traffic management aims to increase the safety and efficiency of the traffic networks without the need to change the infrastructure of the existing roads. Since the highway networks are considered permanent investments that are expensive to build and maintain, the main scope of this dissertation is to propose traffic flow models and methods to improve the efficiency of the current highway systems without the need to change their infrastructure. When all vehicles in a network are \textit{Human-Driven Vehicles} (HDVs), and changing the infrastructure is either so expensive or impossible, then one reasonable approach to improve the efficiency of traffic networks is through the control of traffic signal lights specially because the behavior of the human drivers cannot be directly controlled. A literature review of highway traffic control demonstrate that \textit{Ramp Metering} (RM) is one of the most commonly used approaches as it improves the network performance in regards to travel time, travel distance, throughput, etc and cost-wise, it is a very economical approach. As such, in this research, the ultimate goal focus is to extend the current literature on traffic managements of highway networks by offering new models and algorithms to improve this field. To reach this goal, the first step is to focus on improving and extending the current traffic flow models. There are two categories of traffic flow models in the literature: First-order models, and Second-order models. Many different extensions of the famous first-order model called the Cell-Transmission Model (CTM) have been proposed throughout the past decades, each one proposed based on different criteria and the specific needs of different applications. In the first part of this dissertation, a performance assessment of the most important extensions of CTM will be performed. Then, based on this evaluation, an extended version of the CTM, called the Piece-Wise Affine Approximation-CTM (\textit{PWA-CTM}), will be offered which will be proven to have better performance regarding the evolution of traffic flow and computation time comparing to the previous versions of this model. In the next step, the focus will be shifted to second-order models as they have better capabilities of modeling the behavior of traffic flow comparing to the first-order models. However, any optimization scheme for highway traffic control based on these models is highly nonlinear and computationally intensive. As such, in this part of the research, a linearization of the famous second-order model called the \textit{METANET} will be offered which is based on PWA approximations and also synthetic data generation techniques. With extensive simulations, it will be shown that this linearized approximation can greatly impact the computational complexity of any optimization-based traffic control framework based on this second-order traffic flow model. Moreover, to have significant traffic management improvements, not only the underlying traffic models, but also the control strategies should be enhanced. The availability of increasing computational power and sensing and communication capabilities, as well as advances in the field of machine learning, has developed \textit{learning-based} control approaches which can address constraint satisfaction and closed-loop performance optimization. In this chapter, \textit{Reinforcement Learning} (RL) algorithms will be investigated to solve the optimal control problem of RM. In the case of RM, RL-based techniques offer a potentially appealing alternative method to solve the problem at hand, since they are data-based and make no assumptions on the underlying model parameters. Towards this direction, it is convenient to study the road model as a multi-agent system of non-homogeneous networked agents. In the following, a novel formulation of the RM problem as an optimal control problem based on a first-order multi-agent dynamical system will be offered. Then, applying policy gradient RL algorithms, a probabilistic policy will be found that solves the ramp-metering problem. The performance of the optimal policy learnt will be investigated under different scenarios to evaluate its efficiency.Item ENHANCING RESILIENCE OF COMPLEX NETWORKS: WASHINGTON D.C. URBAN RAIL TRANSIT AS A CASE STUDY(2020) Saadat, Yalda; Ayyub, Bilal BA; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)According to the United Nation’s Department of Economic and Social Affairs Population Division, 66% of the world’s population will reside in urban areas by 2050; a boost from 30 % in 1950. Urbanization has indeed triumphed and its speed has brought innovation and economic growth. Its synergies within infrastructure systems are undeniable and have increased the demand for such systems. However, urbanization is one reason infrastructure systems are knocked out of equilibrium and show complex dynamical behavior. Most infrastructure systems have been designed without planning for this magnitude of potential demographic changes; thus redesigns are long overdue. Also, climate change looms. Resource scarcity and host of other factors leave their impacts; all pose some incidence of perturbation in the state of the infrastructure system. These perturbations can affect the system’s resilience, which is a defining property of each system for remaining functional in the midst of disruption from an adverse event. Therefore, it is essential to develop appropriate metrics and methods to enhance the resilience of infrastructures at the network level. Such enhancements are critical for sustainable infrastructure development that is capable of performing satisfactorily through intentional and/or stochastic disruptions. A resilience evaluation of a network typically entails assessing vulnerability and robustness as well as identifying strategies to increasing network efficiency and performance and offering recovery strategies ideally taken in a cost-effective manner. This dissertation uses complex network theory (CNT) as the theoretic basis to enhance the resilience of large-scale infrastructure networks, such as urban rail transit systems. Urban rail transit infrastructures are heterogeneous, complex systems consisting of a large number of interacting nodes and links, which can imitate a network paradigm. Any adverse event leading to a disruption in the interaction and connectivity of network components would dramatically affect the safety and wellbeing of commuters, as well as the direct and indirect costs associated with performance loss. Therefore, enhancing their resilience is necessary. Using the Washington D.C. Urban rail transit as a case study, this dissertation develops a methodology to analyze network topology, compute its efficiency, vulnerability, and robustness in addition to provide a unified metric for assessing the network resilience. The steps of methodology are applied to two models of weighted and unweighted networks. For the weighted model two novel algorithms are proposed to capture the general pattern of ridership in the network, and to reflect the weights on assessing network efficiency, respectively. This dissertation then proposes an effective strategy to increase the network resilience prior to a disruptive event, e.g., a natural disaster, by adding several loop lines in the network for topological enhancement. As such, adding a loop line can create redundancy to the vulnerable components and improve network resilience. Expanding on this, the dissertation offers comparative recovery strategies and cost model in the case of disruption. An effective recovery strategy must demonstrate rapid optimal restoration of a disrupted system performance while minimizing recovery costs. In summary, the systematic methodology described above, assesses and enhances the network resilience. The initial results rank the most vulnerable and robust components of the network. The algorithms developed throughout the study advance the weighted network analysis state of art. The topological enhancement strategy offered basis to justify capital improvement. Post failure recovery analysis and the cost model serves to inform decision makers in identifying best recover strategies with special attention not only to restoring performance of a system but also on reducing associated failure and recovery costs. The use of the methodology proposed in this dissertation may lead to significant societal benefits by reducing the risk of catastrophic failures, providing references for mitigation of disruption due to adverse events, and offering resilience- based strategies, and related pursuits.Item Solving, Generating, and Modeling Arc Routing Problems(2017) Lum, Oliver; Golden, Bruce; Wasil, Edward; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Arc routing problems are an important class of network optimization problems. In this dissertation, we develop an open source library with solvers that can be applied to several uncapacitated arc routing problems. The library has a flexible architecture and the ability to visualize real-world street networks. We also develop a software tool that allows users to generate arc routing instances directly from an open source map database. Our tool has a visualization capability that can produce images of routes overlaid on a specific instance. We model and solve two variants of the standard arc routing problem: (1) the windy rural postman problem with zigzag time windows and (2) the min-max K windy rural postman problem. In the first variant, we allow servicing of both sides of some streets in a network, that is, a vehicle can service a street by zigzagging. We combine insertion and local search techniques to produce high-quality solutions to a set of test instances. In the second variant, we design a cluster-first, route-second heuristic that compares favorably to an existing heuristic and produces routes that are intuitively appealing. Finally, we show how to partition a street network into routes that are compact, balanced, and visually appealing.Item PERFORMANCE EVALUATION OF DISRUPTION TOLERANT NETWORKS WITH IMMUNITY MECHANISM AND CODING TECHNIQUE(2015) Lee, Jin Na; La, Richard J; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)We examine the performance of a Disruption Tolerant Networks (DTNs) with an epidemic routing (ER) scheme with the coding technique and/or immunity mechanism under the various network environments. We are interested in the scenarios of opportunistic dissemination of large files. First, we study how the different implementations of the ER scheme perform in diverse network settings. We compare the performance of ER with its summary vector implemented as both a list and as a Bloom filter. Second, we examine how network coding affects the performance of the ER scheme. To this end, we investigate the performance of encoding-based routing (EBR), a variant of the ER scheme which uses random linear coding at source nodes. EBR is expected to mitigate what is commonly known as the coupon collector’s problem, which arises when a large file is chopped into small fragments and then the fragments are disseminated throughout the network. We compare this to the case where intermediate non-source nodes are allowed to create new linear combinations from the ones it already holds. Lastly, we evaluate the benefits of two different types of immunity mechanisms – one based on file ID and the other based on bundle ID – with not only the ER scheme but also two different EBR schemes in various network scenarios and settings. We also investigate the performance gain from compressing the immunity list. By presenting and analyzing extensive simulation results, we provide information that could provide a guideline for employing each of the aforementioned techniques in routing schemes of interest in various network settings.Item Applications of parametric and semi-parametric models for longitudinal data analysis(2014) Talukder, Hisham; Corrada Bravo, Héctor; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A wide range of scientific applications involve analyses of longitudinal data. Whether it is time or location, careful considerations need to be made when applying different statistical tools. One such challenge is to correctly estimate variance components in observed data. In this dissertation, I apply statistical tools to solve problems involving longitudinal data in the field of Biology, Healthcare and Networks. In the second chapter, I apply SSANOVA models to find regions in the genome that have a specific biological trait. We introduce a direct approach of estimating genomic longitudinal data of two different biological groups. Using SSANOVA we then produce a novel method to estimate the difference between the two groups and find regions (location or time) where this difference is biologically significant. In the third chapter, we analyze longitudinal network data using an overdispersed Poisson model. We build a network of musical writers yearly for a 42 year period. Using statistical models, we predict network level topology changes and find covariates that explain these changes. Network level characteristics used for this chapter include average node degree, clustering coefficient and network density. We also build a visualization tool using R-Shiny. The fourth chapter uses data partitioning to study the difference between insured patients and uninsured patients in health outcomes. There is a disparity in health outcomes depending on an individual's type of insurance. The level of risk for an injury is the longitudinal aspect of this dataset. We partition the data into four pre-defined risk categories and evaluate the disparity between insured and uninsured patients using logistic regression models.Item Implementation, Evaluation, and Applications of Mobile Mesh Networks for Platforms in Motion(2009) Napora, Jared Stanislaus; Davis, Christopher C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This thesis explores the selection, implementation, and evaluation of two mobile mesh networks, each involving a different distributed computing problem. In the forthcoming discussion, it will become apparent how system constraints affect the optimal choice of mesh networking design and implementation in these cases. The first problem explores the design and implementation of a distributed computing mesh network that will allow a collection of autonomous land vehicles to gather, process, and exchange information in an unknown environment. This network was established by adapting standard commercial 802.11 routers and by providing a software framework that handles all communication between wireless nodes. The second problem involves the design of a network for tracking and monitoring personnel. This network was implemented utilizing ZigBee modules due to power and custom implementation constraints. Both networks were tested with respect to their specific design constraints and they lay the foundation for additional application development and research.Item Throughput Evaluation and Optimization in Wireless Networks(2007-12-10) Rentz, Nicolas; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)While wireless communication is progressively replacing wired technology, methods for the implementation of Wireless Ad-Hoc Networks are currently under development. As these methods do not require centralized coordination, they are particularly adapted to environments such as disaster recovery and military communication and are, therefore, of great interest. Despite the potential advantages, no reliable methodologies for the design of Wireless Ad-Hoc Networks have been proposed. This condition is largely due to the complexity of analysis of a wireless channel in comparison to that of a wired channel. In this thesis, we discuss the implementation of a tool for wireless network design. Taking a set of nodes and the corresponding characteristics, this tool computes the routes between each source-destination pair. The tool then computes the throughput for each connection and, finally, proposes a method for the optimization of throughput based on probabilistic routing via sensitivity analysis.Item Network flow optimization and distributed control algorithms(2006-11-21) Chen, Huigang; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This thesis concerns the problem of designing distributed algorithms for achieving efficient and fair bandwidth allocations in a resource constrained network. This problem is fundamental to the design of transmission protocols for communication networks, since the fluid models of popular protocols such as TCP and Proportional Fair Controller can be viewed as distributed algorithms which solve the network flow optimization problems corresponding to some fairness criteria. Because of the convexity of the optimization problem as well as its decoupling structure, there exist classical dual algorithm and primal/dual algorithm which are both distributed. However, the main difficulty is the possible instability of the dynamics of these algorithms caused by transmission delays. We use customized Lyapunov-Krasovskii functionals to obtain the stability conditions for these algorithms in networks with heterogeneous time-varying delays. There are two main features of our results. The first is that these stability conditions can be enforced by a small amount of information exchange among relevant users and links. The second is that these stability conditions only depend on the upper bound of delays, not on the rate of delay variations. We further our discussion on scalable algorithms with minimum information to maintain stability. We present a design methodology for such algorithms and prove the global stability of our scalable controllers by the use of Zames-Falb multipliers. Next we extend this method to design the first scalable and globally stable algorithm for the joint multipath routing and flow optimization problem. We achieve this by adding additional delays to different paths for all users. Lastly we discuss the joint single path routing and flow optimization problem, which is a NP hard problem. We show bounded price of anarchy for combined flow and routing game for simple networks and show for many-user networks, simple Nash algorithm leads to approximate optimum of the problem.Item On finding paths and flows in multicriteria, stochastic and time-varying networks(2004-11-24) Opasanon, Sathaporn -; Miller-Hooks, Elise; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation addresses two classes of network flow problems in networks with multiple, stochastic and time-varying attributes. The first problem class is concerned with providing routing instructions with the ability to make updated decisions as information about travel conditions is revealed for individual travelers in a transportation network. Three exact algorithms are presented for identifying all or a subset of the adaptive Pareto-optimal solutions with respect to the expected value of each criterion from each node to a desired destination for each departure time in the period of interest. The second problem class is concerned with problems of determining the optimal set of a priori path flows for evacuation in capacitated networks are addressed, where the time-dependent and stochastic nature of arc attributes and capacities inherent in these problems is explicitly considered. The concept of Safest Escape is formulated for developing egress instructions. An exact algorithm is proposed to determine the pattern of flow that maximizes the minimum path probability of successful arrival of supply at the sink. While the Safest Escape problem considers stochastic, time-varying capacities, arc travel times, while time-varying, are deterministic quantities. Explicit consideration of stochastic and time-varying travel times makes the SEscape problem and other related problems significantly more difficult. A meta-heuristic based on the principles of genetic algorithms is developed for determining optimal path flows with respect to several problems in dynamic networks, where arc traversal times and capacities are random variables with probability mass functions that vary with time. The proposed genetic algorithm is extended for use in more difficult, stochastic, time-varying and multicriteria, capacitated networks, for which no exact, efficient algorithms exist. Several objectives may be simultaneously considered in determining the optimal flow pattern: minimize total time, maximize expected flow and maximize the minimum path probability of successful arrival at the sink (the objective of the SEscape problem). Numerical experiments are conducted to assess the performance of all proposed approaches.