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.

Our work in this paper concerns a wireless sensor network (WSN) problem, called the path exposure with communication range uncertainty (EXPO-RU) problem. Nodes in the network are assumed to rely on energy harvesting from the ambient environment to achieve prolonged operation of a WSN deployed to monitor unauthorized traversal along a given path. Fluctuations in the harvested energy are assumed to affect each node’s transmission range. A 3-state probabilistic model where each node can be either in a full, reduced, or depleted energy state is used. We present two algorithms that complement existing algorithms in the literature to assess the reliability of a given energy harvesting wireless sensor network (EH-WSN). Each algorithm provides a basic tool that enables the construction of many other algorithms to bound the exact solution of the problem. We also present numerical results that show the impact of using the presented algorithms.

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.

In this paper, we consider WSNs where nodes harvest solar energy for sustainable operation. We use a probabilistic graph model that associates a probability distribution with each node to model the random variability of a node’s transmission range. In its basic form, the graph uses a 3-state node model that associates a probability distribution representing the likelihood that a node is either in a full power, reduced power, or failed state. Using this model, we tackle a problem, called path exposure with transmission range uncertainty (EXPO-RU) to analyze the exposure of a given path that we want to monitor against unauthorized traversal. The problem calls for quantifying the ability of an EH-WSN to jointly detect and report a traversal along the given path. To assess the reliability of an EH-WSN, we develop an algorithm for computing upper bounds on exact solutions, and present numerical results to analyze its performance.

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.

In this work, we consider a fundamental wireless sensor network (WSN) problem where the network is deployed to guard against unauthorized traversal along a given path. Nodes are assumed to utilize energy harvesting from the ambient environment, and fluctuations in a node's energy are assumed to affect its transmission range. In this context, we investigate a problem called the path exposure with range uncertainty (EXPO-RU) problem that asks for the likelihood that the EH-WSN can provide joint detection and reporting of the traversal. The problem models the EH-WSN using a probabilistic graph where each node is associated with multiple possible states. We present algorithms for deriving lower and upper bounds from operating and failed network configurations, respectively. We discuss properties of the presented methods, present numerical results that illustrate their usefulness, and draw remarks on the obtained numerical results.

We investigate the likelihood that two nodes are connected in an Underwater Wireless Sensor Network (UWSN) where nodes are floating freely with the underwater currents and the location of nodes at any given time can only be determined in a probabilistic fashion. This problem is #P-hard, thus, we propose HB-Conn2, an algorithm that returns an exact solution in polynomial time when applied on a set of node-disjoint (s, t)-paths.

In this paper, we consider terrestrial wireless sensor networks (WSNs) that utilize energy replenishment methods such as environmental energy harvesting or wireless charging to achieve perpetual operation. In such networks, a node's operating energy fluctuates over time, thus affecting its transmission range. Accordingly, we adopt a simple model that associates a probability distribution representing the likelihood that a node falls in either a failed state, a state where it can transmit in full power, or reduced power. Using the probabilistic model, we formalize a problem, called EXPO-RU, to analyze the exposure of a given path that we want to monitor for unauthorized intrusion. The problem calls for computing the likelihood that the network succeeds in detecting intrusion along the given path. We present algorithms for computing lower bounds on the exact solutions, and draw remarks on the obtained performance results.

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.

We identify 13 problems whose solutions can significantly enhance our ability to design and analyze firewalls and other packet classifiers. These problems include the firewall equivalence problem, the firewall redundancy problem, the firewall verification problem, and the firewall completeness problem. The main result of this paper is to prove that every one of these problems is NP-hard. Our proof of this result is interesting in the following way. Only one of the 13 problems, the so called slice probing problem, is shown to be NP-hard by a reduction from the well-known 3-SAT problem. Then, the remaining 12 problems are shown to be NP-hard by reductions from the slice probing problem. This proof suggests that the slice probing problem plays an important role in the design and analysis of firewalls. The negative results of this paper suggest that firewalls designers may need to rely on SAT solvers to solve instances of these 13 problems or may be content with probabilistic solutions of these problems. On the positive side, we show that each of the 13 firewall analysis problems presented in this paper is polynomially reducible to the slice probing problem. Thus any algorithm, that can effectively solve the slice probing problem, can also be employed to effectively solve any of these 13 problems.

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.

