Geographic routing with limited information in sensor networks

Sundar Subramanian, Sanjay ShakkottaiIEEE Trans. Information Theory 2010 · OpenReview

TL;DR

This paper investigates how sensor networks can efficiently route data even when nodes have imperfect or limited information about the destination's location. The authors demonstrate that routing delays remain asymptotically optimal (similar to perfect information scenarios) even with imprecise GPS or coarse location knowledge (like quadrants), and even if only a fraction of nodes possess this information. Furthermore, they show that "hotspots" caused by suboptimal routing paths don't degrade overall network throughput capacity.

What Problem Does This Paper Address?

Sensor networks, with their vast number of distributed nodes, rely on efficient routing to deliver data. Geographic routing, a popular approach, typically assumes nodes have precise knowledge of the destination's coordinates to make greedy forwarding decisions. This allows packets to travel directly towards the destination. However, in real-world scenarios, nodes might have inaccurate location data due to GPS errors, or they might only possess coarse information (e.g., knowing the destination is in a specific quadrant). Additionally, maintaining precise routing information across a massive network can be resource-intensive, leading to scenarios where only a fraction of nodes have this data. This paper addresses the critical question: how do these imperfections in location information affect routing efficiency, and can we still achieve near-optimal performance? It also explores the impact of "progressive" routing strategies, which prioritize moving closer to the destination but might not always take the shortest path, on network throughput.

Methods

The authors employ a theoretical analysis using a continuum model of a sensor network, where nodes are treated as points on a plane. They analyze routing delays by focusing on the "hitting time" – the time it takes for a packet to enter a small region around the destination.

Key methodological aspects include:

  • Asymptotic Analysis: The analysis focuses on the behavior of the network as the number of nodes ($n$) approaches infinity. This allows them to derive order-wise bounds on routing delays.
  • Probabilistic Modeling: They model location errors as random angular deviations in the intended direction of transmission. For coarse information, they consider routing to a random node within a specified quadrant or half-plane.
  • Bounds on Random Variables: They utilize techniques like Chernoff bounds and triangular array limit theorems to derive upper and lower bounds on the routing delay.
  • Continuum Model Validation: While the theoretical analysis uses a continuum model, the authors validate their findings with simulations on discrete node deployments, accounting for discretization effects.
  • Throughput Capacity Analysis: For throughput, they switch to a discrete node model and analyze "progressive" routing strategies, which guarantee a reduction in distance to the destination at each hop. They use graph coloring concepts to analyze scheduling and concurrent transmissions.

Datasets

Not discussed in the paper. The paper uses simulated networks for evaluation, not pre-existing datasets.

Key Insights and Ideas

  • Robustness to Imperfect GPS: Even with random angular errors in node positions (simulating imprecise GPS), routing delays are asymptotically equivalent to those with perfect information. This suggests that geographic routing is surprisingly resilient to moderate location inaccuracies.
  • Value of Coarse Information: Knowing only the quadrant or half-plane of the destination is sufficient to achieve near-optimal routing delays. This is a significant finding, as acquiring precise coordinates can be challenging.
  • Fractional Information is Sufficient: If even a fixed fraction of nodes possess routing information (e.g., quadrant data), the network can still achieve routing delays within a constant factor of the optimal. This implies that not every node needs to be "smart" for the network to perform well.
  • Hotspots Don't Kill Throughput: Progressive routing strategies, which might lead to "hotspots" (areas where many data flows converge), do not reduce the overall network throughput capacity in an order-wise sense. This is a crucial result for designing scalable sensor networks.

Key Results

  • Routing Delay Bounds: For scenarios with imprecise GPS (angular error) or quadrant information, the routing delay is shown to be $\Theta(1/M(n))$ (where $M(n)$ is the transmission range), which is asymptotically the same as with perfect information.
  • Fractional Information Performance: With a probability $p$ of a node having routing information, the delay is within a constant factor of the optimal, with the constant scaling as $1/p$.
  • Throughput Capacity: For progressive routing strategies, the throughput capacity is shown to be $O(n \log n)$, which is the same order as the maximum achievable throughput capacity for ideal routing.

Limitations and Future Work

  • Continuum Model Simplification: The theoretical analysis relies on a continuum model, which simplifies the problem by ignoring the discrete nature of nodes. While simulations validate the findings, real-world networks might exhibit more complex behaviors due to node placement.
  • Specific Error Models: The paper focuses on specific error models (e.g., random angular error). Other types of location errors or information limitations might yield different results.
  • Adversarial Quadrant Routing: While the paper shows that adversarial quadrant routing can be handled, the analysis for half-plane information in an adversarial scenario is noted as insufficient for order-wise straight-line routing delay.
  • Future Work: The authors suggest exploring the impact of other types of information limitations and error models. Further investigation into the trade-offs between information availability and routing performance could also be valuable. The paper also hints at the need for more detailed analysis of throughput capacity under various routing strategies.

Summary updated

Abstract

Geographic routing with greedy relaying strategies are important routing schemes in sensor networks. These schemes assume that the nodes have perfect information about the location of the destination. When the destination is unit distance away, the asymptotic routing delays are Θ(1/M(n)) , where M(n) is the maximum distance traveled in one hop (transmission range). We consider three scenarios where: i) nodes have location errors (imprecise GPS); ii) only coarse geographic information about the destination is available, e.g., the quadrant in which the destination is located; and iii) only a small fraction of the nodes have routing information. In this paper, we show that even with such limited destination-location information, the routing delays are Θ(1/ M(n)) , and validate our analysis with simulations. Finally, we consider the throughput-capacity of networks with progressive routing strategies that take packets closer to the destination in every step, but not necessarily along a straight-line. While such a routing strategy could lead to spatial “hotspots” due to the suboptimal flows nonuniformly loading the network, we show that the effect of hot spots due to progressive routing does not reduce the network throughput-capacity in an order sense, i.e., is order-wise the same as the maximum achievable throughput-capacity.
BibTeX
@article{subramanian2010geographic,
  author = {Sundar Subramanian and Sanjay Shakkottai},
  title = {{Geographic routing with limited information in sensor networks}},
  journal = {IEEE Trans. Information Theory},
  year = {2010},
  url = {https://openreview.net/forum?id=mosrV6c0FE},
}
Figure