International Journal of Computational Intelligence Systems

Volume 10, Issue 1, 2017, Pages 1263 - 1271

Hybrid Firefly Variants Algorithm for Localization Optimization in WSN

Authors
P. SrideviPonmalarsridevi_ponmalar@yahoo.co.in
Faculty of Information and Communication, College of Engineering Guindy, Chennai, India
V. Jawahar Senthil Kumarveerajawahar@gmail.com
Department of Electronics and Communication Engineering, College of Engineering Guindy, Chennai, India
R. Harikrishnanrhareish@gmail.com
School of Electrical and Electronics Engineering, Sathyabama University, Chennai, India
Received 1 March 2017, Accepted 8 July 2017, Available Online 24 July 2017.
DOI
10.2991/ijcis.10.1.85How to use a DOI?
Keywords
Localization; Genetic Algorithm; Differential Evolution; Particle Swarm Optimization; Firefly; WSN
Abstract

Localization is one of the key issues in wireless sensor networks. Several algorithms and techniques have been introduced for localization. Localization is a procedural technique of estimating the sensor node location. In this paper, a novel three hybrid algorithms based on firefly is proposed for localization problem. Hybrid Genetic Algorithm-Firefly Localization Algorithm (GA-FFLA), Hybrid Differential Evolution-Firefly Localization Algorithm (DE-FFLA) and Hybrid Particle Swarm Optimization -Firefly Localization Algorithm (PSO-FFLA) are analyzed, designed and implemented to optimize the localization error. The localization algorithms are compared based on accuracy of estimation of location, time complexity and iterations required to achieve the accuracy. All the algorithms have hundred percent estimation accuracy but with variations in the number of fireflies’ requirements, variation in time complexity and number of iteration requirements.

Copyright
© 2017, the Authors. Published by Atlantis Press.
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

Smart and pervasive systems require sensor nodes for surveillance and controlling various physical parameters of the environment. Sensor node can sense the data, process, store and communicate to the next level of hierarchy and finally to the sink for which the information is required [1].

Several sensor nodes are interconnected in a particular topology depending on the applications which are called as Wireless Sensor Networks (WSN). Localization in WSN is a procedural method for finding position information of the sensor nodes. In most of the applications, the sensed data becomes meaningful only when the data has location information embedded to it [2]. The application of wireless sensor networks includes environmental monitoring, animal habitat monitoring, precision agriculture, water quality, forest fire detection and pollution monitoring, military surveillance, health care monitoring, mine and underground applications [3]. The location information can be found by global positioning system (GPS). Attaching GPS for every sensor node is not practically viable. Moreover, it is bulky and requires more energy, which is not feasible for energy constraint sensor node [4]. Localization in wireless sensor nodes can be centralized or distributed based up on the processing of location information. In centralized processing the location information is processed centrally in cluster head or base station. In distributed processing the location information is processed in the individual sensor node. So the processing is distributed in the network [5]. This reduces the communication between the hops. So the lifetime and reliability of the sensor node and in turn for the wireless sensor networks is improved. Distributed algorithms are classified in to range based or range free algorithms. Range based include angle of arrival (AOA) technique, radio signal strength indicator (RSSI) technique and time difference of arrival (TDOA) techniques [6]. Range free algorithms uses neighborhood and hop counting techniques. The proposed hybrid algorithms uses radio signal strength indicator and follows trilateration method [7] as shown in Fig. 1.

Fig. 1.

Trilateration Method

WSN localization is mapped as error optimization problem, were error is minimized. Analytical methods are not suitable for solving complex problems. As the complexity increases the computation also increases [8]. For resource constraint sensor nodes, where the memory and computation resource is less, the analytical methods are not suitable [9]. Therefore, nature inspired algorithm, which is computationally efficient are used for complex optimization problems. Nature inspired algorithms has the ability to describe complex relationships and find a solution with simple initial conditions and with minimum or no data available [10].

