Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Rawat, Anuj

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Utilizing Path Diversity via Asynchronous and Asymmetric Wakeups in Sensor Networks
    (2008) Rawat, Anuj; Shayman, Mark
    We present an asynchronous wakeup policy for wireless sensor networks that exploits the available path diversity for maximizing the expected network lifetime. We assume a random traffic generation model such that the rate is constant in time. Each node is assumed to have a set of forwarding neighbors, any of which may be used for forwarding its traffic to the sink. A node having data packet to send, transmits the packet to the first available node in its forwarding set. In order to maximize the network lifetime, we balance the power dissipation at the network nodes by adjusting the wakeup parameters at various nodes. Allowing different nodes to wakeup with different rates makes the scheme asymmetric. For ease of analysis, we restrict ourselves to static, open-loop policies. We show that the optimization problem is a Signomial Program (SP), that can be well approximated as a Geometric Program (GP). By extensive simulations, we compare the asymmetric policy thus obtained to the best possible symmetric policy obtained from the same optimization setup but ensuring additionally that the wakeup rates at all the nodes are the same (in which case the optimization problem is shown to be exactly a GP). The simulations show that allowing asymmetry can extend the network lifetime by effectively exploiting the available path diversity. Moreover, we also prove that, in case of symmetric policies, no piecewise static policy can beat the simple static policy that we use for comparison in our results. This shows that in the space of open-loop, asynchronous wakeup policies, employing the static, asymmetric policy presented in this paper is much more profitable than even the best piecewise static, symmetric policy.
  • Thumbnail Image
    Item
    Coloring Rooted Subtrees on a Bounded Degree Host Tree
    (2007) Rawat, Anuj; Shayman, Mark; La, Richard J.; Marcus, Steven I.
    We consider a rooted tree R to be a rooted subtree of a given tree T if the tree obtained by replacing the directed arcs of R by undirected edges is a subtree of T. In this work, we study the problem of assigning colors to a given set of rooted subtrees of a given host tree such that if any two rooted subtrees share a directed edge, then they are assigned different colors. The objective is to minimize the total number of colors used in the coloring. The problem is NP hard even in the case when the degree of the host tree is restricted to 3. This problem is motivated by the problem of assigning wavelengths to multicast traffic requests in all-optical tree networks. We present a greedy coloring scheme for the case when the degree of the host tree is restricted to 3 and prove that it is a 5/2-approximation algorithm. We then present another simpler coloring scheme and prove that it is an approximation algorithm for the problem with approximation ratio 10/3, 3 and 2 for the cases when the degree of the host tree is restricted to 4, 3, and 2, respectively.
  • Thumbnail Image
    Item
    Interesting Examples of IBGP Configuration
    (2006) Rawat, Anuj; Shayman, Mark; Shayman, Mark; ISR
    In this paper we give examples to show that if an Internal Border Gateway Protocol (IBGP) configuration using route reflections violates even one of the four conditions mentioned in the theorem given in a previous work, then there may be persistent oscillations or forwarding loops.