 Open Access
 Total Downloads : 28
 Authors : Divya P. L.
 Paper ID : IJERTCONV3IS08017
 Volume & Issue : NSNMN – 2015 (Volume 3 – Issue 08)
 Published (First Online): 24042018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Swarm Intelligence for Sensor Localization
Divya P. L.
Heera College of Engineering and Technology Panavoor , Trivandrum
AbstractWireless sensor networks (WSNs) consist of dis tributed autonomous devices which sense the environmental or physical conditions cooperatively and pass the information through the network to a base station. Sensor Localization is fundamental challenge in WSN. Location information of the node is critically important to detect an event or for routing the packet via the network. In this paper localization is modeled as a multi dimensional optimization problem and solved using bio inspired algorithms, because of their quick convergence to quality solutions. Distributive localization is addressed using Particle Swarm Optimization (PSO) and comprehensive learning particle swarm optimization (CLPSO). The performances of both the algorithms are studied. Accuracy of both algorithms are analyzed using parameters such as number of nodes localized, computational time and localization error. Comparison of both the results are presented. Simulation result show that the PSO based localization is faster and CLPSO is more accurate.
Key wordsParticle Swarm Optimization, Comprehensive Parti cle Swarm Optimization, Localization, Wireless Sensor Network

INTRODUCTION
A wireless sensor network (WSN) consists of distributed au tonomous devices which senses the environmental or physical conditions cooperatively and passes the information through the network to the base station. Each sensor node has a CPU, battery supply, limited number of sensors and a radio transceiver for communication [1]. WSN is used in many applications such as area monitoring, structural monitoring, industrial monitoring, water monitoring etc. In all these ap plications each sensor nodes are deployed such a way that they operate in dynamic environment. Each sensor node has onboard radio which is used to send the collected data to the base station either directly or via multiple hops. The main Problems in WSN are scale and density of deployment, environmental uncertainties and constraints in energy, memory, bandwidth and computing resource.
Sensor localization is a fundamental challenge in WSN. It is process of determining the physical coordinates of individual the sensor node in WSN. The need for localization problem is closely related to how the nodes are deployed. Localization is a onetime optimization process in which solution quality is more important than fast convergence [2]. When the network size is small and the area to be monitored is humanaccessible, each node can easily be deployed manually and their locations can be registered during deployment. In more complex cases, when the area is not humanaccessible and/or there are many nodes in the network, then manual deployment is infeasible or impossible to achieve. In such situation, then nodes should be deployed by a vehicle, which is generally assumed to be an
airplane or helicopter. An example can be a forest fire detection system where nodes should be deployed by a plane over the region.
Global Positioning System (GPS) can be used for local ization purpose which gives accurate results, but the main disadvantage is that GPS cannot function in indoor and many outdoor applications, especially when there is no direct line of sight from nodes to terrestrial satellites. Besides, the use of these devices on sensor nodes is still not a good solution due to their size, price and energy consumption. Therefore, a localization algorithm may be the only option for locating sensor nodes for many WSN applications.
A WSN consists of N nodes, each having a communica tion range of r, distributed in a mission field. The WSN is represented as the Euclidean graph G = (V, E), where V =
{v1,v2,…,vn} is the set of sensor nodes. i,j E if the distance between vi and vj is dij r. let S be the beacon nodes and U be the unknown nodes. let (xb, yb) be the position of beacon nodes, for all b B, it is desired to find the position (xu, yu) of as many uU as possible, transforming the unknown nodes into settled nodes S.
Unknown Nodes (U ): The nodes whose position is not known is called dumb nodes or unknown nodes. The main aim of the localization system is to estimate the physical coordinate of as much dumb nodes as possible.
Beacon nodes (B): The nodes whose position is known already are called beacons, reference or anchor nodes. These nodes will be having hardware such as GPS to find the position of the node or they will be deployed in position whose coordinate is known already.
Settled nodes (s): The node whose position is unknown at the beginning but later the position of node is estimated using localization system. The main parameters that determine quality of the localization system are number of settled nodes and the estimated position error.
The aim of this paper is to achieve efficient localization using bio inspired approach which is more accurate. CI approach is chosen for localization because it is flexible, gives optimal result and requires less memory when compared to other approaches. This localization algorithm makes use of beacon nodes, this is the first assumption. The node deployment is assumed to be achieved by means of an autonomous or human controlled vehicle therefore; manual registration of node loca tions is not possible. Lastly, the field over which the WSN is laid is assumed to be a forest and this assumption is made because a forest is one of the most challenging environments
for a WSN. In this paper localization is addressed as a multi dimensional optimization problem. Swarm Intelligence techniques Particle swarm Optimization and Comprehensive Learning Particle swarm optimization (CLPSO) is used to solve the localization problem. Performance study of PSO and CLPSO based localization are done using the parameters such as number of nodes localized, computational time and computational accuracy. It is observed that PSO converges into result faster compared to CLPSO and CLPSO gives more accurate result. Simulation results are also presented.
The rest of the paper is organized as follows. Brief information on similar approaches in the literature are presented in section
2. The algorithms considered for localization problem are described in Section 3. The localization approach is presented in Section 4. Discussion on simulation results is done in Section 4. Finally, conclusion and future work in Section 6.

