Design and Implementation of ACO Algorithm for WSN and MANETs

Design and Implementation of ACO Algorithm for WSN and MANETs

Dr. Nataraj K. R1, Shilpa G D2

1 Head of the Department, Electronics and Communication Engineering, SJB Institute of Technology,

Bangalore-560060

2 Electronics and Communication Engineering, SJB Institute of Technology, Bangalore-560060

Abstract: In wireless sensor networks (WSNs), energy consumption is crucial. Routing plays a very high role for energy optimization, as taking less hop numbers usually leads to a better performance. The main goal of this paper is to provide a routing algorithm that is simple to understand and implement. Ant Colony Optimization (ACO) which is inspired from self- organizing behavior of ants which fall under swarm intelligence. In this paper we proposed an optimal ACO routing algorithm for wireless sensor networks (WSN) and Mobile Ad-Hoc Network (MANETs). Node deployment algorithm, Route discovery algorithm and best route algorithm are demonstrated. A comparison of previous Ant-F and ACO algorithm is made based on the parameters such as route discovery time, number of hops, total energy consumption and total power consumption and which shows that proposed algorithm is better compared to previous approach.

Keywords WSN; MANET; Swarm Intelligence; Ant-F; Ant Colony Optimization.

1. INTRODUCTION

   The increasing demand for wireless mobile communication, especially in situations where traditional infrastructure communication networks do not exist or were destroyed, has encouraged the appearance of the infrastructure less Mobile Ad hoc Networks commonly referred to as (WSNSs). WSNSs enable the communication of mobile (nodes) without the aid of any physical central point of communication. The nodes in WSNSs may be mobile devices like: laptops, palmtops or mobile-phones. WSNSs are multi-hop, self-organized and decentralized networks. The dynamic nature of WSNSs provides many challenges that require extensive research in order to provide a satisfying performance to their mobile users.

   In this paper Swarm intelligence is used which involves a collective behavior of autonomous agents that locally interact with each other in a distributed

   environment to solve a given problem [1]. The idea of Swarm intelligence is to design algorithms inspired by the collective behavior of insects such as bees, termites, ants and other animal societies that exist in decentralized, self-organized systems. These insects live in a hostile, dynamic environment. They communicate directly with one another or indirectly through the environment to accomplish their essential tasks such as foraging, labor division, nest building or brood sorting.

   Figure 1 shows a scenario in which at first the ants follow two different paths in searching the food while depositing a substance called pheromone on their path. Other ants are able to smell this pheromone and it influences the choice of their paths as they tend to follow stronger pheromone concentrations. The best route between two choices is chosen by the ants after a while.

   Figure 1: All ants take the shortest path after an initial searching time.

2. METHODOLOGY

   The previous ANT-F routing algorithm leads to long routing path (containing many hops). Since in this method the path length of the route discovered is very high this in turn will add up to cumulative power consumption there by energy consumption is also increased. To find an optimal path from source to destination and to achieve better performance compared to ANT-F an ACO algorithm is proposed [2].

   The proposed method algorithm includes the following modules.

   • Node deployment

   • Route discovery process

   • Best route selection (node level criteria, network level criteria)

   1. NODE DEPLOYMENT

      This module is responsible to distribute the nodes in an environment. It takes number of nodes and distance between nodes as input and it generates the grid topology.

      shown in Figure 3, picks the intermediate node in such a way that it is closest to the destination and farthest from the source node.

   2. Route Discovery Process

      The route discovery process is responsible for finding multiple ANT-F routes from source node to destination node. Route Discovery is based on PRP (Purely ANT-F Propagation) [1], but it improves the propagation efficiency by recording the nodes traversed so far. The sensor node maintains the neighbor list. When source wants to send shares to the sink, it initializes the TTL to initial value N and unicasts the share to the random neighbor. After receiving the share, each neighbor decrement the TTL. Specifically, Route Discovery adds a node-in-route (NIR) field to the header of each share. Initially, this field is empty. Starting from the source node, whenever a node propagates the share to the next hop, the id of the upstream node (which is the previous hop) is appended to the NIR field. Nodes included in NIR are excluded from the ANT-F pick at the next hop. This Route Discovery guarantees that the share will be relayed to a different node in each step of ANT-F propagation, leading to better propagation efficiency.

      The route discovery process used in ACO algorithm is shown in Figure 2. When the TTL becomes zero, the final node receiving this share stops the random propagation of this share and starts routing using Min- Hop routing. The minimum hop routing algorithm

      Figure 2: ACO Route Discovery Process

      Figure 3: Min-hop routing algorithm.

   3. Best Route Selection Algorithm

   This algorithm is responsible for picking the best route from source node to destination node with respect to number of hops, delay and energy efficiency [6]. The set of multiple routes obtained from route discovery process

   are subjected to node level test where the battery power of individual nodes is determined. If any of the nodes have their current battery power less than threshold then the route is completely discarded. From the set of non eliminated routes it will find a best route which has maximum goodness ratio. The following equations are used for finding the goodness factor.

   Input: Number of nodes=64 Distance between nodes=10 Output: Topology Information

   E( p) i * v *t p

   (1)

   t p [

   ph

   6 *106

   • pd ] 54 *106

   (2)

   Et ( p) 280 * v *t p Er ( p) 240 * v *t p E(ni ) Et Er Eo E(Rj ) h(Rj ) * Er

   n

   D(R j ) d (ni , ni1 )

   i1

   (3)

   (4)

   (5)

   (6)

   (7)

   Figure 4: Node Deployment Algorithm Output

   g(R j ) E(R j

   Where,

   ) * D(R j

   M

   ) /

   i1

   E(R j

   ) * D(R j )

   (8)

   III.B ACO Routing Output

   Figure 5 shows the best route among a set of non- eliminated routes as the goodness ratio of this route

   i current of the node

   v voltageof the node

   t p packet transmit time

   is the maximum.

   Input: Source Node=2, Destination Node=45 TTL=4, Coverage Area=30,

   Ph length of Pd length of

   packet header data payload

   Power for Transmission=1w, Environmental Factor=0.5,

   Data Payload= This is ACO Routing.

   Et energy required for transmission

   Er energy required for reception Eo energy required for hearing h(Rj ) number of hops in the route g(Rj ) goodness ratio of the route D(Rj ) end to end delay of route