This work proposes 3 nature inspired hybrid algorithms for optimization of localization error. In Genetic Algorithm Firefly Localization algorithm (GA-FFLA), the firefly algorithm is hybrid with genetic algorithm for better accuracy and less computation. Mutation process of differential evolution (DE) can be included in firefly localization algorithm (FFLA) to improve the performance. In DE-FFLA, the firefly algorithm is hybrid with differential evolution. In Particle Swarm Optimization Firefly Localization Algorithm (PSO-FFLA), FFLA is hybrid with particle swarm optimization (PSO). Movement process used in the firefly algorithm is carried out by the velocity function of PSO to estimate the best location information.

The hybrid algorithms are analyzed, designed, implemented and compared with respect to location estimation accuracy and time complexity.

2. Related Work

The sensor nodes coordinate and cooperate to fulfill the requirements of the applications. Wireless sensor networks (WSN) not only collect the data but can also process data for intelligent decision making.WSN connect the physical environment with intelligent digital environment.

For event detection and tracking application, the data sensed may not be useful if WSN can’t provide the location information of the sensor nodes [11]. In applications such as animal habitat monitoring, surveillance of bush fire, precision agriculture and water quality monitoring the data sensed by WSN becomes meaningless without location information. Localization information of sensor nodes enables the application like road traffic monitoring, inventory management, commercial and social surveillance and security, health monitoring and intrusion detection. For event management and tracking applications like tracking patients and doctors in hospitals, public safety systems, product tracking in warehouse, remote product quality assessment, fire and flood monitoring and control, crop quality monitoring, soldier and mine tracking systems etc., the localization information is mandatory. The localization technique has to be developed and the accuracy of estimation of location information has to be optimized [12][13][14][15].

In [16] Delaunay triangulation and smoothing algorithm is introduced for determining the node location , where the sensor nodes has to be deployed for air pollutant monitoring and warning systems. About 13.7 % of recent scientific publications involves wireless sensor networks based localization aspects and target tracking [17]. In [5] different measurement techniques like AOA, RSSI, profiling techniques and TDOA are discussed. This work also proposes one hop and multi hop localization algorithm, connectivity based and distance based localization algorithms.

Efficient localization and optimization of localization is much needed for efficient performance of WSN and to improve the lifetime of WSN. In [7] connectivity localization algorithm, centroid localization algorithm, energy attenuation localization algorithm, region overlap localization algorithm, bionics localization algorithm, verification localization algorithm, landmark placement localization algorithm, landmark upgrade localization algorithm, localization algorithm, geometric localization algorithm, path planning localization algorithm, time localization algorithm and probability distribution localization algorithm are discussed and future research directions in localization are suggested.

In [18] localization algorithms based up on Monte Carlo method, convex method and geometric constraints methods are discussed. In [19] centralized localization techniques and distributed localization techniques such as approximate point in triangle, DV hop, multi hop, centroid and gradient techniques are reviewed. In [20] a localization objective function has been defined and a closed neighbor time of arrival grid algorithm has been introduced to minimize the objective function. In [21] another localization objective function has been defined and a Davidson least squares algorithm has been introduced to minimize the objective function.

Paper [8] proposed bio inspired algorithm namely particle swarm optimization and bacterial foraging optimization for wireless sensor networks localization optimization. Paper [9] discusses the application of computational intelligence techniques for wireless sensor networks. In particular GA and PSO has been proposed for wireless sensor network localization.

In [10] a survey of different bio inspired optimization algorithms such as GA, genetic programming, DE, evolution strategy, paddy field algorithm, group search optimizer, PSO, ant colony optimization, fish swarm algorithm, bacterial foraging algorithm, firefly, intelligent water drop algorithm, invasive weed colony optimization, artificial immune system algorithm, biogeography based optimization, and symbiotic PSO algorithm were done.

Localization in WSN is mapped as error optimization problem, were error is minimized by using proposed nature inspired hybrid algorithms namely GA-FFLA, DE-FFLA, and PSO-FFLA.