RELATED WORKS
A survey on localization system is described in [1]. Computational Intelligence (CI) provides adaptive mechanism that exhibit intelligent behavior in complex and dynamic environment. In [2] issues in WSNs are formulated as multidimensional optimization problems, and are approached through bioinspired techniques and a brief survey on PSO is also given. In the current research swarm intelligence technique is used to solve the sensor localization problem.
WSN localization is treated as a multidimensional optimization problem and PSO is proposed for centralized localization of WSN nodes in [3]. A genetic algorithm (GA) based node localization algorithm is presented in [6]. This centralized algorithm determines locations of all dumb nodes by using an estimate of their distances from all onehop neighbors. PSO is proposed for centralized localization of WSN nodes in [4]. A position estimation approach in a sensor network using convex optimization is presented in [5]. In this paper a centralized approach is used to solve the problem, where each node relays its connection statistics to a centralized authority which hen computes the global solution. A twophase centralized localization scheme which uses approches simulated annealing and GA is presented in [6]. A centralized localization method that uses a combination of GA and simulated annealing algorithm proposed in [7]. This addresses the flip ambiguity problem. The centralized approach scales poorly with the size of the network.
An efficient localization system that extends GPS capabil ities to nonGPS nodes in an ad hoc network is proposed in [8]. An investigation on distributed localization using particle swarm optimization (PSO) and bacterial foraging algorithm (BFA) is presented in [9] . The performance of PSO and BFA algorithms are studied in this paper. The distributed algorithm has much better scaling properties than a centralized solution and a lower communication cost, because the nodes are not required to relay information; therefore, distributed solutions are more attractive for large networks containing thousands
of nodes. So in the proposed system iterative distributed localization approach is used for sensor localization.
The realtime results comparison of PSObeaconless algorithm with GaussNewton algorithm is presented in [10]. It is ob served that PSO has more localization accuracy than Gauss Newton algorithm. Here, we compared localization accuracy of PSO algorithms is compared with CLPSO.

