This paper introduces a new resource sharing problem in wireless sensor networks (WSNs) that employ energy harvesting for prolonged network uptime. The problem is on managing a given infrastructure of EH-WSNs by supporting concurrent applications. Each application is characterized by a set of traffic generating nodes, a sink node, and a minimum required traffic rate that should be periodically delivered to its sink node. The overall EH-WSN is modelled by a probabilistic graph where energy fluctuation over time in each node is described by a probability distribution and handled by adjusting the flow relaying capacity of a node. Performance of the obtained network management scheme is assessed by a reliability metric on the formulated probabilistic graph. We call the formulated problem the flow sharing reliability (FS-REL) problem in EH-WSNs. We present a heuristic algorithm to cope with the problem using ideas from minimum cost multi-commodity flows in networks and approximation of flow reliability using a factoring algorithm. We also present numerical results that give more insights into the problem and the proposed solution.

In this paper, we deal with a wireless sensor network (WSN) infrastructure management problem where a provider wants to partition a network into a given number of node-disjoint subgraphs (called slices) for running different user applications. Nodes in the given infrastructure use energy harvesting for prolonged service time. The nodes manage fluctuations in their stored energy by adjusting their transmission range. We assume that each node is assigned an importance weight, and model the overall network using a probabilistic graph. In this context, we formalize a problem, denoted k-WBS-RU (for k weighted balanced slices with range uncertainty), to partition the network into k slices subject to some connectivity and operation constraints. We devise a solution to the problem, and present numerical results on the quality of the obtained slices. We also discuss an application of the proposed framework and solution when the assigned weights are derived from an area coverage application.

A basic wireless sensor networks (WSNs) reliability problem calls for finding the likelihood that a sink node receives at least a certain amount of traffic generated periodically by sensor nodes that can either operate or fail. When the nodes rely on harvesting energy from the ambient environment, a node can be in any one of a possible number of energy states with probabilities that can be estimated using measured environmental data. A node’s energy management unit can work by controlling the amount of data that can be periodically transmitted in each state. In this context, we formalize a flow reliability problem (denoted FLOWREL) in EH-WSNs. We present a method for computing lower bounds on exact solutions using an iterative algorithmic framework. Numerical results are presented to examine the performance of the devised methodology. Further, we discuss its use in a sample application that asks for determining the best sink location among a set of candidate locations.

In this paper, we consider reliability assessment of energy harvesting wireless sensor networks (EH-WSNs) deployed to guard a geographic area against intruders that can enter and exit the network through a known set of entry-exit perimeter sides. To handle energy fluctuations during different time slots, a node may reduce its transmission power. Using a probabilistic graph model, we formalize a problem denoted EH-BPDREL (for breach path detection reliability). The problem calls for estimating the likelihood that any such intrusion can be detected and reported to a sink node. Due to the hardness of the problem, bounding algorithms are needed. We devise an efficient algorithm to solve a core problem that facilitates the design of various lower bounding algorithms. We obtain numerical results on the use of Monte Carlo simulation to estimate the probabilistic graph parameters, and illustrate the use of our devised algorithm to bound the solutions.

We consider Wireless Sensor Networks (WSNs) that undergo frequent uncontrollable topological changes over time due to changes in node states. Examples of such WSNs include networks that utilize energy replenishment methods, networks where a node's communication or sensing capabilities vary over time, and Underwater Sensor Networks (UWSNs) with free mobile floats. Quantifying the likelihood that a network of this type succeeds in performing a given task requires the adoption of a suitable mathematical model coupled with the development of a suitable performance evaluation algorithm. Our work here serves the above goal for networks where each node can be in any one of a possible set of states, each node has a weight, the topology of the network varies over time, and we want to find the likelihood that the network is in a state with a connected component whose total weight is at least a given threshold value.

We consider an Underwater Sensor Network (UWSN) where nodes can move freely according to water currents. Thus, a node location after sometime of deployment can only be described probabilistically. Nodes close to the water surface can use their GPS devices to localize themselves, whereas other nodes rely on their neighbours for localization. Given the location uncertainty in such networks, we aim at developing a methodology for estimating the probability that a given node succeeds in localizing itself. We devise a graph theoretic approach based on embedding a graph model of a given UWSN in a special graph, called a k-tree. The devised algorithm is exact and runs in polynomial time, for any fixed k. We also present numerical results to explore the performance of the devised algorithm.

In this paper, we consider Underwater Sensor Networks (UWSNs) where nodes can move freely with underwater currents. In such networks, it is of interest to estimate the likelihood that a network has a connected component of (at least) a given size during some interval of time of interest after deployment. We formalize the problem using a probabilistic graph model, and develop a dynamic programming algorithm to solve the problem exactly when the graph has an interval representation. The interval representation model is motivated by scenarios where nodes move along a path in a relatively long but thin geographical area. We present numerical results on the performance of the algorithm under varying conditions of the required component size, and the size and structure of the set of intervals representing the probabilistic graph.

In this paper we consider Underwater Sensor Networks (UWSNs) employing nodes that move freely with water currents. Localization of nodes in UWSNs depends on collaborative work of nodes in the network since GPS signals fade quickly underwater. Using the concept of probabilistic graphs to capture node location information, we formalize a problem called the Probabilistic Localization Problem (P-LOC) that calls for computing the probability that a given target node in a given probabilistic graph can localize itself during some interval of time. We then devise an iterative algorithm that gives exact solution to the problem if allowed to execute a sufficient number of iterations, otherwise, the algorithm provides a lower bound on the solution. We present numerical results to show the performance of the algorithm.

