Replacement of Fault Node in Wireless Sensor Networks

Replacement of Fault Node in Wireless Sensor Networks

Roshni R S1*, Asha George2

1*PG Scholar, Dept. of computer science and engineering 2Assistant Professor, Dept. of computer science and engineering TKM Institute of Technology,

Kollam,India

Abstract Wireless sensor network is a spatially distributed autonomous sensor network to monitor physical or environment conditions, such as temperature, humidity etc and to co- operatively pass their messages throughout the network to the main location. This paper proposes a Fault Node Recovery algorithm which is used to enhance the lifetime of a wireless sensor network when some of the sensor nodes are shutdown, due to the energy depletion, hardware failures, environmental conditions etc. Fault node recovery algorithm is combination of grade diffusion algorithm and genetic algorithm. In the previous work, the rate of false positive ratio is very high. The false positive ratio means some of the nodes are taken as fault, but that nodes are not fault because when the nodes are moved to the other locations that nodes are taken as fault. To reduce false positive ratio here MaxMin clustering is used. Finally apply FNR algorithm to each cluster. Then the lifetime of a WSN increases and also replacement cost reduces.

Index Terms Genetic algorithm, grade diffusion (GD)algorithm, gradient diffusion algorithm, wireless sensor networks(WSN).

1. INTRODUCTION

   In wireless sensor networks, each sensor node has limited power to process and transfer data to the base station

   [1] [2]. Therefore, to increase the transmission area [3] the sensor network includes large number of sensor nodes. Wireless sensor networks mainly use broadcast communication. Generally, each sensor node has limited power, energy and computational capability. When the energy of a sensor node is exhausted, node does not pass messages to the other nodes and that node is taken as faulty node.

   This paper proposes a fault node recovery algorithm is used for enhance the lifetime of a wireless sensor networks, when the sensor nodes are shut down, due to the energy depletion, hardware failures etc. FNR algorithm is the combination of grade diffusion and genetic algorithm. The grade diffusion is used to create the routing tables and also identify the set of neighbor nodes. The genetic algorithm is used to replace the fault node in the sensor networks.

2. RELATED WORKS

   The traditional approach [4], routing includes direct diffusion (DD), ladder diffusion algorithm (LDA) and grade diffusion (GD) is used to replace some nodes that are inoperative or depleted batteries and of reusing the maximum number of routing paths.

   1. Directed Diffusion Algorithm

      Directed diffusion algorithm [5] consists of 3 steps: interest propagation, initial gradients setup, and data delivery reinforced path. Sink node sends out its query whenever it wants to obtain some information from the sensor nodes. When a node receives an interest packet, the information of the packet is stored and the packet is forwarded to the neighboring nodes. For delivering the interest packet to the sink node propagation of interest packet setup the gradient. The gradient is the reply link to a neighbor node from which the interest was received. When a node matches an interest, it generates a sampled sensed data called exploratory data. As the exploratory data reach the sink node, they are established several paths between sink and source node. The sink reinforces one of the paths, which has the least delay. Finally the data is transferred from source to the sink through the selected path. The main disadvantage of DD is to arise circle route that result the wastage of power consumption.

   2. Ladder Diffusion Algorithm

      Ladder Diffusion algorithm [6] is used to avoid the generation of circle routes. And also it is used to solve power consumption and transmission problems in WSN. LDA contain two phases. Ladder diffusion phase and route choosing phase. In ladder diffusion phase, where create the ladder table, and the sensor node transmits data based on the ladder table. The data transmitted route is going from high grade value to low grade value. The route choosing phase is used to select and constructing the routes from source node to sink node.

   3. Grade Diffusion algorithm

   Grade Diffusion algorithm [7] is used to improve the LDA by using ant colony optimization techniques. Grade Diffusion update routing path in real time and the event data is thus sent to the sink node quickly and correctly. It is used to create a routing of nodes based on the grade value. It identifies a set of neighbor nodes and create routing table to reduce transmission loading. GD used to eliminate redundant transmission. It can also record some information regarding the data rely.

   In the previous system [8], sometimes the nodes that are not fault is taken as fault node. Because in previous work the nodes that move to other locations are taken as fault node.

   Actually, those nodes are not faulty. To avoid this problem here MaxMin clustering is introduced. MaxMin clustering uses the result of k-scheme clustering. And iteratively split and merge the cluster to obtain a better clustering. After the clustering, select cluster head of each cluster. Cluster head is selected on the basis of less energy constrained than the other sensor nodes. After the selection of cluster head, apply grade diffusion and genetic algorithm to each cluster through cluster head. Each cluster head contains the information about the cluster members in the cluster. A node move from one cluster to another; the cluster head store that information. If any node is fault, that information is stored in the cluster head. Then easily identify the faulty node in WSN. Sometimes the nodes have high energy, but that node doesnt forward data to the neighboring nodes. In the proposed work those nodes are taken as fault node.

