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

Filters

2004 - 20062

Settings

Author: search.filters.author.Kashyap, AbhishekSubject: search.filters.subject.Engineering, Electronics and Electrical

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Robust design of wireless networks
    (2006-11-20) Kashyap, Abhishek; Kashyap, Abhishek; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    We consider the problem of robust topology control, routing and power control in wireless networks. We consider two aspects of robustness: topology control for robustness against device and link failures; routing and power control for robustness against traffic variations. The first problem is more specific to wireless sensor networks. Sensors typically use wireless transmitters to communicate with each other. However, sensors may be located in a way that they cannot even form a connected network (e.g, due to failures of some sensors, or loss of battery power). Using power control to induce a connected topology may not be feasible as the sensors may be placed in clusters far apart. We consider the problem of adding the smallest number of relay nodes so that the induced communication graph is k-connected. We consider both edge and vertex connectivity. The problem is NP-hard. We develop approximation algorithms that find close to optimal solutions. We consider extension to higher dimensions, and provide approximation guarantees for the algorithms. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal obstacles. We also consider extension to networks with non-uniform transmission range, and provide approximation algorithms. The second problem we consider is of joint routing and transmission power assignment in multi-hop wireless networks with unknown traffic. We assume the traffic matrix, which specifies the traffic load between every source-destination pair in the network, is unknown, but always lies inside a polytope. Our goal is to find a fixed routing and power assignment that minimizes the maximum total transmission power in the network over all traffic matrices in a given polytope. In our approach, we do not need to monitor and update paths to adapt to traffic variations. We formulate this problem as a non-convex semi-infinite programming problem. We propose an efficient algorithm that computes a routing and power assignment that is schedulable for all traffic matrices in the given polytope. We perform extensive simulations to show that the proposed algorithm performs close to algorithms that adaptively optimize their solution to the traffic variations.
  • Thumbnail Image
    Item
    Profile Based Topology Control and Routing in Wireless Optical Networks
    (2004-05-04) Kashyap, Abhishek; Shayman, Mark A; Electrical Engineering
    The problem of topology control and routing of bandwidth-guaranteed flows over wireless optical backbone networks is addressed. The input is a potential topology and a traffic profile. The constraints are that of limited interfaces at each node and the limited link bandwidth, and the objective is to maximize the throughput. The problem turns out to be NP-Hard. A new framework for integrated topology control and routing is proposed. A simple heuristic is proposed, and efficient rollout algorithms are proposed which enhance the heuristic. The routing problem is formulated as a multi-commodity flow problem, and is used to enhance the rollout algorithms to achieve a higher throughput. Another set of heuristics is proposed which use matching theory and multi-commodity flow formulation of routing to achieve the desired results. We enhance the heuristics to provide fairness to the ingress-egress pairs in terms of how much traffic we route for each of them.