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.
MANETs are self-organizing and self-configuring networks having nodes connected by wireless links. They are infrastructure-less and nodes in them can join or leave at any point of time. There is no centralized control in MANETs, all nodes behave as routers for each other, and data packets are transferred for node to node in a multi-hop fashion.
The mobile nodes, which are inherently resource constrained, exhibit various kinds of faulty behavior. Faulty behavior may be transient or permanent and may be due to hardware or software problems. In such a scenario, a faulty node may not forward packets. Absence of any underlying infrastructure makes it difficult to keep these devices monitored. Moreover, the adversarial environment in MANETs makes the situation worse. Making routing decisions oblivious of these nodes will significantly degrade the performance of any routing protocol and can also threaten its prime objectives. Fault-tolerant routing protocols address this problem by exploring the network redundancy through multipath routing techniques.
The problem of fault-tolerant routing was first identified and addressed by Xue and Nahrstedt [1]. They developed the end-to-end estimation based fault-tolerant routing algorithm (E2FT). E2FT uses two complementary processes: route estimation and route selection. The former estimates the quality of a certain route through end-to-end performance measurement, while the latter uses the information provided by the former to decide a multipath route for packet delivery. Route selection is refined progressively with the increasingly accurate estimation result using confirmation and dropping procedures, which are elaborated further in Section 2.2.
The work by Xue and Nahrstedt acts as a direct motivation for this work, as it addresses the challenges faced by the E2FT algorithm. When the mobility of the nodes is taken into account, E2FT can be less efficient. The optimization of the algorithm to address the mobility of the nodes is a weak one and does not exploit the information gathered by the nodes to its full extent. E2FT can also incur large packet overhead due to its conservative estimation method. Clearly, there is a need for an algorithm that can address these challenges more effectively, and this can be achieved using stigmergic[3] communication among the nodes of a MANET by situating it within the ACO [2] framework.
In this paper, we describe the fault-tolerant ant-based routing (FTAR) algorithm for MANETs. The design of FTAR is based on the self-organizing behavior observed in ant colonies. We use the structure of ACO to develop an effective fault-tolerant routing scheme. It has been observed that ants converge to the shortest path among the various routes found out by independent ants from the nest to the source of food.
As ants travel, they leave out a biochemical substrate, called as the pheromone. The shorter paths tend to have a higher concentration of pheromone and the ants preferentially move in a direction of higher pheromone content and, thus, further reinforce those paths. These paths will, therefore, attract more ants and, thus, lead to the convergence of the majority of the ants to the shortest path. The local intensity of the pheromone field, which is the overall result of the repeated and concurrent path sampling experiences of the ants, encodes a spatially distributed measure of goodness associated with each possible move. This form of distributed control based on the indirect communication among agents, which locally modify the environment and react to these modifications leading to a phase of global coordination of the agent actions, is called stigmergy[3].
The FTAR algorithm provides a confidence value to each path based on the network information collected by the artificial ant agents. The confidence in a particular path shows its degree of fault-tolerance. Instead of blindly routing through all the paths, data can be routed through these fault-tolerant paths, neglecting the highly faulty or the fault-prone ones. Using control packets to select routes on the basis of a priori information decreases the overhead further, as equal number of control packets need not be sent on faulty paths, as is done in E2FT.
The paper is organized as follows. We first discuss the works related to FTAR, which encompasses other significant fault-tolerant routing techniques and the discussion of ant colony optimization (ACO) framework and other ACO routing algorithms. This is followed by a detailed discussion of the FTAR algorithm. We then discuss the simulation scenario and explain the results. Then we provide the conclusion to our work.
In this paper, we proposed the first ant-based approach for fault-tolerant routing in MANETs. Through extensive simulation experiments, we observe that the FTAR algorithm achieves fault-tolerant routing with high packet delivery rate and throughput compared to the non-fault-tolerant routing algorithms. Most prominently, in general, we obtain lower overhead compared to the best fault-tolerant routing algorithm known to date for MANETs.
In the future, we plan to: (a) use other mobility models, (b) use networks having a much larger number of nodes and varying the network density and (c) develop test-beds for observing whether the results remain the same for actual network environments.
