An adaptive mesh-based protocol for geocast routing

Tracy Camp, Yu LiuJournal of Parallel and Distributed Computing 2003 · DOI

TL;DR

This paper introduces GAMER, an adaptive geocast routing protocol for mobile ad hoc networks (MANETs). GAMER dynamically adjusts its mesh density to optimize packet delivery and network load, outperforming non-adaptive approaches in terms of accuracy without significantly increasing overhead.

What Problem Does This Paper Address?

Mobile ad hoc networks (MANETs) are self-configuring networks of mobile devices that can operate without a fixed infrastructure. These networks are crucial for scenarios like emergency response or military operations. A key challenge in MANETs is efficient routing, especially for group communication. While multicast delivers data to a group of nodes, geocasting narrows this down to nodes within a specific geographical area. Existing geocast protocols often struggle with the dynamic nature of MANETs, where nodes frequently move, leading to network partitioning and packet loss. This paper addresses the need for a geocast routing protocol that can adapt to varying mobility patterns and network conditions to maintain reliable communication.

Methods

GAMER employs a combination of established techniques and novel adaptations:

  • Source Routing: Similar to the Dynamic Source Routing (DSR) protocol, each packet carries its full route, reducing the need for intermediate nodes to maintain routing tables.
  • Forwarding Zones: Inspired by protocols like LAR and DREAM, GAMER uses forwarding zones to limit the scope of packet flooding, preventing unnecessary network-wide broadcasts. It defines three types of forwarding zones:
  • CONE FA: The most restrictive, creating a sparse mesh.
  • CORRIDOR FA: A rectangular zone, creating a denser mesh than CONE.
  • FLOOD FA: Floods packets across the entire network, creating the densest mesh.
  • Mesh-Based Routing: Like ODMRP and CAMP, GAMER uses a mesh structure to provide multiple paths between the source and the geocast region, enhancing robustness against node failures or link breakages.
  • Adaptive Forwarding Approach (FA) Selection: This is GAMER's core innovation. The protocol dynamically selects the most appropriate forwarding zone (CONE, CORRIDOR, or FLOOD) based on the current network environment. It starts with the most restrictive (CONE) and expands to CORRIDOR or FLOOD if mesh creation fails within a timeout. This adaptation aims to balance transmission accuracy and network overhead.
  • Two Versions:
    • Passive GAMER: Uses a fixed interval for sending JOIN-DEMAND (JD) packets to build the mesh.
  • Active GAMER: Combines a fixed interval with a dynamic mechanism. If a JD packet fails to establish a mesh connection, it immediately sends another JD packet, potentially with a larger forwarding zone, making it more proactive in adapting.

Datasets

Not discussed in the paper. The authors used a custom simulation environment within the ns-2 simulator.

Key Insights and Ideas

  • Adaptation is Key: The paper strongly suggests that adapting the routing strategy (specifically, the forwarding zone size and mesh density) to the network's mobility is crucial for efficient geocasting in MANETs.
  • Trade-offs in Mesh Density: Denser meshes (from larger forwarding zones like FLOOD) offer higher transmission accuracy but at the cost of increased network overhead. Conversely, sparser meshes (from smaller zones like CONE) reduce overhead but can lead to lower accuracy, especially in highly mobile environments.
  • Active vs. Passive Adaptation: The "Active GAMER" approach, which more aggressively attempts to expand the forwarding zone upon failure, demonstrates superior performance in terms of data packet delivery ratio, especially at higher mobility speeds, though it incurs slightly higher overhead.
  • Mesh Formation Efficiency: The protocol's strategy of starting with the smallest forwarding zone (CONE) and expanding only when necessary is effective, as evidenced by the high percentage of successful mesh formations using CONE and CORRIDOR FAs.

Key Results

  • Improved Data Packet Delivery Ratio: Both Active and Passive GAMER significantly improve data packet delivery ratio compared to non-adaptive FLOOD, CORRIDOR, and CONE FAs, especially at higher mobility speeds. Active GAMER consistently provides the best delivery ratio.
  • Reduced End-to-End Delay: The CONE FA, due to its sparser mesh and fewer hops, exhibits the lowest end-to-end delay. However, its accuracy is lower.
  • Controlled Overhead: While Active GAMER shows higher control overhead than Passive GAMER and CORRIDOR FA, it is significantly lower than the FLOOD FA. The paper argues that the accuracy gains justify this overhead.
  • Adaptive Behavior: Figures 13-16 show that as mobility speed increases, GAMER (both versions) relies more on larger forwarding zones (CORRIDOR and FLOOD) and less on the CONE FA, demonstrating its adaptive nature. Active GAMER switches to larger zones more quickly than Passive GAMER.

Limitations and Future Work

  • Simulation-Based: The results are based on simulations using ns-2, and real-world testing would be valuable.
  • Semi-Tough Environment: The authors note that their simulation environment is "semi-tough," implying that real-world MANETs might present even greater challenges.
  • Future Work:
    • Evaluate other GAMER versions that adapt based on different network features (e.g., source-to-region location).
  • Incorporate features to prioritize more efficient paths within the mesh.
  • Implement local repair mechanisms for failed paths.
  • Investigate a hybrid approach combining Passive GAMER for low speeds and Active GAMER for high speeds.
  • Compare GAMER's performance with other geocast routing protocols through simulation.

Summary updated

BibTeX
@article{camp2003adaptive,
  author = {Tracy Camp and Yu Liu},
  title = {{An adaptive mesh-based protocol for geocast routing}},
  journal = {Journal of Parallel and Distributed Computing},
  year = {2003},
  doi = {10.1016/s0743-7315(02)00064-3},
}
Figure