A New Proposal for Route Finding in Mobile AdHoc Networks

Published Online June 2013 in MECS

A Mobile Ad hoc Network (MANET) is one consisting of a set of mobile hosts capable of communicating with each other without the assistance of base stations. The interest in MANETs has grown recently and many novel routing protocols were developed that deal with the special characteristics of such networks. Proactive routing protocols attempt to maintain at all times routing information from each node to every other node in the network (DSDV, WRP, OLSR, CGSR), whereas reactive protocols only acquire routes on demand (AODV, DSR, TORA, LAR). Obviously, both categories will not scale with large scale MANETs as considered in this paper. The signaling traffic constantly present in the network for proactive protocols is substantial because update messages are propagated throughout the network for any changes in the topology. Reactive protocols often employ a kind of flooding to acquire and sustain routes. The overhead induced becomes a serious limitation as well.

Earlier research has proposed several hybrid routing protocols specifically on MANET. However, the single path is easily broken and needs to perform a route discovery process again due to the dynamic topology of ad hoc networks. This leads to increase in both delay and control overhead as well as decrease in packet delivery ratio [1]. Due to the mobility of nodes, the topology of the network changes constantly. And paths, which were initially efficient, can quickly become inefficient or even in feasible. This means that routing information should be updated more regularly than in wired networks. So that in principle more routing control packets are needed. This is a problem in MANETs [2]. Since the bandwidth of the wireless medium is shared, nodes can only send/receive data if no other node is sending in their neighborhood. These changes cause frequent route breaks and force sources to re-establish or maintain connections to their distant communication partners. There are many number of Ad-Hoc routing protocols [1] [3] [4] [5] used. Generally they are classified into two. They are,

• A.    Proactive Protocols

In this Proactive protocol [5] each node maintains one/more tables containing Routing information to every node in the network. All nodes update these tables so as to maintain a consistent and up-to-date view of the network. When the network topology changes it may generate an unnecessary overhead to maintain the routing table.

• B.    Reactive Protocols

These protocols take a slow approach to routing. In contrast to Table Driven Routing protocols [4] [5] [6] all up-to-date routes are not maintained at every node. Instead the routes are created as and when required. When a source wants to send the packet to a destination it invokes the route discovery mechanisms to find the path to the destination. The route remains valid till the destination is reachable or until the routes no longer needed. Due to the advantages and disadvantages of each kind of routing algorithm, we can consider the usage of hybrid routing scheme.

Multi-Agent Systems (MAS) [7] can enable autonomous, team based problem solving under varying environmental conditions. Agent-based systems technology has generated lots of excitement in recent years because of its promise as a new paradigm for conceptualizing, designing and implementing software systems.

Swarm intelligence is a relatively new approach to problem solving that takes inspiration from the social behaviors of insects and of other animals. In particular, ants have inspired a number of methods and techniques among which the most studied and the most successful is the general purpose optimization technique known as ant colony optimization [8] [9]. Ant colony optimization (ACO) takes inspiration from the foraging behavior of some ant species. These ants deposit pheromone on the ground in order to mark some favorable path that should be followed by other members of the colony. Ant colony optimization exploits a similar mechanism for solving optimization problems. From the early nineties, when the first ant colony optimization algorithm was proposed, ACO attracted the attention of more researchers and a relatively large amount of successful applications are now available. Moreover, a substantial corpus of theoretical results is becoming available that provides useful guidelines to researchers and practitioners in further applications of ACO.

This paper performs a discussion on two routing algorithms ACO and MAS, and proposes a novel routing pattern based on the existing two algorithms. Section II describes briefly about the path establishment in MANET, Section III illustrates on the path establishment in MANET using existing protocols. Then, Section IV discusses on Ant Colony Optimization (ACO) and Section V on Multi Agent System (MAS). The proposed novel routing pattern is given in Section VI. Finally this paper is concluded in Section VII.

• II.    Path Establishment In MANET

MANET [1] can be created and used ‘anywhere, anytime’ offering unique advantages and versatility for certain environments and certain applications, i.e. for rescue agencies, transporting companies or merely for office use. In the case of rescue problems, for example in data analysis in scenes of natural disasters, an ad hoc network could be formed by communication devices in fire brigades, helicopters, ambulances and also people with laptop computers or mobile phones in hospitals, pharmacies and so on, all together working in a collaborative way to provide effective solutions to the problem.

Figure 1: A Mobile Ad Hoc Network

