Multi-Level LEACH protocol for Homogeneous Wireless Sensor Network

Multi-Level LEACH protocol for Homogeneous Wireless Sensor Network

Mohamed Saad Azizi

Research Team: ISIC ESTM, LMMI Laboratory Moulay-Ismail University

Meknes, Morocco

Moulay Lahcen Hasnaoui

Research Team: ISIC ESTM, LMMI Laboratory Moulay-Ismail University

Meknes, Morocco

Abstract Wireless Sensor Network (WSN) is a wireless network of small nodes with sensing capabilities, computation, and wireless communication. Each sensor collects data from the monitored area (such as temperature, sound, vibration, pressure, motion or pollutants). Then it sends data back to the base station BS. In Wireless Sensor Networks (WSN), the power resource of sensor nodes is limited, energy dissipation and network lifetime are the most important parameters to consider in the design of routing protocols for sensor networks. In this paper, we propose a new approach of LEACH (Low Energy Adaptive Clustering Hierarchy) protocol, which aims to reduce energy consumption by using a second hierarchical level in cluster head selection for data transmission process. Moreover, it uses a new random formula of probability based on the ratio between residual energy of each node and the remaining energy of the network. Finally, Simulation results show that the improved method can reduce the network consumption energy greatly and lengthens the network lifetime efficiently.

Keywords Wireless sensor networks, Cluster Head, Primal Cluster Head.

1. INTRODUCTION

   Recent advances in wireless communications and electronics have enabled the development of low-cost, low- power, multifunctional sensor nodes that are small in size and communicate in short distances. A wireless sensor network (WSN) is composed of a large number of sensor nodes that are deployed in ad hoc manner in an unreachable field to gives the end-user, the ability to instrument, observe, and react to events and phenomena in a specified environment. Wireless sensor networks provide unforeseen applications: from military applications such as battlefield mapping and target surveillance, to creating context-aware homes and health monitoring; the number of applications is endless [1]. In most of applications, sensors are required to detect events and then routes the collected information to a distant base station (BS) where parameters characterizing these events are estimated. Since the cost of transmitting information is higher than computation. Clustering sensors into groups, so that sensors communicate information only to cluster heads and then the cluster heads communicate the aggregated information to the processing center, saves energy [2], [3] [4]. Thus, it is advantageous to organize the sensors into clusters; where the data gathered and fused by the sensors are communicated to the BS through a hierarchy of cluster-heads.

   Fig. 1. Architecture of clustering method.

   The cluster-heads, which are elected periodically by certain clustering algorithms, aggregate the data of their cluster nodes and send it to the base station, from where the end-users can access the sensed data. Thus, only some nodes are required to transmit data over a long distance and the rest of the nodes will need to complete short distance transmission only. Therefore, more energy is saved and the overall network lifetime is extended.

   Based on LEACH protocol, we develop and validate a newest Improved LEACH algorithm called M-LEACH (Multi- Level LEACH). This protocol is proposed to increase the whole network lifetime on a homogenous network with a BS located far away from the sensing area, this by introducing a second hierarchical level of clustering and a new probability in cluster head selection based on residual energy of nodes, which improves and optimizes the use of the energy dissipated in the network like M-LEACH [4]. The use of two levels of clusters for transmitting data to the BS, leverages the advantages of small transmit distances and reduces the number of transmission data to the BS. As a consequence, fewer cluster heads are required to transmit far distances to the BS. This permits a better distribution of the energy load through the sensors in the network and increases the whole network lifetime.

   The remainder of this paper is organized as follows. Section II presents the related work. Section III exhibits the details and analyses the properties of M-LEACH. Section IV evaluates the performance of M-LEACH by simulations and compares it with LEACH. Finally, Section V gives concluding remarks.

