Swarm Intelligence for Sensor Localization

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 words-Particle Swarm Optimization, Comprehensive Parti- cle Swarm Optimization, Localization, Wireless Sensor Network

1. 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 one-time 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 human-accessible, each node can easily be deployed manually and their locations can be registered during deployment. In more complex cases, when the area is not human-accessible 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.

2. 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 bio-inspired 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 one-hop 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 two-phase 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 non-GPS 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 real-time results comparison of PSO-beaconless algorithm with Gauss-Newton 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.

3. 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

   1. 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.

4. 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:

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

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

   3. 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.

   4. 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.

5. 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

   1. Case Study 1: PSO based localization

      In this case study, each target node that can be localized runs a 2-D 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.

   2. Case Study 2: CLPSO based localization

      In this case study, each target node that can be localized runs a 2-D 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

     1. PSO and CLPSO search for best (x, y) value in the 2D

        search space therefore dimension of the problem is 2.

     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

   1. 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 non-localizable,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.

6. 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 bio-inspired 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

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

1. 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.

2. 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.

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

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

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

6. M. Marks and E. Niewiadomska-Szynkiewicz, Two-phase stochastic optimization to sensor network localization, n Proc. Int. Conf. on Sensor Technologies and Applications SensorComm 2007, vol. 4, p. 134139, 2007.

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

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

9. R. V. Kulkarni, G. K. Venayagamoorthy, and M. X. Cheng, Bio-inspired node localization in wireless sensor networks, in Proceedings of the

   IEEE International Conference on Systems, Man and Cybernetics, San Antonio, TX,, Oct. 2009.

10. 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.

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

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

13. 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.

14. 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.

15. 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. 35-41, June 2006.