BIOINSPIRED ALGORITHMS
Particle swarm optimization (PSO) is a population based stochastic optimization technique which shares many sim ilarities with evolutionary computation techniques such as Genetic Algorithms (GA) [11]. PSO is introduced in [12]. The system is initialized with a population of random solutions and recursively searches for optima by updating generations. Variants of PSO are used in diverse fields for optimaizing a problem[13]. In past several years, PSO has been suc cessfully applied in many research and application areas[14]. It is demonstrated that PSO gets better results in a faster, cheaper way compared with other methods. Many versions of PSO have been proposed and applied in areas, including multirobot navigation, power systems, pattern classification and electromagnetic [2].
PSO consists of swarm (population) of s particles, each one of them is a candidate solution. These particles searches for global solution in n dimensional space, n is the number of parameters to be optimized. Each particle has a position represented by Xid and velocity V id where i ranges from
1is and d ranges from 1dn. Each particle in the
swarm is evaluated by an objective function f (x1, x2, …, xn). The fitness of a particle is determined from its position in the
search space. The cost of a particle closer to the global solution is lower than that of a particle that is farther. Alternately, the fitness of a particle closer to the global solution is higher than that of a particle that is farther. PSO tries to minimize or maximize the fitness function. The fitness function is chosen based on the problem to be solved. In each iteration the velocity and position of all the particle is updated to get higher fitness. Each particle has its best value called P bestid .The global best value is Gbest .At each iteration k velocity Vid and position Xid of the particle updated using the formula
Vid(k) = wVid(k 1) + c1r1id(k)(Xpbestid Xid) (1)
+ c2r2id(k(Xgbestd Xid)
Xid(k) = Xid(k 1) + Vid(k) (2)
Here, r1 and r2 are the random numbers with a uniform distribution in the range [0, 1]. Velocity update is dependent on three components of accelaration.w is the inertia of the particle which changes linearly in each iteration 0.2 w 0.9. Psuedocode for PSO is given in [9].
A. Comprehensive Learnig Particle Swarm Optimization
A CLPSO Learning Strategy is
V d =wÃ— +cÃ—randi Ã—(pbestf (3)
i i i(d) i )
Algorithm 1 Comprehensive Learning PSO
1: Intialize position X,Velocity V , P best and Gbest
2: Intialze w0 = 0.9, w1 = 0.4, c = 1.49445 and m = 7
3: while K < Kmax do
Algorithm 2 Procedure for selection for exembler for particle
i
0s(i11) )1
1: Intialize pci = 0.05 + 0.45 exex 2: p(10)1
for each dimension d do
4: w(k) = w0 Ã— (wm0awxg1eÃ—nk)
5: for i = 0 : s do do
6: if (f lagi m) then
7: call Procedure select exembler()
3: if f 1i = pci) then
4:
5: f 2i = rand2i s
8: flag = 0
6: if f (pbestf 1d)>f(pbestf2d ) then
i i
i i
7: fdi =f1i
9: end if
10: for each dimension d do
11: compute Vid using (3.3)
12: restrict Vid:Vmin Vid Vmax
13: compute Xid using (3.4)
14: end for
15: if (x [Xmin, Xxmax]) then
16: if f (Xi) f (Xpbesti) then then
17: for each dimension d do do
18: Xpbestid = Xid
19: end for
20: flagi = 0
21: end if
22: if f (Xi) f (Xgbest) then then
23: for each dimension d do do
24: Xgbestd = Xid
25: end for
26: end if
27: else
28: flagi = flagi + 1
29: end if
30: end for
31: end while
Xid = i + i (4)
Here fi = [fi(1), fi(2), …fi(D)] denotes a set of particle indices with respect to each dimension of the particle i.fi(d) represents a comprehensive exemplar with each dimension composed of the value from the corresponding dimension of the pbest of particle pbestf i.These indices take the value i itself with the probability P ci, referred to as the learning prob ability, which takes different values with respect to different particles. For each particle i a random number is generated.If this random number is greater than P ci, the corresponding dimension of particle i will learn from its own pbest, otherwise it will learn from the pbest of another randomly chosen particle. Tournament selection with size 2 is used to choose the index fi(d). To ensure that a particle learns from good exemplars and to minimize the time wasted on poor directions, we allow each particle to learn from the exemplars until

such particle stop to improve for a certain number of generations, called the refreshing gap m. After this refreshing graph fi = [fi(1), fi(2), …fi(D)] is reassigned.
Three major differences between CLPSO and conventional PSO are [15]

In CLPSO instead of using particles pbest and gbest as
8: else
9: fdi =f2i
10: end if
11: else
12: fdi =i
13: end if
14: end for
the exemplars, all particles pbests can be used to guide a particles flying direction.

In PSO particle learn from same exemplar for all dimen sions but for CLPSO different dimensions of a particle may learn from different exemplars within certain gener ations.

