A Hybrid ACO-PSO Based Clustering Protocol in VANET PDF

A hybrid ACO-PSO based clustering protocol in VANET J.Amudhavel K.Prem Kumar A. Monica Department of CSE, SMVEC Department of CSE, SMVEC Departmen...

A hybrid ACO-PSO based clustering protocol in VANET J.Amudhavel K.Prem Kumar A. Monica Department of CSE, SMVEC Department of CSE, SMVEC Department of CSE, SMVEC Pondicherry, India Pondicherry, India Pondicherry, India [email protected] [email protected] [email protected] B.Bhuvaneshwari S.Jaiganesh S.Sampath Kumar Department of CSE, SMVEC Research scholar Department of ECE, MIT Pondicherry, India Department of CS, R&D Centre Pondicherry, India [email protected] Bharathiar University [email protected] Coimbatore, India [email protected] ABSTRACT and it creates an ad-hoc network between the vehicles for the VANET means vehicular ad-hoc network. The routing protocol communication between the vehicles. It also includes the ant colony optimization (ACO) is a swarm intelligence which is communication among the road side units. The main goal of based on the behavior of the ant, the ACO algorithm includes the VANET is to ensure the road safety. The type of cooperation and adaption and it produces an optimal communicationin VANET is vehicle to vehicle (v2v), vehicle to solution.ACOalgorithm depends upon the amount of pheromone infrastructure (v2i), vehicle to roadside (v2r) and in hybrid model deposit. The particle swarm optimization is also swarm v2v and v2i, v2v and v2r. VANET is large scale and this suit for intelligence, the PSO algorithm is population based and depends the cars because cars move at very high speed and they often upon the movement and the intelligence of the swarm. The changes their locations.Intelligent VANET is shortly known as pheromone value is used for the decision purpose. The benefit of InVANET. This technology comprised of lots of technologies particle swarm optimization technique is that the particle moves such as Wi-Fi IEEE 802.11p, wave IEEE 1609, Bluetooth, and always in the same direction with the same velocity and it also IRA. The main use of the VANET is to control the traffic. There selects the position that is better than the previous position thus are lots of protocols in VANET to find the fastest path to reach the best path is followed by each particle. In PSO the set of the destination. The network in VANET is an Ad-hoc network. potential solutions evolves to approach a convenient solution for a The vehicle which comes into the network is considered as one of problem. This algorithm produces Global best (Gbest) and the node in the network, the network is about 100 to 300 meters. Personal best (Pbest) solution. The benefits of the ACO and PSO Another important thing in VANET is reliable message passing. protocols are combine have a hybridACO-PSOalgorithm to have To find the location the GPS is used along with VANET. In this an optimal solution to a multicast network and thus it helps in paper two routing protocols are used to improve the clustering. clustering. One of them is ACO which means ant colony optimization. Ant colony optimization algorithm is a swarm intelligent method in Categories and Subject Descriptors which the network is considered as a graph and the best path to C. [Computer Systems Organization ]: C.2 [COMPUTER- reach the destination is determined. Ant moves in a random COMMUNICATION NETWORKS ], C.2.1 [ Network manner in search of their food and while they return, they try to Architecture and Design ] eject the pheromone trails. This pheromone act as a key for the other ants, if any ants finds the pheromone they stop their move in General Terms random and start to travel in the path of the pheromone deposit. Performance, Design, Standardization, Theory. When an ant wants to find a path where there is more number of pheromone deposit, it select the path which has the larger Keywords pheromone deposits. Another routing protocol is Particle swarm Ant colony optimization(ACO), Particle swarm optimization. PSO is a powerful optimization technique which is optimization(PSO), Vehicular Ad-hoc network(VANET). precisely based upon the movements and intelligence of swarms. This technique was originally developed for social interaction of 1. INTRODUCTION problem solving and involves a number of particles or agents VANET means vehicular ad-hoc network. It is a subclass of which describes swarm that moves around the search space for MANET. In VANET the vehicles are considered as a mobile node best solution. Thus each agent constitutes as a point in N- dimensional space that adjust its flying and its own experience on Permission to make digital or hard copies of all or part of this work for others as well. Each particle co-ordinate position will corresponds personal or classroom use is granted without fee provided that copies are to a best candidate solution which is achieved by that particle is not made or distributed for profit or commercial advantage and that called Personal best (Pbest). This has another value were tracking copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be the neighbourhood particle is called Global best (Gbest). These honored. Abstracting with credit is permitted. To copy otherwise, or two concepts lies in the accelerating the agents towards its Pbest republish, to post on servers or to redistribute to lists, requires prior and Gbest positions and also it should have a random weighted specific permission and/or a fee. Request permissions accelerations at each step. Thus each agent or particle modifies its from [email protected]. own position by the following conditions: ICARCSET '15, March 06 - 07, 2015, Unnao, India Copyright 2015 ACM 978-1-4503-3441- 9/15/03…$15.00 http://dx.doi.org/10.1145/2743065.2743090  2.2.1 Discrete PSO This is shortly called as DPSO. This PSO is an approach to solve the grid job scheduling [7, 8, 19]. In this method the particles are  Current positions needed to have a sequence of job in the grid machine. It is also used to handle the discrete binary variables.  Current velocities  Distance between current position and personal best 2.2.2 MINLP PSO  Distance between current position and global best This can handle both discrete binary variables and continuous variables. In this method the given problem is divided into parts ACO-PSO this hybrid protocol is used in case of multicast tree. such as siting planning model and capacity planning model [9, 10]. By this method the no. of search is reduced and thus the time 2. VARIENTS OF ACO AND PSO complexity is reduced. 2.1 Ant colony optimization (ACO) 2.2.3 Hybrid PSO Ant colony optimization is a technique in which the problem This model combines any technique with the PSO. This network is considered as a graph and the best path to reach the utilizes fundamental mechanism of PSO and extends selection destination is obtained. In ant colony optimization [1, 2] the mechanism, which is utilized by EC method such as GA’s. behavior of the ant is considered. The ant moves in a random fashion in search of its food. On it return to its home, it starts to 3. MOTIVATION emit a substance called as pheromone. The other ant which found The time complexity in the ACO [14, 15, 16] algorithm is seems this emission of pheromone follows the same path to reach the to be more and in some cases it also includes the worst case destination. When more number of paths is found then the ant scenario. The PSO algorithm still suffers from finding a follows the path where there is large amount of pheromone solution to the crossovers and also for the mutation because they deposit. need internal velocity for themselves and memory.PSO algorithm 2.1.1 Elitist ant system fails to communicate between two clusters. The proposed This system is to strength the searching in an ant system. This clustering algorithm are still not been implemented for the inner system includes the procedures such as diversification and cities. intensification techniques. But the drawback in this system is the time taken by the system is more (i.e. the number of search made in this system is more). B D 2.1.2 Max min ant system This system allows only the best solutions and it uses the greedy E search technique. This system allows only the solution that is Source best to add the pheromone at the time of pheromone update. In addition this system avoids the premature convergence of search. Destination 2.1.3 Rank based ant system This system is much better than the other system in case of average behavior and it also considers the worst case behavior also. In this system the solutions are measured based on the C F length. The amount of the pheromone deposit is weighed. The path that is having more amount of pheromone is called as the shortest path where the path which is having less amount of Figure 1. Shortest path finding in ACO pheromone deposit is called as longest path to reach the destination. 2.1.4 Continuous optimization ant colony This system is for solving the continuous optimizations in an effective way. In this method the orthogonal design is followed. Using this design the ant can select their region very rapidly and more effectively. 2.1.5 Recursive ant colony This system is better than the all the above mentioned system. In this system the parameter functions are need not to be initialized. The result of this algorithm is sharper. This system runs the nested ant system to increase the precision of the output. 2.2 Particle Swarm Optimization (PSO) PSO is a technique which uses the movement and the intelligence Intial stageFinal stage of the swarm. In this each particle is considered as a point in N- Figure 2. Optimal solution finding in PSO dimensional space and the particle adjusts its flying based on its flying experience and also based on the experience of others. 4. CONTRIBUTION There are lots of clustering protocols available in VANET. To best of our knowledge this paper is seemed to be the first survey on the clustering protocol since the existing algorithm doesn’t focuses on the clustering data. The concept of hybrid ACO and PSO [17, 18] combines the advantage of both ACO algorithm and PSO algorithm. The solution obtained in this method seems to have a lesser time complexity [25, 26] than the other method proposed. In future we would like to implement clustering to the inner cities using hybrid ACO- PSO based clustering [21, 22, 23, 24] protocol. 5. HYBRID ACO AND PSO ALGORITHM The ant colony optimization is a method in which the given network is considered as graph and the problem is to find out the best path to reach the destination. The particle swarm optimization is method which is based on the movements and intelligent swarm movement. The hybrid ACO-PSO is used to solve the multicast tree. In ACO algorithm, the pheromone plays a vital role. This algorithm is used to perform behavior coordination and also for communication. These processes are done with the help of the pheromone. The PSO algorithm is used for the behavior coordination as in ACO but it includes interaction between the agents. The major advantage of PSO algorithm is that a global optimal solution is obtained. Thus the ACO and PSO algorithms are combined to have an optimization on the solution in the multicast network. The main purpose of this algorithm is to overcome the drawbacks of both ACO and PSO algorithm. By this method the time complexity is reduced. The advantage of the hybrid ACO-PSO is that the pattern generated is feasible for any large number. If the value of the pheromone deposit is minimum means it gives the best attribute value as well as the best pattern. In addition updating the particle velocity will switch to relevant position. 6. APPROACH OF HYBRID ACO-PSO Figure 3.A hybrid ACO-PSO based clustering MODEL FOR CLUSTERING IN VANET In this algorithm the pheromone levelis used which is plays a vital role in ant colony optimization technique and the personal best, global best solutions are used which plays a vital role in particle swarm optimization. The path that has the maximum Pheromone 7. PROPOSED HYBRID ACO-PSO BASED level indicates the best pathto be followed by the ants. The Gbest and Pbest is used to find the optimal solution. Thus the MODEL FOR CLUSTERING IN VANET combination of these things provides us the best path which can The proposed model insists the use of hybrid ACO-PSO model to be used by the vehicles so that they can reach the destination as enhance the clustering in VANET. The benefit of the ACO is fast as possible. There are lots of drawbacks in the already combined with the benefits of PSO. The result obtained using ant existing clustering protocols. Thus to improve the performance of colony optimization technique is improved by the particle swarm the clustering protocol this approach is proposed. As a first step in optimization technique. Initially the position of the vehicle which this method each particle is initialized with the random position. enters into the ad-hoc network is initialized with random position. Secondly the values for Gbest and Pbest of the particles are The Gbest and Pbest values for the vehicles are initialized. And initialized. The Gbest is initialized with the particle which is less the vehicles position is obtained as a partial solution. Then update fit in the swarm. Then initialize each particle in the random the path which is most often used by the vehicles. Again evaluate position. The partial solution will be obtained then continue with the position of the vehicles. Thus a random pattern is generated. the updation of the pheromone level. This steps are proceeded for Also update the Gbest and Pbest values of each vehicle. Then the number of nodes in the network. Thus we obtain a solution. To check for the Gbest value. After comparison either assign the strengthen the obtained result the techniques of particle swarm Pbest value as Gbest or assign Gbest value as g. Finally update the optimization is applied. So find the fitness of the particles. If the position of each vehicle using the Pbest value. Thus this model result obtained is Gbest then that is the final result else continue to improves the clustering in VANET. The proposed model has less find the fitness of the particle. time complexity.  9. Challenges faced in ACO and PSO The problem in this algorithm is that simulation of the problem as graph and optimizing it. And also the developing of code for these problems is also difficult task. Mostly the result of this algorithm is seems to less optimal. Tendency to a fast and premature in mid optimum points. Slow convergence in refined search stage (weak local search abilities).Values for minimum and maximum objective function which fails to satisfy the constraints. 10. CONCLUSION This paper proposes a hybrid ACO-PSO based protocol and aims to improve the clustering. The benefit of the ant colony optimization is that it selects the best path by means of greedy method or with the level of energy. The pheromone value is used for the decision purpose. The benefit of particle swarm optimization technique is that the particle moves always in the same direction with the same velocity and it also selects the position that is better than the previous position thus the best path is followed by each particle. And the particle always follows the best neighbourhood direction. But the fault in PSO algorithm is that it fails to communicate between two clusters and in ACO algorithm the time consumption is too long. So the benefits of the ant colony optimization and particle swarm optimization are combined. In this method a random pattern is generated. And the pattern generated in this method is feasible and the pheromone minimum value provides the best pattern and the personal best, global best solutions are obtained. The main advantages of this paper is that the updating of the velocity of the particle plays a vital role in relevant positioning and also the time complexity is Figure 4. Proposed hybrid ACO-PSO for clustering reduced. 11. REFERENCES S. Bououden, M. Chadli, H.R. Karimi, ―An ant colony 8. VISION optimization-based fuzzy predictive control approach for 8.1 Selection nonlinear processes‖, Information Sciences, Volume 299, 1 The selection of the next node is most important in find out the April 2015, Pages 143-158, ISSN 0020-0255. best solution. The ant selects the next node based on the energy Amudhavel, J, Vengattaraman, T, Basha, M.S.S, level of the neighboring nodes. The energy level represent the Dhavachelvan, P, ―Effective Maintenance of Replica in amount of pheromone deposit. The path which has the more Distributed Network Environment Using DST‖, International pheromone deposit is considered as the shortest path. Conference on Advances in Recent Technologies in 8.2 Pheromone value Communication and Computing (ARTCom) 2010, vol, no, pp.252,254, 16-17 Oct. 2010, doi: The selection in ant colony optimization directly depends on the 10.1109/ARTCom.2010.97. pheromone level. The pheromone values are saved for the future decision i.e. selecting the next node based on the current node. T.A. Sebaey, C.S. Lopes, N. Blanco, J. Costa, ―Ant Colony Shortest path is decided based on the pheromone value. Optimization for dispersed laminated composite panels under biaxial loading‖, Composite Structures, Volume 94, Issue 1, 8.3 Inertia December 2011, Pages 31-36, ISSN 0263-8223. This makes the particle move in the same directions and with the Hossein Hemmatian, Abdolhossein Fereidoon, Ali Sadollah, same velocity. The inertia directly affects the convergence, Ardeshir Bahreininejad, ―Optimization of laminate stacking exploitation and exploration in the process of PSO. sequence for minimizing weight and cost using elitist ant system optimization‖, Advances in Engineering Software, 8.4 Personal influence Volume 57, March 2013, Pages 8-18, ISSN 0965-9978. Personal influence is one of the three factors in particle swarm optimization. It improves the individual particle by making them Thomas Stützle, Holger H. Hoos, ―MAX–MIN Ant System, to select the previous position based on the current position. Future Generation Computer Systems‖, Volume 16, Issue 8, June 2000, Pages 889-914, ISSN 0167-739X. 8.5 Social influence: Jing Xiao, LiangPing Li, ―A hybrid ant colony optimization It is also one of the factor in particle swarm optimization. Social for continuous domains‖, Expert Systems with Applications, influence is important because it makes the particle tofollow the Volume 38, Issue 9,September 2011, Pages 11072-11077, best neighbourhood direction. ISSN 0957-4174. Manuel Costeira da Rocha, João Tomé Saraiva, ―A discrete evolutionary PSO based approach to the multiyear  transmission expansion planning problem considering P. Dhavachelvan, G.V. Uma, V.S.K.Venkatachalapathy demand uncertainties‖, International Journal of Electrical (2006), ―A New Approach in Development of Distributed Power & Energy Systems, Volume 45, Issue 1, February Framework for Automated Software Testing Using Agents‖, 2013, Pages 427-442, ISSN 0142-0615. International Journal on Knowledge –Based Systems, Raju, R, Amudhavel, J, Pavithra, M, Anuja, S, Abinaya, B, Elsevier, Vol. 19, No. 4, pp. 235-247, August 2006. ―A heuristic fault tolerant MapReduce framework for Juan Rada-Vilela, Mark Johnston, Mengjie Zhang, minimizing makespan in Hybrid Cloud Environment‖, ―Population Statistics for Particle Swarm Optimization: International Conference on Green Computing Hybrid Methods in Noisy Optimization Problems‖, Swarm Communication and Electrical Engineering (ICGCCEE) and Evolutionary Computation, Available online 17 February 2014, vol, no, pp.1,4, 6-8 March 2014, doi: 2015, ISSN 2210-6502. 10.1109/ICGCCEE.2014.6922462. M. Basu, ―Modified particle swarm optimization for Luo Yiqing, Yuan Xigang, Liu Yongjian, ―An improved nonconvex economic dispatch problems‖, International PSO algorithm for solving non-convex NLP/MINLP Journal of Electrical Power & Energy Systems, Volume 69, problems with equality constraints‖, Computers & Chemical July 2015, Pages 304-312, ISSN 0142-0615. Engineering, Volume 31, Issue 3, 19 January 2007, Pages Zahra Beheshti, Siti Mariyam Shamsuddin, Shafaatunnur 153-162, ISSN 0098-1354. Hasan, ―Memetic binary particle swarm optimization for discrete optimization problems‖, Information Sciences, Sandeep Kaur, Ganesh Kumbhar, Jaydev Sharma, ―A Volume 299, 1 April 2015, Pages 58-84, ISSN 0020-0255. MINLP technique for optimal placement of multiple DG units in distribution systems‖, International Journal of Xin-She Yang, Chapter 7 –―Particle Swarm Optimization, In Electrical Power & Energy Systems, Volume 63, December Nature-Inspired Optimization Algorithms‖, edited by Xin- 2014, Pages 609-617, ISSN 0142-0615. She Yang, Elsevier, Oxford, 2014, Pages 99-110, ISBN 9780124167438. Raju, R, Amudhavel, J, Kannan, N, Monisha, M, ―A bio inspired Energy-Aware Multi objective Chiropteran Hamid Reza Arkian, Reza Ebrahimi Atani, Atefe Pourkhalili, Algorithm (EAMOCA) for hybrid cloud computing Saman Kamali, ―Cluster-based traffic information environment‖, International Conference on Green Computing generalization in Vehicular Ad-hoc Networks‖, Vehicular Communication and Electrical Engineering (ICGCCEE) Communications, Volume 1, Issue 4, October 2014, Pages 2014, vol, no, pp.1,5, 6-8 March 2014, doi: 197-207, ISSN 2214-2096. 10.1109/ICGCCEE.2014.6922463. Madhuja Bhaumik, Suparna DasGupta, Soumyabrata Saha, Manoj Kumar Patel, Manas Ranjan Kabat, Chita Ranjan ―Affinity Based Clustering Routing Protocol for Vehicular Tripathy, ―A hybrid ACO/PSO based algorithm for QoS Ad hoc Networks‖, Procedia Engineering, Volume 38, 2012, multicast routing problem‖, Ain Shams Engineering Journal, Pages 673-679, ISSN 1877-7058. Volume 5, Issue 1, March 2014, Pages 113-120, ISSN 2090- Rasmeet S Bali, Neeraj Kumar, Joel J.P.C. Rodrigues, 4479. ―Clustering in vehicular ad hoc networks: Taxonomy, Oscar Castillo, Evelia Lizárraga, Jose Soria, Patricia Melin, challenges and solutions‖, Vehicular Communications, Fevrier Valdez, ―New approach using ant colony Volume 1, Issue 3, July 2014, Pages 134-152, ISSN 2214- optimization with ant set partition for fuzzy control design 2096. applied to the ball and beam system‖, Information Sciences, B. Hassanabadi, C. Shea, L. Zhang, S. Valaee, ―Clustering in Volume 294, 10 February 2015, Pages 203-215, ISSN 0020- Vehicular Ad Hoc Networks using Affinity Propagation‖, Ad 0255. Hoc Networks, Volume 13, Part B, February 2014, Pages Jaqueline S. Angelo, Heder S. Bernardino, Helio J.C. 535-548, ISSN 1570-8705. Barbosa, ―Ant colony approaches for multiobjective Raju, R, Amudhavel, J, Kannan, N, Monisha, M, structural optimization problems with a cardinality ―Interpretation and evaluation of various hybrid energy constraint‖, Advances in Engineering Software, Volume 80, aware technologies in cloud computing environment — A February 2015, Pages 101-115, ISSN 0965-9978. detailed survey‖, International Conference on Green Mohammad Ali Jan Ghasab, Shamsul Khamis, Faruq Computing Communication and Electrical Engineering Mohammad, Hessam Jahani Fariman, ―Feature decision- (ICGCCEE) 2014, vol, no, pp.1,3, 6-8 March 2014, doi: making ant colony optimization system for an automated 10.1109/ICGCCEE.2014.6922432. recognition of plant species‖, Expert Systems with T. Vengattaraman, S. Abiramy, P. Dhavachelvan, R. Applications, Volume 42, Issue 5, 1 April 2015, Pages 2361- Baskaran (2011), ―An Application Perspective Evaluation of 2370, ISSN 0957-4174. Multi-Agent System in Versatile Environments‖, International Journal on Expert Systems with Applications, Elsevier, Vol. 38, No. 3, pp. 1405-1416.