In this paper we consider a wireless sensor network (WSN) deployed to monitor a set of targets with known positions. Each target has an associated desired level of coverage by its neighbouring sensor nodes. The network deployment process introduces node placement uncertainty described by known probability distributions. Consequently, deficiency in achieving the desired coverage levels occurs with certain probabilities. To estimate such probabilities, we formalize a target coverage deficiency (TCD) problem. We show that the TCD problem is #P-hard even when restricted to grid WSNs. We then consider networks where node transmission ranges guarantee that the network after deployment has the same connectivity as the planned network. For such networks, we devise a dynamic programming algorithm that can solve a discrete version of the problem exactly and can produce lower bounds on the solution of any arbitrary given instance of the problem. We present simulation results that investigate the accuracy of the algorithm, and illustrate its usefulness in evaluating performance of any given node deployment scheme.

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.

We consider wireless sensor networks (WSNs) deployed in the plane for area surveillance against intrusion attacks. Sensor nodes often employ low-cost sensing and wireless communication modules that are prone to random failure especially when operated in harsh environments. To quantify the network's ability to monitor the area, we formalize the breach path detection reliability (BPDREL) problem that takes as input a specified set of entry-exit pairs of network sides, and calls for computing the likelihood that the network can detect intrusion paths between any of the specified pairs of sides. We devise an exact algorithm for solving the problem on networks that can be embedded in grid networks utilizing diagonal links. Using the devised algorithm, we analyze the least and most detectable classes of intrusion paths, as well as the impact of varying various network parameters on the overall network reliability.

This paper considers wireless sensor networks (WSNs) deployed to provide surveillance against intruders that wish to cross a given area. Due to limited resources, low manufacturing cost, and operation in harsh environments, nodes in such networks are subject to random failure in the field. Hence, there is a need to develop suitable reliability assessment mechanisms to quantify a WSN's ability to perform successfully. Here, we consider one such measure, called the breach path detection reliability (BPDREL), that applies to networks where any intruder crossing a line segment between some adjacent operating pairs of sensor nodes can be detected, and the network perimeter is made of a polygon of such line segments. Each breach path across the network is associated with a pair of entry-exit sides on the perimeter. Our measure takes into account intrusion events associated with any user-specified set of such entry-exit sides. Computing the exact BPDREL can be shown to be #P-hard. We extend existing results on the BPDREL by developing an approach for deriving lower bounds on the problem for arbitrary WSNs where the sink node is located on the network's perimeter. The resulting algorithm is used to analyze the impact of varying various network parameters on the overall network reliability.

This paper deals with a resource sharing problem in wireless sensor networks (WSNs). The problem calls for identifying k data collection trees that can be managed by independent users to run applications requiring area coverage. The formalized problem, called k-balanced area coverage slices (k-BACS), calls for identifying an ensemble of k trees that share the sink node only (and no other node) in a given WSN. To avoid nodal congestion, each tree is required to satisfy constraints on the maximum degree of its nodes. The objective is to maximize the minimum total area covered by any tree in the ensemble. Existing results in the literature show that the k-BACS problem is NP-complete even if k =2. Thus, effective heuristic algorithms are needed. In this paper, we present and compare the performance of two efficient algorithms for solving the problem. Our results show that the devised algorithms produce well-balanced trees. In addition, the combined use of the computed partitions and the PEAS energy conservation protocol can produce competitive lifetime for networks where a prescribed level of area coverage is required for successful operation.

