1. Introduction
A wireless sensor network (WSN) connects autonomous systems to sensors that sense data, such as temperature, humidity, and light [1]. In a WSN environment, data are sent from a sensor node to a base station (BS), and vice versa. Sensor nodes transmit data directly to a BS, consuming large quantities of energy and rapidly depleting the energy supply of the node. Hierarchical routing protocols has been proposed to solve the problem of energy dissipation during the transmission and receiving of data. Nodes form clusters with one cluster head (CH) that has higher residual energy than other nodes. A CH is responsible for transmitting data to another CH or directly to the BS. The clustering system has the potential to increase the lifetime of the network. In the past, the methods commonly used in WSNs were enhanced simplified hybrid, energy-efficient, distributed clustering (EDsHEED) [2], low energy adaptive clustering hierarchy (LEACH) [3], distance and energy aware LEACH (DE-LEACH) [4], and energy aware LEACH (E-LEACH) [5].
The EDsHEED method [2] implements a CH for every cluster to minimize power consumption. The LEACH method [3] implements a protocol that utilizes randomized rotations of a local CH. By selecting CHs through a rotation, network disconnects caused by dead nodes are avoided. The weakness of this method lies in the random rotation it uses, which disregards the energy supply of a node in electing the CH [3]. It is possible to elect a node with low residual energy as a CH. As a result, the CH will not survive to perform its assigned role. The DE-LEACH [4] method uses the average distance from the base station (BS) as the basis for choosing threshold values. The DE-LEACH method divides the entire sensing region into two parts. The first region is one with a boundary of less than the average distance from the BS, and the second region is one whose distance is greater than the average distance from the BS. The first region will use distance as a parameter to elect CHs, and the second region uses a scheme based on the nodes’ residual and initial energy values.
The E-LEACH [5] method is another method that improves the LEACH algorithm in the CH election phase. The process of electing a CH assesses the energy residual of a node. E-LEACH uses two approaches to elect a CH. When the residual energy is more than 50%, the node will choose the same value as a threshold that is used in LEACH. When the residual energy drops to below 50%, the node will use another value as a threshold.
An E-LEACH [6] election of a CH is based on the node’s residual energy and its average energy use. However, in the E-LEACH operation, all selected CHs will directly transmit data to the BS. This activity consumes a great deal of energy [7].
Another approach has been proposed based on fuzzy logic using the K-means algorithm in combination with the midpoint method [8]. In addition to residual energy, the Euclidean distance can also be used as the basis for a CH consideration. In these cases, the packet transmission is performed from the CHs to the BS depending on the distance between them. There are two other methods already proposed, namely, the sparsity-aware energy efficient clustering (SEEC) [9] and the enhanced cluster formation technique accompanied by the fuzzy logic (EERRCUF) [10]. The SEEC method selects the strongest node in every cluster, while the EERRCUF method implements a super cluster head (SCH) as the middle hop to the BS.
The energy depletion caused by sending data from a CH to the BS affects the entire WSN operation. Since the energy used to send data from a CH to the BS is substantial, the node elected as a CH will run out of energy. If a node is frequently elected as a CH, it will die more rapidly than other nodes. As a result, the lifetime of the WSN will decrease.
This main research contribution of this paper is in improving E-LEACH and other methods’ performance by changing the data transmission mechanism from a CH to the BS. Instead of directly sending data to the BS, a CH will find the nearest neighboring CH to use as the next hop path to the BS. This paper consists of five sections: Section 1 outlines the background and the research problem. Section 2 discusses related works. The ME-LEACH algorithm is presented in Section 3. Section 4 provides an analysis of the experiments and the results. A conclusion is provided in Section 5.
2. Related Works
Many routing protocols have been developed to accommodate the WSN characteristics, in which energy is a crucial issue, such as hierarchical, flat, and location-based types [11]. Other types of routing protocols are data centric routings, such as SPIN [12] and directed diffusion [13]. There are also routing protocols for low power and lossy networks [14]. The nodes are aware of their locations through the use of signal strengths to predict the distance between nodes [51,16]. Other methods use a satellite with a GPS receiver. Geographical and energy aware routing (GEAR) [17] includes an algorithm that uses energy aware neighbor selection for routing packets to a destination region. Cluster-based routing was designed for scalability and efficient communication. The creation of clusters and selecting CHs can therefore increase the lifetime of a network [11].
Hierarchical routing is implemented to decrease the energy consumption within a cluster. Hierarchical routing also performs fusion and data aggregation. By lowering the energy used for data transmission, the total energy consumption in a WSN will decrease. Hierarchical routing usually uses two routing procedures. The first procedure is used to select a CH and then a member node, while the second procedure sends and aggregates data to the BS.
Since the energy capacity on a sender node is relatively limited [18], saving energy is an important factor in determining the life time of the sensor network. Many methods have been proposed to enhance the lifetime of a network. The first is LEACH [3] method, in which sensor nodes transmit data to a CH instead of sending it directly to the BS. The LEACH method became a foundational method among hierarchical routing protocols, and many improvements to the LEACH have been proposed. The LEACHC protocol is a LEACH improvement that utilizes location and residual energy parameters [3]. LEACHH [19] was introduced to solve the problem of low degrees in load balancing. The TL-LEACH protocol [20] is another variant used to solve the distance problem between CHs and BSs. CH data collection and fusion also use the LEACH protocol, but a CH will use another CH nearer to the BS. A power-efficient gathering in sensor information systems (PEGASIS) [7] is another protocol in which nodes connect only with their closest neighbor. Sensing node systems create transmission chains using a greedy algorithm to ensure that all nodes have paths to the base station. Another variant of LEACH is V-LEACH [21], which is highly energy efficient.
In another scheme, i.e., SEEC [9], the network is divided into several blocks, each of which has a strong node. Energy efficiency is achieved depending on the placement of a number of strong nodes at each level of heterogeneity. Another approach is to use the EERRCUF scheme [10]. Grouping of nodes is performed using the particle swarm optimization (PSO) method. In the system, an SCH is designated as the main CH. The SCH connects the CHs to the BS. Another advanced concept is the E-LEACH scheme, which uses the residual energy in a node as a parameter to elect a CH. The node with the highest energy is the selected CH. The other nodes receive advertisements from the selected CH to become cluster members. The transmission of node data uses a time division multiple access (TDMA) scheduling system.
There are many steps in E-LEACH, beginning with the set-up phase. In this step, all nodes compute a random number (between 0 to 1). This number is later compared to a threshold value. In the next step, the node calculates the percentage of the remaining energy against its initial energy to decide what threshold number to use. In the first round, the remaining energy is the same as the initial energy; hence, the value is 1. Otherwise, the node calculates the threshold value T as in [3]
where r is the current round between 0 and 1, P is the probability of a CH, n is a node, and G is a group of nodes that have not become CHs. When the comparison between the remaining energy and the initial energy is less than 50%, the node will use Eq. (2). E-LEACH uses a new CH election scheme to minimize the chance of a low energy node being selected as a CH. For the remaining energy of more than 50%, Eq. (1) is used. Otherwise, an equation is applied as in [3]
where T(n) is the threshold value, n is a node, p is the probability to become a CH, Eresidual is the remaining energy of a node, and Einitial is the initial energy of a node. When T(n) is larger than a random number (between 0 to 1), the node will become a CH.
Cluster formation begins when a CH broadcasts an advertising message to a neighboring node as an invitation to join its cluster. The advertising message consists of the location of the CH. When a candidate member node receives messages from the CH, it must decide which CH to choose. From the many advertisements received, the nodes starts to compare distances and subsequently joins the closest CH. The node will answer the advertisement with a joint request message, and thereafter, one cluster is formed. After clusters have been formed, each CH sends a time schedule using a TDMA scheme. All member nodes can transmit data based on this time schedule.
3. The New ME-LEACH Method
Previous research on E-LEACH has introduced a method for selecting a CH to conserve energy. ELEACH uses residual energy as a parameter to consider when to select the next CH. Simulations show that E-LEACH has an improved network lifetime compared to LEACH.
Fig. 1 shows that the topology of E-LEACH consists of a BS and many clusters, with a CH for every cluster. In E-LEACH, the algorithm is executed as follows: a new CH is selected by assessing the remaining energy of every node. A node with remaining energy higher than a certain value is more likely to become a CH. In the cluster formation phase, a node will join a CH that has a better cost value and hence the shortest distance to the CH. This CH will conduct a poll among all the member nodes and send data to the BS. The receiving as well as the transmitting of data consume much of the power of the CH. Every CH will transmit member node data to the BS.
Flow chart of the proposed ME-LEACH algorithm.
distance to the BS, as described in Fig. 2. The new main phases of the proposed method operate as follows: ME-LEACH uses a nearly optimal chain-based protocol between a CH and the BS. ME-LEACH aims to conserve energy. Each CH connects with the closest neighboring CH. Each CH takes turns transmitting to the BS and thus reduces the energy consumption per round. There are four required phases to implement the proposed method:
Select the nearest CH: This process takes place during the cluster formation phase when all the CHs exchange advertisement messages. A CH will keep all the advertisement messages it receives from CHs that contain the location of other CHs. The CH calculates the distance between it and other CHs and then sorts through the neighboring CHs based on distance. The nearest CH will become the candidate for the next hop.
Compare distances to the BS: The nearest neighboring CH does not automatically become the next hop; a CH will compare its distance to a neighboring CH and to the BS. If the distance of the neighboring CH to the BS is shorter than that to the CH, then the neighboring CH becomes the next hop. If the distance of the neighboring CH to the BS is longer than its distance, the CH will choose the next CH as the candidate. The process is repeated until the CH finds the best route to the BS.
Chain table formation: When Step 2 is complete, all CHs will have a chain table that consists of the next hop, and the member CH will use it to send data to the BS.
Send data to the BS: This process occurs in the data transmission phase when the member node has finished sending data to the CH. Then, the CH performs the task of forwarding the data to the BS instead of directly sending the data to the BS, and the CH will use the route in the chain table to send the data. The CHs may directly send the data to the BS or use another CH as the next hop. The route the CHs choose is the best route to conserve energy.
ME-LEACH uses a nearly optimal chain-based protocol between CHs and the BS. ME-LEACH aims to conserve energy. Each CH connects with the closest neighboring CH. Each CH takes turns transmitting to the BS and thus reduces the energy consumption per round. The idea is to modify the way a CH sends data instead of transmitting data directly to the BS. A CH will transmit data to the nearest CH if the distance of the CH is shorter than that to the BS. The proposed topology is shown in Fig. 3.
Modified E-LEACH (ME-LEACH) topology.
CH chain formation is performed at the same time as cluster formation. When the CHs broadcasts advertisements about their existence, the advertisement is not only received by the member nodes but also by other CHs. There are advertisement exchanges between CHs. When CHs receive multiple advertisements from other CHs, they begin to calculate and compare their distances to the base station.
The CHs will choose another CH to become the next hop if the distance to the other CH is shorter than that to the BS. After finding a CH candidate to become the next hop, the CHs send a joint request to the preferred CH. The CHs begin to fill the chain table with the next hop CH and the source CH. All the CHs will complete the chain table and ensure there are no loops in the chain.
Fig. 2 shows the proposed ME-LEACH method. The process with the white background is based on E-LEACH, and the process with the blue background is the proposed method, ME-LEACH.
The following is the ME-LEACH pseudocode method. The difference between the proposed method and the previous method lies in the //Proposed Scheme section. In this subprocess, the next hop is chosen from one CH to the nearest CH. This is a new distinct method compared to the previous method.
ME-LEACH Algorithm (pseudocode)
4. Performance Analysis
4.1 Simulation Scenarios
Scenario 1 consists of several phases: the set-up phase: all the nodes are placed randomly in the monitored area of 100 m2. All the nodes are known by their location, initial energy and base station positions. After all the sensor nodes are set, they are ready for the first step of the simulation. First, the sensor nodes check their residual energy and compare it to the initial energy. The value is 1 if the residual energy is the same as the initial energy. After many rounds, the energy will be dispatched, and when the ratio of the residual and initial energy is under 50%, the sensor nodes will use Eq. (2) as their threshold value. In this case, a sensor node will use a quotation as in 1 as its threshold. The threshold value is calculated.
The next step is CH election. The nodes compare the threshold numbers to the generated random numbers (between 0 and 1). The nodes decide, autonomously, to become CHs based on the comparison between the threshold value and a random number. If the random number is lower than the threshold, then the corresponding sensor node will declare itself as a CH.
After the CH is selected, the next step is the cluster set-up. The CH broadcasts an advertising message that it is a CH to its neighbor. The broadcast message contains its location. In this step, all sensors will activate their radios to listen to the broadcast message. After the sensor node receives the broadcast messages, which usually come from many CHs, they will perform a calculation to determine which CH is the nearest since distance is a major factor in energy dissipation.
The nearest cluster will conserve energy. When the sensor node has already selected which CH has the shortest distance, it will send a joint request message to the corresponding CH and join the cluster. In this step, a cluster is set-up. Every cluster has one CH and some member nodes. A member node is optional. There are cases in which the CH does not have any members. For example, there are situations in which there is not any closer nodes or when all the nodes have become CHs.
Schedule creation occurs when a joint request message is received by a CH. The CH will send a TDMA schedule to a member node as a response. The schedule will tell the member node when to wake the transceiver to send data and when to sleep. To conserve energy, the member node will be in the sleep state and will awake only when it is time to send data. A schedule also tells the member node when the round ends and when to start a new round.
Data transmission is also known as the operation phase. When a cluster is set up and the all sensor nodes are known, it becomes a CH or a member node. The member node will send data to its CH according to the schedule, and the CH will forward the aggregate information to the BS. The first round is finished, and the next round will start over for the process of CH selection.
Scenario 2 runs in reference to the Modified E-LEACH, with the following steps. The set-up and CH selection in Experiment 2 have the same processes as those in Experiment 1. Modifications are made in the cluster set-up phase and in the schedule creation.
In the cluster set-up phase, the CH also listens to an advertised message broadcast sent from another CH. The objective is to conserve energy. This is the same process that happens when a CH sends a broadcast. In the previous method, the advertisement is only received by a non-CH, while in the proposed method, the broadcast is also received by another CH. Thus, the CH receives the location of the advertisement and then calculates whether it is better to send data directly to the BS or to send, based on its distance, to the nearest neighboring CH.
After the CHs exchange advertisement messages and make decisions on how they will send information to the BS, the chain formation phase can be implemented to decide the way the CHs will send the information. A CH can send data directly to the BS or to the nearest CH based on distance. To avoid looping, the CH should not send data to another CH already in the chain.
In the schedule creation phase, it is not only the member node that will activate its receiver but also another CH, which will make the previous cluster its next hop. The CH will send its data to other CHs when it finishes collecting the data from the member nodes.
In this experiment, we used three parameters to measure the performance of the system, namely, the energy used, throughput and network lifetime. The energy used is the total energy used by all the nodes, the throughput is the amount of data that is passed on the network per time unit, and the network lifetime is time needed until there is no live node in the network.
4.2 Simulation Results and Analysis
There are many tasks that consume the energy of sensor nodes, as shown in Experiments 1 and 2. Transmitting and receiving data are the main tasks that consume great quantities energy as well as the signal control advertisements and the joint request tasks for both the previous and the proposed methods. In this experiment, we use 100 sensor nodes placed in [TeX:] $$1,000 \times 1,000 \mathrm{m}^{2}$$ size areas, as shown in Fig. 4. The distribution of the nodes could be application dependent or self-organizing. The parameters are grouped based on the methods to be compared. The throughput and time to the first node die, half node die, and all nodes die parameters are used to compare the SEEC, EERRCUF and ME-LEACH methods. Meanwhile, the total network lifetime is used in the comparison of the E-LEACH and the ME-LEACH methods.
Based on the experiment, it was found that the consumption of power under the ME-LEACH method is better than that of the EERRCUF and SEEC algorithms. Fig. 5(a) shows that in ME-LEACH, the first node dies after 25 seconds; in comparison, the first node dies after 16 seconds and 7 seconds in EERRCUF and SEEC, respectively. The time until the last node dies in ME-LEACH is better than that of EERRCUF and SECC.
The duration since the first sensor node’s death to the time of half of the node’s deaths shows the stability of the WSN algorithm. The WSN algorithm improves the stability of the network. Fig. 5(b) shows the half nodes in SEEC, EERRCUF, and ME-LEACH that die first after 17, 36, and 55 seconds, respectively, which indicates that ME-LEACH survives for a much longer time than SEEC and EERRCUF.
In ME-LEACH, the duration since the first node’s death to the half node’s death is 30 seconds, whereas in SEEC and EERRCUF, this time is 10 and 20 seconds, respectively. These results show that the MELEACH scheme on the WSN is more stable than the SEEC and EERRCUF schemes.
Fig. 5(c) shows that the network lifetime for the ME-LEACH method is 63 seconds, whereas the network lifetime under EERRCUF is 49 seconds. This result shows the stability of the proposed method compared to the EERRCUF method.
The total energy consumption is measured for both the proposed and the previous methods. The results show that energy consumption gradually increases for all the schemes. Fig. 6 shows that the ME-LEACH protocol consumes less energy than the SEEC protocol and slightly more than the EERRCUF protocol. Thus, the network lifetime increases when the ME-LEACH protocol is utilized in a WSN.
Comparison between methods: (a) the first node dies over time, (b) half the nodes die over time, and (c) all the nodes die over time.
Energy consumption over time.
The efficiency of the system is measured by throughput, which is the amount of data delivered to the BS in bits per second. The throughput will decrease as the simulation time increases. Fig. 7 shows the higher throughput of a WSN using a ME-LEACH protocol than the other approaches.
The second test was conducted to compare the E-LEACH and ME-LEACH methods. The parameters of the first node die and network lifetime are used to compare the two methods.
Fig. 8 shows that the lifetime of the sensor nodes using ME-LEACH are longer than that of E-LEACH. In E-LEACH, the first node dies in round 211, and all the nodes are dead in round 925. In ME-LEACH, the first node dies in round 440, and all the nodes are dead in round 1394. Using the proposed method (ME-LEACH) applied to a WSN network with 100 nodes, the network lifetime was increased significantly compared to E-LEACH.
This fact shows that ME-LEACH has effectively increased the lifetime of the network. This achievement is very important because energy efficiency is a critical issue in a WSN.
The ME-LEACH method compared to the E-LEACH method for the network lifetime of 100 nodes.
4.3 Summary of Findings
In this paper, we have analyzed and improved the SEEC, EERRCUF, and E-LEACH algorithms. ELEACH has weaknesses in the way that the CHs send data to the BS. Since distance is a major factor in energy usage calculations, it would be beneficial to find ways to shorten the distance of data transmission. The proposed method changes the way the CHs send data to the BS. A CH will find another nearest CH with a shorter distance to the BS as its next hop. Shorter distances means less energy is required to transmit data.
By running Experiment 1 using E-LEACH and then comparing the results to the SEEC and EERRCUF protocols and making comparisons to Experiment 2, we find that:
1. The ME-LEACH method is more stable than SEEC and EERRCUF based on the first, half and all nodes die-over-time parameters.
2. The ME-LEACH method has a higher throughput than SEEC and EERRCUF.
3. The E-LEACH method of sending information from a CH to the base station still uses a large amount of energy, but the proposed method can conserve the energy used in sending information. In the previous method, after receiving data from a member node, a CH aggregates the data and then directly sends the data to the BS. The proposed method changes this process by using a CH as its next hop to the BS. A simulation shows that a selected round using a chain formation uses 0.00708 J of energy, while the previous method uses 0.04757 J of energy. This result means that the proposed method conserves -0.0405 J by changing the way a CH sends its information to the BS.
4. In the previous method, the first node died after 211 rounds, while in the proposed method, the first node died after 440 rounds. There is a 108.53% improvement in rounds until first death using the proposed method. This improvement is because the energy usage is distributed more evenly in the proposed method by conserving the energy usage of the CH.
5. The average lifetime of a wireless sensor network is increased by 35.2% compared to that of the previous method. In E-LEACH, all nodes die after 925 rounds, and in the proposed method, all nodes die after 1394 rounds.
By using two hops or more to send data from a member node to the BS, there are delays before the data are received by the BS. The delay from the member node to the CH occurs because CHs must wait until all the data from their member nodes are received before aggregating and sending the data to the BS or another CH as the next hop. Another delay occurs in the process of sending data between a CH in the chain formation as a path to the BS.
5. Conclusions
We have proposed the ME-LEACH algorithm, which consumes less energy than the SEEC, EERRCUF, and E-LEACH methods. The ME-LEACH method is more stable than SEEC and EERRCUF based on the first node die-, half node die-, and all node die-over-time parameters, and it has a higher throughput than the other methods. The E-LEACH protocol consumes relatively high quantities of energy when sending data from a CH to the BS. More than one node that becomes a CH that transmits node data to the BS in ME-LEACH. Additionally, ME-LEACH consumes less energy than the other methods because it uses a chain formation to send the data to the BS. Only the nearest CH node to the BS transmits the node data. In each round, ME-LEACH uses less energy than E-LEACH. There is only one CH that communicates with the BS. Through the energy conserved by using the CH chain formation among the CHs, the lifetime of the WSN increases when sending data to the base station. When we can decrease the energy usage by a CH, the CH has a higher probability of living longer. The experiment shows that the use of chain formation can decrease energy consumption in the transmitting and receiving of data, distributing energy more evenly among nodes and increasing the lifetime of the WSN by 35.2% compared to the previous E-LEACH method. There are many methods for clustering, such as the mean-shift, density-based spatial, and agglomerative hierarchical clustering methods. These methods have also been considered for obtaining more efficient power consumptions on WSNs.
Acknowledgement
The authors would like to thank Telkom University and the School of Computing for the financial and facilities support that allowed the completion of this research and its publication. Additionally, the authors would like to thank Dr. Khoirul Anwar and the AdWitech research center for their support as the first reviewers of this paper.