A low-overhead fault-tolerant routing algorithm for mobile ad hoc networks: A scheme and its simulation analysis

The fault-prone nodes in a mobile ad hoc network (MANET) degrade the performance of any routing protocol. Using greedy routing mechanisms that tend to choose a single path every time, may cause major data losses, if there is a breakdown of such a path in a fault-prone environment. On the other hand, using all the available paths causes an undesirable amount of overhead on the system. Designing an effective and efficient fault-tolerant routing protocol is inherently hard, since the problem is NP-complete because of the unavailability of precise path information in adversarial environments [1]. To address the above mentioned problem, we present a fault-tolerant routing algorithm (FTAR), which bases on the ideas of foraging in natural ants [2]. The algorithm is divided into six stages, namely, initialization, path selection, pheromone deposition, confidence calculation, evaporation and negative reinforcement. Simulation results show that FTAR achieves high packet delivery ratio and throughput as compared to some of the key protocols which do not address fault-tolerance at all. Most importantly, FTAR is established to supersede the performance of one of the best fault-tolerant MANET routing schemes [1] known currently, with respect to the amount of routing overhead incurred - it is an important achievement for ad hoc networks. (C) 2010 Elsevier B.V. All rights reserved.