Paper Info
Title
Self-Stabilizing Optimal Local Routing in Ad Hoc Networks
Abstract
Given a wireless mobile ad hoc network (MANET), we present a self-stabilizing optimal local routing (SOLR) algorithm. Our claim of optimality is based on the minimum distance. The optimal routing is done with respectto the t closest nodes (called t-set). The locality is maintained with respect to the t-set, not with the direct neighbors. The algorithm is transparent to what the distance means: can be either the real distance, or the number of hops. The value of t is application dependent, and is decided in advance. t is n (where n is the upper bound on the maximum number of nodes in the network) when each node needs to know the shortest paths to all other nodes. t is less than n when nodes need to know the network only partially. A self-stabilizing system has the ability to automatically recover to normal behavior in case of transient faults, without a centralized control. Each node can start in some arbitrary state and with no knowledge of the network architecture, but still eventually computes a correct routing table for the t-closest nodes (t-set). The space complexity per node of SOLR is 0((t + 驴)log(n)) bits (where 驴 is the node degree) with a total of 0(n(t + 驴) log(n)) bits (where 驴 is the maximum node degree) for the whole network. The stabilization time of the SOLR algorithm is 0(d + c) time units (where d is the network diameter and c is a large constant depending on some local computation). SOLR can easily work for optimal on-demand routing by considering the set of nodes for which the shortest paths are desired instead of the t closest nodes. Also, it can be extended to a global routing protocol by using features specific to other protocols (e.g., hierarchical routing, cluster routing, interval routing, etc.).
Year
DOI
Venue
2005
10.1109/ICDCSW.2005.123
ICDCS Workshops
Keywords
Field
DocType
ad hoc networks,hierarchical routing,global routing protocol,interval routing,cluster routing,shortest path,self-stabilizing optimal local routing,closest node,correct routing table,optimal routing,optimal on-demand routing,mobile ad hoc network,upper bound,space complexity,mobile network,ad hoc network,computer science,wireless sensor networks,routing protocol,computer networks,computational complexity,network topology,distributed algorithms,mobile ad hoc networks,intelligent networks,network architecture,mobile computing,self stabilization,distributed algorithm,routing protocols
Topology,Link-state routing protocol,Equal-cost multi-path routing,Dynamic Source Routing,Computer science,Static routing,Destination-Sequenced Distance Vector routing,Computer network,Optimized Link State Routing Protocol,Routing table,Routing protocol
Conference
ISBN
Citations 
PageRank 
0-7695-2328-5-06
0
0.34
References 
Authors
7
3
Name
Order
Citations
PageRank
Doina Bein110321.64
Ajoy K. Datta236935.83
Vincent Villain354445.77