3. Localization problem modeling

A total of 50 nodes are taken within the solution space. In which 10 are the landmarks nodes for the location information in known priori and the remaining 40 are sensor nodes for which the location has to be formed. Using trilateration method, the location of 40 sensor nodes are estimated by using the 10 landmarks nodes location information.

This type of estimation follows two steps. First step is the distance calculation and next one is the position estimation. The distance calculation is carried out by using the expression

dist=((yactylandmark)2+(zactzlandmark)2)

The position estimation is carried by using the expression

f(Yu,Zu)=[(YestYlandmark)2+(ZestZlandmark)2dist]2
Yact,Zact

- actual Y and Z position of sensor node respectively.

Yest,Zest

- estimated Y and Z positions respectively of sensor node which does not know the location.

Ylandmark,Zlandmark

- anchor or landmark, Y and Z position respectively.

Above “Eq. (2)” is the objective function for the optimization localization error in WSN. The location error is minimized by using three different hybrid algorithms to achieve better accuracy of estimation. The localization optimization algorithms proposed are Hybrid GA-FFLA, Hybrid DE-FFLA and Hybrid PSO-FFLA.

4. Firefly Localization Algorithm

Dr.Xin-She Yang developed firefly algorithm in the 2007 [22]. The proposed algorithm uses firefly algorithm technique.

Fireflies emit lights to attract their prey for food, survive from predators, and discover mates. The objective function of localization is from the flashing light of fireflies. The techniques of firefly algorithm are simple to develop and easy to implement [23].

FFLA uses following conditional behavioral set up by fireflies [24].

  1. 1.

    Fireflies, irrespective of sex, attracted by brighter fireflies.

  2. 2.

    The attractiveness decreases with distance and increases with brightness. Firefly move randomly, when there are no brighter fireflies.

  3. 3.

    Using “Eq. (2)”, firefly light intensity is estimated.

The formulation of FFLA is carried out as follows. First firefly algorithm mapped to node localization. In solution space of 100, 20 fireflies are considered as localization variables the brightness of firefly is estimated by “Eq. (2)”.

Next attractiveness is calculated using “Eq. (3)”. Attractiveness is the process of movement of pth firefly to brighter qth firefly.

A(d)=A0*exp(γdm)withm>>1
d

– attraction distance among 2 firefly.

A0

- attractiveness (d=0)

γ

- Absorption parameter.

Distance of attraction is calculated using “Eq. (4)

dpq=((apaq)2+(bpbq)2)
dpq

- distance of pth firefly from qth firefly in 2D space.

Next process is the firefly movement towards the brightest firefly. Depending on the attractiveness and distance, the movement is given by the “Eq. (5)

mpk+1=mpk+Ao*exp(γd2)*(aqkapk)+*randpk
mpk

- Initial position of pth firefly

Ao*exp(γd2)*(aqkapk)

- Attractiveness component.

*randpk

- Random component.

The above processes are repeated for100 iterations or convergence is achieved which is the stopping criterion. The brightest firefly position is the estimated optimal location value of the sensor node.

5. Hybrid Genetic Algorithm-Firefly Localization Algorithm (GA-FFLA)

GA is good optimization algorithm to minimize the error but it is inferior to eliminate this error [25]. Hence GA is used to course tune or find near location of unknown nodes. Firefly is good for fine tuning but the drawback is time consuming. It is not effective for search in very large solution space. So, GA is used to estimate near location and hence it reduces the boundary size for Firefly to search. Firefly finds the exact location in this reduced solution space thereby it eliminates the error. This hybrid reduces the time consumption of firefly since it is restricted to search in small solution space. GA used to reduce this solution space boundary and performs course tuning [26].

The procedure for hybrid GA and firefly localization algorithm to solve localization problem in wireless sensor network is given below. Initial population is crucial for localization this initial population is randomly generated within the boundaries by GA.

GA performs course tune to estimate unknown nodes. The unidentified unknown nodes positions are estimated using fine tune of firefly. The final result of course tuned by GA becomes initial population of firefly algorithm.

