FAULTY NODE RECOVERY AND REPLACEMENT ALGORITHM FOR WIRELESS SENSOR NETWORKF

FAULTY NODE RECOVERY AND REPLACEMENT ALGORITHM FOR WIRELESS SENSOR NETWORKF

• 1.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 36 FAULTY NODE RECOVERY AND REPLACEMENT ALGORITHM FOR WIRELESS SENSOR NETWORK Triveni C.L1 Rashmi T.S2 P.C Srikanth3 1 Assistant Professor, Department of ECE, Malnad College of Engineering, Hassan, India 2 Department of ECE, Malnad College of Engineering, Hassan, India 3 Professor and Head, Department of ECE, Malnad College of Engineering, Hassan, India ABSTRACT This paper proposes an algorithm by combining grade diffusion and genetic algorithm to enhance the lifetime of a wireless sensor network. The algorithm is named as Fault Node Recovery and Replacement algorithm. The algorithm enhances the lifetime of the wireless sensor network with fewer replacements of sensor nodes. In the simulation it is shown that the proposed algorithm increases the number of active node, reduces the rate of data loss, increases the life time of the wireless sensor network and reduces the rate of energy consumption. Keywords: Grade Diffusion (GD), Genetic Algorithm (GA), Fault Node Recovery and Replacement (FNRR), Wireless Sensor Networks (WSN). 1. INTRODUCTION Recent advances in micro processing, wireless and battery technology, and smart sensors have enhanced data processing [1], [2], [3], wireless communication, and detection capability. In sensor networks, each sensor node has limited wireless computational power to process and transfer the live data to the base station or data collection center [4], [5], [6]. Therefore, to increase the sensor area and the transmission area [7], [8], the wireless sensor network usually contains many sensor nodes. Generally, each sensor node has a low level of battery power that cannot be replenished. When the energy of a sensor node is exhausted, wireless sensor network leaks will appear, and the failed nodes will not relay data to the other nodes during transmission processing. Thus, the other sensor nodes will be burdened with increased transmission processing. This paper proposes an algorithm by combining grade diffusion (GD) and Genetic Algorithm (GA) to enhance the lifetime of a wireless sensor network (WSN) when some of the sensor nodes shut down because they no longer have battery energy. Existing algorithms IJECERD © PRJ PUBLICATION International Journal of Electronics and Communication Engineering Research and Development (IJECERD) ISSN 2248– 9525 (Print) ISSN 2248 –9533 (Online) Volume 4, Number 2, April- June (2014), pp. 36-44 © PRJ Publication, http://www.prjpublication.com/IJECERD.asp
• 2.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 37 for recovery and replacement are costlier and implementation is difficult. The algorithm proposed in the paper is easier to implement and since it replaces some of the sensor nodes it is not much expensive. The proposed algorithm can result in fewer replacements of sensor nodes. Thus, the algorithm enhances the WSN lifetime and also reduces the cost of replacing the sensor nodes. 2. RELATED WORK The traditional approaches to sensor network routing include the directed diffusion (DD) [9] algorithm and the grade diffusion (GD) [3] algorithm. The algorithm proposed in this paper is based on the GD algorithm, with the goal of replacing fewer sensor nodes that are inoperative or have depleted batteries. These optimizations will ultimately enhance the WSN lifetime and reduce sensor node replacement cost. 2.1 Directed Diffusion Algorithm A series of routing algorithms [10], [11] for wireless sensor networks have been proposed in recent years. C. Intanagonwiwat et al. presented the Directed Diffusion (DD) algorithm [10]. The goal of the DD algorithm is to reduce the data relay transmission counts for power management. The DD algorithm is a query-driven transmission protocol. The collected data is transmitted only if it matches the query from the sink node. In the DD algorithm, the sink node provides the queries in the form of attribute-value pairs to the other sensor nodes by broadcasting the query packets to the whole network. Subsequently, the sensor nodes send the data back to the sink node only when it fits the queries. 2.2 Fault Recovery Techniques Fault recovery techniques enable systems to continue operating according to their specifications even if faults of a certain type are present. The most widely used fault recovery techniques are as follows. Replication of components is one of the most widely used fault recovery technique. Although redundancy has several advantages in terms of high reliability and availability, it also increases the costs of a deployment. There are two types in replication of nodes. 2.2.1 Active replication in WSN Active replication in wireless sensor networks is naturally applied in scenarios where all, or many, nodes provide the same functionality. Nodes that run this service activate their sensors and forward their readings to an aggregation service or to a base station. When some nodes fail to provide that information, the recipient still gets the results from other nodes, which is often sufficient. Fault recovery in the presence of active replicas is relatively straightforward. Some of these approaches are: 1) Multipath routing 2) Sensor value aggregation 3) Ignore values from faulty nodes. 2.2.2 Passive replication in WSN When passive replication is applied, the primary replica receives all requests and processes them. In order to maintain consistency between replicas, the state of the primary replica and the request information are transferred to the backup replicas. Given the constraints of WSNs, applications should be designed to have only little or no state at all, which minimizes the overhead for transferring state information between nodes or eliminates it altogether. The process of recovering from a fault when using passive replication consists of three main steps: fault detection, primary selection and service distribution.
• 3.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 38 3. FAULT NODE RECOVERY AND REPLACEMENT (FNRR) ALGORITHM The power consumption of the sensor nodes in WSNs is unavoidable. This paper, however, proposes an algorithm to search for and replace fewer sensor nodes and to reuse the most routing paths. Conventional search techniques are often incapable of optimizing nonlinear functions with multiple variables. One scheme, the genetic algorithm (GA) [12], is a directed random search technique developed in 1975, based on the concept of natural genetics. The current paper proposes a fault node recovery and replacement (FNRR) algorithm based on the GD algorithm combined with the GA. The FNRR algorithm creates a routing table using the GD algorithm and replaces sensor nodes using the GA when the number of sensor nodes that are not functioning. This algorithm not only reuses the most routing paths to enhance the WSN lifetime but also reduces the replacement cost. 3.1 Grade Diffusion Algorithm Grade Diffusion Algorithm is proposed to solve the power consumption and transmission routing problems in wireless sensor networks [13]. In the grade diffusion algorithm the first step is to assign the grade for the sensor nodes and to update the routing table for each node. The data transmission takes place from higher grade nodes to lower grade nodes and hence it is named as grade diffusion algorithm. The GD algorithm is fast and completely creates the grade table in each sensor node based on the entire wireless sensor network by issuing the grade create packet that is created from the sink node. The process of grade diffusion is as follows. First, the sink node broadcasts the grade-creating package with the grade value of zero. A grade value of one means that the sensor node receiving this grade-creating package transmits data to the sink node requires only one hop. The sensor nodes ‘‘b’’ and ‘‘c’’ receive a ladder-creating package with a grade value of one from sink node ‘‘a’’. Then sensor nodes ‘‘b’’ and ‘‘c’’ increase the grade value of the ladder-creating package to two and broadcast the modified ladder-creating package. A grade value of two means that the sensor node receiving this ladder-creating package sends data to the sink node requires two hops count. The sensor nodes ‘‘d’’, ‘‘e’’, and ‘‘f’’ receive ladder-creating packages with a grade value of two from nodes ‘‘b’’ and ‘‘c’’. Sensor nodes ‘‘d’’, ‘‘e’’ and ‘‘f’’ increase the grade value of the ladder-creating package to three and broadcast the modified package again. Sensor nodes ‘‘b’’, ‘‘g’’ and ‘‘h’’ receive this ladder-creating package, but node ‘‘b’’ discards the package because the grade value of this package is three, which is higher than the recording value in the ladder table for node ‘‘b’’. Moreover, if many sensor nodes simultaneously broadcast ladder-creating packages with the same grade value, the sensor nodes receive and record the packages in their respective ladder tables as back-up nodes. Thus, node ‘‘h’’ recording nodes ‘‘d’’ and ‘‘f’’ in the ladder table. Finally, sensor nodes ‘‘g’’ and ‘‘h’’ increase the grade value of the ladder-creating package to four and broadcast the ladder-creating package. But the sensor nodes discard the package because the grade value of the sensor nodes surrounding nodes ‘‘g’’ and ‘‘h’’ are less than four. The process of ladder diffusion is thus complete, as shown in Fig. 1.
• 4.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 39 Fig 1: Grade Diffusion Process The data transmission takes place from higher grade node to lower grade node as shown in Fig 2. Each sensor node records the grade value in the ladder table when the ladder diffusion algorithm is applied. The sensor node can record more than one node as relay nodes in the ladder table when receiving the ladder-creating package with a grade value less than itself. Fig 2: Data transfer route of sensor nodes 3.2 Genetic Algorithm for Fault Node Replacement Grade Diffusion Algorithm is used for data transmission in the network. Genetic Algorithm is used to replace the faulty nodes in the network. Genetic Algorithm has to run once after 30 iterations for fault node recovery. The steps for faulty node replacement are as follows.
• 5.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 40 3.2.1 Initialization At this step the chromosomes are generated. All the faulty nodes in the network whose energy is less than the threshold level must be listed. The length of the chromosome is equal to the number of faulty nodes in the network. The elements in the genes are either 0 or 1. A 1 means the node should be replaced and a 0 means that the node will not be replaced. Here population size is limited to only 4. Fig. 3 represents a chromosome. The chromosome length is 10 and the gene is 0 or 1, chosen randomly in the initialization step. In this case, there are 10 sensor nodes not functioning, and their node numbers are 9, 7, 10, 81, 23, 57, 34, 46, 66, and 70. Fig 3: Chromosome and its gene 3.2.2 Evaluation The chromosomes are evaluated based upon how many lower grade nodes will be replaced by the chromosome. 3.3.3 Selection Out of the above four chromosomes choose the two chromosomes which replaces many lower grade sensor nodes. This is shown in the Fig. 4. Fig 4: Selection Step 3.3.4 Crossover The crossover step is used in the genetic algorithm to change the individual chromosome. In this algorithm, one-point crossover strategy is used to create new chromosomes, as shown in Fig. 5. Two chromosomes chosen in the selection are used to produce two new offspring. A crossover point is selected between the first and last genes of the parent individuals. Then, the fraction of each individual on either side of the crossover point is exchanged and concatenated.
• 6.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 41 Fig 5: Crossover Step 3.3.5 Mutation The mutation step can introduce traits not found in the original individuals and prevents the GA from converging too fast. In this algorithm, simply a gene is randomly flipped. The chromosome is as shown in Fig. 6. Fig 6: Mutation Step The FNR algorithm will replace the sensor nodes in the chromosome with genes of 1 to extend the WSN lifetime. 4. SIMULATION In the simulation the sensor nodes are uniformly distributed over 100*100 area in grid manner. The radio ranges (transmission range) of the nodes were set to 15 units. The data packages were exchanged between random source/destination pairs with 100 event data packages. The power of each sensor node is set to 3000 W that is the actual available energy. Each sensor consumed 50W when it conducts a data transformation. The active sensor nodes, total energy consumption and total dead nodes after 120 events are shown in Figs. 7, 8 and 9. The active nodes mean that the sensor node has enough energy to transfer data to other nodes, but some sensor nodes can be deleted from the active nodes list if their routing tables do not have a sensor node that can be used as a relay node, or if they are not in the routing table of any other sensor nodes.
• 7.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 42 Fig 7: Number of Alive Nodes As shown in fig 7 FNRR algorithm recovers the faulty nodes for every 30 iterations and hence keeps most of the nodes alive. As shown in fig 7 even after 100 data events number of alive nodes is greater than 60. In grade diffusion algorithm only 50% of the nodes are alive after 40 data transmissions. Fig 8: Number of dead nodes As shown in fig 8 throughout the data transmission number of dead nodes is less than five whereas with grade diffusion algorithm more than 50% of the nodes are dead by 40 data events. So FNRR algorithm reduces the number of dead nodes by 96% as compared to grade diffusion.
• 8.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 43 Fig 9: Power Consumption Power consumed for data transmission from source to sink for different iterations is shown in fig 9. Power consumption of FNRR algorithm is around 20mJ. The power consumed by the grade diffusion algorithm is around 110mJ. Hence power consumption for data transmission of fault node recovery is lesser compared to grade diffusion algorithm. As shown in fig 10 number of hops required for data transmission is lesser for FNRR algorithm compared to grade diffusion algorithm. Since the number of hops required for data transmission is lesser it takes lesser time for data transmission. Fig 10: Number of Hops for Data Transmission
• 9.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 44 5. CONCLUSION In real wireless sensor networks, the sensor nodes use battery power supplies and thus have limited energy resources. In addition to the routing, it is important to research the optimization of sensor node replacement, reducing the replacement cost. This paper proposes a faulty node recovery and replacement algorithm for WSN based on the grade diffusion algorithm combined with a genetic algorithm. The FNRR algorithm requires replacing fewer sensor nodes and reuses the most routing paths, increasing the WSN lifetime and reducing the replacement cost. In the simulation, the proposed algorithm increases the number of active nodes reduces the rate of energy consumption. Therefore, the FNRR algorithm not only replaces sensor nodes, but also reduces the replacement cost. 6. REFERENCES [1] S. Corson and J. Macker, Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations. New York, NY, USA: ACM, 1999. [2] T. H. Liu, S. C. Yi, and X. W. Wang, “A fault management protocol for low-energy and efficient wireless sensor networks,” J. Inf. Hiding Multimedia Signal Process., vol. 4, no. 1, pp. 34–45, 2013. [3] E. M. Royer and C. K. Toh, “A review of current routing protocols for ad-hoc mobile networks,” IEEE Personal Commun., vol. 6, no. 2, pp. 46–55, Apr. 1999. [4] F. C. Chang and H. C. Huang, “A refactoring method for cache-efficient swarm intelligence algorithms,” Inf. Sci., vol. 192, no. 1, pp. 39–49, Jun. 2012. [5] Z. He, B. S. Lee, and X. S. Wang, “Aggregation in sensor networks with a user- provided quality of service goal,” Inf. Sci., vol. 178, no. 9, pp. 2128–2149, 2008. [6] J. H. Ho, H. C. Shih, B. Y. Liao, and S. C. Chu, “A ladder diffusion algorithm using ant colony optimization for wireless sensor networks,” Inf. Sci., vol. 192, pp. 204– 212, Jun. 2012. [7] J. A. Carballido, I. Ponzoni, and N. B. Brignole, “CGD-GA: A graphbased genetic algorithm for sensor network design,” Inf. Sci., vol. 177, no. 22, pp. 5091–5102, 2007. [8] J. Pan, Y. Hou, L. Cai, Y. Shi, and X. Shen, “Topology control for wireless sensor networks,” in Proc. 9th ACM Int. Conf. Mobile Comput. Netw., 2003, pp. 286–299. [9] T. P. Hong and C. H. Wu, “An improved weighted clustering algorithm for determination of application nodes in heterogeneous sensor networks,” J. Inf. Hiding Multimedia Signal Process, vol. 2, no. 2, pp. 173–184, 2011. [10] C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, “Directed diffusion for wireless sensor networking,” IEEE/ACM Trans. Netw., vol. 11, no. 1, pp. 2–16, Feb. 2003. [11] W. H. Liao, Y. Kao, and C. M. Fan, “Data aggregation in wireless sensor networks using ant colony algorithm,” J. Netw. Comput. Appl., vol. 31, no. 4, pp. 387–401, 2008. [12] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design. New York, NY, USA: Wiley, 1997. [13] J. H. Ho, H. C. Shih, B. Y. Liao, and J. S. Pan, “Grade diffusion algorithm,” in Proc. 2nd Int. Conf. Eng. Technol. Innov., 2012, pp. 2064–2068.