TL;DR
This paper introduces the "Trap Array" (TA) topology model, a novel benchmark designed to rigorously evaluate the worst-case performance of geometric routing algorithms in wireless networks. By creating a unified framework, the authors uncover significant scalability limitations in existing geo-routing methods and propose "Compact Geometric Routing" (CGR), a hybrid algorithm that combines the strengths of geometric and compact routing to achieve better stretch and state trade-offs.
What Problem Does This Paper Address?
Scalable routing in wireless networks is a critical challenge, balancing route stretch (path length vs. optimal) and per-node state (memory and traffic overhead). Two main approaches exist: compact routing (guarantees constant stretch with sub-linear state for general graphs) and geometric routing (geo-routing, leverages node positions for potentially better scalability in simple environments but can suffer in complex ones). While both have been studied, a direct, worst-case comparison has been difficult due to the lack of a standardized, challenging topology model for geo-routing. Existing benchmarks often use simple obstacle configurations that don't fully expose algorithms' limitations. This paper aims to bridge this gap by providing a unified theoretical framework to analyze geo-routing algorithms and to develop a new algorithm that leverages the benefits of both approaches.
Methods
The core contribution is the Trap Array (TA) topology model. This model constructs networks by arranging multiple "trap components" (e.g., linear segments or curves) connected by bridges. The key idea is to create configurations that repeatedly lead greedy routing algorithms into local minima, forcing them to take long detours and thus exposing their worst-case performance. The TA model is controllable via parameters like the number of trap components (K) and their connectivity, allowing for systematic stress-testing of algorithms.
Using this model, the authors derive theoretical lower bounds on stretch and state for ten representative geo-routing algorithms, including GPSR, GOAFR+, GDSTR, MDT, MAP, BVR, HopID, GEM, DRP, and CONVEX.
Based on these findings, they propose a new algorithm called Compact Geometric Routing (CGR). CGR employs a two-level hierarchy:
- L-clusters: Localized sub-networks designed to be "LM-free" (local-minimum-free) for greedy routing.
- H-clusters: Higher-level clusters formed based on network locality, inspired by compact routing.
CGR aims to combine the efficient greedy routing within L-clusters with the scalability of compact routing at the H-cluster level.
Datasets
The paper does not use traditional datasets. Instead, it introduces and utilizes the Trap Array (TA) topology model as a benchmark for evaluating routing algorithms. They also compare performance against results obtained using an obstacle model (common in prior work) and an obstacle+rand model (more realistic with non-uniform radio and randomized placement).
Key Insights and Ideas
- Geo-routing's hidden weaknesses: The TA model reveals that many geo-routing algorithms, despite good performance on simpler topologies, can exhibit polynomial stretch and state in more complex, albeit structured, scenarios, a stark contrast to the constant stretch guarantees of compact routing.
- The TA model as a powerful stress test: The model's ability to systematically create "traps" allows for a more rigorous and unified evaluation of algorithms' limiting behaviors, exposing vulnerabilities not apparent in simpler benchmarks.
- Hybrid approach is promising: The success of CGR demonstrates that combining geometric routing's local efficiency with compact routing's global structure can lead to algorithms that achieve both low stretch and low state, outperforming existing methods.
- Controllability of TA: The TA model's parameters (like K) provide a "control knob" to tune the complexity of the network and observe how algorithms' performance scales, which is crucial for theoretical analysis and practical understanding.
Key Results
- Theoretical Bounds: The paper derives non-trivial stretch and state lower bounds for ten geo-routing algorithms using the TA model. For instance, GPSR can exhibit $\Omega(N)$ stretch, and GOAFR+ can have $\Omega(N/K+K)$ stretch.
- CGR Performance:
- Stretch: CGR achieves an average stretch very close to 1 (e.g., < 1.07) and a maximum stretch below 4 in simulations, significantly outperforming other algorithms, especially in challenging TA topologies.
- State: CGR uses significantly less state than many algorithms, with an average state size of $O(\sqrt{K})$ in TA graphs and $O(\sqrt{N'})$ in general networks (where $N'$ is the number of L-clusters). It achieves up to an 85% reduction in state compared to algorithms with similar stretch performance (like S4 and DRP).
- TA Model Effectiveness: Simulations show the TA model generates a 10x wider range of stretch and a 4x wider range of state compared to obstacle models, highlighting its effectiveness in exposing algorithm limitations.
Limitations and Future Work
- TA Model Limitations: While powerful, the TA model is a specific construction. The paper notes that some algorithms (like NoGeo) may not perform well on TA graphs due to their specific structure (e.g., linear components). The analysis of MDT's state overhead shows it can be highest for small K, indicating that the TA model's trends aren't universally monotonic for all metrics across all algorithms.
- CGR Implementation: The paper mentions that CGR's performance is based on theoretical analysis and simulations. Future work includes implementing CGR on real systems to bridge the gap between theory and practice.
- Message Cost: CGR incurs a higher message cost during setup compared to localized algorithms, though this is deemed reasonable. Further investigation into message aggregation and optimization for CLDP probing is suggested.
- Dynamic Networks: The current analysis and CGR design primarily focus on static networks. Adapting these to dynamic environments with node mobility remains an open area.
Summary updated