3. METHODS

   For clustering the WSN, use K-Means clustering and MaxMin clustering [9]. Then use the grade diffusion algorithm to create routing table and identify the set of neighbor nodes. Genetic algorithm is used to replace sensor nodes that are not functioning in WSN.

   1. K-Means clustering

      Groups event location based on their relative distances in the sensing field such that those locations close to each other are grouped together. Here L represents the event location. S represents the set of mobile sensors. Figure 1 shows the k-means clustering scheme.

      Fig 1: K means clustering scheme.

      Fig 2: MaxMin clustering

      This scheme can avoid clusters containing long edges, thereby reducing the energy costs of sensors. Fig. 1 and fig. 2

      give an example. In Fig. 1, wintramax = 50 (in cluster D) and

      Algorithm

      1. Initially, L is randomly partitioned into |S| nonempty clusters.

      2. Calculate the central point of each cluster

         1. Given a cluster of locations

            {(x1,y1),(x2,y2)(xp,yp)} its central point is calculated as

      3. Locations closest to the same central point are put into the same cluster.

      4. The process is repeated until no cluster is changed.

   2. MaxMin Clustering

      Here use the result of K-Means clustering and split or merge the clusters to obtain better clustering.

      Algorithm

      1. Let wintramax be the maximum of the maximum edge weight in each cluster among all clusters and wintermin bethe minimum of the distances between all cluster pairs.

      2. Split the cluster which contains the edge with weight/p>

         wintramaxby removing that edge.

      3. Among all |S|+1 clusters, merge two clusters with distance

         wintermin .

      4. This operation is repeated until wintramax <= wintermin.

      wintermin = 15 (between clusters A and B). Thus split cluster D into two clusters D1 and D2, and then merge clusters A and B, as shown in Figure 2. Now, wintramax = 40 and wintermin = 20, enforcing to further split A0 and then to merge C and D1. After this operation, wintramax = 20 and wintermin = 40. Thus, the scheme terminates and the final result is shown in Fig. 2.

      After the clustering, where select the cluster head. Cluster head is selected on the basis of energy. That is the cluster head is select on the basis of less energy constrained than other sensors. After the selection of cluster head, apply grade diffusion and genetic algorithm to each cluster head.

   3. Grade Diffusion Algorithm

      Grade Diffusion Algorithm is used to find the set of neighbor nodes and also create the routing table.

      Algorithm

      1. The source node will broadcast the RREQ packets to all its neighbors and also updates the path.

      2. Then select a sensor node from the set of neighbor nodes when the available energy is more than the other nodes.

      3. Check the set of neighbors contain sink node. If there does not contain the destination node again send RREQ to the next neighbor set until reach the destination node.

      4. After finding the sink node send data from source to sink node.

   4. Genetic Algorithm

   Genetic Algorithm [10] is used to replace the sensor nodes that are not functioning.

   Algorithm

   1. Generate the chromosome by using genes.

   2. Evaluate the fitness value, fn.

   3. If the fitness value is have higher probability select that chromosome. Otherwise chromosome will be eliminating.

   4. After the selection of chromosome where apply the crossover.

   5. Apply mutation .Mutation will consist of having the bit flip a 1 changes to a 0 and a 0 changes to a 1.

   6. Replace the old chromosome with new chromosome.

   7. The process is repeated from 1 to 6 until get the best solution.

