Energy Efficient Routing in Wireless Sensor Network Using Ant Colony Optimization and Firefly Algorithm

Abstract

-Energy conservation in Wireless Sensor Networks (WSN) is a crucial venture as their miniaturize nature limits their power capabilities. An effective way of energy conservation is the adoption of efficient routing of data from source to sink. This work investigates the performance of two meta-heuristic algorithms, Ant Colony Optimization (ACO) and Firefly Algorithm (FA) on optimal route detection in a WSN routing management system. An adapted ACO was used to search for optimal routes between selected source and sink nodes, after which a developed Discrete FA ran same search. Performance of both were tested on sensor networks deployed randomly, in a clustered pattern and finally randomly-clustered. Evaluators used were energy budget of reported routes. Results show that FA was able detect routes with less cost than those detected by ACO for short routes while ACO performed better with longer routes. Considering the enhanced speed of performance of ACO in comparison to FA and the local search nature of FA, it would be beneficial for future work to explore a hybridized FA-ACO algorithm.

I. INTRODUCTION

Wireless Sensor Networks (WSN) are a collection of small devices working together to capture/monitor a particular phenomenon of interest. They find useful applications in home automation, disasters and environmental monitoring, military operations, multiple target tracking, security surveillance, health services and other commercial purposes [ 1 ], [ 2 ]. Energy management in WSN is crucial as their usefulness is dependent on how long they are alive and replacement is difficult as deployment area usually is not easily accessible. As such a lot of techniques are employed to prolong their lifespan, these include topology management schemes (can be location-driven or connection driven), power management (sleep/wakeup protocols and MAC protocols), data reduction schemes (data compression and in-network processing), energy efficient data acquisition and sending (adaptive sampling, hierarchical sampling and efficient routing) and mobility based schemes (such as mobile sink and mobile relay) [ 3 ]. This work presents an investigation of efficient routing in WSN.

Routing in WSN is handled differently from what is obtainable in traditional wireless networks. This is because of the limited resources available in sensors, and as such any routing technique deployed in WSNs should minimize energy consumption and ultimately maximize network lifetime [ 4 ]. Generally the many WSN efficient routing schemes can be categorized into network structure, communication models, topology based and reliable routing schemes. The network structure protocols on which this paper is based takes into consideration how the nodes are interconnected and routes used to send data to destination from source. They are further classed into flat protocols, hierarchical protocols and location based protocols [ 5 ]. This paper investigates energy optimization of a location based routing protocol using metaheuristic algorithms.

Meta-heuristic algorithms are designed to mimic natural phenomena as they randomly search through a space for the optimum solution subject to preconfigured constraints. In this paper we use two of such algorithms, Firefly algorithm and the Ant Colony algorithm, to find the optimal path that minimizes the total energy expended in sending a data packet from source to sink. First, a review of related works is presented in section II. A description of the optimization problem and detailed report of two methods of route optimization based on each algorithm is outlined in section III. A Vehicle Routing Problem with Time Windows (VRPTW) dataset was used to test and evaluate the performance of the algorithms, after which comparison is made between the two algorithms in section IV. Section V presents the conclusions of the investigation

II. RELATED WORKS

A. Related Work on Routing Protocol in WSN

A wireless sensor network (WSN) consists of sensor nodes which are distributed around a given location. These sensors have limited energy capability to stay alive for a long period of time [ 4 ]. Although, over the years, sensors have improved in their computational capabilities, the batteries are still highly inefficient in comparison. Consequently, in an effort to extend the life of a sensor node, research has been pointed towards reducing the energy demand of the nodes. This same discrete algorithm was also applied by the authors to is obviously because the core design aspects in a WSN are solve the manufacturing cell formation problem [ 17 ]. Energy Efficiency and Reliability [ 6 ]. Energy Efficient (EE) Firefly algorithm was used for routing optimization in Routing has been mentioned in the literature as a means WSN in [ 18 ]. A novel fitness function depending on residual of extending the life of a sensor node[ 7 ]. Since energy is energy, node degree and distance was proposed, and then expended during transmission, the most energyefficient route optimized. Results showed superior performance to some during transmission will consume the least energy. This has stated existing routing algorithms. engendered EE routing protocol for WSNs. Another interesting work combined firefly algorithm with

