Ant Algorithm:
Contents
1 Abstract 1
2 Introduction 2
2.1 An Ant Colony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
2.2 Existing Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2.1 Basic Ant Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 The Ant-Colony-Based Routing Algorithm for MANETs (ARA) . . . . 5
3 Algorithm 6
3.1 Basics of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.1 Random Walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.2 FAnts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.3 Updating Routing Information . . . . . . . . . . . . . . . . . . . . . . 9
3.1.4 BAnts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Extensions of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.1 Improving the route . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.2 Dealing with mobility . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 Discussion 22
4.1 Comparison with Flooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.1 The Flooding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.2 The Ant Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1.3 Finding the Target . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.4 Quality of the found route . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Route Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.1 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Summary and Conclusions 34
5.1 The ant algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6 Future Works 36
6.1 Ant parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.2 Route Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Abstract
In this report we present a routing algorithm for mobile ad hoc networks (MANETs). The algorithm uses techniques of route discovery that was observed by ants. FAnts walk randomly around the network to find the target. These FAnts leave their track in writing routing table entries in each node they pass. If the target is found, another ant (BAnt) can walk back along this route and also writes the routing table entries. When the BAnts reaches the source the routing table of all nodes between the source and the destination carry the necessary routing information and data packets can be sent.
The routing algorithm based on ants was developed by G. Di Carlo and M. Dorigo [3] and M. Günes, U. Sorges and I. Bouazizi in [7] and further discussed in [6]. However, none of these works investigated the problem of mobile networks, where nodes change their position over time. In such a mobile network, some nodes may be connected during route discovery, but are disconnected when the data should be transferred. If this happen a mechanism called Route Maintenance will start to find the node the messages should be sent to. That is how we guaranteed that the route is stable and doesn’t break down.
Simulation results show that the total number of messages to find the target can be reduced compared to a basic flooding algorithm.
Introduction
In this report we introduce a routing protocol we developed. It is based on ideas of different ant algorithms. In particular, we consider mobile ad hoc networks (MANETs), where the network
nodes are able to change their position and the communication between the network nodes is established over a wireless medium. Also, we consider homogenous networks with no additional
infrastructure. There is no difference between the nodes. This has among other things the following consequences:
• Nodes can leave and join the network at any time
• There is no centralized control or overview
• Packets have to be forwarded form node to node
Routing in MANETs is a challenge due to the fact that a good path can suddenly become an inefficent or even an infeasible one. To succeed, a routing algorithm for such an environment
needs to be adaptive and to be able to deal with sudden changes in the topology of the network. These properties can also be found in nature. Insect populations show us a robust and efficient
way to adapt to the changing environment. This fact inspired us to design a routing algorithm based on simple biological agents, in our case ants.
Contents
1 Abstract 1
2 Introduction 2
2.1 An Ant Colony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
2.2 Existing Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2.1 Basic Ant Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 The Ant-Colony-Based Routing Algorithm for MANETs (ARA) . . . . 5
3 Algorithm 6
3.1 Basics of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.1 Random Walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.2 FAnts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.3 Updating Routing Information . . . . . . . . . . . . . . . . . . . . . . 9
3.1.4 BAnts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Extensions of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.1 Improving the route . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.2 Dealing with mobility . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 Discussion 22
4.1 Comparison with Flooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.1 The Flooding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.2 The Ant Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1.3 Finding the Target . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.4 Quality of the found route . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Route Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.1 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Summary and Conclusions 34
5.1 The ant algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6 Future Works 36
6.1 Ant parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.2 Route Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Abstract
In this report we present a routing algorithm for mobile ad hoc networks (MANETs). The algorithm uses techniques of route discovery that was observed by ants. FAnts walk randomly around the network to find the target. These FAnts leave their track in writing routing table entries in each node they pass. If the target is found, another ant (BAnt) can walk back along this route and also writes the routing table entries. When the BAnts reaches the source the routing table of all nodes between the source and the destination carry the necessary routing information and data packets can be sent.
The routing algorithm based on ants was developed by G. Di Carlo and M. Dorigo [3] and M. Günes, U. Sorges and I. Bouazizi in [7] and further discussed in [6]. However, none of these works investigated the problem of mobile networks, where nodes change their position over time. In such a mobile network, some nodes may be connected during route discovery, but are disconnected when the data should be transferred. If this happen a mechanism called Route Maintenance will start to find the node the messages should be sent to. That is how we guaranteed that the route is stable and doesn’t break down.
Simulation results show that the total number of messages to find the target can be reduced compared to a basic flooding algorithm.
Introduction
In this report we introduce a routing protocol we developed. It is based on ideas of different ant algorithms. In particular, we consider mobile ad hoc networks (MANETs), where the network
nodes are able to change their position and the communication between the network nodes is established over a wireless medium. Also, we consider homogenous networks with no additional
infrastructure. There is no difference between the nodes. This has among other things the following consequences:
• Nodes can leave and join the network at any time
• There is no centralized control or overview
• Packets have to be forwarded form node to node
Routing in MANETs is a challenge due to the fact that a good path can suddenly become an inefficent or even an infeasible one. To succeed, a routing algorithm for such an environment
needs to be adaptive and to be able to deal with sudden changes in the topology of the network. These properties can also be found in nature. Insect populations show us a robust and efficient
way to adapt to the changing environment. This fact inspired us to design a routing algorithm based on simple biological agents, in our case ants.
DOWNLOAD LINK:
No comments:
Post a Comment