In this paper we consider wireless sensor networks (WSNs) whose nodes can fail independently of each other during normal operation. For successful operation, a network is required to provide sensing coverage of an aggregate area that exceeds a given application-specific coverage requirement. We formulate an area coverage reliability problem that quantifies the likelihood that the network can be in an operating state where the coverage condition is satisfied. Existing results show that the problem is #P-hard even when the WSN is restricted to a rectangular grid with a single corner-located sink. Thus, an exact solution is unlikely to exist for many WSN topologies. We present a framework for computing reliability lower bounds by decomposing an arbitrary WSN into subnetworks that share only the sink node and computing coverage probabilities for each subnetwork. We show that the framework yields an efficiently computable lower bound when the subnetworks are chosen to be trees and cycles. Our design utilizes a 3-state node reliability model that has been shown to improve over the conventional 2-state (operate/fail) model. The obtained results investigate some design issues of the framework, the quality of the obtained lower bounds, and discuss an application of the obtained lower bounds in improving the design of WSNs.

In this paper we formalize a problem called weighted balanced two-slice problem (WB2S) that calls for partitioning (slicing) a wireless sensor network (WSN) so as to support concurrent running of two independent applications. Our model associates a weight with each node to reflect the node's relative importance to the applications. As well, the model imposes a degree constraint on each node to control its traffic load when it operates in a multi-level tree. The problem calls for computing two disjoint trees (sharing a common sink) whose minimum total weight is maximized among all possible feasible pairs of trees. We show that the WB2S problem is NP-complete, present a dynamic program to handle the problem, analyze the algorithm, and show its potential impact by simulation.

Welcome to this special issue of the Wiley's Wireless Communications and Mobile Computing Journal

In this paper we formulate and analyze a model for assessing the reliability of a wireless sensor network (WSN) based on classifying the operating states of each node at any instant into one of three possible states: a state where both the sensing and wireless modules are operating, a state where only the wireless module is operating, and a state where the wireless module is failed. Thus, in the second state a node can only relay traffic among its neighbours without generating its own data. We define the reliability of a WSN as the probability that the sink node can collect data from a number of nodes whose total weight exceeds a specified threshold limit, given that each node can be in any one of the three possible states with a given probability. Existing results in the literature show that a restricted 2-state version of the problem is #P-hard even when the network is a rectangular grid. Nevertheless, for a rectangular W × L grid on n nodes where the sink node lies in one of the corners, the restricted 2-state reliability problem can be solved in O(nL2w) time. Thus, the algorithm runs in polynomial time for any fixed W. Our work here derives an exact algorithm for the generalized 3-state reliability model on a generalized class of grids, called diagonalized grids, while maintaining the same O(nL2w) running time. We obtain numerical results that illustrate the use of the devised algorithm as a WSN topological design tool.

In this paper we consider the design of IEEE 802.15.4 wireless sensor networks (WSNs) where nodes belong to different priority classes. Each class is characterized by a specified average data transmission rate requirement, and the overall network forms a multi-level tree. We devise a framework for constructing TDMA schedules for solving the underlying rate differentiation problem using the GTS facility of the standard. Our framework defines a class of schedules, called flow balanced schedules, that are efficient in terms of the delay incurred by packets transmitted to the sink node, and the number of packets queued in each node. We identify two useful optimization aspects that help in constructing schedules with short cycle length. We then outline an algorithm, called GTS-TDMA, which integrates two algorithms that take advantage of the identified optimization aspects, and present simulation results that show the performance gains of the devised algorithm.