Basically, routing protocols for WSN are classified into flat the gossip algorithm and applied it to WSN to investigate protocol, hierarchical protocol and location based Protocol time of sensor synchronization and data convergence rate [ 5 ]. In Flat protocol routing scheme, nodes are distributed [ 18 ]. The impact of hybrid algorithm was investigated on uniformly; with none performing a leading role; to transmit a live network to find out how simulation results correlate data in a cooperative manner i.e. transmitting to the next with live field applications. Conclusion drawn from results neighbor. In the case of the hierarchical scheme, nodes are obtained indicate that assumptions such as fireflies commugiven varying roles and groups known as clusters [ 8 ]. Each nicating at the speed of light and the low latency due to fast cluster must have a Cluster Head (CH) which is a node that processing speed is not applicable in a live networks where has higher capabilities than other nodes and is used to relay much higher latency is expected. A wide range of application data to the sink node. Within a distribution of nodes, there in diverse fields are presented in [ 14 ], [ 19 ]. may be many possible routes to get to a particular destination.

Mathematical models were developed in [ 9 ] to determine the C. Review of Ant Colony Optimization Related Work most energy efficient route to use in a WSN under resource An Adaptive Ant Colony Optimization (ACO) algorithm restriction. The task of determining the most energy efficient is proposed in [ 20 ] for clustering based dynamic routing in a route is a hard optimization problem [ 10 ]. Consequently, WSN. This was designed to take into consideration the unpremany meta-heuristic techniques have been developed to find dictable nature of a Wireless Sensor Network. Sensors nodes the most optimal energy efficient route. can be deployed in either a sparse or dense nature. The ACO

Artificial Bee Colony meta-heuristics algorithm [ 11 ] and finds the optimal network setting in order to improve data improved harmony search algorithm [ 12 ] were used to de- aggregation thereby reducing data redundancy. An adaptive termine the optimal energy efficient route in a WSN. An routing scheme based on ACO was also developed in [ 10 ]. Improved Genetic Algorithm was developed to eliminate the Route selection is based on the residue energy inn the nodes possibility of choosing an invalid note for routing in a WSN as well as the location of nodes. In this case, clusters were [ 13 ]. Parameters used in the node selection include nodes not used in the grouping of nodes. position in relation to sink, neighboring nodes, remaining Fuzzy logic was used in addition to ACO in [ 21 ] in a crossenergy and energy requirement. Since this research work layer WSN protocol stack to optimize routing in a WSN. To was based on using Firefly and Ant Colony optimization improve EE of the routing protocol, a multilayer approach algorithms for route optimization, the literature will be based was adopted. Nodes were grouped into clusters with cluster on them. heads which are closest to the sink. Fuzzy logic was used in the cluster head selection using metrics such as residual B. Review of Firefly Related Work energy, number of neighbors and quality of communication link for the selection. However, ACO was used for reliable and energy efficient inter-cluster routing from cluster heads to sinks.

ACO was further used to determine a multi-objective optimization i.e. energy efficiency and security of transmitted data [ 22 ] in a WSN. The factors used to carry out this include the time delay, bandwidth and the energy consumption.

Neural Network was used together with ACO to for the purpose of routing in [ 23 ]. The neural network is used to select the cluster head while ACO was used to determine best route. An ACO was used to develop an enhanced routing protocol for WSN [ 24 ] with mobility as the metric.

Firefly optimization algorithm, which is presented in more detail in section III have been used to solve several research optimizations in literature. These work include, but not limited to a wide range of issues in the field of engineering design problems, image processing, identification and clustering, and software testing [ 14 ]. A review of some of its application is hereby presented.

In [ 15 ], the authors modified the original firefly algorithm by discretizing it and applying several novel route operators to solve the Vehicle Routing Problem with Time Windows (VRPTW). Results presented showed that the developed Evolutionary Discrete Firefly Algorithm (EDFA) is promising compared to other versions of EDFAs. Another discrete firefly algorithm, using the sigmoidal logistic function is presented in [ 16 ], is used to find the optimal solution to permutation flow shop minimizing the makespan. The problem is NP-hard and formulated as a mixed integer programming.

