Spiral-based data dissemination in sensor networks

Yang Sun, Guangbin Fan, Shigang ChenInt. J. Ad Hoc Ubiquitous Comput 2007 · DOI

TL;DR

This paper introduces Logarithmic Spiral Data Dissemination (LSDD), a novel approach for efficient and scalable data dissemination in wireless sensor networks (WSNs). By having data advertisements and queries follow spiral paths, LSDD significantly reduces communication overhead and energy consumption compared to traditional flooding-based methods, making it well-suited for large-scale WSN deployments.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are composed of numerous small, resource-constrained nodes that collect and transmit data. A critical challenge in WSNs is data dissemination: efficiently spreading information about detected events or user queries across the network. Traditional methods like flooding, where messages are broadcast to all neighbors, lead to high energy consumption, network congestion, and reduced network lifetime, especially in large networks. While some schemes aim to optimize this, they often rely on global network knowledge or complex routing, which is impractical for ad-hoc WSNs. This paper addresses the need for an energy-efficient, scalable, and robust data dissemination scheme that works with local information and avoids the pitfalls of flooding.

Methods

The core of the proposed solution is the Logarithmic Spiral Data Dissemination (LSDD) scheme. Data advertisements are disseminated along a path that approximates a logarithmic spiral, originating from a source node. Conversely, sink nodes initiate queries that follow a reverse logarithmic spiral path. This spiral geometry is chosen for its versatility and simple parameterization.

Key algorithmic components include:

  • Spiral Path Search Algorithm (SPSA): Each sensor node uses SPSA to determine the next hop along the spiral path. This algorithm employs linear programming to balance moving along the intended spiral angle and minimizing the distance to the ideal spiral.
  • Reverse Spiral Search Algorithm (RSPSA): Used by sink nodes to guide queries along a reverse spiral path, ensuring it efficiently meets the dissemination spiral.
  • Parameterization: The spiral's shape is controlled by parameters like 'a' (initial radius) and 'b' (growth rate). Adjusting 'b' allows control over the blind area within the spiral and the coverage pattern.

The scheme is designed to be localized, meaning nodes only need information about their immediate neighbors and pre-defined spiral parameters.

Datasets

Not discussed in the paper. The authors conducted extensive simulations using MATLAB to evaluate their proposed scheme.

Key Insights and Ideas

  • Spiral Geometry for Efficiency: The paper ingeniously leverages the mathematical properties of logarithmic spirals to create efficient data paths. Instead of spreading messages everywhere, LSDD guides them along a focused, expanding path.
  • Localized Decision Making: LSDD avoids the need for global network maps. Nodes make routing decisions based on local neighborhood information and pre-set spiral parameters, making it practical for dynamic WSNs.
  • Trade-off Management: LSDD explicitly manages the trade-off between dissemination speed (delay) and energy efficiency/scalability. It prioritizes the latter, accepting a potentially longer delay for significant gains in energy savings and network lifetime.
  • Scalability through Path Control: By controlling the spiral's growth, LSDD can effectively cover large areas with a fraction of the nodes required by flooding, demonstrating superior scalability.
  • Robustness to Node Failures: The spiral path naturally adapts to some node failures, maintaining a high success rate for data dissemination even with a significant percentage of node failures.

Key Results

  • Lower Dissemination Cost: LSDD's dissemination cost is shown to be O(√n) compared to O(n) for flooding-based schemes, where 'n' is the number of nodes.
  • Improved Scalability: Simulations demonstrate that LSDD's search cost increases linearly with distance, while flooding-based methods increase exponentially. LSDD also scales better with multiple sink nodes.
  • Energy Efficiency: LSDD achieves higher energy efficiency, covering larger areas with the same amount of energy compared to SIDD and GBDD.
  • Fault Tolerance: LSDD exhibits good fault tolerance, maintaining a high dissemination success rate (over 90%) even with 10% node failures.
  • Delay Trade-off: While LSDD offers significant advantages, it incurs a relatively longer delay compared to flooding-based schemes, which is acknowledged as a trade-off for its efficiency and robustness.

Limitations and Future Work

  • Time-Urgent Applications: LSDD is not ideal for time-urgent applications due to its inherent delay.
  • Parameter Optimization: The paper mentions that optimizing spiral parameters (a and b) for specific network conditions is a topic for future research.
  • Mobility: The current study assumes static network topology. The authors suggest that handling sensor node mobility is a direction for future work.
  • Blind Area: While controllable by parameters, a blind area within the spiral path exists. The paper suggests that incrementing the starting angle (θ₀) in successive disseminations can help sweep the entire coverage area over time.

Summary updated

BibTeX
@article{sun2007spiral,
  author = {Yang Sun and Guangbin Fan and Shigang Chen},
  title = {{Spiral-based data dissemination in sensor networks}},
  journal = {Int. J. Ad Hoc Ubiquitous Comput.},
  year = {2007},
  doi = {10.1504/ijahuc.2007.011603},
}
Figure