In this paper we explore a fundamental joint routing and scheduling problem in wireless mesh networks (WMNs) that employ time division multiple access (TDMA). The problem, referred to as the minimum cost single flow routing and scheduling (MC-SFRS) problem, deals with incremental update of transmission schedules necessitated by dynamic arrival of new flows and termination of existing flows during the operation of the network. In the problem, we are given a multi-hop WMN, a set of ongoing flows, a transmission schedule for the ongoing flows, a set of costs associated with links, and a new flow demand. All flows contend for using one of the available wireless channels. The problem asks for finding a non-bifurcated route with minimum cost along which the new flow can be scheduled without perturbing slot assignments in the given schedule, if such route exists. Our main contribution is an efficient algorithm for solving the MC-SFRS problem for arbitrary interference relations among pairs of transmission links in networks with arbitrary topologies. Among other classes of routes, our algorithm is exact over the class of shortest routes. The obtained simulation results demonstrate the effectiveness of our proposed algorithm over the competing method of exact scheduling for a fixed routing tree. In addition, the results show improvement obtained by using our algorithm to augment the schedules obtained by fixed tree routing.

In this paper we consider multi-hop wireless mesh networks intended to provide Internet connectivity to both end users and hotspots. In such networks mechanisms for provisioning QoS for delay sensitive flows arise as an important topic. In this context, we focus on the non-bifurcated (single path) r

This paper deals with two fundamental joint routing and scheduling problems in multi-hop wireless mesh networks (WMNs) employing time division multiple access (TDMA). The problems pertain to incremental update of schedules as some of the existing flows terminate and new flow demands are received. In the first problem, referred to as single flow scheduling (SFS) problem, we are given a set of ongoing flows in a WMN, a new incoming flow demand, and a specific potential path for routing the demand. All flows contend for using one of the available wireless channels. We ask whether the new flow demand can be served without perturbing existing slot assignments in the schedule serving the current flows. In the second problem, referred to as single flow routing and scheduling (SFRS) problem, no specific route is given. We first prove that conflict graphs of trees composed of certain class of interference limited paths in wireless networks have bounded treewidth. This characterization yields efficient solution to the SFS problem, among a number of other resource allocation problems in wireless networking. Next we consider the SFRS problem in grid networks. For such networks, we present an efficient solution to a generalized version of the SFRS problem where each link is associated with a cost, and a minimum cost schedulable route is desired. Using both concrete examples and simulation, we show that the devised SFRS algorithm yields improved throughput results over a competing approach that uses tree based routing.

On behalf of the Organizing Committee, it is my great pleasure to welcome you to the 34th annual IEEE Conference on Local Computer Networks (LCN). IEEE LCN is the conference on leading edge and practical computer networking. IEEE LCN 2009 is being held in Zurich, Switzerland during October 20 to 23, 2009. This is the fifth time that IEEE LCN has been hosted outside of the US. LCN 2009 continues a tradition of having authors from many countries across the world. This year, the top twelve author countries are Germany, USA, France, Canada, Australia, Japan, Korea, Spain, United Kingdom, Switzerland, China, and Norway.

We discuss the stabilization properties of networks that are composed of ¿displacement elements¿. Each displacement element is defined by an integer K, called the displacement of the element, an input variable x, and an output variable y, where the values of x and y are non-negative integers. An execution step of this element assigns to y the maximum of 0 and K + x. The objective of our discussion is to demonstrate that two principles play an important role in ensuring that a network N is stabilizing, i. e. starting from any global state, network N is guaranteed to reach a global fixed point. Specifically, the principle of consistent fixed points is analogous to the requirement that a control system be free from self-oscillations. And the principle of negative gain is analogous to the requirement that the feedback loop of a sum of displacements along every directed loop in network N is negative.

Wireless sensor networks (WSNs) have many applications in industry and environmental monitoring where sensor nodes are deployed at fixed places for monitoring some phenomena. One of the commonly used deterministic deployment topologies is a rectangular grid. In a WSN reliability measure that considers the aggregate flow of sensor data into a sink node is formulated, and it has been shown that computing this measure for an arbitrary WSN is #P-hard. Thus, it is unlikely that efficient algorithms for solving the problem exist. In this paper we consider a WSN deployed on rectangular W times L grid (WSG) and show that the problem remains #P-hard even when restricted to the grid graph model. We then present a routing scheme upon which we develop an O(nL2W) algorithm to compute the exact WSG reliability. Therefore, for Wradicn). We also present numerical results that demonstrate some of the potential applications of the algorithm. A noteworthy finding is that significant improvement in the WSG reliability can be achieved using more reliable sensors at the two boundaries adjacent to the sink node.

Consider a communication network where each process needs to securely exchange messages with its neighboring processes. In this network, each sent message is encrypted using one or more symmetric keys that are shared only between two processes: the process that sends the message and the neighboring process that receives the message. A straightforward scheme for assigning symmetric keys to the different processes in such a network is to assign each process O ( d ) keys, where d is the maximum number of neighbors of any process in the network. In this article, we present a more efficient scheme for assigning symmetric keys to the different processes in a communication network. This scheme, which is referred to as logarithmic keying, assigns O (log d ) symmetric keys to each process in the network. We show that logarithmic keying can be used in rich classes of communication networks that include star networks, acyclic networks, limited-cycle networks, planar networks, and dense bipartite networks. In addition, we present a construction that utilizes efficient keying schemes for general bipartite networks to construct efficient keying schemes for general networks.

In this paper we present an admission control framework for serving streaming connections to mobile users in wireless cellular networks. The network is assumed to allocate a fixed number of channels to streaming services, and serve each connection at a fixed data rate. In addition, it is assumed that each connection has specified bounds on the maximum tolerable start of service delay, and the total service interruption delay. The admission control problem is formalized as a discrete scheduling problem which the framework handles by utilizing a heuristic algorithm guided by a mechanism that dynamically adapts a scheduling planning interval according to the offered connection request pattern. The devised framework does not assume a priori knowledge of the distribution of the arriving requests from either the target cell, or as a consequence of handoff. Performance is compared against a scheme that assumes a priori knowledge of such traffic distribution and admits a stream only if the estimated cell overload probability, after a prescribed prediction interval, does not exceed a specified threshold value. The obtained results show improvements with regard to the achieved throughput of the connections served to completion, and forced terminations.

In this paper we consider traffic routing in 802.11- based multi-hop wireless mesh networks (WMNs). Interest in such networks arises since they offer flexible, and cost effective means of providing Internet connectivity to communities of subscribers. Successful deployment of such networks, however, hinges on the ability of the network to serve subscribers at the data rates specified by service agreements, as well as providing quality of service to certain key traffic types, such as TCP traffic, delay-jitter sensitive traffic, and traffic that requires synchronized delivery to end users. Since delays on different routes in such networks may vary widely, routing of the above traffic types can potentially benefit from non-bifurcated routing schemes that do not split flows among multiple paths. In this paper, we formalize the problem of non-bifurcated routing, while meeting subscriber demands, as an optimization problem. We present a heuristic algorithm that utilizes results from the theory of maximum flows, and insights into the routing problem to obtain efficient solutions. Simulation experiments indicate improved achieved throughput, and delay-jitter results over the use of the standard Dynamic Source Routing (DSR) algorithm.

We consider a network where users can issue certificates that identify the public keys of other users in the network. The issued certificates in a network constitute a set of certificate chains between users. A user u can obtain the public key of another user v from a certificate chain from u to v in the network. For the certificate chain from u to v, u is called the source of the chain and v is called the destination of the chain. Certificates in each chain are dispersed between the source and destination of the chain such that the following condition holds. If any user u needs to securely send messages to any other user v in the network, then u can use the certificates stored in u and v to obtain the public key of v (then u can use the public key of v to set up a shared key with v to securely send messages to v). The cost of dispersing certificates in a set of chains among the source and destination users in a network is measured by the total number of certificates that need to be stored in all users. A dispersal of a set of certificate chains in a network is optimal if no other dispersal of the same chain set has a strictly lower cost. In this paper, we show that the problem of computing optimal dispersal of a given chain set is NP-complete. Thus, minimizing the total number of certificates stored in all users is NP--complete. We identify three special classes of chain sets that are of practical interests and devise three polynomial-time algorithms that compute optimal dispersals for each class. We also present two polynomial-time extensions of these algorithms for more general classes of chain sets.

