Handling Neighbor Discovery and Rendezvous Consistency with Weighted Quorum-Based Approach

Chung-Ming Own, Zhaopeng Meng, Kehan Liu2015 · DOI

TL;DR

This paper introduces a Weighted Quorum System (WQS) to improve energy efficiency and neighbor discovery in wireless sensor networks (WSNs). By intelligently scheduling active time slots and considering node energy levels, WQS significantly reduces redundant communication and extends network lifetime compared to existing methods.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are crucial for various applications but are severely limited by their power sources. Efficient power management is paramount to extending network lifetime. A key challenge is "neighbor discovery" and "rendezvous," where nodes need to wake up periodically to communicate with their neighbors. Existing solutions often fall into two categories: quorum-based and co-primality based protocols. While effective, these methods can be energy-intensive due to clock synchronization requirements or inefficient slot utilization. Asynchronous wakeup mechanisms, while avoiding strict synchronization, often require nodes to wake up more frequently, leading to higher energy consumption. This paper addresses the need for a more energy-efficient and robust approach to neighbor discovery and rendezvous maintenance, especially in dynamic environments with mobile nodes.

Methods

The paper proposes a Weighted Quorum System (WQS). This approach builds upon the concept of quorum graphs, which represent active time slots for nodes. The core innovation lies in:

  • Weighted Decision Factor: A decision factor, $f(x_i) = (1 - \alpha)b_{x_i} + \alpha a_{x_i}$, is introduced for each vertex (active slot). This factor balances two key considerations:
  • $b_{x_i}$: The node's energy status (remaining power).
  • $a_{x_i}$: The accumulative wakeup factor, which is inversely proportional to the number of times a node has been referenced (i.e., more referenced nodes have a lower factor, indicating they are more "known").
  • $\alpha$: A system-defined parameter (set to 0.5 in experiments) that tunes the balance between energy status and reference rate.
  • Graph Reduction Algorithm: WQS employs a graph reduction algorithm to prune redundant connections in the quorum graph. It divides the graph and iteratively selects "bridging nodes" based on the weighted decision factor, aiming to maximize connections while minimizing active slots.
  • Indirect Reachability: Similar to the Extended Quorum System (EQS), WQS leverages indirect reachability, allowing nodes to discover neighbors through intermediate nodes, thus reducing the need for direct pairwise connections.

Datasets

Not discussed in the paper. The evaluation is based on simulations.

Key Insights and Ideas

  • Balancing Energy and Connectivity is Key: The paper highlights that simply maximizing connections or minimizing active slots isn't enough. A nuanced approach that considers both the node's remaining energy and how "known" it is by others is crucial for long-term network health.
  • Intelligent Pruning of Redundancy: By using a weighted decision factor and a graph reduction approach, WQS effectively eliminates unnecessary active slots, directly translating to energy savings.
  • Adaptability to Mobile Environments: The WQS method is designed to be more flexible in mobile environments, allowing for easier reconfiguration when nodes join or leave the network, a significant advantage over static scheduling.
  • The Role of $\alpha$: The parameter $\alpha$ offers a tunable knob to prioritize energy conservation versus reference rate based on network conditions (e.g., density).

Key Results

  • Superior Energy Efficiency: WQS demonstrates significantly better energy conservation compared to DISCO and EQS. The average duty cycle time was reduced by 8.88% compared to EQS and 58.28% compared to DISCO.
  • Improved Network Lifetime: Figure 9 shows that WQS achieves a higher "loop index" (a measure of how long the network can operate before energy exhaustion), indicating a longer network lifetime. Specifically, WQS achieved 69.94% more loop index times than EQS and 78.39% more than DISCO.
  • Fast Reconfiguration: In dynamic network scenarios, WQS (along with DISCO) can reschedule active slots for newly joining nodes very quickly, with system time effectively equal to zero, whereas EQS requires a more extensive reconfiguration.
  • Optimal $\alpha$ Value: Experiments suggest that $\alpha = 0.5$ provides an optimal balance for maintaining network execution time across various densities.

Limitations and Future Work

  • Mobile Environment Complexity: While WQS is designed for mobile environments, the paper notes that the extended quorum graph doesn't completely support them, especially concerning flexible network design and device energy considerations. The paper implies that further work might be needed to fully address these aspects.
  • Parameter Tuning: The optimal value of $\alpha$ might vary depending on specific network conditions and application requirements, suggesting that adaptive or dynamic tuning of this parameter could be a future research direction.
  • Real-world Deployment: The evaluation is based on simulations. Future work could involve testing WQS on actual hardware in real-world WSN deployments to validate its performance under practical constraints.

Summary updated

BibTeX
@misc{own2015handling,
  author = {Chung-Ming Own and Zhaopeng Meng and Kehan Liu},
  title = {{Handling Neighbor Discovery and Rendezvous Consistency with Weighted Quorum-Based Approach}},
  year = {2015},
  doi = {10.3390/s150922364},
}
Figure