PSO learns from two exemplars (pbest and gbest) in every generation,but each dimension of a particle in CLPSO learns from just one comprehensive exemplar within certain generations.



LOCALIZATION ALGORITHM
Node localization is finding the physical coordinate of the node.If N dumb nodes and M beacon nodes are deployed in the field then main aim of node localization is to estimate the position of as many N as possible. Node localization is viewed as an optimization problem. In this algorithm we are estimating the position by using bioinspired algorithms CLPSO and PSO . The Fig 1 shows the flowchart of the distributed sensor localization approach.
Approach for node localization is as follows:

There are N dumb nodes and M beacon nodes who know its physical coordinates in the field and both nodes have transmission range,r.

Each node check wheather there 3 or more noncollinear beacon in the range if so, computes its distance from those beacon node.

A node calculates its distance from beacon node i
using di = di + ni where ni is the gaussian additive nose while determing the distance.The distance di is
calculated by di (x xi)2 + (y yi)2, here (x, y)
is coordinate of the localizable noede and (xi, yi) is coordinate of the beacon node. The measurement noise
ni has a random value uniformly distributed in the range diÂ±di(P n/100). It is clear that the result of localization depends on the value of P n, the percentage noise that affects distance.

Two case studies are conducted to localize the nodes in the first case each node will run PSO and in the second
values of NL and Er decreases the performance of the algorithm increases
As number of iteration increases more and more number of nodes are localized and at the end of each iteration the settled nodes can be designated as the referece node this new set of refernce nodes will help to localize more nodes.


EXPERIMENTATION AND RESULTS
Simulation of the WSN and its performance evaluation is done in Matlab. 100 target nodes and 20 beacons are randomly deployed in a sensor field having dimensions of 255 Ã— 255
square units. Each beacon has a transmission radius of r = 30
units. Simulation settings specific to case studies 1 and 2, and the result obtained are presented in the following subsections.
Fig. 1. Flowchart for localization approach
case each node will run CLPSO.In both the case will get the Position of the node (x, y). Both PSO and CLPSO will try to minimize the Optimization function (5) M 3 it is the number of beacons in the transmission radius of the node to be localized

Case Study 1: PSO based localization
In this case study, each target node that can be localized runs a 2D PSO to localize itself. Some PSO parameters chosen as follows:

Population size, ps=30;

Accelaration constants c1=2 and c2=2

Inertia weight linearly decreases in each iteration form
0.9 to 0.4

number of iteration, kmax=200

dimension,d=2

Particle boundary is defined by Xmin = 0,Xmax = 255,Ymin = 0 and Ymax = 255 velocity of particle,Vmax = Xmax and Vmin = Vmax
This PSO based localization is conducted 50 times and number of localized nodes in each iteration,average error and compu tational time are estimated.


Case Study 2: CLPSO based localization
In this case study, each target node that can be localized runs a 2D CLPSO to localize itself. Some PSO parameters chosen as follows:

Population size,ps=30;

f (x, y) =
1 M M
i=1
( (x xi)2 + (y yi)2 di)2 (5)

Accelaration constants c1=1.49445 and c2=1.49445

Inertia weight linearly decreases in each iteration form
0.9 to 0.4

PSO and CLPSO search for best (x, y) value in the 2D
search space therefore dimension of the problem is 2.

After localizing maximum number of nodes which can
be localized the localization error is computed as equa tion (4.2) where (xi, yi) is the actual position of the
node and (xi,yi) is the position estimated by PSO and CLPSO. L is the total number of nodes localized.


number of iteration, kmax=200

dimension,d=2

Particle boundary is defined by Xmin = 0,Xmax = 255,Ymin = 0 and Ymax = 255 velocity of particle,Vmax = 10 and Vmin = 10
This CLPSO based localization is conducted 50 times and number of localized nodes in each iteration, average error and computational time are estimated.
Er = 1 L ((xi xi)2 + (yi yi2)) (6)
L i=1
C. Discussion and Result

