Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

Centroid Based Localization Utilizing Artificial Bee Colony Algorithm

Centroid Based Localization Utilizing Artificial Bee Colony Algorithm International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE Centroid Based Localization Utilizing Artificial Bee Colony Algorithm Vikas Gupta Chandigarh Engineering College, Landran, Mohali, Punjab, India. vikasgupta2k11@gmail.com Brahmjit Singh National Institute of Technology, Kurukshetra, Haryana, India. brahmjit.s@gmail.com Published online: 27 June 2019 unidentified sensor nodes with good correctness, but the kind of hardware these techniques use is very costly. However, the Abstract – Estimation of position of unknown nodes is of range free location determination algorithms do not involve immense importance for proper deployment and tracking of such kinds of hardware for localization. They find the sensors. The centroid based localization algorithm (CLA) is locations of unidentified nodes by means of connectivity widely used for the localization of the sensors but its original and modified versions suffer from large positioning error. Here the information and hence entire arrangement is localized. A localization algorithm is evaluated in terms of localization error hefty amount of research papers on range free localization utilizing artificial bee colony based (ABC) algorithm. methods have been published in literature. For example, Comparison of outcome is presented through other widely used Bulusu et al. in [6] presented a centroid based location techniques including swarm based particle swarm optimization estimation algorithm that falls under the category of range (PSO) and evolutionary algorithms based differential evolution free algorithms. In this work, the receiver localizes itself to (DE) on basic centroid localization algorithm. The results the areas, which coincide with the area of the anchor nodes. obtained through simulation demonstrate that localization error is minimal in ABC and DE based CLA as compared to basic and The coinciding area is called as the centroid of the anchor PSO based schemes but the computation time is the largest in nodes. Beacon nodes or reference nodes are the other names DE based localization algorithm as compared to others. In of anchor nodes used in literature. The beacon nodes or the comparison to the basic CLA the average localization error is beacons are having some built in location determination reduced by 95% and computation time is increased by seven fold equipment. Hop count based localization algorithm DV-HOP in ABC based CLA. It may be established that having considered was presented by Niculescu et al. in [7]. The notion of this localization error of prime importance, ABC algorithm based CLA is the most suitable strategy for localization amongst all the algorithm was to replace the Euclidean distance between two three algorithms. nodes with inter node hop distance. Another range free algorithm, APIT (approximation point in triangulation test) Index Terms – Wireless Sensor Networks, Localization, was proposed by He et al. in [8]. Here three beacon nodes Artificial Bee Colony, Particle Swarm Optimization, Differential create triangular regions; the centroid formed by the Evolution, Localization Error etc. intersection of these regions is used to find out the position of 1. INTRODUCTION unknown sensor nodes. Estimation of unknown positions of sensor nodes distributed In [9], Doherty et al. presented a location estimation arbitrarily in the area of concern is termed as localization and algorithm for localizing the unknown nodes using is of immense significance. Localization plays a significant connectivity-induced based constraints that further employ a role in location of sensed events, geographic routing and semi-definite program (SDP) to resolve the localization issue. target tracking [1]. Broadly the location estimation Multi dimension scaling (MDS-MAP) algorithm was floated algorithms are separated in two classes, namely range based by Shang et al. in [10] which takes into account the and range free. Time of arrival (TOA) [2], time difference of connectivity based knowledge ‘who is in the communication arrival (TDOA) [3], angle of arrival (AOA) [4], and received range of whom’. MDS-MAP algorithm is composed of three signal strength indicator (RSSI) [5] are generally utilized steps, first deals with the estimation of rough distance algorithms those fall in the class of range based. In order to between all the nodes, second is to find the node positions localize the nodes these algorithms rely on accurate point-to- that fits the estimated distance. At last, the normalization is point assessment of position. The major benefit of these employed to determine the unknown coordinates. To improve range based algorithms is that they locate the position of the performance of these range free localization algorithms ISSN: 2395-0455 ©EverScience Publications 47 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE 2 2 different bio inspired and evolutionary algorithms based soft = √(𝑋 − 𝑋 ) + (𝑌 − 𝑌 ) (2) 𝑠𝑡𝑒 𝑎 𝑠𝑡𝑒 𝑎 computing techniques have been proposed in past by the research community. Some of the utilized techniques Here (X , Y ) depicts the actual values of coordinates of a a reported in literature are genetic algorithm [11], simulated unidentified sensor node. This algorithm is very easy and annealing [11], artificial neural networks [12][13], fuzzy inexpensive but the main disadvantage associated with this logic systems [14], particle swarm optimization (PSO) algorithm is large localization error. This error in this scheme [14][15]16][17][18][19], differential evolution [20] etc. In comes out to be within 2 to 4 meters. An improved version of general, all these algorithms optimize the research problem the original CLA algorithm is presented in [22]. Hay-qing et by considering one or more parameters. For example in PSO al. premeditated the coordinates of unknown node on the basis [14] the interest is to optimize the objective function and in of weights. They estimated the distance between transmitting the problem of localization the target is to minimize the and receiving node and decided the weights based on these localization error. In [21] the differential evolution algorithm distances. The estimated value of the unknown coordinates is is applied on RSSI (received signal strength indicator) to calculated based on the equation 3 [22]. optimize the location estimation of the unknown sensor nodes. 𝑤 ∗𝑋 +⋯+𝑤 ∗𝑋 𝑤 ∗𝑌 +⋯+𝑤 ∗𝑌 1 1 𝑛 𝑛 1 1 𝑛 𝑛 ( ) 𝑋 , 𝑌 = ( , ) (3) 𝑠𝑡𝑒 𝑠𝑒𝑡 𝑤 +⋯+𝑤 𝑤 +⋯+𝑤 1 𝑛 1 𝑛 In [14] the RSSI from reference nodes to the unidentified The weights are calculated using RSSI. This method increases nodes is taken in terms of weights and weights are optimized using fuzzy inference engine. These optimized weights the accuracy level but achievement of this improved algorithm extremely depends upon the optimization of these further improve the average localization error. Use of these soft computing techniques by the research community to weights which is a tedious task. Blumenthal et al. [23] presented a weighted centroid algorithm for the estimation of optimize the positioning error motivates us to use ABC algorithm. So in this research article, the original centroid position of unknown sensor nodes. They investigated the theoretical and practical aspects of RSSI measurements and localization algorithm (CLA) is examined and its performance is evaluated using ABC algorithm. Further, the studied the impact on localization error. Although the localization error obtained from this method is less than 1 m same algorithm is first studied with swarm intelligence based PSO algorithm, then with evolutionary algorithm based DE but one of the disadvantages of this method is that it do not take into account the environmental abnormalities while algorithm, and a comparison of these algorithms is made. Remaining structure of paper is separated into 5 sections. estimating the unknown coordinates. Quande et al. [24] proposed a weight compensated RSSI based weighted CLA. Related work in detail is presented in section 2. Simulation of ABC based CLA is given in section 3. Section 4 discuss in The algorithm is simple to implement consume less power and increases the accuracy of localization compared to other detail the results and discussion. Conclusions followed by references are presented in section 5. weighted CLAs. Although the localization error is reduced to 2.81 m but still the localization error is too big which need to 2. RELATED WORK be reduced further. Therefore, the sole objective of present research is to optimize the localization error of basic centroid 2.1. Basic Centroid Localization Algorithm based algorithm. In [6] Bulusu et al. presented an idealized connectivity based 2.2. Natural Behavior of Honey Bees model for outdoor propagation under uncluttered environment. They assumed equal power for all the nodes. In The honey bees follow a collective intelligent behavior in the this model the reference are put on known locations. The search of the food. They are intelligent on the basis of their unknown nodes localize themselves in the region that capacity to share, memorize and store the information. As the coincides with the region of intersection of the anchors. They environment change their behavior also changes. This estimated the position of unknown sensor nodes using intellectual behavior of the bees inspires the researchers to equation 1 [6]. replicate this conduct of bees. In the camp of the bees, three categories exist: first the employed bees (EB), second the 𝑋 +𝑋 +⋯+𝑋 𝑌 +𝑌 +⋯+𝑌 𝑖 1 𝑖 2 𝑖𝑘 𝑖 1 𝑖 2 𝑖𝑘 (𝑋 , 𝑌 ) = ( , ) (1) onlookers bees (OB), and third the scouts bees (SB). Out of 𝑠𝑡𝑒 𝑠𝑒𝑡 𝑘 𝑘 these EBs are connected with the source of food, OBs chooses the food source. The SBs randomly hunt all sources of food. Here (X , Y ) is the estimated value of unknown est est At the start, the scout bees reveal the entire foodstuff. Both coordinates of sensor node and the number k represents the EBs and OBs keep on exploiting the nectar present in each amount of reference nodes. The performance measure used to food source until all nectar is bushed. After this the employed determine the accuracy of this method called as localization bees becomes scout bees and start probing the food sources error (LE) can be described with the equation 2 [6]. ISSN: 2395-0455 ©EverScience Publications 48 𝐿𝐸 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE again. General architecture of algorithm of ABC may be discard the older ones. This position updation is represented described as [25] by equation 5 [27]. Repeat 𝑣 = 𝑥 + 𝜙 (𝑥 − 𝑥 ) (5) Employed Bee (EBs) stage Where 𝜙 (𝑥 − 𝑥 ) is called as step size, k Є {1, 2...N} and j Є {1, 2... d} are two arbitrarily selected indices. And k and i Onlooker Bees (OBs) stage are chosen to be of different values so as to have some Scout Bees (SBs) stage significant contribution of step size, 𝜙 whose value lies in between [–1, 1]. Remember the optimized result obtained 2.2.4. Onlooker Bees Phase Until (the threshold reaches) In OBs phase, the suitability of updated solutions and the 2.2.1. Localization Using ABC Algorithm positional data are shared with OBs present in hive. These The ABC algorithm [25][26][27] comes under the category of bees analyses existing knowledge and pick a resolution based swarm intelligence based soft computing technique that uses on some probability. This probability (P ) is given by equation the food finding activities of honey bees to optimize the 6 [27]. solution. In the context of localization problem, all food 𝑡𝑓𝑖 sources represent all the sensors nodes scattered in the area of 𝑃 = (6) 𝑖 𝑁 ∑ 𝑡𝑓𝑖 𝑖 =1 interest. The degree of sweetness or nectar present in the food th source gives the level of suitability of the outcome. To get the Where 𝑡𝑓𝑖 is the worth of fitness for the i solution. optimized value of localization error, it is considered as the 2.2.5. Scout Bees Phase objective function. The control parameters are decided and scout bees (SBs) initialize the inhabitants of food references In SBs, if solutions obtained by the employed bees cannot be (or solutions). In first phase the EBs hunt for all new available enhanced further even after a predetermined threshold, the food references having large nectar present in the vicinity of employed bees now become the scouts and current solutions the these references. Every time after discovering the new obtained by them are discarded. The scouts again begin food references, the greedy selection algorithm between new moving arbitrarily in the hunt for new sources (or solutions). obtained solution and its parent is used to obtain new fitness The preset number of cycle or the limit of rejection is an value. This food references information is conveyed by the important control parameter. Let us suppose that the discarded EBs with OBs waiting in the hive with the help of a dance on solution is x, the scout bees replace this source (solution) with the dancing area. Based on the knowledge given by the EBs, newer on the basis of equation 7[27] the OBs select their food probabilistically for which fitness 𝑗 𝑗 𝑗 𝑗 [ ] 𝑥 = 𝑥 + 𝑎𝑛𝑑𝑟 0,1 (𝑥 − 𝑥 ), ∀ = 1,2, … 𝑑 (7) selection method, roulette wheel selection is employed. The 𝑗 𝑖 𝑖𝑚𝑛 𝑖𝑚𝑛 sources that are poor or exploited are deserted and scout bees Where and are the lower and upper restrictions of start to seek new solutions. These steps are replicated in jth direction. repeatedly in anticipation of a threshold. 2.3. Particle Swarm Optimization 2.2.2. Initialization of Population In 1995, Eberhart and Kennedy [28] presented a swarm-based Initially, the artificial bee colony algorithm produces algorithm called as PSO. Algorithm was developed by inhabitants of evenly distributed solutions where each studying the conduct of bird flocking. Although PSO is very solution x (i = 1, 2... N) depicts a d-dimensional vector. Here simple and akin to genetic algorithm but it does not exploit x represents the ith food source and d signifies the variables crossover or mutation. Because of the simplicity and fewer present in the problem of optimization. Generation of each mathematical expressions involved, PSO is easy to food source can be presented by the given equation 4 [27]. implement. Originally, the aim was to emulate the conduct of [ ] 𝑥 = 𝑥 + 𝑎𝑛𝑑𝑟 0,1 (𝑥 − 𝑥 ) (4) min 𝑗 max 𝑗 min 𝑗 birds in a very easy way but later on it emerged as a very good algorithm to discover the optimum solutions. Each Where x is the lower and x is the upper restriction of x min j max j i solution, which is to be optimized, is represented by a bird or in the jth direction. particle in the hunt space. To obtain optimum results the 2.2.3. Employed Bees Phase solution having greatest fitness value is chosen for the objective function. In [15][16][17][18][19] the PSO algorithm Here the existing solution is modified on the basis of its is initialized by taking a arbitrary inhabitants of the particles fitness value. Depending upon the worth of fitness of fresh which search for the paramount solution in hunt space. Here solution, the bees update their position with newer value and in PSO the personal best (Pbest) is the individual best of a ISSN: 2395-0455 ©EverScience Publications 49 𝑖𝑗 𝑚𝑎𝑥 𝑖𝑗 𝑘𝑗 𝑖𝑗 𝑖𝑗 𝑘𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE particle and the global best (gbest) is the collective best many problems. So here ABC algorithm is applied on considered among all the particles. Updation of velocity and centroid based algorithm for diverse values of an important position is done using the equation 8 and 9. network parameter, the communication range. So in the present work the effects of swarm based technique ABC on ( ) ( ) ( ) 𝑡 + 1 = 𝑤 . 𝑡 + 𝑐 1. 𝑎𝑛𝑑𝑟 (). (𝑏𝑒𝑝𝑡𝑃𝑠 𝑡 − localization error in wsn are studied. In algorithm of ABC (𝑡 )𝑐 2. 𝑎𝑛𝑑𝑟 (). (𝑔𝑏𝑒𝑠𝑃𝑡 (𝑡 ) (𝑡 )) (8) best position of food source denotes the best possible solution in the problem of optimization. While using the ABC (𝑡 + 1) = (𝑡 ) + (𝑡 + 1) (9) algorithm in wsn each food resource represents the In the above equations x (t + 1) is the updated new position distribution of sensors in the area of interest and the amount and v (t + 1) is the updated new velocity. Another important of nectar present in the food resource shows the height of factor w represents the weight assigned to the first part of the fitness of the solution. And localization error that is to be equation 8, w.v (t) which is termed as the inertia term. The optimized (given in equation 2) is considered as the objective succeeding part of the equation 8 that represents the function. The goal of the bees in ABC algorithm is to unearth individual behavior of the particle is called as cognition part the best possible solution and three categories of the bees and third part that represents the collective behavior of the namely the EBs, OBs and the SBs fulfill this goal. The EBs particles is called as the social part. In both parts, c1 and c2 exploits the food source and shares this knowledge with the are acceleration coefficients which are constant terms. Here OBs. In terms of localization problem the best position is the localization error (equation 2) is taken as the objective determined by the employed bees using equation 5. The function and the optimized localization error is determined onlooker bees evaluate this sweetness (nectar) information using PSO. using certain threshold. For localization problem this is the probability given in equation 6 which acts as threshold. The 2.4. Differential Evolution onlooker bees become the scout bees after all the nectar is In localization of unknown nodes in wsn, the problem of exhausted or if the quality of nectar is below the threshold. localization is taken as the problem of differential evolution These scout bees again start searching the newer food source and the optimized solution is found. Like genetic algorithm using equation 7. The minimum localization error is the best the differential evolution algorithm is also an algorithm which solution achieved from the ABC algorithm. The proposed is based on population that employs the same operators: approach, in very simplified manner is presented here with crossover, mutation and selection [20][21][29][30]. In the help of an architectural diagram as shown in the Figure 1. general, the genetic algorithm relies on crossover whereas the It can be easily understood from the diagram that approach DE relies on mutation. The mutation is given importance as it starts with simulation of basic centroid based localization gives good parametric variations and diverse results. The algorithm (CLA). Due to the large localization error in CLA, equation of mutation is given by soft computing techniques are employed to reduce or 𝑢𝑚𝑡𝑑𝑡𝑎𝑒 optimize this error. For doing so the localization error is 𝑀 = 𝑀 + 𝑆 ∗ (𝑇 − 𝑅 ) (10) 𝑡 𝑠𝑡𝑏𝑒 𝑣 𝑣 assumed as the objective function to be optimized. Then Where M is the best solution, Mt is the mutated value, S is best ABC algorithm is used on basic CLA and results obtained are the scaling factor and T and R are the targeted and V V compared with PSO and DE based CLA. randomly selected positions. Here also the localization error is considered as fitness function of DE and the optimum fitness function is found by mutation (equation 10), cross over and selection. 3. SIMULATION OF ABC BASED CENTROID LOCALIZATION ALGORITHM In wireless sensor networks (wsn) the problem associated with the localization is the error in estimation of exact coordinates of the unknown nodes. Here first the basic CLA Figure 1 An Architectural Diagram of the Proposed is studied and simulated in matlab and then localization error Approach is premeditated by estimating the distinction between actual and estimated values of coordinates of unidentified sensor The localization error and computation time for both basic nodes. To reduce the error in CLA based algorithm a big and ABC based CLA is premeditated by changing the number of swarm based soft computing techniques have been communication range. Then the performance of CLA is proposed in past. But very little work has been done using studied and simulated by applying the PSO and DE ABC algorithm which is a very good optimization algorithm algorithms. The simulation outcomes demonstrate that the and extensively used method to find the optimum solutions of ABC based algorithm outperform other algorithms. The ISSN: 2395-0455 ©EverScience Publications 50 𝑣𝑖 𝑥𝑖 𝑥𝑖 𝑥𝑖 𝑥𝑖 𝑣𝑖 𝑣𝑖 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE pseudocode for the whole ABC based centroid localization the parameters chosen and mathematical values used for the algorithm is presented in sub section 3.1. simulation environment. All the terms used in the table 1 are self-explanatory. As indicated in table 1 an area of 100 sqm is 3.1. Pseudocode of ABC based CLA considered and 200 sensor nodes are spread arbitrarily in this The pseudocode 1 represents the ABC based CLA. area. As the coordinates of these unknown nodes in centroid based localization is estimated on the basis of some anchor Objective function (equation 2) nodes so in the same area of 100sqm 40 anchor nodes (the nodes having GPS like arrangements) are also randomly Initialize food source or solutions N (equation 4) distributed. That means the anchor ratio chosen is .2 (anchor Cycle=1; nodes divided by the total number of nodes). The communication range is varied from 10m to 100m. The path While cycle <= Maximum Threshold Do loss model considered for simulation is log normal Begin multiplicative. The path loss exponent value is chosen to be 2. Performance measures the average localization error and Employed bees’ phase computational time is obtained after simulation in matlab. All For i=1 to N the numerical figures mentioned in the paper related to the results are obtained by taking the average of all the values Generate a candidate solution v for x and evaluate 𝑣 from i i (given in table 2 and 3) with respect to the communication 𝑥 (equation 5) range which varies from 10m to 100m. The average If fitness of v > x Then swap values localization error and computation time obtained through i i simulation of ABC based CLA, PSO based CLA, DE based Counter (i) =0 CLA and basic CLA with respect to the different Else counter (i) = counter (i) + 1 communication range is given in subsection 4.1 and 4.2. End #of employed bees Parameter Setting of the value Area of interest 100×100 m Exit from loop if best found Number of nodes 200 Onlooker bees’ phase Anchor nodes 40 While i<=N Communication range 10-100m If fitness of random solution < p (probability) Generate candidate solution v for xi (using equation 5) Path loss exponent 2 If fitness of v > x Then swap values i i Path loss model Log normal multiplicative Counter (i) =0 Anchor ratio 0.2 Else counter (i) = counter (i) + 1 Table: 1 System Parameters Exit from loop if best found Average Average Average Localiza Localiza Localiza Average If i=N+1 tion tion tion Localiza Scout bees’ phase Communic Error Error Error tion ation (LE) in (LE) in (LE) in Error Solution with best value at threshold Range (m) ABC PSO DE (LE) in Solution is changed with new random solution (equation 7) based Based based Basic CLA CLA CLA CLA(m) Cycle = cycle +1 (m) (m) (m) End while 10 0.3553 1.4583 0.0599 3.9461 20 0.085 1.9961 0.0277 1.8613 Pseudocode 1 ABC based CLA 30 0.0436 0.1609 0.0153 1.3228 4. RESULTS AND DISCUSSION 40 0.0251 0.883 0.0075 0.9716 50 0.0069 0.6323 0.0032 0.8312 All the network parameters with numerical values used for 60 0.0031 0.2486 0.0024 0.6428 the simulation of basic CLA and ABC based CLA are 70 0.0081 0.1884 0.0025 0.5513 presented in the table 1. The table 1 contains the summary of ISSN: 2395-0455 ©EverScience Publications 51 𝑖𝑗 𝑖𝑗 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE 80 0.0051 0.3145 0.0012 0.4805 that the computation time is smallest in basic centroid based algorithm which suffers from large localization error. This 90 0.004 0.1339 0.0017 0.4372 computation time increases with PSO at same time 100 0.0011 0.2785 0.00098 0.3814 localization error decreases. The computation time is largest Table: 2 Comparison of Average Localization Errors for DE based algorithm although the localization error is very Average Localization Error Vs Communication Range small. For ABC based algorithm the computation time is very small as compared to the DE based CLA although the Average Localization Error (LE) in ABC based CLA 4.5 localization error for both is approximately same. It can also Average Localization Error (LE) in PSO Based CLA be concluded from the observation that the computation time Avergae Localization Error (LE) in DE based CLA increases to seven fold in ABC based CLA, three fold in PSO Average Localization Error (LE) in Basic CLA based CLA and thirty fivefold in DE based CLA if compared 3.5 with original CLA. Comput Comput Computat Computat ation ation 2.5 Communi ion Time ion Time Time in Time in cation in PSO in DE ABC Basic Range Based based based CLA (m) CLA CLA 1.5 CLA(se (second (seconds) (seconds) conds) s) 10 46.925 21.521 240.74 6.851 20 47.097 21.171 238.152 6.87 0.5 30 46.983 21.122 240.432 6.831 40 46.864 21.348 239.693 6.876 10 20 30 40 50 60 70 80 90 100 50 47.711 21.889 241.171 6.874 Communication Range(m) 60 47.724 22.198 244.233 6.973 Figure 2 Average Localization Error for Various Values of 70 47.261 22.614 244.169 6.831 Communication Range 80 48.048 22.046 243.397 6.934 90 47.208 22.058 242.897 6.883 4.1. Average Localization Error for Different Communication 100 47.692 21.836 242.959 6.845 Range: Table: 3. Comparison of computation time Table 2 presents all the values of average localization error Computation Time Vs Communication Range for ABC, PSO, DE based CLA and basic CLA obtained after Computation Time in ABC based CLA simulation for diverse values of communication range. Figure Computation Time in PSO Based CLA 2 shows the graphical illustration of average localization error Computation Time in DE based CLA Computation Time in Basic CLA for all of the localization algorithms. It can be shown from the graph that the localization error is largest in basic centroid based algorithm that reduces by using PSO but still the error is large. This error further reduces by using the ABC and DE algorithms. The performance of these two algorithms is 300 largely same for localization error. One of the common observations for all of the algorithms is that there is an inverse relation between communication range and localization error. It can also be concluded from the observation that the average localization error reduces by 95% in ABC based CLA, 45% in PSO based CLA and 99% in DE based CLA in comparison to basic CLA. 100 4.2. Computation Time for Different Communication Range: The computation time taken in simulations of ABC, PSO, DE 10 20 30 40 50 60 70 80 90 100 based CLA and basic CLA in matlab, for different Communication Range(m) communication ranges is presented in table 3. Figure 3 shows the graphical illustration of computation time for all of the Figure 3 Computaion Time for Various Values of four localization algorithms. It can be shown from the plot Communication Range ISSN: 2395-0455 ©EverScience Publications 52 Average Localization Error (m) Computation Time (seconds) International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE [11] H. S. Chagas, J. Martins, and L. Oliviera, “Genetic Algorithms and 5. CONCLUSION Simulated Annealing Optimization Methods in Wireless Sensor Networks Localization using ANN”, In IEEE International Midwest In this paper, the performance of original CLA is investigated Symposium on Circuit and Systems, 2012. and analyzed on the basis of average localization error and [12] M. S. Rahman, Y. Park, and K. Kim,, “Localization of Wireless Sensor computation time utilizing the ABC algorithm for diverse Networks using ANN”, In IEEE International Symposium on values of communication range. Results obtained from ABC Communication and Information Technology, pp. 639-642, 2009. [13] Khan, Zaki Ahmad, and Abdus Samad. "A study of machine learning based CLA are compared with PSO based CLA and in wireless sensor network." Int. J. Comput. Netw. Appl 4 (2017): 105- evolutionary algorithm, differential evolution (DE) based CLA. The numerical results obtained through simulation, [14] W. Katekaew, C. So-In, K. Rujirakul, and B. Waikham, “H-FCD: shows that the localization error is the minimal in case of Hybrid Fuzzy Centroid & DV- Hop Localization Algorithm in Wireless Sensor Networks”, In IEEE International Conference on ABC and DE based CLA as compared to basic and PSO Intelligent System, Modelling and Simulation, 2014. based CLA but the computation time, that is required to [15] A. Gopakumar, L. Jacob, “Localization in wireless sensor networks pinpoint the unknown sensor nodes, is largest in DE based using PSO”, In IET International Conference on Wireless, Mobile and localization. From the simulation results it can be concluded Multimedia Networks, pp. 227-230, Beijing, China, 2008. [16] Z. Sun, L. X. Wang, and V. Zhou, “Localization algorithm in wireless that the average localization error is reduced by 95% in ABC sensor networks based on multi-objective particle swarm based CLA, 45% in PSO based CLA and 99% in DE based optimization”, In International Journal of Distributed Sensor Networks, CLA as compared to original CLA. The computation time is vol. 11, pp. 1-9, 2015. increased by seven fold in ABC based CLA, three fold in [17] S. Shunyuan, Y. Quan, and X. Baoguo, “A node positioning algorithm in wireless sensor networks based on improved particle swarm PSO based CLA and thirty fivefold in DE based CLA in optimization”, In International Journal of Future Generation comparison to basic CLA. It is therefore, concluded that Communication and Networking, Vol. 9, pp. 179-190, 2016. considering the localization error as of prime importance, [18] R. Kulkarni, G. Venayagamoorthy, “Particle swarm optimization in ABC based CLA is the most suitable technique for the wireless sensor networks: a brief survey”, In IEEE Transaction on Systems, Man and Cybernetics, Vol. 41, pp. 262-267, 2011. localization of unknown nodes. The work can be extended to [19] A. Elsayed and M. Sharaf, “MA-LEACH: Energy Efficient Routing further reduce the localization error and computation time by Protocol for WSNs using Particle Swarm Optimization and Mobile employing advanced self-learning computing techniques. Aggregator”, International Journal of Computer Networks and Applications (IJCNA), vol.5, issue 1, 2018. REFERENCES [20] R. Harikrishnan, V. J. S. Kumar, and P. S. Ponmalar, “Differential evolution approach for localization in wireless sensor network”, In [1] I.F. Akyildiz, W. Su, Y. Sankarasubramaninam, and E. Cayirci, “A IEEE International Conference on Computational Intelligence and survey on sensor networks”, In IEEE Communication Magazine, vol Computing Research, Vol. 3, Coimbatore, India, pp. 1655–1663, 40, no. 8, pp. 102-114, 2002. [2] P. J. Voltz, and D. Hernandez, “Maximum Likelihood Time of Arrival [21] R. Harikrishnan, “An Integrated Xbee Audrino and Differential Estimation for Real-Time Physical Location Tracking of 802.1 1 Evolution Approach for Localization in Wireless Sensor Networks”, In a/g Mobile Stations in Indoor Environments Ad-hoc Positioning International Conference on Intelligent Computing, Communication & System”, In IEEE Conference, Position Location and Navigation Convergence, Procedia Computer Science, Vol. 48, 447 – 453, Symposium, 2004. Bhubaneswar, India, 2015. [3] L. Kovavisarruch, and K. C. Ho, “Alternate Source and Receiver [22] C. Hay-qing,, W. Hua, and W. Hua-kui, “An improved centroid Location Estimation Using TDoA with Receiver Position localization algorithm based on weighted average in WSN”, In Third Uncertainties”, In IEEE International Conference on Acoustic, Speech IEEE International Conference on Electronics Computer Technology, and Signal Processing, 2005. pp. 258-26, 2011. [4] D. Niculescu, and B. Nath, “Ad hoc positioning system (APS) using [23] J. Blumenthal, F. Grossmann, Golatowski, and D. Timmermann, AoA”, In IEEE Conference, INFOCOM, 2003. “Weighted centroid localization in zigbee-based sensor networks”, In [5] P. Kumar, L. Reddy, and S. Varma, “Distance Measurement and Error IEEE International Symposium on Intelligent Signal Processing, pp. 1- Estimation Scheme for RSSI Based Localization in Wireless Sensor 6, 3-5, 2007. Networks”, In IEEE Conference, Wireless Communication and Sensor [24] Q. Dong, and X. Xu, “A novel weighted centroid localization Networks, 2009. algorithm based on RSSI for an outdoor environment, In Journal of [6] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less Low Cost Outdoor Communication, Vol. 9, pp. 279-285, 2014. Localization for Very Small Devices”, In IEEE Personal [25] D. Karaboga, B. Gorkemli, C. Ozturk, and N. Karaboga, “A Communications Magazine, Volume 7, Issue 5, pp. 28 – 34, 2000. comprehensive survey: artificial bee colony (ABC) algorithm and [7] D. Niculescu, and B. Nath, “DV based positioning in ad hoc applications”, In Artif Intell Rev., Springer Science Business Media networks”, In Telecommunications Systems, vol. 22, pp. 267-280, B.V., 2012. [26] C. Ozturk, D. Karaboga, and B. Gorkemli, “Artificial bee colony [8] T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher, “Range- algorithm for dynamic deployment of wireless sensor networks”, In Free Localization Schemes for Large Scale Sensor Networks”, In Turkish Journal of Electrical Engineering & Computer Sciences, MobiCom ’03, ACM Press, pp. 81-95, 2003. Vol.20, Issue 2, 2012. [9] L. Doherty, K. S. Pister, and L. E. Ghaoui, “Convex Position [27] J. C. Bansal, H. Sharma, and S. S. Jadon, “Artificial bee colony Estimation in Wireless Sensor Networks”, In IEEE Conference ICC algorithm: a survey”, In International Journal of Advanced ’01, Vol. 3, Anchorage, AK, pp. 1655–63, 2001. Intelligence Paradigms, Vol.5, Issue 2, 2013. [10] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz, “Localization from [28] J. Kennedy, and R. Eberhart, “Particle Swarm Optimization”, In IEEE Connectivity in Sensor Networks”, In IEEE Transactions on International Conference on Neural Networks. Perth, pp. 1942-1948, Parallel and Distributed Systems, Vol. 15, No. 10, 2004. ISSN: 2395-0455 ©EverScience Publications 53 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE [29] L.Cui, C. Xu., G. Li, Z. Ming, Y. Fang and N. Lu, “A high accurate Prof. (Dr.) Brahmjit Singh is Professor in localization algorithm with DV Hop and differential evolution for Electronics and Communication Engineering wireless sensor networks ”, In Applied Soft Computing, vol. 68, pp. Department of National Institute of Technology 39-52, 2018. Kurukshetra, Haryana, India. His area of interest is [30] Q. Wan, M. Weng, and S. Liu, “Optimization of wireless sensor wireless communication, wireless networks and networks based on differential evolution algorithm”, In International wsn etc. Journal of Online and Biomedical Engineering, vol.15, issue 1, 2018. Authors Vikas Gupta is PhD Scholar in Electronics and Communication Engineering Department of National Institute of Technology Kurukshetra. He is working as Assistant Professor in Chandigarh Engineering College, Mohali, Punjab, India. His area of interest is wireless communication and sensor networks. ISSN: 2395-0455 ©EverScience Publications 54 http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png International Journal of Computer Networks and Applications Unpaywall

Centroid Based Localization Utilizing Artificial Bee Colony Algorithm

International Journal of Computer Networks and ApplicationsJun 28, 2019

Loading next page...
 
/lp/unpaywall/centroid-based-localization-utilizing-artificial-bee-colony-algorithm-7D9AkLmn0d

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Unpaywall
ISSN
2395-0455
DOI
10.22247/ijcna/2019/49655
Publisher site
See Article on Publisher Site

Abstract

International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE Centroid Based Localization Utilizing Artificial Bee Colony Algorithm Vikas Gupta Chandigarh Engineering College, Landran, Mohali, Punjab, India. vikasgupta2k11@gmail.com Brahmjit Singh National Institute of Technology, Kurukshetra, Haryana, India. brahmjit.s@gmail.com Published online: 27 June 2019 unidentified sensor nodes with good correctness, but the kind of hardware these techniques use is very costly. However, the Abstract – Estimation of position of unknown nodes is of range free location determination algorithms do not involve immense importance for proper deployment and tracking of such kinds of hardware for localization. They find the sensors. The centroid based localization algorithm (CLA) is locations of unidentified nodes by means of connectivity widely used for the localization of the sensors but its original and modified versions suffer from large positioning error. Here the information and hence entire arrangement is localized. A localization algorithm is evaluated in terms of localization error hefty amount of research papers on range free localization utilizing artificial bee colony based (ABC) algorithm. methods have been published in literature. For example, Comparison of outcome is presented through other widely used Bulusu et al. in [6] presented a centroid based location techniques including swarm based particle swarm optimization estimation algorithm that falls under the category of range (PSO) and evolutionary algorithms based differential evolution free algorithms. In this work, the receiver localizes itself to (DE) on basic centroid localization algorithm. The results the areas, which coincide with the area of the anchor nodes. obtained through simulation demonstrate that localization error is minimal in ABC and DE based CLA as compared to basic and The coinciding area is called as the centroid of the anchor PSO based schemes but the computation time is the largest in nodes. Beacon nodes or reference nodes are the other names DE based localization algorithm as compared to others. In of anchor nodes used in literature. The beacon nodes or the comparison to the basic CLA the average localization error is beacons are having some built in location determination reduced by 95% and computation time is increased by seven fold equipment. Hop count based localization algorithm DV-HOP in ABC based CLA. It may be established that having considered was presented by Niculescu et al. in [7]. The notion of this localization error of prime importance, ABC algorithm based CLA is the most suitable strategy for localization amongst all the algorithm was to replace the Euclidean distance between two three algorithms. nodes with inter node hop distance. Another range free algorithm, APIT (approximation point in triangulation test) Index Terms – Wireless Sensor Networks, Localization, was proposed by He et al. in [8]. Here three beacon nodes Artificial Bee Colony, Particle Swarm Optimization, Differential create triangular regions; the centroid formed by the Evolution, Localization Error etc. intersection of these regions is used to find out the position of 1. INTRODUCTION unknown sensor nodes. Estimation of unknown positions of sensor nodes distributed In [9], Doherty et al. presented a location estimation arbitrarily in the area of concern is termed as localization and algorithm for localizing the unknown nodes using is of immense significance. Localization plays a significant connectivity-induced based constraints that further employ a role in location of sensed events, geographic routing and semi-definite program (SDP) to resolve the localization issue. target tracking [1]. Broadly the location estimation Multi dimension scaling (MDS-MAP) algorithm was floated algorithms are separated in two classes, namely range based by Shang et al. in [10] which takes into account the and range free. Time of arrival (TOA) [2], time difference of connectivity based knowledge ‘who is in the communication arrival (TDOA) [3], angle of arrival (AOA) [4], and received range of whom’. MDS-MAP algorithm is composed of three signal strength indicator (RSSI) [5] are generally utilized steps, first deals with the estimation of rough distance algorithms those fall in the class of range based. In order to between all the nodes, second is to find the node positions localize the nodes these algorithms rely on accurate point-to- that fits the estimated distance. At last, the normalization is point assessment of position. The major benefit of these employed to determine the unknown coordinates. To improve range based algorithms is that they locate the position of the performance of these range free localization algorithms ISSN: 2395-0455 ©EverScience Publications 47 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE 2 2 different bio inspired and evolutionary algorithms based soft = √(𝑋 − 𝑋 ) + (𝑌 − 𝑌 ) (2) 𝑠𝑡𝑒 𝑎 𝑠𝑡𝑒 𝑎 computing techniques have been proposed in past by the research community. Some of the utilized techniques Here (X , Y ) depicts the actual values of coordinates of a a reported in literature are genetic algorithm [11], simulated unidentified sensor node. This algorithm is very easy and annealing [11], artificial neural networks [12][13], fuzzy inexpensive but the main disadvantage associated with this logic systems [14], particle swarm optimization (PSO) algorithm is large localization error. This error in this scheme [14][15]16][17][18][19], differential evolution [20] etc. In comes out to be within 2 to 4 meters. An improved version of general, all these algorithms optimize the research problem the original CLA algorithm is presented in [22]. Hay-qing et by considering one or more parameters. For example in PSO al. premeditated the coordinates of unknown node on the basis [14] the interest is to optimize the objective function and in of weights. They estimated the distance between transmitting the problem of localization the target is to minimize the and receiving node and decided the weights based on these localization error. In [21] the differential evolution algorithm distances. The estimated value of the unknown coordinates is is applied on RSSI (received signal strength indicator) to calculated based on the equation 3 [22]. optimize the location estimation of the unknown sensor nodes. 𝑤 ∗𝑋 +⋯+𝑤 ∗𝑋 𝑤 ∗𝑌 +⋯+𝑤 ∗𝑌 1 1 𝑛 𝑛 1 1 𝑛 𝑛 ( ) 𝑋 , 𝑌 = ( , ) (3) 𝑠𝑡𝑒 𝑠𝑒𝑡 𝑤 +⋯+𝑤 𝑤 +⋯+𝑤 1 𝑛 1 𝑛 In [14] the RSSI from reference nodes to the unidentified The weights are calculated using RSSI. This method increases nodes is taken in terms of weights and weights are optimized using fuzzy inference engine. These optimized weights the accuracy level but achievement of this improved algorithm extremely depends upon the optimization of these further improve the average localization error. Use of these soft computing techniques by the research community to weights which is a tedious task. Blumenthal et al. [23] presented a weighted centroid algorithm for the estimation of optimize the positioning error motivates us to use ABC algorithm. So in this research article, the original centroid position of unknown sensor nodes. They investigated the theoretical and practical aspects of RSSI measurements and localization algorithm (CLA) is examined and its performance is evaluated using ABC algorithm. Further, the studied the impact on localization error. Although the localization error obtained from this method is less than 1 m same algorithm is first studied with swarm intelligence based PSO algorithm, then with evolutionary algorithm based DE but one of the disadvantages of this method is that it do not take into account the environmental abnormalities while algorithm, and a comparison of these algorithms is made. Remaining structure of paper is separated into 5 sections. estimating the unknown coordinates. Quande et al. [24] proposed a weight compensated RSSI based weighted CLA. Related work in detail is presented in section 2. Simulation of ABC based CLA is given in section 3. Section 4 discuss in The algorithm is simple to implement consume less power and increases the accuracy of localization compared to other detail the results and discussion. Conclusions followed by references are presented in section 5. weighted CLAs. Although the localization error is reduced to 2.81 m but still the localization error is too big which need to 2. RELATED WORK be reduced further. Therefore, the sole objective of present research is to optimize the localization error of basic centroid 2.1. Basic Centroid Localization Algorithm based algorithm. In [6] Bulusu et al. presented an idealized connectivity based 2.2. Natural Behavior of Honey Bees model for outdoor propagation under uncluttered environment. They assumed equal power for all the nodes. In The honey bees follow a collective intelligent behavior in the this model the reference are put on known locations. The search of the food. They are intelligent on the basis of their unknown nodes localize themselves in the region that capacity to share, memorize and store the information. As the coincides with the region of intersection of the anchors. They environment change their behavior also changes. This estimated the position of unknown sensor nodes using intellectual behavior of the bees inspires the researchers to equation 1 [6]. replicate this conduct of bees. In the camp of the bees, three categories exist: first the employed bees (EB), second the 𝑋 +𝑋 +⋯+𝑋 𝑌 +𝑌 +⋯+𝑌 𝑖 1 𝑖 2 𝑖𝑘 𝑖 1 𝑖 2 𝑖𝑘 (𝑋 , 𝑌 ) = ( , ) (1) onlookers bees (OB), and third the scouts bees (SB). Out of 𝑠𝑡𝑒 𝑠𝑒𝑡 𝑘 𝑘 these EBs are connected with the source of food, OBs chooses the food source. The SBs randomly hunt all sources of food. Here (X , Y ) is the estimated value of unknown est est At the start, the scout bees reveal the entire foodstuff. Both coordinates of sensor node and the number k represents the EBs and OBs keep on exploiting the nectar present in each amount of reference nodes. The performance measure used to food source until all nectar is bushed. After this the employed determine the accuracy of this method called as localization bees becomes scout bees and start probing the food sources error (LE) can be described with the equation 2 [6]. ISSN: 2395-0455 ©EverScience Publications 48 𝐿𝐸 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE again. General architecture of algorithm of ABC may be discard the older ones. This position updation is represented described as [25] by equation 5 [27]. Repeat 𝑣 = 𝑥 + 𝜙 (𝑥 − 𝑥 ) (5) Employed Bee (EBs) stage Where 𝜙 (𝑥 − 𝑥 ) is called as step size, k Є {1, 2...N} and j Є {1, 2... d} are two arbitrarily selected indices. And k and i Onlooker Bees (OBs) stage are chosen to be of different values so as to have some Scout Bees (SBs) stage significant contribution of step size, 𝜙 whose value lies in between [–1, 1]. Remember the optimized result obtained 2.2.4. Onlooker Bees Phase Until (the threshold reaches) In OBs phase, the suitability of updated solutions and the 2.2.1. Localization Using ABC Algorithm positional data are shared with OBs present in hive. These The ABC algorithm [25][26][27] comes under the category of bees analyses existing knowledge and pick a resolution based swarm intelligence based soft computing technique that uses on some probability. This probability (P ) is given by equation the food finding activities of honey bees to optimize the 6 [27]. solution. In the context of localization problem, all food 𝑡𝑓𝑖 sources represent all the sensors nodes scattered in the area of 𝑃 = (6) 𝑖 𝑁 ∑ 𝑡𝑓𝑖 𝑖 =1 interest. The degree of sweetness or nectar present in the food th source gives the level of suitability of the outcome. To get the Where 𝑡𝑓𝑖 is the worth of fitness for the i solution. optimized value of localization error, it is considered as the 2.2.5. Scout Bees Phase objective function. The control parameters are decided and scout bees (SBs) initialize the inhabitants of food references In SBs, if solutions obtained by the employed bees cannot be (or solutions). In first phase the EBs hunt for all new available enhanced further even after a predetermined threshold, the food references having large nectar present in the vicinity of employed bees now become the scouts and current solutions the these references. Every time after discovering the new obtained by them are discarded. The scouts again begin food references, the greedy selection algorithm between new moving arbitrarily in the hunt for new sources (or solutions). obtained solution and its parent is used to obtain new fitness The preset number of cycle or the limit of rejection is an value. This food references information is conveyed by the important control parameter. Let us suppose that the discarded EBs with OBs waiting in the hive with the help of a dance on solution is x, the scout bees replace this source (solution) with the dancing area. Based on the knowledge given by the EBs, newer on the basis of equation 7[27] the OBs select their food probabilistically for which fitness 𝑗 𝑗 𝑗 𝑗 [ ] 𝑥 = 𝑥 + 𝑎𝑛𝑑𝑟 0,1 (𝑥 − 𝑥 ), ∀ = 1,2, … 𝑑 (7) selection method, roulette wheel selection is employed. The 𝑗 𝑖 𝑖𝑚𝑛 𝑖𝑚𝑛 sources that are poor or exploited are deserted and scout bees Where and are the lower and upper restrictions of start to seek new solutions. These steps are replicated in jth direction. repeatedly in anticipation of a threshold. 2.3. Particle Swarm Optimization 2.2.2. Initialization of Population In 1995, Eberhart and Kennedy [28] presented a swarm-based Initially, the artificial bee colony algorithm produces algorithm called as PSO. Algorithm was developed by inhabitants of evenly distributed solutions where each studying the conduct of bird flocking. Although PSO is very solution x (i = 1, 2... N) depicts a d-dimensional vector. Here simple and akin to genetic algorithm but it does not exploit x represents the ith food source and d signifies the variables crossover or mutation. Because of the simplicity and fewer present in the problem of optimization. Generation of each mathematical expressions involved, PSO is easy to food source can be presented by the given equation 4 [27]. implement. Originally, the aim was to emulate the conduct of [ ] 𝑥 = 𝑥 + 𝑎𝑛𝑑𝑟 0,1 (𝑥 − 𝑥 ) (4) min 𝑗 max 𝑗 min 𝑗 birds in a very easy way but later on it emerged as a very good algorithm to discover the optimum solutions. Each Where x is the lower and x is the upper restriction of x min j max j i solution, which is to be optimized, is represented by a bird or in the jth direction. particle in the hunt space. To obtain optimum results the 2.2.3. Employed Bees Phase solution having greatest fitness value is chosen for the objective function. In [15][16][17][18][19] the PSO algorithm Here the existing solution is modified on the basis of its is initialized by taking a arbitrary inhabitants of the particles fitness value. Depending upon the worth of fitness of fresh which search for the paramount solution in hunt space. Here solution, the bees update their position with newer value and in PSO the personal best (Pbest) is the individual best of a ISSN: 2395-0455 ©EverScience Publications 49 𝑖𝑗 𝑚𝑎𝑥 𝑖𝑗 𝑘𝑗 𝑖𝑗 𝑖𝑗 𝑘𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE particle and the global best (gbest) is the collective best many problems. So here ABC algorithm is applied on considered among all the particles. Updation of velocity and centroid based algorithm for diverse values of an important position is done using the equation 8 and 9. network parameter, the communication range. So in the present work the effects of swarm based technique ABC on ( ) ( ) ( ) 𝑡 + 1 = 𝑤 . 𝑡 + 𝑐 1. 𝑎𝑛𝑑𝑟 (). (𝑏𝑒𝑝𝑡𝑃𝑠 𝑡 − localization error in wsn are studied. In algorithm of ABC (𝑡 )𝑐 2. 𝑎𝑛𝑑𝑟 (). (𝑔𝑏𝑒𝑠𝑃𝑡 (𝑡 ) (𝑡 )) (8) best position of food source denotes the best possible solution in the problem of optimization. While using the ABC (𝑡 + 1) = (𝑡 ) + (𝑡 + 1) (9) algorithm in wsn each food resource represents the In the above equations x (t + 1) is the updated new position distribution of sensors in the area of interest and the amount and v (t + 1) is the updated new velocity. Another important of nectar present in the food resource shows the height of factor w represents the weight assigned to the first part of the fitness of the solution. And localization error that is to be equation 8, w.v (t) which is termed as the inertia term. The optimized (given in equation 2) is considered as the objective succeeding part of the equation 8 that represents the function. The goal of the bees in ABC algorithm is to unearth individual behavior of the particle is called as cognition part the best possible solution and three categories of the bees and third part that represents the collective behavior of the namely the EBs, OBs and the SBs fulfill this goal. The EBs particles is called as the social part. In both parts, c1 and c2 exploits the food source and shares this knowledge with the are acceleration coefficients which are constant terms. Here OBs. In terms of localization problem the best position is the localization error (equation 2) is taken as the objective determined by the employed bees using equation 5. The function and the optimized localization error is determined onlooker bees evaluate this sweetness (nectar) information using PSO. using certain threshold. For localization problem this is the probability given in equation 6 which acts as threshold. The 2.4. Differential Evolution onlooker bees become the scout bees after all the nectar is In localization of unknown nodes in wsn, the problem of exhausted or if the quality of nectar is below the threshold. localization is taken as the problem of differential evolution These scout bees again start searching the newer food source and the optimized solution is found. Like genetic algorithm using equation 7. The minimum localization error is the best the differential evolution algorithm is also an algorithm which solution achieved from the ABC algorithm. The proposed is based on population that employs the same operators: approach, in very simplified manner is presented here with crossover, mutation and selection [20][21][29][30]. In the help of an architectural diagram as shown in the Figure 1. general, the genetic algorithm relies on crossover whereas the It can be easily understood from the diagram that approach DE relies on mutation. The mutation is given importance as it starts with simulation of basic centroid based localization gives good parametric variations and diverse results. The algorithm (CLA). Due to the large localization error in CLA, equation of mutation is given by soft computing techniques are employed to reduce or 𝑢𝑚𝑡𝑑𝑡𝑎𝑒 optimize this error. For doing so the localization error is 𝑀 = 𝑀 + 𝑆 ∗ (𝑇 − 𝑅 ) (10) 𝑡 𝑠𝑡𝑏𝑒 𝑣 𝑣 assumed as the objective function to be optimized. Then Where M is the best solution, Mt is the mutated value, S is best ABC algorithm is used on basic CLA and results obtained are the scaling factor and T and R are the targeted and V V compared with PSO and DE based CLA. randomly selected positions. Here also the localization error is considered as fitness function of DE and the optimum fitness function is found by mutation (equation 10), cross over and selection. 3. SIMULATION OF ABC BASED CENTROID LOCALIZATION ALGORITHM In wireless sensor networks (wsn) the problem associated with the localization is the error in estimation of exact coordinates of the unknown nodes. Here first the basic CLA Figure 1 An Architectural Diagram of the Proposed is studied and simulated in matlab and then localization error Approach is premeditated by estimating the distinction between actual and estimated values of coordinates of unidentified sensor The localization error and computation time for both basic nodes. To reduce the error in CLA based algorithm a big and ABC based CLA is premeditated by changing the number of swarm based soft computing techniques have been communication range. Then the performance of CLA is proposed in past. But very little work has been done using studied and simulated by applying the PSO and DE ABC algorithm which is a very good optimization algorithm algorithms. The simulation outcomes demonstrate that the and extensively used method to find the optimum solutions of ABC based algorithm outperform other algorithms. The ISSN: 2395-0455 ©EverScience Publications 50 𝑣𝑖 𝑥𝑖 𝑥𝑖 𝑥𝑖 𝑥𝑖 𝑣𝑖 𝑣𝑖 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE pseudocode for the whole ABC based centroid localization the parameters chosen and mathematical values used for the algorithm is presented in sub section 3.1. simulation environment. All the terms used in the table 1 are self-explanatory. As indicated in table 1 an area of 100 sqm is 3.1. Pseudocode of ABC based CLA considered and 200 sensor nodes are spread arbitrarily in this The pseudocode 1 represents the ABC based CLA. area. As the coordinates of these unknown nodes in centroid based localization is estimated on the basis of some anchor Objective function (equation 2) nodes so in the same area of 100sqm 40 anchor nodes (the nodes having GPS like arrangements) are also randomly Initialize food source or solutions N (equation 4) distributed. That means the anchor ratio chosen is .2 (anchor Cycle=1; nodes divided by the total number of nodes). The communication range is varied from 10m to 100m. The path While cycle <= Maximum Threshold Do loss model considered for simulation is log normal Begin multiplicative. The path loss exponent value is chosen to be 2. Performance measures the average localization error and Employed bees’ phase computational time is obtained after simulation in matlab. All For i=1 to N the numerical figures mentioned in the paper related to the results are obtained by taking the average of all the values Generate a candidate solution v for x and evaluate 𝑣 from i i (given in table 2 and 3) with respect to the communication 𝑥 (equation 5) range which varies from 10m to 100m. The average If fitness of v > x Then swap values localization error and computation time obtained through i i simulation of ABC based CLA, PSO based CLA, DE based Counter (i) =0 CLA and basic CLA with respect to the different Else counter (i) = counter (i) + 1 communication range is given in subsection 4.1 and 4.2. End #of employed bees Parameter Setting of the value Area of interest 100×100 m Exit from loop if best found Number of nodes 200 Onlooker bees’ phase Anchor nodes 40 While i<=N Communication range 10-100m If fitness of random solution < p (probability) Generate candidate solution v for xi (using equation 5) Path loss exponent 2 If fitness of v > x Then swap values i i Path loss model Log normal multiplicative Counter (i) =0 Anchor ratio 0.2 Else counter (i) = counter (i) + 1 Table: 1 System Parameters Exit from loop if best found Average Average Average Localiza Localiza Localiza Average If i=N+1 tion tion tion Localiza Scout bees’ phase Communic Error Error Error tion ation (LE) in (LE) in (LE) in Error Solution with best value at threshold Range (m) ABC PSO DE (LE) in Solution is changed with new random solution (equation 7) based Based based Basic CLA CLA CLA CLA(m) Cycle = cycle +1 (m) (m) (m) End while 10 0.3553 1.4583 0.0599 3.9461 20 0.085 1.9961 0.0277 1.8613 Pseudocode 1 ABC based CLA 30 0.0436 0.1609 0.0153 1.3228 4. RESULTS AND DISCUSSION 40 0.0251 0.883 0.0075 0.9716 50 0.0069 0.6323 0.0032 0.8312 All the network parameters with numerical values used for 60 0.0031 0.2486 0.0024 0.6428 the simulation of basic CLA and ABC based CLA are 70 0.0081 0.1884 0.0025 0.5513 presented in the table 1. The table 1 contains the summary of ISSN: 2395-0455 ©EverScience Publications 51 𝑖𝑗 𝑖𝑗 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE 80 0.0051 0.3145 0.0012 0.4805 that the computation time is smallest in basic centroid based algorithm which suffers from large localization error. This 90 0.004 0.1339 0.0017 0.4372 computation time increases with PSO at same time 100 0.0011 0.2785 0.00098 0.3814 localization error decreases. The computation time is largest Table: 2 Comparison of Average Localization Errors for DE based algorithm although the localization error is very Average Localization Error Vs Communication Range small. For ABC based algorithm the computation time is very small as compared to the DE based CLA although the Average Localization Error (LE) in ABC based CLA 4.5 localization error for both is approximately same. It can also Average Localization Error (LE) in PSO Based CLA be concluded from the observation that the computation time Avergae Localization Error (LE) in DE based CLA increases to seven fold in ABC based CLA, three fold in PSO Average Localization Error (LE) in Basic CLA based CLA and thirty fivefold in DE based CLA if compared 3.5 with original CLA. Comput Comput Computat Computat ation ation 2.5 Communi ion Time ion Time Time in Time in cation in PSO in DE ABC Basic Range Based based based CLA (m) CLA CLA 1.5 CLA(se (second (seconds) (seconds) conds) s) 10 46.925 21.521 240.74 6.851 20 47.097 21.171 238.152 6.87 0.5 30 46.983 21.122 240.432 6.831 40 46.864 21.348 239.693 6.876 10 20 30 40 50 60 70 80 90 100 50 47.711 21.889 241.171 6.874 Communication Range(m) 60 47.724 22.198 244.233 6.973 Figure 2 Average Localization Error for Various Values of 70 47.261 22.614 244.169 6.831 Communication Range 80 48.048 22.046 243.397 6.934 90 47.208 22.058 242.897 6.883 4.1. Average Localization Error for Different Communication 100 47.692 21.836 242.959 6.845 Range: Table: 3. Comparison of computation time Table 2 presents all the values of average localization error Computation Time Vs Communication Range for ABC, PSO, DE based CLA and basic CLA obtained after Computation Time in ABC based CLA simulation for diverse values of communication range. Figure Computation Time in PSO Based CLA 2 shows the graphical illustration of average localization error Computation Time in DE based CLA Computation Time in Basic CLA for all of the localization algorithms. It can be shown from the graph that the localization error is largest in basic centroid based algorithm that reduces by using PSO but still the error is large. This error further reduces by using the ABC and DE algorithms. The performance of these two algorithms is 300 largely same for localization error. One of the common observations for all of the algorithms is that there is an inverse relation between communication range and localization error. It can also be concluded from the observation that the average localization error reduces by 95% in ABC based CLA, 45% in PSO based CLA and 99% in DE based CLA in comparison to basic CLA. 100 4.2. Computation Time for Different Communication Range: The computation time taken in simulations of ABC, PSO, DE 10 20 30 40 50 60 70 80 90 100 based CLA and basic CLA in matlab, for different Communication Range(m) communication ranges is presented in table 3. Figure 3 shows the graphical illustration of computation time for all of the Figure 3 Computaion Time for Various Values of four localization algorithms. It can be shown from the plot Communication Range ISSN: 2395-0455 ©EverScience Publications 52 Average Localization Error (m) Computation Time (seconds) International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE [11] H. S. Chagas, J. Martins, and L. Oliviera, “Genetic Algorithms and 5. CONCLUSION Simulated Annealing Optimization Methods in Wireless Sensor Networks Localization using ANN”, In IEEE International Midwest In this paper, the performance of original CLA is investigated Symposium on Circuit and Systems, 2012. and analyzed on the basis of average localization error and [12] M. S. Rahman, Y. Park, and K. Kim,, “Localization of Wireless Sensor computation time utilizing the ABC algorithm for diverse Networks using ANN”, In IEEE International Symposium on values of communication range. Results obtained from ABC Communication and Information Technology, pp. 639-642, 2009. [13] Khan, Zaki Ahmad, and Abdus Samad. "A study of machine learning based CLA are compared with PSO based CLA and in wireless sensor network." Int. J. Comput. Netw. Appl 4 (2017): 105- evolutionary algorithm, differential evolution (DE) based CLA. The numerical results obtained through simulation, [14] W. Katekaew, C. So-In, K. Rujirakul, and B. Waikham, “H-FCD: shows that the localization error is the minimal in case of Hybrid Fuzzy Centroid & DV- Hop Localization Algorithm in Wireless Sensor Networks”, In IEEE International Conference on ABC and DE based CLA as compared to basic and PSO Intelligent System, Modelling and Simulation, 2014. based CLA but the computation time, that is required to [15] A. Gopakumar, L. Jacob, “Localization in wireless sensor networks pinpoint the unknown sensor nodes, is largest in DE based using PSO”, In IET International Conference on Wireless, Mobile and localization. From the simulation results it can be concluded Multimedia Networks, pp. 227-230, Beijing, China, 2008. [16] Z. Sun, L. X. Wang, and V. Zhou, “Localization algorithm in wireless that the average localization error is reduced by 95% in ABC sensor networks based on multi-objective particle swarm based CLA, 45% in PSO based CLA and 99% in DE based optimization”, In International Journal of Distributed Sensor Networks, CLA as compared to original CLA. The computation time is vol. 11, pp. 1-9, 2015. increased by seven fold in ABC based CLA, three fold in [17] S. Shunyuan, Y. Quan, and X. Baoguo, “A node positioning algorithm in wireless sensor networks based on improved particle swarm PSO based CLA and thirty fivefold in DE based CLA in optimization”, In International Journal of Future Generation comparison to basic CLA. It is therefore, concluded that Communication and Networking, Vol. 9, pp. 179-190, 2016. considering the localization error as of prime importance, [18] R. Kulkarni, G. Venayagamoorthy, “Particle swarm optimization in ABC based CLA is the most suitable technique for the wireless sensor networks: a brief survey”, In IEEE Transaction on Systems, Man and Cybernetics, Vol. 41, pp. 262-267, 2011. localization of unknown nodes. The work can be extended to [19] A. Elsayed and M. Sharaf, “MA-LEACH: Energy Efficient Routing further reduce the localization error and computation time by Protocol for WSNs using Particle Swarm Optimization and Mobile employing advanced self-learning computing techniques. Aggregator”, International Journal of Computer Networks and Applications (IJCNA), vol.5, issue 1, 2018. REFERENCES [20] R. Harikrishnan, V. J. S. Kumar, and P. S. Ponmalar, “Differential evolution approach for localization in wireless sensor network”, In [1] I.F. Akyildiz, W. Su, Y. Sankarasubramaninam, and E. Cayirci, “A IEEE International Conference on Computational Intelligence and survey on sensor networks”, In IEEE Communication Magazine, vol Computing Research, Vol. 3, Coimbatore, India, pp. 1655–1663, 40, no. 8, pp. 102-114, 2002. [2] P. J. Voltz, and D. Hernandez, “Maximum Likelihood Time of Arrival [21] R. Harikrishnan, “An Integrated Xbee Audrino and Differential Estimation for Real-Time Physical Location Tracking of 802.1 1 Evolution Approach for Localization in Wireless Sensor Networks”, In a/g Mobile Stations in Indoor Environments Ad-hoc Positioning International Conference on Intelligent Computing, Communication & System”, In IEEE Conference, Position Location and Navigation Convergence, Procedia Computer Science, Vol. 48, 447 – 453, Symposium, 2004. Bhubaneswar, India, 2015. [3] L. Kovavisarruch, and K. C. Ho, “Alternate Source and Receiver [22] C. Hay-qing,, W. Hua, and W. Hua-kui, “An improved centroid Location Estimation Using TDoA with Receiver Position localization algorithm based on weighted average in WSN”, In Third Uncertainties”, In IEEE International Conference on Acoustic, Speech IEEE International Conference on Electronics Computer Technology, and Signal Processing, 2005. pp. 258-26, 2011. [4] D. Niculescu, and B. Nath, “Ad hoc positioning system (APS) using [23] J. Blumenthal, F. Grossmann, Golatowski, and D. Timmermann, AoA”, In IEEE Conference, INFOCOM, 2003. “Weighted centroid localization in zigbee-based sensor networks”, In [5] P. Kumar, L. Reddy, and S. Varma, “Distance Measurement and Error IEEE International Symposium on Intelligent Signal Processing, pp. 1- Estimation Scheme for RSSI Based Localization in Wireless Sensor 6, 3-5, 2007. Networks”, In IEEE Conference, Wireless Communication and Sensor [24] Q. Dong, and X. Xu, “A novel weighted centroid localization Networks, 2009. algorithm based on RSSI for an outdoor environment, In Journal of [6] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less Low Cost Outdoor Communication, Vol. 9, pp. 279-285, 2014. Localization for Very Small Devices”, In IEEE Personal [25] D. Karaboga, B. Gorkemli, C. Ozturk, and N. Karaboga, “A Communications Magazine, Volume 7, Issue 5, pp. 28 – 34, 2000. comprehensive survey: artificial bee colony (ABC) algorithm and [7] D. Niculescu, and B. Nath, “DV based positioning in ad hoc applications”, In Artif Intell Rev., Springer Science Business Media networks”, In Telecommunications Systems, vol. 22, pp. 267-280, B.V., 2012. [26] C. Ozturk, D. Karaboga, and B. Gorkemli, “Artificial bee colony [8] T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher, “Range- algorithm for dynamic deployment of wireless sensor networks”, In Free Localization Schemes for Large Scale Sensor Networks”, In Turkish Journal of Electrical Engineering & Computer Sciences, MobiCom ’03, ACM Press, pp. 81-95, 2003. Vol.20, Issue 2, 2012. [9] L. Doherty, K. S. Pister, and L. E. Ghaoui, “Convex Position [27] J. C. Bansal, H. Sharma, and S. S. Jadon, “Artificial bee colony Estimation in Wireless Sensor Networks”, In IEEE Conference ICC algorithm: a survey”, In International Journal of Advanced ’01, Vol. 3, Anchorage, AK, pp. 1655–63, 2001. Intelligence Paradigms, Vol.5, Issue 2, 2013. [10] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz, “Localization from [28] J. Kennedy, and R. Eberhart, “Particle Swarm Optimization”, In IEEE Connectivity in Sensor Networks”, In IEEE Transactions on International Conference on Neural Networks. Perth, pp. 1942-1948, Parallel and Distributed Systems, Vol. 15, No. 10, 2004. ISSN: 2395-0455 ©EverScience Publications 53 International Journal of Computer Networks and Applications (IJCNA) DOI: 10.22247/ijcna/2019/49655 Volume 6, Issue 3, May – June (2019) RESEARCH ARTICLE [29] L.Cui, C. Xu., G. Li, Z. Ming, Y. Fang and N. Lu, “A high accurate Prof. (Dr.) Brahmjit Singh is Professor in localization algorithm with DV Hop and differential evolution for Electronics and Communication Engineering wireless sensor networks ”, In Applied Soft Computing, vol. 68, pp. Department of National Institute of Technology 39-52, 2018. Kurukshetra, Haryana, India. His area of interest is [30] Q. Wan, M. Weng, and S. Liu, “Optimization of wireless sensor wireless communication, wireless networks and networks based on differential evolution algorithm”, In International wsn etc. Journal of Online and Biomedical Engineering, vol.15, issue 1, 2018. Authors Vikas Gupta is PhD Scholar in Electronics and Communication Engineering Department of National Institute of Technology Kurukshetra. He is working as Assistant Professor in Chandigarh Engineering College, Mohali, Punjab, India. His area of interest is wireless communication and sensor networks. ISSN: 2395-0455 ©EverScience Publications 54

Journal

International Journal of Computer Networks and ApplicationsUnpaywall

Published: Jun 28, 2019

There are no references for this article.