Results revealed superior performance to the ant colony. This

III. METHODOLOGY

This section presents details about how the Firefly algorithm (FA) and Ant Colony optimization (ACO) algorithms are used to optimize the selection of energy efficient route between two nodes. The objective function used for optimization was derived from [ 9 ]. It requires finding the route with the least energy consumption and maintaining the energy limitation of the nodes. Consequently, the next section provides details about the input parameters for the developed algorithm i.e. the objective function and defined constraints. When a node wants to transmit, it searches for the most optimal route to use for the transmission. Fig. 1 shows an overview of the link between source and sink nodes. Subsequent sections provide details on the FA and the ACO techniques adopted.

The model considers multi-period transmissions from nodes and aims at prolonging the lifetime of the WSN. It is assumed that there are n number of nodes distributed randomly around an area with each node having a limited energy with an initial value of ei0. The equation for the optimization process is represented in equation 1 where ej is the energy at the next hop node.

min(X ei0

X ej )

Equation 2 is used to determine the amount of energy consumed during transmission from source to destination node. Where cw is the energy used to wake nodes for transmission and ct is the energy expended by a node to transmit to the next hop node i.e. a node directly linked. This direct transmission is constrained by a a linking distance which is a maximum distance (ld) within which nodes can transmit. Therefore, two nodes i and j that are dij distance away from each other can only communicate directly if dij<ld. Such nodes will be considered to be linked where Xij represents the connect between node i and j. Xij= 1 means there is a link between i and j otherwise, Xij = 0 this is shown in equations 3 and 4.

Eit

Eit 1 + cw X

Xijt + ct X dij Xijt = 0 dij = p(Dx[i]

Dx[j])2 (Dy[i]

Dy[j])2 where Dx is the x coordinate of the node (i or j) while Dy is the y coordinate of the node (i or j).

