Fitness (F) = i=1….m+1
Length of path
Length of initial path
Maximum length of all m+1 path
International Journal of Scientific & Engineering Research, Volume 5, Issue 3, March-2014 436
ISSN 2229-5518
Artificial Bee Colony (ABC) Algorithm with ECDH Algorithm for Finding Optimal Path and Secure Data Transfer
V.Deeban Chakravarthy, S.Sivarajan, N.Gayathiri
Abstract— In a dynamic network, routing is a very challenging because of the topology of the network is not fixed. This paper involves Artifi- cial Bee Colony (ABC) Algorithm for finding shortest path in a dynamic mesh networks. The ABC optimization algorithm is a population-based search algorithm which applies the concept of social interaction to problem solving. The ABC algorithm is inspired by the collective behavior of bees to find better food sources around the hive and this biological phenomenon when applied to the process of path planning problems, it is found to be an excelling in solution quality as well as in computation time. The effectiveness of the paths has been evaluated with the parame- ters such as tour length, bee travel time by using Artificial Bee Colony (ABC) Algorithm. Thus the pursued approach gives the best result for finding the shortest path in a shortest time for moving towards the goal in more effective way. Then the data is transfer securely by using ECDH algorithm in this optimal path.
Index Terms— Routing, Path planning, Shortest path, Artificial Bee Colony (ABC) Algorithm, ECDH Algorithm.
—————————— ——————————
N wireless mesh network, routing is a major problem be- cause of the dynamic nature of the nodes in the network. Thus finding the shortest path and sending the data with more optimal one in a wireless mesh network is difficult. There are many routing algorithms and approaches that are used to find the shortest path but, the path that are given by those algorithms and approaches may not be optimal and
more feasible.
Many approaches had certain limitations such as inef-
ficiency in solving larger scale combinational and/or highly
nonlinear problems and their inflexibility to adapt the solution
algorithm to a given problem. Thus a given problem is mod-
eled in such a way that a classical algorithm has to make sev-
eral assumptions which might not be easy to validate in many
situations. So that the interest of the scientific community
switched to the intelligent techniques such as Genetic Algo-
rithms, Swarm Intelligence approaches. Many of the research-
es are inspired by the nature to develop new algorithmic mod-
els to solve different problems especially in the field of opti-
mization.
A branch of nature inspired algorithm which are
known as Swarm Intelligence are focused on insect behavior
so as to develop some meta-heuristic which can imitate the
way insects used to solve their problems. Bonabeau has de-
fined swarm intelligence as any attempt to design algorithms
or to the distributed problem solving devices which is inspired
by the collective behavior of social insect colonies and other
• Deeban chakaravarthy.V , Assistant Professor in Computer Science and Engineering in SRM University, India,PH-9003387773,E-mail : vdeeban@gmail.com.
• Sivarajan.S is currently pursuing Master of Engineering degree program in
Computer Science and Engineering in SRM University, India, PH-
9629723010. E-mail: sivaavis226@mail.com
• Gayathiri.N is currently pursuing Master of Engineering degree program in
Computer Science and Engineering in Anna University, India, PH-
9944159805. E-mail: gayubhagya7@mail.com
animal societies. Swarm Intelligence consists of many algo- rithms such as Ant Colony Optimization, Particle Swarm Op- timization, Wasp Nets and Fish Schools.
C.W. Alm and R.S.Ramakrishna have proposed an approach using a genetic algorithm to the shortest path routing prob- lem. This GA based shortest path algorithm exhibits a much better quality of solution (i.e., the route optimality) and a much higher rate of convergence than other algorithms. A population-sizing equation that facilitates a solution with the desired quality was also developed.
A.W. Mohemmed et al. have proposed a PSO-based search algorithm for a priority-based indirect path-encoding scheme is used to widen the scope of the search space and a heuristic operator is used to reduce the probability of invalid loop creations during the path construction procedure. It was claimed that the PSO-base shortest path algorithm is superior to those using GAs. However, all these algorithms address only the static shortest path problem. When the node mobility occurs, the network topology changes, they will consider it as a new network and restart the algorithms over the new topol- ogy.
S. Aravindh et al. have proposed a hybrid of Ant colony optimization algorithm and Genetic algorithm for routing in packet switched data networks. An Ant algorithm is found to reduce the size of routing table where else the Genetic algo- rithm cannot use the global information of the network. Hence, the combination of ACO and GA algorithms, which makes the packets to explore the wireless mesh network inde- pendently and helps in finding path between pair of nodes effectively.
IJSER © 2014 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 3, March-2014 437
ISSN 2229-5518
Artificial bee colony (ABC) algorithm is an optimization algo- rithm based on the intelligent behavior of honey bee foraging. This is a population based optimization technique which was first introduced by Dervis Karabonga in 2005, and is based on inspecting the behaviors of real bees on finding nectar amounts and sharing the information of food sources to the other bees in the hive. These specialized bees try to maximize the nectar amount stored in the hive by performing efficient division of labor and self-organization.
The honey bees from the colonies that are extended over a very long distance, in order to exploit the food sources in a multiple directions. The nectar sources with large amount of nectar that can be extracted with minimum difficulty are visited by more number of the bees while the nectar sources with less amount of nectar are discarded. The foraging begins by the scout bees which are sent to collect nectar. The search starts randomly by the scout bees from one source to another. When the scout bees reach the hive, they deposit the amount collected and goes to the dance floor to perform waggle dance. This type of dance is the sole medium of communicating the information about the most promising nectar source to all oth- er bees in the hive. This mysterious dance contains three piec- es of information about the source: direction in which it is found, distance from the hive and the quality of nectar. When the food source exists at a distance less than 50 meters, then the scout bees perform round dance. On the other hand, if the food source exists at a distance greater than 50 meters, then the bees perform waggle dance.
After watching the waggle dance, unemployed bees (onlooker bees) follow the scout bee to promising nectar source to collect nectar. This waggle dance process helps all the bees to collect nectar in efficient and faster way. The quali- ty of food source is continuously monitored by the bees so as to propagate this information in the next waggle dance. The three agents in Artificial Bee Colony are:
The Employed Bee
The Onlooker Bee
The Scout Bee
The employed bees are associated with the specific food sources, the onlooker bees watching the dance of employed bees within the hive to choose a food source, and the scout bees searching for food sources randomly. The onlooker bees and the scout bees are the unemployed bees. Initially, the scout bees will discover the positions of all food sources, thereafter, the job of the employed bee starts. Artificial employed bees would probabilistically obtain some modifications on the posi- tion in its memory to target a new food source and find the nectar amount or the fitness value of the new source. Later, the onlooker bee evaluates the information taken from all artificial employed bees and then chooses a final food sources with the highest probability related to its nectar number. If the fitness value of the new one is higher than the previous one, then the bee forgets the old one and memorizes the new position. This is called as greedy selection process. Then the employed bee whose food source has been exhausted becomes a scout bee to search for the further food sources once again.
In ABC, the solutions represent the food sources and the nectar quantity of the food sources corresponds to the fitness of the associated problem. The number of employed and on- looker bees is same, and this number is equal to the number of food sources. Employed bees whose solutions cannot be im- proved through a predetermined the number of trials that was specified by the user of the ABC algorithm and called “limit”, become scouts and their solutions are abandoned.
In this algorithm, the employed bee produces a modifica- tion in the position (i.e. solution) in its memory and checks the nectar amount (fitness value) of that source (solution). The employed bee then evaluates this nectar information (fitness value) and then chooses the food source with the probability related to its fitness value.
Fitness (F) = i=1….m+1
Length of path
Length of initial path
Maximum length of all m+1 path
(1)
: Probability of selecting the 
employed bee.
S : No. of employed bees
: Position of the 
employed bee. F(
) : The fitness value
(2)
: Position of the onlooker bee t : Iteration number
: Randomly chosen employed bee j : Dimension of the solution
: Series of random variables in the range [1,1]
(3)
r : random number and rand ϵ[0,1]
The general method of the ABC algorithm is as follows: Bee Initialization Phase
Set the Loop Employed Bee Phase Onlooker Bee Phase Scout Bee Phase
Memorize the best solution found
Until the loop is terminated
The pseudo-code for the ABC Algorithm is,
IJSER © 2014 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 3, March-2014 438
ISSN 2229-5518
1: Load training samples
2: Generate the initial population
3: Evaluate the fitness value
4: set cycle to 1
5: repeat
6: FOR each employed bee { Produce new solution Calculate the fitness value
Apply greedy selection process}
7: Calculate the probability values
8: FOR each onlooker bee {
Select a solution depending on the probability values
Produce new solution
Calculate the fitness value
Apply greedy selection process}
9: If there is an abandoned solution for the scout bee
Then replace it with a new solution which is randomly
produced by (step 7)
10: Memorize the optimal solution
11: cycle=cycle+1
12: Until cycle=MCN
The essential control parameters in the Artificial Bee Colony Algorithm are the number of food sources which is equal to the number of employed/ onlooker bees (Colony Size), the working to onlooker bee rate, the value of the limit (L) and the number of cycles or the number of iterations (MCN) that are required to terminate the program.
Start
Memorize best solution
Update working bees
Cycle=cycle+1
Cycle=MCN End
Fig.1 Flowchart of ABC algorithm
The implementation of Artificial Bee Colony algorithm for solving shortest path problem is explained with the help of flow-char shown in fig.1. The control parameters are set in the initialization phase such as colony size, iteration number (bee travel time), the working to onlooker bee rate. By computing the probabilities, the bees will work and draw the next node to obtain the path and memorize the best solution found so far using greedy selection process. Finally the bees become scout bees and the number of working bees is updated, that is the employed bee which is exhausted becomes the scout bee again. The optimization loop is terminated when the numbers of iterations are completed and the best result is obtained.
Along with ABC Algorithm, ECDH algorithm is used for se- cure and reliable data transfer. The algorithm goes secure for- warding of packet to destination posture of the node. It con- sists of the following steps, Key Generation, Key Exchange, and Encryption/Decryption.
Set control parameters
Obtain no. of locations
Initialize the working bees
Network formation f
Generate key
Key estab- lishmentt
Packet Encryp- tion
Set Cycle=1
Route discovery
Reset the path
Pre-compute the start nodes of bees
Construct the new paths for bees
Compute the step probabilities
Compute fitness
IJSER © 2014 http://www.ijser.org
Check authen- tication
International Journal of Scientific & Engineering Research, Volume 5, Issue 3, March-2014 439
ISSN 2229-5518
Route mainte-
Decrypt packet
Fig 2: Flowchart of ECDH
Data Pro- cessing
nal of Global Research in computer Science, 3(1),January 2012, 31-34, ISSN-2229-371X.
[5] Yousra Ahmed , Routing using Genetic Algorithm for large network,
Diyala Journal of Engineering Sciences, 3(2), 55-70, ISSN- 1999-8716. [6] K.Vijayalakshmi, S.Radhakrishnan, Dynamic Routing to multiple
destination in IP networking using Hybrid Genetic Algorithm (DRHGA), International Journal of Information Technology, Vol 4, No 1, PP 45-52.
[7] D.Karaboga, Artificial Bee Colony Algorithm, Scholarpedia 2010,
i)A generates its private key nA and calculates its public key ,
PA= nA * P. ii) B generates its private key nB and calculates its
public key , PB= nB * P.
computes it’s shared key , k=nB * PA.
C)Encryption/Decryption :A sends cm (2 cipher texts=kG,Pm +
kPB ) and B decrypt the message using different shared key.
formed, by positioning the nodes. Generation of keys and the
key is established by using the Elliptic Diffie-Hellmann key
exchange algorithm.
Authentication is checked between the nodes. The en-
cryption and decryption of the message is also done by ECC
algorithm. Finally the discovered route is maintained in the
networks.
In this paper, Artificial Bee Colony algorithm is presented by considering a new approach. The Artificial Bee Colony Algo- rithm can be used to solve several optimal problems. It is aimed to minimize the length of the tour and find the optimal path. The Artificial bee colony algorithm is highly flexible and can be effectively used to find shortest path by considering very few control parameters as compared with the other heu- ristic algorithms. The Future scope might incorporate the comparative study of Artificial Bee Colony (ABC) Algorithm with the other optimization algorithms to find more optimal solutions with ECDH Algorithm for secure data transfer.
It’s my immense pleasure to thank my Guide and Mentor for his earnest efforts and incessant support throughout my pro- ject accomplishment.
[1] E.Bonabeau, M.Dorigo, G.Theraulaz, Swarm Intelligence: From Nat- ural to Artificial System, Oxford University press, NY,1999.
[2] T.Xiang, X.Liao, K.W.Wong, An improved particle swarm optimiza-
tion algorithm combined with piecewise linear chaotic map, Applied
Mathematics and Computation 190,1637-1645,2007.
[3] Yu Bin, An improved ant colony optimization for vehicle routing problem, European Journal of Operational Research 196,171-
176,2009.
[4] S.Aravindh, G.Michael, Hybrid of Ant Colony Optimization and
Genetic Algorithm for shortest path in wireless mesh network, Jour-
5,6915. Avaliableonline://www.scholarpedia.org/article/Artificial_bee_colon y_algorithm.
[8] D.Karaboga, An idea based on honey bee swarm for numerical opti- mization, Erciyes University, Kayseri,Turkey, Thenical Report- TR06,
2005.
[9] D.Karaboga, B.Akay, A comparative study of artificial bee colony algorithm, Applied Mathematics and Computation 214, 108-132,2009.
[10] D.Karaboga, A Combinational Artificial Bee Colony Algorithm for
Traveling Salesman Problem, IEEE Transactions, 50-53, 2011.
[11] Ashita S.Bhagade, Artificial Bee Colony (ABC) Algorithm for Vehicle Routing Optimization Problem, International Journal of Soft Compu- ting and Engineering (IJSCE), 2231-2307, Volume 2, Issue 2, May
2012.
[12] W.Tsai, J.S.Pan, B.Y.Liao, Enhanced artificial bee colony optimiza- tion, International Journal of Innovative Computing, Information and Control, Vol 5, No 12, 2009.
[13] P.Curkovic, B.Jerbic, Honey bees optimization algorithm applied to path planning problem, International Journal of Simulation Model- ing, PP.137-188,2007.
IJSER © 2014 http://www.ijser.org