Fig.1 shows a sample Mobile Ad Hoc Network, where different kinds of objects are connected by an autonomous system. Fig.2 depicts the use of ad hoc network in military environment. Fig.3(a) and 3(b) shows the difference between wired (fixed) network and wireless (ad hoc) network respectively.

Each protocol when it is individual has some demerits. One possible solution to the existing routing problem is to combine proactive and reactive routing in a single network, as is done in hybrid routing algorithms.

Figure 2: MANET in Military Environment

• III.    Path Establishment Using Existing Protocols

Wireless networks can be classified in two types: infrastructure based network and infrastructure less (ad hoc) networks [1] [3] [5]. In ad hoc networks all nodes are mobile and can be connected dynamically in an arbitrary manner. All nodes of these networks behave as routers and take part in discovery and maintenance of routes to other nodes in the network. Ad hoc networks [1] are very useful in emergency search-and-rescue operations, meetings or conventions in which persons wish to quickly share information, and data acquisition operations in an inhospitable terrain.

Figure 3(a): Wired (fixed) Network

Figure 3(b): Wireless (ad hoc) Network

Ad hoc routing protocols can be divided into two categories: table-driven and on-demand routing [3] [4] [5] based on when and how the routes are discovered. In table driven routing protocols consistent and up-to-date routing information to all nodes are maintained at each node whereas in on-demand routing the routes are created only when desired by the source host.

• A.    Table Driven Routing protocols

• 1.    Destination Sequenced Destination-Vector Routing

• 2.    Protocol

• 3.    Wireless Routing Protocol

• 4.    Global State Routing

• 5.    Fisheye State Routing

• 6.    Hierarchical State Routing, etc.

• B.    On Demand Routing Protocols

• 1.    Ad Hoc On Demand Distance Vector Routing

• 2.    Dynamic Source Routing

• 3.    Temporally Ordered Routing Algorithm

• 4.    Associatively Based Routing

• 5.    Signal Stability Routing, etc.

• C.    Hybrid Protocols

This tries to profit the advantages of both reactive and proactive protocols and combine their basic properties into one. These protocols have the potential to provide higher scalability than pure reactive or proactive protocols [2].

Some of the hybrid protocols are

• 1.    DDR (Distributed Dynamic Routing)

• 2.    ZRP (Zone-Based Hierarchical Link-State Routing Protocol)

• 3.    Scalable Location Updates Routing Protocol (SLURP)

• 4.    Distributed Spanning Trees Based Routing Protocol (DST)

IV. Routing Based on Ant Colony Behaviour

Figure 4: Route searching behavior of real ants

In the area of network routing, algorithms have taken inspiration from the notion of stigmergy that describes the indirect communication taking place among individuals through modifications induced in their environment. Lately, a new kind of completely distributed routing protocols for fixed, wired communication networks evolved inspired from social insects (e.g. ants) behavior (ABC, AntNet, Max-Min, CAF). Ants were shown to find shortest paths through a process called “stigmergy”, which could be described as indirect communication between individuals through the environment. Ants [9] returning from a food source to the nest lay down pheromones (a chemical substance) behind them (See Fig.4). Other ants are attracted by these pheromone trails and in turn reinforce them even more. As a result of this “auto-catalytic” effect, the shortest path will emerge rapidly. This process has been adapted for telecommunication networks. Current traffic conditions and link costs are measured by transmitting “artificial ants” (mobile routing agents) into the network, which not only update routing tables depending on the collected information, but as well mark the traveled path with an “artificial pheromone”.

These protocols showed very promising results [10] and turned out to be highly adaptive in dynamic network environments, and in fact, there already exist two different approaches for routing in mobile ad-hoc networks with ants-based algorithms.

In ARA [9] [11], ants are broadcasted into the network on demand to discover paths to destinations and mark them with pheromones. Again, this kind of flooding to acquire routes will not scale for large scale MANETs.

Most of the algorithms, in this area, have taken their inspiration from natural ant colonies because ants are able to find shortest paths using as only the pheromone trail deposited by other ants. In a packet network context, such pheromones are simply probabilities represented at each node by a routing table [12] and are derived from the number of visitations associated with route-finding packets or ants. In AntNet [9] [11] the information processed by ants is represented in every node by a routing table and an additional data structure that contains statistics about local traffic - delay statistics.

Figure 5: Representation of the information in every node by means of the traditional AntNet routing.

Fig.5 shows the node structures used by mobile agents in AntNet [9] [11] for the case of a node with L neighbors and a network with N nodes. The entries in the routing table [12] are probabilistic values. The Local Traffic Statistics (LTS) function is an adaptive model for the traffic towards each possible destination.

