Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
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 give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
6 results
Search Results
Item Optimization of Signal Routing in Disruption-Tolerant Networks(2021) Singam, Caitlyn; Ephremides, Anthony; Systems Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Communication networks are prone to disruption due to inherent uncertainties such as environmental conditions, system outages, and other factors. However, current state-of-the-art communication protocols are not yet optimized for communication in highly disruption-prone environments, such as deep space, where the risk of such uncertainties is not negligible. This work involves the development of a novel protocol for disruption-tolerant communication across space-based networks that avoids idealized assumptions and is consistent with system limitations. The proposed solution is grounded in an approach to information as a time-based commodity, and on reframing the problem of efficient signal routing as a problem of value optimization. The efficacy of the novel protocol was evaluated via a custom Monte Carlo simulation against other state-of-the-art protocols in terms of maintaining both data integrity and transmission speed, and was found to provide a consistent advantage across both metrics of interest.Item MULTI-VEHICLE ROUTE PLANNING FOR CENTRALIZED AND DECENTRALIZED SYSTEMS(2019) Patel, Ruchir; Herrmann, Jeffrey W; Azarm, Shapour; Mechanical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Multi-vehicle route planning is the problem of determining routes for a set of vehicles to visit a set of locations of interest. In this thesis, we describe a study of a classical multi-vehicle route planning problem which compared existing solutions methods on min-sum (minimizing total distance traveled) and min-max (minimizing maximum distance traveled) cost objectives. We then extended the work in this study by adapting approaches tested to generate robust solutions to a failure-robust multi vehicle route planning problem in which a potential vehicle failure may require modifying the solution, which could increase costs. Additionally, we considered a decentralized extension to the multi-vehicle route planning problem, also known as the decentralized task allocation problem. The results of a computational study show that our novel genetic algorithm generated better solutions than existing approaches on larger instances with high communication quality.Item HYBRID ROUTING MODELS UTILIZING TRUCKS OR SHIPS TO LAUNCH DRONES(2018) Poikonen, Stefan Allan; Golden, Bruce L; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Technological advances for unmanned aerial vehicles, commonly referred to as drones, have opened the door to a number of new and interesting applications in areas including military, healthcare, communications, cinematography, emergency response, and logistics. However, limitations due to battery capacity, maximum take-off weight, finite range of wireless communications, and legal regulations have restricted the effective operational range of drones in many practical applications. Several hybrid operational models involving one or more drones launching from a larger vehicle, which may be a ship, truck, or airplane, have emerged to help mitigate these range limitations. In particular, the drones utilize the larger vehicle as both a mobile depot and a recharging or refueling platform. In this dissertation, we describe routing models that leverage the tandem of one or more drones with a larger vehicle. In these models, there is generally a set of targets that should be visited in an efficient (usually time-minimizing) manner. By using multiple vehicles, these targets may be visited in parallel thereby reducing the total time to visit all targets. The vehicle routing problem with drones (VRPD) and traveling salesman problem with a drone (TSP-D) consider hybrid truck-and-drone models of delivery, where the goal is to minimize the time required to deliver a set of packages to their respective customers and return the truck(s) and drone(s) to the origin depot. In both problems, the drone can carry one homogeneous package at a time. Theoretical analysis, exact solution methods, heuristic solution methods, and computational results are presented. In the mothership and drone routing problem (MDRP), we consider the case where the larger launch vehicle is free to move in Euclidean space (the open seas) and launch a drone to visit one target location at a time, before returning to the ship to pick up new cargo or refuel. The mothership and high capacity drone routing problem (MDRP-HC) is a generalization of the mothership and drone routing problem, which allows the drone to visit multiple targets consecutively before returning to the ship. MDRP and MDRP-HC contain elements of both combinatorial optimization and continuous optimization. In the multi-visit drone routing problem (MVDRP), a drone can visit multiple targets consecutively before returning to the truck, subject to energy constraints that take into account the weight of packages carried by the drone.Item COVERAGE AND ROUTING IN DYNAMIC NETWORKS(2016) Rabieekenari, Ladan; Baras, John S.; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Dynamic networks have become ubiquitous in the current technological framework. Such networks have widespread applications in commercial, public safety and military domains. Systems utilizing these networks are deployed in scenarios influencing critical aspects of human lives, e.g. connecting first responders to command center in disasters, wildlife monitoring, vehicular communication, and health care systems. %Dynamicity of a communication network can be either due to network dynamics or input dynamics. Network dynamics means the topology of the network changes over time. In these networks, nodes and edges may come and go. Input dynamics refers to changes in load of the network. In this dissertation, we explore two significant aspects of dynamic networks. In the first part of the dissertation, we study coverage problem in dynamic networks such as public safety networks. Networking infrastructure can partially (or sometimes fully) breakdown during a catastrophe. At the same time, unusual peaks in traffic load could lead to much higher blocking probability or service interruptions for critical communication. Lack of adequate communication among emergency responders or public safety personnel could put many lives at risks. One possible solution to deal with such scenarios is through the use of mobile/portable infrastructures, commonly referred to as Cells on Wheels (COW) or Cells on Light Trucks (COLT). These mobile cells can effectively complement the existing undamaged infrastructure or enable a temporary emergency network by themselves. Given the limited capacity of each cell, variable and spatially non-uniform traffic across the disaster area can make a big impact on the network performance. Not only judicious deployment of the cells can help to meet the coverage and capacity demands across the area, but also intelligent relocation strategies can optimally match the network resources to potentially changing traffic demands. Assuming that each cell can autonomously change its location, in this dissertation, we investigate such opportunities and constraints. We propose strategies for autonomous relocation of the mobile resource to adapt network coverage and increase the supported user traffic. We demonstrate the performance improvement for several scenarios via simulations using our algorithms. In practical scenarios, typically there are some areas in the field where mobile base stations cannot move into. Structural obstacles, areas with outstanding water or other hazardous materials, or surfaces with debris are examples of prohibited areas that mobile cells are expected to avoid. Such prohibited areas introduce additional constraints on designing intelligent relocation strategies. We propose a decentralized relocation algorithm that enables mobile cells to adapt their positions in response to potentially changing traffic patterns in a field with such prohibited areas. In the second part of dissertation, we study routing problem in dynamic networks. Routing is critical when there is no direct link connecting source to its destination. Performance of this algorithm is critical in many different applications. Two important metrics in routing are delay and throughput. We propose a throughput-optimal routing and scheduling algorithm that improves delay performance by accounting for the network topology. First, we propose algorithm for the fixed topology scenario. We improve delay performance by solving an optimization problem which aims to send packets mostly to greedy neighbors, subject to throughput-optimality constraints. Next, we consider the network with dynamic topology, where routers or links may be added or removed during time. We propose variations of the proposed algorithm for networks with dynamic topology. We identify key design parameters and illustrate the performance of our schemes through simulations.Item Using Internet Geometry to Improve End-to-End Communication Performance(2009) Lumezanu, Cristian; Spring, Neil; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The Internet has been designed as a best-effort communication medium between its users, providing connectivity but optimizing little else. It does not guarantee good paths between two users: packets may take longer or more congested routes than necessary, they may be delayed by slow reaction to failures, there may even be no path between users. To obtain better paths, users can form routing overlay networks, which improve the performance of packet delivery by forwarding packets along links in self-constructed graphs. Routing overlays delegate the task of selecting paths to users, who can choose among a diversity of routes which are more reliable, less loaded, shorter or have higher bandwidth than those chosen by the underlying infrastructure. Although they offer improved communication performance, existing routing overlay networks are neither scalable nor fair: the cost of measuring and computing path performance metrics between participants is high (which limits the number of participants) and they lack robustness to misbehavior and selfishness (which could discourage the participation of nodes that are more likely to offer than to receive service). In this dissertation, I focus on finding low-latency paths using routing overlay networks. I support the following thesis: it is possible to make end-to-end communication between Internet users simultaneously faster, scalable, and fair, by relying solely on inherent properties of the Internet latency space. To prove this thesis, I take two complementary approaches. First, I perform an extensive measurement study in which I analyze, using real latency data sets, properties of the Internet latency space: the existence of triangle inequality violations (TIVs) (which expose detour paths: ''indirect'' one-hop paths that have lower round-trip latency than the ''direct'' default paths), the interaction between TIVs and network coordinate systems (which leads to scalable detour discovery), and the presence of mutual advantage (which makes fairness possible). Then, using the results of the measurement study, I design and build PeerWise, the first routing overlay network that reduces end-to-end latency between its participants and is both scalable and fair. I evaluate PeerWise using simulation and through a wide-area deployment on the PlanetLab testbed.Item THE VEHICLE ROUTING PROBLEM WITH DEMAND RANGES(2009) Cornick, Namrata Uppal; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The classic Capacitated Vehicle Routing Problem (CVRP) has been studied in the Operations Research field for over 5 decades. This thesis formulates the vehicle routing problem with a variation that has not been studied in detail. It is called the Vehicle Routing Problem with Demand Ranges (VRPDR). With increasing competition, corporations are looking to minimize costs. This problem aims to reduce the cost of distributing goods by allowing flexibility in the delivered or dropped off quantity. This benefits the customer as well, by reducing storage and other inventory costs. We solve the VRPDR problem where the customer gives the distributor a demand range. The distributor is rewarded for delivering more. A metaheuristic, record-to-record travel with demand range (RTRDR), is developed which is capable of solving large problem instances. The metaheuristic is a modification of a successful CVRP metaheuristic used in the past. In this thesis, we report results on problems ranging in size from 560 to 1200 customers. The developed metaheuristic uses the Clarke-Wright procedure to get initial solutions and then applies record-to-record travel in conjunction with two-opt moves, one point moves, and two point moves. Since the problem has not been studied yet from a computational point of view, we have developed a comparison algorithm, which takes advantage of the demand range flexibility of this problem only after the algorithm has optimized for distance alone. We use the results from this algorithm as a benchmark to compare with our proposed metaheuristic RTRDR.