Many emerging sensor network applications operate in challenging environments wherein the base station is unavailable. Data generated from such intermittently connected sensor networks (ICSNs) must be stored inside the network for some unpredictable time before uploading opportunities become available. Consequently, sensory data could overflow the limited storage capacity available in the entire network, making discarding valuable data inevitable. To overcome such overall storage overflow in ICSNs, we propose and study a new algorithmic framework calleddataaggregation foroverall storageoverflow ($\text {DAO}^{2}$). Utilizing spatial data correlation that commonly exists among sensory data,$\text {DAO}^{2}$employs data aggregation techniques to reduce the overflow data size while minimizing the total energy consumption in data aggregation. At the core of our framework are two new graph theoretical problems that have not been studied. We refer to them astravelingsalesmenplacementproblem ($\text {TSP}^{2}$) and quota traveling salesmen placement problem (Q-$\text {TSP}^{2}$). Different from the well-known multiple traveling salesman problem (mTSP) and its variants, which mainly focus on the routing of multiple salesmen initially located at fixed locations,$\text {TSP}^{2}$and Q-$\text {TSP}^{2}$must decide the placement as well as the routing of the traveling salesmen. We prove that both problems are NP-hard and design approximation, heuristic, and distributed algorithms. Our algorithms outperform the state-of-the-art data aggregation work with base stations by up to 71.8% in energy consumption.

We study overall storage overflow problem in sensor networks, wherein data-collecting base station is not available while more data is generated than available storage spaces in the entire network. Existing research designs a two-stage solution to solve this problem. It first aggregates overflow data to the size that can be accommodated by the available storage capacity in the network, and then offloads the aggregated data into the network to be stored. We refer to this naive two-stage solution as DAO-N. In this paper, we demonstrate that this approach does not necessarily achieve good performance. We propose a more unified method that is based upon data replication techniques, referred to as DAO-R, in order to improve the performance of DAO-N. Specifically, we design two energy-efficient data replication algorithms to integrate data aggregation and data offloading in DAO-N. We show via extensive simulations that DAO-R outperforms DAO-N by around 30% in terms of energy consumption under different network parameters.