In AntNet (see Fig.6), two types of ants (routing packets) are used, forward ants and backward ants. Forward ants are explorative ants that have the goal of discovering new routes and constantly evaluate the state of existing routes, analyzing the delay.

When a forward ant reaches its goal, another ant called backward ant is activated, which returns to its source node using the reverse path taken by the forward ant and updates the LTS structure and the routing table at each node along the return path. In the routing table, every value of P ij represents the probability or appropriateness of choosing j as next node when the destination node is i . These values are calculated according to the information

(delay) gathered by forward ants and modified by taking into account historical aspects or statistics of local traffic. The concept is more clearly illustrated with an example (see Fig.6).

Figure 6: Forward Ant and Backward Ant in AntNet

ACO has been widely applied to solving various combinatorial optimization problems such as Traveling Salesman Problem (TSP), Job-shop Scheduling Problem (JSP), Vehicle Routing Problem (VRP), Quadratic Assignment Problem (QAP), etc. Although ACO has a powerful capacity to find out solutions to combinational optimization problems, it has the problems of stagnation and premature convergence and the convergence speed of ACO is very slow. Those problems will be more obvious when the problem size increases. Therefore, several extensions and improvements versions of the original ACO algorithm were introduced over the years.

ACO has been widely applied to solving various combinatorial optimization problems such as Traveling Salesman Problem (TSP), Job-shop Scheduling Problem (JSP), Vehicle Routing Problem (VRP), Quadratic Assignment Problem (QAP), etc. The behavior of ACO algorithms and the ACO model are analyzed for certain types of permutation problems. It is shown analytically that the decisions of an ant are influenced in an intriguing way by the use of the pheromone information and the properties of the pheromone matrix. Traveling salesman problem (TSP) [13] is one of the well-known and extensively studied problems in discrete or combinational optimization and asks for the shortest roundtrip of minimal total cost visiting each given city (node) exactly once.

TSP is an NP-hard problem and it is so easy to describe and so difficult to solve. Ant System was first introduced and applied to TSP by Marco Dorigo. Initially, each ant is randomly put on a city. During the construction of a feasible solution, ants select the following city to be visited through a probabilistic decision rule. Graph theory defines the problem as finding the Hamiltonian cycle with the least weight for a given complete weighted graph. It is widespread in engineering applications and some industrial problems such as machine scheduling, cellular manufacturing and frequency assignment problems can be formulated as a TSP. A complete weighted graph G= (N, E) can be used to represent a TSP [13], where N is the set of n cities and E is the set of edges (paths) fully connecting all cities. Each edge (i,j) ∈ E is assigned a cost dij, which is the distance between cities i and j. dij can be defined in the Euclidean space and is given as follows:

d j = i - Xj)² + (y-y )^{2) (1)}

In TSP, the main modifications introduced by ACO are the following. First, to avoid search stagnation and ACO is more effective if ants are initially placed on different cities. Second, information entropy is introduced which is adjust the algorithm’s parameters. Additionally, the best performing ACO algorithms for the TSP [13] improve the solutions generated by the ants using local search algorithms.

Nowadays, ACO is a well-established metaheuristic applied to a wide range of optimization problems and with hundreds of successful implementations. By analyzing the many available ACO implementations, one can identify ingredients necessary for the successful application of ACO.

Firstly, an effective mechanism for iteratively constructing solutions must be available. Ideally, this construction mechanism exploits problem-specific knowledge by using appropriate heuristic information. Secondly, the best performing ACO algorithms have specialized features that allow to carefully controlling the balance between the exploration of new solutions and the intensification of the search around the best solutions. Thirdly, the usage of local search algorithms for improving the solutions constructed by the ants is very successful in practice. Finally, the integration of other techniques such as constraint programming, tree search techniques, or multilevel frameworks often yields a further improvement in performance or increases the robustness of the algorithms.

• V.    Multi Agent System

Research in MAS [2] [7] is concerned with the study, behavior, and construction of a collection of possibly preexisting autonomous agents that interact with each other and their environments. Study of such systems goes beyond the study of individual intelligence to consider, in addition, problem solving that has social components. An MAS can be defined as a loosely coupled network of problem solvers that interact to solve problems that are beyond the individual capabilities or knowledge of each problem solver. These problem solvers, often called agents, are autonomous and can be heterogeneous in nature.

The characteristics of MASs are that (1) each agent has incomplete information or capabilities for solving the problem and, thus, has a limited viewpoint; (2) there is no system global control; (3) data are decentralized; and (4) computation is asynchronous. Multi Agent system (MAS)

