A scalable quorum-based location service in ad hoc and sensor networks

Ivan Stojmenović, Dandan Liu, Xiaohua JiaInternational Journal of Communication Networks and Distributed Systems 2008 · DOI

TL;DR

This paper introduces a novel quorum-based location service for mobile ad hoc and sensor networks that significantly reduces communication overhead compared to traditional flooding-based methods. By using a grid-like structure of "columns" for updates and "rows" for searches, it achieves an efficient O(√n) overhead per task and demonstrates high success rates and scalability in simulations.

What Problem Does This Paper Address?

In mobile ad hoc networks (MANETs) and wireless sensor networks, nodes are constantly moving, making it challenging to maintain up-to-date location information for efficient communication. Existing location services often suffer from high communication overhead due to partial flooding of the network, and can fail in scenarios with group mobility. This paper aims to address these issues by proposing a scalable and energy-efficient location service that can handle node mobility and reduce communication costs.

Methods

The core of the proposed solution is a quorum-based location service. The fundamental idea is to divide the network conceptually into a grid. When a node needs to update its location, it registers this information along a "column" (north-south direction). When a source node needs to find a destination, it queries along a "row" (east-west direction). The location of the destination is found at the intersection of these update and search quorums.

Key aspects of their method include:

  • O(√n) Overhead: The authors claim that the overhead for each location update and search task is reduced to O(√n), where 'n' is the total number of nodes in the network. This is a significant improvement over flooding-based approaches.
  • Localized Approach: The system relies on localized information, meaning nodes make decisions based on their own location and their neighbors', avoiding the need for global network knowledge.
  • Face Routing for Guarantee: To ensure successful location retrieval, especially in dynamic environments, they extend their quorum system with "face routing." This technique, based on the Gabriel Graph, traverses the outer boundary of the network to guarantee that update and search quorums intersect, even with node movement.
  • Update Triggering: Location updates are triggered by changes in link existence (edges being broken or created) or when a node detects a new neighbor. This is further refined by using a counter for link changes to avoid excessive updates.
  • Four Strategies: The paper proposes four variants of the quorum system, differing in how columns and rows are constructed and whether face routing is used, to balance communication overhead and success rates.

Datasets

Not discussed in the paper. The authors rely on simulations using a unit disk graph model.

Key Insights and Ideas

  • Grid-based Quorums for Efficiency: The core insight is that by structuring location updates and searches into orthogonal "columns" and "rows," the system can efficiently pinpoint a node's location without flooding the entire network.
  • Face Routing as a Robustness Mechanism: The integration of face routing to traverse the network's outer boundary is a clever way to guarantee quorum intersection and thus successful location retrieval, even when nodes are moving unpredictably.
  • Adaptability to Group Mobility: The relative nature of the "columns" and "rows" makes the system well-suited for scenarios where entire groups of nodes move together, minimizing the need for frequent individual updates.
  • Trade-offs in Quorum Design: The exploration of different quorum strategies highlights that there's no single "best" approach; designers must balance communication overhead against the probability of successful location discovery.

Key Results

The paper presents simulation results demonstrating the effectiveness of their proposed quorum-based location service.

  • High Success Rate: The proposed methods, particularly those incorporating face routing (CF+RF and CF+RF(N)), achieve high success rates in locating destinations.
  • Good Scalability: The success rate remains high as the number of nodes (N) increases, indicating good scalability.
  • Reduced Communication Overhead: Compared to strategies that involve extensive face routing (CF+RF), simpler strategies (C+R, CR+CR) show lower update message counts, especially as node degree increases. However, strategies with face routing (CF+RF, CF+RF(N)) are shown to guarantee delivery.
  • Impact of Node Degree and Network Size: Simulations show that success rates generally increase with node degree and decrease with network size for some strategies. Communication overhead for CF+RF and CF+RF(N) decreases with node degree but increases with network size.

Limitations and Future Work

  • Idealized Network Model: The simulations are conducted using a unit disk graph model, which assumes no obstacles and a uniform transmission radius. Real-world networks may have varying transmission ranges and obstacles.
  • Static Network Assumption for Initial Verification: While the methods are designed for mobility, initial effectiveness was verified in static networks.
  • Potential for High Overhead with Face Routing: While face routing guarantees success, it can increase communication overhead, especially in dense networks or when nodes are on the outer perimeter.
  • Future Work Suggestions:
    • Investigating hierarchical quorum-based protocols to further reduce overhead when source and destination are close.
  • Developing more sophisticated mechanisms for handling node mobility and maintaining quorum integrity.
  • Exploring alternative strategies for extending quorums beyond simple north-south and east-west directions.
  • Comparing the proposed methods with other existing schemes using a common simulator and appropriate medium access layer.

Summary updated

Abstract

Location service provides position of mobile destination to source node so that position-based routing can be applied. Previous location service protocols suffer from partial flooding overhead, and/or location failure in group movement scenarios. To overcome those deficiencies, we propose a quorum-based location service. The basic idea is that destination node registers its location along a 'column' to form an update quorum. Source node makes a query along a 'row' to form a search quorum. The destination location is detected at the intersection between the update and search quorums. The overhead of each routing task, including location service, is O(√n), where n is the number of nodes in the network. Four strategies are proposed to adjust the quorum system and improve it's performance. To guarantee the success of location retrieval, both search and update quorums are extended by face routing which traverses outer boundary of the network. The simulation results show that our proposed location service has high success rate and good scalability.
BibTeX
@article{stojmenovic2008scalable,
  author = {Ivan Stojmenović and Dandan Liu and Xiaohua Jia},
  title = {{A scalable quorum-based location service in ad hoc and sensor networks}},
  journal = {International Journal of Communication Networks and Distributed Systems},
  year = {2008},
  doi = {10.1504/ijcnds.2008.017205},
}
Figure