2. RELATED WORKS

   The main goal of cluster-based routing protocol is to efficiently maintain the energy consumption of sensor nodes by involving them in multi-hop communication within a cluster and by performing data aggregation and fusion in order to decrease the number of transmitted messages to the sink and transmission distance of sensor nodes [6-8]. In this section, we make a few statements and assumptions about the network scheme and introduce the radio model used in this work.

   1. Homogeneous Network Model

      In this study, we describe the network model. Assume that there are N sensor nodes, which are uniformly dispersed within a M x M square region (Fig. 1). The nodes always have data to transmit to a base station, which is often far from the sensing area. The network is organized into a clustering hierarchy, and the cluster-heads execute fusion function to reduce correlated data produced by the sensor nodes within the clusters. The cluster-heads (Fig. 2) transmit the aggregated data to the base station directly. We assume that the nodes are stationary as supposed in [3].

      100

      90

      80

      70

      60

      50

      40

      30

      20

      180

      160

      140

      120

      100

      80

      60

      40

      20

      0

      0 10 20 30 40 50 60 70 80 90 100

      Fig. 3. Dynamic cluster structure by M-LEACH algorithm:

      (1)

      Where is the energy dissipated per bit to run the transmitter or the receiver circuit, and depend on the transmitter amplifier model used and d is the

      distance between the sender and the receiver. We have fixed the value of at 70 meters.

      10

      0

      0 10 20 30 40 50 60 70 80 90 100

      Fig. 2. 100 nodes randomly deployed in the network.

      Furthermore, we use in this study a similar energy model as proposed in [5]. According to the radio energy dissipation model illustrated in (Fig. 4), and in order to achieve an acceptable Signal-to-Noise Ratio (SNR) in transmitting an L- bit message over a distance d, the energy expended by the radio is given by :

      Fig. 4. First order radio model

   2. Problem speech

   Since in most WSN applications the energy source is a battery, energy plays an important role in WSN [7]. Therefore, preserving the consumed energy of each node is an important goal that must be considered when developing a routing protocol for WSNs. To increase the whole network lifetime, we have developed energy efficient clustering algorithms called M-LEACH. Based on a balanced way to elect networks clusters heads, we achieve a large reduction in the energy dissipation. In the next section, we describe our proposed algorithm in details.

3. MULTI-LEVEL LEACH

   A. Selecting a Template

   First, M-LEACH uses the same clustering algorithm as LEACH that is it uses the same strategy in Clusters Head selection, Clusters formation, and Schedule Creation (TDMA) but differs in Data transmission. its algorithm can be summarized as follow:

   Where are the residual and the initial energy respectively. is the cluster-head probability (see

   TABLE I) and is the number of onsecutive rounds in which a node has not been cluster-head within an epoch. When reaches the value the threshold is reset to the value it had before the inclusion of the remaining energy into

   the threshold-equation.

   YES

   CH Selection

   Aggregate Data

   Node i is NCH

   YES

   First Data aggregation(nodes)

   Second data

   NO

   Node is not PCH

   YES

   NO

   dtoBS>dtoPCH

   NO

   In each , when node finds it is eligible to be a cluster head, it will choose a random number between 0 and 1. If the number is less than , the node becomes a cluster head during the current round.

   Each node that has elected itself a cluster-head for the current round broadcasts an advertisement message to the rest of the nodes. For this cluster-head-advertisement phase, the cluster-heads use a CSMA MAC protocol, and all cluster- heads transmit their advertisement using the same transmit energy. The non-cluster-head nodes must keep their receivers on during this phase of set-up to hear the advertisements of all the cluster-head nodes. After this phase is complete, each non- cluster-head node decides the cluster to which it will belong for this round. This decision is based on the received signal strength of the advertisement. Assuming symmetric propagation channels, the cluster-head advertisement heard with the largest signal strength is the cluster-head to whom the minimum amount of transmitted energy is needed for communication. In the case of ties, a random cluster-head is chosen [8].

   Each non cluster heads sends its data during their allocated

   Send data to BS

   aggregation(CHs)

   Send to PCH

   Send to PCH Send to BS

   transmission time (TDMA) to the respective cluster head. The cluster head node must keep its receiver on in order to receive all the data from the nodes in the cluster. When all the data is received, the cluster head node performs signal processing functions to compress the data into a single signal. When this phase is completed, each cluster head can send the aggregated data to the BS. After that, each non cluster head can turn off the sleep mode

   Based on the information coordinates included on the

   Fig. 4. Flow-chart of M-LEACH Algorithm

   Furthermore, M-LEACH introduces two level hierarchical concept of clusters for transmitting data to the BS. Thus, it leverages the advantages of multi-hop transmission and reduces the disadvantages of single-hop transmission. In this way, fewer cluster heads, only PCH (Primal Cluster Heads) are required to transmit far distances to the BS. We consider a network with N nodes, uniformly distributed within M×M square region and that the network topology remains unchanged over time and the BS location is (x = 50, y = 175). In M-LEACH, We get the probability threshold, which each node uses to determine whether itself to become a cluster- head in each round, as follow:

   (2)

   message broadcasted, the CHs elected can select the Maximum Energy Cluster Heads which will be Primal Cluster Head PCH. Consequently, the CH with the important energy will be the PCH in this round. This last node collects all data coming from all CHs, compress it into a single signal and send it directly to the base station. We have chosen the PCH as intermediate hierarchical level, because the latter granted the transmission for long time. In fact, they have not waste energy in long transmission to the BS.

   Each non cluster heads sends its data during their allocated transmission time (TDMA) to the respective cluster head. The CH node must keep its receiver on in order to receive all the data from the nodes in the cluster. When all the data is received, the cluster head node performs signal processing functions to compress the data into a single signal. When this phase is completed, each cluster head can send the aggregated data to the PCH. After that, each non cluster head can turn off the sleep mode.

   Parameter	Value
   	5 nJ/bit
   	10 pJ/bit/
   	0.0013 pJ/bit/
   	0.5 J
   	5 nJ/bit/message
   	70 m
   Message size	4000 bits
   	0.1

   TABLE I. RADIO CHARACTERISTICS USED IN OUR SIMULATIONS

   30% better than LEACH. Secondly, we notice that the unstable time of LEACH is also larger than M-LEACH. It is because the advanced nodes die more slowly than normal nodes in LEACH. This metric is preferable to be narrow in order to give clear idea about time of reload or substitution of sensors to extend the network lifetime and avoid unreliable information from the sensing area.

   4

   x 10

   Number of messages received at the BS

   				LEACH M-LEACH

   3.5

   Initially, all the nodes need to know the initial energy and lifetime R of the network, which can be determined a priori.