offers modularity. If a problem domain is particularly complex, large, or unpredictable, then the only way it can reasonably be addressed is to develop a number of functionally specific and (nearly) modular components (agents) that are specialized at solving a particular problem aspect. The motivations for the increasing interest in MAS research include the ability of MASs to do the following:

First is to solve problems that are too large for a centralized agent to solve because of resource limitations or the sheer risk of having one centralized system that could be a performance bottleneck or could fail at critical times.

Second is to allow for the interconnection and interoperation of multiple existing legacy systems. To keep pace with changing business needs, legacy systems must periodically be updated. Completely rewriting such software tends to be prohibitively expensive and is often simply impossible [2] [7] [14]. Therefore, in the short to medium term, the only way that such legacy systems can remain useful is to incorporate them into a wider cooperating agent community in which they can be exploited by other pieces of software. Incorporating legacy systems into an agent society can be done, for example, by building an agent wrapper around the software to enable it to interoperate with other systems.

Third is to provide solutions to problems that can naturally be regarded as a society of autonomous interacting components-agents.

Fourth is to provide solutions that efficiently use information sources that are spatially distributed. Examples of such domains include sensor networks seismic monitoring, and information gathering from the internet.

Fifth is to provide solutions in situations where expertise is distributed [2] [7] [14]. Examples of such problems include concurrent engineering, health care, and manufacturing.

Sixth is to enhance performance along the dimensions of (1) computational efficiency because concurrency of computation is exploited (as long as communication is kept minimal, for example, by transmitting high-level information & results rather low-level data); (2) reliability, that is, graceful recovery of component failures, because agents with redundant capabilities or appropriate inter-agent coordination are found dynamically (for example, taking up responsibilities of agents that fail); (3) extensibility because the number and the capabilities of agents working on a problem can be altered; (4) robustness, the system’s ability to tolerate uncertainty, because suitable information is exchanged among agents; (5) maintainability because a system composed of multiple components-agents [2] [7] [14] is easier to maintain because of its modularity; (6) responsiveness because modularity can handle anomalies locally, not propagate them to the whole system; (7) flexibility because agents with different abilities can adaptively organize to solve the current problem; and (8) reuse because functionally specific agents can be reused in different agent teams to solve different problems.

The first MAS applications appeared in the mid-1980s and increasingly cover a variety of domains, ranging from manufacturing to process control, air traffic control, and information management. One of the earliest MAS applications was distributed vehicle monitoring (DVMT), where a set of geographically distributed agents monitor vehicles that pass through their respective areas, attempt to come up with interpretations of what vehicles are passing through the global area, and track vehicle movements. The DVMT has been used as an MAS test bed. The basic problem can be described as follows: A manufacturing enterprise is modeled as a hierarchy of functionally specific work cells. These work cells are further grouped into flexible manufacturing systems (FMSs) that collectively constitute a factory. The goal of YAMS is to efficiently manage the production process of these factories. To achieve this complex task, YAMS adopts a multiagent approach, where each factory and factory component is represented as an agent.

Each agent has a collection of plans representing its capabilities. The CNP allows tasks (that is, production orders) to be delegated to individual factories, and from individual factories down to FMSs, and then to individual work cells. Other systems in this area include those for configuration design of manufacturing products and collaborative design. The best-known MAS for process control is ARCHON, a software platform for building MASs and an associated methodology for building applications with this platform. ARCHON has been applied in several process-control applications, including electricity transportation management (the application is in use in northern Spain) and particle accelerator control. ARCHON also has the distinction of being one of the world’s earliest fields tested MAS. Other agent-based process-control systems have been written for monitoring and diagnosing faults in nuclear power plants, spacecraft control and climate control. In addition, there are a variety of MAS applications in telecommunications.

Multi-Agent Systems (MAS) can enable autonomous, team based problem solving under varying environmental conditions. Previous work done in MAS has assumed relatively benign wired network behavior and inter-agent communications characteristics that may not be well supported in MANET environments. Hence, here we present a proposal in a wireless environment with a hybrid routing scheme. Some possible examples of future MAS applications include distributed command and control support software, network management, sensor networking, and mobile cooperative robotics. Early analysis has shown that MAS teamwork communications within MANET can be improved through better design between the layers.

• VI.    The Proposed Routing Scheme

The proposed routing pattern is a hybrid multipath algorithm that combines both reactive and proactive features to route in MANETs [1] [15]. It is integrated by an ant-based routing algorithm [9] [16] [17] (Ant Colony Optimization - ACO) enhanced by a Multi-Agent System

