AIRCC PUBLISHING CORPORATION
FAULT-TOLERANT ROUTING SCHEME BASED ON LEACH FOR WIRELESS SENSOR NETWORKS
Chifaa TABET HELLEL¹ , Mohamed LEHSAINI¹ , and Hervé GUYENNET²
¹ STIC Laboratory, Faculty of Technology, Tlemcen University, Algeria
²FEMTO-ST/DISC UFR ST, University of Franche-Comte, France
Most routing protocols designed for wireless sensor networks used the unit disk graph model (UGD) to represent the physical layer. This model does not take into account fluctuations of the radio signal. Therefore, these protocols must be improved to be adapted to a non-ideal environment. In this paper, we used the lognormal shadowing (LNS) model to represent a non-ideal environment. In this model, the probability of successful reception is calculated according to the link quality. We evaluated LEACH’s performance with LNS model to illustrate the effects of radio signal. Unfortunately, our findings showed that the fluctuations of signal radio have a significant impact on protocol performance. Thereby, we proposed a Fault-Tolerant LEACH-based Routing scheme (FTLR scheme) to improve the performance of LEACH in a non-ideal environment. Simulation results proved that our contribution provides good performance over the ideal model in terms packet loss rate and energy consumption
FTLR scheme, LEACH, Lognormal Shadowing Model, Model Unit Disk Graph Model, WSN.
Wireless sensor network (WSN) is a set of devices called “sensor nodes” distributed over an area to monitor the surrounded environment. Sensor nodes have capabilities of computing, sending and receiving sensed data. Recently, WSNs have attained an appreciable attention that many researchers have devoted a lot of studies to improve its interests in many domains like environmental monitoring, industrial control, transportation, and healthcare, and in these applications, the reliability of the network is required for collecting data without loss from nodes. Therefore, prolonging the network lifetime is an important and challenging issue, which is also the focus of designing the routing protocols for WSNs .
Routing process is a fundamental operation in WSNs. It consists in transmitting a message from a source node to a remote base station according to the main routing schemes: hierarchical, location-based, data-centric and QoS-aware . Furthermore, most routing protocols derived from these schemes rely on a physical layer based on an ideal model represented by the Unit Disk Graph model (UDG) . However, this model although commonly used cannot be considered as a realistic model since it assumes that the messages are always received without any error if the distance between the transmitter and the receiver is less than or equal to the transmission range . This assumption does not take into account the random fluctuations of the radio signal, which may have a significant impact on the transmissions. Therefore, it is interesting to study the behaviour of these routing protocols in a realistic environment to illustrate the impact of radio fluctuations on the performance of these protocols. Among all these solutions, we have chosen to focus on LEACH protocol  for several reasons: it provides good results using an ideal physical layer and it is the most popular routing protocol designed for WSNs.
In this paper, we used the LogNormal Shadowing model (LNS)  for a non-ideal environment and analyze the performance of LEACH protocol with this model. The used model takes into account radio signal fluctuations, and therefore could be more realistic than the commonly used static UDG model. LNS model computes the probability of successful reception between communicating nodes according to the distance separating them. Then, we accordingly propose a Fault-Tolerant LEACH-based Routing scheme (FTLR) to adapt the original version of LEACH to a non-ideal environment. In FTLR scheme, we assume that if the probability of reception without error is lower than a certain threshold, the message will be dropped. In this case to avoid this anomaly, we proposed a multi-hop routing scheme for intra-cluster communications so that the member node could use a relay node to reach its cluster-head.
The remainder of this paper is organized as follows: Section 2 provides some necessary preliminaries for describing the model used for the realistic physical layer. In section 3, we review related work. Section 4 evaluates LEACH with the lognormal shadowing model and proposes an improved version of LEACH for realistic environments. In Section 5, we present simulation results and compare them with the original version of LEACH over an ideal environment. Finally, Section 6 concludes the paper with a summary and future work related to this topic.
Before presenting our contribution, we will give some definitions and notations that facilitate the understanding of what follows.
2.1.Notations and assumptions
WSN can be represented as a graph G=(V,E) with a set of vertices (V) consisting of the nodes of the network and a set of edges (E ⊆ V² ) consisting of the links between the nodes. An edge e = (u,v) belongs to E if and only if the node u is physically able to transmit messages to v and vice versa. Each node (u∈V) is assigned by an unique value to be used as an identifier Id(u). The set of neighbors of a node u is represented by N1(u) and the size of this set is known as the degree of u, denoted by δ(u) as presented in equation (1).
– Each node has an omni-directional antenna thereby a single transmission of a node can be received by all nodes within its vicinity.
– The nodes are almost static in a reasonable period of time.
– A node is considered as neighbor of another node if the probability of receiving messages from each other is greater than a defined threshold p0.
– A message can be received without any error, if the distance separating the communicating nodes is less than or equal to p0.
2.1. Radio model
We primarily present the unit disk graph model. Let us assume a graph G = (V, E), where all nodes have the same transmission range denoted by Rc. The UDG model defines the set E of the edges as follows:
where dist(u,v) is the Euclidean distance between u and v. This model although commonly used cannot be considered as a realistic model since it assumes that the messages are always received without errors if the distance between the communicating nodes is lower than or equal to the transmission radius Rc . This assumption does not take into account the random fluctuations of the radio signal, which could have a significant impact on the quality of transmission.
Thereby, it is interesting to evaluate the performance of these routing protocols in a realistic environment to illustrate their robustness in this kind of environments. For that, we have involved the link quality factor in determining the probability of successful reception between nodes in order to know if the message is received or it is corrupted. Since this probability implied several factors such as signal strength, the distance separating the communicating nodes, and the presence of obstacles, etc…, it may be difficult to obtain an accurate evaluation of these factors which are themselves prone to errors. Therefore, we assume that signal strength gradually decreases according to the distance; thereby the probability of reception without errors can be calculated according to the distance separating two nodes. Thus, we proposed using the LNS model described in [6,7] to evaluate this probability between nodes as presented in equation (3).
where α represents the attenuation factor which depends on the environment and x is thenconsidered distance separating the transmitter node from the receiver node. In equation (3), we assume that the probability of successful reception is 0.5 when the distance between the communicating nodes is equal to Rc. Figure 1 illustrates the evolution of the probability of reception without errors depending on the distance between the communicating nodes with Rc=10
3. RELATED WORK
Routing in wireless sensor networks has previously been studied in several papers such as . Moreover, other protocols use a multi-path routing scheme to avoid failed nodes when sending data such as that described in . However, most of the protocols presented in these works have been performed with an ideal simulation environment.
As mentioned above, in this paper we have proposed using the LNS model to evaluate the performance of LEACH protocol in a realistic scenario. The considered model takes into account the variation of the radio signal strength caused by obstructions and irregularities in the surroundings of the transmitting and receiving antennas . Therefore, this model is more realistic than the UDG model.
In this section, we review some related works which have been carried out to alleviate routing in WSNs with non-ideal environment. In , the authors have developed an energy-efficient fault tolerant algorithm called DFCR (Distributed Fault-tolerant Clustering and Routing) for WSN. In DFCR, the base station (BS) broadcasts a “HELLO” message, and depending on the RSSI Received Signal Strength Indication) of the message received, each CH calculates the distance from the base station. Then, each CH broadcasts a hop-packet indicating the number of hops to reach the base station. Moreover, during cluster formation process, each sensor node selects its CH based on the cost function involving the residual energy of the CH, the distance between the node and CH, and the distance from CH to BS. If the sensor node has not a CH within it communication range due to random deployment or sudden failure of the corresponding CH, it broadcasts a “HELP” message to join the CH via a helping sensor node with multi-hop communication. Furthermore, CH selects the next hop to reach BS according to the distance between the base station and the number of hops calculated during the setup phase.
In , the authors proposed two algorithms to find the optimal routing path despite even in the case of loss of links. The proposed algorithms aim to reduce energy consumption and ensure reliable data transfer to the base station. Sending data from a source node to the base station is done using a multi-hop communication scheme in a generic model in which the probability of reception of data without errors is calculated according to the distance separating communicating nodes. The first algorithm establishes a path to the base station with the minimum energy consumption while guaranteeing reliable routing data. The second algorithm aims to balance energy consumption among the nodes and minimize energy consumption when a node fails. In , the authors proposed a novel hierarchical routing protocol which addresses fault-tolerance through a multi-path topology and energy preservation through a cluster-based routing protocol.
In this algorithm three kinds of nodes are used: cluster member, cluster-head, overlapping areahead (OAH). The principle of this algorithm is almost similar to that of LEACH protocol and the only difference is that a cluster member may belong to more than one cluster. Moreover, a CH may have several OAHs associated with it and a cluster should have a common OAH with its neighboring clusters. In data transmission phase, the CH aggregates data received from its members and sends it to each OAH within its cluster, and each OAH sends received data to its associated CH. This process of transfer data continues until reaching the remote base station. In , an improved version of LEACH is proposed, in which each cluster member is within transmission range of two neighboring cluster-heads. Therefore, if a CH fails the member node joins the other CH. This anomaly is detected by the base station such as if no response is received from a CH, the latter is considered as faulty CH.
In , another algorithm has been proposed to detect the failure of CH in a short time after the beginning of each round. It is assumed that the CH transmits a “HELLO” message to all its members, and if no transmission is received, the CH is considered as failed node. The election of the new CH is based on the position of nodes in the cluster. In , the authors improved the previous version. They added another phase to the original LEACH phases called detection phase in which the failure is detected and all members should be advised about it. Therefore, to recover this failure, a faulty recovery phase is launched by the base station that selects the new CH among the cluster members based on their residual energy.
In , an enhanced version of LEACH is proposed in which each member cluster is covered by two cluster-heads: the main CH and its vice that takes its role when the main CH fails. The selection of CH is based on three criteria: minimum distance, maximum residual energy and minimum energy. Each non-CH chooses its CH based on RSSI such as, greater RSSI means shorter distance and thereby energy consumed for transmission is not enough.
In , the authors proposed an enhanced version of LEACH wherein each cluster contains a CH which is responsible for gathering data and sending it to the remote base station. These tasks could quickly deplete its energy; thereby a vice-CH will be involved to take its role to tolerate the failure of CH.
In , the authors proposed two fault-tolerant versions of LEACH. In the first version called FT1-LEACH, there is two cluster-heads in each cluster: ; primary CH (CHp) and secondary CH (CHs). The cluster members send their collected data to CHp and CHs . Moreover, when CHp is alive, it is considered as responsible for aggregating data and transmitting it to the base station, and if CHp fails, its vice (CHs) would send collected data to the base station. In the second version called FT2-LEACH, the authors used the checkpoint technique in which the base station should store all availability information about cluster-heads and their members. If at any time, the base station does not receive any supervisory message from CH, it considers it as failed CH, and elects a new CH among their members.
As mentioned above, several studies have been proposed to make LEACH fault-tolerant protocol but these studies do not take into account the link quality during data delivery. Furthermore, most of these contributions involve more than one cluster-head in a cluster to ensure reliable delivery such as in [10,17,18] but these contributions could not guarantee this goal with a realistic environment. In this context, we evaluated LEACH with LNS model to illustrate its limitations in such environments. Then, we proposed an improved version of LEACH that involves the link quality in the selection of relay nodes in order to guarantee reliable data delivery and consequently make LEACH adaptable to a realistic environment.
Before presenting our contribution, we evaluated at first the performance of LEACH protocol with the LNS model to point out its weaknesses in terms of the number of lost packets, the ratio of lost packets and energy consumption.
4.1. Evaluation of LEACH with LNS Model
In this section, we evaluated the performance of the original version of LEACH in a non-ideal environment in terms of the number of lost packets and the ratio of lost packets. We used TOSSIM simulator  to evaluate the performance of LEACH and we analyzed the obtained results to illustrate the weaknesses of the original version of LEACH in a non-ideal environment. We used the LNS model to represent a non-ideal environment. This model implies the link quality to compute the probability of successful reception. Furthermore, we have varied this probability (p=0.6, 0.7, 0.8) for various network sizes: 20, 40, 60, 80 and 100 nodes.
Figure 2 shows the variation of the number of packets lost according to the network size for various values of probability of successful reception. We observe that the number of lost packets increases when this probability increases. These obtained results mean that the performance of LEACH degrades in a realistic environment thereby the original version of this protocol is not adaptable for non-ideal environment.
Figure 3 illustrates the ratio of packets lost according to the network size with various values of probability. We notice that the ratio of packets corrupted increases when the probability of successful reception increases. For example, in a network that contains 100 nodes with the probability of successful reception is 0.8, the ratio of lost packets becomes half of all transmitted packets thereby it is necessary to take into account link quality.
4.2. Proposed routing scheme (FTLR scheme)
According to the performance of LEACH in a non-ideal environment, it is shown that is necessary to improve LEACH, so that it would be adapted to a realistic environment. Hence, we have proposed a multi-hop routing scheme called FTLR scheme instead of a single-hop routing scheme to overcome packet loss when a member node could not communicate correctly with its CH.
Our contribution takes into account the link quality to avoid unreliable links, hence when a member node would transmit data to its corresponding CH, it computes the probability of successful reception. If this probability is high er than a predefined threshold Thresh, the packet will be received without errors; otherwise a multi-hop routing scheme will be incorporated to ensure reliable delivery and in the same time minimize energy consumption since a multi-hop routing scheme consumes less energy than single-hop routing scheme .
We assumed that if a cluster member has a reliable communication link with its respective CH, it is considered as a perfect node, and a list of this kind of nodes is created. Moreover, when the probability of reception without errors is less than the predefined threshold, the cluster member selects the optimal next-hop node among its neighbors to reach its CH. This selection is performed according to the following algorithm:
– Mi: Identifier of a cluster member i
– CHi: Identifier of a clusterhead i
-(xm,ym):coordinates of Mi
-(xc,yc):coordinates of Mi
Mi computes the Euclidean distance to its CHi
Mi computes the probability of successful reception
if (Pr(d)<Thresh) then
—Mi chooses among its neighbors one that guarantees reliable data delivery with its CH
– Choose v from N1(Mi)
– Computing of distances : d1 and d2
– d1: distance from Mi to v
– d2: distance from v to CHi
– Computing of the probabilities: Pr1 and Pr2
Until:(Pr1(d1)≥Thresh) and (Pr2(d2)≥Thresh)
In our experiments, we conducted extensive simulations with the LNS model to evaluate the performance of the proposed contribution (FTLR scheme) in terms of the ratio of lost packets and energy consumption. For that, we used a network topology in which nodes are randomly distributed between (x = 0, y = 0) and (x = 500, y = 500). We performed simulations using two distinct thresholds Thresh1=0.6 and Thresh2=0.7 for probability of reception without errors. Table 1 summarizes the simulation parameters used for these evaluations.
5.1. Rate of lost packets
We evaluated the performance of FTLR and the original version of LEACH with the LNS model.
Figure 4 shows that the number of lost packets is almost negligible in FTLR scheme compared to that of LEACH. That means that the reliability is achieved with FTLR for various probability values Thresh1=0.6 and Thresh2=0.7
Figure 5 proves the efficiency of our contribution such as the ratio of lost packets is also almost negligible, it attains the reliability required. Therefore, our contribution would provide a sufficient trade-off between guaranteeing the transmission reliability and achieving fault-tolerance of communication links. Hence, based on these results, FTLR can outperform the original version of LEACH and it can be applied in realistic environment
5.2. Energy consumption
Since energy consumption is one of the major concerns in WSNs, we evaluated the energy consumption and compared it between FTLR and the original version of LEACH. We assumed that if the probability of reception without errors is less than a predefined threshold the cluster member generates a random number whose value is between 0 and 1, and if this number is higher than 0.5, it will perform a retransmission of the packet; otherwise the packet will be dropped. In this context, the energy consumption is calculated according to the energy model [21 ] which considers that the energy consumed for transmitting and receiving of one bit using MICA2 sensor model is respectively 4.602 µJ and 2.34 µJ
Figures 6 and 7 shown respectively that energy consumption in FTLR is lower than in LEACH, since the multi-hop communication scheme is efficient in minimizing energy consumption, by against the retransmission is costly in terms of energy consumption when packets are dropped.
In this paper, we used the LNS model to evaluate the performance of the original version of LEACH protocol to illustrate its robustness in non-ideal environments. LNS model takes into account the fluctuations of radio signal, and could therefore be considered as a realistic model compared with the UDG model. The results showed the weaknesses of LEACH protocol in a nonideal simulation environment such as the LNS model. Thereby, we have proposed a fault-tolerant LEACH-based routing protocol for non-ideal environments. Simulation results illustrate that our proposed contribution compared with the original version of LEACH provides much better performance in terms of the ratio of lost packets and energy consumption.
Furthermore, since most existing protocols rely on a physical layer based on the UDG model, evaluating these protocols in a realistic layer could be interesting. Our further work includes the analysis of other protocols in a realistic environment.
 Guo, W., Zhang, W. (2014) ”A survey on intelligent routing protocols in wireless sensor networks”. Journal of Networks and Computer Applications, Vol. 38, pp185-201.
 Akkaya, K., Younis, M. (2005) “A survey on routing protocols for wireless sensor networks”. Ad Hoc Networks, Vol. 3, No. 3, pp 325-349.
 Clark, B.N., Colbourn, C.J., Johnson, D.S. (1990) “Unit disk graphs”. Discrete Mathematics, Vol. 86, No. 13, pp 165-177.
 Lehsaini, M., Guyennet, H., Feham, M. (2007) “MPR-based broadcasting in ad hoc and wireless sensor networks with a realistic environment”. International Journal of Computer Science and Network Security, Vol. 7, No. 10, pp 82-89.
 Heinzelman, W., Chandrakasan, A., Balakrishnan, H. (2000) “Energy-efficient communication protocol for wireless microsensor networks”. In the Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Vol. 2, pp 1-10.
 Rappaport, T.S. (2002) “Wireless Communications: Principles and Practice”. Second edition. Prentice Hall PTR.
 Kuruvila, J., Nayak, A., Stojmenoviç, I. (2006) “Hop-count optimal position based packet routing algorithms for ad hoc wireless networks with a realistic physical layer”. IEEE International Conference on Mobile Ad-hoc and Sensor Systems, Vol. 23, No. 6, pp 1267-1275.
 Ahlawat, A., Malik, V. (2013) “An extended vice-cluster selection approach to improve v LEACH protocol in WSN”. In the proceeding of third International Conference on Advanced Computing and Communication Technologies, pp 236-240.
 Tyagi, S., Kumar, N. (2013) “A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks”. Journal of Networks and Computer Applications, Vol. 3, pp 623-645.
 Tang S. (2011) “Traffic Flow Analysis of a Multi-hop Wireless Sensor Network Subject to Node Failure”. International Journal of Communication Networks and Information Security (IJCNIS), Vol. 3, No. 2, pp 163-169.
 Azharuddin, M., Kuila, P., Jana, P.K. (2015) “Energy efficient fault tolerant clustering and routing algorithms for wireless sensor networks”. Computers and Electrical Engineering, Vol. 41, pp 177- 190.
 Levendovszky, J., Tran-Thanh, L., Treplan, G., Kiss, G. (2010) “Fading-aware reliable and energy efficient routing in wireless sensor networks”. Computer Communications, Vol. 33, No. 1, pp 102- 109.
 Beldjehem, M. (2013) “Toward a multi-hop, multi-path fault-tolerant and load balancing hierarchical routing protocol for wireless sensor network”. Wireless Sensor Network, Vol. 5, No. 11, pp 215-222.
 Mitra, R., Biswas, A. (2012) “Incorporating fault tolerance in LEACH protocol for wireless sensor network”. International Journal of Computer Science and Communication Networks, Vol. 2, No.3, pp380-384.
 Mohammed, A.S., Shanmukhaswamy, M.N. (2012) “New algorithm for optimized cluster-heads with failure detection and failure recovery to extend coverage of wireless sensor network”. International Journal of Scientific and Research Publications, Vol. 2, No. 11, pp.1-4.
 Min H. Y., Z.W. (2014) “Energy-efficient fault-tolerant routing leach (EF-LEACH) protocol for wireless sensor networks”. International Conference on Advances in Engineering and Technology, pp. 36-40.
 M. Bani Yassein A. Al-zou’bi, Y. Khamayseh, W. Mardini. (2009) “Improvement on LEACH protocol of wireless sensor network (VLEACH)”. International Journal of Scientific and Research Publications, Vol. 3, No. 2, pp260-264.
 Lehsaini, M. and Guyennet, H. (2013) “Improvement of LEACH for fault-tolerance in sensor networks”. The Fourth IFIP International Conference on Modeling Approaches and Algorithms for Advanced Computer Applications, Vol. 488, pp175-183.
 Levis, P., Lee, N., Welsh, M., Culler, D. (2003) “Tossim: Accurate and scalable simulation of entire tinyos applications”. In Proceedings of the First ACM International Conference on Embedded Networked Sensor Systems, pp. 126-137.
 Vlajic, N. and Xia, D. (2006) “Wireless sensor networks: to cluster or not to cluster?”, International Symposium on World of Wireless, Mobile and Multimedia Networks, pp260-268.
 Shnayder, V., Hempstead, M., Chen, B., Allen, G.W., Welsh, M. (2004) “Simulating the power consumption of large-scale sensor network applications”. In the Proceedings of the 2nd ACM International Conference on Embedded Networked Sensor Systems, pp188-200.