Paper Info
Title
On Delivery Guarantees and Worst-Case Forwarding Bounds of Elementary Face Routing Components in Ad Hoc and Sensor Networks
Abstract
In this paper, we provide a thorough theoretical study on delivery guarantees, loop-free operation, and worst-case behavior of face and combined greedy-face routing. We show that under specific planar topology control schemes, recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary planar graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. We provide complete and formal proofs that several proposed face routing and combined greedy-face routing schemes guarantee message delivery in specific planar graph classes or even in arbitrary planar graphs. We also discuss the reasons why other methods fail to deliver a message or even end up in a loop. In addition, we investigate the behavior of face routing in arbitrary not necessarily planar networks and show, while delivery guarantees cannot be supported in such a general case, most face and combined greedy-face routing variants support at least loop-free operation. For those variants, we derive worst-case upper bounds on the number of forwarding steps.
Year
DOI
Venue
2010
10.1109/TC.2010.107
Computers, IEEE Transactions
Keywords
Field
DocType
ad hoc networks,failure analysis,graph theory,telecommunication congestion control,telecommunication network routing,telecommunication network topology,wireless sensor networks,ad hoc networks,arbitrary planar graphs,elementary face routing components,face selection mechanism,greedy routing failure,greedy-face routing,loop-free operation,message delivery guarantees,planar topology control schemes,sensor networks,worst-case forwarding bounds,Ad hoc network,correctness analysis,face routing,sensor network,worst-case analysis.
Equal-cost multi-path routing,Link-state routing protocol,Multipath routing,Dynamic Source Routing,Computer science,Static routing,Destination-Sequenced Distance Vector routing,Computer network,Real-time computing,Routing table,Geographic routing,Distributed computing
Journal
Volume
Issue
ISSN
59
9
0018-9340
Citations 
PageRank 
References 
26
1.16
20
Authors
2
Name
Order
Citations
PageRank
Hannes Frey1587.40
Ivan Stojmenovic26553520.25