repeat the steps from 2 to 6 utill all the nodes are lo calized or maximum number of nodes are localized.The performance of the localization algorithm can be deter mined by determing the no: of nonlocalizable,NL nodes
and localization error,Er where NL = N L.As the
In CLPSO and PSO based localization it was observed that as number of iteration increases the number of node localized also increases. The computational time required for CLPSO localization is more when compared with PSO. The Table I shows the average error and time required for both CLPSO
Fig. 2. Location estimated for PSO based localization Fig. 3. Location estimated for CLPSO based localization
and PSO. Each trial is the average of 50 trials. The location estimated by PSO and CLPSO are shown in Fig2 and Fig3, here number of dumb nodes=100, number of beacon=20 and transmission range 30. The graph in fig4 gives the distances between the actual and the estimated location. From the Table II CLPSO is more accurate than PSO since average error is less in CLPSO for all cases when compared with PSO. The computational time required for localization is more for CLPSO. PSO converges in to result more quickly. It is also observed that as percentage noise increases the average error value is also increasing for both cases. In Table I, here maximum number of beacons which can be used for localizing a node is made 6 in one case and 8, as beacons for, localizing a node was increased error decreases but the computational time increased i.e., accuracy of the result increased. From all these results it is evident that CLPSO is having more localization accuracy than PSO.


CONCLUSION AND FUTURE WORK
Localization is viewed as a multidimensional optimization problem is solved using bio inspired algorithms PSO and CLPSO. An energy efficient localization approach is used which a very important constraint in WSN. In distributed localization number of transmission to the base station is less so energy of the WSN can be conserved. The two bioinspired algorithms are outlined and statistical representation of the result obtained is also presented for comparison. The performance of two approaches is compared by measuring the parameters computational time, computational accuracy and number of nodes localized. It was observed that PSO converges in to the result more quickly since computational time required for PSO is less than other and CLPSO gives very accurate result since its localization error is very much less compared to PSO. The amount of memory required for CLPSO is more than that for PSO. A choice between PSO and CLPSO is influenced by constraints such as memory and computational resources of the
Fig. 4. Distance between actual position and estimated position for both PSO and CLPSO
Fig. 5. For increasing percentage of error the error rate is observed
TABLE I
RESULTS OBTAINED FOR LOCALIZATION BOTH PSO AND CLPSO FOR VARYING NUMBER OF BEACONS
PSO CLPSO
number of beacons=6 number of beacons=8 number of beacons=6 number of beacons=8 Avg. error(m) Avg. time(s) Avg. error(m) Avg. time(s) Avg error(m) Avg time Avg error Avg time
0.6472 36.0360 0.5486 73.8721 0.3173 574.5513 0.0551 975.0115
TABLE II
RESULT OBTAINED FOR PSO AND CLPSO LOCALIZATION EACH TRIAL IS DONE FOR 50 RUNS AND THE CORRESPOINDING VALUES ARE AVERAGED HERE
Er IS THE AVERAGE ERROR,L IS THE NUMBER OF NODES LOCALIZED AND CT IS THE COMPUTATIONAL TIME REQUIRED
PSO CLPSO
Trial 1 
L 
iteration1 73 
iteration2 96 
iteration3 99 
iteration4 100 
iteration1 73 
iteration2 98 
iteration3 100 
Er 
1.1843 
1.4892 
1.3164 
0.5869 
0.3269 
0.4980 
0.3031 

CT 
7.1794 
16.5233 
26.1706 
9.3654 
228.0498 
458.7456 
783.1441 

Trial 2 
L 
90 
99 
100 
90 
99 
100 

Er 
0.1370 
1.1326 
0.1370 
0.4929 
0.3334 
0.0639 

CT 
8.7894 
18.3703 
3.7326 
352.6139 
517.1685 
294.5091 

Trial 3 
L 
73 
99 
100 
74 
99 
100 

Er 
0.4314 
0.6702 
0.4314 
0.2928 
0.4171 
0.21881 