In wireless sensor networks (WSN), reliable monitoring of a phenomenon (or event detection) depends on the collective data provided by the target cluster of sensors and not on any individual node. In this paper we define a WSN reliability measure that considers the aggregate flow of sensor data into a sink node (gateway or cluster head). Given an estimation of the data generation rate and the failure probability of each sensor, we formulate the reliability measure and show that computing this measure for an arbitrary WSN is WSN. We then consider some special cases where we can either compute or approximate (bound) the reliability using an efficient algorithm. Finally, we present some numerical results that demonstrate some of the applications of our algorithms. Reliability evaluation tools are important in the context of design and analysis of sensitive information gathering sensor networks.

Provisioning multimedia streaming services to mobile users in next generation wireless networks is considered critical to the successful deployment of such networks. Streaming traffic is characterized by the need of relatively high data transmission rates, and the need to limit the wireless network delays during transmission. Such factors contribute to the importance of the design and use of scheduling mechanisms that work at the streaming connection level to manage network resources. In this paper, we consider the problem of designing schedulers that aim at maximizing the achieved throughput subject to constraints on the maximum acceptable delay that can be tolerated by each traffic stream. We propose an adaptive scheduling framework for the non-preemptive delivery of traffic streams in cellular networks where a fixed number of channels are allocated to streaming services. The obtained simulation results indicate the competitiveness of the proposed design when used online to control traffic, and the usefulness of the underlying algorithms when used offline to analyze traffic traces

In this paper, we introduce a new type of parameterized class of cutsets for the 2-terminal network reliability problem, called the circular layout (CL) cutsets with parameter k, and devise a polynomial time algorithm for computing upper bounds from such structures. The CL cutsets, and the devised bounding method are characterized by the following aspects. 1) CL cutsets include the well known class of consecutive minimal cutsets, introduced by Shanthikumar, as a proper subset. Thus, bounds obtained by our main algorithm yield strict improvements on the basic consecutive cutsets algorithm. We note that extensive empirical studies done to date have shown that the consecutive cutsets method, when empowered by heuristics for choosing suitable cutsets, yields competitive bounds. 2) CL cutsets satisfy the semilattice structure required by Shier's algorithm for computing upper bounds in time polynomial in the number of cuts in a given cutset. Thus, CL cutsets define a new class of efficiently constructible cutsets of polynomial size that benefit from such generalized algorithm. 3) For any fixed value of the parameter k, the devised bounding method can be adapted to satisfy stringent constant-time update constraints, required by the most probable state algorithm of Colbourn & Harms , for obtaining iteratively improvable bounds, without adding significant time overhead to the method. Moreover, the devised bounding algorithm is easy to implement, and the obtained numerical results show more than a 32% improvement over bounds obtained by the basic consecutive cutsets algorithm

In T. Kwon et al. (2003) the authors have developed call admission control and adaptive bandwidth allocation schemes for serving multimedia connections in cellular wireless networks with fixed cell capacity. The architecture considers an adaptive networking framework where the bandwidth of multimedia calls can be dynamically adjusted, and the proposed admission method works by enforcing an upper bound on the cell overload probability. In this paper we consider a similar adaptive framework, and devise call admission control and bandwidth allocation strategies to serve multimedia connections in a CDMA-based 3G cellular network. The architecture aims at maintaining the session's quality during both intra-cell and inter-cell user movements by limiting the cell overload probability. A novel aspect of our work is a method for exploiting a priori knowledge of user mobility patterns to estimate the cell overload probability after some prescribed prediction interval. Important properties of the devised method are proved analytically. Compared to a non-predictive admission control scheme, the obtained results show that the proposed scheme achieves a lower forced termination probability, and higher throughput while consuming less base station transmission energy

