We consider the problem of preserving data in intermittently connected sensor networks wherein sensor nodes do not always have connected paths to the base stations. The generated data is first stored inside the network before being uploaded to the base station when uploading opportunities arise. Each node has both limited energy level and limited storage space, and is associated with a probability of failure. To guarantee that at any moment, each generated data item is available for being uploaded in the presence of node failure, we propose to replicate K copies of each data item in the network, where K depends upon the node failure probability. We refer to the problem as Data K-Availability Problem (DKAP). DKAP is naturally divided into two phases: K-Availability creation and K-Availability maintenance. For K-Availability creation, we show that the problem is NP-hard for arbitrary data sizes, and that it is equivalent to minimum cost flow problem for unit data sizes. For K-Availability maintenance, we show that it is NP-hard even for unit data sizes and design a centralized greedy heuristic. We further design an efficient and low-overhead distributed algorithm, which is applicable to both phases, and show using extensive simulations that it performs close to the heuristic.

We address the energy-efficient data redistribution problem in data-intensive sensor networks (DISNs). In a DISN, a large volume of data gets generated, which is first stored in the network and is later collected for further analysis when the next uploading opportunity arises. The key concern in DISNs is to be able to redistribute the data from data-generating nodes into the network under limited storage and energy constraints at the sensor nodes. We formulate the data redistribution problem where the objective is to minimize the total energy consumption during this process while guaranteeing full utilization of the distributed storage capacity in the DISNs. We show that the problem is APX-hard for arbitrary data sizes; therefore, a polynomial time approximation algorithm is unlikely. For unit data sizes, we show that the problem is equivalent to the minimum cost flow problem, which can be solved optimally. However, the optimal solution's centralized nature makes it unsuitable for large-scale distributed sensor networks. Thus, we design a distributed algorithm for the data redistribution problem which performs very close to the optimal, and compare its performance with various intuitive heuristics. The distributed algorithm relies on potential function-based computations, incurs limited message and computational overhead at both the sensor nodes and data generator nodes, and is easily implementable in a distributed manner. We analytically study the convergence and performance of the proposed algorithm and demonstrate its near-optimal performance and scalability under various network scenarios. In addition, we implement the distributed algorithm in TinyOS, evaluate it using TOSSIM simulator, and show that it outperforms EnviroStore, the only existing scheme for data redistribution in sensor networks, in both solution quality and message overhead. Finally, we extend the proposed algorithm to avoid disproportionate energy consumption at different sensor nodes without compromising the solution quality.

Energy harvesting and cooperative communication are promising solutions to overcome the power limitations of Wireless Sensor Networks (WSNs) comprising of battery-powered nodes. In order to maximize the efficiency of such systems, measured in terms of packet delivery ratio achieved over time, efficient scheduling algorithms need to be designed. In particular, relay usage scheduling is critical for addressing the trade-off between energy consumption and efficiency in the network. However, the stochastic nature of the recharge and traffic generation processes at the sensor nodes, along with partial state information availability about neighboring nodes, makes the transmission and relay scheduling problem quite challenging. To address this problem, we model the system using a stochastic framework, and formulate the scheduling problem at source sensor node, when only partial state information about the relay is available at the source, as a Partially Observable Markov Decision Process (POMDP). We characterize an approximate solution to the optimality equations, which provides us with useful insights into the system dynamics. We observe that the structure of optimal policy is quite sensitive to system parameters, which makes it unsuitable for practical deployment. Therefore, we design a simple and practical threshold based relay scheduling policy, and show using simulations that it achieves close to optimal performance.

We address the issue of misbehavior detection and reaction in IEEE 802.11 based Ad Hoc networks. Selfish misbehavior involves disobeying standard protocol mechanisms to gain unfair access to the channel at the expense of other users. We outline conditions on genuine (non-misbehaving) node's throughput to guarantee the presence of misbehavior, and propose non-adaptive and strong reaction mechanism for such aggressive misbehaviors. For selfish misbehaviors which do not result in severe throughput degradation for genuine users, we design an adaptive reaction mechanism. Both mechanisms are distributed in nature, rely only upon local information available at genuine nodes, and are thus easily implementable in practice. Proposed reaction mechanisms provide the necessary disincentive towards selfish misbehavior, and are aimed at preventing misbehavior.

This paper considers wireless sensor networks (WSNs) with energy harvesting and cooperative communications and develops energy efficient scheduling strategies for such networks. In order to maximize the long-term utility of the network, the scheduling problem considered in this paper addresses the following question: given an estimate of the current network state, should a source transmit its data directly to the destination or use a relay to help with the transmission? We first develop an upper bound on the performance of any arbitrary scheduler. Next, the optimal scheduling problem is formulated and solved as a Markov Decision Process (MDP), assuming that complete state information about the relays is available at the source nodes. We then relax the assumption of the availability of full state information, and formulate the scheduling problem as a Partially Observable Markov Decision Process (POMDP) and show that it can be decomposed into an equivalent MDP problem. Simulation results are used to show the performance of the schedulers.

