Self-Stabilizing Local Routing in Ad Hoc Networks

We present a self-stabilizing optimal (in terms of the distance) local routing algorithm () for a wireless mobile ad hoc network. The distance may represent various metrics, including the real distance and the number of hops. The optimal routing for any node is computed for t closest nodes (called t...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2007-03, Vol.50 (2), p.197-203
Main Authors: Bein, Doina, Datta, Ajoy K., Villain, Vincent
Format: Article
Language:English
Subjects:
Algorithms
Computer networks
Computer science
Hierarchies
Protocol
Routing
Traffic flow
Wireless 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:We present a self-stabilizing optimal (in terms of the distance) local routing algorithm () for a wireless mobile ad hoc network. The distance may represent various metrics, including the real distance and the number of hops. The optimal routing for any node is computed for t closest nodes (called t-set) where t is an application-dependent parameter and is decided in advance. The locality is defined with respect to the t-set, not with respect to the direct neighbours. Our protocol is a particular case of distance vector routing protocol, where the number of entries in the routing table is limited to t. A self-stabilizing system has the ability to automatically recover to normal behaviour 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 nodes in its t-set. If we assume that the t-set represents the set of destinations for which the shortest path needs to be computed, becomes an optimal on-demand routing protocol. 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.). [PUBLICATION ABSTRACT]
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/bxl059