4. PERFORMANCE EVALUATION

   The proposed FNR algorithm can result in replacements of sensor nodes and more reused routing path. The proposed algorithm increases the number of active nodes and reduces the rate of data loss and energy consumption. The FNR algorithm not only replaces sensor nodes, but also reduces the replacement cost and reuses the most routing paths to increase the WSN lifetime. In the previous work, the false positive ratio is very high. That is a node which does not forward data to the neighbor nodes is taken as a fault node. Actually, that node may not be faulted, because that node may move to another location. In the previous work such nodes are taken as a fault. Hence accuracy is decreased. To avoid such problems the proposed work use clustering on WSN. By this way reduce the false positive ratio and also increase the accuracy of the system.

   The figure 3 represents the comparison of accuracy between existing and proposed system. The accuracy is calculated by dividing the number of actual defective nodes and number of total defective nodes. Actual defective nodes are the correct fault node. The total defective nodes may contain active nodes. The value of accuracy is between 0 and 1.For example the number of actual fault node is 9 and number of total defective node is 10, then the accuracy is reduced to 0.9. The number of total defective nodes and actual nodes are same then the accuracy is increased and the value of accuracy becomes 1. In existing system the accuracy is very low, because the total defective nodes may be greater than the actual defective node. In the proposed system to increase the accuracy apply clustering on WSN. In clustering, if a node moves to another location that node does not take as fault node. Therefore in the existing system, the accuracy is very low as compared to the proposed system. In clustering, the total defective node is almost equivalent to an actual defective node; therefore the rate of fault node is decreased.

   The figure 4 represents the comparison of the fault positive ratio between existing system and proposed system. In the existing system, the false positive ratio is increased when the nodes are moved to the other location, those node take as fault node. To reduce the false positive ratio applies clustering on WSN. In the proposed system, the false positive ratio is decreased because a node moves from one cluster to another; that information is stored in the cluster

   head. Such that those node dont take as a fault. But in the previous work does not contain cluster. So cant find the node is fault or not, when a node moves to another location.

   Fig. 3: Comparison of accuracy between existing system and proposed

   system.

   Fig. 4: Comparison of false positive ratio between existing system and proposed system

   In the existing system, the false positive ratio increases and accuracy is decreased. But in the proposed system false positive ratio is decreasing and accuracy is increased.

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, and reusing the most routing paths when some sensor nodes are nonfunctional. In this work first WSN are clustered by using MaxMin clustering algorithm. Then find the cluster head of each cluster. The cluster head have less energy constrained than other sensors. To reduce the false positive ratio, apply grade diffusion and genetic algorithm to each cluster. Therefore FNR algorithm increases the lifetime of a WSN and also reduce the replacement cost.

REFERENCES

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

2. 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. 173184, 2011.

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

4. H. C. Shih, S. C. Chu, J. Roddick, J. H. Ho, B. Y. Liao, and J. S. Pan, A Reduce Identical Event Transmission Algorithm for Wireless Sensor Networks, in Proc. 3rd Int. Conf. Intell. Human Comput. Interact., 2011,pp. 147154.

5. 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. 216, Feb. 2003.

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. 204212, Jun. 2012.

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

8. Hong-Chi Shih, Jiun-Huei Ho,Bin-Yih Liao etc Fault Node Recovery Algorithm for a Wireless Sensor Network IEEE sensors journal VOL:13 NO 7 2683 – 2689 July 2013.

9. Y.C. Wang, W.C. Peng, and Y.C. Tseng, Energy-Balanced Dispatch of Mobile Sensors in a Hybrid Wireless Sensor Network, IEEE Trans. Parallel and Distributed Systems, vol. 21, no. 12, pp. 1836-1850, Dec. 2010.

10. Scott M. Thede ,ePauw University Greencastle, An Introduction to Genetic Algorithms JCSC 20, 1 October 2004.