Sensors equipped with energy harvesting and cooperative communication capabilities are a viable solution to the power limitations of Wireless Sensor Networks (WSNs) associated with current battery technology. However, the optimal scheduling of transmissions in such networks is challenging due to the requirement of complete state information of the relay nodes. This paper addresses the problem of transmission scheduling in such networks when onlypartialstate information about the relays is available at the source. We formulate the scheduling problem as a Partially Observable Markov Decision Process (POMDP), and show that it can be decomposed into an equivalent Markov Decision Process (MDP) problem. Simulation results are used to show the performance of the scheduler.

We address the energy-efficient data redistribution problem in data intensive sensor networks (DISNs). The key question in sensor networks with large volumes of sensory data is how to redistribute the data efficiently under limited storage and energy constraints at the sensor nodes. The goal of the redistribution scheme is to minimize the energy consumption during the process, while guaranteeing full utilization of the distributed storage capacity in the DISNs. We formulate this problem as a minimum cost flow problem, which can be solved optimally. However, the optimal solution's centralized nature makes it unsuitable for large-scale distributed sensor networks. We thus design a distributed algorithm for the data redistribution problem which performs very close to the optimal, and compare its performance with various intuitive heuristics. Our proposed algorithm relies on potential function based computations, incurs limited message and computational overhead at both the sensor nodes and data generator nodes, and is easily implementable in a distributed manner. We analytically show the convergence of our algorithm, and demonstrate its near-optimal performance and scalability under various network scenarios considered. Finally, we implement our distributed algorithm in TinyOS and evaluate it using TOSSIM simulator, and show that it outperforms EnviroStore, the only existing scheme for data redistribution in sensor networks, in both solution quality and overhead messages.

Sensor networks have major applications in environmental monitoring, relief operations, surveillance, health-care and defense. Future sensor networks would comprise of sensing devices with energy harvesting capabilities from renewable energy sources such as solar power. Multiple sensor nodes deployed in the region of interest would collaborate to achieve a global objective, such as detection of application specific events. This paper focuses on the design of efficient algorithms for multi-sensor activation in order to optimize the overall event detection probability. The recharge-discharge dynamics of the individual rechargeable sensor nodes, along with temporally correlated nature of event occurrences makes the optimal multi-sensor event detection question very challenging. We formulate the dynamic multi-sensor event detection question in a stochastic optimization framework, and design efficient sensor activation algorithms. Particularly, we analyze certain classes of threshold activation policies and show that they achieve near-optimal performance when the threshold is chosen carefully. Specifically, we show that a time-invariant threshold policy, which attempts to maintain a fixed number (appropriately chosen) of sensors active at all times, is optimal in absence of temporal correlations. Moreover, the same energy-balancing time-invariant threshold policy approaches optimality in presence of temporal correlations as well, albeit under certain limiting assumptions. Through simulation studies, we compare the performance of this time-invariant policy with energy-balancing correlation-dependent policies, and observe that although the latter perform better, the performance difference is rather small.

We address the problem of optimal node activation in a sensor network, where the optimization objective is represented as a global time-average utility function over the deployment area of the network. Each sensor node is rechargeable, and can hold up toKquanta of energy. When the recharge and/or discharge processes in the network are random, the problem of optimal sensor activation is a complex stochastic decision question. For the case of identical sensor coverages, we show the existence of a simplethreshold policywhich isasymptotically optimalwith respect to the energy bucket sizeK, that is, the performance of this threshold policy approaches the optimal performance asKbecomes large. We also show that the performance of the optimal threshold policy is robust to the degree of spatial correlation in the discharge and/or recharge processes. We then extend this approach to a general sensor network where coverage areas of different sensors could have complete, partial or no overlap with each other. We demonstrate through simulations that a local information based threshold policy, with an appropriately chosen threshold, achieves a performance which is very close to the global optimum.

We consider a system of rechargeable sensor nodes deployed redundantly in the region of interest. Active sensor nodes are subject to a discharge process which depends on the occurrence of events in the system. All sensor nodes experience a continuous recharge of their battery energies, however at a considerably lower rate than of discharge. The decision problem is to find the optimal activation policy for the sensor nodes which would maximize the aggregate system utility. We model our rechargeable sensor system as a system of finite-buffer queues and show the existence of a simple threshold activation policy that achieves near optimal performance. Our results hold both in presence as well as absence of correlation in the discharge and/or recharge processes, thereby showing the robustness of such policies with respect to the degree of correlation in the system.

We consider a network of rechargeable sensors, deployed redundantly in a random sensing environment, and address the problem of how sensor nodes should be activated dynamically so as to maximize a generalized system performance objective. The optimal sensor activation problem is a very difficult decision question, and under Markovian assumptions on the sensor discharge/recharge periods, it represents a complex semi-Markov decision problem. With the goal of developing a practical, distributed but efficient solution to this complex, global optimization problem, we first consider the activation question for a set of sensor nodes whose coverage areas overlap completely. For this scenario, we show analytically that there exists a simple threshold activation policy that achieves a performance within a factor of 3/4 of the optimum over all possible policies. We extend this threshold policy to a general network setting where the coverage areas of different sensors could have partial or no overlap with each other, and show by simulations that the performance of our policy is very close to that of the globally optimal policy. Our policy is fully distributed, and requires the sensor nodes to only keep track of the node activation states in its immediate neighborhood. We also consider the effects of spatial correlation on the performance of the threshold activation policy, and the choice of the optimal threshold.