1,720,991 research outputs found
Design Optimization of Multi-Sink Sensor Networks by Analogy to Electrostatic Theory
Full text linkIn 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
Lifetime Maximizing Adaptive Power Control in Wireless Sensor Networks
Full text linkNetwork 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
Interesting Examples of IBGP Configuration
Full text linkIn 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
Solving POMDP by Onolicy Linear Approximate Learning Algorithm
Full text linkThis paper presents a fast Reinforcement Learning (RL) algorithm to solve Partially Observable Markov Decision Processes (POMDP) problem. The proposed algorithm is devised to provide a policyשּׂaking framework for Network Management Systems (NMS) which is in essence an engineering application without an exact model.The algorithm consists of two phases. Firstly, the model is estimated and policy is learned in a completely observable simulator. Secondly, the estimated model is brought into the partially observed realorld where the learned policy is then fineהּuned.The learning algorithm is based on the onאּolicy linear gradientﬤescent learning algorithm with eligibility traces. This implies that the Qזּalue on belief space is linearly approximated by the Qזּalue at vertex over the belief space where onשּׁine TD method will be applied.The proposed algorithm is tested against the exact solutions to extensive small/middleדּize benchmark examples from POMDP literature and found near optimal in terms of averageﬤiscountedגּeward and stepהּogoal. The proposed algorithm significantly reduces the convergence time and can easily be adapted to large stateאַumber problems
Using POMDP as Modeling Framework for Network Fault Management
Full text linkFor highדּpeed networks, it is important that fault management be proactive--i.e., detect, diagnose, and mitigate problems before they result in severe degradation of network performance. Proactive fault manageשּׂent depends on monitoring the network to obtain the data on which to base manager decisions. However, monitoring introduces additional overhead that may itself degrade network performance especially when the network is in a stressed state. Thus, a tradeoff must be made between the amount of data collected and transferred on one hand, and the speed and accuracy of fault detection and diagnosis on the other hand. Such a tradeoff can be naturally formulated as a Partially Observable Markov decision process (POMDP).Since exact solution of POMDPs for a realistic number of states is computationally prohibitive, we develop a reinforcementשּׁearningﬢased fast algorithm which learns the decisionגּule in an approximate network simulator and makes it fast deployable to the real network. Simulation results are given to diagnose a switch fault in an ATM network. This approach can be applied to centralized fault management or to construct intelligent agents for distributed fault management
Stability of Wireless Networks for Mode S Radar
Full text linkStability issues in a connectionless, one-hop queueing system featuring servers with overlapping service regions (e.g. a Mode Select (Mode S) Radar communications network or part of an Aeronautical Telecommunications Network (ATN) network) are considered, and a stabilizing policy is determined in closed-loop form. The cases of queues at the sources (aircraft) and queues at the servers (base stations) are considered separately. Stabilizability of the system with exponential service times and Poisson arrival rates is equivalent to the solvability of a linear program and if the system is stabilizable, a stabilizing open loop routing policy can be expressed in terms of the coefficients of the solution to the linear program. We solve the linear program for the case of a single class of packets.The research and scientific content in this material has been published under the same title in the Proceedings of the 32nd Conference on Information Sciences and Systems; Princeton, NJ; March 1998.</Center
Multi-time Scale Markov Decision Processes
Full text linkThis paper proposes a simple analytical model called M time-scale MarkovDecision Process (MMDP) for hierarchically structured sequential decision making processes, where decisions in each level in the M-level hierarchy are made in M different time-scales. In this model, the state space and the control space ofeach level in the hierarchy are non-overlapping with those of the other levels, respectively, and the hierarchy is structured in a "pyramid" sense such that a decision made at level m (slower time-scale) state and/or the state will affect the evolutionary decision making process of the lower level m+1 (faster time-scale) until a new decision is made at the higher level but the lower level decisions themselves do not affect the higher level's transition dynamics. The performance produced by the lower level's decisions will affect the higher level's decisions.A hierarchical objective function is defined such that the finite-horizon value of following a (nonstationary) policy at the level m+1 over a decision epoch of the level m plus an immediate reward at the level m is the single step reward for the level m decision making process. From this we define "multi-level optimal value function" and derive "multi-level optimality equation."We discuss how to solve MMDPs exactly or approximately and also study heuristic on-line methods to solve MMDPs. Finally, we give some example control problems that can be modeled as MMDPs
Relay Placement Approximation Algorithms for k-Connectivity in Wireless Sensor Networks
Full text linkRobust Routing with Unknown Traffic Matrices
Full text linkIn this paper, we present an algorithm for intra-domain traffic engineering. We assume that the traffic matrix, which specifies traffic load between every source-destination pair in the network, is unknown and varies with time, but that always lies inside an explicitly defined region. Our goal is to compute a fixed robust routing with best worst case performance for all traffic matrices inside the bounding region. We formulate this problem as a semi-infinite programming problem. Then, we focus on a special case with practical merits, where (1) the traffic matrix region is assumed to be a polytope specified by a finite set of linear inequalities, and (2) our objective is to find the routing that minimizes the maximum link utilization. Under these assumptions, the problem can be formulated as a polynomial size linear programming (LP) problem with finite number of constraints. We further consider two specific set of constraints for the traffic matrix region. The first set is based on the hose model and limits the total traffic rate of network point of presence (PoP) nodes. The second set is based on the pipe model and limits the traffic between source-destination pairs. We study the effectiveness of each set of constraints using extensive simulations
- …
