17-05-2012, 01:30 PM
Ant Hocnet
anthocknet.ppt (Size: 6.26 MB / Downloads: 148)
MANETs
in Mobile Ad Hoc Networks (MANETs), all nodes are mobile and they communicate with each other via wireless connections.
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.
So it takes less bandwidth, less cost
Natural behavior of ants
Natural behavior of ants have inspired scientists to mimic insect operational methods to solve real-life complex problems
By observing ant behavior, scientists have begun to understand their means of communication
Optimization Technique Proposed by Marco Dorigo in the early ’90
Natural ants: How do they do it?
Since the route B is shorter, the ants on this path will complete the travel more times and thereby lay more pheromone over it.
The pheromone concentration on trail B will increase at a higher rate than on A, and soon the ants on route A will choose to follow route B
Since most ants will no longer travel on route A, and since the pheromone is volatile, trail A will start evaporating
Only the shortest route will remain!
Most of the algorithms are single path Multipath routing offers an interesting alternative in terms of link failure robustness and load balancing.
Some algorithms create multiple paths at path setup time, and use the best of these until it fails, after which they switch to the second best and so on.
A problem with this way of working is that alternative paths are often infeasible by the time they need to be used.
AntHocNet
AntHocNet is a hybrid multipath algorithm. When a data session is started at nodes with destination d, s checks whether it has up-to-date routing information for d. If not, it reactively sends out ant-like agents, called reactive forward ants, to look for paths to d.
These ants gather information about the quality of the path they followed, and at their arrival in d they become backward ants which trace back the path and update routing tables.
They are stochastically spread over the paths: in each node they select the next hop with a probability proportional to its pheromone value.
AntHocNet conti….
Once paths are set up and the data session is running, s starts to send proactive forward ants to d. These ants follow the pheromone values similarly to data packets. In this way they can monitor the quality of the paths in use.
Moreover, they have a small probability of being broadcasted, so that they can also explore new paths. In case of link failures, nodes either try to locally repair paths, or send a warning to their neighbors such that these can update their routing tables.
Reactive path setup
Reactive forward ants looking for destinations d are either broadcasted or unicasted, according to whether or not the node they are currently in has routing information for d. Due to the broadcasting, ants can proliferate quickly over the network, following different paths to the destination.
When a node receives several ants of the same generation it will compare the path traveled by the ant to that of the previously received ants of this generation: only if its number of hops and travel time are both within a certain factor of that of the best ant of the generation, it will forward the ant.
Using this policy, overhead is limited by removing ants which follow bad paths, while the possibility to find multiple good paths is not hindered
Stochastic data routing
The path setup phase described above creates a number of good paths between source and destination, indicated in the routing tables of the nodes.
Data can then be forwarded between nodes according to the values of the pheromone entries. Nodes in AntHocNet forward data stochastically.
The probabilistic routing strategy leads to data load spreading with consequent automatic load balancing. When a path is clearly worse than others, it will be avoided, and its congestion will be relieved.
it is important to frequently monitor the quality of the different paths. To this end we use the proactive ants.
Proactive path maintainence
While a data session is running, the source node sends out proactThey follow the pheromone values in the same way as the data sending rate
They follow the pheromone values in the same way as the data but have a small probability at each node of being broadcasted. In this way they serve two purposes.
If no broadcast is there it simply updates the pheromone values
If broadcast occurs the ant will arrive in all the neighbors of the broadcasting node. It is possible that in this neighbor it does not find pheromone pointing towards the destination, so that it will need to be broadcasted again.
If the proactive ant does not find routing information within two hops, it will be deleted.
Link failures
Nodes can detect link failures when expected hello messages were not received. When a link fails, a node might loose a path to one or more destinations.
If the node has other next hop alternatives to the same destination, or if the lost destination was not used regularly by data, this loss is not so important
if the destination was regularly used for data traffic, and it was the node's only alternative for this destination, the loss is important and the node should try to repair the path.
This is the strategy followed in AntHocNet, with the restriction that a node only repairs the path if the link loss was discovered with a failed data packet transmission.
Link failures conti….
After the link failure, the node broadcasts a route repair ant that travels to the involved destination like a reactive forward ant:
it follows available routing information when it can, and is broadcasted otherwise. One important difference is that it has a maximum number of broadcasts, so that its proliferation is limited.
The node waits for a certain time, and if no backward repair ant is received, it concludes that it was not possible to find an alternative path to the destination which is removed from the routing table.
Conclusions and future work
It is a hybrid algorithm, combining reactive route setup with proactive route probing and exploration.
In simulation experiments we show that AntHocNet can outperform AODV in terms of delivery ratio and average delay, especially in difficult scenarios.
Also in terms of delay jitter, AntHocNet shows better results.
In future work we want to improve the exploratory working of proactive ants.