Xij = (1 0 dij < ld

Otherwise

Furthermore, nodes are required to have enough energy for transmission to the next hop neighbor Ei < Eij where Ei is the remaining energy in node i and Eij is the energy required to transmit from node i to next hop node j. (1) (2) (3) (4)

B. Ant Colony Optimization Algorithm

In this section, we present the use of ant colony optimization (ACO) algorithm for the selection of the optimal energy efficient route. The pheromone secreted along the selected path is based on the equation (5) which shows the inverse relationship between the deposited pheromone and the cost. '(i; j) = '(i; j) +

Q cost(k)

Where ' is the deposited pheromone, i= source node, j = destination node, k = selected ant and Q is a constant. Subsequent ants are most likely going to select the path with the most pheromone along its trail. This is represented in the equation (6)

P (i; j) =

['(i;j)] ['(i;j)] + ['(i;k)] A colony of ants (P) is generated to find possible solutions subject to the condition of least energy consumption along a selected path. The decision at each node on which path to select next is made using a Roulette Wheel Selection algorithm. The pseudocode for the ACO is shown in Algorithm 1.

Algorithm 1 Ant Colony Optimization Algorithm While termination condition is not met

For each ant k=1 to P,

Move ant(k) until it gets to destination

Compute the cost of the route using the objective function

Compare cost with best route

If lower,

overwrite best route with new route, Else

maintain best route End If (5) (6)

End For Use best route to transmit data Update pheromone trail Perform evaporation End While

C. Firefly Related Algorithm

The firefly algorithm is a highly efficient algorithm that mimics the social behavior of fireflies and was introduced in 2009 [ 25 ]. The original algorithm was formulated to solve continuous optimization problems and works based on three assumptions of the behaviors of the fireflies stated in [ 14 ]. A population of fireflies is randomly generated and each generation evaluates its fitness based on a set objective function. The fitter fireflies attract other less fit in close proximity to it. The movement of each firefly towards the fitter fly is guided by equation 7.

xt+1 = xit + 0e i 2 rij (xtj xit) + t i (7)

The first term is the position of the firefly in the subsequent round, the second term (due to attraction) is the movement towards a better firefly dependent on the distance, rij , of firefly xi to xj, the coefficient of absorption, b0 and the attraction coefficient g. The last term is the randomization parameter which determines the degree of exploitation of the search space. Detailed explanation of each parameter and setting is presented in [ 26 ].

In this work, the Firefly Algorithm was modified to handle the discrete problem of route selection. First, the fireflies search for feasible routes by using incremental dimensions (d) until a feasible route is found. This is then used to generate three initial population C1, C2, and C3 shown in equations 8, 9 and 10.

0 Pij C1 = BBB@ Pij...+1

Pin 0 Pij C2 = BB@B Pij...+1

Pin 0 Pij C3 = BB@B Pij...+1

Pin

j Pi+1 Pij++11 . .

.

Pin+1

j Pi+1 Pij++11 . .

.

Pin+1

j Pi+1 Pij++11 . .

.

Pin+1

P j 1 Pdj+21 d 2 C ... ACC P n

d 2 P j 1 Pdj+11 d 1 C ... CAC P n d 1

Pdj 1 Pdj...+1 CCCA P n d

In the matrices, n i s the number of fireflied, each value P2f1,2......Ng and N is the number of sensors. Luster C1 and C2 search for routes shorter and longer than the feasible route while C3 searches for route of same length. The three clusters were the fed to the firefly algorithm for final test, with a retest of teh C1 and C2 for a feasible route. Two fitness functions were then used to initiate movement in fireflies and perform the search for the best firefly, ffg n(x) and g(x). See equations 11and 12.

fi(x) = E(Pi ! Pi+1) g(x) = d 1 X E(Pi ! Pi+1) i=1 where i=1,2,......No. of iterations and is set not less than the dimension of each population

f i(x) is the energy expended by Pi in sending data to Pi+1 for iteration i. and g(x) is the total energy expended along a route.

The pseudocode of the modified firefly and parameter setting is shown in Algorithm 2. (8) (9) (10) (11) (12)

Algorithm 2 Pseudocode for Firefly Algorithm Initial population of n fireflies x(t)=[x 1,x 2. . . . . . ..x d] Divide population into 3 clusters Generate objective function fn(x), Generate objective function g(x) Light intensity Ii determined by g(x) Define light absorption coefficient For k=1:n

While (t<MaxGeneration),

If g(k ) = inf

Mutate k to new k using b0=0, and b0=1, for invalid and valid nodes for each x (i ) respectively.

Each x (i )moves probabilistically towards the valid nodes closest to it.

If g(new k) < g(best k) best k = new k

End If

End If

End While End for k Report best k as final route Post process results and visualization

IV. RESULTS AND DISCUSSION

The developed algorithms were tested using VRPTW dataset with 100 nodes being considered. Source and sink nodes were selected at random and the algorithms are tasked with finding a route with the least possible energy consumption i.e. Cost. The number of iterations for the algorithm were set at 200, 150, 100 and 50. The results were observed to determine which algorithm performed best as the number of iterations increased. Furthermore, 1000 individuals were considered for both Algorithms and 3 different VRPTW datasets were considered namely: the Random (R1), Clustered (C1) and Random-Clustered (RC1). The values for the constraints of the objective function are shown in Table I. The results obtained are shown in Tables II, III and IV.

For the randomly distributed sensors, the results show that as the number of iterations increased, the performance of Ant Colony Optimization (ACO) increased while that of Firefly Algorithm (FA) remained same (See Table II). FA performed better than ACO in finding routes under the random dataset. It therefore can be inferred that for problems where the solutions are randomly distributed in a search space, FA would be the recommended algorithm to use.

In the clustered scenario, it was observed that as the number of iterations increased, FA quickly converged towards the best observed route while ACO converges slowly towards the same route. This is shown in Table III. The performance of FA was therefore, better than ACO in finding routes in the clustered dataset.

The performance of ACO improved in the RandomClustered dataset and even performed better than FA in finding long routes. It can also be seen from Table IV that both ACO and FA have improved performance as the number of iteration increases.

Furthermore, it should be noted that both ACO and FA algorithms are statistical in nature thus they often provide different results after a number of runs. Therefore, the algorithms were subjected to multiple iterations. Even though FA performed generally better than ACO, it should be noted that there were also numerous instances where ACO performed better than FA in discovering an energy efficient route.

V. CONCLUSION

In this paper, an investigation into the performance of two meta-heuristic algorithms for energy efficient route discovery was presented. These algorithms are the Firefly Algorithm (FA) and the Ant Colony Optimization (ACO) Algorithm. VRPTW dataset was used to generate nodes to be deployed in a Wireless Sensor Network (WSN) setting and the algorithms are to find the best route that costs the least amount of energy to transmit data. It can be seen from the results presented that FA performed better than ACO in discovering short routes while ACO performed better than FA in discovering long routes. Furthermore, it was observed that ACO was faster at detecting the routes in comparison to FA. This speed can be attributed to the local search nature of FA which is not applicable in the applied ACO algorithm. Consequently, it is suggested that future works should explore equipping ACO with local search functionality in order to enhance its performance. Therefore, applying a hybridized FA-ACO algorithm with a WSN deployment is proposed.

References

[1] A.-B. Garc ´ıa- Hernando , J.-F. Mart ´ınez- Ortega , J. -M. Lo ´pez- Navarro , A. Prayati , and L. Redondo-Lo´pez, Problem Solving for Wireless Sensor Networks , vol. 58 of Computer Communications and Networks. London: Springer London, dec 2008 .

[2] M. Saidu , E. Onwuka, M. Okwori , and A. Umar , “ An Enhanced LEACH Routing Algorithm for Energy Conservation in A Wireless Sensor Network ,” International Journal of Wireless and Microwave Technologies , vol. 6 , pp. 59 - 71 , jul 2016 .

[3] G. Anastasi , M. Conti , M. Di Francesco, and A. Passarella , “ Energy conservation in wireless sensor networks: A survey,” Ad Hoc Networks , vol. 7 , pp. 537 - 568 , may 2009 .

[4] N. A. Pantazis , S. A. Nikolidakis , and D. D. Vergados , “ EnergyEfficient Routing Protocols in Wireless Sensor Networks: A Survey,” IEEE Communications Surveys & Tutorials , vol. 15 , pp. 551 - 591 , jan 2013 .

[5] V. K. Arora (Research Scholar), V. Sharma , and M. Sachdeva , “ A survey on LEACH and other's routing protocols in wireless sensor network ,” Optik - International Journal for Light and Electron Optics , vol. 127 , pp. 6590 - 6600 , aug 2016 .

[6] N. Z. Zenia , M. Aseeri , M. R. Ahmed , Z. I. Chowdhury , and M. Shamim Kaiser , “ Energy-efficiency and reliability in MAC and routing protocols for underwater wireless sensor network: A survey , ” Journal of Network and Computer Applications , vol. 71 , pp. 72 - 85 , aug 2016 .

[7] S. Singh , “ A Survey on Energy Efficient Routing in Wireless Sensor Networks ,” International Journal of Advanced Research in Computer Science and Software Engineering Research , vol. 3 , no. 7 , pp. 184 - 189 , 2013 .

[8] L. Guo , W. Wang , J. Cui , and L. Gao , “ A Cluster-Based Algorithm for Energy-Efficient Routing in Wireless Sensor Networks ,” in 2010 International Forum on Information Technology and Applications , vol. 2 , pp. 101 - 103 , IEEE, jul 2010 .

[9] J.-h. Lee and I. Moon , “ Modeling and optimization of energy efficient routing in wireless sensor networks , ” Applied Mathematical Modelling , vol. 38 , pp. 2280 - 2289 , apr 2014 .

[10] X. Wang , Q. Li , N. Xiong , and Y. Pan , “ Ant Colony OptimizationBased Location-Aware Routing for Wireless Sensor Networks,” in Wireless Algorithms , Systems, and Applications, pp. 109 - 120 , Berlin, Heidelberg: Springer Berlin Heidelberg, 2008 .

[11] A. A. A. Ari , B. O. Yenke , N. Labraoui , I. Damakoa, and A. Gueroui , “ A power efficient cluster-based routing algorithm for wireless sensor networks: Honeybees swarm intelligence based approach , ” Journal of Network and Computer Applications , vol. 69 , pp. 77 - 97 , jul 2016 .

[12] B. Zeng and Y. Dong , “ An improved harmony search based energyefficient routing algorithm for wireless sensor networks , ” Applied Soft Computing , vol. 41 , pp. 135 - 147 , apr 2016 .

[13] G. Yao , Z. Dong , W. Wen , and Q. Ren , “ A Routing Optimization Strategy for Wireless Sensor Networks Based on Improved Genetic Algorithm,” Journal of Applied Science and Engineering , vol. 19 , no. 2 , pp. 221 - 228 , 2016 .

[14] X.-S. Yang , “Firefly Algorithms,” in Nature-Inspired Optimization Algorithms , pp. 111 - 127 , Elsevier, 2014 .

[15] E. Osaba , R. Carballedo , X.-S. Yang , and F. Diaz , “ An Evolutionary Discrete Firefly Algorithm with Novel Operators for Solving the Vehicle Routing Problem with Time Windows,” in Studies in Computational Intelligence , vol. 637 , pp. 21 - 41 , 2016 .

[16] M. K. Sayadi , R. Ramezanian , and N. Ghaffari-Nasab , “A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems ,” International Journal of Industrial Engineering Computations , vol. 1 , pp. 1 - 10 , jul 2010 .

[17] M. K. Sayadi , A. Hafezalkotob , and S. G. J. Naini , “ Firefly-inspired algorithm for discrete optimization problems: An application to manufacturing cell formation , ” Journal of Manufacturing Systems , vol. 32 , pp. 78 - 84 , jan 2013 .

[18] P. Lalwani , I. Ganguli , and H. Banka , “FARW : Firefly Algorithm for Routing in Wireless Sensor Networks ,” pp. 248 - 252 , IEEE, 2016 .

[19] I. Fister , X. S. Yang , and J. Brest , “ A comprehensive review of firefly algorithms , ” Swarm and Evolutionary Computation , vol. 13 , pp. 34 - 46 , 2013 .

[20] Z. Ye and H. Mohamadian , “ Adaptive Clustering based Dynamic Routing of Wireless Sensor Networks via Generalized Ant Colony Optimization,” IERI Procedia , vol. 10 , pp. 2 - 10 , 2014 .

[21] S. Gajjar , M. Sarkar , and K. Dasgupta , “FAMACRO: Fuzzy and Ant Colony Optimization Based MAC/Routing Cross-layer Protocol for Wireless Sensor Networks,” Procedia Computer Science , vol. 46 , no. Icict 2014 , pp. 1014 - 1021 , 2015 .

[22] Zhong Luo , Liuzheng Lu, Jianqun Xie, and Jinrong He, “ An ant colony optimization-based trustful routing algorithm for wireless sensor networks , ” in 2015 4th International Conference on Computer Science and Network Technology (ICCSNT) , pp. 1128 - 1131 , IEEE, dec 2015 .

[23] T. Li , F. Ruan , Z. Fan , J. Wang , and J.-U. Kim, “ An Improved PEGASIS Protocol for Wireless Sensor Network,” in 2015 3rd International Conference on Computer and Computing Science (COMCOMS) , pp. 16 - 19 , IEEE, oct 2015 .

[24] M. Umadevi and M. Devapriya , “ An Enhanced Ant Colony Based Approach to Optimize the Usage of Critical Node in Wireless Sensor Networks,” Procedia Computer Science , vol. 47 , no. C, pp. 452 - 459 , 2015 .

[25] X.-S. Yang , “Firefly Algorithms for Multimodal Optimization, ” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , vol. 5792 LNCS, pp. 169 - 178 , 2009 .

[26] S. Arora and S. Singh , “ The Firefly Optimization Algorithm : Convergence Analysis and Parameter Selection ,” International Journal of Computer Applications , vol. 69 , no. 3 , pp. 48 - 52 , 2013 .