pp 27- 31
Pramod Sharma
Professor, Department of ECE, JIEM, Jaipur.
erpramodsharma@gmail.com
applications such as industrial process monitoring and control, environment and habitat monitoring, machine health monitoring, home automation, health care applications, nuclear reactor control, fire detection, object tracking and traffic control. Energy utilization and network life time are key issues in design of routing proto- cols for Wireless sensor network. LEACH is the first clustering routing protocol which is proven to be better compared to other such algorithms. TL-LEACH is one of the descendants of LEACH that saves better the energy consumption by building a two-level hierarchy. It uses random rotation of local cluster base stations to better distribute the energy load among the sensors in the network especially when the density of network is higher.
Key Words: WSN, LEACH, TL-LEACH.
- INTRODUCTION
LEACH (Low-Energy Adaptive Clustering Hierarchy) is the first clustering routing protocol which is proven to be better compared to other clustering algorithms. It is a distributed clustering algorithm, first proposed in 2000 by W. R. Heinzelman et al. [1]. The authors have suggested a hierarchical adaptive approach in which CHs are selected with a random probability independent of others to organize the nodes into clusters. TL-LEACH is one of the descendants of LEACH proposed by V. Loscri et al. in the year 2005[2], which introduces a two level hierarchy for cluster formation. It uses random rotation of local cluster base stations to better distribute the energy load among the sensors in the network, especially when the density of network is higher. As the clusters are adaptive in LEACH and TL-LEACH, poor clustering set-up during a round will affect overall performance. However, using a central control scheme for cluster set-up may produce better clusters by distributing the cluster head nodes throughout the network. In 2007 Taewook Kang et al. [3] proposed a centralized clustering algorithm, LEACH-C that realizes the above idea and provides better results through uniform distribution of CHs avoiding their redundant creation of in a small area. The main objectives of LEACH, was to find a way to low consumption of energy in the cluster and to improve the life time of WSN. EACH adopts a hierarchical and adaptive approach to organize the network into a set of clusters, managed by selected CHs. The CH carries out multiple tasks, such as periodic collection of data from the members of the cluster, aggregation of data to remove redundancy among correlated values, transmission of the aggregated data directly to the base station through a single hop method, creation and advertisement of a TDMA schedule. In the schedule created by the CH, each node of the cluster is assigned a time slot that can be used by non-CH nodes for transmission. The CHs broadcast the schedule to their corresponding cluster members. For reducing the likelihood of collisions among sensor nodes, LEACH nodes use a code division multiple accesses (CDMA) based scheme for communication. The network model used by LEACH is depicted in Figure1.
Figure 1: A Network Model of LEACH
Figure 2: Two Phases of LEACH
- OPERATIONS OF LEACH
The basic operation of LEACH consists of many rounds, each round being divided into two phases. The phases of LEACH are illustrated in Figure 2. The first phase called the setup phase consists of three steps,
(i) Cluster head advertisement,
(ii) Cluster set-up and
(iii) Transmission schedule creation.
The second phase, the steady-state phase, focuses on,
- Data transmission to cluster heads,
- Signal processing (data aggregation/ fusion) and
- Delivery to the base station.
To minimize the protocol overhead, the duration of the setup phase is assumed to be relatively shorter than the steady-state phase. At the beginning of the setup phase, cluster-head selection takes place. The role of CH rotates among sensor nodes, thereby distributing energy consumption evenly across the network nodes. To determine if it is its turn to become a CH, a node n, generates a random number x (between 0 and 1), and compares it with the CH selection threshold T(n).
The node becomes a CH if it’s generated value, x, is less than T (n). The CH selection threshold, T (n) is aimed to ensure with high possibility that a predetermined fraction of nodes, P, should be elected as CHs at each round. Further, the threshold ensures that the nodes, those have been CHs in last 1/P rounds, will not again be selected in the current round. At the completion of the CH selection process, every node that is selected as a CH, advertises its new role to the rest of the network. Upon receiving the advertisements, each remaining node selects a cluster to join based on the received signal strength. Then the nodes inform their corresponding CHs of their desire to become a member of the cluster. Once the cluster is formed, each CH creates and distributes a TDMA schedule that specifies the time slots allocated to each member of the cluster for transmission. CHs also select CDMA code so as to reduce inter-cluster interference, which is then distributed to all members of its cluster [4].
The completion of the setup phase signals the start of the steady-state phase. In this phase, nodes collect the required data and use their allocated slots to transmit those to the CH. Data collection is performed periodically. Then, the CH nodes receive all the data; aggregate them before sending to the base-station. The network goes back into the setup phase after a certain time, which is determined a priori.
Advantages and Drawbacks of LEACH:
Major advantages of LEACH include,
- It incorporates data fusion into routing protocol.
- It is 4-8 times effective over direct communication in prolonging the network lifetime.
Some drawbacks of LEACH are
- It may lead to large number of clusters.
- CHs are un-uniformly distributed in the network.
- There is less number of data signals received at BS.
- TL-LEACH
The main objectives of TL-LEACH was to find a way to minimize the consumption of energy than LEACH and hence to improve the life time of WSN.TL-LEACH uses the concept of data-fusion rigorously through a two-level hierarchy in order to avoid the overloading of data. Large energy gain can be resulted from data fusion, as less data is needed to be transmitted to the base station. TL-LEACH uses the following techniques to realise energy and latency efficiency: Randomized, adaptive and self-configuring cluster formation, Localized control for data transfer.
TL-LEACH introduces a two-level hierarchy: a top level represented by cluster- head called primary cluster-head or master cluster head (MCH), a second level represented by secondary cluster-head or CH and simple nodes.The two-level hierarchy of TL-LEACH is shown in the Figure 3. In TL-LEACH, a partial local computation starts in each secondary CH and completes at primary CHs at the top level, from where data is transmitted to the base station directly.
Figure 3: A Network Model of TL-LEACH
As LEACH, the basic operation of TL-LEACH consists of many rounds, each round being divided into two phases. In the setup phase initially each node decides if it wants to be, in current round, primary cluster-head (MCH), secondary cluster-head (CH) or simple node. A node that has elected itself as MCH has to advertise other nodes. The mechanism used in this phase is the CSMA. Subsequently CHs send the advertisement to the simple nodes. In the cluster set-up step each CH decides which primary cluster it belongs to and each simple node decides its secondary cluster based on the received signal strength of advertisement, and both confirm their joining. A MCH knows which nodes are in its group and creates a TDMA schedule, assigning each node a slot to transmit. It also chooses a CDMA code and informs all the nodes at the second level in its group to transmit using this code. Each CH transmits the information to nodes in its cluster, both the code to be used use to transmit and the schedule. In the steady-state phase, each node transmits according to the TDMA schedule decided by its corresponding primary CH. Non-CH nodes transmit data to their respective secondary cluster heads. CHs retransmit the aggregate data to their respective primary cluster heads. MCHs forward the fused data to the Base Station.
Advantages and Drawbacks of TL-LEACH:
Major advantages of TL-LEACH, include
- The use of two-levels of clusters for data transmissions is advantageous as compared to LEACH because of the small transmit distances for more nodes. In this way only a few nodes are required to transmit through a long distances to the base station.
- It incorporates improved data aggregation and fusion than LEACH.
- Number of primary clusters in TL-LEACH is less, so it can be applied for larger networks.
Major drawbacks of TL-LEACH include,
- It may lead to non-uniform distribution of CHs in the network.
- of cluster heads formed in each round are not uniform, which may otherwise have increased the network lifetime to some extent.
- LEACH-C
The main objectives of LEACH-C was to produce better performance in terms of energy consumption, by dispersing the cluster heads throughout the network and hence to improve the life time of WSN. LEACH is distributed cluster formation algorithm, which offers no guarantee about the placement and number of cluster head nodes. LEACH-centralized is a protocol that uses a centralized clustering algorithm for cluster set-up and the same steady-state phase as LEACH [5, 3]. Leach-C tries to avoid redundant creation of cluster heads in a small area. It attempts to minimize the amount of energy for the ordinary nodes to transmit their data to the cluster head.
As LEACH and TL-LEACH, the basic operation of LEACH-C consists of many rounds, each round being divided into two phases. In the set-up phase of LEACH-C, information about a node’s current location and residual energy level is sent to the BS [5]. The BS ensures better distribution of en- erg load among all the nodes, in addition to determining good clusters. To do this, BS computes the average energy of nodes, and determines the nodes having energy above this average as candidates for CH. BS selects CHs from the candidate nodes in a random basis such that a CH does not lie inside a predefined radius of any other CH [3].
In the CH selection process shown in Figure 4 (a), node a, b, c, and d are elected for candidate nodes for CHs among the sensor nodes. First, the BS selects node a as CH. As node b is within radius r of a, it is ruled out of the qualification of candidate nodes. Similarly, node d is also ruled out of the qualification. As a result, node a and c are actually selected as CHs as shown in Figure 4(b).
This approach does not find the optimal clusters but one of the beneficial parts is the computation, which is not NP-hard anymore as in conventional LEACH-C .Once the CHs and associated clusters are found, the BS broadcasts a message that contains the CH ID for each node. If the node ID matches with the CH ID, then it becomes a cluster head; otherwise the node determines its TDMA slot for data transmission, from the TDMA schedule and goes to sleep until it’s time to transmit data.
The steady-state phase of LEACH-C is identical to that of the LEACH protocol, i.e. The nodes collect data and send them to their CHs during the TDMA slot allocated, where the data are aggregated or diffused
Figure 4: Basic Concept Used in LEACH-C for CH Selection mitted to the BS.
Major advantages of LEACH-C include,
- CHs are evenly distributed among the nodes in the network.
- of cluster heads formed in each round are almost uniform, which results in more number of nodes being alive till the end of the network lifetime.
- Life time of network will be more compared to LEACH.
LEACH-C has also a drawback of being a single hop protocol that will not be able to provide more data aggregation and fusion. And hence BS may receive more number of redundant data causing wastage of energy.
REFERENCE
- R.Heinzelman, A.P.Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless micro sensor networks. In Proceedings of the 33rd Hawaii International Conference on System Sciences, volume 8, pages 8020–8029, Washington, DC, USA, 2000. IEEE Computer Society.
- Loscri, G. Moabite, and S. Marino. A two-level hierarchy for low-energy adaptive clustering hierarchy (tl-leach). In Vehicular Technology Conference. 2005 IEEE 62nd, volume 3, pages1809–1813, 2005.
- Taewook Kang, Jangkyu Yun, Hoseung Lee, Icksoo Lee, Hyunsook Kim, Byunghwa Lee, Byeongjik Lee, and Kijun A clustering method for energy efficient routing in wireless sensor networks. In Proceedings of the 6th WSEAS International Conference on Electronics, Hardware, Wireless and Optical Communications, EHAC’07, pages 133–138, Stevens Point, Wisconsin, USA, 2007. World Scientific and Engineering Academy and Society (WSEAS).
- Shrubby, D. Minoli, and T. Znati. Wireless Sensor Networks: Technology Protocols and Applications. Wiley, 2007.
- R. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan. An application specific protocol architecture for wireless microsensor networks. Wireless Communications, IEEE Transactions on, 1(4):660–670, 2002.