Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach

In geographic (or geometric) routing, messages are by default routed in a greedy manner: The current node always forwards a message to its neighbor node that is closest to the destination. Despite its simplicity and general efficiency, this strategy alone does not guarantee delivery due to the exist...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2012-06, Vol.20 (3), p.864-877
Main Authors: Guang Tan, Kermarrec, A-M
Format: Article
Language:English
Subjects:
Ad hoc networks
Algorithm design and analysis
Approximation
Bars
Computer networks
Computer Science
Decomposition
geographic routing
greedy
Junctions
Messages
Minima
Networking and Internet Architecture
Networks
Routing
Routing (telecommunications)
Routing protocols
Strategy
Studies
wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In geographic (or geometric) routing, messages are by default routed in a greedy manner: The current node always forwards a message to its neighbor node that is closest to the destination. Despite its simplicity and general efficiency, this strategy alone does not guarantee delivery due to the existence of local minima (or dead ends). Overcoming local minima requires nodes to maintain extra nonlocal state or to use auxiliary mechanisms. We study how to facilitate greedy forwarding by using a minimum amount of such nonlocal states in topologically complex networks. Specifically, we investigate the problem of decomposing a given network into a minimum number of greedily routable components (GRCs), where greedy routing is guaranteed to work. We approach it by considering an approximate version of the problem in a continuous domain, with a central concept called the greedily routable region (GRR). A full characterization of GRR is given concerning its geometric properties and routing capability. We then develop simple approximate algorithms for the problem. These results lead to a practical routing protocol that has a routing stretch below 7 in a continuous domain, and close to 1 in several realistic network settings.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2011.2167758