Following is the design procedure for Hybrid GA-FFLA.

  • Step 1: NP-number of chromosomes is generated in the constraint solution space. Where, NP is number of population. Each chromosome has 2-genes, the first one is x-position, and second one is y-position of unknown node.

  • Step 2: Roulette wheel selection is used to find mating parents among the NP-population. Then form mating pool for fittest parents.

  • Step 3: Single point cross over is done on the parent chromosomes in the mating pool.

  • Step 4: Mutation of genes in the population is carried out based on mutation probability.

  • Step 5: GA performs course tune to estimate unknown nodes using step-2 to step-4 repeatedly until it reaches maximum number of iteration.

  • Step 6: The final population of course tuned by GA becomes initial population of firefly algorithm.

  • Step 7: Using “Eq. (2)”, estimate brightness.

  • Step 8: Using “Eq.(3)” ,calculate attractiveness

  • Step 9: Using “Eq.(4)” ,calculate distance

  • Step 10: Using “Eq. (5)”, calculate movement

  • Step 11: Select the global best among the fireflies.

  • Step 12: Until stopping criterion repeat steps 7 to 11.

  • Step 13: Location value of sensor node is estimated.

Design consideration for hybrid GA-FFLA is recorded in the Table 1.

Parameters (Localization) Tuned Values
Maximum No. Of Iterations 100
Space size 99
No. of land marks 10
No. of unknown node 40
No. of total node 50
No. of fireflies 20
Random coefficient(α) 0.2
Attractiveness (d=0),Ao 1.0
Absorption parameter(γ) 0.96
Cross over constant(GA) 0.7
Mutation(GA) 0.1
Table 1

Hybrid GA-FFLA design parameters

6. Hybrid DE-FFLA

DE is random search algorithm which is simple and easy to implement for optimization experiments. DE has the property of parallel operability, consistent convergence and uses less control parameters [27]. The operations carried out for DE-FFLA is mapping node localization with DE minimization optimization, mutation process, recombination process followed by selection process [27].

In DE, mutation process gets more importance compare to cross over. Mutation creates diversity in solution and variation in the parameter involve to achieve best results with lesser time. Depending on objective function value estimated, selection of target vector is made, which is further mutated as per “Eq. (6)

Utmutated=Ubest+S*(TVRV)
U t=

mutated vector.

U best=

best solution.

T v=

target vector position.

S=

scaling factor = 0.7

R v=

random selection.

Mutation process of DELA is combined with the process of firefly algorithm that involves firefly flashing light intensity or the brightness calculation, attractiveness process and movement process, to derive the Hybrid DE-FFLA.

Hybrid DE-FFLA estimates brightness for firefly using “Eq. (2)”. Following is the design procedure for hybrid DE-FFLA.

  • Step 1: For sensor node localization fireflies are the set of control variables

  • Step 2: 20 fireflies are initialized.

  • Step 3: Using “Eq. (2)”, estimate brightness.

  • Step 4: Using “Eq.(3)”, calculate attractiveness

  • Step 5: Using “Eq.(4)” ,calculate distance

  • Step 6: Using “Eq. (5)”, calculate movement

  • Step 7: Using “Eq.(6)”, mutation process is carried out.

  • Step 8: Select the global best among the fireflies

  • Step 9: Until stopping criterion repeat steps 4 to 8.

  • Step 10: Location value of sensor node is estimated.

Design consideration for hybrid DE-FFLA is recorded in the Table 2.

Parameters (Localization) Tuned Values
Maximum No. of Iterations 100
Space size 99
No. of land marks 10
No. of unknown node 40
No. of total node 50
No. of fireflies 20
Random coefficient(α) 0.2
Attractiveness (d=0),Ao 1.0
Absorption parameter(γ) 0.96
Scaling factor, S (DE) 0.7
Table 2

Hybrid DE-FFLA design parameters