4. SIMULATION RESULTS

In this section, we evaluate the performance of M-LEACH protocol using MATLAB. We consider a wireless sensor network with N = 100 nodes randomly distributed in a field. We assume the base station is far away

3

2.5

2

1.5

1

0.5

0

0 200 400 600 800 1000 1200

Time(Round)

from the sensing region. To compare the performance of M- LEACH with other protocols, we ignore the effect caused by signal collision and interference in the wireless channel. The radio parameters used in our simulations are shown in TABLE

I. We assume that all nodes know their location coordinates. The Base station is located far away from the sensing area. It was placed at location (x=50, y=175). We will consider following scenarios and examine several performance measures.

After deployment of WSN, the nodes consume energy during the course of the WSN lifetime. In fact, energy is removed whenever a node transmits or receives data and whenever it performs data aggregation using the radio parameters shown in TABLE I. Once a node runs out of energy, it is considered dead and can no longer transmit or receive data.

	LEACH M-LEACH

100

Number of nodes alive

80

60

40

20

0

0 200 400 600 800 1000 1200

Time(Round)

Fig. 5. LEACH vs M-LEACH in term of Number of nodes alive

It is obvious that the stable time of M-LEACH is large compared to that of LEACH Fig. 4 and 5. The stable time metric is important to be longer in the meaning that it enables the end user to have reliable information of the sensing area. This reliability is vital for sensitive natural disaster prevention application. Firstly, we see that M-LEACH performs in about

Fig. 6. LEACH vs M-LEACH: Number of messages received in BS.

V. CONCLUSION

We described M-LEACH, an energy-aware adaptive clustering protocol used in homogenous wireless sensor network. In M-LEACH, every sensor node elects itself independently as a cluster-head based on its initial energy and residual energy. In order control the energy expenditure of nodes by means of adaptive approach, it uses the average energy of the network as the reference energy. Thus, M- LEACH does not require a global knowledge of energy at every election round. Therefore, it uses the two hierarchical levels which offers a better use and optimization of the energy dissipated in the network. The introduced modifications enlarge and outperform better the performances of our proposed protocol than the others and can be extended by adding more hierarchical levels.

REFERENCES

1. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirici, A survey on sensor networks, IEEE communications magazine 40 (8) (2002)102 114.

2. V. Mhatre, C. Rosenberg, D. Kofman, R. Mazumdar, N. Shroff, Design of surveillance sensor grids with a lifetime constraint, in: 1st European Workshop on Wireless Sensor Networks (EWSN), Berlin, January 2004.

3. W.R. Heinzelman, A.P. Chandrakasan, H. Balakrishnan, Energy efficient communication protocol for wireless microsensor networks, in: Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS-33), January 2000.

4. A. A. Abbasi and M. Younis. A survey on clustering algorithms for wireless sensor networks. Computer Communication, 30(14-15):2826 2841, 2007

5. S. Lindsey, C.S. Raghavenda, PEGASIS: power efficient gathering in sensor information systems, in: Proceeding of the IEEE Aerospace Conference, Big Sky, Montana, March 2002.

6. O. Younis, S. Fahmy, HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks, IEEE Transactions on Mobile Computing 3 (4) (2004) 660669.

7. Dilip Kumar, Trilok C. Aseri, R.B. Patel, EEHC: Energy efficient heterogeneous clustered scheme for wireless sensor networks, elsevier, Computer Communications 32 (2009) 662667.

8. Georgios Smaragdakis, Ibrahim Matta, Azer Bestavros, SEP: A Stable Election Protocol for clustered heterogeneous wireless sensor networks, Technical Report BUCS-TR-2004-022.