Localization Algorithm for WSN Application using Genetic Algorithm

Localization Algorithm for WSN Application using Genetic Algorithm

Harmeet Kaur

Student

Ludhiana College of Engineering and Technology Ludhiana, India

Amanpreet Kaur Asst. Professor

Ludhiana College of Engineering and Technology Ludhiana, India

Abstract This paper proposes a localization approach based on genetic algorithm for Wireless Sensor Networks. A new way to calculate the distance between anchor node and unknown node has been elaborated, which help in reducing the power consumption of nodes. Genetic Algorithm is based on natural evalution. The genetic algorithm is a probabilistic search algorithm that iteratively transforms a set (called a population) of mathematical objects (typically fixed-length binary character strings), each with an associated fitness value, into a new population of offspring objects using the Darwinian principle of natural selection and using operations that are patterned after naturally occurring genetic operations, such as crossover (sexual recombination) and mutation.

The starting node and the ending node are fixed in node distance optimization algorithm. The algorithm has to cover each and every node, keeping in mind that the node should not be repeated. During the first run of algorithm, it has to calculate the distance and mark that distance as index distance. Then GA makes use the GA operators like crossover and mutation to generated new paths and try to find the minimum distance. If distance calculated is less than the index distance, then it is replaced, otherwise rejected. Termination criteria are met, when the number of iteration is completed.

Application for genetic algorithm has been succesfully built using MATLAB tool. The distance between two dummy nodes for constant population has been observed as 26.136m and for random population it has been observed as 34.147m and 39.669m respectively.

Keywords Cross-Over, Fitness, Genetic Algorithm, GPS, Mutation.

1. INTRODUCTION

   Sensor networks are distributed networks of small, lightweight wireless nodes that are deployed in large numbers to monitor the system by measuring the physical parameters such as relative humidity, temperature or pressure [1]. Sensor nodes are energy-constraint devices and the consumption is generally related with the amount of gathered data, since communication is usually the most expensive in terms of the energy [1].

   The traditional theory of genetic algorithm was first implemented by Holland in year 1975 [2]. Genetic algorithm works by discovering, emphasizing and recombining good building blocks of solutions in a highly parallel fashion. This algorithm works on the principle of natural selection where in searching the best optimum result and giving them the chance to reproduce. The algorithm treats each and every result as the chromosome and for each chromosome value the

   particular fitness value is calculated. With higher the fitness value, the more likely is the survival of that chromosome for the next generation.

2. WIRELESS SENSOR NETWORK

   A wireless sensor network is a network consisting of a large numbers of sensors that are scattered over a large geographical area. These sensors are having the capability of communication among themselves to detect objects, gather the data, and transmit messages. Sensor networks are a promising field in the area for environmental monitoring, military applications, etc [3,4]. However, due to small size of the sensor it has lots of physical limitation such as powerful Processing Unit and is limited in power and storage memory. On the other hand, power source for the sensor is by a battery instead of a power outlet. This is main challenge as recharging is not possible, sensors has to work very carefully so that it utilizes very limited energy in collecting, processing, and transmitting information.

   In almost all applications, sensors need to grasp information regarding its geographical locations. Global Positioning System (GPS) can be used for a sensor to locate itself. In practical aspects, it is not feasible to use GPS in every sensor node because installing GPS in each and every node will be very costly and power inefficiency process. Problem can be solved by localization methods, in which. Instead of all nodes only a few nodes ( 3) are installed with GPS hardware. These nodes are referred as anchor or beacon nodes and they act as master because they know their own position instead of communicating with any other node. Rest all nodes or sensor have to obtain the information about the distance through talking among each other and derive their positions based on the anchor or beacon node. A good localization protocol can decrease the probability of error in position estimation. The distance between unknown nodes when compared with anchor node will help in finding the position of unknown node; genetic algorithm is the best algorithm for this problem.

3. GENETIC ALGORITHM

Genetic algorithm is robust problem solving method based on the natural selection [5]. Genetic algorithm had been applied on various applications for solving different type of problems. The distance in this algorithm is calculated using the simple formula of mathematics. In this any node in the space must consist of two coordinates say x and y. The value of coordinates is substituted in the formula 1.1 and the

particular distance between unknown and anchor node is obtained.

.Eq. 1.1 From the above shown formula the distance from the

unknown node is calculated to the next adjoining anchor

nodes. The node which is having the least distance is selected and the other nodes are rejected. Then accordingly the other nodes are covered up till the anchor node is reached. The unknown and the anchor node and the possible solutions are shown in figure 1.

Fig.1. A simple undirected graph with 15 unknown and one anchor node

Genetic algorithm consists of genetic operators which act as the ALU unit. Genetic operators are responsible for maintaining the diversity in the population. Genetic operators like mutation and crossover acts upon the chromosome of the population in such a way that it continuously brings some change in them.

1. Crossover

   In genetic algorithms, crossover is a genetic operator used to vary the value of a chromosome or chromosomes from one generation to the next. It is analogous to reproduction and biological crossover, upon which genetic algorithms are based. Cross over is a process of taking more than one-parent solutions and producing a child solution from them.

2. Mutation

   Mutation Operators are type of reproduction operator applied for destroying homogeneity in the population. The mutation operator alters the single bit or group of bits in the chromosome. Usually a Mutation operator leads to improvement of the chromosome value, thus increasing or improving the fitness value of the population. It is also responsible for boosting of the search operation. [6]

