Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Robust design of wireless networks

    Thumbnail
    View/Open
    umi-umd-3908.pdf (568.3Kb)
    No. of downloads: 3118

    Date
    2006-11-20
    Author
    Kashyap, Abhishek
    Advisor
    Kashyap, Abhishek
    Metadata
    Show full item record
    Abstract
    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.
    URI
    http://hdl.handle.net/1903/4118
    Collections
    • Electrical & Computer Engineering Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility