In a Wireless Sensor Network (WSN), sensor nodes are powered by batteries that can operate for only a short period of time, which results in short network lifetime. The short lifetime disables the application of WSNs for long term tasks such as structural health monitoring for bridges and tunnels, border surveillance, road condition monitoring, and so on. Hence, many energy conservation schemes were proposed to battle the constraint. With these schemes, the rate of energy consumption is slowed down, but consumed energy cannot be compensated. Therefore, the effectiveness of these schemes is inherently restrained by the amount of energy preloaded to sensor nodes. Fully addressing the problem requires that energy be continually replenished to sensor nodes. One possible approach is to harvest energy from various environmental sources such as the sunlight. However, efficient harvesting technologies are still absent. In particular, the amount of energy that a solar cell can harvest is proportional to its surface area, but it is infeasible to equip a tiny sensor node with a large-size solar cell. The amount of available solar energy also depends on uncontrollable conditions such as cloudiness of the sky. Hence, it is very likely that the energy harvested is limited and unable to satisfy the needs of sensor nodes. Another solution is to incrementally deploy new sensor nodes to take over sensor nodes running out of energy. This approach, however, is costly because sensor node hardware cannot be reused, and more importantly, it causes pollution to the environment because dead batteries and hardware are left in the environment. Seeking an effective and efficient way to guarantee long-term energy supply remains as a big challenge.

This paper proposes a Fault Node Detection Algorithm [1] to improve the lifetime of a wireless sensor network when some of the sensor nodes shut down, either because they no longer have battery energy or they have reached their operational threshold. Here, by using Unequal Clusterbased Routing Protocol, the network is divided into cluster groups which have cluster heads which are used to form a routing path. Using the FNR algorithm [1] can result in fewer replacements of sensor nodes and more reused routing paths. Thus, the algorithm not only enhances the WSN lifetime but also reduces the cost of replacing the sensor nodes.

The traditional approaches to sensor network routing include the Directed Diffusion (DD) algorithm [2] and the Grade Diffusion (GD) algorithm [3]. The algorithm proposed in this paper is based on the GD algorithm, with the goal of replacing fewer sensor nodes that are inoperative or having depleted batteries, and of reusing the maximum number of routing paths. These optimizations will ultimately enhance QoS parameters [4] as well as the lifetime of sensor network and also reduce the cost of the wireless sensor networks applications.

Directed Diffusion is a novel data-centric, data dissemination paradigm for sensor networks. Directed diffusion has some novel features: data-centric dissemination, reinforcement-based adaptation to the empirically best path, and in-network data aggregation and caching. These features can enable highly energyefficient and robust dissemination in dynamic sensor networks, while at the same time minimizing the per-node configuration that is characteristic of today's networks.

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.

In 2011, H. C. Shih et al proposed a Grade Diffusion algorithm that improves upon the LD-ACO algorithm [5] to enhance node lifetime, raise transmission efficiency, and solve the problem of node routing and power consumption. The GD algorithm broadcast grade completely and quickly creates packages from the sink node to every node in the wireless sensor network by the LDACO algorithm. Then the GD algorithm proposes a routing algorithm to reduce the nodes' average load, enhance the nodes' lifetimes and reduce the nodes' power consumption.The GD algorithm can also record some information regarding the data relay. Then, a sensor node can select a node with a lighter loading or more available energy than the other nodes to perform the extra relay operation. That is, the GD algorithm updates the routing path in real time, and the event data is thus sent to the sink node quickly and correctly.

Whether the DD or the GD algorithm is applied, the grade creating packages or interested query packets must first be broadcasted. Then, the sensor nodes transfer the event data to the sink node, according to the algorithm, when suitable events occur. The sensor routing paths are shown in Figure 1.

Figure 1. Wireless sensor node routing

The WSN may fail due to a variety of causes, including the following: the routing path might experience a break; the WSN sensing area might experience a leak; the batteries of some sensor nodes might be depleted, requiring more relay nodes; or the nodes wear out after the WSN has been in use fora long period of time. In Figure 2, the nodes transfer event data to the sink node via the inside nodes (the sensor nodes near the sink node) in a WSN which illustrates the accommodation measures for non-working nodes [6]. The inside nodes thus have the largest data transmission loading, consuming energy at a faster rate. If all the inside nodes deplete their energy or otherwise cease to function, the event data can no longer be sent to the sink node, and the WSN will no longer function

Figure 2. Wireless sensor node routing path when some nodes are not functioning.

The power consumption of the sensor nodes in WSNs is unavoidable. This paper, 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) [7], is a directed random search technique developed in 1975, based on the concept of natural genetics. The current paper proposes Fault Node Detection (FND) algorithm based on the GD algorithm combined with the GA. The FNR 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 exceed the threshold. This algorithm not only reuses the most common routing paths to enhance the WSN lifetime, but also reduces the replacement cost.

This paper proposes Fault Node Detection (FND) algorithm for WSNs based on the grade diffusion algorithm combined with the genetic algorithm. The flow chart is shown in Figure. 3. The FND algorithm creates the grade value, routing table, neighbour nodes, and payload value for each sensor node using the grade diffusion algorithm.

Figure 3. Fault Node Detection algorithm flow chart.

In the FNR algorithm, the number of non functioning sensor nodes is calculated during the wireless sensor network operation, and the parameter B is calculated according th to below equations (1),(2).

(1)

(2)

In the above equations, Grade is the sensor node's grade value. The variable  N_i^original  is the number of sensor nodes with the grade value i .The variable N_i^now is the number of sensor nodes still functioning at the current time with grade value i . The parameter β is set by the user and must have a value between 0 and 1. If the number of sensor nodes that function for each grade is less than β, Ti will become 1, and B_th will be larger than zero. Then, the algorithm will calculate the sensor nodes to replace using the genetic algorithm.

The parameters are encoded in binary string and serve as the chromosomes for the GA. The elements (or bits), i.e., the genes, in the binary strings are adjusted to minimize or maximize the fitness value. The fitness function generates its fitness value, which is composed of multiple variables to be optimized by the GA. At each iteration of the GA, a predetermined number of individuals will produce fitness values associated with the chromosomes. There are 5 steps in the genetic algorithm:

• Initialization
• Evaluation
• Selection
• Crossover
• Mutation.

Descriptions of the steps follow.

In the initialization step, the genetic algorithm generates chromosomes, and each chromosome is an expected solution. The number of chromosomes is determined according to the population size, which is defined by the user. Each chromosome is a combination solution, and the chromosome length is the number of sensor nodes that are depleted or nonfunctioning. 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. Figure 4 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.

Figure 4. Chromosome and its gene

In general, the fitness value is calculated according to a fitness function, and the parameters of the fitness function are the chromosome's genes. However, we cannot put genes directly into the fitness function in the FNR algorithm, because the genes of the chromosome are simply whether the node should be replaced or not. In the FNR algorithm, the goal is also to reuse the most routing paths and to replace the fewest sensor nodes.

Hence, the number of routing paths available if some nonfunctioning sensor nodes are replaced is calculated, and the fitness function is shown in below equation (3).

(3)

In the above equation:

N_i = the number of replaced sensor nodes and their grade  value at i .

P_i = the number of re-usable routing paths from sensor nodes with their grade value at i .

TN = total number of sensor nodes in the original WSN.

TP = total number of routing paths in the original WSN. Here, a high fitness value is sought because the WSN is looking for the most available routing paths and the least number of replaced sensor nodes.

The selection step will eliminate the chromosomes with the lowest fitness values and retain the rest. We use the elitism strategy and keep half of the chromosomes with better fitness values and put them in the mating pool. The worse chromosomes will be deleted, and new chromosomes will be made to replace them after the crossover step. The process is shown in Figure 5.

Figure 5. Selection Step

The crossover step is used in the genetic algorithm to change the individual chromosome. In this algorithm, the authors use the one-point crossover strategy to create new chromosomes, as shown in Figure 6. Two individual chromosomes are chosen from the mating pool to produce two new offsprings. 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. The rate of choice is made according to roulette-wheel selection and the fitness values.

Figure 6. Crossover Step

The mutation step can introduce traits not found in the original individuals and prevents the GA from converging too fast. In this algorithm, we simply flip a gene randomly in the chromosome, as shown in Figure 7.

Figure 7. Mutation Step

In this paper, Figure 3 explains the FNR algorithm and in Figure 8, the proposed algorithm of the Unequal clusterbased routing protocol in which the FNR algorithm is used to recover the fault nodes in the cluster-based routing protocol which we are implementing. This protocol is explained through clustering mechanism in further part of this section.

Figure 8. Unequal Cluster Routing Protocol flow chart

Clustering Mechanism [8], [10] is performed in two phases: Cluster formation and data transmission phase

As shown in Figure 9. the cluster heads in the first round are the nodes in the middle of each partitioned sector as they have more neighbor nodes which are close to the centre of cluster. Initially, the base station broadcasts the “hello” packet to all the nodes throughout the network. This packet contains node-ID, cluster ID, initial energy Eo, number of neighboring nodes or node degree Di and distance to centroid Ci.

Figure 9. Cluster formation with cluster head

In this phase, each cluster head initially computes the distance (d CH) for all member nodes and searches for any node which is located beyond critical distance d0 = 87m. If the cluster head finds any member node with dCH > do in the sector, then it computes Dijkstra's algorithm to find shortest path to those nodes with multi-hop routing. Then it sends a control packet to the relay node with node-Id of multi-hop node. If the multi–hop node has data to transmit then it transmits data to relay node. The relay node combine the data with its own data and it sends to the base station through the next cluster head.

The experiment was simulated using the Network Simulator [9] version 2(NS-2) with below simulation parameters shown in Table 1.

Table 1. Simulation Parameters

After simulating the experiment and obtaining the respective simulation values, we compared these values to the previous Direct Diffusion (DD) algorithm and the results are shown below Figure. 10. illustrates the number of packets received by both FNR algorithm and direct diffusion algorithm that it attains a constant value at some time where, as time increases, number of packets for reception goes to a constant level. The simulation result of the packet loss in both FNR and UCRP is shown in Figure 11 which illustrates that the number of packet loss increases as time goes on in the FNR. But by using UCRP, the packet loss decreases in a large scale. Packet loss is achieved by switching of cluster head when it runs out of energy to other cluster head in a cluster which is at the center.

Figure 10. Number of messages reaching the sink node

Figure 11. Packet loss between FNR and UCRP

In Figure12, the illustration of energy ratio is obtained for both FNR and DD algorithm where, as time goes on the energy consumption of DD algorithm gradually decreases and comes to constant and for FNR algorithm, the decrease in energy is not so efficient than DD algorithm.

Figure 12. Average Energy Consumption

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 used routing paths when some sensor nodes are non-functional. This paper proposes a fault node detection algorithm for WSN based on the grade diffusion algorithm combined with a genetic algorithm using unequal cluster-based protocol. The FNR 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. The number of active nodes is enhanced. The algorithm reduces the rate of data loss and reduces the rate of energy consumption. Therefore, the FNR algorithm using Unequal cluster-based protocol not only replaces sensor nodes, but also reduces the replacement cost and reuses the most routing paths to increase the WSN lifetime.