(MAS) [8] [18]. The ACO acts in the proactive route probing and exploration to offer a path from source to destination to a data session and a group of possible backup paths. This Hybrid Scheme is composed of three main data structures in each node: the Routing Table ( RT ), the Historical Path Table ( HPT ) and the Alliance Formation Table ( AFT ). The RT i in node i contain for each destination d and each possible next hop n a value P dn (pheromone) that represents the probability of choosing n as next hop to reach destination d when a data session in node source S needs it. This pheromone tables in different nodes indicate multiple paths between s and d , and data packets can be sent from node to node until they reach their destination. To update the pheromone tables, initially, this Scheme (in fact, the MAS [8] [14] [18]) has a reactive behavior when a data session is started at node s with destination d , and it does not find up-to-date routing information to reach d.

The MAS [7]  [8]  [14] acts sending agents

(broadcasting) to the neighborhoods, and it waits for successful information represented by the initial AFT in node i . This AFT is inspired by previous works related to Alliance Formation for Agents. This AFT i represents node alliances for node i and contains information related to the degree of trust existing between node i and its neighbors to reach destination d . If the degree of trust related to node n (possible next hop) to reach destination d is high, then the pheromone P dn in RT i will be high, or vice versa. The MAS [18] always acts when a reactive behavior is needed. As an Alliance Diameter Control ( ADC ), there is a hop-count field that would decide the number of hops to which the advertisement of trust may be propagated by receiving platforms.

In a highly dynamic environment, such as MANETs, a small diameter of an alliance is more desirable. This is because, if the diameter is large, stability of a system in an alliance would be less. To maintain and explore routes in a proactive way, the proposed scheme (in fact, the ACO [9] [16] [17]) acts sending out routing packets (forward ants) according to the data sending rate while a data session is running. Ants follow and actualize the pheromone values in the routing table [12] in order to maintain the existing routes, and they also have a small probability of being broadcasted, in order to have the possibility of finding new routes [2].

Figure 7: Proposed Hybrid Scheme

Alliance Formation Table

Like in the traditional AntNet [9] [11] [16], when a forward ant finds a destination, a backward ant is generated to go back from the destination to the source with the goal of maintaining up-to-date the estimates of this path, and to update the pheromone values related to this path. If at any point the forward ant is broadcasted, it will explore new paths and leave a pheromone trail. In order to guide the forward ants a bit better, the traditional hello messages are used for routing in MANETs. As it is shown in Fig.7, the ACO [16] has two main aims, first to update the RT and second to maintain the HPT in order to have possible backup paths. The HPT contains information about the last five paths traversed, and their respective delay statistics. The MAS [14] enhances the decisions of the ACO [10] by using an AFT and updating the RT . Finally, when a data session arrives, it follows the P dn pheromone to reach their destination d.

QoS routing provides support to effectively control the total traffic that can flow into the network. QoS routing is a routing mechanism under which paths for flows are determined according to resource availability in the network as well as the QoS requirement of flows. QoS routing means that it selects routes with sufficient resources for the requested QoS parameters. Multicast routing sends a single copy of a data packet simultaneously to multiple receivers over a communication link that is shared by the paths to the receivers. QoS should be maintained in Hybrid Schemes. In this paper we have proposed a hybrid route finding scheme. This is our initial step; this proposal will be extended to produces test results in future.

• VII.    Conclusion

Routing in MANETs is ‘a hard work’ and actually it is an interesting research area that has been growing in recent years. Its difficulty is mainly generated because of the constant changes in the network. There exist some traditional solutions such as proactive protocols and reactive protocols, each one with their advantages and disadvantages. In spite of this, these solutions have to be improved to offer better scalability and performance, in future. In fact, hybrid routing protocols have ‘the potential’ to provide higher scalability than pure reactive or proactive protocols, and moreover to maintain routing information much longer because of the collaboration between nodes.

In this paper, the proposed hybrid routing scheme is a new Multi-agent Ant-based System for routing in mobile ad Hoc networks combines, in summary, a reactive behavior of a multi-agent system with a proactive behavior (route probing and exploration) of an ant-based routing algorithm. The proposed integrated approach has a relatively short route establishment time while using a small number of control messages which makes it a scalable routing approach. The overhead of this routing approach will be inexpensive and also will enable to have an alternate route during route failure. This proposed route finding scheme in order to provide high connectivity of nodes, will minimize the route discovery latency and the end-to-end delay.