A Hybrid Ant Colony Optimization Technique for Wireless Ad Hoc Networks

A Hybrid Ant Colony Optimization Technique for Wireless Ad Hoc Networks

Pramod Hanagandi

Ramrao Adik Institute of Technology, Navi Mumbai

Abstract:- A Wireless Ad Hoc Network (WANET) has a set of mobile nodes that communicate with each other wirelessly using radio signals with a shared common channel. Routing is a process of finding a path in a network to transfer information from a desired source to a destination. Routing is a difficult task in WANETs due to the fact that the mobility of the nodes makes the network topology amorphous. The real challenge lies not in finding just a route but in finding an optimal route between the two mobile nodes. There are a number of algorithms in swarm intelligence which focus on a combined behaviour of decentralized systems, one such algorithm is the ant colony optimization which mimics the ants in their process of finding an optimal route from their nest to a source of food and vice versa. In this paper, a hybrid routing algorithm for Wireless Ad Hoc Networks is proposed which applies the Ant Colony Optimization algorithm, the Global State Routing Protocol (GSR) and the Zone Routing Protocol (ZRP) to find the shortest path between the source and destination nodes.

Keywords: Ant Colony Optimisation, Global State Routing Protocol, Zone Routing Protocol, Wireless Ad Hoc Networks.

1. INTRODUCTION

   A wireless ad hoc network is a group of decentralised mobile nodes that exchange information and are connected to each other wirelessly. Nodes may enter or leave the connection any time which makes the network topology unpredictable. A certain node can communicate with all the other nodes that are present in its transmission range. WANETs do not need an infrastructure and are more economic and flexible than other networks that need an infrastructure for their implementation. Other advantages of WANETs include better mobility and robustness due to non hierarchical management mechanisms. On the other hand, nodes in WANETs have certain disadvantages like limited battery power, low quality communication and limited bandwidth. Sometimes, the number of nodes in a network may increase drastically hence causing scalability issues. In the network, nodes are connected in a random order and there may or may not be a direct connection between a given set of nodes. Hence, to establish a connection between any given set of nodes, routing protocol is essential. Networks are evolving into more and more complex structures thus challenging the working of routing algorithms. Limited network resources and its erratic structure make the routing algorithm difficult to implement. All these challenging factors combined with the disadvantages of WANETs undermine the routing

   algorithm which lacks in adapting and responding to all these changes happening frequently in the network.

   At Present, the services that a traditional routing algorithm provides are on a verge of becoming obsolete. There is a need for an algorithm that computes various paths for communication as per the requirement and not just computes a shortest path. Computational complexity is also one of the obstacles that need to be faced while computing multiple paths for a given route. The major objectives of routing are i) To find a path from source to destination satisfying users requirements ii) To optimize network resource usage and iii)To degrade the network performance when unwanted things like congestion, path break appear in a network [3]. For the purpose of routing in WANETs, many numbers of routing algorithms have been proposed falling under the category of both reactive as well as proactive protocols. A reactive protocol is the one where the process of routing takes place only when demanded and until then the system does not perform any routing process. On the contrary, a proactive protocol is the one which constantly keeps track of the network by sending requests to the surrounding nodes and updating its tables. Proactive protocols use a lot of resources to keep track of the network hence limiting the efficiency of the network. Proactive protocols are much suitable for stable networks and reactive protocols are best when applied to the networks where the nodes are mobile and unstable. However, the stability of the WANETs are unpredictable and there is always a possibility that there is a combination of stable as well as mobile nodes in a network, hence to tackle such situations a hybrid algorithm is proposed in this paper which combines the principles of Ant Colony Optimization, Global State Routing Protocol and Zone Routing Protocol.

   The paper is structured in the following manner Section II describes the Global State Routing Protocol in detail and the Zone Routing Protocol is explained in section III. Section IV provides the understanding of the Ant Colony Optimization. Section V presents the hybrid algorithm combining the ACO, GSR and ZRP protocol and finally, Section VI contains the conclusion.

2. GSR PROTOCOL

   The Global State Routing Protocol (GSR) is a routing scheme that is MAC efficient in wireless ad hoc networks because the overhead of the control messages is kept low [2]. Similar to the link state routing mechanism, GSR keeps track of the whole network topology while avoiding the

   flooding which causes inefficiencies in the network. Each of the nodes collects the link state information and shares it periodically with the neighbouring nodes. To ensure that the link state table is up to date, GSR uses sequence numbers and these numbers are later replaced by the newer numbers as the network undergoes changes. For each node in the table, one list and three tables are maintained by the GSR. They are: a neighbour list, a topology table, a next hop table and a distance table. A neighbour list is the one which contains information about all the other nodes that are adjacent to the given node. A topology table consists of two parts-one which stores the link state information reported by the destination node and the other which stores the time at which this information was reported. A next hop table consists of the address of the next hop where the data packet has to be sent in order to take a shortest path to the destination and a distance table contains the distances from the given node to the destination node. The key difference between GSR and link state is the way routing information is disseminated. In LS, link state packets are generated and flooded into the network whenever a node detects topology changes. GSR doesnt flood the link state packets. Instead, nodes in GSR maintain the link state table based on the up to date information received from neighbouring nodes, and periodically exchange it with their local neighbours only. Information is disseminated as the link state with larger sequence numbers replaces the one with smaller sequence numbers [2].