The breach path detection reliability (BPDREL) problem is a core Wireless Sensor Networks (WSNs) surveillance problem discussed in the literature. The problem concerns WSNs deployed to guard an area with multiple entry-exit sides where intruders can cross the area through any specified subset of sides. Nodes in the network can fail randomly, and we ask what is the likelihood that the network can successfully detect intrusion events. Our work here develops methods for deriving upper bounds on the solutions by means of packing network nodes into cutsets having certain properties. The developed methods are efficient and can be used either as standalone tools, or as subroutines to improve the time-accuracy of other iterative methods that can achieve higher accuracy with increased number of iterations. The obtained numerical results are used to analyze the merits of the devised methods. In addition, we discuss and evaluate the applicability of our methods to tackle an optimum sink location design problem.

Wireless Sensor Networks (WSNs) equipped with directional communication and sensing devices provide a high level of tunability needed in optimizing their performance in critical applications. Such devices and nodes, however, remain prone to failure when operating in the field. In this paper we formalize a problem, called directional breach path detection reliability (DIR-BPDREL), that quantifies the ability of such networks to jointly detect and report unauthorized traversal through a network when communication and sensing devices fail independently of each other. We adopt a framework for deriving lower and upper bounds on exact reliability solutions, and develop efficient algorithms for optimizing the computations using pathset and cutset structures of the given network. The algorithms process separate communication and sensing graphs to ensure joint detection and reporting of intrusion events from multiple possible entry-exit sides. The obtained numerical results give insight into the effect of various design parameters on network wide performance.

We consider Wireless Sensor Networks (WSNs) deployed in the plane to guard against intrusion events aiming to access a specified area of interest. Sensor nodes of the network are assumed to be unreliable with known failure probabilities. In such an environment, system dependability is of prime importance. To aid in analyzing dependability, we formalize a network wide reliability measure that quantifies the likelihood that the network provides simultaneous detection and reporting of intrusion events. We refer to the problem of computing the defined measure as the breach path to target area reliability (BPTA-REL) problem. We show that the problem admits polynomial time solution on grid networks employing diagonal links where the width of a grid is limited but the length can be arbitrarily large. Such grid topologies are useful for border area protection applications. The result is notable since the BPTA-REL problem is #P-hard in general. We present numerical results that show the potential use of our devised algorithm as a network design tool.

A common configuration used in area surveillance occurs when an area of interest is protected by deploying a number of concentric rings of sensor nodes around the area. When operating in a harsh environment, the nodes of the deployed Wireless Sensor Network (WSN) become subject to random failure. Consequently, the network becomes vulnerable to undetected unauthorized traversals to the area of interest. In this paper, we formulate a network wide reliability problem that quantifies the likelihood that the network continues to provide joint intrusion detection and reporting to a sink node at the center of the network. The algorithm uses a dynamic programming approach that strives to process many of the operating states of network while running efficiently. Our obtained numerical results illustrates the use of the algorithm as a network design tool.

Area surveillance against intrusion events is an important application of Wireless Sensor Networks (WSNs). Sensor nodes, however, are subject to random failure and hence the ability of a successful network operation is quantified probabilistically. In many situations, the area under surveillance is 2-dimensional and bounded by a polygon with known sides. The breach path detection reliability (BPDREL) problem calls for computing the network's success probability in detecting an intruder that crosses the perimeter through any specified subset of the available entry-exit polygon sides. Our work here analyzes pathsets and cutsets of the BPDREL problem and devises an algorithm that can compute lower and upper bounds on the exact solution based on the ability to compute good pathsets and cutsets. The effectiveness of the devised solution, as well as its potential use in solving some related surveillance design problems are demonstrated using simulation results.

Wireless Sensor Networks (WSNs) deployed for surveillance tasks are sometimes required to detect unauthorized traversal of intruders from outside the WSN area to an internal area of interest. When network nodes are subject to random failure, it becomes important to estimate the likelihood of successfully detecting and reporting an intrusion event to the sink node. To serve this purpose, we formalize the breach path to target area reliability (BPTA-REL) problem. We devise efficient methods to derive lower and upper bounds on the exact solution. Our approach is based on developing efficient algorithms for generating network pathsets and cutsets for the problem. Next, we present simulation results that illustrate the effectiveness of the obtained bounds as well as their potential use in tackling related design problems.

We consider wireless sensor networks for surveillance applications where a node's ability to detect and report intrusion is described probabilistically. In addition, intruders traversing an area may probabilistically disrupt sensors by spreading jamming devices. Thus, at any instant a network can be either in an operating state that enables detection, or a failed state. To analyze the likelihood that a network is in an operating state, we formalize a problem called the path exposure (EXPO) problem. We show that EXPO is #P-hard and then devise an algorithm that works by processing most probable network states first. Our algorithm computes exact solutions for small networks efficiently. For large networks, the algorithm computes lower and upper bounds on a solution. The obtained simulation results analyze the gap between the obtained lower and upper bounds. We also demonstrate the use of our algorithm as a tool in analyzing two related intrusion problems.