3. Fitness

   In nature, an individuals fitness is the ability to pass on its genetic material. This ability includes traits that enable it to survive and further reproduce. In a GA, fitness is evaluated by the function defining the problem. The fate of an individual chromosome depends on the fitness value. The chances of survival are higher for better fitness values

4. Selection

   The selection process determines which of the chromosomes from the current population will mate (crossover) to create new chromosomes. These new chromosomes join the existing population. This combined population will e the basis for the next selection. The individuals (chromosomes) with better fitness values have better chances of selection [7].

5. Steps involved in the algorithm

   1. Calculate the fitness f (x) of each string x in the population.

   2. Choose (with replacement) two parents from the current population with probability proportional to each string's relative fitness in the population.

   3. Cross over the two parents (at a single randomly chosen point) with probability pc to form two offspring. (If no crossover occurs, the offspring are exact copies of the parents.)

   4. Select one of the offspring at random and discard the other.

   5. Mutate each bit in the selected offspring with probability pm, and place it in the new population.

   6. Go to step 2 until a new population is complete.

   7. Go to step 1

6. Decision to be done during designing of algorithm.

   During the designing of the algorithm, some rules and decision are to be done to complete it process. Some of the decisions are discussed.

   1. Encoding Technique: Encoding technique is the method of encoding the chromosome to meet the requirement of the algorithm. A second reason for adapting the encoding is that a fixedlength representation limits the complexity of the candidate solutions

   2. Selection Method: There are lots of selection methods are available like tournament selection, roulette wheel selection etc. The decision of selecting the selection method varies from application to application.

   3. Genetic Operator: Genetic operator like mutation and crossover are of different types from which the required types depend upon the particular application.

   1) Termination Technique: This is responsible for the termination of the GA. There are different types of the termination which as met will lead to the stoppage of the iteration going on in GA

7. Parameter tuning in algorithm

   Parameter is the most important decision to be made during the designing as well as application part of the genetic algorithm. Parameters are nothing but the value (constants) like population size, mutation probability and crossover probability and types of the mutation and crossover technique to be decided. The parameter value changes according to the application and is always different for different applications [8].

   Fig.2. Types of parameter setting

   There are mainly two ways for setting the parameter, one is parameter control and other is parameter tuning. Figure 2 depicts the ways of setting the parameter and also there subparts. By parameter tuning it means the value of parameter are controlled before the actual run of the algorithm. In this the user manually set the parameter value. Parameter control means the value of parameter are controlled during the actual run of the algorithm. Parameter control is further divided into three classes, deterministic, adaptive, and self adaptive.

8. Choice of operating parameter for genetic algorithm.

1. Individual code of chromosome can be random value or fixed decimal value varying from 1 to 7.

2. Number of Population size is 16.

3. Number of genetic generation is 100.

   Fig.3. Directed output of 16 nodes for fixed population

   Fig.4. Node location and best history report for fixed population

   Figure 4 depicts the history report and node location for the fixed population. It shows total minimum distance as 26.4361 units.

   Other way is by using random function for producing the population.

4. Minimum number of person and tour is taken as 1.

5. Crossover and mutation technique is flipping, sliding and swapping.

III. EXPERIMENT AND RESULTS

There are two possible ways of executing the algorithm. One way is by keeping the chromosome in the population as constant. Figure 3 depict the output for fixed chromosome which shows all the 16 nodes covered from unknown to anchor node point.

xy = 10*rand(n,2)Eq.1.2

Equation 1.2 shows the random function used in the algorithm. Equation clearly depicts the use of rand which is random function, which gives random value to XY coordinates.

(a)

(b)

Fig.5 (a) and (b). Randomly generated population output.

Figure 5(a) and (b) depict the output for randomly generated population where two snapshots are taken for different generation of random population.

III. CONCLUDING REMARK

Major challenge in Wireless Sensor network is power consumption which is overcome by node localization technique. Localization algorithm based on genetic algorithm. Taking into account of the energy consumption of nodes, the algorithm makes some improvements in the selection, crossover and mutation operations, and makes both positioning accuracy and energy consumption. Genetic algorithm is a method, which is very easy to understand, and it practically does not demand the knowledge of mathematics. Route is optimized using the minimum distance calculation technique. Two techniques were applied for calculating the distance; one was using fixed population and other by using random function.

REFERENCES

1. Hoglar Karl Andreas Willing, PROTOCOLS AND ARCHITECTURES FOR WIRELESS SENSOR NETWORKS, Book, .pp 1-481.

2. Agoston Endre Eiben, Robert Hinterding, and Zbigniew Michalewicz (1999), Parameter Control in Evolutionary Algorithms. IEEE Transaction on Evolutionary Computation (2), 3

3. X. Ji and H. Zha. Sensor positioning in wireless sensor networks using multidimensional scaling. In IEEE Infocom, 2004.

4. H. Lim and J. C. Hou. Localization for anisotropic sensor networks. In

   IEEE Infocom, 2005.

5. Alan Piszcz and Terence Soule (2006), A Survey on Mutation Technique in Genetic Programming. GECCO, USA

6. Chun-Liang Lin; Horn-Yong Jan, Thong-.Hsing Huang(2004), Self- organizing PID control design based on DNA computing method. International Conference on Control Application, Taipie, Taiwan.

7. Hasan BS, Khamees MA, Mahmoud ASH (2007), A Heuristic Genetic Algorithm for the Single Source Shortest Path Problem. In Computer Systems and Applications, Proceedings of the 5th IEEE/ACS International Conference, 187-194.

8. John H. Holland, John Henry Holland (1975), Adaptation in natural and artificial systems: University of Michigan Press