7. Hybrid Particle Swarm Optimization-Firefly Localization Algorithm (PSO-FFLA)

J. Kennedy, R.C. Eber hart and Y. Shi introduced PSO, a swarm intelligent algorithm in 1995 [28]. PSO is inspired by bird flocking foraging behavior. The PSO algorithm comprised of set of agents (particle) that constitute a particle swarm moving around the solution space looking for the best solution. Depending on the experience of the particles each particle in search space adjusts its flying, and then move towards a global optimum position. The velocity equation of particle swarm optimization is given by the “Eq. (7)” [29],

uk(t+k)=w`.uk(t)+A1.r1.(pbZkk(t))+A2.r2.(gbZkk(t))

Where

ẁ=

initial weight.

uk(t + k)

=new velocity.

A1. A2=

constant weight factor.

pb =

particle best known location.

gb =

best location known to the swarm.

r1, r2

=generate a uniformly random variable.

uk(t)=

velocity of the particle k at time t

Zkk(t)=

position of the particle k at time t

The movement process in firefly localization algorithm is carried out by the PSO velocity function, to derive the Hybrid PSO-FFLA.

Hybrid PSO-FFLA estimates brightness for firefly using “Eq. (2)”. Following is the design procedure for hybrid PSO-FFLA.

  • Step 1: For sensor node localization fireflies are the set of control variables

  • Step 2: 20 fireflies are initialized.

  • Step 3: Using “Eq. (2)”, estimate brightness.

  • Step 4: Using “Eq.(3)”, calculate attractiveness

  • Step 5: Using “Eq.(4)” ,calculate distance

  • Step 6: Use PSO velocity “Eq.(7)” to move pth firefly towards qth firefly.

  • Step 7: step 4 to 6 is repeated for all fireflies

  • Step 8: Until stopping criterion repeat steps 3 to 7.

  • Step 10: Location value of sensor node is estimated.

Design consideration for hybrid PSO-FFLA is recorded in the Table 3.

Parameters (Localization) Tuned Values
Maximum No. Of Iterations 100
Space size 99
No. of land marks 10
No. of unknown node 40
No. of total node 50
No. of fireflies 20
No. of vector 20
Random coefficient(α) 0.2
Attractiveness (d=0),Ao 1.0
Absorption parameter(γ) 0.96
acceleration co-efficient A1,A2 (PSO) 1.2
weight ẁ (PSO) 0.3
Table 3

Hybrid PSO-FFLA design parameters

8. Result analysis

The three nature inspired hybrid algorithms namely GA-FFLA, DE-FFLA, PSO-FFLA, were analyzed and implemented to estimate the location information of the sensor node

Table 4 provides a performance comparison of the 3 nature inspired hybrid algorithms. Output of the three Hybrid algorithms GA-FFLA, DE-FFLA, PSO-FFLA based on number of Fireflies are shown in the Fig. 2 to Fig. 6.

Fig. 2.

Output for 20 Fireflies

Fig. 3.

Output for 18 Fireflies

Fig. 4.

Output for 15 Fireflies

Fig. 5.

Output for 12 Fireflies

Fig.6.

Output for 10 Fireflies

Localization Algorithm GA-FFLA DE-FFLA PSO-FFLA
Number of Firefly Low Medium High
Number of iteration Low Medium High
Time complexity Best Worst Medium
Accuracy Best Medium Worst
Number of Land Marks Less More Medium
Table 4.

Performance comparison of the three hybrid algorithm.

Table. 5 shows the comparative analysis of GA-FFLA, DE-FFLA and PSO-FFLA with respect to location information estimation accuracy and time complexity based on number of fireflies.

Localization Algorithm GA-FFLA DE-FFLA PSO-FFLA
Number of fireflies=20 Accuracy (percentage) 100 100 100
Time Complexity(sec) 1.1049 1.4914 3.5082
Number of fireflies=18 Accuracy (percentage) 100 99 100
Time Complexity(sec) 1.0757 2.1354 3.8725
Number of fireflies=15 Accuracy (percentage) 100 98 99
Time Complexity(sec) 0.9913 2.6390 3.2135
Number of fireflies=12 Accuracy (percentage) 99 96 97
Time Complexity(sec) 0.9648 2.6667 3.1114
Number of fireflies=10 Accuracy (percentage) 98 95 96
Time Complexity(sec) 1.0008 2.7767 3.3314
Table. 5.

The output analysis of the three Hybrid algorithms GA-FFLA, DE-FFLA, PSO-FFLA based on number of Firefiles.

From Table. 5 it can be concluded that all hybrid algorithms have hundred percent accuracy of location information estimation when the number of fireflies is twenty. Moreover, this accuracy was achieved in single iteration for GA-FFLA, two iterations for DE-FFLA and 19 iterations for PSO-FFLA. This shows that the time complexity of GA-FFLA is better than DE-FFLA and PSO-FFLA. The accuracy and time complexity of GA-FFLA is better compared to DE-FFLA and PSO–FFLA when the number of fireflies is reduced. The accuracy of PSO-FFLA is better when compared to DE-FFLA, but time complexity is higher. Further all the three algorithms showed a better time complexities as the landmark were increased from 10 to 15.

9. Conclusions

Nature-inspired hybrid algorithms, Genetic Algorithm-Firefly Localization Algorithm (GA-FFLA), Differential Evolution Firefly Localization Algorithm (DE-FFLA), Particle Swarm Optimization Firefly Localization Algorithm (PSO-FFLA), were studied, analyzed, designed and implemented. These algorithms were used to optimize the localization error in WSN to achieve the optimal location information of the sensor nodes. The proposed algorithms were tested with variation in number of fireflies, variations in design parameters and variations in number of iterations to achieve better accuracy. From the proposed design standards, it can be concluded that GAFFLA shows better performance in terms of accuracy and time complexity. Further tuning of design parameter and different hybrid mechanism could be considered for improving the time complexity, which would improve the reliability and life time of WSN. As future directions of work the designed algorithm could be implemented in real time environment which involves 3D localization scenario.

References

2.REN Xiuli, GAO Chuangen, and XI Yuanhao, A Node Localization Algorithm Based on Simple Particle Swarm Optimization in Wireless Sensor Networks, Journal of Computational Information Systems, Vol. 9, No. 22, 2013, pp. 9203-9210.
10.S Binitha and S Sivasathya, A Survey of Bio inspired Optimization Algorithms, International Journal of Soft Computing and Engineering, Vol. 2, No. 2, 2012, pp. 137-151.
16.Kurt Derr and Milos Manic, Wireless sensor networks node localization for various Industry Problems, IEEE Transactions on Industrial Information, 2015, pp. 1551-3203.
26.CN Ravi, G Selvakumar, and CC Rajan, A Hybrid Real Coded Genetic Algorithm-Differential Evolution for Optimal Power Flow, International Journal of Engineering and Technology (IJET), Vol. 5, No. 4, 2013, pp. 3404-3412.
29.XS Yang, Nature Inspired MetaHeuristic Algorithms, Luniver Press, Beckington, UK, 2008.
Journal
International Journal of Computational Intelligence Systems
Volume-Issue
10 - 1
Pages
1263 - 1271
Publication Date
2017/07/24
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.2991/ijcis.10.1.85How to use a DOI?
Copyright
© 2017, the Authors. Published by Atlantis Press.
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

TY  - JOUR
AU  - P. SrideviPonmalar
AU  - V. Jawahar Senthil Kumar
AU  - R. Harikrishnan
PY  - 2017
DA  - 2017/07/24
TI  - Hybrid Firefly Variants Algorithm for Localization Optimization in WSN
JO  - International Journal of Computational Intelligence Systems
SP  - 1263
EP  - 1271
VL  - 10
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.10.1.85
DO  - 10.2991/ijcis.10.1.85
ID  - SrideviPonmalar2017
ER  -