CT 
7.0384 
16.5746 
26.1756 
228.0498 
358.7456 
793.1441 
Fig. 6. For each trial of experiments the error rate of PSO and CLPSO is measured
node, how accurate the localization is expected to be and how quickly that should happen.
The research can be extended in many directions; if the beacons are mobile then more number of nodes can be localized. With the help of one mobile beacon node we can localize all the nodes in the field. The optimal path of mobile beacon is to be determined. Study on the error propagation in the proposed localization approach can be studied. The CLPSO and PSO can be used for centralized localization and compared with distributive localization which is presented in this report. The comparison of deterministic and stochastic localization methods compared and performance can be studied.
ACKNOWLEDGEMENT
We would like to express our immense gratitude to our beloved Chancellor Shri.(Dr.) Mata Amritanandamayi Devi for providing a very good motivation and inspiration for doing this research work.
REFERENCES

A. Boukerche, A. B. F. O. Horacio, E. F. Nakamura, and A. A. F. Loureiro, Localization system for wireless sensor network, IEEE Wireless Communications, Dec 2007.

R. V. Kulkarni and G. K. Venayagamoorthy, Particle swarm optimiza tion in wireless sensor networks: A brief survey, IEEE Transactions On Systems, Man, And Cybernetics.

A. Gopakumar and L. Jacob, Localization in wireless sensor networks using particle swarm optimization, in Proc. IET Int. Conf. on Wireless, p. 227230, 2008.

G. Nan, M.Q. Li, and J. Li, Estimation of node localization with a realcoded genetic algorithm in wsns, in Proc. Int. Conf. on Machine Learning and Cybernetics, vol. 3, p. 873878, 2007.

L. Doherty, K. S. J. Pister, and L. E. Ghaoui, Convex position estimation in wireless sensor networks, Infocom 2001,Anchorage, AK, 2001.

M. Marks and E. NiewiadomskaSzynkiewicz, Twophase stochastic optimization to sensor network localization, n Proc. Int. Conf. on Sensor Technologies and Applications SensorComm 2007, vol. 4, p. 134139, 2007.

J. W. C. J. J. Y. W. Z. Q. Zhang, J. Huang and J. Hu, A twophase localization algorithm for wireless sensor network, in Proc. Int. Conf. on Information and Automation ICIA 2008, vol. 4, p. 5964, 2008.

D. Niculescu and B. Nath, Ad hoc positioning system, in Proc.IEEE Global Telecommun. Conf. (GLOBECOM), vol. 5, p. 29262931, Nov. 25292001.

R. V. Kulkarni, G. K. Venayagamoorthy, and M. X. Cheng, Bioinspired node localization in wireless sensor networks, in Proceedings of the
IEEE International Conference on Systems, Man and Cybernetics, San Antonio, TX,, Oct. 2009.

K. S. L. H. Guo and H. A. Nguyen, Optimizing the localization of a wireless sensor network in real time based on a low cost microcon troller, IEEE Trans. Ind. Electron., p. 19, In Press.

G. K.Venayagamoorthy, A successful interdisciplinary course on com putational intelligence, IEEE Comput. Intell. Mag., vol. 4, p. 1423, Jan. 2009.

J. Kennedy and R. Eberhart, Particle swarm optimization, in Proc. IEEE Int. Conf. Neural Netw., vol. 4, p. 19421948, Nov. 27Dec. 1, 1995.

S. M. J. C. H. Y. del Valle, G. K. Venayagamoorthy and R. G. Harley, Particle swarm optimization: Basic concepts, variants and applications in power systems, IEEE Trans. Evol. Comput., vol. 12, p. 171195, Apr. 2008.

R. V. Kulkarni, A. Frster, and G. K. Venayagamoorthy, Computational
intelligence in wireless sensor networks: A survey, IEEE Communica tions Surveys and Tutorials, vol. 13, First Quarter 2011.

J. J. Liang, A. K. Qin, P. N. Suganthan, and S. Baskar, Comprehensive learning particle swarm optimizer for global optimization of multimodal functions, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTA TION, vol. 10, pp. 3541, June 2006.