AntHocNet : Seminar Report and PPT
Mobile Ad Hoc Networks (MANETs) are networks in which all nodes are mobile and communicate with each other via wireless connections. Nodes can join or leave at anytime. There is no fixed infrastructure, all nodes are equal and there is no centralized control or overview. There are no designated routers: all nodes can serve as routers for each other, and data packets are forwarded from node to node in a multi-hop fashion.
Since a few years research interest in MANETs has been growing, and especially the design of MANET routing protocols has received a lot of attention. One of the reasons is that routing in MANETs is a particularly challenging task due to the fact that the topology of the network changes constantly, and paths which were initially efficient can quickly become inefficient or even infeasible. Moreover, control information flow in the network is very restricted. This is because the bandwidth of the wireless medium is limited, and the medium is shared. The access to the shared channel is controlled by protocols at the Medium Access Control layer (MAC), such as ANSI/IEEE 802.11 DCF (which is commonly used in MANETs), which in their turn create extra overhead. It is therefore important to design algorithms that are adaptive, robust and self-healing. Moreover, they should work in a localized way, due to the lack of central control or infrastructure in the network.
Nature’s self-organizing systems like insect societies show precisely these desirable properties. Making use of a number of relatively simple biological agents (e.g., ants) a variety of different organized behaviors are generated at the system-level from the local interactions among the agents and with the environment. The robustness and efficiency of the collective behaviors of insect societies with respect to variations of environment conditions is a key-aspect of their biological success. Because of these same properties, they have recently become a source of inspiration for the design of routing algorithms for dynamic networks (as well as for the solution of several other classes of problems).
Here we describe AntHocNet, a new routing algorithm for MANETs. AntHocNet’s design is based on a specific self-organizing behavior of ant colonies, the shortest paths discovery, and on the related framework of Ant Colony Optimization (ACO). It has been observed that ants in a colony can converge on moving over the shortest among different paths connecting their nest to a food source. The main catalyst of this colony-level shortest path behavior is the use of a volatile chemical substance called pheromone: ants moving between the nest and a food source deposit pheromone, and preferentially move towards areas of higher pheromone intensity. Shorter paths can be completed quicker and more frequently by the ants, and will therefore be marked with higher pheromone intensity. These paths will then attract more ants, which will in turn increase the pheromone level, until there is convergence of the majority of the ants onto 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 move. This form of distributed control based on 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 . Stigmergic coordination is one of the keys to obtain self-organized behaviors not only in ant colonies but more generally across social systems, from insects to humans. When stigmergy is at work, system’s protocols (interfaces) play a prominent role with respect to modules (agents). Protocols are the rules that prescribe the characteristics of the allowed interfaces and of the information exchanged between modules, permitting system functions that could not be achieved by isolated modules. A good stigmergic model supplies global robustness, scalability, evolvability, and allows to fully exploit the potentialities of the modules and of modularity.
All these ingredients have been reverse-engineered in the framework of ACO, which exploits the mechanisms behind the ant colony shortest path behavior to define a Nature-inspired metaheuristic for combinatorial optimization. ACO features multi-agent organization, stigmergic communication among the agents, distributed operations, use of astochastic decision policy to construct solutions, stigmergic learning of the parameters of the decision policy, and so on. It has been applied with success to a variety of combinatorial problems (e.g., traveling salesman, vehicle routing, etc, as well as to routing. The first ACO routing algorithms were designed for wired networks (e.g., AntNet for packet-switched networks and ABC for circuit-switched networks). These algorithms exhibit interesting properties which are also desirable for MANET routing: they work in a fully distributed way, are highly adaptive, use mobile agents for active path sampling, are robust to agent failures, provide multipath routing, and automatically take care of data load spreading. However, the fact that they crucially rely on repeated path sampling can cause significant overhead if not dealt with carefully. There have already been some attempts to design ACO routing algorithms for MANETs. Examples are ARA and PERA. However, these algorithms loose much of the proactive sampling and exploratory behavior of the original ant-based algorithms in their attempt to limit the overhead caused by the ants. With AntHocNet we aim to design an algorithm which works efficiently in MANETs while maintaining the properties which make ACO routing algorithms so appealing. While most of the previous algorithms for wired networks were adopting a proactive scheme by periodically generating ant-like agents for all possible destinations, AntHocNet follows a hybrid approach: ants are generated according to both proactive and reactive schemes.
This Report is organized as follows. In Section 2 we describe basic fundamentals. And Section 3 contains the description of our algorithm.
In this section we describe related literature. In 2.1 we give an introduction to MANET routing algorithms, and in 2.2 we describe the basic elements of Ant System and ACO for routing. Then in 2.3 we give an overview of existing implementations of ACO routing for MANETs, and in 2.4 we indicate other MANET routing algorithms which contain ACO routing elements.
The IETF identifies what they characterize as a Mobile Ad Hoc Network (MANET). It is a collection of nodes, each of which is equipped with one or more wireless network interfaces. The system may operate in isolation, or have gateways to and interface with a fixed network. When a MANET is connected to a fixed internetwork, it is envisioned that it will operate as a stub network, i.e. only carrying traffic originating at or destined for internal nodes.
A number of characteristics of MANETs are identified:
- Dynamic Topologies: Nodes are free to move arbitrarily. The network topology may change rapidly and randomly and contain both unidirectional and bidirectional links
- Bandwidth constrained, variable capacity links: After accounting for interference, noise, contention, the realized throughput may be much lower than a radio’s maximum rate.
- Energy Constrained Operation.
- Limited physical security. Possibility of eavesdropping, spoofing, denial of service attacks.
- Networks may be large. This is described as tens or hundreds of nodes.
In recent years a large number of MANET routing algorithms have been proposed. These algorithms all deal with the dynamic aspects of MANETs in their own way, using reactive or proactive behavior, or a combination of both. Reactive behavior means that an algorithm only gathers routing information in response to an event, usually an event which triggers the need for new paths, such as the start of a data session or the failure of an existing path. Proactive behavior means that the algorithm also gathers routing information at other times, so that it is readily available when needed.
In the MANET literature, the classical distinction is between purely proactive, purely reactive, and hybrid algorithms. In purely proactive algorithms (e.g., DSDV) nodes try to maintain paths to all other nodes at all times. This means that they need to keep track of all topology changes, which can become difficult if there are a lot of nodes or if they are very mobile. In purely reactive algorithms (e.g., AODV and DSR), nodes only gather routing information on demand: when a data session to a new destination starts, or when a path which is in use fails. Reactive algorithms are in general more scalable since they greatly reduce the routing overhead, but they can suffer from oscillations in performance because they are never prepared for disruptive events. In practice, many algorithms are hybrid algorithms (e.g. ZRP), using both proactive and reactive components in order to try to combine the best of both worlds.
Ant algorithms were first proposed by Dorigo and colleagues as a multi-agent approach to difficult combinatorial optimization problems such as the traveling salesman problem (TSP) and the quadratic assignment problem (QAP). There is currently much ongoing activity in the scientific community to extend and apply ant-based algorithms to many different discrete optimization problems. Recent applications cover problems such as vehicle routing, sequential ordering, graph coloring, routing in communications networks, and so on.
Ant algorithms were inspired by the observation of real ant colonies. Ants are social insects, that is, insects that live in colonies and whose behavior is directed more to the survival of the colony as a whole than to that of a single individual component of the colony. Social insects have captured the attention of many scientists because of the high structuration level their colonies can achieve, especially when compared to the relative simplicity of the colony’s individuals. An important and interesting behavior of ant colonies is their foraging behavior, and, in particular, how ants can find the shortest paths between food sources and their nest.
While walking from food sources to the nest and vice versa, ants deposit on the ground a substance called pheromone, forming in this way a pheromone trail. Ants can smell pheromone, and when choosing their way, they tend to choose, in probability, paths marked by strong pheromone concentrations. The pheromone trail allows the ants to find their way back to the food source (or to the nest). Also, it can be used by other ants to find the location of the food sources found by their nest mates.
It has been shown experimentally that this pheromone trail following behavior can give rise, once employed by a colony of ants, to the emergence of shortest paths. That is, when more paths are available from the nest to a food source, a colony of ants may be able to exploit the pheromone trails left by the individual ants to discover the shortest path from the nest to the food source and back.
Nodes in AntHocNet forward data stochastically. When a node has multiple next hops for the destination d of the data, it randomly selects one of them with probability Pnd. Pnd is calculated in the same way as for reactive forward ants (Equation 1), but with a higher exponent (set to 2), in order to be more greedy with respect to the better paths. According to this strategy, we do not have to choose a priori how many paths to use: their number is selected automatically in function of their quality.
The probabilistic routing strategy leads to data load spreading according to the estimated quality of the paths. If the estimates are kept up-to-date (which is done using the proactive ants described in Subsection 3.3), this leads to automatic load balancing. When a path is clearly worse than others, it will be avoided, and its congestion will be relieved. Other paths will get more traffic, leading to higher congestion, which will make their end-to-end delay increase. By continuously adapting the data traffic, the nodes try to spread the data load evenly over the network.
While a data session is running, the source node sends out proactive forward ants according to the data sending rate (one ant every n data packets, where n was 5 in the experiments). They are normally unicast, choosing the next hop according to the pheromone values using the same formula as reactive forward ants (Equation 1), but also have a small probability at each node of being broadcast (this probability was set to 0.1 in the experiments). This way they serve two purposes. If a forward ant reaches the destination without a single broadcast it probes an existing path. It gathers up-to-date quality estimates of this path, and the backward ant updates the pheromone values of intermediate nodes, just like reactive backward ants do. If on the other hand the ant got broadcast at any point, it leaves the currently known paths and explores new ones.
After a broadcast the ant arrives in all neighbors of the broadcasting node. It is possible that in these neighbors it does not find pheromone for its destination, so that it needs to be broadcast again. The ant will then quickly proliferate and flood the network, like reactive forward ants do. To avoid this, we limit the number of broadcasts to nb (set to 2 in the tests). If the proactive ant does not find routing information within nb hops, it is killed. The effect of this is that the search for new paths is concentrated around the current paths, so that we are looking for path improvements and variations.
To guide the forward ants better, we use hello messages. These are short messages (in our case containing just the sender’s address) broadcast every thello seconds by the nodes (e.g., thello = 1sec). If a node receives a hello from a new node n, it adds n in its routing table. After that it expects a hello from n every thello seconds. After missing a certain number of hello’s (allowed-hello-loss = 2 here), n is removed. Using these messages, nodes have pheromone information about their immediate neighbors in their routing table. So when an ant arrives in a neighbor of its destination, it can go straight to its goal. Looking back at the ant colony inspiration of our model, this can be seen as pheromone diffusion: pheromone deposited on the ground diffuses and can be detected also by ants further away. In future work we will extend this concept to give better guidance to the exploration by proactive ants. Hello messages also serve another purpose: they allow to detect broken links. This allows nodes to clean up stale entries from their routing tables.
Each node tries to maintain an updated view of its immediate neighbors at any time, in
order to detect link failures quickly, before they can lead to packet losses. The presence
of a neighbor node can be confirmed when a hello message is received, or after any other successful interception or exchange of signals. The disappearance of a neighbor is assumed when such an event has not taken place for a certain amount of time, defined by
thello £ allowed-hello-loss, or when a unicast transmission to this neighbor fails.
When a neighbor is assumed to have disappeared, the node takes a number of actions. First, it removes the neighbor from its neighbor list and all associated entries from its routing table. Then it broadcasts a link failure notification message. This message contains a list of destinations to which the node lost its best path, and the new best estimated end-to-end delay and number of hops to this destination (if it still has entries for the destination). All its neighbors receive the notification and update their pheromone using the new estimates. If they in turn lost their best or their only path to a destination due to the failure, they also broadcast a notification, until all concerned nodes are notified.
If the link failure was discovered due to the failed transmission of a data packet, and there is no other path available for this packet, the node tries to locally repair the path (and does not include this path in the link failure notification). The node broadcasts a path repair ant that travels to the involved destination like a reactive forward ant: it follows available pheromone when it can and is broadcast otherwise. One difference is that it has a maximum number of broadcasts (2 in our tests) so that proliferation is limited. The node waits for some time (empirically set to 5 times the estimated delay of the lost path), and if no backward repair ant is received, it concludes that it was not possible to repair the path. Packets which were in the meantime buffered for this destination are discarded, and the node sends a link failure notification about the lost destination.
Link failure notifications keep routing tables on paths up-to-date about upstream link
failures. However, they can sometimes get lost and leave dangling links. A data packet
following such a link arrives in a node where no further pheromone is available. The node will then discard the data packet and unicast a warning back to the packet’s previous
hop, which can remove the wrong routing information.