Distributed Flooding-based Storage Algorithms for Large-scale Sensor Networks

Salah A. Aly, Hager S. Darwish, Moustafa Youssef, Mahmoud ZidanarXiv 2009 · OpenReview

TL;DR

This paper introduces two novel distributed storage algorithms (DSA-I and DSA-II) for large-scale wireless sensor networks. These algorithms use network flooding to efficiently disseminate and store sensed data, even when nodes are unreliable, and require querying only a fraction of the network to retrieve information.

What Problem Does This Paper Address?

Wireless sensor networks (WSNs) are deployed in vast, often inaccessible areas to monitor environmental conditions. These networks consist of numerous small, resource-constrained nodes (limited power, memory, bandwidth) that are prone to failure or battery depletion. A critical challenge is efficiently collecting the valuable data sensed by these nodes before they disappear. Traditional methods often rely on knowing the network's topology or the total number of nodes, which is impractical in dynamic WSNs. This paper tackles the problem of designing distributed storage algorithms that can reliably collect data from a large number of potentially unreliable sensor nodes without requiring prior knowledge of the network's global state.

Methods

The authors propose two distributed storage algorithms (DSAs):

  • DSA-I: This algorithm assumes that each node knows the total number of nodes ($n$) in the network. It utilizes network flooding to disseminate data. Each node prepares a packet containing its ID, sensed data, a hop count, and a flag. The hop count is inversely proportional to the node's degree, meaning nodes with fewer connections have a higher hop count to ensure wider dissemination. Nodes accept data with a certain probability and store it in their buffers.
  • DSA-II: This algorithm is designed for scenarios where the total number of nodes ($n$) is unknown. It introduces an "inference phase" where each node dynamically estimates its hop count based on its own degree and the degrees of its neighbors. This allows for a distributed approach that doesn't rely on global information.

Both algorithms leverage the concept of flooding for initial data dissemination and then employ strategies to ensure data persistence and recoverability. They also introduce a mechanism for data updates by XORing new data with old data.

Datasets

Not discussed in the paper. The evaluation is based on simulations of wireless sensor networks with varying numbers of nodes and network sizes.

Key Insights and Ideas

  • Decentralized Data Collection: The core innovation is enabling data collection in large-scale, dynamic WSNs without centralized control or global knowledge.
  • Flooding with Smart Counters: DSA-I's use of hop counts inversely proportional to node degree is a clever way to balance dissemination speed and coverage. Nodes with fewer connections are incentivized to "shout louder" to reach more nodes.
  • Adaptability to Unknown Network Size: DSA-II's inference phase is crucial for real-world WSNs where node counts can fluctuate. This makes the algorithm more robust and practical.
  • Efficient Data Retrieval: A significant advantage highlighted is the ability to retrieve all sensed data by querying only a small fraction (20-30%) of the network nodes, which is a substantial improvement over prior methods.
  • Data Updates Handled: The proposed mechanism for handling data updates using XOR operations is efficient and fits well within the distributed storage framework.

Key Results

The paper demonstrates through analysis and simulation that:

  • DSA-I: Achieves efficient encoding and decoding operations. The number of transmissions required to disseminate information is $O(n^2)$, and the number of steps for a packet is $O(n/\mu)$, where $\mu$ is the mean degree.
  • DSA-II: Provides a distributed storage solution that does not depend on knowing the total number of nodes. The encoding operations take $O(C\mu^2)$.
  • Query Efficiency: Both algorithms show that successful decoding probability increases with the decoding ratio (percentage of queried nodes). Crucially, they achieve high decoding probabilities by querying only about 20-30% of the total nodes.
  • Scalability: Simulations with up to 600 nodes show that the algorithms perform well for large-scale WSNs, with decoding ratios approaching 1 for certain thresholds.

Limitations and Future Work

  • Practical Implementation: The authors acknowledge that their future work will include practical and implementation aspects of these algorithms.
  • Buffer Size Impact: While the paper mentions buffer size ($M$) and slot size ($c$), a deeper analysis of how buffer constraints specifically impact performance and the required decoding ratio could be explored further.
  • Node Failure Models: The algorithms assume nodes might disappear due to failures or battery depletion. More sophisticated failure models (e.g., correlated failures) could be investigated.
  • Energy Efficiency: While the algorithms aim for efficiency, a detailed analysis of the energy consumption of flooding and packet handling in large-scale networks would be valuable.

Summary updated

Abstract

In this paper we propose distributed flooding-based storage algorithms for large-scale wireless sensor networks. Assume a wireless sensor network with $n$ nodes that have limited power, memory, and bandwidth. Each node is capable of both sensing and storing data. Such sensor nodes might disappear from the network due to failures or battery depletion. Hence it is desired to design efficient schemes to collect data from these $n$ nodes. We propose two distributed storage algorithms (DSA's) that utilize network flooding to solve this problem. In the first algorithm, DSA-I, we assume that every node utilizes network flooding to disseminate its data throughout the network using a mixing time of approximately O(n). We show that this algorithm is efficient in terms of the encoding and decoding operations. In the second algorithm, DSA-II, we assume that the total number of nodes is not known to every sensor; hence dissemination of the data does not depend on $n$. The encoding operations in this case take $O(C\mu^2)$, where $\mu$ is the mean degree of the network graph and $C$ is a system parameter. We evaluate the performance of the proposed algorithms through analysis and simulation, and show that their performance matches the derived theoretical results.
BibTeX
@misc{aly2009distributed,
  author = {Salah A. Aly and Hager S. Darwish and Moustafa Youssef and Mahmoud Zidan},
  title = {{Distributed Flooding-based Storage Algorithms for Large-scale Sensor Networks}},
  year = {2009},
  eprint = {0908.4419},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0908.4419},
}
Figure