Access the full text.
Sign up today, get an introductory month for just $19.
References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.
Regular Issue Nature Inspired Range Based Wireless Sensor Node Localization Algorithms Ranjit Kaur*, Sankalap Arora DAV University, Jalandhar, Punjab (India) Received 1 April 2016 | Accepted 10 January 2017 | Published 30 March 2017 Abstract Keywords Localization is one of the most important factors highly desirable for the performance of Wireless Sensor Wireless Sensor Network (WSN). Localization can be stated as the estimation of the location of the sensor nodes in sensor Network, Localization, network. In the applications of WSN, the data gathered at sink node will be meaningless without localization Flower Pollination information of the nodes. Due to size and complexity factors of the localization problem, it can be formulated Algorithm, Particle as an optimization problem and thus can be approached with optimization algorithms. In this paper, the nature Swarm Optimization, inspired algorithms are used and analyzed for an optimal estimation of the location of sensor nodes. The Firefly Algorithm, Grey performance of the nature inspired algorithms viz. Flower pollination algorithm (FPA), Firefly algorithm (FA), Wolf Optimization. Grey Wolf Optimization (GWO) and Particle Swarm Optimization (PSO) for localization in WSN is analyzed in terms of localization accuracy, number of localized nodes and computing time. The comparative analysis has shown that FPA is more proficient in determining the coordinates of nodes by minimizing the localization error DOI: 10.9781/ijimai.2017.03.009 as compared to FA, PSO and GWO. range free algorithms. Range based localization algorithms uses point I. Introduction to point distance estimation or angle based estimation between sensor ireless Sensor Network (WSN) consists of independent similar nodes whereas range free localization algorithms do not require range Wor diverse types of nodes that monitor the environment. These information between target node and anchor node but depends on tiny, autonomous, portable and economical nodes sense the data and the topological information. The former provides more accuracy as pass it to designated location or the base station by using wireless ad-hoc compared to range free localization algorithms. network technique. Each sensor node has a transducer, power supply, The range based localization of nodes has two phases – ranging microcomputer and transceiver to record and process the sensory data phase and position estimation phase. In the ranging phase, each [1]. WSN is being used for many applications like industrial process target node measures its distance from the anchor nodes using the monitoring, battlefield, forest fire detectors, natural disaster prevention, strength of received signal or the signal propagation time. Accurate traffic monitoring, etc. [2]. Most of the applications need location measurement of distance is not possible due to noise. There is a noisy information of the sensor nodes for tracking and monitoring [3]. range measurement irrespective of the ranging method used whereas in In WSN, sensor nodes sense and report the events of interest which position estimation phase, the information acquired from ranging phase can be examined when the position of target nodes reporting the event is used to determine position of target node. It can also be estimated is known. The information gathered at sink node will be in vain without using geometric approach or by using an optimization algorithm. localization information of sensor nodes. The estimation of the position The optimization algorithms are really effective in solving NP- of sensor nodes is one of the important issues of the WSN and is known Hard problems like Traveling salesman problem, decision subset as localization problem [4]. Localization can be defined as determining sum problem, localization, etc. Localization problem is considered the coordinates of unknown nodes called as target nodes using the as an optimization problem due to size and complexity factors. The position of known nodes called as anchor nodes or beacons [5] based analytical methods of optimization like linear programming takes more on the measurements such as Time of arrival (TOA), Time difference computation time for solving optimization problems and increase the of arrival (TDOA), Angle of arrival measurement (AOA), etc. [6]. complexity as the size of problem increases [8]. This propelled to use The localization issue can be resolved by deploying each node with nature inspired optimization algorithms for WSN as these are robust Global Positioning System (GPS) but this is not preferred due to size, and effective [9]. These algorithms became popular from the last cost and power factors [7]. Moreover, GPS has restricted functionality decade as they can easily adjust to frequently changing environment as it cannot work indoor and underwater. So, an efficient alternative and have high efficiency [10]. The various algorithms like Particle is required for the localization. The non-GPS based localization Swarm Optimization (PSO) [11], Firefly Algorithm (FA) [12] [13], algorithms can be used which is categorized into range based and Genetic Algorithm (GA) [14], Grey Wolf Optimization (GWO) [15], Flower pollination Algorithm [16], etc. have been used to determine * Corresponding author. positions of target nodes. The objective of the various optimization algorithms in WSN localization is to minimize the position estimation E-mail address: kaurranjit2212@gmail.com - 7 - International Journal of Interactive Multimedia and Artificial Intelligence, Vol. 4, Nº6 error. These nature inspired algorithms really performed well on phases. In first phase, the location of target node is estimated whereas benchmark functions and localization problem [17]. The work on FPA in second phase, the optimization is executed on those nodes that may based node localization algorithm [18] does not provide comparison of have flip ambiguity problem [31]. The localization algorithms based two or more localization algorithms with FPA. The distance between on GA are proposed in [14], [32], [33]. To minimize the localization target node and an estimated node for each target node has not been error, localization algorithm based on PSO is proposed [30]. The reported. In order to provide a fair comparison, it is necessary to show Biogeography Based optimization (BBO) and H-best particle swarm the behavior of the aforementioned techniques considering other optimization (HPSO) performs better in terms of accuracy and values of the parameters involved in the considered algorithms which localized nodes as described in [34]. FPA based localization is also has not been done yet. proposed to solve the localization issue [18]. In this paper, the application of FPA, PSO, FA and GWO for the optimal location estimation of sensor nodes is analysed. All the III. Nature Inspired Algorithms aforementioned factors are considered for the comparison and analysis. Nature inspired algorithms mimics’ nature to solve various hard These range based localization algorithms are compared with each other to determine the proficient algorithm which performs better and complex problems as nature exhibits flexible, robust, diverse and to solve localization issue. Factors like transmission range, number dynamic phenomenon. The nature inspired becomes popular as it can easily adjust to frequently changed environment and the conventional of anchor nodes and number of iterations affecting the localization or traditional methods were inefficient. These optimization algorithms error are considered and analysed for each localization algorithm and really perform well to solve the optimization problems like localization compared graphically. All the localization algorithms are analysed in 36 trail runs by changing number of anchor nodes and target nodes issue, traveling salesman problem, etc. The various algorithms in sensor field in terms of localized nodes, localization accuracy and like PSO, FA, FPA, GWO and GA. have been applied to solve the localization problem in WSN. The algorithms which are used for the computation time. analysis and comparison are: The organization of the rest of the paper is as follows: Section II includes literature survey on WSN. Section III describes the meta- A. Flower Pollination Algorithm heuristic optimization algorithms. Section IV present the localization FPA is a nature inspired algorithm proposed by Xin-She Yang based on optimization algorithms. In section V, simulation results and in 2012 [35]. It is inspired from the natural process ‘pollination of comparative study are given and discussed. In section 6, a conclusion flowers’. This metaheuristic algorithm has evolutionary characteristics along with the future work is presented. and its convergence rate is relatively high as compared to other nature inspired algorithms [36]. II. Related Work Pollination is an intriguing process in which pollen grains are transferred from the anther to the stigma with the help of pollinators Localization has become an active research topic in WSN in for reproduction. It has two major types: biotic and abiotic pollination. recent years as exact localization information is really desirable for Biotic requires help of some living organisms like insects, bats etc. the performance of WSN. This problem is approached with different to transfer pollen grains whereas the latter are dependent on wind and methods by the researchers. The localization with Ad-hoc Positioning water for pollination. There is a process known as flower constancy System (APS)-distributed method in an ad-hoc network is developed in which some pollinators visit specific species of flowers bypassing by Niculescu [19]. The principle of APS is similar to the GPS but it others. extends the potential of GPS to non-GPS sensor nodes as position Pollination can be attained by two ways i.e. self-pollination and information of anchor nodes is passed to all sensor nodes in the cross-pollination. Self-pollination is defined as the reproduction of wireless network. For each target node, minimum three anchor nodes flower by the transfer of pollen grains from the same or different flower are necessary to execute the triangulation or trilateration to determine of the same plant species whereas in cross-pollination, pollinators like its location. Another algorithm was proposed by Savarese [20] to birds, bees, bats etc. travel a long distance for pollination and follows improve Niculescu’s method which consists of two phases-hop terrain Levy flight behaviour in which the step length obeys Levy distribution. and refinement. Hop terrain phase is similar to the APS. The refinement phase uses an iterative procedure for the accuracy of location of each There are four rules which have been derived for FPA based on the node which is enhanced by estimating the least square distances from characteristics of pollination which are: the neighbouring sensor nodes [21]. The sensor nodes in the sensor 1. Global pollination process is attained by considering biotic and field work collectively to determine the location but the error is cross pollination because various pollinators performs levy flights. accumulated in the network. To avoid the accumulation, the kalman 2. Local pollination is attained through abiotic and self- pollination. filter along with the least square estimation method is used to estimate the co-ordinates of location simultaneously as proposed by Savvides 3. Flower constancy is defined as the probability of reproduction [22]. Localization problem is approached with the convex optimization which directly depends on the similarity of two flowers which are involved. which is based on semi-definite programming [23]. The technique of semi-definite program is extended further to non- convex inequality 4. Switch probability helps in controlling local p ∈ [0, 1 ] constraints by Prtaik [24]. Tzu-Chen Liang extends the Pratik’s method pollination (exploitation) and global pollination (exploration). In to apply gradient search method [25]. It uses technique of data analysis overall pollination activities, local pollination can have a value of called multidimensional scaling (MDS) [26]. The range based anchor p in significant fraction due to the various factors like physical less localization algorithms are discussed in [27-29]. proximity, wind etc. The localization problem can be considered as an optimization These rules are formulated into mathematical equations to have problem. The optimization methods use population based stochastic position updating formulas. The two most important steps of FPA method to evaluate the location of nodes by minimizing the mean are local pollination and global pollination. In global pollination, square error [30]. Simulated annealing method was proposed to pollinators carry the pollen grains to the different flowers by traveling locate the position of nodes but this doesn’t provide good results. An a long distance as birds, insects [37]. Through this, exploration can be improved simulated annealing method was proposed which has two attained and reproduction of the fittest is ensured. - 8 - Regular Issue The first and third rule can be mathematically represented in Eq. (1). change in light intensity and formulation of attractiveness [43]. The intensity of light I changes with distance r having a constant light absorption coefficient which is described mathematically as follows: (1) (4) Here is pollen i at iteration t or solution vector and is the global best value in every generation. L is the most important parameter Here Io represents light intensity at initial value. The attractiveness for pollination as the various insects use Levy flight to move over between fireflies is relative which is seen or judged by fireflies and it a long distance for pollination [38]. Thus, we draw L > 0 from levy varies with distance r between two fireflies. Thus, the attractiveness distribution which is valid for large steps i.e. s > 0 [39] and it can be β is defined as follows which is corresponding to the light intensity represented as: judged or seen by fireflies. (5) , (s >0) (2) Here the represents attractiveness between fireflies when The local pollination takes place by the transfer of pollen grains with distance r is 0. The Cartesian distance method is used to calculate the help of abiotic pollinators from one ﬂower to another. The second rule distance between two fireflies. The firefly i move towards the brighter and ﬂower constancy can be represented mathematically as: firefly j which is determined with the help of Eq. (6). (3) (6) The second part of the equation represents the attractiveness and the where e and are pollens from distinct ﬂowers of the same third part is for randomization where the parameter α lies in the range plant species at iteration t. It imitates the ﬂower constancy in restricted of [0, 1] which helps in randomization and is a random variable neighbourhood which helps to attain convergence quickly. If and whose value is drawn from Gaussian distribution. The pseudo code for are from same population and ∈ is drawn from a uniform distribution this algorithm is given in Fig. 2. [0, 1], then it becomes a local random walk. Switch probability p helps to switch from local to global pollination and vice-versa. The pseudo Objective f(x ), i = (1,2,3,…d) code of the FPA is given in Fig. 1. i Initialize the population of fireflies x (i=1,2,3…n) Objective f(x ), i = (1,2,3,…d) i Set light absorption coefficient γ Initialize the flower population with n flowers While (t < Max number of generations) Find the best flower g in the population. for i =1: n fireflies Set switch probability p ϵ [0,1] for j =1: n fireflies while (t < Max number of generations) Light intensity I_iat x_i is determined by f(x ) for i =1:n if (I >I ) i j if rand < p, Move firefly i towards j in d dimensions. Draw Levy flight using Eq.(1) end if Do global pollination using Eq.(2) Attractiveness changes with distance r using exp[-γr] else Evaluate new solutions and update the light intensity Draw ϵ from uniform distribution in [0,1] end for j Do local pollination using Eq.(3) end for i end if Rank the fireflies according to light intensity and Update the fitter solutions in existing population determine the best firefly end for end while Find the best solution in the population Fig. 2. Pseudo code of FA. end while C. Particle Swarm Optimization Fig. 1. Pseudo code of FPA. The PSO algorithm was proposed by Kennedy and Eberhart [44]. B. Firefly Algorithm This algorithm is mainly inspired from the behaviour of birds flocking in nature. The flock of birds communicate with each other while FA was proposed by Xin she Yang in 2009 and it was mainly inspired migrating to the destination and find the bird at best position. Each bird from the flashing qualities or characteristics of fireflies [40]. The in the flock moves towards best position with velocity dependent on fireflies get attracted to each other despite of their sex. Attractiveness the current position of the bird and then, they explore the search space between fireflies depends directly on the brightness due to which from their new positions. The process is reiterated until they reach their less luminous fireflies will be attracted towards brighter firefly. But destination [45]. attractiveness decreases with an increase in distance between them [41]. If there is no brighter firefly available, then firefly will move In this algorithm, the social interaction and intelligence of birds randomly in the search space. The brightness of the firefly is evaluated are involved. The birds grasp knowledge from their own experience by the objective function which is to be optimized [42]. The brightness as well as the experience of other birds [46]. Each particle or bird determines the attractiveness between fireflies corresponding to the possesses three values i.e. the present position ( ), the local best value objective function. FA is mainly based on two important factors i.e. - 9 - International Journal of Interactive Multimedia and Artificial Intelligence, Vol. 4, Nº6 ( ) and their velocity ( ). The objective function helps to find out the ( ) ( ) (10) best particle’s position ( ). Every particle in the flock updates their velocity with respect to best particle using following mathematical Here and represents the position vector of grey wolf and prey. formula given in Eq. (7). Vectors and are depicted with the help of following equations: ( ) ( ) ∗ ∗ (11) (7) (12) Here rand ( ) and Rand ( ) are two random functions whose value Here Here and are random vectors in range [0, 1] and lies in the range [0, 1]. The and parameters are acceleration constants or learning factors and w represents inertia weight which is parameter r is linearly decreased from 2 to 0. The best three solutions mainly used to control the impact of previous velocities of particle on are saved and further the candidate solutions i.e., grey wolves update current velocity. The second part of the equation is used to compare their positions accordingly. Social behavior of hunting mechanism is the particle’s current position to its own local best position whereas mathematically derived using Eq. (13), (14) and Eq. (15). third part compares the particle’s position to the global best particle. The position of a particle using new velocity is updated with the help of Eq. (8). (13) (8) The value of lies in the range of user specified values of Vmax, ( ) . ( ), i.e., to control the effect of change in particle’s ( ) , lh velocity. The pseudo code of PSO algorithm is given in Fig. 3. (14) ( ) ( ) Objective f(x ), i = (1,2,3,…d) Initialize the population of particles ( ) = (15) Initialize the value of inertia weight w While (t < Max number of generations) At the end, when the last criterion specified will be satisfied, GWO for i: n particles algorithm will get terminated and the best position of α wolf will be considered as the outcome. All the steps are presented in pseudo code find local best (pbest) of all particles which is given in Fig. 4. end for find global best (gbest) as the best fitness of all particles Initialize the population of grey wolves x , (i=1,2,3….n) for i: n particles Initialize a, A and C Calculate the velocity of particle using Eq. (7) Calculate the fitness of each search agent or wolf Update the position of particle using Eq. (8) X =the best search agent end for X =the second best search agent end While X =the third best search agent while (t < Max number of iterations) Fig. 3. Pseudo code of PSO. for each search agent D. Grey Wolf Optimization Update the position of current search agent using Eq.(15) Grey Wolf Optimizer (GWO) is a nature inspired algorithm end for proposed by Mirjalili et al. in 2014 that focuses on social behaviour Update a, A and C of grey wolves [47]. This algorithm is inspired from grey wolves that belong to canidae family. It simulates the leadership quality and the Calculate the fitness of all search agents. hunting behaviour of grey wolves in three steps as tracking, encircling Update X , X , X α β δ and attacking. Grey wolves consists of 5-12 wolves. Grey wolves end while live in pack that contains 5-12 wolves. α, β, δ and ω are four types of return X grey wolves following a strict social hierarchy. α is the dominant wolf among the other grey wolves that makes different decisions which are Fig. 4. Pseudo code of GWO. followed by other submissive grey wolves. β grey wolf is second in the hierarchy after α grey wolf. β grey wolf help the dominant leader α to make decisions about sleeping etc. IV. Localization Using Nature Inspired Algorithms Approaching and encircling the prey are behaviour of team hunting The objective of sensor node localization using nature inspired followed by the grey wolves’ pack which is mathematically modelled algorithms is to evaluate the position of the maximum number of target in Eq. (9) and Eq. (10). nodes using analytical information about the position of anchor nodes. The localization problem can be formulated as an objective function ( ) ( ) (9) which is to be minimized using nature inspired algorithm. The overall ﬂowchart of range based distributed localization of sensor nodes using - 10 - Regular Issue nature inspired algorithm is shown in Fig. (5). performance of the localization algorithm as the localization error increases with the increase in noise. The actual distance can be The following steps are followed to perform node localization of measured by using the Eq. (16): each target node in WSN: 1. M target nodes and N beacons or anchor nodes are deployed = ) ) (16) randomly in the sensor field. Each anchor node has transmission range R. The localized nodes act as beacon in next iteration to Where (x, y) and ( , ) are the coordinates of target node and remove ﬂip ambiguity problem. anchor node respectively. 3. The target node that has anchor node ≥ 3 within its transmission Start range is known as localizable node. This target node is localized using an optimization algorithm. 4. For each target node, an optimization algorithm is executed Deploy target nodes and anchor nodes independently. Initialize the particles of the algorithm with the in 2-D sensor field. centroid of the anchor nodes (within the transmission range) by using the Eq. (17) as follows: Estimate distance between target node (x ,y ) ∑ x , ∑ y (17) and anchor node where N is the number of the anchor nodes within transmission range of each target node. 5. The algorithm minimizes the objective function or error for the localization problem in WSN which is given mathematically in Eq. (18). If each target node has ( ) = (∑ ( ) + ( ) ) anchor nodes within (18) transmission range >= 3 where N ≥3 are the number of anchor nodes within transmission range, is the anchor node within the transmission range and (x,y) is the position of the particles. No 6. FPA finds the optimal value (X, Y) after the maximum number of Yes iterations. 7. When the position of all localized nodes get estimated, compute Find the centroid of the anchor nodes the average localization error to find the localization accuracy by using the Eq. (19) as follows: Deploy particles around the centroid = ) ) (19) where are the coordinates of actual node, ( , ) are the Evaluate mean of square error by coordinates of estimated position and is the total number of using the objective function localized nodes. 8. Repeat steps 2-7 until all the target nodes get localized or no more target nodes can be localized. The localization algorithm’s Optimization algorithm finds the best performance is based on the estimated average localization error position of localized node and the number of un-localized nodes where = . M− Localization accuracy is better if value of and is less. The number of localized nodes increases as the iteration increments. Find average localization error A node that has been localized can be used as a beacon for the next node. This decreases the problem of ﬂip ambiguity as more references Repeat until all are available for the localized node. However, this increases the target nodes Stop computation time. get localized Fig. 5. Flow chart of Sensor node localization using nature inspired algorithm. V. Simulation Results and Discussion 2. The distance between each target node and anchor node is The simulation of WSN localization is conducted using PSO, measured. There is an additive white Gaussian noise which blurs FA, GWO and FPA in QT Creator 2.4.0. In 2-D sensor field, target nodes and anchor nodes are deployed in the region of 100*100 square the measurement. Each target node’s distance from every anchor units. The transmission range of beacons or anchor nodes is set as 30 node is measured as where is the actual distance units. The performance of each localization algorithm is analysed and is the measurement noise which has gaussian distributed considering other values of the parameters involved in the considered ( ) random value in the range which really affects the - 11 - International Journal of Interactive Multimedia and Artificial Intelligence, Vol. 4, Nº6 FA is run for each target node till the specified number of iterations algorithms in terms of localized node ( ), localization error ( ) to localize target nodes. FA based localization for 50 target nodes is and computation time (( ). The parameter values that provide better represented in Fig.7 localization accuracy are considered for the localization algorithms. TABLE II. Performance of FA with Different Tuning Parameters The strategic settings and parameter values of PSO, FA, GWO and FPA are discussed below: S. No. Parameters A. PSO Based Localization 0.25 100 0.903181 6.503 1. α The performance of PSO based localization with different 0.50 100 1.01864 8.737 parameters is analysed and summarized in Table 1. The parameter 1.0 100 0.528133 7.892 values that result in less localization error are considered. The inertia 2. β 0.2 100 0.378845 9.133 weight is an important parameter to control the effect of the previous 1.0 100 0.410389 7.618 velocities on the existing velocity and the parameters and is the 3. γ 0.7 100 0.430746 7.743 learning factors. The number of particles n helps to localize a target node by updating the position according to optimization algorithm. 20 100 0.360542 5.229 4. n The number of iterations represents the number of times the position is 30 100 0.366548 6.763 updated to find an optimal solution. The parameter values that works 100 100 0.305937 8.681 best for localization is considered for PSO based node localization 5. Iteration algorithm which are as follows. 200 100 0.576672 9.315 • No. of particles or population (n) = 30 C. GWO Based Node Localization • No. of iterations = 100 The performance of GWO based node localization algorithm • Cognitive or social scaling parameter = = 1.494 considering the parameters is summarized in Table 3. The vector is a • Inertia weight (w) = 0.7 controlling parameter for exploration and exploitation in an algorithm which linearly decreases from 2 to 0. The numbers of grey wolves or TABLE I. Performance of PSO with Different Tuning Parameters particles n helps to determine the localization information of target S. No. Parameters node by updating their position. 0.7 100 0.584384 2.287 The following parameters are considered for the localization of 1. w target nodes using GWO: 0.650246 0.4 100 2.206 • No. of particles (n) = 30 1.494 100 0.690518 2.259 • No. of iterations = 100 2.0 100 0.694749 2.45 vector = 2 to 0 20 100 0.721967 2.21 TABLE III. Performance of GWO with Different Tuning Parameters 3. n 30 100 0.717235 1.997 S. No. Parameters 100 100 0.698956 2.591 1. 2 to 0 100 0.382065 2.894 4. iteration 200 100 0.567573 4.335 20 100 0.442893 2.531 2. n 0.362075 30 100 2.734 The PSO based localization algorithm is conducted using above parameters for specified number of iterations to find the localization 100 100 0.445948 2.531 3. iteration information. The localized nodes, 50 target nodes and 15 anchor nodes 200 100 0.314762 2.406 are depicted in Fig. 6. GWO based node localization of 50 target nodes with 15 anchor B. FA Based Localization nodes is illustrated in Fig. 8 which shows target nodes, localized nodes Each localized node runs FA to estimate the position of sensor and anchor nodes. nodes in the sensor field. The performance of FA based localization is evaluated by tuning parameters and summarized in Table 2. The D. FPA Based Node Localization parameter γ is the light absorption coefficient which is really important The performance of the FPA based localization algorithm is analysed for the convergence of the algorithm. The value of randomization factor and summarized by considering parameters in Table 4. α lies between [0, 1] and β is the initial attractiveness when the distance Table IV. Performance of FPA with Different Tuning Parameters between two fireflies is 0. The value of n shows the number of fireflies to be deployed in the sensor field to attain the localization information S. No. Parameters by running the algorithm for specified number of iterations. 0.7 100 0.203275 2.854 The parameters which shows less localization error are considered 1. p 0.8 100 0.609618 2.445 for localization which are: 1 100 0.261968 1.873 • No. of fireflies (n) = 30 2. λ 1.5 100 0.201976 2.138 • No. of iterations = 100 20 100 0.766729 1.954 3. n • Randomization parameter (α) = 0.25 30 100 0.265837 3.098 • Absorption coefficient (γ) = 1.0 100 100 0.244462 2.225 4. iteration • Initial attractiveness (β) = 1.0 200 100 0.685683 3.771 - 12 - Regular Issue Fig. 6. Node localization using PSO. Fig. 7. Node localization using FA. Fig. 8. Node localization using GWO. - 13 - International Journal of Interactive Multimedia and Artificial Intelligence, Vol. 4, Nº6 Fig. 9. Node localization using FPA. The parameter switch probability p is mainly used to control the algorithm depends on the density of anchor nodes. It is difficult to locate global pollination and local pollination of the algorithm. The value of position of nodes if sufficient number of anchor nodes (N >= 3) are not λ is really crucial for the Levy flight which plays an important role available. The less number of anchor nodes localize very few number for global pollination. The number of pollens n is deployed around of target nodes. Location estimation accuracy and the percentage of the centroid of the anchor nodes which update the position with the localized nodes increase with the increase in anchor node density. help of position updating formulas for specified number of times. The increase in transmission range of anchor nodes helps in improving The following parameters are considered for FPA based localization the performance as the number of anchor nodes within transmission algorithm: range of each target node will be more. This will also increase the number of localized nodes. The dependency of localized nodes on the • No of pollen/flowers (n) = 30 transmission range for FA, PSO, GWO and FPA is shown in Fig. 11. • No. of iterations = 100 Smaller transmission range localizes very less number of sensor nodes. • Switch probability (p) = 0.7 • Lambda (λ) = 1.5 50 target nodes estimated by FPA based node localization with the help of 15 anchor nodes is depicted in Fig.9. The nature inspired optimization algorithms are stochastic in nature. So, same results are not produced in all runs or experiments. Due to = 2 this, the results of 30 trial experiments are averaged by using , M = 50 and N = 15. The results are summarized in Table 5 which shows that FPA performs better with respect of localization error and un-localized node. The computation time taken by PSO is less than other algorithms. GWO performs less among other algorithms in terms of localization error. Table V. Summary of Results of 30 Trial Runs Fig. 10. Percentage of localized nodes depending on the number of anchor nodes Algorithms Mean Computing time (s) Mean FPA 4.5 0.28374 0.767 PSO 7.1 0.584231 0.743 FA 5.4 0.725323 3.891 GWO 5.0 0.802848 0.832 The initial deployment of sensor nodes is random due to which the localization accuracy, the number of un-localized node and the total computing time will be different for every run of the localization algorithm. The beacons, target node and the position estimated by the algorithms like PSO, FA, GWO and FPA are shown in Fig. 6, 7, 8 and 9 respectively The transmission range, additive Gaussian noise and the number of anchor nodes are the important parameters to determine the localization error. The performance of localization algorithms is influenced by these parameters. Dependency of the percentage of the localized node on the number of anchor nodes for FA, PSO, GWO and FA based localization Fig. 11. Percentage of localized nodes depending on the transmission range. algorithms is shown in Fig. 10. The performance of the localization - 14 - Regular Issue Gaussian additive noise is also an important parameter that has a great impact on localization accuracy. As noise in distance measurement increases, increases which leads to decrease in localization accuracy. Due to this, all the experiments are conducted by considering Gaussian noise . = 2 The localization accuracy also improves with the increase in number of iterations as shown in Fig. 12. As the number of iteration progresses, the localization error declines. FPA shows more decline in the error as compared to other two algorithms. The distance between target node and estimated node for varying number of target nodes is shown in Fig. 13. In this estimated distance for each target node using optimization algorithms is compared which shows FPA based node localization performs better for target nodes Fig. 12. Error V/S iterations. which shows its proficiency. Node localization based on FA, PSO, GWO and FPA algorithms by varying number of anchor and target better localization accuracy to estimate the position than FA, PSO nodes is summarized in Table 6. All the experiments are conducted and GWO localization algorithms in terms of mean square error. But with different configurations in 36 trails. All the optimization the computing time required by FPA in locating the sensor nodes is algorithms performed well to estimate the location of nodes in WSN. more than other optimization algorithms. However, the performance of The FPA based localization algorithms provides less localization error GWO is comparative less to other algorithms like FA, PSO and FPA in for each number of target nodes whereas PSO estimate the position terms of localization accuracy and computation time. in less computing time but it has high localization error. It shows TABLE VI. Summary of Results of FPA, FA, PSO and GWO Based Node Localization PSO FA FPA GWO Target Anchor Trial Node Node 19 0.65320 0.460 1 22 0.807158 0.36 19 0.335551 1.44 21 0.133565 0.563 25 20 2 17 0.728214 0.39 20 0.264623 1.44 18 0.20504 0.473 23 0.425891 0.480 3 18 0.79765 0.40 21 0.296398 1.70 20 0.197211 0.454 24 0.477140 0.570 46 0.421750 0.890 1 48 0.578797 0.74 50 0.505511 2.50 49 0.325364 0.668 50 15 2 50 0.753254 0.85 49 0.32698 4.42 50 0.22299 0.685 44 0.519238 0.970 3 47 0.587004 0.75 49 0.254824 1.63 48 0.367064 0.941 48 0.525000 0.830 75 0.471716 1.370 1 75 0.67414 1.31 74 0.703964 2.97 74 0.169253 2.046 75 20 2 75 0.720123 1.35 75 0.291862 2.73 75 0.278071 2.451 75 0.448495 1.380 3 73 0.771325 1.30 72 0.279126 3.84 73 0.189639 1.008 75 0.428363 1.370 100 0.3623 2.592 1 100 0.668227 2.49 100 0.779716 5.66 100 0.171925 1.506 100 25 2 100 0.614843 2.10 100 0.299194 6.33 100 0.181158 2.156 100 0.55558 2.590 3 100 0.608155 2.20 100 0.385758 6.55 100 0.151736 2.853 100 0.51877 2.590 = number of localized nodes = localization error = computing time (in seconds) Fig. 13. Distance between actual node and estimated node with different optimization algorithms. - 15 - International Journal of Interactive Multimedia and Artificial Intelligence, Vol. 4, Nº6 3rd International Conference on Advanced Computing, Networking and VI. Conclusion Informatics, Springer, 2016, pp. 209–214. [13] S. Arora, S. Singh, A conceptual comparison of firefly algorithm, bat Localization of sensor nodes is really important for the performance algorithm and cuckoo search, in: Control Computing Communication & of WSN as many applications of WSN require localization information. Materials (ICCCCM), 2013 International Conference on, IEEE, 2013, pp. The main objective of this optimization problem is to minimize 1–4. the localization error with the help of nature-inspired optimization [14] Q. Zhang, J. Wang, C. Jin, J. Ye, C. Ma, W. Zhang, Genetic algorithm algorithms. In this paper, node localization using meta-heuristic based wireless sensor network localization, in: Natural Computation, optimization algorithm like Firefly Algorithm (FA), Particle Swarm 2008. ICNC’08. Fourth International Conference on, Vol. 1, IEEE, 2008, Optimization (PSO) and Grey Wolf Optimization (GWO) algorithm pp. 608–613. is conducted to determine the position of the sensor nodes in WSN. [15] M. M. Fouad, A. I. Hafez, A. E. Hassanien, V. Snasel, Grey wolves This paper has analysed the localization problem and solved it with optimizer-based localization approach in wsns, in: 2015 11th International different optimization algorithms and provides the summary of results Computer Engineering Conference (ICENCO), IEEE, 2015, pp. 256–260. [16] M. Sharawi, E. Emary, I. A. Saroit, H. El-Mahdy, Flower pollination by comparing the algorithm with the each other in terms of localization optimization algorithm for wireless sensor network lifetime global error, localized nodes and computing time. The FPA based node optimization, International Journal of Soft Computing and Engineering 4 localization algorithm shows better localization accuracy in estimating (3) (2014) 54–59. the position than other algorithms. GWO performs comparative less [17] X.-S. Yang, Nature-inspired metaheuristic algorithms, Luniver press, with respect to localization error and computation time among the optimization algorithms. These distributed localization algorithms are [18] S. Goyal, M. S. Patterh, Flower pollination algorithm based localization f better than centralized algorithms as the number of transmissions to wireless sensor network, in: 2015 2nd International Conference on Recent the sink node is reduced which helps to conserve the energy of sensor Advances in Engineering & Computational Sciences (RAECS), IEEE, nodes. These localization algorithms further can be implemented 2015, pp. 1–5. for centralized method and can be compared with distributed [19] D. Niculescu, B. Nath, Ad hoc positioning system (aps), in: Global Telecommunications Conference, 2001. GLOBECOM’01. IEEE, Vol. 5, method for analysis. FPA can be hybridized with other optimization IEEE, 2001, pp. 2926–2931. algorithm to further minimize the location estimation error. These [20] C. S. J. Rabaey, K. Langendoen, Robust positioning algorithms for optimization algorithms can be implemented in 3D scenario to find distributed ad-hoc wireless sensor networks, in: USENIX technical annual localization accuracy. The parameter values can be varied to improve conference, 2002, pp. 317–327. the optimization algorithm to improve convergence rate, localization [21] N. Bulusu, D. Estrin, L. Girod, J. Heidemann, Scalable coordination accuracy and computation time. for wireless sensor networks: self-configuring localization systems, in: International Symposium on Communication Theory and Applications (ISCTA 2001), Ambleside, UK, 2001. References [22] A. Savvides, H. Park, M. B. Srivastava, The bits and flops of the n-hop multilateration primitive for node localization problems, in: Proceedings [1] R. V. Kulkarni, A. Förster, G. K. Venayagamoorthy, Computational of the 1st ACM international workshop on Wireless sensor networks and intelligence in wireless sensor networks: a survey, Communications applications, ACM, 2002, pp.112–121. Surveys & Tutorials, IEEE 13 (1) (2011) 68–96. [23] L. Doherty, K. S. Pister, L. El Ghaoui, Convex position estimation in [2] I. F. Akyildiz,W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor wireless sensor networks, in: INFOCOM 2001. Twentieth Annual Joint networks: a survey, Computer networks 38 (4) (2002) 393–422. Conference of the IEEE Computer and Communications Societies. [3] J. Yick, B. Mukherjee, D. Ghosal, Wireless sensor network survey, Proceedings. IEEE, Vol. 3, IEEE, 2001, pp. 1655–1663. Computer networks 52 (12) (2008) 2292–2330. [24] P. Biswas, Y. Ye, Semidefinite programming for ad hoc wireless sensor [4] R. V. Kulkarni, G. K. Venayagamoorthy, Particle swarm optimization in network localization, in: Proceedings of the 3rd international symposium wireless-sensor networks: A brief survey, Systems, Man, and Cybernetics, on Information processing in sensor networks, ACM, 2004, pp. 46–54. Part C: Applications and Reviews, IEEE Transactions on 41 (2) (2011) [25] T.-C. Liang, T.-C. Wang, Y. Ye, A gradient search method to round the 262–267. semidefinite programming relaxation solution for ad hoc wireless sensor [5] J.Wang, R. K. Ghosh, S. K. Das, A survey on sensor localization, Journal network localization, Sanford University, formal report 5. of Control Theory and Applications 8 (1) (2010) 2–11. [26] Y. Shang,W. Rum, Improved mds-based localization, in: INFOCOM [6] G. Mao, B. Fidan, B. D. Anderson, Wireless sensor network localization 2004. Twenty-third Annual Joint Conference of the IEEE Computer and techniques, Computer networks 51 (10) (2007) 2529–2553. Communications Societies, Vol. 4, IEEE, 2004, pp. 2640–2651. [7] R. G. Crespo, G. G. Fernandez, O. S. Martínez, V. García-Díaz, L. J. [27] S. Cˇ apkun, M. Hamdi, J.-P. Hubaux, GPS-free positioning in mobile ad Aguilar, E. T. Franco, In premises positioning–fuzzy logic, in: International hoc networks, Cluster Computing 5 (2) (2002) 157–167. Work-Conference on Artificial Neural Networks, Springer, 2009, pp. 284– [28] U. Ferner, H. Wymeersch, M. Z. Win, Cooperative anchor-less localization for large dynamic networks, in: Ultra-Wideband, 2008. ICUWB 2008. [8] R. V. Kulkarni, G. K. Venayagamoorthy, Bio-inspired algorithms for IEEE International Conference on, Vol. 2, IEEE, 2008, pp. 181–185. autonomous deployment and localization of sensor nodes, Systems, Man, [29] A. Youssef, A. Agrawala, M. Younis, Accurate anchor-free node and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on localization in wireless sensor networks, in: Performance, Computing, 40 (6) (2010) 663–675. and Communications Conference, 2005. IPCCC 2005. 24th IEEE [9] R. V. Kulkarni, G. K. Venayagamoorthy, M. X. Cheng, Bioinspired International, IEEE, 2005, pp. 465–470. node localization in wireless sensor networks, in: Systems, Man and [30] S. Yun, J. Lee,W. Chung, E. Kim, S. Kim, A soft computing approach to Cybernetics, 2009. SMC 2009. IEEE International Conference on, IEEE, localization in wireless sensor networks, Expert Systems with Applications 2009, pp. 205–210. 36 (4) (2009) 7552–7561. [10] J. Meza, H. Espitia, C. Montenegro, R. G. Crespo, Statistical analysis of a [31] A. A. Kannan, G. Mao, B. Vucetic, Simulated annealing based wireless multi-objective optimization algorithm based on a model of particles with sensor network localization with flip ambiguity mitigation, in: Vehicular vorticity behavior, Soft Computing (2015) 1–16. Technology Conference, 2006. VTC 2006-Spring. IEEE 63rd, Vol. 2, [11] A. Gopakumar, L. Jacob, Localization in wireless sensor networks IEEE, 2006, pp. 1022–1026. using particle swarm optimization, in: Wireless, Mobile and Multimedia [32] Q. Zhang, J. Huang, J. Wang, C. Jin, J. Ye, W. Zhang, A new centralized Networks, 2008. IET International Conference on, IET, 2008, pp. 227– localization algorithm for wireless sensor network, in: Communications and Networking in China, 2008. China-Com 2008. Third International [12] R. Harikrishnan, V. J. S. Kumar, P. S. Ponmalar, Firefly algorithm Conference on, IEEE, 2008, pp. 625–629. approach for localization in wireless sensor networks, in: Proceedings of - 16 - Regular Issue [33] Q. Zhang, J. Wang, C. Jin, Q. Zeng, Localization algorithm for wireless sensor network based on genetic simulated annealing algorithm, in: Wireless Communications, Networking and Mobile Computing, 2008. WiCOM’08. 4th International Conference on, IEEE, 2008, pp. 1–5. [34] A. Kumar, A. Khosla, J. S. Saini, S. Singh, Meta-heuristic range based node localization algorithm for wireless sensor networks, in: Localization and GNSS (ICL-GNSS), 2012 International Conference on, IEEE, 2012, pp. 1–7. [35] X.-S. Yang, Flower pollination algorithm for global optimization, in: Unconventional computation and natural computation, Springer, 2012, pp. 240–249. [36] X.-S. Yang, M. Karamanoglu, X. He, Flower pollination algorithm: a novel approach for multiobjective optimization, Engineering Optimization 46 (9) (2014) 1222–1237. [37] X.-S. Yang, Nature-inspired optimization algorithms, Elsevier, 2014. [38] S. Arora, S. Singh, Butterfly algorithm with levy flights for global optimization, in: Signal Processing, Computing and Control (ISPCC), 2015 International Conference on, IEEE, 2015, pp. 220–224. [39] I. Pavlyukevich, L´evy flights, non-local search and simulated annealing, Journal of Computational Physics 226 (2) (2007) 1830–1844. [40] X.-S. Yang, Firefly algorithm, stochastic test functions and design optimisation, International Journal of Bio-Inspired Computation 2 (2) (2010) 78–84. [41] S. Arora, S. Singh, S. Singh, B. Sharma, Mutated firefly algorithm, in: Parallel, Distributed and Grid Computing (PDGC), International Conference on, IEEE, 2014, pp. 33–38. [42] S. Arora, S. Singh, Performance research on firefly optimization algorithm with mutation, in: International Conference, Computing & Systems, 2014. [43] S. Gupta, S. Arora, A hybrid firefly algorithm and social spider algorithm for multimodal function, in: Intelligent Systems Technologies and Applications, Springer, 2016, pp. 17–30. [44] R. C. Eberhart, J. Kennedy, et al., A new optimizer using particle swarm theory, in: Proceedings of the sixth international symposium on micro machine and human science, Vol. 1, New York, NY, 1995, pp. 39–43. [45] J. Meza, H. Espitia, C. Montenegro, E. Giménez, R. González- Crespo, Movpso: Vortex multi-objective particle swarm optimization, Applied Soft Computing. [46] Y. Shi, R. C. Eberhart, Empirical study of particle swarm, in: Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, Vol. 3, IEEE, 1999. [47] S. Mirjalili, S. M. Mirjalili, A. Lewis, Grey wolf optimizer, Advances in Engineering Software 69 (2014) 46–61. Ranjit Kaur Ranjit Kaur received M.Tech in computer science and engineering from DAV University, Jalandhar, Punjab (India) and B.Tech in Computer Science Engineering from Punjab Technical University, Jalandhar, Punjab (India). Her current research interests includes optimization, nature inspired algorithms and wireless sensor networks. Sankalap Arora Sankalap Arora was born on Nov 3, 1988. He received his Bachelor’s degree (B.Tech.) and Master’s degree (M.Tech.) from Lovely Professional University, Phagwara, Punjab (India) with specialization in Computer Science & Engineering. He is working as an Assistant Professor in Department of Computer Science & Engineering in DAV University, Janadhar, Punjab (India). He has more than 5 years’ research and teaching experience. His fields of special interest include Nature Inspired Algorithms, Engineering Design problems and Wireless Sensor Networks. He has published nearly 30 research papers in reputed International Journals and Conferences. - 17 -
International Journal of Interactive Multimedia and Artificial Intelligence – Unpaywall
Published: Jan 1, 2017
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get an introductory month for just $19.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.