We consider a network where nodes can issue certificates that identify the public keys of other nodes in the network. The issued certificates in a network constitute a directed graph, called the certificate graph of the network. The issued certificates are dispersed among the network nodes such that the following condition holds. If any node, u, needs to send messages to any other node, v, in the network, then u can use the certificates stored in both u and v to obtain the public key of v (then u can securely send messages to v). The cost of a dispersal which assigns certificates to the nodes of a network is measured by the average number of certificates that need to be stored in one node. A dispersal is optimal if its cost is minimum. We present three algorithms and show that each algorithm computes optimal dispersals for a rich class of certificate graphs. The time complexity of each of these algorithms, when one of the algorithms is used to disperse the certificates from a given certificate graph, is O(n/sup 2/), where n is the number of nodes in the input certificate graph.

Efficient call admission control (CAC) techniques are of paramount importance in UMTS networks to satisfy the quality of service (QoS) requirements of different traffic classes and to utilize the system resources in an efficient manner. In this paper, we propose a novel uplink CAC framework to enhance existing UMTS networks on three related accounts. First, we introduce a measurement-based component to calculate the current load of the system; second, this measurement-based component is integrated with a power prediction module to estimate the load increment that the new call will bring into the system; and third, the proposed framework feeds the results obtained to a call admission control algorithm with a QoS-enforcing mechanism that gives each class of traffic different treatment based on the QoS requirement of the connections. To the best of our knowledge, ours is a first attempt towards combining the above components into one uplink CAC framework that aims to enhance system performance and to achieve per-class QoS objectives. Simulation results show that the framework is able to reduce dropping ratio for active users to zero level. Thus, it satisfies mobile users' needs resulting in stable performance levels during heavy load periods. Furthermore, the framework provides a low blocking ratio for new calls, which translates into high resource utilization. This is a highly desirable property from the service provider point of view.

The differentiated services (DiffServ) architecture for provisioning quality of service (QoS) in the Internet provides a flexible framework for supporting a variety of services in heterogeneous environments. The assured forwarding (AF) per hop behaviour is a means of providing differential treatment of various DiffServ classes through achieving higher forwarding probabilities for higher priority classes. Extending the AF model to support fine grain QoS specification in W-CDMA environments allows mobile users in third-generation systems to benefit from the economical savings made possible by resource sharing among different classes of aggregated traffic. We consider extending the AF model to support the delivery of quasi constant bit-rate (QCBR) traffic streams on the downlink. In our study, each QCBR stream is assumed to have a prescribed average bit-rate and time duration, and is expected to be transmitted to completion without interruption at the requested bit-rate. The availability of such a service is beneficial for transmitting real-time traffic to mobile devices with limited power and buffering resources. The proposed mechanisms are based on integrating a suitable power-sharing structure for achieving differential treatment between classes with a crude power prediction algorithm for estimating the probability that no forced termination will occur at certain instants in the future. We compare the performance of a non-predictive scheme with a predictive scheme for different AF classes and source information bit-rates. Our results show that significant improvement in the forwarding probability, throughput, and power utilization for the DiffServ classes can be attained using the predictive scheme.

Abstract This paper considers the following permutation routing problem: Given an N × N augmented data manipulator (ADM) network and a permutation π between its N inputs and outputs, can all the traffic connections of π be routed through the network in one pass? A number of backtrack search algorithms have been devised for recognizing ADM admissible permutations. None of the published results, however, appears to settle the time complexity of the problem. The goal of this paper was to answer the question positively by showing the first polynomial time bound for solving the problem. The devised algorithm requires O(N1.695) time to decide whether a given permutation π is admissible and compute a setting of the switches whenever π is admissible. For many practical applications, the obtained bound compares favorably with the O(N lg N) size of an N‐input ADM network. © 2002 Wiley Periodicals, Inc.