3. ZONE ROUTING PROTOCOL

   The Zone Routing Protocol is one of the most unique protocols which use both reactive as well as a proactive approach in its routing process. Using proactive methods on large networks has its disadvantages because it uses the resources in the system to maintain the tables. Hence, to avoid this, a zone is created in the network within which proactive approach is used and to communicate with the

   To demonstrate this behaviour, let us consider the experiment shown in Figure 1. Ants travel from their nest A to their food source B in a straight line (Figure 1a). Whenever an obstacle is placed in the path of the ants, the searching process starts again from the point of the obstacle. In Figure 1b we can see that an obstacle CD is placed such that the disance ACB is less than that of the distance ADB. Now, in the beginning, the ants will choose a random path among ACB or ADB but the ants which choose the path ACB will reach the food source earlier than the other ants and they also return to their nest earlier causing more pheromone deposition on the shorter path i.e. the path ACB. Furthermore, the following ants will now choose the path ACB more often than the path ADB which will gradually lead to all the ants choosing this path (Figure 1c).

   ij

   ij

   Whenever an ant reaches a junction, it selects the next node based on the pheromone level of the paths available. Each node maintains a pheromone table rd where i is the current node, d is the destination and j is the node which is used to pass through while traversing from i to d. Hence rd is the effectiveness of the route while passing through j. At a point i, an ant select the next node j which must be used to reach the destination while travelling from i is a

   probability which is given as:

   node that lays outside of the zone a reactive approach is used. This also helps in avoiding the excess flooding done when searching for a path in the reactive approach.

   Where,

   pij

   = ((ri,j)a).( ( yi,j)/3)

   (i,k)C((ri,k)a)((yi,k)/3)

   . . . . . . (1)

4. ANT COLONY OPTIMIZATION

   Ants are one of the most well organised living creatures on the planet and they have a certain method to find the shortest path from their nest to a source of food and vice versa. While travelling from one place to another, ants leave a trail of pheromone. On the shortest path, the ant will complete more trips from the nest to the source than the other paths hence causing heavy pheromone deposition. The trail of pheromone evaporates after some time and the route which is heavily followed has high pheromone deposition. The probability that an ant will follow the route with high pheromone deposition is much higher than that of the route with low pheromone deposition. Gradually, all the ants start following the path with high pheromone deposition which is the shortest path. If there is some obstacle, the whole process is again repeated from the point of the obstacle and again a shortest path is found.

   ri,j is the pheromone intensity on the path (i, j), yi,j is the ants visibility field on the path, and are the parameters which control the relative importance of pheromone intensity compared to ants visibility and C represents the set of possible paths starting from point i [4].

5. PROPOSED ALGORITHM

   The proposed algorithm uses the Global State Routing Protocol as a proactive approach within a zone to keep track of the network. However, to communicate with the node outside of the zone, the ACO algorithm is used as a reactive approach. When a source node has to send data to a destination node, it checks whether the destination node is present in its network zone or not. If the destination node is within the zone of the source node then the source node can find a path which is stored in its tables. Now, let us consider the scenario where the source node and the destination node both lie in different zones. For such a

   scenario, the algorithm is rather complex which includes path finding phase and path maintenance phase.

   1. Path finding phase

      1. Let S and D be the source and destination nodes respectively such that they both are in different network zones.

      2. Node S has the address of the destination node D stored in its table.

      3. With the help of bordercasting process, node S sends the Route_Request packets to all the nodes that are situated on the border of the zone.

      4. The Route_Request packet contains the address of the destination node and also the route to the source node from the border node.

      5. From each of the nodes where the Route_Request packet has been sent, a forward ant (FANT) is initiated. FANT is then sent to the neighbouring nodes.

      6. The nodes which receive the FANT for the first time update their routing tables consisting of destination address, next hop and pheromone value.

      7. After updating, the node forwards the FANT to its neighbours.

      8. If the FANT reaches its destination node D, a Backward Ant (BANT) is initiated by the destination node which traverses back to the source of the FANT i.e. the border node.

      9. After the BANT reaches border node, the Route_Request packet containing the route to the source reaches the source node S.

      10. Finally a route is established from source node S to destination node D and the required data transfer can take place.

   2. Path maintenance phase

   The communication link that has been established between the source and destination is constantly monitored for a hassle free data transfer in the path maintenance phase. During the data transfer, the pheromone levels of that path automatically become high due to heavy traffic which strengthens the path. Due to the mobility of the nodes there may be failure of connection, at such situations an alternative path is used which is found during the path finding phase. Also, these alternative routes are periodically checked even when they are not in use.

6. CONCLUSION

The proposed routing algorithm combines the reactive and proactive approaches to create an efficient routing protocol. In the WANET, the nodes are not always stable. It also has limited bandwidth, limited power and an unstructured topology. Proactive methods use the network resources like bandwidth to keep their tables updated which may hamper the efficiency of a network, hence to avoid this the proactive approach is limited to a certain zone. The proposed algorithm is most effective when the data has to be transferred between two nodes which are in different network zones. In such cases, both the reactive as well as proactive approaches come into play in a combined manner. The algorithm may prove very useful where not only need to find a short path but also reliable and secure path. Even if some error occurs, an alternative path may be used, hence the algorithm is reliable.

REFERENCES

1. Nicklas Beijar, "Zone Routing Protocol (ZRP)" Networking Laboratory, Helsinki University of Technology P.O. Box 3000, FIN- 02015 HUT, Finland

2. Tsu-Wei Chen and Mario Gerla, "Global State Routing: A New Routing Scheme for Ad-hoc Wireless Networks" Computer Science Department, University of California, Los Angeles

3. Suman Banik, Bibhash Roy, Biswajit Saha and Nabendu Chaki, Design of QoS Routing Framework based on OLSR Protocol, ARTCOM 2010, Kochin, Kottyam Kerala, IEEE Explorer, pp-171-73, 2010

4. Bibhash Roy, Suman Banik, Parthi Dey, Sugata Sanyal and Nabendu Chaki, "Ant Colony based Routing for Mobile Ad-Hoc Networks towards Improved Quality of Services"