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
14 results
Search Results
Item Utilizing Path Diversity via Asynchronous and Asymmetric Wakeups in Sensor Networks(2008) Rawat, Anuj; Shayman, MarkWe 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.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.Item Lifetime Maximizing Adaptive Traffic Distribution and Power Control in Wireless Sensor Networks(2006) Sun, Fangting; Shayman, Mark; Shayman, Mark; ISRIn this paper we study how to maximize the lifetime of randomly deployed wireless sensor networks by applying adaptive traffic distribution and power control. We model this problem as a linear program by abstracting the network into multiple layers. First we focus on the scenario where transmission energy consumption plays the dominant role in overall energy consumption. After ignoring the processing energy consumption, we observe that: in order to maximally extend the lifetime, each node should split its traffic into two portions, and send one portion directly to the sink, and the other one to its neighbor in the next inner layer. Next we consider the effect of incorporating the processing energy consumption. In this case, we have similar observation: for each packet to be sent, the sender should either transmit it using the transmission range with the highest energy efficiency per bit per meter, or transmit it directly to the sink. Besides studying the upper bound of maximum achievable lifetime extension, we discuss some practical issues, such as how to handle the signal interference caused by adaptive power control. Finally, we propose a fully distributed algorithm to adaptively split traffic and adjust transmission power for randomly deployed wireless sensor networks. We also provide extensive simulation results which demonstrat that the network lifetime can be dramatically extended by applying the proposed approach in various scenarios.Item Relay Placement Approximation Algorithms for k-Connectivity in Wireless Sensor Networks(2006) Kashyap, Abhishek; Khuller, Samir; Shayman, Mark; Shayman, Mark; ISRItem Lifetime Maximizing Adaptive Power Control in Wireless Sensor Networks(2006) Sun, Fangting; Shayman, Mark; shayman; ISRNetwork lifetime is one of the most critical performance measures for wireless sensor networks. Various schemes have been proposed to maximize the network lifetime. In this paper we consider the lifetime maximization problem via a new approach: adaptive power control. We focus on the sensor networks that consists of a sink and a set of homogeneous wireless sensor nodes, which are randomly deployed according to a uniform distribution. Each node has the same initial energy and the same data generation rate. We formally analyze the lifetime maximizing adaptive power control problem by dividing the network into different layers and then modelling it as a linear programming problem, where the goal is to find an optimal way to adjust the transmission power and split the traffic such that the maximum energy consumption speed among all layers is minimized, and therefore the network lifetime is maximized. One surprising observation from the numerical results is that when every node can reach the sink directly, the optimal solution for each node is to send traffic either to its next inner layer or to the sink directly. This observation has also been justified by the theoretical analysis. The numerical results also show that the lifetime elongation can still be significant even when only those nodes in the innermost few layers are allowed to adaptively adjust their transmission power. We then propose a fully distributed algorithm, the Energy-Aware Push Algorithm (EAPA), and show through simulation that it can dramatically extend the network lifetime.Item Robust Routing with Unknown Traffic Matrices(2006) Tabatabaee, Vahid; Kashyap, Abhishek; Bhattacharjee, Bobby; La, Richard J.; Shayman, Mark; Shayman, Mark; ISRItem Interesting Examples of IBGP Configuration(2006) Rawat, Anuj; Shayman, Mark; Shayman, Mark; ISRIn 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.Item Single-path routing of time-varying traffic(2006) Kashyap, Abhishek; Bhattacharjee, Bobby; La, Richard J.; Shayman, Mark; Tabatabaee, Vahdi; Shayman, Mark; ISRItem Design Optimization of Multi-Sink Sensor Networks by Analogy to Electrostatic Theory(2005) Kalantari, Mehdi; Shayman, Mark; Shayman, Mark; ISRIn this work we introduce a new mathematical tool for optimization of routes, and topology design in wireless sensor networks. We introduce a vector field formulation that models communication in the network, and routing is performed in the direction of this vector field at every location of the network. The magnitude of the vector field at every location represents the density of amount of data that is being transited through that location. We define the total communication cost in the network as the integral of a quadratic form of the vector field over the network area. Our mathematical machinery is based on partial differential equations analogous to the Maxwell equations in electrostatic theory. We use our vector field model to solve the optimization problem for the case in which there are multiple destinations (sinks) in the network. In order to optimally determine the destination for each sensor, we partition the network into areas, each corresponding to one of the destinations. We define a vector field, which is conservative, and hence it can be written as the gradient of a scalar function (also known as a potential function). Then we show that in the optimal assignment of the communication load of the network to the destinations, the value of that potential function should be equal at the locations of all the destinations. Also, we show that such an optimal partitioning of the network load among the destination is unique, and we give iterations to find the optimal solution.Item Rollout Algorithms for Integrated Topology Control and Routing in Wireless Optical Backbone Networks(2003) Kashyap, Abhishek; Lee, Kwang-Il; Shayman, Mark; Shayman, Professor Mark; ISRWe consider a wireless backbone network with free space optical point-to-point links. Such a network could form a backbone for either a cellular or hierarchical ad hoc network. Each backbone node has a limited number of transceivers with which to establish links to neighbors. Given estimated aggregate traffic demands between source and destination backbone nodes, we consider the problem of topology control and routing-- determining which links to set up and which routes to establish in order to maximize the throughput. While the problem may be formulated as an integer linear program, its solution is computationally prohibitive. Consequently, we use the mathematical technique of rollout to develop effective heuristic algorithms. Through simulation experiments, we show that the performance of the rollout algorithms we derive is clearly superior to that of the initial heuristic algorithms on which they are based.