Harnessing the time varying topological aspect of mobile ad hoc networks so as to support Quality of Service (QoS) measures is a challenging problem. In this paper we develop and investigate the use of a simple spatial probabilistic locality model to enhance the performance of current on-demand routing algorithms. To explore the applicability of our approach, we examine two basic routing problems. The first problem calls for evaluating the likelihood that a given source-destination route exists, given that each mobile host on the route can be in any position of its locality set. The second problem calls for choosing the most probable route between a given source-destination pair that avoids traffic bottlenecks. In each case, we formalize a suitable problem, and devise an efficient solution strategy.

Wireless Mobile Ad hoc NETworks (MANET) provide end-users with a flexible and cheap way to access and exchange information. While most research in MANETs is oriented to the general application environments, little work is done to utilize the specific characteristics of particular application scenarios, in which end-users' behavior is quite predictable or controllable. To deploy a MANET for a particular realistic system, the end-users' behavior, or profiles, can be used to simplify the implementation and enhance the network performance. We present a scheme to simplify routing strategy in MANET with the help of end-users' mobility profiles. We also study how the routing strategy improves the network performance in a realistic city transportation system.

Abstract In this paper, we consider the integral multicommodity flow problem on directed graphs underlying two classes of multistage interconnection networks. In one direction, we consider three‐stage networks. Using existing results on (g, f)‐factors of bipartite graphs, we show sufficient and necessary conditions for the existence of a solution when the network has at most two secondary switches. In contrast, the problem is shown to be NP‐complete if the network has three or more secondaries. In a second direction, we introduce a recursive class of networks that includes multistage hypercubic networks (such as the omega network, the indirect binary n‐cube, and the generalized cube network) as a proper subset. Networks in the new class may have an arbitrary number of stages. Moreover, each stage may contain identical switches of any arbitrary size. The notion of extrastage networks is extended to the new class, and the problem is shown to have polynomial time solutions on r‐stage networks where r = 3 or where each link has a unit capacity and r ≥ 3. The latter result implies an efficient algorithm for deciding admissible permutations on conventional extrastage hypercubic networks. In contrast, we show that the multicommodity flow problem is NP‐complete on extrastage networks, even if r = 6, each link has an integral capacity ≤ 3, and all flow demands are equal.

Abstract Consider a distributed processing system with a set K of sites that can either cooperate in computing a function or hold resources required by other sites. The system is implemented using a communication network with unreliable nodes. Two simplified reliability problems then arise. In the first problem, we are interested in computing the probability that every operational pair of sites in K can communicate with each other. This problem is known to be #P‐complete. In the second problem, the sites in K are service centers. Our reliability measure is the probability that every operational site in the network is connected to at least one operational service center. In this paper, we define the class of t‐polygon graphs, t ≥ 3, as the intersection graphs of straight‐line chords in a convex t‐gon. Hence, any t‐polygon graph is a circle graph. We show that both problems admit polynomial time solutions when the underlying graph of the network is restricted to a t‐polygon graph, for a fixed t.

Abstract In this paper, we show that every 3‐connected (3‐edge‐connected) planar graph contains a 2‐connected (respectively, 2‐edge‐connected) spanning partial 2‐tree (series‐parallel) graph. In contrast, a recent result implies that not all 3‐connected graphs contain 2‐edge‐connected series‐parallel spanning subgraphs.

The optimum communication spanning tree problem is to locate a spanning tree which minimizes the sum of the lengths of the shortest routes between all pairs of vertices in a graph, weighted by traffic requirements. Although NP-complete in general, this problem has an efficient solution for series-parallel graphs when all requirements are equal. This problem was introduced by Hu, who gave an efficient solution for the restricted case when the network is complete and the distances are equal.