Leach protocol Description

W.Heinzelman, introduced a hierarchical clustering algorithm for sensor networks, called Low Energy Adaptive Clustering Hierarchy (LEACH). LEACH arranges the nodes in the network into small clusters and chooses one of them as the cluster-head. Node first senses its target and then sends the relevant information to its cluster-head. Then the cluster head aggregates and compresses the information received from all the nodes and sends it to the base station. The nodes chosen as the cluster head drain out more energy as compared to the other nodes as it is required to send data to the base station which may be far located. Hence LEACH uses random rotation of the nodes required to be the cluster-heads to evenly distribute energy consumption in the network. After a number of simulations by the author, it was found that only 5 percent of the total number of nodes needs to act as the cluster-heads. TDMA/CDMA MAC is used to reduce inter-cluster and intra-cluster collisions. This protocol is used were a constant monitoring by the sensor nodes are required as data collection is centralized (at the base station) and is performed periodically.

                                      

 OPERATION

LEACH operations can be divided into two phases:-

1. Setup phase

2. Steady phase

In the setup phase, the clusters are formed and a cluster-head is chosen for each cluster. While in the steady phase, data is sensed and sent to the central base station. The steady phase is longer than the setup phase. This is done in order to minimize the overhead cost.

2.2.1. Setup phase :-

 During the setup phase, a predetermined fraction of nodes, p, choose themselves as cluster-heads. This is done according to a threshold value, T(n). The threshold value depends upon the desired percentage to become a cluster-head- p, the current round r, and the set of nodes that have not become the cluster-head in the last 1/p rounds, which is denoted by G. The formulae is as follows :

T(n) = p/1-p[r mod(1/p)] if n E G

T(n) = 0 otherwise

Every node wanting to be the cluster-head chooses a value, between 0 and 1. If this random number is less than the threshold value, T(n), then the node becomes the cluster-head for the current round. Then each elected CH broadcasts an advertisement message to the rest of the nodes in the network to invite them to join their clusters. Based upon the strength of the advertisement signal, the non-cluster head nodes decide to join the clusters. The non-cluster head nodes then informs their respective cluster heads that they will be under their cluster by sending an acknowledgement message. After receiving the acknowledgement message, depending upon the number of nodes under their cluster and the type of information required by the system (in which the WSN is setup), the cluster heads creates a TDMA schedule and assigns each node a time slot in which it can transmit the sensed data. The TDMA schedule is broadcasted  to all the cluster-members. If the size of any cluster becomes too large, the cluster head may choose another cluster- head for its cluster. The cluster-head chosen for the current round cannot again become the cluster-head until all the other nodes in the network haven't become the cluster-head.

Steady phase :-

During the steady phase, the sensor nodes i.e. the non-cluster head nodes starts sensing data and sends it to their cluster-head according to the TDMA schedule. The cluster-head node, after receiving data from all the member nodes, aggregates it and then sends it to the base-station.

After a certain time, which is determined a priori, the network again goes back into the setup phase and new cluster-heads are chosen. Each cluster communicates using different CDMA codes in order to reduce interference from nodes belonging to other clusters.