# A version of LEACH Adapted to the Lognormal Shadowing Model

Chifaa Tabet Hellel, Mohamed Lehsaini, Hervé Guyennet

► To cite this version:

Chifaa Tabet Hellel, Mohamed Lehsaini, Hervé Guyennet. A version of LEACH Adapted to the Lognormal Shadowing Model. 5th International Conference on Computer Science and Its Applications (CIIA), May 2015, Saida, Algeria. pp.465-475, 10.1007/978-3-319-19578-0_38. hal-01789956

HAL Id: hal-01789956

https://inria.hal.science/hal-01789956

Submitted on 11 May 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Version of LEACH Adapted to the Lognormal Shadowing Model

¹Tabet Hellel Chifaa, ¹Lehsaini Mohamed, and ²Guyennet Hervé

¹STIC Laboratory, University of Tlemcen, Algeria

²FEMTO-ST/DISC UFR ST, University of Franche-Comte, France

tabetchifaa@gmail.com, m_lehsaini@mail.univ-tlemcen.dz,

hervé.guyennet@femto-st.fr

**Abstract.** The most protocols designed for wireless sensor networks (WSNs) have been developed for an ideal environment represented by unit disc graph model (UDG) in which the data is considered as successfully received if the communicating nodes are within the transmission range of each other. However, these protocols do not take into account the fluctuations of radio signal that can happen in realistic environment. This paper aims to adapt LEACH protocol for realistic environment since LEACH is considered as the best cluster-based routing protocol in terms of energy consumption for WSNs. We have carried out an evaluation of LEACH based on two models; lognormal shadowing model (LNS) in which the probability of reception without error is calculated according to the Euclidian distance separating the communicating nodes and probabilistic model in which the probability of reception is generated randomly. In both models, if the probability of successful reception is lower than a predefined threshold, a multi-hop communication is incorporated for forwarding data between cluster-heads (CHs) towards the base station instead of direct communication as in original version of LEACH. The main aims of this contribution are minimizing energy consumption and guaranteeing reliable data delivery to the base station. The simulation results show that our proposed algorithm outperforms the original LEACH for both models in terms of energy consumption and ratio of successful received packets.

**Keywords:** LEACH, Lognormal shadowing model, Multi-hop scheme, Probabilistic model, Unit Disc Graph model, WSNs.

## 1 Introduction

WSNs are composed of hundreds and thousands of small devices called "sensor nodes" distributed over a monitoring area for sensing data and sending it to a remote base station directly or via a multi-hop communication scheme depending on the application designed [1]. This novel technology has allowed the appearance of many applications such as; military, security, medical, environment monitoring, etc, due to the low cost of sensor nodes. Moreover, with this technology our way of life has been revolutionized since it allowed us to interact with the surrounded environment.
Routing process is a fundamental operation in wireless sensor networks. It consists in establishing path to transmit 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 [2]. However, cluster-based routing in wireless sensor network is considered as the perfect solutions for minimizing energy consumption [3,4]. In this scheme, the network is divided into clusters wherein each cluster contains a number of members which sense data from its environment and send it to its corresponding cluster-head (CH). The latter is responsible for gathering data received from its members. If the distance between the source node and the destination node will increase, the energy consumption also increases, thereby a cluster-based routing scheme is recommended. Among the protocols proposed, LEACH (Low Energy Adaptive Clustering Hierarchy) [5] is considered as the best cluster-based protocol for saving energy. Nevertheless, the performance of these protocols may degrade in non-ideal environments.

In this paper, we used the lognormal shadowing model [6] and the probabilistic model to simulate a non-ideal environment, and we evaluated the performance of LEACH with these both models. Then, we proposed an improved version of LEACH to overcome the limitations of the original version. The proposed version involves a CH-to-CH routing scheme to guarantee reliable delivery. This routing scheme is used if the probability of reception of packets without error between cluster-heads and the base station is lower than a predefined threshold. Moreover, this scheme also permits to minimize energy consumption.

The rest of paper is organized as follow; in section 2, we give an overview on LEACH protocol and discuss some works that improve LEACH related to our requirements. Section 3 presents our improved version of LEACH to be adapted in realistic environment, and in section 4, we illustrate performance of LEACH and the proposed contribution in non-ideal environment. Finally, in section 5, we conclude our paper.

## 2 Related Work