3. RESULTS AND DISCUSSION

   The results are obtained using a MATLAB simulator tool which is licensable software. The simulation results o all modules are shown below.

   III.A NODE DEPLOYMENT ALGORITHM

   The Node Deployment Algorithm output is shown in Figure 4, which shows the 64 nodes deployed in 8*8 grid matrix. Each node is numbered between 1 and 64.

   Figure 5: Best Route Selected

   1. COMPARISON WITH TIME

      The comparison of ANT-F routing with ACO is shown in the Figure 6. ACO takes less route discovery time as compared to ANT-F routing.

      Figure 6: Time Comparison

   2. COMPARISON WITH POWER AND NUMBER OF HOPS CONSUMED

   Figure 7 shows the comparison of ANT-F routing with ACO algorithm in terms of power consumption. As seen from figure the ACO algorithm takes less power as compared to ANT-F. As seen from Figure 8, the ACO algorithm takes less number of Hops as compared to ANT-F in finding destination node.

   Figure 7: Power Comparison

   Figure 8: Number of hops consumed

4. CONCLUSION

In this work, we proposed an Ant Colony Optimization algorithm to find the best route from source node to destination node. The various algorithms namely Node Deployment Algorithm., Route Discovery Algorithm and Best Route Election Algorithms are discussed. The previous ANT-F and proposed ACO algorithm are simulated using MATLAB 7.10.0. A comparison of both the algorithms is made based on the parameters route discovery time, number of hops, total energy consumption and total power consumption. The proposed algorithm provides advantages over both time, as well as power as compared to existing ANT-F routing algorithm.

REFERENCES

1. Sudarshan D Shirkande and Rambabu A Vatti, ACO Based Routing Algorithms for Ad-hoc Network (WSN, MANETs): A Survey, IEEE International conference on Communication Systems and Network Technologies, 2013, DOI: 10.1109/CSNT. 2013.56, pp. 230-235.

2. Yingzhuang Liu, Hong Zhang, Qiang Ni, Zongyi Zhou and Guangxi Zhu, "An Effective Ant-Colony Based Routing Algorithm for Mobile Ad-Hoc Network", IEEE International Conference on Circuits and Systems for Communications, 2008, ICCSC 2008, 4th volume, pp.100-103.

3. Xiao-Min Hu and Jun Zhang, "Ant routing optimization algorithm for extending the lifetime of wireless sensor networks", IEEE International Conference on Systems Man and Cybernetics (SMC), Oct 2010, pp.738-744.

4. Dorigo M, Birattari M and Stutzle T, "Ant colony optimization," IEEE International Conference on Computational Intelligence Magazine, Nov2006, vol.1, no.4, pp. 28-39.

5. L.M. Feeney, "An energy consumption model for performance analysis of routing protocols for mobile ad hoc networks", Mobile Networks and Applications, 2001,pp.239-249,

6. L.M. Feeney and M. Nilsson, "Investigating the energy consumption of a wireless network interface in an ad hoc networking environment", In Proceedings of IEEE INFOCOM, 2001.

7. N. Nie and C. Comaniciu, "Energy efficient AODV routing in cdma ad hoc networks using beam forming", EURASIP J. Wireless Communication Networks, 2006, pp. 14-24.

8. Cui Y, Xue Y and Nahrstedt K, "A Utility-Based Distributed Maximum Lifetime Routing Algorithm for Wireless Networks",

   .IEEE Transactions on vehicular technology, 2006, pp. 797-800.

9. R. Shah and J. Rabaey, "Energy aware routing for low energy ad hoc sensor networks", IEEE International Conference on Wireless Communications and Networking, 2002, vol. 1, pp. 350-355.

10. K. Pappa, A. Athanasopoulos, E. Topalis, and S. Koubias, "Implementation of power aware features in AODV for ad hoc sensor networks a simulation study", IEEE Conference on Emerging Technologies and Factory Automation ETFA, Sept 2007, pp.1372- 1375.