Since LEACH protocol is considered among the best cluster-based routing protocols in terms of energy efficiency, a lot of researches have been enhancing this protocol to reduce its limitations. In the following, we present briefly LEACH protocol and some variants of it.

LEACH [5] is a cluster-based routing protocol that aims to minimize energy consumption and thereby increasing network lifetime. In LEACH, the network is divided into clusters and each cluster is headed by a cluster-head which is elected by itself by generating a random number between 0 and 1. If the number generated is lower than a predefined threshold, the concerned node becomes a CH for the current round. The threshold is computed by each sensor node according to the equation (1).

$$T(i) = \begin{cases} \frac{p}{1-p*(r \mod \frac{1}{p})} & \text{if } i \in G \\ 0 & \text{otherwise} \end{cases} \quad (1)$$
where *p* is the percentage of cluster-heads, *r* is the current round, *G* is the set of nodes that have not been selected as cluster-heads in the last (1/*p*) rounds.

LEACH is performed in two phases: setup phase and steady phase. In setup phase, each CH broadcasts an advertisement message to construct its cluster, and each non-CH that receives this message joins the adequate cluster based on the RSSI (Received Signal Strength Indication) of the message received. Once the clusters are formed, a TDMA (Time Division Multiple Access) schedules are assigned to member nodes in each cluster. In steady phase, each member transmits its sensed data to its corresponding CH in its scheduled time-slot, and then the CH aggregates all data received from its members and sends it to the remote base station directly. To avoid interference between cluster-heads, each CH chooses a CDMA (Coding Division Multiple Access) code that is different from other clusters to communicate with the base station.

In [7], the authors have proposed a multihop routing scheme with lower energy adaptive clustering hierarchy called MR-LEACH. In this scheme, the CHs are responsible to aggregate data sensed by their members and act as relay nodes for remote CHs from the base station. MR-LEACH increases network lifetime since it uses a multihop routing scheme. This protocol is performed in three phases: cluster formation at lowest level, cluster discovery at different levels and scheduling. At the beginning of each round, cluster formation phase is lunched to construct a table in which each node maintains the information about its neighbors (node identifier, residual energy and node status) by using a 'Hello' message. Then, CHs broadcast a HEAD-MSG message in its vicinity and each non-CH chooses its respective CH among those in its neighborhood based on the strength of RSSI. In cluster discovery, the base station broadcasts its identifier (ID). Each CH that receives this broadcasted message records the identifier of the base station and replies by a beacon signal with its ID. CHs that are closest to the base station are in level one i.e. they could reach the base station by single hop. Then, BS broadcasts again a control message, the CHs that are at level two reply to this message forwarded by CHs of level one and the BS would record cluster-head's ID and its level. Similarly, this process is repeated until no new CH is discovered. After that, the BS will form a cluster of CHs. In scheduling phase; after cluster formation, a TDMA scheduling is used for communication between CHs at different levels.

In [8], the authors proposed MH-LEACH which uses a new scheme for multihop communication to minimize energy consumption. MH-LEACH is carried out in two phases to establish paths towards the base station. In the first phase, the cluster-heads are selected as in the original version of LEACH protocol, and then each CH broadcasts an announcement message within its vicinity. Each non-CH that receives this message chooses the closest one based on the RSSI of the message received. Moreover, the base station performs the same process. In the second phase; each CH sends its initial route to reach the base station and the latter send back the route to the CH to confirm that there is a route between the considered CH and the base station. Therefore, a routing table is created by each CH that contains a list of available routes to the base station and the shortest one is used.
In [9], the authors proposed an improved version of LEACH in which a multihop scheme is used and the election of the cluster-heads is done according to its residual energy. In this protocol, a multihop routing scheme for intra-cluster communication and a chain structure routing scheme for inter-cluster communication. The proposed protocol is performed in three phases: cluster formation, data delivery and update of clusters. At the beginning of the first phase, each node generates a random number between 0 and 1 and compares it with a predefined threshold to which the energy factor is added as illustrated by the equation (2).

$$T(n) = \begin{cases} \frac{p}{1-p*(r \mod \frac{1}{p})} \cdot \frac{E_n}{E_{Average}} & \text{if } n \in G \\ 0 & \text{otherwise} \end{cases} \quad (2)$$

where $E_n$ is the residual energy and $E_{Average}$ is the average residual energy of all nodes.

Each CH sets H to 0, where H is the number of hops from CH, and broadcasts a message containing (H=0, ID) in its vicinity. Each non-CH that receives this message joins the cluster to which it belongs the transmitter CH and sets its own CH to the CH of the message received and H to H+1, and PID with the ID of its parent. Then, this node also broadcasts a message containing (Hj,ID). If a node receives more than one message it compares its own H with H of the sending nodes and it updates its H with the lowest one among those received. For intra-cluster communication, each node sends its packet to its parent and this latter sends it to its parent until reach the CH, and in inter-cluster communication, CH transmits data in chain structure. The concerned CH chooses the closest CH from it as the next hop and this process is repeated until reach the base station. In update of clusters, at the end of a round the remaining energy of CH may not be sufficient for the next round so the CH must be replaced by the node with the greatest residual energy.

In [10], an enhanced version of LEACH is proposed whose aims are saving energy by using a CH-to-CH multihop scheme and creating a backup path between cluster-heads to achieve fault-tolerance in the presence of failures. At the beginning, the base station broadcasts a HELLO message and each CH that receives this message calculates the RSSI. If RSSI is higher than a predefined threshold, this CH is closest to the base station and if not the CH is away from it and therefore it needs a relay node to reach the base station. The relay node is one of the CHs that are closest to the base station and it is selected based on the RSSI of a message exchanged between CHs and a variable called $C_{red}$ which is a random number comprised between 0 and 1. If each of these parameters is higher than a threshold, this CH is considered as perfect relay node. However, the failure of one CH on the multihop path can affect the entire path and then the information cannot reach the base station, in this case a backup path is incorporated to this multihop path to ensure fault-tolerance and reliable delivery.
# 3 Contribution

Before presenting our contribution, we give a brief description of the lognormal model and probabilistic model. Then, we evaluate the performance of LEACH protocol with the both models to point out its weaknesses over an ideal environment.

## 3.1 Lognormal Shadowing Model

The lognormal shadowing model [6] is considered as a realistic model. It takes into account the fluctuations of radio signal caused by several factors such as noise, the presence of obstacles, weather conditions, etc... to evaluate the link quality between communicating nodes. The link quality is used to determine the probability of successful reception between communicating nodes in order to know if the message is received or it is corrupted by the destination node. Since this probability implied several factors, it may be difficult to obtain an accurate evaluation for all 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 computed according to the distance separating two nodes. We used the fluctuation of the signal model described in [11] as presented by the equation (3).

$$F(x) = \begin{cases} 1 - \frac{\left(\frac{x}{R_c}\right)^{2\alpha}}{2} & \text{if } 0 < x \le R_c \\ \frac{\left(\frac{2R_c-x}{R_c}\right)^{2\alpha}}{2} & \text{if } R_c < x \le 2R_c \\ 0 & \text{otherwise} \end{cases} \quad (3)$$

where $\alpha$ is the attenuation factor that depends on the environment and $x$ is the distance separating the two communicating nodes. $R_c$ is the transmission range and if the distance between two nodes is equal to $R_c$, the probability of successful reception is 0.5.

## 3.2 Probabilistic Model

In this model, the probability of reception without errors is generated randomly between each two communicating nodes. This model is used to illustrate the link quality. Moreover, the probability of successful reception is independent of the distance separating the communicating nodes but it depends on the factors which exist in the environment such as the presence or the absence of obstacles. Fig. 1 shows that node A can communicate with the node B but it cannot communicate with the node C although the distance that separates it with the node C is lower than that of the node B.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Communication in probabilistic model</figcaption></figure>

## 3.3 Proposed Scheme

In WSNs, LEACH is considered one of the best protocols in terms of energy efficiency. Several proposed protocols compare its effectiveness to LEACH and a lot of improved versions of LEACH have been proposed to reduce its limitations but they cannot guarantee its functionalities in a realistic environment. Our proposed algorithm aims to minimize energy consumption and ensures reliable delivery to the base station in a realistic environment based on lognormal shadowing model and probabilistic model.

We have proposed a multihop scheme instead of direct communication scheme between clusterheads and the base station to overcome the limitations of LEACH, such as when a CH aggregates data received from its members it computes the probability of reception without error of its packet to the base station. If this probability is higher than a predefined threshold, the packet is received correctly via direct communication by the base station and if not it means that the communication link is unreliable and in this case a multihop communication scheme will be incorporated to ensure the successful reception of packets by the base station. The proposed routing schemes are performed according to the following algorithms:

**Algorithm 1: Routing scheme based on LNS model**

- CHS: Set of clusterheads

- BS: Base station whose coordinates ($x_b, y_b$)

- d: Euclidean distance between CH($x, y$) and BS

- CHD: Set of clusterheads that can send data directly to the BS

- CHR: Set of clusterheads that use relay nodes to reach the BS

**Begin**

$$CH_D = \emptyset$$

$$CH_R = \emptyset$$

**For** ($CH \in CH_S$) **do**

- CH($x, y$) calculates the Euclidean distance that separates it from the BS

$$d = \sqrt{(x - x_b)^2 + (y - y_b)^2}$$

- CH computes the probability of reception without error
$$ Pr(d) = 1 - \frac{\left(\frac{d}{R_c}\right)^{2\alpha}}{2} $$

if (Pr(d) > Threshold) then

$$ CH_D = CH_D \cup \{CH\} $$

else

$$ CH_R = CH_R \cup \{CH\} $$

end if

end For

- Let CH a clusterhead

if (CH ∈ CH_D) then

- CH sends directly aggregated data to BS

else

- CH selects a (CH_r ∈ CH_D) as relay node with minimum distance to BS

$$ Min = \infty $$

For (CH_i ∈ CH_D) do

- computes the distance between CH(x, y) and CH_i (x_i, y_i)

$$ dd = \sqrt{(x - x_i)^2 + (y - y_i)^2} $$

if dd < Min then

$$ Min = dd $$

$$ CH_r = CH_i $$

end if

end for

- CHr is selected as relay node by CH

end if

End

Algorithm 2: Routing scheme based on probabilistic model

- CHS: Set of clusterheads

- BS: Base station

- CHD: Set of clusterheads that can send data directly to the BS

- CHR: Set of clusterheads that use relay nodes to reach the BS
Begin

CH<sub>D</sub> = Ø

CH<sub>R</sub> = Ø

For (CH ∈ CH<sub>S</sub>) do

- CH generates a random number (rd_number) comprise between 0 and 1

if (rd_number ≥ 0.5) then

CH<sub>D</sub> = CH<sub>D</sub> ∪ {CH}

else

CH<sub>R</sub> = CH<sub>R</sub> ∪ {CH}

end if

end For

- Let CH a clusterhead

if (CH ∈ CH<sub>D</sub>) then

- CH sends directly aggregated data to BS

else

- CH selects a (CH<sub>r</sub> ∈ CH<sub>D</sub>) as relay node such as CH and CH<sub>r</sub> have a maximum probability.

pr = 0

For (CH<sub>i</sub> ∈ CH<sub>D</sub>) do

- CH generates a random number (rd_number) between CH and CH<sub>i</sub>

if (rd_number > pr) then

pr = rd_number

CH<sub>r</sub> = CH<sub>i</sub>

end if

end for

- CH<sub>r</sub> is selected as relay node by CH

end if

End

## 4 Simulation Results

Several simulations have been carried out to illustrate the performance of our contribution using TOSSIM simulator [12], and compared them with the original version of LEACH in terms of energy consumption and the ratio of successful received packets at the base station. For that, we used a network that contains respectively 20, 40, 60,
80 and 100 stationary nodes, which are randomly deployed on a 100m x 100m square area and the initial energy of each node is equal to 2 joules. The simulations were performed in 600 seconds, and we used a threshold p= 0.7 for probability of reception without error in LNS model. We used this threshold to avoid on the one hand the ideal model whose threshold is 0.5 and the other to avoid a highly disturbed environment. Moreover, for probabilistic model, we used a threshold of p=0.5 i.e. a clusterhead generates a random number comprise between 0 and 1 and if this number is higher than 0.5 we assume that this clusterhead can communicate directly with the base station. Table I summarize simulation parameters.

<table><caption>**Table 1.** Simulation Parameters</caption><thead><tr><td>Parameter</td><td>Value</td></tr></thead><tbody><tr><td>Deployment Area</td><td>100m x 100m</td></tr><tr><td>Simulation Time</td><td>600 sec</td></tr><tr><td>Number of nodes</td><td>20, 40, 60, 80, 100</td></tr><tr><td>Packet size</td><td>29 bytes</td></tr><tr><td>Initial node energy</td><td>2 Joules</td></tr><tr><td>Threshold for LNS model</td><td>p = 0.7</td></tr><tr><td>Threshold for probabilistic model</td><td>p = 0.5</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Evaluation of ratio of successful received packets at BS with p=0.7</figcaption></figure>
Fig. 2 shows that the ratio of successful packets received at base station with a probability of p=0.7 in improved LEACH is higher than in original LEACH and also the ratio is higher with probabilistic model compared with LEACH. In improved LEACH the unreliability of links between a clusterhead and the base station can be treated by a multihop communication by against, in original LEACH the packet will be lost due to the unreliable links.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Energy consumption in LEACH and Improved-LEACH</figcaption></figure>

Fig.3 illustrates that energy consumption in improved LEACH based on LNS model or Probabilistic model is lower than in LEACH because in the improved version, the multihop transmission scheme minimizes energy consumption but the direct communication in LEACH consumes more energy.

# 5 Conclusion

In this paper, we have evaluated LEACH protocol in a realistic environment represented by lognormal shadowing model and a probabilistic model. However, results obtained illustrated that the performance of LEACH degrades in this kind of environment. Therefore, we have proposed an improved version of LEACH to overcome its weaknesses with realistic environment. The proposed scheme aims to find an op-
timal multihop path over links error which is modeled by LNS model and probabilistic model.

The simulation results showed that our contribution outperforms the original version of LEACH in terms of energy consumption and ratio of successful packets received at the base station. Moreover, our contribution deals with fault tolerance in LEACH, ensures reliable delivery and minimizes energy consumption.

# 6 References

1. Chanak, P., Banerjee, I.: Energy efficient fault-tolerant multipath routing scheme for wireless sensor networks. The Journal of China Universities of Posts and Telecommunications. 20(6), 42-61 (2013).

2. Akkaya, K., Younis, M. A.: Survey on routing protocols for wireless sensor networks. Ad Hoc Networks. 3(3), 325-349 (2005).

3. Tyagi, S., Kumar, N.: A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks. Journal of Network and Computer Applications. 36(2), 623-645 (2013).

4. Vlajic, N. and Xia, D.: Wireless sensor networks: to cluster or not to cluster?. International Symposium on World of Wireless, Mobile and Multimedia Networks. pp260-268, 2006.

5. Heinzelman, W. R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd IEEE Annual Hawaii International Conference on System Sciences, pp.1-10, Hawaii (2000).

6. Rappaport, T. S.: Wireless Communications Principles and Practice. Second Edition by Publisher: Prentice Hall Release (2001).

7. Farooq, M. O., Dogar, A. B., Shah, G. A.: MR-LEACH: Multi-hop Routing with Low Energy Adaptive Clustering Hierarchy. In: Proceeding of Fourth IEEE International Conference on Sensor Technologies and Applications (IEEE), pp.262-268, Venice, Italy (2010).

8. Neto, J., Antoniel Rego, A., Andr-Cardoso, A., Jnior, J.: MH-LEACH: A Distributed Algorithm for Multi-Hop Communication in Wireless Sensor Networks. In Proceeding of The Thirteenth International Conference on Networks (ICN), pp.55-61, Nice, France (2014).

9. Yang, H., Xu, J., Wang, R., Qian, L.: Energy-Efficient Multi-hop Routing Algorithm Based on LEACH. In: R. Wang and F. Xiao (Eds): CWSN 2012, CCIS 334, vol. 334, pp.578-587. Springer-Verlag, Heidelberg (2013).

10. Tabet Hellel, C., Lehsaini, M., Guyennet, H.: An Enhanced Fault-tolerant Version of LEACH for Wireless Sensor Networks. International Journal of Advancements in Computing Technology(IJACT). 6(6), 50-57 (2014).

11. Kurvilla, J., Nayak, A., Stojmenović, I.: Hop count optimal position based packet routing algorithms for ad hoc wireless networks with a realistic physical layer. IEEE Journal on Selected Areas in Communications. 23(6), 1267-1275 (2005).

12. Levis, P., Lee, N., Welsh, M., Culler, D.: TOSSIM: accurate and scalable simulation of entire TinyOS applications. In the First ACM International conference on Embedded networked sensor systems (SenSys'03), pp.126-137, New York, USA (2003).